数据结构课程设计详细要求

详细要求：

一、试设计一个航空客运订票系统。基本要求如下：

1、每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。 2、系统能实现的操作和功能如下： 1） 查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额； 2） 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。若需要，可登记排队候补； 3） 承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。

3、实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。由于预约人数无法预计，队列也应以链表作为存储结构。

二、简单编译器

功能：输入一页字符（包括文字、数学表达式等），程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。

存储结构使用线性表，分别用几个子函数实现相应的功能；

输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出\全部字母数\、\数字个数\、\空格个数\、\文章总字数\（3）输出删除某一字符串后的文章；

三、实现二叉树中所有结点左右子树的交换

要求：构造一颗20个节点的完全二叉树或者20个节点以上的满二叉树（同一个班的选择该题的同学必须选择构造不同的二叉树）

实现如下步骤：

（1）实现二叉树的构造过程，并打印出二叉树

（2）对该二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历；

（3）将该二叉树的所有左右子树进行交换，得到新的二叉树，并打印出该二叉树； （4）对新获得的二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历；

四、哈夫曼树在通信编码中的应用 [问题描述]

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。

[基本要求]

一个完整的系统应具有以下功能： （1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。

（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 [测试数据]

（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。

（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。 字符 频度 字符 频度 186 N 57 A 64 O 63 B 13 P 15 C 22 Q 1 D 32 R 48 E S 51 F T 80 G 15 U 23 H 47 V 8 I 57 W 18 J 1 X 1 K 5 Y 16 L 32 Z 1 M 20 103 21 [实现提示]

（1）文件CodeFile的基类型可以设为子界型bit = 0..1。

（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行Quit。请用户键入一个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。

（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

五、全国交通咨询模拟 242 哈尔滨 【测试数据】

乌鲁木齐 668

305 呼和浩特 长春 1892 1145

北京 137 704 沈阳 397 676 西宁 天津 216 511 349 674 兰州 大连 西安 郑州 徐州 842 534 651

成都 武汉 1100 967 409 上海 639 907 367 825

昆明 贵阳 株州 南昌 607 622 福州 672 675

255 柳州 广州 140 南宁 深圳

【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。

（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。

（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。

（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。 （2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。

六、模拟旅馆管理系统的一个功能——床位的分配与回收

⒈问题描述：

某旅馆有n个等级的房间，第i等级有

个房间，每个等级有

个床位（1≤I≤n）。试模

拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回

收床位（供下次分配）的算法。 ⒉基本要求 （1）输入数据

对房间信息进行初始化，包括房间的类别、数量以及房间和床位的计费标准； 分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级； 回收时，输入房间等级、房间号和床位号。 （2）输出数据

分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。

分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。 （3）结帐管理

在旅客离开时计算房费，并打印账单，账单格式自行设计，要求信息齐全、清晰。 （4）对旅客信息和房间信息以及收费标准采用文件的形式存储也可以在程序中初始化。 ⒊实现提示 （1）数据结构

主要采用顺序结构链接结构的线性表及堆栈。

每个房间用一个如下所示的具有五个字段的结点（房结点）表示： 性别 房间号 现有空床数 BTOP RLINK

其中，性别：0表示房间为空状态

1表示房间分配给女旅客 2表示房间分配给男旅客 现有空床数：数据在0～为

之间，其中

是第I等级一个房间的床位数，当现有空床数

时，表示房间为空；为0时，表示房间满。

RLINK：当房间空时，用作空房栈的连接；当房间不空时，指向下一个房结点。

BTOP：指向该房间的空床号栈栈顶。一个房间对应一个顺序表示的空床号栈。栈的容量为

，栈中存放空床号。分配时，从栈顶取出空床号，栈顶下移（BTOP=BTOP+1）；

回收时，栈顶上移（BTOP=BTOP-1），将回收的空床号填入栈顶。

每一个等级中的空房间构成一个空房栈；已住旅客的房间构成一个链栈（简称房链），其头结点结构如下：

可分配女床位总数 可分配男床位总数 其中：

：第I等级中房间总数

TTOP RLINK 第I等级中每个房间的床位数 可分配男、女床位的总数的初值等于

*

，因为开始时所有房间和床位既可以分配给

男旅客，也可以分配给女旅客。当在房链中分配一个床位给男（女）旅客，床位总数应减1；当从空房栈中取出一个房间作为男（女）旅客房间时，则可分配女（男）床位总数应减

