东 莞 理 工 学 院C语言课程设计课程 程序设计基础 题目 集合运算 院系名称 计算机学院 班 级 学生姓名 学号 组 员 指导教师 曲超 时 间 1 问题要求及任务描述1.1 题目要求集合运算问题描述：设有两个用单链表表示的集合A、B，其元素类型是int且以非递减方式存储，其头结点分别为a、b。要求下面各问题中的结果集合同样以非递减方式存储，结果集合不影响原集合。实现要求： 编写集合元素测试函数IN_SET，如果元素已经在集合中返回0，否则返回1； 编写集合元素输入并插入到单链表中的函数INSERT_SET，保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中； 编写求集合A、B的交C=AB的函数，并输出集合C的元素； 编写求集合A、B的并D=AB的函数，并输出集合D的元素； 求集合A与B的对称差E=(A-B)(B-A) 的函数，并输出集合D的元素； 设计一个菜单，具有输入集合元素、求集合A、B的交C、求集合A、B的并D、求集合A与B的对称差E、退出等基本的功能。测试数据：由读者自定，但集合A、B的元素个数不得少于16个。1.2 主要任务编写集合元素输入并插入到单链表中的函数INSERT_SET，保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中；主要功能：创建一个单链表，并在创建的过程中边插入边排序，按非递减的方式存储在单链表中，在此过程中还要保证所输入的集合是唯一的，如果输入的元素是重复的，就删掉此元素然后再输入元素，此过程中保证所规定输入的元素个数不变，直至输到元素个数与规定的元素的个数相等时就退出。2 解决问题的主要思路和方法2.1 关键问题1，如何在创建单链表时要同时输入元素和排序（按非递减的方式排序）2，在输入的时候遇到相同的元素时要怎样做既能删除该相同元素又不会减少所规定的输入的元素个数。2.2 拟采用解决问题的方法输入元素，先判断是不是空链表；如果是则输入元素（此链表只有这个元素）然后退出。否则则表明至少有一个元素，则定义一个指向第一个结点的指针p3,然后将每次输入的元素p1-value都要和之前的元素比较一次用指针p4来指向p3,将p3一步一步的往下移进行与输入的元素p1-value比较 判断大小，分三种情况：大于、相等、小于。分别依次插入，在相等的情况下则要删掉输入的元素，同时用i-,j使其元素个数减一，以保证其规定输入的元素个数不变。2.3 主要算法：1,输入i,j,n的值，定义结构指针。2，赋值p2=head使头结点为第0个结点，判断输入元素的个数是否为规定的元素个数，是则结束，不是则继续执行；3，判断第一个结点是否为空，是则输入元素，证明此单链表中只有一个元素，则退出。否则执行下面的步骤；4，令p3为第一个结点，与输入的元素p1-value进行比较。当p1-value比p3-value大时且p3-next不为空时，令p4为p3的前一个结点，使p3指向的元素一步一步的往下移与输入的元素p1-value进行比较直至p3-next为空。5分三种情况进行比较有序的插入。p1-valuevalue时，分两种情况：判断p3是否为第一个结点，是则p1插入到head与p3之间，即head-next=p1,p1-next=p3;不是则把p1插入到p4与p3之间，即p4-next=p1,p1-next=p3;如果相等则把输入的元素p1-value赋给temp然后删掉，且输入下一个元素时也同时使元素个数减1.如果p1-valuep3-value时，则将p1-value放到最尾，即p3-next=p1,p1-next=NULL,p1为尾结点6，return(head) 结束处理流程图:Struct gather *head,*p1,*p2,*p3,*p4,*temp;开 始int i=0, j=0,n;p2=headivaluehead-next= =NULL?Yp1-next=p2-nextp2-next=p1p2=p1;Np3=head-next(p1-valuep3-value)&(p3-next!=NULL)= =1?Yp4=p3,p3=p3-nextp1-valuevalueYhead-next= =p3head-next=p1Yp4-next=p1Ntemp=p1,p1=p1-next, delete temp,i-, j-p1-value= =p3-valueYNNP3-next=p1,p1-next=NULL结 束return( head)p1-next=p33 程序实现3.1 程序实现时应考虑的问题Main函数b=INSERT-SET(number)a=INSERT-SET(number)a为集合A中的元素,b为集合B中的元素函数调用关系图print(a) print(b)打印出集合A，B中的元素3.2 主要源代码及说明#include stdafx.h#include stdlib.h#include string.h#include malloc.h#define NULL 0#define LEN sizeof(struct gather)struct gatherint value;struct gather *next; ;struct gather *INSERT_SET(int n)struct gather *head;head=(struct gather *)malloc(LEN);head-next=NULL;struct gather *p1,*p2,*p3,*p4,*temp;p2=head;/先建立一个带头结点为第0个结点的单链表for(int i=0,j=0;ivalue);if(head-next=NULL)/表明只有第一个结点为空只输入一个元素p1-next=p2-next;/新元素插入表尾p2-next=p1;p2=p1;/p1始终指向新建的结点elsep3=head-next;/为第一个结点while(p1-value p3-value) & (p3-next!=NULL)/p3一步一步的往下移进行与p1比较p4=p3;/p4为p3的前一个结点p3=p3-next;if(p1-value value)if(head-next=p3)head-next=p1;elsep4-next=p1;p1-next=p3;elseif(p1-value = p3-value)printf(ttt输入元素重复，请重新输入:n);temp=p1;/temp指向要删除的结点p1=p1-next;/输入下一个元素进行比较delete temp;i-;j-;elsep3-next=p1; /比其它的都大，放在最尾p1-next=NULL;return head;void print(struct gather *head)struct gather *p; p=head-next; while(p!=NULL) printf(%dn,p-value); p=p-next; printf(n);int main(int argc, char* argv)struct gather *a;int number;printf(Hello World!n);printf(请输入集合元素的个数n);scanf(%d,&number);a=INSERT_SET(number);printf(输出的元素为:n);print(a);return 0; 4 测试4.1 测试结果及分析分析：能够保证输入的元素不重复且在元素个数不变的情况下按非递减的方式进行排序5 小结5.1本问题解决方法及程序实现小结缺点：所需要的指针太多了，有点复杂繁琐，这样很容易指错。方法：在单链表中插入与排序是依据C语言设计（第三版）课本中的插入函数和数据结构课本中的有序查找的思想而写的。5.2 尚未解决的问题及下一步工作思路尚未解决的问题：不知道怎么缩减指针数或是用什么方法可以更加简短方便易懂的实现同样的功能。思路：利用双链表在创建的时候就已经环环相扣，指向前结点的指针和指向后结点的指针相互依存，比单链表多了一个指向前面或后面的指针，这样比较方便。6 参考文献【1】谭浩强.C程序设计(第三版).清华大学出版社.2005.07【2】维斯.数据结构与算法分析-C语言描述.机械工业出版社.2004.11 / 文档可自由编辑打印