数据结构(C语言版)实验报告集合的交并差.doc

《数据结构与算法》实验报告

一、 需求分析
问题描述：编制一个能演示执行集合的并、交和差运算的程序
基本要求：集合元素限定为小写字母[’a’…’z’];演示程序以用户和计算机对话方式执行。集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。计算机终端中显示提示信息之后，由用户自行选择下一步命令，相应输入数据和运算结果在其后显示。
数据测试：
（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.定义顺序表
typedef struct SET{
char *elem;
int size;
int length;
}set;
2 基本操作：
set InitSet(set s);
//初始化集合
set Input(set s);
//向集合中输入元素
set InsertSet(set s, char e);
//向集合中插入元素
set DelateSet(set s,int n);
//从集合中删除元素
void display(set s);
//显示集合
set SetMix(set set1,set set2,set set3);
//求集合的交集
set check(set s);
//检查集合中是否有数字或者重复字母
set Sort(set s);
//对集合中的元素进行排序
三、 详细设计
1. 头文件
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
2. 定义
#define MAX_SIZE 20（顺序表的初始大小）
#define ADD_SIZE 10（顺序表的递增大小）
3. 结构类型
typedef struct SET{
char *elem;
int size;
int length;
}set;

4. 初始化集合
set InitSet(set s){
s.elem=(char*)malloc(MAX_SIZE*sizeof(char));
s.size=MAX_SIZE;
s.length=0;
return s;
}

5. 向集合中输入元素
set Input(set s){
char *newbase;
gets(s.elem);
s.length+=strlen(s.elem);
if(s.size<=s.length){
newbase=(char*)realloc(s.elem,(s.size+ADD_SIZE)*sizeof(char));
s.elem=newbase;
s.size+=ADD_SIZE;
}
return s;
}

6.向集合中插入元素
set InsertSet(set s,char e){
s.elem[s.length]=e;
s.elem[s.length+1]='\0';
s.length++;
return s;
}
7.从集合中删除元素
set DelateSet(set s,int n){
int i;
for(i=n;i<=s.length;i++){
s.elem[i-1]=s.elem[i];
}
s.length--;
return s;
}
8.显示集合
void display(set s){
puts(s.elem);
}
9.检查集合中是否有数字或者重复字母
set check(set s){
int i,j,count;
for(i=1;i<=s.length;i++){
for(j=1;j<i;j++){
if(s.elem[i-1]==s.elem[j-1]){
s=DelateSet(s,i);
i--;
break;
}
}
}
for(i=1;i<=s.length;i++){
if(s.elem[i-1]>'z'||s.elem[i-1]<'a'){
s=DelateSet(s,i);
i--;
}
}
return s;
}
10.求集合的并集
set SetMix(set set1,set set2,set set3){
int i;
for(i=1;i<=set1.length;i++){
set3=InsertSet(set3,set1.elem[i-1]);
}
for(i=1;i<=set2.length;i++){
set3=InsertSet(set3,set2.elem[i-1]);
}
set3=check(set3);
set3=Sort(set3);
return set3;
}
11.求集合的交集
set SetSame(set set1,set set2,set set3){
int i,j;
for(i=1;i<=set1.length;i++){
for(j=1;j<set2.length;j++){
if(set1.elem[i-1]==set2.elem[j-1]){
set3=InsertSet(set3,set1.elem[i-1]);
break;
}
}
}
set3=check(set3);
set3=Sort(set3);
return set3;
}
12.求集合的差
set SetReduce(set set1,set set2,set set3){
int i,j;
for(i=1;i<=set1.length;i++){
set3=InsertSet(set3,set1.elem[i-1]);
}
for(i=1;i<=set3.length;i++){
for(j=1;j<set2.length;j++){
if(set3.elem[i-1]==set2.elem[j-1]){
set3=DelateSet(set3,i);
}
}
}
set3=check(set3);
set3=Sort(set3);
return set3;
}
set Sort(set s){
int i,j;
char temp;
for(i=0;i<s.length-1;i++){
for(j=0;j<s.length-i-1;j++){
if(s.elem[j]>s.elem[j+1]){
temp=s.elem[j];
s.elem[j]=s.elem[j+1];
s.elem[j+1]=temp;
}
}
}
return s;
}
13.主程序
main(){
int i;
set set1,set2,set3;
set1=InitSet(set1);
printf("输入第一个集合：");
set1=Input(set1);
set2=InitSet(set2);
printf("输入第二个集合：");
set2=Input(set2);
set3=InitSet(set3);
printf("选择要进行的操作：1、求交集 2、求并集 3、求集合的差：");
scanf("%d",&i);
if(i==1){
set3=SetSame(set1,set2,set3);
set3=check(set3);
set3=Sort(set3);
printf("交集为：");
display(set3);
}
else if(i==2){
printf("并集为：");
set3=SetMix(set1,set2,set3);
set3=check(set3);
set3=Sort(set3);
display(set3);
}
else if(i==3){
printf("集合的差：");
set3=SetReduce(set1,set2,set3);
set3=check(set3);
set3=Sort(set3);
display(set3);
}
else
printf("输入错误");
return 0;
}
四、 调试分析
1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。
2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。
3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。

