1、生活需要游戲，但不能游戲人生；生活需要歌舞，但不需醉生夢死；生活需要藝術，但不能投機取巧；生活需要勇氣，但不能魯莽蠻干；生活需要重復，但不能重蹈覆轍。 -無名考研數(shù)據(jù)結(jié)構(gòu)學習筆記第一章緒論一、基本問題問答：1、什么叫數(shù)據(jù)結(jié)構(gòu)？如何理解“數(shù)據(jù)結(jié)構(gòu)”？如何樹立數(shù)據(jù)結(jié)構(gòu)的學習體系？廣義上的數(shù)據(jù)結(jié)構(gòu)指的是：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。狹義上的數(shù)據(jù)結(jié)構(gòu)專指邏輯結(jié)構(gòu)，就是元素間的邏輯關系，主要類型有：集合型，線性結(jié)構(gòu)，樹型，圖型！整個數(shù)據(jù)結(jié)構(gòu)的課程就是圍繞著以上幾種數(shù)據(jù)類型展開的，加上基于這些結(jié)構(gòu)的基本操作：插入，刪除，查找，取元素，取長度等等。另外，還有基于這些數(shù)據(jù)結(jié)構(gòu)的較為復雜的算法：查找和排序。在嚴老師和其

2、他很多的數(shù)據(jù)結(jié)構(gòu)教材中都把查找和排序作為了一個獨立的部分，這一部分實際上主要在探討算法，而不在是結(jié)構(gòu)本身了。算法的概念將在后面提到。2、數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)，當計算機程序運行時，程序就按照定義給這些數(shù)據(jù)分配了空間。而數(shù)據(jù)定義，是在定義其邏輯結(jié)構(gòu)。以鏈表為列，在實際定義時，一個個的結(jié)點，由于其指針域可以指向另一個結(jié)點，那么依靠這種指向關系，就可在邏輯上建立起一條鏈狀結(jié)構(gòu)！但是，在實際的程序執(zhí)行時，是不會有這樣的一條鏈的，而是通過在一個結(jié)點空間的某個空間內(nèi)填入了下一個結(jié)點的地址！這樣的每個有數(shù)據(jù)和地址的結(jié)點，才是其物理結(jié)構(gòu)。3、算法的概念、分析，算法時間復雜度的含義及分析算法就是解

3、決問題的方法或策略。一個算法好與壞的評價標準是：正確，可讀，健壯，效率高，空間省！設計算法時，應該按照嚴教材上關于類C（或類P）語言的描述來作，格式為：status fun_name/算法說明for . ;/典型功能及復雜語句后加注釋/fun_name注意寫好注釋！不求多，但求精！時間復雜度：分析算法效率的重要工具。主要是靠推算語句執(zhí)行次頻度而得來的。時間復雜度考查的是“某數(shù)量級”的概念，即：T（n）=O（f（n）中，存在正的常數(shù)C和n0，使得當n=n0時，0=T(N)=C*F(N)當空間復雜度為O(1)時，稱算法為就地工作（原地工作）。算法時間復雜度的分析：時間復雜度的分析說到底是分析當系統(tǒng)

4、規(guī)模增大時，系統(tǒng)所耗費時間的數(shù)量級。數(shù)量級的定義見上。簡而言之，2n2，6n2，n2是同一數(shù)量級，因為由n2可推出其它兩個（常數(shù)相乘）。此外，當時間復雜度的公式中出現(xiàn)n的多項式時，應該以高階為準。因為此時影響總體變化規(guī)律的是高階項的值。在分析時間復雜度時，應該以程序或算法中執(zhí)行次數(shù)最多的語句為準，通常情況下是最內(nèi)層循環(huán)的時間復雜茺，最內(nèi)層語句的執(zhí)行次數(shù)計算出來后，取最高的次數(shù)，然后去掉該項中的常數(shù)因子即可?？臻g復雜度的度量主要是看當系統(tǒng)規(guī)模n增大時，系統(tǒng)所占用的額外空間是否也在增大，按怎么的規(guī)律增大。如果沒有增大，即額外空間始終是個常數(shù)，算法就是原地工作！4、算法設計規(guī)范1在算法設計中，第一個

