数组和广义表.docx

数组和广义表.docx

《数组和广义表.docx》由会员分享，可在线阅读，更多相关《数组和广义表.docx（98页珍藏版）》请在冰点文库上搜索。

数组和广义表

数据结构实验指导书

邢振祥

计算机应用教研室

第1章绪论

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

1.1实验的一般步骤

1.1.1概述

数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结构中要解决的问题更接近于实际。

数据结构的实验是对学生的一种全面的综合训练，与程序设计语言课程中的实验不同，数据结构课程中的实验多属创造性的活动，需要学生自己进行问题分析、进行数据结构和算法的设计、再上机调试和测试程序。

数据结构的实验是一种自主性很强的学习过程，其教学目的主要有两个：

⑴深化理解和掌握书本上的理论知识，将书本上的知识变“活”；⑵理论和实践相结合，使学生学会如何把书本上有关数据结构和算法的知识用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。

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

⑴验证实验：

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

⑵设计实验：

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

⑶综合实验：

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

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

在验证实验中，不要求但鼓励学生在完成实验任务的基础上，对该实验涉及的数据结构的其他实现方法进行探索。

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

虽然在设计实验和综合实验中都给出了一定的设计方案，但是，学生不应拘泥于这些分析和设计，要尽量发挥想象力和创造力。

对于一个实际问题，每个人可能会有不同的解决办法，本书给出的范例方案，只是希望把学生的思路引入正轨，提出了思考问题的方法，但是不希望限制学生的思维，鼓励学生自己设计解决方案。

1.1.2验证实验的一般步骤

验证实验安排的内容在书上都能找到具体的实现方法，并且在主教材的随书光盘中也都有相应的程序实现。

这些验证实验是学生在学习完一种数据结构后进行的，对于深化理解和掌握相应数据结构具有很重要的意义。

1.预备知识的学习

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

这需要学生有自主的学习意识和整理知识的能力。

2.上机前的准备

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

很多学生在上机时只带一本数据结构书或实验指导书，而书上只有算法设计而没有实验程序，于是就直接在键盘上输入程序，结果不仅程序的输入速度慢，而且编译后出现很多错误。

上机前的充分准备能高效利用机时，在有限的时间内完成更多的实验内容。

3.上机调试和测试程序

调试程序是一个辛苦但充满乐趣的过程，也是培养程序员素质的一个重要环节。

很多学生都有这样的经历：

化了好长时间去调试程序，错误却越改越多。

究其原因，一方面，是对调试工具不熟悉，出现了错误提示却不知道这种错误是如何产生的；另一方面，没有认识到努力预先避免错误的重要性，也就是对程序进行静态检查。

对程序进行测试，首先需要设计测试数据。

在数据结构中测试数据需要考虑两种情况：

⑴一般情况：

例如循环的中间数据、随机产生的数据等；⑵特殊情况：

例如循环的边界条件、数据结构的边界条件等。

4.实验报告

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

1.1.3设计实验和综合实验的一般步骤

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

1.问题分析

在设计实验和综合实验中的问题描述通常都很简洁，因此，首先要充分理解问题，明确问题要求做什么，限制条件是什么，也就是对所需完成的任务做出明确的描述。

例如：

输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围以及输入的形式；哪些属于非法输入，等等。

在问题分析时还应该准备好测试数据。

2.概要设计

概要设计是对问题描述中涉及到的数据定义抽象数据类型，设计数据结构，设计算法的伪代码描述。

在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单，抽象数据类型尽可能做到数据封闭，基本操作的说明尽可能明确。

而不必过早地考虑存储结构，不必过早地考虑语言的实现细节，不必过早地表述辅助数据结构和局部变量。

3.详细设计

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

此外，还要设计一定的用户界面。

数据结构课程实验的主要目的是为了培养数据结构的应用能力，因此在实验中不要求图形界面，只需要在屏幕上提示用户每一步操作的输入、将结果输出即可。

4.编码实现和静态检查

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

很多初学者在编写程序后都有这样的心态：

确信自己的程序是正确的，认为上机前的任务已经完成，检查错误是计算机的事。

这种心态是极为有害的，这样的上机调试效率是极低的。

事实上，即使有几十年经验的高级软件工程师，也经常利用静态检查来查找程序中的错误。

5.上机调试和测试程序

掌握调试工具，设计测试数据，上机调试和测试程序。

调试正确后，认真整理源程序和注释，给出带有完整注释且格式良好的源程序清单和结果。

6.总结并整理实验报告

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

1.2设计实验

1.2.1在数组中求最小值

1.问题描述

已知一个数组，求该数组中值最小的元素。

2.基本要求

⑴对于由确定元素组成的数组（即在程序中直接赋值），实现求最小值；

⑵随机生成数组元素（即由机器生成随机数），实现求最小值；

⑶分析算法的时间性能。

3.设计思想

我们都知道“打擂台”这个名词，它的意思是说，如果有若干人比武，先有一个人站在台上，再上去一个人与其交手，败者下台，胜者留在台上。

