数据结构课程方案

1、第一章课程设计的步骤和报告规范课程设计的步骤：一、问题分析和任务定义在设计之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什 么？对所需完成的任务作出明确的回答。二、系统设计系统设计分为逻辑设计和详细设计两步。逻辑设计指的是，对问题描述中的操作对象 定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义软件模块结构图； 详细设计则为定义相应的存储结构，并写出各函数模块的伪码算法。三、编码实现和调试四、总结和整理课程设计报告课程设计报告规范：课程设计报告的开头应给出题目、专业、班级、学号、姓名、指导老师和完成日期，并包 括以下七个内容：一、问题描述二、需求分析：以无歧义

2、的陈述说明程序设计的任务，强调的是程序要做什么？同时明确 规定：输入的形式和输出值的范围；输出的形式；程序所能够达到的功能；测试数据：包 括正确的输入及其输出结果和含有错误的输入及其输出结果。三、概要设计：在此说明每个部分的算法设计说明 可以是描述算法的流程图），每个程 序中使用的存储结构设计说明 如果指定存储结构请写出该存储结构的定义。四、软件模块结构图五、详细设计：每部分模块的设计，含数据结构的设计，算法的描述 流程图或PDL）。各个算法实现的源程序，对每个题目要有相应的源程序 可以是一组源程序，每个功能模 块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的 重

3、点变量，重点功能部分要加上清晰的程序注释。六、程序流程图七、源程序八、调试分析：测试数据、测试过程、测试结果及评价九、测试数据与实验结果十、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤十一、本章小结：总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过 程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数 据结构课程的认识等内容课程设计要求：1、学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时 主动通过各种方式与教师联系沟通。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、哈夫曼树在通信编码中的应用问题描述：设一份电文中有不同出现频率的字符，为了提高电文的输入和翻译效率， 必须有一套简短而又不会产生歧义的字符代码。试根据哈夫曼算法，对电文中的不同字符，构造出一棵哈夫曼树，对每个字符进行编码。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、工程造价最小问题问题描述：如果以无向网表示n个城市之间的交通网络建设规划，顶点表示城市，边 上的权表示该线路的造价，试

11、设计一个方案，使这个交通网的总造价最小。13、旅游导游系统问题问题描述：假设一个旅游景区由n个不同景点组成有向网），并用带权邻接矩阵表 示，权值表示两个景点间的步行时间，试编写程序求任意两个景点间的最短步行时间。14、校园导游咨询 为来访的客人提供各种信息服务）问题描述：设计中南大学校园平面图，有三个校区和三所附属医院，在这些校区和医 院内选10个以上的建筑物、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地 名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。1）为来访客人提供图中任意地名相关信息的查询。2）为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短

12、路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向 网。顶点和边均含有相关信息。15、迷宫问题问题描述：从迷宫的入口开始寻找一条到出口的路径。要求显示迷宫的布局，及找到 的路径 最好显示寻找路径的过程）。走到某一步后，假定往下有四个方向的可能，即 上、下、左、右四个方向。16、最短路径迷宫问题问题描述：从迷宫的入口开始寻找一条到出口的最短路径。要求显示迷宫的布局，及 找到的路径 最好显示寻找路径的过程）。走到某一步后，假定往下有四个方向的可能， 即上、下、左、右四个方向。17、变形的约瑟夫问题。问题描述：设有n个人围坐圆桌周围。从某个位置上的人开始报数，报到m的人便

13、出 列，下一个人第m+1个人）又从1报起，报到m的人便是第二个出列的人。照此重复下 去，直到最后一个人出列为止。编写程序求出出列顺序，要求使用线性表的顺序存储结 构。18、运动会分数统计。问题描述：某学校开运动会，共有m个班参加，比赛设有n个男子工程和L个女子工 程。假设工程编号为1n，n+1n+L，并且假设编号为偶数的工程取前5名，得分顺序 为7，5，3，2，1，编号为奇数的工程取前3名，得分顺序为5，3，2。请编写出一个统计 程序以产生：各班成绩单 包括各班所得的各项成绩的工程号，名次，姓名和得分）；团 体总分报表 包括班级，男团总分，女团总分和团体总分）；可假设mW20，nW15, LW

14、10，姓名长度不超过20个字符。每个工程结束时，将其 编号、类型符区分取前5名还是取前3名）输入，并按名次输入运动员的姓名、班级、成 绩。19、停车场管理。问题描述：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽 车进出。汽车在停车场内按其到达时间的先后顺序，依次由北向南排队 大门在最南端， 最先到达的第一辆车停放在车场的最北端），若车辆内停满n辆汽车，则后来的汽车只能 在门外的便道等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆 车要离开时，在它之后开入的车辆必须退出车场让路。待该辆车开出大门后，退出的车辆 再按原次序进入车场。离开停车场的每辆车必须按它停

15、留的时间交纳费用。试为停车场编 制按上述要求管理的模拟程序。20、模拟旅馆管理系统的一个子功能一床位分配和回收。问题描述：某旅馆有n个等级的房间；第i等级有al个房间；每个房间有bl个床位 1WiWn）。旅馆管理系统提供如下服务：1）为单身旅客分配床位。根据旅客性别要求所需要房间等级），进行分配，若 分配成功，输出旅客姓名、性别、房间等级、房间号码；分配失败时，若所有等级均无空 位，则打印“客满”，若旅客需要的等级无空床位，但其他等级有床位，则打印“是否愿 意更改等级”的询问。若旅客愿意更改，则重新输入有关信息，再进行分配；否则，分配 工作结束。2）当单身旅客离店时回收床位。根据旅客提供情况房

16、间等级、房间号码、床位 号码）进行回收。21、排序综合问题描述：利用随机函数产生N个随机整数20000以上），对这些数进行多种方法 进行排序。要求：1）至少采用三种方法实现上述问题求解提示，可采用的方法有插入排序、希尔排序、 起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的 文件中。2）统计每一种排序方法的性能以上机运行程序所花费的时间为准进行对比），找出其 中两种较快的方法。22、图遍历的演示。问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的，试编一个程序， 演示在连通图的无向图上行遍全部结点的操作。23、最短路径。问题描述：试设计一个程序，求图中一个

17、源点到其他各顶点的最短路径。要求： 1）用邻接表表示图。2）按长度非递减次序打印输出最短路径的长度及相应的路径。24、教案计划编制问题问题描述：大学的每个专业都要制定教案计划。假设任何专业都有固定的学习年限， 每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定 的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的， 可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教案 计划编制程序。1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数 字串、学分和直接先修课的课程号。2）允许用户指定下列两

18、种编排策略之一：一是使学生在各学期中的学习负担尽量均匀； 二是使课程尽可能地集中在前几个学期中。3）若根据给定的条件问题无解，则报告适当的信息；否则将教案计划输出到用户指定的 文件中。计划的表格格式自行设计。4）测试数据：学期总数：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，C15）实现提示可设学期总数不超过12,课程总数不超过100。如果输入的先修课程号不在该专业开设的 课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。25、哈希表设计。问题描述：针对自己的班集体中的“人名”设计一个哈希表，假设人名为中国姓名的 汉语拼音形式。待填入哈希表的人名共有30个，取平