2012数据结构课程设计题目

1、数据结构课程设计任务书学期：12-9- 班级： 计算机 10一、设计目的数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强 上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学 会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计 技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等 方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比 较系统和严格的训练。2、学生必须仔细研读数

2、据结构课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独 立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在三周时间内独立完成，学生要发挥自主学习的能力，充分利用时间， 安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题选题说明：前面 6 个为必做题(全做可达 60 分)，后面题目越多难度越大，根据实际选做题目的难度和数 量以及实现程序的完善性可以适当加减分；同学们在选题时，要结合个人实际情况，确保及格，力争多做。1、集合的并、交和差运算任务：编制一个能演示执行集合的并、交和差

3、运算的程序。要求:(1) 集合的元素限定为小写字母字符 a.z 。演示程序以用户和计算机的对话方式执行。实现提示:以链表表示集合。选作内容:集合的元素判定和子集判定运算。(2) 求集合的补集。集合的混合运算表达式求值。集合的元素类型推广到其他类型 ， 甚至任意类型。2、停车场管理 任务：设停车场是一个可以停放 n 辆汽车的狭长通道，且只 有一个大门可供汽车进出。汽车在停车场内按车辆到达时间 的先后顺序，依次有北向南排列(大门在最南端，最先到达 的第一车停放在车场的最北端)，若车场内已停满 n 辆车， 那么后来的车只能在门外的便道上等候，一旦有车开走，则 排在便道上的第一辆车即可开入；当停车场内

4、某辆车要离开 时，在它之后进入的车辆必须先退出车场为它让路，待该辆 车开出大门外，其他车辆再按原次序进入车场，每辆停放在 车场的车在它离开停车场时必须按它停留的时间长短交纳 费用。试为停车场编制按上述要求进行管理的模拟程序。要求：以栈模拟停车场，以队列模拟车场外的便道。每一组 输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车 牌照号码以及到达或离去的时刻。对每一组输入数据进行操 作后的输出信息为：若是车辆到达，则输出汽车在停车场内 或便道上的停车位置；若是车辆离去，则输出汽车在停车场 内停留的时间和应交纳的费用（在便道上停车不收费）。栈 以顺序存储结构实现，队列以链表结构实现。3、哈夫

5、曼码的编/译码系统【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但 是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对 于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站 写一个哈夫曼码的编/译码系统。【基本要求】一个完整的系统应具有以下功能：（1） 1:初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将 它存于文件 hfmTree 中。（2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则

6、从文件hfmTree中读入），对文件ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。（3）D:译码（Decoding）利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile 中。（4）P:打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5）T:打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在 终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】（1）利用下面

7、这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为 0.25，0.29， 0.07， 0.08， 0.14， 0.23， 0.03， 0.11，试设计哈夫曼编码。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码： “THISPROGRAM IS MY FAVORITE” 。字符 空格 A B C D E F G H I J K L M频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度576315148 518023818116 1【实现提示】编码结果以文本方式存储在文件CodeFile中。用

8、户界面可以设计为“菜单”方式：显示上述功能符号，再加上Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了 “Q”为止。在程序的一次执行过程中，第一次执行I，D或E命令之后，哈夫曼树已经在内存了，不必再读入。 每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。4、校园导游咨询 任务：设计一个校园导游程序，为来访的客人提供各种信息 查询服务。要求：设计学校的校园平面图，所含景点不少于 10 个，以图 中顶点表示校内各景点，存放景点名称、代号、简介等信息； 以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询

9、。为来访客人提供景点的问路查询，即已知一个景点， 查询到某景点之间的一条最短路径及长度。5、散列表的设计与实现任务：设计散列表实现电话号码查找系统。要求：设每个记录有下列数据项：用户名、电话号码、地址；从键盘输入各记录，以用户名(汉语拼音形式)为关键字建立散列表；采用一定的方法解决冲突；查找并显示给定电话号码的记录；选作内容：( 1) 系统功能的完善；设计不同的散列函数，比较冲突率；在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。6、排序综合利用随机函数产生N个随机整数(20000以上)，对这些数进行多种方法进行排序。要求：（1）至少采用三种方法（希尔排序、快速

10、排序、堆排序）实现上述问题求解；（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方 法；（3）统计每种算法所用的比较次数和交换次数，最后列表显示；（4）如果采用4 种或4 种以上的方法者，可适当加分。7、一元稀疏多项式的计算（*）任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出； 要求：以链式存储结构实现多项式。8、文章编辑（*）功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求:（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某

11、一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4 行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；9、迷宫求解（*）任务：以一个 m*n 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意 设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通

12、路以三元组（i,j,d）的形式输出， 其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。10、猴子选大王（*）任务：一堆猴子都有编号，编号是1，2，3 .m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始 数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大 王。要求：输入数据：输入 m,n。 m,n 为整数， nm输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现 此功能11、统计二叉树的结点个数 ： 建立二叉树，统计二叉树中度为2的结点个数和叶子结点个数（ 用递归或 非递归的方法都可以，先序、

