序号

实验项目名称

学时

内容提要

实验类型

基础性

综合设计性

创新性

1

医务室模拟

18

[实验目的]

1、要求输出医生的总等待时间和病人的平均等待时间。

2、掌握队列等数据结构的实际应用。

[实验内容]

问题描述：假设只有一位医生，在一段时间内随机地来几位病人；假设病人到达的时间间隔为0~14分钟之间的某个随机值，每个病人所需处理时间为1~9分钟之间的某个随机值。试用队列结构进行模拟。

程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有一位病人到达，则这些病人应依次排队，等候就诊。

[实验方法及原理]

编写代码，上机调试。

√

2

景区旅游信息管理系统

18

[实验目的]

1.设计一个景区旅游信息管理系统，提高对图的创建、输出、最短路径算法和最小生成树构建算法的应用能力，掌握高级语言的编程方法。

2.全面提高学生的程序设计、开发能力。

[实验内容]

1.景区旅游信息管理系统中，首先通过遍历景点，给出一个入口景点。

2.可以设计景区的旅游景点，确定入口和出口景点。

3.建立导游线路图并遍历景点。

4.可以提供两个任意景点之间的最短路径及最短距离。

5.可以通过求最小生成树对景区进行建设和规划。

[实验方法及原理]

编写代码，上机调试。

√

3

哈夫曼编码

18

[实验目的]

1.设某编码系统共有n个字符，使用频率分别为{w1, w2, …, wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。

2.全面提高学生的程序设计、开发能力。

设计E-R图

[实验内容]

1.设计数据结构；

2.设计编码算法；

3.分析时间复杂度和空间复杂度。

[实验方法及原理]

编写代码，上机调试。

√

4

校园导游程序

18

[实验目的]

1.用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。

2.全面提高学生的程序设计、开发能力。

[实验内容]

1.查询各景点的相关信息；

2.查询图中任意两个景点间的最短路径。

3.查询图中任意两个景点间的所有路径。

4.增加、删除、更新有关景点和道路的信息。

[实验方法及原理]

编写代码，上机调试。

√

5

员工管理系统

18

[实验目的]

1. 每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。

2.全面提高学生的程序设计、开发能力。

[实验内容]

1.排序：按不同关键字，对所有员工的信息进行排序。

2.查询：按特定条件查找员工。

3.更新：按编号对某个员工的某项信息进行修改。

4.插入：加入新员工的信息。

5.删除：按编号删除已离职的员工的信息。

[实验方法及原理]

编写代码，上机调试。

√

6

表达式求值

18

[实验目的]

1.一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。

2.全面提高学生的程序设计、开发能力。

[实验内容]

1.从键盘读入一个合法的算术表达式，输出正确的结果。

2.显示输入序列和栈的变化过程。

[实验方法及原理]

编写代码，上机调试。

√

7

括号匹配的检验

18

[实验目的]

1.假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即CC或[（[ ] [ ]）]等为正确格式，[（]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：

[([][])]

12345678

　　当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，…… ，依次类推。可见这个处理过程正好和栈的特点相吻合。

2.全面提高学生的程序设计、开发能力。

[实验内容]

 设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中，若是右括号，则或者是和当前栈顶的括号相匹配，或者是不合法的情况，输出“此串括号匹配不合法”。在初始和结束时，栈应该是空的。

 输入#（[ ]（））#，结果“匹配”

 输入#[（ ）]#，结果“此串括号匹配不合法”

#为起始和结束标志。

[实验方法及原理]

编写代码，上机调试。

√

8

航班信息的查询与检索

18

[实验目的]

1．深刻理解排序的定义和各种排序方法的特点,并能灵活的应用；

2．掌握描述查找过程的判定树的构造方法。

[实验内容]

设计民航售票处的计算机系统可以为客户提供下列各项服务：1. 查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行、最近一天航班的日期和余票额；2. 承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况。

要求：

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

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

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

[实验方法及原理]

编写代码，上机调试。

√

9

停车场管理系统

18

[实验目的]

1．掌握栈和队列的建立。

2．掌握栈和队列的基本操作。

3．深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们。

4．加深对栈和队列的理解和认识

[实验内容]

1．以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。

2．每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。

3．对每一组输入数据进行操作后的输出信息为：若是车辆到达,则输出汽车在停车场或便道上的停车位置；若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费，功能可自己添加)

[实验方法及原理]

编写代码，上机调试。

√

10

餐厅自助叫号系统

18

[实验目的]

1、掌握线性表和队列的建立。

2、掌握线性表和队列的基本操作。

3、深入了解线性表和队列的特性,以便在解决实际问题中灵活运用它们。

4、加深对线性表和队列的理解和认识

[实验内容]

