1、數據結構知識數據結構是計算機軟件的一門基礎課程 , 計算機科學各個領域及有關的應用軟件都要用到各種數據結構 語言編譯要使用棧、散列表及語法樹；操作系統中用隊列、存儲管理表及目錄樹等；數據庫系統運用線性表、多鏈表及索引樹等進行數據管理；而在人工智能領域，依求解問題性質的差異將涉及到各種不同的數據結構，如廣義表、集合、搜索樹及各種有向圖等等。學習數據結構目的是要熟悉一些最常用的數據結構，明確數據結構內在的邏輯關系，知道它們在計算機中的存儲表示，并結合各種典型應用說明它們在進行各種操作時的動態性質及實際的執行算法，進一步提高軟件計和編程水平。通過對不同存儲結構和相應算法的對比，增強我們根據求解問題的

2、性質選擇合理的數據結構，并將問題求解算法的空間、時間及復雜性控制在一定范圍的能力。軟件設計師考試大綱對數據結構部分的要求是熟練掌握常用數據結構和常用算法，因此，本專題從數據結構的概述出發，對基本的概念引出常用的數據結構類型的介紹和講解，同時在講解各種數據結構中間采用算法與數據結構相結合的方式，在算法步驟中使用數據結構，對數據結構的重點、難點進行了分析，最后講解了與數據結構緊密相關的排序和查找算法，以及一些以往考試題的分析。1. 數據結構概述數據結構 研究了計算機需要處理的數據對象和對象之間的關系；刻畫了應用中涉及到的數據的邏輯組織；也描述了數據在計算機中如何存儲、傳送、轉換。學習數據結構注意的

3、問題：系統掌握基本數據結構的特點及其不同實現。了解并掌握各種數據結構上主要操作的實現及其性能（時間、空間）的分析。掌握各種數據結構的使用特性，在算法設計中能夠進行選擇。掌握常用的遞歸、回溯、迭代、遞推等方法的設計掌握自頂向下、逐步求精的程序設計方法。掌握自頂向下、逐步求精的程序設計方法。在學習數據結構的知識之前，我們要了解一下數據結構中的基本概念。數據 ：對客觀事物的符號表示，在計算機中就是指所有能輸入到計算機中并被計算機程序所處理的符號的總稱。數據項：是數據的不可分割的最小單位；數據元素： 是數據的基本單位，在計算機程序中通常作為一個整體進行處理；一個數據元素可由若干個數據項組成。數據對象：

4、 是性質相同的數據元素的集合，是數據的一個子集。數據結構上的基本操作：插入操作刪除操作更新操作查找操作排序操作數據結構是指數據對象及相互關系和構造方法，一個數據結構 B 形式上可以用一個二元組表示為中， A 是數據結構中的數據（稱為結點）的非空有限集合， R是定義在 A 上的關系的非空有限集合。根據數據元素之間的關系的不同特性，通常有下列 4 類基本結構。B=（ A，R）。其集合結構中的數據元素除了“同屬于一個集合”的關系外，別無其他關系。線性結構結構中的數據元素之間存在一個對一個的關系。樹形結構結構中的元素之間存在一個對多個的關系。圖狀結構或網狀結構結構中的元素之間存在多個對多個的關系。數據

5、結構中，結點與結點間的相互關系是數據的邏輯結構。數據結構在計算機中的表示（又稱為映象）稱為數據的物理結構，也稱存儲結構。數據元素之間的關系在計算機中有兩種不同的表示方式：順序映象和非順序映象，并由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。任何一個算法的設計取決于選定的數據（邏輯）結構，而算法的實現依賴于采用的存儲結構。數據的邏輯結構分為兩類：線性結構：線性表、棧、隊列和串非線性結構：樹、圖數據的存儲方法有四類：順序存儲方法鏈接存儲方法索引存儲方法散列存儲方法2.常用數據結構2.1線性表在數據結構中，線性結構常稱為線性表，是最簡單、最常用的一種數據結構，它是由n 個相同數據類型的結點

