用单链表实现集合交并补

1、课程设计(论文)任务书 软件 学院软件工程专业2010 - 3班 一、课程设计(论文)题目数据结构课程设计(a)二、课程设计(论文)工作自 2011 年 12月 22日起至 2011 年 12月 23 日止。三、课程设计(论文) 地点: 软件学院机房 四、课程设计(论文)内容要求：1本课程设计的目的（1）使学生熟练掌握抽象数据类型的组织和定义； （2）使学生熟练掌握数据类型的定义和实现； （3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。2基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计： 集合的

2、并交差运算：参见数据结构题集p80。 赫夫曼编/译码器：参见数据结构题集p149。 井字棋：参见数据结构教材p2。设计棋谱，当对方落子后，能从棋谱中选择一种应对方式，并能判断胜负。3课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；学生签名： 2011年 12月 日课程设计(论文)评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）； （3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（1

3、0分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人： 职称： 讲 师 2012年 1 月 5 日正 文一、 数据结构定义1. 抽象数据类型本设计中用到的数据结构adt定义如下：adt list 数据对象：d= 数据关系：= 基本操作：initlist(&l) 操作结果：构造一个空的线性表l； destroylist(&l) 初始条件：线性表l已存在 操作结果：销毁线性表l clearlist(&l) 初始条件：线性表l已存在 操作结果：将l重置为空表 listem

4、pty(l) 初始条件：线性表l已存在 操作结果：若l为空表，则返回true，否则返回false listlenght(l) 初始条件：线性表l已存在 操作结果：返回l中数据元素的个数2. 存储结构定义数据存储结构的c语言定义如下：typedef struct lnode/定义单链表结点类型 elemtype data; struct lnode *next;linklist;3. 基本操作数据结构的基本操作实现如下：displist(linklist *l)：输出单链表lcreatlistr(linklist *&l,elemtype a,int n)：运用尾插法建立单链表sort(link

5、list *&head)：单链表元素排序shanchu(linklist *&head)：在进行过sort排序之后，删除单链表里相同的元素bing(linklist *&ha,linklist *&hb,linklist *&hc )：求两个有序集合的并jiao(linklist *ha,linklist *hb,linklist *&hc)：求两个有序集合的交cha(linklist *ha,linklist *hb,linklist *&hc)：求两个有序集合的差、main()：采用尾差法建立单链表，使用sort进行单链表排序构成有序链表，在使用shanchu函数删除相同元素和非小写字母。

6、利用一个switch语句进行运算的选择，使用相关函数对有序链表进行交并差的相关运算二、 解题过程1. 问题分解该问题主要应实现以下功能：1. 利用尾差法建立单链表2. 对于输入的链表进行有序排列3. 删除有序链表中不符合要求的元素4. 调用函数对单链表进行交，并，差运算，并输出2. 模块结构系统主要由8个模块组成，分别是：1. 单链表的建立2. 单链表的有序排列3. 删除单链表中不符合条件的元素4. 集合交集5. 集合并集6. 集合差集7. 单链表输出8. 主函数模块之间的结构如下：主函数单链表的建立及由于排列删除不符合条件的元素集合交集集合差集单链表输出集合并集3. 解题思路各模块的实现步骤

7、为：1. 在尾差法建立单链表时，开始时指针指向头结点。2. 建立有序列表是利用指针的移动来是后续的元素和第一次个元素进行比较，并使用while循环实现单链表的有序排列。3. 判定有序单链表中的重复元素定义指针p，通过指针p访问链表中的元素并且通过if语句检测链表中的元素。对于不属于小写字母的元素判定后进行删除操作。4. 定义三个头结点pa，pb，pc，把ha的元素赋给hc，在使用指针移动与hb中的元素进行比较，不同的元素则插入到hc中，相同时指针移动到ha的下一个元素。当ha为空，直接把hb赋给hc。5. 同样定义了三个结点，不过hc是pa与pb不同的元素。6. 差集是通过指针的移位把两个有序

8、单链表中的元素进行比较，不同的话，则赋给hc。7. 利用主函数把有序单链表，及三个函数输出链表进行输出8. 主函数通过一个switch语句，方便的对函数进行调用，从而进行集合的交，并，差运算。三、 实现代码及注释:#include #include using namespace std;typedef char elemtype;typedef struct lnode/定义单链表结点类型 elemtype data; struct lnode *next;linklist;void creatlistr(linklist *&l,elemtype a,int n) /运用尾插法建立单链表

