数据结构设计任务书

第二学期《数据结构》课程设计任务书2023-2023课程设计名称数据结构课程设计课程设计学分1课程设计周（时）数1周课程设计授课单位计算机专业教研室指导方式集体辅导与个别辅导相结合课程设计合用专业计算机科学与技术、软件工程、网络工程课程设计教材及重要参考资料《数据结构C++版》王红梅、胡明、王涛编著清华大学出版社2023年《数据结构》，严蔚敏编著，清华大学出版社,2023年服务课程名称数据结构服务课程讲课学时:56服务课程学分:

3.5

一、课程设计教学目的及基本规定L了解并掌握数据结构与算法的设计方法，具有初步的独立分析和设计能力；

2.初步掌握软件开发过程的问题分析、数据结构定义、算法流程分析、程序编码、测试等基本方法和技能；

3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4.训练用系统的观点和软件开发的规范完毕课程设计内容，培养软件工作者所应具有的科学的工作方法和作风

二、课程设计内容及安排

1.分析题目，设计解题思绪根据设计题目的规定，充足地分析和理解问题，明确问题规定做什么？（而不是怎么做？）限制条件是什么.

2.数据结构定义对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型写出每个抽象数据类型的定义（涉及数据结构的描述和每个基本操作的功能说明），各个重要模块的算法，并画出模块之间的调用关系图;以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理每一组输入数据涉及三个数据项:汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜别的时刻,对每一组输入数据进行操作后的输出数据为若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车拜别；则输出汽车在停车场内停留的时间和应交纳的费用在便道上停留的时间不收费核心算法栈和队列的操作第十一题学生成绩管理系统［问题描述］编写一个简朴的学生信息管理程序，能实现对学生信息的简朴管理［基本规定］建立一个4个学生的信息登记表，每个学生的信息涉及学号，姓名，和3门课程的成绩FOX,C,ENGLISH程序运营时显示一个简朴的菜单，例如:1信息输入INPUT2总分记录COUNT3总分排序SORT4查询QUERY其中1对4个学生的信息进行输入；2对每个学生的3门课程记录总分；3对4个学生的总分按降序排序并显示出来；4查询输入一个学号后，显示出该学生的有关信息;核心算法查找和排序第十二题哈希表的设计与实现［问题描述］设计哈希表实现电话号码查询系统［基本规定］

1.设每个记录有下列数据项电话号码、用户名、地址；

2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表;

3.采用再哈希法解决冲突；

4.查找并显示给定电话号码的记录；

5.查找并显示给定用户名的记录同类型解决冲突的方法至少两种，.在哈希函数拟定的前提下，尝试各种不6平均查找长度的变化核心算法哈希表的存储和查找第十三题通讯录管理系统该系统至少应具有如下功能

1.输入记录规定随时都能使用该项功能实现记录的输入，一次可以输入一条记录，也可以输入多条记录

2.输出

（1）按自然顺序输出

（2）按某种排序顺序输出至少两种

3.查询至少提供两种查询方式4,修改至少提供两种修改方式

5.删除既能一次删除一条记录，也能一次删除多条记录

6.退出通讯录管理结束后，正常退出系统规定每个记录至少包含如下信息姓名、电话、所在城市、所在单位、年龄、E-mail、备注等以采单方式实现功能选择控制编写功能独立的函数实现各功能

7.记录最大个数100o核心算法链表的查找、插入和删除第十四题内部排序算法比较［问题描述］各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大约执行时间试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受［基本规定］

（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）对于多条主串进行模式匹配，假如匹配成功则返回主串内容及子串在主串中的位置假如匹配失败，则返回0o第二十题括号匹配的检查[问题描述]假设表达式中允许有两种括号圆括号和方括号，其嵌套的顺序随意，即[]或[[][]]等为对的格式，[]或均为不对的的格式检查括号是否匹配的方法可用“期待的紧迫限度”这个概念来描述例如考虑下列的括号序列[[][]]12345678当计算机接受了第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棋盘Bord[8H8]的某个方格中，马按走棋规则进行移动规定每个方格上只进入一次，走遍棋盘上所有64个方格【任务规定】编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,,,,64依次填入一个8*8的方阵，输出之第二十七题数制转换问题【问题描述】任意给定一个M进制的数x,实现如下规定⑴求出此数x的10进制值;2实现对X向任意的一个非M进制的数的转换；【基本规定】至少用两种或两种以上的方法实现上述规定用栈解决，用数组解决，其它方法解决第二十八题集合的并、交和差运算的程序【问题描述】编制一个能演示执行集合的并、交和差运算的程序【基本规定】⑴集合的元素限定为小写字母符［a z集合的大小*27⑵集合输入的形式为一个以〃回车符〃为结束标志的字符串，串中字符顺序不限，且允许出现反复字符或非法字符，程序应能自动滤去⑶输出的运算结果字符串中将不含反复字符或非法字符⑷演示程序以用户和计算机的对话方式执行第二十九题一元多项式计算器【问题描述】设有一元多项式Amx.和Bn x...Amx..A0+Alxl+A2x2+A3x3+.+Amx...Bn x..B0+Blxl+B2x2+B3x3+.+Bnx..试求Mx.Amx+Bnx、Mx.Amx-Bnx和

