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

如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。

八、全国铁路运输网最佳经由问题 1.问题描述

该题目采用我国铁路运输网的数据进行编程和运行验证。图如下(详细可在网上搜索《全国铁路局管辖线路示意图》)，可以不要这么详细，只要全国的主干线就可以了。

铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。

铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。

火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。

2.要求

（1） 查询某站所属的铁路线

（2） 要求具备新增铁路线的管理功能 （3） 要求具备新增车站的管理功能

（4） 针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。

并且要求能够显示出该最短路径的各个火车站的经由顺序

九、编制一个课程管理系统 [问题描述]

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 [基本要求]

（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

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

（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 [测试数据]

学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下： 课程编号 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 课程名称 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 先决条件 无 C1 C1，C2 C1 C3，C4 C11 C5，C3 C3，C6 无 C9 C9 C9，C10，C1 [实现提示] 可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。

十、简单的职工管理系统

[问题描述]

可以利用自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。对将班上同学看做职工进行管理，包括插入、删除、查找、排序等功能。

[基本要求]

假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。

职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。 （1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。 （2）删除一名职工：从职工管理文件中删除一名职工对象。

（3）查询：从职工管理文件中查询符合某些条件的职工。 （4）修改：检索某个职工对象，对其某些属性进行修改。 （5）排序：按某种需要对职工对象文件进行排序。 [测试数据]

读取熟悉的30个人的姓名。 [实现提示]

职工对象数一次读入内存，所有操作不经过内外存交换。

（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。 （2）对职工对象中的\姓名\按字典顺序进行排序。

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

十一、简单个人电话号码查询系统

1、问题描述

人们在日常生活中经常要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息(例如姓名等)进行快速查询。

2．基本要求

(1)在外存上，用文件保存电话号码信息；

(2)在内存中，设计数据结构存储电话号码信息； (3)提供查询功能：根据姓名实现快速查询；

(4)提供其他维护功能，例如插入、删除、修改等。 (5)至少要有1000个电话号码，每个号码至少包括手机、固定电话、电子邮件、姓名等。

3．实现提示

由于要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：

const int max=1000; struct TeleNumber {

string name; //姓名 string phoneNumber; string mobileNumber; string email; }Tele[max]

为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录须频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，须考虑该二叉排序树是否平衡，如何使之达到平衡。

十二、迷宫问题 1．问题描述

迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫

的惟一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，下图所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。

迷宫示意图，其中1代表有障碍，0代表无障碍，前进的方向有8个，分别是上、下、左、右、左上、左下、右上、右下

2．基本要求

(1)设计数据结构存储迷宫；

(2)设计存储结构保存从人口到出口的通路 (3)设计算法完成迷宫问题的求解； (4)分析算法的时间复杂度。

十三、算术表达式求值 1，问题描述

从键盘上输入算术表达式，包括括号，（1）判断表达式是否是正常表达式；（2）计算出一般表达式（类似如a*b+c/d-e）的值，（3）并能实现一元多项式相加。 2．基本要求

(1)程序对所输入的友达式作简单的判断，如表达式有错，能给出适当的提示 (2)能处理单目运算符：十和一。 （3）已知A(x)?a0?a1x?a2x2???anxn和B(x)?b0?b1x?a2x2???bmxm，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)+B(x)。要求设计存储结构表示一元多项式，设计算法实现一元多项式相加。

3．实现提示

可以使用中缀表达式，一般运算规则如下 (1)先乘方，再乘除，最后加减。 (2)同级运算从左算到有。 (3)先算括号内，再算括号外。

十四、遗传算法的模拟

(1) 问题描述

遗传算法是以达尔文生物进化论为基础，借鉴自然界中物种进化原理，依据优胜劣汰而达到优化的规律而创建的一种数学模型和算法。遗传算法（也可称为基因算法）的基本原理：优化问题的可能解被称为是个体（individuals），首先考虑可能解（个体）组成的集合，即群

体（population）；然后依据环境特征（优化问题特征）评定各个体的优劣（其适应度（fitness）来定义）；对适应度较差的个体进行淘汰，选取适应度好的个体（类比生物选择），在其上进行杂交，变异等操作形成新的群体；最后再进入下一轮遗传进化，上述过程不断迭代，直到群体满足了某条件，此时出现了满足要求的优化解。

对于计算机问题而言，一般要将问题的解进行编码，编码成二进制字符串，杂交和变异就在这些字符串上进行。

遗传算法可以很好解决很多的优化问题。 (2) 课程设计目的 体会遗传算法思想，能够设计并编写遗传算法的相关操作函数，并能够应用遗传算法求解具体问题。

(3) 基本要求

① 编写遗传算法的基本操作函数，包括选择，变异，交叉等。 ② 应用遗传算法实现求解如下函数的极值 f(x)=x*sin(10*π*x)+1.0 x∈[-1,2]

③ 结果精度要求在小数点后六位。 ④ 给出算法效率分析的实验结果。 (4) 实现提示

根据精度要求确定个体的二进制编码位数，同时要确定该编码和[-1,2]间数的换算规则，由于是求最大值的问题，所以适应度函数就可选为f(x)，值越大的个体适应度越好。关于交叉和变异的方法参阅相关资料。

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