數(shù)據(jù)結(jié)構(gòu)課程實驗報告

課程實驗報告課程名：數(shù)據(jù)結(jié)構(gòu)目錄TOC\o"1-3"\h\u18974實驗一單鏈表隊列 321369實驗二順序數(shù)組 1223558實驗三順序二叉樹 172868實驗四鏈式二叉樹 2716151實驗五圖 3319286實驗六拓撲排序 4010834實驗七靜態(tài)查找表 4820453實驗八二叉排序樹 6528290實驗九折半排序、二路插入排序，表插入排序 72

實驗一單鏈表隊列學(xué)生姓名：xx學(xué)號：xxxxxxxx專業(yè)班級：計算機185實驗類型：□驗證□綜合□設(shè)計□創(chuàng)新實驗日期：2019-10-10實驗成績：實驗項目名稱用順序表實現(xiàn)學(xué)生健康情況登記表。實驗?zāi)康恼莆辗茄h(huán)隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作。利用單鏈表實現(xiàn)非循環(huán)隊列，用C++編寫程序?qū)崿F(xiàn)簡單的控制臺交互界面。實驗基本原理非循環(huán)的隊列特點是先進先出。使用隊頭指針front和隊尾指針rear來進行對隊列的元素的插入刪除操作。主要儀器設(shè)備及耗材PC微型計算機，C++集成開發(fā)環(huán)境編譯器。實驗步驟（完整內(nèi)容見光盤）問題分析與程序設(shè)計問題分析非循環(huán)隊列是一個有著特定操作的單鏈表，特點只能操作隊頭和隊尾的元素。應(yīng)當(dāng)允許進行隊尾元素的插入，隊頭元素的刪除，打印隊列等基本操作。算法原理利用單鏈表可以創(chuàng)建一個理論上無限長的單鏈表隊列。隊尾元素插入的對應(yīng)操作是生成一個新的節(jié)點，類比于單鏈表的元素插入操作，將新節(jié)點插入隊列末尾。隊頭元素的刪除則類比于單鏈表的刪除元素的操作，將隊頭節(jié)點內(nèi)存釋放，隊頭指針指向下一個節(jié)點。代碼#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;

};

//基本操作的函數(shù)

//創(chuàng)建一個隊列

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;

}//釋放所有結(jié)點內(nèi)存

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;

}//釋放所有結(jié)點內(nèi)存

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

<<

"結(jié)點Node"

<<

i

<<

"的"

<<

endl

<<

"name:"

<<

cur_Node->

<<

endl

<<

"value:"

<<

cur_Node->data.value

<<

endl;

i++;

cur_Node

=

cur_Node->next;

}

cout

<<

"結(jié)點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.創(chuàng)造一個隊列"

<<

endl

<<

"2.銷毀一個隊列"

<<

endl

<<

"3.清空隊列"

<<

endl

<<

"4.查詢隊列是否為空"

<<

endl

<<

"5.返回隊列的長度"

<<

endl

<<

"6.返回隊頭元素"

<<

endl

<<

"7.插入隊尾元素"

<<

endl

<<

"8.刪除隊頭元素"

<<

endl

<<

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

<<

endl

<<

"10.退出"

<<

endl

<<

"輸入對應(yīng)的操作碼選擇對應(yīng)的功能!"

<<

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;

}

實驗數(shù)據(jù)及處理結(jié)果初始菜單頁面創(chuàng)建一個隊列查隊列是否為空返回隊列長度返回隊頭元素插入隊尾元素刪除隊頭元素思考討論題或體會或?qū)Ω倪M實驗的建議利用隊列的特性可以設(shè)計一個基于隊列原理的銀行/醫(yī)院領(lǐng)號排隊系統(tǒng)。利用非循環(huán)隊列模擬銀行用戶的排隊情況，可以借此分析銀行的業(yè)務(wù)辦理高峰期，用戶平均排隊時間等信息，可以方便銀行進行業(yè)務(wù)優(yōu)化。可以看見，掌握了數(shù)據(jù)結(jié)構(gòu)的基本方法，我們還要善于運用創(chuàng)新思維，學(xué)以致用，結(jié)合生活實際把書本上抽象的知識具體起來。八、參考資料《數(shù)據(jù)結(jié)構(gòu)》