3.算法流程分析在这个过程中，要综合考虑题目的具体规定，使得解决算法流程清楚、合理、简朴和易于调试，抽象数据类型的实现尽也许做到数据封装，基本操作的规格说明尽也许明确具体算法流程分析的结果是对数据结构和基本操作进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；

4.编写代码把具体设计的结果进一步求精为程序设计语言程序同时加入一些注解和断言，使程序中逻辑概念清楚；

5.程序调试与测试采用自底向上，分模块进行，即先调试低层函数可以纯熟掌握调试工具的各种功能，设计测试数据拟定疑点，通过修改程序来证实它或绕过它调试对的后,认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；

6.结果分析程序运营结果涉及对的的输入及其输出结果和具有错误的输入及其输出结果算法的时间、空间复杂性分析；

7.编写课程设计报告；

三、课程设计考核方法及成绩评估课程设计结束时，规定学生写出课程设计报告（附源程序），可运营的软件系统课程设计成绩分两部分，设计报告占30%,设计作品占70%按照优秀、良好、中、及格，不及格五级给予成绩

四、其他规定周一布置题目、分析题目指导教师吕冬梅张沛露岳俊华课程设计时间安排周二分析题目，设计解题思绪指导教师段淼郑琦林娜周三数据结构定义，算法流程分析指导教师吕冬梅张沛露岳俊华周四编写代码，调试分析指导教师段淼郑琦林娜周五验收指导教师吕冬梅张沛露岳俊华段淼郑琦林娜M x.Amx XBnx.【基本规定】⑴一方面鉴定多项式是否稀疏；⑵分别采用顺序和链式结构实现；⑶结果Mx中无反复阶项和无零系数项；⑷规定输出结果的升幕和降幕两种排列情况第三十题实时监控报警系统【问题描述】建立一个报警和出警管理的系统【基本规定】1,采用一定的存储结构存储报警信息，规定有内容、时间；

2.有一次的出警就应当在待解决的信息中删除这条信息；

3.记录出警信息.

4.待解决信息过多时会发出警告；计算机科学与工程学院2023-6-24设计题目及基本规定第一题关键途径问题当一项工程被划分为若干个子任务或活动后，人们不仅需要拟定这些活动的先后顺序,并且需要进一步计算完毕整个工程的时间，拟定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为准时或提前完毕整个工程提供保证规定给定一个带权的有向图代表一个工程的AOE网络，研究如下问题

（1）完毕整项工程至少需要多少时间？

（2）哪些活动是影响工程进度的关键活动？示例图核心算法图的关键途径第二题电梯模拟模拟某校九层教学楼的电梯系统该楼有一个自动电梯，能在每层停留九个楼层由下至上依次称为地下层、第一层、第二层、……第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命乘客可随机地进出于任何层对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃模拟时钟从0开始，时间单位为

0.1秒人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；假如电梯在某层静止时间超过300t,则驶回1层侯命而题目的最终规定输H1时:准时序显示系统状态的变化过程，即发生的所有人和电梯的动作序列核心算法乘客采用栈，等待乘客采用队列第三题研究生入学考试成绩解决假设某大学计算机应用技术专业招收研究生n名，现在要根据报考者的考试成绩择优录取考试课程有政治、英语、数学、专业综合四门考试成绩分为两类第一类为每门课程都达成最低录取线；第二类为有一门或多门课程未达成最低录取线录取方法是在每门课程达成最低录取线的考生中按总分从高到低录取试设计一个成绩解决程序实现以上功能根据录取方法，打印输出n份录取告知书，列出录取者四门课程的成绩及总分（规定采用堆排序）并能实现对任一考生或任一门课程成绩的查找（规定两种查找方式，根据考号或姓名进行查找，采用高效的查找算法）录取告知书的格式如下核心算法链表的查找第四题哈夫曼编码与译码问题

