数据结构(C语言版)实验报告-集合的交并差.docx
《数据结构(C语言版)实验报告-集合的交并差.docx》由会员分享，可在线阅读，更多相关《数据结构(C语言版)实验报告-集合的交并差.docx（15页珍藏版）》请在冰点文库上搜索。
《数据结构与算法》实验报告
一、需求分析
问题描述：
编制一个能演示执行集合的并、交和差运算的程序
基本要求：
集合元素限定为小写字母[’a’…’z’];演示程序以用户和计算机对话方式执行。
集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。
计算机终端中显示提示信息之后，由用户自行选择下一步命令，相应输入数据和运算结果在其后显示。
数据测试：
（1）Set1=”magazine”,Set2=’paper”,
Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”;
（2）Set1=”012oper4a6tion89”,Set2=”errordata”,
Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”,Set1-Set2=”inp”.
二、概要设计
运用顺序表
1.定义顺序表
typedefstructSET{
char*elem;
intsize;
intlength;
}set;
2基本操作：
setInitSet（sets）;
//初始化集合
setInput（sets）;
//向集合中输入元素
setInsertSet（sets,chare）;
//向集合中插入元素
setDelateSet（sets,intn）;
//从集合中删除元素
voiddisplay（sets）;
//显示集合
setSetMix（setset1,setset2,setset3）;
//求集合的交集
setcheck（sets）;
//检查集合中是否有数字或者重复字母
setSort（sets）;
//对集合中的元素进行排序
三、详细设计
1.头文件
#include
#include
#include
2.定义
#defineMAX_SIZE20（顺序表的初始大小）
#defineADD_SIZE10（顺序表的递增大小）
3.结构类型
typedefstructSET{
char*elem;
intsize;
intlength;
}set;
4.初始化集合
setInitSet（sets）{
s.elem=（char*）malloc（MAX_SIZE*sizeof（char））;
s.size=MAX_SIZE;
s.length=0;
returns;
}
5.向集合中输入元素
setInput（sets）{
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;
}
returns;
}
6.向集合中插入元素
setInsertSet（sets,chare）{
s.elem[s.length]=e;
s.elem[s.length+1]='\0';
s.length++;
returns;
}
7.从集合中删除元素
setDelateSet（sets,intn）{
inti;
for（i=n;i<=s.length;i++）{
s.elem[i-1]=s.elem[i];
}
s.length--;
returns;
}
8.显示集合
voiddisplay（sets）{
puts（s.elem）;
}
9.检查集合中是否有数字或者重复字母
setcheck（sets）{
inti,j,count;
for（i=1;i<=s.length;i++）{
for（j=1;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--;
}
}
returns;
}
10.求集合的并集
setSetMix（setset1,setset2,setset3）{
inti;
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）;
returnset3;
}
11.求集合的交集
setSetSame（setset1,setset2,setset3）{
inti,j;
for（i=1;i<=set1.length;i++）{
for（j=1;j if（set1.elem[i-1]==set2.elem[j-1]）{
set3=InsertSet（set3,set1.elem[i-1]）;
break;
}
}
}
set3=check（set3）;
set3=Sort（set3）;
returnset3;
}
12.求集合的差
setSetReduce（setset1,setset2,setset3）{
inti,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 if（set3.elem[i-1]==set2.elem[j-1]）{
set3=DelateSet（set3,i）;
}
}
}
set3=check（set3）;
set3=Sort（set3）;
returnset3;
}
setSort（sets）{
inti,j;
chartemp;
for（i=0;i for（j=0;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;
}
}
}
returns;
}
13.主程序
main（）{
inti;
setset1,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）;
}
elseif（i==2）{
printf（"并集为：
"）;
set3=SetMix（set1,set2,set3）;
set3=check（set3）;
set3=Sort（set3）;
display（set3）;
}
elseif（i==3）{
printf（"集合的差：
"）;
set3=SetReduce（set1,set2,set3）;
set3=check（set3）;
set3=Sort（set3）;
display（set3）;
}
else
printf（"输入错误"）;
return0;
}
四、调试分析
1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。
2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。
3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：
元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。
五、用户守则
1.可执行文件为：
a.exe
2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。
3.进入演示程序后即显示文本形式的用户界面，再按提示一步步完成：
六、测试结果
测试数据
（1）
1.求交集
2.求并集
3.求集合的差
测试数据
（2）
1.交集
2.并集
3.差
七、附录（源代码）
#include
#include
#include
#defineMAX_SIZE20
#defineADD_SIZE10
typedefstructSET{
char*elem;
intsize;
intlength;
}set;
setInitSet（sets）{
s.elem=（char*）malloc（MAX_SIZE*sizeof（char））;
s.size=MAX_SIZE;
s.length=0;
returns;
}
setInput（sets）{
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;
}
returns;
}
setInsertSet（sets,chare）{
s.elem[s.length]=e;
s.elem[s.length+1]='\0';
s.length++;
returns;
}
setDelateSet（sets,intn）{
inti;
for（i=n;i<=s.length;i++）{
s.elem[i-1]=s.elem[i];
}
s.length--;
returns;
}
voiddisplay（sets）{
puts（s.elem）;
}
setcheck（sets）{
inti,j,count;
for（i=1;i<=s.length;i++）{
for（j=1;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--;
}
}
returns;
}
setSetMix（setset1,setset2,setset3）{
inti;
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）;
returnset3;
}
setSetSame（setset1,setset2,setset3）{
inti,j;
for（i=1;i<=set1.length;i++）{
for（j=1;j if（set1.elem[i-1]==set2.elem[j-1]）{
set3=InsertSet（set3,set1.elem[i-1]）;
break;
}
}
}
set3=check（set3）;
set3=Sort（set3）;
returnset3;
}
setSetReduce（setset1,setset2,setset3）{
inti,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 if（set3.elem[i-1]==set2.elem[j-1]）{
set3=DelateSet（set3,i）;
}
}
}
set3=check（set3）;
set3=Sort（set3）;
returnset3;
}
setSort（sets）{
inti,j;
chartemp;
for（i=0;i for（j=0;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;
}
}
}
returns;
}
main（）{
inti;
setset1,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）;
}
elseif（i==2）{
printf（"并集为：
"）;
set3=SetMix（set1,set2,set3）;
set3=check（set3）;
set3=Sort（set3）;
display（set3）;
}
elseif（i==3）{
printf（"集合的差：
"）;
set3=SetReduce（set1,set2,set3）;
set3=check（set3）;
set3=Sort（set3）;
display（set3）;
}
else
printf（"输入错误"）;
return0;
}
升级会员 