C/C++《数据结构课程设计》题目[2023-07-01]

《数据结构课程设计》题目

一、【大数四则运算】——线性表

[习题描述]
设计—个实现任意长的整数进行四则运算和幂次运算的演示程序。
[基本要求]
利用双向循环链表实现大数的存储，每个结点含一个整型变量。
[实现提示]
实现原理：任何一个数都可以表示成指数形式，如下所示：
N=nEe (0=<n的绝对值<=1,e为10的指数幂)
例如100可以表示成1E2,1001可以表示成1.01E3

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

二、【银行业务模拟】——队列、栈

[问题描述]
客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果居于第一种，且申请额超出银行现存资金总额顺得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查相处理(如果可能)第二个队列中的客广，对能满足的申请者予以满足，不能满足者重新排列第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止被盗(因为此时已不可能还有能满足者)转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有存户立即离开银行。
写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平
均时间。
[测试数据]
一天营业开始时银行拥有的款额为10000(元)．营业时间为600(分钟)。其他模拟参量
自定。注意测定两种极端的情况：一是两个到达事件之间的间隔时间很短，而客户的交易时
间很长，另一个恰好相反，设置两个到达事件的间隔时间很长，而客户的交易时间很短。
[实现提示]
事件有两类；到达银行和离开银行。韧始时银行现存资金总额为total。开始营业后的第—个事件是客户到达，营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间相距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类相第二类业务。变量total、closetime以及上述两个随机量的上下界均文互地从终端读入，作为模拟参数。
两个队列和一个事件表均要用动态存储结构实现。注意弄清应该在什么条件下设置离开事件，以及第二个队列甩怎样的存储结构实现时可以获得较高的效率。注意：事件表是按
时间顺序有序的。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

三、【航空订票系统】——队列、栈

[问题描述]：
航空客运订票的业务活动包括：查询航线、客票预订和办理退票等运订票系统，以使上述业务可以借助计算机来完成。
[基本要求]
(1)每条航线所涉及的够息有：终点站名、航班号、KVL号、6行周日(星期几)、乘员定
额、众票量、已订票的客户名单(包括姓名、订票量、舱位等级1，2或3)以及等候替补的客户名单(包括姓名、所需票层)；
(2)作为示意系统，全部数据可以只放在内存中；
(3)系统能实现的操作和功能如下：
①查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额。
②承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续．输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；
③承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询
该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求．则为他
力、理订票手续，否则依次询问其它排队候补的客户。

[实现提示]
两个客户名单可分别由线性表和队列实现。为查找方便．已订票客户的线性表应按客户
姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线约情况登录在一张线性表上，由于航线基本不变．可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的—个记录，包含上述8个域，其中乘员名单域为指向乘员名单链表的头指针，等侯替补的客户名单域为分别指向队头和队尾的指针。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

四、【电梯模拟】——队列、栈

[问题描述]
设计一个电梯模拟系统。这是一个离散的模拟程序，因为电梯系统是乘客和电梯等“活
动体”构成的集合，虽然它们彼此交互作用，但它们的行为是基本独立的。在离散的模拟中，
以模拟时钟决定每个活动体的动作发生的时刻和顺序，系统在某个模拟瞬间处理有待完成
的各种事情，然后把模拟时钟推进到某个动作预定要发生的下一个时刻。
[基本要求]
(1)模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层
由下至上依次称为地下层、第一层、第二层、第三层和第四层，其中第一层是大楼的进出层，
即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。
(2)乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一
旦等候电梯时间过长，他将放弃。
(3)模拟时钟从o开始．时间单位为o．1秒。人和电梯的各种动作均要耗费一定的时间
单位(简记为t)，比如：
有人进出时，电梯每隔40t测试一次，若无人进出，则关门；
关门和开门各需要20t；
每个人进出电梯均需要25t，
如果电梯在某层静止时间超过300t，则驶回1层候命。
(4)按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

五、【程序分析】——串

[问题描述]
读入一个C程序，统计程序中代码、注释和空行的行数以及过程(函数)的个数和
平均行数，并利用统计信息分析评价该程序的风格。
[基本要求]
(1)把C程序文件作为TEXT文件读入源程序；
(2)边读入程序，边识别统计代码行、注释行相空行，同时还要识别过程和函数的开始
和结束，以便统计其个数和平均行数。
(3)程序的风格评价分为代码、注释和空行3个方面。每个方面分为A、B、C和D 4个等级，等级的划分标准是：

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

