数据结构+单链表应用

一、问题描述

编写程序实现两个有序表的交和差，令 L1=(x1, x2, x3, ..., xn)，L2=(y1, y2, y3, ..., yn)，它们是两个线性表，采用带头结 点的单链表存储，请先实现单链表存储两个链表，再完成如下功能： （1）sort：将单链表的所有结点按照数据域进行递增排序，构 造成有序单链表； （2）interSect：求两个有序单链表的交集，即C = A B，C 中 包含两个集合中重复出现的所有元素； （3）subs：求两个有序单链表的差集，即，C = A− BC 中包含所 有属于 A 但不属于 B 的元素。

二、问题解决

#include <stdio.h> 
#include <cstdlib> 
typedef int ElemType; 
typedef struct LNode { ElemType data; struct LNode *next; }LinkNode; void CreateList(LinkNode *&L,ElemType a[],int n) { LinkNode *s,*r; L=(LinkNode *)malloc(sizeof(LinkNode)); r=L; for(int i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=a[i]; r->next=s; r=s; } r->next=NULL; } LinkNode *InitList() { LinkNode *L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; return L; } void DestroyList(LinkNode **L) 
{ LinkNode *pre=*L,*p=(*L)->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); *L=NULL; 
} void DispList(LinkNode *L) { LinkNode *p=L->next; while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("\n"); } void sort(LinkNode *L) 
{ LinkNode *p,*pre,*q; p=L->next->next; L->next->next=NULL; while(p!=NULL) { q=p->next; //q 保持结点后继
结点的指针 pre=L; while(pre->next!=NULL&&pre->next->data<p->data) pre=pre->next; p->next=pre->next; pre->next=p; p=q; //扫描单链表余下结
点 } printf("递增排序结果为："); } void InterSect(LinkNode *L1, LinkNode *L2, LinkNode *L3) 
{ LNode *p1, *p2, *p3; //生成三个 LNode 类型的指针
p1, p2 ,p3 p1 = L1->next; //p1 指向 L1 的首元结点 p2 = L2->next; //p2 指向 L2 的首元结点 p3 = L3; //p3 指向 L3 的头结点 （p3 用
来存放交集部分） p3->next = NULL; //p3 的 next 域置空， 当前还
没有存放数据 while (p1&& p2) { if (p1->data < p2->data) //两个链表当前结点的数据域进
行比较，数据小的结点，就继续向后移动，指向下一个结点 { p1 = p1->next; } else if (p1->data > p2->data) { p2 = p2->next; } else { //两个结点的数据域相同时 p3->next = p2; //就将 p3 结点的 next 域指向 p2 p1 = p1->next; //p1,p2 结点指向下一结点 p2 = p2->next; p3 = p3->next; //p3 指向下一结点 } } printf("链表交集为："); 
} void Subs(LinkNode *L1, LinkNode *L2) 
{ LinkNode *p1, *p2 ,*pre; p1 = L1->next;  p2 = L2->next; pre= L1; while (p1!= NULL&&p2!= NULL) { if (p1->data < p2->data) { pre=p1; p1 = p1->next; } else if (p1->data > p2->data) { p2=p2->next; } else if(p1->data == p2->data) { pre->next = p1->next;//若 p1 和 p2 指向的数据域的
值相同则删去 L1 中该数据 p1=p1->next; p2=p2->next; } } printf("链表差集为："); } int main() 
{ int a[]={5,2,1,6,8,9}; int b[]={3,9,5,6,7,4}; LNode *L1=(LNode*)malloc(sizeof(LNode)); int n=sizeof(a)/sizeof(a[0]); CreateList(L1,a,n); printf("L1 原链表为："); DispList(L1); sort(L1); DispList(L1); LNode *L2=(LNode*)malloc(sizeof(LNode)); int m=sizeof(b)/sizeof(b[0]); CreateList(L2,b,m);  printf("L2 原链表为："); DispList(L2); sort(L2); DispList(L2); LNode *L3=(LNode*)malloc(sizeof(LNode)); InterSect(L1,L2,L3); DispList(L3); Subs(L1,L2); DispList(L1); return 0; 
} 

三、代码分析

1、将单链表的所有结点按照数据域进行递增排序，只需要将遍历 一遍链表，判断前一个结点的数据域的值是否大于后继结点的 数据域的值，是则交换两结点。

2、 两个有序单链表的交集，设置三个指针 p1、p2、p3 开始时分 别指向 L1、L2、L3 的开始结点。循环进行以下判断和操作： 如果 p1 所指结点的值小于 p2 所指结点的值，则 p 后移一 位; 如果 p2 所指结点的值小于 p1 所指结点的值，则 q 后移一位; 如果两者所指结点的值相同，则将 p1 或 p2 所指结点的值放在 L3 中，同时 p3 后移一位。 最后，p1 与 p2 任一指针为 NULL 时算法结束。

3、 求两个有序单链表的差集，设置两个指针 p1、p2 开始时分别 指向 L1 和 L2 的开始结点。循环进行以下判断和操作： 如果 p 所指结点的值小于 q 所指结点的值，则 p 后移一位; 如果 q 所指结点的值小于 p 所指结点的值，则 q 后移一位; 如果两者所指结点的值相同，则删除 p1 所指结点。 最后，p 与 q 任一指针为 NULL 时算法结束。