数据结构实验一.doc

实验报告实验一 线性表实验目的：1.理解线性表的逻辑结构特性；2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容：221 设计单循环链表，要求：(1) 单循环链表抽象数据类型包括初始化操作、秋数据元素个数操作、插入操作、删除操作，取数据元素操作和判非空操作。(2)设计一个测试主函数，实际运行验证所设计单循坏链表的正确性。222 设计一个有序顺序表，要求：(1)有序顺序表的操作集合有如下操作：初始化，求数据元素个数、插入、删除和取数据元素操作。有序顺序表与顺序表的主要区别是：有序顺序表中数据元素按数据元素值非递减有序。(2)设计一个测试主函数，实际运行验证所设计单循坏链表的正确性。*(3)设计合并函数ListMerge（L1,L2,L3），功能是把有序顺序表L1和L2中的数据元素合并到L3中，要求把L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。程序代码：221(1) typedef struct NodeDataType data;struct Node *next;SLNode;void ListInitiate(SLNode *head)if(*head=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1);(*head)-next=NULL;int ListLength(SLNode *head)SLNode *p=head;int size=0;while(p-next!=NULL)p=p-next; size+;return size;int ListInsert(SLNode *head,int i,DataType x)SLNode *p,*q;int j;p=head;j=-1;while(p-next!=NULL&jnext;j+;if(j!=i-1)printf(insert wrong way !);return 0;if(q=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1);q-data=x;q-next=p-next;p-next=q;return 1;int ListDelete(SLNode *head,int i,DataType *x)SLNode *p,*s;int j;p=head;j=-1;while(p-next!=NULL&p-next-next!=NULL&jnext;j+;if(j!=i-1)printf(the delete wrong data!);return 0;s=p-next;*x=s-data;p-next=p-next-next;free(s);return 1;int ListGet(SLNode *head,int i,DataType *x)SLNode *p;int j;p=head;j=-1;while(p-next!=NULL&jnext;j+;if(j!=i)printf(get the wrong data!);return 0;*x=p-data;return 1;void Destroy(SLNode *head)SLNode *p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);*head=NULL;int ListEmpty(SLNode *head)if(head-next=NULL)return 0;else return 1;(2)测试主函数#include#include#includetypedef int DataType;#includeSLNode.hvoid main(void)SLNode *head;int i,x;ListInitiate(&head);for(i=0;i10;i+)if(ListInsert(head,i,i+1)=0)printf(wrong);return;if(ListDelete(head,4,&x)=0)printf(wrong);return;for(i=0;isize=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,DataType x)int i,j;for(i=0;isize;i+)if(xlisti)break;if(i=L-size)L-listi=x;L-size+;return 1;elsefor(j=L-size;ji;j-)L-listj=L-listj-1;L-listi=x;L-size+;return 1;int ListDelete(SeqList *L,DataType x)int i,j;for(i=0;isize;i+)if(x=L-listi)break;if(i=L-size)return 0;elsefor(j=i+1;jsize;j+)L-listj-1=L-listj;L-size-;return 1;int ListGet(SeqList L,int i,DataType *x)if(iL.size-1)printf(wrong);return 0;else*x=L.listi;return 1;(2)测试主函数#include#define MaxSize 100typedef int DataType;#include SXList.hvoid main(void)SeqList mylist;int i,x;ListInitiate(&mylist);for(i=0;i10;i+)ListInsert(&mylist,i+1);if(ListDelete(&mylist,4)=0)printf(wrong);return;for(i=0;iListLength(mylist);i+)if(ListGet(mylist,i,&x)=0)printf(wrong);return;else printf(%d ,x);实验结果如下：*(3)#include#define MaxSize 100typedef int DataType;#include SXList.hvoid Mylist(SeqList Q,SeqList L,SeqList *S)int i=0,j=0,k=0;while(iQ.size&jL.size)if(Q.listilistk=Q.listi;i+;k+;S-size+;else S-listk=L.listj;j+;k+;S-size+;while(ilistk=Q.listi;i+;k+;S-size+;while(jlistk=L.listj;j+;k+;S-size+;for(i=0;isize;i+)printf(%d ,S-listi);void main(void)SeqList a,b,c;int i,n;int x5=1,3,4,5,2;int y6=7,12,8,10,11,13;ListInitiate(&a);ListInitiate(&b);ListInitiate(&c);for(i=0;i5;i+)ListInsert(&a,xi);for(i=0;i6;i+)ListInsert(&b,yi);Mylist(a,b,&c);实验结果如下：总结与思考:在没上机以前，感觉自己学到的都是理论知识，对那些代码没有真实性的感觉。经过自己打代码，上机实验，同