《計算機導(dǎo)論》課件-計算機導(dǎo)論第四章

第四章數(shù)據(jù)結(jié)構(gòu)和算法4.1數(shù)據(jù)結(jié)構(gòu)4.2算

法

4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)4.1.3圖狀結(jié)構(gòu)

4.1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)的一個分支。它主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)，物理結(jié)構(gòu)以及數(shù)據(jù)結(jié)構(gòu)上的基本數(shù)據(jù)運算：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)在計算機的存儲方式無關(guān)，數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)，其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)又統(tǒng)稱為非線性結(jié)構(gòu)。下面分別介紹這三種數(shù)據(jù)結(jié)構(gòu)：線性結(jié)構(gòu)

數(shù)據(jù)元素之間存在前后依次相鄰的邏輯關(guān)系，除第一個元素和最后一個元素外，其余元素都有唯一一個直接前驅(qū)和直接后繼。即元素之間是一對一的關(guān)系。如圖4.1所示，線性結(jié)構(gòu)包括線性表、棧、隊列、數(shù)組以及串等。

4.1數(shù)據(jù)結(jié)構(gòu)樹形結(jié)構(gòu)

數(shù)據(jù)元素之間存在的順序關(guān)系，除了第一個根結(jié)點外，其余結(jié)點都有唯一的一個直接前驅(qū)，但可以有零個或多個后繼結(jié)點。即元素之間是一對多的關(guān)系。如圖4.2所示，樹形結(jié)構(gòu)包括二叉樹、森林等。

4.1數(shù)據(jù)結(jié)構(gòu)圖形結(jié)構(gòu)

也叫網(wǎng)狀結(jié)構(gòu)，其每個結(jié)點都可以有多個前驅(qū)和多個后繼結(jié)點。數(shù)據(jù)元素之間是多對多的關(guān)系，如圖4.3所示

4.1數(shù)據(jù)結(jié)構(gòu)（2）數(shù)據(jù)的物理結(jié)構(gòu)。

數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機中是如何存儲的，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲上的實現(xiàn)。它有多種不同的方式，其中順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)是最常用的兩種存儲方式。順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上也相鄰的一系列存儲單元里，一般用數(shù)組來實現(xiàn)。其主要特點是：元素之間的邏輯關(guān)系由物理相鄰關(guān)系體現(xiàn)，且每個結(jié)點僅存儲元素的數(shù)據(jù)信息，因此存儲密度大，空間利用率高。但是在進(jìn)行插入和刪除運算時會造成相應(yīng)元素的大量移動，因此效率比較低。鏈?zhǔn)酱鎯Y(jié)構(gòu)

鏈?zhǔn)酱鎯催壿嬌舷噜彽臄?shù)據(jù)元素可以存放在物理上不一定相鄰的存儲單元中。鏈?zhǔn)酱鎯Y(jié)構(gòu)常用鏈表表示，鏈表中的結(jié)點除了包括數(shù)據(jù)域，還要包括相應(yīng)的指針域，以存放該數(shù)據(jù)元素邏輯上相關(guān)的數(shù)據(jù)元素的地址。其主要特點是：由于結(jié)點除存儲數(shù)據(jù)元素本身之外（數(shù)據(jù)域），還要存儲邏輯上相關(guān)的相鄰元素的地址（指針域），因此與順序存儲結(jié)構(gòu)相比，存儲密度小、空間利用率低，會占用更大的存儲空間。但與順序存儲結(jié)構(gòu)相比，這樣的做的優(yōu)點是：在進(jìn)行插入和刪除操作時僅需要修改相應(yīng)指針域的值即可，不會造成其他元素的大量移動，因此使用靈活方便。線性表、樹、圖等多種邏輯結(jié)構(gòu)均可以采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

4.1數(shù)據(jù)結(jié)構(gòu)（3）數(shù)據(jù)的運算（操作）

