1、第一節 算法一、 算法概念算法：解題方案的準確而完整的描述。（算法不等于程序）1、算法基本特征：1） 可行性：（算法與計算公式有差別）2） 確定性：算法中的每一個步驟都必須有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。3） 有窮性：算法必須能在有限的時間內做完，即算法必須能在執行有限個步驟之后終止。算法有窮性還應包括合理的執行時間的含義4）擁有足夠的情報2、算法的基本要素：兩種基本要素：一是對數據對象的運算和操作，二是算法的控制結構。1）算法中對數據的運算和操作(在計算機中)l 算術運算：l 邏輯運算：l 關系運算：l 數據傳輸：算法的主要特征著重于算法的動態執行。2）算法的控制結構

2、算法中各操作之間的執行順序稱為算法的控制結構。描述算法的工具：傳統流程圖、N-S結構化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環三種基本控制結構組合而成。4） 算法設計基本方法l 列舉法：基本思想是，根據提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。常用于解決“是否存在”或“有多少種可能”等類型問題。l 歸納法：基本思想是，通過列舉少量的特殊情況，經過分析，最后找出一般的關系。l 遞推：是指從已知的初始條件出發，逐次推出所要求的各中間結果和最后結果。本質上也屬于歸納法。l 遞歸：在解決一些復雜問題時，為了降低問題的復雜程度，一般總是將問

3、題逐層分解，最后歸結為一些最簡單的問題。本質上也屬于歸納法。遞歸分為直接遞歸與間接遞歸兩種。l 減半遞推技術（分治法）所謂“減半”，是指將問題的規模減半，而問題的性質不變；所謂“遞推”，是指重復“減半”產過程。l 回溯法二、算法復雜度算法的復雜度主要包括時間復雜度和空間復雜度。1、時間復雜度是指執行算法所需要的計算工作量。算法的工作量用算法所執行的基本運算次數來度量，而算法所執行的基本運算次數是問題規模的函數，即：算法的工作量=f(n)其中n是問題的規模。在同一個問題規模下，如果算法執行所需的基本運算次數取決于某一特定輸入時，可以用以下兩種方法來分析算法的工作量。1） 平均性態：是指用各種特定

4、輸入下的運算次數的加權平均值來試題算法的工作量。設x是所有可能輸入中的某個特定輸入，p(x)是x出現的概率，t(x)是算法在輸入為x時所執行的基本運算次數，則算法的平均性態定義為： 其中Dn表示當規模為n時，算法執行時所有可能輸入的集合。2）最壞情況復雜性是指在規模為n時，算法所執行的基本運算的最大次數，定義為：2、算法的空間復雜度一般是指執行這個算法所需要的內存空間。第二節 數據結構的基本概念主要研究和討論以下三個方面的問題：l 數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。l 在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。l 對各種數據結構進行的運算。

5、一、什么是數據結構1、 定義：數據處理：是指對數據集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數據元素進行分析。數據結構：相互有關聯的數據元素的集合。數據元素（元素）：現實世界中客觀存在的一切個體都可以是數據元素。在數據處理領域中，每一個需要處理的對象都可以抽象成數據元素。在數據處理領域中，通常把數據元素之間這種固有的關系簡單地用前后件（直接前驅與直接后繼）關系來描述。1、數據的邏輯結構一個數據結構應包含以下兩方面的信息：l 表示數據元素的信息;(D:數據元素的集合)l 表示各數據元素之間的前后件關系。(R:前后件關系)所謂數據的邏輯結構，是指反映數據元素之間邏

6、輯關系的數據結構。一個數據結構可以表示成：B=(D，R)其中B表示數據結構。例：一年四季的數據結構：B=(D,R)D=春，夏，秋，冬R=（春，夏）（夏，秋）（秋，冬）2、數據的存儲結構：（數據的物理結構）數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構。一種數據的邏輯結構根據需要可以表示成多種存儲結構。二、數據結構的圖形表示：數據結點(結點)：有向線段 前件結點à后件結點在數據結構中，沒有前件的結點稱為根結點；沒有后件的結點稱為終端結點（葉子結點）；除了根結點與終結點外的其他結點一般稱為內部結點。三、線性結構與非線性結構1、空的數據結構：在一個數據結構中一個數據元素都沒有

