第一篇：數(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）編寫算法，判斷圖中指定的兩個(gè)頂點(diǎn)是否連通。

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

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

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

（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)鍵路徑算法

第二篇：數(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、使用普里姆算法生成最小生成樹

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

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

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

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

2.程序分析

本實(shí)驗(yàn)要求掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解最小生成樹的思想和相關(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)開始深度優(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)

四.最小生成樹——普里姆算法

1,關(guān)鍵思路

一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹上的結(jié)點(diǎn))和V-U(尚未落在生成樹上的頂點(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)，適合稠密圖

五.最小生成樹----克魯斯卡爾算法

1,關(guān)鍵思路

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

3.代碼詳解

template void Graph::Kruskal()

//最小生成樹—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位置后打印距離并開始回溯

總結(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)的目的和要求

通過(guò)上機(jī)實(shí)驗(yàn)加深對(duì)課程內(nèi)容的理解，增加感性認(rèn)識(shí)，提高軟件設(shè)計(jì)、編寫及調(diào)試程序的能力。

要求所編的程序能正確運(yùn)行，并提交實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)報(bào)告的基本要求為：

1、需求分析：陳述程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)程序要做什么，明確規(guī)定：

（1）輸入的形式和輸出值的范圍；

（2）輸出的形式；

（3）程序所能達(dá)到的功能；

（4）測(cè)試數(shù)據(jù)：包括正確的輸入輸出結(jié)果和錯(cuò)誤的輸入及輸出結(jié)果。

2、概要設(shè)計(jì)：說(shuō)明用到的數(shù)據(jù)結(jié)構(gòu)定義、主程序的流程及各程序模塊之間的調(diào)用關(guān)系。

3、詳細(xì)設(shè)計(jì)：提交帶注釋的源程序或者用偽代碼寫出每個(gè)操作所涉及的算法。

4、調(diào)試分析：

（1）調(diào)試過(guò)程中所遇到的問(wèn)題及解決方法；

（2）算法的時(shí)空分析；

（3）經(jīng)驗(yàn)與體會(huì)。

5、用戶使用說(shuō)明：說(shuō)明如何使用你的程序，詳細(xì)列出每一步操作步驟。

6、測(cè)試結(jié)果：列出對(duì)于給定的輸入所產(chǎn)生的輸出結(jié)果。若有可能，測(cè)試隨輸入規(guī)模的增長(zhǎng)所用算法的實(shí)際運(yùn)行時(shí)間的變化。

第四篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告

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

課程 數(shù)據(jù)結(jié)構(gòu) _ 院 系

專業(yè)班級(jí) 實(shí)驗(yàn)地點(diǎn)

姓 名 學(xué) 號(hào)

實(shí)驗(yàn)時(shí)間 指導(dǎo)老師

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

一﹑實(shí)驗(yàn)名稱：

實(shí)驗(yàn)一——鏈表

二﹑實(shí)驗(yàn)?zāi)康模?/p>

1.了解線性表的邏輯結(jié)構(gòu)特性；

2.熟悉鏈表的基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，熟練掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法；

3.掌握鏈表的基本操作（建表、插入、刪除等）4.掌握循環(huán)鏈表的概念，加深對(duì)鏈表的本質(zhì)的理解。5.掌握運(yùn)用上機(jī)調(diào)試鏈表的基本方法

三﹑實(shí)驗(yàn)內(nèi)容：

（1）（2）（3）（4）創(chuàng)建一個(gè)鏈表 在鏈表中插入元素 在鏈表中刪除一個(gè)元素 銷毀鏈表 四﹑實(shí)驗(yàn)步驟與程序

#include #include typedef struct LNode {int data;struct LNode *next;}Lnode, *LinkList;//假設(shè)下面的鏈表均為帶頭結(jié)點(diǎn)。void CreatLinkList(LinkList &L,int j){//建立一個(gè)鏈表L,數(shù)據(jù)為整數(shù)，數(shù)據(jù)由鍵盤隨機(jī)輸入。

LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L;

cout<<“請(qǐng)輸入一個(gè)鏈表：”<

for(int i=0;i

{

p=(LinkList)malloc(sizeof(Lnode));

cin>>p->data;

p->next=q->next;

q->next=p;

q=p;

} } int PrintLinkList(LinkList &L){//輸出鏈表L的數(shù)據(jù)元素

LinkList p;

} void LinkListLengh(LinkList &L){//計(jì)算鏈表L的數(shù)據(jù)元素個(gè)數(shù)。int i=0;p=L->next;if(L->next==NULL){

} cout<<“鏈表的數(shù)據(jù)元素為:”;while(p)

{

cout<

data<<“ ”;

p=p->next;} cout<<“鏈表沒有元素!”<

} LinkList p;p=L->next;while(p){

i++;

p=p->next;

} cout<<“鏈表的數(shù)據(jù)元素個(gè)數(shù)為:”<

LinkList p,s;int j=0;p=L;

while(p&&j

} if(!p||j>i-1){ p=p->next;++j;

}

} cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//刪除鏈表L的第I個(gè)數(shù)據(jù)元素。

LinkList p,q;int j=0;p=L;while(p->next&&j

} if(!(p->next)||j>i-1){ p=p->next;++j;

}

} cout<<“刪除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//銷毀鏈表L。

LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q;

free(p);} p=q;

free(L);

cout<<“鏈表已經(jīng)被銷毀!”<

LinkList L;

int i,j,x;cout<<“第一次數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)—鏈表”<>j;

CreatLinkList(L,j);

LinkListLengh(L);

PrintLinkList(L);

cout<<“在第幾個(gè)元素前插入:”;cin>>i;cout<<“輸入插入的元素:”;cin>>x;

InsertLinkList(L,i,x);

LinkListLengh(L);

PrintLinkList(L);

cout<<“輸入刪除元素的位置:”;cin>>i;

DeleteLinkList(L,i);

LinkListLengh(L);

PrintLinkList(L);

cout<<“銷毀程序后為:”<

DestroyLinkList(L);} 五﹑實(shí)驗(yàn)結(jié)果

六﹑實(shí)驗(yàn)心得體會(huì)：

鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：一為用戶需要用的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址。

實(shí)驗(yàn)的程序設(shè)計(jì)規(guī)劃（實(shí)現(xiàn)的功能、分幾個(gè)模塊、子函數(shù)）（1）編寫鏈表創(chuàng)建子函數(shù)void CreatLinkList(L,j)（2）編寫鏈表插入子函數(shù) int InsertLinkList(LinkList &L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList &L)（4）編寫鏈表刪除子函數(shù) int DeleteLinkList(LinkList &L,int i)（5）編寫鏈表銷毀子函數(shù)void DestroyLinkList(LinkList &L)（6）編寫主函數(shù)Main()，通過(guò)功能菜單調(diào)用子函數(shù)（7）編譯調(diào)試程序

經(jīng)過(guò)多次的調(diào)試，修改，實(shí)驗(yàn)結(jié)果終于正確了，在這個(gè)過(guò)程中，經(jīng)歷了不知道怎么進(jìn)行聲明區(qū)的編寫如包含文件，宏定義，函數(shù)聲明，全局變量聲明，結(jié)構(gòu)體等的定義等的結(jié)合，到學(xué)會(huì)了使用先把程序主要規(guī)劃為四個(gè)部分來(lái)寫就簡(jiǎn)單多了，第一，定義；第二，寫所要調(diào)用的子函數(shù)；第三，寫主函數(shù)，調(diào)用子函數(shù)；第四就是程序的編譯與調(diào)試，修改。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)需要我們對(duì)每個(gè)程序的算法有深刻的理解，才能應(yīng)用到實(shí)際中去，因此我們需要在做實(shí)驗(yàn)之前要熟悉實(shí)驗(yàn)的內(nèi)容，且先把所要實(shí)驗(yàn)的程序?qū)懗鰜?lái)，在實(shí)驗(yàn)中就可以查找錯(cuò)誤并加以改正，這是一個(gè)成長(zhǎng)的過(guò)程。

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告一﹑實(shí)驗(yàn)名稱：

