用单链表实现集合的操作

《数据结构》课设计报告2012—2013学年第一学期课程名称数据结构设计题目用单链表实现集合的操作专业班级姓名学号指导教师一．实验目的掌握单链表的算法，插入、删除、遍历等。二．实验内容（1）对集合中的元素用有序单链表进行存储；（2）实现交、并、差等基本运算时，不能另外申请存储空间；（3）充分利用单链表的有序性，要求算法有较好的时间性能。三．设计与编码集合是由互不相同的元素构成的一个整体，在集合中，元素之间可以没有任何关系，所以，集合也可以作为线性表的处理。用单链表实现集合的操作，需要注意集合中元素的唯一性，即在单链表中不存在值相同的结点。（1）判断A和B是否相等。两个集合相等的条件是不仅长度相同，而且各个对应的元素也相等。由于用单链表表示集合，所以只要同步搜啊秒两个单链表，若从头至尾每个对应的元素都相等，则表明两个集合相等。（2）求集合A和B的交集。根据集合的运算规则，集合A∩B中包含所有既属于集合A又属于集合B的元素，因此，需要查找单链表A和B中的相同元素并保留在单链表A中。由于用有序单链表表示集合，因此判断某元素是否在B中不需要遍历表B，而是从上次搜索到的位置开始，若在搜索过程中，遇到一个其值比该元素大的结点，便可断定该元素不在单链表中，为此，需要用两个指针p、q分别指向当前被比较的两个结点，会出现以下三种情况：1、若p-dataq-data，说明还未找到，需在表B中继续查找；2、若p-dataq-data，说明表B中无此值，处理表A中下一结点；3、若p-data=q-data,，说明找到了公共元素。（3）求集合A和B的并集，集合A∪B中包含所有或属于集合A或属于集合B的元素。因此，对单链表B中的每一个元素x，在单链表A中进行查找，若存在和x不同的元素，则将该结点出入到单链表A中。（4）求集合A和B的差集。根基集合的运算规则，集合A-B中包含所有属于集合A而不属于集合B的元素。因此，对单链表B中的每个元素x在单链表A中进行查找，若存在和x相同的结点，则将该结点从链表A中删除。在主函数中，首先建立两个有序单链表表示集合A和B，然后依次调用相应函数实现集合的判等、交、并和差等运算，并输出运算结果。代码：#includeiostreamusingnamespacestd;templateclassTstructNode{Tdata;NodeT*next;};templateclassTclassLinkList{public:LinkList(Ta[],intn);//建立有n个元素的单链表~LinkList();intIfdeng(NodeT*A,NodeT*B);//判断是否相等voidInterest(NodeT*A,NodeT*B);//求交集voidSum(NodeT*A,NodeT*B);//求并集voidSubtraction(NodeT*A,NodeT*B);//求差集voidPrintList();voidShow(inti);private:NodeT*first;};templateclassTLinkListT::LinkList(Ta[],intn){NodeT*s;first=newNodeT;first-next=NULL;for(inti=0;in;i++){s=newNodeT;s-data=a[i];s-next=first-next;first-next=s;}}templateclassTLinkListT::~LinkList(){NodeT*p,*q;p=first;//工作指针p初始化while(p){//释放单链表的每一个结点的存储空间q=p;//暂存被释放结点p=p-next;//工作指针p指向被释放结点的下一个结点，使单链表不断开deleteq;}}templateclassT//判断是否相等intLinkListT::Ifdeng(NodeT*A,NodeT*B){NodeT*pa,*pb;pa=A-next;pb=B-next;while(pa!=NULL&&pb!=NULL){if(pa-data==pb-data){pa=pa-next;pb=pb-next;}elsebreak;}if(pa==NULL&&pb==NULL)return1;elsereturn0;}templateclassT//交集voidLinkListT::Interest(NodeT*A,NodeT*B){NodeT*pre,*p,*q;pre=A;p=A-next;q=B-next;while(p!=NULL&&q!=NULL){if(p-dataq-data){pre-next=p-next;p=pre-next;}elseif(p-dataq-data){q=q-next;}else{pre=p;p=p-next;q=q-next;}}}templateclassT//求并集voidLinkListT::Sum(NodeT*A,NodeT*B){NodeT*pre,*p,*q;pre=A;p=A-next;q=B-next;while(p!=NULL&&q!=NULL){if(p-dataq-data){pre=p;p=p-next;}elseif(p-dataq-data){q=q-next;}else{pre-next=p-next;p=p-next;q=q-next;}}}templateclassT//求差集voidLinkListT::Subtraction(NodeT*A,NodeT*B){NodeT*pre,*p,*q,*pra;pre=A;pra=B;p=A-next;q=B-next;while(p!=NULL&&q!=NULL){if(p-dataq-data){pre=p;p=p-next;}elseif(p-dataq-data){q=q-next;}else{pre-next=p-next;p=pre-next;q=q-next;}}}templateclassTvoidLinkListT::PrintList(){//遍历输出所有元素NodeT*p;p=first-next;//工作指针p初始化while(p!=NULL){coutp-data;p=p-next;}coutendl;}intmenu(){//菜单函数intm;do{cout请输入对应数字(1、判断是否相等2、求交集3、求并集4、求差集5、结束运行)endl;cinm;}while(m1||m5);returnm;}inta[]={5,4,3,2,1},b[]={6,4,2};intn=5,m=3;LinkListintSL(a,n);LinkListintsl(b,m);LinkListints(a,n);LinkListintS(b,m);LinkListintl(a,n);LinkListintL(b,m);staticboolbl=true;templateclassTvoidLinkListT::Show(inti){switch(i){case1:{NodeT*pa,*pb;pa=s.first;pb=S.first;s.PrintList();S.PrintList();while(0){cout相等endl;}cout不相等endl;}break;case2:{NodeT*p,*q;p=SL.first;q=sl.first;SL.PrintList();sl.PrintList();SL.Interest(p,q);SL.PrintList();coutendl;cout已求交集endl;}break;case3:{NodeT*p,*q;p=s.first;q=S.first;s.PrintList();S.PrintList();s.Sum(p,q);s.PrintList();S.PrintList();cout已求并集endl;}break;case4:{NodeT*p,*q;p=l.first;q=L.first;l.PrintList();L.PrintList();l.Subtraction(p,q);l.PrintList();cout已求差集endl;}break;case5:{bl=false;}break;}}voidmain(){cout集合a[]={5,4,3,2,1}endl;cout集合b[]={3,1}endl;coutendl;while(bl==true){inti=menu();SL.Show(i);}}运行后结果如下：四．总结与心得主要利用点链表实现，首先得建立单链表，注意利用单链表的有序性指针的使用也非常重要，包括头指针的使用注意*的使用，注意指针p的初始化，得建立析构函数释放单链表的每一个结点的存储空间。调试时找出错误逐个找出其错误，然后研究解决。通过这次课程设计，我们对C语言以及数据结构有了更深刻的了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，我们终于完成了这段程序。在调试过程中，我们认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我们也认识到了自己的薄弱之处，如对链表相关知识的欠缺，文件运用的不熟练，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面