7、。2、非空的數據結構：在一個空的數據結構中插入一個新元素后就變為非空；將該元素刪除后就變為空的數據結構。2、線性結構(線性表)如果一個非空的數據結構滿足下列兩個條件，則稱其為線性結構：l 有且只有一個根結點l 每一個結點最多有一個前件，也最多有一個后件。u 在一個線性結構中插入或刪除任何一個結點后還應是線性結構。第三節 線性表及其順序存儲結構一、線性表的基本概念線性表是最簡單、最常用的一種數據結構；矩陣也是一個線性表。非空線性表有如下一些結構特征：1） 有且只有一個根結點a1，它無前件；2） 有且只有一個終端結點an，它無后件；3） 除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只

8、有一個后件。線性表中結點的個數n稱為線性表的長度；當n=0時，稱為空表。二、 線性表的順序存儲結構（順序分配）順序存儲結構具有以下兩個基本特點：1） 線性表中所有元素所占的存儲空間是連續的；2） 線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。假設線性表中的第一個數據元素的存儲地址（首地址）為ADR(a1)，每一個數據元素占k個字節，則線性表中第i個元素ai在計算機存儲空間中的存儲地址為：ADR(ai)= ADR(a1)+(i-1)k三、順序表的插入運算四、順序表的刪除運算第四節 棧和隊列一、棧及其基本運算1、什么是棧棧是限定在一端進行插入與刪除的線性表。在棧中，允許插入與刪除的一端稱為

9、棧頂，而不允許插入與刪除的另一端稱為棧底。棧是按照“先進后出”或“后進先出”的原則組織數據的。棧具有記憶作用。通常用指針top來指示棧頂的位置，用指針bottom指向棧底。往棧中插入一個元素稱為入棧運算，從棧中刪除一個元素稱為退棧運算。2、棧的順序存儲及其運算用一維數組S(1:m)作為棧的順序存儲空間。通常，棧底指針指向棧空間的低地址一端，S(bottom)通常為棧底元素，S(top)為棧頂元素。Top=0表示棧空；top=m表示棧滿。棧的基本運算有三種：入棧、退棧與讀棧項元素二、隊列及其基本運算1、什么是隊列隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常

10、用一個稱為尾指針的指針指向隊尾元素，即尾指針總是指向最后被插入的元素；允許刪除的一端稱為排頭，通常也用一個排頭指針指向排頭的前一個位置。隊列又稱為“先進先出”或“后進后出”的線性表，它體現了“先來先服務”的原則。往隊列的隊尾插入一個元素稱為入隊運算，從隊列的排頭刪除一個元素稱為退隊運算。2、循環隊列及其運算所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。循環隊列的初始狀態為空，即rear=front=m。每進行一次入隊運算，隊尾指針就進一。當隊尾指針rear=m+1時，則置rear=1。每進行一次退隊運算，排頭指針就進一，當排頭指針front

11、=m+1時，則置front=1。在實際使用循環隊列時，為了能區分隊列滿還是隊列空，通常還需增加一個標志s,s值的定義如下：0 表示隊列空s=1表示隊列非空隊列空與隊列滿的條件如下：隊列空的條件為s=0;隊列滿的條件為s=1且front=rear。循環隊列入隊與退隊的運算：假設循環隊列的初始狀態為空，即：s=0,且front=rear=m。1） 入隊運算首先將隊尾指針進一(rear=rear+1)，并當rear=m+1時，置rear=1；然后將新元素插入到隊尾指針指向的位置。當循環隊列非空(s=1)且隊尾指針等于排頭指針時，說明循環隊列已滿，不能進行入隊運算，這種情況稱為“上溢”。2）退隊運算首

12、先將排頭指針進一(front=front+1)，并當front=m+1時置front=1;然后將排頭指針指向的元素賦給指定的變量。當循環隊列為空(s=0)時，不能進行退隊運算，這種情況稱為“下溢”。第五節 線性鏈表一、線性鏈表的基本概念線性表的順序存儲結構存在以下缺點：1） 在一般情況下，要在順序存儲的線性表中插入一個新元素或刪除一個元素時，為了保證插入或刪除后的線性表仍然為順序存儲，則在插入或刪除過程中需要移動大量的數據2） 當為一個線性表分配順序存儲空間后，如果出現線性表的存儲空間已滿，但還需要插入新的元素時，就會發生“上溢”錯誤。3） 在實際應用中，往往是同時有多個線性表共享計算機的存儲

