第3章算法與數(shù)據(jù)結構

第3章算法與數(shù)據(jù)結構

3.1緒論3.2線性表3.3棧和隊列3.4數(shù)組3.5樹與二叉樹3.6圖3.7查找技術3.8排序技術第3章算法與數(shù)據(jù)結構3.1緒論程序=算法+數(shù)據(jù)結構算法是指對操作的描述，即操作的步驟；數(shù)據(jù)結構是指對數(shù)據(jù)的描述，即數(shù)據(jù)的類型和組織形式； 線性結構：線性表、棧、隊列、數(shù)據(jù)的邏輯結構字符串、數(shù)組、廣義表非線性結構：樹、圖

順序存儲數(shù)據(jù)結構數(shù)據(jù)的存儲結構鏈式存儲 檢索、排序、數(shù)據(jù)的運算插入、刪除、修改等

圖3-1數(shù)據(jù)結構主要研究的三個方面問題3.1.1數(shù)據(jù)結構的基本概念1.數(shù)據(jù)：是指用符號來描述客觀事物,包含數(shù)值、字符、圖形、圖像、聲音等。2.數(shù)據(jù)項：是指能用來描述數(shù)據(jù)的最小單位。3.數(shù)據(jù)元素(記錄)：是描述數(shù)據(jù)的基本單位，一個數(shù)據(jù)元素可以由一個或多個數(shù)據(jù)項組成。4.數(shù)據(jù)對象：是一類性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)結構的基本概念5.數(shù)據(jù)結構數(shù)據(jù)結構是指相互之間有關系的數(shù)據(jù)元素的集合。組成：數(shù)據(jù)和結構數(shù)據(jù)：數(shù)據(jù)元素的集合；結構：數(shù)據(jù)元素之間關系的集合。數(shù)據(jù)元素之間的關系：（1）集合結構：所有數(shù)據(jù)元素“屬于同一個集合，關系松散。（2）線性結構：數(shù)據(jù)元素之間存在“一對一”的相鄰關系（3）樹狀結構：數(shù)據(jù)元素之間存在“一對多”的層次關系（4）圖狀結構：數(shù)據(jù)元素之間存在“多對多”的任意關系邏輯結構和存儲結構分類：邏輯結構和存儲結構。（1）邏輯結構：用數(shù)學模型來描述數(shù)據(jù)元素之間的邏輯關系一個數(shù)據(jù)的邏輯結構包括兩個方面內容：①數(shù)據(jù)元素的信息；②數(shù)據(jù)元素之間的前后關系（前驅和后繼）。表示方法：Data_Structure=（D，R）D為數(shù)據(jù)元素的有限集合，R為D上關系的有限集合例如，每周的數(shù)據(jù)結構表示為：Week=(D,R)D={周一,周二,周三,周四,周五,周六,周日}R={(周一,周二),(周二,周三),(周三,周四),(周四,周五),(周五,周六),(周六,周日)}邏輯結構和存儲結構(2)存儲結構：數(shù)據(jù)的邏輯結構在計算機內的存儲形式。分類：順序存儲結構、鏈式存儲結構等順序存儲結構的特點：借助于數(shù)據(jù)元素在存儲器中的相鄰位置來表示數(shù)據(jù)元素之間的邏輯關系。即邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。鏈式存儲結構的特點：使用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，借助于指示數(shù)據(jù)元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關系。即邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上不一定相鄰。另外還有索引存儲結構和散列存儲結構，但是它們都是通過順序存儲結構和鏈式存儲結構復合而成。數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構是數(shù)據(jù)結構不可分開的兩個方面。一方面，數(shù)據(jù)的邏輯結構是數(shù)據(jù)結構的抽象；另一方面，數(shù)據(jù)的存儲結構是數(shù)據(jù)結構的具體實現(xiàn)在進行數(shù)據(jù)處理時候，一種數(shù)據(jù)的邏輯結構可以依據(jù)需要而采用多種不同的存儲結構，只要能反映出所要求的邏輯關系即可。但是，選用其中最合適的存儲結構對于提高數(shù)據(jù)處理的效率是非常重要的。

3.1.2算法

1.算法的定義算法：是問題求解邏輯步驟的一種準確而完整地描述。同一個算法如果采用不同的編程語言能夠編寫出不同的程序，所以，算法不等于程序，程序的編寫也絕不可能優(yōu)于算法的設計。描述算法的工具：自然語言、傳統(tǒng)流程圖、N-S流程圖、偽代碼、類計算機語言、計算機語言。

2.算法的基本特性

