第一篇：數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)一 圖[推薦]

北京郵電大學(xué)信息與通信工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二——圖 學(xué)生姓名： 佘晨陽(yáng) 班

級(jí)： 2014211117 班內(nèi)序號(hào)： 20 學(xué)

號(hào)： 2014210491 日

期： 2015年12月05日

1．實(shí)驗(yàn)要求

根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個(gè)圖。圖的基本功能：

1、圖的建立

2、圖的銷毀

3、深度優(yōu)先遍歷圖

4、廣度優(yōu)先遍歷圖

5、使用普里姆算法生成最小生成樹(shù)

6、使用克魯斯卡爾算法生成最小生成樹(shù)

7、求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑

8、其他：比如連通性判斷等自定義操作

編寫(xiě)測(cè)試main()函數(shù)測(cè)試圖的正確性

2.程序分析

本實(shí)驗(yàn)要求掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解最小生成樹(shù)的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)習(xí)使用圖解決實(shí)際問(wèn)題的能力。

2.1 存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)：1.不帶權(quán)值的無(wú)向圖鄰接矩陣

2.帶權(quán)值的無(wú)向圖鄰接矩陣

3.帶權(quán)值的有向圖鄰接矩陣

1．不帶權(quán)值的無(wú)向圖鄰接矩陣

第1頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

2帶權(quán)值的無(wú)向圖鄰接矩陣.3.帶權(quán)值的有向圖鄰接矩陣

[備注]：

1.在使用打印元素、BFS、DFS 采用無(wú)權(quán)值的無(wú)向圖鄰接矩陣存儲(chǔ)方式 2.在使用PRIM、KRUSKAL、3.在使用最短路徑的算法時(shí)采用具有權(quán)值的有向圖鄰接矩陣存儲(chǔ)方式

2.2 關(guān)鍵算法分析

第2頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

一．圖的鄰接矩陣構(gòu)造函數(shù)：

1.關(guān)鍵算法： template Graph::Graph(f a[], int n, int e)

//帶權(quán)值的圖的構(gòu)造函數(shù) { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];}

//初始化頂點(diǎn)

for(k = 0;k

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

{

arc[k][i] =-1;

if(i == k)arc[k][i] = 0;

//初始化權(quán)值的大小

}

visited[k] = 0;} cout << endl;for(k = 0;k

//初始化邊

{

cout << “請(qǐng)輸入線性鏈接節(jié)點(diǎn):”;

cin >> s1 >> s2 >> height;

arc[convert(s1)][convert(s2)] = height;

arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用無(wú)向圖帶權(quán)值的鄰接矩陣

} cout << endl;cout << “所得鄰接矩陣為：” << endl;

for(k = 0;k

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

{

if(arc[k][i] ==-1)

cout << “∞” << “ ”;

else cout << arc[k][i] << “ ”;

//打印鄰接矩陣的格式

}

cout << endl;

} cout << endl 2.算法的時(shí)間復(fù)雜度

第3頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

有構(gòu)造可知，初始化時(shí)其時(shí)間復(fù)雜度：O(n2)

二．深度優(yōu)先便利DFS:

1.關(guān)鍵算法

①?gòu)哪稠旤c(diǎn)v出發(fā)并訪問(wèn)

②訪問(wèn)v的第一個(gè)未訪問(wèn)的鄰接點(diǎn)w，訪問(wèn)w的第一個(gè)未訪問(wèn)的鄰接點(diǎn)u，……

③若當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問(wèn)過(guò)，則回溯，從上一級(jí)頂點(diǎn)的下一個(gè)未訪問(wèn)過(guò)的頂點(diǎn)開(kāi)始深度優(yōu)先遍歷

④直到所有和v路徑相通的頂點(diǎn)都被訪問(wèn)到； 2.代碼圖解：

深度優(yōu)先遍歷示意圖 3.代碼詳解：

template void Graph::DFS(int v){ cout << vertex[v];visited[v] = 1;

for(int j = 0;j < vnum;j++)

//連通圖

if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//當(dāng)存在回路時(shí)，則連通深一層遍歷

} 4.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度：O(n2)

空間復(fù)雜度：棧的深度O(n)

輔助空間O(n)

第4頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

三．廣度遍歷BFS 1.關(guān)鍵算法 ①訪問(wèn)頂點(diǎn)v ②依次訪問(wèn)v的所有未被訪問(wèn)的鄰接點(diǎn)v1,v2,v3…

③分別從v1,v2,v3…出發(fā)依次訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn) ④反復(fù)①②③，直到所有和v路徑相通的頂點(diǎn)都被訪問(wèn)到；

2.代碼圖解

3.代碼詳解

1.初始化隊(duì)列Q

2.訪問(wèn)頂點(diǎn)v，visited[v]=1