13、空間。（線性表的順序存儲結構不便于對存儲空間的動態分配。）1、線性鏈表:線性表的鏈式存儲結構稱為線性鏈表。(線性單鏈表和雙向鏈表)一個存儲結點分為兩部分：一部分用于存儲數據元素的值，稱為數據域；另一部分用于存放下一個數據元素的存儲序號(即存儲結點的地址)，即指向后件結點，稱為指針域。指針HEAD（頭指針）指向線性鏈表中第一個元素的結點；最后一個結點的指針域為NULL或0;當HEAD=NULL時稱為空表。2、帶鏈的棧3、帶鏈的隊列二、線性鏈表的基本運算1、在線性鏈表中查找指定元素2、線性鏈表的插入3、線性鏈表的刪除三、循環鏈表及其基本運算循環鏈表的特點：1） 在循環鏈表中增加了一個表頭結點，其數

14、據域為任意或根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。2） 循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈第六節 樹與二叉樹一、樹的基本概念樹是一種簡單的非線性結構。所有數據元素之間的關系具有明顯的層次特性。關于樹的特征和術語：l 在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點（根）。l 在樹結構中，每一個結點可以有多個后件，它們都稱為該結點的子結點。沒有后件的結點稱為葉子結點。l 在樹結構中，一個結點所擁有的后件個數稱為該結點的度。葉子結點的度為0。在樹中，

15、所有結點中的最大的度稱為樹的度。樹結構的層次：l 根結點在第1層l 樹的最大層次稱為樹的深度l 在樹中，以某結點的一個子結點為根構成的樹稱為該結點的一棵子樹；葉子結點沒有子樹。在計算機中，可以用樹來表示算術表達式：1） 表達式中的每一個運算符在樹中對應一個結點，稱為運算符結點。2） 運算符的每一個運算對象在樹中為該運算符結點的子樹(順序為從左到右)3） 運算對象中的單變量均為葉子結點。二、二叉樹及其基本性質1、什么是二叉樹：一種很有用的非線性結構二叉樹的特點：1）非空二叉樹只有一個根結點2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。二叉樹中，每一個結點的度最大為2，即所有子樹

16、也均為二叉樹；一個結點可以只包括左子樹或右子樹，或為葉子結點。2、二叉樹的基本性質：性質1：在二叉樹的第K層上，最多有2K-1（K>=1）個結點。性質2：深度為M的二叉樹最多有2M-1個結點。性質3：在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。性質4：具有N個結點的二叉樹，其深度至少為log2N+1，其中log2N表示取log2N的整數三、滿二叉樹與完全二叉樹1）滿二叉樹定義：除最后一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為M的滿二叉樹有2M-1個結點。2）完全二叉樹定

17、義：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。對于完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現；對于任何一個結點，若其右分支下的子孫結點的最大層次為P，則其左分支下的子孫結點的最大層次或為P，或為P+1。滿二叉樹是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹的性質：性質5：具有N個結點的完全二叉樹的深度為log2N+1。性質6：設完全二叉樹共有N個結點。如果從根結點開始，按層序用自然數1，2，N給結點進行編號，則對于編號為（K=1,2,n）的結點有以下結論：1）若K=1，則該結點為根結點，它沒有父結點；若K>1，則該結點的父結點編號為I

18、NT(K/2)2）若2K<=N，則編號為K的結點的左子結點編號為2K；否則該結點無左子結點。3）若2K+1<=N，則編號為K的結點的右子結點為2K+1；否則該結點無右子結點。三、二叉樹的存儲結構(二叉鏈表)在計算機中，二叉樹通常采用鏈式存儲結構二叉樹的存儲結點的指針域有兩個：一個用于指向該結點的左子結點的存儲地址，稱為左指針域；另一個用于指向該結點的右子結點的存儲地址，稱為右指針域。L(i)左指針域V(i)R(i)右指針域四、二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。原則：先左后右1）前序遍歷(DLR)是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然后遍歷

19、左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。（遞歸過程）2）中序遍歷(LDR)首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。（遞歸過程）3）后序遍歷(LRD)首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然選遍歷左子樹，然后遍歷右子樹，最后訪問根結點。第七節 查找技術所謂查找是指在一個給定的數據結構中查找某個指定元素。一、順序查找（順序搜索）在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較。適用