如此下去，直到所有人都上台比过为止，最后留在台上的就是胜者。

按照这个思路，首先把数组a[0]的值赋给变量min，min就是开始时的擂主，然后让下一个元素与它比较，将二者中值较小者保存在min中，直到数组中所有元素都比完为止。

最后min中保存的就是数组中所有元素的最小值。

4.算法描述

下面给出具体的在以个整型数组中求最小值的算法。

【思考题】⑴在数组中求最大值和最小值，要求算法有较好的时间性能；

⑵在数组中求最大值和次最大值，要求算法有较好的时间性能。

1.2.2统计候选人得票

1.问题描述

设有n个候选人参加选举，统计每个候选人最后的得票情况。

2.基本要求

⑴以数组作为存储结构；

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

3.设计思想

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

constintn=10;//假设有10个人参加选举

structPerson

{

char*name;

intcount;

}Leader[n];

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

4.算法描述

【思考题】将该问题用C++中的类实现。

1.3综合实验

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

1.问题描述

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

2.基本要求

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

⑵求出最好、最坏、平均情况下待查值与数组元素的实际比较次数；

⑶总结实验结果，给出结论。

3.设计思想

所谓顺序查找就是从数组的第一个元素开始，依次比较每一个元素与待查值是否相等。

为了测算待查值与数组元素的实际比较次数，需要在算法中设置计算比较次数的累加器count，算法结束后输出其值。

4.算法描述

【思考题】⑴如果考虑查找失败的情况，应如何修改算法？

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

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

1.问题描述

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

2.基本要求

⑴采用模板函数实现；

⑵至少采用两种方法求解；

⑶分析不同算法的时间性能。

3.设计思想

方法一：

采用起泡排序，将数组中的所有元素排序，然后输出第k个元素。

起泡排序的基本思想是：

两两比较相邻元素，如果反序则交换，直到全部元素都排好序为止。

该算法的时间性能是Ｏ（n2）。

方法二：

采用选择排序，当找出第k小元素后，不再进行排序过程。

选择排序的基本思想是：

第i趟排序通过n-i次关键码的比较，在n-i+1（1≤i≤n-1）个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。

该算法的时间性能是Ｏ（k×n）。

【思考题】你还能设计出其他算法吗？

自行设计另外一种方法，并分析其时间性能。

第2章线性表

线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。

通过本章的验证实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础。

通过本章的设计实验和综合实验，进一步培养以线性表作为数据结构解决实际问题的应用能力。

2.1验证实验

2.1.1顺序表操作验证

1.实验目的

⑴掌握线性表的顺序存储结构；

⑵验证顺序表及其基本操作的实现；

⑶掌握数据结构及算法的程序实现的基本方法。

2.实验内容

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

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

3.实现提示

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

constintMaxSize=10;

template//定义模板类SeqList

classSeqList

{

public:

SeqList（）{length=0;}//无参构造函数

SeqList（Ta[],intn）;//有参构造函数

voidInsert（inti,Tx）;//在线性表中第i个位置插入值为x的元素

TDelete（inti）;//删除线性表的第i个元素

intLocate（Tx）;//按值查找，求线性表中值为x的元素序号

voidPrintList（）;//遍历线性表，按序号依次输出各元素

private:

Tdata[MaxSize];//存放数据元素的数组

intlength;//线性表的长度

};

其次，建立含有n个数据元素的顺序表，即设计构造函数。

算法如下：

最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。

⑴插入算法

⑵删除算法

⑶查找算法

4.实验程序

//以下为头函数，文件名为SeqList.h

#ifndefSeqList_H

#defineSeqList_H

constintMaxSize=100;//100只是示例性的数据，可以根据实际问题具体定义

template//定义模板类SeqList

classSeqList

{

public:

SeqList（）{length=0;}//无参构造函数，创建一个空表

SeqList（Ta[],intn）;//有参构造函数

voidInsert（inti,Tx）;//在线性表中第i个位置插入值为x的元素

TDelete（inti）;//删除线性表的第i个元素

intLocate（Tx）;//按值查找，求线性表中值为x的元素序号

voidPrintList（）;//遍历线性表，按序号依次输出各元素

private:

Tdata[MaxSize];//存放数据元素的数组

intlength;//线性表的长度

};

#endif

//以下为SeqList类中成员函数的定义部分，文件名为SeqList.cpp

#include"SeqList.h"

template

SeqList:

:

SeqList（Ta[],intn）

{

if（n>MaxSize）throw"参数非法";

for（inti=0;i

data[i]=a[i];

length=n;

}

template

voidSeqList:

:

Insert（inti,Tx）

{

if（length>=MaxSize）throw"上溢";

if（i<1||i>length+1）throw"位置";

for（intj=length;j>=i;j--）

data[j]=data[j-1];//注意第j个元素存在数组下标为j-1处

data[i-1]=x;

length++;

}

template

TSeqList:

:

Delete（inti）

