数据结构设计任务书.doc

《数据结构设计任务书.doc》由会员分享，可在线阅读，更多相关《数据结构设计任务书.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2014-2015第二学期数据结构课程设计任务书课程设计名称：数据结构课程设计 课程设计学分：1 课程设计周（时）数：1周课程设计授课单位：计算机专业教研室 指导方式：集体辅导与个别辅导相结合课程设计适用专业：计算机科学与技术、软件工程、网络工程 课程设计教材及主要参考资料：数据结构C+版 王红梅、胡明、王涛编著 清华大学出版社 2011年数据结构，严蔚敏编著，清华大学出版社，2001年服务课程名称：数据结构服务课程讲课学时：56 服务课程学分：3.5一、课程设计教学目的及基本要求1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、数据结构

2、定义、算法流程分析、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发的规范完成课程设计内容，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计内容及安排1. 分析题目，设计解题思路：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.数据结构定义：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模

3、块之间的调用关系图；3.算法流程分析：在这个过程中，要综合考虑题目的具体要求，使得解决算法流程清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。算法流程分析的结果是对数据结构和基本操作进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4. 编写代码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式

4、和风格良好的源程序清单和结果；6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7.编写课程设计报告；三、课程设计考核方法及成绩评定课程设计结束时，要求学生写出课程设计报告（附源程序），可运行的软件系统课程设计成绩分两部分，设计报告占30，设计作品占70。按照优秀、良好、中、及格，不及格五级给予成绩。四、其他要求课程设计时间安排周一 布置题目、分析题目 指导教师 吕冬梅 张沛露 岳俊华周二 分析题目，设计解题思路 指导教师 段淼 郑琦 林娜周三 数据结构定义，算法流程分析 指导教师 吕冬梅 张沛露 岳俊华周四 编写代码，调试分析 指导

5、教师 段淼 郑琦 林娜周五 验收 指导教师 吕冬梅 张沛露 岳俊华 段淼 郑琦 林娜设计题目及基本要求第一题：关键路径问题当一项工程被划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证。要求：给定一个带权的有向图代表一个工程的AOE网络，研究如下问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键活动？示例图：核心算法：图的关键路径第二题：电梯模拟模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在

6、每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；如果电梯在某层静止时间超过300t，则驶回1层侯命。而题目的最终要求输出时：按时序显示系统状态的变化过程，即发生的全部人和电梯的动作序列。核心算法

7、：乘客采用栈，等待乘客采用队列第三题：研究生入学考试成绩处理假设某大学计算机应用技术专业招收研究生n名，现在要根据报考者的考试成绩择优录取。考试课程有政治、英语、数学、专业综合四门。考试成绩分为两类：第一类为每门课程都达到最低录取线；第二类为有一门或多门课程未达到最低录取线。录取方法是在每门课程达到最低录取线的考生中按总分从高到低录取。试设计一个成绩处理程序实现以上功能。根据录取方法，打印输出n份录取通知书，列出录取者四门课程的成绩及总分（要求采用堆排序）。并能实现对任一考生或任一门课程成绩的查找（要求两种查找方式，根据考号或姓名进行查找，采用高效的查找算法）。录取通知书的格式如下：核心算法：

8、链表的查找第四题：哈夫曼编码与译码问题设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。（1） 从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；（2） 统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；（4） 将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）（5） 用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6） 进行译码，将huf文件译码为ASC

9、II编码的txt文件，与原txt文件进行比较。核心算法：哈夫曼树的编码及译码第五题：校园导游图用无向网表示本学校校园景点平面图，选取若干个有代表性的景点抽象成无向带权图，图中顶点表示校内各顶点，边上权值表示路径长度。能够：（1）为来访客人查询各景点的相关信息；（2）为来访客人查询图中任意两个景点间的最短路径（3）为来访客人查询图中任意两个景点间的所有路径（4）为来访客人修改图中顶点和边的信息（5）为来访客人增加景点和路径（6）为来访客人删除景点和路径（7）为来访客人输出对应编号景点的信息核心算法：图的最短路径第六题：简单的文本编辑器内容：输入一页文字，程序可以统计出文字、数字、空格的个数。静态

10、存储一页文章，每行最多不超过80个字符，共N行。要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一字符或者子串，并将后面的字符前移。（4）插入某一字符或者子串。（5）查找某一字符或者子串。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章。通过题目及其要求可知，本程序应实现以下功能：文章内容的输入：包括字母、标