每一種類型的數(shù)據(jù)結(jié)構(gòu)都有相應(yīng)的基本運算或操作，主要包括插入、刪除、修改、查找、排序等。數(shù)據(jù)結(jié)構(gòu)與其上定義的基本操作封裝在一起構(gòu)成了抽象數(shù)據(jù)類型（Abstractdatatype,

ADT）。在程序設(shè)計中，有很多支持抽象數(shù)據(jù)類型的語言，如C++、JAVA等程序設(shè)計語言用“類”來支持抽象數(shù)據(jù)類型的表示。

4.1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容可以用圖4.4來表示：4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

1.線性表（1）線性表的定義。

線性表是由n(n≥0)個性質(zhì)相同的數(shù)據(jù)元素(結(jié)點)a1,a2,…,an所組成的有限序列，是一種結(jié)構(gòu)最

簡單使用最多的數(shù)據(jù)結(jié)構(gòu)。每一個線性表的數(shù)據(jù)元素根據(jù)不同的情況可以有不同的類型。例如，表4-1所示的學(xué)生成績表也是一個線性表，這里的數(shù)據(jù)元素是一條條的學(xué)生記錄，每一條記錄為一個數(shù)據(jù)元素，數(shù)據(jù)元素由學(xué)號、姓名、性別、班級名稱和成績等多個數(shù)據(jù)項組成，這里的數(shù)據(jù)元素類型可以定義為結(jié)構(gòu)體。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

（2）線性表的存儲結(jié)構(gòu)。線性表的存儲結(jié)構(gòu)可以采用順序存儲或鏈?zhǔn)酱鎯Γ?/p>

順序存儲結(jié)構(gòu)的線性表，也叫順序表。順序表通常用數(shù)組來實現(xiàn)，用一組地址連續(xù)的存儲單元來依次存放線性表中的每一個元素。數(shù)據(jù)元素之間物理上的先后關(guān)系和邏輯上的先后關(guān)系保持一致。由數(shù)組的特征可以得出，第i個數(shù)據(jù)元素的存儲地址可由以下公式求得：Loc（ai）=Loc(a1)+(i-1)*L公式中，Loc(a1)是第一個數(shù)據(jù)元素的存儲地址，L為每個元素所占存儲單元的大小。由以上公式可以得出，任意數(shù)據(jù)元素的存儲地址均可以直接計算出來，所以對任意數(shù)據(jù)元素的訪問都可以采用直接訪問的方式，因此速度快、效率高，這是它的優(yōu)點。如圖4.5所示，采用順序存儲結(jié)構(gòu)實現(xiàn)對線性表，如果要訪問第i個元素，計算表的長度等操作比較簡單，但在實現(xiàn)插入或刪除元素操作時，會造成其他大量相關(guān)元素的移動從而需要花費較多的時間，因此效率比較低。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表，也叫鏈表。鏈表中的每一個結(jié)點在內(nèi)存中的存儲單元不一定連續(xù)。為了表示數(shù)據(jù)元素之間的邏輯關(guān)系，每個存儲單元除了存放數(shù)據(jù)元素本身之外，還需要存儲邏輯上相關(guān)的下一個元素的存儲地址，所以每一個數(shù)據(jù)元素對應(yīng)一個物理存儲單元，包含數(shù)據(jù)域和指針域兩部分，如圖4.6所示。整個線性表的各個數(shù)據(jù)元素的存儲區(qū)域之間，通過指針連接成為一個鏈?zhǔn)降慕Y(jié)構(gòu)，稱為鏈表，如圖4.7所示鏈?zhǔn)酱鎯Φ膬?yōu)勢是可以利用零散的存儲單元存放數(shù)據(jù)元素，而且在實現(xiàn)插入和刪除操作時，只需要修改局部指針，不會引起其他元素的移動，因此效率較高。但是，鏈表中的每一個結(jié)點除了存儲數(shù)據(jù)元素本身之外還額外增加一個指針域，這將增加存儲空間的開銷，存儲密度小。而且訪問鏈表的數(shù)據(jù)元素，只能沿著頭指針“順藤摸瓜”順序訪問，效率也大大降低。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

