数据结构实验指导书

数据结构实验指导书

邢振祥

计算机应用教研室

2 数据结构实验指导

第 1 章 绪 论

本章讨论的是数据结构和算法的基本概念，为巩固理论知识的学习，本章的实验内容针对最基本的数据结构——数组，以及基于数组的简单算法，实现程序设计语言和数据结构的自然衔接，从数据结构的角度重新思考如何进行程序设计，从而提升程序设计乃至算法设计的能力。

1.1 实验的一般步骤 1.1.1 概述

数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结构中要解决的问题更接近于实际。数据结构的实验是对学生的一种全面的综合训练，与程序设计语言课程中的实验不同，数据结构课程中的实验多属创造性的活动，需要学生自己进行问题分析、进行数据结构和算法的设计、再上机调试和测试程序。数据结构的实验是一种自主性很强的学习过程，其教学目的主要有两个：⑴ 深化理解和掌握书本上的理论知识，将书本上的知识变“活”；⑵ 理论和实践相结合，使学生学会如何把书本上有关数据结构和算法的知识用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。

为了达到上述目的，本书安排了如下三类实验：

⑴ 验证实验：其主要内容是将书上的重要数据结构上机实现，深化理解和掌握理论知识，这部分的实验不需要学生自己设计，只需将给定的方案实现即可；

⑵ 设计实验：其主要内容是针对具体问题，应用某一个知识点，自己设计方案，并上机实现，目的是培养学生对数据结构的简单应用能力；

⑶ 综合实验：其主要内容是针对具体问题，应用某几个知识点，自己设计方案，并上机实现，目的是培养学生对数据结构的综合应用能力。

在验证实验中，由实验目的、实验内容、实现提示和实验程序等四部分组成，其中实验目的明确了该实验要学生掌握哪些知识点；实验内容规定了实验的具体任务；实现提示给出了数据结构和算法的设计方法；实验程序给出了实验的范例程序，并且在主教材的随书光盘中有该实验涉及到的数据结构的全部实现。在验证实验中，不要求但鼓励学生在完成实验任务的基础上，对该实验涉及的数据结构的其他实现方法进行探索。

3 数据结构实验指导 在设计实验和综合实验中，由问题描述、基本要求、设计思想、思考题等四部分组成，其中问题描述是为学生建立问题的背景环境，指明“问题是什么”；基本要求是对问题的实现进行基本规范，保证预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查；设计思想给出了设计数据结构和算法的主要思路；思考题引导学生在做完实验后进行总结和扩充。

虽然在设计实验和综合实验中都给出了一定的设计方案，但是，学生不应拘泥于这些分析和设计，要尽量发挥想象力和创造力。对于一个实际问题，每个人可能会有不同的解决办法，本书给出的范例方案，只是希望把学生的思路引入正轨，提出了思考问题的方法，但是不希望限制学生的思维，鼓励学生自己设计解决方案。

1.1.2 验证实验的一般步骤

验证实验安排的内容在书上都能找到具体的实现方法，并且在主教材的随书光盘中也都有相应的程序实现。这些验证实验是学生在学习完一种数据结构后进行的，对于深化理解和掌握相应数据结构具有很重要的意义。 1. 预备知识的学习

由于篇幅所限，本书没有整理验证实验所用到的预备知识，但主教材中的相关内容已经叙述得很清楚了，需要学生在实验前复习实验所用的预备知识。这需要学生有自主的学习意识和整理知识的能力。 2. 上机前的准备

将实现提示中给出的数据类型和算法转换为对应的程序，并进行静态检查，尽量减少语法错误和逻辑错误。

很多学生在上机时只带一本数据结构书或实验指导书，而书上只有算法设计而没有实验程序，于是就直接在键盘上输入程序，结果不仅程序的输入速度慢，而且编译后出现很多错误。上机前的充分准备能高效利用机时，在有限的时间内完成更多的实验内容。 3. 上机调试和测试程序

调试程序是一个辛苦但充满乐趣的过程，也是培养程序员素质的一个重要环节。很多学生都有这样的经历：化了好长时间去调试程序，错误却越改越多。究其原因，一方面，是对调试工具不熟悉，出现了错误提示却不知道这种错误是如何产生的；另一方面，没有认识到努力预先避免错误的重要性，也就是对程序进行静态检查。

对程序进行测试，首先需要设计测试数据。在数据结构中测试数据需要考虑两种情况：⑴ 一般情况：例如循环的中间数据、随机产生的数据等；⑵ 特殊情况：例如循环的边界条件、数据结构的边界条件等。 4. 实验报告

在实验后要总结和整理实验报告，实验报告的一般格式请参见附录一。

4 数据结构实验指导 1.1.3 设计实验和综合实验的一般步骤

设计实验和综合实验的自主性比较强，涉及到的知识点也比较多，可以在课程设计中完成，设计实验推荐单人完成，综合实验推荐多人完成，主要目的是为了培养数据结构的应用能力、软件工程的规范训练、团队精神和良好的科学作风。 1. 问题分析

在设计实验和综合实验中的问题描述通常都很简洁，因此，首先要充分理解问题，明确问题要求做什么，限制条件是什么，也就是对所需完成的任务做出明确的描述。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围以及输入的形式；哪些属于非法输入，等等。在问题分析时还应该准备好测试数据。 2. 概要设计

概要设计是对问题描述中涉及到的数据定义抽象数据类型，设计数据结构，设计算法的伪代码描述。在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单，抽象数据类型尽可能做到数据封闭，基本操作的说明尽可能明确。而不必过早地考虑存储结构，不必过早地考虑语言的实现细节，不必过早地表述辅助数据结构和局部变量。 3. 详细设计

