顺序表的定义及基本操作.doc

顺序表的定义及基本操作 一、实验目的、意义（1）掌握线性表顺序存储结构的特点。（2）熟练掌握顺序表的基本运算，理解用它们表示时插入与删除操作的算法。（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容及要求说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、输出（遍历）、销毁, 置空表、求表长、查找元素、判线性表是否为空等。（参见教材19页）实验提示：（1）定义顺序表：SqList，完成顺序表的基本操作，生成头文件SqList.h。参考运行界面：三、实验所涉及的知识点数据结构、C语言语法函数、指针、数组、循环语句等。四、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 五、总结与体会（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）调试程序时，出现了许多错误。如：头结点的建立出错、忽略了创建释放节点，另外还有一些语法上的错误。单单排查错误就用满了实验课的时间，课上未完成。后来经过查阅教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，完善自己的不足之处。六、程序清单(包含注释)#include #include #include int temptag = 0;typedef int ElemType;typedef struct LNode/定义单链表结点类型ElemType data; struct LNode *next; LinkList;void InitList(LinkList *&L) /初始化链表L=(LinkList *)malloc(sizeof(LinkList); /创建头结点L-next=NULL;printf(初始化链表成功！n);void DestroyList(LinkList *&L) /销毁链表，也就是释放内存 LinkList *p=L,*q=p-next;while (q!=NULL)free(p);p=q;q=p-next;free(p);int ListLength(LinkList *L) /输出链表的长度 LinkList *p=L;int i=0;while (p-next!=NULL)i+;p=p-next;return(i);void DispList(LinkList *L) /显示链表的数据 printf(链表中的数据如下：n);LinkList *p=L-next;while (p!=NULL)printf(%d ,p-data);p=p-next;printf(n);int GetElem(LinkList *L,int i,ElemType &e) /获取链表中的任意位置的元素。但是不能越界 int j=1;LinkList *p=L-next;while (jnext;if (p=NULL)return 0;elsee=p-data;return 1;int ListInsert(LinkList *&L,int i,ElemType e) /插入新的节点 int j=0;LinkList *p=L,*s;while (jnext;if (p=NULL)/未找到第i-1个结点 printf(未找到第%d个节点！n, (i-1);return 0; else/找到第i-1个结点*ps=(LinkList *)malloc(sizeof(LinkList);/创建新结点*ss-data=e;s-next=p-next;/将*s插入到*p之后p-next=s;return 1;int ListDelete(LinkList *&L,int i) /删除相应位置的节点 int j=0;LinkList *p=L,*q;while (jnext;if (p=NULL)/未找到第i-1个结点return 0;else/找到第i-1个结点*pq=p-next;/q指向要删除的结点if (q=NULL) return 0;/e=q-data;p-next=q-next;/从单链表中删除*q结点free(q);/释放*q结点return 1;void jiangxu(LinkList *&L) /降序排列链表中的元素 int temp1, temp2; LinkList *q, *temp; q = L-next; while(q != NULL) temp = q-next; while(temp != NULL) temp1 = q-data; temp2 = temp-data; if(temp1 data = temp2; temp-data = temp1; temp = temp-next; q = q-next; void nizhi(LinkList *&L) /将链表中的元素顺序逆置 LinkList *New, *p, *q; p = L-next; New = (LinkList *)malloc(sizeof(LinkList); New-next = NULL; while(p != NULL) LinkList *s=(LinkList *)malloc(sizeof(LinkList); s-data = p-data; p = p-next; s-next = New-next; New-next = s; L = New;void MaxAndMin(LinkList *&L) /求最大值和最小值 LinkList *temp; int Max, Min; temp = L-next; Max = -100; Min = 100; while(temp != NULL) if(temp-data data; if(temp-data = Max) Max = temp-data; temp = temp-next; printf(最大值是：%dn最小值是：%dn, Max, Min);void Add(LinkList *&L) /添加一个新的链表，并与之前的链表合并，降序输出 LinkList *List2, *p; InitList(List2); int data, tag = 1; printf(请输入第二个链表的数据：n); scanf(%d, &data); while(data != -1) ListInsert(List2, tag, data); tag+; scanf(%d, &data); printf(第一个链表：n); DispList(L); printf(第二个链表：n); DispList(List2); p = List2-next; while(p != NULL) LinkList *s=(LinkList *)malloc(sizeof(LinkList); s-data = p-data; p = p-next; s-next = L-next; L-next = s; jiangxu(L); printf(合并后的链表：n); DispList(L); int MaxDigui(LinkList *&L) /递归求最大值 int MaxValue; if(!L-next) return L-data; else MaxValue=MaxDigui(L-next); if(L-data MaxValue) MaxValue = L-data; return MaxValue; LinkList *CreatLinkList (LinkList *&L) /递归创建链表 /建立单链表 int ch; scanf(%d,&ch); if(ch=-1) L = NULL; return L; else L=(LinkList *)malloc(sizeof(LinkList); L-data=ch; L-next = NULL; return CreatLinkList (L-next); int IsAscendOrder(LinkList *L) /递归检查链表是否单调递增 if(L-next = NULL) return 1; else if(L-next-data data) return 0; else return IsAscendOrder(L-next); int main()LinkList *h;ElemType e;int temp = 1, data;while(temp != 0) printf(*); printf( (1)输入 1，初始化单链表hn); printf( (2)输入 2，采用尾插法插入元素, -1表示输入结束n); printf( (3)输入 3，输出单链表h:n); printf( (4)输入 4，输出单链表h长度n); printf( (5)输入 5，然后输入N，查找单链表的第N个元素n); printf( (6)输入 6，在第M个元素位置上插入元素NUMn); printf( (7)输入 7，然后输入K，删除链表的第K个元素n); printf( (8)输入 8，释放单链表n); printf( (9)输入 9，将链表元素降序排列n); printf( (10)输入10，输出最大值和最小值n); printf( (11)输入11，将该链表逆置n); printf( (12)输入12，创建第二个链表，并合并之前链表，降序输出n); printf( (13)输入13，用递归算法创建链表n); printf( (14)输入14，用递归算法求最大值n); printf( (15)输入15，用递归算法判断链表数据是否单调递增n); printf(*); scanf(%d, &temp); if(temp = 1) InitList(h); else if(temp = 2) int tag = 1; scanf(%d, &data); while(data != -1) ListInsert(h, tag, data); tag+; scanf(%d, &data); printf(数据插入成功！n); else if(temp = 3) DispList(h); else if(temp = 4) printf(该单链表的长度 = %dn,ListLength(h); else if(temp = 5) int N; scanf(%d, &N); if(NListLength(h) printf(你输入的数据不合法！n); else GetElem(h,N,e); printf(第%d个元素是%dn, N, e); else if(temp = 6) int M, num; printf(请输入M值和NUM值:n); scanf(%d%d, &M, &num); if(MListLength(h)+1) printf(你输入的数据不合法！n); else ListInsert(h, M, num); else if(temp = 7) int K; scanf(%d, &K); ListDelete(h,K); else if(temp = 8) DestroyList(h); else if(temp = 9) jiangxu(h); else if(temp = 10) MaxAndMin(h); else if(temp = 11) nizhi(h); else if(temp = 12) Add(h); else if(temp = 13) LinkList *temp; temp = CreatLinkList(h); LinkList *T; T = (LinkList *)malloc(sizeof(LinkList); T-next = h-next;