《数据结构课程设计报告集合运算》由会员分享，可在线阅读，更多相关《数据结构课程设计报告集合运算（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告设计题目： 集合运算专 业 班 级 学 生 学 号 指导教师 2011年5月目 录一.设计题目2（一）.题目：集合运算2（二）.问题描述和分析2二.设计内容3(一). 数据结构设计3(二). 算法设计3三.概要设计4(一).程序结构图4（二）.具体程序设计4四.算法分析5源代码5五.结果分析16六.心得体会21七.参考文献22一.设计题目（一）.题目：集合运算功能：使用链表来表示集合，完成集合的合并，求交集等操作。主要包含以下内容：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2完成最低要求； 3进一步要求：要求：1）界面友好，函数功能要划分好2）总体设计
2、应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。（二）.问题描述和分析 本课程设计中，链表长度不能超过100，集合输入的形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤。输出的运算结果字符串中将不含重复字符或非法字符。 问题描述： 有两个集合A、B，要求它的交集、并集。用两个链表L1、L2存储集合A、B。描 述该问题的存储结构，算法，并通过编写程序来实现。 问题分析： 1. 定义一个链表来存储集合元素； 2. 链表L包括数据域和指针域，数据域中存
3、储集合元素，指针域中存储下一个集合元素的位置； 3. 创建若干个基本函数，通过函数调用对链表进行作，实现集合的交、并运算。 二.设计内容(一). 数据结构设计 1. 数据结构设计考虑 创建三个带头结点的单链表，用来存储两个集合中的元素和最终的结果，为实现集合的交，并运算功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。 2. 逻辑结构存储结构 逻辑结构： 创造一个带结点的单链表包括（头结点L，结点若干，尾结点） 单链表中每个结点包括（*next 表示指针data表示域） (二). 算法设计 程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘
4、上输入演示程序中规定的运算命令；相应的输入数据（滤输入中的非法字符）和运算结果显示在其后。 程序执行的命令包括： a) 构造集合A； b) 构造集合B； c) 求交集； d) 求并集； e) 结束。 “构造集合A”和“构造集合B”时，需以字符串的形式键入集合元素。三.概要设计(一).程序结构图Main函数InterSect交函数Union并函数Sort链表排序函数CreateList尾插法建表DispList输出函数（二）.具体程序设计1.定义链表 typedef int ElemType；typedef struct Lnode2.返回链表长度3.返回指定节点的值4.定位制定值的节点的值5.
5、显示链表 void display(struct Lnode *L)6.创建链表，并设置链表为空 void creat(struct Lnode *L)7.向链表中插入元素 void insert(struct Lnode *L,int n,ElemType 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,st
6、ruct Lnode *L2,struct Lnode *L3)13.求并集unionset(struct Lnode *L1,struct Lnode *L2,struct Lnode *L3)14.把L1复制到L3，然后比较L2和L3，得到L2与L3中没有的元素，并插入15.插在排序的位置上insert(&*L3,k,t2-data); 16.插在链尾四.算法分析源代码如下：#include #include #include #define null 0#define M 100typedef int ElemType;/*定义链表*/typedef struct Lnode ElemT
7、ype data; struct Lnode *next;int lenth(struct Lnode *L) int n=0; struct Lnode *t; t=*L; while(t!=null) 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 printf(The %dth Lnode havent find !n,n); int locate(struc
8、t Lnode *L,ElemType x ) int n=1;struct Lnode *t; t=*L;while (t!=null&t-data!=x)t=t-next; n+;if(t=null) return(0); else 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 cre
9、at(struct Lnode *L)/*创建链表*/ *L=null;void insert(struct Lnode *L,int n,ElemType x)/*向链表中插入元素*/ struct Lnode *t1,*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; els
10、e printf(Insert error!); void delete(struct Lnode *L,int n) int i=1;struct Lnode *t1,*t2; t1=*L;if(n=1) t2=t1; *L=t1-next; else while(inext!=null) t1=t1-next; i+; if(t1-next!=null&i=n-1) t2=t1-next; t1-next=t2-next; else printf(Delete error!n); if(t2=null) free(t2); void init(struct Lnode *L,int len
11、)/*初始化链表*/ int dM,i,j,k,ti; struct Lnode *t;input: for(i=1;i=len;i+) scanf(%d,&di); for(j=1;j=len;j+) for(k=j+1;kdk) ti=dj; dj=dk; dk=ti; for(i=1;ilen;i+) if(di=di+1) printf(Dont allow the same data! Please reinput!); goto input; creat(&*L); for(i=1;i=len;i+) insert(&*L,i,di); printf(The data of the linktable is:
