(完整word版)数据结构.单链表的合并0001

1、 数据结构 单链表的合并 14 辽宁大学 宋文龙 、实验内容： 1、求La和Lb两集合的并运算，要求占用原来空间。 A、在main函数上边编写一个函数能够实现 La和Lb两集合的并运算(合 并后仍然是递增的)，例如： void bing(LinkList La,LinkList Lb) /求La和Lb两集合的并运算，结果用La保存而无需使用LC /因为占用原来空间，所以需释放多余结点 注意本算法需考虑删除相同的元素，因为我们考虑的集合中没有重复 B、在 main 函数中输入数据： （如果是头插法，输入数据时要倒着录 ） La：1 3 7 8 15 20 Lb：2 4 8 15 17 24 90

2、 C、在主函数中调用bing（ La,Lb）算法，并输出合并后的La结果： 1 2 3 4 7 8 15 17 20 24 90 二，实验完整代码： #include #include /malloch 函数头文件 #include /getch 函数头文件 typedef struct LNode int data; struct LNode *next; LNode,*LinkList; LinkList creatlist(LinkList L,int n) LinkList p,q; int i; L=(LinkList)malloc(sizeof(LNode); L-next=NUL

3、L; p=(LinkList)malloc(sizeof(LNode); printf( 第 1 个节点值 :); scanf(%d, p-next=L-next; L-next=p; q=p;/ 插入第一个结点， for 语句插入剩余结点 for(i=n-1;i0;i-) p=(LinkList)malloc(sizeof(LNode); printf(第d(节点值:,n+1-i); scanf(%d, p-next=q-next; q-next=p; q=p; / 使用尾插法，创建一个含有 n 个结点的带头结点的单链表 / 也可以使用头插法来创建 L return L; / 因为链表是动态

4、分配内存，所以创建后头指针需返回，在调用时接收 void show(LinkList L) / 能够输出带头结点的单链表 L 中的各个结点的值 LinkList p; for(p=L-next;p!=NULL;p=p-next) printf(%dt,p-data); void bing(LinkList La,LinkList Lb) /求La和Lb两集合的并运算，结果用La保存而无需使用LC /因为占用原来空间，所以需释放多余结点 LinkList p1,p2,q1,q2; for(p1=La,p2=La-next,q1=q2=Lb-next;q1!=NULL) if(p2-data=q2

5、-data) q1=q1-next; free(q2);/ 释放 Lb 中重复结点所占空间 q2=q1; else if(p2-dataq2-data) q1=q1-next; p1-next=q2; q2-next=p2; p1=p1-next; q2=q1; else p1=p1-next; p2=p2-next; if(p2=NULL) p1-next=q2; free(Lb);/ 释放Lb中头结点所占空间 main() 创建带头结点单链表La含6个结点 La=creatlist(La,6); / printf(输出单链表 La:n); show(La); prin tf(n); Lb=creatlist(Lb,7); printf(输出单链表 Lb:n); show(Lb); bing(La,Lb); /求并集，合并后的结果在La中，Lb就不存在了 printf(n合并后:n); sh