数据结构实验报告线性表及其应用

《数据结构实验报告线性表及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告（1）姓名：张惠荣学号：6103115102专业班级：计算机科学与技术153实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。问题描述：1、问题描述：构造一个空的线性表L。2、在线性表L的第i个元素之前插入新的元素e；3、在线性表L中删除第i个元素，并用e返回其值。实验要求：1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复

2、杂度进行分析。算法分析：顺序结构算法：#defineLIST_INIT_SIZE100//线性存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;/当前长度intlistsize;//当前分配的存储量}Sqlist;StatusInitList_Sq(SqList&L){//操作结果：构造一个空的顺序线性表L.elem=(ElemType*)malloc(LIST_INIT_

3、SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_SqStatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L中第i个元素之前插入新的元素e，//i的合法值为1<

4、

5、i>ListLength(L

6、)+1)returnERROR;//i值不合法If（L.length>=L.listsize）{//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREATMENT)*sizeof(ElemType);if（！newbase）exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L．listsize+=LISTINCREMENT;//增加存储容量}q=&(L.elem[i-1]);//q为插

7、入位置for(p=(&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素后移*q=e;//插入e++L.length;//表长增1returnOK;}//ListInsert_SqStatusListDelete_Sq(SqList&L,inti,ElemTypee){//在顺序表L中删除第i个元素，并用e返回其值if(i<1

8、

9、i>ListLength(L))returnERROR;//i值不合法for(p=&(L.elem[i]);p<&(L.el

10、em[L.length];++p)*p=*(p+1);//删除位置之后的前移--l.length;//表长减1returnOK;}//ListDelete_Sq链式结构算法：typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode;StatusInit_L(LinkList&L){//构造一个空的线性链表L=(Linklist*)malloc(sizeof(LNode));if(!L)exit(OVERFLOW)//分配内存失败L．

11、next=NULLreturnOK;};Init_LStatusInsert_L(LinkList&L,inti,,ElemTypee){//在第i个元素之前插入eq=(Linklist*)malloc(sizeof(LNode));//创建插入结点if（！q）exit(OVERFLOW)//创建失败q->data=e;LNode*p;p=L.next;intj=1;while((p!=NULL)&&(j

12、K;}//Insert_LStatusDelete_L(LinkList&L,inti){//删除第i个元素p=L.next;intj=1;while((p!=NULL)&&(j