{

if（length==0）throw"下溢";

if（i<1||i>length）throw"位置";

Tx=data[i-1];

for（intj=i;j

data[j-1]=data[j];//注意此处j已经是元素所在的数组下标

length--;

returnx;

}

template

intSeqList:

:

Locate（Tx）

{

for（inti=0;i

if（data[i]==x）returni+1;//下标为i的元素等于x，返回其序号i+1

return0;//退出循环，说明查找失败

}

template

voidSeqList:

:

PrintList（）

{

for（inti=0;i

cout<

}

//以下为主函数

#include//引用输入输出流库函数的头文件

#include"SeqList.cpp"//引用顺序表的类声明和定义

voidmain（）

{

intr[]={1,2,3,4,5};

SeqLista（r,5）;

cout<<"执行插入操作前数据为：

"<

a.PrintList（）;//输出所有元素

try

{

a.Insert（2,3）;

}

catch（char*s）

{

cout<

}

cout<<"执行插入操作后数据为：

"<

a.PrintList（）;//输出所有元素

cout<<"值为3的元素位置为:

";

cout<

cout<<"执行删除第一个元素操作，删除前数据为：

"<

a.PrintList（）;//输出所有元素

try

{

a.Delete

（1）;//删除元素1

}

catch（char*s）

{

cout<

}

cout<<"删除后数据为：

"<

a.PrintList（）;//输出所有元素

}

2.1.2单链表操作验证

1.实验目的

⑴掌握线性表的链接存储结构；

⑵验证单链表及其基本操作的实现；

⑶进一步掌握数据结构及算法的程序实现的基本方法。

2.实验内容

⑴用头插法（或尾插法）建立带头结点的单链表；

⑵对已建立的单链表实现插入、删除、查找等基本操作。

3.实现提示

首先，将单链表中的结点定义为如下结构类型：

template

structNode

{

Tdata;

Node*next;

};

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

template

classLinkList

{

public:

LinkList（Ta[],intn）;//建立有n个元素的单链表

~LinkList（）;//析构函数

voidInsert（inti,Tx）;//在单链表中第i个位置插入元素值为x的结点

TDelete（inti）;//在单链表中删除第i个结点

intLocate（Tx）;//求单链表中值为x的元素序号

voidPrintList（）;//遍历单链表，按序号依次输出各元素

private:

Node*first;//单链表的头指针

};

再次，设计单链表类LinkList的构造函数和析构函数。

⑴用头插法或尾插法建立单链表。

头插法建立单链表的算法如下：

⑵析构函数用于释放单链表中所有结点，算法如下：

最后，对所建立的单链表设计插入、删除、查找等基本操作的算法。

⑴插入算法

⑵删除算法

⑶查找算法

4.实验程序

//以下为头函数，文件名为LinkList.h

#ifndefLinkList_H

#defineLinkList_H

template

structNode

{

Tdata;

Node*next;//此处也可以省略

};

template

classLinkList

{

public:

LinkList（Ta[],intn）;//建立有n个元素的单链表

~LinkList（）;//析构函数

voidInsert（inti,Tx）;//在单链表中第i个位置插入元素值为x的结点

TDelete（inti）;//在单链表中删除第i个结点

intLocate（Tx）;//求单链表中值为x的元素序号

voidPrintList（）;//遍历单链表，按序号依次输出各元素

private:

Node*first;//单链表的头指针

};

#endif

//以下为头函数LinkList.h中LinkList类的成员函数的定义，文件名为LinkList.cpp

#include"LinkList.h"

template

LinkList:

:

LinkList（Ta[],intn）

{

first=newNode;

first->next=NULL;//初始化一个空链表

for（inti=0;i

{

Node*s;

s=newNode;s->data=a[i];//为每个数组元素建立一个结点

s->next=first->next;//插入到头结点之后

first->next=s;

}

}

template

LinkList:

:

~LinkList（）

{

Node*p,*q;

p=first;//工作指针p初始化

while（p）//释放单链表的每一个结点的存储空间

{

q=p;//暂存被释放结点

p=p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开

deleteq;

}

}

template

voidLinkList:

:

Insert（inti,Tx）

{

Node*p;intj;

p=first;j=0;//工作指针p初始化

while（p&&j

{

p=p->next;//工作指针p后移

j++;

}

if（!

p）throw"位置";

else{

Node*s;

s=newNode;

s->data=x;//向内存申请一个结点s，其数据域为x

s->next=p->next;//将结点s插入到结点p之后

p->next=s;

}

}

template

TLinkList:

:

Delete（inti）

{

Node*p;intj;

p=first;j=0;//工作指针p初始化

while（p&&j

{

p=p->next;

j++;

}

if（!

p||!

p->next）throw"位置";//结点p不存在或结点p的后继结点不存在

else{

Node*q;intx;

q=p->next;x=q->data;//暂存被删结点

p->next=q->next;//摘链

deleteq;

returnx;

}

}

template

intLinkList:

:

Locate（Tx）

{

Node*p;intj;

p=first->next;j=1;

while（p&&p->data!

=x）

{

p=p->next;

j++;

}

if（p）returnj;

else