西电数据结构大作业(单链表求集合)

《西电数据结构大作业(单链表求集合)》由会员分享，可在线阅读，更多相关《西电数据结构大作业(单链表求集合)（8页珍藏版）》请在装配图网上搜索。

1、1.1.题目题目单链表求集合2.2.功能描述功能描述利用带头结点的单链表实现两个集合的并、交、差运算。要求：1、要求用带头结点的单链表存储两个集合中的元素和最终的结果。2、集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即使得显示两个集合的内容及其并集、交集和差集的内容。3、要求不改变原来的集合，并集、交集和差集分别另外存放。3.3.流程图流程图开始输入集合N非 0Y在 L1 中有重复数YN插入 L1输出集合 L1输入集合N非 0Y在 L2 中有重复数YN插入 L2输出集合 L2L1 与 L2 有相同数Y插入 L3N查到表尾Y输出 L3N复制 L1复制 L1与 L3有相同数Y从复制

2、L1 删除N查到表尾Y输出 L4（复制 L1）N复制 L2Y查到 L4 表尾N插入 L4 于 L2输出 L5（复制 L2）结束4.4.程序源代码和注释程序源代码和注释#include /头文件#includetypedef int datatype;/定义单链表数据类型typedef struct nodedatatype data;/数值域struct node*next;/指针域linklist;void Insert(linklist*head,int a)/单链表头插数值已知(头结点,插入值)linklist*p=head,*s;/p 指向头结点s=(linklist*)malloc(

3、sizeof(linklist);/建立新节点s-data=a;/给新节点赋值s-next=p-next;/新节点指向第一个节点p-next=s;/头结点指向新节点linklist*Locate(linklist*head,datatype key)/在一个链表中找相同值，返回其地址已知(头结点,查找值(整形)linklist*p=head-next;/P 指向第一个指针while(p!=NULL&p-data!=key)/遍历整个链表(直到为 NULL 或找到）p=p-next;if(p=NULL)return NULL;/查找不到，返回 NULLelse return p;/查找到返回其地

4、址linklist*CreateListF()/建立链表带头节点的头插法，返回单链表的头指针（去除重复数）linklist*head;int a;/声明插入数值类型head=(linklist*)malloc(sizeof(linklist);/建立头结点head-next=NULL;/令头结点指针域为空scanf(%d,&a);/输入第一个数值while(a!=0)/循环插入数值当输入 0 结束 if(Locate(head,a)=NULL)Insert(head,a);/插入数值(去除重复数)scanf(%d,&a);/输入下一个数值return head;/返回头指针linklist*c

5、opy(linklist*L)/复制链表返回复制链表头节点已知（要复制链表）linklist*head,*p;head=(linklist*)malloc(sizeof(linklist);/建新头节点head-next=NULL;/令指针域为 NULLp=L-next;/p 指向第一个节点while(p!=NULL)/逐个插入，p 指向表尾结束Insert(head,p-data);p=p-next;return head;linklist*Jiao(linklist*L1,linklist*L2)/求交集,返回头结点已知（两链表头指针）linklist*head,*p,*q,*s;head

6、=(linklist*)malloc(sizeof(linklist);/建立交集头结点head-next=NULL;/头结点指针域为空p=L2;/p 指向 L2 头结点q=L1;/q 指向 L1 头结点while(p-next!=NULL)/遍历 L2 链表s=Locate(q,p-next-data);/在L1中查找L2数值是否存在if(s!=NULL)Insert(head,s-data);/如果存在插入交集链表p=p-next;/P 指向 L2 下一个节点return head;/返回交集头指针linklist*Locate2(linklist*head,datatype key)/在

7、一个链表中找相同值，返回此值上一地址已知(头结点,查找值)linklist*p=head;/p 指向头结点while(p-next!=NULL&p-next-data!=key)/遍历整个链表直到为 NULL 或使 P 的下一节点数值为查找值p=p-next;if(p-next=NULL)return NULL;/未找到返回 NULLelse return p;/找到则返回 p 的地址void Delete(linklist*p)/删除单链表中的值已知（删除值的上一节点）linklist*r;r=p-next;/r 指向删除节点p-next=r-next;/使删除节点的上一节点指向删除节点的后

8、一节点free(r);/释放删除节点存储空间linklist*Cha(linklist*L1,linklist*L3)/求差集(L1-L2)返回头结点已知（L1 链表头结点，L1,L2 交集头结点）linklist*head,*p,*q,*s;head=copy(L1);/令 head 为 L1 复制链表头指针p=L3;/p 指向 L3 头指针q=head;/q 指向 headwhile(p-next!=NULL)/遍历 L3s=Locate2(q,p-next-data);/查找在 L1 复制链表中是否有于 L3 中相同的值 Delete(s);/在 L1 复制链表中删除两链表的相同数值p=

9、p-next;return head;/返回差集链表头指针 linklist*Bing(linklist*L2,linklist*L4)/求并集返回头结点已知（L2 头结点，L1-L2 差集头结点）linklist*head,*p,*q;head=copy(L2);/令 head 指向 L2 复制链表头指针p=head;/p 指向 L2 复制链表头指针q=L4;/q 指向 L4 头指针while(q-next!=NULL)/遍历 L4Insert(p,q-next-data);/把差集中数据插入 L2 复制链表中q=q-next;return head;/返回并集头指针void Print(l

10、inklist*head)/输出单链表已知（输出链表头指针）linklist*temp;temp=head-next;/令 temp 指向第一个节点while(temp!=NULL)/遍历链表 printf(%3d,temp-data);/temp=temp-next;printf(n);int main()linklist*L1,*L2,*L3,*L4,*L5;printf(输入 L1(输入 0 结束)：);L1=CreateListF();/printf(L1：);Print(L1);printf(输入 L2(输入 0 结束)：);L2=CreateListF();/printf(L2：)

11、;Print(L2);L3=Jiao(L1,L2);/printf(交集：);Print(L3);L4=Cha(L1,L3);/printf(差集(L1-L2)：);Print(L4);L5=Bing(L2,L4);/printf(并集：);Print(L5);return 0;5.5.数据检测数据检测1.两集合都不为空（有重复数据）输出数值建立单链表 LI建立单链表 LI求交集求差集求并集2.L1 为空 L2 不为空（有重复数据）3.L1 不为空（有重复数据）L2 为空4.两集合为空6.6.心心得体会得体会在编程当中，对于单链表的理解进一步加深，熟练地掌握了单链表的基本操作。成功解决了重复数据输入的剔除，并且调整集合求解顺序，采用先交集后差集再并集的方式，由简到繁逐步求解，简化的求解步骤。还存在由于 0 作为标识符无法在集合中出现的问题。感受到合理安排程序顺序在程序设计时的重要性，能有效减少不必要的步骤。在函数编写时把子函数分的小一些，这样在函数调用时就很方便，不必因为某个子函数只有一部分有用另一部分无用而去编写另一个相似的程序。