實(shí)驗(yàn)二—隊(duì)列

二﹑實(shí)驗(yàn)?zāi)康模?1.掌握隊(duì)列這種抽象數(shù)據(jù)類型的特點(diǎn), 掌握棧與隊(duì)列在實(shí)際問(wèn)題中的應(yīng)用和基本編程技巧,并能在相應(yīng)的問(wèn)題中選用它;2.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別是隊(duì)滿和隊(duì)空的描述方法；

3．掌握棧與隊(duì)列的數(shù)據(jù)類型描述及特點(diǎn)；

4.掌握棧的順序和鏈?zhǔn)酱鎯?chǔ)存表示與基本算法的實(shí)現(xiàn)； 5.掌握隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示與基本操作算法實(shí)現(xiàn);6.按照實(shí)驗(yàn)題目要求，獨(dú)立完成實(shí)際程序的編寫編寫、調(diào)試和運(yùn)行，并通過(guò)用例數(shù)據(jù)的運(yùn)行過(guò)程抓獲相關(guān)屏面驗(yàn)證程序設(shè)計(jì)的正確性； 7.認(rèn)真書寫實(shí)驗(yàn)報(bào)告，并按時(shí)提交。

三﹑實(shí)驗(yàn)內(nèi)容：

對(duì)順序循環(huán)隊(duì)列，常規(guī)的設(shè)計(jì)方法是使用対尾指針和對(duì)頭指針，對(duì)尾指針用于指示當(dāng)前的対尾位置下標(biāo)，對(duì)頭指針用于指示當(dāng)前的対頭位置下標(biāo)。現(xiàn)要求：

（1）掌握棧和隊(duì)列的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。（2）設(shè)計(jì)一個(gè)使用對(duì)頭指針和計(jì)數(shù)器的順序循環(huán)隊(duì)列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊(duì)列，出隊(duì)列，取對(duì)頭元素和判斷隊(duì)列是否為空；

（3）編寫主函數(shù)進(jìn)行測(cè)試。

四﹑實(shí)驗(yàn)步驟與程序

#include #include #include

#define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){

} Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){

} void EnQueue(LinkQueue &Q,int e){

} int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“該鏈隊(duì)為空:”);else printf(“該鏈隊(duì)不為空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入隊(duì)成功”,e);

} if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p;

return OK;void DeQueue(LinkQueue &Q){

} void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊(duì)為空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“隊(duì)首元素刪除成功”);

} if(Q.front==Q.rear)printf(“該鏈隊(duì)為空”);p=Q.front->next;printf(“隊(duì)首元素為:%d”,p->data);void OutQueue(LinkQueue &Q){

} void LengthQueue(LinkQueue &Q){

int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊(duì)為空”);p=Q.front->next;while(p!=Q.rear->next){

} printf(“%d%,”,p->data);p=p->next;

} printf(“該隊(duì)列的長(zhǎng)度為:%d”,f);else {

} p=Q.front->next;while(p!=Q.rear->next){

} printf(“該隊(duì)列的長(zhǎng)度為:%d”,f);p=p->next;f++;void main(){

system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************鏈隊(duì)列功能菜單***********************n”);printf(“1:初始化鏈隊(duì)列，2:判斷鏈隊(duì)列是否為空, 3:進(jìn)入隊(duì)列，4:取出隊(duì)首元素n”);printf(“5:輸出該隊(duì)列的所有元素,6:輸出該隊(duì)列的長(zhǎng)度，7:結(jié)束程序，8:清屏n”);

