数据结构课程设计报告集合运算

1、数据结构 课程设计报告 设计题目： 集合运算 专 业 班 级 学 生 学 号 指导教师 2011 年 5 月 1 目目 录录 一一.设计题目设计题目 .2 （一）.题目：集合运算.2 （二）.问题描述和分析.2 二二.设计内容设计内容 .3 (一). 数据结构设计.3 (二). 算法设计.3 三三.概要设计概要设计 .4 (一一).程序结构图程序结构图.4 （二）.具体程序设计.4 四四.算法分析算法分析 .5 源代码.5 五五.结果分析结果分析 .16 六六.心得体会心得体会 .21 七七.参考文献参考文献 .22 2 一一.设计题目设计题目 （一）.题目：集合运算 功能：使用链表来表示集合

2、，完成集合的合并，求交集等操作。 主要包含以下内容： 1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2完成最低要求； 3进一步要求： 要求：1）界面友好，函数功能要划分好 2）总体设计应画一流程图 3）程序要加必要的注释 4）要提供程序测试方案 5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运 行的程序是没有价值的。 （二）.问题描述和分析 本课程设计中，链表长度不能超过 100，集合输入的形式为一个以“回车符”为 结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程 序应能自动滤。输出的运算结果字符串中将不含重复字符或非法字符。 问题描述：

3、 有两个集合 a、b，要求它的交集、并集。用两个链表 l1、l2 存储集合 a、b。描 述该问题的存储结构，算法，并通过编写程序来实现。 问题分析： 1. 定义一个链表来存储集合元素； 2. 链表 l 包括数据域和指针域，数据域中存储集合元素，指针域中存储下一个 集合元素的位置； 3. 创建若干个基本函数，通过函数调用对链表进行作，实现集合的交、并运算。 3 二二.设计内容设计内容 (一). 数据结构设计 1. 数据结构设计考虑 创建三个带头结点的单链表，用来存储两个集合中的元素和最终的结果，为实 现集合的交，并运算功能，应以有序链表表示集合。为此，需要两个抽象数据 类型：有序表和集合。 2.

4、 逻辑结构存储结构 逻辑结构： 创造一个带结点的单链表包括（头结点 l，结点若干，尾结点） 单链表中每个结点包括（*next 表示指针 data 表示域） (二). 算法设计 程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后， 由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤输入中 的非法字符）和运算结果显示在其后。 程序执行的命令包括： a) 构造集合 a； b) 构造集合 b； c) 求交集； d) 求并集； e) 结束。 “构造集合 a”和“构造集合 b”时，需以字符串的形式键入集合元素。 4 三三.概要设计概要设计 (一).程序结构图 main 函

5、数 intersect 交函数 union 并函数 sort 链表排 序函数 createlist 尾插法建 表 displist 输出函 数 （二）.具体程序设计 1.定义链表 typedef int elemtype； typedef struct lnode 2.返回链表长度 3.返回指定节点的值 4.定位制定值的节点的值 5.显示链表 void display(struct lnode *l) 6.创建链表，并设置链表为空 void creat(struct lnode *l) 7.向链表中插入元素 void insert(struct lnode *l,int n,elemtype

6、x) 8.插在第 n 个节点的前面 9.删除指定位置的节点 10.初始化链表 void init(struct lnode *l,int len) 11.复制链表 l1 到 l2 void copy(struct lnode *l1,struct lnode *l2 ) 12.求交集 void intersection(struct lnode *l1,struct lnode *l2,struct lnode *l3) 13.求并集 unionset(struct lnode *l1,struct lnode *l2,struct lnode *l3) 14.把 l1 复制到 l3，然后比较

