集合的并、交和差运算
题目：编制一个演示集合的并、交和差运算的程序
班级：10092711
姓名：魏洲
学号：10927128
完成日期：2012.4
一、需求分析
1.本演示程序中，集合的元素限制在小写字母‘a’-‘z’之间。集合的大小不限制，集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。
2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。
3.程序的执行命令有：1）选择操作2）任意键清屏
4.数据测试
（1）Set1=”magazine”, Set2=’paper”,
Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”;
(2) Set1=”012oper4a6tion89”,Set2=”error data”,
Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”, Set1-Set2=”inp”.
二、概要设计
为实现上述功能，需要顺序表这个抽象数据类型。
1.顺序表抽象数据类型定义
ADT sqlist{
数据对象：D={ai|a i∈Elemset,i=1,2,3,…n,n>=0}
数据关系：R1={
基本操作：
InitList(&l)
操作结果：构造一个空的顺序表l。
ListLength(l)
初始条件：顺序表l已存在。
操作结果：返回l中的元素个数。
ListInsert_Sq(&L, i, e)
初始条件：顺序表l已存在。
操作结果：在l中第i个元素前面插入元素e。
CreatSqList(&l, a[],n)
初始条件：顺序表l已存在。
操作结果：将数组a[n]每个元素赋给顺序表l。
GetElem(L, i, &e)
初始条件：顺序表l已存在。
LocateElem_Sq(L, e, Status (*compare)())
初始条件：顺序表l已存在。
操作结果：依次遍历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 LIST_INIT_SIZE 100 //顺序表的初始大小
#define LISTINCREMENT 10 //顺序表的递增大小
typedef int Status; //返回状态类型
typedef char ElemType; //元素类型
typedef struct
{
ElemType *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=0;
L.listsize=LIST_INIT_SIZE;
int ListLength(SqList &L)
{
return L.length;
}
Status ListInsert(SqList &L,int i, ElemType e)
{
if(i<1||i>L.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 = newbase;
L.listsize+=LISTINCREMENT;
}
ElemType *q=&(L.elem[i-1]);
for(ElemType *p = &(L.elem[L.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 { if((a[i]>='a'&&a[i]<='z')||(a[i]>='0'&&a[i]<='9')) ListInsert(L,++len,a[i]); } return OK; } Status GetElem(SqList L,int i,ElemType &e) { if(i<=0||i>L.length) return ERROR; else e=*(L.elem+i-1); Status ListDelete(SqList &L,int i,ElemType &e) { if((i<1)||i>L.length) return ERROR; ElemType *p = &(L.elem[i-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); ElemType 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; else { if(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 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<=L1_len;i++) { GetElem(L1,i,e); for(j=L2_len;j>=1;j--) { GetElem(L2,j,u); if(e==u) { ListInsert(L3,++L3_len,u); break; } else continue; } } return OK; } Status ChaJi(SqList L1,SqList L2,SqList &Ld) { SqList Lc; 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; } void 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); 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 { printf("%c",*(L.elem+i)); } } //程序的主函数 void main() { system("@title 集合的并交叉运算"); for(;;) { system("color a0"); int c; printf("****************************************************************\n"); printf(" ######## 执行程序: 1 ######## 退出程序: 2\n"); printf("****************************************************************\n"); printf("请按键选择: "); scanf("%d",&c); getchar(); printf("\n"); if(c==1) { SqList l1,l2,l3,l4,l5,la; int n1,n2,i,j; char a1[30], a2[30]; InitList(l1); InitList(l2); InitList(l3); InitList(l4); InitList(l5); InitList(la); printf("请输入第一个集合: "); gets(a1); n1=strlen(a1); { for(j=0;j { if(a1[j]==a1[i]) a1[i]=0; } } CreatSqList(l1,a1,n1); la=l1; printf("请输入第二个集合: "); gets(a2); n2=strlen(a2); for(i=n2-1;i>=0;i--) //同上 { for(j=0;j { if(a1[j]==a1[i]) a1[i]=0; } } CreatSqList(l2,a2,n2); printf("操作运算符:U、D、I为交并差按#退出\n"); char char1; scanf("%c",&char1); while(char1!='#') { switch(char1) { case 'U':printf("集合的交集是: ");JiaoJi(l1,l2,l3);Outputlist(l3);printf("\n");break; case 'I':printf("集合的并集是: ");Union(l1,l2,l5);Outputlist(l5); printf("\n");break; case 'D':printf("集合的差集是: ");ChaJi(l1,l2,l4);Outputlist(l4);printf("\n");break; } scanf("%c",&char1); } printf("\n\n*****************按*任*意*键*清*屏!********************"); system("pause>null"); system("cls"); else exit(0); } } 四、调试分析 1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。 2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。 3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。 五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文件为：集合的并交差运算.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面： 六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行
相关主题
文本预览