，当回收一个男（女）床位时，则可分配男（女）床位总数应加1；当回收一

。

个男（女）空房至空房栈时，则可分配女（男）床位总数应加

TTOP：指向本级空房栈栈顶，当无空房间时，TTOP=^（NIL）。 RLINK：指向本级房链第一个顶点，当房链为空时，RLINK=^(NIL) 顺序表s=(

存放内容如下所示： 全店可分配女床总数 初始时，全店可分配男、女床总数相同，均为，在分配或回收时，对各等级可分配男（女）床位总数处理的同时也要对全店可分配男（女）床总数作相应处理，当全店可分配男（女）床总数等于零时，表示客满。

七、交通旅游图的最短路径问题

1．问题描述：

已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通

全店可分配女床总数 0 0 ^ ^ )，其中，

顺序存放第1～n等级房间的头结点；

过终端询问知道：

是否有公共汽车到达指定的目的地?

若有，告诉乘车路线。如需中途换车，应指示再那里换车 基本要求：

（1）自己提出一个公共汽车路线图，可以在网上搜索现实城市公交路线图（如长沙市的），至少要有7条公交线路，每条线路至少要有7个公共汽车站。

（2）数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。

（3）算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。 数据结构可以采用链接结构： structNODE {

char* stname;

struct NODE* link; };

struct NODE hdtp[MAX+1]； 数据结构也可以采用顺序结构： struct NODE{ int go,back; };

struct NODE a[max+1,max+1];

其中，a[I，j].go>0 表示第i条线路上，向站j 去方向的下一站号；a[i，j].back>0表示第i条线路上，站j回来的下一站号。若站j不在第i条线路上，a[i，j].go 和a[i，j].back 均为0。

（4）另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。

（5）对所采用的算法进行算法分析 2. 实现提示

假定顶点编号为1..n，数据结构采用连接结构。设置表头数组为head[1..n]，head[i]包含站i的名字和一指针，该指针指向i的所有邻接顶点组成的单链表。单链表中的每个结点包含3个域：一个站号域，两个指针域。一个指针指向i的下一个邻接顶点，另一个指针指向从i到该结点的所有线路号组成的链表。 struct LINENODE {

int lineno;

struct LINENODE* next; };

struct STNODE {

int stno;

struct LINENODE* Link1,*Link2; };

如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。

八、全国铁路运输网最佳经由问题 1.问题描述

该题目采用我国铁路运输网的数据进行编程和运行验证。图如下(详细可在网上搜索《全国铁路局管辖线路示意图》)，可以不要这么详细，只要全国的主干线就可以了。

铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。

铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。

火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。

2.要求

（1） 查询某站所属的铁路线

（2） 要求具备新增铁路线的管理功能 （3） 要求具备新增车站的管理功能

（4） 针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。

并且要求能够显示出该最短路径的各个火车站的经由顺序

九、编制一个课程管理系统 [问题描述]

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 [基本要求]

（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 [测试数据]

学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下： 课程编号 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 课程名称 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 先决条件 无 C1 C1，C2 C1 C3，C4 C11 C5，C3 C3，C6 无 C9 C9 C9，C10，C1 [实现提示] 可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。

十、简单的职工管理系统

[问题描述]

可以利用自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。对将班上同学看做职工进行管理，包括插入、删除、查找、排序等功能。

[基本要求]

假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。

职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。 （1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。 （2）删除一名职工：从职工管理文件中删除一名职工对象。

（3）查询：从职工管理文件中查询符合某些条件的职工。 （4）修改：检索某个职工对象，对其某些属性进行修改。 （5）排序：按某种需要对职工对象文件进行排序。 [测试数据]

读取熟悉的30个人的姓名。 [实现提示]

职工对象数一次读入内存，所有操作不经过内外存交换。

（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。 （2）对职工对象中的\姓名\按字典顺序进行排序。

（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。

十一、简单个人电话号码查询系统

1、问题描述

人们在日常生活中经常要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息(例如姓名等)进行快速查询。

2．基本要求

(1)在外存上，用文件保存电话号码信息；

(2)在内存中，设计数据结构存储电话号码信息； (3)提供查询功能：根据姓名实现快速查询；

(4)提供其他维护功能，例如插入、删除、修改等。 (5)至少要有1000个电话号码，每个号码至少包括手机、固定电话、电子邮件、姓名等。

3．实现提示

由于要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：

