資料結構課程設計

滁州學院

課程設計報告

課程名稱：資料結構課程設計

設計題目：交通諮詢模擬

系別：計算機資訊與工程學院

專業：電腦科學與技術

組別第七組

起止日期: 2023年 5 月 20 日 ~ 年 6月10日

指導教師戴支祥

計算機與資訊工程學院二○一二年制

課程設計任務書

目錄引言3

1 廣度優先遍歷3

1.1 廣度優先遍歷的遞迴定義

1.2 廣度優先遍歷的過程

2 兩點間所有路徑演算法設計3

2.1~2.6 演算法分析

3 詳細設計6

3.1 部分**

4 除錯與操作說明11

4.1 使用說明

5 課程設計總結11

5.1總結

致謝11

[參考文獻11

課程設計的主要內容

【引言】本文首先介紹圖的廣度優先遍歷演算法，接著根據圖的廣度優先遍歷演算法求出連通圖中兩點間所有路徑，並給出**.

【關鍵詞】圖；廣度優先遍歷演算法

1 廣度優先遍歷（breadth_first search）

1.1 廣度優先遍歷的遞迴定義

設圖g的初態是所有頂點均未訪問過。在g中任選一頂點v為源點，則廣度優先遍歷可以定義為：首先訪問出發點v，接著依次訪問v的所有鄰接點w1，w2，…，wt，然後再依次訪問與wl，w2，…，wt鄰接的所有未曾訪問過的頂點。

依此類推，直至圖中所有和源點v有路徑相通的頂點都已訪問到為止。此時從v開始的搜尋過程結束。

若g是連通圖，則遍歷完成；否則，在圖c中另選乙個尚未訪問的頂點作為新源點繼續上述的搜尋過程，直至g中所有頂點均已被訪問為止。

廣度優先遍歷類似於樹的按層次遍歷。採用的搜尋方法的特點是盡可能先對橫向進行搜尋，故稱其為廣度優先搜尋(breadth-firstsearch)。相應的遍歷也就自然地稱為廣度優先遍歷。

1.2 廣度優先遍歷的過程

在廣度優先搜尋過程中，設x和y是兩個相繼要被訪問的未訪問過的頂點。它們的鄰接點分別記為x1，x2，…，xs和y1，y2，…，yt。

為確保先訪問的頂點其鄰接點亦先被訪問，在搜尋過程中使用fifo佇列來儲存已訪問過的頂點。當訪問x和y時，這兩個頂點相繼入隊。此後，當x和y相繼出隊時，我們分別從x和y出發搜尋其鄰接點x1，x2，…，xs和y1，y2，…，yt，對其中未訪者進行訪問並將其人隊。

這種方法是將每個已訪問的頂點人隊，故保證了每個頂點至多只有一次人隊。

2求兩點間所有路徑的演算法

假設簡單連通圖如圖一所示，那麼的他的儲存結構如圖2所示。假設我們要找出結點3到結點6的所有路徑，那麼我們就設節點3為起點，結點6為終點。我們需要的儲存結構有：

圖的鄰接表建立圖，乙個標記陣列visited，乙個儲存路徑的陣列a，乙個儲存權值的陣列b。

2.1. 首先建立含有8個結點的交通圖，初始a，b全部為-1，然後輸入3和6，傳遞到廣度優先遍歷的函式中；

2.2. 將3標記為已訪問狀態visited[3]=1，並用a[0]=3儲存下路徑，然後尋找結點3的第乙個鄰接點1，用b[0]儲存下從3到1的權值w；

2.3. 1未訪問且不為6，遞迴，將1標記為以訪問，然後尋找與1相鄰的第乙個鄰接點0，用a[1]=1儲存下路徑，並用b[1]儲存下從1到0的權值w；

2.4. 0未訪問且不為6，遞迴，將0標記為以訪問，然後尋找與1相鄰的第乙個鄰接點2，用a[2]=0儲存下路徑，並用b[2]儲存下從0到2的權值w；

2.3. 2未訪問且不為6，遞迴，將2標記為以訪問，然後尋找與2相鄰的第乙個鄰接點6，用a[3]=2儲存下路徑，並用b[3]儲存下從0到2的權值w；

2.4 6為終點，用b[4]記錄下從2到6的權值，然後用a[4]=6儲存下路徑。從i=0到i<= max_vertex_num 20 ，當且僅當a[i]>=0&&b[i]>0，輸出即為依次輸出b[i]中的所有已存頂點，用s=s+b[i]累加輸出總權值；

2.5 將6標為未訪問，將陣列a，b的最後一位a[4]b[4]置為-1，接著迴圈尋找2的另乙個鄰接點5，5未訪問且不為6，用b[4]儲存從2到5的權值，遞迴，將5標為已訪問，用a[4]=5儲存路徑，然後求的5的第乙個為訪問頂點6，用b[5]記錄從5到6的權值，6為終點，用a[5]=6儲存路徑，從i=0到i<= max_vertex_num 20 ，當且僅當a[i]>=0&&b[i]>0，輸出即為依次輸出b[i]中的所有已存頂點，用s=s+b[i]累加輸出總權值；

2.6 將陣列a，b的最後一位a[5]b[5]置為-1，結束2的迴圈，回到0，將陣列a，b的最後一位a[4]b[4]置為-1，結束0的迴圈，回到1，結束迴圈，將a[3]，b[3]置為-1，尋找3的另乙個鄰接點7，再從起開始遞迴尋找鄰接點，直到找出6後輸出。//（此演算法可以簡單的理解為，由3開始，將3先儲存到a，將先找到它的第乙個鄰接點1，儲存到a，接著遞迴找1的第乙個鄰接點0，直到找到6，將a儲存的序號返回到圖中，找到此點圖中的資訊，期間用b儲存路程，然後結束迴圈，將ab儲存的最後乙個置回初始值，返回上層接著找2的另乙個鄰接點。

如是迴圈知道找到所有的路徑。）

3 c++**

#include ""

#define infinity 10000// 用整型最大值代替∞

#define max_vertex_num 20 // 最大頂點個數

#define ok 1

#define error 0

#define false 0

#define true 1

#define maxqsize100

typedef int qelemtype;

typedef float vrtype;

typedef float infotype;

typedef char vertextype;

typedef char vextype;

鄰接表的定義*****====

typedef struct arcnode表結點

int adjvex該弧所指向的頂點的位置

struct arcnode *nextarc; // 指向下一條弧的指標

float info網的權值指標

} arcnode;

typedef struct頭結點

vertextype data[100頂點資訊

arcnode *firstarc第乙個表結點的位址

} vnode, adjlist[max_vertex_num];

typedef struct algraph;

int visited[max_vertex_num],c=0,a[20]=;

float b[20]=;

鄰接表的定義

資料結構課程設計

資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