数据结构课程实验报告

课程实验报告课程名：数据结构

目录TOC\o"1-3"\h\u18974实验一单链表队列 321369实验二顺序数组 1223558实验三顺序二叉树 172868实验四链式二叉树 2716151实验五图 3319286实验六拓扑排序 4010834实验七静态查找表 4820453实验八二叉排序树 6528290实验九折半排序、二路插入排序，表插入排序 72

南昌大学实验报告实验一单链表队列学生姓名：xx学号：xxxxxxxx专业班级：计算机185实验类型：□验证□综合□设计□创新实验日期：2019-10-10实验成绩：实验项目名称用顺序表实现学生健康情况登记表。实验目的掌握非循环队列的逻辑结构、存储结构、操作。利用单链表实现非循环队列，用C++编写程序实现简单的控制台交互界面。实验基本原理非循环的队列特点是先进先出。使用队头指针front和队尾指针rear来进行对队列的元素的插入删除操作。主要仪器设备及耗材PC微型计算机，C++集成开发环境编译器。实验步骤（完整内容见光盘）问题分析与程序设计问题分析非循环队列是一个有着特定操作的单链表，特点只能操作队头和队尾的元素。应当允许进行队尾元素的插入，队头元素的删除，打印队列等基本操作。算法原理利用单链表可以创建一个理论上无限长的单链表队列。队尾元素插入的对应操作是生成一个新的节点，类比于单链表的元素插入操作，将新节点插入队列末尾。队头元素的删除则类比于单链表的删除元素的操作，将队头节点内存释放，队头指针指向下一个节点。代码#include

<iostream>

#include

<string>

#include

<windows.h>

using

namespace

std;

#define

OK

1

#define

ERROR

0

#define

TRUE

1

#define

FALSE

0

typedef

int

Status;

struct

ElemType

{

string

name;

int

value;

};

typedef

struct

QNode

{

ElemType

data;

QNode

*next;

}

QNode,

*QueuePtr;

struct

LinkQueue

{

QueuePtr

rear,

front;

int

length;

};

//基本操作的函数

//创建一个队列

Status

InitQueue(LinkQueue

&Q)

{

QueuePtr

baseNode;

baseNode

=

new(QNode);

Q.front

=

baseNode;//头

Q.rear

=

baseNode;//尾

Q.length

=

0;

return

OK;

}

//销毁一个队列

Status

DestroyQueue(LinkQueue

&Q)

{

if

(!Q.front)

return

ERROR;

QueuePtr

cur_Node,

next_Node;

cur_Node

=

Q.front->next;

next_Node

=

cur_Node->next;

while

(cur_Node

!=

Q.rear)

{

delete

(cur_Node);

cur_Node

=

next_Node;

next_Node

=

cur_Node->next;

}//释放所有结点内存

Q.rear

=

NULL;

Q.front

=

NULL;

return

OK;

}

//清空一个队列

Status

ClearQueue(LinkQueue

&Q)

{

if

(!Q.front)

return

ERROR;

QueuePtr

cur_Node,

next_Node,

firstNode;

cur_Node

=

Q.front->next;

next_Node

=

cur_Node->next;

while

(cur_Node

!=

Q.rear)

{

delete

(cur_Node);

cur_Node

=

next_Node;

next_Node

=

cur_Node->next;

}//释放所有结点内存

if

(firstNode

=

new(QNode))

{

Q.front

=

firstNode;//头

Q.rear

=

firstNode;//尾

Q.length

=

0;

}

return

OK;

}

//查询队列是否为空

Status

QueueEmpty(LinkQueue

Q)

{

if

(Q.front

==

Q.rear

||

Q.length

==

0)

return

TRUE;

else

return

FALSE;

}

//返回队列的长度

int

QueueLength(LinkQueue

Q)

{

return

Q.length;

}

//获取队头元素

Status

GetHead(LinkQueue

Q,

ElemType

&e)

{

if

(!Q.front

&&

Q.length

!=

0)

return

ERROR;

=

Q.front->next->;

e.value

=

Q.front->next->data.value;

return

OK;

}

//插入新元素

Status

EnQueue(LinkQueue

&Q,

ElemType

e)

{

if

(!Q.rear)return

ERROR;

QueuePtr

newNode;

newNode

=

new(QNode);

newNode->

=

;

newNode->data.value

=

e.value;

Q.rear->next

=

newNode;

Q.rear

=

newNode;

Q.length++;

return

OK;

}