（1）有窮性：一個算法應包含有限的操作步驟（2）確定性：一個算法中的每一步驟必須有確定的含義，不能是含糊不清的。并且算法只有一個入口和一個出口。（3）可行性：一個算法應可以有效地執(zhí)行（4）輸入：一個算法有零個或多個外部輸入。零個輸入是指算法本身具有初始條件。（5）輸出：一個算法至少要有一個輸出。3.算法的基本要素兩個基本要素：（1）算法中對數(shù)據(jù)對象的運算和操作：算法中基本的運算和操作包括算術運算、關系運算、邏輯運算和數(shù)據(jù)傳輸。（2）算法的控制結構：是指算法中各個操作之間的先后執(zhí)行次序。一個算法的執(zhí)行次序可以使用順序、選擇和循環(huán)三種基本結構組合而成。

4.算法設計的基本方法

（1）列舉法：根據(jù)實際問題，列舉出所有可能的情況（2）歸納法：通過對特殊的情況進行歸納分析后找出一般的關系。（3）遞推法：從已知的條件逐漸推出結果。它也屬于歸納法。（4）遞歸法：先將復雜問題逐層分解（即回推）成最簡單的問題，當解決了最簡單的問題后，再沿著原來分解的逆過程逐步回歸（即遞推）以便解決復雜問題（5）減半遞推法：將復雜問題的規(guī)模減少一半，并且重復進行減半的過程。

5.算法的評價

（1）正確性：根據(jù)算法編寫的程序能夠得到滿足問題要求的結果。（2）可讀性：算法首先應是便于理解、其次才是計算機可以執(zhí)行。（3）健壯性：輸入不合法數(shù)據(jù)時算法能作出相應的處理，而不是陷入癱瘓。（4）高效率：根據(jù)算法編寫的程序有較快的運算速度。（5）低存儲量：根據(jù)算法編寫的程序在運行時占用較少的存儲空間。6.算法的復雜度（1）算法的時間復雜度算法的時間復雜度：是指執(zhí)行算法所需要的計算工作量。算法的計算工作量應使用算法在執(zhí)行過程中的基本運算執(zhí)行次數(shù)來度量。算法執(zhí)行的基本運算次數(shù)與問題的規(guī)模有關例如，兩個30階矩陣相乘的基本運算次數(shù)一定大于兩個5階矩陣相乘的基本運算次數(shù)。算法的復雜度（2）算法的空間復雜度

算法的空間復雜度：是指執(zhí)行算法所需存儲空間的度量。它包括算法程序占用的存儲空間、輸入的原始數(shù)據(jù)占用的存儲空間和執(zhí)行算法所需額外占用的存儲空間（如在鏈式存儲結構中，既要存儲數(shù)據(jù)又要額外存儲鏈接地址以便來表示數(shù)據(jù)元素之間的關系）。

3.2線性表

3.2.1線性表的基本概念線性表是最簡單的一種數(shù)據(jù)結構，它是由一組數(shù)據(jù)元素組成。一年的月份號（1，2，3，…，12）是一個線性表，每個數(shù)據(jù)元素是一個整型數(shù)。英文小寫字母表（a，b，c，…，z）是一個線性表，每個數(shù)據(jù)元素是一個小寫字母。學生成績表也是一個線性表，每個數(shù)據(jù)元素是由學號、姓名、數(shù)學、外語、計算機等數(shù)據(jù)項組成。

線性表的基本概念

綜上所述，線性表是由n（n≥0）個類型相同的數(shù)據(jù)元素a1，a2，…，ai-1，ai，ai+1，…，an組成的有限序列。一般可以表示為：L=（a1，a2，…，ai-1，ai，ai+1，…，an）其中，L稱為線性表的名稱。n稱為線性表的長度。當n=0時稱為空線性表。非空線性表的特征①有且只有一個根結點，它沒有前驅結點。②有且只有一個終端結點，它沒有后繼結點③除根結點和終端結點外，每個結點有且只有一個直接前驅結點，有且只有一個直接后繼結點。

3.2.2線性表的順序存儲及其基本運算

