实验一顺序表与链表成品.doc

《实验一顺序表与链表成品.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。二、实验预习说明以下概念1、线性表：线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。2、顺序表：线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。3、链表：指针域中存储的信息称作指针或链。N个接点连接成一个链表，故又称线性链表。三、实验内容和要求1、阅读下面程序，在横线处填写函数的基

2、本功能。并运行程序，写出结果。l#includel#includel#defineERROR0l#defineOK1ll#defineINIT_SIZE5/*初始分配的顺序表长度*/l#defineINCREM5/*溢出时，顺序表长度的增量*/ltypedefintElemType;/*定义表元素的类型*/ltypedefstructSqlist{lElemType*slist;/*存储空间的基地址*/lintlength;/*顺序表的当前长度*/lintlistsize;/*当前分配的存储空间*/l}S

3、qlist;llintInitList_sq(Sqlist*L);/*构造一个空的线性表L*/lintCreateList_sq(Sqlist*L,intn);/*不断地插入元素*/lintListInsert_sq(Sqlist*L,inti,ElemTypee);/*在L中第i个位置之前插入一个数据元素e，L的长度加1*/lintPrintList_sq(Sqlist*L);/*输出顺序表的元素*/lintListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/lintListLocate(Sqlist*L,Ele

4、mTypee);/*查找值为e的元素*/llintInitList_sq(Sqlist*L){lL->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));lif(!L->slist)returnERROR;lL->length=0;lL->listsize=INIT_SIZE;lreturnOK;l}/*InitList*/llintCreateList_sq(Sqlist*L,intn){lElemTypee;linti;lfor(i=0;i

5、ta%d",i+1);lscanf("%d",&e);lif(!ListInsert_sq(L,i+1,e))lreturnERROR;l}lreturnOK;l}/*CreateList*/ll/*输出顺序表中的元素*/lintPrintList_sq(Sqlist*L){linti;lfor(i=1;i<=L->length;i++)lprintf("%5d",L->slist[i-1]);lreturnOK;l}/*PrintList*/llintListInsert_sq(Sqlist*L,inti,ElemTypee){lintk;

6、lif(i<1

7、

8、i>L->length+1)lreturnERROR;lif(L->length>=L->listsize){lL->slist=(ElemType*)realloc(L->slist,l(INIT_SIZE+INCREM)*sizeof(ElemType));lif(!L->slist)lreturnERROR;lL->listsize+=INCREM;l}lfor(k=L->length-1;k>=i-1;k--){lL->slist[k+1]=L->slist[k];l}lL->slist[i-1]=e;lL->len

9、gth++;lreturnOK;l}/*ListInsert*/ll/*在顺序表中删除第i个元素*/lintListDelete_sq(Sqlist*L,inti)l{intk;lif(i<1

10、

11、i>L->length)lreturnERROR;lfor(k=i-1;k<=L->length-1;k++)l{lL->slist[k]=L->slist[k+1];l}lL->length--;lreturn0;l}//listDelete_l/*在顺序表中查找指定值元素，返回其序号*/l/*intListLocate(Sqlist*L,Elem

12、Typee)l{lintn;linti;lif(i<1

13、

14、i>L->length)lreturnERROR;lfor(n=0;ns