5、牽涉到的概念是：算法說明。它是寫在過程或函數(shù)首部以下的注釋內(nèi)容。雖是注釋內(nèi)容，卻是必不可少的。在測試中也占有相當大的作用。此說明主要包括：算法的功能，參數(shù)表中各參數(shù)的含義及輸入輸出定義；算法中引用了哪些全局變量或外部定義的變量，它們的作用，入口初值，以及應該滿足哪些限制條件。如：鏈表是否帶頭結(jié)點，表中元素是否有序，如果有序是遞增還是遞減等等！必要時，算法說明還可用來陳述算法思想，采用的存儲結(jié)構(gòu)等。遞歸算法的說明特別重要，讀者應該力求將它寫為算法的嚴格定義。幾個例子：2.29procedure DifferenceSqlist(VAR a;Sqlist;b,c:Sqlist);刪去增序順序表中那

6、些既在增序順序表中B出現(xiàn)又在增序順序表C中出現(xiàn)的元素2.33procedure Sqlistlinkedlist(VAR lc,ld,loinkedList;llinkedList);將線性表ll分割為3個循環(huán)鏈表lc,ld和lo,其中每個循環(huán)鏈表只含一類字符，分別為A.Z、0.9和其它字符。2注釋與斷言在難懂的語句和關鍵的語句（段）之后加以注釋可以大大提高程序的可讀性。注釋要恰當，并非越多越好；此外，注釋句的抽象程度應略高于語句（段）。斷言是注釋的一種特殊寫法，它是一個邏輯謂詞，陳述算法執(zhí)行到此點時應滿足的條件，即這種形式：當、時，、。最重要的就是算法的入口斷言與else分支斷言。如果算法不

7、含有參數(shù)僉性檢測的代碼段，書寫入口斷言是最低限度的要求。3輸入、輸出三種方式：a、通過專門的輸入/出語句：read，write，scanf，printf等b、通過參數(shù)表中的參數(shù)傳遞c、通過全局及外部變量4錯誤處理三種處理方式：a、error語句實現(xiàn)b、通過函數(shù)返回錯誤代碼或錯誤狀態(tài)值c、exit語句實現(xiàn)提倡使用第二種方式來實現(xiàn)錯誤處理5語句的使用與算法結(jié)構(gòu)避免使用goto語句，算法結(jié)構(gòu)結(jié)構(gòu)應該同層次對齊，下一層向上一層縮進兩格，并以適當?shù)姆枠俗R語句段的開始與結(jié)束：， 6基本運算未明確要求的，不得直接用教科書上的基本運算非用不可的，要將這些基本運算的代碼全部寫出7幾點建議a、建議以圖說明算法b

8、、建議在算法書寫完畢后，用邊界條件的值驗證一下算法能否正確執(zhí)行5、類P與類C大比拼許多朋友問我類P與類C有啥區(qū)別，哪個更好？考試的時候用哪個語言？其實，這些都是一些很基礎的問題，不客氣地說這是考研門外漢的問題。類P較類C的教材版本出得早，在后期的類C版數(shù)據(jù)中省去了類P中的一些內(nèi)容，比如：棧一章的遞歸到非遞歸的轉(zhuǎn)化等。但并不能因此就說類C版要差，事實上，類C的更符合當前考試和應用的發(fā)展趨勢，從整體認同度而言，個人建議還是用類C好一點，原因：一，C語言本身很靈活，程序簡潔，是真正的程序員用的語言，更是一個計算機研究生必須掌握的；二，C語言本身在實際項目的應用中是一種通用語言，軟件公司絕大多數(shù)是要精

9、通VC的，學好C的DS其意義更深遠一些。另外，考慮到考上后絕大多數(shù)研友都會被導師拉去作項目，而作項目時多用的也是C！三，就交流范圍而言，現(xiàn)在計算機版里用C的人要多得多，所以，交流的機會應該要多一些，這樣提高的也快些。四，其它原因。至于考試的時候用哪一個，應該以報考學校的要求為準，如果沒有作要求的，請參照一下該校給出的歷年題的標準答案是用哪種語言。當然，一般情況下，用兩種語言都行，只要算法正確，就會得分。下面，羅列一下類C與類P的不同：類P類C類型定義TYPE、RECORD、ENDTYPEDEF、常量定義CONSTDEFINE函數(shù)定義PROC（或FUNC）名（參數(shù)） STATUS（VOID）名（

