数据结构课程设计-集合运算.doc

i 目 录 第一章 前 言 1 1 1 内容 1 第二章 数据结构设计 2 2 1 数据结构设计 2 第三章 算法设计 5 3 1 算法设计 5 第四章 测试数据及程序运行情况 10 4 1 测试数据及程序运行情况 10 第五章 实验过程中的问题及解决方法 11 5 1 实验过程中出现的问题及解决方法 11 参考文献 12 集合运算 第一章 前言 0 第一章第一章 前前 言言 1 11 1 内容 内容 实验题目 编制一个演示集合的并 交和差运算的程序 需求分析 1 本演示程序中 集合的元素限定为小写字母字符 a z 集合输入的形 式为一个以 回车符 为结束标志的字符串 串中字符顺序不限 2 演示程序以用户和计算机的对话方式执行 即在计算机终端上显示 提示 信息 之后 由用户在键盘上输入演示程序中规定的运算命令 相应的输 入数据和运算结果显示在其后 3 程序执行的命令包括 1 构造集合 1 2 构造在集合 2 3 求并集 4 求交集 5 求差集 6 返 回 7 结束 构造集合 1 和 构造集合 2 时 需以字符的形式键入 集合元素 集合运算 第二章 数据结构设计 1 第二章第二章 数据结构设计数据结构设计 2 12 1 数据结构设计 数据结构设计 为了实现上述程序的功能 应以有序链表表示集合 为此 需要两个抽象数据 类型 有序表和集合 1 有序表的抽象数据类型定义为 readdata pointer head 初始条件 head 是以 head 为头节点的空链表 操作结果 生成以 head 为头节点的非空链表 pop pointer head 初始条件 head 是以 head 为头节点的非空链表 操作结果 将以 head 为头节点的链表中数据逐个输出 集合运算 第二章 数据结构设计 2 2 集合的抽象数据类型定义为 and pointer head1 pointer head2 pointer head3 初始条件 链表 head1 head2 head3 已存在 操作结果 生成一个由 head1 和 head2 的并集构成的集合 head3 or pointer head1 pointer head2 pointer head3 初始条件 链表 head1 head2 head3 已存在 操作结果 生成一个由 head1 和 head2 的交集构成的集合 head3 differ pointer head1 pointer head2 pointer head3 初始条件 链表 head1 head2 head3 已存在 操作结果 生成一个由 head1 和 head2 的差集构成的集合 head3 3 本程序抱含四个模块 1 节点结构单元模块 定义有序表的节点结构 集合运算 第二章 数据结构设计 3 2 有序表单元模块 实现有序表的抽象数据类型 3 集合单元模块 实现集合获得抽象数据类型 4 主程序模块 Void main 初始化 do 接受命令 处理命令 while 命令 退出 集合运算 第三章 算法设计 4 第三章第三章 算法设计算法设计 3 13 1 算法设计 算法设计 include include typedef struct LNode 定义结构体类型指针 char data struct LNode next pointer void readdata pointer head 定义输入集合函数 pointer p char tmp scanf c while tmp n p pointer malloc sizeof struct LNode p data tmp p next head next 集合运算 第三章 算法设计 5 head next p scanf c void pop pointer head 定义输出集合函数 pointer p p head next while p NULL printf c p data p p next printf n 集合运算 第三章 算法设计 6 void and pointer head1 pointer head2 pointer head3 定义集合的并集函数 pointer p1 p2 p3 p1 head1 next while p1 NULL p3 pointer malloc sizeof struct LNode p3 data p1 data p3 next head3 next head3 next p3 p1 p1 next p2 head2 next while p2 NULL p1 head1 next while p1 NULL if p1 NULL p3 pointer malloc sizeof struct LNode p3 data p2 data p3 next head3 next head3 next p3 p2 p2 next void or pointer head1 pointer head2 pointer head3 定义集合的交集函数 pointer p1 p2 p3 p1 head1 next while p1 NULL p2 head2 next while p2 NULL 集合运算 第三章 算法设计 7 if p2 NULL p3 data p1 data p3 next head3 next head3 next p3 p1 p1 next void differ pointer head1 pointer head2 pointer head3 定义集合的差集函数 pointer p1 p2 p3 p1 head1 next while p1 NULL p2 head2 next while p2 NULL if p2 NULL p3 pointer malloc sizeof struct LNode p3 data p1 data p3 next head3 next head3 next p3 p1 p1 next void main 主函数 int x printf 输入数据 按回车键结束 第一个集合大于第二个集合 n pointer head1 head2 head3 head1 pointer malloc sizeof struct LNode head1 next NULL head2 pointer malloc sizeof struct LNode head2 next NULL 集合运算 第三章 算法设计 8 head3 pointer malloc sizeof struct LNode head3 next NULL printf 请输入集合 1 n readdata head1 调用输入集合函数 printf 请输入集合 2 n readdata head2 调用输入集合函数 A printf 1 并集 2 交集 3 差集 4 结束 x 重新运算 n do printf 请选择序号 n scanf d switch x case 1 printf 两集合的并是 n and head1 head2 head3 调用并集函数 pop head3 head3 next NULL break case 2 printf 两集合的交是 n or head1 head2 head3 调用交集函数 pop head3 head3 next NULL break case 3 printf 两集合的差是 n differ head1 head2 head3 调用差集函数 pop head3 head3 next NULL break case 4 break default goto A while x 4 集合运算 第四章 测试数据及程序运行情况 9 第四章第四章 测试数据及程序运行情况测试数据及程序运行情况 4 14 1 测试数据及程序运行情况 测试数据及程序运行情况 运行时提示输入 输入集合 1 asd 输入集合 2 asf 根据提示输入运算类型 1 并集 2 交集 3 差集 4 结束 x 重新运算 输入 1 输出 fasd 输入 2 输出 as 输入 3 输出 d 输入 4 输出 press any key to continue 结束 输入其他数 输出 1 并集 2 交集 3 差集 4 结束 x 重新运算 重新选择运 算类型 下面是运行时的界面 附图 集合运算 第五章 实验过程中的问题及解决方法况 10 第五章第五章 实验过程中的问题及解决方法实验过程中的问题及解决方法 5 15 1 实验过程中出现的问题及解决方法 实验过程中出现的问题及解决方法 1 由于对集合的三种运算的算法推敲不足 在链表类型及其尾指针的设置时 出现错误 导致程序低效 2 刚开始时曾忽略了一些变量参数的标识 使调试程序浪费时间不少 今 后应重视确定参数的变量和赋值属性的区分和标识 3 开始时输入集合后 程序只能进行一次运算 后来加入 switch 语句 成功解 决了这一难题 4 该算法并不能排除重复输入相同字符的情况 也不能自动滤去非法字符 如 空格 阿拉伯数字等 5 本程序的模块划分比较合理 且尽可能的将指针的操作封装在节点和链表 的两个模块中 致使集合模块的调试比较顺利 6 本实习作业采用数据抽象的程序设计方案 将程序化分为四个层次结构 使得设计时思路清晰 实现时调试顺利 各模块具有较好的可用性 确实得到 了一次良好的程序设计训练 集合运算 第五章 参考文献 11 参考文献参考文献 1 李