10计科《数据结构》课程设计指导书

1、景德镇陶瓷学院科技艺术学院数据结构课程设计指导书指导老师： 何福保、胡开华2011 年 12 月目录第一节、序言 2第二节、课程设计要求 3第三节、课程设计论文的格式 4第四节、考勤及考核 5第五节、课题及任务（题目及要求） 6题目 1 运动会分数统计 * 6题目 2 一元多项式计算 * 7题目 3 迷宫求解 7题目 4 文章编辑 7题目 5joseph 环* 8题目 6 建立二叉树，层序、先序遍历（用非递归的方法） * 8题目 7 扑克牌游戏 9题目 8 商品货架管理 9题目 9 行文本编辑器 9题目 10 作业调度 11题目 11图（校园导游图） * 12题目 12 教学计划编编制问题 1

2、3题目 13 航空客运订票系统 * 13第一节、序言数据结构课程设计是为配合课堂教学，使学生进一步掌握数据结构课 程中有关理论知识，并通过对具体事物的分析，得出抽象的结构 （关系），建立 数据模型（公式），并最终设计出良好的算法（流程图） 。本次课程设计统一要 求用C或者C+言编程并调试（程序设计），以提高学生的程序设计及解决实 际问题的能力；并为后续课程学习打下基础。本次课程设计所列问题， 大都与现实生活密切相关， 并且其包含了 数据结构 课程中所讲述的基本类型，具有典型意义。要求学生利用数据结构 课程有关理论， 参考本手册所介绍的软件工程 的的相关方法，对不同问题分别进行需求分析，概要设计

3、，然后进行详细设计 和代码的编写， 并进行测试得出相应软件， 最后编写软件说明及课程设计论文。因为只有二周共十天的时间， 为使学生能尽快抓住问题的本质， 每个题目 不但给出了问题描述，要求，还给出实现提示，以便学生能尽快完成课程设计 任务。第二节、课程设计要求学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。 有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并 在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要两周时间完成，两周中每天（按每周 5 天）至 少要上3-4小时的机来调试C/C+语言设

4、计的程序，总共至少要上机调试程序 30小时。数据结构是一门涉及多门课程的课程，难度较大，需要较好的C/C+语言的程序设计和调试能力，如果学生能够按照要求，从时间和精力上保证完全的 投入，相信能够有很大的收获。第三节、课程设计论文的格式1、对每个题目要有需求分析在需求分析中，将题目中要求的功能进行叙述分析，并且设计解决此问题 的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计） ，设计 或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键 语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进 行测试的结果列出来。对有些题目提出算法改进方案

5、， 比较不同算法的优缺点。 如果程序不能正 常运行，写出实现此算法中遇到的问题，和改进方法；2、对每个题目要有相应的源程序（可以是一组源程序，即详细设计部分）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量， 重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循 环。3、最后提供的主程序可以象一个应用系统一样有主窗口， 通过主菜单和分级菜 单调用课程设计中要求完成的各个功能模块，调用后可以返回到主菜单，继续 选择其他功能进行其他功能的选择。4、对每个模块的层次结构用具体的语言来实现（C/C+语言）。5、编写软件使用说明手册。6、课程设

6、计的上交作业包括：课程设计论文 +源程序+可执行程序 +运行说明文第四节、考勤及考核全体同学在课程设计期间，必须在上课时间到专业机房进行考勤，一天四 次（早上 8：00 及 11：30，下午 2：00 及 3：50）。每位同学必须的课题完成之后，必须通过指导老师的考核，基本完成课题 要求的起点为合格，另根据具体完成模块情况进行考核评分。数据结构课程设计的最后成绩有以下几个方面组成： 程序运行情况（ 20 分）， 程序的结构合理与否（ 10 分）， 算法说明的清晰程度（ 10 分），总结的深刻程度（ 10 分）， 课设过程中的课设进展情况 （应该至少有四次）（20 分）， 独立完成情况（学生间不

7、相互雷同） （20 分）， 以及加分因素（ 10 分）；共 100 分附注：1 在学生实习中，学生若有 5 次考勤不到，综合评定成绩不得超过中以上 成绩；2 在学生实习中，学生若有 7 次考勤不到，综合评定成绩不得超过及格及 以上成绩；3 在学生实习中，学生若有 9 次考勤不到，综合评定成绩为不及格。 在学生实习中，发现学生有抄袭现象，综合评定成绩为不及格。第五节、课题及任务（题目及要求）本次课程设计完成如下模块 （共 13个模块，两个带有* 号的模块必做， 在四个 带*号的模块中必须选做一个，多做可以加分）题目 1 运动会分数统计 *1、问题描述参加运动会有n个学校，学校编号为1n。比赛分成