（3）線性表的運算

插入。在線性表L中插入一個數(shù)據(jù)元素ListInsert(L,i,e)，該運算的功能是將數(shù)據(jù)元素為e的元素插入到線性表L的第i個位置上。插入成功后，線性表L的元素個數(shù)增加1，即長度增加1。例如，在線性表L=（25,12,47,89,36,14）的第四個位置插入一個值為99的元素，插入成功后線性表成為L=（25,12,47,99,89,36,14），長度由6增加為7，如圖4.8所示。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

刪除。刪除線性表L中第i個數(shù)據(jù)元素ListDelete(L,i)。該運算的功能是將刪除線性表L的第i個數(shù)據(jù)元素。刪除成功后，線性表L的數(shù)據(jù)元素個數(shù)減1，即長度減1。

檢索。獲取線性表L中的某個數(shù)據(jù)元素內(nèi)容GetElem(L,i,e)。該運算的功能是獲取線性表L中第i個位置上的數(shù)據(jù)元素的值，并由參數(shù)e帶回。

查找。查找值為e的數(shù)據(jù)元素LocateELem(L,e)，該運算用來在線性表L中查找指定的數(shù)據(jù)元素e。如果查找成功，則返回該元素線在性表中的位置，否則返回0。

求線性表的長度。求線性表L的長度ListLength(L)，該運算用來求線性表L的長度，即線性表L中數(shù)據(jù)元素的個數(shù)。

判斷線性表是否為空。判斷線性表L是否為空IsEmpty(L)，若為空則返回1，否則返回0。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

2．棧（1）棧的定義。

棧是一種操作受限的特殊線性表，它只能在表的一端（棧頂）進(jìn)行插入和刪除運算。與線性表相同，數(shù)據(jù)元素之間仍為一對一關(guān)系。設(shè)棧S=（a1,a2,...,an），按照a1,a2,...,an順序依次先后進(jìn)棧，則稱a1是棧底元素，an是棧頂元素。進(jìn)棧和出棧只能在棧頂操作，且遵循后進(jìn)先出（LastInFirstOut，LIFO）或先進(jìn)后出（FirstInLastOut，F(xiàn)ILO）的原則，如圖4.9所示。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

（2）棧的存儲結(jié)構(gòu)。用順序存儲（順序棧）和鏈?zhǔn)酱鎯Γㄦ湕＃┚?，但以順序棧更常見，即用一個連續(xù)的存儲區(qū)域來存放棧元素，并設(shè)置一個指針top指向棧頂元素或棧頂元素下一個位置。圖4.10分別表示了棧的初始狀態(tài)（空棧），以及棧元素A、B、C依次進(jìn)站的過程。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

（3）棧的運算。設(shè)S為一個棧，則對?？梢赃M(jìn)行以下一些基本運算：初始化空棧InitStack(S)。該運算將棧S初始化為空棧。進(jìn)棧Push(S,x)。該運算將新的數(shù)據(jù)元素x壓入棧S（圖4.11）中，作為棧S的棧頂元素。例如，在棧S頂部壓入素x，壓入成功后棧的長度由3增加為4（圖4.12）。過程如下：1)判斷是否棧滿，若滿則出錯2)元素X壓入棧頂。3)棧頂指針加1。出棧Pop(S)。該運算刪除棧S的棧頂元素，且棧S的元素少1。取棧頂元素GetTop（S）。該運算取得棧S的棧頂元素作為其函數(shù)值。4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

3.隊列（1）隊列的定義。隊列（Queue）是一種先進(jìn)先出(FIFO)的線性表，只允許在表的一端進(jìn)行插入，而在另一端刪除元素。允許入隊操作的一端稱作隊尾，允許刪除操作的一端稱作隊頭。設(shè)隊列Q=（a1,a2,...,an），按照a1,a2,...,an順序依次入隊，則稱a1是隊頭元素，an是隊尾元素，入隊和出隊操作遵循后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則，如圖4.13所示。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