10、參數(shù)）；語句段、條件語句IF、THEN、ELSEIF（）、ELSE、賦值語句：比較運算多分支語句CASE變量名OFSWITCH（表達式）（只寫一種）值1：、 CASE值1：、；BREAK；、 、ELSE語句 DEFAULT：語句N1ENDC；循環(huán)語句WHILE條件DO、 WHILE條件、REPEAT、UNTIL（） DO、WHILE（）FOR（初值）TO（終值）DO語句FOR（初值；條件；表達式）語句出錯處理ERROR（錯誤）EXIT（出錯代碼）輸入/出 READ，WRITESCANF，PRINTF注釋 /基本函數(shù)MAX，MIN，ABS，EOF，EOLN，上下取整上下取整分別為FLOOR，CE

11、IL邏輯運算AND，OR，NOT，CAND，COR，！注：以上不同之處在具體算法中的體現(xiàn)，請參照教材P版P25頁和C版P24頁的對應算法。二、本章習題集中?？技耙芽碱}1.1相同1.2相同1.3相似1.4無1.5相似1.6相似1.7相似1.8相似1.9相似1.10相同1.11相似（時間復雜度的比較）1.12相似（時間復雜度的比較）1.13無1.14相似于1.101.15無三、本章例題及習題分析由于本章較為簡單，此部分省略。數(shù)據(jù)結(jié)構(gòu)序言在可視化化程序設計的今天，借助于集成開發(fā)環(huán)境可以很快地生成程序，程序設計不再是計算機專業(yè)人員的專利。很多人認為，只要掌握幾種開發(fā)工具就可以成為編程高手，其實，這是一

12、種誤解。要想成為一個專業(yè)的開發(fā)人員，至少需要以下三個條件： 能夠熟練地選擇和設計各種數(shù)據(jù)結(jié)構(gòu)和算法。 至少要能夠熟練地掌握一門程序設計語言。 熟知所涉及的相關應用領域的知識。 其中，后兩個條件比較容易實現(xiàn)，而第一個條件則需要花相當?shù)臅r間和精力才能夠達到，它是區(qū)分一個程序設計人員水平高低的一個重要標志，數(shù)據(jù)結(jié)構(gòu)貫穿程序設計的始終，缺乏數(shù)據(jù)結(jié)構(gòu)和算法的深厚功底，很難設計出高水平的具有專業(yè)水準的應用程序。曾經(jīng)有一本經(jīng)典計算機專業(yè)書籍叫做數(shù)據(jù)結(jié)構(gòu)+算法=程序，也說明了數(shù)據(jù)結(jié)構(gòu)和算法的重要性。 數(shù)據(jù)結(jié)構(gòu)是計算機科學與工程的基礎研究之一，掌握該領域的知識對于我們進一步進行高效率的計算機程序開發(fā)非常重要。無

13、論在中國還是在美國，數(shù)據(jù)結(jié)構(gòu)一直是大學的計算機專業(yè)重要的專業(yè)基礎課。例如，在著名的美國的加州大學伯克利分校（著名的BSD Unix的發(fā)源地，很多Unix操作系統(tǒng)由它派生而來或帶有它的痕跡例如FreeBSD、Sun公司的Solaris、IBM的AIX），就用一個學期開設數(shù)據(jù)結(jié)構(gòu)和算法課程（在這之前，用一個學期開設C+程序設計課程）。 現(xiàn)行的中學相關的計算機教程或者是關于怎樣使用Windows操作系統(tǒng)及其工具、或者是有關辦公軟件的使用，或者是打字教程。計算機對他們始終有一種神秘感，也許是理論導向吧，因為不可能每個人將來都成為計算機專業(yè)人員。 作為一個中學生，在學完C/C+以后，關鍵的問題是怎樣熟練

