西安建筑科技大学：《数据结构与算法》教学资源（课程设计）课程设计任务指导书

计算机科学与技术专业 数据结构课程设计 任务指导书

计算机科学与技术专业 数据结构课程设计 任务指导书

20052.10 第一部分:数据结构课程设讣说明 数据结构课程是计算机科学与技术专业的一门专业技术基础 课。该课程是计算机科学的算法理论基础和软件设计的技术基础, 主要硏究信息的逻辑结构及其基本操作在计算机中的表示和实现。 通过该课程的学习学生应该能够深刻理解各种常用的数据结 构,以及各种数据结构之间的逻辑关系;同时应该熟练掌握各种数 据结构在计算机中的存储表示和在这些数据结构上的运算与实际 的算法,并对于算法的效率能够进行简要的分析。在学习过程中, 还要求学生能够掌握复杂程序设计的方法,养成良好的编程习惯。 由课程的性质决定该门课程必须以实际上机作为基础根据实 际情况,上机实践应该从总体上分成两大部分 第-部分:结合各章的教学内容实现各种算法。这-部分属于 基础,一般分成六大部分。分别是:一般线性表(数组、链表两种 结构),受限线性表(栈与队列)及递归,树与广义表,图,查找, 排序。该部分以各章作业的形式已经布置给大家,并要求大家以上 机报告的书面形式交出作业

2005.2.10 第一部分：数据结构课程设计说明 数据结构课程是计算机科学与技术专业的一门专业技术基础 课。该课程是计算机科学的算法理论基础和软件设计的技术基础， 主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。 通过该课程的学习，学生应该能够深刻理解各种常用的数据结 构，以及各种数据结构之间的逻辑关系；同时应该熟练掌握各种数 据结构在计算机中的存储表示和在这些数据结构上的运算与实际 的算法，并对于算法的效率能够进行简要的分析。在学习过程中， 还要求学生能够掌握复杂程序设计的方法，养成良好的编程习惯。 由课程的性质决定该门课程必须以实际上机作为基础，根据实 际情况，上机实践应该从总体上分成两大部分： 第一部分：结合各章的教学内容实现各种算法。这一部分属于 基础，一般分成六大部分。分别是：一般线性表（数组、链表两种 结构），受限线性表（栈与队列）及递归，树与广义表，图，查找， 排序。该部分以各章作业的形式已经布置给大家，并要求大家以上 机报告的书面形式交出作业

第二部分:综合实践部分。本部分一般应结合具体应用场合, 由大家选择相应的存储结构实现题目的要求。这一部分就是我们数 据结构课程设计所要完成的任务 第二部分:数据结构课程设计的总体要求与 评分方法 总体要求: 学生结合自己的实际情况,可以选择以小组协作的形式(最多 三人)或者自己独立完成的形式进行课程设计。课程设计的题目可 以选择自己感兴趣的问题,也可以选择附录部分给定的题目。 对于每一个设计题目,如果是小组协作,设计小组3人(或 者2人)共同商量:该设计题目应采用的数据结构与算法要点和 细节,进行角色分工,协力完成设计题目。 1.编程人员:负责编制程序,注意在代码中加上注释,使用缩 进法等,尽量提高程序的可读性 2测试分析人员:要根据所讨论结果提供测试数据,要求每种 情况各个出口都要测试到,测试中发现问题和编程人员商量,修改 算法。测试通过后,分析一下效率(时间、空间复杂度);

第二部分：综合实践部分。本部分一般应结合具体应用场合， 由大家选择相应的存储结构实现题目的要求。这一部分就是我们数 据结构课程设计所要完成的任务。 第二部分：数据结构课程设计的总体要求与 评分方法 总体要求： 学生结合自己的实际情况，可以选择以小组协作的形式（最多 三人）或者自己独立完成的形式进行课程设计。课程设计的题目可 以选择自己感兴趣的问题，也可以选择附录部分给定的题目。 对于每一个设计题目，如果是小组协作，设计小组 3 人（或 者 2 人）共同商量：该设计题目应采用的数据结构与算法要点和 细节，进行角色分工，协力完成设计题目。 ⒈编程人员：负责编制程序，注意在代码中加上注释，使用缩 进法等，尽量提高程序的可读性； ⒉测试分析人员：要根据所讨论结果提供测试数据，要求每种 情况各个出口都要测试到，测试中发现问题和编程人员商量，修改 算法。测试通过后，分析一下效率（时间、空间复杂度）；

