《2022年数据结构课程设计 7.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计 7.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 课程设计的步骤和报告规范课程设计的步骤：一、问题分析和任务定义在设计之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什么？对所需完成的任务作出明确的回答。二、系统设计系统设计分为逻辑设计和详细设计两步。逻辑设计指的是，对问题描述中的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义软件模块结构图；详细设计则为定义相应的存储结构，并写出各函数模块的伪码算法。三、编码实现和调试四、总结和整理课程设计报告课程设计报告规范：课程设计报告的开头应给出题目、专业、班级、学号、姓名、指导老师和完成日期，并包括以下七个内容：一、问题描述二、需求分析：以无歧义的陈述
2、说明程序设计的任务，强调的是程序要做什么？同时明确规定：输入的形式和输出值的范围；输出的形式；程序所能够达到的功能；测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。三、概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。四、软件模块结构图五、详细设计：每部分模块的设计，含数据结构的设计，算法的描述（流程图或PDL）。各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能
3、部分要加上清晰的程序注释。六、程序流程图七、源程序八、调试分析：测试数据、测试过程、测试结果及评价九、测试数据与实验结果十、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤十一、本章小结：总结可以包括:课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容课程设计要求：1、学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -主动通过各种方式与教师联系沟通。2、学生要发挥自主学习的能力，充分利用时间，安排
4、好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。3、课程设计按照教学要求需要两周时间完成，两周中每天（按每周5 天）至少要上3-4 小时的机来调试C/C+语言/JAVA 设计的程序。4、设计期间，要求严格遵守学校规章制度和实验室管理制度。5、按指定时间上机，服从指导教师和实验室其他老师的安排。6、上机前，应编写相应的程序，禁止无准备的上机。7、每次上机，由老师点名，与最后演示以及设计报告一起，构成最终成绩。第一次上机，填写老师手中的选题表。非特殊情况，不得中间换题。选题尽可能不要集中在某些题上，最后给分会结合题目的难度进行平衡。第二章 课程设计选题1、试设计一个火
5、车票销售系统。问题描述：试编制一个简单的火车票销售系统，可完成售票、退票、车票剩余情况查询等功能。每张车票包含车次、座位等信息。2、试设计一个航空客运订票系统。问题描述：每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2 或 3）以及等候替补的客户名单（包括姓名、所需数量）。系统能实现的操作和功能如下：（1）查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；（2）承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理
6、订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。若需要，可登记排队候补；（3）承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。由于预约人数无法预计，队列也应以链表作为存储结构。3、简单编译器的实现（括号配对检查）问题描述：通常在程序调试时都有对源代码编译的过程，而对左右括号是否
7、匹配也是编译过程中的一个重要环节，试设计一个程序对任意输入的语句或数学表达式，判断其左右括号是否匹配。4、实现二叉树中所有结点左右子树的交换问题描述：对任意一棵二叉树，试将其所有结点的左右子树交换。并将交换前后的不同二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历。5、哈夫曼树在通信编码中的应用问题描述：设一份电文中有不同出现频率的字符，为了提高电文的输入和翻译效率，必须有一套简短而又不会产生歧义的字符代码。试根据哈夫曼算法，对电文中的不同字符，构名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -造出一棵哈夫曼树，对每个字符进行编码。6、二叉排序树建立和查找问题描
8、述：首先建立一棵二叉排序树，二叉排序树查找是指按照二叉排序树中结点的关系进行查找，查找关键字首先同树根结点进行比较，如果相等则查找成功；如果比根结点小，则在左子树中查找；如果比根结点大，则在右子树中进行查找。7、二叉排序树插入和删除问题描述：首先建立一棵二叉排序树，二叉排序树插入是指如果在二叉排序树中能够找到该结点，不插入；如果查找不成功，按照二叉排序树中结点的关系查找，关键字首先同树根结点进行比较，如果比根结点小，则将该结点插入到左子树中；如果比根结点大，则将该结点插入到右子树中。在二叉排序树中删除一个结点时，必须保证删除这个结点后，仍然还是一棵二叉排序树。8、通讯录的管理问题描述：试编程完
9、成通讯录的一般性管理工作，如通讯录中记录的增加、修改、查找、删除、输出等功能。每个记录包含姓名、电话号码、住址等个人基本信息。9、简单的职工管理系统问题描述：对单位的职工进行管理，包括插入、删除、查找、排序等功能。职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。10、学生成绩统计、排序的实现问题描述：在
10、学生成绩管理中，经常会遇到求平均成绩，统计不及格学生成绩，统计优秀学生人数，以及按成绩对学生进行排名等。现假设有某个班级的若干名学生，每个学生都考试完成了4 门课程，试对所有学生的成绩完成以下工作：（1）求每门课程的平均成绩。（2）输出所有有不及格课程的学生的学号、姓名、全部课程的成绩、平均成绩。（3）输出所有平均分在90 分以上（含90 分）的学生学号、姓名。（4）对 4 门课程中的任何一门，可随意抽取1 门按学生成绩进行排序11、表达式计算问题描述：我们对表达式做如下简化：（1）假定所有运算分量都是整数；（2）所有运算符都是整数的二元操作，且都用一个字符表示。利用栈实现表达式求值方法。12
11、、工程造价最小问题问题描述：如果以无向网表示n个城市之间的交通网络建设规划，顶点表示城市，边上的权表示该线路的造价，试设计一个方案，使这个交通网的总造价最小。13、旅游导游系统问题问题描述：假设一个旅游景区由n 个不同景点组成（有向网），并用带权邻接矩阵表示，权值表示两个景点间的步行时间，试编写程序求任意两个景点间的最短步行时间。14、校园导游咨询（为来访的客人提供各种信息服务）问题描述：设计中南大学校园平面图，有三个校区和三所附属医院，在这些校区和医院内选 10 个以上的建筑物、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信
12、息。（1）为来访客人提供图中任意地名相关信息的查询。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -（2）为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。15、迷宫问题问题描述：从迷宫的入口开始寻找一条到出口的路径。要求显示迷宫的布局，及找到的路径（最好显示寻找路径的过程）。走到某一步后，假定往下有四个方向的可能，即上、下、左、右四个方向。16、最短路径迷宫问题问题描述：从迷宫的入口开始寻找一条到出口的最短路径。要求显示迷宫的布局，及找到的路径（最
13、好显示寻找路径的过程）。走到某一步后，假定往下有四个方向的可能，即上、下、左、右四个方向。17、变形的约瑟夫问题。问题描述：设有 n 个人围坐圆桌周围。从某个位置上的人开始报数，报到 m的人便出列，下一个人（第m 1 个人）又从1 报起，报到m的人便是第二个出列的人。照此重复下去，直到最后一个人出列为止。编写程序求出出列顺序，要求使用线性表的顺序存储结构。18、运动会分数统计。问题描述：某学校开运动会，共有m 个班参加，比赛设有n 个男子项目和L 个女子项目。假设项目编号为1n，n1n L，并且假设编号为偶数的项目取前5 名，得分顺序为 7，5，3，2，1，编号为奇数的项目取前3 名，得分顺序
14、为5，3，2。请编写出一个统计程序以产生：各班成绩单（包括各班所得的各项成绩的项目号，名次，姓名和得分）；团体总分报表（包括班级，男团总分，女团总分和团体总分）；可假设 m20，n15，L10,姓名长度不超过20 个字符。每个项目结束时，将其编号、类型符（区分取前5 名还是取前3 名）输入，并按名次输入运动员的姓名、班级、成绩。19、停车场管理。问题描述：设停车场内只有一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按其到达时间的先后顺序，依次由北向南排队（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车辆内停满n 辆汽车，则后来的汽车只能在门外的便道等候。
15、一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后开入的车辆必须退出车场让路。待该辆车开出大门后，退出的车辆再按原次序进入车场。离开停车场的每辆车必须按它停留的时间交纳费用。试为停车场编制按上述要求管理的模拟程序。20、模拟旅馆管理系统的一个子功能床位分配和回收。问题描述：某旅馆有n 个等级的房间；第i 等级有 a1 个房间；每个房间有b1 个床位（1in）。旅馆管理系统提供如下服务：（1）为单身旅客分配床位。根据旅客性别要求（所需要房间等级），进行分配，若分配成功，输出旅客姓名、性别、房间等级、房间号码；分配失败时，若所有等级均无空位，则打印“客满”，若旅客需要
16、的等级无空床位，但其他等级有床位，则打印“是否愿意更改等级”的询问。若旅客愿意更改，则重新输入有关信息，再进行分配；否则，分配工作结束。（2）当单身旅客离店时回收床位。根据旅客提供情况（房间等级、房间号码、床位号码）进行回收。21、排序综合问题描述：利用随机函数产生N 个随机整数（20000 以上），对这些数进行多种方法进行排序。要求：（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法
17、的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。22、图遍历的演示。问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的，试编一个程序，演示在连通图的无向图上行遍全部结点的操作。23、最短路径。问题描述：试设计一个程序，求图中一个源点到其他各顶点的最短路径。要求：（1）用邻接表表示图。（2）按长度非递减次序打印输出最短路径的长度及相应的路径。24、教学计划编制问题问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门
18、课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占 3 位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。（4）测试数据：学期总数：6；学分上限：10；该专业共开设12 门课，课程号从C01 到 C12，学分顺序为2,3,4,3,2,3
19、,4,4,7,5,2,3。先修关系如下：课程编号课程名称先决条件C1 程序设计基础无C2 离散数学C1 C3 数据结构C1，C2 C4 汇编语言C1 C5 语言的设计和分析C3，C4 C6 计算机原理C11 C7 编译原理C5，C3 C8 操作系统C3，C6 C9 高等数学无C10 线性代数C9 C11 普通物理C9 C12 数值分析C9，C10，C1（5）实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。25、哈希表设计。问题描述：针对自己的班集体中的“人名”设计一个哈希表，假设人名
20、为中国姓名的汉名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -语拼音形式。待填入哈希表的人名共有30 个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。使得平均查找长度不超过上限，完成相应的建表和查表程序。26、文章编辑问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80 个字符，共N 行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据
21、的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分 4 行输出 全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；27、拓扑排序问题问题描述：采用适当的存储结构，实现有向网的存储，建立，输入，显示，以及实现对有向无环图的拓扑有序序列的输出。28、农夫过河问题问题描述：农夫要带狼、羊、白菜过河,但船每次只能容纳农夫和一样东西,如果农夫不在，狼会吃羊，羊会吃白菜，但是狼不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河呢？29、一元多项式简单计算问题描述：输入并建立多项式；输出多项式；两个多项式相加减、相乘，建立并输出多项式。30、二叉树的前序、中序、后序遍历算法问题描述：建立一棵以二叉链表为存储结构的二叉树，试编写按非递归算法进行前序、中序、后序遍历。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -