數(shù)據(jù)結(jié)構(gòu)課后習(xí)題解答

第一章緒論

一、基本問題問答：

1、什么叫數(shù)據(jù)結(jié)構(gòu)？如何理解“數(shù)據(jù)結(jié)構(gòu)”？如何樹立數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)體系？

廣義上的數(shù)據(jù)結(jié)構(gòu)指的是：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。狹義上的數(shù)據(jù)結(jié)構(gòu)專指邏輯結(jié)構(gòu)，就是兀

素間的邏輯關(guān)系，主要類型有：集合型，線性結(jié)構(gòu)，樹型，圖型！

整個(gè)數(shù)據(jù)結(jié)構(gòu)的課程就是圍繞著以上幾種數(shù)據(jù)類型展開的，加上基于這些結(jié)構(gòu)的基本操作：

插入，刪除，查找，取元素，取長度等等。另外，還有基于這些數(shù)據(jù)結(jié)構(gòu)的較為復(fù)雜的算法:

查找和排序。在嚴(yán)老師和其他很多的數(shù)據(jù)結(jié)構(gòu)教材中都把查找和排序作為了?個(gè)獨(dú)立的部

分，這一部分實(shí)際上主要在探討算法，而不在是結(jié)構(gòu)本身了。算法的概念將在后面提到。

2、數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)

定義數(shù)據(jù)結(jié)構(gòu)，當(dāng)計(jì)算機(jī)程序運(yùn)行時(shí)，程序就按照定義給這些數(shù)據(jù)分配了空間。而數(shù)據(jù)定義,

是在定義其邏輯結(jié)構(gòu)。以鏈表為列，在實(shí)際定義時(shí)，一個(gè)個(gè)的結(jié)點(diǎn)，由于其指針域可以指向

另一個(gè)結(jié)點(diǎn)，那么依靠這種指向關(guān)系，就可在邏輯上建立起一條鏈狀結(jié)構(gòu)！但是，在實(shí)際的

程序執(zhí)行時(shí)，是不會有這樣的一條鏈的，而是通過在一個(gè)結(jié)點(diǎn)空間的某個(gè)空間內(nèi)填入了下一

個(gè)結(jié)點(diǎn)的地址！這樣的每個(gè)有數(shù)據(jù)和地址的結(jié)點(diǎn)，才是其物理結(jié)構(gòu)。3、算法的概念、分析，

算法時(shí)間復(fù)雜度的含義及分析算法就是解決問題的方法或策略。一個(gè)算法好與壞的評價(jià)標(biāo)準(zhǔn)

是：正確，可讀，健壯，效率高，空間??！

設(shè)計(jì)算法時(shí)，應(yīng)該按照嚴(yán)教材上關(guān)于類C(或類P)語言的描述來作，格式為：

statusfun_name{

〃算法說明

for{…〃典型功能及復(fù)雜語句后加注釋

}//fun_name

注意寫好注釋！不求多，但求精！

時(shí)間復(fù)雜度：分析算法效率的重要工具。主要是靠推算語句執(zhí)行次頻度而得來的。時(shí)間復(fù)雜

度考查的是“某數(shù)量級”的概念，即：

T(n)=0(f(n))中,存在正的常數(shù)C和nO,使得當(dāng)n>=nO時(shí)，0<=T(N)<=C*F(N)

當(dāng)空間復(fù)雜度為。(1)時(shí)，稱算法為就地工作(原地工作)。

算法時(shí)間復(fù)雜度的分析：時(shí)間復(fù)雜度的分析說到底是分析當(dāng)系統(tǒng)規(guī)模增大時(shí)，系統(tǒng)所耗費(fèi)時(shí)

間的數(shù)量級。數(shù)量級的定義見上。簡而言之，2nA2,6M2,計(jì)2是同一數(shù)量級，因?yàn)橛蒑2

可推出其它兩個(gè)(常數(shù)相乘)。此外，當(dāng)時(shí)間復(fù)雜度的公式中出現(xiàn)n的多項(xiàng)式時(shí)，應(yīng)該以高

階為準(zhǔn)。因?yàn)榇藭r(shí)影響總體變化規(guī)律的是高階項(xiàng)的值。在分析時(shí)間復(fù)雜度時(shí)，應(yīng)該以程序或

算法中執(zhí)行次數(shù)最多的語句為準(zhǔn)，通常情況下是最內(nèi)層循環(huán)的時(shí)間復(fù)雜荒，最內(nèi)層語句的執(zhí)

行次數(shù)計(jì)算出來后，取最高的次數(shù)，然后去掉該項(xiàng)中的常數(shù)因子即可。

空間復(fù)雜度的度量主要是看當(dāng)系統(tǒng)規(guī)模n增大時(shí)，系統(tǒng)所占用的額外空間是否也在增大，按

怎么的規(guī)律增大。如果沒有增大，即額外空間始終是個(gè)常數(shù)，算法就是原地工作！

4、算法設(shè)計(jì)規(guī)范

1〉在算法設(shè)計(jì)中，第一個(gè)牽涉到的概念是：算法說明。

它是寫在過程或函數(shù)首部以下的注釋內(nèi)容。雖是注釋內(nèi)容，卻是必不可少的。在測試中也占

有相當(dāng)大的作用。此說明主要包括：算法的功能，參數(shù)表中各參數(shù)的含義及輸入輸出定義；

算法中引用了哪些全局變量或外部定義的變量，它們的作用，入口初值，以及應(yīng)該滿足哪些

限制條件。如：鏈表是否帶頭結(jié)點(diǎn)，表中元素是否有序，如果有序是遞增還是遞減等等！必

要時(shí)，算法說明還可用來陳述算法思想，采用的存儲結(jié)構(gòu)等。遞歸算法的說明特別重要，讀

S

者應(yīng)該力求將它寫為算法的嚴(yán)格定義。幾個(gè)例子：

2.29procedureD訐ferenceSqlist(VARa;Sqlist;b,c:Sqlist);

｛刪去增序順序表中那些既在增序順序表中B出現(xiàn)又在增序順序表C中出現(xiàn)的元素｝

2.33procedureSqlistlinkedlist(VARIcJdJoinkedListJIinkedList);

｛將線性表II分割為3個(gè)循環(huán)鏈表lc,Id和Io,｝

｛其中每個(gè)循環(huán)鏈表只含一類字符，分別為［7V..Z］、［'O'..'9'J和其它字符。｝

2》注釋與斷言

在難懂的語句和關(guān)鍵的語句(段)之后加以注釋可以大大提高程序的可讀性。注釋要恰當(dāng)，

并非越多越好；此外，注釋句的抽象程度應(yīng)略高于語句(段)。

斷言是注釋的一種特殊寫法，它是一個(gè)邏輯謂詞，陳述算法執(zhí)行到此點(diǎn)時(shí)應(yīng)滿足的條件，即

這種形式：當(dāng)、、、時(shí)，、、。最重要的就是算法的入口斷言與else分支斷言。如果算法不含有

參數(shù)僉性檢測的代碼段，書寫入口斷言是最低限度的要求。

3＞輸入、輸出

三種方式：

a^通過專門的輸入/出語句：read,write,scanf,printf等

b、通過參數(shù)表中的參數(shù)傳遞

c、通過全局及外部變量

4＞錯(cuò)誤處理

三種處理方式：

a、error語句實(shí)現(xiàn)

b、通過函數(shù)返回錯(cuò)誤代碼或錯(cuò)誤狀態(tài)值

c、exit語句實(shí)現(xiàn)

提倡使用第二種方式來實(shí)現(xiàn)錯(cuò)誤處理

5》語句的使用與算法結(jié)構(gòu)

避免使用got。語句，算法結(jié)構(gòu)結(jié)構(gòu)應(yīng)該同層次對齊，下一層向上一層縮進(jìn)兩格，并以適當(dāng)

的符號標(biāo)識語句段的開始與結(jié)束：［］，｛｝

6＞基本運(yùn)算

未明確要求的，不得直接用教科書上的基本運(yùn)算

非用不可的，要將這些基本運(yùn)算的代碼全部寫出

7＞幾點(diǎn)建議

a、建議以圖說明算法

b、建議在算法書寫完畢后，用邊界條件的值驗(yàn)證一下算法能否正確執(zhí)行

5、類P與類C大比拼

許多朋友問我類P與類C有啥區(qū)別，哪個(gè)更好？考試的時(shí)候用哪個(gè)語言？其實(shí)，這些都是一

些很基礎(chǔ)的問題，不客氣地說這是考研門外漢的問題

。類P較類C的教材版本出得早，在后期的類C版數(shù)據(jù)中省去了類P中的一些內(nèi)容，比如:

棧一章的遞歸到非遞歸的轉(zhuǎn)化等。但并不能因此就說類C

版要差，事實(shí)上，類C的更符合當(dāng)前考試和應(yīng)用的發(fā)展趨勢，從整體認(rèn)同度而言，個(gè)人建議

還是用類C好一點(diǎn)，原因：一，C語言本身很靈活，程

序簡潔，是真正的程序員用的語言，更是一個(gè)計(jì)算機(jī)研究生必須掌握的；二，C語言本身在

實(shí)際項(xiàng)目的應(yīng)用中是一種通用語言，軟件公司絕大多

數(shù)是要精通VC的，學(xué)好C的DS其意義更深遠(yuǎn)一些。另外，考慮到考上后絕大多數(shù)研友都

會被導(dǎo)師拉去作項(xiàng)目，而作項(xiàng)目時(shí)多用的也是C!三，就

交流范圍而言，現(xiàn)在計(jì)算機(jī)版里用C的人要多得多，所以，交流的機(jī)會應(yīng)該要多一些，這樣

S

提高的也快些。四，其它原因。至于考試的時(shí)候用哪

一個(gè)，應(yīng)該以報(bào)考學(xué)校的要求為準(zhǔn)，如果沒有作要求的，請參照一下該校給出的歷年題的標(biāo)

準(zhǔn)答案是用哪種語言。當(dāng)然，一般情況下，用兩種

語言都行，只要算法正確，就會得分。

下面，羅列一下類C與類P的不同：

1類P1類c

類型定義1TYPE、、、RECORD、、、END1TYPEDEF、、、{、、}

常量定義1CONST1#DEFINE

函數(shù)定義1PROC（或FUNC）名（參數(shù)）[]ISTATUS(VOID)名(參數(shù))；()

語句段1［、、、11｛、、、）

條件語句1IF、、THEN、、ELSE1IF()、、ELSE、、

賦值語句1=

比較運(yùn)算1==

多分支語句1CASE變量名OF1SWITCH(表達(dá)式){

（只寫i種）1值1：、、、1CASE值L、、、、；BREAK;

、、、1、、、

1ELSE語句1DEFAULT：語句N+l

1ENDC；11

循環(huán)語句1WHILE條件DO［、、、、］1WHILE條件｛、、、｝

1REPEAT、、、UNTIL()1DO{、、、}WHILE()

1FOR（初值）TO（終值）DO［語句］1FOR（初值；條件；表達(dá)式）｛語句｝

出錯(cuò)處理IERROR('錯(cuò)誤’)1EXIT（出錯(cuò)代碼）

輸入/出1READ,WRITE1SCANF,PRINTF

注釋1{)1//

基本函數(shù)1MAX,MIN,ABS,EOF,EOLN,上下取整1上下取整分別為FLOOR,CEIL

邏輯運(yùn)算1AND,OR,NOT,CAND,COR1&&,11,!

注：以上不同之處在具體算法中的體現(xiàn)，請參照教材P版P25頁和C版P24頁的對應(yīng)算法。

二、本章習(xí)題集中?？技耙芽碱}

S

1.1相同1.2相同1.3相似1.4無1.5相似1.6相似L7相似1.8相似1.9相似1.10

相同1.11相似（時(shí)間復(fù)雜度的比較）1.12相似（時(shí)間復(fù)雜度的比較）1.13無1.14相

似于1.101.15無

三、本章例題及習(xí)題分析

由于本章較為簡單，此部分省略。

數(shù)據(jù)結(jié)構(gòu)一一序言在可視化化程序設(shè)計(jì)的今天，借助于集成開發(fā)環(huán)境可以很快地生成程序，

程序設(shè)計(jì)不再是計(jì)算機(jī)專業(yè)人員的專利。很多人認(rèn)為，只要掌握幾種開發(fā)工具就可以成為編

程高手，其實(shí)，這是一種誤解。要想成為一個(gè)專業(yè)的開發(fā)人員，至少需要以下三個(gè)條件：

能夠熟練地選擇和設(shè)計(jì)各種數(shù)據(jù)結(jié)構(gòu)和算法。至少要能夠熟練地掌握一門程序設(shè)計(jì)語言。

熟知所涉及的相關(guān)應(yīng)用領(lǐng)域的知識。其中，后兩個(gè)條件比較容易實(shí)現(xiàn)，而第一個(gè)條件則

需要花相當(dāng)?shù)臅r(shí)間和精力才能夠達(dá)到，它是區(qū)分一個(gè)程序設(shè)計(jì)人員水平高低的一個(gè)重要標(biāo)