8、m个男子项目，和 w个女子项目。项目编号为男子 1 m，女子m+1 m+w。不同的项目取 前五名或前三名积分；取前五名的积分分别为： 7、5、3、2、1，前三名的积分 分别为： 5、3、2；哪些取前五名或前三名由学生自己设定。 （m<=20,n<=20） 2、 要求 功能要求：（1）可以输入各个项目的前三名或前五名的成绩；（2）能统计各学校总分；（3）可以按学校编号、学校总分、男女团体总分排序输出；（4）可以按学校编号查询学校某个项目的情况；（5）可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围： 20以内的整数（如果做得更好可以输入学校的名 称，运动项目的名称）

9、输出形式：有中文提示，各学校分数为整数 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关 的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据 要存储在数据文件中。（数据文件的数据读写方法等相关内容在 c 语言程序设计 的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用 1 、全部合法数据； 2、整体非法数据； 3、局部非法数据。 进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写 明；题目 2 一元多项式计算 *1、问题描述1）、能够按照指数降序排列建立并输出多项式； 2）、能够完成两个多项式的

10、相加、相减，并将结果输入。2、要求 在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使 用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出 算法的改进方法。题目 3 迷宫求解1、问题描述 可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的 路径，并将路径输出。2、要求 在上交资料中请写明：存储结构、基本算法（可以使用程序流程图） 、源程 序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。题目 4 文章编辑1、问题描述 输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过 80个字符，共 N 行2、要

11、求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符 号。输出形式：（1）分行输出用户输入的各行字符；（2）分 4行输出"全部字母数 "、"数字个数"、"空格个数"、"文章总字数 "（3）输出删除某一字符串后的文章题目5joseph环*1、问题描述编号是1, 2,n的n个人按照顺时针方向围坐一圈，

12、每个人只有一个 密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密 码作为新的 m 值，从他在顺时针方向的下一个人开始重新从 1 报数，如此下去， 直到所有人全部出列为止。设计一个程序来求出出列顺序。2、要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7,7个人的密码依次为3，1, 7, 2, 4, 7, 4,首先m=6, 则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入 m的初值，n,输入每个人的密码， 建立单循环链表。输出形

13、式：建立一个输出函数,将正确的输出序列题目 6 建立二叉树,层序、先序遍历（用非递归的方法） *1、问题描述 要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先 序遍历序列的函数；2、要求在上交资料中请写明：存储结构、基本算法（可以使用程序流程图） 、源程 序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。题目 7 扑克牌游戏1、问题描述编号为 1-52张牌，正面向上，从第 2 张开始，以 2为基数，是 2的倍数的 牌翻一次，直到最后一张牌；然后，从第 3张开始，以 3 为基数，是 3的倍数 的牌

14、翻一次，直到最后一张牌；然后从第 4张开始，以4为基数，是4的倍 数的牌翻一次，直到最后一张牌； .再依次 5的倍数的牌翻一次， 6的， 7 的直 到以 52 为基数的翻过，输出：这时正面向上的牌有哪些？2、要求在上交资料中请写明：存储结构、基本算法（可以使用程序流程图） 、源程 序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。题目 8 商品货架管理1、问题描述 一超市货架以栈的方式摆放商品，生产日期越靠近栈底；出货时从栈顶取 货，一天营业结束，如果货架不满， 则需上货。 如果直接将商品摆放到货架上， 则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，仍使生产日期越 近的

15、越靠近栈底。假设该超市由专人根据电脑销售数据随时进行上货，某种商品每件次“取货”平均时间为TX1，每件次“上货”平均时间为TX2，该商品每天销售件数 为NX （每天销售总件数据为N，K为商品种类数，N=N1+NK）,该员工该 商品上货工作时间为 TX （每天工作总时间为 T， T=T1+TK），2、要求 设计一个算法，每一次上货后始终保持生产日期越近的商品越靠近栈底。求货架上剩余货物M、每天销售件数N、员工每天上货工作时间T,三者之间 有何关系及 T 的最小值。题目 9 行文本编辑器1、问题描述行文本编辑器（ EDLIN ）通过终端对文本文件进行创建、删除、修改、存储操作。2、要求（1）编辑新