3.while(隊(duì)列非空)

3.1 v=隊(duì)頭元素出隊(duì)

3.2 訪問(wèn)隊(duì)頭元素的所有未訪問(wèn)的鄰接點(diǎn) 4.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度：O(n2)

空間復(fù)雜度：輔助空間O(n)

四.最小生成樹(shù)——普里姆算法

1,關(guān)鍵思路

一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹(shù)上的結(jié)點(diǎn))和V-U(尚未落在生成樹(shù)上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。主數(shù)據(jù)結(jié)構(gòu)：

鄰接矩陣 輔助數(shù)據(jù)結(jié)構(gòu)：

int

adjvex[MAXSIZE];// U集中的頂點(diǎn)序號(hào)

第5頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

int

lowcost[MAXSIZE];

// U?(V-U)的最小權(quán)值邊

2.代碼圖解

第6頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

第7頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

3;代碼詳解

template void Graph::Prim(){ for(int i = 0;i < vnum;i++)

//輔助數(shù)組存儲(chǔ)所有到的V0邊

{

adjvex[i] = 0;lowcost[i] = arc[0][i];

} lowcost[0] = 0;for(int j = 1;j < vnum;j++)

//循環(huán)n-1次

{

int k = Mininum(lowcost);

//求下一個(gè)頂點(diǎn)

cout << vertex[adjvex[k]] << “->” << vertex[k] << endl;

lowcost[k] = 0;

//U=U+{Vk}

for(int j = 0;j < vnum;j++)

//設(shè)置輔助數(shù)組

{

if((lowcost[j]!= 0 && arc[k][j] < lowcost[j]))

{

lowcost[j] = arc[k][j];

adjvex[j] = k;

}

}

第8頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

} } 4,時(shí)間復(fù)雜度：

時(shí)間復(fù)雜度O(n2)，適合稠密圖

五.最小生成樹(shù)----克魯斯卡爾算法

1,關(guān)鍵思路

先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。2.代碼圖解：

3.代碼詳解

template void Graph::Kruskal()

//最小生成樹(shù)—kruskal算法

{ cout<<“Krusal算法結(jié)果為：”<

int k = 0, j = 0;

while(k < vnum-1){

int m = vedgelist[j].fromv, n = vedgelist[j].endv;

int sn1 = vset[m];

int sn2 = vset[n];

//兩個(gè)頂點(diǎn)分屬

第9頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

不同的集合 if(sn1!= sn2)

{

cout << vertex[m] << “->” << vertex[n] << endl;

k++;

for(int i = 0;i < vnum;i++)

{

if(vset[i] == sn2)

vset[i] = sn1;

//集合sn2全部改成sn1

}

}

j++;} } 4.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度O(nlogn)，適合稀疏圖

六．最短路徑——Dijkstra算法 1.關(guān)鍵代碼

? 按路徑長(zhǎng)度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。? 1)設(shè)置集合s存儲(chǔ)已求得的最短路徑的頂點(diǎn)，? 2)初始狀態(tài)：s=源點(diǎn)v ? 3)疊代算法：

? 直接與v相連的最近頂點(diǎn)vi,加入s ? 從v經(jīng)過(guò)vi可以到達(dá)的頂點(diǎn)中最短的，加入s

……

2.代碼圖解

第10頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

3.代碼詳解

emplate void Graph::ShotPath(f x)

//關(guān)于最短路徑的初始化 { int v=convert(x);

for(int i = 0;i < vnum;i++)

//初始化路徑和點(diǎn)

{

s[i]=0;

disk[i] = arc[v][i];

if(disk[i]!= maxs)path[i] = v;

else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++)

//反復(fù)經(jīng)過(guò)從該點(diǎn)到其他點(diǎn)的路徑

{

if((v = FindMin())==-1)continue;

s[v] = 1;

for(int j = 0;j < vnum;j++)

if(!s[j] &&(disk[j]>arc[v][j] + disk[v]))

{

第11頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

disk[j] = arc[v][j] + disk[v];

path[j] = v;

} } Print();

//打印路徑長(zhǎng)度和遍歷

} 4.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度為：n^2

七．判斷連通圖算法

template bool Graph::judgegraph(){ DFS(convert(vertex[0]));if(count==vnum)

{

cout<<“該圖為連通圖！*******輸入成功！”<

return false;

} else {

cout<<“該圖不為連通圖！*******請(qǐng)重新輸入”<

return true;

} }

時(shí)間復(fù)雜度：n^2

3.程序運(yùn)行結(jié)果

1.測(cè)試主函數(shù)流程：

第12頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

函數(shù)流程圖：

1.輸入圖的連接邊并打印

構(gòu)造下面所示圖的鄰接矩陣：

第13頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