五、 用户守则
1.可执行文件为：a.exe
2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。
3.进入演示程序后即显示文本形式的用户界面，再按提示一步步完成：

六、 测试结果
测试数据（1）
1. 求交集

2. 求并集

3.求集合的差

测试数据（2）
1. 交集

2. 并集

3. 差

七、 附录（源代码）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 20
#define ADD_SIZE 10

typedef struct SET{
char *elem;
int size;
int length;
}set;

set InitSet(set s){
s.elem=(char*)malloc(MAX_SIZE*sizeof(char));
s.size=MAX_SIZE;
s.length=0;
return s;
}

set Input(set s){
char *newbase;
gets(s.elem);
s.length+=strlen(s.elem);
if(s.size<=s.length){
newbase=(char*)realloc(s.elem,(s.size+ADD_SIZE)*sizeof(char));
s.elem=newbase;
s.size+=ADD_SIZE;
}
return s;
}

set InsertSet(set s,char e){
s.elem[s.length]=e;
s.elem[s.length+1]='\0';
s.length++;
return s;
}

set DelateSet(set s,int n){
int i;
for(i=n;i<=s.length;i++){
s.elem[i-1]=s.elem[i];
}
s.length--;
return s;
}

void display(set s){
puts(s.elem);
}

set check(set s){
int i,j,count;
for(i=1;i<=s.length;i++){
for(j=1;j<i;j++){
if(s.elem[i-1]==s.elem[j-1]){
s=DelateSet(s,i);
i--;
break;
}
}
}
for(i=1;i<=s.length;i++){
if(s.elem[i-1]>'z'||s.elem[i-1]<'a'){
s=DelateSet(s,i);
i--;
}
}
return s;
}
set SetMix(set set1,set set2,set set3){
int i;
for(i=1;i<=set1.length;i++){
set3=InsertSet(set3,set1.elem[i-1]);
}
for(i=1;i<=set2.length;i++){
set3=InsertSet(set3,set2.elem[i-1]);
}
set3=check(set3);
set3=Sort(set3);
return set3;
}

set SetSame(set set1,set set2,set set3){
int i,j;
for(i=1;i<=set1.length;i++){
for(j=1;j<set2.length;j++){
if(set1.elem[i-1]==set2.elem[j-1]){
set3=InsertSet(set3,set1.elem[i-1]);
break;
}
}
}
set3=check(set3);
set3=Sort(set3);
return set3;
}

set SetReduce(set set1,set set2,set set3){
int i,j;
for(i=1;i<=set1.length;i++){
set3=InsertSet(set3,set1.elem[i-1]);
}
for(i=1;i<=set3.length;i++){
for(j=1;j<set2.length;j++){
if(set3.elem[i-1]==set2.elem[j-1]){
set3=DelateSet(set3,i);
}
}
}
set3=check(set3);
set3=Sort(set3);
return set3;
}
set Sort(set s){
int i,j;
char temp;
for(i=0;i<s.length-1;i++){
for(j=0;j<s.length-i-1;j++){
if(s.elem[j]>s.elem[j+1]){
temp=s.elem[j];
s.elem[j]=s.elem[j+1];
s.elem[j+1]=temp;
}
}
}
return s;
}
main(){
int i;
set set1,set2,set3;
set1=InitSet(set1);
printf("输入第一个集合：");
set1=Input(set1);
set2=InitSet(set2);
printf("输入第二个集合：");
set2=Input(set2);
set3=InitSet(set3);
printf("选择要进行的操作：1、求交集 2、求并集 3、求集合的差：");
scanf("%d",&i);
if(i==1){
set3=SetSame(set1,set2,set3);
set3=check(set3);
set3=Sort(set3);
printf("交集为：");
display(set3);
}
else if(i==2){
printf("并集为：");
set3=SetMix(set1,set2,set3);
set3=check(set3);
set3=Sort(set3);
display(set3);
}
else if(i==3){
printf("集合的差：");
set3=SetReduce(set1,set2,set3);
set3=check(set3);
set3=Sort(set3);
display(set3);
}
else
printf("输入错误");
return 0;
}