（1）

（2）设计一个哈夫曼编码、译码系统对一个ASCII编码的文本文献中的字符进行哈夫曼编码，生成编码文献；反过来，可将编码文献译码还原为一个文本文献

（3）从文献中读入任意一篇英文短文（文献为ASCII编码，扩展名为txt）；

（4）记录并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符解决）；

（5）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；

（6）将文本文献运用哈夫曼树进行编码，存储成压缩文献（编码文献后缀名.huf）用哈夫曼编码来存储文献，并和输入文本文献大小进行比较，计算文献压缩率；进行译码，将huf文献译码为ASCII编码的txt文献，与原txt文献进行比较核心算法哈夫曼树的编码及译码第五题校园导游图用无向网表达本学校校园景点平面图，选取若干个有代表性的景点抽象成无向带权图，图中顶点表达校内各顶点，边上权值表达途径长度可以1为来访客人查询各景点的相关信息；2为来访客人查询图中任意两个景点间的最短途径3为来访客人查询图中任意两个景点间的所有途径4为来访客人修改图中顶点和边的信息5为来访客人增长景点和途径6为来访客人删除景点和途径7为来访客人输出相应编号景点的信息核心算法图的最短途径第六题简朴的文本编辑器内容输入一页文字，程序可以记录出文字、数字、空格的个数静态存储一页文章，每行最多不超过80个字符，共N行规定1分别记录出其中英文字母数和空格数及整篇文章总字数；2记录某一字符串在文章中出现的次数，并输出该次数；3删除某一字符或者子串，并将后面的字符前移4插入某一字符或者子串5查找某一字符或者子串存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围可以输入大写、小写的英文字母、任何数字及标点符号输出形式:1分行输出用户输入的各行字符；2分4行输出”所有字母数“、“数字个数“、“空格个数“、”文章总字数”3输出删除某一字符串后的文章通过题目及其规定可知，本程序应实现以下功能1文章内容的输入涉及字母、标点符号、数字等；文章内容的记录涉及文章中大写字母、小写字母、数字、标点符号、空格以及文章所有字数的个数的记录；文章内容的解决涉及对文章内容的查找、删除以及对指定位置进行插入操作，其中在查找的过程中记录出该字符或字符串在文章中出现的次数；核心算法链表的查找、删除、插入第七题运动会分数记录参与运动会有n个学校，学校编号为1……no比赛提成m个男子项目，和w个女子项目项目编号为男子1……叫女子ni+1……m+w不同的项目取前五名或前三名积分；取前五名的积分分别为

7、

5、

3、

2、1,前三名的积分分别为

5、

3、2；哪些取前五名或前三名由学生自己设定m=20,n=20［基本规定］⑴可以输入各个项目的前三名或前五名的成绩；⑵能记录各学校总分3可以按学校编号、学校总分、男女团队总分排序输出；4可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校规定输入数据形式和范围20以内的整数假如做得更好可以输入学校的名称，运动项目的名称输出形式有中文提醒，各学校分数为整形界面规定有合理的提醒，每个功能可以设立菜单，根据提醒，可以完毕相关的功能规定存储结构学生自己根据系统功能规定自己设计，但是规定运动会的相关数据要存储在数据文献中（数据文献的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据规定使用

1.所有合法数据；2,整体非法数据；

3.局部非法数据进行程序测试,以保证程序的稳定测试数据及测试结果请在上交的资料中写明；核心算法排序第八题航空客运订票系统［问题描述］通过此系统可以实现如下功能录入可以录入航班情况（数据可以存储在一个数据文献中，数据结构、具体数据自定）查询可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞到达城市，航班票价，票价折扣，拟定航班是否满仓）；可以输入起飞到达城市，查询飞机航班情况；订票（订票情况可以存在一个数据文献中，结构自己设定）可以订票，假如该航班已经无票，可以提供相关可选择航班；退票可退票，退票后修改相关数据文献；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号修改航班信息当航班信息改变可以修改航班数据文献［基本规定］根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完毕功能;核心算法队列的操作第九题模拟旅馆管理系统的一个功能一一床位的分派与回收［问题描述］某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位IWiWn试模拟旅馆管理系统中床位分派和回收的功能，设计能为单个旅客分派床位，在其离店便回收床位供下次分派的算法［基本规定］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,,0,0o每一组输入数据涉及三个数据项汽车“到达”或“拜别”信息、汽车牌照号码及到达或拜别的时刻，其中，A，表达成达；D，表达拜别，E，表达输入结束［基本规定］。