数据结构课程设计任务书

《数据结构课程设计任务书》由会员分享，可在线阅读，更多相关《数据结构课程设计任务书（10页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程设计任务书（本科）辽宁工程技术大学软件学院软件工程系一、课程设计目的和任务数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设 计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的 一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类 C 语言的算 法转换成 C 程序并上机调试的基本方法。课程设计要求学生在完成程序设计的 同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本 程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。二、课程设计基本要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选

2、 择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序 设计方法以及上机操作等基本技能方面受到比较系统的训练。2、学生必须按照课程设计要求，以学生为主、指导教师指导为辅，认真、 独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在一周时间内独立完成，学生要发挥自 主学习的能力，充分利用时间，按时完成设计内容。三、课程设计内容（注：题目号与学生学号尾数对应）1、题目：Joseph环设计任务：编号是1, 2,小的口个人按照顺时针方向围坐一圈，每个人只有一个 密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时 针方向自1开

3、始顺序报数，报到m时停止报数。报m的人出列，将他的密码作 为新的 m 值,从他在顺时针方向的下一个人开始重新从 1 报数,如此下去,直 到所有人全部出列为止。设计一个程序来求出出列顺序。设计要求：设计一个程序，以人机交互的方式执行，用户指定约瑟夫环游戏的总人数n 和初始的报数上限m ,然后输入每个人所持有的密码key。模拟约瑟夫环，从头 开始报数,直到所有人出列。系统按照出列顺序给出编号及该人所持有的密码。实现提示：(1) 利用带头结点的循环链表作为模拟约瑟夫环的存储结构。(2) 先创建一个有头结点的单循环链表，依次输入 n 个人的密码。然后从第一 个结点出发，连续略过 m-1 个结点，将第

4、m 个结点删除，并将第 m 个人的 密码作为新的 m 值，接着从下一个结点出发，重复以上过程，直到链表为空 为止。2、题目：教学计划编制问题设计任务：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每 学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都 是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修 课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这 样的前提下设计一个教学计划编制程序。设计要求：(1) 输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占 3 位的字母数字串)、学分和直接先修课的课程号

5、。(2) 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担 尽量均匀；二是使课程尽量可能地集中在前几个学期中。(3) 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到 屏幕。计划的表格格式自行设定。实现提示：(1) 数据结构使用有向图和栈。(2) 果程先修关系参照教材P181页图7.26(3) 如果输入的先修课程号不在该专业开设的课程序列内，则作为错误处理。3、题目：运动会分数统计设计任务：参加运动会有n个学校，学校编号为1no比赛分成m个男子项目，和w 个女子项目。项目编号为男子1一山，女子m+1 _m+w。不同的项目取前五名或 前三名积分；取前五名的积分分别

6、为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些项目取前五名或前三名由学生自己设定。(mv=20,nv=20) 设计要求：(1) 产生各院系的成绩单，内容包括各院系取得的每项成绩的项目号、名次(成 绩)、姓名和得分；(2) 产生团体总分报表，内容包括院系编号、男子团体总分、女子团体总分和 团体总分。实现提示： 可以假设姓名长度不超过20个字符。每个项目结束时，将其编号、类型符(区分取前五名还是取前三名)输入，并按名次顺序输入运动员姓名、院系编号 和成绩。4、题目：算术表达式求值演示程序 设计任务：设计一个程序，演示用算符优先法对算术表达式求值的过程。 设计要求：(1) 以字符序列的

7、形式从终端输入语法正确的、不含变量的整数表达式。(2) 利用教材P53页表3.1给出的算符优先关系，实现对算术四则混合运算表 达式的求值；(3) 仿照教材例 3-1 演示在求值过程中运算符栈、运算数栈、输入字符和主要 操作的变化过程。实现提示：(1) 设置运算符栈和运算数栈辅助分析算符优先关系；(2) 在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及 相应的运算；(3) 在识别出运算数的同时，要将其字符序列形式转换成整数形式；(4) 在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。5、题目：停车场管理 设计任务：设停车场是一个可停放n辆汽车的狭长通道，且只有一

8、个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端， 最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来 的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可 开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让 路，待该辆车开出大门外，其他车辆再按原次序进入停车场，每辆停放在车场的 车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述 要求进行管理的模拟程序。设计要求： 以栈模拟停车场，以队列模拟停车场外的便道，按照从终端读入的输入数据 序列进行模拟管理。（1）每一组输入数据