志，數(shù)據(jù)結(jié)構(gòu)貫穿程序設(shè)計(jì)的始終，缺乏數(shù)據(jù)結(jié)構(gòu)和算法的深厚功底，很難設(shè)計(jì)出高水平的

具有專業(yè)水準(zhǔn)的應(yīng)用程序。曾經(jīng)有一本經(jīng)典計(jì)算機(jī)專業(yè)書籍叫做《數(shù)據(jù)結(jié)構(gòu)+算法引辱》，

也說明了數(shù)據(jù)結(jié)構(gòu)和算法的重要性。

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與工程的基礎(chǔ)研究之一，掌握該領(lǐng)域的知識對于我們進(jìn)一步進(jìn)

行高效率的計(jì)算機(jī)程序開發(fā)非常重要。無論在中國還是在美國，《數(shù)據(jù)結(jié)構(gòu)》一直是大學(xué)的

計(jì)算機(jī)專'也重要的專業(yè)基礎(chǔ)課。例如，在著名的美國的加州大學(xué)伯克利分校（著名的BSDUnix

的發(fā)源地，很多Unix操作系統(tǒng)由它派生而來或帶有它的痕跡——例如FreeBSD、Sun公司的

Solaris,IBM的AIX）,就用一個(gè)學(xué)期開設(shè)《數(shù)據(jù)結(jié)構(gòu)和算法》課程（在這之前，用一個(gè)學(xué)期

開設(shè)《C++程序設(shè)計(jì)》課程）。現(xiàn)行的中學(xué)相關(guān)的計(jì)算機(jī)教程或者是關(guān)于怎樣使用Windows

操作系統(tǒng)及其工具、或者是有關(guān)辦公軟件的使用，或者是打字教程。計(jì)算機(jī)對他們始終有一

種神秘感，也許是理論導(dǎo)向吧，因?yàn)椴豢赡苊總€(gè)人將來都成為計(jì)算機(jī)專業(yè)人員。作為一個(gè)

中學(xué)生，在學(xué)完C/C++以后，關(guān)鍵的問題是怎樣熟練地應(yīng)用和鞏固。本網(wǎng)站希望能夠結(jié)合《數(shù)

據(jù)結(jié)構(gòu)》和相關(guān)的數(shù)、理、化知識來鞏固C/C++。其實(shí)《數(shù)據(jù)結(jié)構(gòu)》并不難。可以說，數(shù)據(jù)

結(jié)構(gòu)貫穿于我們的數(shù)學(xué)課程之中，只是思考問題方法的不同。在大學(xué)的《數(shù)據(jù)結(jié)構(gòu)》教程中，

很多生僻的詞語、晦澀難懂的語句，連大學(xué)生就感到望而生畏。本網(wǎng)站將集合小學(xué)和中學(xué)的

數(shù)學(xué)、物理、化學(xué)教材，深入淺出地講解這門課程。希望不但能夠?qū)W(xué)習(xí)電腦有所幫助，更

希望能夠?qū)?shù)理化的學(xué)習(xí)起到一個(gè)促進(jìn)作用。

在學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》之前，要求學(xué)生有C/C++基礎(chǔ)?？梢赃@樣說，C/C++是其他程序設(shè)計(jì)語

言的基礎(chǔ)。掌握了C/C++,學(xué)習(xí)其他語言就會易如反掌。例如，微軟的MFC類庫基于C++；

ATL基于C++中的模板類；Java語言基于C++思想，其編程風(fēng)格與C++差別很小；C++Builder

又是基于C++；Delphi中的有關(guān)對象的概念與C++中的對象幾乎完全一致。C++相比其他語言

具有與計(jì)算機(jī)硬件集合緊密、代碼效率高，這是Java語言和其他高級語言所無法比擬的。

這樣，C/C++對于學(xué)習(xí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)有很大的好處。

第一章：概論（包括習(xí)題與答案及要點(diǎn)）

本章的重點(diǎn)是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系，

難點(diǎn)是算法復(fù)雜度的分析方法。

需要達(dá)到〈識記〉層次的基本概念和術(shù)語有：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)。特別

是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯

結(jié)構(gòu)和四種常用的存儲表示方法。

需要達(dá)到〈領(lǐng)會〉層次的內(nèi)容有算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞的和平均時(shí)間復(fù)

雜度等概念，算法描述和算法分析的方法、對一般的算法要能分析出時(shí)間復(fù)雜度。對于

基本概念，仔細(xì)看書就能夠理解，這里簡單提一下：數(shù)據(jù)就是指能夠被計(jì)算機(jī)識別、存儲和

加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時(shí)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)

S

據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位。如整數(shù)這個(gè)集合中，10這個(gè)數(shù)就可稱

是一個(gè)數(shù)據(jù)元素.又比如在一個(gè)數(shù)據(jù)庫(關(guān)系式數(shù)據(jù)庫)中，一個(gè)記錄可稱為一個(gè)數(shù)據(jù)元素，而

這個(gè)元素中的某一字段就是一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)結(jié)構(gòu)的定義雖然沒有標(biāo)準(zhǔn)，但是它包括以下

三方面內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、和對數(shù)據(jù)的操作。這一段比較重要，我用自己的語言來

說明一下，大家看看是不是這樣。

比如?個(gè)表(數(shù)據(jù)庫)，我們就稱它為一個(gè)數(shù)據(jù)結(jié)構(gòu)，它由很多記錄(數(shù)據(jù)元素)組成，每個(gè)元

素又包括很多字段(數(shù)據(jù)項(xiàng))組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢？我們分析數(shù)據(jù)結(jié)構(gòu)

都是從結(jié)點(diǎn)(其實(shí)也就是元素、記錄、頂點(diǎn)，雖然在各種情況下所用名字不同，但說的是同

一個(gè)東東)之間的關(guān)系來分析的，對于這個(gè)表中的任一個(gè)記錄(結(jié)點(diǎn))，它只有一個(gè)直接前趨，

只有一個(gè)直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個(gè)表只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終

端結(jié)點(diǎn)，那我們知道了這些關(guān)系就能明白這個(gè)表的邏輯結(jié)構(gòu)了。

而存儲結(jié)構(gòu)則是指用計(jì)算機(jī)語言如何表示結(jié)點(diǎn)之間的這種關(guān)系。如上面的表，在計(jì)算機(jī)語言

中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機(jī)的存放在內(nèi)存中再用指針把它們鏈接在一

起，這兩種表示法就成為兩種不同的存儲結(jié)構(gòu)。(注意，在本課程里，我們只在高級語言的

層次上討論存儲結(jié)構(gòu)。)第三個(gè)概念就是對數(shù)據(jù)的運(yùn)算，比如一張表格，我們需要進(jìn)行查找,

增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢？這也就是數(shù)據(jù)的運(yùn)算，它

不僅僅是加減乘除這些算術(shù)運(yùn)算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運(yùn)算常常涉及算法問題。

弄清了以上三個(gè)問題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個(gè)概念。通常我們就將數(shù)據(jù)的邏輯結(jié)

構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)(這兩個(gè)很容易理解)

數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。

下一個(gè)是難點(diǎn)問題，就是算法的描述和分析，主要是算法復(fù)雜度的分析方法及其運(yùn)用。

首先了解一下兒個(gè)概念。一個(gè)是時(shí)間復(fù)雜度，?個(gè)是漸近時(shí)間復(fù)雜度。前者是某個(gè)算法的時(shí)

間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算

法時(shí)間復(fù)雜度的數(shù)量級。

當(dāng)我們評價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度，因此，在算

法分析時(shí)，往往對兩者不予區(qū)分，經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n)簡稱為時(shí)間復(fù)雜度，

其中的f(n)一般是算法中頻度最大的語句頻度。

此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。但

是我們總是考慮在最壞的情況下的時(shí)間復(fù)雜度。以保證算法的運(yùn)行時(shí)間不會比它更長。

常見的時(shí)間復(fù)雜度，按數(shù)量級遞增排列依次為：常數(shù)階。(1)、對數(shù)階O(log2n)、線性階

O(n)、線性對數(shù)階。(nlog2n)、物階O(n"2)、立方階O(n"3)、k次方階O(n"k)、搠階0(2?)。

時(shí)間復(fù)雜度的分析計(jì)算請看書本上的例子，然后我們通過做練習(xí)加以領(lǐng)會和鞏固。

數(shù)據(jù)結(jié)構(gòu)習(xí)題一

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ù)：指能夠被計(jì)算機(jī)識別、存儲和加工處理的信息載體。

?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、

記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成。

?數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。

?數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:

數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。

?邏輯結(jié)構(gòu)：指各數(shù)據(jù)元素之間的邏輯關(guān)系。

?存儲結(jié)構(gòu)：就是數(shù)據(jù)的邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)。

S

?線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類，它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一

個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性

表就是一個(gè)典型的線性結(jié)構(gòu)。

?非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前

趨和直接后繼。

1.2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。

?例如有一張學(xué)生成績表，記錄了一個(gè)班的學(xué)生各門課的成績。按學(xué)生的姓名為一行記成

的表。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號，成績等字段)就是一個(gè)結(jié)點(diǎn)，對

于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其

他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記

錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)。

那么我們怎樣把這個(gè)表中的數(shù)據(jù)存儲到計(jì)算機(jī)里呢？用高級語言如何表示各結(jié)點(diǎn)之間

的關(guān)系呢？是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)

數(shù)據(jù)再用指針進(jìn)行鏈接呢？這就是存儲結(jié)構(gòu)的問題，我們都是從高級語言的層次來討論這個(gè)

問題的。(所以各位趕快學(xué)C語言吧)。

最后，我們有了這個(gè)表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對這張表中的記錄進(jìn)行查

詢，修改，刪除等操作，對這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算

問題了。

1.3常用的存儲表示方法有哪幾種？

常用的存儲表示方法有四種：

?順序存儲方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的

邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。

?鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是

由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。

?索引存儲方法：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。

?散列存儲方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址。

1.4設(shè)三個(gè)函數(shù)fgh分別為f(n)=100nA3+92+1000,g(n)=25nA3+5000nA2,

h(n)=nA1.5+5000nlgn請判斷下列關(guān)系是否成立：

⑴f(n)=O(g(n))

(2)g(n)=O(f(n))

(3)h(n)=O(nA1.5)

(4)h(n)=O(nlgn)

?⑴成立。

?這里我們復(fù)習(xí)一下漸近時(shí)間復(fù)雜度的表示法T(n)=O(f(n)),這里的"O"是數(shù)學(xué)符號，它的嚴(yán)

格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù),則T(n)=0(f(n))表示存在正的常數(shù)

C和nO,使得當(dāng)n^nO時(shí)都滿足OWT(n)WC?f(n)。"用容易理解的話說就是這兩個(gè)函數(shù)當(dāng)整型

自變量n趨向于無窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。這么一來，就好計(jì)算了吧。

第⑴題中兩個(gè)函數(shù)的最高次項(xiàng)都是M3,因此當(dāng)n―8時(shí)，兩個(gè)函數(shù)的比值是一個(gè)常數(shù)，所以

這個(gè)關(guān)系式是成立的。

?(2)成立。

?(3)成立。

?(4)不成立。

1.5設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100M2和2M,要使前者快于后者，

n至少要多大？

S

?15

?最簡單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10,則前者的值是10000,后者的

值是1024,小于前者，那我們就加個(gè)5,用15代入得前者為22500,后者為32768,已經(jīng)比

前者大但相差不多，那我們再減個(gè)1,用14代入得，前者為19600,后者為16384,又比前

者小了，所以結(jié)果得出來就是n至少要是15.

1.6設(shè)n為正整數(shù)，利用大記號，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。