2.判斷圖連通是否成功

3.BFS DFS PRIM算法的實(shí)現(xiàn)

第14頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

4.克魯斯卡爾算法實(shí)現(xiàn)過(guò)程

4.有向圖鄰接矩陣的構(gòu)建

第15頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

插入V0位置后打印距離并開(kāi)始回溯

總結(jié)

1.調(diào)試時(shí)出現(xiàn)的問(wèn)題及解決的方法

問(wèn)題一：prim算法中

解決方法：調(diào)整循環(huán)條件，修正函數(shù)體注意有無(wú)Next的區(qū)別

第16頁(yè) 北京郵電大學(xué)信息與通信工程學(xué)院

問(wèn)題二：BFS和DFS同時(shí)在一個(gè)類里作用時(shí)會(huì)輸出錯(cuò)誤

解決方案：每次BFS/DFS使用時(shí)都把visited數(shù)組初始化一遍

問(wèn)題三：在最短路徑，經(jīng)常出現(xiàn)了停止輸入的情況

解決方法：改return為continue，并修改打印算法 2.心得體會(huì)

通過(guò)本次實(shí)驗(yàn)，基本熟練掌握了c++基本語(yǔ)句，尤其對(duì)圖的結(jié)構(gòu)及應(yīng)用有了較深了解；調(diào)試代碼時(shí)盡量做到完成一個(gè)代碼段調(diào)試一次，可以最快檢測(cè)出錯(cuò)誤所在；類的封裝和調(diào)用，類的共有成員和私有成員的設(shè)置。

3.下一步的改進(jìn)

第一，設(shè)置增加圖節(jié)點(diǎn)和邊的函數(shù)

第二，實(shí)現(xiàn)圖形化輸出圖的路徑的功能

第三，主函數(shù)設(shè)計(jì)簡(jiǎn)單，不要過(guò)于累贅

4.程序中出現(xiàn)的亮點(diǎn)

1)利用dfs算法衍生生成判斷是否為連通圖的連通算法

2)采用graph類實(shí)現(xiàn)所有圖的所有算法，所需的數(shù)據(jù)類型均在私有成員內(nèi)，封裝 3)利用convert函數(shù)采取象意輸入，采用ABCD的節(jié)點(diǎn)輸入方式而并非轉(zhuǎn)化成01234再輸入。

4)BFS中采用c++標(biāo)準(zhǔn)庫(kù)的。

5)打印鄰接矩陣時(shí)，打印出非鏈接的∞符號(hào)和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯(cuò)誤，重新輸入圖元素

第17頁(yè)

第二篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)--圖

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)六

實(shí)驗(yàn)內(nèi)容:圖的基本操作

實(shí)驗(yàn)要求:

1)圖的遍歷與基本操作要作為函數(shù)被調(diào)用.2)把自己使用的圖結(jié)構(gòu)明確的表達(dá)出來(lái).3)基本上實(shí)現(xiàn)每個(gè)實(shí)驗(yàn)題目的要求.分組要求：可單獨(dú)完成，也可兩人一組。

實(shí)驗(yàn)?zāi)康?

1)熟悉C/C++基本編程,培養(yǎng)動(dòng)手能力.2)通過(guò)實(shí)驗(yàn),加深對(duì)圖的理解.評(píng)分標(biāo)準(zhǔn)：

1)只完成第一和第二題，根據(jù)情況得4，5分；

2）完成前3題，根據(jù)情況得5至7分；

3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。

題目:

一)建立一個(gè)無(wú)向圖+遍歷+插入

(1)以數(shù)組表示法作為存儲(chǔ)結(jié)構(gòu)，從鍵盤依次輸入頂點(diǎn)數(shù)、弧數(shù)與各弧信息建立一個(gè)無(wú)向圖；

(2)對(duì)（1）中生成的無(wú)向圖進(jìn)行廣度優(yōu)先遍歷并打印結(jié)果；

(3)向（1）中生成的無(wú)向圖插入一條新弧并打印結(jié)果；

二)建立一個(gè)有向圖+遍歷+插入+刪除

(1)以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，從鍵盤輸入圖的頂點(diǎn)與弧的信息建立一個(gè)有向圖；

(2)對(duì)（1）中生成的有向圖進(jìn)行深度優(yōu)先遍歷并打印結(jié)果；