14、地應用和鞏固。本網(wǎng)站希望能夠結(jié)合數(shù)據(jù)結(jié)構(gòu)和相關的數(shù)、理、化知識來鞏固C/C+。其實數(shù)據(jù)結(jié)構(gòu)并不難。可以說，數(shù)據(jù)結(jié)構(gòu)貫穿于我們的數(shù)學課程之中，只是思考問題方法的不同。在大學的數(shù)據(jù)結(jié)構(gòu)教程中，很多生僻的詞語、晦澀難懂的語句，連大學生就感到望而生畏。本網(wǎng)站將集合小學和中學的數(shù)學、物理、化學教材，深入淺出地講解這門課程。希望不但能夠?qū)W習電腦有所幫助，更希望能夠?qū)?shù)理化的學習起到一個促進作用。在學習數(shù)據(jù)結(jié)構(gòu)之前，要求學生有C/C+基礎。可以這樣說，C/C+是其他程序設計語言的基礎。掌握了C/C+，學習其他語言就會易如反掌。例如，微軟的MFC類庫基于C+；ATL基于C+中的模板類；Java語言基于C+思

15、想，其編程風格與C+差別很?。籆+ Builder又是基于C+；Delphi中的有關對象的概念與C+中的對象幾乎完全一致。C+相比其他語言具有與計算機硬件集合緊密、代碼效率高，這是Java語言和其他高級語言所無法比擬的。這樣，C/C+對于學習計算機系統(tǒng)結(jié)構(gòu)有很大的好處。第一章：概論(包括習題與答案及要點)本章的重點是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運算三方面的概念及相互關系，難點是算法復雜度的分析方法。 需要達到層次的基本概念和術語有：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。需要

16、達到層次的內(nèi)容有算法、算法的時間復雜度和空間復雜度、最壞的和平均時間復雜度等概念，算法描述和算法分析的方法、對一般的算法要能分析出時間復雜度。對于基本概念，仔細看書就能夠理解，這里簡單提一下：數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。如整數(shù)這個集合中，10這個數(shù)就可稱是一個數(shù)據(jù)元素.又比如在一個數(shù)據(jù)庫(關系式數(shù)據(jù)庫)中，一個記錄可稱為一個數(shù)據(jù)元素，而這個元素中的某一字段就是一個數(shù)據(jù)項。數(shù)據(jù)結(jié)構(gòu)的定義雖然沒有標準，但是它包括以下三方面內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、和對數(shù)據(jù)的操作。這一段

17、比較重要，我用自己的語言來說明一下，大家看看是不是這樣。 比如一個表(數(shù)據(jù)庫)，我們就稱它為一個數(shù)據(jù)結(jié)構(gòu)，它由很多記錄(數(shù)據(jù)元素)組成，每個元素又包括很多字段(數(shù)據(jù)項)組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢? 我們分析數(shù)據(jù)結(jié)構(gòu)都是從結(jié)點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對于這個表中的任一個記錄(結(jié)點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結(jié)點和一個終端結(jié)點，那我們知道了這些關系就能明白這個表的邏輯結(jié)構(gòu)了。 而存儲結(jié)構(gòu)則是指用計算機語言如何表示結(jié)點之間的這種關系。如上面的表，在

18、計算機語言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結(jié)構(gòu)。(注意，在本課程里，我們只在高級語言的層次上討論存儲結(jié)構(gòu)。) 第三個概念就是對數(shù)據(jù)的運算，比如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎么樣才能進行這樣的操作呢? 這也就是數(shù)據(jù)的運算，它不僅僅是加減乘除這些算術運算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運算常常涉及算法問題。弄清了以上三個問題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個概念。通常我們就將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu) (這兩個很容易理解)數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈

19、接存儲方法、索引存儲方法和散列存儲方法。-下一個是難點問題，就是算法的描述和分析，主要是算法復雜度的分析方法及其運用。 首先了解一下幾個概念。一個是時間復雜度，一個是漸近時間復雜度。前者是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當問題規(guī)模趨向無窮大時，該算法時間復雜度的數(shù)量級。 當我們評價一個算法的時間性能時，主要標準就是算法的漸近時間復雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間復雜度T(n)=O(f(n)簡稱為時間復雜度，其中的f(n)一般是算法中頻度最大的語句頻度。此外，算法中語句的頻度不僅與問題規(guī)模有關，還與輸入實例中各元素的取值相關。但是我們

20、總是考慮在最壞的情況下的時間復雜度。以保證算法的運行時間不會比它更長。常見的時間復雜度，按數(shù)量級遞增排列依次為：常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)。時間復雜度的分析計算請看書本上的例子，然后我們通過做練習加以領會和鞏固。數(shù)據(jù)結(jié)構(gòu)習題一 1.1 簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。 數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)

