数据结构课程设计52290

1、数据结构课程设计课程设计时间：1014周周三下午及晚上一、课程设计的目的数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：n 了解并掌握数据结构与算法的设计方法，掌握数组、链表

2、、队列、堆栈、树等基本数据结构，具备初步的独立分析和设计能力；n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；n 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计的基本要求1、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。3、按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个

3、内容认真完成，其中包括：a）需求分析：对题目进行分析，将问题转换成计算机语言描述，选择合适的数据结构，明确每个模块的功能要求。b）概要设计在此说明每个部分的算法设计思想（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构，请写出该存储结构的定义）。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，时间和空间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如

4、何解决？），算法的改进设想等。 e）课程设计总结总结一般应包括：需求分析说明、功能模块和算法设计思想说明和程序调试报告。对所做课程设计程序算法优劣度的分析、是否可以改进算法，在哪些方面改进？课程设计过程的收获、在课程设计过程中对数据结构课程的认识等内容。4、课程设计提交内容： a) 每组的课程设计结果要进行检查和演示，程序源代码和文档文件等在课程设计结束后上交，作为考核内容的一部分。 b) 课程设计报告。可以结合3中的每个步骤对自己负责编写的部分重点描述。在电子文件中写明小组各成员具体分工，在PPT演示中明确说明。 所有内容打包成文件夹，文件夹内应包含：源代码、可执行文件、PPT、课程设计报告

5、等。三、上交作业及成绩评定1、上交要求 按照课程设计提交内容准备，其中课程设计报告以打印或者手写文稿的形式上交（打印版A4，正文部分小四或者五号字体，可参考论文写作要求格式），电子文档以小组为单位在课程结束后统一拷贝至各班学习委员处，最后由各班学习委员交至2503办公室。2、评分标准 根据完成任务的情况，各小组在第13周和第14周以PPT和源代码执行文件形式在机房进行系统演示，面向全体同学讲解。课程设计报告书的质量、演示情况和课程设计过程中的工作态度等按照30%、50%、20%加权综合打分。上机程序检查未通过者、最终无设计报告者或严重抄袭他人设计者，成绩为不及格。备注：l 每班分为68个小组，

6、每组4人，特殊情况可5人一组。自由分组，分组名单由各班学习委员统计确认后交给任课老师。l 每个题目每班最多只能有二个小组选做，评分时根据各题目难度确认难度系数，由得分和难度系数相乘得出最终分数。每组至少要完成二个题目。第一题为示例，讲解用，不可选。l 每小组之间题目及内容不得雷同，否则成绩最高为及格。四、课程设计内容：一、敢死队问题 （示例题，不可选）有M个敢死队员要炸掉敌人的一个碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，

7、且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 假设排长为1号，请你设计一个程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 二、设计一个航空客运定票系统。基本要求如下： 1.01、 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。2、 系统能实现的操作和功能如下：1） 查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行

8、，最近一天航班的日期和余票额；2） 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。若需要，可登记排队候补；3） 承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。3、 实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。由于预约人数无法

9、预计，队列也应以链表作为存储结构。三、校园导游咨询（为来访的客人提供各种信息服务）1.01、 基本要求：1） 参考校园设计平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2） 为来访客人提供图中任意景点相关信息的查询。3） 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。2、 实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。四、停车场管理问题 1.0 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场

10、内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场。每辆停放在车场的车在它不离开停车场时必须按它停留的时间长短交费。试为停车场编制按上述要求进行管理的模拟程序。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离开”信息，汽车牌照号码以及到达或离去的时

11、刻。与每一组输入数据信息相对应的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。（提示：需另设一个栈，临时停放为给要离去的汽车让路从停车场退出来的汽车，也用顺序存储结构实现。）测试数据设n，输入数据为：（，），（，），（，），（，），（，），（，），（，），（，）。其中：表示到达，表示离去，表示输入结束。 其中：（，）表示1号牌照车在5这个时刻到达，而（，）表示1号牌照车在15这个时刻离去。五、全国交通咨询模拟 1.1【问题描述】处于对不同目的的旅客对