(3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結(jié)果；

(4)在（1）中生成的有向圖中，分別插入與刪除一個(gè)頂點(diǎn)并打印結(jié)果；

(5)在（1）中生成的有向圖中,各頂點(diǎn)的入度與出度并打印結(jié)果；

三）基本應(yīng)用題

（1）編寫(xiě)算法，判斷圖中指定的兩個(gè)頂點(diǎn)是否連通。

（2）編寫(xiě)算法，判斷圖的連通性。如果不連通，求連通分量的個(gè)數(shù)

（3）編寫(xiě)算法，判斷圖中任意兩個(gè)頂點(diǎn)的連通性

（4）編寫(xiě)算法，判斷圖中是否存在回路。

（5）實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法。

四）高級(jí)應(yīng)用題

（1）實(shí)現(xiàn)Prim算法

（2）實(shí)現(xiàn)Kruskal算法

（3）實(shí)現(xiàn)迪杰斯特拉算法

（4）實(shí)現(xiàn)拓?fù)渑判蛩惴?/p>

（5）實(shí)現(xiàn)關(guān)鍵路徑算法

第三篇：北化航天工業(yè)學(xué)院~數(shù)據(jù)結(jié)構(gòu)~實(shí)驗(yàn)5圖

實(shí)驗(yàn)五：圖的應(yīng)用

班級(jí)學(xué)號(hào)姓名

一、實(shí)驗(yàn)預(yù)備知識(shí)復(fù)習(xí)C++中的全局變量的概念。復(fù)習(xí)圖的鄰接矩陣和鄰接表兩種存儲(chǔ)方式。復(fù)習(xí)圖的兩種遍歷方法和求圖的最小生成樹(shù)的方法。

二、實(shí)驗(yàn)?zāi)康恼莆請(qǐng)D的鄰接矩陣和鄰接表兩種存儲(chǔ)方法。掌握有關(guān)圖的操作算法并用高級(jí)語(yǔ)言實(shí)現(xiàn)。熟悉圖的構(gòu)造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)與算法有著密切聯(lián)系。掌握?qǐng)D的兩種搜索路徑的遍歷算法。掌握求圖的最小生成樹(shù)的普里姆算法和克魯斯卡爾算法。

三、實(shí)驗(yàn)內(nèi)容創(chuàng)建給定的圖，從鄰接表和鄰接矩陣兩種存儲(chǔ)方式中選擇一種。對(duì)所創(chuàng)建的圖進(jìn)行深度和廣度優(yōu)先搜索遍歷，給出遍歷過(guò)程中的頂點(diǎn)序列。3 求圖的最小生成樹(shù)，按構(gòu)造順序輸出邊的序列。編寫(xiě)一個(gè)主函數(shù)，將上面函數(shù)連在一起，構(gòu)成一個(gè)完整程序。將實(shí)驗(yàn)源程序調(diào)試并運(yùn)行。

四、實(shí)驗(yàn)要求

所建立的圖為：

? 用鄰接表存儲(chǔ)結(jié)構(gòu)時(shí)，所創(chuàng)建的單鏈表以結(jié)點(diǎn)的從小到大排列。? 注意標(biāo)志數(shù)組visited[n+1] 的定義和賦值。

? 將頂點(diǎn)1作為起點(diǎn)。

五、實(shí)驗(yàn)結(jié)果

給出源程序及輸入、輸出結(jié)果。

六、實(shí)驗(yàn)總結(jié)

實(shí)驗(yàn)過(guò)程中遇到的問(wèn)題及解決方法，收獲。

第四篇：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(shū)

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)(訓(xùn))指導(dǎo)書(shū)

電氣與信息工程學(xué)院實(shí)驗(yàn)中心

前 言

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校研究生入學(xué)考試專業(yè)課必考課程之一。它主要介紹線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖形結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲(chǔ)實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時(shí)、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法分析、設(shè)計(jì)能力及良好的程序設(shè)計(jì)習(xí)慣。通過(guò)學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)，能夠根據(jù)實(shí)際問(wèn)題選取合適的存儲(chǔ)方案，設(shè)計(jì)出簡(jiǎn)潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開(kāi)發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實(shí)驗(yàn)是兩個(gè)關(guān)鍵環(huán)節(jié)。學(xué)生理解算法的最佳途徑是上機(jī)實(shí)驗(yàn)。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫(xiě)該實(shí)驗(yàn)指導(dǎo)書(shū)。

一、實(shí)驗(yàn)?zāi)康摹⒁蠛腿蝿?wù)

計(jì)算機(jī)編程中加工處理的對(duì)象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)編寫(xiě)計(jì)算機(jī)程序僅僅了解計(jì)算機(jī)語(yǔ)言是不夠的，還必須掌握數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法，這是數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)和研究的內(nèi)容。由于數(shù)據(jù)結(jié)構(gòu)的原理和算法較抽象，而該課程一般在本科低年級(jí)開(kāi)設(shè)，對(duì)于計(jì)算機(jī)程序設(shè)計(jì)知識(shí)的初學(xué)者，理解和掌握其中的原理就顯得較為困難。

