排序系统 数据结构课程设计

课程设计任务书 2011 2012 学年第学年第 1 学期学期 电子与信息工程 系 专业 班级 课程设计名称 数据结构课程设计 设计题目 排序系统 完成期限 自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周 设计依据 要求及主要内容 可另加附页 一 设计目的 熟悉各种数据结构和运算 会使用数据结构的基本操作解决一些实际问题 二 设计要求 1 重视课程设计环节 用严谨 科学和踏实的工作态度对待课程设计的每一项任务 2 按照课程设计的题目要求 独立地完成各项任务 严禁抄袭 凡发现抄袭 抄袭者与被抄袭者 皆以零分计入本课程设计成绩 凡发现实验报告或源程序雷同 涉及的全部人员皆以零分计入本课程设 计成绩 3 学生在接受设计任务后 首先要按设计任务书的要求编写设计进程表 4 认真编写课程设计报告 三 设计内容 设编号为 1 2 3 n 的 n n 0 个人按顺时针方向围坐一圈 每个人持有一个正整数密码 开 始时任选一个正整数做为报数上限 m 从第一个人开始顺时针方向自 1 起顺序报数 报到 m 是停止报数 报 m 的人出列 将他的密码作为新的 m 值 从他的下一个人开始重新从 1 报数 如此下去 直到所有人 全部出列为止 令 n 最大值取 30 要求设计一个程序模拟此过程 求出出列编号序列 初步完成总体设 计 搭好框架 确定人机对话的界面 确定函数个数 四 参考文献 1 王红梅 数据结构 清华大学出版社 2 王红梅 数据结构学习辅导与实验指导 清华大学出版社 3 严蔚敏 吴伟民 数据结构 C 语言版 清华大学出版社 目录目录 一 需求分析 3 二 总体设计 3 三 详细设计 5 四 调试与测试 5 五 关键源程序清单和执行结果 5 六 参考资料 8 一 需求分析 本系统为实现排序功能 输入所要排序的人数 要求人数大于等于 1 小于等于 30 人并为其排号 系 统运用循环链表将输入的 n 个人顺时针排成环 每人手里又一张密码牌 密码拍亦要求大于等于 1 记录 为 m 的值 首先 一圈人顺时针报数 利用指针将 m 指向与其相同的报数号 记录该人的报数号和密码 值并将其作为作为新的 m 值 该人出链 指针指向下一人 重复执行以上操作直至链表为空 记录出链 顺序号 二 总体设计 程序设计组成框图 流程图 见右图 三 详细设计 定义结构体 people 并定义 number key 为整型 struct people 声明结构体类型 people 定义类 link 声明两个成员函数 create 和 show 定义人数 n 与密码 m 值 class link 链表类 此类包含多个 people 类 并控制输入输出 link 定义构造成员函数 函数名与类名相同 m 0 n 0 head NULL 利用构造函数对对象中的数据成员赋初值 void create 声 明环的成员函数 void show 声明运算并输出的成员函数 Create 函数用来建立相应的输入输出功能和建立循环链表 其中 链表的定义借助两个临时指针 p1 p2 p1 new people 利用 for 循环 利于一个 int 型数据存放结点编号 进而实现循环 通过临时 指针的首尾相接 建立循环链表 输出链表数据 考虑到链表为空的情况 添加 if 语句 避免出现编译 错误 person p1 p2 定义 2 个临时指针 p1 new people 新实例化一个人的对象 p1 number i 给这 个人编个号 如果当前链表为空 头结点指向第一个人 否则 p2 永远指向尾结点 新建的结点都接到 p2 之后 p2 next head 把链表连成一个循环链表 就是一个环 Show 函数执行排序功能 设 int 型函数 count 初值为 1 通过循环语句找到第 m 个人 利用三个临 时指针 p1 p2 和 p 将 p1 指向 m 个人 p2 指向他的前一人 p2 next 指向 p1 next 实现第 m 人的出 链 将 p1 指针后移一位 p 指针指向该结点 即第 m 人 删除该结点 此外要将 m 值赋给 p1 key m 值 更新 下一次循环开始 直至链表结点全部出链 用 count 定位到第 m 个人 循环后 p1 指向这个人 p2 指向这个人的上一个人 cout number 输入当 前人的编号 m p1 key 把当前人的密码作为指向下一个人所要经过的人数 p p1p 指向当前这个人 p2 next p1 next 把这个人前面的人和后面的人连接 p1 p1 next 下次从这个人的下一个人开始数 delete p 从链表中删除这个人 主函数调用 create 函数和 show 函数 四 调试与测试 刚开始研究这个题目时 觉得应该用循环链表写 可是对指针这方面 我并不是很擅长 出了很多 错 都是指向的问题 后来经过看书调试 终于把指针这方面的都写对了 五 关键源程序清单和执行结果 include using namespace std struct people 声明结构体类型 people int number number 为编号 int key key 为密码 people next class link 链表类 此类包含多个 people 类 private int n 存放人数 int m 存放初始密码 people head 链表的头结点 public link 定义构造成员函数 函数名与类名相同 m 0 n 0 head NULL void create 声明环的成员函数 void show 声明运算并输出的成员函数 void link create 定义成员函数 create cout n while n30 人数取值范围在 1 到 30 人之间 cout 人数错误 请重新输入 n cout m while m 1 cout m 值输入错误 请重新输入 m people p1 p2 定义 2 个临时指针 for int i 1 inumber i 给这个人编个号 cout 请输入第 i p1 key while p1 key 1 cout 密码输入错误 请重新第 i 个人的密码 p1 key if i 1 如果当前链表为空 头结点指向第一个人 head p1 p2 p1 else 否则 p2 永远指向尾结点 新建的结点都接到 p2 之后 p2 next p1 p2 p1 p2 next head 把链表连成一个循环链表 就是一个环 void link show 定义类 link 中的函数 show people p1 p2 p p1 head cout 编号序列结果 endl 有 n 个人 所以执行 n 次循环 for int i 1 i n i int count 1 用 count 定位到第 m 个人 循环后 p1 指向这个人 p2 指向这个人的上一个人 while count next cout number 输入当前人的编号 cout key 把当前人的密码作为指向下一个人所要经过的人数 p p1 p 指向当前这个人 p2 next p1 next 把这个人前面的人和后面的人连接 p1 p1 next 下次从这个人的下一个人开始数 delete p 从链表中删除这个人 in