数据结构实验报告-顺序表与链表

《数据结构实验报告-顺序表与链表》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构与算法》实验指导V2016实验二顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。【实验学时】4学时【实验预习】回答以下问题：1、顺序表的存储表示假设线性表中每一个数据元素的存储空间大小为1个字节，并且以其所占存储空间的第一个字节的地址作为该元素的存储位置，则线性表中任一个数据元素的存储位置为：LOC(Ai)=LOC(A1)+(i-1)*1其中，LOC(A1)为线性表中第一个数据元素a1的存储位

2、置，也称为线性表的起始位置（首地址）。typedefstructSqlist{ElemType*slist;//存储空间的基地址intlength;//表长度intlistsize;//当前分配的存储空间容量}Sqlist;2、单链表的存储表示线性链表也称单链表，在每一个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连，最后一个结点因为没有后继结点，其指针置为空（NULL）。这样，链表中所有数据元素（结点）构成一对一的逻辑关系，实现线性表的链式存储。【实验内容和要求】1、按照要求完成程序exp2_1.c，实现顺序表的相关操作。以下函数均具有

3、返回值，若操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。exp2_1.c部分代码如下：#include#include#defineERROR0#defineOK1常熟理工学院计算机科学与工程学院18《数据结构与算法》实验指导V2016#defineINIT_SIZE100#defineINCREM10typedefintElemType;/*定义表元素的类型*//*（1）---补充顺序表的存储分配表示，采用定长和可变长度存储均可*/typedefstructSqlist{ElemType

4、*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,ElemType*e);intListLocate(Sqlist*L,ElemTypee,int*pos);intmenu_selec

5、t();/*（2）---顺序表的初始化*/intInitList_sq(Sqlist*L){L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L->slist){returnERROR;}L->length=0;L->listsize=INIT_SIZE;//初始空间容量returnOK;}/*InitList*//*（3）---创建具有n个元素的顺序表*/intCreateList_sq(Sqlist*L,intn){ElemTypee;inti;for(i=0;i

6、"inputdata%d:",i+1);scanf("%d",&e);if(!ListInsert_sq(L,i+1,e))常熟理工学院计算机科学与工程学院18《数据结构与算法》实验指导V2016{returnERROR;}}returnOK;}/*CreateList*//*（4）---输出顺序表中的元素*/intPrintList_sq(Sqlist*L){inti;for(i=1;i<=L->length;i++){printf("%5d",L->slist[i-1]);}returnOK;}/*PrintList*//*（5）---在顺序表的第i个位置之前

7、插入新元素e*/intListInsert_sq(Sqlist*L,inti,ElemTypee){intk;if(i<1

8、

9、i>L->length+1){returnERROR;}if(L->length>=L->listsize)//当前空间已满，申请新的空间{L->slist=(ElemType*)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType));if(!L->slist){returnERROR;}L->listsize+=INCREM;}for(k=L->length-1;k>=i-1;k--

10、){L->