在計算機中存放線性表，主要有兩種基本存儲結構：順序存儲結構和鏈式存儲結構。順序存儲結構：把線性表中邏輯結構上相鄰的數(shù)據(jù)元素依次存放在計算機內一組物理地址連續(xù)的存儲單元中，即把邏輯關系上相鄰接的數(shù)據(jù)元素存儲在物理地址也相鄰接的存儲單元之中。順序表：用順序存儲結構來存儲的線性表。順序表具有的兩個基本特點：（1）順序表的所有數(shù)據(jù)元素所占的存儲空間是連續(xù)的；（2）順序表的各個數(shù)據(jù)元素在存儲空間中是按照邏輯順序依次存放的。線性表的順序存儲假設長度為n的順序表（a1，a2，…，ai-1，ai，ai+1，…，an）中每個數(shù)據(jù)元素所占的存儲空間相同（假設都為k字節(jié)），并且第i個數(shù)據(jù)元素ai的存儲地址用Address（ai）表示，順序表中第i個數(shù)據(jù)元素ai在計算機存儲空間中的存儲地址可以表示為：Address（ai）=Address（a1）+（i-1）*k（1≤i≤n）若知道順序表的起始地址Address（a1）和每個數(shù)據(jù)元素所占的字節(jié)數(shù)k，則順序表中任意一個數(shù)據(jù)元素都可隨機存取。順序表的存儲結構是一個隨機存取的存儲結構。1.順序表的插入運算（1）在通常情況下，若在第i（1≤i≤n+1）個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)元素時，要從最后一個（即第n個）數(shù)據(jù)元素開始，直到第i個數(shù)據(jù)元素之間共n-i+1個數(shù)據(jù)元素依次向后移動一個位置。（2）在特殊情況下，若要在順序表第一個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)元素，則需要依次向后移動表中所有的n個數(shù)據(jù)元素若要在順序表最后一個數(shù)據(jù)元素之后插入一個新的數(shù)據(jù)元素，只要在表的末尾后面增加一個新的數(shù)據(jù)元素即可。（3）在平均情況下，插入一個新的數(shù)據(jù)元素需要移動表中一半的數(shù)據(jù)元素。數(shù)據(jù)元素的移動消耗很多時間，因此順序表的插入運算效率低。2.順序表的刪除運算（1）在通常情況下，若要在第i（1≤i≤n）個位置上刪除一個數(shù)據(jù)元素時，要從第i+1個數(shù)據(jù)元素開始，直到最后一個數(shù)據(jù)元素依次向前移動一個位置。（2）在特殊情況下，若要刪除第一個數(shù)據(jù)元素，則需要依次向前移動表中所有其它的數(shù)據(jù)元素；若要刪除最后一個數(shù)據(jù)元素，只要刪除表中末尾一個數(shù)據(jù)元素即可。（3）在平均情況下，刪除一個數(shù)據(jù)元素需要移動表中一半的數(shù)據(jù)元素。數(shù)據(jù)元素的移動消耗很多時間，因此順序表的刪除運算效率低

線性表順序存儲結構的優(yōu)缺點：

（1）優(yōu)點：存儲的物理位置相鄰，不需要增加額外的存儲空間可以根據(jù)初始地址隨機存取線性表中任一數(shù)據(jù)元素運算簡單方便，存儲空間緊湊，占用最少存儲空間（2）缺點：進行插入、刪除操作時需要移動大量的數(shù)據(jù)元素，消耗許多處理時間；由于占用連續(xù)存儲空間，只能進行預先靜態(tài)分配，若開辟的存儲空間太大，造成存儲空間浪費，若開辟的存儲空間小，當分配的存儲空間已滿時，再插入數(shù)據(jù)就會發(fā)生“上溢”錯誤，不便于擴充；由于使用相鄰整塊存儲單元，會產生較多的碎片。結論：線性表的順序存儲結構不適用于大線性表或者其中數(shù)據(jù)元素經常變動的線性表。適合于主要是進行查找而很少做插入和刪除操作。

3.2.3線性表的鏈式存儲及其基本運算

鏈式存儲結構：使用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，借助于指示數(shù)據(jù)元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關系。即邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上不一定相鄰。線性鏈表：用鏈式存儲結構來存儲的線性表簡稱為鏈表。根據(jù)鏈接的方式把鏈表分為單鏈表、雙鏈表和循環(huán)鏈表等。鏈表適合于頻繁地進行插入和刪除操作。

1．單鏈表

每個結點的存儲空間被分為兩個部分。數(shù)據(jù)域：存儲結點的值；指針域：存儲指向直接后繼的指針（地址）。所有的結點通過指針（地址）的連接按其邏輯順序鏈接在一起而組成了鏈表。線性單鏈表：每一個結點只包含一個指針域。頭指針（HEAD）：為了增強程序的可讀性，在線性單鏈表中增加一個指針指向鏈表的第一個結點。最后一個結點由于沒有直接后繼結點，則它的指針域值為空(用NULL、0或∧表示)，表示鏈表終止。由于任意一個結點的存取都必須從頭指針出發(fā)，順著鏈域逐個結點往下進行，所以單鏈表是順序存取的存儲結構。

（1）建立線性單鏈表

建立線性單鏈表①頭插法建立線性單鏈表：從空鏈表開始，每次申請生成一個新的結點，將讀入的數(shù)據(jù)存放到數(shù)據(jù)域，并設置指針域為空。然后將新結點插入到鏈表頭結點的后面，即新結點的指針域存儲原來頭結點指針域存放的指針，再將頭結點的指針域存儲指向新結點的指針（或存儲地址），重復以上的操作，直到讀入的數(shù)據(jù)為結束標志。使用頭插法建立線性單鏈表時，結點的邏輯順序與輸入數(shù)據(jù)元素的順序相反。

（1）建立線性單鏈表