21、據(jù)元素有時可以由若干數(shù)據(jù)項組成。 數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。 邏輯結(jié)構(gòu)：指各數(shù)據(jù)元素之間的邏輯關系。 存儲結(jié)構(gòu)：就是數(shù)據(jù)的邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)。 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類，它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。1.2 試舉一個數(shù)據(jù)結(jié)

22、構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。 例如有一張學生成績表，記錄了一個班的學生各門課的成績。按學生的姓名為一行記成的表。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學號，成績等字段)就是一個結(jié)點，對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關系就確定了這個表的邏輯結(jié)構(gòu)。那么我們怎樣把這個表中的數(shù)據(jù)存儲到計算機里呢? 用高級語言如何表示各結(jié)點之間的關系呢? 是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機存放各結(jié)點數(shù)據(jù)再用指針進行鏈接呢

23、? 這就是存儲結(jié)構(gòu)的問題，我們都是從高級語言的層次來討論這個問題的。(所以各位趕快學C語言吧)。最后，我們有了這個表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對這張表中的記錄進行查詢，修改，刪除等操作，對這個表可以進行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。1.3 常用的存儲表示方法有哪幾種?常用的存儲表示方法有四種: 順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。 鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈

24、式存儲結(jié)構(gòu)。 索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。 散列存儲方法：就是根據(jù)結(jié)點的關鍵字直接計算出該結(jié)點的存儲地址。1.4 設三個函數(shù)f,g,h分別為 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 請判斷下列關系是否成立：(1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5)(4) h(n)=O(nlgn) (1)成立。 這里我們復習一下漸近時間復雜度的表示法T(n)=O(f(n)，這里的O是數(shù)學符號，它的嚴格定義是若T(n)和f(n)是定義在正整

25、數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n)表示存在正的常數(shù)C和n0 ,使得當nn0時都滿足0T(n)C?f(n)。用容易理解的話說就是這兩個函數(shù)當整型自變量n趨向于無窮大時，兩者的比值是一個不等于0的常數(shù)。這么一來，就好計算了吧。第(1)題中兩個函數(shù)的最高次項都是n3,因此當n時，兩個函數(shù)的比值是一個常數(shù)，所以這個關系式是成立的。 （2）成立。 （3）成立。 （4）不成立。1.5 設有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者，n至少要多大? 15 最簡單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我

