數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí).doc

一 基本概念1. 時、空復(fù)雜性（）及等級2. 數(shù)據(jù)結(jié)構(gòu)基本概念：l 數(shù)據(jù)類型、對象、操作、數(shù)據(jù)結(jié)構(gòu)l 三大類數(shù)據(jù)結(jié)構(gòu)：線性（堆棧、隊列）、樹、圖l 數(shù)據(jù)結(jié)構(gòu)的物理表示方式：數(shù)組、鏈表二 數(shù)組和結(jié)構(gòu)1. 多項式結(jié)構(gòu)：l 表示：（COEF，EXPON）數(shù)組、（START，F(xiàn)INISH）l 操作：padd2. 稀疏矩陣l 表示：（COL，ROW，VALUE）數(shù)組l 操作：TRANSPOSE，F(xiàn)ASTTRANSPOSE（記錄每行起點）3. 字符串：l 表示：數(shù)組l 操作：PATTERN MATCHING，F(xiàn)AIL函數(shù)三 堆棧和隊列1. 堆棧：l 概念：在同一端插入和刪除，F(xiàn)ILOl 表示：數(shù)組l 操作：入/出棧，空/滿判斷2. 隊列l(wèi) 概念：在一端插入而在另一端刪除，F(xiàn)IFOl 表示：數(shù)組l 操作：入/出隊列，空/滿判斷3. 應(yīng)用1-迷宮問題4. 應(yīng)用2-表達(dá)式求值，EVAL，POSTFIX四 表1. 鏈表的基本操作2. 堆棧、隊列的鏈表實現(xiàn)3. 多項式問題：鏈表的實現(xiàn)-表示，操作（PADD）4. 等價問題：鏈表5. 稀疏矩陣：多重鏈表的表示，及操作五 樹1. 樹的基本概念和二叉樹的性質(zhì)2. 二叉樹的表示：數(shù)組、鏈表方式3. 樹的基本操作：遍歷（先/中/后序），遞歸與循環(huán)4. 線索二叉樹l 原因l 操作：遍歷、插入、構(gòu)造5. 堆：l 概念l 表示：數(shù)組（完全二叉樹方式）l 操作：插入（ANY）、刪除（MIN/MAX）6. 二分查找樹l 概念l 表示：鏈表l 操作：查找、插入、刪除7. 一般樹、森林=二叉樹8. 應(yīng)用：集合問題（UNION，F(xiàn)IND）9. 二叉樹形態(tài)的計數(shù)=堆棧的輸出序列個數(shù)=矩陣的乘積方式數(shù)六 圖1. 基本概念2. 表示：矩陣、鄰接表（逆鄰接表）、鄰接多重表、十字鏈表3. 基本操作：DFS、BFS4. 其他操縱：最小生成樹、最短路徑、TOPSORT5. 應(yīng)用：雙連圖、關(guān)節(jié)點（DFS，LOW）七 排序（算法、時間復(fù)雜性）1. 基本查找方法：順序、二分法2. 插入排序：基本插入排序方法、希爾排序3. 交換排序：基本交換排序（冒泡）、快速排序（遞歸）4. 歸并排序：循環(huán)、遞歸5. 選擇排序：基本選擇排序、堆排序（基本思想：ADJUST）6. 基數(shù)排序7. 排序的穩(wěn)定性、內(nèi)排序/外排序八 HASH1. 基本思想2. HASH函數(shù)的構(gòu)造方法3. 沖突處理方法：開發(fā)地址、鏈表、再HASH4. 成功與不成功的平均查找次數(shù)九 堆結(jié)構(gòu) 不同操作下的堆結(jié)構(gòu)l INSERT，DELETE（MIN & MAX）:最大/最小堆、DEAP十 查找結(jié)構(gòu)哈夫曼（HAFFMAN）樹、查找樹的最優(yōu)化平衡方法：AVL樹、2-3樹數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指南一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點構(gòu)成數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為:概論，線性表，棧和隊列，串，多維數(shù)組和廣義表，樹和二叉樹，圖，查找，內(nèi)排，外排，文件，動態(tài)存儲分配。對于絕大多數(shù)的學(xué)校而言，“外排，文件，動態(tài)存儲分配”三章基本上是不考的，在大多數(shù)高校的計算機本科教學(xué)過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對于報考名校特別是該校又有在試卷中對這三章進(jìn)行過考核的歷史，那么這部分朋友就要留意這三章了。按照以上我們給出的章節(jié)以及對后三章的介紹，數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為:概論:內(nèi)容很少，概念簡單，分?jǐn)?shù)大多只有幾分，有的學(xué)校甚至不考。線性表:基礎(chǔ)章節(jié)，必考內(nèi)容之一?？碱}多數(shù)為基本概念題，名校考題中，鮮有大型算法設(shè)計題。如果有，也是與其它章節(jié)內(nèi)容相結(jié)合。棧和隊列:基礎(chǔ)章節(jié)，容易出基本概念題，必考內(nèi)容之一。而棧常與其它章節(jié)配合考查，也常與遞歸等概念相聯(lián)系進(jìn)行考查。串 :基礎(chǔ)章節(jié)，概念較為簡單。專門針對于此章的大型算法設(shè)計題很少，較常見的是根據(jù)KMP進(jìn)行算法分析。多維數(shù)組及廣義表 :基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見的，分?jǐn)?shù)比例波動較大，是出題的“可選單元”或“侯補單元”。一般如果要出題，多數(shù)不會作為大題出。數(shù)組常與“查找，排序”等章節(jié)結(jié)合來作為大題考查。樹和二叉樹 :重點難點章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在于，是否在本章中出一到兩道大的算法設(shè)計題。通過對多所學(xué)校的試卷分析，絕大多數(shù)學(xué)校在本章都曾有過出大型算法設(shè)計題的歷史。圖 :重點難點章節(jié)，名校尤愛考。如果作為重點來考，則多出現(xiàn)于分析與設(shè)計題型當(dāng)中，可與樹一章共同構(gòu)成算法設(shè)計大題的題型設(shè)計。查找 :重點難點章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。算法設(shè)計型題中可以數(shù)組結(jié)合來考查，也可以與樹一章結(jié)合來考查。排序 :與查找一章類似，本章同屬于重點難點章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序算法的優(yōu)劣比較此類的題。算法設(shè)計大題中，如果作為出題，那么常與數(shù)組結(jié)合來考查。二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點勾劃:第零章 概述本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。大家主要注意以下幾點:數(shù)據(jù)結(jié)構(gòu)的基本概念，時間和空間復(fù)雜度的概念及度量方法，算法設(shè)計時的注意事項。本章考點不多，只要稍加注意理解即可。第一章 線性表作為線性結(jié)構(gòu)的開篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯Φ母拍?，鏈?zhǔn)酱鎯Ω拍顚⑹钦麄€數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無論哪一章都涉及到了這個概念?？傮w來說，線性表一章可供考查的重要考點有以下幾個方面:1.線性表的相關(guān)基本概念，如:前驅(qū)、后繼、表長、空表、首元結(jié)點，頭結(jié)點，頭指針等概念。2.線性表的結(jié)構(gòu)特點，主要是指:除第一及最后一個元素外，每個結(jié)點都只有一個前趨和只有一個后繼。3.線性表的順序存儲方式及其在具體語言環(huán)境下的兩種不同實現(xiàn):表空間的靜態(tài)分配和動態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。4.線性表的鏈?zhǔn)酱鎯Ψ绞郊耙韵聨追N常用鏈表的特點和運算:單鏈表、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。此外，近年來在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實現(xiàn)單鏈表輸出(可能是順序也可能是倒序)的問題。在鏈表的小題型中，經(jīng)常考到一些諸如:判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。5.線性表的順序存儲及鏈?zhǔn)酱鎯η闆r下，其不同的優(yōu)缺點比較，即其各自適用的場合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲結(jié)構(gòu)的各自好處。第二章 棧與隊列棧與隊列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。所以，理解棧與隊列，是走向DS高手的一條必由之路，。學(xué)習(xí)此章前，你可以問一下自己是不是已經(jīng)知道了以下幾點:1.棧、隊列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括:順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等。棧與隊列存取數(shù)據(jù)(請注意包括:存和取兩部分)的特點。2.遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法:n!階乘問題，fib數(shù)列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。3.棧的應(yīng)用:數(shù)值表達(dá)式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計題不多。4.循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊算法。如果你已經(jīng)對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。第三章 串經(jīng)歷了棧一章的痛苦煎熬后，終于迎來了串一章的柳暗花明。串，在概念上是比較少的一個章節(jié)，也是最容易自學(xué)的章節(jié)之一，但正如每個過來人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過去又是一馬平川的大好DS山河了，呵呵。串一章需要攻破的主要堡壘有:1.串的基本概念，串與線性表的關(guān)系(串是其元素均為字符型數(shù)據(jù)的特殊線性表)，空串與空格串的區(qū)別，串相等的條件2.串的基本操作，以及這些基本函數(shù)的使用，包括:取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點。3.順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實現(xiàn)方式。4.KMP算法思想。KMP中next數(shù)組以及nextval數(shù)組的求法。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)之外。其中，理解算法是核心，會求數(shù)組是得分點。不用我多說，這一節(jié)內(nèi)容是本章的重中之重?？赡苓M(jìn)行的考查方式是:求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運用KMP算法進(jìn)行匹配的匹配過程。第四章 數(shù)組與廣義表學(xué)過程序語言的朋友，數(shù)組的概念我們已經(jīng)不是第一次見到了，應(yīng)該已經(jīng)“一回生，二回熟”了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學(xué)里的程序語言所關(guān)注的不太一樣，下面會作介紹。廣義表的概念，是數(shù)據(jù)結(jié)構(gòu)里第一次出現(xiàn)的。它是線性表或表元素的有限序列，構(gòu)成該結(jié)構(gòu)的每個子表或元素也是線性結(jié)構(gòu)的，所以，這一章也歸入線性結(jié)構(gòu)中。本章的考查重點有:1.多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。2.明確按行存儲和按列存儲的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類型的題。3.將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括:對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式:三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。4.廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點，是理解整個廣義表一節(jié)算法的基礎(chǔ)。近來，在一些學(xué)校中，出現(xiàn)了這樣一種題目類型:給出對某個廣義表L若干個求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。5.與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如:求表深度，復(fù)制廣義表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運用兩種不同的方式解答:一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進(jìn)行操作;二是把一個廣義表看作是若干個子表，分別對每個子表進(jìn)行操作。第五章 樹與二叉樹從對線性結(jié)構(gòu)的研究過度到對樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業(yè)課總分。所以，樹這一章的重要性，已經(jīng)不說自明了?？傮w來說，樹一章的知識點包括:二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)，二叉樹遍歷的三種算法(遞歸與非遞歸)，在三種基本遍歷算法的基礎(chǔ)上實現(xiàn)二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構(gòu)成和應(yīng)用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，樹與森林和二叉樹的轉(zhuǎn)換。下面我們來看考試中對以上知識的主要考查方法:1.二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)考查方法可有:直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區(qū)別;考查滿二叉樹和完全二叉樹的性質(zhì)，普通二叉樹的五個性質(zhì):第i層的最多結(jié)點數(shù)，深度為k的二叉樹的最多結(jié)點數(shù)，n0=n2+1的性質(zhì)，n個結(jié)點的完全二叉樹的深度，順序存儲二叉樹時孩子結(jié)點與父結(jié)點之間的換算關(guān)系(左為:2*i，右為:2*i+1)。二叉樹的順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法。2.二叉樹的三種遍歷算法這一知識點掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進(jìn)而關(guān)系到樹一章的算法設(shè)計題能否順利完成。二叉樹的遍歷算法有三種:先序，中序和后序。其劃分的依據(jù)是視其每個算法中對根結(jié)點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來(比如:求葉子個數(shù))，所以，掌握了三種遍歷的非遞歸算法后，對付諸如:“利用非遞歸算法求二叉樹葉子個數(shù)”這樣的題目就下筆如有神了。我會在另一篇系列文章(/ibbs.dll?b . 3&bp=2&bt=0)里給出三種遍歷的遞歸和非遞歸算法的背記版，到時請大家一定熟記。3.可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹算法:求葉子個數(shù)，求二叉樹結(jié)點總數(shù)，求度為1或度為2的結(jié)點總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結(jié)點，刪除值為n的某個指定結(jié)點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。4.線索二叉樹:線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。對于線索二叉樹，應(yīng)該掌握:線索化的實質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如:查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點就是一類常考題)。5.最優(yōu)二叉樹(哈夫曼樹):最優(yōu)二叉樹是為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送分題。6.樹與森林:二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個最重要的特殊之處是在于:二叉樹是有序的!即:二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認(rèn)為是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法:先根與后根(對于森林而言稱作:先序與后序遍歷)。在難度比較大的考試中，也有基于此二種算法的基礎(chǔ)上再進(jìn)行擴展要求你利用這兩種算法設(shè)計其它算法的，但一般院校很少有這種考法，最多只是要求你根據(jù)先根或后根寫出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的:先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。這一點成為很多學(xué)校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然后回答這個問題。二叉樹、樹與森林之所以能有以上的對應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟(稱孩子兄弟鏈表)，而森林也是利用二叉鏈表存儲孩子及兄弟。樹一章，處處是重點，道道是考題，大家務(wù)必個個過關(guān)。第六章 圖如果說，從線性結(jié)構(gòu)向樹形結(jié)構(gòu)研究的轉(zhuǎn)變，是數(shù)據(jù)結(jié)構(gòu)學(xué)科對數(shù)據(jù)組織形式研究的一次升華，那么從樹形結(jié)構(gòu)的研究轉(zhuǎn)到圖形結(jié)構(gòu)的研究，則進(jìn)一步讓我們看到了數(shù)據(jù)結(jié)構(gòu)對于解決實際問題的重大推動作用。圖這一章的特點是:概念繁多，與離散數(shù)學(xué)中圖的概念聯(lián)系緊密，算法復(fù)雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。下面我們看一下圖這一章的主要考點以及這些考點的考查方式:1.考查有關(guān)圖的基本概念問題:這些概念是進(jìn)行圖一章學(xué)習(xí)的基礎(chǔ)，這一章的概念包括:圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，(強)連通圖，(強)連通分量等概念。與這些概念相聯(lián)系的相關(guān)計算題也應(yīng)該掌握。2.考查圖的幾種存儲形式:圖的存儲形式包括:鄰接矩陣，(逆)鄰接表，十字鏈表及鄰接多重表。在考查時，有的學(xué)校是給出一種存儲形式，要求考生用算法或手寫出與給定的結(jié)構(gòu)相對應(yīng)的該圖的另一種存儲形式。3.考查圖的兩種遍歷算法:深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設(shè)計題常常是基于這兩種基本的遍歷算法而設(shè)計的，比如:“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。4.生成樹、最小生成樹的概念以及最小生成樹的構(gòu)造 RIM算法和KRUSKAL算法?？疾闀r，一般不要求寫出算法源碼，而是要求根據(jù)這兩種最小生成樹的算法思想寫出其構(gòu)造過程及最終生成的最小生成樹。5.拓?fù)渑判騿栴}:拓?fù)渑判蛴袃煞N方法，一是無前趨的頂點優(yōu)先算法，二是無后繼的頂點優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當(dāng)然，后一種排序出來的結(jié)果是“逆拓?fù)溆行颉钡摹?.關(guān)鍵路徑問題:這個問題是圖一章的難點問題。理解關(guān)鍵路徑的關(guān)鍵有三個方面:一是何謂關(guān)鍵路徑，二是最早時間是什么意思、如何求，三是最晚時間是什么意思、如何求。簡單地說，最早時間是通過“從前向后”的方法求的，而最晚時間是通過“從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經(jīng)求出來之后才能進(jìn)行。這個問題拿來直接考算法源碼的不多，一般是要求按照書上的算法描述求解的過程和步驟。在實際設(shè)計關(guān)鍵路徑的算法時，還應(yīng)該注意以下這一點:采用鄰接表的存儲結(jié)構(gòu)，求最早時間和最晚時間要采用不同的處理方法，即:在算法初始時，應(yīng)該首先將所有頂點的最早時間全部置為0。關(guān)鍵路徑問題是工程進(jìn)度控制的重要方法，具有很強的實用性。7.最短路徑問題:與關(guān)鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關(guān)鍵是算法的理解。最短路徑問題分為兩種:一是求從某一點出發(fā)到其余各點的最短路徑;二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應(yīng)該就是旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法。注意區(qū)分。第七章 查找在不少數(shù)據(jù)結(jié)構(gòu)的教材中，是把查找與排序放入高級數(shù)據(jù)結(jié)構(gòu)中的。應(yīng)該說，查找和排序兩章是前面我們所學(xué)的知識的綜合運用，用到了樹、也用到了鏈表等知識，對這些數(shù)據(jù)結(jié)構(gòu)某一方面的運用就構(gòu)成了查找和排序?，F(xiàn)實生活中，search幾乎無處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時代，萬事離不開search，小到文檔內(nèi)文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大部分時間。在復(fù)習(xí)這一章的知識時，你需要先弄清楚以下幾個概念:關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義;靜態(tài)查找與動態(tài)查找的含義及區(qū)別;平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結(jié)果，特別是一些典型結(jié)構(gòu)的ASL值，應(yīng)該記住。在DS的教材中，一般將search分為三類:1st，在順序表上的查找;2nd，在樹表上的查找;3rd，在哈希表上的查找。下面詳細(xì)介紹其考查知識點及考查方式:1.線性表上的查找:主要分為三種線性結(jié)構(gòu):順序表，有序順序表，索引順序表。對于第一種，我們采用傳統(tǒng)查找方法，逐個比較。對于及有序順序表我們采用二分查找法。對于第三種索引結(jié)構(gòu)，我們采用索引查找算法?？忌枰⒁膺@三種表下的ASL值以及三種算法的實現(xiàn)。其中，二分查找還要特別注意適用條件以及其遞歸實現(xiàn)方法。2.樹表上的查找:這是本章的重點和難點。由于這一節(jié)介紹的內(nèi)容是使用樹表進(jìn)行的查找，所以很容易與樹一間的某些概念相混淆。本節(jié)內(nèi)容與樹一章的內(nèi)容有聯(lián)系，但也有很多不同，應(yīng)注意規(guī)納。樹表主要分為以下幾種:二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結(jié)構(gòu)為重，也有部分名校偏愛考B樹的。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯(lián)系就更為緊密，二叉樹一章學(xué)好了，這里也就不難了。二叉排序樹，簡言之，就是“左小右大”，它的中序遍歷結(jié)果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質(zhì)也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定:深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個?？键c，但該知識點歸根結(jié)底還是關(guān)注的平衡二叉樹的四種調(diào)整算法，所以應(yīng)該掌握平衡二叉樹的四種調(diào)整算法，調(diào)整的一個參照是:調(diào)整前后的中序遍歷結(jié)果相同。B樹是二叉排序樹的進(jìn)一步改進(jìn)，也可以把B樹理解為三叉、四叉.排序樹。除B樹的查找算法外，應(yīng)該特別注意一下B樹的插入和刪除算法。因為這兩種算法涉及到B樹結(jié)點的分裂和合并，是一個難點。B樹是報考名校的同學(xué)應(yīng)該關(guān)注的焦點之一。鍵樹也稱字符樹，特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過程。3.基本哈希表的查找算法:哈希一詞，是外來詞，譯自“hash”一詞，意為:散列或雜湊的意思。哈希表查找的基本思想是:根據(jù)當(dāng)前待查找數(shù)據(jù)的特征，以記錄關(guān)鍵字為自變量，設(shè)計一個function，該函數(shù)對關(guān)鍵字進(jìn)行轉(zhuǎn)換后，其解釋結(jié)果為待查的地址?；诠１淼目疾辄c有:哈希函數(shù)的設(shè)計，沖突解決方法的選擇及沖突處理過程的描述。第八章 內(nèi)部排序內(nèi)排是DS課程中最后一個重要的章節(jié)，建立在此章之上的考題可以有多種類型:填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點，就是考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標(biāo)(時間復(fù)雜度)能否了如指掌。這一章，我們對重點的規(guī)納將跟以上各章不同。我們將從以下幾個側(cè)面來對排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。從排序算法的種類來分，本章主要闡述了以下幾種排序方法:插入、選擇、交換、歸并、計數(shù)等五種排序方法。其中，在插入排序中又可分為:直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷耄徽Z以敝之:用中間數(shù)將待排數(shù)據(jù)組一分為二。快速排序，在處理的“問題規(guī)?！边@個概念上，與希爾有點相反，快速排序，是先處理一個較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。選擇排序，相對于前面幾種排序算法來說，難度大一點。具體來說，它可以分為:簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據(jù)什么規(guī)則選取最小的數(shù)。簡單選擇，是通過簡單的數(shù)組遍歷方案確定最小數(shù);樹選擇，是通過“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大(小)者，最終選出最小(大)數(shù);而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點。樹選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請大家注意。歸并排序，故名思義，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心:歸并排序是穩(wěn)定排序?；鶖?shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場合，比如撲克牌排序問題等?；鶖?shù)排序，又分為兩種:多關(guān)鍵字的排序(撲克牌排序)，鏈?zhǔn)脚判?整數(shù)排序)。基數(shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個有序序列。本章各種排序算法的思想以及偽代碼實現(xiàn)，及其時間復(fù)雜度都是必須掌握的，學(xué)習(xí)時要多注意規(guī)納、總結(jié)、對比。此外，對于教材中的10.7節(jié)，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點一、有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)是所有能輸入到計算機中并被計算機程序處理的符號總稱；數(shù)據(jù)元素(或記錄)是數(shù)據(jù)的基本單位；數(shù)據(jù)項是組成數(shù)據(jù)的不可分割的最小單位；一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)類型是一個“值”的集合和定義在此集合上的“一組操作”的總稱。 二、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型(ADT)定義的內(nèi)容與意義、四類基本結(jié)構(gòu)的名稱及其邏輯關(guān)系特點數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)容：數(shù)據(jù)對象及其關(guān)系。抽象數(shù)據(jù)類型(ADT)格式定義包括三個部分的內(nèi)容：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作。四類基本結(jié)構(gòu)的邏輯關(guān)系特點：集合：數(shù)據(jù)元素之間除同屬一個集合外,不存在其它關(guān)系；線性結(jié)構(gòu)：一對一；樹形結(jié)構(gòu)：一對多；圖狀結(jié)構(gòu)：多對多。 三、算法及其時間復(fù)雜度：算法的重要特性：有窮性、確定性、可行性、輸入、輸出。一個正確的算法必須有輸出。算法分析（效率）的2個主要內(nèi)容：時間復(fù)雜度(算法執(zhí)行時間與問題規(guī)模之間的關(guān)系)、空間復(fù)雜度(算法所需存儲空間的量度)。 算法分析的目的是 ：分析算法的有效性以求改進(jìn) 。 程序段for (i=1;i=n;+i) k+;的時間復(fù)雜度：O(n)，線性階。程序段for (j=1,j=n,+j) for (i=1; inext=NULL(nil)；不帶頭結(jié)點的單鏈表L為空的條件是L=NULL(nil)。在單鏈表L中，已知q指向其中一個非終端結(jié)點，刪除q的直接后繼結(jié)點的操作是: q-next= q-next -next； 或p=q-next;q-next=p-next；設(shè)某雙鏈表的結(jié)點形式為prior、data、next，若要在指針q所指結(jié)點（假設(shè)是中間結(jié)點）的后面插入一個新結(jié)點s，則需執(zhí)行下述語句段：s-prior=q； s-next=q-next；q-next-prior=s ；q-next=s；七、棧和隊列的基本概念和操作棧(Stack)、棧頂(S.top)、棧底（S.base）。入棧(Push(S,e)、出棧(Pop(S,e)?？諚?S.top=S.base)。隊列(Queue)、隊頭(Q.front)、隊尾(Q.rear)。入隊(EnQueue(Q,e)、出隊(DeQueue(Q,e)。空隊列：循環(huán)隊列：(Q.rear+1)%M=Q.front 鏈隊列: (Q.front=Q.rear) 七、棧和隊列的部分類型題棧和隊列的異同：共同點是：都是操作受限的線性表，只能在端點插入和刪除數(shù)據(jù)元素。不同的是：棧的插入和刪除是在同一端，而隊列是插入在一端，刪除在另外一端。棧操作的特點是數(shù)據(jù)元素只能從棧頂插入、刪除，先進(jìn)后出(FILO)。隊列操作的特點是數(shù)據(jù)元素只能從隊頭刪除、隊尾插入，先進(jìn)先出(FIFO)。存儲空間長度為M的循環(huán)隊列sq滿隊列的條件是：(sq-rear+1)%M = = sq-front 。 若輸入序列為1 2 3 4 5,借助一個棧不可能得到的輸出序列有1 2 5 4 3、4 2 5 3 1、4 3 5 1 2等等。若輸入序列為1234,借助一個棧可能得到的輸出序列有：1234，2431，3421，4321，1243，2134，3241，1342，2143，3214，1324，2341， 1432，2314。設(shè)數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為：front=(front+1)%m 。 八、串的基本概念及類型題串是有限個字符的序列；它一種特殊的線性表,其特殊性表現(xiàn)在每個數(shù)據(jù)元素都是1個字符。 兩個串相等的充分必要條件：兩個串的長度相等且各個對應(yīng)位置的字符都相等。串的基本操作：求子串substr()、定位index()、求串的長度strlen()等。兩個串p, q，求q在p中首次出現(xiàn)的位置的運算稱作模式匹配 。 九、二維數(shù)組和廣義表一維數(shù)組的元素起始地址loc6=1000，元素長度為4，則： loc8=1000+(8-6)*4=1008 常對數(shù)組進(jìn)行的兩種基本操作是：查找和修改 設(shè)n階方陣A是一對稱矩陣，為節(jié)省存儲空間，將其下三角（包括對角線）以行序為主序存儲在一維數(shù)組B1.n(n+1)/2中，則對任一上三角元素aij(i1),左孩子是結(jié)點2i(2in),右孩子是結(jié)點2i+1(2i+1n)。設(shè)在樹中，結(jié)點x是結(jié)點y的父親時，用(x,y)來表示樹邊。已知一棵樹邊的集合為：(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用樹形表示法畫出此樹，并指出葉子節(jié)點、根節(jié)點、子孫、祖先等。 注意：這是無序樹 樹的深度：5 以c為根的子樹的深度：3 節(jié)點e的子孫有：i m n 節(jié)點k的層次：4 樹的度數(shù)：3二叉樹的基本組成部分是：根（N）、左子樹（L）、右子樹（R），因而二叉樹的遍歷有6種。最常用的3種遍歷方法是：前序按NLR次序，后序按LNR次序，中序按LRN次序。 遍歷二叉樹的常用方案：深度優(yōu)先遍歷(先序(前序或先根),中序,后序)；廣度優(yōu)先遍歷(層次遍歷)。先序遍歷森林(對應(yīng)二叉樹先序遍歷 )中序遍歷森林(對應(yīng)二叉樹中序遍歷) 中綴表達(dá)式3*X+(Y6-0.3)所對應(yīng)的后綴表達(dá)式為：3X*Y6/0.3-+。中綴表達(dá)式一棵深度為k二叉樹最多有2k-1個結(jié)點；第k層上最多有個結(jié)2k-1點。對有25個結(jié)點的完全二叉樹按層編號，則編號為8的結(jié)點的左、右孩子編號分別為：16和17。 度等于0的結(jié)點稱為葉子結(jié)點。 二叉樹具有的五種基本形態(tài) 用孩子兄弟鏈表表示一棵樹，若要找到結(jié)點x的第5個孩子，只要先找到x的第一個孩子，然后從兄弟域指針連續(xù)掃描4個結(jié)點即可找到。 已知二叉樹的前序遍歷順序(或后序遍歷順序)和中序遍歷順序，則可以唯一確定一棵二叉樹。某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac,則它的前序遍歷序列是 ：cedba 設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，則B中右指針域為空的結(jié)點有n+1個。哈夫曼樹是訪問葉結(jié)點的外部路徑長(帶權(quán)路徑長度)最短的二叉樹。 外部路徑長度E定義為從擴充二叉樹的根到每個外部結(jié)點的路徑長度之和。一棵有100個結(jié)點的完全二叉樹根結(jié)點編號為1，則編號為45的結(jié)點的左孩子的編號是90；編號為49的結(jié)點在第6層；它的右孩子的編號是99。二叉樹的先序遍歷中第一個被訪問的結(jié)點和后序遍歷中最后訪問的結(jié)點是：根結(jié)點十三、圖的存儲方式與遍歷 圖的存儲方式：鄰接矩陣和鄰接表。在圖結(jié)構(gòu)中，如果一個從Vp到Vq的路徑上除Vp和Vq可以相同外，其它結(jié)點都不相同，則稱此路徑為簡單路徑，若Vp和Vq相同則稱為回路。 在一個具有n個頂點的無向連通圖中，至少包含n-1條邊，若是完全無向圖則包含n(n-1)/2條邊，在一個具有n個頂點的有向完全圖中，包含n(n-1)條邊 。鄰接表是圖的一種鏈?zhǔn)酱鎯?。對于采用鄰接表存儲的圖，其廣度優(yōu)先遍歷類似二叉樹層次遍歷，其深度優(yōu)先遍歷類似二叉樹先序遍歷。 一個無向連通圖的生成樹是含有該連通圖的全部頂點的極小連通子圖。 遍歷圖(包括無向圖和有向圖)的基本方法有：深度優(yōu)先搜索和廣度優(yōu)先搜索兩種；圖的深度優(yōu)先搜索是一個遞歸過程 。 圖G1的鄰接表十四、查找表、順序查找、折半查找、哈希表查找表、關(guān)鍵字、查找成功、平均查找長度、二叉排序樹(二叉查找樹)、平衡二叉樹、哈希表、沖突的概念。 靜態(tài)查找表：對數(shù)據(jù)元素只作查找操作的查找表為靜態(tài)查找表,典型代表結(jié)構(gòu)如赫夫曼樹。動態(tài)查找表：在查找過程中可同時插入、修改或刪除數(shù)據(jù)的查找表為動態(tài)查找表,典型代表結(jié)構(gòu)如二叉排序樹。二叉排序樹的定義的要點：任一結(jié)點的值大于其左子樹各結(jié)點值且小于其右子樹各結(jié)點值。 查找算法中哨兵的作用：避免查找過程中每步都檢測表是否查找完畢,從而減少查找時間。在順序查找算法，若在表頭設(shè)置監(jiān)視哨，則正確的查找方式為：從第n個元素開始往前查找。若在表尾設(shè)置監(jiān)視哨，則應(yīng)從第1個元素開始往后查找。哈希表與其他結(jié)構(gòu)的表的本質(zhì)差別：記錄的存儲位置和記錄的關(guān)鍵字之間有無確定的對應(yīng)關(guān)系。哈希表的平均查找長度與元素個數(shù)n無關(guān)；而其他結(jié)構(gòu)的表平均查找長度與元素個數(shù)n密切相關(guān)。 十五、內(nèi)部排序 排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。排序算法的時間復(fù)雜度和空間復(fù)雜度。簡單排序(直接插入、冒泡和簡單選擇排序)的算法都是穩(wěn)定的。時間復(fù)雜度都是O(n2)，需要時間較長；空間復(fù)雜度都是O(1)。在Shell排序、快速排序、堆排序和2-路歸并排序等先進(jìn)的排序中，一般情況下是快速排序所需要的時間最短；但在初始數(shù)據(jù)有序時，花費的時間最多的也是快速排序。 一組記錄的關(guān)鍵字的初始數(shù)據(jù)是：25，48，16，35，79，82，23，40，36，72；在此基礎(chǔ)上進(jìn)行一趟Shell排序后的結(jié)果為(設(shè)dk=n/2=5)：25，23，16，35，72，82，48，40，36，79一組記錄的關(guān)鍵字經(jīng)一趟二路歸并排序后得到含有5個長度為2的有序表如下：25，48，16，35，79，82，23，40，36，72，在此基礎(chǔ)上按二路歸并排序方法再對該序列進(jìn)行一趟歸并后的結(jié)果為：16，25，35，48，23，40，78，82，36，72。 文 件 文件：文件是存儲在外部介質(zhì)上的由大量性質(zhì)相同的記錄組成的集合。按其記錄的類型不同可以分為兩類：程序文件和數(shù)據(jù)文件。 程序文件是一維的、連續(xù)的、無結(jié)構(gòu)的字符序列，可以看成是由一條無結(jié)構(gòu)的記錄組成的文件。 數(shù)據(jù)文件是帶有結(jié)構(gòu)的、性質(zhì)相同的記錄的集合。每個記錄由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是最基本的不可分割的數(shù)據(jù)單位，也是文件中可以操作的最小數(shù)據(jù)單位。主要介紹的就是數(shù)據(jù)文件的組織結(jié)構(gòu)。 關(guān)鍵字：能夠標(biāo)識文件中記錄的數(shù)據(jù)項稱為關(guān)鍵字，能夠唯一標(biāo)識記錄的關(guān)鍵字稱為主關(guān)鍵字，否則為次關(guān)鍵字。 記錄的邏輯結(jié)構(gòu)：是指文件的記錄在用戶或應(yīng)用程序員面前逞現(xiàn)的方式，是對數(shù)據(jù)間的客觀聯(lián)系的一種表示，是用戶對數(shù)據(jù)的存取方式 。 記錄的物理結(jié)構(gòu)：是指文件中的記錄在物理存儲介質(zhì)上的存儲方式，是數(shù)據(jù)的物理表示和組織。根據(jù)不同的需要、設(shè)備本身的特性及操作系統(tǒng)中的文件系統(tǒng)，記錄的物理結(jié)構(gòu)可以有不同的表示和組織方法 。 文件的組織 文件在存儲介質(zhì)（如磁盤或磁帶）上的組織方式稱為物理結(jié)構(gòu)。常用的文件組織方式有三種基本形式：順序組織、隨機組織和鏈組織。 順序文件的記錄是按其在文件中的邏輯順序依次存入存儲介質(zhì)的。它是一種順序組織方式。順序文件中記錄的物理次序與邏輯次序是一致的。散列文件類似于哈希表，即根據(jù)文件中的關(guān)鍵字特點設(shè)計一種哈希函數(shù)（也叫作散列函數(shù)）和處理沖突的方法來確定記錄的存儲位置，將記錄散列在存儲介質(zhì)上，這樣的文件被稱作散列文件。散列文件是一種隨機組織方式 。索引文件是指除了文件本身（數(shù)據(jù)區(qū)）之外，還要為文件建立一個索引表，索引表的每一項是由一個關(guān)鍵字值和一個指針（即存儲位置）構(gòu)成的二元組（k，p），k是對應(yīng)記錄的關(guān)鍵字值，p是該記錄的外存地址 。索引順序文件是索引文件的數(shù)據(jù)區(qū)的記錄按關(guān)鍵字排列有序，對一組記錄建立一個索引項，這種索引叫稀疏索引，此時k是一組記錄上關(guān)鍵字值最小的或最大記錄的關(guān)鍵字值。所以可以進(jìn)行預(yù)查找(相當(dāng)于分塊查找)。索引非順序文件是索引文件的數(shù)據(jù)區(qū)的記錄不是按關(guān)鍵字排列有序，每個索引項都對應(yīng)文件的一個邏輯記錄，這種索引叫稠密索引。不可以進(jìn)行預(yù)查找。數(shù)據(jù)結(jié)構(gòu)算法背誦一、線性表 1.逆轉(zhuǎn)順序表中的所有元素算法思想：第一個元素和最后一個元素對調(diào)，第二個元素和倒數(shù)第二個元素對調(diào)，依此類推。 void Reverse(int A, int n) int i, t;for (i=0; i next;while (p != NULL) if (p-data = item) q-next = p-next;free(p);p = q-next; else q = p;p = p-next;if (list-data = item) q = list;list = list-next;free(q); 3.逆轉(zhuǎn)線性鏈表 void Reverse(LinkList &list) LinkList p, q, r; p = list;q = NULL;while (p != NULL) r = q;q = p;p = p-next;q-next = r;list = q; 4.復(fù)制線性鏈表（遞歸） LinkList Copy(LinkList lista) LinkList listb; if (lista = NULL)return NULL;else listb = (LinkList)malloc(sizeof(LNode);listb-dat