1.6設(shè)n為正整數(shù)，利用大"0"記號，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。

(1)i=l;k=0

while(i{k=k+10*i;i++;

}?T(n)=n-1

T(n)=O(n)

O這個(gè)函數(shù)是按線性階遞增的

⑵i=0;k=0;

do{

k=k+10*i;i++;

)

while(iT(n)=O(n)

O這也是線性階遞增的

⑶i=l；j=0；

while(i+j<=n)

(

if(ielsei++;

)?T(n)=n/2

T(n)=O(n)

?雖然時(shí)間函數(shù)是n/2,但其數(shù)量級仍是按線性階遞增的。

⑷x=n;〃n>l

while(x>=(y+l)*(y+l))

y++;?T(n)=nX*2

T(n)=O(nl?2)

?最壞的情況是y=0,那么循環(huán)的次數(shù)是n磔次，這是一個(gè)按平方根階遞增的函數(shù)。

(5)x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

elsex++;?T(n)=O(l)

O這個(gè)程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到n沒有？沒。這段程

序的運(yùn)行是和n無關(guān)的，就算它再循環(huán)?萬年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。

1.7算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎？

?No,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相

關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時(shí)間復(fù)

雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。

1.8按增長率由小至大的順序排列下列各函數(shù)：2”00,儂)An,(藜)An,n"n,,n!,2An,

Ign,nAlgn,n"(藜)

?分析如下：2八100是常數(shù)階；(羽)即和(轉(zhuǎn))》是指數(shù)階,其中前者是隨n的增大而減小

S

的；n"n是指數(shù)方階；Vn是方根階,n!就是n(n-D(n-2)…就相當(dāng)于n次方階；2An是指

數(shù)階，Ign是對數(shù)階，n7gn是對數(shù)方階,M(M)是初次方階。根據(jù)以上分析按增長率由小至

大的順序可排列如下：

?(羽)An<2Al00<Ign<Vn<nA(^2)<nAlgn<(V2)An<2An<n!<nAn

1.9有時(shí)為了比較兩個(gè)同數(shù)量級算法的優(yōu)劣，須突出主項(xiàng)的常數(shù)因子，而將低次項(xiàng)用大"。"

記號表示。例如，設(shè)Tl(n)=L39nlgn+100n+256=：L.39Mgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+0(n),

這兩個(gè)式子表示，當(dāng)n足夠大時(shí)Tl(n)優(yōu)于T2(n),因?yàn)榍罢叩某?shù)因子小于后者。請用此方

法表示下列函數(shù)，并指出當(dāng)n足夠大時(shí)，哪一個(gè)較優(yōu)，哪一個(gè)較劣？

函數(shù)大"O"表示優(yōu)劣

(1)Tl(n)=5nA2-3n+60lgn.5nA2+O(n).較差

(2)T2(n)=3nA2+1000n+3lgn.3nA2+O(n).其次

(3)T3(n)=8nA2+3lgn.8nA2+O(lgn).最差

(4)T4(n)=1.5nA2+6000nlgn.1.5nA2+O(nlgn).最優(yōu)

第一章概論復(fù)習(xí)要點(diǎn)

本章的復(fù)習(xí)要點(diǎn)是：

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)(包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu))以及數(shù)據(jù)類型的概念、數(shù)據(jù)的邏輯結(jié)

構(gòu)分為哪兩大類，及其邏輯特征、數(shù)據(jù)的存儲結(jié)構(gòu)可用的四種基本存儲方法。

時(shí)間復(fù)雜度與漸近時(shí)間復(fù)雜度的概念，如何求算法的時(shí)間復(fù)雜度。

可能出的題目有選擇題、填空題或簡答題。如：

………是數(shù)據(jù)的基本單位......是具有獨(dú)立含義的最小標(biāo)識單位。

什么是數(shù)據(jù)結(jié)構(gòu)?什么是數(shù)據(jù)類型？

數(shù)據(jù)的.....與數(shù)據(jù)的存儲無關(guān)，它是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的存儲結(jié)構(gòu)包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)............................

設(shè)n為正整數(shù)，利用大0記號，將該程序段的執(zhí)行時(shí)間表示為n的函數(shù)，則下列程序段的

時(shí)間復(fù)雜度可表示為：(.…)

x=91;y=100;

while(y>10)

if(x>100){x=x-10;y-;}

elsex++;

A.0(1)B.0(x)C.O(y)D.O(n)

等等。

順便一提，基本概念和基本理論的掌握是得分的基本手段。

第二章：線性表(包括習(xí)題與答案及要點(diǎn))

本章的重點(diǎn)是掌握順序表和單鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時(shí)間性能分析，難點(diǎn)是使

用本章所學(xué)的基本知識設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。

要求達(dá)到〈識記〉層次的內(nèi)容有:線性表的邏輯結(jié)構(gòu)特征；線性表上定義的基本運(yùn)算，并利用

基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算。

要求達(dá)到〈綜合應(yīng)用〉層次的內(nèi)容有：順序表的含義及特點(diǎn)，順序表上的插入、刪除操作及其

平均時(shí)間性能分析，解決簡單應(yīng)用問題。

鏈表如何表示線性表中元素之間的邏輯關(guān)系；單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別；

單鏈表上實(shí)現(xiàn)的建表、查找、插入和刪除等基本算法及其時(shí)間復(fù)雜度。循環(huán)鏈表上尾指針取

代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應(yīng)算法的異同點(diǎn)。雙鏈表的定義和

相關(guān)算法。利用鏈表設(shè)計(jì)算法解決簡單應(yīng)用問題。

要求達(dá)到〈領(lǐng)會>層次的內(nèi)容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結(jié)構(gòu)才

S

能取得較優(yōu)的時(shí)空性能。

線性表的邏輯結(jié)構(gòu)特征是很容易理解的，如其名，它的邏輯結(jié)構(gòu)特征就好象是一條線，上面

打了?個(gè)個(gè)結(jié)，很形象的，如果這條線上面有結(jié)，那么它就是非空表，只能有一個(gè)開始結(jié)點(diǎn)，

有且只能有一個(gè)終端結(jié)點(diǎn)，其它的結(jié)前后所相鄰的也只能是一個(gè)結(jié)點(diǎn)（直接前趨和直接后