26、們就加個5，用15代入得前者為22500，后者為32768，已經(jīng)比前者大但相差不多，那我們再減個1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來就是n至少要是15. 1.6 設n為正整數(shù)，利用大O記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。1.6 設n為正整數(shù)，利用大O記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。(1) i=1; k=0 while(i k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 這個函數(shù)是按線性階遞增的 (2) i=0; k=0;dok=k+10*i; i+; while(i T(n)=O(n) 這也是線性階遞增的 (3)

27、 i=1; j=0; while(i+j1 while (x=(y+1)*(y+1)y+; T(n)=n1/2 T(n)=O(n1/2) 最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個按平方根階遞增的函數(shù)。 (5) x=91; y=100; while(y0)if(x100)x=x-10;y-;else x+; T(n)=O(1) 這個程序看起來有點嚇人，總共循環(huán)運行了1000次，但是我們看到n沒有? 沒。這段程序的運行是和n無關的，就算它再循環(huán)一萬年，我們也不管他，只是一個常數(shù)階的函數(shù)。 1.7 算法的時間復雜度僅與問題的規(guī)模相關嗎? No,事實上，算法的時間復雜度不僅與問題的規(guī)模

28、相關，還與輸入實例中的元素取值等相關，但在最壞的情況下，其時間復雜度就是只與求解問題的規(guī)模相關的。我們在討論時間復雜度時，一般就是以最壞情況下的時間復雜度為準的。1.8 按增長率由小至大的順序排列下列各函數(shù)： 2100, (2/3)n，(3/2)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 分析如下：2100 是常數(shù)階； (2/3)n和 (3/2)n是指數(shù)階,其中前者是隨n的增大而減小的； nn是指數(shù)方階； n 是方根階, n! 就是n(n-1)(n-2). 就相當于n次方階；2n 是指數(shù)階，lgn是對數(shù)階 ,nlgn是對數(shù)方階, n(3/2)是3/2次方階。根據(jù)以上

29、分析按增長率由小至大的順序可排列如下： (2/3)n 2100 lgn n n(3/2) nlgn (3/2)n 2n n! 10)if(x100)x=x-10;y-; else x+;A. O(1) B.O(x) C.O(y) D.O(n) 等等。順便一提，基本概念和基本理論的掌握是得分的基本手段。第二章：線性表(包括習題與答案及要點)本章的重點是掌握順序表和單鏈表上實現(xiàn)的各種基本算法及相關的時間性能分析，難點是使用本章所學的基本知識設計有效算法解決與線性表相關的應用問題。要求達到層次的內(nèi)容有:線性表的邏輯結(jié)構(gòu)特征；線性表上定義的基本運算，并利用基本運算構(gòu)造出較復雜的運算。要求達到層次的內(nèi)容

30、有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應用問題。鏈表如何表示線性表中元素之間的邏輯關系；單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別；單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法及其時間復雜度。循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。雙鏈表的定義和相關算法。利用鏈表設計算法解決簡單應用問題。要求達到層次的內(nèi)容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時空性能。線性表的邏輯結(jié)構(gòu)特征是很容易理解的，如其名，它的邏輯結(jié)構(gòu)特征就好象是一條線，上面打了一個個結(jié)，很形象的，如果這條線上面有結(jié)，那么它

31、就是非空表，只能有一個開始結(jié)點，有且只能有一個終端結(jié)點，其它的結(jié)前后所相鄰的也只能是一個結(jié)點(直接前趨和直接后繼)。關于線性表上定義的基本運算，主要有構(gòu)造空表、求表長、取結(jié)點、查找、插入、刪除等。線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關系。在計算機中，如何把線性表的結(jié)點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點相鄰關系是一致的。在順序表中實現(xiàn)的基本運算主要討論了插入和刪除兩種運算。相關的算法我們通過練習掌握。對于順序表的插入和刪除運算，其平均時間復雜度均為O(n)。線性表的

32、鏈式存儲結(jié)構(gòu)。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結(jié)點，這組存儲單元可以分布在內(nèi)存中任何位置上。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。所以為了能正確表示結(jié)點間的邏輯關系，在存儲每個結(jié)點值的同時，還存儲了其后繼結(jié)點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點結(jié)構(gòu)。 一個單鏈表由頭指針的名字來命名。對于單鏈表，其操作運算主要有建立單鏈表(頭插法、尾插法和在鏈表開始結(jié)點前附加一個頭結(jié)點的算法)、查找(按序號和按值)、插入運算、刪除運算等。以上各運算的平均時間復雜度均為O(n).其主要時間是耗費在查找操作上。循環(huán)鏈表是一種首尾相接的鏈表。也就是終端結(jié)點的指針域不

33、是指向NULL空而是指向開始結(jié)點(也可設置一個頭結(jié)點)，形成一個環(huán)。采用循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。這樣做的好處是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表了。判別鏈表終止的條件也不同于單鏈表，它是以指針是否等于某一指定指針如頭指針或尾指針來確定。 雙鏈表一般也由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。關于順序表和鏈表的比較，請看下表：具體要求 順序表 鏈表 基于空間 適于線性表長度變化不大，易于事先確定其大小時采用。 適于當線性表長度變化大，難以估計其存儲規(guī)模時采用。 基于時間 由于順序表是一種隨機存儲結(jié)構(gòu)，當線性表的操作主要是查找時，

34、宜采用。 鏈表中對任何位置進行插入和刪除都只需修改指針，所以這類操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。 第二章 線性表習題及答案 一、基礎知識題(答案及點評) 2.1 試描述頭指針、頭結(jié)點、開始結(jié)點的區(qū)別、并說明頭指針和頭結(jié)點的作用。一、基礎知識題2.1 答：開始結(jié)點是指鏈表中的第一個結(jié)點，也就是沒有直接前趨的那個結(jié)點。鏈表的頭指針是一指向鏈表開始結(jié)點的指針(沒有頭結(jié)點時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。頭結(jié)點是我們?nèi)藶榈卦阪湵淼拈_始結(jié)點之前附加的一個結(jié)點。有了頭結(jié)點之后，頭指針指向頭結(jié)點，不論鏈

35、表否為空，頭指針總是非空。而且頭指針的設置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點之后)。(答案及點評) 2.2 何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?2.2 答：在實際應用中，應根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，通常有以下幾方面的考慮：1.基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。2.基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；

36、反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。(答案及點評) 2.3 在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點?具體的移動次數(shù)取決于哪兩個因素?2.3.答：在等概率情況下，順序表中插入一個結(jié)點需平均移動n/2個結(jié)點。刪除一個結(jié)點需平均移動(n-1)/2個結(jié)點。具體的移動次數(shù)取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動的結(jié)點數(shù)越少。(答案及點評) 2.4 為什么在單循環(huán)鏈表中設置尾指針比設置頭指針更好?2.4. 答：尾指針是指向終端結(jié)點的指針，用它來表示單

37、循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear-next-next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。(答案及點評) 2.5 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應的鏈表中刪去?若可以，其時間復雜度各為多少?2.5 答：我們分別討論三種鏈表的情況。1. 單鏈表。當我們知道指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此

38、無法刪去該結(jié)點。2. 雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復雜度為O(1)。3. 單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的直接前趨。因此可以刪去p所指結(jié)點。其時間復雜度應為O(n)。(答案及點評) 2.6 下述算法的功能是什么?LinkList Demo(LinkList L) / L 是無頭結(jié)點單鏈表ListNode *Q,*P;if(L&L-next)Q=L;L=L-next=L;while (P-next) P=P-next;

39、P-next=Q; Q-next=NULL;return L;/ Demo二、算法設計題(答案及點評) 2.7 設線性表的n個結(jié)點定義為(a0,a1,.an-1)，重寫順序表上實現(xiàn)的插入和刪除算法：InsertList 和DeleteList./P二、算法設計題：2.7 (本題感謝pastar的指正)解：算法如下:#define ListSize 100/ 假定表空間大小為100#include #include void Error(char * message)fprintf(stderr,錯誤:%sn,message);exit(1);/從0開始計， 表空間大小應為101了typedef

40、 int Datatype ;/假定Datatype的類型為int型typedef structDatatype dataListSize;/ 向量data用于存放表結(jié)點int length; / 當前的表長度 Seqlist;/以上為定義表結(jié)構(gòu)/-以下為要求算法-void InsertList ( Seqlist *L, Datatype x, int i)/將新結(jié)點x插入L所指的順序表的第i個結(jié)點ai的位置上int j;if ( i L - length )Error(position error;/ 非法位置，退出if ( L-length=ListSize )Error(overflo

41、w;for ( j=L-length-1 ; j = i ; j -)L-dataj+1=L-data j;L-data=x ;L-length+ ;void DeleteList ( Seqlist *L, int i )/ 從L所指的順序表中刪除第i個結(jié)點aiint j;if ( i L- length-1)Error( position error ) ;for ( j = i+1 ; j length ; j+ ) L-data j-1 =L-data j; / 結(jié)點前移L- length- ; /表長減小/=以下為驗證算法而加=void Initlist(Seqlist *L)L-l

42、ength=0;void main()Seqlist *SEQA=new Seqlist;Initlist(SEQA);int i;for (i=0;i InsertList (SEQA,i,i);printf(%dn,SEQA-data);DeleteList (SEQA,99);for (i=0;i printf(%dn,SEQA-data); (答案及點評) 2.8 試分別用順序表和單鏈表作為存儲結(jié)構(gòu)，實現(xiàn)將線性表(a0,a1,.an-1)就地逆置的操作，所謂就地指輔助空間應為O(1)。2.8 解：按題意，為將線性表逆置，但輔助空間不能隨表的規(guī)模增大。我們分別討論順序表和單鏈表的情況：1

43、. 順序表：要將該表逆置，可以將表中的開始結(jié)點與終端結(jié)點互換，第二個結(jié)點與倒數(shù)第二個結(jié)點互換，如此反復，就可將整個表逆置了。算法如下：/ 表結(jié)構(gòu)定義同上void ReverseList( Seqlist *L)Datatype t ; /設置臨時空間用于存放dataint i;for ( i=0 ; i length/2 ; i+) t = L-data;/交換數(shù)據(jù) L - data i = L - data L - length - 1 - i ; L - data L - length - 1 - i = t ;2. 鏈表：也是可以用交換數(shù)據(jù)的方式來達到逆置的目的，但是由于是單鏈表，數(shù)據(jù)的

44、存取不是隨機的，因此算法效率太低，我們可以利用指針的指向轉(zhuǎn)換來達到表逆置的目的。算法是這樣的：/ 結(jié)構(gòu)定義略LinkList ReverseList( LinkList head )/ 將head 所指的單鏈表逆置ListNode *p ,*q ;/設置兩個臨時指針變量if( head-next & head-next-next)/當鏈表不是空表或單結(jié)點時p=head-next;q=p-next;p - next=NULL;/將開始結(jié)點變成終端結(jié)點while (q)/每次循環(huán)將后一個結(jié)點變成開始結(jié)點p=q;q=q-next ;p-next = head- next ;head-next = p

45、;return head;return head;/如是空表或單結(jié)點表，直接返回head(答案及點評) 2.9 設順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。2.9 解：因已知順序表L是遞增有序表，所以只要從頭找起找到第一個比它大(或相等)的結(jié)點數(shù)據(jù)，把x插入到這個數(shù)所在的位置就是了。算法如下：void InsertIncreaseList( Seqlist *L , Datatype x )int i;for ( i=0 ; i length & L-data i x ; i+) ; / 查找并比較,分號不能少InsertList ( L ，x , i ); /

46、 調(diào)用順序表插入函數(shù)(答案及點評) 2.10 設順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。2.10 解：與上題相類似，只要從頭找到第一個比x小(或相等)的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。算法如下：void InsertDecreaseList( Seqlist *L, Datatype x )int i;for (i=0; i length & L- data x ; i+) ; /查找InsertList ( L , x , i ); / 調(diào)用順序表插入函數(shù)(答案及點評) 2.11 寫一算法在單鏈表上實現(xiàn)線性表的ListLength(L)運算。2.11 解：求單鏈

47、表長只能用遍歷的方法了，從頭數(shù)到尾，總能數(shù)出來吧。算法如下：int ListLength ( LinkList L )int len=0 ;ListNode *p;p=L; /設該表有頭結(jié)點while ( p-next )p=p-next;len+;return len;(答案及點評) 2.12 已知L1和L2分別指向兩個單鏈表的頭結(jié)點，且已知其長度分別為m和n。試寫一算法將這兩個鏈表連接在一起，請分析你的算法的時間復雜度。2.12 解：算法如下:LinkList Link( LinkList L1 , LinkList L2 )/將兩個單鏈表連接在一起ListNode *p , *q ;p=

48、L1;q=L2;while ( p-next ) p=p-next; /查找終端結(jié)點p-next = q-next ; /將L2的開始結(jié)點鏈接在L1之后return L1 ;本算法的主要操作時間花費在查找L1的終端結(jié)點上，與L2的長度無關，所以本算的法時間復雜度為：m+1=O(m)(答案及點評) 2.13 設 A和B是兩個單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請分析算法的時間復雜度。2.13 解：根據(jù)已知條件，A和B是兩個遞增有序表，所以我們可以以A表為基礎，按照插入單個元素的辦法把B表的元素插入A表中，完成后，將表逆置就得到了一個按元素值遞減有序的單鏈表C了。算法如下：LinkList MergeSort ( LinkList A , LinkList B )/ 歸并兩個遞增有序