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

《数据结构线性表的链式表示和实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验二线性表的链式表示和实现一、实验目的1.掌握线性表的单链表存储结构2.掌握单链线性表合并算法。二、实验内容已知单链线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。（算法2.12）三、实验步骤：1.创建线性表La和Lb。2.合并La和Lb得到Lc。3.输出La、Lb、Lc。四、算法说明建立带结点的空单链表，输入元素的值。用voidMergeList(LinkListLa,LinkList&Lb,LinkList&Lc)函数将La和Lb归并，首先比较La和Lb中元素的

2、大小，然后逐个插入。当一个链表为空时，只需将另一个链表剩下的元素插入结点后面即可。最后用voidPrintf_L(LinkList&L)函数将La，Lb和Lc中的元素输出。五、测试结果六、分析与探讨1：从上面的测试结果可以看出，在归并单链表La，Lb时，首先是比较链表中元素值的大小，从小到大的顺序插入，当一个链表为空时，只需将另一个链表剩下的元素插入结点后面即可。2：在输入La和Lb链表中的元素并输出时没涉及到将元素值按一定的顺序排序。3：在输入链表La和Lb的元素时是非递增非递减的顺序，在当输出归并后Lc中的元素能按照一定的顺序输出数据

3、结构实验报告一、附录：源代码源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%。#include#includetypedefintElemType;//定义ElemType为整型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidCreateList(LinkList&L,intn){//正位序(结点插在表尾)输入n个元素的值，建立带表头结点的单链线性表Linti;LinkList

4、p,q;L=(LinkList)malloc(sizeof(LNode));//生成头结点L->next=NULL;//先建立一个带头结点的空单链表q=L;//q指向空表的头结点(相当于尾结点)printf("请输入%d个数据",n);for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf("%d",&p->data);//给新结点输入元素值q->next=p;//将新结点插在表尾q=q->next;//q指向尾结点}p->next=NULL;//最后一个结点的

5、指针域为空}voidMergeList(LinkListLa,LinkList&Lb,LinkList&Lc)//算法2.12{//已知单链线性表La和Lb的元素按值非递减排列。//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。(销毁Lb，Lc即新的La)LinkListpa=La->next,pb=Lb->next,pc;//pa、pb分别指向La、Lb的首元结点(待比较结点)Lc=pc=La;//用La的头结点作为Lc的头结点，pc指向La的头结点(Lc的尾结点)while(pa&&pb)//La和Lb中的元素都未

6、比较完if(pa->data<=pb->data)//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);//

7、释放Lb的头结点Lb=NULL;//Lb不再指向任何结点}voidPrintf_L(LinkList&L){LNode*p;p=L->next;while(p!=NULL){printf("%d",p->data);p=p->next;}printf("");}voidmain(){intn=5;LinkListLa,Lb,Lc;printf("按非递减顺序，");CreateList(La,n);//根据输入顺序，正位序建立线性表printf("按非递减顺序，");CreateList(Lb,n);//根据输入顺序，逆位序建立线性表

8、printf("La=");Printf_L(La);//输出链表La的内容printf("Lb=");Printf_L(Lb);//输出链表Lb的内容MergeList(La,Lb,Lc);