南昌大學(xué)實驗報告實驗二順序數(shù)組學(xué)生姓名：xx學(xué)號：xxxxxxxx專業(yè)班級：計算機185班實驗類型：□驗證□綜合□設(shè)計□創(chuàng)新實驗日期：2019-10-17實驗成績：實驗項目名稱自定義數(shù)組及其常規(guī)操作實驗?zāi)康挠米约憾x的數(shù)據(jù)類型構(gòu)造一個新數(shù)據(jù)類型的順序數(shù)組。實現(xiàn)順序數(shù)組的基本操作：初始化，賦值，取值，刪除。實驗基本原理1.順序數(shù)組可以看成一個定長的順序鏈表。在確定了里面數(shù)據(jù)的約束關(guān)系后就可以為數(shù)組分配內(nèi)存空間并進行相應(yīng)的操作。四、主要儀器設(shè)備及耗材PC微型計算機，C++集成開發(fā)環(huán)境編譯器。五、實驗步驟（完整內(nèi)容見光盤）1.問題分析：本次實驗只需要實現(xiàn)數(shù)組的幾個基本操作：初始化，賦值，取值，刪除。由于使用了不定參數(shù)傳參方式，所以不方便設(shè)計用戶交互界面，只能實現(xiàn)基本功能。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.初始化數(shù)組"

<<

endl

<<

"2.刪除數(shù)組"

<<

endl

<<

"3.數(shù)組賦值"

<<

endl

<<

"4.數(shù)組取值"

<<

endl

<<

"5.退出"

<<

endl

<<

"10.退出"

<<

endl

<<

"輸入對應(yīng)的操作碼選擇對應(yīng)的功能!"

<<

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

<<

"數(shù)組初始化成功！"

<<

endl;

break;

case

2:

if(AO.DestroyArray(A))

cout<<"數(shù)組初始化刪除成功！"<<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;

}

實驗數(shù)據(jù)及處理結(jié)果數(shù)組初始化數(shù)組賦值數(shù)組取值思考討論題或體會或?qū)Ω倪M實驗的建議自定義的順序數(shù)組只能實現(xiàn)簡單的操作。用鏈表實現(xiàn)數(shù)組可以豐富數(shù)組的功能，例如實現(xiàn)不定長度的數(shù)組，或者構(gòu)造不規(guī)則的多維數(shù)組，更可以引申為矩陣。基本的數(shù)據(jù)結(jié)構(gòu)只是提供了底層原理和基礎(chǔ)操作的實現(xiàn)。我們可以根據(jù)實際需要或者自己的理解，從基礎(chǔ)操作入手，將簡單的方法演化為更高級的功能。參考資料《數(shù)據(jù)結(jié)構(gòu)》

南昌大學(xué)實驗報告實驗三順序二叉樹學(xué)生姓名：xx學(xué)號：xxxxxxxx專業(yè)班級：計算機185班實驗類型：□驗證□綜合□設(shè)計□創(chuàng)新實驗日期：2019-11-7實驗成績：實驗項目名稱順序二叉樹及其基本操作實驗?zāi)康慕㈨樞蚨鏄洳崿F(xiàn)基本操作：1.求樹的深度2.求樹的節(jié)點數(shù)3.打印二叉樹4.二叉樹左右節(jié)點互換。實驗基本原理采用數(shù)組的方式存儲二叉樹，二叉樹各節(jié)點的關(guān)系由其對應(yīng)的下標之間的數(shù)學(xué)關(guān)系判定。即存在下標為i存在有效節(jié)點n1，若下標為2i存在有效節(jié)點n2，下標2i+1存在有效節(jié)點n3，則n2為n1的左子節(jié)點，n3為n1的右子節(jié)點。主要儀器設(shè)備及耗材PC微型計算機，C++集成開發(fā)環(huán)境編譯器。實驗步驟（完整內(nèi)容見光盤）問題分析與程序設(shè)計樹的有效節(jié)點數(shù)可以通過遍歷存儲二叉樹的數(shù)組，記錄有效節(jié)點實現(xiàn)。求樹的深度可以通過判斷最后一個節(jié)點所在的區(qū)間范圍，即求出2k-1~2k，則k為這棵樹的最大深度。二叉樹的左右節(jié)點互換則是在每一層中，將該層對應(yīng)的節(jié)點互換即可。打印二叉樹則要計算好對應(yīng)的空格與樹枝，逐層打印。源代碼/**

*

程序采用了動態(tài)建立數(shù)組的方式，程序在C14或更新的cpp編譯環(huán)境下才能正常運行

*

*/

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

}//數(shù)組初始化

int

i

=

1;

string

s

=

"OK";

string

user_input;//輸入信息

string

parent;//雙親節(jié)點的信息

string

child_flag;//判斷是否為左/右孩子

string

NodeName;//孩子節(jié)點的信息

int

index

=

1;

while

(s

!=

"END"

&&

s

!=

"end")

