# 数据结构课程设计大曝光（1）
**注:转发请注明出处，以免老师误以为本人从网上抄袭……**
[TOC]
# 课程设计一 集合的并、交和差
## 一、实习目的和任务：
### 【问题描述】
编制一个能演示执行集合的并、交和差运算的程序
### 【基本要求】
1）集合的元素限定为小写字母；
2）演示程序以用户和计算机的对话方式执行。
## 二、概要设计：
### 1.集合结构的顺序表实现
#### Status InitList_Sq(SqList &L)
操作结果：构造一个空的线性表L。
#### void destroy(SqList &L)
初始条件：线性表L已存在
操作结果：销毁顺序表
#### int length(SqList &L)
初始条件：线性表L已存在
操作结果：返回线性表长度
#### Status ListInsert_Sq(SqList &L,int i,ElemType e)
初始条件：线性表L已存在，i的合法值为1<=i<=ListLength.Sq(L)+1
操作结果：在顺序线性表L中第i个位置之前插入新的元素e
#### int equal(ElemType a,ElemType b)
操作结果：数据元素判定函数之一，用于判定两元素是否相等
#### int locateElem(SqList L,ElemType e,int (* compare)(ElemType,ElemType))
初始条件：线性表L已存在，compare()位数据元素判定函数
操作结果：在顺序线性表L中查找第1个值与e满足compare()的元素的位序
#### void union2new(SqList &La,SqList &Lb,SqList &Lc)
初始条件：线性表L已存在
操作结果：合并顺序线性表La和Lb的元素到一个新表中
#### void union2src(SqList &La,SqList &Lb)
初始条件：线性表L已存在
操作结果：将所有在线性表Lb中但不在La中的元素插入到La中
#### void commen(SqList &La,SqList &Lb,SqList &Lc)
初始条件：线性表L已存在
操作结果：求La，Lb的交集并存入Lc中
#### void decommen(SqList &La,SqList &Lb,SqList &Lc)
初始条件：线性表L已存在
操作结果：求La与Lb的差集并存入Lc中
#### int check(SqList &L)
初始条件：线性表L已存在
操作结果：检验是线性表L是否符合集合条件(元素必须为小写，元素不要重复)，符合返回0，不满足元素为小写返回1，不满足不重复返回2
#### void input(SqList &L)
初始条件：线性表L已存在
操作结果：依键盘输入建立L中的元素
#### void print(SqList &L)
初始条件：线性表L已存在
操作结果：依次输出L中的元素
### 2、用户交互的实现：
- char precmd[]---------------------------------定义用户可以使用的命令
- int isCmd(char cmd) ------------------------判断是否为可识别的命令，即是否存在于precmd中
- void Pause() ----------------------------------暂停并按任意键继续
- void Help() ------------------------------------输出命令帮助
- void openScreen()-----------------------------输出开始界面
- void Goodbye(SqList &sl1,SqList &sl2,SqList &sl3)----------------退出界面并完成销毁工作
- void CMDtran(char c,SqList &sl1,SqList &sl2,SqList &sl3)---------解释命令并执行
- char inCMD()---------------------------------命令输入函数
## 三、程序代码：
```C
/*------------------------------------------
Name: 集合交并差演示程序
Copyleft: huaying1988.com
Author: huaying1988.com
Date: 21-02-06 21:16
Description:
集合的并、交和差
【问题描述】
编制一个能演示执行集合的并、交和差运算的程序
【基本要求】
1）集合的元素限定为小写字母；
2）演示程序以用户和计算机的对话方式执行。
-------------------------------------------*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
int equal(ElemType a,ElemType b)
{//比较a，b是否满足相等关系
if(a==b)return 1;
else return 0;
}//equal
//----------线性表的动态分配顺序存储结构---------------
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空姐的分配增量
typedef struct
{
ElemType * elem; //存储空间基址
int length; //当前长度
int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList,* SqLink;
//--------------------线性表的动态分配顺序存储结构----------------------
Status InitList_Sq(SqList &L)
{//构造一个空的线性链表L。
if(!L.elem)free(L.elem);//如果Lc中有元素则释放
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW); //存储分配失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE; //初始存储容量
return OK;
}//InitList_Sq
void destroy(SqList &L)
{//删除顺序表
L.length=0; //空表长度为0
L.listsize=0; //初始存储容量
free(L.elem);
}//destroy
int length(SqList &L)
{//返回线性表长度
return L.length;
}//length
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
//在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为1<=i<=ListLength.Sq(L)+1
ElemType * newbase;
if(i<1||i>L.length+1)return ERROR; //i值不合法
if(L.length>=L.listsize)
{ //当前存储空间已满，增加分配
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]),*p; //q未插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
//插入位置及之后的元素右移
*q=e; //插入e
++L.length; //表长增1
return OK;
}//ListInsert_Sq
int locateElem(SqList L,ElemType e,int (* compare)(ElemType,ElemType))
{//在顺序线性表L中查找第1个值与e满足compare()的元素的位序
//若找到，则返回其在L中的位序，否则返回0
int i;
ElemType *p=L.elem;//p的初值为第1个元素的存储位置
for(i=1;i<=L.length&&!compare(*p++,e);i++);//i的初值为第1个元素的位次//空循环
if(i<=L.length)return i;
else return 0;
}//locateElem
void union2new(SqList &La,SqList &Lb,SqList &Lc)
{//合并顺序线性表La和Lb的元素到一个新表中
ElemType e;
int La_len=La.length;
int j=0,i;
InitList_Sq(Lc);//对Lc进行初始化
for(i=0;i<La.length;i++)//将La直接并入Lc
{
e=La.elem[i];
ListInsert_Sq(Lc,++j,e);
}
for(i=0;i<Lb.length;i++)//分情况将Lb并入
{
e=Lb.elem[i];
if(!locateElem(La,e,equal))
ListInsert_Sq(Lc,++j,e);
}
}//union2new
void union2src(SqList &La,SqList &Lb)
{//将所有在线性表Lb中但不在La中的元素插入到La中
ElemType e;
int La_len=La.length;
for(int i=0;i<Lb.length;i++)
{
e=Lb.elem[i];
if(!locateElem(La,e,equal))
ListInsert_Sq(La,++La_len,e);
}
}//union2src
void commen(SqList &La,SqList &Lb,SqList &Lc)
{//求La，Lb的交集并存入Lc中
ElemType e;
int La_len=La.length;
int j=0;
InitList_Sq(Lc);//对Lc进行初始化
for(int i=0;i<Lb.length;i++)
{
e=Lb.elem[i];
if(locateElem(La,e,equal))
ListInsert_Sq(Lc,++j,e);
}
}//commen
void decommen(SqList &La,SqList &Lb,SqList &Lc)
{//求La与Lb的差集并存入Lc中
ElemType e;
int j=0;
InitList_Sq(Lc);//对Lc进行初始化
for(int i=0;i<La.length;i++)
{
e=La.elem[i];
if(!locateElem(Lb,e,equal))
ListInsert_Sq(Lc,++j,e);
}
}//decommen
int check(SqList &L)
{//检验是否符合集合条件(元素必须为小写，元素不要重复)
//符合返回0，不满足元素为小写返回1，不满足不重复返回2
int i,j;
for(i=0;i<L.length-1;i++)
{
if(L.elem[i]<'a'||L.elem[i]>'z')return 1;
for(j=i+1;j<L.length;j++)
if(L.elem[i]==L.elem[j])return 2;
}
return 0;
}//check
void input(SqList &L)
{//依次从键盘输入L中的元素
char in;//输入临时变量
int flag;//是否为集合标志
if(L.length>0)InitList_Sq(L);
do{
for(in=getchar();in!='\n';in=getchar())
ListInsert_Sq(L,L.length+1,in);//向集合1中输入数据
// printf("check:%d",check(L));
if(flag=check(L))//check符合条件时返回0
{
if(flag==1)
printf("元素必须为小写字母，请重新输入:\n");
else
printf("元素不要重复，请重新输入:\n");
InitList_Sq(L);
}
}while(flag);
}//input
void print(SqList &L)
{//依次输出L中的元素
int i;
if(L.length==0)
printf("此集合为空集");
else
for(i=0;i<L.length;i++)
printf("%c",L.elem[i]);
printf("\n");
}//print
//-----------------------------命令及界面 函数 定义 开始-----------------------
char *precmd="aAbBuUiIdDpPrRsSHhEexX\033";
int isCmd(char cmd)
{//判断是否为命令
int i;
for(i=0;precmd[i]!='\0';i++)
{
if(precmd[i]==cmd)return 1;
}
return 0;
}
void Pause()
{//按任意键继续
printf("\n按任意键继续……\n");
getch();
}//Pause
void Help()
{//命令帮助
printf("命令说明：\n\
h/H(help)----------命令帮助\n\
a/A------------------建立/重建集合a\n\
b/B------------------建立/重建集合b\n\
s/S(show)------------显示a,b两个集合\n\
u/U(union)-----------计算并输出两集合的并\n\
i/I(intersection)----计算并输出两集合的交\n\
d/D(difference)------计算并输出a与b的差\n\
p/P(difference)------计算并输出b与a的差\n\
r/R(result)----------计算结果并全部输出\n\
e/E,x/X(exit)--------退出\n");
}//Help
void openScreen()
{//开始界面美化
system("color f0");
system("title 集合交并差演示程序 WrittenBy huaying1988.com");
printf("\n\n\t\t\t集合交并差演示程序\n");
printf("\t\t\t****大学\n");
printf("\t\t\t**学院 **07-*\n");
printf("\t\t\thuaying1988.com 学号:07*********\n");
printf("\n\t\t\t\t\t---WrittenBy huaying1988.com\n\n\n");
Help();
}//openScreen
void Goodbye(SqList &sl1,SqList &sl2,SqList &sl3)
{//退出界面及后续工作
printf("\n\n\nGoodbye ^_^ ~!\n\n\n\t\t\t\t\t ***CopyLeft # WrittenBy huaying1988.com***\n");//结束语
Pause();
destroy(sl1);destroy(sl2);destroy(sl3);//释放已申请空间
exit(0);
}//Goodbye
void CMDtran(char c,SqList &sl1,SqList &sl2,SqList &sl3)
{//解释命令并执行
putch('\n');
//char o;
switch(c)
{
case 'a'://pass through
case 'A'://建立/重建集合a
if(sl1.length>0){
printf("集合a已存在，是否重建？(y/*)\n");
if(getch()=='y')
{
printf("请输入集合a的元素（小写字符，不要重复，不用分隔，按enter确定):\n");
input(sl1);//向集合1中输入数据
}//if(getch)
else{
printf("用户撤销重建\n");
}//else
}//if(t)
else{
printf("请输入集合a的元素（小写字符，不要重复，不用分隔，按enter确定):\n");
input(sl1);//向集合1中输入数据
}//else
break;
case 'b'://pass through
case 'B'://建立/重建集合b
if(sl2.length>0){
printf("集合b已存在，是否重建？(y/*)\n");
if(getch()=='y')
{
printf("请输入集合b的元素（小写字符，不要重复，不用分隔，按enter确定):\n");
input(sl2);//向集合2中输入数据
}//if(getch)
else{
printf("用户撤销重建\n");
}//else
}//if(t)
else{
printf("请输入集合b的元素（小写字符，不要重复，不用分隔，按enter确定):\n");
input(sl2);//向集合2中输入数据
}//else
break;
case 'u'://pass through
case 'U'://计算并输出两集合的并
union2new(sl1,sl2,sl3);//求并
printf("两集合的并为：");//显示两集合的并
print(sl3);
break;
case 'i'://pass through
case 'I'://计算并输出两集合的交
commen(sl1,sl2,sl3);//求交
printf("两集合的交为：");//显示两集合的交
print(sl3);
break;
case 'd'://pass through
case 'D'://计算并输出a与b的差
decommen(sl1,sl2,sl3);
printf("集合a与集合b的差为：");//显示集合1与集合2的差
print(sl3);
break;
case 'p'://pass through
case 'P'://计算并输出b与a的差
decommen(sl2,sl1,sl3);//求差
printf("集合b与集合a的差为：");//显示集合2与集合1的差
print(sl3);
break;
case 'r'://pass through
case 'R'://计算结果并全部输出
printf("集合a为：");//显示集合a
print(sl1);
printf("集合b为：");//显示集合b
print(sl2);
union2new(sl1,sl2,sl3);//求并
printf("两集合的并为：");//显示两集合的并
print(sl3);
commen(sl1,sl2,sl3);//求交
printf("两集合的交为：");//显示两集合的交
print(sl3);
decommen(sl1,sl2,sl3);
printf("集合a与集合b的差为：");//显示集合1与集合2的差
print(sl3);
decommen(sl2,sl1,sl3);//求差
printf("集合b与集合a的差为：");//显示集合2与集合1的差
print(sl3);
break;
case 's'://pass through
case 'S'://显示a,b两个集合
printf("集合a为：");//显示集合a
print(sl1);
printf("集合b为：");//显示集合b
print(sl2);
break;
case 'H'://pass through
case 'h'://命令帮助
Help();
break;
case 27://pass through
case 'x'://pass through
case 'X'://pass through
case 'e'://pass through
case 'E'://退出
Goodbye(sl1,sl2,sl3);
break;
default://其他输入
printf("不能识别的命令\n");
}//switchn cmd;
}//CMDtran
char inCMD()
{//命令输入函数
char cmd;
printf("h-help,x-exit|cmd>");
do{cmd=getch();}while(!isCmd(cmd));
putch(cmd);
return cmd;
}
//-----------------------------命令及界面 函数 定义 结束-----------------------
//-------------主函数-----------------
int main(char * argc[],int argv)
{
SqList sl1,sl2,sl3;
char cmd;
openScreen();
InitList_Sq(sl1);InitList_Sq(sl2);//定义并初始化集合
printf("\n");
do{
printf("\n");
cmd=inCMD();
CMDtran(cmd,sl1,sl2,sl3);
}while(1);
//Goodbye(sl1,sl2,sl3);
return 0;
}
```
## 四、测试数据及结果分析：
### 运行界面：
### 测试数据1：
在命令提示符”h-help,x-exit|cmd>”下输入a显示“请输入集合a的元素（小写字符，不要重复，不用分隔，按enter确定):”，依次输入“abcdefghijklmnopqrst”回车，则集合a建立，以次建立集合b如下：
```
h-help,x-exit|cmd>b
请输入集合b的元素（小写字符，不要重复，不用分隔，按enter确定):
begilrtuvwxyz↓
输入r,可以查看全部结果如下：
h-help,x-exit|cmd>r
集合a为：abcdefghijklmnopqrst
集合b为：begilrtuvwxyz
两集合的并为：abcdefghijklmnopqrstuvwxyz
两集合的交为：begilrt
集合a与集合b的差为：acdfhjkmnopqs
集合b与集合a的差为：uvwxyz
```
运行结果正确
### 测试数据2：
同样如下输入：
```
h-help,x-exit|cmd>a
集合a已存在，是否重建？(y/*)
请输入集合a的元素（小写字符，不要重复，不用分隔，按enter确定):
qwertyuiopasdfg↓
h-help,x-exit|cmd>b
集合b已存在，是否重建？(y/*)
请输入集合b的元素（小写字符，不要重复，不用分隔，按enter确定):
qazwsxedcrfvtgbyhn↓
h-help,x-exit|cmd>r
集合a为：qwertyuiopasdfg
集合b为：qazwsxedcrfvtgbyhn
两集合的并为：qwertyuiopasdfgzxcvbhn
两集合的交为：qawsedrftgy
集合a与集合b的差为：uiop
集合b与集合a的差为：zxcvbhn
```
结果同样正确。
**注:转发请注明出处，以免老师误以为本人从网上抄袭……**
鲁公网安备 37010202001027号