某餐厅由于排队人数太多，造成管理不便，拟开发自助叫号系统。根据餐桌大小分成大桌（八人桌）、中桌（四人桌）和小桌（2人桌）三类的号，大桌和中桌提供拼桌服务，每桌同时就餐人数不得超过餐桌限额。每组就餐人员必须先到前台根据就餐人数取号，不超过2人取小桌号，不超过4人取中桌号，不超过8人取大桌号，超过8人需按照最少分组和最少空座的原则分桌就餐，如10人就餐则取一个大桌号和一个小桌号，12人就餐则取一个大桌号和一个中桌号，14人就餐则取两个大桌号。

每桌取号需要选择是否接受拼桌。每一类餐桌单独编号，如大桌1号、中桌1号、小桌1号，每类餐桌按顺序叫号。若当前就餐的餐桌有空余餐位，且顾客同意拼桌，则在同意拼桌的等待号中选择取号时间最早且就餐人数不超过空余餐位的号，直接进入就餐。如当前大桌3号的5位顾客正在就餐且同意拼桌，则在叫所有等待号中选择取号时间最早的就餐人数少于3人的号直接进入该桌就餐。

备注：

餐厅的所有餐桌编号，小桌1…m，中桌m+1…n，大桌n+1….k；

用户取号时，输入就餐人数以及是否同意拼桌，系统自动产生就餐序号；

当有空桌时，系统通知当前等待的最小同类就餐序号的顾客进入就餐，并告知餐桌号；

若某餐桌就餐完成，系统自动为当前餐桌叫号，每次叫号仅针对同类餐桌的就餐序号；

若某桌当前就餐序号愿意拼桌，且桌上有空座位，则为拼桌客户叫号，每桌最多允许两组就餐人员同时就餐；

对于不愿拼桌的顾客，每桌每次仅允许一组就餐人员就餐。

要求：

输入每类餐桌的数量；

提供用户取号、自动叫号、自动拼桌的功能；

提供自动结算功能（结算的过程实质上是注销就餐序号，重新为餐桌叫号）。

[实验方法及原理]

编写代码，上机调试。

√

11

求解迷宫问题

18

[实验目的]

1、掌握栈的建立。

2、掌握栈的基本操作。

3、深入了解栈的特性,以便在解决实际问题中灵活运用它们。

4、掌握递归算法的非递归写法

[实验内容]

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

（1）以链栈作为存储结构，编写一个求解迷宫的非递归程序，并将求得的通路以三元组（i,j,d）的形式输出，其中： i,j指示迷宫中的一个坐标，d表示走到下一坐标的方向；

（2）编写递归形式的算法，求得迷宫中所有可能的通路；(3)以方阵形式输出迷宫及其通路。（选做） [测试数据] 

左上角（1，1）为入口，右下角（9，8）为出口。 

0 0 1 0 0 0 1 0 

0 0 1 0 0 0 1 0 

0 0 0 0 1 1 0 1

0 1 1 1 0 0 1 0

 0 0 0 1 0 0 0 0

 0 1 0 0 0 1 0 1

 0 1 1 1 1 0 0 1

 1 1 0 0 0 1 0 1

 1 1 0 0 0 0 0 0

实现提示： 

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 

可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

[实验方法及原理]

编写代码，上机调试。

√

12

敢死队问题

18

[实验目的]

1、掌握线性表的不同存储结构的设计和实现

2、掌握的特性及其应用

[实验内容]

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

   排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

[实验方法及原理]

编写代码，上机调试。

√

13

综合排序

18

[实验目的]

1、掌握内部排序算法思想

2、掌握排序算法的实现

3、了解每个排序算法的性能分析及改进

[实验内容]

问题要求：

（1）至少采用四种排序方法实现随机生成100个数值的排序（可采用的排序方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。  

（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

解决思路：

[实验方法及原理]

编写代码，上机调试。

√

14

家谱管理

18

[实验目的]

1、掌握树和二叉树的建立及实现

2、掌握树和二叉树的应用

3、理解树和二叉树的特性

4、了解树和二叉树的递归算法和非递归算法的设计

[实验内容]

（1）项目简介 

家谱（或称族谱）是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属珍贵的人文资料，对于历史学、民俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。 

（2） 设计思路 

本项目的实质是完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。 

（3） 数据结构 

因为家族中的成员之间存在一个对多个的层次结构关系，所以不能用上面讲的线性表来表示。家谱从形状上看像一颗倒长的树，所以用树结构来表示家谱比较适合。树型结构是一类非常重要的非线性数据结构，直观看来，树是以分支关系定义的层次结构。 

可以二叉链表作为树的存储结构，链表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，固该表示法又称二叉树表示法，或孩子兄弟表示法。孩子兄弟表示法是一种链式存储结构，它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系。

[实验方法及原理]

编写代码，上机调试。

√

15

电网建设造价计算

18

[实验目的]

1、掌握图的建立和存储

2、掌握最小生成树算法的设计和实现