12、交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。 （2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。 （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：

13、最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。徐州397乌鲁木齐哈尔滨长春沈阳天津郑州西安兰州成都上海昆明贵阳株州福州柳州广州深圳南宁189221611456681100967639907349676511242305704651622367409255607675140【测试数据】呼和浩特北京137674西宁大连534842武汉825南昌672【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据

14、交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。 （2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。六、编制一个求解迷宫通路的图形界面演示程序。 1.0 用矩阵MN表示一个迷宫，0和1分别表示通路和墙壁。试求出从入口点到达出口点的一条通路。七、按实现提示内容创建线索二叉树，完成后使用中序遍历将二叉树的内容输出。 1.1【实现提示】创建二叉树结点数据的策略有三个，如下：将第一个要创建的元素插入成为根节点。将元素值与结点值比较，

15、如果元素值大于结点值，将此元素送往结点的右儿子结点，如果右儿子结点不是空的，需要重复比较，否则创建结点将元素值插入。如果元素值小于结点值，将此元素送往结点的左儿子结点，如果左儿子结点不是空的，需要重复比较，否则创建结点将此元素值插入。例如：二叉树结点值输入的数据顺序是5，6，4，8，2，3，7，1，9。按照上述策略创建的二叉树，如下图所示：八、商店存货管理系统 1.0建立一个商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进

16、行扩充（追加），修改和删除以及简单的排序；3 进一步要求：扩充商品数量，以及完成系统查询功能。 1.1九、订票系统 1.1问题描述：通过此系统可以实现如下功能：1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，

17、订单要有编号。5）修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；十、个人帐簿管理系统设计 1.0个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。十一、编写一个五子棋的游戏程序。 1.2实现人与机对下的功能。要求：1、要有图形棋盘；2、设计输、赢判断规则函数；3、给出下棋过程（电脑能智能判断，中级难度以上）。十二、简单的职工管理系统 1.01.问

18、题描述对单位的职工进行管理，包括插入、删除、查找、排序等功能。2.要求职工对象包括工号、姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式存入职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。3.实现提示（1）职工对象数不必很多，由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的工号按顺序进行排序。（3）对排序后的职工对象进行查询、

19、增加、删除、修改等操作。十三、教学计划编制问题 1.2 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求 （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前

20、几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1实现提示可设学期总数不超过12，课程总数不超过1

21、00。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。十四、建通讯录 1.2【问题描述】设计散列表实现通讯录查找系统。【基本要求】(1) 设每个记录有下列数据项：电话号码、用户名、地址；(2) 从键盘输入各记录，分别以电话号码为关键字建立散列表；(3) 采用二次探测再散列法解决冲突；(4) 查找并显示给定电话号码的记录；(5) 通讯录信息文件保存；(6) 要求人机界面友好，使用图形化界面；【选做内容】(1) 系统功能的完善；(2) 设计不同的散列函数，比较冲突率；(3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查

22、找长度的变化。(4) 使用汉字显示。【实现提示】主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创建新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()

23、的功能：显示通讯录中的所有记录。Save()的功能：保存通讯录中的所有记录到指定文件中。Load()的功能：从指定文件中读取通讯录中的记录。十五、银行业务模拟： 1.1银行业务模拟问题描述：客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列的客户，对能满足的

24、申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。 十六、图书管理基本业务模拟 1.11) 书的登记内容包括书号、书名、著作者、现存量和库存量；2) 建立索引表（线性表）以提高查找效率；a) 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；b) 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；c) 归还：注销对借阅者的登记，改变该书的现存量。3）主要功能如下：输出形式：能按书号、书名、著作者查找库存的书籍信息 能按学生的借书证号显示学生信息和借阅信息 书籍入库 借书功能实现 还书功能实现十七、学生成绩管理系统 1.15现有学生成绩信息文件1（1.txt），内容如下姓名 学号 语文 数学 英语 张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56