//删除队头元素（若队列不为空）,用e返回队头元素

Status

DeQueue(LinkQueue

&Q,

ElemType

&e)

{

if

(Q.length

==

0)return

ERROR;

QueuePtr

cur_Node;

cur_Node

=

Q.front->next;

=

cur_Node->;

e.value

=

cur_Node->data.value;

Q.front

=

cur_Node->next;

delete

(cur_Node);

return

OK;

}

//

打印所有元素

Status

visitQueue(LinkQueue

Q)

{

if

(Q.front

==

Q.rear)

return

ERROR;

QueuePtr

cur_Node;

cur_Node

=

Q.front->next;

int

i

=

1;

while

(cur_Node

!=

Q.rear)

{

cout

<<

"结点Node"

<<

i

<<

"的"

<<

endl

<<

"name:"

<<

cur_Node->

<<

endl

<<

"value:"

<<

cur_Node->data.value

<<

endl;

i++;

cur_Node

=

cur_Node->next;

}

cout

<<

"结点Node"

<<

i

<<

"的"

<<

endl

<<

"name:"

<<

cur_Node->

<<

endl

<<

"value:"

<<

cur_Node->data.value

<<

endl;

return

OK;

}

int

main()

{

ElemType

var,U_var;

LinkQueue

Q;

int

exit_code

=

-1;

while

(exit_code

!=

10)

{

Sleep(1000);

cout

<<

"1.创造一个队列"

<<

endl

<<

"2.销毁一个队列"

<<

endl

<<

"3.清空队列"

<<

endl

<<

"4.查询队列是否为空"

<<

endl

<<

"5.返回队列的长度"

<<

endl

<<

"6.返回队头元素"

<<

endl

<<

"7.插入队尾元素"

<<

endl

<<

"8.删除队头元素"

<<

endl

<<

"9.打印队列所有元素"

<<

endl

<<

"10.退出"

<<

endl

<<

"输入对应的操作码选择对应的功能!"

<<

endl;

while

(!(cin

>>

exit_code)

||

cin.fail()

||

exit_code

>

10)

{

cin.clear();

cin.sync();

cout

<<

"输入错误，请重新输入！"

<<

endl;

}

switch

(exit_code)

{

case

1:

if

(InitQueue(Q))

{

=

"张三";

var.value

=

1;

EnQueue(Q,

var);

=

"李四";

var.value

=

2;

EnQueue(Q,

var);

=

"王五";

var.value

=

3;

EnQueue(Q,

var);

}

{

if

(visitQueue(Q))cout

<<

"操作成功！"

<<

endl;

};

break;

case

2:

if

(DestroyQueue(Q))

cout

<<

"操作成功！"

<<

endl;

break;

case

3:

if

(ClearQueue(Q))

cout

<<

"操作成功！"

<<

endl;

break;

case

4:

if

(QueueEmpty(Q))

cout

<<

"队列为空！"

<<

endl;

else

cout<<"队列不为空！"<<endl;

break;

case

5:

if

(QueueLength(Q))

cout

<<

"Q.length

is

:"

<<

QueueLength(Q)

<<

endl

<<

"操作成功！"

<<

endl;

break;

case

6:

if

(GetHead(Q,

var))

{

cout

<<

"操作成功！"

<<

endl

<<

"H

is:"

<<

<<endl

<<

"Head.value

is:"

<<

var.value

<<

endl;

}

break;

case

7:

cout<<"input

name:"<<endl;

cin>>U_;

cout<<"input

value:"<<endl;

cin>>U_var.value;

if

(EnQueue(Q,U_var))

cout

<<

"操作成功！"

<<

endl;

break;

case

8:

if

(DeQueue(Q,var))

cout

<<

"操作成功！"

<<

endl

<<

"H

is:"

<<

<<endl

<<

"Head.value

is:"

<<

var.value

<<

endl;

break;

case

9:

if

(visitQueue(Q))

{

cout

<<

"操作成功！"

<<

endl;}

break;

}

}

return

0;

}

实验数据及处理结果初始菜单页面创建一个队列查队列是否为空返回队列长度返回队头元素插入队尾元素删除队头元素思考讨论题或体会或对改进实验的建议利用队列的特性可以设计一个基于队列原理的银行/医院领号排队系统。利用非循环队列模拟银行用户的排队情况，可以借此分析银行的业务办理高峰期，用户平均排队时间等信息，可以方便银行进行业务优化。可以看见，掌握了数据结构的基本方法，我们还要善于运用创新思维，学以致用，结合生活实际把书本上抽象的知识具体起来。八、参考资料《数据结构》

