資料結構課程設計報告

設計題目： _圖的遍歷和生成樹求解實現 ___

學生姓名董軍

專業班級： ____11軟體技術一班

指導教師汪紅霞

完成時間： 2023年12月

資訊工程學院信管系

安徽新華學院課程設計成績評定表(專科)

在電腦科學中，資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件（資料元素）以及它們之間的關係和運算等的學科，而且確保經過這些運算後所得到的新結構仍然是原來的結構型別。　　「資料結構」作為一門獨立的課程在國外是從2023年才開始設立的。 2023年美國唐·歐·克努特教授開創了資料結構的最初體系，他所著的《計算機程式設計技巧》第一卷《基本演算法》是第一本較系統地闡述資料的邏輯結構和儲存結構及其操作的著作。

「資料結構」在電腦科學中是一門綜合性的專業基礎課。資料結構是介於數學、計算機硬體和計算機軟體三者之間的一門核心課程。資料結構這一門課的內容不僅是一般程式設計（特別是非數值性程式設計）的基礎，而且是設計和實現編譯程式、作業系統、資料庫系統及其他系統程式的重要基礎。

　　計算機是一門研究用計算機進行資訊表示和處理的科學。這裡面涉及到兩個問題：資訊的表示，資訊的處理。

　　而資訊的表示和組織又直接關係到處理資訊的程式的效率。隨著計算機的普及，資訊量的增加，資訊範圍的拓寬，使許多系統程式和應用程式的規模很大，結構又相當複雜。因此，為了編寫出乙個「好」的程式，必須分析待處理的物件的特徵及各物件之間存在的關係，這就是資料結構這門課所要研究的問題。

眾所周知，計算機的程式是對資訊進行加工處理。在大多數情況下，這些資訊並不是沒有組織，資訊（資料）之間往往具有重要的結構關係，這就是資料結構的內容。資料的結構，直接影響演算法的選擇和效率。

　　計算機解決乙個具體問題時，大致需要經過下列幾個步驟：首先要從具體問題中抽象出乙個適當的數學模型，然後設計乙個解此數學模型的演算法（algorithm），最後編出程式、進行測試、調整直至得到最終解答。尋求數學模型的實質是分析問題，從中提取操作的物件，並找出這些操作物件之間含有的關係，然後用數學的語言加以描述。

計算機演算法與資料的結構密切相關，演算法無不依附於具體的資料結構，資料結構直接關係到演算法的選擇和效率。運算是由計算機來完成，這就要設計相應的插入、刪除和修改的演算法。也就是說，資料結構還需要給出每種結構型別所定義的各種運算的演算法。

　　資料是對客觀事物的符號表示，在電腦科學中是指所有能輸入到計算機中並由電腦程式處理的符號的總稱。　　資料元素是資料的基本單位，在電腦程式中通常作為乙個整體考慮。乙個資料元素由若干個資料項組成。

資料項是資料的不可分割的最小單位。有兩類資料元素：一類是不可分割的原子型資料元素，如：

整數"5"，字元 "n" 等；另一類是由多個款項構成的資料元素，其中每個款項被稱為乙個資料項。例如描述乙個學生的資訊的資料元素可由下列6個資料項組成。其中的出生日期又可以由三個資料項：

"年"、"月"和"日"組成，則稱"出生日期"為組合項，而其它不可分割的資料項為原子項。　　關鍵字指的是能識別乙個或多個資料元素的資料項。若能起唯一識別作用，則稱之為 "主" 關鍵字，否則稱之為 "次" 關鍵字。

　　資料物件是性質相同的資料元素的集合，是資料的乙個子集。資料物件可以是有限的，也可以是無限的。　　資料處理是指對資料進行查詢、插入、刪除、合併、排序、統計以及簡單計算等的操作過程。

在早期，計算機主要用於科學和工程計算，進入八十年代以後，計算機主要用於資料處理。據有關統計資料表明，現在計算機用於資料處理的時間比例達到80%以上，隨著時間的推移和計算機應用的進一步普及，計算機用於資料處理的時間比例必將進一步增大。

在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。當我們使用計算機來解決乙個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題抽象出乙個適當的數學模型，然後設計或選擇乙個解此數學模型的演算法，最後編出程式進行除錯、測試，直至得到最終的解答。

例如，求解梁架結構中應力的數學模型的線性方程組，可以使用迭代演算法來求解。

由於當時所涉及的運算物件是簡單的整型、實型或布林型別資料，所以程式設計者的主要精力是集中於程式設計的技巧上，而無須重視資料結構。隨著計算機應用領域的擴大和軟、硬體的發展，非數值計算問題越來越顯得重要。據統計，當今處理非數值計算性問題占用了85%以上的機器時間。