while(flag){

printf(“n請(qǐng)輸入操作符:”);scanf(“%d”,&i);switch(i){ case 1:

int e,n,k;printf(“請(qǐng)輸入隊(duì)列的長(zhǎng)度:”);scanf(“%d”,&n);printf(“請(qǐng)輸入隊(duì)列的元素:”);for(e=1;e<=n;e++){

} printf(“初始化鏈隊(duì)成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q);

break;case 3:

int j;printf(“請(qǐng)輸入要進(jìn)入隊(duì)列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5:

printf(“該隊(duì)列的元素為:”);OutQueue(Q);break;

case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break;

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

六﹑實(shí)驗(yàn)心得體會(huì)：

程序主要構(gòu)造了主函數(shù)main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等調(diào)用函數(shù)，實(shí)現(xiàn)了隊(duì)列的創(chuàng)立，隊(duì)列是否為空的判斷，入隊(duì)和出隊(duì)等功能。

通過(guò)此次實(shí)驗(yàn)，加深了對(duì)隊(duì)列的存儲(chǔ)結(jié)構(gòu)的了解，同時(shí)也對(duì)程序設(shè)計(jì)能力有了提高，加深了對(duì)隊(duì)列先進(jìn)先出性質(zhì)的理解，它允許在表的一端進(jìn)行插入，在另一端刪除元素，這和我們?nèi)粘Ｉ钪械呐抨?duì)是一致的，最早進(jìn)入隊(duì)列的元素最早離開。我們往往寫不出程序，這其中的原因我覺得是對(duì)程序的結(jié)構(gòu)不是很了解，對(duì)實(shí)驗(yàn)的內(nèi)容也不熟練的結(jié)果，數(shù)據(jù)結(jié)構(gòu)給我們?cè)S多程序的算法和模型，對(duì)我們寫程序的思維有很大的鍛煉，我們應(yīng)珍惜每次上機(jī)實(shí)驗(yàn)的機(jī)會(huì)去實(shí)踐課堂上所學(xué)的東西并從中發(fā)現(xiàn)問(wèn)題，從而達(dá)到提升寫程序的能力。

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告一﹑實(shí)驗(yàn)名稱：

實(shí)驗(yàn)三—二叉樹的遍歷

二﹑實(shí)驗(yàn)?zāi)康模?/p>

1、熟悉二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法；

2、掌握二叉樹的生成，掌握二叉樹的定義和存儲(chǔ)表示，學(xué)會(huì)建立一棵特定二叉樹的方法；

3、理解二叉樹的三種遍歷方法：先序遍歷、中序遍歷和后序遍歷；

4、學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。

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

1、使用類定義實(shí)現(xiàn)二叉樹，補(bǔ)充完整所缺的函數(shù)，并實(shí)現(xiàn)創(chuàng)建和遍歷二叉樹的基本操作；

2、編程實(shí)現(xiàn)在二叉鏈表這種存儲(chǔ)方式下，實(shí)現(xiàn)二叉的遍歷，可采用遞歸或者非遞歸實(shí)現(xiàn)，遍歷算法為在先序、中序和后序遍歷算法。

三、實(shí)驗(yàn)步驟與程序：

#include #include #include typedef struct BiTNode { char data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;//定義結(jié)點(diǎn)類型 BiTree CreateBiTree()//創(chuàng)建樹 { char p;BiTree T;scanf(“%c”,&p);if(p==' ')T=NULL;else { T=(BiTNode *)malloc(sizeof(BiTNode));//為結(jié)點(diǎn)開辟空間 T->data=p;T->lchild=CreateBiTree();T->rchild=CreateBiTree();} return(T);}

void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函數(shù) {

printf(“------------二叉樹的遍歷-------------n”);printf(“請(qǐng)輸入要遍歷的數(shù)：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍歷:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍歷:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍歷:”);printf(“n”);PostOrder(Ta);} 五﹑實(shí)驗(yàn)結(jié)果

六﹑實(shí)驗(yàn)心得體會(huì)：