南昌大学实验报告实验二顺序数组学生姓名：xx学号：xxxxxxxx专业班级：计算机185班实验类型：□验证□综合□设计□创新实验日期：2019-10-17实验成绩：实验项目名称自定义数组及其常规操作实验目的用自己定义的数据类型构造一个新数据类型的顺序数组。实现顺序数组的基本操作：初始化，赋值，取值，删除。实验基本原理1.顺序数组可以看成一个定长的顺序链表。在确定了里面数据的约束关系后就可以为数组分配内存空间并进行相应的操作。四、主要仪器设备及耗材PC微型计算机，C++集成开发环境编译器。五、实验步骤（完整内容见光盘）1.问题分析：本次实验只需要实现数组的几个基本操作：初始化，赋值，取值，删除。由于使用了不定参数传参方式，所以不方便设计用户交互界面，只能实现基本功能。2.代码#define

MAX_ARRAY_DIM

8

#define

ERROR

0

#define

OVERFLOW

-2

#define

OK

1

typedef

int

Status;

typedef

int

ElemType;

typedef

struct

{

ElemType

*base;

int

dim;

int

*bounds;

int

*constants;

}Array;

Status

Array_Operation::InitArray(Array

&A,

int

dim,

...)

{

if(dim

<1||dim

>

MAX_ARRAY_DIM)

return

ERROR;

A.dim

=

dim;

A.bounds

=

new

(int)(dim);

if(!A.bounds)

exit(OVERFLOW);

int

elemtotal

=

1;

va_list

ap;

va_start(ap,dim);

for

(int

i

=

0;i<dim;i++){

A.bounds[i]=

va_arg(ap,int);

if(A.bounds[i]<0)

return

OVERFLOW;

elemtotal*=A.bounds[i];

}

va_end(ap);

A.base

=

(ElemType

*)malloc(elemtotal*

sizeof(ElemType));

//A.base

=

new

(ElemType)(elemtotal);

if(!A.base)

exit(OVERFLOW);

A.constants

=

new(int)(dim);

if(!A.constants)

exit(OVERFLOW);

A.constants[dim-1]

=

1;

for

(int

i

=

dim-2;i>=0;--i){

A.constants[i]

=

A.bounds[i+1]*A.constants[i+1];

}

return

OK;

}

Status

Array_Operation::DestroyArray(Array

&A)

{

if(!A.base)return

ERROR;

free(A.base);A.base

=

NULL;

if(!A.bounds)

return

ERROR;

free(A.bounds);A.bounds

=

NULL;

if(!A.constants)

return

ERROR;

free(A.constants);A.constants

=NULL;

return

OK;

}

Status

Locate(Array

A,va_list

ap,int

&off){

off

=

0;

for

(int

i

=0;i<A.dim;++i){

int

ind

=

va_arg(ap,int);

if(ind

<0||ind>=A.bounds[i])

return

OVERFLOW;

off

+=

A.constants[i]*ind;

}

return

OK;

}

Status

Array_Operation::Value(Array

A,

ElemType

&e,

...)

{

va_list

ap;

va_start(ap,e);

int

result=0;

int

off;

if((result

=

Locate(A,ap,off)<=0))

return

result;

e

=

*(A.base+off);

return

OK;

}

Status

Array_Operation::Assign(Array

&A,

ElemType

e,

...)

{

va_list

ap;

va_start(ap,e);

int

result=0;

int

off;

if((result

=

Locate(A,ap,off)<=0))

return

result;

va_end(ap);

*(A.base+off)

=

e;

return

OK;

}

#include

<iostream>

#include

<stdarg.h>

#include

"Statement.h"

#include

"Array_OPeration.h"

#include

<windows.h>

using

namespace

std;

int

main()

