数据结构线表的链式表示和实现.doc

数据结构实验报告 实验二 线性表的链式表示和实现一、 实验目的1. 掌握线性表的单链表存储结构2. 掌握单链线性表合并算法。二、 实验内容已知单链线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。（算法2.12）三、 实验步骤：1. 创建线性表La和Lb。2. 合并La和Lb得到Lc。3. 输出La、Lb、Lc。四、 算法说明 建立带结点的空单链表，输入元素的值。用void MergeList(LinkList La,LinkList &Lb,LinkList &Lc)函数将La和Lb归并，首先比较La和Lb中元素的大小，然后逐个插入。当一个链表为空时，只需将另一个链表剩下的元素插入结点后面即可。最后用void Printf_L(LinkList&L)函数将La，Lb和Lc中的元素输出。五、 测试结果 六、 分析与探讨 1：从上面的测试结果可以看出，在归并单链表La，Lb时，首先是比较链表中元素值的大小，从小到大的顺序插入，当一个链表为空时，只需将另一个链表剩下的元素插入结点后面即可。 2：在输入La和Lb链表中的元素并输出时没涉及到将元素值按一定的顺序排序。 3：在输入链表La和Lb的元素时是非递增非递减的顺序，在当输出归并后Lc中的元素能按照一定的顺序输出七、 附录：源代码源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%。#include#includetypedef int ElemType; / 定义ElemType为整型typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateList(LinkList &L,int n) / 正位序(结点插在表尾)输入n个元素的值，建立带表头结点的单链线性表Lint i;LinkList p,q;L=(LinkList)malloc(sizeof(LNode); / 生成头结点L-next=NULL; / 先建立一个带头结点的空单链表q=L; / q指向空表的头结点(相当于尾结点)printf(请输入%d个数据n,n);for(i=1;idata); / 给新结点输入元素值q-next=p; / 将新结点插在表尾q=q-next; / q指向尾结点p-next=NULL; / 最后一个结点的指针域为空void MergeList(LinkList La,LinkList &Lb,LinkList &Lc) / 算法2.12 / 已知单链线性表La和Lb的元素按值非递减排列。/ 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。(销毁Lb，Lc即新的La)LinkList pa=La-next,pb=Lb-next,pc; / pa、pb分别指向La、Lb的首元结点(待比较结点)Lc=pc=La; / 用La的头结点作为Lc的头结点，pc指向La的头结点(Lc的尾结点)while(pa&pb) / La和Lb中的元素都未比较完if(pa-datadata) / La的当前元素不大于Lb的当前元素 pc-next=pa; / 将pa所指结点归并到Lc中pc=pa; / pc指向表Lc的最后一个结点pa=pa-next; / 表La的下一个结点成为待比较结点else / Lb的当前元素小于La的当前元素 pc-next=pb; / 将pb所指结点归并到Lc中pc=pb; / pc指向表Lc的最后一个结点pb=pb-next; / 表Lb的下一个结点成为待比较结点pc-next=pa?pa:pb; / 插入剩余段free(Lb); / 释放Lb的头结点Lb=NULL; / Lb不再指向任何结点void Printf_L(LinkList&L)LNode*p;p=L-next;while(p!=NULL)printf(%d ,p-data);p=p-next;printf(n);void main()int n=5;LinkList La,Lb,Lc;printf(按非递减顺序，);CreateList(La,n); / 根据输入顺序，正位序建立线性表printf(按非递减顺序，);CreateList(Lb,n); / 根据输入顺序，逆位序建立线性表printf(La=);Printf_L(La); / 输出链表La的内容printf(Lb=);Printf