繼）。

關(guān)于線性表上定義的基本運(yùn)算，主要有構(gòu)造空表、求表長、取結(jié)點(diǎn)、查找、插入、刪除等。

線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。在計(jì)算機(jī)中，如何把線性表的結(jié)點(diǎn)存放到存儲單

元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結(jié)構(gòu)次序依次存

放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相

鄰關(guān)系是一致的。

在順序表中實(shí)現(xiàn)的基本運(yùn)算主要討論了插入和刪除兩種運(yùn)算。相關(guān)的算法我們通過練習(xí)掌

握。對于順序表的插入和刪除運(yùn)算，其平均時(shí)間復(fù)雜度均為0（n）。

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結(jié)

點(diǎn)，這組存儲單元可以分布在內(nèi)存中任何位置上。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序

不一定相同。所以為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個(gè)結(jié)點(diǎn)值的同時(shí);還存儲了

其后繼結(jié)點(diǎn)的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。

一個(gè)單鏈表由頭指針的名字來命名。

對于單鏈表，其操作運(yùn)算主要有建立單鏈表（頭插法、尾插法和在鏈表開始結(jié)點(diǎn)前附加?個(gè)

頭結(jié)點(diǎn)的算法）、查找（按序號和按值）、插入運(yùn)算、刪除運(yùn)算等。以上各運(yùn)算的平均時(shí)間復(fù)雜

度均為0（n）.其主要時(shí)間是耗費(fèi)在查找操作上。

循環(huán)鏈表是一種首尾相接的鏈表。也就是終端結(jié)點(diǎn)的指針域不是指向NULL空而是指向開始

結(jié)點(diǎn)（也可設(shè)置一個(gè)頭結(jié)點(diǎn)），形成一個(gè)環(huán)。采用循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)

鏈表。這樣做的好處是查找頭指針和尾指針的時(shí)間都是0（1）,不用遍歷整個(gè)鏈表了。

判別鏈表終止的條件也不同于單鏈表,它是以指針是否等于某一指定指針如頭指針或尾指針

來確定。雙鏈表一般也由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)

鏈表。關(guān)于順序表和鏈表的比較，請看下表：具體要求順序表鏈表

基于空間適于線性表長度變化不大，易于事先確定其大小時(shí)采用。適于當(dāng)線性表長度變化

大，難以估計(jì)其存儲規(guī)模時(shí)采用。

基于時(shí)間由于順序表是一種隨機(jī)存儲結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用。鏈表

中對任何位置進(jìn)行插入和刪除都只需修改指針，所以這類操作為主的線性表宜采用鏈表做存

儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。

第二章線性表習(xí)題及答案

一、基礎(chǔ)知識題

（答案及點(diǎn)評）2.1試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。

一、基礎(chǔ)知識題

2.1答：

開始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，也就是沒有直接前趨的那個(gè)結(jié)點(diǎn)。

鏈表的頭指針是一指向鏈表開始結(jié)點(diǎn)的指針（沒有頭結(jié)點(diǎn)時(shí)），單鏈表由頭指針唯一確定，因

此單鏈表可以用頭指針的名字來命名。

頭結(jié)點(diǎn)是我們?nèi)藶榈卦阪湵淼拈_始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向

頭結(jié)點(diǎn)，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對鏈表的第一個(gè)位置上

的操作與在表其他位置上的操作一致（都是在某一結(jié)點(diǎn)之后）。

（答案及點(diǎn)評）2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲結(jié)構(gòu)為宜？

2.2答：

s

在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，

通常有以下幾方面的考慮：

1.基于空間的考慮。當(dāng)要求存儲的線性表長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約

存儲空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲規(guī)模時(shí)，采用動態(tài)

鏈表作為存儲結(jié)構(gòu)為好。

2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序

表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈

表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的

單循環(huán)鏈表為宜。

(答案及點(diǎn)評)2.3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動多少個(gè)結(jié)點(diǎn)?具體的移動次數(shù)

取決于哪兩個(gè)因素？

23答：在等概率情況下，順序表中插入一個(gè)結(jié)點(diǎn)需平均移動個(gè)結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)需

平均移動(n-l)2個(gè)結(jié)點(diǎn)。具體的移動次數(shù)取決于順序表的長度n以及需插入或刪除的位置io

i越接近n則所需移動的結(jié)點(diǎn)數(shù)越少。

(答案及點(diǎn)評)2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？

2.4.答：尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)

點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear,則開始結(jié)點(diǎn)和終端

結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是。(1)。

若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為0(n)。

(答案及點(diǎn)評)2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道

頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時(shí)間復(fù)雜度各為多少？

2.5答：我們分別討論三種鏈表的情況。

1.單鏈表。當(dāng)我們知道指針P指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到其直接后繼，但是由于

不知道其頭指針，所以無法訪問到p指針指向的結(jié)點(diǎn)的直接前趨。因此無法刪去該結(jié)點(diǎn)。

2.雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點(diǎn)可以查找到其直接前趨和直

接后繼，從而可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為。(1)。

3.單循環(huán)鏈表。根據(jù)已知結(jié)點(diǎn)位置，我們可以直接得到其后相鄰的結(jié)點(diǎn)位置(直接后繼)，又

因?yàn)槭茄h(huán)鏈表，所以我們可以通過查找，得到p結(jié)點(diǎn)的直接前趨。因此可以刪去p所指結(jié)

點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為。(n)。

(答案及點(diǎn)評)2.6下述算法的功能是什么？

LinkListDemo(LinkListL){//L是無頭結(jié)點(diǎn)單鏈表

ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

)

returnL;

}//Demo

二、算法設(shè)計(jì)題

(答案及點(diǎn)評)2.7設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(aO,al,...an-l),重寫順序表上實(shí)現(xiàn)的插入和刪

除算法：InsertList和DeleteList.</P<p>

二、算法設(shè)計(jì)題：

2.7(本題感謝pastar的指正)

S

解：

算法如下：

#defineListSize100//假定表空間大小為100

include

tfinclude

voidError(char*message)

(

fprintf(stderr/錯(cuò)誤:%s\n”,message);

exit(l);

}〃從0開始計(jì)，表空間大小應(yīng)為101了

typedefintDatatype;〃假定Datatype的類型為int型