6、組成的有限序列。其特點是：在數據元素的非空有限集合中，存在唯一的一個被稱做“第一個”的數據元素存在唯一的一個被稱做“最后一個”的元素數據元素除第一個之外，集合中的每個數據元素均只有一個前驅除最后一個之外，集合中每個數據元素均只有一個后繼一個由 n 個結點 e0，e1 ， en-1 組成的線性表記為： （e0，e1 ， en-1 ）。線性表的結點個數稱為線性表的長度，長度為0 的線性表稱為空的線性表，簡稱空表。對于非空線性表，e0 是線性表的第一個結點，en-1 是線性表的最后一個結點。線性表的結點構成了一個序列，對序列中兩個相鄰結點ei 和 ei-1 ，稱前者是后者的前驅結點，后者是前者的后繼

7、結點。線性表最重要的性質是線性表中結點和相對位置是確定的。線性表的結點也稱為表元，或稱為記錄，要求線性表的結點一定是同一類型的數據。線性表的結點可由若干個成分組成，其中唯一標識表元的成分成為關鍵字，簡稱鍵。線性表是一個相當靈活的數據結構，它的長度可以根據需要增長或縮短。對線性表的基本運算如下：LENGTH（ L）求長度函數GET（ L， i ）取元素函數PRIOR（L，elm）求前驅函數NEXT（L， elm） 求后繼函數LOCATE（ L，x ） 定位函數INSERT（ L，i ，b）插入操作DELETE（ L，i ）刪除操作有多種存儲方式能將線性表存儲在計算機內，其中最常用的是順序存儲和鏈

8、接存儲。根據存儲方式的不同，其上述的運算實現也不一樣。 順序存儲：是最簡單的存儲方式，其特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰。通常使用一個足夠大的數組，從數組的第一個元素開始，將線性表的結點依次存儲在數組中。順序存儲方式優點：能直接訪問線性表中的任意結點。線性表的第i 個元素 ai的存儲位置可以使用以下公式求得：LOC（ai ） =LOC（ a1）+（i-1 ）*l式中 LOC（ a1）是線性表的第一個數據元素a1 的存儲位置，通常稱做線性表的起始位置或基地址。順序存儲的缺點：1) 線性表的大小固定，浪費大量的存儲空間，不利于節點的增加和減少；執行線性表的插入和刪除操作要移動其他元

9、素，不夠方便；鏈式存儲線性表鏈接存儲是用鏈表來存儲線性表，。單鏈表（線性鏈表） ：從鏈表的第一個表元開始，將線性表的結點依次存儲在鏈表的各表元中。鏈表的每個表元除要存儲線性表結點的信息以外，還要有一個成分來存儲其后繼結點的指針。線性鏈表的特點是：每個鏈表都有一個頭指針，整個鏈表的存取必須從頭指針開始，頭指針指向第一個數據元素的位置，最后的節點指針為空。當鏈表為空時，頭指針為空值；鏈表非空時，頭指針指向第一個節點。鏈式存儲的缺點：1) 由于要存儲地址指針，所以浪費空間；直接訪問節點不方便；循環鏈表：循環鏈表是另一種形式的鏈式存儲結構 ，是單鏈表的變形 。它的特點就是表中最后一個結點的指針域指向頭

10、結點，整個鏈表形成一個環。因此，從表中任意一個結點出發都可以找到表中的其他結點。循環鏈表和單向鏈表基本一致，差別僅在于算法中循環的條件不是結點的指針是否為空，而是他們的指針是否等于頭指針，循環鏈表最后一個結點的link指針不為 0 (NULL)，而是指向了表的前端。為簡化操作，在循環鏈表中往往加入表頭結點。循環鏈表的特點是：只要知道表中某一結點的地址，就可搜尋到所有其他結點的地址。循環鏈表的示例：帶表頭結點的循環鏈表：雙向鏈表：雙向鏈表是另一種形式的鏈式結構，雙向鏈表的結點中有兩個指針域，其一指向直接后繼，另一指向直接前趨。雙向鏈表克服了單鏈表的單向性的缺點。前驅方向后繼方向雙向鏈表也可以有循