（2）隊列的存儲結(jié)構(gòu)。與棧一樣，隊列也有順序存儲（順序隊列）和鏈?zhǔn)酱鎯Γㄦ滉犃校﹥煞N。如果隊列需要頻繁地做插入和刪除操作，那么隊列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)較為適宜，它需要設(shè)置兩個指針，一個為隊頭指針，另一個為隊尾指針，分別指向隊列的隊頭和隊尾。鏈隊列的結(jié)構(gòu)如圖4.14所示。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.1線性結(jié)構(gòu)

（3）隊列的運算。設(shè)Q為一個隊列，則對Q可以進(jìn)行以下一些基本運算：構(gòu)造空隊列InitQueue(Q)。該運算將隊列Q初始化為空隊列，具體過程是：首先申請一個結(jié)點，為該結(jié)點的指針域賦空值，并讓隊頭指針front和隊尾指針rear同時指向該結(jié)點。如圖4.15所示。取隊列長度QueueLength(Q)。該運算求隊列Q的長度，即隊列Q中數(shù)據(jù)元素的個數(shù)。取隊頭元素GetHead(Q)。該運算取得隊列Q的隊頭元素作為其函數(shù)值。入隊列EnQueue(Q,e)。該運算將新的數(shù)據(jù)元素值為e進(jìn)入隊列Q中，作為隊尾元素。出隊列DeQueue(Q)。該運算刪除隊列Q的隊頭元素。4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

1.樹樹（tree）是n(n≥0)個結(jié)點的有限集合。當(dāng)n=0時，則稱為空樹。在一棵非空樹中：（1）有且僅有一個特定的結(jié)點，稱為樹的根結(jié)點。（2）當(dāng)n>1時，除根節(jié)點之外的其余結(jié)點被分成m（m

1）個互不相交的集合T1,T2,...，Tm，其中每一個集合Ti（1≤i≤m）本身又是一棵樹，稱為根結(jié)點的子樹。

在樹中，一個結(jié)點可以看作是一個數(shù)據(jù)元素。圖4.16是一個具有12個結(jié)點的樹，根節(jié)點為A。

如果一棵樹中結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置，則構(gòu)成

了不同的樹，稱這棵樹為有序樹。反之稱之為無序樹。零棵或有限棵不相交的樹的集合稱為森林（forest）。任何一棵樹，刪除根結(jié)點就變成了森林。由圖4.16的樹刪除掉根結(jié)點后形成的森林如圖4.17所示。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

1.樹結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度，度為0的結(jié)點稱為葉子結(jié)點，度不為0的結(jié)點稱為分支節(jié)點。一棵樹的結(jié)點除葉子節(jié)點之外，其余的都是分支節(jié)點。樹中一個結(jié)點的子數(shù)的根結(jié)點稱為該結(jié)點的孩子，這個結(jié)點稱為它的子結(jié)點的父結(jié)點，具有同一個父結(jié)點的孩子互稱為兄弟結(jié)點。如果一棵樹的一串結(jié)點n1，n2，...，nk有關(guān)系：結(jié)點ni是ni+1的父結(jié)點（1≤i≤k），就把n1，n2，...，nk稱為一條由n1到nk的路徑。這條路徑的長度是K-1。在樹中如果有一條路徑，從結(jié)點M到結(jié)點N，那么M就稱為N的祖先，而N成為M的子孫。

規(guī)定樹的根節(jié)點的層次為1，其余結(jié)點的層次等于它的父結(jié)點的層數(shù)加1。樹中所有節(jié)點的最大層數(shù)稱為樹的深度，樹中各節(jié)點度的最大值稱為該樹的度。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