1.熟練掌握C語(yǔ)言的編輯、編譯、調(diào)試程序。2.會(huì)書(shū)寫(xiě)類C語(yǔ)言的算法，并將算法轉(zhuǎn)變?yōu)槌绦驅(qū)崿F(xiàn)。

3.正確理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯特性和存儲(chǔ)表示和基本操作的算法實(shí)現(xiàn)。4.有較強(qiáng)的邏輯分析能力。

5.針對(duì)問(wèn)題的不同選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法設(shè)計(jì)的能力和動(dòng)手實(shí)驗(yàn)的技能。

6.學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用設(shè)計(jì)的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。

7.本課程的學(xué)習(xí)過(guò)程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)生編寫(xiě)的程序結(jié)構(gòu)清楚、正確易讀，符合軟件過(guò)程的規(guī)范，從而培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。

8.通過(guò)若干數(shù)據(jù)結(jié)構(gòu)應(yīng)用實(shí)例，引導(dǎo)學(xué)生學(xué)習(xí)數(shù)據(jù)類型的使用，為今后學(xué)習(xí)面向?qū)ο蟮某绦蜃鲆恍╀亯|。

二、實(shí)驗(yàn)基本內(nèi)容及學(xué)時(shí)分配

為了達(dá)到實(shí)驗(yàn)?zāi)康模菊n程安排了4個(gè)實(shí)驗(yàn)單元，訓(xùn)練的重點(diǎn)在于基本的數(shù)據(jù)結(jié)構(gòu)，而不是強(qiáng)調(diào)面面俱到。各實(shí)驗(yàn)單元與教科書(shū)的各章只具有粗略的對(duì)應(yīng)關(guān)系，一個(gè)實(shí)驗(yàn)題常常涉及到幾部分教學(xué)內(nèi)容?？倢W(xué)時(shí)：8學(xué)時(shí)。

1、線性表（2學(xué)時(shí)）

（1）熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實(shí)現(xiàn)；（2）以線性表的各種操作（建立、插入、刪除等）的實(shí)現(xiàn)為重點(diǎn)；

（3）通過(guò)本次實(shí)驗(yàn)幫助學(xué)生提高C語(yǔ)言的編程能力（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。

2、數(shù)組和廣義表（2學(xué)時(shí)）（1）掌握稀疏矩陣的壓縮存儲(chǔ)

（2）掌握稀疏矩陣的轉(zhuǎn)置算法

3、樹(shù)與二叉樹(shù)（2學(xué)時(shí)）

常見(jiàn)的二叉樹(shù)遍歷算法有先序遍歷，中序遍歷和后序遍歷算法。實(shí)現(xiàn)簡(jiǎn)單的先序遍歷，中序遍歷和后序遍歷算法。

4、排序（2學(xué)時(shí)）

常見(jiàn)的內(nèi)部排序算法，插入類排序算法，如直接插入排序和希爾排序；交換類排序算法，如冒泡排序和快速排序；選擇類排序算法，如簡(jiǎn)單選擇排序、樹(shù)形選擇類排序和堆排序。實(shí)冒泡排序或者直接插入排序算法。

三、說(shuō)明

該課程采用理論與實(shí)踐相結(jié)合的教學(xué)方法，集知識(shí)性與趣味性于一體，達(dá)到良好的教學(xué)效果。硬件要求：在多媒體教室講解及演示。為保證教學(xué)順利進(jìn)行，要求實(shí)驗(yàn)室提供電腦等設(shè)備。學(xué)生每次上機(jī)實(shí)驗(yàn)都必須遵守實(shí)驗(yàn)室的有關(guān)規(guī)定。

四、實(shí)驗(yàn)報(bào)告規(guī)范 實(shí)驗(yàn)報(bào)告的內(nèi)容包括：

1、實(shí)驗(yàn)?zāi)康模赫f(shuō)明實(shí)驗(yàn)所驗(yàn)證的知識(shí)點(diǎn)。

2、需求分析：以無(wú)歧義的陳述說(shuō)明程序設(shè)計(jì)的任務(wù)、約束條件、輸入輸出要求、對(duì)功能的規(guī)定及模型。

3、邏輯設(shè)計(jì)：說(shuō)明本程序中用到的所有抽象的數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系。

4、詳細(xì)設(shè)計(jì)：邏輯設(shè)計(jì)中定義的所有數(shù)據(jù)類型的實(shí)現(xiàn)，核心算法的設(shè)計(jì)描述、人機(jī)界面設(shè)計(jì)、函數(shù)之間調(diào)用關(guān)系的描述，主要功能的算法框架，測(cè)試數(shù)據(jù)設(shè)計(jì)。

5、測(cè)試分析：測(cè)試結(jié)果的分析與討論，測(cè)試過(guò)程中遇到的主要問(wèn)題及采取的解決措施。

