实验一顺序表与链表成品

1、.实验一次序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的观点。2、掌握次序表与链表的成立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行剖析。4、理解次序表、链表数据结构的特色（优弊端）。二、实验预习说明以下观点1、线性表：线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。2、次序表：线性表的次序储存结构或次序映像，往常，称这类储存结构的线性表为次序表。3、链表：指针域中储存的信息称作指针或链。N个接点连结成一个链表，故又称线性链表。三、实验容和要求1、阅读下边程序，在横线处填写函数的基本功能。并运转程序，写出结果。#include#in

2、clude#defineERROR0#defineOK1#defineINIT_SIZE5/*初始分派的次序表长度*/#defineINCREM5/*溢出时，次序表长度的增量*/typedefintElemType;/*定义表元素的种类*/typedefstructSqlistElemType*slist;/*储存空间的基地点*/intlength;/*次序表的目前长度*/intlistsize;/*目前分派的储存空间*/Sqlist;intInitList_sq(Sqlist*L);/*结构一个空的线性表L*/intCreateList_sq(Sqlist*L,intn);/*不停地插入元素

3、*/intListInsert_sq(Sqlist*L,inti,ElemTypee);/*在L中第i个地点以前插入一个数据元素e，L的长度加1*/Word文档.intPrintList_sq(Sqlist*L);/*输出次序表的元素*/intListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/intListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/intInitList_sq(Sqlist*L)L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(!L-slist)ret

4、urnERROR;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;ilength;i+)printf(%5d,L-slisti

5、-1);returnOK;/*PrintList*/intListInsert_sq(Sqlist*L,inti,ElemTypee)intk;if(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-)Word文档.L-slistk+1=L-slistk;L-slisti-1=

6、e;L-length+;returnOK;/*ListInsert*/*在次序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti)intk;if(iL-length)returnERROR;for(k=i-1;klength-1;k+)L-slistk=L-slistk+1;L-length-;return0;/listDelete_/*在次序表中查找指定值元素，返回其序号*/*intListLocate(Sqlist*L,ElemTypee)intn;inti;if(iL-length)returnERROR;for(n=0;nslistn-1;*/intLi

7、stLocate(Sqlist*L,ElemTypee)intk;for(k=0;klength-1;k+)if(e=L-slistk)printf(此元素地点为：%dn,k+1);returnOK;if(k=L-length)Word文档.printf(不存在!);returnERROR;intmain()Sqlistsl;intn,m,k;printf(pleaseinputn:);/*输入次序表的元素个数*/scanf(%d,&n);if(n0)printf(n1-CreateSqlist:n);InitList_sq(&sl);CreateList_sq(&sl,n);printf(n

8、2-PrintSqlist:n);PrintList_sq(&sl);printf(npleaseinputlocatelocation:(location)n);scanf(%d,&m);ListLocate(&sl,m);printf(n3-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);

9、printf(npleaseinputDeletelocationanddata:(location)n);scanf(%d,&m);ListDelete_sq(&sl,m);printf(n3-PrintSqlist:n);PrintList_sq(&sl);/*printf(npleaseinputlocatelocation:(location)n);Word文档.scanf(%d,&m);ListLocate(&sl,m);printf(n3-PrintSqlist:n);PrintList_sq(&sl);*/printf(n);elseprintf(ERROR);return0;运

10、转结果算法剖析1；输入线性表的元素个数，而后建立一个新的线性表，2；连续用creatlist函数往性表里插入元素，将其元素输出，3；在下一步中输入插入元素的地点和个数，最后一步，输出运转后的线性表。2、为第1题增补删除和查找功能函数，并在主函数中增补代码考证算法的正确性。Word文档.删除算法代码：intListDelete_sq(Sqlist*L,inti)intk;if(iL-length)returnERROR;for(k=i-1;klength-1;k+)L-slistk=L-slistk+1;L-length-;return0;/listDelete_运转结果查找算法代码：intLi

11、stLocate(Sqlist*L,ElemTypee)intk;for(k=0;klength-1;k+)if(e=L-slistk)printf(此元素地点为：%dn,k+1);Word文档.returnOK;if(k=L-length)printf(不存在!);returnERROR;运转结果算法剖析/*在次序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee)intk;for(k=0;klength-1;k+)/*从第一个元素开始查找*/if(e=L-slistk)printf(此元素地点为：%dn,k+1);returnOK;/*若存在

12、与e相等的元素，则输出其地点，返回OK*/if(k=L-length)Word文档.printf(不存在!);returnERROR;/*不存在*/3、阅读下边程序，在横线处填写函数的基本功能。并运转程序，写出结果。#include#include#defineERROR0#defineOK1typedefintElemType;/*定义表元素的种类*/typedefstructLNode/*线性表的单链表储存*/ElemTypedata;structLNode*next;LNode,*LinkList;LinkListCreateList(intn);/*不停的往链表中插入元素*/voidP

13、rintList(LinkListL);/*输出带头结点单链表的全部元素*/intGetElem(LinkListL,inti,ElemType*e);/*当第i个元素存在时，其值赋给e*/intListInsert(LinkListL,inti,ElemType*e);voidListDelete(LinkListL,inti);LinkListCreateList(intn)LNode*p,*q,*head;inti;head=(LinkList)malloc(sizeof(LNode);head-next=NULL;p=head;for(i=0;idata);/*输入元素值*/q-nex

14、t=NULL;/*结点指针域置空*/p-next=q;/*新结点连在表末端*/p=q;Word文档.returnhead;/*CreateList*/voidPrintList(LinkListL)LNode*p;p=L-next;/*p指向单链表的第1个元素*/while(p!=NULL)printf(%5d,p-data);p=p-next;/*PrintList*/intListInsert(LinkListL,inti,ElemType*e)LNode*p,*s;intj;p=L;j=0;while(p&jnext;+j;if(!p|ji-1)returnERROR;s=(LinkLi

15、st)malloc(sizeof(LNode);s-data=*e;s-next=p-next;p-next=s;returne;/ListInsertvoidListDelete(LinkListL,inti)LNode*p,*q;intj;p=L;j=0;while(p-next&jnext;+j;Word文档.if(!(p-next)|ji-1)returnERROR;q=p-next;p-next=q-next;free(q);/ListDeleteintGetElem(LinkListL,inti,ElemType*e)LNode*p;intj=1;p=L-next;while(p&

16、jnext;j+;if(!p|ji)returnERROR;*e=p-data;returnOK;/*GetElem*/intmain()intn,i;ElemTypee;LinkListL=NULL;/*定义指向单链表的指针*/printf(pleaseinputn:);/*输入单链表的元素个数*/scanf(%d,&n);if(n0)printf(n1-CreateLinkList:n);L=CreateList(n);printf(n2-PrintLinkList:n);PrintList(L);printf(n请输入插入地点和数据:(location,data)n);scanf(%d,

17、%d,&i,&e);ListInsert(L,i,&e);PrintList(L);Word文档.printf(n请输入删除地点:n);scanf(%d,&i);ListDelete(L,i);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题增补插入功能函数和删除功能函数。并在主函数中增补代码考证算法的正确性。插入算法代码：intListInsert(LinkListL,inti,ElemType*e)Word文档.LNode*p,*s;intj;p=L;j=0;while(p&jnext;+j;if(!p|ji-1)ret