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

数据结构
课程设计报告

设计题目：

专 业 计算机科学与技术
班 级 计091
学 生 张楠
学 号 3090911020
指导教师
起止时间 2011.7.4～2011.7.9

22011 年 夏季 学期

目录

1.实验内容
实验题目：编制一个演示集合的并、交运算的程序。
题目： 集合运算
功能： 使用链表来表示集合，完成集合的合并，求交集等操作。
分步实施：
1． 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2． 完成最低要求：
3． 进一步要求：
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4）要提供程序测试方案
1） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

需求分析：
1、  本演示程序中，集合的元素限定为整形数据。集合输入的形式为一个以“0“为结束标志。
2、  演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。
3、  程序执行的命令包括：
1）  构造集合1；2）构造在集合2；3）求并集；4）求交集；5）求差集；6）返回；7）结束。“构造集合1”和“构造集合2”时，需以整形的形式键入集合元素。
二、数据结构设计及流程图
为了实现上述程序的功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。
1、有序表的抽象数据类型定义为：
input(linklist l)
初始条件：l是以l为头节点的空链表。
操作结果：生成以l为头节点的非空链表。
output(linklist l)
初始条件：l是以l为头节点的非空链表。
操作结果：将以l为头节点的链表中数据逐个输出。
2、集合的抽象数据类型定义为：
heji(linklist A,linklist B,linklist C)
初始条件：链表A、B、C已存在
操作结果：生成一个由A和B的并集构成的集合C。
jiaoji(linklist A,linklist B ,linklist ,C)
初始条件：链表A、B、C已存在
操作结果：生成一个由A和B的交集构成的集合C。
3、本程序抱含四个模块：
1）  节点结构单元模块——定义有序表的节点结构；
2）  有序表单元模块——实现有序表的抽象数据类型；
3）  集合单元模块——实现集合获得抽象数据类型；
4）主程序模块：
Void main（）{
初始化；
do{
接受命令；
处理命令；
}while（“命令”!=“退出”）；
}
流程图

三、源程序
# include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
typedef struct node
{
int data;
struct node* next;

}lnode,*linklist;
lnode *init_lnode();
void input(linklist l);
void jiaoji(linklist A,linklist B,linklist C);
void heji(linklist A,linklist B,linklist C);
void output(linklist l);
void main()
{

lnode *a,*b,*c;
a=init_lnode();
b=init_lnode();
c=init_lnode();
printf("求AB集合的交集和并集\n");
printf("请输入A集合的元素:");
input(a);
printf("\n请输入B集合的元素:");
input(b);
printf("\n输入完成\n");
printf("\n按任意键进入主菜单:");
getch();
do
{
char menu[]={"\n\n\n-----☆ 1.交集运算 ☆---------\n\n"
"---------☆ 2和集运算☆---------\n\n"
"---------☆3.差集运算 ☆---------\n\n"
"---------☆ 0. 退出 ☆---------\n\n"
};
printf("%s",menu);
printf("\n请在0-3中选择:");
scanf("%d",&sel);
switch(sel)
{
case 1:
printf("AB集合的交集是:");
jiaoji(A,B,C);
output(C);
C->next=NULL;
break;
case 2:
printf("AB的合集是:");
heji(A,B,C);
output(C);
C->next=NULL;
break;

case 3:
chaji(A,B,C);
break;
case 0:
break;
}

}while(sel!=0);
} /*主函数结束*/

/**********初始化函数***************/
lnode * init_lnode()
{
lnode *l;
l=(lnode *)malloc(sizeof(lnode));
l->next=NULL;
return l;
}
/***************录入函数********************/
void input(linklist l)
{
lnode *s;
int x;
scanf("%d",&x);
while(x!=0)
{
s=(lnode *)malloc(sizeof(lnode));
s->data=x;
s->next=l->next;
l->next=s;
scanf("%d",&x);
}
}
/************交集函数*********************/
void jiaoji(linklist A,linklist B,linklist C)
{
lnode *p,*q,*t;
p=A->next;
while(p!=NULL)
{
q=B->next;
while((q!=NULL)&&(q->data!=p->data))
q=q->next;
if((q!=NULL)&&(q->data==p->data))
{
t=(lnode*)malloc(sizeof(lnode));
t->data=p->data;
t->next=C->next;
C->next=t;
}
p=p->next;
}
}
/***********输出函数*****************/
void output(linklist l)
{
lnode *s;
s=l->next;
while(s!=NULL)
{
printf("%5d",s->data);
s=s->next;
}
printf("\n");

}
/********并集函数*************************/
void heji(linklist A,linklist B,linklist C)
{
lnode *p,*q,*t;
p=A->next;
while(p!=NULL)
{
t=(lnode*)malloc(sizeof(lnode));
t->data=p->data;
t->next=C->next;
C->next=t;
p=p->next;
}
q=B->next;
while(q!=NULL)
{
p=A->next;
while((p!=NULL)&&(p->data!=q->data))
p=p->next;
if (p==NULL)
{
t=(lnode*)malloc(sizeof (lnode));
t->data=q->data;
t->next=C->next;
C->next=t;
}
q=q->next;
}
/*********************差集函数****************/
void chaji(linklist A,linklist B, linklist C)
{
lnode *p,*q,*s,*t;
p=A->next;
printf("A与B的差集是:\n");
while(p!=NULL)
{
q=B->next;
while((q!=NULL)&&(p->data!=q->data))
q=q->next;
if(q==NULL)
{
s=(lnode*)malloc(sizeof(lnode));
s->data=p->data;
s->next=C->next;
C->next=s;
}
p=p->next;
}
output(C);
C->next=NULL;
q=B->next;
printf("B与A的差集是:\n");
while(q!=NULL)
{
p=A->next;
while((p!=NULL)&&(p->data!=q->data))
p=p->next;
if(p==NULL)
{
t=(lnode*)malloc(sizeof(lnode));
t->data=q->data;
t->next=C->next;
C->next=t;
}
q=q->next;
}
output(C);
}

}四、测试数据及程序运行情况
下面是运行时的界面(附图):

五、心得体会
1、由于对集合的三种运算的算法推敲不足，在链表类型及其尾指针的设置时出现错误，导致程序低效。
2、刚开始时曾忽略了一些变量参数的标识”&”，使调试程序浪费时间不少。今后应重视确定参数的变量和赋值属性的区分和标识。
3、开始时输入集合后，程序只能进行一次运算，后来加入switch语句,成功解决了这一难题。
4、该算法并不能排除重复输入相同字符的情况，也不能自动滤去非法字符(如空格、阿拉伯数字等)。
5、本程序的模块划分比较合理，且尽可能的将指针的操作封装在节点和链表的两个模块中，致使集合模块的调试比较顺利。
6、本实习作业采用数据抽象的程序设计方案，将程序化分为四个层次结构，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可用性，确实得到了一次良好的程序设计训练。

评语（教师填写）