集合的并交差运算

1、数 据 结 构课程设计说明书题 目集合的并交差运算学 号姓 名指导教师康懿日 期2015年7月2日内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目集合的并交差运算指导教师康懿时间2013年秋学期第15周至第19周一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一

2、题，独立完成，题目选定后不可更换。集合的并交差运算以链表存储集合，在此基础上完成对集合的操作。要求设计类（或类模板）来描述集合，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入、输出集合v 查询集合中的元素v 在集合中进行插入、删除元素v 实现集合的并、交、差运算 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五

3、、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编， 清华大学出版社 2007目录目录3第1章 需求分析4第2章 总体设计4第

4、3章 抽象数据类型定义53.1 LinkList抽象数据类型的设计53.2 集合抽象数据类型的设计5第4章 详细设计54.1 工程视图54.2 类图视图64.3 主要算法的详细设计64.3.1 插入算法的详细设计74.3.2 清除算法的详细设计74.3.3 求交集算法的详细设计74.3.4 求并集算法的详细设计84.3.5 求差集算法的详细设计9第5章 测试9第6章 总结11附录：程序代码11第1章 需求分析1、  本演示程序中，集合的元素限定为小写字母字符“a”z”。集合输入的形式为一个以“0“为结束标志的字符串，串中字符顺序不限。2、 演示程序以用户和计算机的对话方式执行，即在计

5、算机终端上显示“提示信息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。3、  程序执行的命令包括：1） 构造集合A；2）构造在集合B；3）删除集合A内的元素；4）删除集合B内的元素；5） 在集合A中插入元素；6）在集合B中插入元素；7）求AB集合的并集；8)求AB集合的交集；9）求AB及BA的差集第2章 总体设计 总体设计框架图，如图2.1所示： 开始 输入A集合 输入B集合 添加 删除 添加 删除 B-A A-B AB AB图2.1 总体设计框架第3章 抽象数据类型定义定义格式如下：3.1 LinkList抽象数据类型的设计 AD