2.二叉樹（1）二叉樹的概念二叉樹（binarytree）是有限個結(jié)點的集合，該集合或為空或有一個稱為根的節(jié)點及兩個互不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時，稱該二叉樹為空二叉樹。二叉樹是有序的，即使樹中結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。因此二叉樹具有5種基本形態(tài)：空二叉樹、只有根節(jié)點的二叉樹，只有根節(jié)點及左子樹的二叉樹，如圖4.18所示。在二叉樹中，左子樹的根稱為左孩子，右子樹的根稱為右孩子。如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

2.二叉樹一顆深度為K的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下從、左至到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點，在二叉樹中的位置相同，則稱這樣二叉樹為完全二叉樹。完全二叉樹的特點：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子節(jié)點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。圖4.19是一棵滿二叉樹，當(dāng)然也是完全二叉樹。圖4.20是完全二叉樹，但不是滿二叉樹。4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

2.二叉樹（2）二叉樹的主要性質(zhì)性質(zhì)1：一棵非空二叉樹的第i層上最多只有2i-1個節(jié)點(i≥1)。性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點。性質(zhì)3：對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)n0必定為n2＋1（即n0=n2+1）性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度必為?log2n?＋1。性質(zhì)5：對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為?i/2?。4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

2.二叉樹二叉樹的存儲二叉樹的存儲結(jié)構(gòu)也有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種：順序存儲結(jié)構(gòu)二叉樹的順序存儲，是用一組連續(xù)的存儲單元（數(shù)組）存放二叉樹中的結(jié)點。一般是按照二叉樹結(jié)點從上至下、從左到右的順序存儲。但這樣的話，結(jié)點在存儲位置上的前驅(qū)后繼關(guān)系并不一定是它們在邏輯上的鄰接關(guān)系（如父子關(guān)系）。依據(jù)二叉樹的性質(zhì)，只有完全二叉樹和滿二叉樹才能很好體現(xiàn)出它們的邏輯關(guān)系，樹中結(jié)點的序號可以唯一的反映出結(jié)點之間的邏輯關(guān)系，圖4.20所示的完全二叉樹的順序存儲如圖4.21所示。而對于普通的二叉樹，尤其是單支鏈的二叉樹，會造成很多存儲空間的浪費，如圖4.22所示。依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點的序號可以唯一的反映出結(jié)點之間的邏輯關(guān)系，這樣能夠最大可能的節(jié)省存儲空間，又可以利用列表元素的索引值，確定結(jié)點在二叉樹中的位置以及結(jié)點之間的關(guān)系。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.2樹形結(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用鏈表來表示一棵二叉樹。鏈表中每個節(jié)點都有三個域組成，除了數(shù)據(jù)之外，還有兩個指針域，分別用來存儲該結(jié)點的左孩子和右孩子結(jié)點所在的單元存儲地址。結(jié)點的存儲結(jié)構(gòu)為圖4.23所示：其中數(shù)據(jù)域存放結(jié)點（數(shù)據(jù)元素）的數(shù)據(jù)信息，若該結(jié)點的左孩子與右孩子不存在時，相應(yīng)的地址即指針域的值為空（用符號^或者NULL表示）。圖4.24給出了的二叉樹的鏈?zhǔn)酱鎯Α?.1數(shù)據(jù)結(jié)構(gòu)4.1.3圖狀結(jié)構(gòu)

1.圖的定義和術(shù)語

圖（graph）是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，數(shù)據(jù)元素間具有很明顯的層次關(guān)系，每一層上的數(shù)據(jù)元素只能和上一層中的至多一個數(shù)據(jù)元素相關(guān)，但可能和下一層的多個數(shù)據(jù)元素有關(guān)。在圖狀結(jié)構(gòu)中，任意兩個數(shù)據(jù)元素之間都有可能有關(guān)，即數(shù)據(jù)元素之間的鄰接關(guān)系可以是任意的。

