数据结构实验指导书学生版

LIAOCHENGUNIVERSITY数据结构实验指导书聊城大学计算机学院2015年9月《数据结构》课程实验指导书I目录实验一线性表...........................................1基本信息........................................................1实验预习........................................................1实验过程........................................................1实验数据和实验结果记录.........................................11实验结果分析...................................................12实验二栈和队列........................................12基本信息.......................................................12实验预习.......................................................12实验过程.......................................................13实验数据和实验结果记录.........................................16实验结果分析...................................................17实验三二叉树..........................................17基本信息.......................................................17实验预习.......................................................18实验过程.......................................................18实验数据和实验结果记录.........................................20实验结果分析...................................................20实验四查找............................................21基本信息.......................................................21实验预习.......................................................21实验过程.......................................................21实验数据和实验结果记录.........................................22实验结果分析...................................................23《数据结构》课程实验指导书1实验一线性表基本信息实验课程：数据结构设课形式：非独立课程学分：4实验项目：线性表项目类型：设计项目学时：4实验预习实验目的和要求：1、熟悉C语言集成开发环境；2、会定义线性表的顺序结构和链式结构；3、熟悉对线性表的基本操作，如插入、删除等。实验内容和原理或涉及的知识点：自己编写程序实现线性表的建立、插入、删除等功能。实验条件：具有C语言集成开发环境的计算机实验设计方案：设计的顺序表算法有：1、初始化顺序表；2、顺序表的插入操作；3、顺序表的删除操作。设计的链表算法有：1、建立链表；2、链表的插入操作；3、链表的删除操作；4、链表数据元素的访问。实验过程1、根据实验预习阶段的实验设计方案，顺序表算法伪C代码如下。typedefstruct《数据结构》课程实验指导书2{ElemType*elem;intlength;intlistsize;}SqList;statusInitList(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}statusListInsert_Sq(SqList&L,inti,ElemTypee){if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;L.length++;returnOK;}statusListDelete_Sq(SqList&L,inti,ElemType&e){if((i1)||iL.length)returnERROR;p=&L.elem[i-1];e=*p;q=L.elem+L.length-1;for(++p;p=q;++p)*(p-1)=*p;--L.length;returnOK;}//ListDelete_Sq2、将算法细化为程序代码如下。《数据结构》课程实验指导书3#includestdio.h#includestdlib.h#defineOK1#defineERROR0#defineOVERFLOW-2#defineLISTINCREMENT10#defineLIST_INIT_SIZE20typedefintstatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;statusInitList(SqList*L);//构造一个空的线性表statusListInsert_Sq(SqList*L,inti,ElemTypee);//在L中第i个位置之前插入e，L长度加1statusListDelete_Sq(SqList*L,inti,ElemType*e);//删除L的第i个数据元素，并用e返回其值，L长度减1voidvisit(ElemTypee);//打印e的值到显示器voidListTraverse(SqListL,voidvisit(ElemType));//依次对L的每个元素调用函数visit(ElemType)intmain(){inti,j;SqListL;InitList(&L);puts(Pleaseinput6numbertoinitilizelinkedlist:);for(i=1;i=6;i++){scanf(%d,&j);ListInsert_Sq(&L,i,j);}puts(Thelinkedlistis:);ListTraverse(L,visit);puts(Pleaseinputaelementtoinsert:);scanf(%d,&i);puts(Pleaseinputthepositiontoinsert:);scanf(%d,&j);《数据结构》课程实验指导书4ListInsert_Sq(&L,j,i);puts(Afterinsert,thelinkedlistis:);ListTraverse(L,visit);puts(Pleaseinputthepositiontodelete:);scanf(%d,&i);ListDelete_Sq(&L,i,&j);puts(Afterdelete,thelinkedlistis:);ListTraverse(L,visit);printf(Thedeletedelementis:%d\n,j);return0;}statusInitList(SqList*L){L-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L-elem)exit(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;returnOK;}statusListInsert_Sq(SqList*L,inti,ElemTypee){if(i1||iL-length+1)returnERROR;if(L-length=L-listsize){ElemType*newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L-elem=newbase;L-listsize+=LISTINCREMENT;}ElemType*p,*q=&(L-elem[i-1]);for(p=&(L-elem[L-length-1]);p=q;--p)*(p+1)=*p;*q=e;L-length++;returnOK;}《数据结构》课程实验指导书5statusListDelete_Sq(SqList*L,inti,ElemType*e){if(i1||iL-length)returnERROR;ElemType*p=&L-elem[i-1];*e=*p;ElemType*q=L-elem+L-length-1;for(++p;p=q;++p)*(p-1)=*p;L-length--;returnOK;}voidvisit(ElemTypee){printf(%d\t,e);}voidListTraverse(SqListL,voidvisit(ElemType)){inti;for(i=0;iL.length;i++)visit(L.elem[i]);putchar('\n');}3、编译、链接、运行程序。4、链表伪C代码如下：typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*Linklist;statusCreateList_L(Linklist&L,intn){L=(Linklist)malloc(sizeof(Lnode));L-next=NULL;for(i=n;i0;--i){《数据结构》课程实验指导书6p=(Linklist)malloc(sizeof(Lnode));scanf(%d,&p-data);p-next=L-next;L-next=p;}returnOK;}//createList_L/*或者用下面的尾插法statusCreateList_L(Linklist&L,intn){Linklistr;L=(Linklist)malloc(sizeof(LNode));L-next=NULL;r=L;for(i=1;i=n;++i){p=(Linklist)malloc(sizeof(LNode));scanf(%d,&p-data);r-next=p;r=p;};r-next=NULL