3.文栏编制人员要详细写出 ①题目 ②数据结构 算法思路 ④测试结果 ⑤人员分工情况; 整个文档要求按照软件工程的规范撰写可以在文栏对应部分包含 上述内容,如分析设计部分可以给出算法思路以及相应图表,测试 部分给出测试用例与测试结果(测试报告由测试人员编写),源代 码部分注意各种注释的使用 4对于独立完成项目的同学,应该在文档中写清楚是自己独立 完成的。由于大型软件的开发都是由开发项目组完成的,所以在数 据结构课程设计中我们尽量鼓励大家以设计小组的形式参加 设计评分方法: 对于每个设计题目,满分将是50分。本次设计每位同学至少 要完成两套设计题目。 对于小组合作的同学来说,3人一组,分工负责。每个设计题

⒊文档编制人员要详细写出: ① 题目； ② 数据结构； ③ 算法思路； ④ 测试结果； ⑤ 人员分工情况； 整个文档要求按照软件工程的规范撰写，可以在文档对应部分包含 上述内容，如分析设计部分可以给出算法思路以及相应图表，测试 部分给出测试用例与测试结果（测试报告由测试人员编写），源代 码部分注意各种注释的使用。 4.对于独立完成项目的同学，应该在文档中写清楚是自己独立 完成的。由于大型软件的开发都是由开发项目组完成的，所以在数 据结构课程设计中我们尽量鼓励大家以设计小组的形式参加。 设计评分方法： 对于每个设计题目，满分将是 50 分。本次设计每位同学至少 要完成两套设计题目。 对于小组合作的同学来说，3 人一组，分工负责。每个设计题

目中,编程满分25分、测试分析满分10分、文档满分15分。 由于三人小组一共应当完成六个设计题目所以一共最多可以获得 (25+10+15)*6=300分,人均100分。在分工中,每位同学都应 该自己独立完成两次编程,两次测试分析,两次文档。也就是说各 次分工应当不同,不能一个同学负责全部的文档,一个同学负责全 部的测试分析,一个同学负责所有的编程工作。每位同学自己完成 两大套设计题目 对于每个设计题目的每一部分,视完成情况得到相应的分数, 缺少或抄袭都得0分。抄袭者不给成绩。 设计结束后,务必上交以下材料: 每一个设计题目包括两部分: 第一部分:分析设计报告与测试报告,两份报告装订在一起, 以纸介质形式提交。分析设计报告在前,测试报告在后(测试报告 另起一页)报告一律用A4纸,正文用宋体5号字。报告封面见 附页。 第二部分:源程序、分析设计报告与测试报告。三者以电子版 形式提交,软盘上请写清自己的班级和姓名。教师收到电子版文档 后两周内会将所有文档拷出,软盘归还学生,并确认所交文档已经 接收

目中，编程满分 25 分、测试分析满分 10 分、文档满分 15 分。 由于三人小组一共应当完成六个设计题目，所以一共最多可以获得 (25+10+15)*6=300 分，人均 100 分。在分工中，每位同学都应 该自己独立完成两次编程，两次测试分析，两次文档。也就是说各 次分工应当不同，不能一个同学负责全部的文档，一个同学负责全 部的测试分析，一个同学负责所有的编程工作。每位同学自己完成 两大套设计题目。 对于每个设计题目的每一部分，视完成情况得到相应的分数， 缺少或抄袭都得 0 分。抄袭者不给成绩。 设计结束后，务必上交以下材料： 每一个设计题目包括两部分： 第一部分：分析设计报告与测试报告，两份报告装订在一起， 以纸介质形式提交。分析设计报告在前，测试报告在后（测试报告 另起一页）。报告一律用 A4 纸，正文用宋体 5 号字。报告封面见 附页。 第二部分：源程序、分析设计报告与测试报告。三者以电子版 形式提交，软盘上请写清自己的班级和姓名。教师收到电子版文档 后两周内会将所有文档拷出，软盘归还学生，并确认所交文档已经 接收