在详细设计阶段，需要设计具体的存储结构（即用C++描述抽象数据类型对应的类）以及算法所需的辅助数据结构，算法在伪代码的基础上要考虑细节问题并用C++描述。

此外，还要设计一定的用户界面。数据结构课程实验的主要目的是为了培养数据结构的应用能力，因此在实验中不要求图形界面，只需要在屏幕上提示用户每一步操作的输入、将结果输出即可。 4. 编码实现和静态检查

将详细设计阶段的结果进一步优化为C++程序，并做静态检查。

很多初学者在编写程序后都有这样的心态：确信自己的程序是正确的，认为上机前的任务已经完成，检查错误是计算机的事。这种心态是极为有害的，这样的上机调试效率是极低的。事实上，即使有几十年经验的高级软件工程师，也经常利用静态检查来查找程序中的错误。

5. 上机调试和测试程序

掌握调试工具，设计测试数据，上机调试和测试程序。调试正确后，认真整理源程序和注释，给出带有完整注释且格式良好的源程序清单和结果。 6. 总结并整理实验报告

在实验后要总结和整理课程设计报告，课程设计报告的一般格式请参见附录二。

5 数据结构实验指导 1.2 设计实验

1.2.1 在数组中求最小值

1. 问题描述

已知一个数组，求该数组中值最小的元素。 2. 基本要求

⑴ 对于由确定元素组成的数组（即在程序中直接赋值），实现求最小值； ⑵ 随机生成数组元素（即由机器生成随机数），实现求最小值； ⑶ 分析算法的时间性能。 3. 设计思想

我们都知道“打擂台”这个名词，它的意思是说，如果有若干人比武，先有一个人站在台上，再上去一个人与其交手，败者下台，胜者留在台上。如此下去，直到所有人都上台比过为止，最后留在台上的就是胜者。按照这个思路，首先把数组a[0]的值赋给变量min，min就是开始时的擂主，然后让下一个元素与它比较，将二者中值较小者保存在min中，直到数组中所有元素都比完为止。最后min中保存的就是数组中所有元素的最小值。 4. 算法描述

下面给出具体的在以个整型数组中求最小值的算法。 在数组中求最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i

1.2.2 统计候选人得票

1. 问题描述

设有n个候选人参加选举，统计每个候选人最后的得票情况。 2. 基本要求

⑴ 以数组作为存储结构；

⑵ 设计统计得票算法，将最后的得票情况统计并输出。

6 数据结构实验指导 3. 设计思想

可以将每个候选人设计为一个结构类型，包括名字和得票数，将n个候选人组成一个结构数组，其存储结构定义如下：

const int n=10; //假设有10个人参加选举 struct Person {

char *name; int count; } Leader[n];

可以从键盘依次输入选举情况，每次输入一个人的名字，将输入的名字与结构数组Leader进行比较，将对应候选人的得票数加1。 4. 算法描述

