1、实验报告课程数据结构实验名称实验一 线性表学号姓名实验日期:实验一 线性表实验目的:1.理解线性表的逻辑结构特性;2.熟练掌握线性表的顺序存储结构的描述方法,以及在该存储结构下的基本操作;并能灵活运用;3.熟练掌握线性表的链表存储结构的描述方法,以及在该存储结构下的基本操作;并能灵活运用;4.掌握双向链表和循环链表的的描述方法,以及在该存储结构下的基本操作。实验原理:线性表顺序存储结构下的基本算法;线性表链式存储结构下的基本算法;实验内容:221设计单循环链表,要求:(1) 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。(2) 设计
2、一个测试主函数,实际运行验证所设计单循环链表的正确性。222 .设计一个有序顺序表,要求:(1) 有序顺序表的操作集合有如下操作:初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是:有序顺序表中的数据元素按数据元素值非递减有序。(2) 设计一个测试主函数,实际运行验证所设计有序顺序表的正确性。(3) 设计合并函数ListMerge(L1,L2,L3),功能是把有序顺序表L1和L2中的数据元素合并到L3,要求L3中的数据元素依然保持有序。并设计一个主函数,验证该合并函数的正确性。程序代码:221(1)头文件LinList.h如下:typedef struct node
3、 DataType data; struct node *next;SLNode;/*(1)初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) /*如果有内存空间,申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1); (*head)-next=NULL; /*置结束标记NULL*/ /*(2)求当前数据元素个数ListLength(SLNode * head)*/ int ListLength(SLNode
4、 * head) SLNode *p=head; int size=0; while(p-next!=head) p=p-next; size+; return size; /*(3)插入ListInsert(SLNode * head, int i, DataType x)*/ /*在带头结点的单链表的第i(0=inext!=head & jnext; j+; if(j!=i-1) printf(The inserted position is error!); return 0; /*生成新结点由指针q指示*/ if(q=(SLNode *)malloc(sizeof(SLNode)=NU
5、LL) exit(1); q-data=x; q-next=p-next; p-next=q; return 1; /*(4)删除ListDelete(SLNode * head, int i, DataType *x) */ /*删除带头结点的单链表head的第i(0=inext!=head & p-next-next!=head & jnext; j+; if(j!=i-1) printf(The deleted position of parameter is error!); return 0; s=p-next; /*指针s指指向ai结点*/ *x=s-data; p-next=p-
6、next-next; /*删除*/ free(s); /*释放指针s所指结点的内存空间*/ return 1; /*(5)取数据元素ListGet(SLNode * head, int i, DataType *x)*/ int ListGet(SLNode * head, int i, DataType *x) SLNode *p; int j; p=head; j=-1; while(p-next!=head & jnext; j+; if(j!=i) printf(The gotten position of parameter is error!); return 0; *x=p-da
7、ta; return 1; /*(6)撤销单链表Destroy(SLNode * * head)*/ void Destroy(SLNode * * head) SLNode *p, *p1; p=*head; while(p!=NULL) p1=p; p=p-next; free(p1); *head=NULL; (2)测试主函数如下:#include /*包含printf()函数*/#include /*包含exit()函数*/#include /*包含malloc()函数*/typedef int DataType; /*定义DataType为int*/#include LinList.
8、h /*包含单链表的头文件*/void main(void) SLNode *head; /*定义头指针变量*/ int i, 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; isize=0; /* 定义初始化数据元素个数 */int ListLength(
9、SeqList L) return L.size;int ListInsert(SeqList *L, int i, DataType x) int j; if (L-size=MaxSize) printf(顺序表已满无法插入!n); return 0; else if (iL-size) printf(参数i不合法!n); return 0; else for(j=L-size; ji; j-) L-Listj=L-Listj-1; L-Listi=x; L-size+; return 1; int ListDelete(SeqList *L, int i, DataType *x) in
10、t j; if(L-size=0) printf(顺序表已空无数据元素可删!n); return 0; else if(iL-size-1) printf(参数i不合法!n); return 0; else *x=L-Listi; for(j=i+1; jsize-1;j+) L-Listj-1=L-Listj; L-size-; return 1; int ListGet(SeqList L, int i, DataType *x) if(iL.size-1) printf(参数i不合法!n); return 0; else *x=L.Listi; return 1; /*测试主函数设计如下
11、:*/#include#define MaxSize 100typedef int DataType;#include SeqList.hint SLOrderInsert(SeqList *L,DataType x)int j;if(L-size=MaxSize-1 )printf(顺序表已满无法插入!n); return 0;for(j=L-size-1;j0& xlistj;j-)L-listj+1=L-listj;L-listj+1=x;L-size+;return 1;void main(void) SeqList MyList; int a=1,2,4,5,6,8,9;/*数组a中的数据元素递增有序*/int i,n=7;int x;ListInitiate(&MyList);for(i=0;in+1;i+) ListInitiate(&MyList);SLOrderInsert(&MyList,ai);for(i=0;inext=NULL改为(*head)-next=head。2、在其它函数中,循环判定条件p-next!=NULL和p-next-next!=NULL中的NULL换成头指针head.