[实验内容]

（1）项目简介 

假设一个城市有n个小区，要实现n个小区之间的电网都能够相互接通，构造这个城市n个小区之间的电网，使总工程造价最低。请设计一个能满足要求的造价方案。 

（2）设计思路 

在每个小区之间都可以设置一条电网线路，相应的都要付出一点经济代价。n个小区之间最多可以有n(n-1)/2条线路，选择其中的n-1条使总的耗费最少。可以用连通网来表示n个城市之间以及n个城市之间可能设置的电网线路，其中网的顶点表示小区，边表示两个小区之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个电路网。现在，我们要选择总耗费最少的生成树，就是构造连通网的最小代价生成树的问题，一颗生成树的代价就是树上各边的代价之和。 

设G=(V, E)是具有n个顶点的网络，T=(U, TE)为G的最小生成树，U是T的顶点集合，TE是T的边集合。Prim算法的基本思想是：首先从集合V中任取一顶点（例如去顶点v0）放入集合U中，这时U={ v0}，TE=NULL。然后找出所有一个顶点在集合U里，另一个顶点在集合V-U里的边，使权(u, v)(u∈U, v∈V-U)最小，将该边放入TE，并将顶点v加入集合U。重复上诉操作直到U=V为止。这时TE中有n-1条边，T=(U, TE)就是G的一颗最小生成树。 

（3）数据结构 

可以用带权的无向图（即无向网）表示这n个小区之间的电网连接，其中顶点表示小区，权值表示城市之间电网建设的造价，构造一个无向网的最小生成树即是满足要求的最低电网连接造价方案。假设图以邻接表为存储结构。

[实验方法及原理]

编写代码，上机调试。

√

16

教学计划编制问题

18

[实验目的]

1、掌握图的建立和存储

2、掌握拓扑排序算法的设计和实现

[实验内容]

【问题描述】

    大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学

期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在

开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，

也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

【基本要求】

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

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

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

【测试数据】

学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：

【实现提示】

可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。

[实验方法及原理]

编写代码，上机调试。

 √

17

一元多项式的加法、减法的实现

18

[实验目的]

1、掌握线性表的建立和实现

2、掌握线性表应用于多项式的运算

[实验内容]

设有一元多项式Am(x)和Bn(x)。Am(x)=A₀+A₁x¹+A₂x²+A₃x³+…+A_mx^m

Bn(x)=B₀+B₁x¹+B₂x²+B₃x³+…+B_nxⁿ

请实现求M(x)= Am(x)+Bn(x)、N(x)= Am(x)-Bn(x)。 要求：

1) 分别采用顺序和链式存储结构实现； 

2) 结果M(x)、N(x)中无重复阶项和无零系数项；  

3) 要求输出结果按指数的升幂和降幂两种排列情况输出。

[实验方法及原理]

编写代码，上机调试。

 √

18

组织机构问题

18

[实验目的]

1、掌握树和二叉树的建立及实现

2、理解树和二叉树的特性及在组织结构表示中的应用

[实验内容]

问题描述：以南京中医药大学为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求：

1. 树中每个结点保存部门名称；

2. 假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？

软件可以查询某部门下面的具体编制？

[实验方法及原理]

编写代码，上机调试。

 √

19

公园主要游览景点之间最短距离问题

18

[实验目的]

1、掌握图的建立和存储

2、掌握拓扑排序算法的设计和实现

[实验内容]

问题描述：图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。

 公园最短路径问题中的数据元素有：

1.  顶点数

2.  边数

3.  边的长度

功能需求：要求完成以下功能：

(1) 输出顶点信息：将公园内各景点输出。

（2）输出边的信息：将公园内每两个位置（若两个位置之间有直接路径）的距离输出。

(3) 修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；

(4) 求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径。（较高要求）

（5）删除：删除任意一条边。

（6）插入：插入任意一条边。

[实验方法及原理]

编写代码，上机调试。

 √

20

职工工作量统计

18

[实验目的]

1、掌握线性表的建立和实现

2、掌握线性表的应用

[实验内容]

问题描述：采用随机函数产生职工的工号和他所完成产品个数的数据信息，对同一职工多次完成的产品个数进行累计，按职工完成产品数量的名次、该名次每位职工完成的产品数量、同一名次的职工人数和他们的职工号格式输出。

实现要求：输出统计结果，如下所示：

Order   Quantity   Count   Number

1    3753102021

4250235

620019

71502     1114

……………

程序设计思路：采用链表结构存储有关信息，链表中的每个结点对应于一位职工。在数据采集的同时，形成一个有序链表（按完成的产品数量和工号排序）。当一个职工有新的数据输入，在累计他的完成数量时会改变原来链表的有序性，为此应对链表进行删除、查找和插入等操作。

[实验方法及原理]

编写代码，上机调试。

 √