建立線性單鏈表②尾插法建立線性單鏈表：從空鏈表開始，每次申請生成一個新的結點，將讀入的數(shù)據(jù)存放到數(shù)據(jù)域，并設置指針域為空。然后將新結點插入到鏈表尾結點的后面，即原來鏈表尾結點的指針域存儲指向新結點的指針（或存儲地址），此時新結點轉變?yōu)樾碌奈步Y點，重復以上操作，直到讀入的數(shù)據(jù)為結束標志。使用尾插法建立線性單鏈表時，結點的邏輯順序與輸入數(shù)據(jù)元素的順序相同

（2）線性單鏈表的查找

①按照值進行查找：從線性單鏈表的頭指針出發(fā)，順著鏈表逐個將結點數(shù)據(jù)域的值和要查找的給定值作比較。實際應用中，為了便于操作，需要在線性單鏈表中查找包含給定值x元素的前一結點存儲位置（用指針pre指向），可以方便地在該結點后插入新的結點或者刪除該結點后的結點。查找的結果如下：若單鏈表中存在要查找的給定值，則返回的（pre）為第一次找到的包含給定值x元素的前一結點位置；若單鏈表中不存在要查找的給定值，則返回的(pre)為單鏈表的最后結點位置。線性單鏈表的查找②按照序號進行查找：從線性單鏈表的頭指針出發(fā)，順著鏈表逐個結點往下掃描直到第i個結點為止。實際應用中，為了便于操作，在線性單鏈表中查找第i個結點的前一結點存儲位置（用指針pre指向），就可以方便地在該結點后插入新的結點或者刪除該結點后的結點。查找的結果：查找到結點（1≤i≤n），則返回的（pre）為第i個結點的前一結點位置；沒查找到返回的(pre)為單鏈表的最后結點位置.

（3）線性單鏈表的插入

線性單鏈表的插入：在線性單鏈表中插入一個新的數(shù)據(jù)元素。①按照值進行插入：是在線性單鏈表中指定值數(shù)據(jù)元素之前插入一個新數(shù)據(jù)元素。運算過程：1）申請新結點：生成一個新結點，輸入數(shù)據(jù)存放到數(shù)據(jù)域；2）查找：在單鏈表中查找包含給定值x元素的前一結點存儲位置（用指針pre指向）；3）修改鏈接：首先設置新結點的指針域指向結點x，然后再設置x前一結點的指針域指向新結點。線性單鏈表的插入②按照序號進行插入：是指在線性單鏈表中第i個結點之前插入一個新的結點。運算過程：1）申請新結點：生成一個新結點，輸入數(shù)據(jù);2）查找：在單鏈表中查找第i個結點之前的結點ai-1的存儲位置（用指針pre指向）；3）修改鏈接：首先設置新結點的指針域指向結點ai，再設置結點ai-1的指針域指向新結點（注意，在程序設計時此順序不能顛倒）。在線性單鏈表的插入過程中，不需要移動數(shù)據(jù)元素，只要改變相關結點的指針就可以實現(xiàn)，提高了效率。

（4）線性單鏈表的刪除

線性單鏈表的刪除:是指在線性單鏈表中刪除一個數(shù)據(jù)元素。①按照值進行刪除：是指在線性單鏈表中刪除指定值的數(shù)據(jù)元素。運算過程：1）查找：在單鏈表中查找包含給定值x元素的前一結點存儲位置，用指針pre指向；2）修改鏈接：設置x的前一結點指向x的直接后繼結點；3）釋放結點：釋放結點x所占用的存儲空間。

線性單鏈表的刪除

②按照序號進行刪除：是指在線性單鏈表中刪除第i個結點。運算過程：1）查找：在單鏈表中查找第i個結點之前的結點ai-1的存儲位置（用指針pre指向）；2）修改鏈接：設置ai-1指向ai的直接后繼結點ai+1，即把ai-1的指針域改變?yōu)榇娣沤Y點ai指針域的值（為ai+1的存儲地址），就能把結點ai從鏈上摘下；3）釋放結點：最后釋放結點ai所占用的存儲空間鏈表的優(yōu)缺點：①優(yōu)點:在鏈表中進行插入、刪除操作時只需要修改指針而不需要移動表中的數(shù)據(jù)元素.適合對于頻繁進行插入、刪除操作的線性表；②缺點:對鏈表中的數(shù)據(jù)元素只能順著鏈表進行順序存取而不能進行隨機存取。

2．雙鏈表

在線性單鏈表中，指針可以很方便地找到后繼結點，但是卻不能找到前驅結點；在線性單鏈表的每個結點中再增加一個指針域用來指向該結點的直接前驅。每個結點包含兩個指針指向直接前驅結點的指針稱為左指針(llink)，指向直接后繼結點的指針稱為右指針(rlink)，由此形成的線性鏈表就有兩個不同方向的鏈，則稱為雙向鏈表，簡稱為雙鏈表（doublelinkedlist）。3．循環(huán)鏈表將單鏈表中最后一個結點的指針域由空（NULL）改變?yōu)橹赶蝾^結點而使鏈表頭尾相接形成環(huán)狀，稱為單向循環(huán)鏈表，簡稱為循環(huán)鏈表（circularlinkedlist）。在單向循環(huán)鏈表中，只是對表的鏈接方式稍微改變一些，就使得可以從任意一個結點出發(fā)來訪問表中所有其它的結點，提高了查找的效率。而線性單鏈表卻做不到這一點。

