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

详细要求：

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

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; };

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课程设计详细要求在线全文阅读。