选票统计算法 void Election(Person Leader[ ], int n) { cin>>name; while (name!=\) { for (i=0; i>name; } for (i=0; i

1.3 综合实验

10.3.1 顺序查找最好、最坏和平均的时间性能

1. 问题描述

在一维整型数组A[n]中顺序查找与给定值相等的元素。 2. 基本要求

⑴ 只考虑查找成功的情况；

⑵ 求出最好、最坏、平均情况下待查值与数组元素的实际比较次数； ⑶ 总结实验结果，给出结论。

7 数据结构实验指导 3. 设计思想

所谓顺序查找就是从数组的第一个元素开始，依次比较每一个元素与待查值是否相等。为了测算待查值与数组元素的实际比较次数，需要在算法中设置计算比较次数的累加器count，算法结束后输出其值。 4. 算法描述

顺序查找算法 int Find(int A[ ], int n, int k) { count=0; for (i=0; i

⑵ 对于排序问题设计一个算法，并分析最好、最坏和平均的时间性能。

1.3.2 比较解决相同问题的不同算法的时间性能

1. 问题描述

在一个数组中确定第k小的元素（假定数组元素可以进行比较）。 2. 基本要求

⑴ 采用模板函数实现； ⑵ 至少采用两种方法求解； ⑶ 分析不同算法的时间性能。 3. 设计思想

方法一：采用起泡排序，将数组中的所有元素排序，然后输出第k个元素。起泡排序的基本思想是：两两比较相邻元素，如果反序则交换，直到全部元素都排好序为止。 起泡排序算法 template T BubbleSort (T r[ ], int n, T k) { for (i=1; i

for (j=0; j

if（r[j]>r [j+1]）{ [j]←→r[j+1]; //交换元素 } return r[k-1]; //第k小元素在数组中下标为k-1的位置

} 8 数据结构实验指导 该算法的时间性能是Ｏ(n2)。

方法二：采用选择排序，当找出第k小元素后，不再进行排序过程。选择排序的基本思想是：第i趟排序通过n-i次关键码的比较，在n-i+1（1≤i≤n-1）个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。 选择排序算法

template

T SelectSort(T r[ ], int n, T k) { for (i=0; i

index=i;

for (j=i+1; j

if (r[j]

}

return r[k-1]; //第k小元素在数组中下标为k-1的位置

}

该算法的时间性能是Ｏ(k×n)。

【思考题】你还能设计出其他算法吗？自行设计另外一种方法，并分析其时间性能。

9 数据结构实验指导

第 2 章 线性表

线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的验证实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础。通过本章的设计实验和综合实验，进一步培养以线性表作为数据结构解决实际问题的应用能力。

2.1 验证实验 2.1.1 顺序表操作验证

1. 实验目的

⑴ 掌握线性表的顺序存储结构； ⑵ 验证顺序表及其基本操作的实现；

⑶ 掌握数据结构及算法的程序实现的基本方法。 2. 实验内容

⑴ 建立含有若干个元素的顺序表；

⑵ 对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示

首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。

const int MaxSize=10;

template //定义模板类SeqList class SeqList {

public:

SeqList( ){length=0;} //无参构造函数 SeqList(T a[ ], int n); //有参构造函数

void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素

int Locate(T x ); //按值查找，求线性表中值为x的元素序号 void PrintList( ); //遍历线性表，按序号依次输出各元素

10 数据结构实验指导 private:

T data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 };

其次，建立含有n个数据元素的顺序表，即设计构造函数。算法如下： 顺序表有参构造函数SeqList template SeqList:: SeqList(T a[ ], int n) { if (n>MaxSize) throw \参数非法\ for (i=0; i void SeqList::Insert(int i, T x) { if (length>=MaxSize) throw \上溢\ if (i<1 | | i>length+1) throw \位置\for (j=length; j>=i; j--) data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处 data[i-1]=x; length++; } ⑵ 删除算法 顺序表删除算法Delete template T SeqList::Delete(int i) { if (length==0) throw \下溢\ if (i<1 | | i>length) throw \位置\ x=data[i-1]; for (j=i; j

46 数据结构实验指导 2. 实验内容

⑴ 建立一棵含有n个结点的二叉树，采用二叉链表存储； ⑵ 前序（或中序、后序）遍历该二叉树。 3. 实现提示

二叉链表的结点结构如图5-2所示。 lchild data rchild

图5-2 二叉树的结点结构

二叉链表的结点用C++中的结构类型描述为： template struct BiNode {

T data;

BiNode *lchild, *rchild; };

设计实验用二叉链表类BiTree，类中包含遍历操作。

template class BiTree {

public:

BiTree(BiNode *root); //有参构造函数，初始化一棵二叉树，其前序序列由键盘输入 ~BiTree( ); //析构函数，释放二叉链表中各结点的存储空间 void PreOrder(BiNode *root); //前序遍历二叉树 void InOrder(BiNode *root); //中序遍历二叉树 void PostOrder(BiNode *root); //后序遍历二叉树 private:

BiNode *root; //指向根结点的头指针

void Creat(BiNode *root); //有参构造函数调用 void Release(BiNode *root); //析构函数调用 };

设计构造函数，建立一棵二叉树的二叉链表存储。

将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的一个遍历序列就能唯一确定一棵二叉树。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：首先输入根结点，若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL；否则输入的字符应该赋给root->data,，之后依次递归建立它的左子树和右子树。建立二叉链表的递归算法如下：

47 数据结构实验指导 二叉树的构造函数算法BiTree template BiTree ::BiTree(BiNode *root) { root =creat( ); } template BiNode *BiTree ::Creat( ) { cin>>ch; if (ch=='# ') return NULL; //建立一棵空树 else { root=new BiNode; //生成一个结点 root->data=ch; root->lchild=Creat( ); //递归建立左子树 root->rchild=Creat( ); //递归建立右子树 } } 前序遍历的递归算法如下： 二叉树前序遍历递归算法PreOrder template void BiTree::PreOrder(BiNode *root) { if (root ==NULL) return; //递归调用的结束条件 else { cout<data; //访问根结点的数据域 PreOrder(root->lchild); //前序递归遍历root的左子树 PreOrder(root->rchild); //前序递归遍历root的右子树 } } 中序和后序遍历的算法请仿照前序遍历的递归算法自行设计。 4. 实验程序

参见主教材随书光盘。

48 数据结构实验指导 5.2 设计实验

5.2.1 求二叉树中叶子结点的个数

1. 问题描述

已知一棵二叉树，求该二叉树中叶子结点的个数。 2. 基本要求

⑴ 采用二叉链表作存储结构；

⑵ 设计递归算法求叶子结点的个数。 3. 设计思想

求二叉树中叶子结点的个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。因此可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。算法如下：

求二叉树叶子结点个数算法 void CountLeaf(BiNode *root, int &count) //前序遍历根指针为root的二叉树以计算叶子数count，假定count的初值为0； { if (root!=NULL) { if (root->lchild==NULL && root->rchild = =NULL) count++; //若root所指的结点是叶子，则计数器加1; CountLeaf(root->lchild, count); //累计左子树上的叶子数； CountLeaf(root->rchild, count); //累计右子树上的叶子数； } } 【思考题】如何设计非递归算法求叶子结点的个数？

5.2.2 判断两棵二叉树是否相似

1. 问题描述

设计算法判断给定的两棵二叉树是否相似。

两棵二叉树当且仅当满足以下条件，称这两棵二叉树是相似的： ⑴ 他们都为空或都只有一个根结点； ⑵ 他们的左右子树也相似。 2. 基本要求

⑴ 采用二叉链表作存储结构；

⑵ 设计递归算法判断两棵二叉树是否相似。

49 数据结构实验指导 3. 设计思想

由二叉树相似的定义，得到如下判定两棵二叉树s和t是否相似的递归函数Like： ⑴ 若s=t=NULL，则s和t相似，即Like(s, t)=1;

⑵ 若s和t中有一个为NULL，另一个不为NULL，则s和t不相似，即Like(s, t)=0; ⑶ 进一步判断s的左子树和t的左子树、s的右子树和t的右子树是否相似。 具体算法如下： 二叉树相似算法Like int Like(BiNode *s, BiNode *t) { if (!s && !t) return 1; else if ((!s && t) | | (s && !t)) return 0; else { same=Like(s->lchild, t->lchild); if (same) same=Like(s->rchild, t->rchild); return same; } } 【思考题】设计非递归算法完成两棵二叉树是否相似的判断。

5.3 综合实验 5.3.1 信号放大器

1. 问题描述

天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。 2. 基本要求

⑴ 建立模型，设计数据结构； ⑵ 设计算法完成放大器的放置； ⑶ 分析算法的时间复杂度。 3. 设计思想

为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。图5-3是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。

50 数据结构实验指导

1 B 2 D 2 H 1 I 2 E A 3 C 1 F 2 G 2 J K

2 图5-3 网络分布示意图

对于网络中任一结点i，设d(i)表示结点i与其父结点间的衰减量，D(i)为从结点i到结点i的子树中任一叶子结点的衰减量的最大值，并有如下递推公式：

D(i)=0 若i为叶结点 D(i)= max{D(j) + d(j)} 若i不是叶结点且j是i的孩子

在此公式中，要计算某结点的D值，必须先计算其孩子结点的D值，因而必须后序遍历二叉树，当访问一个结点时，计算其D值。

例如，D(B)=max{D(D)+d(D)，D(E)}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。若在结点D 处放置一个放大器，则D(B)=2。

根据上述分析，设计如下存储结构： STRUCT ELEMENT

{

int D; // 该结点的衰减量 int d; // 父结点的衰减量

bool boost; //当且仅当本处设置放大器，则boost为true };

struct BiNode {

element data;

BiNode *lchild,*rchild; };

计算并放置放大器的伪代码为： 1. D(i) = 0 ; 2. for (i 的每个孩子j ) 2.1 如果D(j) +d(j)>容忍值，则在j处放置放大器; 2.2 否则D(i) = max{D(i)，D(j) +d(j)} ;

31 数据结构实验指导 所以把8号车厢移动至H2，这样就可以把5号车厢直接从入轨移至出轨。如图(c)所示。此后，可依次从缓冲轨中移出6号、7号、8号和9号车厢。

96 963 H1 H1 581 581742963 4321

H3 H3 出 轨 出 轨 入 轨 入 轨 7 742 H2 H2 (a) 将369、247依次入缓冲轨 (b) 将1移至出轨，234移至出轨

96

H1 H1

5 54321 987654321

H3 H3 入 轨 出 轨 出 轨 入 轨 87

H2 H2

(c) 将8入缓冲轨，5移至出轨 (d) 将6789移至出轨

图3-2 火车车厢重排过程

由上述重排过程可知：在把车厢c移至缓冲轨时，车厢c应移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择队尾车厢编号最大的缓冲轨；否则选择一个空的缓冲轨。算法如下：

1. 分别对k个缓冲轨队列初始化；

2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号 for (i=1; i<=n; i++) 3.1 如果入轨中的车厢编号等于nowOut，则 3.1.1 输出该车厢；

3.1.2 nowOut++；

3.2 如果入轨中的车厢编号不等于nowOut，则考察每一个缓冲轨队列

for (j=1; j<=k; j++) 3.2.1 取队列j的队头元素c； 3.2.2 如果c等于nowOut，则 3.2.2.1 将队列j的队头元素出队并输出； 3.2.2.2 nowOut++；

3.3 如果入轨和缓冲轨的队头中没有编号为nowOut的车厢，则

3.3.1 比较k个队尾元素，求最大队尾元素所在队列编号j;

3.3.2 如果入轨中第一个车厢的编号小于缓冲轨j中队尾车厢编 号，则车厢无法重排，算法结束； 3.3.3 否则，把入轨中的第一个车厢移至缓冲轨j； 32 数据结构实验指导 【思考题】如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？

3.2.3 统计文本中单词的个数

1. 问题描述

一个文本可以看成一个字符序列，在这个序列中，有效字符被空格分隔为一个个单词。设计算法统计文本中单词的个数。 2. 基本要求

⑴ 可以读取任意文本内容；

⑵ 设计算法统计文本中的单词个数； ⑶ 分析算法的时间性能。 3. 设计思想

被处理文本的内容可以用getchar函数由键盘读入，设置一个计数器count统计文本中单词的个数。

在逐个读入和检查字符时，需要区分当前字符是否是空格。不是空格的字符总是某个单词的一部分，空格的作用就是分隔单词。但即使当前字符不是空格，它是不是新词的开始还依赖于前一字符是否是空格，只有当前字符是单词的首字符时，才可以给计数器加1。因此，读取的字符有两种不同的状态：

⑴ state=1:读入过程处在单词之外，如果遇到非空格字符，则是新词； ⑵ state=0:读入过程处在某单词的内部，则不会遇到新词。

因此，需要设置一个状态变量state，表示读入字符的状态。算法用伪代码描述如下：

1. 初始化计数器count=0; 初始化读取字符的状态state=1；

2. 当文本未结束时，循环执行下述操作：

2.1 如果读入的字符是空格，则state=1;

2.2 否则，如果state=1，则

2.2.1 state =0;

2.2.2 ++count;

3. 输出count；

【思考题】如果文本以文件形式存放，如何统计文本中的单词个数？

33 数据结构实验指导 3.3 综合实验

3.3.1 表达式求值

1. 问题描述

对一个合法的中缀表达式求值。 假设表达式只包含+、-、×、÷ 四个双目运算符，且运算符本身不具有二义性。 2. 基本要求

⑴ 正确解释表达式； ⑵ 符合四则运算规则； ⑶ 输出最后的计算结果。 3. 设计思想

对中缀表达式求值，通常使用“算符优先算法”。根据四则运算规则，在运算的每一步中，任意两个相继出现的运算符t和c之间的优先关系至多是下面三种关系之一：

⑴ tc：t的优先级高于c。 为实现算符优先算法，可以使用两个工作栈：一个栈OPTR存放运算符；另一个栈OPND存放操作数，中缀表达式用一个字符串数组存储。算法用伪代码描述如下：

1. 初始化：栈OPTR中只有一个元素'# '，栈OPND为空栈； 2. 依次读入字符，执行下述操作： 2.1 ch=读入的字符; 2.2 若ch='# '，则算法结束，返回栈OPND的栈顶元素； 2.3 若ch不是运算符，则将ch入栈OPND； 2.4 若ch是运算符，则 2.4.1 t=取栈OPTR的栈顶元素； 2.4.2 比较ch和t的优先级，执行下述三种操作之一： ⑴ 若ch=t：将栈OPTR的栈顶元素出栈； ⑵ 若ch>t：将ch插入栈OPTR中； ⑶ 若ch

34 数据结构实验指导 3.3.2 迷宫问题

1. 问题描述

迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图3-3所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。

0 入口(1, 1) 1 2 3 4 5 6 7 2. 基本要求

⑴ 设计数据结构存储迷宫；

⑵ 设计存储结构保存从入口到出口的通路； ⑶ 设计算法完成迷宫问题的求解； ⑷ 分析算法的时间复杂度。 3. 设计思想

可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。

可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向 v (0≤v≤7) 到达新点（i，j）的坐标：i=x+move[v].x ； j=y+move[v].y。

算法用伪代码描述如下：

0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 2 1 1 0 1 1 0 1 1 3 1 1 1 0 1 0 1 1 4 1 1 0 0 1 1 0 1 5 1 0 1 0 0 1 0 1 6 1 1 1 0 1 0 1 1 7 1 1 1 0 1 0 1 1 8 1 1 1 1 1 0 0 1 9 1 1 1 1 1 1 1 1 出口(6, 8)

图3-3 迷宫示意图，其中1代表有障碍，0代表无障碍

前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下

35 数据结构实验指导

1. 栈初始化；

2. 将入口点坐标(x , y)及该点的方向d（设为-1）入栈；

3. 当栈不空时循环执行下述操作：

3.1 (x , y , d)<==栈顶元素出栈；

3.2 求出下一个要试探的方向d++ ;

3.3 沿顺时针试探每一个方向，执行下述操作：

3.3.1 如果方向d可走，则

3.3.1.1 将(x , y , d)入栈；

3.3.1.2 求新点坐标(i, j)；

3.3.1.3 将新点(i , j)切换为当前点(x , y)；

3.3.1.4 若(x, y)是终点，则算法结束；

否则，重置d=0；

3.3.2 否则，试探下一个方向d++；

【思考题】如何记录栈的每一个变化状态（即搜索的详细过程）。

3.3.3 双端队列

1. 问题描述

双端队列是插入和删除操作可以在两端进行的线性表，表的两端分别称作端点1和端点2。设计双端队列的数据结构，实现入队、出队等基本操作 2. 基本要求

⑴ 定义双端队列的抽象数据类型； ⑵ 设计存储结构存储双端队列； ⑶ 设计双端队列的插入和删除算法； ⑷ 分析算法的时间性能。 3. 设计思想

为便于双端队列的插入和删除操作，采用双链表存储双端队列，为使空表和非空表的处理一致，双链表带头结点，在双链表中设指针end1指向头结点，指针end2指向终端结点。其顺序存储示意图如图3-4所示。

end2end1 a1 a a -n n1 first 图3-4 双端队列存储示意图

定义双端队列的双链表类DulQueue，包括入队和出队等基本操作。

36 数据结构实验指导 template struct DulNode {

T data;

DulNode *prior, *next; };

template class DulQueue {

public:

DulQueue( ); ~ DulQueue( );

void EnQueue(int i, T x); T DeQueue(int i); private:

DulNode *end1, *end2; };

入队操作的算法用伪代码描述如下： 1. 判断是插在端点1还是端点2； 2.1 若是在端点1插入，则将新结点插在头结点之后； 2.2 若是在端点2插入，则将新结点插在终端结点之后； 出队操作的算法用伪代码描述如下： 1. 判断删除是在端点1还是端点2； 2.1 若是在端点1删除，则将开始结点删除； 2.2 若是在端点2删除，则将终端结点删除； 【思考题】⑴ 设计并实现输出受限的双端队列，即一个端点允许插入和删除操作，另一端点只允许插入操作。

⑵ 设计并实现输入受限的双端队列，即一个端点允许插入和删除操作，另一端点只允许删除操作。

37 数据结构实验指导

第 4 章 数组和广义表

数组是人们非常熟悉的基本数据结构，科学计算中的矩阵在程序设计语言中就是采用数组实现的。通过本章的验证实验和设计实验，巩固对特殊矩阵和稀疏矩阵的压缩存储方法的理解和运用，在综合实验中安排了两个利用数组实现的简单游戏，从而理解数组在实际问题中的应用。

广义表作为一种特殊的数据结构，兼有线性表、树、图的特性，所以，本章的实验仅实现广义表的基本操作。

4.1 验证实验

4.1.1 对称矩阵的压缩存储

1. 实验目的

⑴ 掌握对称矩阵的压缩存储方法； ⑵ 掌握对称矩阵压缩存储的寻址方法。 2. 实验内容

⑴ 建立一个n×n的对称矩阵； ⑵ 将对称矩阵用一维数组存储； 3. 实现提示

首先建立一个n×n的对称矩阵A并初始化矩阵的元素。对称矩阵只需存储下三角部分，即将一个n×n的对称矩阵用一个大小为n×(n+1)/2的一维数组SA来存储，则下三角中的元素aij（i≥j）在SA中的下标k与i、j的关系为k＝i×(i-1)/2＋j。算法如下：

对称矩阵的压缩存储算法 void Matrix(int A[ ][ ], int n, int SA[ ]) { for (i=0; i

参见主教材随书光盘。

4.1.2 广义表操作验证

1. 实验目的

⑴ 掌握广义表的逻辑结构；

⑵ 掌握广义表的头尾表示法存储结构；

⑶ 掌握广义表的基本操作在头尾表示法上的实现方法。 2. 实验内容

⑴ 采用头尾表示法建立广义表； ⑵ 求广义表的深度。 3. 实现提示

采用头尾表示法来存储广义表，其结点结构如图4-1所示。

tag=1 hp tp tag=0 data

(a) 表结点 (b) 元素结点

图4-1 头尾表示法的结点结构

用C++中的结构类型和联合类型来定义上述结点结构。

enum Elemtag {Atom, List}; //Atom=0为单元素；List=1为子表 template struct GLNode {

Elemtag tag; //标志域，用于区分元素结点和表结点 union

{ //元素结点和表结点的联合部分 T data; //data是元素结点的数据域 struct {

GLNode *hp, *tp; //hp和tp分别指向表头和表尾

} ptr; }; };

定义实验所用的广义表类Lists，除构造函数和析构函数外，只包括求深度操作。 class Lists {

public:

Lists(Lists ls1, Lists ls2); //有参构造函数，用表头ls1和表尾ls2构造广义表 ~Lists( ); //析构函数，释放广义表中各结点的存储空间 int Depth( ); //求广义表的深度 private:

39 数据结构实验指导 GLNode *ls; //ls是指向广义表的头指针 };

⑴ 以表头、表尾建立一个广义表

广义表构造函数算法Lists template Lists::Lists(Lists ls1,Lists ls2) { ls = new GLNode ls->tag = 1; ls->ptr.hp = ls1; ls->ptr.tp = ls2; } ⑵ 求广义表的深度

设非空广义表LS＝（a1，a2，??，an），其中每个直接元素ai或者是单元素，或者是子表。这样，求LS的深度可分解为n个子问题，每个子问题为求ai的深度。若ai是单元素，其深度为0；若ai是子表，则对ai继续分解。最后LS的深度为各ai的深度的最大值加1。因此可以采用递归算法实现求广义表深度。

求广义表深度算法Depth template int Lists::Depth( ) { if (ls!=NULL) return 1; //空表深度为1 if (ls->tag==0) return 0; //单元素深度为0 max=0; p = ls; while (p) { dep = Depth(p->ptr.hp); //求以p->ptr.hp为头指针的子表即表头的深度 if (dep>max) max = dep; p = p->ptr.tp; //准备求表尾的深度 } return max+1; //非空表的深度是各元素的深度的最大值加1 } 4. 实验程序

参见主教材随书光盘。

40 数据结构实验指导 4.2 设计实验

4.2.1 稀疏矩阵的转置

1. 问题描述

采用三元组顺序表存储稀疏矩阵，并实现其转置。 2. 基本要求

⑴ 设计存储结构实现稀疏矩阵的压缩存储； ⑵ 设计算法实现稀疏矩阵的转置；

⑶ 分析算法的时间复杂度和空间复杂度。 3. 设计思想

将稀疏矩阵的非零元素对应的三元组（行号、列号、非零元素值）所构成的集合，按行优先的顺序排列成一个线性表，对该线性表采用顺序存储结构，同时存储该矩阵的行数、列数和非零元素的个数。三元组顺序表的存储结构定义如下： template struct element {

int row, col; T item };

const int MaxTerm=10; struct SparseMatrix {

element data[MaxTerm];

int mu, nu, tu; //行数、列数、非零元个数 };

将稀疏矩阵A转置为矩阵B的基本思想是：在A的三元组顺序表中依次找第0列、第1列、??、直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。算法用伪代码描述如下：

1. 设置转置后矩阵B的行数、列数和非零元素的个数； 2. 在B中设置初始存储位置pb； 3. for (col=最小列号; col<=最大列号; col++) 3.1 在A中查找列号为col的三元组； 3.2 交换其行号和列号，存入B中pb位置； 3.3 pb++； 【思考题】将主教材中稀疏矩阵转置的第二种方法实现，并与第一种方法进行比较。

21 数据结构实验指导

⑵ 根据集合的运算规则，集合A?B中包含所有或属于集合A或属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x不相同的元素，则将该结点插入到单链表A中。算法请参照求集合的交集自行设计。

⑶ 根据集合的运算规则，集合A-B中包含所有属于集合A而不属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x相同的结点，则将该结点从单链表A中删除。算法请参照求集合的交集自行设计。

【思考题】如果表示集合的单链表是无序的，应如何实现集合的交、并和差运算？

2.3 综合实验 2.3.1 约瑟夫环问题

1. 问题描述

设有编号为1，2，??，n的n(n>0)个人围成一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，??，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 2. 基本要求

⑴ 建立模型，确定存储结构；

⑵ 对任意n个人，密码为m，实现约瑟夫环问题；

⑶ 出圈的顺序可以依次输出，也可以用一个数组存储。 3. 设计思想

22 数据结构实验指导 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node {

int data; //编号 Node *next;

};

其次，建立一个不带头结点的循环链表并由头指针first指示。具体算法请参见2.1.2自行设计。

最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图2-1所示。 1. 工作指针pre和p初始化，计数器count初始化；

pre first 1 pre 2 p count=2 (a) 一般情况

pre=first; p=first->next; count=2; //为便于删除操作，从2开始计数 2. 循环直到p=pre 2.1 如果count=m，则 2.1.1 输出结点p； 2.1.2 删除结点p； 2.1.3 计数器count清零，重新开始计数； 2.2 否则，执行 2.2.1 工作指针pre和p后移； 2.2.2 计数器增1； 3. 退出循环，链表中只剩下一个结点p，输出结点p后将结点p删除； 3 n 1 p (b) 只剩下一个结点的特殊情况 图2-1 约瑟夫环问题存储示意图 【思考题】⑴ 采用顺序存储结构如何实现约瑟夫环问题？

⑵ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？

23 数据结构实验指导 2.3.2 一元多项式相加

1. 问题描述

已知A(x)=a0+a1x+a2x2+??+anxn和B(x)=b0+b1x+b2x2+??+bmxm，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)+B(x)。 2. 基本要求

⑴ 设计存储结构表示一元多项式； ⑵ 设计算法实现一元多项式相加；

⑶ 分析算法的时间复杂度和空间复杂度。 3. 设计思想

一元多项式求和实质上是合并同类项的过程，其运算规则为：⑴ 若两项的指数相等，则系数相加；⑵ 若两项的指数不等，则将两项加在结果中。

一元多项式A(x)=a0+a1x+a2x2+??+anxn由n+1个系数唯一确定，因此，可以用一个线性表(a0，a1，a2，??，an)来表示，每一项的指数i隐含在其系数ai的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多零元素。一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。

由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。结点结构如图2-2所示。

coef exp next

图2-2 一元多项式单链表的结点结构

其中，coef：系数域，存放非零项的系数；

exp：指数域，存放非零项的指数；

next：指针域，存放指向下一结点的指针。

将两个一元多项式用两个单链表存储后，如何实现二者相加呢？

设两个工作指针p和q，分别指向两个单链表的开始结点。通过对结点p的指数域和结点q的指数域进行比较进行同类项合并，则出现下列三种情况：

⑴ 若p->expexp，则结点p应为结果中的一个结点；

⑵ 若p->exp>q->exp，则结点q应为结果中的一个结点，将q插入到第一个链表中结点p之前；

⑶ 若p->exp=q->exp，则结点p与结点q为同类项，将q的系数加到p的系数上。若相加结果不为0，则结点p应为结果中的一个结点，同时删除结点q；若相加结果为0，则表明结果中无此项，删除结点p和结点q；

算法用伪代码描述如下：

24 数据结构实验指导

【思考题】用顺序表如何实现两个多项式相加，设计算法并与单链表实现进行比较。

1. 工作指针p、q初始化； 2. while（p存在且q存在）执行下列三种情形之一 2.1 如果p->expexp，则指针p后移; 2.2 如果p->exp>q->exp，则 2.2.1 将结点q插入到结点p之前； 2.2.2 指针q指向原指结点的下一个结点； 2.3 如果p->exp=q->exp，则 2.3.1 p->coef =p->coef+q->coef； 2.3.2 如果p->coef ==0，则执行下列操作，否则，指针p后移; 2.3.2.1 删除结点p； 2.3.2.2 使指针p指向它原指结点的下一个结点； 2.3.3 删除结点q； 2.3.4 使指针q指向它原指结点的下一个结点； 3. 如果q不为空，将结点q链接在第一个单链表的后面； 25 数据结构实验指导

第 3 章 栈、队列和串

本章的实验内容围绕三种特殊线性表——栈、队列和串展开。

栈和队列广泛应用在各种软件系统中，掌握栈和队列的存储结构及基本操作的实现是以栈和队列作为数据结构解决实际问题的基础，尤其栈有很多经典应用，深刻理解并实现这些经典应用，对于提高数据结构和算法的应用能力具有很重要的作用。

尽管在大多数高级语言中都提供了串变量并实现了串的基本操作，但在实际应用中，串往往具有不同的特点，要实现串的处理，就必须根据具体情况采用（或设计）合适的存储结构。本章安排的有关串的实验是灵活运用串的基础。

3.1 验证实验

3.1.1 栈操作验证

1. 实验目的

⑴ 掌握栈的顺序存储结构； ⑵ 掌握栈的操作特性；

⑶ 掌握基于顺序栈的基本操作的实现方法。 2. 实验内容

⑴ 建立一个空栈；

⑵ 对已建立的栈进行插入、删除、取栈顶元素等基本操作。 3. 实现提示

首先，定义顺序栈的数据类型——顺序栈类SeqStack，包括入栈、出栈、取栈顶元素等基本操作。

const int StackSize=10;

template //定义模板类SeqStack class SeqStack {

public:

SeqStack( ); //构造函数，初始化一个空栈 void Push(T x); //将元素x入栈

26 数据结构实验指导 T Pop( ); //将栈顶元素弹出 T GetTop( ); //取栈顶元素（并不删除） private:

T data[StackSize]; //存放栈元素的数组

int top; //栈顶指针，指示栈顶元素在数组中的下标 };

其次，设计顺序栈类SeqStack 的构造函数。初始化一个空栈的算法如下： 顺序栈初始化算法 template void SeqStack:: SeqStack( ) { top=-1； } 最后，对建立的栈设计算法完成插入、删除、取栈顶元素等基本操作。 ⑴ 入栈算法 顺序栈入栈算法Push template void SeqStack::Push(T x) { if (top== StackSize-1) throw \上溢\ top++; data[top]=x; } ⑵ 出栈算法 顺序栈出栈算法Pop template T SeqStack:: Pop( ) { if (top==-1) throw \下溢\ x=data[top--]; return x; } ⑶ 取栈顶元素算法

取栈顶元素算法与出栈算法类似，只是注意不要修改栈顶指针top。 4. 实验程序

参见主教材随书光盘。

27 数据结构实验指导 3.1.2 队列操作验证

1. 实验目的

⑴ 掌握队列的链接存储结构； ⑵ 掌握队列的操作特性；

⑶ 掌握基于链队列的基本操作的实现方法。 2. 实验内容

⑴ 建立一个空队列；

⑵ 对已建立的队列进行插入、删除、取队头元素等基本操作。 3. 实现提示

首先，定义链队列的数据类型——链队列类LinkQueue，包括入队、出队、取队头元素等基本操作。

template class LinkQueue {

public:

LinkQueue( ); //构造函数，初始化一个空的链队列

~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队 T GetQueue( ); //取链队列的队头元素 private:

Node *front, *rear; //队头和队尾指针，分别指向头结点和终端结点 };

链队列的结点结构和单链表的结点结构相同，请参见2.1.2相关内容。 其次，设计构造函数和析构函数。

⑴ 构造函数（初始化一个空队列）的算法如下： 链队列构造函数算法LinkQueue template LinkQueue::LinkQueue( ) { s=new Node; s->next=NULL; //创建一个头结点s front=rear=s; //将队头指针和队尾指针都指向头结点s } ⑵ 析构函数的算法请读者仿照单链表类LinkList的析构函数自行设计。

最后，设计算法完成队列的入队（插入）、出队（删除）、取队头元素等基本操作。 ⑴ 入队算法

28 数据结构实验指导

链队列入队算法EnQueue

template void LinkQueue::EnQueue(T x) { s=new Node; s->data=x; //申请一个数据域为x的结点s s->next=NULL; rear->next=s; //将结点s插入到队尾

rear=s; }

⑵ 出队算法 链队列出队算法DeQueue template T LinkQueue::DeQueue( ) { if (rear==front) throw \下溢\p=front->next; x=p->data; //暂存队头元素 front->next=p->next; //将队头元素所在结点摘链 if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p; return x; } ⑶ 取队头元素算法

取队头元素算法与出队算法类似，只是不将队头元素删除。 4. 实验程序

参见主教材随书光盘。

3.1.3 串操作验证

1. 实验目的

⑴ 掌握串的顺序存储结构；

⑵ 掌握顺序串的基本操作的实现方法； ⑶ 掌握串的操作特点。 2. 实验内容

⑴ 创建两个串，并采用顺序存储；

⑵ 实现串的插入、删除、求子串等基本操作。 3. 实现提示

首先，定义两个串s1和s2，并存储一些字符，对已建立的串，设计算法完成插入、删除、比较等基本操作。

29 数据结构实验指导 ⑴ 串的插入操作Insert(char *s, int i, char *t)

在串s中将第i个字符至最后一个字符后移串t的长度，然后将串t插入。 ⑵ 串的删除操作Delete(char *s, int i, int len)

在串s中将第i+1个字符至最后一个字符前移len个位置。 ⑶ 求子串SubStr(char *s, int i, int len)

在串s中从第i个字符开始依次取len的字符，存入串t中，串t为所求子串。 4. 实验程序

参见主教材随书光盘。

3.2 设计实验

3.2.1 汗诺塔问题

1. 问题描述

汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 2. 基本要求

⑴ 设计数据结构，表示三座宝塔和n个盘子； ⑵ 输出每一次移动盘子的情况； ⑶ 分析算法的时间性能。 3. 设计思想

对于汉诺塔问题的求解，可以通过以下三个步骤实现： ⑴ 将塔A上的n-1个碟子借助塔C先移到塔B上。 ⑵ 把塔A上剩下的一个碟子移到塔C上。

⑶ 将n-1个碟子从塔B借助于塔A移到塔C上。

显然，这是一个递归求解的过程，当n=3时的求解过程如图3-1所示。 A CBCBA (a) (b) A BCBA C (c) (d) 图3-1 Hanoi求解示意图 30 数据结构实验指导 三座宝塔（塔A、塔B、塔C）分别用三个字符A、B、C来表示，n个盘子用从1开始的连续自然数编号。具体算法如下：

汉诺塔算法Hanoi

void Hanoi(int n, char A, char B, char C)

{ if (n==1) cout<<\?C\ //将碟子从A移到C上 else { Hanoi(n-1, A, C, B); cout<<\?C\ Hanoi(n-1, B, A, C);

} }

【思考题】你能设计一个非递归算法解决汉诺塔问题吗？

3.2.2 火车车厢重排问题

1. 问题描述

一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 ~ n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。

车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。 2. 基本要求

⑴ 设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨； ⑵ 设计并实现车厢重排算法； ⑶ 分析算法的时间性能。 3. 设计思想

假设有3个缓冲轨，入轨中有9节车厢，次序为5, 8, 1, 7, 4, 2, 9, 6, 3，重排后，9节厢出轨次序为9, 8, 7, 6, 5, 4, 3, 2, 1。重排过程如下：

3号车厢不能直接移至出轨（因为1号车厢和2号车厢必须排在3号车厢之前），因此，把3号车厢移至H1。6号车厢可放在H1中3号车厢之后（因为6号车厢将在3号车厢之后出轨）。9号车厢可以继续放在H1中6号车厢之后，而接下来的2号车厢不能放在9号车厢之后（因为2号车厢必须在9号车厢之前出轨）。因此，应把2号车厢移至H2。4号车厢可以放在H2中2号车厢之后，7号车厢可以继续放在4号车厢之后，如图3-2 (a)所示。至此，1号车厢可通过H3直接移至出轨，然后从H2移动2号车厢至出轨，从H1移动3号车厢至出轨，从H2移动4号车厢至出轨，如图 (b)所示。由于5号车厢此时仍在入轨中，

本文来源：https://www.bwwdw.com/article/5n1f.html