循環(huán)鏈表

循環(huán)鏈表的特點：①循環(huán)鏈表增加一個頭結點，其數(shù)據(jù)域可以依據(jù)需要設置，其指針域指向第一個結點。即循環(huán)鏈表的頭指針HEAD指向頭結點，而頭結點指向第一個結點；②循環(huán)鏈表最后一個結點的指針域指向頭結點而不是空。

3.3棧和隊列

3.3.1棧及其基本運算1．棧的基本概念棧（stack）是一種特殊的線性表，它是限定僅在一端進行插入或刪除操作的線性表。允許進行插入或刪除操作的一端稱為棧頂（top）；不允許進行插入、刪除操作的另一端稱為棧底（bottom）。不含數(shù)據(jù)元素的棧稱為空棧。棧是根據(jù)“先進后出或“后進先出”的原則組織數(shù)據(jù)。向棧中插入一個數(shù)據(jù)元素稱為入棧；從棧中刪除一個數(shù)據(jù)元素稱為退棧。

2．棧的順序存儲及其基本運算棧的順序存儲結構的基本運算：入棧運算、退棧運算、讀棧運算。（1）順序棧的入棧運算順序棧的入棧運算是指在棧頂位置插入一個新的數(shù)據(jù)元素。運算過程：①修改指針：將棧頂指針加1（top加1）；②插入；在當前棧頂指針所指向的位置將新的數(shù)據(jù)元素插入。在順序棧的入棧運算過程中，若棧頂指針已經指向棧存儲空間的最后位置（即top=n），表明此時棧的空間已滿，不能再進行入棧運算，否則會產生棧的上溢錯誤。

棧的順序存儲及其基本運算

（2）順序棧的退棧運算順序棧的退棧運算是指在棧頂位置取走一個數(shù)據(jù)元素并且把它賦給某個變量。運算過程：①退棧：將棧頂指針所指向的棧頂元素讀取后并且賦給一個變量；②修改指針：將棧頂指針減1（top減1）。在順序棧的退棧運算過程中，若棧頂指針已經為0時（即top=0），表明此時棧空，不能再進行退棧運算，否則會產生棧的下溢錯誤。

棧的順序存儲及其基本運算

（3）順序棧的讀棧運算順序棧的讀棧運算是指在棧頂位置讀取一個數(shù)據(jù)元素并且把它賦給某個變量。運算過程：將棧頂指針所指向的棧頂元素讀取并賦給一個變量，棧頂指針保持不變。在順序棧的讀棧運算過程中，若棧頂指針已經為0時（即top=0），表明此時棧空，不能再進行讀棧運算，即讀不到棧頂元素。

3．棧的鏈式存儲及其基本運算

與一般的線性表類似，在程序設計時，棧也可以使用鏈式存儲結構。用鏈式存儲結構來存儲的棧，稱為帶鏈的棧，簡稱為鏈棧。它其實就是運算受限的單鏈表，其插入和刪除操作僅限制在鏈表的表頭位置上進行，所以，棧頂指針就是鏈表的頭指針，頭指針指向棧頂結點（不帶頭結點）或者頭結點（帶頭結點）。

3.3.2隊列及其基本運算

1．隊列的基本概念隊列也是一種特殊的線性表，它是限定在一端進行插入操作，而在另一端進行刪除操作的線性表。其中，允許進行插入操作的一端稱為隊尾，允許進行刪除操作的另一端稱為隊頭。不含數(shù)據(jù)元素的隊列稱為空隊列。隊列是根據(jù)“先進先出或“后進后出的原則組織數(shù)據(jù)，一般用隊頭指針（front）指向隊頭位置數(shù)據(jù)元素的前一個單元，用隊尾指針（rear）指向隊尾位置數(shù)據(jù)元素。向隊列中插入一個數(shù)據(jù)元素稱為入隊，插入的結點只能加到隊尾。從隊列中刪除一個數(shù)據(jù)元素稱為退隊，刪除的結點只能來自隊頭位置。

2．隊列的順序存儲及其運算