這類問題涉及到的資料結構更為複雜，資料元素之間的相互關係一般無法用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的資料結構，才能有效地解決問題。

軟體設計課程設計是學習完《資料結構》課程後進行的一次全面的綜合性實踐過程，其目的在於為學生提供了乙個既動手又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結合起來，鍛鍊學生分析解決實際問題的能力。提高學生實踐程式設計的能力。這次的課程設計，我主要是設計圖的遍歷以及生成樹的求解，包含儲存、遍歷、最小生成樹的求解。

而圖的遍歷和生成樹的求解這個程式是乙個簡單的圖的基本操作實現系統。這個程式不僅要包含建立圖中包含的頂點數、邊數，還應具有圖的兩種遍歷、最小生成樹的求解等功能。

乙個圖必有頂點和邊，在此基礎上實現圖的儲存，進而實現圖的遍歷和最小生成樹的求解。

具有以下幾種功能：

1、先任意建立乙個圖；

2、圖的dfs,bfs的遞迴和非遞迴演算法的實現

3、最小生成樹（兩個演算法）的實現，求連通分量的實現

4、要求用鄰接矩陣、鄰接表等多種結構儲存實現

程式設計一般由兩部分組成：演算法和資料結構，合理地選擇和實現乙個資料結構和處理這些資料結構具有同樣的重要性。圖是一種較線性表和樹更為複雜的資料結構。

**性表中，資料元素之間僅有線性關係，每個資料元素只有乙個直接前驅和乙個直接後繼；在樹形結構中，資料元素之間有著明顯的層次關係，並且每一層上的資料元素可能和下一層中多個元素（及其孩子結點）相關但只能和上一層中乙個元素（即雙親結點）相關；而在圖形結構中，節點之間的關係可以是任意的，圖中任意兩個資料元素之間都可能相關。

生成樹求解主要利用普利姆和克雷斯特演算法求解最小生成樹，只有強連通圖才有生成樹。

a.圖的鄰接矩陣儲存：根據所建無向圖的結點數n,建立n*n的矩陣，其中元素全是無窮大（int_max），再將邊的資訊存到陣列中。

其中無權圖的邊用1表示，無邊用0表示；有全圖的邊為權值表示，無邊用∞表示。

b.圖的鄰接表儲存：將資訊通過鄰接矩陣轉換到鄰接表中，即將鄰接矩陣的每一行都轉成鍊錶的形式將有邊的結點進行儲存。

c.圖的廣度優先遍歷：假設從圖中的某個頂點v出發，在訪問了v之後依次訪問v的各個未曾訪問過的鄰接點，然後再訪問此鄰接點的未被訪問的鄰接點，並使「先被訪問的頂點的鄰接點」先於「後被訪問的頂點的鄰接點」被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。

若此時圖中還有未被訪問的，則另選未被訪問的重複以上步驟，是乙個非遞迴過程。

d.圖的深度優先遍歷：假設從圖中某頂點v出發，依依次訪問v的鄰接頂點，然後再繼續訪問這個鄰接點的系乙個鄰接點，如此重複，直至所有的點都被訪問，這是個遞迴的過程。

e.圖的連通分量：這是對乙個非強連通圖的遍歷，從多個結點出發進行搜尋，而每一次從乙個新的起始點出發進行搜尋過程中得到的頂點訪問序列恰為其連通分量的頂點集。

本程式利用的圖的深度優先遍歷演算法

#include

#include <>

using namespace std;

#define int_max 10000//最大值

static int n=0;//全域性變數，判斷有權圖和無權圖

static int o=0;//全域性變數，清除錯誤

static int l=0;//全域性變數，清除錯誤

#define inf 9999//最小值的最大值

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

typedef int vrtype,qelemtype,status;

typedef char infotype,vertextype;

3.2.2 定義功能函式

adt queue

資料關係：r1=

基本操作：

initqueue(&q)

操作結果：構造乙個空佇列q。

queueempty(q)

初始條件：q為非空佇列。

操作結果：若q為空佇列，則返回真，否則為假。

enqueue(&q,e)

初始條件：q為非空佇列。

操作結果：插入元素e為q的新的隊尾元素。

dequeue(&q,e)

初始條件：q為非空佇列。

操作結果：刪除q的隊頭元素，並用e返回其值。

}adt queue

adt graph

vr=基本操作p：

creatgraph(&g,v,vr);

資料結構課程設計報告

資料結構課程設計報告

資料結構課程設計報告

《資料結構》課程設計報告

相關推薦