数据结构线性表实验报告

实验报告课程数据结构实验名称实验一线性表学号姓名实验日期：实验一线性表实验目的：1.理解线性表的逻辑结构特性；2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容：2－21设计单循环链表，要求：（1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。（2）设计一个测试主函数，实际运行验证所设计单循环链表的正确性。2－22.设计一个有序顺序表，要求：（1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。（2）设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。（3）设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。程序代码：2－21（1）头文件LinList.h如下：typedefstructnode{DataTypedata;structnode*next;}SLNode;/*（1）初始化ListInitiate(SLNode**head)*/voidListInitiate(SLNode**head){/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);(*head)-next=NULL;/*置结束标记NULL*/}/*(2)求当前数据元素个数ListLength(SLNode*head)*/intListLength(SLNode*head){SLNode*p=head;intsize=0;while(p-next!=head){p=p-next;size++;}returnsize;}/*(3)插入ListInsert(SLNode*head，inti，DataTypex)*//*在带头结点的单链表的第i(0=i=size)个结点前*//*插入一个存放数据元素x的结点。插入成功时返回1，失败返回0*/intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;while(p-next!=head&&ji-1)/*最终让指针指向第i-1个结点*/{p=p-next;j++;}if(j!=i-1){printf(Theinsertedpositioniserror!);return0;}/*生成新结点由指针q指示*/if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);q-data=x;q-next=p-next;p-next=q;return1;}/*(4)删除ListDelete(SLNode*head，inti，DataType*x)*//*删除带头结点的单链表head的第i(0=i=size)个结点前*//*被删除结点的数据元素域由x带回。删除成功时返回1，失败返回0*/intListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;j=-1;while(p-next!=head&&p-next-next!=head&&ji-1)/*最终让指针指向第i-1个结点*/{p=p-next;j++;}if(j!=i-1){printf(Thedeletedpositionofparameteriserror!);return0;}s=p-next;/*指针s指指向ai结点*/*x=s-data;p-next=p-next-next;/*删除*/free(s);/*释放指针s所指结点的内存空间*/return1;}/*(5)取数据元素ListGet(SLNode*head，inti，DataType*x)*/intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;p=head;j=-1;while(p-next!=head&&ji){p=p-next;j++;}if(j!=i){printf(Thegottenpositionofparameteriserror!);return0;}*x=p-data;return1;}/*(6)撤销单链表Destroy(SLNode**head)*/voidDestroy(SLNode**head){SLNode*p,*p1;p=*head;while(p!=NULL){p1=p;p=p-next;free(p1);}*head=NULL;}（2）测试主函数如下：#includestdio.h/*包含printf()函数*/#includestdlib.h/*包含exit()函数*/#includemalloc.h/*包含malloc()函数*/typedefintDataType;/*定义DataType为int*/#includeLinList.h/*包含单链表的头文件*/voidmain(void){SLNode*head;/*定义头指针变量*/inti,x;ListInitiate(&head);/*初始化*/for(i=0;i10;i++)/*插入10个数据元素*/{if(ListInsert(head,i,i+1)==0){printf(error!\n);return;}}if(ListDelete(head,4,&x)==0)/*删除第四个数据元素*/{printf(error!\n);return;}for(i=0;iListLength(head);i++)/*显示当前数据元素*/{if(ListGet(head,i,&x)==0)/*取数据元素*/{printf(error!\n);return;}elseprintf(%d,x);/*显示*/}Destroy(&head);/*撤销单链表*/}2－22设计一个有序顺序表头文件程序如下：#defineNULL0typedefstruct{DataTypeList[MaxSize];intsize;}SeqList;voidlistInitiate(SeqList*L)/*初始化顺序表L*/{L-size=0;/*定义初始化数据元素个数*/}intListLength(SeqListL){returnL.size;}intListInsert(SeqList*L,inti,DataTypex){intj;if(L-size=MaxSize){printf(顺序表已满无法插入！\n);return0;}elseif(i0||iL-size){printf(参数i不合法！\n);return0;}else{for(j=L-size;ji;j--)L-List[j]=L-List[j-1];L-List[i]=x;L-size++;return1;}}intListDelete(SeqList*L,inti,DataType*x){intj;if(L-size=0){printf(顺序表已空无数据元素可删！\n);return0;}elseif(i0||iL-size-1){printf(参数i不合法！\n);return0;}else{*x=L-List[i];for(j=i+1;jL-size-1;j++)L-List[j-1]=L-List[j];L-size--;return1;}}intListGet(SeqListL,inti,DataType*x){if(i0||iL.size-1){printf(参数i不合法！\n);return0;}else{*x=L.List[i];return1;}}/*测试主函数设计如下：*/#includestdio.h#defineMaxSize100typedefintDataType;#includeSeqList.hintSLOrderInsert(SeqList*L,DataTypex){intj;if(L-size=MaxSize-1){printf(顺序表已满无法插入！\n);return0;}{for(j=L-size-1;j0&&xL-list[j];j--)L-list[j+1]=L-list[j];L-list[j+1]=x;L-size++;return1;}}voidmain(void){SeqListMyList;inta[]={1,2,4,5,6,8,9};/*数组a中的数据元素递增有序*/inti,n=7;intx;ListInitiate(&MyList);for(i=0;in+1;i++)ListInitiate(&MyList);SLOrderInsert(&MyList,a[i]);for(i=0;in+1;i++){ListGet(MyList,i,x);printf(%d,a[i]);}}实验结果：（1）2－21运行结果如下：（2）2－22运行结果如下：总结与思考（1）在TC2的使用过程中遇到很多问题，路径问题总是导致错误。有序顺序表的操作集合和线性表的操作集合类似。（2）带头结点循环链表的操作实现与带头结点的单链表的操作实现方法相似，但也有差别主要在：1、在初始化函数中，把语句(*head)-next=NULL改为(*head)-next=head。2、在其它函数中，循环判定条件p-next!=NULL和p-next-next!=NULL中的NULL换成头指针head.