16、文件，运行 EDLIN 进入编辑状态， 是新文件则提示“ NewFile”， 并给出编辑提示符“ * ”号。CEDLINfilename*I RETURN（输入I命令进入插入状态）1：*a=12：*b=23：*c=a+b4：*?c5：* Ctrl + Break*ERETURN（存盘退出）（ 2）修改旧文件，运行 EDLIN 进入编辑状态，是旧文件则提示Endofainputfile”说明文件已从盘上调出，可以进行修改；并给出编辑提示*3< RETURN（输入行号进行修改）3：*c=a+b3：*c=a*b（ 输入修改内容 ）*QRETURN（不存盘退出）3）显示文件内容*L1：RETUR

17、N*a=12：*b=23：*c=a+b4：*?c插入行：*nD RETURN（从n行之前开始插入内容，以Ctrl+ Break结束） 删除行*nD RETURN（将第n行内容删除）*n，mD RETURN（将第n行到第m行的所有内容删除）3、实现提示：采用一种堆结构存储待编辑字符，具体做法在下面介绍。（1）在内存开辟可容纳 maxlines 行大小的编辑工作区的 bufsize 的修改缓 冲区。（2）系统启动时，要求用户输入编辑文件名，如果该文件存在，则调入 maxlines 行到文本编辑工作区；如果该文件不存在，则认为是新建文件。（3）对读入的文件建立相应的行表。行表指出每一行的行号和该行子

18、串的 长度，它们按照行号排序。在文本编辑程序中设立行指针、字符指针，分别批 示当前操作的行、字符。（4）执行插入、删除、修改操作时，将本次操作内容放到缓冲区。题目 10 作业调度1、问题描述 一个公司的职员可分为经理、部门主管和职工。公司的服务支持由一个共 同的秘书处承担，每一个职员都可以提出服务请求（诸如企划及建议、指示及 批复等），只要填写一张包括该职员的职位、任务号、 任务内容的表格即可。这 张表格内的信息存储在一个作业请求记录JobReques队列中，并根据时间将作业加入到对应的优先级队列中。初始作业队列存放于一个作业队列文件中，作业队列文件中存放有一批将被加入到优先级队列的作业。每个

19、作业请求都以记录的形式存放在“job.dat”文件中。记录中记载着职员的职位、作业标识号和工作时间。所有作业在读入 后都加入到一个名为“ jobpool-作业池”的优级队列中，然后，按其所具有的优 先级逐个进行处理，并将处理结果打印出来。程序最后打印为每一类人的总服 务时间。2、要求（1）编写为输入打开文件“ job.dat”，读入作业文件，为staffPerson域、作 业标识域、任务内容等域赋值。（2）利用优先级队列对所有作业调度，计录作业流转各处理环节所需的处 理的时间，并打印作业信息。最后打印为每一作业服务的总时间。（3）将调度策略改为“先来先服务” ，利用先进先出的队列重新实现作业调

20、度3、实现提示（1）为表明每一员工因职位不同具有不同的优先级，将其按职位建在一个枚举型变量中。经理优先级最高（为 0）;部门主管优先级次之（为1），等等:（2） 程序中需要使用一个辅助数组jobServicesUse用来存放为每一类职 员提供服务的时间。（3） 程序中还需要用到两个打印函数，一个是PrintJobInfo （），它打印出 每一个作业的信息；另一个是 PrintSummary（），打印公司为各类职员提供服 务的总时间。JobReques记录及相关的函数都在头文件“ job.h”中。（4）为输入打开文件“ job.dat”，读入作业文件时，需判断出错情况。再根 据不同类的人，分别为

21、为staffPers on域、作业标识域、作业所需时间域赋值。（5）执行一个循环，当优先级队列不空时，作业逐个退批优先级队列，打印作业信息，进行服务时间累计。待作业全部退出后，打印公司为各类职员提供服务的总时间。题目11图（校园导游图）*1、问题描述制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线3,使游客可以不重复地游览各景点, 最后回到出口（出口就在入口处旁边）2、要求（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各 景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。3、实现提示（1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景 点较少的路径提供给游客。（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路 径最小的路线提供给游客。题目 12 教学计划编编制问题1、 问题描述、在学的每个专业都要制定教学计划。 假设任何专业都有固定的学习班年限， 每学期含两个学期，每学期的时间长度和学分上限值均相等。每个专业开设的 课