六、【全国交通咨询模拟】——图

[问题描述]
出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的
时间尽可能短，G门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编
制一个全国城市的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。
[基本要求]
(1)提供对城市信息进行编辑(如：添加或删除)的功能。
(2)城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑、
增设或删除)的功能。
(3)提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。
(4)旅途中耗费的总时间应该包括中转站的等候时间。
(5)咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则
和交通工具，输出信息为：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并
详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。
[实现提示]
(1)对全国城市交通图和列车时刻表及飞机航班表的编辑，应该提供文件形式输入相
键盘输入两种方式。飞机航班表的信息应包括；起始站的出发时间、终点站的到达时间和票
价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：基于教科书7．6节图7．35
的交通图，对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出
发时间、到达时间及票价等信息。
(2)以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，还应包括
交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

七、【哈希表设计】——查找

[问题描述]
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表，使得平均查找长度不
超过R，完成相应的建表和查表程序。
[基本要求]
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找
长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。
[测试数据]
取读者周围较熟悉的30个人的姓名。
[实现提示]
如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。人名的K度均不超过19个字符(最长的人名如：庄双双(zhang shuangshuang)。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

八、【图书管理系统】——二叉树

[问题描述]
图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。
[基本要求]
(1)每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等5项。
(2)作为演示系统，不必使用文件，全部数据可以都在内存存放。但是由于上述4项基
本业务活动都是通过书号(即关键字)进行的，所以要用B树)对书号建立索引，以
获得高效率。
(3)系统应实现的操作及其功能定义如下：
1)采编入库：新购入一种书，经分类和确定书号之后登记到图书账目中去
在帐中已有，则只将总库存量增加。
2)清除库存：某种书已无保留价值，将它从图书账目中注销。
3)借阅：如果一种书的现存量大于军，则借出一本，登记借阅者的图书证号和归还期
限。
4) 归还：注销对借阅者的登记，改变该书的现存量。
5)显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。下列B树的打印格式如下所示：

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

九、【成语接龙小游戏】——查找

[问题描述]
编程模拟成语接龙游戏。玩家输入一个成语，程序则能输出一个成语，重复上述过程直到一方无法接龙为止。成语接龙游戏规则是程序输出的成语中的第一个汉字要与玩家输入的成语中的最后一个汉字相同，接着玩家继续输入的成语要保证其中的第一个汉字与前面程序输出的成语中的最后一个汉字相同，如此重复，直到玩家不能继续输入正确的成语或程序不能输出正确的成语，则游戏结束。
[基本要求]
（1）分析成语接龙游戏中的关键要素及其操作特性，选择恰当的数据存储结构。
（2）抽象出关键操作模块，并给出其接口描述。
（3）输入输出说明如下。
① 程序可以从磁盘文件中读取成语，构造一个成语库；
② 在游戏过程中要求输入的内容为四字汉字组成的成语，即字符串长度不超过4个汉字，根据玩家输人的成语的第一个汉字，程序从构造的成语库中检索出对应的接龙成语并输出。
③ 如果玩家输入的字符串不符合四字成语的要求，则输出"玩家输入的不是成语"。
④ 如果玩家无法完成接龙，输入“玩家无法接龙”，即结束游戏。
⑤ 如果程序无法完成接龙，输出“程序无法接龙”，即结束游戏。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

十、【动态表的查找操作】——查找

[问题描述]
（1）创建一棵二叉排序树，并在此二叉排序树上实现插入和查找操作。
（2）创建一棵二叉平衡树，并在此二叉平衡树上实现插入、旋转和查找操作。
（3）设计菜单，使用户可通过菜单形式重复选择上述的功能以完成多次操作。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

十一、【新高考位次模拟计算】——排序

[问题描述]
新高考（相对传统文综、理综划分的旧高考而言）位次是指考生成绩和考生人数总和后的综合排序，是填报志愿的参考因素之一。位次并不是指名次，相同分数的考生名次相同，但位次不同。编程实现新高考位次模拟计算，并输出和保存计算结果。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111