参考教材: Robert L. Kruse, Alexander J Ryba, Data Structures And Program Design in C++,高等教育出版社,2001.5。 第三部分:数据结构课程设计的参考题目 一、用循环链表实现约瑟夫( Joseph)环 1.问题描述:编号为1,2,…,n的η个人按顺时针方向围 坐一圈,每人持有一个密码(正整数)开始任选一个正整数作为报 数值m,自第—个人开始按顺时针方向自1开始顺序报数,报到 m时停止报数,报m的人出列,将他持有的密码作为新的m值, 从他的顺时针方向上的下一个人开始重新从1报数,如此下去, 直至所有的人全部出列为止。编写完整的程序求出出列顺序。 2具体要求 ()输入:从键盘输入人数n,n个人的密码,及初始m值。 输入应有提示,输入数据错误应当有出错提示,然后退出。当

参考教材： Robert L. Kruse，Alexander J. Ryba，Data Structures And Program Design in C++，高等教育出版社，2001.5。 第三部分：数据结构课程设计的参考题目 一、用循环链表实现约瑟夫（Joseph）环。 ⒈问题描述：编号为 1，2，…，n 的 n 个人按顺时针方向围 坐一圈，每人持有一个密码（正整数）开始任选一个正整数作为报 数值 m，自第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数，报 m 的人出列，将他持有的密码作为新的 m 值， 从他的顺时针方向上的下一个人开始重新从 1 报数，如此下去， 直至所有的人全部出列为止。编写完整的程序求出出列顺序。 ⒉具体要求： ⑴ 输入：从键盘输入人数 n，n 个人的密码，及初始 m 值。 输入应有提示，输入数据错误应当有出错提示，然后退出。当

输入n值过大,而输入的n个整数不够时应有处理措施,将其补 够n个整数 (2)输出:输出最好是写到文件中,将原输入的值n,n个整 数,初始m值均写入到文件中,出列顺序也写入到文件中,这样 文栏编制人员将其插入即可。(调试阶段可以先输出到屏幕,以便 及时看到结果 二、马踏棋盘 1.问题描述:设计一个国际象棋的马踏棋盘的演示程序。 2具体要求 ()将马随机放在国际象棋的8×8棋盘的某个方格中,马按走 棋规则进行移动。要求毎个方格只进入一次,走遍棋盘上全部64 个方格。编制非递归程序,求出马的行走路线,并按求出的行走路 线,将数字1,2,…,64依次填入一个8×8的方阵并输出。 (2)测试数据由键盘指定出马的起始位置(),0≤j≤7。 (3)本题目选作内容:求出从某一点出发的多条以至全部行走 路线 (4)提示

输入 n 值过大，而输入的 n 个整数不够时应有处理措施，将其补 够 n 个整数。 ⑵ 输出：输出最好是写到文件中，将原输入的值 n，n 个整 数，初始 m 值均写入到文件中，出列顺序也写入到文件中，这样 文档编制人员将其插入即可。（调试阶段可以先输出到屏幕，以便 及时看到结果）。 二、马踏棋盘 ⒈问题描述：设计一个国际象棋的马踏棋盘的演示程序。 ⒉具体要求： ⑴ 将马随机放在国际象棋的 8×8 棋盘的某个方格中，马按走 棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路 线，将数字 1，2，…，64 依次填入一个 8×8 的方阵并输出。 ⑵ 测试数据由键盘指定出马的起始位置(i,j)，0≤i,j≤7。 ⑶ 本题目选作内容：求出从某一点出发的多条以至全部行走 路线。 (4)提示：

①一般来说,当马位于方格()时,可以走到下列8个位置 之一:(-2j+1),(i-1j+2),(+1j+2),(i+2j+1),(i+2)-1), (i+1-2),(i-1j-2),(i-2j-1)。但是,如果(j)靠近棋盘的边缘, 上述有些位置可能超出棋盘范围,成为不允许的位置。 ②每次在多个可走位置中选择其中一个进行试探其余未曾试 探过的可走位置必须用适当结构妥善管理以备试探失败时“回溯 (悔棋)使用。 三平衡二叉树操作的演示 1.问题描述:利用平衡二叉树实现一个动态查找表 2具体要求 ()实现动态查找表的三种基本功能:查找、插入和删除。 (2)测试数据自行设定 (3)提示 ①初始状态下,平衡二叉树为空树,操作界面给出查找、插 入和删除三种操作供选择。每种操作均要提示输入关键字。毎次插 入或删除一个节点后,应更新平衡二叉树的显示 平衡二叉树的显示可以采用凹入表形式,也可以采用图形

