数据结构设计任务书.doc

2023-2023第二学期数据结构课程设计任务书课程设计名称：数据结构课程设计 课程设计学分：1 课程设计周（时）数：1周课程设计授课单位：计算机专业教研室 指导方式：集体辅导与个别辅导相结合课程设计合用专业：计算机科学与技术、软件工程、网络工程 课程设计教材及重要参考资料：数据结构C+版 王红梅、胡明、王涛编著 清华大学出版社 2023年数据结构，严蔚敏编著，清华大学出版社，2023年服务课程名称：数据结构服务课程讲课学时：56 服务课程学分：3.5一、课程设计教学目的及基本规定1.了解并掌握数据结构与算法的设计方法，具有初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、数据结构定义、算法流程分析、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发的规范完毕课程设计内容，培养软件工作者所应具有的科学的工作方法和作风。二、课程设计内容及安排1. 分析题目，设计解题思绪：根据设计题目的规定，充足地分析和理解问题，明确问题规定做什么？（而不是怎么做？）限制条件是什么？ 2.数据结构定义：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。写出每个抽象数据类型的定义(涉及数据结构的描述和每个基本操作的功能说明)，各个重要模块的算法，并画出模块之间的调用关系图；3.算法流程分析：在这个过程中，要综合考虑题目的具体规定，使得解决算法流程清楚、合理、简朴和易于调试，抽象数据类型的实现尽也许做到数据封装，基本操作的规格说明尽也许明确具体。算法流程分析的结果是对数据结构和基本操作进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4. 编写代码：把具体设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。可以纯熟掌握调试工具的各种功能，设计测试数据拟定疑点，通过修改程序来证实它或绕过它。调试对的后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6.结果分析：程序运营结果涉及对的的输入及其输出结果和具有错误的输入及其输出结果。算法的时间、空间复杂性分析；7.编写课程设计报告；三、课程设计考核方法及成绩评估课程设计结束时，规定学生写出课程设计报告（附源程序），可运营的软件系统课程设计成绩分两部分，设计报告占30，设计作品占70。按照优秀、良好、中、及格，不及格五级给予成绩。四、其他规定课程设计时间安排周一 布置题目、分析题目 指导教师 吕冬梅 张沛露 岳俊华周二 分析题目，设计解题思绪 指导教师 段淼 郑琦 林娜周三 数据结构定义，算法流程分析 指导教师 吕冬梅 张沛露 岳俊华周四 编写代码，调试分析 指导教师 段淼 郑琦 林娜周五 验收 指导教师 吕冬梅 张沛露 岳俊华 段淼 郑琦 林娜设计题目及基本规定第一题：关键途径问题当一项工程被划分为若干个子任务或活动后，人们不仅需要拟定这些活动的先后顺序，并且需要进一步计算完毕整个工程的时间，拟定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为准时或提前完毕整个工程提供保证。规定：给定一个带权的有向图代表一个工程的AOE网络，研究如下问题：（1）完毕整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键活动？示例图：核心算法：图的关键途径第二题：电梯模拟模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；假如电梯在某层静止时间超过300t，则驶回1层侯命。而题目的最终规定输出时：准时序显示系统状态的变化过程，即发生的所有人和电梯的动作序列。核心算法：乘客采用栈，等待乘客采用队列第三题：研究生入学考试成绩解决假设某大学计算机应用技术专业招收研究生n名，现在要根据报考者的考试成绩择优录取。考试课程有政治、英语、数学、专业综合四门。考试成绩分为两类：第一类为每门课程都达成最低录取线；第二类为有一门或多门课程未达成最低录取线。录取方法是在每门课程达成最低录取线的考生中按总分从高到低录取。试设计一个成绩解决程序实现以上功能。根据录取方法，打印输出n份录取告知书，列出录取者四门课程的成绩及总分（规定采用堆排序）。并能实现对任一考生或任一门课程成绩的查找（规定两种查找方式，根据考号或姓名进行查找，采用高效的查找算法）。录取告知书的格式如下：核心算法：链表的查找第四题：哈夫曼编码与译码问题设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文献中的字符进行哈夫曼编码，生成编码文献；反过来，可将编码文献译码还原为一个文本文献。（1） 从文献中读入任意一篇英文短文（文献为ASCII编码，扩展名为txt）；（2） 记录并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符解决）；（3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；（4） 将文本文献运用哈夫曼树进行编码，存储成压缩文献（编码文献后缀名.huf）（5） 用哈夫曼编码来存储文献，并和输入文本文献大小进行比较，计算文献压缩率；（6） 进行译码，将huf文献译码为ASCII编码的txt文献，与原txt文献进行比较。核心算法：哈夫曼树的编码及译码第五题：校园导游图用无向网表达本学校校园景点平面图，选取若干个有代表性的景点抽象成无向带权图，图中顶点表达校内各顶点，边上权值表达途径长度。可以：（1）为来访客人查询各景点的相关信息；（2）为来访客人查询图中任意两个景点间的最短途径（3）为来访客人查询图中任意两个景点间的所有途径（4）为来访客人修改图中顶点和边的信息（5）为来访客人增长景点和途径（6）为来访客人删除景点和途径（7）为来访客人输出相应编号景点的信息核心算法：图的最短途径第六题：简朴的文本编辑器内容：输入一页文字，程序可以记录出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。规定：（1）分别记录出其中英文字母数和空格数及整篇文章总字数；（2）记录某一字符串在文章中出现的次数，并输出该次数；（3）删除某一字符或者子串，并将后面的字符前移。（4）插入某一字符或者子串。（5）查找某一字符或者子串。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出所有字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章。通过题目及其规定可知，本程序应实现以下功能：文章内容的输入：涉及字母、标点符号、数字等；（1） 文章内容的记录：涉及文章中大写字母、小写字母、数字、标点符号、空格以 及文章所有字数的个数的记录；（2） 文章内容的解决：涉及对文章内容的查找、删除以及对指定位置进行插入操作， 其中在查找的过程中记录出该字符或字符串在文章中出现的次数；核心算法：链表的查找、删除、插入第七题：运动会分数记录参与运动会有n个学校，学校编号为1n。比赛提成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）基本规定(1)可以输入各个项目的前三名或前五名的成绩；(2)能记录各学校总分(3)可以按学校编号、学校总分、男女团队总分排序输出；(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（假如做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提醒，各学校分数为整形界面规定：有合理的提醒，每个功能可以设立菜单，根据提醒，可以完毕相关的功能规定。存储结构：学生自己根据系统功能规定自己设计，但是规定运动会的相关数据要存储在数据文献中。（数据文献的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：规定使用1、所有合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；核心算法：排序第八题：航空客运订票系统问题描述通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文献中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞到达城市，航班票价，票价折扣，拟定航班是否满仓）；可以输入起飞到达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文献中，结构自己设定）可以订票，假如该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文献；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文献基本规定根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完毕功能； 核心算法：队列的操作第九题：模拟旅馆管理系统的一个功能床位的分派与回收问题描述某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位（1in）。试模拟旅馆管理系统中床位分派和回收的功能，设计能为单个旅客分派床位，在其离店便回收床位（供下次分派）的算法。基本规定（1）输入数据分派时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。回收时，输入房间等级、房间号和床位号。（2）输出数据分派成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。分派不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否乐意更换等级？”的询问信息。若旅客乐意更换，则重新输入有关信息，再进行分派，否则分派工作结束。核心算法：队列的操作第十题：停车场管理问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原顺序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述规定进行管理的模拟程序。测试数据设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表达输入结束。基本规定以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据涉及三个数据项：汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜别的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车拜别；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。核心算法：栈和队列的操作。第十一题：学生成绩管理系统问题描述编写一个简朴的学生信息管理程序，能实现对学生信息的简朴管理。基本规定建立一个4个学生的信息登记表，每个学生的信息涉及：学号，姓名，和3门课程的成绩（FOX,C,ENGLISH）。程序运营时显示一个简朴的菜单，例如：（1）信息输入（INPUT）（2）总分记录（COUNT）（3）总分排序（SORT）（4）查询(QUERY） 其中： （1）对4个学生的信息进行输入； （2）对每个学生的3门课程记录总分； (3)对4个学生的总分按降序排序并显示出来；(4)查询输入一个学号后，显示出该学生的有关信息；核心算法：查找和排序第十二题：哈希表的设计与实现 问题描述 设计哈希表实现电话号码查询系统。基本规定1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。6、在哈希函数拟定的前提下，尝试各种不同类型解决冲突的方法（至少两种），考察平均查找长度的变化。 核心算法：哈希表的存储和查找第十三题：通讯录管理系统该系统至少应具有如下功能：1输入记录 规定随时都能使用该项功能实现记录的输入，一次可以输入一条记录，也可以输入多条记录。2输出 （1）按自然顺序输出 （2）按某种排序顺序输出。至少两种。3查询 至少提供两种查询方式。4修改 至少提供两种修改方式。5删除 既能一次删除一条记录，也能一次删除多条记录。6退出 通讯录管理结束后，正常退出系统。规定：每个记录至少包含如下信息：姓名、电话、所在城市、所在单位、年龄、E-mail、备注等。 以采单方式实现功能选择控制。 编写功能独立的函数实现各功能。 4记录最大个数100。核心算法：链表的查找、插入和删除第十四题：内部排序算法比较问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大约执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本规定（1） 对以下几种常用的内部排序算法进行比较：直接插入排序；折半折入排序；希尔排序；起泡排序；快速排序；简朴选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参与的比较次数和关键字移动次数（关键字互换计为3次移动）。测试数据由随机产生器决定。第十五题：记录成绩问题描述给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关记录，并打印登记表。基本规定（1） 按总数高低顺序，打印出名次表，分数相同的为同一名次；（2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。第十六题：大数相乘问题问题描述在用某种程序设计语言进行编程时，也许需要解决非常大或者运算精度规定非常高的整数（称为大整数），这种大整数用该语言的基本数据类型无法直接表达。对这样的两个大整数，编写程序计算两个大整数相乘。基本规定输入第一个数为：172586输入第二个数为：1147程序运营后输出172586*1147=对的答案。核心算法：用数组存储大整数，数组元素代表大整数的一个位，通过数组元素的运算模拟大整数的元素。第十七题：矩阵的运算问题描述矩阵式很多工程与科学计算问题中的解决对象。在实际应用中，经常出现一些阶数很高的矩阵，同时在矩阵中有很多零元素，称为稀疏矩阵。对于这样的矩阵可以进行压缩存储，从而节省存储空间，使矩阵的加法运算可以有效的进行。基本规定(1采用十字链表表达稀疏矩阵，并实现矩阵的加法运算。 (2) 要检查有关运算的条件，并对错误的条件产生报警。第十八题：构造n个城市连接的最小生成树问题描述一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本规定1)城市间的距离网采用邻接矩阵表达，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。规定在屏幕上显示得到的最小生成树中涉及了哪些城市间的道路，并显示得到的最小生成树的代价。2)表达城市间距离网的邻接矩阵(规定至少6个城市，10条边)第十九题：字符串的模式匹配问题描述在事务解决程序中，顾客的姓名、货品的产地等一般都是作为字符串解决的。对于这些关键词的查询也就是在主串中寻找子串的过程，即为模式匹配。基本规定（1）输入多条主串，及一条子串。（2）对于多条主串进行模式匹配，假如匹配成功则返回主串内容及子串在主串中的位置。假如匹配失败，则返回0。第二十题：括号匹配的检查问题描述 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（） ）或（ ）等为对的格式，（ ）或（均为不对的的格式。检查括号是否匹配的方法可用“期待的紧迫限度”这个概念来描述。例如：考虑下列的括号序列： ( ) 1 2 3 4 5 6 7 8 当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫限度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫限度高于第2个括号，而第2个括号的期待紧迫限度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急切的任务了， ，依次类推。可见这个解决过程正好和栈的特点相吻合。 基本规定 （1）读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。（2）以下面测试数据为例，若 输入（ （），结果应输出“匹配” 输入 （ ），结果应输出“此串括号匹配不合法” 实现提醒 设立一个栈，每读入一个括号，若是左括号，则作为一个新的更急切的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，假如读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应当是空的。第二十一题：图书管理系统的设计与实现【问题描述】 设计一个计算机管理系统完毕图书管理基本业务。【基本规定】 （1）每种书的登记内容涉及书号、书名、著作者、现存量、库存量和借阅信息； （2）系统重要功能如下： 采编入库：新购一种书，拟定书号后，登记到图书帐目表中，假如表中已有，则只将库存量增长； 借阅：假如一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； 归还：注销对借阅者的登记，改变该书的现存量。第二十二题：客户消费积分管理系统的设计与实现 【问题描述】 针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同限度的打折优惠。 【基本规定】 采用一定的存储结构进行客户信息的存储； 对客户的信息可以进行修改、删除、添加； 可以根据消费情况进行客户积分的累加； 根据积分情况，对客户实行不同限度的打折优惠；第二十三题：家谱管理系统的设计与实现【问题描述】设计并实现一个简朴的家谱管理系统。 【基本规定】 （1）建立家族关系并能存储到文献中。 （2）实现家族成员的添加、删除功能。 （3）可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。 （4）按某种顺序输出家谱信息（树的遍历操作）、以树型结构输出家谱资料等功能。第二十三题：算术表达式求解 【问题描述】给定一个算术表达式，通过程序求出最后的结果。 【基本规定】 (1)从键盘输入规定解的算术表达式； (2)采用栈结构进行算术表达式的求解过程； (3)可以判断算术表达式对的与否； (4)对于对的的表达式给出最后的结果、并可以显示运算的整个过程。第二十四题：病人就医管理【问题描述】编写一个程序实现就医管理。在病人就医过程中，重要发生三件事： 预检，分科室，挂号。 病人到达诊室，将病历本交给护士，排到等待队列中候诊。 护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。【基本规定】规定程序采用菜单方式，其选项及功能说明如下： 挂号-预检，分科室，生成就诊号。 排队-输入病人的就诊号，加入到病人排队队列中。 就诊-病人排队队列中最前面的病人就诊，并将其从队列中删除。 查看排队-从队首到队尾列出所有的排队病人的病历号。 下班-退出运营。第二十五题： 银行业务模拟【问题描述】设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，优先级不同。客户到达银行后，先到打号机上打号，号票上涉及到达时间、编号和需要办理的业务，然后在银行内等候。当任一服务窗口空闲时,解决等候客户中优先级最高，排在最前面的客户的业务。写一个上述银行业务的模拟系统,通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。 【基本规定】每个客户到达银行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口天天办理的客户数和每种业务数。第二十六题： 马踏棋盘 【问题描述】 将马随机放在国际象棋的8* 8棋盘Bord88的某个方格中，马按走棋规则进行移动。规定每个方格上只进入一次，走遍棋盘上所有64个方格。 【任务规定】 编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个8* 8的方阵，输出之。第二十七题： 数制转换问题【问题描述】任意给定一个M进制的数x，实现如下规定： (1)求出此数x的10进制值； (2) 实现对X向任意的一个非M进制的数的转换； 【基本规定】至少用两种或两种以上的方法实现上述规定（用栈解决，用数组解决，其它方法解决）第二十八题： 集合的并、交和差运算的程序【 问题描述】 编制一个能演示执行集合的并、交和差运算的程序。 【基本规定】(1)集合的元素限定为小写字母符a.z ，集合的大小n27。 集合输入的形式为一个以回车符为结束标志的字符串，串中字符顺序不限，且允许出现反复字符或非法字符，程序应能自动滤去。 输出的运算结果字符串中将不含反复字符或非法字符。 演示程序以用户和计算机的对话方式执行。第二十九题： 一元多项式计算器 【问题描述】 设有一元多项式Am(x) 和Bn(x). Am(x) = A0+A1x1+A2x2+A3x3+ +Amxm Bn(x) = 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.待解决信息过多时会发出警告；计算机科学与工程学院2023-6-24