7、 l2 和 l3，得到 l2 与 l3 中没有的元素，并插入 15.插在排序的位置上 insert( 16.插在链尾 5 四四.算法分析算法分析 源代码如下如下： #include #include #include #define null 0 #define m 100 typedef int elemtype;/*定义链表*/ typedef struct lnode elemtype data; struct lnode *next; ; int lenth(struct lnode *l) int n=0; struct lnode *t; t=*l; while(t!=null)

8、n+; t=t-next; return n; elemtype get(struct lnode *l,int n) int i=1; struct lnode *t; t=*l; while (inext; i+; if(t!=null) return(t-data); else 6 printf(the %dth lnode havent find !n,n); int locate(struct lnode *l,elemtype x ) int n=1; struct lnode *t; t=*l; while (t!=null n+; if(t=null) return(0); e

9、lse return(n); void display(struct lnode *l)/*显示链表*/ struct lnode *t; t=*l; if(t=null) printf(the link is null!); else do printf(%d,t-data); t=t-next; while(t!=null); printf(n); void creat(struct lnode *l)/*创建链表*/ 7 *l=null; void insert(struct lnode *l,int n,elemtype x)/*向链表中插入元素*/ struct lnode *t1,

10、*t2; int j=1; t1=(struct lnode *)malloc(sizeof(struct lnode); t1-data=x; t2=*l; if(n=1) t1-next=t2; *l=t1; else while(jnext!=null) t2=t2-next; j+; if(j=n-1) t1-next=t2-next; t2-next=t1; else printf(insert error!); void delete(struct lnode *l,int n) int i=1; struct lnode *t1,*t2; t1=*l; if(n=1) t2=t1

11、; *l=t1-next; else 8 while(inext!=null) t1=t1-next; i+; if(t1-next!=null t1-next=t2-next; else printf(delete error!n); if(t2=null) free(t2); void init(struct lnode *l,int len)/*初始化链表*/ int dm,i,j,k,ti; struct lnode *t; input: for(i=1;i=len;i+) scanf(%d, for(j=1;j=len;j+) for(k=j+1;kdk) ti=dj; dj=dk;

12、 dk=ti; for(i=1;ilen;i+) if(di=di+1) printf(dont allow the same data! please reinput!); 9 goto input; creat( for(i=1;i=len;i+) insert( printf(the data of the linktable is: ); display( void copy(struct lnode *l1,struct lnode *l2 )/*复制链表 l1 到 l2*/ int i,len; elemtype t; len=lenth( creat( for(i=1;i=len

13、;i+) t=get( insert( void intersection(struct lnode *l1,struct lnode *l2,struct lnode *l3)/*求交集*/ int i,j,k=1; struct lnode *t1,*t2; t1=*l1; t2=*l2; creat( for(i=1;i=lenth(i+) for(j=1;jdata=t2-data) insert( k+; t2=t2-next; 10 t1=t1-next; t2=*l2; unionset(struct lnode *l1,struct lnode *l2,struct lnode

14、 *l3)/* 求并集*/ int i,j,k; struct lnode *tt,*t2,*t3; creat( copy( t2=*l2; t3=*l3; for(i=1;i=lenth(i+) k=1; for(j=1;jdata=t3-data) k=0; break; else if(t2-datadata) break; else if(t2-datat3-data) k+; if(knext; if(k0 else if(klenth( tt-data=t2-data; 11 tt-next=null; t3-next=tt; t2=t2-next; t3=*l3; void d

15、iffrenceset(struct lnode *l1,struct lnode *l2,struct lnode *l3) int i,t,n; creat( copy( for(i=1;i=lenth(i+) t=get( n=locate( if(n) delete( main() int len1,len2; char r; static struct lnode *head1,*head2,*head3,*head4; printf(/*the begin*/n); printf(please input the lenth of the first linktable! ); s

16、canf(%d, printf(the lenth of the first linktable is %d,please input %d datas! ,len1,len1); init( printf(/-/n); printf(please input the lenth of the second linktable! ); scanf(%d, printf(the lenth of the second linktable is %d,please input %d datas! ,len2,len2); init( printf(nn/-/n); intersection( pr

17、intf(the intersection of two linktable: ); display( unionset( 12 printf(the union set of two linktable: ); display( printf(/*the end*/n); 五五.结果分析结果分析 1.在 turboc2.01 环境中输入源代码 2.按 atl+f9 编译文件 得到以下结果，发现无错误。 13 3.由提示按任意键，后按 ctrl+f9 编译运行，得到以下结果。 给第一个链表的长度设为 5 后按 enter 程序开始（程序开始（thethe beginbegin） 4.输入以下数

18、字：10 25 78 99 1000 14 5.输完数字后按 enter,得到以下结果，第一个链表输入完毕。 6.由提示任意给定第二个链表长度为 17。 15 7.屏幕提示链表长度已定，并要求输入 17 个数字。 8.输入以下 17 个数字：1 2 3 4 5 6 7 8 9 28 78 86 99 100 120 150 10000 16 9.按 enter 屏幕显示如下 10.按 alt+f5 查看输出结果 得出交集：78 99 并集：1 2 3 4 5 6 7 8 9 10 25 28 78 86 99 100 120 150 1000 10000 17 程序结束程序结束(the(the end)end) 18 六六.心得体会心得体会 通过实践才发现 c 语言程序设计的掌握直接关系