数据结构实验报告：集合的交叉并.docx

《数据结构》实验报告

题目：集合的并、交、差

专业：信息管理与信息系统 班级：17信管3

组别：一 组长：胡源 完成日期：2018年10月23日

评分依据及结果

态度（A-D）

规范性（A-D）

完成度（A-D）

总评（A-D）

评语

代码分工情况

姓名

胡源

肖晓红

景新月

关延宇

杜彪

工作内容

改进代码

编写原始代码

调试代码

处理bug

运行代码

实验报告分工情况

姓名

胡源

肖晓红

景新月

关延宇

杜彪

工作内容

报告初稿

报告规范化处理

报告细节处理

实验调试和截图

报告整合

需求分析

本演示程序中，集合的元素限定为小写字母和数字，集合的大小小于MAXSIZE=100(可以通过宏定义来动态改变大小)。集合的输入形式为以一个“回车符”为结束标志的字符串，串中字符顺序不限。程序能自动过滤出现的重复字符和非法字符，且经过过滤的集合中，数字始终在字母前面。输出运算结果字符中不含重复字符或非法字符。

演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（除去非法字符）和运算结果显示在其后。

程序的执行命令包括：

1）构造集合1；2）构造集合2；3）求并集；4）求交集；

5）求差集；6）程序结束。

“构造集合1”和“构造集合2”时，需要以字符串的形式链入集合元素。

测试数据

Set1=”abcdefg”，Set1=”123456”（未赋值时的原始集合）Set2∩Set2=”123456abcdefg”,Set2∩Set2=””,

Set2-Set2=”abcdefg”

Set1=”1314524huyuan”，Set1=”748fuck”

Set2∩Set2=cfhknuy”,Set2∩Set2=”4u”,

Set2-Set2=”1235ahny”

Set1=”1314524huyuan数据结构”，Set1=”958abcd考研”

Set2∩Set2=”1234589abcdhnuy”,Set2∩Set2=”5a”,

Set2-Set2=”1234hnuy”

概要设计

用有序链表表示集合来使程序达到预期功能。因此，需要一个抽象数据类型：有序集合。

有序集合的抽象数据类型定义为：

ADTOrderedList{

数据对象：D={a|a为数字（1-9）或字母（a-z）}

数据关系：R={a[i]-1,a[i]|a[i-1],a[i]∈D，a[i-1]a[i],i为自然数}

}

基本操作：

InitList(L)

操作结果：构造空的有序链集合

LocateElem(L,e,p)。

初始条件：L为存在的有序表，e为一个字符

操作结果：如果能找到元素，p带回e元素的下标，结果为true。若找不到元素，用p带回比与元素e最近的一个元素的位置。如果e元素比所有元素都要小，返回指向头结点的指针，结果为false。

InsertAfter(L,q,s)

初始条件：L为存在的有序表，q是指向L中一个结点的指针。

操作结果：让s结点插在q结点后面一个位置。

Append(L,s)

初始条件：L为有序表，s为一个结点的指针

操作结果：把s指向的结点插在L的最后面。

CreateSet(L,*s)

初始条件：L为存在的顺序集和，s指向一个串。

操作结果：生成一个由s串组成的顺序集合

ListTraverse(p)

初始条件：p为一个集合的头结点指针

操作结果：打印出这个集合

Append(L,s)

初始条件：L为顺序表，s为一个结点的指针

操作结果：把s指向的结点插在L的最后面。

Union(L,S1,S2)

初始条件：S1,S2为有序集合

操作结果：L=S1∪S2

Intersection(T,S1,S2)

初始条件：S1,S2为有序集合

操作结果：L=S1∩S2

Difference(T,S1,S2)

初始条件：S1,S2为有序集合

操作结果：L=S1-S2

}

本程序包括3个模块：

主程序模块：

voidmain{

初始化；

do{

接受命令；

处理命令；

}while（“命令”=“退出”）

}

有序集合单元模块——实现有序集合的抽象数据类型

结点结构模块——定义有序表的结点结构

各个模块之间的调用如下：

主程序有限集合单元结点结构单元

主程序

有限集合单元

结点结构单元

详细设计

用字符串a，字符串b表示原始输入的字符串。

两个集合的并运算：把字符串a中各个元素过滤后放在有序集合L1中。将数组b中的元素过滤后放在有序集合L2中。将L1中的元素和L2中的元素进行比较，会出现三种情况：

当L1中的元素比L2中的元素小的时候，把L1中的当前元素放在L3中，