4.1數(shù)據(jù)結(jié)構(gòu)4.1.3圖狀結(jié)構(gòu)

1.圖的定義和術(shù)語

4.1數(shù)據(jù)結(jié)構(gòu)4.1.3圖狀結(jié)構(gòu)

2.圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)有鄰接矩陣和鄰接表：鄰接矩陣鄰接矩陣存儲結(jié)構(gòu),就是用一維數(shù)組記錄圖中頂點的信息，用一個鄰接矩陣（二維數(shù)組）表示圖中各個頂點之間關(guān)系。設(shè)圖A=(V,E)有n個頂點，則圖中各頂點相鄰關(guān)系為一個n×n的矩陣。鄰接矩陣是一個二維數(shù)組A.Edge[n][n]，定義為：用矩陣表示圖中各頂點之間的鄰接關(guān)系，有邊相連對應(yīng)的矩陣元素值為1，否則為0：1，如果<i,j>∈E或者（i,j）∈EA.Edge[i][j]=0，否則圖4.25的鄰接矩陣表示如下圖所示：

4.1數(shù)據(jù)結(jié)構(gòu)4.1.3圖狀結(jié)構(gòu)

2.圖的存儲結(jié)構(gòu)鄰接表

鄰接表是圖的一種順序存儲與鏈?zhǔn)酱鎯Y(jié)合的存儲方法。對每個頂點vi

建立一個單鏈表，

把與vi有關(guān)聯(lián)的邊的信息鏈接起來，形成單鏈表，并將圖中所有頂點信息和鄰接表頭放在數(shù)組中，就構(gòu)成了鄰接表。鏈表中每個結(jié)點設(shè)為2個域，如圖4.28所示。圖4.29給出了無向圖4.25對應(yīng)的鄰接表表示4.2算

法4.2.1算法概述4.2.2搜索4.2.3排序4.2.4并行算法

4.2算

法4.2.1算法概述

1.算法發(fā)展歷史2.算法的概念和特征（1）算法的概念為了解決某個特定問題而采取的方法和步驟的一組有窮的指令集，稱為算法。算法是被精確定義的一組規(guī)則，這些規(guī)則規(guī)定了先做什么再做什么，以及判斷出現(xiàn)某種情況時做哪種操作，因此，算法是一個步進(jìn)式的完成任務(wù)的過程。（2）算法的描述根據(jù)不同的應(yīng)用場景和面向的任務(wù)不同，算法通過可以用自然語言、流程圖、偽代碼和程序設(shè)計語言來描述。（3）算法的特征輸入：一個算法應(yīng)該有0個或多個輸入。輸出：一個算法應(yīng)該有1個或多個輸出（即處理結(jié)果）。確定性：算法中的每一步定義都必須是確切的、無歧義的。有窮性：一個算法應(yīng)在執(zhí)行有窮步后可以結(jié)束。有效性：算法中描述的每一步操作都應(yīng)該能有效地執(zhí)行，并最終得到確定的結(jié)果。

4.2算

法4.2.1算法概述

2.算法的概念和特征（4）算法的評價

一般可以從正確性、時間復(fù)雜度和空間復(fù)雜度3個方面對算法進(jìn)行評價。

正確性

算法的正確性是指算法能夠正確的完成所要解決的問題。

時間復(fù)雜度時間復(fù)雜度指依據(jù)算法編寫出程序后在計算機上運行時所耗費的時間度量。一個程序在計算機上運行的時間取決于程序運行時輸入的數(shù)據(jù)、對源程序編譯所需要的時間、執(zhí)行每條語句所需要的時間及語句重復(fù)執(zhí)行的次數(shù)等。其中，最重要的是語句重復(fù)執(zhí)行的次數(shù)。通常，把算法中關(guān)鍵操作（循環(huán)和遞歸）重復(fù)執(zhí)行次數(shù)之和作為該程序的時間復(fù)雜度，用T(n)表示，其中的n為問題規(guī)模。對于一個從線性表中查詢某個數(shù)據(jù)的算法，設(shè)n為線性表的長度，即線性表中數(shù)據(jù)的個數(shù)。算法時間復(fù)雜度的漸進(jìn)表示法，記作：T(n)=O(f(n))漸進(jìn)符號（O）的定義：當(dāng)且僅當(dāng)存在一個正的常數(shù)C和n0，使得對所有的n