{

Array

A;

int

dim;

ElemType

e

,e2;

e

=

666;

int

bounds[MAX_ARRAY_DIM];

Array_Operation

AO;

int

exit_code

=

-1;

while

(exit_code

!=

10)

{

Sleep(1000);

cout

<<

"1.初始化数组"

<<

endl

<<

"2.删除数组"

<<

endl

<<

"3.数组赋值"

<<

endl

<<

"4.数组取值"

<<

endl

<<

"5.退出"

<<

endl

<<

"10.退出"

<<

endl

<<

"输入对应的操作码选择对应的功能!"

<<

endl;

while

(!(cin

>>

exit_code)

||

cin.fail()

||

exit_code

>

10)

{

cin.clear();

cin.sync();

cout

<<

"输入错误，请重新输入！"

<<

endl;

}

switch

(exit_code)

{

case

1:

if

(AO.InitArray(A,

3,

3,

3,

3))cout

<<

"数组初始化成功！"

<<

endl;

break;

case

2:

if(AO.DestroyArray(A))

cout<<"数组初始化删除成功！"<<endl;

break;

case

3:

if(AO.Assign(A,e,0,1,1))

cout<<"赋值成功！"<<endl;

break;

case

4:

if(AO.Value(A,e2,0,1,1)){

cout<<"取值成功！取到的值是："<<e2<<endl;

}

break;

}

}

return

0;

}

实验数据及处理结果数组初始化数组赋值数组取值思考讨论题或体会或对改进实验的建议自定义的顺序数组只能实现简单的操作。用链表实现数组可以丰富数组的功能，例如实现不定长度的数组，或者构造不规则的多维数组，更可以引申为矩阵。基本的数据结构只是提供了底层原理和基础操作的实现。我们可以根据实际需要或者自己的理解，从基础操作入手，将简单的方法演化为更高级的功能。参考资料《数据结构》

南昌大学实验报告实验三顺序二叉树学生姓名：xx学号：xxxxxxxx专业班级：计算机185班实验类型：□验证□综合□设计□创新实验日期：2019-11-7实验成绩：实验项目名称顺序二叉树及其基本操作实验目的建立顺序二叉树并实现基本操作：1.求树的深度2.求树的节点数3.打印二叉树4.二叉树左右节点互换。实验基本原理采用数组的方式存储二叉树，二叉树各节点的关系由其对应的下标之间的数学关系判定。即存在下标为i存在有效节点n1，若下标为2i存在有效节点n2，下标2i+1存在有效节点n3，则n2为n1的左子节点，n3为n1的右子节点。主要仪器设备及耗材PC微型计算机，C++集成开发环境编译器。实验步骤（完整内容见光盘）问题分析与程序设计树的有效节点数可以通过遍历存储二叉树的数组，记录有效节点实现。求树的深度可以通过判断最后一个节点所在的区间范围，即求出2k-1~2k，则k为这棵树的最大深度。二叉树的左右节点互换则是在每一层中，将该层对应的节点互换即可。打印二叉树则要计算好对应的空格与树枝，逐层打印。源代码/**

*

程序采用了动态建立数组的方式，程序在C14或更新的cpp编译环境下才能正常运行

*

*/

#include

<iostream>

#include

<iomanip>

#include

<cmath>

#include

<cstring>

using

namespace

std;

#define

ERROR

0

#define

OK

1

typedef

int

Status;

#define

MAX_TREE_SIZE

100

struct

SqBiTree

{

string

NodeName="empty";

int

use=0;

};

struct

info

{

string

NodeName;

int

r_child

=

0;

int

l_child

=

0;

};

class

SequenceBinaryTree