與一般的線性表類似，在程序設計時，可以使用一維數(shù)組作為隊列的順序存儲空間。用順序存儲結構來存儲的隊列簡稱為順序隊列。隊列的順序存儲結構可以采用循環(huán)隊列的形式。將順序存儲的隊列的最后一個位置指向第一個位置，從而使順序隊列形成邏輯上的環(huán)狀空間，稱為循環(huán)隊列。當循環(huán)隊列的最后一個位置已經被使用而還要進行入隊運算時，此時只要第一個位置空閑，就可以將數(shù)據(jù)元素插入到第一個位置，即將第一個位置作為新的隊尾。可以設置n表示循環(huán)隊列的最大存儲空間。循環(huán)隊列在循環(huán)隊列中，從隊頭指針front指向的下一個位置到隊尾指針rear指向的隊尾位置之間的所有數(shù)據(jù)元素都是隊列中的數(shù)據(jù)元素。循環(huán)隊列具有兩種基本運算：入隊運算、退隊運算。循環(huán)隊列的初始狀態(tài)為空，此時front=rear=n。循環(huán)隊列進行一次退隊運算，隊頭指針front就加1，若front=n+1時，則設置front=1。循環(huán)隊列進行一次入隊運算，隊尾指針rear就加1，若rear=n+1時，則設置rear=1。由于在循環(huán)隊列中，循環(huán)隊列為空或滿都有front=rear，即根據(jù)front=rear不能判定隊列是空還是滿，一般還要增加一個標志sign，用sign=0表示隊列空；用sign=1且front=rear表示隊列滿。

循環(huán)隊列的兩種基本運算

（1）循環(huán)隊列的入隊運算循環(huán)隊列的入隊運算是指在循環(huán)隊列的隊尾位置插入一個新的數(shù)據(jù)元素。運算過程：①修改隊尾：將隊尾加1（即rear=rear+1），此時若rear=n+1則設置rear=1；②結點插入：將新結點插入到將隊尾指針所指向的位置。當sign=1并且rear=front，循環(huán)隊列空間已滿，就不能進行入隊，否則會產生上溢錯誤。（2）循環(huán)隊列的退隊運算。循環(huán)隊列的退隊運算是指在循環(huán)隊列的隊頭位置退出一個數(shù)據(jù)元素并且保存在指定的變量中。運算過程：①修改隊頭：先將隊頭加1（即front=front+1），此時若front=n+1則設置front=1；②結點退出保存：將隊頭指針所指向位置的數(shù)據(jù)元素退出并且賦給一個指定變量。當sign=0時循環(huán)隊列為空，就不能進行退隊，否則會產生下溢錯誤。

3.4數(shù)組

3.4.1數(shù)組的基本概念數(shù)組是一種特殊的線性表，它的數(shù)據(jù)元素自身也是一個線性表。在科學計算中，矩陣是一種常用的數(shù)學對象，在使用高級語言編寫程序時，一般將一個矩陣描述為一個二維數(shù)組。所以在此主要研究二維數(shù)組。因為計算機的內存空間是一維結構，而數(shù)組是多維結構，所以使用計算機的內存單元存儲數(shù)組元素存在次序問題。二維數(shù)組有兩種存儲次序：以行為主序的順序存儲和以列為主序的順序存儲。

3.4.2數(shù)組的存儲結構

以行為主序的順序存儲是將數(shù)組中的數(shù)據(jù)元素從第一行開始一行接一行地順序存儲在計算機內連續(xù)的存儲空間中。以列為主序的順序存儲是將數(shù)組中的數(shù)據(jù)元素從第一列開始一列接一列地順序存儲在計算機內連續(xù)的存儲空間中。例如，C語言的數(shù)組在計算機中采用以行為主序的順序存儲方式。在二維數(shù)組以行為主序的順序存儲中，數(shù)據(jù)元素aij在一維內存空間中存儲地址為：Address(aij)=Address(a11)+[(i-1)*n+j-1]k其中，Address(a11)為二維數(shù)組中第一個數(shù)據(jù)元素的存儲地址，每個數(shù)據(jù)k字節(jié),n為列數(shù)。

3.5樹與二叉樹

樹是一類非線性數(shù)據(jù)結構，其中最為常用的是二叉樹。使用圖形來表示樹這樣的數(shù)據(jù)結構時，很像是自然界中一棵倒長的樹。在現(xiàn)實生活中，有許多能用樹的結構表示的關系：人類家族的血緣關系、銀行的行政關系、書目錄的層次關系等。3.5.1樹的基本概念樹（tree）是n（n≥0）個結點的有限集合，在任意一棵非空樹中：①有且僅有一個結點稱為樹的根（root）；②其余n-1個結點被分成為m（m≥0）個互相不相交的有限集合，其中每一個集合自身又是一棵樹，稱為根結點的子樹（subtree）。樹的定義是一個遞歸定義。樹的基本概念在樹的結構中，樹中的每個數(shù)據(jù)元素也稱為結點。可分為根結點、分支結點和葉子結點。每個結點的上一層結點稱為該結點的雙親結點。沒有雙親的結點稱為樹的根。每個結點的下一層結點稱為該結點的孩子結點。每個結點擁有的子樹數(shù)目稱為該結點的度。所有結點的度中最大的值稱為樹的度。樹中度為0的結點稱為葉子結點。從根結點開始到某結點的層數(shù)稱為該結點的深度。所有結點的層數(shù)中最大的值稱為樹的深度。若樹中結點的各棵子樹是從左至右有先后次序的，則稱該樹為有序樹，否則稱為無序樹。