20、范圍：1）如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。二、二分法查找只適用于順序存儲的有序表。有序表是指線性表中的元素按值從小到大排列。對于長度為N的有序線性表，在最壞情況下，二分查找只需要比較log2N次，而順序查找需要比較N次。第八節 排序技術所謂排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。一、交換類排序法所謂交換類排序法是借助數據元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、冒泡排序法（下沉排序）通過相鄰數據元素的交換逐步將線性表變成有序。假

21、設線性表的長度為N，則在最壞情況下，冒泡排序需要經過N/2遍的從前往后的掃描和N/2遍的從后往前掃描，需要的比較次數為N(N-1)/2。2、快速排序法無序線性表<=TT>=T分割分割分割二、插入類排序法1、簡單插入排序法所謂插入排序，是指將無序序列中的各元素依次插入到已經有序的線性表中。在最壞情況下，簡單插入排序需要N(N-1)/2次比較。2、希爾排序法基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序。子序列的分割方法如下：將相隔某個增量H的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當H減到1時，進行一次插入排序，排序就完成增量序列一般取Ht=n/2k(k

22、=1,2,log2n)，其中n為待排序序列的長度。在最壞情況下，希爾排序所需要的比較次數為O(n1.5)。三、選擇類排序法1、簡單選擇排序法基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。對于長度為N的序列，選擇排序需要掃描N-1遍。在最壞情況下需要比較N(N-1)/2次。2、堆排序法堆的定義如下：具有N個元素的序列(h1,h2,hn)，當且僅當滿足：hi>=h2ihi<=2i 或 hi>=2i+1 hi<=2i+1(i=1,2,n/2)時稱為堆。堆頂元素（第一個元素）必為最大項。在最壞情況下，堆排序需

23、要比較的次數為O(nlog2n)。直接插入排序說明：逐個將后一個數加到前面的排好的序中。在直接插入排序過程中，對其中一個記錄的插入排序稱為一次排序；直接插入排序是從第二個記錄開始進行的，因此，長度為n的記錄序列需要進行n-1次排序才能完成整個序列的排序。時間復雜度為O(n2)。void InsertSort(elemtype x,int n)/*用直接插入法對x0-xn-1排序*/int i,j;elemtype s;for(i=0;i<n-1;i+) s=xi+1; j=i; while(j>-1&&s.key<xj.key) xj+1=xj; j-; xj

24、+1=s;希爾排序說明：希爾排序又稱縮小增量排序，增量di可以有各種不同的取法，但最后一次排序時的增量必須為1，最簡單可取di+1=di/2（取小）。時間復雜度為O(n(log2n)2)。void ShellSort(elemtype x,int n,intd,int Number)/*用希爾排序法對記錄x0-xn-1排序，d為增量值數組*/*Number為增量值個數，各組內采用直接插入法排序*/int i,j,k,m,Span;elemtype s;for(m=0;m<Number;m+) Span=dm; for(k=0;k<Span;k+) for(i=k;i<n-1;

25、i+=Span)/*這個for之后的是“組內采用直接插入法排序”*/ s=xi+Span; j=i; while(j>-1&&s.key<xj.key) xj+Span=xj; j-=Span; xj+Span=s; 直接選擇排序說明：每次將后面的最小的找出來插入前面的已排好的序中。同理，具有n個記錄的序列要做n-1次排序。時間復雜度為O(n2)。void SelectSort(elemtype x,int n)/*用直接選擇排序法對x0-xn-1排序*/int i,j,Small;elemtype Temp;for(i=0;i<n-1;i+) Small=i

26、; for(j=i+1;j<n;j+) if(xj.key<xSmall.key) Small=j; if(Small!=i) Temp=xi; xi=xSmall; xSmall=Temp; 冒泡排序說明：兩個兩個比較，將大的往后移。通過第一次冒泡排序，使得待排序的n個記錄中關鍵字最大的記錄排到了序列的最后一個位置上。然后對序列中前n-1個記錄進行第二次冒泡排序。對于n個記錄的序列，共需進行n次冒泡排序。時間復雜度為O(n2)。void BubbleSort(elemtype x,int n)/*用冒泡排序法對x0-xn-1排序*/int i,j,flag=1;elemtype Temp;for(i=1;i<n&&flag=1;i+) flag=0;