6、心得：軟件設(shè)計(jì)與實(shí)現(xiàn)過(guò)程中的經(jīng)驗(yàn)與體會(huì)，進(jìn)一步改進(jìn)的設(shè)想。

7、程序清單：源程序中應(yīng)有足夠的注釋。如果提交源程序軟盤，列出程序文件名。

五、如何提高上機(jī)效率

為了提高上機(jī)的效率，真正達(dá)到實(shí)驗(yàn)?zāi)康?，要求同學(xué)做好實(shí)驗(yàn)前的準(zhǔn)備工作，寫(xiě)好實(shí)驗(yàn)預(yù)習(xí)報(bào)告，即實(shí)驗(yàn)報(bào)告規(guī)范中的1）、2）、3）、4）部分，編寫(xiě)好程序，并用一組測(cè)試數(shù)據(jù)手工執(zhí)行程序靜態(tài)檢查程序是否有錯(cuò)，通過(guò)閱讀、執(zhí)行程序或給別人講解自己的程序而深入全面地理解程序邏輯，提高程序的正確性。對(duì)C語(yǔ)言程序不熟悉的同學(xué)，上機(jī)時(shí)最好帶上C語(yǔ)言程序設(shè)計(jì)的教材，以備查閱。調(diào)試中遇到問(wèn)題，應(yīng)認(rèn)真分析，確定可疑點(diǎn)，設(shè)置調(diào)試斷點(diǎn)或輸出斷點(diǎn)處變量的值，以便發(fā)現(xiàn)問(wèn)題，迅速排除問(wèn)題，加快調(diào)試速度。

實(shí)驗(yàn)室要求：

不能曠課，不遲到，不穿拖鞋進(jìn)實(shí)驗(yàn)室

實(shí)驗(yàn)需預(yù)習(xí)報(bào)告（不能單純抄寫(xiě)，預(yù)習(xí)程序代碼）實(shí)驗(yàn)報(bào)告（總結(jié)，注釋，實(shí)驗(yàn)結(jié)果）

目 錄

實(shí)驗(yàn)一 線性表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）..........................................4 實(shí)驗(yàn)二 數(shù)組和廣義表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）....................................6 實(shí)驗(yàn)三 樹(shù)與二叉樹(shù)（設(shè)計(jì)性實(shí)驗(yàn)）..........................................8 實(shí)驗(yàn)四 排序（設(shè)計(jì)性實(shí)驗(yàn)）................................................9

實(shí)驗(yàn)一

線性表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）

一、實(shí)驗(yàn)?zāi)康?/p>

1.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。

3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。4.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表中的各種基本操作。

二、實(shí)驗(yàn)內(nèi)容

1.順序線性表的建立、插入及刪除。2.鏈?zhǔn)骄€性表的建立、插入及刪除。

三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦

四、實(shí)驗(yàn)步驟

1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。

2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68。

3.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。

五、實(shí)驗(yàn)提示

1.由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。

