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

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

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

2、和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。l#includel#includel#defineERROR0l#defineOK1ll#defineINIT_SIZE5/*初始分配的顺序表长度*/l#defineINCREM5/*溢出时，顺序表长度的增量*/ltypedefintElemType;/*定义表元素的类型*/ltypedefstructSqlist{lElemType*slist;/*存储空间的基地址*/lintlengt

3、h;/*顺序表的当前长度*/lintlistsize;/*当前分配的存储空间*/l}Sqlist;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);/*输出顺序表的元素*/lintLis

4、tDelete_sq(Sqlist*L,inti);/*删除第i个元素*/lintListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/l..lintInitList_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

5、*/llintCreateList_sq(Sqlist*L,intn){lElemTypee;linti;lfor(i=0;ilength;

6、i++)lprintf("%5d",L->slist[i-1]);lreturnOK;l}/*PrintList*/llintListInsert_sq(Sqlist*L,inti,ElemTypee){lintk;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(!

9、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->length++;..lreturnOK;l}/*ListInsert*/ll/*在顺序表中删除第i个元素*/lintListDelete_sq(Sqlist*L,inti)l{intk;lif(i<1

10、

11、i>L->length)lreturnERROR

12、;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,ElemTypee)l{lintn;linti;lif(i<1

13、

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