{

cout

<<

"請輸入順序二叉樹各個節(jié)點的信息："

<<

"(少于"

<<

MAX_TREE_SIZE

<<

"個節(jié)點）"

<<

endl;

cout

<<

"輸入END結(jié)束!"

<<

endl;

cout

<<

"輸入樣例：A

L

B"

<<

endl

<<

"其中：A是要輸入的節(jié)點的雙親節(jié)點"

<<

endl

<<

"L指定是左節(jié)點還是右節(jié)點"

<<

endl

<<

"B是新節(jié)點的名稱"

<<

endl;

if

(index

==

1)

cout

<<

"頭節(jié)點的雙親節(jié)點，左右子節(jié)點的標記

可以用空格代替"

<<

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;

}

}//找最后一個節(jié)點的下標

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;//記錄當(dāng)前層數(shù)

int

temp

=

0;//臨時變量

int

depth

=

GetTreeDepth(T);//樹的總深度

int

Node_num

=

GetNodeNum(T);//樹的節(jié)點數(shù)

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;

}

}//記錄每個節(jié)點的左右孩子信息

for

(nD

=

1;

nD

<

depth;

nD++)

{

//每層的第一部分，先打節(jié)點

int

count

=

1;

for

(int

k

=

pow(2,

nD

-

1);

k

<

pow(2,

nD);

k++)

{

//計算當(dāng)前層數(shù)的基準空格

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

{

//計算當(dāng)前層數(shù)的基準空格

Base

=

calBase(depth,

nD,

layer);//節(jié)點的基準偏移

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]);

//如果有左子節(jié)點

printSpace(1);

if

(Node_info[k].r_child)

{

cout

<<

"\\";

printUnderline(layer[depth

-

nD]

-

1);

}

else

printSpace(layer[depth

-

nD]);//如果有右子節(jié)點

printSpace(2

*

Base2

+

1);

count++;

continue;

}

if

(Node_info[k].l_child)

{

printUnderline(layer[depth

-

nD]

-

1);

cout

<<

"/";

}

else

printSpace(layer[depth

-

nD]);

//如果有左子節(jié)點

printSpace(1);

if

(Node_info[k].r_child)

{

cout

<<

"\\";

printUnderline(layer[depth

-

nD]

-

1);

}

else

printSpace(layer[depth

-

nD]);//如果有右子節(jié)點

printSpace(2

*

Base2

+

1);

count++;

}

cout

<<

endl;

}

//下面打印最底層的節(jié)點

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

<<

"使用預(yù)設(shè)方案："

<<

endl;

SBT.InitBiTree_Default(T);

cout<<"當(dāng)前的二叉樹為："<<endl;

SBT.printBiTree(T);

cout

<<

endl

<<

"當(dāng)前二叉樹的節(jié)點數(shù)是："

<<

SBT.GetNodeNum(T)

<<

endl;

cout

<<

"當(dāng)前二叉樹的深度是："

<<

SBT.GetTreeDepth(T)

<<

endl;

cout

<<

"將二叉樹的左右節(jié)點互換："

<<

endl;

SBT.NodeExchange(T,

1);

cout

<<

"二叉樹左右節(jié)點互換后的結(jié)果為："

<<

endl;

SBT.printBiTree(T);

return

0;

}

實驗數(shù)據(jù)及處理結(jié)果二叉樹的創(chuàng)建。求二叉樹的節(jié)點數(shù)求二叉樹的深度二叉樹左右節(jié)點互換用戶輸入版思考討論題或體會或?qū)Ω倪M實驗的建議實驗體會：本次實驗的難點在于實現(xiàn)打印二叉樹。因為要考慮打印二叉樹的樹枝部分，所以要提前計算好基準空格數(shù)，根據(jù)基準空格數(shù)才能正確的計算出二叉樹的各個樹枝的打印寬度。在計算基準空格時，要注意每一層的基準空格數(shù)可以利用動態(tài)規(guī)劃從最底層開始地推求出，這樣才能保證打印的二叉樹規(guī)整有序。八、參考資料《數(shù)據(jù)結(jié)構(gòu)》 南昌大學(xué)實驗報告實驗四鏈式二叉樹學(xué)生姓名：xx學(xué)號：xxxxxxxx專業(yè)班級：計算機185班實驗類型：□驗證□綜合□設(shè)計□創(chuàng)新實驗日期：2019-11-14實驗成績：一、實驗項目名稱鏈式二叉樹的創(chuàng)建與遍歷。二、實驗?zāi)康膶崿F(xiàn)分別采用先序方式創(chuàng)建二叉樹，并實現(xiàn)二叉樹的先序，中序，后序遍歷。三、實驗基本原理采用先序方式創(chuàng)建鏈式二叉樹，樹的各個節(jié)點的關(guān)系由各個節(jié)點的指針指向界定。所以每個節(jié)點的指針域要指明為左子節(jié)點，右子節(jié)點，雙親節(jié)點。先序遍歷定義為：先訪問根節(jié)點，再先序遍歷左子樹，再先序遍歷右子樹。中序遍歷的定義為：先中序遍歷左子樹，再訪問根節(jié)點，再中序遍歷右子樹。后序遍歷的定義為：先后序遍歷左子樹，再后序遍歷右子樹，再訪問根節(jié)點。四、主要儀器設(shè)備及耗材PC微型計算機，C++集成開發(fā)環(huán)境編譯器。五、實驗步驟（完整內(nèi)容見光盤）問題分析與程序設(shè)計二叉樹是遞歸定義的，所以有關(guān)二叉樹的操作，例如二叉樹的創(chuàng)建，遍歷，核心思想都是遞歸。所以創(chuàng)建二叉樹時可以采用遞歸方式依次創(chuàng)建每個節(jié)點的左右子節(jié)點。而前序中序后序遍歷的區(qū)別在于打印節(jié)點的時機不同。遞歸的核心思想與棧相類似，為了避免二叉樹的深度過深而出現(xiàn)的棧溢出問題，可以用棧代替遞歸，同樣實現(xiàn)二叉樹的前序中序和后序遍歷。源代碼#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:

