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

集合的并、交和差运算实习报告题目：编制一个演示集合的并、交和差运算的程序班级：10092711姓名：魏洲学号：10927128完成日期：2012.4一、需求分析 1.本演示程序中，集合的元素限制在小写字母a-z之间。集合的大小不限制，集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。 2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。 3.程序的执行命令有：1）选择操作 2）任意键清屏 4.数据测试 （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,ai>|ai-1,aiD,i=2, 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已存在。 操作结果：依次遍历l中每个元素带入函数。 ListDelete(&L,i, &e) 初始条件：顺序表l已存在。 操作结果：删除顺序表中第i个元素。 Outputlist(&L)初始条件：顺序表l已存在。 操作结果：输出顺序表的每个元素值。ADT sqlist三、详细设计/ 程序的头文件#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>/ 函数返回值#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 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=0;L.listsize=LIST_INIT_SIZE;return OK;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.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<n;i+)if(ai>='a'&&ai<='z')|(ai>='0'&&ai<='9')ListInsert(L,+len,ai);return OK;Status GetElem(SqList L,int i,ElemType &e)if(i<=0|i>L.length)return ERROR;elsee=*(L.elem+i-1);return OK;Status ListDelete(SqList &L,int i,ElemType &e)if(i<1)|i>L.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);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;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 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;elsecontinue;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<L.length;+i) printf("%c",*(L.elem+i);/程序的主函数void main()system("title 集合的并交叉运算");for(;)system("color a0");int c; printf("*n"); printf(" # 执行程序: 1 # 退出程序: 2n");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 a130, a230; InitList(l1); InitList(l2); InitList(l3);InitList(l4);InitList(l5); InitList(la); printf("请输入第一个集合: "); gets(a1); n1=strlen(a1); for(i=n1-1;i>=0;i-) /从最后一个开始依次与前面的比较 重复赋值为0 for(j=0;j<i;j+) if(a1j=a1i) a1i=0; CreatSqList(l1,a1,n1); la=l1; printf("请输入第二个集合: "); gets(a2); n2=strlen(a2); for(i=n2-1;i>=0;i-) /同上 for(j=0;j<i;j+) if(a1j=a1i) a1i=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("nn*按*任*意*键*清*屏!*"); system("pause>null"); system("cls");elseexit(0);四、调试分析 1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。 2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。 3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文件为：集合的并交差运算.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面：六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行