数据结构课程设计指导书

指导书。信息工程学院计算机科学与技术专业。

2023年12月。

数据结构课程设计》指导书。

一、课程设计题目与要求。

根据课程设计题目规模，要求每个题目3人一组。分组规则如下：

按照学号顺序每3人编为一组（或者自由组合），一经确定不得随意调换，题目由各组选派代表抽签确定，设计题目不得更换。

选题一：教学计划编制问题（图的应用）（2—3人）

问题描述]大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。

每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

实现提示]1、输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。

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

3、若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的**格式可以自己设计。

4、可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。

选题二：电视大赛观众投票及排名系统（排序应用）（1人）

问题描述】1、在很多的电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。现在要求编写一程序模拟实现上述系统的功能。

2、【实现提示】

在本例中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依此存入顺序表单元中，观众通过按键进行投票，按’1’为1号选手投票，按’2’为2号选手投票，以此类推，以按’0’作为投票结束标志。投票结束后进行排序，在此采用希尔排序，然后为每个选手计算名次，得票相同的名次也相同，

1）存储类型的定义。

参赛选手信息存储类型的定义：

typedef struct node{

char name[8]; 选手姓名*/

int num; /选手编号*/

int score; /选手得分*/

int tax; /选手名次*/

node;问题描述】

以一个mxn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

任务要求】1) 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：

（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…

2) 编写递归形式的算法，求得迷宫中所有可能的通路。

3) 以方阵形式输出迷宫及其通路。

测试数据】迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。

题目17：（马的遍历问题）设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。

要求：依次输出所走过的各位置的坐标。（限选2-3人）

问题描述】将马随机放在国际象棋的8* 8棋盘bord[8ⅱ8]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。

任务要求】编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8* 8的方阵，输出之。

测试数据：由读者指定，可自行指定一个马的初始位置。

实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。

测试数据】自行设定，注意边界等特殊情况。

问题描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。

任务要求】假设算术表达式expression内可以含有变量（a～z）、常量（0～9）和二元运算符乘幂)）。实现以下操作：

1) readexpre(e)—以字符序列的形式输入语法正确的前缀表达式并构造表达式e。

2) writeexpre(e)—用带括弧的中缀表达式输出表达式e。

3) assign(v,c)—实现对变量v的赋值（v=c），变量的初值为0。

4) value(e)—对算术表达式e求值。

5) compoundexpr（p，e1，e2）--构造一个新的复合表达式（e1）p（e2）

测试数据】1) 分别输入0；a；-91；+a*bc；+*5^x2*8x；++3^x3*2^x2x6并输出。

2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。

选题六：航班信息的查询与检索（2人）

问题描述】

设计民航售票处的计算机系统可以为客户提供下列各项服务：

1.查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行、最近一天航班的日期和余票额；

2.承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况。

实现提示】1.对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

2.采用基数排序法对一组具有结构特点的飞机航班号进行排序。

3.利用二分查找法对排好序的航班记录按航班号实现快速排序。

4.每个航班记录包括八项，分别为：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等。

其中航班号一项的格式为：

k0k1k2k3k4k5

选题七：宿舍管理查询系统（1人）

1) 任务：为宿舍管理人员编写一个宿舍管理查询软件，程序设计要求：

a. 采用交互工作方式。

b. 建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(希尔、快速、堆排序等任选两种方法实现)

2) 查询菜单： (用二分查找实现以下操作)

a. 按姓名查询

b. 按学号查询

c. 按房号查询。

3) 打印任一查询结果（可以连续操作）

选题八：校园导航（1人）

设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

基本要求：1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。

2）为来访客人提供图中任意景点相关信息的查询。

3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。

实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。

选题九：职工管理系统（2人）

问题描述：对单位的职工进行管理，包括插入、删除、查找、排序等功能。

要求：职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、**等信息。

1）新增一名职工：将新增职工对象存入职工数据文件中。

2）删除一名职工：从职工数据文件中删除一名职工对象。

3）查询：从职工数据文件中查询符合某些条件的职工。

4）修改：检索某个职工对象，对其某些属性进行修改。

5）排序：按某种需要对职工对象文件进行排序（冒泡、选择、插入排序等任选两种方法实现）。

实现提示：职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。

1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。

2）对职工对象中的"姓名"按字典顺序进行排序。

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

选做内容：将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。

选题十：全国交通资讯系统（3人）

问题描述：设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：

1）时间最短。

2）费用最小。

3）中转次数最少。

需求分析：该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。

1）在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。

2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

3）程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。

附录：测试数据。

航班时刻表。

列车时刻表

数据结构课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

其他用户还读了