typedefstruct{

Datatypedata[ListSize];//向量data用于存放表結(jié)點(diǎn)

intlength;//當(dāng)前的表長度

}Seqlist;

〃以上為定義表結(jié)構(gòu)

//-------以下為要求算法------

voidInsertList(Seqlist*L,Datatypex,inti)

(

〃將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上

intj;

if(i<011i>L->length)

Error("positionerror";//非法位置,退出

if(L->length>=ListSize)

Error("overflow";

for(j=L->length-l;j>=i;j-)

L->data[j+l]=L->data[j];

L->data=x;

L->length++;

)

voidDeleteList(Seqlist*L,inti)

{//從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)ai

intj;

if(i<011i>L->length-1)

Error("positionerror");

for(j=i+1;j<L->length;j++)

L->data[j-1]=L->data[j];//結(jié)點(diǎn)前移

L->length-;〃表長減小

)

〃===========以下為驗(yàn)證算法而加=======

voidlnitlist(Seqlist*L)

(

L->length=0;

)

s

voidmain()

(

Seqlist*SEQA=newSeqlist;

Initlist(SEQA);

inti;

for(i=0;i{

InsertList(SEQAJJ);

printf("%d\n",SEQA->data);

)

DeleteList(SEQA,99);

for(i=0;i{

printf("%d\n"zSEQA->data);

}

)

(答案及點(diǎn)評)2.8試分別用順序表和單鏈表作為存儲結(jié)構(gòu)，實(shí)現(xiàn)將線性表(aO,al,...an-l)就地

逆置的操作，所謂"就地"指輔助空間應(yīng)為0(1)。

2.8解：按題意，為將線性表逆置，但輔助空間不能隨表的規(guī)模增大。我們分別討論順序表

和單鏈表的情況：

1.順序表：

要將該表逆置，可以將表中的開始結(jié)點(diǎn)與終端結(jié)點(diǎn)互換，第二個(gè)結(jié)點(diǎn)與倒數(shù)第二個(gè)結(jié)點(diǎn)互換，

如此反復(fù)，就可將整個(gè)表逆置了。算法如下：

//表結(jié)構(gòu)定義同上

voidReverseList(Seqlist*L)

(

Datatypet;〃設(shè)置臨時(shí)空間用丁?存放data

inti;

for(i=0;i<L->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ù)的方式來達(dá)到逆置的目的，但是由于是單鏈表，數(shù)據(jù)的存取不是隨機(jī)的,

因此算法效率太低，我們可以利用指針的指向轉(zhuǎn)換來達(dá)到表逆置的目的。算法是這樣的：

//結(jié)構(gòu)定義略

LinkListReverseList(LinkListhead)

(

//將head所指的單鏈表逆置

ListNode*p產(chǎn)q;〃設(shè)置兩個(gè)臨時(shí)指針變量

if(head->next&&head->next->next)

(

〃當(dāng)鏈表不是空表或單結(jié)點(diǎn)時(shí)

s

p=head->next;

q=p->next;

p->next=NULL;〃將開始結(jié)點(diǎn)變成終端結(jié)點(diǎn)

while(q)

{//每次循環(huán)將后一個(gè)結(jié)點(diǎn)變成開始結(jié)點(diǎn)

p=q;

q=q->next;

p->next=head->next;

head->next=p;

)

returnhead;

)

returnhead;〃如是空表或單結(jié)點(diǎn)表，直接返回head

}

(答案及點(diǎn)評)2.9設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是

一個(gè)有序表。

2.9解：因已知順序表L是遞增有序表，所以只要從頭找起找到第一個(gè)比它大(或相等)的結(jié)

點(diǎn)數(shù)據(jù)，把x插入到這個(gè)數(shù)所在的位置就是了。算法如下：

voidlnsertlncreaseList(Seqlist*L,Datatypex)

(

inti;

for(i=0;i<L->length&&L->data[i]<x;i++);//查找并比較，分號不能少

InsertList(L,x,i);//調(diào)用順序表插入函數(shù)

}

(答案及點(diǎn)評)2.10設(shè)順序表L是一個(gè)遞減有序表，試寫一算法，將x插入其后仍保持L的有

序性。

2.10解：

與上題相類似，只要從頭找到第一個(gè)比x小(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。

算法如下：

voidlnsertDecreaseList(Seqlist*L,Datatypex)

(

inti;

for(i=0;i<L->length&&L->data>x;i++);〃查找

InsertList(L,x,i);//調(diào)用順序表插入函數(shù)

)

(答案及點(diǎn)評)2.11寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。

2.11解：

求單鏈表長只能用遍歷的方法了，從頭數(shù)到尾，總能數(shù)出來吧。算法如下：

intListLength(LinkListL)

(

intlen=0;

ListNode*p;

p=L;〃設(shè)該表有頭結(jié)點(diǎn)

while(p->next)

s

p=p->next;

len++;

)

returnlen;

)

(答案及點(diǎn)評)2.12已知LI和L2分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn),且己知其長度分別為m和n。

試寫一算法將這兩個(gè)鏈表連接在一起，請分析你的算法的時(shí)間復(fù)雜度。

2.12解：

算法如下：

LinkListLink(LinkListLI,LinkListL2)

(

〃將兩個(gè)單鏈表連接在一起

ListNode*p,*q;

P=L1;

q=L2;

while(p->next)p=p->next;〃查找終端結(jié)點(diǎn)

p->next=q->next;〃將L2的開始結(jié)點(diǎn)鏈接在L1之后

returnL1;

}

本算法的主要操作時(shí)間花費(fèi)在查找L1的終端結(jié)點(diǎn)上，與L2的長度無關(guān)，所以本算的法時(shí)間

復(fù)雜度為：

m+l=O(m)

(答案及點(diǎn)評)2.13設(shè)A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸

并成一個(gè)按元素值遞減有序的單鏈表C,并要求輔助空間為0(1),請分析算法的時(shí)間復(fù)雜度。

2.13解：

根據(jù)已知條件，A和B是兩個(gè)遞增有序表，所以我們可以以A表為基礎(chǔ)，按照插入單個(gè)元素

的辦法把B表的元素插入A表中，完成后，將表逆置就得到了一個(gè)按元素值遞減有序的單

鏈表C了。

算法如下：

LinkListMergeSort(LinkListA,LinkListB)

(

//歸并兩個(gè)遞增有序表為一個(gè)遞減有序表</P<p>

ListNode*pa,*pb,*qa,*qb;

pa=A;

pb=B;

qa=A->next;

qb=B->next;

while(qa&&qb)

(

if(qb->data<qa->data)

(

//當(dāng)8中的元素小于A中當(dāng)前元素時(shí)，插入到它的前面

pb=qb;

s

qb=qb->next;//指向B中下一元素

pa->next=pb;

pb->next=qa;

pa=pb;

)

elseif(qb->data>=pa->data&&qb->data<=qa->data)

(

//當(dāng)B中元素大于等于A中當(dāng)前元素

//且小于等于A中后一元素時(shí)，

//將此元素插入到A的當(dāng)前元素之后

pa=qa;

qa=qa->next;〃保存A的后一元素位置

pb=qb;

qb=qb->next;//保存B的后一元素位置

pa->next=pb;〃插入元素

pb->next=qa;

)

else

(

//如果B中元素總是更大，指針移向下一個(gè)A元素

pa=qa;

qa=qa->next;

)

)

if(qb)//如果A表已到終端而B表還有結(jié)點(diǎn)未插入

(

〃將B表接到A表后面

pa->next=qb;

)

LinkListC=ReverseList(A);//調(diào)用前面2.8題所設(shè)計(jì)的逆置函數(shù)

returnC;〃返回新的單鏈表C,已是遞減排列

該算法的時(shí)間復(fù)雜度分析如卜：

算法中只有一個(gè)while循環(huán)，在這個(gè)循環(huán)中，按照最壞的情況是B元素既有插到A的最前

的，也有插到最后的，也就是說需要把A中元素和B中元素全部檢查比較過，這時(shí)的所費(fèi)

時(shí)間就是m+n.而新鏈表的長度也是m+n+1(有頭結(jié)點(diǎn))，這樣逆置函數(shù)的執(zhí)行所費(fèi)時(shí)間為

m+n+1.所以可得整個(gè)算法的時(shí)間復(fù)雜度為：

m+n+m+n+l=2(m+n)+l=O(m+n)

為驗(yàn)證本題，曉津設(shè)計(jì)了一個(gè)程序，清單如下：

//ListStruct.h將鏈表結(jié)構(gòu)存為頭文件

typedefcharDataType;〃假設(shè)結(jié)點(diǎn)的數(shù)據(jù)類型是字符型

typedefstructnode{〃結(jié)點(diǎn)類型定義

DataTypedata;

s

structnode*next;〃結(jié)點(diǎn)的指針域

}UstNode;

typedefListNode*LinkList;

//以下是源文件〃在VC++中運(yùn)行通過。

tfinclude

include

include"ListStruct.h"

ttinclude

LinkListCreatList(void)

{〃用尾插法建立帶頭結(jié)點(diǎn)的單鏈表

charch;

LinkListhead=(LinkList)malloc(sizeof(ListNode));〃生成頭結(jié)點(diǎn)

ListNode*sz*r;

r=head;〃尾指針亦指向頭結(jié)點(diǎn)

while((ch=getchar())!='\n')

(

s=(ListNode*)malloc(sizeof(ListNode));

s->data=ch;

r->next=s;

r=s;

)

r->next=NULL;

returnhead;

)

voidOutList(LinkListL)

(

ListNode*p;

P=L；

while(p->next)

(

cout?p->next->data?"";

p=p->next;

}

cout?endl;

)

LinkListReverseList(LinkListhead)

(

//將head所指的單鏈表逆置

ListNode*p,*q；〃設(shè)置兩個(gè)臨時(shí)指針變量

if(head->next&&head->next?>next)〃當(dāng)鏈表不是空表或單結(jié)點(diǎn)時(shí)

{

p=head->next;

q=p->next;

p->next=NULL;〃將開始結(jié)點(diǎn)變成終端結(jié)點(diǎn)

s

while(q)

{//每次循環(huán)將后一個(gè)結(jié)點(diǎn)變成開始結(jié)點(diǎn)

p=q;

q=q->next;

p->next=head->next;

head->next=p;

)

returnhead;

)

returnhead;〃直接返回head

}

LinkListMergeSort(LinkListA,LinkListB)

(

//歸并兩個(gè)遞增有序表為一個(gè)遞減有序表

ListNode*pa,*pb,*qa,*qb;

pa=A;

pb=B;

qa=A->next;

qb=B->next;

while(qa&&qb)

(

if(qb->data<qa->data)

(

//當(dāng)B中的元素小于A中當(dāng)前元素時(shí)，插入到它的前面

pb=qb;

qb=qb->next;//指向B中下一元素

pa->next=pb;

pb->next=qa;

pa=pb;

)

elseif(qb->data>=pa->data&&qb->data<=qa->data)

(

//當(dāng)B中元素大于等于A中當(dāng)前元素

//且小于等于A中后一元素時(shí)，

//將此元素插入到A的當(dāng)前元素之后

pa=qa;

qa=qa->next;//保存A的后一元素位置

pb=qb;

qb=qb->next;//保存B的后一元素位置

pa->next=pb;〃插入元素

pb->next=qa;

)

else

s

//如果B中元素總是更大，指針移向下一個(gè)A元素

pa=qa;

qa=qa->next;

}

)

if(qb)//如果A表已到終端而B表還有結(jié)點(diǎn)未插入

(

//將B表接到A表后面

pa->next=qb;

)

LinkListC=ReverseList(A);//調(diào)用前面2.8題所設(shè)計(jì)的逆置函數(shù)

returnC;〃返回新的單鏈表C,已是遞減排列

}

voidmain()

(

LinkListA,B,C;

A=CreatList();

OutList(A);

B=CreatList();

OutList(B);

C=MergeSort(A,B);

OutList(C);

}(答案及點(diǎn)評)2.14已知單鏈表L是一個(gè)遞增有序表，試寫一高效算法，刪除表中值大于

min且小于max的結(jié)點(diǎn)(若表中有這樣的結(jié)點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)的客，這里min和max

是兩個(gè)給定的參數(shù)。請分析你的算法的時(shí)間復(fù)雜度。

2.14解：

要解這樣的問題，我們首先想到的是拿鏈表中的元