在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/*

線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/*

順序表的長(zhǎng)度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。

2.注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。

3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：

typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域

struct node *next;//指針域

}linklist;

注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：

p=(linklist *)malloc(sizeof(linklist));該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。

六、實(shí)驗(yàn)總結(jié)與思考

1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？

實(shí)驗(yàn)二

數(shù)組和廣義表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握稀疏矩陣的壓縮存儲(chǔ) 2.掌握稀疏矩陣的轉(zhuǎn)置算法

二、實(shí)驗(yàn)內(nèi)容

1.實(shí)現(xiàn)上三角陣的壓縮存儲(chǔ)。

2.用三元組順序表存儲(chǔ)稀疏矩陣，并實(shí)現(xiàn)矩陣的轉(zhuǎn)置。

三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦

四、實(shí)驗(yàn)步驟

1.創(chuàng)建一個(gè)數(shù)組。2.輸入數(shù)據(jù)

3.給定矩陣任一元素的下標(biāo)，4.打印給定下標(biāo)所對(duì)應(yīng)的數(shù)據(jù)。5.創(chuàng)建三元組順序表。?a22 7.A輸出對(duì)應(yīng)的矩陣。??

21五、實(shí)驗(yàn)提示 ?aaa6.輸入矩陣中的數(shù)據(jù)。?11?a11??a?313233a2122?1.對(duì)于如下對(duì)稱矩陣： ??A?aaa?4243?41?a31a32a33??1個(gè)位置，a21存入到第二個(gè)位置，?將它們存入到一個(gè)線性數(shù)組中B，不存非零元素，a11存入到第a41a42aija44????aij的位則aij能存到第幾個(gè)位置，我們要以用梯形公式算面積。置是它上面的元素之和再加上左邊的元素之和。

它上面的元素之和為((1+(i-1))×(i-1)/2，左邊的元素為(j-1)所以這個(gè)元素存儲(chǔ)的位置為k=i(i-1)/2+j-1。

因?yàn)榫仃嘇為對(duì)稱矩陣，(另一部分沒(méi)有寫(xiě)出)，所以另一部分的元素為 k=j(j-1)/2+i-1.所以存在關(guān)系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i

2.結(jié)點(diǎn)結(jié)構(gòu)

struct triple{ int i,j;//非零元的行下標(biāo)和列下標(biāo) elemtype e;//非零元數(shù)據(jù)} 三元組順序表存儲(chǔ)類型 struct tsmatrix{ triple data[12500];aa?????a44??

int mu,nu,tu;} 三元順序表的轉(zhuǎn)置 方法：(1)將矩陣行列互換，(2)重排矩陣

六、實(shí)驗(yàn)總結(jié)與思考

1.如何存儲(chǔ)三對(duì)角陣？

2.如何用行邏輯鏈接順序表及十字鏈表存儲(chǔ)稀疏矩陣？

實(shí)驗(yàn)三

樹(shù)與二叉樹(shù)（設(shè)計(jì)性實(shí)驗(yàn)）

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握稀疏矩陣的壓縮存儲(chǔ) 2.掌握稀疏矩陣的轉(zhuǎn)置算法

二、實(shí)驗(yàn)內(nèi)容

1.練習(xí)二叉樹(shù)的建立與存儲(chǔ) 2.練習(xí)二叉樹(shù)的遍歷

三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦

四、實(shí)驗(yàn)步驟

1.建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。

2.建立二叉樹(shù),并通過(guò)調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。

五、實(shí)驗(yàn)提示

建立二叉樹(shù)的代碼如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉樹(shù)，輸入結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)和值,編號(hào)和值之間用逗號(hào)隔開(kāi)nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$')

{q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一個(gè)新結(jié)點(diǎn)q*/

q->data = x;q->lchild = NULL;q->rchild = NULL;

s[i] = q;/*q新結(jié)點(diǎn)地址存入s指針數(shù)組中*/

if(i!= 1)/*i = 1，對(duì)應(yīng)的結(jié)點(diǎn)是根結(jié)點(diǎn)*/

{j = i / 2;/*求雙親結(jié)點(diǎn)的編號(hào)j*/

if(i % 2 == 0)s[j]->lchild = q;/*q結(jié)點(diǎn)編號(hào)為偶數(shù)則掛在雙親結(jié)點(diǎn)j的左邊*/

else s[j]->rchild = q;} /*q結(jié)點(diǎn)編號(hào)為奇數(shù)則掛在雙親結(jié)點(diǎn)j的右邊*/

printf(“i,x = ”);

scanf(“%d,%c”,&i,&x);} return s[1];/*返回根結(jié)點(diǎn)地址*/ }

六、實(shí)驗(yàn)總結(jié)與思考

1.如何用孩子兄弟表示法存儲(chǔ)樹(shù)？ 2.熟悉及難赫夫曼樹(shù)。

實(shí)驗(yàn)四

排序（設(shè)計(jì)性實(shí)驗(yàn)）

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法； 2.深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用； 3.了解各種方法的排序過(guò)程及其時(shí)間復(fù)雜度的分析方法。

二、實(shí)驗(yàn)內(nèi)容

統(tǒng)計(jì)成績(jī)

給出n個(gè)學(xué)生的考試成績(jī)表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計(jì)一個(gè)算法：

（1）按分?jǐn)?shù)高低次序，打印出每個(gè)學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2）按名次列出每個(gè)學(xué)生的姓名與分?jǐn)?shù)。

三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦

四、實(shí)驗(yàn)步驟

1.定義結(jié)構(gòu)體。2.定義結(jié)構(gòu)體數(shù)組。

3.定出主程序，對(duì)數(shù)據(jù)進(jìn)行排序。

五、實(shí)驗(yàn)提示

#define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n請(qǐng)輸入學(xué)生成績(jī): n”);for(i=0;iR[max].score)max=j;

if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score

六、實(shí)驗(yàn)總結(jié)與思考

1.快速排序算法解決本問(wèn)題。2.較各種排序算法的優(yōu)缺點(diǎn)及。

3.使用其它排序算法實(shí)現(xiàn)該問(wèn)題（直接插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序等）。

第五篇：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(shū)

數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 指 導(dǎo) 書(shū)

南京工程學(xué)院

信息管理與信息系統(tǒng)教研室

2014年3月

實(shí)驗(yàn)一 線性表操作

一、實(shí)驗(yàn)?zāi)康?/p>

1.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。

3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。4.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表中的各種基本操作。

二、實(shí)驗(yàn)內(nèi)容

1.順序線性表的建立、插入及刪除。

