集合的并交差运算数据结构课程设计

《集合的并交差运算数据结构课程设计》由会员分享，可在线阅读，更多相关《集合的并交差运算数据结构课程设计（9页珍藏版）》请在装配图网上搜索。

1、集合的并、交和差运算实习报告题目：编制一个演示集合的并、交和差运算的程序班级：10092711姓名：魏洲学号：10927128完成日期：2012.4一、需求分析 1.本演示程序中，集合的元素限制在小写字母a-z之间。集合的大小不限制，集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。 2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。 3.程序的执行命令有：1）选择操作 2）任意键清屏 4.数据测

2、试 （1） Set1=”magazine”, Set2=paper”, Set1Set2=”aegimnprz”,Set1Set2=”ae”,Set1-Set2=”gimnz”; (2) Set1=”012oper4a6tion89”,Set2=”error data”,Set1Set2=”adeinoprt”,Set1Set2=”aeort”, Set1-Set2=”inp”.二、概要设计为实现上述功能，需要顺序表这个抽象数据类型。1.顺序表抽象数据类型定义ADT sqlist 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0 数据关系：R1=|ai-1,aiD,i=2,

3、n 基本操作： InitList(&l) 操作结果：构造一个空的顺序表l。 ListLength(l) 初始条件：顺序表l已存在。 操作结果：返回l中的元素个数。 ListInsert_Sq(&L, i, e) 初始条件：顺序表l已存在。 操作结果：在l中第i个元素前面插入元素e。 CreatSqList(&l, a,n) 初始条件：顺序表l已存在。 操作结果：将数组an每个元素赋给顺序表l。 GetElem(L, i, &e) 初始条件：顺序表l已存在。操作结果：返回l中第i个元素的值 LocateElem_Sq(L, e, Status (*compare)() 初始条件：顺序表l已存在。

4、 操作结果：依次遍历l中每个元素带入函数。 ListDelete(&L,i, &e) 初始条件：顺序表l已存在。 操作结果：删除顺序表中第i个元素。 Outputlist(&L)初始条件：顺序表l已存在。 操作结果：输出顺序表的每个元素值。ADT sqlist三、详细设计/ 程序的头文件#include#include#include#include/ 函数返回值#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0#define

5、 LIST_INIT_SIZE 100 /顺序表的初始大小#define LISTINCREMENT 10 /顺序表的递增大小typedef int Status; /返回状态类型typedef char ElemType; /元素类型 typedef structElemType *elem;int length;int listsize;SqList;Status InitList(SqList &L)L.elem=(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType);if(!L.elem) exit(OVERFLOW);L.length=

6、0;L.listsize=LIST_INIT_SIZE;return OK;int ListLength(SqList &L)return L.length;Status ListInsert(SqList &L,int i, ElemType e)if(iL.length+1)return ERROR;if(L.length=L.listsize)ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem

7、 = newbase;L.listsize+=LISTINCREMENT;ElemType *q=&(L.elemi-1);for(ElemType *p = &(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;Status CreatSqList(SqList &L,ElemType a,int n)int len=ListLength(L);for(int i=0;i=a&ai=0&ai=9)ListInsert(L,+len,ai);return OK;Status GetElem(SqList L,int i,El

8、emType &e)if(iL.length)return ERROR;elsee=*(L.elem+i-1);return OK;Status ListDelete(SqList &L,int i,ElemType &e)if(iL.length) return ERROR;ElemType *p = &(L.elemi-1);e=*p;ElemType *q=L.elem+L.length-1;for(+p;p=q;+p) *(p-1)=*p;-L.length;return OK;void paichu(SqList &L) int i,j,l;l=ListLength(L);ElemT

9、ype e,u;for(i=1;i=l-1;i+)GetElem(L,i,e);for(j=1;j=l;j+)GetElem(L,j,u);if(i=j)continue;elseif(u=e)ListDelete(L,j,u);j=1;int LocateElem(SqList &L,ElemType e,Status(*compare)(ElemType,ElemType)int i=1;ElemType *p=L.elem;while(i=L.length&!(*compare)(*p+,e) +i;if(i=L.length) return i;else return 0;Status

10、 JiaoJi(SqList L1,SqList L2, SqList &L3)int L1_len, L2_len,L3_len,i=1,j=1;ElemType e,u;L1_len=ListLength(L1);L2_len=ListLength(L2);L3_len=ListLength(L3);for(i=1;i=1;j-)GetElem(L2,j,u);if(e=u) ListInsert(L3,+L3_len,u); break;elsecontinue;return OK;Status ChaJi(SqList L1,SqList L2,SqList &Ld)SqList Lc

11、;int count=0,Lc_len,L1_len,L2_len,k=1,flag;ElemType e,u,f;InitList(Lc);JiaoJi(L1,L2,Lc);Lc_len=ListLength(Lc);L1_len=ListLength(L1);L2_len=ListLength(L2);for(int i=1;i=L1_len;i+)flag=0;GetElem(L1,i,e);for(int j=1;j=Lc_len;j+) GetElem(Lc,j,u);if(u=e)flag=1;if(flag=0)ListInsert(Ld,k,e);k+;return OK;vo

12、id Union(SqList &La,SqList Lb,SqList &Lc)SqList l1;InitList(l1);JiaoJi(La,Lb,l1);int la_len , lb_len,l1_len,flag;ElemType e,u;int i,j; la_len=ListLength(La); lb_len=ListLength(Lb);l1_len=ListLength(l1);for(i=1;i=la_len;+i)GetElem(La,i,e); ListInsert(Lc,i,e); for(i=1;i=lb_len;+i)flag=0;GetElem(Lb,i,e

13、);for(j=1;j=l1_len;j+)GetElem(l1,j,u);if(u=e)flag=1;if(flag=0)la_len+;ListInsert(Lc,la_len,e);void Outputlist(SqList &L)paichu(L);if(0=L.length)printf(空集!);else for(int i=0;i=0;i-) /从最后一个开始依次与前面的比较 重复赋值为0 for(j=0;j=0;i-) /同上 for(j=0;jnull); system(cls);elseexit(0);四、调试分析 1.本程序的模块划分比较合理，且尽可能的将指针的操作封装

14、在结点和链表的两个模块中，致使集合模块的调试比较成功。 2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。 3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文件为：集合的并交差运算.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面：六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行9