9、linklist *s,*r;int i; l=(linklist *)malloc(sizeof(linklist); /创建头结点，为头结点分配空间 l-next=null; r=l; /r先指向头结点后指向尾结点，开始时指针指向头结点 for(i=0;idata=ai; r-next=s; r=s; r-next=null;/尾结点指向空 void sort(linklist *&head)/建立有序链表 linklist *p=head-next,*q,*r; if(p!=null) r=p-next; p-next=null; p=r; while(p!=null)/后续元素与第一个

10、元素进行比较 r=p-next; q=head; while(q-next!=null&q-next-datadata) q=q-next; p-next=q-next; q-next=p; p=r; void shanchu(linklist *&head)/删除有序链表中重复的元素及非小写字母的元素 linklist *p=head-next,*r=head,*q,*f; while(p-next) if(p-data=p-next-data|(p-next-dataz)|(p-next-datanext; p-next=q-next; free(q); else p=p-next; if

11、(r-next-dataz|r-next-datanext; r-next=f-next; free(f); void bing(linklist * ha,linklist * hb,linklist * hc)/求并集hclinklist * pa,* pb,* pc;pa=ha-next;while(pa!=null)pc=(linklist *)malloc(sizeof(linklist);pc-data=pa-data;pc-next=hc-next;hc-next=pc;pa=pa-next;pb=hb-next;while(pb!=null)pa=ha-next;while(p

12、a!=null)&(pa-data!=pb-data)pa=pa-next;if(pa=null)pc=(linklist *)malloc(sizeof(linklist);pc-data=pb-data;pc-next=hc-next;hc-next=pc;pb=pb-next;void jiao(linklist *ha,linklist *hb,linklist *&hc)/求交集hc linklist *pa=ha-next,*pb,*s,*tc; hc=(linklist *)malloc(sizeof(linklist);/定义hc的头结点 tc=hc; while(pa) pb

13、=hb-next; while(pb&pb-datadata) pb=pb-next; if(pb&pb-data=pa-data) s=(linklist *)malloc(sizeof(linklist); s-data=pa-data; tc-next=s; tc=s; pa=pa-next; tc-next=null; void cha(linklist *ha,linklist *hb,linklist *&hc)/求差集hc linklist *pa=ha-next,*pb,*s,*tc; hc=(linklist *)malloc(sizeof(linklist);/定义hc的头

14、结点 tc=hc; while(pa) pb=hb-next; while(pb&pb-datadata) pb=pb-next; if(!(pb&pb-data=pa-data) s=(linklist *)malloc(sizeof(linklist); s-data=pa-data; tc-next=s; tc=s; pa=pa-next; tc-next=null; void displist(linklist *l)/输出单链表l linklist *p=l-next; while(p!=null) coutdata; p=p-next; coutendl;int main() li

15、nklist *ha,*hb,*hc; elemtype a100,b100;/建立两个数组存储集合 int la,lb,x; cout 请输入集合1： ; cin.getline(a,100); cout 请输入集合2：; cin.getline(b,100); la=strlen(a); lb=strlen(b); creatlistr(ha,a,la); creatlistr(hb,b,lb); sort(ha); sort(hb); shanchu(ha); shanchu(hb); cout1.输出有序集合 2.求集合交集 3.求集合并集 4.求集合并集endl; while(x!=

16、0) /循环对运算的选择 coutx; switch(x) case 1: cout有序1集合:;displist(ha); cout有序2集合:;displist(hb);/输出有序集合 break; case 2: jiao(ha,hb,hc); cout交集合:;displist(hc);/调用求交集函数 break; case 3: bing(ha,hb,hc); cout并集合:;displist(hc);/调求用并集函数 break; case 4: cha(ha,hb,hc); cout差集合:;displist(hc);/调用求差集函数 break; return 0; 四、

17、实验结果1. 实验数据集合1：xiaosihehe集合2：wuhaha2. 实验结果五、 实验小结1. 数据结构使用小结链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。单链表的建立有头插法、尾插法两种方法。在本次课程设计中采取了尾差法进行建立单链表。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针、搜索指针、申请单元指针。在使用尾差法建立单链表时最先得到的一定是头结点。2. 需完善之处本次选取的求取集合的交并差运算，只是限于小写字母，不能推广到所有字符。对于非小写字母只能使用函数删除，有一定的局限性，有待完善课程设计体会通过此次课程设计，我更加熟悉了单链表的运用，对于书上的关于运用单链表进行集合的的交，并，差，进行了添加模块和修改，参考了同学的建议，使之能够简单的运算小写字母的交并补。这次课程设计让我明白，设计思路十