2.鏈?zhǔn)骄€性表的建立、插入及刪除。

三、實(shí)驗(yàn)步驟

1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68。

3.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。

四、實(shí)現(xiàn)提示

1.由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。

在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長(zhǎng)度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。

2.注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。

3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：

typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域

struct node *next;//指針域

}linklist;注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：

p=(linklist *)malloc(sizeof(linklist));該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。

五、思考與提高

1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？

實(shí)驗(yàn)二

棧和隊(duì)列的應(yīng)用

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握棧的順序表示和實(shí)現(xiàn) 2.掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

二、實(shí)驗(yàn)內(nèi)容

1.編寫(xiě)一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2.實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。

三、實(shí)驗(yàn)步驟

1.順序棧(1)初始化順序棧;(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 2.鏈隊(duì)列

(1)初始化并建立鏈隊(duì)列(2.)入鏈隊(duì)列(3)出鏈隊(duì)列(4)遍歷鏈隊(duì)列

四、實(shí)現(xiàn)提示

1./*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack;

/*初始化順序棧函數(shù)*/ void InitStack(SqStack *p)

{q=(SqStack*)malloc(sizeof(SqStack));/*申請(qǐng)空間*/} /*入棧函數(shù)*/ void Push(SqStack *p,ElemType x){if(p->toptop=p->top+1;/*棧頂+1*/ p->stack[p->top]=x;} /*數(shù)據(jù)入棧*/ } /*出棧函數(shù)*/ ElemType Pop(SqStack *p){x=p->stack[p->top];/*將棧頂元素賦給x*/ p->top=p->top-1;} /*棧頂-1*/ /*獲取棧頂元素函數(shù)*/ ElemType GetTop(SqStack *p){ x=p->stack[p->top];} /*遍歷順序棧函數(shù)*/ void OutStack(SqStack *p){ for(i=p->top;i>=0;i--)printf(“第%d個(gè)數(shù)據(jù)元素是：%6dn”,i,p->stack[i]);} /*置空順序棧函數(shù)*/ void setEmpty(SqStack *p){ p->top=-1;} 可參考代碼： #include “stdio.h” #define StackSize 100 typedef int ElemType;main(){

SqStack S;

ElemType e;

int N;

/*初始化順序棧*/ /*入棧*/ /*出棧*/ /*遍歷順序棧*/ getch();}

2./*定義鏈隊(duì)列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue;

/*初始化并建立鏈隊(duì)列函數(shù)*/ void creat(Lqueue *q)

{ h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請(qǐng)空間*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循環(huán)快速輸入數(shù)據(jù)*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入鏈隊(duì)列函數(shù)快速輸入數(shù)據(jù)*/ } /*入鏈隊(duì)列函數(shù)*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出鏈隊(duì)列函數(shù)*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*釋放空間*/ /*遍歷鏈隊(duì)列函數(shù)*/ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊(duì)尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可參考如下代碼： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){

LinkQueue Q;

ElemType e;

/*初始化并建立鏈隊(duì)列*/

/*入鏈隊(duì)列*/ /*出鏈隊(duì)列*/

*遍歷鏈隊(duì)列*/

}

DestoryQueue(&Q);

getch();}

五、思考與提高

1.讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？ 試寫(xiě)一個(gè)算法，判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是?回文?。實(shí)驗(yàn)三 樹(shù)操作

一、實(shí)驗(yàn)?zāi)康?/p>

1.通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的建立與存儲(chǔ) 2.通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的遍歷方法

二、實(shí)驗(yàn)內(nèi)容

1.練習(xí)二叉樹(shù)的建立與存儲(chǔ) 2.練習(xí)二叉樹(shù)的遍歷

三、實(shí)驗(yàn)步驟

1.建立二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。

2.建立二叉樹(shù),并通過(guò)調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。

四、實(shí)現(xiàn)提示

1.采用遞歸方法建立二叉樹(shù)：

首先建立二叉樹(shù)的根 結(jié)點(diǎn)，然后建立其左右子樹(shù)，直到空子樹(shù)為止。

2.先序遍歷、中序遍歷與后序遍歷二叉樹(shù)。#include #include typedef int Status;typedef char ElemType;typedef struct BiTNode { ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/*建立二叉樹(shù)*/

BiTree CreateBiTree(BiTree &T){ } /*先序遍歷*/ Status PreOrderTraverse(BiTree T){ } /*中序遍歷*/ Status InOrderTraverse(BiTree T){ } /*后序遍歷*/ Status PostOrderTraverse(BiTree T){ }

int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍歷*/ InOrderTraverse(T);printf(“n”);/*中序遍歷*/ PostOrderTraverse(T);printf(“n”);/*后序遍歷*/

return 0;}

五、思考與提高

編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。