n0

，有T(n)

Cf(n)，則T(n)=O(f(n))。表示隨著n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率相同，稱漸近時間復(fù)雜度。4.2算

法4.2.1算法概述

2.算法的概念和特征

時間復(fù)雜度例如，分析下述count算法的時間復(fù)雜度。voidcount(){x=0;y=0;//T1(n)=O(1)for(intk=0;k<n;k++)x++;//T2(n)=O(n)for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;//T3(n)=O(n2)}算法的時間復(fù)雜度約等于該算法所有指令的執(zhí)行的時間復(fù)雜度的最大值，即T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)。4.2算

法4.2.1算法概述

2.算法的概念和特征

時間復(fù)雜度時間復(fù)雜度T(n)按數(shù)量級遞增順序為：時間復(fù)雜度自左向右由低向高遞增，當(dāng)n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上會非常懸殊。圖4.32是常數(shù)(1)、對數(shù)(logn)和線性(n)算法復(fù)雜度增長對比，圖4.33是多項式

(nc)、指數(shù)(cn)和階乘(n!)算法復(fù)雜度增長對比。4.2算

法4.2.1算法概述

2.算法的概念和特征

空間復(fù)雜度空間復(fù)雜度是指依據(jù)算法編寫出程序后在計算機上運行時所需內(nèi)存空間大小的度量，也就是和問題規(guī)模n有關(guān)的度量。記作:S(n)=O(f(n))其中n為問題的規(guī)模(或大小)。算法要占據(jù)的空間包括算法本身要占據(jù)的空間，輸入/輸出、指令、常數(shù)、變量以及算法要使用的輔助空間。例如，某個算法在執(zhí)行過程中所占的存儲空間為2n-1，則該算法的空間復(fù)雜度為O(2n)。若輸入數(shù)據(jù)所占空間和算法無關(guān)，則不考慮輸入本身所占空間，否則應(yīng)同時考慮。4.2算

法4.2.2搜索

搜索即查找，是一種在列表中確定目標(biāo)所在位置的算法。在列表中，搜索意味著給定一個值，并在包含該值的列表中找到第一個元素的位置。對于搜索中有兩種基本的方法：順序查找和折半查找。順序查找可以在任何列表中查找，沒有要求，而折半查找則要求列表是有序的。1．順序搜索（線性查找）順序搜索一般用來查找表內(nèi)元素之間無序的線性表，當(dāng)查詢的序列較大時，這種查找效率較低。順序查找的查找過程是：從列表起始處開始查找，當(dāng)找到關(guān)鍵字元素或確信查找關(guān)鍵字不在列表中時，查找過程結(jié)束。根據(jù)順序搜索的算法，可以看出，對于任一數(shù)列，順序搜索算法的時間復(fù)雜度為O(n)。4.2算

法4.2.2搜索

2.折半搜索如果查詢的列表是無序的，則順序查找是唯一的方法。但如果查詢的序列較大，為了提高效率，最好將列表先排序，然后使用效率較高的折半查找進(jìn)行查找。

折半搜索是通過查找列表的中間元素和待查找的關(guān)鍵字比較，以判別出目標(biāo)在列表的前半部分還是后半部分。根據(jù)折半搜索的算法，可以看出，對于有序的數(shù)列，折半搜索算法的時間復(fù)雜度為O(log2n)。4.2算

法4.2.3排序

4種最基本的排序算法：選擇排序、冒泡排序、插入排序和歸并排序。1．選擇排序基本思想：把待排序數(shù)字序