6、T LinkList 基本操作： InitList(LinkList *L) 构造一个空的线性表L DestroyList(LinkList *L) 初始条件：线性表L已存在 ListEmpty(LinkList L) 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE Status ListInsert(LinkList L,int i,ElemType e） 在带头结点的单链线性表L中第i个位置之前插入元素e ListPrint(LinkList L) 依次输出链表中的元素3.2 集合抽象数据类型的设计 typedef struct LNode char d

7、ata; struct LNode *next; LNode, *LinkList;第4章 详细设计4.1 工程视图 图4.1 工程视图4.2 类图视图 图4.2 类图视图4.3 主要算法的详细设计4.3.1 插入算法的详细设计 void ListSort(LinkList L)LinkList first; /*为原链表剩下用于直接插入排序的节点头指针*/LinkList t; /*临时指针变量：插入节点*/LinkList p; /*临时指针变量*/LinkList q; /*临时指针变量*/first = L->next; /*原链表剩下用于直接插入排序的节点链表*/L->n

8、ext = NULL; /*只含有一个节点的链表的有序链表。*/while (first != NULL) /*遍历剩下无序的链表*/*插入排序*/for (t = first, q = L; (q!=NULL) && (q->data < t->data); p=q, q=q->next); /*无序节点在有序链表中找插入的位置*/*退出for循环，就是找到了插入的位置*/first = first->next; /*无序链表中的节点离开，以便它插入到有序链表中。*/if (q = L) L = t; /*插在第一个节点之前*/else p-&g

9、t;next = t; /*p是q的前驱*/t->next = q; /*完成插入动作*/4.3.2 清除算法的详细设计void qingchu(LinkList La)/*清除链表中相同的元素*/char i,j;LinkList p,q;La->next;p=La;q=p->next;while(q)i=p->data; j=q->data; if(i=j) q=p->next; /* 删除并释放结点 */ p->next=q->next; free(q); p=p->next; q=p->next;4.3.3 求交集算法的详细设

10、计void Jiaoji(LinkList La,LinkList Lb,LinkList Lc) /*求两集合的交集，将结果存入另一个链表中*/ char i,j; LinkList p ,q; La->next; Lb->next; p=La; q=Lb; while(p&&q) i=p->data; j=q->data; if(i<j) p=p->next; if(i=j) ListInsert(Lc,1,i); p=p->next;q=q->next; if(i>j) q=q->next; ListSort(L

11、c); printf("AB=");ListPrint(Lc);4.3.4 求并集算法的详细设计void bingji(LinkList La,LinkList Lb,LinkList Lc) char i,j;/*求两集合的并集*/LinkList p,q;La->next;Lb->next;p=La;q=Lb;while(p&&q)i=p->data; j=q->data; if(i<j) ListInsert(Lc,1,i);p=p->next; if(i=j) ListInsert(Lc,1,i); p=p->

12、;next;q=q->next; if(i>j) ListInsert(Lc,1,j); q=q->next; while(p)i=p->data;ListInsert(Lc,1,i);p=p->next; while(q)j=q->data;ListInsert(Lc,1,j);q=q->next;ListSort(Lc);printf("AB=");ListPrint(Lc); 4.3.5 求差集算法的详细设计void chaji(LinkList La,LinkList Lb,LinkList Lc)char i,j;Link

13、List p,q;La->next;Lb->next;p=La;q=Lb;while(p&&q)i=p->data; j=q->data;if(i<j)ListInsert(Lc,1,i);p=p->next;if(i=j)p=p->next;if(i>j)q=q->next;while(p)i=p->data;ListInsert(Lc,1,i);p=p->next;ListSort(Lc);ListPrint(Lc);第5章 测试图5.1 输入输出AB集合图5.2 对AB集合进行删除操作图5.3 对AB集合进

14、行插入操作图5.4 对AB集合进行并交差操作第6章 总结在本次数据结构课程设计的过程中，深刻的意识到对程序代码设计的难度，不过这更让我在这过程中受益匪浅，体味到计算机系的高大上。这个课程具有很高的挑战性和耐性。进行程序设计的时候注意模块的划分，从各个小模块开始进行设计。设计的过程中，出现了很多错误，但是通过查找资料，反复对比内容的真伪性，找出了问题的所在，并最终解决了问题，这过程中结果并不显的那么重要，因为有艰辛的过程，所以才显出了结果的完美，它让我更加坚定了在这条路上的努力发展。附录：程序代码 #include<string.h> #include<ctype.h>

15、#include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream> / cout,cin / 函数结

16、果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE typedef int ElemType;/*线性表的单链表存储结构*/typedef struct LNode

17、char data;struct LNode *next;LNode, *LinkList;LinkList h;/*带有头结点的单链表的基本操作*/void InitList(LinkList *L) /* 操作结果：构造一个空的线性表L */*L=(LinkList)malloc(sizeof( LNode); /* 产生头结点，并使L指向此头结点 */if(!*L) /* 存储分配失败 */exit(OVERFLOW);(*L)->next=NULL; /* 指针域为空 */void DestroyList(LinkList *L) /* 初始条件：线性表L已存在。操作结果：销毁线

18、性表L */LinkList q;while(*L)q=(*L)->next;free(*L);*L=q;void ClearList(LinkList L) /* 不改变L */ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */LinkList p,q;p=L->next; /* p指向第一个结点 */while(p) /* 没到表尾 */q=p->next;free(p);p=q;L->next=NULL;printf("删除成功n"); /* 头结点指针域为空 */Status ListEmpty(LinkList L) /* 初

19、始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */if(L->next) /* 非空 */return FALSE;elsereturn TRUE;Status ListInsert(LinkList L,int i,ElemType e) /* 不改变L */ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */int j=0;LinkList p=L,s;while(p&&j < i-1) /* 寻找第i-1个结点 */p=p->next;j+;if(!p|j>i-1) /* i小于1或者大于表长 */r

20、eturn ERROR;s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */s->data=e; /* 插入L中 */s->next=p->next;p->next=s;return OK;Status ListDelete(LinkList L,int i,ElemType *e) /* 不改变L */ /* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */int j=0;LinkList p=L,q;while(p->next&&j< i-1) /* 寻找第i个结点，并令

21、p指向其前岖 */p=p->next;j+;if(!p->next|j>i-1) /* 删除位置不合理 */return ERROR;q=p->next; /* 删除并释放结点 */p->next=q->next;*e=q->data;free(q);return OK;void ListPrint(LinkList L) /*依次输出链表中的元素*/LinkList p=L->next;if(!p)printf("空集n");while(p)printf("%c", p->data);p = p-&

22、gt;next;printf("n");void ListSort(LinkList L)LinkList first; /*为原链表剩下用于直接插入排序的节点头指针*/LinkList t; /*临时指针变量：插入节点*/LinkList p; /*临时指针变量*/LinkList q; /*临时指针变量*/first = L->next; /*原链表剩下用于直接插入排序的节点链表*/L->next = NULL; /*只含有一个节点的链表的有序链表。*/while (first != NULL) /*遍历剩下无序的链表*/*插入排序*/for (t = fi

23、rst, q = L; (q!=NULL) && (q->data < t->data); p=q, q=q->next); /*无序节点在有序链表中找插入的位置*/*退出for循环，就是找到了插入的位置*/first = first->next; /*无序链表中的节点离开，以便它插入到有序链表中。*/if (q = L) L = t; /*插在第一个节点之前*/else p->next = t; /*p是q的前驱*/t->next = q; /*完成插入动作*/void qingchu(LinkList La)/*清除链表中相同的元素

24、*/char i,j;LinkList p,q;La->next;p=La;q=p->next;while(q)i=p->data; j=q->data; if(i=j) q=p->next; /* 删除并释放结点 */ p->next=q->next; free(q); p=p->next; q=p->next;void zengtian(LinkList La)/*向集合中添加元素*/char a;printf("请输入要增添的元素,加0结束n");scanf("%c",&a);while

25、(a!='0')if(a>='a'&&a<='z')|(a>='A'&&a<='Z')ListInsert(La,1,a);scanf("%c",&a);getchar();/*消除空格*/ListSort(La);ListPrint(La); void Jiaoji(LinkList La,LinkList Lb,LinkList Lc) /*求两集合的交集，将结果存入另一个链表中*/ char i,j; LinkList p ,

26、q; La->next; Lb->next; p=La; q=Lb; while(p&&q) i=p->data; j=q->data; if(i<j) p=p->next; if(i=j) ListInsert(Lc,1,i); p=p->next;q=q->next; if(i>j) q=q->next; ListSort(Lc); printf("AB=");ListPrint(Lc);void bingji(LinkList La,LinkList Lb,LinkList Lc) char

27、i,j;/*求两集合的并集*/LinkList p,q;La->next;Lb->next;p=La;q=Lb;while(p&&q)i=p->data; j=q->data; if(i<j) ListInsert(Lc,1,i);p=p->next; if(i=j) ListInsert(Lc,1,i); p=p->next;q=q->next; if(i>j) ListInsert(Lc,1,j); q=q->next; while(p)i=p->data;ListInsert(Lc,1,i);p=p->

28、;next; while(q)j=q->data;ListInsert(Lc,1,j);q=q->next;ListSort(Lc);printf("AB=");ListPrint(Lc);void chaji(LinkList La,LinkList Lb,LinkList Lc)char i,j;LinkList p,q;La->next;Lb->next;p=La;q=Lb;while(p&&q)i=p->data; j=q->data;if(i<j)ListInsert(Lc,1,i);p=p->nex

29、t;if(i=j)p=p->next;if(i>j)q=q->next;while(p)i=p->data;ListInsert(Lc,1,i);p=p->next;ListSort(Lc);ListPrint(Lc);int main()char a;char b;char c;LinkList L1,L2,L3,L4,L5,L6;InitList(&L1);InitList(&L2);InitList(&L3); /*构建需要的链表*/InitList(&L4);InitList(&L5);InitList(&L

30、6);printf("*n");printf(" 欢迎使用集合交并差运算程序n");printf("*n");printf("请输入A集合的元素，加0结束n");scanf("%c",&a);while(a!='0')if(a>='a'&&a<='z')|(a>='A'&&a<='Z')ListInsert(L1,1,a);scanf("%c",&a);getchar();ListSort(L1);qingch