9、包括三个数据项：汽车“到达”或者“离开”信息、汽 车牌照号码以及汽车到达或离开的时刻。（2）对每一组输入数据进行操作后的输出信息为：a、若是车辆到达，则输出汽车在停车场内或便道上的停车位置；b、若是车辆离开，则输出汽车在停车场内停留的时间和应缴的费用（在便 道上停留的时间不收费）。（3）栈以顺序结构实现，队列以链表结构实现。实现提示： 需另设一个栈，临时停放为给要离开的汽车让路而从停车场退出来的汽车， 也用顺序存储结构实现。输入数据按到达或离开的时刻有序。栈中每一个元素表 示一辆汽车，包含 2 个数据项：汽车的牌照号码和进入停车场的时刻。6、题目：表达式类型的实现设计任务：一个表达式与一棵二叉

10、树之间，存在着自然的对应关系。写一个程序，实现 基于二叉树表示的算术表达式 Expression 的操作。设计要求：假设算术表达式Expression内可以含有变量（az）、常量（09 ）和二元运 算符（+, -, *, /,人）。实现以下操作：ReadExpr （E）以字符序列的形式输入语法正确的前缀表示式并构造 表达式 E。WriteExpr(E)用带括号的中缀表示式输出表达式E。(3) Assign(V, c)实现对变量V的赋值(V=c),变量的初值为0。(4) Value (E) 对算术表达式E求值。实现提示：(1) 在读入表达式的字符序列的同时,完成运算符和运算数的识别处理以及 相应

11、的运算。(2) 在识别出运算数的同时,要将其字符形式转换成整数形式。(3) 用后根遍历的次序对表达式求值。(4) 用中缀表示输出表达式 E 时,适当添加括号,以正确反映运算的优先次 序。7、题目：一元稀疏多项式计算器 设计任务：设计一个一元稀疏多项式简单计算器。设计要求：一元稀疏多项式简单计算器的基本功能是：(1) 输入并建立多项式creatpolyn()；(2) 输出多项式，输出形式为整数序列：n,cl,el,c2,e2,cn,en,其中n是多项 式的项数, ci 和 ei 分别是第 i 项的系数和指数,序列按指数升序排列 printpolyn()；(3) 多项式a和b相加，建立多项式a+b

12、，输出相加的多项式ddpolyn()；(4) 多项式a和b相减，建立多项式a-b，输出相减的多项式subpolyn()。实现提示：(1) 用带头结点的单链表存储多项式。(2) 参照教材2.4节内容。8、题目：哈夫曼编码系统 设计任务：从键盘输入一串电文字符能输出对应的哈夫曼编码。同时，能翻译由哈夫曼 编码生成的代码串，输出相应的电文字符串。设计要求：(1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树及哈夫曼编码。(2) 利用已经建好的哈夫曼树，对输入的字符串进行编码，输出编码序列。(3) 利用已建好的哈夫曼树对输入的二进制编码进行译码，并输出结果。 实现提示：参见教材 6.6

13、节内容9、题目：排序算法演示系统设计任务：对随机产生的N(N=1000)个数按照多种方法进行排序。设计要求：(1) 至少采用三种方法实现上述问题求解(提示，可采用的方法有插入排序、 希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。(2) 通过人机交互方式选择排序方法。实现提示： 参见教材第10章内容。10、题目：通讯录的制作设计任务： 针对你所在班集体中的“人名”，设计一个哈希表，使得平均查找长度不超 过 R ，完成相应的建表和查找过程。设计要求：(1) 每个人的信息至少包括姓名，电话，地址。至少包括对通讯录的创建， 添加和按姓名查找等功能。(2) 假设人名为汉语拼音全拼形式，待插

14、入哈希表的长度为你所在班级的人 数。哈希函数用除留余数法构造，采用链地址法或二次探测再散列法解决冲突。(3) 完成菜单设计。操作有必要的提示。实现提示：假设人名最大长度不超过 20，取码可以采用折叠处理，将每个字符对应的ASCII 码求和。四、课程设计安排时间：18周（2010年12月272010 年12月31日） 指导教师：指导、考勤：验收教师：孙宁软件09-1王英博赵雪软件09-2齐向明刘佳旭李婕娜网络09-1陈虹徐娇月网络09-2孙宁李婕娜刘亮软件09-3陈虹徐娇月软件09-4王光李红霞孙宁软件09-5郭伟刘金光软件09-6孙宁李婕娜刘金光软件09-7刘亮刘腊梅软件09-8刘万军曲海成刘佳旭软件09-9安达冯永安软件09-10曲长波姜彦吉上机安排：412机房416机房420机房上午下午晚上上午下午晚上上午下午晚上星期一数据结构 （软件095-6数据结构 （软件091-2数据结构 （软件097-8数据结构 （软件093-4数据结构 （软件099-10星期二数据结构 （网络091-2数据结构 （网络091-2星期三数据结构 （软件095-6数据结构 （软件091-2数据结构 （软件097-8数据结构 （软件093-4数据结构 （软件099-10星期四数据结构 （网络091-2数据结构 （软件095-6数据结构 （软件097-8数据结构 （软件099-10