const int max=1000; struct TeleNumber {

string name; //姓名 string phoneNumber; string mobileNumber; string email; }Tele[max]

为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录须频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，须考虑该二叉排序树是否平衡，如何使之达到平衡。

十二、迷宫问题 1．问题描述

迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫

的惟一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，下图所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。

迷宫示意图，其中1代表有障碍，0代表无障碍，前进的方向有8个，分别是上、下、左、右、左上、左下、右上、右下

2．基本要求

(1)设计数据结构存储迷宫；

(2)设计存储结构保存从人口到出口的通路 (3)设计算法完成迷宫问题的求解； (4)分析算法的时间复杂度。

十三、算术表达式求值 1，问题描述

从键盘上输入算术表达式，包括括号，（1）判断表达式是否是正常表达式；（2）计算出一般表达式（类似如a*b+c/d-e）的值，（3）并能实现一元多项式相加。 2．基本要求

(1)程序对所输入的友达式作简单的判断，如表达式有错，能给出适当的提示 (2)能处理单目运算符：十和一。 （3）已知A(x)?a0?a1x?a2x2???anxn和B(x)?b0?b1x?a2x2???bmxm，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)+B(x)。要求设计存储结构表示一元多项式，设计算法实现一元多项式相加。

3．实现提示

可以使用中缀表达式，一般运算规则如下 (1)先乘方，再乘除，最后加减。 (2)同级运算从左算到有。 (3)先算括号内，再算括号外。

十四、遗传算法的模拟

(1) 问题描述

遗传算法是以达尔文生物进化论为基础，借鉴自然界中物种进化原理，依据优胜劣汰而达到优化的规律而创建的一种数学模型和算法。遗传算法（也可称为基因算法）的基本原理：优化问题的可能解被称为是个体（individuals），首先考虑可能解（个体）组成的集合，即群

体（population）；然后依据环境特征（优化问题特征）评定各个体的优劣（其适应度（fitness）来定义）；对适应度较差的个体进行淘汰，选取适应度好的个体（类比生物选择），在其上进行杂交，变异等操作形成新的群体；最后再进入下一轮遗传进化，上述过程不断迭代，直到群体满足了某条件，此时出现了满足要求的优化解。

对于计算机问题而言，一般要将问题的解进行编码，编码成二进制字符串，杂交和变异就在这些字符串上进行。

遗传算法可以很好解决很多的优化问题。 (2) 课程设计目的 体会遗传算法思想，能够设计并编写遗传算法的相关操作函数，并能够应用遗传算法求解具体问题。

(3) 基本要求

① 编写遗传算法的基本操作函数，包括选择，变异，交叉等。 ② 应用遗传算法实现求解如下函数的极值 f(x)=x*sin(10*π*x)+1.0 x∈[-1,2]

③ 结果精度要求在小数点后六位。 ④ 给出算法效率分析的实验结果。 (4) 实现提示

根据精度要求确定个体的二进制编码位数，同时要确定该编码和[-1,2]间数的换算规则，由于是求最大值的问题，所以适应度函数就可选为f(x)，值越大的个体适应度越好。关于交叉和变异的方法参阅相关资料。

体（population）；然后依据环境特征（优化问题特征）评定各个体的优劣（其适应度（fitness）来定义）；对适应度较差的个体进行淘汰，选取适应度好的个体（类比生物选择），在其上进行杂交，变异等操作形成新的群体；最后再进入下一轮遗传进化，上述过程不断迭代，直到群体满足了某条件，此时出现了满足要求的优化解。

对于计算机问题而言，一般要将问题的解进行编码，编码成二进制字符串，杂交和变异就在这些字符串上进行。

遗传算法可以很好解决很多的优化问题。 (2) 课程设计目的 体会遗传算法思想，能够设计并编写遗传算法的相关操作函数，并能够应用遗传算法求解具体问题。

(3) 基本要求

① 编写遗传算法的基本操作函数，包括选择，变异，交叉等。 ② 应用遗传算法实现求解如下函数的极值 f(x)=x*sin(10*π*x)+1.0 x∈[-1,2]

③ 结果精度要求在小数点后六位。 ④ 给出算法效率分析的实验结果。 (4) 实现提示

根据精度要求确定个体的二进制编码位数，同时要确定该编码和[-1,2]间数的换算规则，由于是求最大值的问题，所以适应度函数就可选为f(x)，值越大的个体适应度越好。关于交叉和变异的方法参阅相关资料。

本文来源：https://www.bwwdw.com/article/ne16.html