實(shí)驗(yàn)的程序設(shè)計(jì)規(guī)劃（實(shí)現(xiàn)的功能、分幾個(gè)模塊、子函數(shù)）（1）先序遍歷遞歸算法函數(shù)：void PreOrder(BiTree T)（2）中序遍歷遞歸算法函數(shù)：void InOrder(BiTree T)（3）后續(xù)遍歷遞歸算法函數(shù)：void PostOrder(BiTree T)（4）主函數(shù)的實(shí)現(xiàn)：void main()

在實(shí)驗(yàn)前我認(rèn)真閱讀關(guān)于二叉樹的實(shí)現(xiàn)的內(nèi)容，為編程實(shí)現(xiàn)第一步，本次實(shí)驗(yàn)通過(guò)按上述的實(shí)驗(yàn)步驟一步步實(shí)現(xiàn)的，實(shí)驗(yàn)過(guò)程中出現(xiàn)了一些錯(cuò)誤，經(jīng)過(guò)一步步的調(diào)試，修改錯(cuò)誤，得到了二叉樹的遍歷用遞歸運(yùn)算的方法的程序。通過(guò)這個(gè)實(shí)驗(yàn)，我體會(huì)到了理解數(shù)據(jù)結(jié)構(gòu)的重要性，這有真正理解了定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來(lái)不是很復(fù)雜，這使我更進(jìn)一步理解了函數(shù)遞歸調(diào)用并得到靈活運(yùn)用；在實(shí)現(xiàn)算法上，從算法的效率看，遞歸方法書寫形式較為簡(jiǎn)潔，更為直觀，一般具有較好的空間效率。

總之，不管做什么實(shí)驗(yàn)，我們?cè)谧鰧?shí)驗(yàn)前都要先預(yù)習(xí)，對(duì)所做的實(shí)驗(yàn)有較深的理解，在做實(shí)驗(yàn)的時(shí)候需要很嚴(yán)謹(jǐn)，仔細(xì)的查找錯(cuò)誤，從而能在實(shí)驗(yàn)中收獲知識(shí)，提升自己。

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告4 一﹑實(shí)驗(yàn)名稱：

實(shí)驗(yàn)四—查找

二﹑實(shí)驗(yàn)?zāi)康模?/p>

1、熟悉掌握順序表的查找方法；

2、熟練掌握二叉排序樹的構(gòu)造方法和查找算法

3、掌握描述查找過(guò)程的判定樹的構(gòu)造方法，以及按照定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度；

4、學(xué)會(huì)定義線性表的儲(chǔ)存類型，實(shí)現(xiàn)C++程序的基本結(jié)構(gòu)對(duì)線性表的一些基本操作和具體的函數(shù)定義；

5、掌握順序表的基本操作，實(shí)現(xiàn)順序表的查找的等基本運(yùn)算；

6、掌握對(duì)于多函數(shù)程序的輸入，編輯，調(diào)試和運(yùn)算過(guò)程。

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

1、實(shí)現(xiàn)順序表的查找算法

2、關(guān)于衡量查找的主要操作—查找的查找平均效率的平均長(zhǎng)度的討論。

三、實(shí)驗(yàn)步驟與程序：

#include #define MAX_SIZE 100 typedef struct{ int key;}element;

element list[MAX_SIZE];

int seqsearch(element list[],int searchnum,int num);int main(){

int i,num,searchnum,k;

printf(“---------------數(shù)據(jù)結(jié)構(gòu)查找實(shí)驗(yàn)-------------n”);printf(“請(qǐng)輸入數(shù)據(jù)元素的個(gè)數(shù)：”);scanf(“%d”,&num);printf(“請(qǐng)輸入數(shù)據(jù)的元素：n”);for(i=0;i

printf(“請(qǐng)輸入要查詢的數(shù)據(jù)元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查詢?cè)氐南聵?biāo)為：”);printf(“%dn”,k);} else printf(“查詢?cè)夭淮嬖?。n”);} return 0;}