3.5.2二叉樹及其基本性質

由于對二叉樹的操作算法相對簡單，所以二叉樹在樹結構的實際應用中起著重要的作用，它解決了樹的存儲結構及其運算中的復雜性問題。1．什么是二叉樹二叉樹是n（n≥0）個結點的有限集合。它或者為空集，或者是由一個根結點加上兩棵互相不相交的左子樹和右子樹組成，并且左子樹和右子樹也都是二叉樹。二叉樹的特點：①二叉樹的每個結點至多有二棵子樹（即不存在度大于2的結點）。②二叉樹的子樹分為左子樹、右子樹，其次序也不能任意顛倒互換。

2．二叉樹的基本性質

性質1：在二叉樹的第i（i≥1）層上，至多有2i-1個結點。性質2：在深度為k（k≥1）的二叉樹上，至多有2k-1個結點。性質3：在任意一棵二叉樹中，葉子結點的數(shù)目總比度為2的結點數(shù)目多一個。性質4：在具有n個結點的一棵二叉樹中，其深度至少為【log2n】＋1。其中【log2n】為取log2n的整數(shù)部分

二叉樹的基本性質

滿二叉樹除最后一層葉子結點以外的各層任何結點都有兩個子結點，并且所有的葉子結點都在同一層上。就是說滿二叉樹中的每一層的結點數(shù)都達到了最大值。完全二叉樹除最后一層外，每一層結點數(shù)都達到最大值；最后一層結點在該層左對齊，但可以缺少右邊的若干結點。完全二叉樹的特點是：（1）如果最大層次為k，則葉子結點都在第k－1層或k層上。（2）對任意結點，如果其右子樹的最大層次為k，則其左子樹的最大層次為k或k＋1。

二叉樹的基本性質

性質5：在具有n個結點的一棵完全二叉樹中，其深度為【log2n】＋1。其中【log2n】為取log2n的整數(shù)部分。性質6：在具有n個結點的一棵完全二叉樹中，若把結點按層序編號（從上層到下層，每層從左到右)，則對任一結點i（1≤i≤n)，有：（1）如果i＝1，則結點i是二叉樹的根，無雙親結點；如果i>1，則結點i的雙親結點編號是【i/2】。其中【i/2】為取i/2的整數(shù)部分。（2）如果2i≤n，則結點i的左孩子結點編號是2i；否則無左孩子結點。（3）如果2i+1≤n，則結點i的右孩子結點編號是2i＋1；否則無右孩子結點。性質7：在具有n個結點的一棵完全二叉樹中，當n為偶數(shù)時，有且只有一個度為1的結點；當n為奇數(shù)時，則沒有度為1的結點。性質8：在具有n個結點的一棵完全二叉樹中，編號大于【n/2】的結點均為葉子結點。其中【n/2】為取n/2的整數(shù)部分。

3.5.3二叉樹的存儲結構

1．二叉樹的順序存儲結構在二叉樹中，將所有結點的數(shù)值按照由上到下、由左到右的順序來存儲在一個一維數(shù)組（線性結構）中，這樣的存儲方式稱為二叉樹的順序存儲結構。對于滿二叉樹或完全二叉樹可以使用順序存儲結構來存儲。因為滿二叉樹或完全二叉樹可以按照層的順序進行順序存儲，并能很快確定每一個結點的雙親結點和左右孩子結點，能明確樹中各個結點的之間的相互關系，并且可以節(jié)省存儲空間。對于一般的二叉樹應使用鏈式存儲結構來存儲。

2．二叉樹的鏈式存儲結構在二叉樹的鏈式存儲結構中，存儲二叉樹的每個結點的存儲空間也被分為兩個部分：數(shù)據(jù)域和指針域。由于二叉樹的每個結點可以有兩個子結點，使得每個結點上需要有兩個指針域，分別指向其左子樹和右子樹，這種二叉樹的鏈式存儲結構稱為二叉鏈表。與分別指向直接前驅結點和直接后繼結點的雙向鏈表不同，二叉鏈表的兩個指針一個用于指向該結點的左子結點，另一個用于指向該結點的右子結點。3.5.4二叉樹的遍歷不重復地訪問二叉樹中的所有結點。一般先遍歷左子樹，再遍歷右子樹。根據(jù)訪問根結點的次序，可分為三種：前序遍歷、中序遍歷、后序遍歷二叉樹的前序遍歷（根左右）先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。再遍歷左右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。如下圖前序序列：ABDECFABCDEF二叉樹的中序遍歷（左根右）先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。再遍歷左右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。如下圖中序序列：DBEAFCABCDEF二叉樹的后序遍歷（左右根）先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。再遍歷左右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。如下圖后序序列：DEBFCAABCDEF二叉樹的遍歷例：設一顆二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則后序遍歷結果為