13、中序或后序均可）（*）任务：要求能够输入树的各个结点；分别建立二叉树存储结构的输入函数、输出中度为 2的结点及个数的函数、 输出叶子结点及个数的函数；12 、线索二叉树（ *）任务：1建立中序线索二叉树，并且中序遍历；求中序线索二叉树上已知结点中序的前驱和后继；13、二叉排序树的基本操作（*）任务： 编写算法实现对依次输入的关键字序列建立二叉排序树，并能实现二叉排序树的查找、插入和删除 运算。14、运动会分数统计（*）任务：参加运动会有n个学校，学校编号为1.n。比赛分成m个男子项目，和w个女子项目。项目编 号为男子1 m，女子m+1 m+w。不同的项目取前五名或前三名积分；取前五名的积分分别

14、为：7、 5、3、2、1,前三名的积分分别为：5、3、2；哪些项目取前五名或前三名由学生自己设定。（m=20,n=20） 功能要求：（1）可以输入各个项目的前三名或前五名的成绩；（2）能统计各学校总分，（3）可以按学校编号、男女团体总分排序输出；（4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围： 20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称） 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运

15、动会的相关数据要存储在数据文件中。（数据 文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用 到的存储结构；相关数据结构（参考）：项目名次及分值 ：用二位数组 Scorem+w5;单项获奖情况登记表（项目编号，获奖名次、获奖学校，得分（自动得分） 学校获奖名次表（学校编号，团体总分，名次）测试数据：要求使用 1、全部合法数据； 2、整体非法数据； 3、局部非法数据。进行程序测试，以保证程 序的稳定。测试数据及测试结果请在上交的资料中写明；15、宿舍管理查询软件（ *） 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：（ 1）采用交互工作方

16、式（2）可以增加、删除、修改信息（3）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序（选择、快速排序、堆排序等任选 一种）（4）查询：a.按姓名查询；b.按学号查询;c按房号查询（5）打印任一查询结果（可以连续操作）16、最小生成树问题（*）【问题描述】若要在 n 个城市之间建设通信网络，只需要假设 n-1 条线路 即可。如何以最低的经济代价建设这个通信网，是一个网的 最小生成树问题。【系统要求】1利用克鲁斯卡尔算法求网的最小生成树。2利用普里姆算法求网的最小生成树。1利用克鲁斯卡尔算法求网的最小生成树。2利用普里姆算法求网的最小生成树。3要求输出各条边及它们的权值。【测试数据】

17、 由学生任意指定，但报告上要求写出多批数据测试结果。【实现提示】 通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30 个， 并为简单起见，网中边的权值设成小于 100 的整数，可利用 C 语言提供的随机函数产生。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩 阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。【选作内容】 利用堆排序实现选择权值最小的边。17、平衡二叉排序树的实现（*）【系统要求】（1）用二叉链表作存储结构，以回车（n）为输入结束标志，输入数列L,生成一棵平衡的二叉排序树T,

18、并 以直观的方式显示在终端上；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点，则删除该结点,并作中序遍历（执行操作2）；否则输出 信息“无x”，并将x插入该二叉排序树中。注意：插入、删除应保证二叉排序树的平衡性。18、商店存货管理系统（ *） 功能：建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。 分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括5 个种类的货物情况，能对商品信息进行扩充（追加），修改和删除 以及简单的排序；进一步要求：扩充商品数量，以及完成

19、系统查询功能。有兴趣的同学可以自己扩充系统功能。19 、售票处的服务系统（ *） 【问题描述】 航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使 上述业务可以借助计算机来完成。【系统要求】 设民航售票处的计算机系统可以为客户提供下列各项服务： 1 查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班 的日期和余票额；2 承办订票业务：根据客户提出的要求（日期、航班号、订票数额）查询该航班票额情况，若尚有余 额，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需要重新询问客户要求。若 需要，可预约登记排

20、队等候。3承办退票业务：根据客户提供的情况（日期、航班、退票数额），为客户办理退票手续，然后查询该航 班是否有人预约登记，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否 则依次询问其他排队预约的客户。【测试数据】 由学生任意指定，但报告上要求写出多批数据测试结果。【实现提示】 每条航线应包含的信息有：终点站名、航班号、飞机号、飞行日期（星期几）、乘员定额、余票额、已订票 的客户名单（包括姓名、订票额、座位号）和预约登记的客户名单（包括日期、姓名、所需票额）。这最后 两项显然是一个线性表和一个队列。为查找方便、已订票客户的线性表应按客户姓名有序，并且，为插入 和删除方便

21、，应以链表作存储结构。由于预约人数无法预料，队列也应以链表作存储结构。整个系统需汇 总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终 点站名有序。每条航线是这张表上的一个记录，包含上述八个域，其中乘员名单域为指向乘员名单链表的 头指针，预约登记客户名单域为分别指向队头和队尾的指针。【选做内容】 当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其它航线情况。 大家还可以充分发挥自己的想象力，增加你的系统的功能和其它服务项目。20、 中国道路交通网络信息查询系统（*）【问题描述】 出于不同的目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短， 出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询 程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1） 提供对城市信息进行编辑（如：添加或删除）的功能。（2） 城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除） 的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具；（4）旅途中耗费的总时间应该包括中转站的等候