① 一般来说，当马位于方格(i,j)时，可以走到下列 8 个位置 之一：(i-2,j+1)，(i-1,j+2)，(i+1,j+2)，(i+2,j+1)，(i+2,j-1)， (i+1,j-2)，(i-1,j-2)，(i-2,j-1)。但是，如果(i,j)靠近棋盘的边缘， 上述有些位置可能超出棋盘范围，成为不允许的位置。 ②每次在多个可走位置中选择其中一个进行试探，其余未曾试 探过的可走位置必须用适当结构妥善管理，以备试探失败时“回溯” （悔棋）使用。 三 平衡二叉树操作的演示 ⒈问题描述：利用平衡二叉树实现一个动态查找表。 ⒉具体要求： ⑴ 实现动态查找表的三种基本功能：查找、插入和删除。 ⑵ 测试数据自行设定。 ⑶ 提示： ① 初始状态下，平衡二叉树为空树，操作界面给出查找、插 入和删除三种操作供选择。每种操作均要提示输入关键字。每次插 入或删除一个节点后，应更新平衡二叉树的显示。 ② 平衡二叉树的显示可以采用凹入表形式，也可以采用图形

界面画出树形。 四实现用 Diskstra方法求最短路径的算法 1.问题描述:从用户指定的顶点为起点,输出该结点到其余各 顶点的最短路径长度及其路径(path 2具体要求: ①结点数不应少于30 ②可以从键盘或从文件输入结点数据:顶点信息、边、权 建议从文件输入,这样可以预先建立输入文件,调试时不用每次都 从键盘输入。 五内部排序算法比较(删去) 1问题描述:各种内部排序算法的时间复杂度分析结果只给 出了算法执行时间的阶(大概执行时间),本题目要求通过随机函 数产生3组每组不少于300个范围为(1~32767)的整数数据 然后调用各种内部排序方法进行排序。分析在不同的输入顺序下各 种排序方法对这组值的执行效率。(调用前、后分别插入时间变量

界面画出树形。 四 实现用 Diskstra 方法求最短路径的算法。 ⒈问题描述：从用户指定的顶点为起点，输出该结点到其余各 顶点的最短路径长度及其路径（path）。 ⒉具体要求： ① 结点数不应少于 30。 ② 可以从键盘或从文件输入结点数据：顶点信息、边、权； 建议从文件输入，这样可以预先建立输入文件，调试时不用每次都 从键盘输入。 五 内部排序算法比较(删去) ⒈问题描述：各种内部排序算法的时间复杂度分析结果只给 出了算法执行时间的阶（大概执行时间），本题目要求通过随机函 数产生 3 组，每组不少于 300 个范围为（1～32767）的整数数据， 然后调用各种内部排序方法进行排序。分析在不同的输入顺序下各 种排序方法对这组值的执行效率。（调用前、后分别插入时间变量

求得各种排序方法对该组值的精确的执行时间。) 2.具体要求 ()对直接插入排序,冒泡排序,简单选择排序,快速排序, 堆排序,归并排序,基数排序迸行比较。 (2)分析人员要对结果作出简单分析,要求产生3组数目(排 序文件长度)不同,以比较长度大小对不同的排序方法的影响,包 括对各组数据得出结果波动大小的解释。 六散列(哈希)表设计 1.问题描述:为你所在班级的学生名设计一个哈希表(学生名 单可从教学办公室处复制)完成插入记录建表和根据给定Key值, 查找记录的查表程序。 2具体要求 (1)完成中文人名转换为整数/英文字符串(作为哈希函数的 Key值)的子函数 (2)自选哈希函数与处理冲突的方法。 (3)调用建表算法完成本班学生名的插入前/后插入时间变量, 得到花费时间

求得各种排序方法对该组值的精确的执行时间。） ⒉具体要求： ⑴ 对直接插入排序，冒泡排序，简单选择排序，快速排序， 堆排序，归并排序，基数排序进行比较。 ⑵ 分析人员要对结果作出简单分析，要求产生 3 组数目（排 序文件长度）不同，以比较长度大小对不同的排序方法的影响，包 括对各组数据得出结果波动大小的解释。 六 散列（哈希）表设计 ⒈问题描述：为你所在班级的学生名设计一个哈希表（学生名 单可从教学办公室处复制），完成插入记录建表和根据给定Key值， 查找记录的查表程序。 ⒉具体要求： ⑴ 完成中文人名转换为整数/英文字符串（作为哈希函数的 Key 值）的子函数。 ⑵ 自选哈希函数与处理冲突的方法。 ⑶ 调用建表算法完成本班学生名的插入前/后插入时间变量， 得到花费时间