《数据结构》(C语言版)严蔚敏著_数据结构实验指导

1《数据结构》实验指导及报告书（2014）/学年第1学期姓名：胡汜亮学号：班级：指导教师：2实验一顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。二、实验预习说明以下概念1、线性表：2、顺序表：3、链表：三、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#includestdio.h#includemalloc.h#defineERROR0#defineOK1#defineINIT_SIZE5/*初始分配的顺序表长度*/#defineINCREM5/*溢出时，顺序表长度的增量*/typedefintElemType;/*定义表元素的类型*/typedefstructSqlist{ElemType*slist;/*存储空间的基地址*/intlength;/*顺序表的当前长度*/intlistsize;/*当前分配的存储空间*/}Sqlist;intInitList_sq(Sqlist*L);/**/intCreateList_sq(Sqlist*L,intn);/**/intListInsert_sq(Sqlist*L,inti,ElemTypee);/**/intPrintList_sq(Sqlist*L);/*输出顺序表的元素*/intListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/intListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/3intInitList_sq(Sqlist*L){L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L-slist)returnERROR;L-length=0;L-listsize=INIT_SIZE;returnOK;}/*InitList*/intCreateList_sq(Sqlist*L,intn){ElemTypee;inti;for(i=0;in;i++){printf(inputdata%d,i+1);scanf(%d,&e);if(!ListInsert_sq(L,i+1,e))returnERROR;}returnOK;}/*CreateList*//*输出顺序表中的元素*/intPrintList_sq(Sqlist*L){inti;for(i=1;i=L-length;i++)printf(%5d,L-slist[i-1]);returnOK;}/*PrintList*/intListInsert_sq(Sqlist*L,inti,ElemTypee){intk;if(i1||iL-length+1)returnERROR;if(L-length=L-listsize){L-slist=(ElemType*)realloc(L-slist,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L-slist)returnERROR;L-listsize+=INCREM;}for(k=L-length-1;k=i-1;k--){L-slist[k+1]=L-slist[k];}L-slist[i-1]=e;4L-length++;returnOK;}/*ListInsert*//*在顺序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti){}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){}intmain(){Sqlistsl;intn,m,k;printf(pleaseinputn:);/*输入顺序表的元素个数*/scanf(%d,&n);if(n0){printf(\n1-CreateSqlist:\n);InitList_sq(&sl);CreateList_sq(&sl,n);printf(\n2-PrintSqlist:\n);PrintList_sq(&sl);printf(\npleaseinputinsertlocationanddata:(location,data)\n);scanf(%d,%d,&m,&k);ListInsert_sq(&sl,m,k);printf(\n3-PrintSqlist:\n);PrintList_sq(&sl);printf(\n);}elseprintf(ERROR);return0;}运行结果算法分析52、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：运行结果算法分析查找算法代码：运行结果算法分析63、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#includestdio.h#includemalloc.h#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/**/voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/intGetElem(LinkListL,inti,ElemType*e);/**/LinkListCreateList(intn){LNode*p,*q,*head;inti;head=(LinkList)malloc(sizeof(LNode));head-next=NULL;p=head;for(i=0;in;i++){q=(LinkList)malloc(sizeof(LNode));printf(inputdata%i:,i+1);scanf(%d,&q-data);/*输入元素值*/q-next=NULL;/*结点指针域置空*/p-next=q;/*新结点连在表末尾*/p=q;}returnhead;}/*CreateList*/intInsertList(LinkListL,ElemTypee,inti){//InsertbeforeithelementLNode*p=L;intj=0;while(p&&ji-1){p=p-next;j++;}if(!p||ji)returnERROR;LNode*s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;7p-next=s;returnOK;}intDeleteList(LinkListL,ElemType&e,inti){//删除第i个元素，并由e返回其值LNode*p=L;intj=0;while(p-next&&ji-1){p=p-next;j++;}if(!(p-next)&&ji-1)returnERROR;LNode*q=p-next;p-next=q-next;e=q-data;free(q);returnOK;}voidPrintList(LinkListL){LNode*p;p=L-next;/*p指向单链表的第1个元素*/while(p!=NULL){printf(%5d,p-data);p=p-next;}}/*PrintList*/intGetElem(LinkListL,inti,ElemType*e){LNode*p;intj=1;p=L-next;while(p&&ji){p=p-next;j++;}if(!p||ji)returnERROR;*e=p-data;returnOK;}/*GetElem*/intmain(){intn,i;ElemTypee;LinkListL=NULL;/*定义指向单链表的指针*/8printf(pleaseinputn:);/*输入单链表的元素个数*/scanf(%d,&n);if(n0){printf(\n1-CreateLinkList:\n);L=CreateList(n);printf(\n2-PrintLinkList:\n);PrintList(L);printf(\n3-GetElemfromLinkList:\n);printf(inputi=);scanf(%d,&i);if(GetElem(L,i,&e))printf(No%iis%d,i,e);elseprintf(notexists);}elseprintf(ERROR);return0;}运行结果算法分析4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。插入算法代码：运行结果9算法分析删除算法代码：运行结果算法分析以下为选做实验：5、循环链表的应用（约瑟夫回环问题）n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。提示：用一个无头结点的循环单链表来实现n个元素的存储。算法代码106、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。算法代码四、实验小结五、教师评语11实验二栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验预习说明以下概念1、顺序栈：2、链栈：3、循环队列：4、链队三、实验内容和要求1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列12345e，运行结果如下所示。#includestdio.h#includemalloc.h#defineERROR0#defineOK1#defineSTACK_INT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT5/*存储空间分配增量*/typedefintElemType;/*定义元素的类型*/typedefstruct{ElemType*base;ElemType*top;intstacksize;/*当前已分配的存储空间*/12}SqStack;intInitStack(SqStack*S);/*构造空栈*/intpush(SqStack*S,ElemTypee);/*入栈*/intPop(SqStack*S,ElemType*e);/*出栈*/intCreateStack(SqStack*S);/*创建栈*/voidPrintStack(SqStack*S);/*出栈并输出栈中元素*/intInitStack(SqStack*S){S-base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));if(!S-base)returnERROR;S-top=S-base;S-stacksize=STACK_INT_SIZE;returnOK;}/*InitStack*/intPush(SqStack*S,ElemTypee){}/*Push*/intPop(SqStack*S,ElemType*e){}/*Pop*/intCreateStack(SqStack*S){inte;if(InitStack(S))printf(InitSuccess!\n);else{printf(InitFail!\n);