数据结构+单链表应用

一、问题描述

编写程序实现两个有序表的交和差，令 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 时算法结束。