int seqsearch(element list[],int searchnum,int num){ int j;

list[num].key=searchnum;

for(j=0;list[j].key!=searchnum;j++);return j

六﹑實(shí)驗(yàn)心得體會(huì)：

實(shí)驗(yàn)的程序設(shè)計(jì)規(guī)劃為先寫一個(gè)主函數(shù)int main()，再寫一個(gè)查找的子函數(shù)int seqsearch(element list[],int searchnum,int num)，主函數(shù)通過(guò)調(diào)用子函數(shù)的方法實(shí)現(xiàn)程序的設(shè)計(jì)。

所謂“查找”即為在一個(gè)眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個(gè)“特定的”數(shù)據(jù)元素（或記錄），通過(guò)本次實(shí)驗(yàn)，我更進(jìn)一步的了解數(shù)據(jù)結(jié)構(gòu)程序?qū)嶒?yàn)設(shè)計(jì)實(shí)現(xiàn)算法的基本模型，和算法實(shí)現(xiàn)等基本內(nèi)容，學(xué)會(huì)了順序表的查找方法。

數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告5 一﹑實(shí)驗(yàn)名稱：

實(shí)驗(yàn)五—內(nèi)部排序

二﹑實(shí)驗(yàn)?zāi)康模?/p>

1、通過(guò)實(shí)現(xiàn)下述實(shí)驗(yàn)內(nèi)容，學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況，并加以靈活應(yīng)用。

2、掌握各種排序時(shí)間復(fù)雜度的分析方法。

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

1、插入排序：依次將待排序的序列中的每一個(gè)記錄插入到先前排序好的序列中，直到全部記錄排序完畢。

2、快速排序：首先選擇一個(gè)基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對(duì)兩部分重復(fù)上述過(guò)程，直至整個(gè)序列排序完成。

3、討論各種內(nèi)部排序方法的基本思路，算法特點(diǎn)，排序過(guò)程及它們的時(shí)間復(fù)雜度的分析。

三、實(shí)驗(yàn)步驟與程序：

