数据结构线性表实验报告

1、实验报告课程数据结构实验名称实验一 线性表学号姓名实验日期：实验一 线性表实验目的：1.理解线性表的逻辑结构特性；2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容：221设计单循环链表，要求：（1）       单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、

2、插入操作、删除操作、取消数据元素操作和判非空操作。（2）       设计一个测试主函数，实际运行验证所设计单循环链表的正确性。222 .设计一个有序顺序表，要求：（1）       有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。（2）       设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。（3）  

3、     设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。程序代码：221（1）头文件LinList.h如下：typedef struct node DataType data; struct node *next;SLNode;/*（1）初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) /*如果有内存空间，申请头结点空间并使头指针head指向头

4、结点*/if(*head=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1); (*head)->next=NULL; /*置结束标记NULL*/ /*(2)求当前数据元素个数ListLength(SLNode * head)*/ int ListLength(SLNode * head) SLNode *p=head; int size=0; while(p->next!=head) p=p->next; size+; return size; /*(3)插入ListInsert(SLNode * head， int i， DataTy

5、pe x)*/ /*在带头结点的单链表的第i(0<=i<=size)个结点前*/ /*插入一个存放数据元素x的结点。插入成功时返回1，失败返回0*/ int ListInsert(SLNode * head, int i, DataType x) SLNode *p, *q; int j; p=head; j=-1; while(p->next!=head && j<i-1) /*最终让指针指向第i-1个结点*/ p=p->next; j+; if(j!=i-1) printf("The inserted position is erro

6、r!"); return 0; /*生成新结点由指针q指示*/ if(q=(SLNode *)malloc(sizeof(SLNode)=NULL) 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<=i<=size)个结点前*/ /*被删除结点的数据元素域由x带回。删除成功时返回1，失败返回0*/ int ListDelete(

7、SLNode * head, int i, DataType *x) SLNode *p, *s; int j; p=head; j=-1; while(p->next!=head && p->next->next!=head && j<i-1) /*最终让指针指向第i-1个结点*/ p=p->next; j+; if(j!=i-1) printf("The deleted position of parameter is error!"); return 0; s=p->next; /*指针s指指向ai结

8、点*/ *x=s->data; p->next=p->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 && j<i) p=p->next; j+; if(j!=i) p

9、rintf("The gotten position of parameter is error!"); return 0; *x=p->data; 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 <stdio.h> /*包含printf()函数*/#

10、include <stdlib.h> /*包含exit()函数*/#include <malloc.h> /*包含malloc()函数*/typedef int DataType; /*定义DataType为int*/#include "LinList.h" /*包含单链表的头文件*/void main(void) SLNode *head; /*定义头指针变量*/ int i, x; ListInitiate(&head); /*初始化*/ for(i=0;i<10;i+) /*插入10个数据元素*/ if(ListInsert(he

11、ad, i, i+1)=0) printf("error!n");return; if(ListDelete(head, 4, &x)=0) /*删除第四个数据元素*/ printf("error!n"); return; for(i=0; i<ListLength(head); i+) /*显示当前数据元素*/ if(ListGet(head, i, &x)=0) /*取数据元素*/ printf("error!n");return; else printf("%d ", x); /*显示*

12、/ Destroy(&head); /*撤销单链表*/222 设计一个有序顺序表头文件程序如下：#define NULL 0typedef struct DataType ListMaxSize; int size;SeqList;void listInitiate(SeqList *L) /*初始化顺序表 L */ L->size=0; /* 定义初始化数据元素个数 */int ListLength(SeqList L) return L.size;int ListInsert(SeqList *L, int i, DataType x) int j; if (L->si

13、ze>=MaxSize) printf("顺序表已满无法插入！n"); return 0; else if (i<0|i>L->size) printf("参数i不合法！n"); return 0; else for(j=L->size; j>i; j-) L->Listj=L->Listj-1; L->Listi=x; L->size+; return 1; int ListDelete(SeqList *L, int i, DataType *x) int j; if(L->size&

14、lt;=0) printf("顺序表已空无数据元素可删！n"); return 0; else if(i<0|i>L->size-1) printf("参数i不合法！n"); return 0; else *x=L->Listi; for(j=i+1; j<L->size-1;j+) L->Listj-1=L->Listj; L->size-; return 1; int ListGet(SeqList L, int i, DataType *x) if(i<0|i>L.size-1) p

15、rintf("参数i不合法！n"); return 0; else *x=L.Listi; return 1; /*测试主函数设计如下：*/#include<stdio.h>#define MaxSize 100typedef int DataType;#include "SeqList.h"int SLOrderInsert(SeqList *L,DataType x)int j;if(L->size>=MaxSize-1 )printf("顺序表已满无法插入！n"); return 0;for(j=L-&g

16、t;size-1;j>0&& x<L->listj;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;i<n+1;i+) ListInitiate(&MyList);SLOrderInsert(&MyList,ai);for(i=0;i<n+1;i+) ListGet(MyList,i,x); printf("%d",ai);实验结果：（1）