《数据结构课程设计》由会员分享，可在线阅读，更多相关《数据结构课程设计（7页珍藏版）》请在金锄头文库上搜索。
1、一、通讯录管理为了实现通讯录管理的几种操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。主控菜单设计要求1.菜单内容程序运行后，给出 6 个菜单项的内容和输人提示：1通讯录数据库的建立2按条件查询数据3插入新数据4按条件删除数据5显示数据0退出管理系统请选择 0-52设计要求使用数字 0-5 来选择菜单项，其他输入则不起作用。1通讯录数据库的建立：使用线性表结构，不能用数据库技术；2按条件查询：给出提示输入查询关键字，若存在则输出符合条件的数据，否则给出相应的信息；3插入新数据：若已存在则提示，否则插入；4按条件删除数据：给出提示输入要删除数据的关键字，若存
2、在则删除相应的数据，否则给出相应的信息；5显示数据：输出全部数据或按条件输出部分数据。二、八皇后问题在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。设计要求与分析八皇后问题是在 8x8 的国际象棋棋盘上，安放 8 个皇后，要求没有一个皇后能够“吃掉”任何其他一个
3、皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。显示八皇后在棋盘上分布的所有合法的格局。八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于 232 种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第 i 个皇后放置在第 i 行上。这样在放置第 i 个皇后时，只要考虑它与前 i 一 1 个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下：从第 1 行起逐行放置皇后，每放置一个皇后均需要依次对第 1，2，8 列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲
4、突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探，当 8 列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。三、文本文件单词的检索与计数要求：1) 具有图形菜单界面；2) 查找，替换（等长，不等长） ，插入（插串，文本块的插入） 、块移动（行块，列块移动） ，删除3) 可正确存盘、取盘；4) 正确显示总行数。四、交通咨询系统设计（最短路径问题）在交通网络非常发达、交通工具和交通方式不断更新的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣。对于这样
5、一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答旅客提出的各种问题。例如，一位旅客要从 A城到 B 城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点 A 到 B 所含边的数目最少的路径。我们只需要从顶点 A 出发对图作广度优先搜索，一旦遇到顶点 B 就终止。由此所得广度优先生成树上，从根顶点 A 到顶点 B 的路径就是中转次数最少的路径。路径上 A 与 B 之间的顶点就是路径的中转站数，但只是一类最简单的图的最短路径问题。设计要求及分
6、析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。该设计共分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。1.建立图的存储结构要实现设计要求，首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设 G(V, E)是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下定义的 n 阶方阵。wij,若（v i,vj）或E（G）Ai,jl =0 或，当不满足上述条件时一个图的邻接矩阵表示是唯一的。图的
7、邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有 n 个元素的一维数组来存储顶点信息，其中下标为 i 的元素存储顶点 vi 的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 5。最大顶点数typedef structVertexType vexsMVNum：顶点数组，类型假定为 char 型Adjmatrix arcsMVNumMVNum;邻接矩阵，假定为 in 七型MGraph；2.单源最短路径3.任意一对顶点间最短路径五、航班信息的查询与检索【问题描述】排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需
8、要先对数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班期、时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。因为航班号是字母数字混编的，例如 CZ3869，这种记录集合是一个适合于多关键字排序的例子。【设计要求】该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。对于本设计，先按关键字对航班记录进行排序，然后利用二分查找法对排好序的航班记录按关键字实现快速查找，注意，满足条件的记录可能有多条。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起
9、飞时间、到达时间、飞机型号以及票价等，假设航班信息表（8 条记录）如下表 8-1 所示。航班号 起点站 终点站 班 期 起飞时间 到达时间 机 型 票 价CA1544 合肥 北京 1，2，4，5 1055 1240 733 960MU5341 上海 广州 每 日 1420 1615 M90 1280CZ3869 重庆 深圳 2，4，6 0855 1035 733 1010MU3682 桂林 南京 2,3,4,6,7 2050 2215 M90 1380HU1836 上海 北京 每 日 0940 1120 738 1250CZ3528 成都 厦门 1,3,4,5,7 1510 1650 CRJ
10、1060MU4594 昆明 西安 1,3,5,6 1015 1140 328 1160SC7425 青岛 海口 1,3,6 1920 2120 DH4 1630其中航班号一项的格式为：C Z 3 8 6 9其中 CZ 是航空公司的别称，用两个大写字母表示，后 4 位为航班编号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。六、图书管理信息系统【问题描述】在许多应用处理方面，特别是在处理面向事务管理类型的问题时，例如财务管理、图书资料管理、人事档案管理等，都将涉及大量的数据处理。由于内存不适应于存储这类数量很大而且
11、保存期又较长的数据，因此一般是将它们存于外存设备中，我们把这种存放在外存中的数据结构称为文件。文件是多个性质相同的记录的集合。文件的数据量通常很大，它被放置在外存上。数据结构中所讨论的文件主要是数据库意义上的文件，而不是操作系统意义上的文件。操作系统中研究的文件是一维的无结构连续字符序列，而数据库中所研究的文件则是带有结构的记录集合，每个记录可由若干个数据项构成。记录是文件中存取数据的基本单位，数据项是文件可使用的最小单位。数据项有时也称为字段或属性，其中能够唯一标识一个记录的数据项称为主关键字项，主关键字项的值称为主关键字。【设计要求】图书信息表所表示的就是一个数据库文件。图书管理一般包括：
12、图书采编、图书编目、图书查询及图书流通（借、还书）等。要求设计一个图书管理信息系统，用计算机实现上述系统功能。具体设计要求：（1)建立一个图书信息数据库文件，输入若干种书的记录，建立一个以书号为主关键字的主索引数据库文件；建立以书名、作者及出版社作为次关键字的索引以及对应的索引链头文件，如图 1所示；记录号书号书名 指针 1 作者 指针 2 出版社 指针 3分类 藏书量借出数1 1021数据库 0 李小云0 人民邮电0 021 8 0 2 1014数据结构0 刘晓阳0 中国科学0 013 6 0 3 1106操作系统0 许海平0 人民邮电1 024 7 0 4 1108数据结构2 孙华英0 清
13、华大学0 013 5 0 5 1203程序设计0 李小云1 中国科学2 035 6 0 6 2105数据库 1 许海平3 清华大学4 021 6 0 7 1012数据结构4 李小云5 人民邮电3 013 5 0 8 0109程序设计5 刘晓阳2 清华大学6 035 7 0 (a)图书数据库文件书名 链头地址 长度数据库 6 2数据结构 7 3操作系统 3 1程序设计 8 2(b)书名索引链头文件 作者 链头地址 长度李小云 7 3刘晓阳 8 2许海平 6 2孙华英 4 1(c)作者索引链头文件出版社 链头指针 长度人民邮电 7 3中国科学 5 2清华大学 8 3 (d)出版社索引链头文件图 1 图书主文件及相关索引文件示例 （2）建立关于书号、书名、作者及出版社的图书查询；（3）实现图书的借还子系统，包括建立读者文件、借还文件、读者管理及图书借还等相关的处理。七 走迷宫【问题描述】用计算机解迷宫路径的程序，就是仿照人走迷宫而设计的，由于计算机解迷宫时