11、点符号、数字等；（1） 文章内容的统计：包括文章中大写字母、小写字母、数字、标点符号、空格以 及文章所有字数的个数的统计；（2） 文章内容的处理：包括对文章内容的查找、删除以及对指定位置进行插入操作， 其中在查找的过程中统计出该字符或字符串在文章中出现的次数；核心算法：链表的查找、删除、插入第七题：运动会分数统计参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）基本要求

12、(1)可以输入各个项目的前三名或前五名的成绩；(2)能统计各学校总分(3)可以按学校编号、学校总分、男女团体总分排序输出；(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明

13、你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；核心算法：排序第八题：航空客运订票系统问题描述通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修

14、改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件基本要求根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 核心算法：队列的操作第九题：模拟旅馆管理系统的一个功能床位的分配与回收问题描述某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位（1in）。试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。基本要求（1）输入数据分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。回收时，输入房间等级、房间号和床位号。（2）输出数据分

15、配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。核心算法：队列的操作第十题：停车场管理问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场

16、内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。测试数据设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3， 20）， （A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从

17、终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。核心算法：栈和队列的操作。第十一题：学生成绩管理系统问题描述编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。基本要求建立一个4个学生的信息登记表，每个学生的信息包括：学号，姓名，和3门课程的成绩（FOX,C,ENGLISH）。程序运行时显示一个简单的菜单，例如：（1）信息输入（IN

18、PUT）（2）总分统计（COUNT）（3）总分排序（SORT）（4）查询(QUERY） 其中： （1）对4个学生的信息进行输入； （2）对每个学生的3门课程统计总分； (3)对4个学生的总分按降序排序并显示出来；(4)查询输入一个学号后，显示出该学生的有关信息；核心算法：查找和排序第十二题：哈希表的设计与实现 问题描述 设计哈希表实现电话号码查询系统。基本要求1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。6、在哈希函数确定的前提下，尝

19、试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。 核心算法：哈希表的存储和查找第十三题：通讯录管理系统该系统至少应具有如下功能：1输入记录 要求随时都能使用该项功能实现记录的输入，一次可以输入一条记录，也可以输入多条记录。2输出 （1）按自然顺序输出 （2）按某种排序顺序输出。至少两种。3查询 至少提供两种查询方式。4修改 至少提供两种修改方式。5删除 既能一次删除一条记录，也能一次删除多条记录。6退出 通讯录管理结束后，正常退出系统。要求：每个记录至少包含如下信息：姓名、电话、所在城市、所在单位、年龄、E-mail、备注等。 以采单方式实现功能选择控制。 编写功能独立的函数

20、实现各功能。 4记录最大个数100。核心算法：链表的查找、插入和删除第十四题：内部排序算法比较问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求（1） 对以下几种常用的内部排序算法进行比较：直接插入排序；折半折入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。测试数据

21、由随机产生器决定。第十五题：统计成绩问题描述给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。基本要求（1） 按总数高低次序，打印出名次表，分数相同的为同一名次；（2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。第十六题：大数相乘问题问题描述在用某种程序设计语言进行编程时，可能需要处理非常大或者运算精度要求非常高的整数（称为大整数），这种大整数用该语言的基本数据类型无法直接表示。对这样的两个大整数，编写程序计算两个大整数相乘。基本要求输入第一个数为：输入第二个数为：41147程序运行后输出*41147=正确答案。核

22、心算法：用数组存储大整数，数组元素代表大整数的一个位，通过数组元素的运算模拟大整数的元素。第十七题：矩阵的运算问题描述矩阵式很多工程与科学计算问题中的处理对象。在实际应用中，经常出现一些阶数很高的矩阵，同时在矩阵中有很多零元素，称为稀疏矩阵。对于这样的矩阵可以进行压缩存储，从而节省存储空间，使矩阵的加法运算能够有效的进行。基本要求(1采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。 (2) 要检查有关运算的条件，并对错误的条件产生报警。第十八题：构造n个城市连接的最小生成树问题描述一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本

23、要求1)城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)第十九题：字符串的模式匹配问题描述在事务处理程序中，顾客的姓名、货物的产地等一般都是作为字符串处理的。对于这些关键词的查询也就是在主串中寻找子串的过程，即为模式匹配。基本要求（1）输入多条主串，及一条子串。（2）对于多条主串进行模式匹配，如果匹配成功则返回主串内容及子串在主串中的位置。如果匹配失败，则

24、返回0。第二十题：括号匹配的检验问题描述 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（） ）或（ ）等为正确格式，（ ）或（均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： ( ) 1 2 3 4 5 6 7 8 当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号

25、的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了， ，依次类推。可见这个处理过程正好和栈的特点相吻合。 基本要求 （1）读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。（2）以下面测试数据为例，若 输入（ （），结果应输出“匹配” 输入 （ ），结果应输出“此串括号匹配不合法” 实现提示 设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如

26、果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。第二十一题：图书管理系统的设计与实现【问题描述】 设计一个计算机管理系统完成图书管理基本业务。【基本要求】 （1）每种书的登记内容包括书号、书名、著作者、现存量、库存量和借阅信息； （2）系统主要功能如下： 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； 归还：注销对借阅者的登记，改变该书的现存量。第二十二题：客户消费积分管理系统的设计与实现 【问题描述】 针对客户的消费情况，进

27、行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。 【基本要求】 采用一定的存储结构进行客户信息的存储； 对客户的信息可以进行修改、删除、添加； 能够根据消费情况进行客户积分的累加； 根据积分情况，对客户实行不同程度的打折优惠；第二十三题：家谱管理系统的设计与实现【问题描述】设计并实现一个简单的家谱管理系统。 【基本要求】 （1）建立家族关系并能存储到文件中。 （2）实现家族成员的添加、删除功能。 （3）可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。 （4）按某种顺序输出家谱信息（树的遍历操作）、以树型结构输出家谱资料等功能。第二十三题：算术表达式求解 【问题描述】给定一个算

28、术表达式，通过程序求出最后的结果。 【基本要求】 (1)从键盘输入要求解的算术表达式； (2)采用栈结构进行算术表达式的求解过程； (3)能够判断算术表达式正确与否； (4)对于正确的表达式给出最后的结果、并可以显示运算的整个过程。第二十四题：病人就医管理【问题描述】编写一个程序实现就医管理。在病人就医过程中，主要发生三件事： 预检，分科室，挂号。 病人到达诊室，将病历本交给护士，排到等待队列中候诊。 护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。【基本要求】要求程序采用菜单方式，其选项及功能说明如下： 挂号-预检，分科室，生成就诊号。 排队-输入病人的就诊号，加入到病人排队队列中。

29、 就诊-病人排队队列中最前面的病人就诊，并将其从队列中删除。 查看排队-从队首到队尾列出所有的排队病人的病历号。 下班-退出运行。第二十五题： 银行业务模拟【问题描述】设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，优先级不同。客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候。当任一服务窗口空闲时,处理等候客户中优先级最高，排在最前面的客户的业务。写一个上述银行业务的模拟系统,通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。 【基本要求】每个客户到达银

30、行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口每天办理的客户数和每种业务数。第二十六题： 马踏棋盘 【问题描述】 将马随机放在国际象棋的8* 8棋盘Bord88的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。 【任务要求】 编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个8* 8的方阵，输出之。第二十七题： 数制转换问题【问题描述】任意给定一个M进制的数x，实现如下要求： (1)求出此数x的10进制值； (2) 实现对X向任意的一个非M进制的数的转换； 【基本要求】至少用两种或两种以上的方

31、法实现上述要求（用栈解决，用数组解决，其它方法解决）第二十八题： 集合的并、交和差运算的程序【 问题描述】 编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】(1)集合的元素限定为小写字母符a.z ，集合的大小n27。 集合输入的形式为一个以回车符为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。 输出的运算结果字符串中将不含重复字符或非法字符。 演示程序以用户和计算机的对话方式执行。第二十九题： 一元多项式计算器 【问题描述】 设有一元多项式Am(x) 和Bn(x). Am(x) = A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)

32、= B0+B1x1+B2x2+B3x3+ +Bnxn 试求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。 【基本要求】 首先判定多项式是否稀疏； 分别采用顺序和链式结构实现； 结果M(x)中无重复阶项和无零系数项； 要求输出结果的升幂和降幂两种排列情况。 第三十题：实时监控报警系统 【问题描述】建立一个报警和出警管理的系统。 【基本要求】 1.采用一定的存储结构存储报警信息，要求有内容、时间； 2.有一次的出警就应该在待处理的信息中删除这条信息； 3. 记录出警信息； 4.待处理信息过多时会发出警告；计算机科学与工程学院2015-6-24