{

public:

int

Locate(SqBiTree

T[],

string

NodeName)

{

for

(int

i

=

1;

i

<

MAX_TREE_SIZE;

i++)

{

if

(T[i].NodeName

==

NodeName)

{

return

i;

}

}

return

ERROR;

}

Status

InitBiTree(SqBiTree

T[])

{

for

(int

j

=

0;

j

<

MAX_TREE_SIZE;

j++)

{

T[j].NodeName

=

"empty";

T[j].use

=

0;

}//数组初始化

int

i

=

1;

string

s

=

"OK";

string

user_input;//输入信息

string

parent;//双亲节点的信息

string

child_flag;//判断是否为左/右孩子

string

NodeName;//孩子节点的信息

int

index

=

1;

while

(s

!=

"END"

&&

s

!=

"end")

{

cout

<<

"请输入顺序二叉树各个节点的信息："

<<

"(少于"

<<

MAX_TREE_SIZE

<<

"个节点）"

<<

endl;

cout

<<

"输入END结束!"

<<

endl;

cout

<<

"输入样例：A

L

B"

<<

endl

<<

"其中：A是要输入的节点的双亲节点"

<<

endl

<<

"L指定是左节点还是右节点"

<<

endl

<<

"B是新节点的名称"

<<

endl;

if

(index

==

1)

cout

<<

"头节点的双亲节点，左右子节点的标记

可以用空格代替"

<<

endl;

getline(cin,user_input);

s

=

user_input;

parent

=

user_input[0];

child_flag

=

user_input[2];

NodeName

=

user_input[4];

if

(parent

==

"

"

&&

child_flag

==

"

")

{

T[index].use

=

1;

T[index].NodeName

=

NodeName;

}

else

if

(child_flag

==

"L")

{

index

=

Locate(T,

parent);

T[2

*

index].use

=

1;

T[2

*

index].NodeName

=

NodeName;

}

else

if

(child_flag

==

"R")

{

index

=

Locate(T,

parent);

T[2

*

index

+

1].use

=

1;

T[2

*

index

+

1].NodeName

=

NodeName;

}

}

return

OK;

}

Status

InitBiTree_Default(SqBiTree

T[])

{

string

s

=

"ABCDEFGHIJKLMNO";

for

(int

j

=

0;

j

<

MAX_TREE_SIZE;

j++)

{

T[j].NodeName

=

"empty";

T[j].use

=

0;

}

for

(int

i

=

1;

i

<

16;

i++)

{

T[i].use

=

1;

T[i].NodeName

=

s[i

-

1];

}

T[18].use

=

1;

T[18].NodeName

=

"Q";

T[20].use

=

1;

T[20].NodeName

=

"W";

return

OK;

}

Status

GetNodeNum(SqBiTree

T[])

{

int

count

=

0;

for

(int

i

=

1;

i

<

MAX_TREE_SIZE;

i++)

{

if

(T[i].NodeName

!=

"empty"

&&

T[i].use)

{

count++;

}

}

return

count;

}

Status

GetTreeDepth(SqBiTree

T[])

{

int

final_index

=

0;

int

k

=

0;

for

(int

i

=

1;

i

<

MAX_TREE_SIZE;

i++)

{

if

(T[i].NodeName

!=

"empty"&&T[i].use)

{

final_index

=

i;

}

}//找最后一个节点的下标

for

(k

=

1;

k

<

MAX_TREE_SIZE;

k++)

{

if

(final_index

<=

pow(2,

k))

{

break;

}

}//用下标求深度

return

k;

}

Status

NodeExchange(SqBiTree

T[],

int

index)

{

int

depth

=

GetTreeDepth(T);

if

(depth

==

1)

return

OK;

else

{

for

(int

nD

=

2;

nD

<=

depth;

nD++)

{

for

(int

k

=

pow(2,

nD

-

1);

k

<

pow(2,

nD)

-

pow(2,

nD

-

2);

k++)

{

swap(T[k],

T[int(pow(2,

nD)

-

(k

-

pow(2,

nD

-

1)

+

1))]);

}

}

}

return

OK;

}

Status

calBase(int

depth,

int

nD,

int

layer[])

{

int

n

=

3;

//

int

result

=

0;

if

(depth

-

nD

==

1)

return

n

+

1;

for

(int

i

=

1;

i

<=

depth

-

nD;

i++)

{

for

(int

k

=

1;

k

<

i;

k++)

{

if

(k

==

1)

n

=

0;

n

+=

layer[k]

+

1;

}

layer[i]

=

n;

}

for

(int

i

=

1;

i

<=

depth

-

nD;

i++)

{

result

+=

layer[i];

}

return

result

+

depth

-

nD;

}

Status

printSpace(int

i)

{

for

(int

j

=

0;

j

<

i;

j++)

{

cout

<<

"

";

}

return

OK;

}

Status

printUnderline(int

i)

{

for

(int

j

=

0;

j

<

i;

j++)

{

cout

<<

"_";

}

return

OK;

}

Status

printBiTree(SqBiTree

T[])

{

int

Base;//每一层的基准

int

nD;//记录当前层数

int

temp

=

0;//临时变量

int

depth

=

GetTreeDepth(T);//树的总深度

int

Node_num

=

GetNodeNum(T);//树的节点数

int

layer[depth

+

1];//每一层的树枝信息

info

Node_info[Node_num];

for

(int

i

=

1;

i

<

Node_num;

i++)

{

if

(T[i].NodeName

!=

"empty"

&&

T[i].use)

{

if

(T[2

*

i].use)

Node_info[i].l_child

=

1;

if

(T[2

*

i

+

1].use)

Node_info[i].r_child

=

1;

}

}//记录每个节点的左右孩子信息

for

(nD

=

1;

nD

<

depth;

nD++)

{

//每层的第一部分，先打节点

int

count

=

1;

for

(int

k

=

pow(2,

nD

-

1);

k

<

pow(2,

nD);

k++)

{

//计算当前层数的基准空格

Base

=

calBase(depth,

nD,

layer);

if

(count

==

1)

{

printSpace(Base);

if

(T[k].NodeName

!=

"empty"

&&

T[k].use)

{

cout

<<

T[k].NodeName;

}

else

{

cout

<<

"

";

}

count++;

continue;

}

printSpace(2

*

Base

+

1);

if

(T[k].NodeName

!=

"empty"

&&

T[k].use)

{

cout

<<

T[k].NodeName;

}

else

{

cout

<<

"

";

}

}

cout

<<

endl;

//

//每层的树枝1

count

=

1;

for

(int

k

=

pow(2,

nD

-

1);

k

<

pow(2,

nD);

k++)

{

//计算当前层数的基准空格

Base

=

calBase(depth,

nD,

layer);//节点的基准偏移

int

Base2

=

Base

-

layer[depth

-

nD];//树枝的基准偏移

if

(count

==

1)

{

printSpace(Base2);

if

(Node_info[k].l_child)

{

printUnderline(layer[depth

-

nD]

-

1);

cout

<<

"/";

}

else

printSpace(layer[depth

-

nD]);

//如果有左子节点

printSpace(1);

if

(Node_info[k].r_child)

{

cout

<<

"\\";

printUnderline(layer[depth

-

nD]

-

1);

}

else

printSpace(layer[depth

-

nD]);//如果有右子节点

printSpace(2

*

Base2

+

1);

count++;

continue;

}

if

(Node_info[k].l_child)

{

printUnderline(layer[depth

-

nD]

-

1);

cout

<<

"/";

}

else

printSpace(layer[depth

-

nD]);

//如果有左子节点

printSpace(1);

if

(Node_info[k].r_child)

{

cout

<<

"\\";

printUnderline(layer[depth

-

nD]

-

1);

}

else

printSpace(layer[depth

-

nD]);//如果有右子节点

printSpace(2

*

Base2

+

1);

count++;

}

cout

<<

endl;

}

//下面打印最底层的节点

int

count_final_layer

=

1;

for

(int

k

=

pow(2,

nD

-

1);

k

<

pow(2,

nD);

k++)

{

if

(count_final_layer

==

1)

{

if

(T[k].NodeName

!=

"empty"

&&

T[k].use)

{

cout

<<

T[k].NodeName;

}

else

{

cout

<<

"

";

}

count_final_layer++;

printSpace(7);

continue;

}

if

(T[k].NodeName

!=

"empty"

&&

T[k].use)

{

cout

<<

T[k].NodeName;

}

else

{

cout

<<

"

";

}

if

(count_final_layer

%

2

==

0)

{

printSpace(1);

}

else

{

printSpace(7);

}

count_final_layer++;

}

return

OK;

}

};

int

main()

{

SqBiTree

T[MAX_TREE_SIZE];

SequenceBinaryTree

SBT;

cout

<<

"使用预设方案："

<<

endl;

SBT.InitBiTree_Default(T);

cout<<"当前的二叉树为："<<endl;

SBT.printBiTree(T);

cout

<<

endl

<<

"当前二叉树的节点数是："

<<

SBT.GetNodeNum(T)

<<

endl;

cout

<<

"当前二叉树的深度是："

<<

SBT.GetTreeDepth(T)

<<

endl;

cout

<<

"将二叉树的左右节点互换："

<<

endl;

SBT.NodeExchange(T,

1);

cout

<<

"二叉树左右节点互换后的结果为："

<<

endl;

SBT.printBiTree(T);

return

0;

}

实验数据及处理结果二叉树的创建。求二叉树的节点数求二叉树的深度二叉树左右节点互换用户输入版思考讨论题或体会或对改进实验的建议实验体会：本次实验的难点在于实现打印二叉树。因为要考虑打印二叉树的树枝部分，所以要提前计算好基准空格数，根据基准空格数才能正确的计算出二叉树的各个树枝的打印宽度。在计算基准空格时，要注意每一层的基准空格数可以利用动态规划从最底层开始地推求出，这样才能保证打印的二叉树规整有序。八、参考资料《数据结构》 南昌大学实验报告实验四链式二叉树学生姓名：xx学号：xxxxxxxx专业班级：计算机185班实验类型：□验证□综合□设计□创新实验日期：2019-11-14实验成绩：一、实验项目名称链式二叉树的创建与遍历。二、实验目的实现分别采用先序方式创建二叉树，并实现二叉树的先序，中序，后序遍历。三、实验基本原理采用先序方式创建链式二叉树，树的各个节点的关系由各个节点的指针指向界定。所以每个节点的指针域要指明为左子节点，右子节点，双亲节点。先序遍历定义为：先访问根节点，再先序遍历左子树，再先序遍历右子树。中序遍历的定义为：先中序遍历左子树，再访问根节点，再中序遍历右子树。后序遍历的定义为：先后序遍历左子树，再后序遍历右子树，再访问根节点。四、主要仪器设备及耗材PC微型计算机，C++集成开发环境编译器。五、实验步骤（完整内容见光盘）问题分析与程序设计二叉树是递归定义的，所以有关二叉树的操作，例如二叉树的创建，遍历，核心思想都是递归。所以创建二叉树时可以采用递归方式依次创建每个节点的左右子节点。而前序中序后序遍历的区别在于打印节点的时机不同。递归的核心思想与栈相类似，为了避免二叉树的深度过深而出现的栈溢出问题，可以用栈代替递归，同样实现二叉树的前序中序和后序遍历。源代码#include

<iostream>

#include

<stack>

using

namespace

std;

typedef

int

Status;

#define

OK

1

#define

ERROR

0

typedef

string

TElemType;

typedef

struct

BitNode

{

string

data

=

"

";

BitNode

*lChild

=

NULL,

*rChild

=

NULL,

*parent

=

NULL;

}

*BitTree;

Status

Visit(BitTree

e)

{

if

(e

&&

e->data

!=

"

")

{

cout

<<

e->data

<<

"

";

return

OK;

}

return

ERROR;

}

class

BitTreeOperation

{

public:

//

创建二叉树

Status

CreatBitTree(BitTree

T,

BitTree

&T_child,

int

i)

{

cout

<<

"输入一个结点(输入END结束):"

<<

endl;

string

NodeName;

if

(i

==

1)

{

cout

<<

"输入"

<<

T->data

<<

"的左子节点，空格表示无该子节点:"

<<

endl;

}

else

if

(i

==

2)

{

cout

<<

"输入"

<<

T->data

<<

"的右子节点，空格表示无该子节点:"

<<

endl;

}

getline(cin,

NodeName);

if

(NodeName

==

"END")

return

OK;

if

(NodeName

==

"

")

T_child

=

NULL;

else

{

T_child

=

new(BitNode);

T_child->data

=

NodeName;

CreatBitTree(T_child,

T_child->lChild,

1);

CreatBitTree(T_child,

T_child->rChild,

2);

}

return

OK;

}

//

前序遍历

Status

PreOrderTraverse(BitTree

T,

Status

(*Visit)(BitTree

e))

{

if

(T)

{

if

(Visit(T))

{

if

(PreOrderTraverse(T->lChild,

Visit))

if

(PreOrderTraverse(T->rChild,

Visit))

return

OK;

}

return

ERROR;

}

else

return

OK;

}

Status

PreOrderTraverse_R(BitTree

T,

Status

(*Visit)(BitTree

e))

{

stack

<BitTree>

s;

while

(T

||

!s.empty())

{

while

(T)

{

Visit(T);

s.push(T);

T

=

T->lChild;

}

if

(!s.empty())

{

T

=

s.top();

s.pop();

T

=

T->rChild;

}

}

return

OK;

}

//

中序遍历

Status

InOrderTraverse(BitTree

T,

Status

(*Visit)(BitTree

e))

{

if

(T)

{

if

(InOrderTraverse(T->lChild,

Visit))

{

if

(Visit(T))

if

(InOrderTraverse(T->rChild,

Visit))

return

OK;

}

}

else

return

OK;

}

Status

InOrderTraverse_R(BitTree

T,

Status

(*Visit)(BitTree

e))

{

stack

<BitTree>

s;

while

(T

||

!s.empty())

{

while

(T)

{

s.push(T);

T

=

T->lChild;

}

if

(!s.empty())

{

T

=

s.top();

s.pop();

Visit(T);

T

=

T->rChild;

}

}

return

OK;

}

//

后序遍历

Status

PostOrderTraverse(BitTree

T,

Status

(*Visit)(BitTree

e))

{

if

(T)

{

PostOrderTraverse(T->lChild,

Visit);

PostOrderTraverse(T->rChild,

Visit);

Visit(T);

}

else

return

OK;

}

Status

PostOrderTraverse_R(BitTree

T,

Status

(*Visit)(BitTree

e))

{

stack<BitTree>

s1,s2;

while(T

||

!s1.empty())

{

while(T)

{

s2.push(T);

s1.push(T);

T

=

T->rChild;

}

if

(!s1.empty())

{

T

=

s1.top();

s1.pop();

T

=

T->lChild;

}

}

while(!s2.empty())

//访问（打印）S2中元素

{

T

=

s2.top();

s2.pop();

cout<<T->data;

}

}

};

int

main()

{

BitTreeOperation

BTO;

TElemType

e;

BitTree

T;

T

=

new(BitNode);

BTO.CreatBitTree(T,

T,

0);

cout

<<

"前序遍历：";

BTO.PreOrderTraverse(T,

Visit);

cout

<<endl<<

"前序遍历（非递归形式）：";

BTO.PreOrderTraverse_R(T,

Visit);

cout

<<

endl

<<

"中序遍历：";

BTO.InOrderTraverse(T,

Visit);

cout

<<

endl

<<

"中序遍历（非递归形式）：";

BTO.InOrderTraverse_R(T,

Visit);

cout

<<

endl

<<

"后序遍历：";

BTO.PostOrderTraverse(T,

Visit);

cout

<<

endl

<<

"后序遍历（非递归形式）：";

BTO.PostOrderTraverse_R(T,

Visit);

return

0;

}

六、实验数据及处理结果二叉树的创建。二叉树的前序、中序、后序遍历。七、思考讨论题或体会或对改进实验的建议实验体会：递归是代码中一种比较特别的形式。代码虽少，核心思想却很难理解。然而二叉树的定义就是用递归思想实现，因此本次实验中涉及的操作都用了递归的思想。使用递归最关键的是递归结束条件，以及递归回溯时各个值的变化。这次实验中，实现前序、中序、后序遍历的函数形态上很相似，区别仅仅在于打印节点信息的位置不同。但是仅仅是位置上的细微区别，就是算法核心上的本质区别。八、参考资料《数据结构》 南昌大学实验报告实验五图学生姓名：xx学号：xxxxxxxx专业班级：计算机185班实验类型：□验证□综合□设计□创新实验日期：2019-11-21实验成绩：一、实验项目名称图的建立与遍历二、实验目的建立无向图并实现深度优先（DFS）遍历。三、实验基本原理无向图实质是有双向边的有向图。实验中对于图的存储采用邻接表的方式。深度优先（DFS）类似于先根遍历，注意要点是要把遍历过的根节点进行标记避免重复遍历。四、主要仪器设备及耗材PC微型计算机，C++集成开发环境编译器。五、实验步骤（完整内容见光盘）问题分析与程序设计本次实验程序有两个核心，一：根据用户输入创建对应的图，二：采用深度优先遍历用户创建的图并输出。其中，图的创建可以在程序中添加适当引导语句引导用户输入，图的保存采用邻接表的方式，具体保存方法可以根据图的类型不同而不同。深度优先遍历类似于树的先根遍历，为了避免重复遍历某些节点，可以采用创建额外的节点数组记录访问与否或在创建节点结构体时加入一个记录是否访问过的风向标。本次实验采取了第二种方法。源代码#include

<iostream>

#include

<string>

using

namespace

std;

#define

INFINITY

INT_MAX

//最大值

#define

MAX_VERTEX_NUM

20

//最大顶点个数s

typedef

int

Status;

#define

ERROR

0

#define

OK

1

typedef

string

VertextType;

//顶点关系类型

typedef

struct

DGArcNode

{

int

adjvex;//该弧所指向的顶点的位置

int

flag

=

0;

int

start,end;

DGArcNode

*nextarc

=

NULL;//指向下一条弧的指针

}

DGArcNode;

struct

DGVNode

{

VertextType

data;

int

flag

=

0;

DGArcNode

*firstarc

=

NULL;

};

typedef

DGVNode

*DGVNode_p,

DGAdjList[MAX_VERTEX_NUM];

typedef

struct

{

DGAdjList

vertices;

int

vexnum;//顶点数

int

arcnum;//弧数

int

kind;//种类

}

ALGraph;

class

Graph

{

public:

Status

Locate(DGAdjList

List,

string

c)

{

int

result;

for

(int

i

=

0;

i

<

MAX_VERTEX_NUM;

i++)

{

if

(List[i].dat