数据结构（c++版）实验参考书

前 言

《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的

更好的理解算法的思想、培养编程能力。 二、实验要求

1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现

象，取消本次上机资格，平时成绩扣10分。

6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。 三、实验环境 Qt或 VC++6.0 四、说明

1、本实验的所有算法中元素类型可以根据实际需要选择。

2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。

3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。 五、实验报告的书写要求 1．明确实验的目的及要求； 2．记录实验的输入数据和输出结果； 3．说明实验中出现的问题和解决过程；

4．写出实验的体会和实验过程中没能解决的问题； 六、参考书目

《数据结构》（C++语言描述） 王红梅等 清华大学出版社

《DATA STRUCTURE WITH C++》 William Ford,William Topp

清华大学出版社（影印版）

实验一 线性表的操作

实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的：

参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。 二、实验要求：

1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容：

1．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，?，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。

2．设计一个带头结点的单链表类，要求：

(1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。 3．设计一个不带头结点的单链表类，要求：

(1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为

k的元素、取数据元素。

(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其

他位置插入和删除其他位置结点时的不同情况。)

(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。 4．设计一个带头结点的循环单链表类，实现约瑟夫环问题；

问题描述：设编号为1,2,?，n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。

测试数据：

n=7,7个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20

*5．设计一个带头结点的循环双向链表类，要求：

(1)带头结点循环双向链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素。

(2)设计一个测试主函数，实际运行验证所设计循环双向链表类的正确性。 *6．设计一个单链表实现一元多项式求和问题。要求：

（1）设计存储结构表示一元多项式； （2）设计算法实现一元多项式相加。

四、程序样例

顺序表类定义：将该类保存在文件SeqList.h中。

const int MaxSize=100; //100只是示例性的数据，可根据实际问题具体定义 template //定义模板类SeqList class SeqList {

public:

SeqList( ) {length=0;} //无参构造函数 SeqList(T a[ ], int n); //有参构造函数 ~SeqList( ) { } //析构函数为空 int Length( ) {return length;} //求线性表的长度

T Get(int i); //按位查找，取线性表的第i个元素 int Locate(T x ); //按值查找，求线性表中值为x的元素序号 void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素

void PrintList( ); //遍历线性表，按序号依次输出各元素 private:

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

template

SeqList:: SeqList(T a[ ], int n) {

if (n>MaxSize) throw \参数非法\ for (i=0; i

template T SeqList::Get(int i) {

if (i<1 && i>length) throw \查找位置非法\ else return data[i-1]; }

template int SeqList::Locate(T x) {

for (i=0; i

if (data[i]==x) return i+1; //下标为i的元素等于x，返回其序号i+1 return 0; //退出循环，说明查找失败 }

template

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++;

}

template T SeqList::Delete(int i) {

if (length==0) throw \下溢\ if (i<1 | | i>length) throw \位置\ x=data[i-1];

for (j=i; j

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

链表类定义：将该类保存在文件LinkList.h中。 template struct Node {

T data;

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

}

template class LinkList {

public:

LinkList( ){first=new Node; first->next=NULL;} //建立只有头结点的空链表 LinkList(T a[ ], int n); //建立有n个元素的单链表 ~LinkList( ); //析构函数

int Length( ); //求单链表的长度

T Get(int i); //取单链表中第i个结点的元素值 int Locate(T x); //求单链表中值为x的元素序号

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

void PrintList( ); //遍历单链表，按序号依次输出各元素 private:

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

template LinkList:: ~LinkList( ) {

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

while (p) //释放单链表的每一个结点的存储空间 {

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

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

template T LinkList::Get(int i) {

p=first->next; j=1; //或p=first; j=0; while (p && j

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

if (!p) throw \位置\ else return p->data; }

template

void LinkList::Insert(int i, T x) {

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

while (p && j

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

if (!p) throw \位置\else {

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

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

}

template T LinkList::Delete(int i) {

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

while (p && j

p=p->next; j++; }

if (!p | | !p->next) throw \位置\ //结点p不存在或结点p的后继结点不存在 else {

q=p->next; x=q->data; //暂存被删结点 p->next=q->next; //摘链 delete q; return x; } }

template

LinkList:: LinkList(T a[ ], int n) {

first=new Node;

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

{

s=new Node; s->data=a[i]; //为每个数组元素建立一个结点 s->next=first->next; //插入到头结点之后 first->next=s; } }

template

LinkList:: LinkList(T a[ ], int n) {

first=new Node; //生成头结点 r=first; //尾指针初始化 for (i=0; i

s=new Node; s->data=a[i]; //为每个数组元素建立一个结点 r->next=s; r=s; //插入到终端结点之后 }

r->next=NULL; //单链表建立完毕，将终端结点的指针域置空 }

1．#include #include void main( )

{ int r[ ]={1,2,3,4,5,6,7,8,9,10}; SeqList a(r,50);

cout<<”执行删除操作前数据为：”<

cout<<”执行删除操作后数据为：”<

#include #include

void divid( LinkList &L) { Node *p,*q,*h; h=new Node( );

p=L.first->next; q=L.first; while (p)

{ if(p->data%2!=0) { q=p; p=p->next;}

else {q=p; p=p->next; q-next=h.first->next; h.first->next=q;} }

p=L.first->next; while(p->next!=Null) {p=p->next; }

p->next= h.first->next; delete h; }

void main( )

{ int r[ ]={1,-2,3,-4,-5,6,-7,8,9,10}; LinkList List(r, 10);

cout<<”执行操作前数据为：”<

divid (List);

cout<<”执行操作后数据为：”<

List.PrintList( ); }

6．void Add(LinkList &A, LinkList B) {

pre=A.first; p=pre->next; //工作指针p初始化，指针pre始终指向p的前驱结点 qre=B.first; q=qre->next; //工作指针q初始化，指针qre始终指向q的前驱结点 while（p&&q） {

if (p->expexp) { //第1种情况 pre=p; p=p->next; }

else if (p->exp>q->exp) { //第2种情况，将结点q插入到结点p之前 v=q->next; pre->next=q; q->next=p; q=v; }

else { //第3种情况

p->coef =p->coef+q->coef; //系数相加

if (p->coef ==0) { //系数为0，删除结点p和结点q pre->next=p->next; //删除结点p delete p; p=pre->next; }

else { //系数不为0，只删除结点q pre=p; p=p->next; }

qre->next=q->next //删除结点q delete q; q=qre->next; }

if (q) pre->next=q; //将结点q链接在第一个单链表的后面 delete B.first; //释放第二个单链表的头结点所占的内存 }

实验二 栈、队列、串的操作

实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的：

参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。 二、实验要求：

1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容：

1. 堆栈类测试和应用问题。要求：

(1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依

次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。

(2)定义数据元素的数据类型为如下形式的结构体：

typedef struct

{ char taskname[10];//任务名 int taskno; //任务号

｝DataType；

设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5

个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 2. 队列类测试和应用问题。要求：

设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依

次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。 3．设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较

结果有大于、等于和小于三种情况。

*4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。 *5. 设计串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，

即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回０。并要求设计主函数进行测试。

一个测试例子为：S＝”I am a student”，T=”student”，V=”teacher “。 四、程序样例

1． 顺序栈类的定义

const int StackSize=10; //10只是示例性的数据，可以根据实际问题具体定义 template //定义模板类SeqStack

class SeqStack {

public:

SeqStack( ) {top=-1;} //构造函数，栈的初始化 ~SeqStack( ) { } //析构函数 void Push( T x ); //将元素x入栈 T Pop( ); //将栈顶元素弹出

T GetTop( ) {if (top!=-1) return data[top];} //取栈顶元素（并不删除） bool Empty( ) {top==-1? return 1: return 0;} //判断栈是否为空 private:

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

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

template

void SeqStack::Push(T x) {

if (top== StackSize-1) throw \上溢\ top++;

data[top]=x; }

template T SeqStack:: Pop( ) {

if (top==-1) throw \下溢\ x=data[top--]; return x; }

2． 链式栈类的定义

template class LinkStack {

public:

LinkStack( ) {top=NULL;} //构造函数，置空链栈

~LinkStack( ); //析构函数，释放链栈中各结点的存储空间 void Push(T x); //将元素x入栈 T Pop( ); //将栈顶元素出栈

T GetTop( ) {if (top!=NULL) return top->data;} //取栈顶元素（并不删除） bool Empty( ) {top==NULL? return 1: return 0;} //判断链栈是否为空栈 private:

Node *top; //栈顶指针即链栈的头指针 };

template

void LinkStack::Push(T x) {

s=new Node; s->data=x; //申请一个数据域为x的结点s s->next=top; top=s; //将结点s插在栈顶 }

template

T LinkStack::Pop( ) {

if (top==NULL) throw \下溢\

x=top->data; //暂存栈顶元素 p=top; top=top->next; //将栈顶结点摘链 delete p; return x; }

template

LinkStack::~LinkStack( ) {

while (top) {

p=top->next; delete top; top=p; } }

3．双栈类的定义

const int StackSize=100; //100只是示例数据，需根据具体问题定义 template class BothStack {

public:

BothStack( ) {top1= -1; top2=StackSize;} //构造函数，将两个栈分别初始化 ~BothStack( ) { } //析构函数

void Push(int i, T x); //将元素x压入栈i T Pop(int i); //对栈i执行出栈操作 T GetTop(int i); //取栈i的栈顶元素 bool Empty(int i); //判断栈i是否为空栈 private:

T data[StackSize]; //存放两个栈的数组

int top1, top2; //两个栈的栈顶指针，分别指向各自的栈顶元素在数组中的下标 };

template

void BothStack:: Push(int i, T x ) {

if (top1==top2-1) throw \上溢\if (i==1) data[++top1]=x; if (i==2) data[--top2]=x; }

template

T BothStack:: Pop(int i) {

if (i==1) { //将栈1的栈顶元素出栈

if (top1== -1) throw \下溢\

return data[top1--]; }

if (i==2) { //将栈2的栈顶元素出栈

if (top2==StackSize) throw ''下溢\

return data[top2++]; } }

4.循环队列类定义

const int QueueSize=100; //定义存储队列元素的数组的最大长度 template //定义模板类CirQueue class CirQueue {

public:

CirQueue( ) {front=rear=0;} //构造函数，置空队 ~ CirQueue( ) { } //析构函数 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队

T GetQueue( ); //取队头元素（并不删除）

bool Empty( ) {front==rear? return 1: return 0;} //判断队列是否为空 private:

T data[QueueSize]; //存放队列元素的数组

int front, rear; //队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置 };

template

void CirQueue::EnQueue(T x) {

if ((rear+1) % QueueSize ==front) throw \上溢\

rear=(rear+1) % QueueSize; //队尾指针在循环意义下加1 data[rear]=x; //在队尾处插入元素 }

template

T CirQueue::GetQueue( ) {

if (rear==front) throw \下溢\

i=(front+1) % QueueSize; //注意不要给队头指针赋值 return data[i];

}

template

T CirQueue::DeQueue( ) {

if (rear==front) throw \下溢\

front=(front+1) % QueueSize; //队头指针在循环意义下加1

return data[front]; //读取并返回出队前的队头元素，注意队头指针 }

5.链队列类定义

template class LinkQueue {

public:

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

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

T GetQueue( ) {if (front!=rear) return front->next->data;} //取链队列的队头元素 bool Empty( ) {front==rear? return 1: return 0;} //判断链队列是否为空

private:

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

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; }

template

LinkQueue::LinkQueue( ) {

s=new Node; s->next=NULL; //创建一个头结点s

front=rear=s; //将队头指针和队尾指针都指向头结点s

}

template

void LinkQueue::EnQueue(T x) {

s=new Node; s->data=x; //申请一个数据域为x的结点s s->next=NULL;

rear->next=s; //将结点s插入到队尾 rear=s; } 注意问题

1．重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。 2．栈、队列的算法是后续实验的基础（树、图、查找、排序等）。

实验三 多维数组和广义表的操作

实验类型：验证性 实验要求：必修 实验学时： 2学时

一、实验目的：参照给定的多维数组类和广义表类的程序样例，验证给出的多维数组和广义表的常见算法，并实现有关的操作。 二、实验要求：

1、掌握多维数组和广义表的特点。掌握它们的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容：

1.设计函数建立一个n*n阶的对称矩阵。要求：

（1）实现将对称矩阵用一维数组存储输出。 （2）实现矩阵转置算法。 （3）实现魔方阵算法。

(4)设计一个测试例子，并编写主程序进行测试。 2．采用链式存储结构设计广义表类，实现以下操作： （1）创建广义表，取广义表的表头元素和表尾元素； （2）求广义表的深度。 四、程序样例

1．稀疏矩阵结构类型声明

const int MaxTerm=100; struct SparseMatrix {

element data[MaxTerm];

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

template ruct element {

int row, col; T item

};

2．稀疏矩阵转置算法Trans1

void Trans1(SparseMatrix A, SparseMatrix &B) {

B.mu=A.nu; B.nu=A.mu; B.tu=A.tu; //设置行数、列数、非零元素个数 if (B.tu>0) { //有非零元素则转换

pb=0;

for (col=0; col

for (pa=0; pa

}

}

3．稀疏矩阵转置算法Trans2

void Trans2(SparseMatrix A, SparseMatrix &B)

{

B.mu=A.nu; B.nu=A.mu; B.tu=A.tu; //设置行数、列数、元素个数 if (B.tu>0) { //有非零元素则转换

for (i=0; i

num[i]=0;

for (i=0; i

j= A.data[i].col; //取三元组的列号 num[j]++; }

cpot[0]=0; //A中第0列第一个非零元素在B中的位置为0

for (i=1; i

cpot[i]= cpot[i-1]+num[i-1];

for (i=0; i

j=A.data[i].col; //当前三元组的列号

k=cpot[j]; //当前三元组在B中的下标 B.data[k].row= A.data[i].col ; B.data[k].col= A.data[i].row ;

B.data[k].item= A.data[i].item;

cpot[j]++; //预置同一列的下一个三元组的下标 } }

}

4．魔方阵

void Square(int a[ ][ ], int n) {

p=0; q=(n-1)/2;

a[0][q]=1; //在第0行的中间位置填1 for (i=2; i<=n*n, i++) {

p=(p-1+n) % n; //求i所在行号 q=(q-1+n) % n; //求i所在列号

if (a[p][q]>0) p=(p+1) % n; //如果位置(p, q)已经有数，填入同一列下一行 a[p][q]=i; } }

5.广义表类定义

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

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

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

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

} ptr; }; };

template class Lists {

public:

Lists( ) {ls=NULL;} //无参构造函数，初始化为空的广义表

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

int Depth(GLNode *ls); //求广义表的深度 GLNode *Head( ); //求广义表的表头 GLNode *Tail( ); //求广义表的表尾 private:

GLNode *ls; //ls是指向广义表的头指针 };

template

Lists::Lists(Lists ls1,Lists ls2) {

ls = new GLNode ls->tag = 1; ls->ptr.hp = ls1; ls->ptr.tp = ls2; }

6．求广义表深度算法Depth template

int Lists::Depth(GLNode *ls) {

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 }

7．取广义表表头算法Head

template

GLNode * Lists::Head( )

{

return ls->ptr.hp;

}

8．取广义表表尾算法Tail

template

GLNode *Lists::Tail( ) {

return ls-> ptr.tp;

}

实验四 树和二叉树

实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的：

参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。

二、实验要求：

1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容：

1．设计实现二叉树类，要求：

（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。 （2）实现二叉树层次遍历的非递归算法。 （3）编写一主函数来验证算法实现。

2. 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶

子结点，并统计叶子结点个数。 *3. 设计实现二叉线索链表类，要求：

（1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。

（2）编写一主函数来验证算法实现。 *4. 编写求二叉树高度的函数。

*5. 编写创建哈夫曼树和生成哈夫曼编码的算法。

*6．假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点

到根结点的路径。

*7．假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）

四、程序样例

１．二叉树 二叉链表结点声明 template struct BiNode {

T data;

BiNode *lchild, *rchild; };

二叉链表类声明

template class BiTree {

public:

BiTree( ){root=NULL;} //无参构造函数，初始化一棵空的二叉树

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

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

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

二叉树的层序遍历算法LeverOrder template

void BiTree::LeverOrder(BiNode *root) {

front=rear=0; //采用顺序队列，并假定不会发生上溢 if (root==NULL) return; Q[++rear]=root; while (front!=rear) {

q=Q[++front]; cout<data;

if (q->lchild!=NULL) Q[++rear]=q->lchild; if (q->rchild!=NULL) Q[++rear]=q->rchild; } }

二叉树的构造函数算法BiTree template

BiTree ::BiTree(BiNode *root) {

creat(root)； }

template

void BiTree ::Creat(BiNode *root) {

cin>>ch;

if (ch=='# ') root=NULL; //建立一棵空树 else {

root=new BiNode; //生成一个结点 root->data=ch;

Creat(root->lchild); //递归建立左子树 Creat(root->rchild); //递归建立右子树 }

}

二叉树的后序遍历递归算法PostOrder

template

void BiTree::PostOrder(BiNode *root) {

if (root==NULL) return; //递归调用的结束条件 else {

PostOrder(root->lchild); //后序递归遍历root的左子树

PostOrder(root->rchild); //后序递归遍历root的右子树 cout<data; //访问根结点的数据域

}

}

二叉树的后序遍历非递归算法PostOrder

template

void BiTree::PostOrder(BiNode *root) {

top= -1; //采用顺序栈，并假定栈不会发生上溢 while (root!=NULL | | top!= -1) {

while (root!=NULL) {

top++;

s[top].ptr=root; s[top].flag=1;

root=root->lchild;

}

while (top!= -1 && s[top].flag==2) {

root=s[top--].ptr; cout<data; }

if (top!= -1) {

s[top].flag=2;

root=s[top].ptr->rchild; }

} }

二叉树前序遍历递归算法PreOrder

template

void BiTree::PreOrder(BiNode *root) {

if (root ==NULL) return; //递归调用的结束条件 else {

cout<data; //访问根结点的数据域

PreOrder(root->lchild); //前序递归遍历root的左子树

PreOrder(root->rchild); //前序递归遍历root的右子树 }

}

二叉树的前序遍历非递归算法PreOrder

template

void BiTree::PreOrder(BiNode *root) {

top= -1; //采用顺序栈，并假定不会发生上溢 while (root!=NULL | | top!= -1)

{

while (root!= NULL) {

cout<data; s[++top]=root;

root=root->lchild; }

if (top!= -1) {

root=s[top--];

root=root->rchild; } } }

二叉树的析构函数算法BiTree

template

BiTree ::~BiTree(BiNode *root) {

Release(root); }

void BiTree ::Release(BiNode *root) {

if (root!=NULL) {

Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } }

二叉树的中序遍历递归算法InOrder

template

void BiTree::InOrder (BiNode *root) {

if (root==NULL) return; //递归调用的结束条件

else {

InOrder(root->lchild); //中序递归遍历root的左子树

cout<data; //访问根结点的数据域

InOrder(root->rchild); //中序递归遍历root的右子树

} }

２．线索链表

线索链表结点声明

enum flag {Child, Thread}; //枚举类型，枚举常量Child=0，Thread=1 template struct ThrNode {

T data;

ThrNode *lchild, *rchild; flag ltag, rtag; };

线索链表类声明 template class InThrBiTree

{

public:

InThrBiTree(ThrNode * root); //构造函数，建立中序线索链表 ~ InThrBiTree( ); //析构函数，释放线索链表中各结点的存储空间 ThrNode *Next(ThrNode *p); //查找结点p的后继 void InOrder(ThrNode *root); //中序遍历线索链表 private:

ThrNode *root; //指向线索链表的头指针

void Creat(ThrNode *root); //构造函数调用

void ThrBiTree(ThrNode *root); //构造函数调用 };

中序线索链表构造函数算法InThrBiTree template

InThrBiTree::InThrBiTree(ThrNode *root) {

Creat(root); pre=NULL;

ThrBiTree(root); }

template

void InThrBiTree ::Creat(ThrNode *root) {

cin>>ch;

if (ch=='# ') root=NULL; //建立一棵空树 else {

root=new ThrNode; //生成一个结点，左右标志均置0 root->data=ch; root->ltag=0; root->rtag=0; Creat(root->lchild); //递归建立左子树 Creat(root->rchild); //递归建立右子树 } }

template

void InThrBiTree ::ThrBiTree(ThrNode *root) {

if (root==NULL) return;

ThrBiTree(root->lchild);

if (!root->lchild) { //对root的左指针进行处理

root->ltag=1;

root->lchild=pre; //设置pre的前驱线索

}

if (!root->rchild) root->rtag=1; //对root的右指针进行处理 if (pre->rtag==1) pre->rchild=root; //设置pre的后继线索 pre=root;

ThrBiTree(root->rchild); }

中序线索链表查找后继的算法Next template

ThrNode *InThrBiTree::Next(ThrNode *p) {

if (p->rtag==1) q=p->rchild; //右标志为1，可直接得到后继结点

else {

q=p->rchild; //工作指针初始化， while (q->ltag==0) //查找最左下结点 q=q->lchild; }

return q; }

中序线索链表查找后继的算法Next template

void InThrBiTree::InOrder(ThrNode *root) {

if (root==NULL) return; //如果线索链表为空，则空操作返回 p=root;

while (p->ltag==0) //查找中序遍历序列的第一个结点p并访问 p=p->lchild; cout<data;

while (p->rchild!=NULL) //当结点p存在后继，依次访问其后继结点 {

p=Next(p); cout<data; } }

中序线索链表构造函数算法InThrBiTree template

InThrBiTree::InThrBiTree(ThrNode *root) {

Creat(root); pre=NULL;

ThrBiTree(root); }

template

void InThrBiTree ::Creat(ThrNode *root) {

cin>>ch;

if (ch=='# ') root=NULL; //建立一棵空树 else {

root=new ThrNode; //生成一个结点，左右标志均置0 root->data=ch; root->ltag=0; root->rtag=0; Creat(root->lchild); //递归建立左子树 Creat(root->rchild); //递归建立右子树 } }

template

void InThrBiTree ::ThrBiTree(ThrNode *root) {

if (root==NULL) return;

ThrBiTree(root->lchild);

if (!root->lchild) { //对root的左指针进行处理

root->ltag=1;

root->lchild=pre; //设置pre的前驱线索

}

if (!root->rchild) root->rtag=1; //对root的右指针进行处理 if (pre->rtag==1) pre->rchild=root; //设置pre的后继线索 pre=root;

ThrBiTree(root->rchild); }

３．哈夫曼树

void HuffmanTree(element huffTree[ ], int w[ ], int n ) {

for (i=0; i<2*n-1; i++) //初始化 {

huffTree [i].parent= -1; huffTree [i].lchild= -1; huffTree [i].rchild= -1;

}

for (i=0; i

for (k=n; k<2*n-1; k++) //n-1次合并 {

Select(huffTree, i1, i2); //在huffTree中找权值最小的两个结点i1和i2 huffTree[i1].parent=k; //将i1和i2合并，则i1和i2的双亲是k huffTree[i2].parent=k;

huffTree[k].weight= huffTree[i1].weight+huffTree[i2].weight; huffTree[k].lchild=i1; huffTree[k].rchild=i2; } } 注意问题

1．注意理解有关树的各种递归算法的执行步骤。

2．注意字符类型数据在输入时的处理。 3．重点理解如何利用栈结构实现非递归算法。

实验五 图的有关操作

实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的：

参照给定的图类的程序样例，验证给出的有关图的常见算法，并实现有关的操作。 二、实验要求：

1、掌握图的特点，利用图的邻接矩阵和邻接表的存储结构实现图的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容：

1. 设计邻接矩阵图类，实现如下操作： （1）测试类中的成员函数； （2）实现拓扑排序算法； （3）实现最小生成树算法； （4）实现最短路径算法；

（5）设计主函数，输入数据，测试各算法。

2. 设计邻接表类，实现无向图的深度优先非递归遍历、无向图的广度优先遍历，并设计主函数输入数据进行测试。

*3.假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到顶点v的长度为l的所有简单路径。

四、程序样例：

1.图的邻接表类的定义

struct ArcNode //定义边表结点

{

int adjvex; //邻接点域 ArcNode *next; };

template

struct VertexNode //定义顶点表结点 {

T vertex;

ArcNode *firstedge;

};

const int MaxSize=10; //图的最大顶点数 template class ALGraph {

public:

ALGraph(T a[ ], int n, int e); //构造函数，初始化一个有n个顶点e条边的图 ~ALGraph; //析构函数，释放邻接表中各边表结点的存储空间 T GetVex(int i); //取图中第i个顶点数据信息

void PutVex(int i, T value); //将图中第i个顶点的数据域置为value

void InsertVex(int i, T value); //在图中插入一个顶点，其编号为i，值为value

void DeleteVex(int i); //删除图中第i个顶点

void InsertArc(int i, int j); //在图中插入一条边，其依附的两个顶点的编号为i和j void DeleteArc(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private:

VertexNode adjlist[MaxSize]; //存放顶点表的数组 int vertexNum, arcNum; //图的顶点数和边数 };

template

ALGraph::ALGraph(T a[ ], int n, int e) {

vertexNum=n; arcNum=e;

for (i=0; i

adjlist[i].vertex=a[i];

adjlist[i].firstedge=NULL; }

for (k=0; k

cin>>i>>j; //输入边所依附的两个顶点的序号

s=new ArcNode; s->adjvex=j; //生成一个边表结点s s->next=adjlist[i].firstedge; //将结点s插入到结点i的边表的表头

adjlist[i].firstedge=s; }

}

template

void ALGraph::DFSTraverse(int v) {

cout<

while (p) //依次搜索顶点v的邻接点j {

j=p->adjvex;

if (visited[j]==0) DFSTraverse(j);

p=p->next; } }

template

void ALGraph::BFSTraverse(int v)

{

front=rear=-1; //初始化队列, 假设队列采用顺序存储且不会发生溢出

cout<

v=Q[++front];

p=adjlist[v].firstarc; //边表中的工作指针p初始化 while (p) {

j= p->adjvex;

void BiSortTree::InsertBST(BiNode *root, BiNode *s) {

if (root==NULL) root=s;

else if (s->datadata) InsertBST(root->lchild, s); else InsertBST(root->rchild, s); }

二叉排序树查找算法SearchBST

BiNode * BiSortTree::SearchBST(BiNode *root, int k) {

if (root==NULL) return NULL； else if (root->data==k) return root;

else if (kdata) return SearchBST(root->lchild, k);

else return SearchBST(root->rchild, k);

}

二叉排序树的删除算法DeleteBST

void BiSortTree::DeleteBST(BiNode *p, BiNode *f ) {

if (!p->lchild && !p->rchild) { //p为叶子

f->lchild= NULL; delete p; }

else if (!p->rchild) { //p只有左子树

f->lchild=p->lchild; delete p; }

else if (!p->lchild) { //p只有右子树 f->lchild=p->rchild; delete p; }

else { //左右子树均不空 par=p; s=p->rchild;

while (s->lchild!=NULL) //查找最左下结点 {

par=s;

s=s->lchild; }

p->data=s->data;

if (par==p) par->rchild=s->rchild; //处理特殊情况 else par->lchild=s->rchild; //一般情况 delete s;

} //左右子树均不空的情况处理完毕 }

６．闭散列表的查找算法HashSearch1

int HashSearch1(int ht[ ], int m, int k) {

j=H(k);

if (ht[j]==k) return j; //没有发生冲突，比较一次查找成功 i=(j+1) % m;

while (ht[i]!=Empty && i!=j)

{

if (ht[i]==k) return i; //发生冲突，比较若干次查找成功 i=(i+1) % m; //向后探测一个位置 }

if (i==j) throw \溢出\

else ht[i]=k; //查找不成功时插入 }

７．开散列表的查找算法HashSearch２

Node *HashSearch2(Node *ht[ ], int m, int k) {

j=H(k); p=ht[j];

while (p && p->data!=k) p=p->next;

if (p->data= =k) return p; else {

q=new Node; q->data=k;

q->next= ht[j];

ht[j]=q; } }

注意问题

1．注意理解折半查找的适用条件（链表能否实现折半查找？）。 2. 注意理解静态查找、动态查找概念。

3．比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。

实验七 排序的有关操作

实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的：

参照各种排序算法程序样例，验证给出的排序常见算法。 二、实验要求：

1、掌握各种排序算法的特点，测试并验证排序的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容：

输入一组关键字序列分别实现下列排序:

1.实现简单选择排序、直接插入排序和冒泡排序。 2.实现希尔排序算法。

3.实现快速排序算法（取第一个记录或中间记录作为基准记录）。 4.实现堆排序算法。 *5.快速排序的非递归算法。 *6.实现折半插入排序。

*7.采用链式存储实现简单选择排序、直接插入排序和冒泡排序。

8.在主函数中设计一个简单的菜单，分别测试上述算法。

*9.双向起泡排序。在起泡排序中，若待排序序列为正序，只需一趟扫描，而待排序序列为反序时，需进行n-1趟扫描。对于初始序列（94，10，12，18，42，44，67）只需扫描2趟，而对于初始序列（12，18，42，44，67，94，10）就需扫描6趟。造成这种不对称的原因：每趟扫描仅能使最小数据下沉一个位置，如果改变扫描方向，，情况正好相反，即每趟从后往前扫描，都能使当前无序区中最大数据上浮一个位置。为了改变上述两种情况下的不对称性，可以在排序过程中交替改变扫描方向，称之为双向起泡排序。 四、程序样例:

1.选择排序

void SelectSort(int r[ ], int n) {

for (i=1; i

index=i;

for (j=i+1; j<=n; j++) //在无序区中选取最小记录 if (r[j]

2．快速排序

int Partition(int r[ ], int first, int end)

{

i=first; j=end; //初始化 while (i

while (i

r[i]←→r[j]; //将较小记录交换到前面 i++; }

while (i

if (i

r[j]←→r[i]; //将较大记录交换到后面 j--;

}

}

retutn i; //i为轴值记录的最终位置 }

void QuickSort(int r[ ], int first, int end)

{

if (first

pivot=Partition(r, first, end); //一次划分

QuickSort(r, first, pivot-1); //递归地对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序

}

}

3.起泡排序

void BubbleSort(int r[ ], int n)

{

exchange=n; //第一趟起泡排序的范围是r[1]到r[n]

while (exchange) //仅当上一趟排序有记录交换才进行本趟排序 {

bound=exchange; exchange=0；

for (j=1; j

if (r[j]>r[j+1]) { r[j]←→r[j+1]；

exchange=j； //记录每一次发生记录交换的位置 } } }

4.希尔排序

void ShellSort(int r[ ], int n) {

for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序 { for (i=d+1; i<=n; i++)

{ r[0]=r[i]; //暂存被插入记录

for (j=i-d; j>0 && r[0]

r[j+d]=r[j]; //记录后移d个位置 r[j+d]=r[0];

} }

}

void InsertSort(int r[ ], int n) {

for (i=2; i<=n; i++)

{ r[0]=r[i]; //设置哨兵

for (j=i-1; r[0]

r[j+1]=r[0];

}

}

5.堆排序

void Sift(int r[ ], int k, int m) {

i=k; j=2*i; //置i为要筛的结点，j为i的左孩子 while (j<=m) //筛选还没有进行到叶子 {

if (jr[j]) break; //根结点已经大于左右孩子中的较大者 else {

r[i]←→r[j]; //将根结点与结点j交换

i=j; j=2*i; //被筛结点位于原来结点j的位置 } } }

void HeapSort(int r[ ], int n) {

for (i=n/2; i>=1; i--) //初始建堆，从最后一个非终端结点至根结点

Sift(r, i, n) ;

for (i=1; i

r[1]←→r[n-i+1]; Sift(r, 1, n-i); } }

6.归并排序

void MergeSort2(int r[ ], int r1[ ], int s, int t) {

if (s==t) r1[s]=r[s]; else { m=(s+t)/2;

Mergesort2(r, r1, s, m); //归并排序前半个子序列 Mergesort2(r, r1, m+1, t); //归并排序后半个子序列 Merge(r1, r, s, m, t); //将两个已排序的子序列归并 } }

void MergeSort1(int r[ ], int r1[ ], int n ) {

h=1;

while (h

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