2024年5月26日发(作者：)

数据结构课程设计选题

1、“吃金子”游戏。在地下某处藏有金子（g），有一个精灵（¤）寻找并获取金子。游戏

者通过输入四个方向键指挥精灵沿该方向移动去吃金子（每输入一次方向键只移动一步）；

金子是随机地、每隔一段时间出现在不同的位置，游戏者需在金子消失前到达才能获取它。

游戏者的成绩是看其在一定时间内获取的金子数量计算。如下图示。所需知识：数组、随

机数、键盘输入码的识别

---

¤

---------------------------

---------------------g---------

-------------------------------

-------------------------------

------g------------------------

----------------------g--------

--------------g----------------

（提示：用到两个库函数

①原型 int bioskey(int cmd)

所属头文件 bios.h

功能 返回键盘读取一个按键的ASCII值，两字节。

Cmd参数说明：参数cmd确定实际的操作，cmd取值为

0 返回下一个键盘输入的字符，如果低8位非0，则为ASCII码；如果低8位为0，

则高8位为扩展键盘代码—查PC ASCII表。

1 测试是否有可读的输入键，如果返回0，则表示没有；否则返回下一个输入键。键

还保存，供下次参数cmd为0的bioskey调用返回。

2 请求当前移位(Shift)状态

…

②原型 void gotoxy(int x,y)

所属头文件 conio.h

功能 将光标移动到(x,y)坐标处。屏幕的坐标系左上角为(0,0)。）

2、五子棋游戏。游戏者A、B对奕五子棋（规则略），百子用W、黑子用B表示，在一个

n*n的棋盘上对奕，棋盘布局及屏幕如下图示例。所需知

识：二维数组。

123456789ABCDEFGHIJKLMNO

2 WBW

3 BWWB

4 WBB

Player A:X- Y- Player B:X- Y-

3、有若干生产者和消费者，生产者负责生产商品、每生产处一个商品就放入一个环形缓

冲区中的空闲缓冲区中供消费者取商品消费，并检查是否有消费者等待取商品，若有就唤

醒他；如果没有空闲的缓冲区则排入等待队列等待消费者取走商品后空出缓冲区。同样，

消费者到环形缓冲区中找一个存有商品的缓冲区取商品，如果所有缓冲区均空（无商品可

供消费）则排入消费者队列等待，如果有商品可取、取出商品后查看生产者队列是否有等

待的生产者并唤醒他。环形缓冲区如下图所示。所需知识：环形队列、链队列。

4、在网吧管理中，需要在每个客户用时（下机）到达前5分钟提醒客户。由于当前上机

的用户数目不确定、每个用户的下机时间不同，所以需要采用链表结构的间隔时钟进行管

理。链表钟头节点中记录的时间值是相对于当前时间还需经过的时间、而后继节点中记录

的时间值是相对于其前趋节点的终止时间还需经过的时间。对新开机用户将其加入链尾；

系统设置一个时钟中断，时钟中断处理程序总是从头节点开始检查需要发布提醒信息的用

户（节点）提醒之并将其删除。所需知识：链表。

5、老鼠走迷宫。有一个n*n格的迷宫，有些格子是墙不能通过、而另一些是通道可以通

行。整个迷宫有一个入口和一个出口，四周也是墙。老鼠从入口进入顺可以通行的通道前

进，当遇到无法通行的墙时就需要尝试另一方向前进、„„直到所有方向（除了进入得方

向）尝试完还不能前行，就得后退再寻找出路。所需知识：数组、回溯程序设计。提示：

用数组Maze[n][n]表示迷宫，标志数组mark[][]用来记录已走过的位置，还要能对下一步前

进方向计算出下已位置等。见下图示（1表示墙、0表示通道）。

入口--0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1

1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1

1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1

1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1

1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1

1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 1

1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1

1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1

1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1

1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1

若存在到达出口的通路则输出之，否则输出“无解”。

6、设有一算术表达式，参与运算的数据均为1位数字、并且只使用加、减、乘、除四则

运算和圆括号，编程实现该表达式求值计算。所用知识：栈和字符串。

提示：教材上有该题的算法，需具体实现。也可以参考其他方法。

7、将n个名字（每个名字步超过10个字符--可英文单词表示）建立成一个单链表，节点

中包含名字、原（输入时的）序号、指向下一个节点的指针。然后将这些名字按字典顺序

排序。要求：

（1） 将原名单按行输出：名字、序号

（2） 按排序后的名单顺序输出，包括：名字、原序号。

所用知识：链表。

思考：你所用的排序算法对于链表来说，性能如何？你认为哪个算法更适合链表排序？

8、电脑摇奖。电视台常从成千上万的电话号码中摇出获奖者，设计一种存放这些电话号

码的数据结构，并设计两种或两种以上的算法对其摇奖，要求每次能随机选择若干个号码

（显示之）、最后停在中奖的号码上；要求被选择的号码与号码存放的位置无关、分布均

匀，使摇奖算法做到公平、每个号码的获奖机会均等。所需知识：表、查找。