11、環表，鏈表中存在兩個環。一個結點的前趨的后繼和該結點的后繼的前趨都是指向該結點的。p = plLink rLink = p rLink lLink2.2棧棧（ Stack ）是限定僅在表尾進行插入或刪除操作的線性表。表尾端稱棧頂（ top ），表頭端稱棧底（ bottom ）。若有棧 S=（s 0，s1 ， ， s n-1 ）則 s0 為棧底結點， sn-1 為棧頂結點。通常稱棧的結點插入為進棧，棧的結點刪除為出棧。因為最后進棧的結點必定最先出棧，所以棧具有后進先出的特點。可以用一下一個圖形來形象的表示：棧有兩種存儲結構：順序棧和鏈棧順序棧即棧的順序存儲結構是 ，利用一組地址連續的存儲單元依次

12、存放自棧底到棧頂的數據元素 ，同時設指針 top 指示棧頂元素的當前位置。棧也可以用鏈表實現，鏈式存儲結構的棧簡稱鏈棧。若同時需兩個以上的棧，則最好采用這種結構。對于棧上的操作，總結如下，大家可以仔細看一下這些程序，一個大的程序都是由一些對數據結構的小的操作組成的。順序存儲的棧的基本操作如下：判斷棧滿：int stackfull(seqstack *s)return (s->top= =stacksize-1);進棧：voidpush(seqstack *s,datatypex)if (stackfull(s)error( “stack verflow”);s->data+s-&g

13、t;top=x;判斷棧空：int stackempty(seqstack *s)return (s->top= = -1)出棧：datatype pop(seqstack *s)if (stackempty(s)error( “stack underflow”);x=s->datatop;s->top-;return (x);鏈接存儲棧：用鏈表實現的棧，鏈表第一個元素是棧頂元素，鏈表的末尾是棧底節點，鏈表的頭指針就是棧頂指針，棧頂指針為空則是空棧。若同時需要兩個以上的棧，最好采用鏈表作存儲結構鏈接存儲的棧的操作如下：進棧：Void push(linkstack *p,data

14、type x)stacknode *q q=(stacknode*)malloc(sizeof(stacknode);q >data=x;q >next=p >top; p >top=q;出棧：Datatypepop(linkstack*p)datatypex;stacknode*q=p >top;if(stackempty(p)error(“stack underflow.”);x=q >data;p >top=q >next; free(q);return x;多棧處理棧浮動技術：n 個棧共享一個數組空間V mn 設立棧頂指針數組t+1和 棧

15、底指針數組b+1nn， t i 和 b i 分別指示第i個棧的棧頂與棧底， bn 作為控制量，指到數組最高下標各棧初始分配空間s= m/n 指針初始值t0=b0 = -1 =-1b nmt i = b i =b i -1 + s,i = 1, 2, n-12.3 隊列隊列是只允許在一端進行插入，另一端進行刪除運算的線性表。允許刪除的那一端稱為隊首（front ），允許插入運算的另一端稱為隊尾（rear ）。通常稱隊列的結點插入為進隊，隊列的結點刪除為出隊。若有隊列Q=（q0， q1 ， ， qn-1 ）則q0 為隊首結點， qn-1 為隊尾結點。因最先進入隊列的結點將最先出隊，所以隊列具有先進

16、先出的特性。可以用順序存儲線性表來表示隊列，也可以用鏈表實現，用鏈表實現的隊列稱為鏈隊列。隊列操作： int push(PNODE *top， int e)是進棧函數，形參top int pop(PNODE *top，int oe)是出棧函數，形參top int enQueue(PNODE *tail， int e)是入隊函數，形參 intdeQueue(PNODE*tail， int*e) 是出隊函數，形參是棧頂指針的指針，形參e 是入棧元素。是棧頂指針的指針，形參e 作為返回出棧元素使用。tail是隊尾指針的指針，形參e 是入隊元素。tail是隊尾指針的指針，形參e 作為返回出隊元素使用。

17、定義結點的結構如下：typedef struct nodeint value;struct node *next;NODE， *PNODE;函數 int push(PNODE *top，int e)PNODE p = (PNODE)malloc(sizeof(NODE);if(!p)return1;p->value = e;p->next = *top; /指向棧頂指針*top = p;return 0;函數int pop(PNODE *top， int *e)PNODE p = *top;if(p = NULL) return1;*e = p->value;*top = p

18、->next;/棧頂指向取出的數的指針free(p);return 0;函數int enQueue(PNODE *tail，int e)PNODE p， t ；t = *tail;p = (PNODE)malloc(sizeof(NODE)；if(!p) return l;p >value = e;p >next = t>next;t->next = p;/ 將元素加在尾指針后*tail = p;return 0;函數int deQueue(PNODE *tail，int e)PNODE p，q；if(*tail)->next = *tail) return

19、1;/ 隊列已經空p = (*tail)->next;/p 獲得尾指針q = p->next;e = q->value;p->next = q->next;if(*tail = q)*tail = p ;/ 尾指針指向最后節點free(q);return 0;)循環隊列 (Circular Queue):存儲隊列的數組被當作首尾相接的表處理。隊頭、隊尾指針加1 時從 maxSize -1 直接進到 0，可用語言的取模 ( 余數 ) 運算實現。隊頭指針進 1:front= (front+1)%;maxSize隊尾指針進 1:rear= ( rear + 1) %ma

20、xSize;隊列初始化： front =rear= 0;隊空條件： front= rear ;隊滿條件： ( rear+ 1) % maxSize = front循環隊列的進隊和出隊:優先級隊列：是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優先權的元素2.4串字符串是非數值處理應用中重要的處理對象。字符串是由某字符集上的字符所組成的任何有限字符序列。當一個字符串不包含任何字符時，稱它為空字符串。一個字符串所包含的有效字符個數稱為這個字符串的長度。一個字符串中任一連續的子序列稱為該字符串的子串。包含子串的字符串相應稱為主串。通常稱該字符在序列中的序號為該字符在串中的位置。字符串

21、的串值必須用單引號括1 c2c 3 c n 起來，但單引號本身不屬于串，它的作用是為了避免于變量名和數的, c常量混淆。在 C 語言中，字符串常量是用一對雙引號括住若干字符來表示，如“I am a student ”字符串通常存于字符數組中，每個字符串最后一個有效字符后跟一個字符串結束符“0”.系統提供的庫函數形成的字符串會自動加結束符號，而用戶的應用程序中形成的字符串必須由程序自行負責添加字符串結束符號。兩個串相等當且僅當兩個串的值相等，長度相等并且各個對應位置的字符都相等。常用的字符串的基本操作有7 種。ASSING（ s，t ）和 CREAT（s ， ss）賦值操作EQUAL（s ，t

22、）判等函數LENGTH（ s）求長度函數CONCAT（ s，t ）聯接函數SUBSTR（ s，start，len ）求子串函數INDEX（s ，t ）定位函數REPLACE（ s， t ，v ）置換函數INSERT（ s，pos， t ）插入函數DELETE（ s，pos， t ）刪除函數(1) 求字符串長 ,int strlen(char s)（ 2）串復制 (copy)char *strcpy(char to,char from);該函數將串 from 復制到串 to 中，并且返回一個指向串to 的開始處的指針。(3)聯接 (concatenation)charstrcat(char to

23、,char from)該函數將串 from 復制到串 to 的末尾，并且返回一個指向串to 的開始處的指針。(4)串比較（ compare)int strcmp(chars1,char s2);該函數比較串 s1 和串 s2 的大小，當返回值小于0，等于 0 或大于 0 時分別表示 s1<s2 或 s1=s2 或 s1>s2例如： result=strcmp( “ baker ”, ”Baker ” )result>0result=strcmp( “12”, ”12”);result=0result=strcmp( “Joe”, ”Joseph”);result<0（

24、5）字符定位 (index)char strchr(char s,char c);該函數是找c 在字符串中第一次出現的位置，若找到則返回該位置，否則返回NULL。字符串的靜態存儲：順序存儲，用一組地址連續的地址單元存儲串的字符序列，特別是在PASCAL程序語言中還可以采用緊縮數組來實現。字符串的動態存儲：采用鏈表的方式存儲字符串，節點的大小可以不同，即每個節點可以存放的字符數是不同的。對于節點大小大于1 的鏈表，需要設置頭指針和尾指針來定位和串連接。存儲密度： 串值所站的存儲位/ 實際分配的存儲位實際應用的串處理系統中采用的是動態存儲結構，每個串的值各自存儲在一組地址連續的存儲單元中，存儲地址

25、在程序執行過程中動態分配。利用串名和串值之間的的對應關系來建立存儲映象來訪問串。2.5數組數組是最常用的數據結構之一，在程序中，數組常用來實現順序存儲的線性表。數組由固定個數的元素組成，全部元素的類型相同，元素依次順序存儲。每個元素對應一個下標，數組元素按數組名和元素的下標引用，引用數組元素的下標個數稱為數組的維數。在 C 語言中， n 個元素的數組中，第一個元素的下標為 0，最后一個的下標為 n-1; 數組可以分為一維、二維 N 維數組，取決于引用數組元素的下標的個數；一維數組：二維數組和三維數組：數組可以分為靜態數組和動態數組兩類，所謂靜態就是指數組的空間存儲分配是在使用之前還是在程序運行

26、當中分配，靜態數組就是在定義時必須進行空間分配，也就是固定數組的大小，這樣就不利于數組的擴展。同樣動態數組就是在程序運行過程中進行數組的賦值或者是空間的分配，動態數組一般采用鏈表的存儲結構，而靜態數組一般采用順序存儲結構。數組元素可以是任何類型的，當元素本身又是數組時，就構成多維數組。多維數組是一維數組的推廣，多維數組中最常用的是二維數組。多維數組的所有元素并未排在一個線性序列里，要順序存儲多維數組按需要按一定次序把所有的數組元素排在一個線性序列里，常用的排列次序有行優先順序和列優先順序。對于多維數組， C 語言按行優先順序存放。對于數組，通常只有兩種操作：給定一個下標，存取相應的數據元素給定

27、一組下標，修改相應數據元素的某一個或幾個數據項的值。一般用多維數組表示矩陣，具體有以下幾種類型：對稱矩陣： Ai,j= =Aj,i三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣中，它的下三角（不包括主對角線）中的元素均為常數。下三角矩陣正好相反，它的主對角線上方均為常數，在大多數情況下，三角矩陣常數為零。三角矩陣可壓縮存儲到向量sa0.n(n+1)/2中， sak 和 aij的對應關系是：k =3、對角矩陣對角矩陣中 ，所有的非零元素集中在以主對角線為了中心的帶狀區域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。當 i-j>1 時，元

28、素ai,j=0。LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1) =LOC(0,0)+(2i+j)4.稀疏矩陣簡單說，設矩陣 A 中有 s 個非零元素，若 s 遠遠小于矩陣元素的總數（即 s m×n），并且分布沒有一定規律。用順序存儲結構的三元組對稀疏矩陣進行存儲，分別記錄行、列和值十字鏈表：由于非零元的位置和個數變化，所以用鏈表存儲更恰當；在這種情況下采用十字鏈表來表示，每個非零元用一個節點表示，節點中有行、列還有向下的域和線右的域；此外還需要一個指向列鏈表的表頭節點和指向行鏈表的表頭節點。還可以設置一個指向整個十字鏈表的表頭節點。還可以把列表頭和行表頭節點組成數組，

29、便于操作；各種廣義表示意圖2.6樹概述樹型結構是一類重要的非線性數據結構。其中以樹和二叉樹最為常用，直觀看來，樹是以分支關系定義的層次結構。樹是由一個或多個結點組成的有限集T，它滿足以下兩個條件：I. 有一個特定的結點，成為根結點II.其余的結點分成m（ m>=0）個互不相交的有限集T0，T1， ， Tm-1。其中每個集合又都是一棵樹，稱T0，T1， ， Tm-1為根結點的子樹。這里可以看出樹的定義是遞歸的，即一棵樹由子樹構成，子樹又由更小的子樹構成。一個結點的子樹數目，稱為結點的度。樹中各結點的度的最大值則稱為樹的度。樹中結點的最大層次稱為樹的深度。如果將樹中結點的各子樹看成從左到右是

30、有次序的 （即不能交換），則稱該樹為有序樹 ，否則為無序樹 。森林是 m（ m>=0）棵互不相交的樹的集合。存儲結構樹是非線性的結構，不能簡單地用結點的線性表來表示。樹有多種形式地存儲結構，最常用的是標準存儲形式和帶逆存儲形式。在樹的標準存儲結構中，樹中的結點可分成兩部分：結點的數據和指向子結點的指針。當程序需從結點返回到其父結點時，需要在樹的結點中存儲其父結點的位置信息，這種存儲形式就是帶逆存儲結構。具體使用的鏈表結構有：雙親表示法：利用每個節點只有一個雙親的特點；求節點的孩子時要遍歷整個向量孩子表示法：把每個節點的孩子都排列起來，一單鏈表存儲，則 n 個節點有 n 個孩子鏈表，而 n

31、 個頭指針又組成了一個線性表。孩子兄弟表示法 （又稱二叉樹表示法，或二叉鏈表表示法） ：節點兩個指針分別指向該節點的第一個孩子和下一個兄弟節點。樹的遍歷在應用樹結構時，常要求按某種次序獲得樹中全部結點的信息，這可通過樹的遍歷操作來實現。常用的樹的遍歷方法有：樹的前序遍歷：首先訪問根結點，然后從左到右遍歷根結點的各棵子樹。樹的后序遍歷：首先從左到右按后序遍歷根結點的各棵子樹，然后訪問根結點。樹的層次遍歷：首先訪問處于 0 層上的根結點，然后從左到右依次訪問處于 1 層、 2 層 上的結點，即自上而下從左到右逐層訪問樹各層上的結點。二叉樹概述與一般的樹的結構比較，二叉樹在結構上更規范和更有確定性，

32、應用也比樹更為廣泛。二叉樹的特點是每個結點至多只有二棵子樹 （即二叉樹中不存在度大于 2 的結點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹與樹不同的地方在于，首先二叉樹可以為空，空的二叉樹沒有結點；另外，在二叉樹中，結點的子樹是有序的，分左右兩棵子二叉樹。二叉樹采用類似樹的標準存儲形式來存儲。二叉樹的性質 :二叉樹具有下列重要特性。在二叉樹的第i 層至多有個結點（i>=1 ）。深度為 k 的二叉樹至多有-1 個結點（k>=1）。對任何一棵二叉樹T，如果其終端結點數為n0，度為2 的結點數為n2，則n0=n2+1。具有 n 個結點的完全二叉樹的深度為。二叉樹的遍歷樹

33、的所有遍歷方法都適用于二叉樹，常用的二叉樹遍歷方法有3 種。#include<stdio.h>#include<stdlib.h>#define NULL 0Typedef struct nodechar data;struct node *lchild,*rchild;TREENODE;TREENODE *root;前序遍歷 :訪問根結點，按前序遍歷根結點的左子樹，按前序遍歷根結點的右子樹。中序遍歷 :按中序遍歷根結點的左子樹，訪問根結點，按中序遍歷根結點的右子樹。中序遍歷算法 :Void inorder(TREENODE *p)if(p!=NULL) inorder

34、(p>lchild);printf(“%c”,p >data)inorder(p>rchild);后序遍歷 :按后序遍歷根結點的左子樹，按后序遍歷根結點的右子樹，訪問根結點。以上 3 種遍歷方法都是遞歸定義的。哈夫曼及其應用：又稱為最優樹，是一類帶權路徑長度最短的樹路徑長度：從樹中一個節點到另一個節點之間的分支構成的這兩個節點之間的路徑，路徑上的分支樹木就稱為路徑長度；樹的路徑長度：從樹根到每一節點的路徑長度之和；樹的帶權路徑長度：樹中所有葉子節點的帶權路徑長度之和；哈夫曼樹就是一棵n 個葉子節點的二叉樹，所有葉子節點的帶權之和最小。算法描述：給定 n 個節點的集合，每個節點

35、都帶權值；選兩個權值最小的節點構造一棵新的二叉樹，新二叉樹的根節點的權值就是兩個子節點權值之和；從 n 個節點中刪除剛才使用的兩個節點，同時將新產生的二叉樹根節點放在節點集合中。重復 2，3 步，知道只有一棵樹為止。例題：已知節點的前序序列和中序序列分別為：前序序列： ABCDEFG中序序列： CBEDAFG求出整個二叉樹，以及構造過程2.7 圖基本概念 :圖是一種較線性表和樹更為復雜的數據結構。在圖形結構中，結點之間的關系可以是任意的，圖中任意兩個數據元素之間都可能相關。一個圖 G 由非空有限的頂點集合V 和有限的邊的集合無向圖無向圖的邊是頂點的無序偶，用（i ，j ）來表示頂點有向圖有向圖

36、的邊是頂點的有序偶，有向圖的邊也成為弧，用E 組成，記為G=（V， E）。圖一般分為兩種類型。i 和 j 之間的邊。<i ， j> 來表示頂點i 和 j 之間的弧。其中，有條邊的無向圖稱為完全圖，而具有n(n-1) 條弧的有向圖成為有向完全圖。有時圖的邊或弧具有與它相關的樹，這種與圖的邊或弧相關的數稱作權。帶權圖也簡稱為網。如果同為無向圖或同為有向圖的兩個圖G1=（V1， E1）和 G2=（ V2 ， E2）滿足V2V1E 2E1則稱圖 G2 是圖 G1的子圖。頂點的度就是指和頂點相關聯的邊的數目。在有向圖中，以頂點v 為頭的弧的數據成為v 的入度；以v 為尾的弧成為v 的出度。這

37、里有一個重要的公式反映了頂點和邊的關系。其中， e 表示邊的數目，n 表示頂點個數， TD(Vi ) 表示頂點Vi 的度。在圖 G=（V，E）中，如果存在頂點序列（v0 ，v1， ， v k），其中 v0 =p，v k =q，且（ v 0 ，v 1），（ v1 ，v2 ） ，（ vk-1v k ）都在 E 中，則稱頂點p 到頂點 q 有一條路徑，并用（v 0 ， v1， ， v k）表示這條路徑，路徑的長度就是路徑上的邊，或弧的數目，這條路徑的長度為k。如果第一個頂點和最后一個頂點相同的路徑稱為回路或環。序列中頂點不重復出現的路徑稱為簡單路徑。對無向圖而言，如果從任意兩個不同頂點i 和 j 之

38、間都有路徑，則該無向圖是連通的。無向圖中的極大連通子圖為該圖的連通分量。對有向圖而言，如果任意兩個不同頂點i 到 j 有路徑，同時j 到 i 也有路徑，則該有向圖是強連通的。同樣，無向圖中的極大連通強子圖為該圖的強連通分量。存儲結構 : 最常用的存儲結構是有兩種。鄰接矩陣 :這是反映頂點間鄰接關系的矩陣。定義如下：設 G=（ V，E）是具有 n（ n1）個頂點的圖 ，G的鄰接矩陣M是一個 n 行 n 列的矩陣，若（ i，j ）或 <i ，j> E，則 Mij=1；否則 Mij=0。鄰接表 : 這是圖的鏈式存儲結構。圖的每個頂點都建立了一個鏈表，且第 i 個鏈表中的結點代表與頂點i

39、相關聯的一條邊或由頂點i 出發的一條弧 。而這些鏈表的頭指針則構成一個順序線性表。另外，還有其他的一些存儲結構，如十字鏈表和鄰接多重表，分別用來存儲有向圖和無向圖。圖的遍歷 :圖的遍歷是指從圖中的某個頂點出發，沿著圖中的邊或弧訪問圖中的每個頂點，并且每個頂點只被訪問一次。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。通常有兩種方法，它們對無向圖和有向圖都適用。深度優先搜索 :類似于樹的先根遍歷。廣度優先搜索 :類似于樹的層次遍歷。這兩種算法的時間復雜度相同，不同之處僅僅在于對頂點訪問的順序不同。圖的有關算法涉及到圖的有關算法比較多，這里只簡單歸納介紹一下，具體算法希望大家

40、參考有關資料。求最小代價生成樹設 G=（V ，E）是一個連通的無向圖，若G1 是包含 G 中所有頂點的一個無回路的連通子圖，則稱G1 為 G 的一棵生成樹。其中代價最小（各條邊的權值之和最小）的生成樹就稱為最小代價生成樹（簡稱最小生成樹）。這里提供兩種算法來求解這一問題：普里姆（Prim）算法和克魯斯卡爾（Kruskal ）算法。分別適用于求邊稠密的網的2最小生成樹和邊稀疏的網的最小生成樹，其時間復雜度分別是O(n )和 O(eloge) （ e 為網中邊的數目） 。其中 prim 算法基本思想 ：任選一個頂點 v0 開始，連接與 v 0 最近的頂點 v1，得子樹 T1，再連接與 T1 最近的

41、頂點 v2 ，得子樹 T2 ，如此進行下去，直到所有頂點都用到為止。L(v):v到子樹 T0 的直接距離。 E 是邊集合。輸入加權連通圖的帶權鄰接矩陣C=（ Cij ） n*n .(1)T0 <- 空集， C（ T0） <-0,V 1=v 0(2)對每一點 v 屬于 V-V 1， L（ v ）<-C(v, v0);如果 (v, v0) 不屬于E，則 C(v, v 0 )= 無窮大 (3) 若 V1 =V,則輸出 T0 ，C（ T0），停機。否則轉到下一步；(4) 在 V-V 1 中找一點 u, 使 L（ u） =minL(v)|v 屬于 (V-V 1), 并記在 V1 中與

42、u 相鄰的點為 w,e=(w,u)(5)T0 <-T 0， C（ T0 ）<- C （ T0）+ C （e）, V 1 <-V 1(6)對所有的 v 屬于 V-V 1，若 C(v, u)<L （ v） , 則 L（ v ）<- C(v, u),否則 L（v）不變。(7) 轉 3克魯斯卡爾（ Kruskal ）算法基本思想 ：最初把圖的n 個頂點看作n 個分離的部分樹，每個樹具有一個頂點，算法的每一步選擇可連接兩分離樹的邊中權最小的邊連接兩個部分樹，合二為一，部分樹逐步減少 ，直到只有一個部分樹，便得到最小生成樹。克魯斯卡爾（ Kruskal ）算法步驟：T0 :

43、存放生成樹的邊的集合，初態為空；C(T 0): 最小生成樹的權，初值為0；VS：部分樹的頂點集合，其初值為v 0 v1 vn輸入邊的端點數組A（e）, 邊的權值 w(e);(1)T0 為空， C(T0)<-0;VS為空，將 E 中的邊按從小到大的順序排列成隊列Q；(2) 對所有的 v 屬于 V， VS -v;(3) 若|VS|=1 ，輸出 T0 ， C(T0 ) ，停止，否則轉下一步；(4) 從 Q中取出排頭邊（ u,v ），并從 Q中刪除（ u,v ）;(5)如 u,v 雜 VS的同一個元素集V1 中，則轉 4，否則分屬于兩個幾個V1 V 2 ，進行下一步；(6)T0<- T 0

44、，V<-, C(T 0 )<- C(T 0 )+ C(u,v), 轉 3求最短路徑在圖中求最短路徑問題有兩種提法，一是求從某個源點到其他頂點的最短路徑，二是求每一對頂點之間的最短路徑。對于前者，一般采用迪杰斯特拉（Dijkstra ）算法，按路徑長度遞增的次序產生最短路徑。時間復雜度為O(n 2)。迪杰斯特拉（ Dijkstra ）算法的基本思想： 生長一棵以 v0 為根的最短路樹，在這棵樹上每一頂點與根之間的路徑都是最短路徑 。由于網絡不存在負權 ，最短路樹的生長過程中各頂點將按照距v0 的遠近及頂點的相鄰關系，逐次長入樹中，先近后遠，直至所有頂點都已經在樹中。解決后面一種問題的

45、方法是：每次以一個頂點為源點，重復執行迪杰斯特拉算法n 次。另外還可以使用一種弗洛伊德（ Floyd ）算法，其時間復雜度也是 O(n3) 。n 個矩陣， D （ 1） D （ 2） .D弗洛伊德 （ Floyd）算法基本思想： 直接在圖的帶權鄰接矩陣中用插入頂點的方法依次構造出（ n） ,使最后得到的矩陣 .D（ n） 成為圖的距離矩陣，同時也求出插入點矩陣以便得到兩點見的最短路徑。拓撲排序拓撲排序的算法原理實際很簡單。I. 在有向圖中選一個沒有前驅的頂點且輸出之II. 從圖中刪除該頂點和所有以它為尾的弧重復執行以上兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。后一種情況則說明有向圖中存在環。求關鍵路徑在 AOE 網絡中的某些活動可以并行的進行，因此完成工程的最少時間是從開始頂點到結束頂點的最長路徑長度，稱從開始頂點到結束頂點的最長路徑為關鍵路徑，關鍵路徑上的活動即為關鍵活動。3. 數據結