#include void main(){

} int x;void charu();void kuaisu();printf(“----------內(nèi)部排序---------n”);printf(“

1、插入排序：n”);printf(“

2、選擇排序：n”);printf(“請(qǐng)根據(jù)序號(hào)選擇：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m;

printf(“插入排序n”);

printf(“請(qǐng)輸入個(gè)您想排序的數(shù)據(jù):n”);

for(i=0;i<7;i++)scanf(“%d”,&a[i]);

for(j=1;j<7;j++)

{ m=a[j];

for(i=j-1;i>=0;i--)

{

if(a[i]

break;

else a[i+1]=a[i];

}

a[i+1]=m;

}

printf(“排序成功:”);

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

printf(“ %d”,a[i]);

printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key;

key=L[first];

while(left

{ while((left=key))

right--;

if(left

L[left++]=L[right];

while((left

left++;

if(left

L[left]=key;

return left;

}

quick_sort(int L[],int first,int end)

{ int split;

if(end>first)

{ split=quick(first,end,L);

quick_sort(L,first,split-1);

quick_sort(L,split+1,end);

}

} void kuaisu(){

int a[7],i;

printf(“快速排序n”);

printf(“請(qǐng)輸入個(gè)您想排序的數(shù)據(jù):n”);

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

scanf(“%d”,&a[i]);

quick_sort(a,0,9);

printf(“排序成功:”);

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

printf(“ %d”,a[i]);

printf(“n”);} 五﹑實(shí)驗(yàn)結(jié)果：

六﹑實(shí)驗(yàn)心得體會(huì)：

排序的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，從新排成按關(guān)鍵字有序的序列；直接插入排序的穩(wěn)定性比快速排序高，且算法較簡(jiǎn)單。本次實(shí)驗(yàn)運(yùn)用到的是插入排序和快速排序。

第五篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告

實(shí)習(xí)報(bào)告

題 目 : 實(shí)現(xiàn)一個(gè)約瑟夫環(huán)程序

班級(jí)：031021姓名：王帥學(xué)號(hào)：03102076

一、需求分析

1． 本演示程序中，利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)約瑟夫環(huán)數(shù)據(jù)（即n個(gè)人的編號(hào)和密碼）。

2． 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運(yùn)算結(jié)果顯示在其后。

3． 程序執(zhí)行的命令包括：

1)構(gòu)造單向循環(huán)鏈表；2）進(jìn)行數(shù)值的輸入，并作判斷分析；3）約瑟夫算法的實(shí)現(xiàn)與結(jié)果輸出；4）結(jié)束。

4． 測(cè)試數(shù)據(jù)

m 的初值為20；n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序?yàn)?，1，4，7，2，1，3，5）。

二、概要設(shè)計(jì)

1．單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：

ADT List｛

數(shù)據(jù)對(duì)象：D=｛ai | ai?正整數(shù)，I=1，2，......，n,n≥0｝數(shù)據(jù)關(guān)系：R1=｛< ai-1，ai > |，ai-1，ai?D,I=1，2，......，n｝基本操作：

Init List(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。

List Insert(&L,i,e)

初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L長(zhǎng)度加1。List Delete(&L,i,&e)

初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L長(zhǎng)度減1。

2． 程序包含四個(gè)模塊：

1）主程序模塊：

void main()

{

初始化；

for（;;）

{}

while（命令=開始）

{

接受命令；

處理命令；

}

for（;;）

{ }

}

2）有序表單元模塊——實(shí)現(xiàn)有序表的抽象數(shù)據(jù)類型；

3）節(jié)點(diǎn)結(jié)構(gòu)單元模塊——定義有序表的節(jié)點(diǎn)結(jié)構(gòu)；

4）數(shù)據(jù)輸入分析模塊——判斷輸入數(shù)據(jù)正確有效；

各模塊之間的調(diào)用關(guān)系如下：

主程序模塊

↓

有序表結(jié)構(gòu)模塊

↓

節(jié)點(diǎn)結(jié)構(gòu)單元模塊

↓

數(shù)據(jù)輸入分析模塊

三、詳細(xì)設(shè)計(jì)

1、結(jié)點(diǎn)類型，指針類型

TypedefstructLNode{

int code,date;//code 為人所在位置 date為人持有的密碼 struct LNode *next;

};// 結(jié)點(diǎn)類型，指針類型

2、構(gòu)造單向循環(huán)鏈表

struct LNode *p,*head,*q;//定義頭節(jié)點(diǎn)，和指針

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

{

struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配

新結(jié)點(diǎn)空間

s->code=i;

input(s->date);

p->next=s;

p=p->next;

}

p->next=head;//根據(jù)輸入的人數(shù)，進(jìn)行單項(xiàng)循環(huán)鏈表的創(chuàng)建，p指向最后一個(gè)結(jié)點(diǎn)，并與頭節(jié)點(diǎn)鏈接，形成單項(xiàng)循環(huán)鏈表

3、約瑟夫環(huán)的程序?qū)崿F(xiàn)部分

while(n!=1)//判斷輸入人數(shù)，如為1則直接輸出結(jié)果，不循環(huán)

{

for(i=1，m=m%n;i

{

p=p->next;

}

q=p->next;//找到要?jiǎng)h除節(jié)點(diǎn)

p->next=q->next;//找到要?jiǎng)h除節(jié)點(diǎn)的后繼，并連接新環(huán)m=q->date;//找到下一個(gè)密碼

printf(“%d”,q->code);

free(q);//釋放已刪除節(jié)點(diǎn)空間

n--;//鏈表長(zhǎng)度減一

}

printf(“%d”,p->code);//約瑟夫環(huán)的結(jié)果輸出

4、其他函數(shù)代碼

數(shù)值的輸入限制

int input()

{

int y,k,z=0;

char c;//元素類型

char a[4];//數(shù)組初始化

if(!z)//輸入判斷，確定位數(shù)字或控制字符且位置和密碼不為零 {

for(y=0;y<4;y++)

{

c=getch();

if(c>=48&&c<=57)//確定為輸入數(shù)字

{a[y]=c;

putch(c);

}

else

{

y--;

if(c=='r')//確定輸入為控制字符 即回車或者刪除

break;

else

if(c==8)

{a[y]='n';

y--;}

continue;

}

}

k=atoi(a);//確定最終輸入數(shù)字的值

printf(“n”);

z=k;

if(z==0)

printf(“ERROR!The number couldn't be 0!n”);// 輸入為零，重新輸入 }

return(k);//數(shù)值的返回

5、函數(shù)的調(diào)用關(guān)系圖反映程序?qū)哟谓Y(jié)構(gòu)

Main→input

四、調(diào)試分析

1、早期程序只寫了約瑟夫環(huán)的實(shí)現(xiàn)部分，沒有對(duì)輸入數(shù)據(jù)進(jìn)行篩選，調(diào)試的時(shí)候會(huì)經(jīng)常出錯(cuò)。比如是輸入字母，或者輸入0，大于32767溢出；

2、早期的循環(huán)過(guò)程中沒有進(jìn)行優(yōu)化，導(dǎo)致循環(huán)次數(shù)過(guò)多，浪費(fèi)時(shí)間；

3、為了輸出時(shí)美觀，分別在input和main函數(shù)主體內(nèi)做了兩次，輸入非零的判斷，浪費(fèi)了資源；

4、算法的時(shí)空分析

為了限制在輸入過(guò)程中不會(huì)上溢，只在輸入中限定為四個(gè)不全為零的數(shù)字，但是做的是do……while循環(huán)，復(fù)雜度為o（1）;

當(dāng)n大于1時(shí)：

在數(shù)據(jù)輸入中，鏈表的創(chuàng)建是for循環(huán)，時(shí)間復(fù)雜度為o（n-1）

在約瑟夫環(huán)實(shí)現(xiàn)程序中，為for循環(huán)。時(shí)間復(fù)雜度為o（m%n-1）

當(dāng)n=1時(shí)，復(fù)雜度為o（1）。

五、用戶手冊(cè)

用戶根據(jù)提示，先輸入起始密碼m，然后輸入人數(shù)n，再根據(jù)人數(shù)，分別輸入每個(gè)人的密碼date，數(shù)值均不能為0，否則會(huì)提示重新輸入，輸入為字母則自動(dòng)丟棄，輸入錯(cuò)誤可用刪除鍵進(jìn)行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數(shù)字大于9999，則第五位自動(dòng)轉(zhuǎn)換為下一個(gè)數(shù)字的起始位，依此類推）。

當(dāng)n個(gè)數(shù)字全部輸入完畢，則自動(dòng)顯示結(jié)果，按任意鍵則退出本程序。

六、測(cè)試結(jié)果

第一組：m 的初值為20；n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4，出列順序?yàn)?，1，4，7，2，1，3，5。

第二組： m 的初值為30；n=8，7個(gè)人的密碼依次為：5，1，6，9，4，7，2，3，出列順序?yàn)?，5，2，3，7，1，4，8。

第三組 : m 的初值為15；n=6，7個(gè)人的密碼依次為：5，3，4，7，6，9，出列順序?yàn)?，1，2，6，4，5。

七、附錄

源程序頭文件名清單：

#include “malloc.h”//內(nèi)存空間分配頭文件

#include “stdio.h”//輸入輸出函數(shù)頭文件

#include “stdlib.h”//input函數(shù)中字符串轉(zhuǎn)短整形函數(shù)的頭文件 #include “conio.h”//最后顯示結(jié)果、清屏函數(shù)頭文件