数据结构课程设计报告(集合交集并集运算).doc

数据结构课程设计报告陕西师范大学计算机科学学院计算机科学与技术专业课程设计报告课程名称：数据结构课程设计课程设计题目：集合的交集并集运算设计姓 名：刘金杰, 杨冰，李啟梅，孙玉婷，王皓靖，王婷，尹淑韵，李玉婷，刘卓院 系：计算机科学学院专 业：计算机科学与技术年级班级：10级02班指导教师：雷秀娟日期：2012年3月16日 3月21日目 录一 课程设计的目的4二 课程设计的要求4三 课程设计的报告内容41系统说明42设计目标和主要功能53. 设计原则54. 系统头文件及流程图55. 程序运行6. 系统的优点和缺点四 收获与体会五 遇到的问题六 源代码七 参考资料集合的交集并集运算一. 课程设计的目的1.掌握在Visual C+集成开发环境下编辑、编译、链接和运行一个C+程序的基本方法； 2.利用最近所学的知识并结合C和C+编写程序，实现集合的简单运算； 3.培养同学与同学之间团结协作互帮互助的精神，使团队精神发挥的淋漓尽致；4. 同时培养同学们的积极动脑动手能力，培养兴趣；二. 课程设计的要求 要求同学能够结合所学过的知识和内容有目的编写程序，能够不断的尝试和查阅资料，对所学的知识有更深刻的理解，并在理解的基础上加以运用.根据自己对线性表的概念、原理和机制的理解，结合数学知识编写程序，并求解运行出集合的交集并集运算.三. 课程设计的报告内容1.系统说明：系统名称是集合的交集并集运算；2.设计目标和主要功能：给出集合的元素个数及元素，可以分别做出集合的交集和并集运算； 3.设计原则：（1）系统运行安全可靠，稳定性好 ；（2）系统输入界面友好，操作简便易行，尽量减少用户的输入工作量； 4.系统头文件及流程图（1）系统的头文件#include<string.h>#include<ctype.h>#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.h>（2）流程图5.程序运行： (1)输入部分演示：(2)求交集部分演示：(3)求并集部分演示：(4)退出部分演示：6.系统优点和缺点(1) 优点:程序简洁明了，可以明确的实现集合的简单的运算，并加以处理，可以加强理解力，并用了所学过的知识实现操作.除此之外，不但可以实现数字与数字之间的运算，还可以实现带字母集合的运算，使得程序多样化，拓展知识.(2) 缺点：只能实现集合的简单操作，运算量小，很多方面设计的不够全面细致，集合的另外许多功能不能加以体现.除此之外，有些步骤重复化，但是又找不到简洁明了的解决办法. 四. 收获与体会通过小组成员的共同努力，我们联系以前学过的知识，并结合新学的有关线性表的内容，除此之外，还查阅了不少资料，并利用所学的数学知识，运用逻辑的投保编写出这个程序.这是我们小组人共同努力的成果，在此过程中，我们体会到了团结协作的力量，每个人都有个人的任务，我们分工明确，各尽其责，并利用课余时间互相帮助讨论,才有今天的成果.除此之外，我们还共同回忆了有关于C和C+的部分知识，熟悉操作，对线性表的知识也得到的深刻的 理解和体会。五. 遇到的问题1. 在讨论用何种算法实现的过程中，大家的意见和想法不一，但是大家并没有固执己见，而是耐心听从他人意见和建议，求同存异，不断改进算法，使程序达到最完美的标准.2. 在使用线性表的问题上，不知道使用几个更简洁，更易懂，在上网查阅资料后才得出答案. 六. 源代码/头文件#include<string.h>#include<ctype.h>#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.h>/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/#define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef intStatus; /Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; /Boolean是布尔类型,其值是TRUE或FALSE typedef int ElemType; / 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 10 / 线性表存储空间的初始分配量 #define LISTINCREMENT 2 / 线性表存储空间的分配增量 typedef structElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位) SqList;/ 顺序表示的线性表的基本操作(12个) Status InitList(SqList *L) / 算法2.3 /操作结果：构造一个空的顺序线性表 (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)exit(OVERFLOW); / 存储分配失败 (*L).length = 0; / 空表长度为0 (*L).listsize = LIST_INIT_SIZE; / 初始存储容量 return OK;Status DestroyList(SqList *L) / 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L free(*L).elem);(*L).elem = NULL;(*L).length = 0;(*L).listsize = 0;return OK;Status ClearList(SqList *L) / 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 (*L).length = 0;return OK;Status ListEmpty(SqList L) / 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE if(L.length = 0)return TRUE;elsereturn FALSE;int ListLength(SqList L) / 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 return L.length;Status GetElem(SqList L, int i, ElemType *e) / 初始条件：顺序线性表L已存在，1iListLength(L) / 操作结果：用e返回L中第i个数据元素的值 if(i < 1 | i > L.length)exit(ERROR);*e = *(L.elem+i-1);return OK;int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType) / 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1,否则为0) / 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 / 若这样的数据元素不存在，则返回值为0。算法2.6 ElemType *p;int i = 1; / i的初值为第1个元素的位序 p = L.elem; / p的初值为第1个元素的存储位置 while(i <= L.length && !compare(*p+, e)+i;if(i<=L.length)return i;elsereturn 0;Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) / 初始条件：顺序线性表L已存在 / 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， / 否则操作失败，pre_e无定义 int i = 2;ElemType *p = L.elem + 1;while(i <= L.length && *p != cur_e)p+;i+;if(i > L.length)return INFEASIBLE;else*pre_e = *-p;return OK;Status NextElem(SqList L, ElemType cur_e, ElemType *next_e) / 初始条件：顺序线性表L已存在 / 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， / 否则操作失败，next_e无定义 int i = 1;ElemType *p = L.elem;while(i < L.length && *p != cur_e)i+;p+;if(i = L.length)return INFEASIBLE;else*next_e = *+p;return OK;Status ListInsert(SqList *L, int i, ElemType e) / 算法2.4 / 初始条件：顺序线性表L已存在，1iListLength(L)+1 / 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *newbase,*q,*p;if(i < 1 | i > (*L).length + 1) / i值不合法 return ERROR;if(*L).length >= (*L).listsize) / 当前存储空间已满,增加分配 newbase = (ElemType *)realloc(*L).elem, (*L).listsize + LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW); / 存储分配失败 (*L).elem = newbase; / 新基址 (*L).listsize += LISTINCREMENT; / 增加存储容量 q = (*L).elem + i - 1; / q为插入位置 for (p = (*L).elem + (*L).length - 1;p >= q; -p) / 插入位置及之后的元素右移 *(p+1) = *p;*q = e; / 插入e +(*L).length; / 表长增1 return OK;Status ListDelete(SqList *L, int i, ElemType *e) / 算法2.5 / 初始条件：顺序线性表L已存在，1iListLength(L) / 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ElemType *p, *q;if(i < 1 | i > (*L).length) / i值不合法return ERROR;p = (*L).elem + i - 1; / p为被删除元素的位置 *e = *p; / 被删除元素的值赋给e q = (*L).elem + (*L).length - 1; / 表尾元素的位置 for (+p; p <= q; +p) / 被删除元素之后的元素左移 *(p-1) = *p;(*L).length-; / 表长减1 return OK;Status ListTraverse(SqList *L, void (*vi)(ElemType*) / 初始条件：顺序线性表L已存在 / 操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败 / vi()的形参加'&'，表明可通过调用vi()改变元素的值 ElemType *p;int i;p = (*L).elem;for(i = 1; i <= (*L).length; i+) vi(p+);/printf("n");return OK;/vivoid print(ElemType *a)printf("%d ",*a);/冒泡排序void sort(SqList *L)int i, j, sign, tmp;for(i = 0; i < L->length - 1; i+)sign = 0;for(j = L->length - 1; j > i; j-)if(L->elemj < L->elemj-1)tmp = L->elemj;L->elemj = L->elemj-1;L->elemj-1 = tmp;sign = 1; /判断当前元素与其它元素是否相等int DuplicateTest(SqList L, ElemType e)int i;ElemType f;for (i = 1; i <= ListLength(L); i+)GetElem(L, i, &f);if (e = f)return TRUE;return FALSE;/Intersectionvoid Intersection(SqList La,SqList Lb,SqList *Lc)int La_length,Lb_length;ElemType a,b; int i=1, j=1, k=1; La_length=La.length;Lb_length=Lb.length;for(i = 1;i <= La_length; i+)GetElem(La, i, &a); for(j=1; j <= Lb_length; j+)GetElem(Lb,j,&b); if(a = b)ListInsert(Lc, k+, a);/UnionStatus Union(SqList La, SqList Lb, SqList *Lc)ElemType e;inti = 1;ClearList(Lc);while(i <= ListLength(La)GetElem(La, i, &e);ListInsert(Lc, 1, e);i+;i = 1;while(i <= ListLength(Lb)GetElem(Lb, i, &e);/get elem from Lbif(DuplicateTest(La, e) = 0)/if all elems are not equal with LaListInsert(Lc, 1, e);i+;return OK;/output输出函数void output(SqList *L)if (ListEmpty(*L)printf(" 该集合为空集!n");elseprintf(" ");sort(L);ListTraverse(L, print);printf("n");/input 输入函数int input(SqList &L)int n;int flag;doflag = scanf("%d", &n);if (flag = 0)printf(" 请输入整数!t");while ( getchar() != 'n' ); /* Clear the input buffer */while (flag != 1);if (n = 0)printf(" 该集合为空集!n");elseinput:printf(" 请输入该集合的元素:");int i, j, e, f, flag;for(i = 1; i <= n; i+)doflag = scanf("%d", &e);if (flag = 0)printf(" 请输入整数!t");while ( getchar() != 'n' ); /* Clear the input buffer */while (flag = 0);ListInsert(&L, i, e);if(n > 1)for (i = 1; i <= n; i+)GetElem(L, i, &e);for (j =i + 1; j <= n; j+)GetElem(L, j, &f);if (e = f)printf(" 集合元素%d有重复,请重新输入n",e);ClearList(&L);goto input;printf(" 该集合为:");output(&L);n = 0;return OK;void operationInterface1()printf(" * ");printf(" * * ");printf(" * 程序名称（Name）： 集合交集并集运算 * ");printf(" * 程序功能（Function）： 求两个集合的交集并集 * ");printf(" * 程序作者（Written By）：刘卓 李玉婷 李啟梅 孙玉婷 王皓靖 王婷 尹淑韵* ");printf(" * 刘金杰 杨冰 * ");printf(" * * ");printf(" * ");printf("n");void operationInterface2(SqList La, SqList Lb, SqList &Lc)printf(" * ");printf(" * Menu * ");printf(" * a.求它们的交集 b.求它们的并集 c.退出 * ");printf(" * * ");printf(" * ");cin:char key;printf("n 请选择ac:t");cin>>key;switch (key)case 'a':case 'A':Intersection(La, Lb, &Lc);printf(" 交集:");output(&Lc);ClearList(&Lc);break;case 'b':case 'B':Union(La, Lb, &Lc);printf(" 并集:");output(&Lc);ClearList(&Lc);break;case 'c':case 'C':printf(" 按任意键退出");getchar();exit(0);break;default:printf(" 错误,请重新输入");goto cin;break;void main()operationInterface1();SqList La,Lb,Lc;InitList(&La);InitList(&Lb);InitList(&Lc);char com;printf(" 请输入集合A的元素个数:");input(La);printf(" 请输入集合B的元素个数:");input(Lb);dooperationInterface2(La, Lb, Lc);printf(" 继续?Y/Nt");doinput:cin>>com;if (com != 'Y' && com != 'y' && com != 'N' && com != 'n')printf(" 请输入正确字符:t");goto doinput;while (com = 'y' | com = 'Y');printf(" 程序结束,谢谢使用!");getchar();exit(0);七. 参考资料1.数据结构（C语言版）(清华大学出版社)2.C+语言程序设计（清华大学出版社）3.数据结构（清华大学出版社）4.算法与数据结构（高等教育出版社）5.数据结构课程设计（机械工业出版社）