//

創(chuàng)建二叉樹

Status

CreatBitTree(BitTree

T,

BitTree

&T_child,

int

i)

{

cout

<<

"輸入一個結(jié)點(輸入END結(jié)束):"

<<

endl;

string

NodeName;

if

(i

==

1)

{

cout

<<

"輸入"

<<

T->data

<<

"的左子節(jié)點，空格表示無該子節(jié)點:"

<<

endl;

}

else

if

(i

==

2)

{

cout

<<

"輸入"

<<

T->data

<<

"的右子節(jié)點，空格表示無該子節(jié)點:"

<<

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;

}

六、實驗數(shù)據(jù)及處理結(jié)果二叉樹的創(chuàng)建。二叉樹的前序、中序、后序遍歷。七、思考討論題或體會或?qū)Ω倪M實驗的建議實驗體會：遞歸是代碼中一種比較特別的形式。代碼雖少，核心思想?yún)s很難理解。然而二叉樹的定義就是用遞歸思想實現(xiàn)，因此本次實驗中涉及的操作都用了遞歸的思想。使用遞歸最關(guān)鍵的是遞歸結(jié)束條件，以及遞歸回溯時各個值的變化。這次實驗中，實現(xiàn)前序、中序、后序遍歷的函數(shù)形態(tài)上很相似，區(qū)別僅僅在于打印節(jié)點信息的位置不同。但是僅僅是位置上的細微區(qū)別，就是算法核心上的本質(zhì)區(qū)別。八、參考資料《數(shù)據(jù)結(jié)構(gòu)》實驗五圖學(xué)生姓名：xx學(xué)號：xxxxxxxx專業(yè)班級：計算機185班實驗類型：□驗證□綜合□設(shè)計□創(chuàng)新實驗日期：2019-11-21實驗成績：一、實驗項目名稱圖的建立與遍歷二、實驗?zāi)康慕o向圖并實現(xiàn)深度優(yōu)先（DFS）遍歷。三、實驗基本原理無向圖實質(zhì)是有雙向邊的有向圖。實驗中對于圖的存儲采用鄰接表的方式。深度優(yōu)先（DFS）類似于先根遍歷，注意要點是要把遍歷過的根節(jié)點進行標記避免重復(fù)遍歷。四、主要儀器設(shè)備及耗材PC微型計算機，C++集成開發(fā)環(huán)境編譯器。五、實驗步驟（完整內(nèi)容見光盤）問題分析與程序設(shè)計本次實驗程序有兩個核心，一：根據(jù)用戶輸入創(chuàng)建對應(yīng)的圖，二：采用深度優(yōu)先遍歷用戶創(chuàng)建的圖并輸出。其中，圖的創(chuàng)建可以在程序中添加適當(dāng)引導(dǎo)語句引導(dǎo)用戶輸入，圖的保存采用鄰接表的方式，具體保存方法可以根據(jù)圖的類型不同而不同。深度優(yōu)先遍歷類似于樹的先根遍歷，為了避免重復(fù)遍歷某些節(jié)點，可以采用創(chuàng)建額外的節(jié)點數(shù)組記錄訪問與否或在創(chuàng)建節(jié)點結(jié)構(gòu)體時加入一個記錄是否訪問過的風(fēng)向標。本次實驗采取了第二種方法。源代碼#include

<iostream>

#include

<string>

using

namespace

std;

#define

INFINITY

INT_MAX

//最大值

#define

MAX_VERTEX_NUM

20

//最大頂點個數(shù)s

typedef

int

Status;

#define

ERROR

0

#define

OK

1

typedef

string

VertextType;

//頂點關(guān)系類型

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;//頂點數(shù)

int

arcnum;//弧數(shù)

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].data

==

c)

{

result