。結果：DEBFCA

3.7查找技術

3.7.1查找的基本概念查找:在一個含有若干記錄（或數(shù)據(jù)元素）的列表中找出關鍵字值與給定值相同的記錄的過程。若找到相應的記錄，則查找成功，返回記錄在表中的位置或記錄的信息；否則，查找失敗，返回空地址或失敗的信息。在查找過程中，若只是對表內數(shù)據(jù)進行查詢，則稱為靜態(tài)查找；在對表內數(shù)據(jù)進行查詢的同時，還對表進行更新（如插入或刪除）操作，則稱為動態(tài)查找。

3.7.2基于線性表的查找

基于線性表的查找分為：順序查找、二分法查找和分塊查找。1．順序查找順序查找是最簡單的一種查找方法。它是從線性表的任意一端開始，從前向后或從后向前逐個將表中數(shù)據(jù)元素與給定的關鍵字進行比較，若表中某個記錄的關鍵字值與給定的關鍵字值相等，則查找成功；若到達表的另一端后，所有記錄的關鍵字值與給定的關鍵字值都不相等，則查找失敗。順序查找的存儲結構既可以采用順序存儲結構，也可以采用鏈式存儲結構。只能使用順序查找的兩種情況：①對于無序線性表（即線性表中數(shù)據(jù)元素排列是無序的），無論是采用順序存儲結構，還是采用鏈式存儲結構，都必須使用順序查找；②對于有序線性表（即線性表中數(shù)據(jù)元素排列是有序的），若采用的是鏈式存儲結構，也必須使用順序查找。

基于線性表的查找

（1）線性表在順序存儲結構下的順序查找返回為要查找的數(shù)據(jù)元素x在線性表中的序號；若不存在時，返回NULL。若線性表的存儲空間中含有多個數(shù)據(jù)元素值為x的記錄，則只能返回第一個查找到的數(shù)據(jù)元素x在線性表中的序號。例如，已知線性表（5，15，20，40，60，35，50，70，85，100）用順序存儲結構來存儲。若順序查找與給定的關鍵字值“60”相等的數(shù)據(jù)元素，則要將給定的關鍵字從前向后依次與線性表中第1個位序（數(shù)據(jù)元素為5）到第5個位序（數(shù)據(jù)元素為60）之間的數(shù)據(jù)元素進行比較，返回的是要查找的數(shù)據(jù)元素在線性表中的序號5。

基于線性表的查找

（2）線性表在鏈式存儲結構下的順序查找返回要查找的數(shù)據(jù)元素x在線性鏈表中的存儲地址；若不存在時，返回NULL。若線性鏈表的存儲空間中含有多個數(shù)據(jù)元素值為x的記錄，只能返回第一個查找到的數(shù)據(jù)元素x在線性鏈表中的存儲地址。順序查找的算法簡單，查找的效率與數(shù)據(jù)元素所在的位置有關。優(yōu)點是對表中數(shù)據(jù)元素的存儲沒有特別要求；它的缺點是在平均情況下查找大約要與表中一半的數(shù)據(jù)元素進行比較，當線性表的長度很大時效率較低，即不適用于長度較大的線性表的查找。

2．二分法查找

線性表采用順序存儲結構存儲并按照關鍵字有序排列。二分查找的查找過程：①若線性表中間位置記錄的關鍵字值與給定的關鍵字值相等，則查找成功；②若線性表中間位置記錄的關鍵字值大于給定的關鍵字值，則在線性表的前半部分子表以同樣的方法進行查找；③若線性表中間位置記錄的關鍵字值小于給定的關鍵字值，則在線性表的后半部分子表以同樣的方法進行查找。重復以上過程，直到查找成功；或者直到子表不存在為止，此時查找失敗。長度為n的有序線性表在最壞情況下，順序查找需要比較n次，而二分查找只需要比較log2n次。

3.8排序技術

按照排序過程中依據(jù)的原則不同，將排序分為以下幾類：①插入排序：將無序序列中的數(shù)據(jù)元素依次插入到有序序列中。②交換排序：通過比較數(shù)據(jù)元素的關鍵字大小決定是否進行交換。例如，冒泡排序、快速排序。③選擇排序：將無序序列中關鍵字值最小的數(shù)據(jù)元素依次放到有序序列中的指定位置。例如，簡單選擇排序、樹型選擇排序、堆排序。

3.8.1插入類排序

插入排序是指每次將一個待排序的數(shù)據(jù)元素插入到有序序列中，直到將所有待排序的數(shù)據(jù)元素全部插入為止。常用的插入排序有直接插入排序、