數(shù)據(jù)結(jié)構(gòu)概論自考講義

課程介紹

一、課程性質(zhì)、教學(xué)目標(biāo)

《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》課程是高等教育自學(xué)考試計(jì)算機(jī)及應(yīng)用專業(yè)（?？疲┑囊婚T

重要的專業(yè)基礎(chǔ)課。用計(jì)算機(jī)解決任何實(shí)際問題都離不開數(shù)據(jù)表示和數(shù)據(jù)處理，而

數(shù)據(jù)的表示和處理的核心問題之一是數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)-這是本課程的基本內(nèi)容。

從這個(gè)意義上說，數(shù)據(jù)結(jié)構(gòu)課程在知識學(xué)習(xí)和技能培養(yǎng)兩個(gè)方面都處于關(guān)鍵性地

位。

本課程的先修課程為高級語言程序設(shè)計(jì)；后續(xù)課程有數(shù)據(jù)庫及其應(yīng)用、操作系

統(tǒng)概論等課程。

本課程的教學(xué)目標(biāo)是使學(xué)生能夠：

1.理解數(shù)據(jù)結(jié)構(gòu)課程與其他課程的關(guān)系；

2.理解數(shù)據(jù)結(jié)構(gòu)基本概念，掌握幾種常用數(shù)據(jù)結(jié)構(gòu)的特征；

3.學(xué)會如何選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)的方法，為進(jìn)一步從事軟件設(shè)

計(jì)工作奠定基礎(chǔ)。

二、指定教材

本課程所用教材《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》是由鄭誠主編，20XX年4月第X版，20XX

年4月第X次印刷，外語教學(xué)與研究出版社出版。

三、新舊教材變化情況說明

新教材與舊教材相比，集中在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識的介紹，內(nèi)容較少了一些，增

強(qiáng)了結(jié)構(gòu)應(yīng)用的討論。具體有以下幾個(gè)方面的增減：

1.去掉了舊教材第一章中"數(shù)據(jù)結(jié)構(gòu)評價(jià)與選擇"的內(nèi)容；

2.去掉了舊教材第二章中"串"的內(nèi)容；

3.簡化了第六章中散列表的討論；

4,去掉了舊教材第六章中"平衡二叉排序樹”的內(nèi)容；

5.去掉了舊教材中"文件"這一章；

6.在第四章突出了"哈夫曼編碼”的內(nèi)容。

四、課程體系

基本被鍬一第一直概論

〔遺鐐觸

r第二^性表3

L第三登技.隊(duì)列和輜騫本運(yùn)算］

W卜實(shí)現(xiàn)運(yùn)齦

何籍抽謗

樹形觸—第四章樹和二叉樹

圖第構(gòu)-_'第五篇:圖」I或

工,常見解

H的殺查我服務(wù)

“第七章排序

五、本課程的學(xué)習(xí)方法

理清課程的基本脈絡(luò)，通過類比的方法進(jìn)行學(xué)習(xí)將會有較好的效果。本課程內(nèi)

容較為規(guī)整，對每種數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)基本都可按照以下步驟進(jìn)行：

1.學(xué)習(xí)該結(jié)構(gòu)的邏輯結(jié)構(gòu)，清楚數(shù)據(jù)元素間的邏輯關(guān)系；

2.了解該結(jié)構(gòu)下的所有基本運(yùn)算功能；

3.研究該結(jié)構(gòu)的幾種存儲結(jié)構(gòu)，主要是順序存儲和鏈?zhǔn)酱鎯纱箢悾?/p>

4.研究不同存儲結(jié)構(gòu)下基本運(yùn)算的實(shí)現(xiàn)并進(jìn)行簡單的算法分析；

5.了解該結(jié)構(gòu)的典型應(yīng)用。

所以我們在學(xué)習(xí)的過程中，要逐步學(xué)會通過類比，加以歸納、總結(jié)，從而找出

它們之間的相同點(diǎn)和不同點(diǎn)。這樣有助于加深對整個(gè)課程的理解，并且在腦海中逐

步形成一個(gè)完整的體系。

六、考情分析

（一）、新考綱說明

令考試方式：閉卷筆試150分鐘；

令題型：填空、單項(xiàng)選擇題、應(yīng)用題、算法設(shè)計(jì)題

令難度分布：易（20%）、較易（30%）、較難（30%）、難（20%）

（二）、往年（舊考綱）的題型分布

令單項(xiàng)選擇題（共15小題，每小題2分，共30分）

令填空題（共13小題，每小題2分，共26分）

令應(yīng)用題（共5小題，每小題6分，共30分）

令算法設(shè)計(jì)題（共2小題，每小題7分，共14分）

第一章概論本章概覽

一、知識結(jié)構(gòu)

T跪E領(lǐng)］

一［泰制儲：

T/列眼:

二、本章重難點(diǎn)

重點(diǎn)：數(shù)據(jù)、數(shù)據(jù)元素和唾項(xiàng)的概念及關(guān)系；數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)的邏輯結(jié)構(gòu);

數(shù)據(jù)的物理結(jié)構(gòu)；順序存儲和鏈?zhǔn)酱鎯Φ奶攸c(diǎn)；算法時(shí)間復(fù)雜度。

難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)、算法時(shí)間復(fù)雜度。

主要題型：單項(xiàng)選擇題，填空題。

往年分值：4-8分

第一節(jié)引言

一、電子計(jì)算機(jī)的主要用途

?早期-數(shù)值計(jì)算

?后來--主要用來處理非數(shù)值領(lǐng)域的計(jì)算問題

二、數(shù)值計(jì)算問題解決的一般步驟

令數(shù)學(xué)模型一設(shè)計(jì)算法T編程一調(diào)試

令數(shù)值計(jì)算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？

令程序設(shè)計(jì)人員匕蹴關(guān)注程序設(shè)計(jì)的技巧。

令例如求解一元二次方程的解

三、非數(shù)值計(jì)算問題解決的一般步驟

令數(shù)據(jù)模型（給出數(shù)據(jù)結(jié)構(gòu)）T設(shè)計(jì)算法一編程一調(diào)試

令解決問題的關(guān)鍵:首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？

?例如：學(xué)生檔案管理問題。將數(shù)據(jù)組織成表格,并存儲在計(jì)算機(jī)中。

?例如：地圖著色問題。將數(shù)據(jù)組織成平面圖，并存儲在計(jì)算機(jī)中。

四、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？

令數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它

們之間的關(guān)系和操作的學(xué)科。

第二節(jié)基本概念和術(shù)語

一、數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)

?數(shù)據(jù)：凡能被計(jì)算機(jī)存儲、加工處理的又嫁。

令數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體而加以考慮和處理。

，數(shù)據(jù)元素是運(yùn)算的基本單位，常簡稱為元素，也稱為結(jié)點(diǎn)。

?數(shù)據(jù)項(xiàng)：又叫字段或域，它是數(shù)據(jù)的不可分割的最小標(biāo)識單位。

令三者關(guān)系：數(shù)據(jù)由若干數(shù)據(jù)元素組成；數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。

二、數(shù)據(jù)結(jié)構(gòu)

令是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

令包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)的操作（運(yùn)算）。

三、數(shù)據(jù)的邏輯結(jié)構(gòu)

令是指數(shù)據(jù)元素之間的邏輯關(guān)系。

令數(shù)據(jù)元素間邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系"。

令四類基本邏輯結(jié)構(gòu)：

，集合：任何兩個(gè)結(jié)點(diǎn)之間都沒有邏輯關(guān)系，組織形式松散；

，線性結(jié)構(gòu)：結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鏈"；

，樹形結(jié)構(gòu)：具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹；

，圖結(jié)構(gòu)：最復(fù)雜，任何兩個(gè)結(jié)點(diǎn)都可以鄰接。

四、數(shù)據(jù)的存儲結(jié)構(gòu)

令是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)。也稱為數(shù)據(jù)的物理結(jié)構(gòu)。

令同一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)。

令一個(gè)存儲結(jié)構(gòu)包括兩個(gè)部分：存儲的數(shù)據(jù)元素；數(shù)據(jù)元素之間的關(guān)聯(lián)方式。

令存儲結(jié)構(gòu)包括四種常見存儲方式：

，順序存儲方式：將數(shù)據(jù)結(jié)構(gòu)中各元素按照其邏輯順序存放于存儲器一片連

續(xù)的存儲空間中，利用結(jié)點(diǎn)在存儲器中的相對位置表示數(shù)據(jù)元素間的邏輯關(guān)系。

，鏈?zhǔn)酱鎯Ψ绞剑好總€(gè)存儲結(jié)點(diǎn)出了包含一個(gè)數(shù)據(jù)元素外，還包含一個(gè)或多

個(gè)指針，指向與本結(jié)點(diǎn)有邏輯關(guān)系的結(jié)點(diǎn)，利用指針表示數(shù)據(jù)元素間的邏輯關(guān)系。

/索引存儲方式：在存儲數(shù)據(jù)的同時(shí)，建立一個(gè)附加的索引表，即索引存儲

結(jié)構(gòu)=數(shù)據(jù)文件+索引表。

，散列存儲方式：根據(jù)數(shù)據(jù)元素的特殊字段（稱為關(guān)鍵字key）,計(jì)算數(shù)據(jù)元

素的存放地址，然后數(shù)據(jù)元素按地址存放。

五、運(yùn)算

令指在邏輯結(jié)構(gòu)上施加的操作。

令運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而具體實(shí)現(xiàn)是在存儲結(jié)構(gòu)上進(jìn)行的。

?每個(gè)邏輯結(jié)構(gòu)上都定義了一組基本運(yùn)算，包括：建立、查找、插入、刪除

等。

六、考點(diǎn)提示

1.數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)間的關(guān)系

【例題?填空題】從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)，數(shù)據(jù)通?？煞譃槿齻€(gè)層次，即：數(shù)據(jù)、數(shù)

據(jù)元素和O

隱藏答案

【答案】■項(xiàng)

【解析】■由若干數(shù)據(jù)元素組成;數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。

2.數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的概念

【例題?單選題】要將現(xiàn)實(shí)生活中的數(shù)據(jù)轉(zhuǎn)化為計(jì)算機(jī)所能表示的形式，其轉(zhuǎn)化

過程依次為（）。

A.邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、機(jī)外表示

B.存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)、機(jī)外表示

C.機(jī)外表示、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)

D才幾外表示、存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)

隱藏答案

【答案】C

【解析】要將現(xiàn)實(shí)生活中的數(shù)據(jù)轉(zhuǎn)化為計(jì)算機(jī)所能表示的形式，首先考慮其機(jī)

外表示，然后抽象其邏輯結(jié)構(gòu)，最后確定其物理結(jié)構(gòu)。

第三節(jié)算法及描述

一、算法的概念

令算法是指規(guī)定了求解給定類型問題所需的處理步驟及其執(zhí)行111頁序，使得給定

問題能在有限時(shí)間內(nèi)被求解。

二、算法的描述

?算法用某種語言加以描述；在此用類C語言來描述算法。

第四節(jié)算法分析

一、評價(jià)算法的質(zhì)量

?正確性：正確地實(shí)現(xiàn)預(yù)定的功能。

令易讀性：易于閱讀、理解和交流，便于調(diào)試、修改和擴(kuò)充。

令健壯性：即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會產(chǎn)

生預(yù)料不到的運(yùn)行結(jié)果。

令時(shí)空性：是指該算法的時(shí)間性能和空間性能。

二、算法的時(shí)間復(fù)雜度

令時(shí)間復(fù)雜度T(n):是該算法的時(shí)間耗費(fèi)，是求解問題規(guī)模n的函數(shù)，這里用

T(n)表示。

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，是算法中所有語句執(zhí)行時(shí)間之和，而每條語句的

執(zhí)行時(shí)間是該語句執(zhí)行一次所用時(shí)間與該語句重復(fù)執(zhí)行次數(shù)的乘積。一個(gè)語句重復(fù)

執(zhí)行的次數(shù)稱為語句的頻度。

V(txG)

算法的時(shí)間復(fù)雜度T(n)表示為：H

其中ti表示語句i執(zhí)行一次的時(shí)間，ci表示語句i的頻度。

假設(shè)每條語句執(zhí)行一次的時(shí)間均為一個(gè)單位時(shí)間，那么算法的時(shí)間耗費(fèi)可簡單

T(/￡)二￡Q

表示為各語句的頻度之和：語郁

下面的程序段用來求兩個(gè)n階方陣A和B的乘積Co

for(i=0;i<n;i++)/*n+1*/

for(j=0;j<n;j++)/*n(n+l)*/

{C[i][j]=O;/*n2*/

for(k=0;k<n;k++)/*n2(n+l)*/

C[i][j]=A[i][k]*B[k]|j];/*n^*/

)

右邊列出了各語句的頻度，因而算法的時(shí)間復(fù)雜度T(n)為：

T(n)=(n+1)+n(n+l)+n2+n2(n+l)+n3=2n3+3n2+2n+l

可見，T(n)是矩陣階數(shù)n的函數(shù)。

而許多時(shí)候要精確地計(jì)算T(n)是困難的，很多算法的時(shí)間復(fù)雜度難以給出解析

形式，或者非常復(fù)雜。而且當(dāng)問題的規(guī)模較大時(shí)，T(n)表達(dá)式中有些項(xiàng)占主導(dǎo)地

位，其它項(xiàng)可忽略不計(jì)。例如在上面的情況中，當(dāng)n很大時(shí)，T(n)中起主導(dǎo)作用的

是高次項(xiàng)"22”,顯然：

T(n)與2是同數(shù)量級的，T(n)可近似的用rP來表示。

因此在實(shí)際應(yīng)用中，往往放棄復(fù)雜的函數(shù)來表示確切的時(shí)間復(fù)雜度，而采用一

些簡單的函數(shù)來近似表示時(shí)間性能，這就是時(shí)間漸進(jìn)復(fù)雜度。

?大0表示法：設(shè)T(n)是問題規(guī)模n的函數(shù)f(n),若存在兩個(gè)正常數(shù)c和nO,

使得對所有的n,nNnO,有：T(n)<cf(n),則記為:T(n)=O(f(n))

例如，一個(gè)程序的實(shí)際執(zhí)行時(shí)間為T(n)=20rl3+25M+9,貝［JT(n)=0(東)。

使用大。記號表示的算法的時(shí)間復(fù)雜度，稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)

間復(fù)雜度。

令如何確定時(shí)間復(fù)雜度(漸近時(shí)間復(fù)雜度)

/for循環(huán)：一次for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語句的運(yùn)行時(shí)間乘

以迭代次數(shù)。

，嵌套的for循環(huán)：從里向外分析，最內(nèi)層一條語句總的運(yùn)行時(shí)間為該語句

的運(yùn)行時(shí)間乘以該組所有for循環(huán)的大小的乘積。

"質(zhì)序語句：將各個(gè)語句求和。

，IF/ELSE語句：判斷加上運(yùn)行時(shí)間長者分支時(shí)間的總和。

令通常用0(1)表示常數(shù)計(jì)算時(shí)間。常見的漸進(jìn)時(shí)間復(fù)雜度按數(shù)量級遞增排列

為：

23n

O(l)<O(log2n)<O(n)<O(nlog2n)<O(n)<O(n)<O(2)

x=x+l;s=0;--------算法時(shí)間復(fù)雜度：0(1)

for(i=l;i<=n;i++)

{x=x+l;

s=s+x;

}------算法時(shí)間復(fù)雜度：0(n)

for(i=l;i<=n;i++)

for(j=l;j<=n;j++)

{x=x+l;

s=s+x;

}------算法時(shí)間復(fù)雜度：0(n2)

三、算法的空間復(fù)雜度

令存儲量主要包括:輸入/輸出、程序本身、輔助變量

令S(n):是該算法的空間耗費(fèi)，是求解問題規(guī)模n的函數(shù)。

s(n)=O(g(n))

，g(n)不是指算法中指令、常數(shù)、變量和輸入數(shù)據(jù)所占內(nèi)存的量，而是指

為了對數(shù)據(jù)進(jìn)行操作而設(shè)置的工作單元的內(nèi)存量。

四、考點(diǎn)提示

1.算法的時(shí)間復(fù)雜度估算

精確地計(jì)算一個(gè)算法的執(zhí)行時(shí)間意義不大，因此求解時(shí)間復(fù)雜度的便捷辦法：

找出執(zhí)行頻度最大的語句，將它的語句頻度的數(shù)量級放入大0的括號中。

【例題?填空題】下列程序段的時(shí)間復(fù)雜度為O

i=l；

while(i<n)

i=i*2;

隱藏答案

【答案】O(log2n)

【解析】執(zhí)行頻度最大的是i=i*2,執(zhí)行的數(shù)量級是log2n,因此時(shí)間復(fù)雜度為

O(log2n)o

2.不同數(shù)量級時(shí)間復(fù)雜度的關(guān)系

本章典型考題

【例題?填空題】數(shù)據(jù)的存儲結(jié)構(gòu)被分為111頁序存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)

和索引存儲結(jié)構(gòu)4種。

隱藏答案

【答案】鏈?zhǔn)酱鎯Y(jié)構(gòu)

【解析】存儲結(jié)構(gòu)包括四種常見存儲方式：順序存儲方式、鏈?zhǔn)酱鎯Ψ绞?、?/p>

引存儲方式和散列存儲方式；四種存儲方式對應(yīng)四種存儲結(jié)構(gòu)。

【例題?填空題】在數(shù)據(jù)結(jié)構(gòu)中，各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任意兩個(gè)結(jié)點(diǎn)

可以鄰接的結(jié)構(gòu)稱為O

隱藏答案

【答案】圖結(jié)構(gòu)

【解析】圖結(jié)構(gòu)最復(fù)雜，任何兩個(gè)結(jié)點(diǎn)都可以鄰接。

【例題?單選題】程序段i=n;x=0;

do{x=x+5*i;i—;}while(i>0);

的時(shí)間復(fù)雜度為()

A.O(l)B.O(n)C.O(n2)D.O(n3)

隱藏答案

【答案】B

【解析】執(zhí)行頻度最大的是x=x+5*i，執(zhí)行的數(shù)量級是n,所以時(shí)間復(fù)雜度為

第二章線性表本章概覽

一、知識結(jié)構(gòu)

定義，樓點(diǎn)，運(yùn)茸

1

話苴實(shí)攥

算法分析

忙|錐式存輔結(jié)構(gòu)上

二、本章重難點(diǎn)

重點(diǎn)：線性表的定義及邏輯特點(diǎn)；順序表上插入、刪除和定位運(yùn)算的實(shí)現(xiàn)；單

鏈表的結(jié)構(gòu)特點(diǎn)及類型說明；頭指針和頭結(jié)點(diǎn)的作用及區(qū)別；定位、刪除、插入運(yùn)

算在單鏈表上的實(shí)現(xiàn)；循環(huán)鏈表、雙鏈表的結(jié)構(gòu)特點(diǎn)，循環(huán)鏈表、雙鏈表上刪除與

插入運(yùn)算的實(shí)現(xiàn)。

難點(diǎn)：頭結(jié)點(diǎn)在鏈表中的作用、指針操作；刪除、插入運(yùn)算中的指針操作順

序；雙鏈表上指針的操作順序。

主要題型：單項(xiàng)選擇，填空，算法設(shè)計(jì)題。應(yīng)用題偶爾出現(xiàn)。

往年分值：6-15分

第一節(jié)線性表的基本概念

一、線性結(jié)構(gòu)

令是n(n“)個(gè)數(shù)據(jù)元素(也稱結(jié)點(diǎn))的有窮序列。

?線性結(jié)構(gòu)的基本特征：

，若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接前趨外，其他結(jié)點(diǎn)有且僅有一

個(gè)直接前趨；

，除終端節(jié)點(diǎn)沒有直接后繼外，其他結(jié)點(diǎn)有且僅有一個(gè)直接趣

二、線性表的定義

令線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。是n(n20)個(gè)結(jié)點(diǎn)的有窮序

列。

令結(jié)點(diǎn)個(gè)數(shù)n稱為表長。

令n=0時(shí),稱為空表，記為()或中。

令n>0時(shí)，表示成:

(ai,821...an)

其中：ai稱為起始結(jié)點(diǎn)；an稱為終端結(jié)點(diǎn)；對任意一對相鄰結(jié)點(diǎn)ai和ai+i,將

ai稱為ai+i的直接前趨，ai+i稱為ai的直接后繼。

令對于3，當(dāng)i=2，…，n時(shí)，有且僅有一個(gè)直接前趨ai-i，當(dāng)i=l,2,n-

1時(shí)，有且僅有一個(gè)直接后繼ai+i,而ai是表中第一個(gè)元素，它沒有前趨，而是

最后一個(gè)元素?zé)o后繼。

令需要說明的是：ai為序號為i的數(shù)據(jù)元素(i=l,2,...,n),通常我們將它的數(shù)

據(jù)類型抽象為datatype,datatype根據(jù)具體問題而定。

令如在學(xué)生情況信息表中，它是用戶自定義的學(xué)生類型；在字符串中，它是字

符型；等等。

三、線性表的基本運(yùn)算

令初始化Initiate(L):建立一個(gè)空表L=(),L不含數(shù)據(jù)元素。

?求表長Length(L):返回線性表L的長度

令讀表元素Get(L,i):返回線性表L的第i個(gè)數(shù)據(jù)元素，當(dāng)i不滿足l<i<

Length(L)時(shí)，返回一特殊值。

令定位(按值查找)Located,x):查找線性表中數(shù)據(jù)元素等于x的結(jié)點(diǎn)序

號，返回找到的結(jié)點(diǎn)集合中序號的最小值，否則返回值為0(說明沒有找到)

令插入Insert(L,x,i):在線性表L的第i個(gè)位置上增加一個(gè)值為x的新結(jié)

點(diǎn)(整個(gè)表長+1)，參數(shù)i的合法取值范圍是lwiwn+l。

?刪除Deleted,i):刪除線性表L的第i個(gè)位置結(jié)點(diǎn)(整個(gè)表長-1)，參數(shù)i

的合法取值范圍是lwiwn。

注意：不同的存儲結(jié)構(gòu)基本運(yùn)算的實(shí)現(xiàn)細(xì)節(jié)是不同的。

第二節(jié)線性表的順序存儲

一、線性表的順序存儲方法

將表中結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組連續(xù)的存儲單元中，數(shù)據(jù)元素在線性

表中的鄰接關(guān)系決定它們在存儲空間中的存儲位置，即邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)其存

儲位置也相鄰。用這種存儲形式存儲的線性表稱其為順序表。

?順序表的存儲特點(diǎn)是：用物理上的相鄰實(shí)現(xiàn)邏輯上的相鄰。

《順序存儲可以按序號隨機(jī)訪問每一個(gè)數(shù)據(jù)元素：

設(shè)譏的存儲地址為Loc(ai),每個(gè)數(shù)據(jù)元素占d個(gè)存儲地址，則第i個(gè)數(shù)據(jù)元

素的地址為：Loc(ai)=Loc(ai)+(i-l)*dl<i<n

軟1a軟j現(xiàn)z■■><j

『基饌址LOCXa,)*Lac(ai)4(ll)*d

二、線性表順序存儲的類型定義：

ConstIntMaxsize=100〃預(yù)先定義一個(gè)足夠大的常數(shù)

typedefstruct

{datatypedata[Maxsize];〃存放數(shù)據(jù)的數(shù)組

intlength;〃順序表的實(shí)際長度

}SeqList;"II酹表的類型為SqeList

SeqListL;〃定義L為一個(gè)111酹表

III頁序表圖示：

Ekfe------------------------------------------------------------------------

魄

藪組下標(biāo)z01旃避闖續(xù)經(jīng)4

注意：順序表的第i個(gè)數(shù)據(jù)元素存放在數(shù)組下標(biāo)為i-1的位置上。

例：學(xué)生檔案信息表的順序存儲實(shí)現(xiàn)

學(xué)號姓名年齡

001張晴18

002李利19

.................

根據(jù)以上學(xué)生檔案信息，給出111頁序表具體的類型定義。

ConstIntMaxsize=5〃預(yù)先定義一個(gè)足夠大的常數(shù)

typedefstruct

{intnum;〃學(xué)號

charname[8];〃姓名

intage;〃年齡

JDataType;〃定義結(jié)點(diǎn)類型

typedefstruct

{datatypedata[Maxsize];〃存放數(shù)據(jù)的數(shù)組

intlength;〃線性表的實(shí)際長度

}SeqList;〃順序表的類型

SeqListstudent;//student為順序表的名稱

三、線性表的基本運(yùn)算在順序表上的實(shí)現(xiàn)

1.插入

III酹表的插入運(yùn)算InsertSeqList(SeqListL,DataTypex,inti)是指在表的

第i(lwiwn+l)個(gè)位置上插入一個(gè)值為x的新元素。

算法主要步驟：

①將a「an依次向后移動一個(gè)元素的位置，共需要移動n-i+1個(gè)元素；

②將x放在第i個(gè)位置上;

③表長+1。

本算法中注意以下問題：

①順序表中數(shù)據(jù)區(qū)域有maxsize個(gè)存儲單元，所以在向順序表中做插入時(shí)先

檢查表空間是否滿了，在表滿的情況下不能再做插入，否則產(chǎn)生溢出錯(cuò)誤。

②要檢驗(yàn)插入位置的有效性，這里i的有效范圍是：1。介+1,其中n為原

③注意數(shù)據(jù)的移動方向。

④表長的修改。

順序表的插入算法描述：

voidInsertSeqList(SeqListL,DataTypex,inti)

{intj;

if(L.length==maxsize)exit{"表滿")；〃表空間已滿，不能插

入

if(i<l||i>L.length+l)置錯(cuò)");〃檢查插入位置的正確

性

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

Ldata[j]=Ldata|j-l];〃*結(jié)點(diǎn)向后移動

L.data[i-l]=x;〃新元素插入

L.length++;〃表長+1

)

2.刪除

111酹表的刪除運(yùn)算DeleteSeqList(SeqListL,inti)是指在表的第i(l<i<n)

個(gè)元素刪去。

算法主要步驟：

①將ai+i~an依次向前移動一個(gè)元素的位置，共移動n-i個(gè)元素；

②表長-1。

本算法中注意以下問題：

①刪除第i個(gè)元素，i的取值為lwiwn，否則第i個(gè)元素不存在，因此，要檢查

刪除位置的有效性。

②當(dāng)表空時(shí)不能做刪除，因表空時(shí)LJength的值為0,條件

(i<l||i>L.length)也包括了對表空的檢查。

③刪除ai之后，該數(shù)據(jù)已不存在，如果需要，先取出，再做刪除。

④注意數(shù)據(jù)的移動方向。

⑤修改表長。

順序表的刪除算法描述：

voidDeleteSeqList(SeqListL,inti)

{intj;

if(i<l||i>L.length)exit("非法彳58");〃檢查位置是否合法

for(j=i;j<Llength;j++)

Ldata[j-l]=Ldata[j];〃*結(jié)點(diǎn)向前移動

LJength—;〃表長-1

)

3.定位

III酹表的定位運(yùn)算LocateSeqList(SeqListL,DataTypex)是指在線性表

中查找與給定值x相等的結(jié)點(diǎn)序號的最小值。當(dāng)找不到值為x的結(jié)點(diǎn)時(shí)，返回結(jié)果

0o

II質(zhì)序表的定位算法描述：

intLocateSeqList(SeqListL,DataTypex)

{inti=0;

While((i<L.length)&&(L.data[i]!=x))〃順序檢查數(shù)據(jù)元素值為x的結(jié)點(diǎn)

i++；

if(i<LJength)returni+1;〃查找成功，返回?cái)?shù)據(jù)元素的序號

elsereturn0;〃查找不成功，返回0

)

4.其他運(yùn)算

順序表的求表長操作Length(L)直接輸出LJength即可。

順序表的讀表元素Get(L,i)直接輸出L.data[i-1]即可。

四、順序表實(shí)現(xiàn)算法的分析

1.順序表的插入算法的時(shí)間復(fù)雜度分析：

II質(zhì)序表上的插入運(yùn)算，時(shí)間主要消耗在了數(shù)據(jù)的移動上，在第i個(gè)位置上插入

x，從ai到an都要向下移動一個(gè)位置，共需要移動n-i+1個(gè)元素，而i的

取值范圍為：1W3n+1,即有n+1個(gè)位置可以插入。在順序表上做插入操作

平均需移動表中一半的數(shù)據(jù)元素，時(shí)間復(fù)雜度為O(n)。

2.順序表的刪除算法的時(shí)間復(fù)雜度分析：

與插入運(yùn)算相同，順序表上的刪除運(yùn)算時(shí)間也主要消耗在數(shù)據(jù)的移動上，刪除

第i個(gè)元素時(shí)，其后面的元素ai+i~an都要向上移動一個(gè)位置，共移動了n-i個(gè)

元素，所以平均移動數(shù)據(jù)元素的次數(shù)為(n-l)/2，時(shí)間復(fù)雜度為O(n)。

3.順序表的定位算法的時(shí)間復(fù)雜度分析：

本算法的主要運(yùn)算是給定值X與表中元素的匕瞰。顯然比較的次數(shù)與X在表中

的位置有關(guān)，也與表長有關(guān)。查找成功的平均比較次數(shù)為(n+l)/2，時(shí)間復(fù)雜度為

O(n)o

4.求表長和讀表元素的時(shí)間復(fù)雜度為0(1)。

五、綜合舉例

【舉例】：有111頁序表A和B,其元素均按從小到大的升序排列，編寫一個(gè)算法

將它們合并成一個(gè)順序表C,要求C的元素也是從小到大的升序排列。

算法思路分析：

依次掃描通過A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C,

如此直到一個(gè)線性表掃描完畢，然后將未完的那個(gè)順序表中余下部分賦給C即

可。C的容量要能夠容納A、B兩個(gè)線性表相加的長度。

算法描述：

voidmerge(SeqListA,SeqListB,SeqListC)

{inti,j,k;

i=0;j=0;k=0;

while(i<A.length&&j<B.length)〃將A和B的當(dāng)前元素較小者復(fù)制

到表C

if(A.data[i]<B.data[j])

C.data[k++]=A.data[i++];

elseC.data[k++]=B.data|j++];

while(i<Alength)/*將A中剩余元素復(fù)制到表C*/

C.data[k++]=A.data[i++];

while0<B.length)/*將B中剩余元素復(fù)制到表C*/

C.data[k++]=B.data[j++];

C.length=k;

)

六、考點(diǎn)提示

i.線性表的基本運(yùn)算在順序表上的實(shí)現(xiàn)

令順序表實(shí)現(xiàn)算法時(shí)插入、刪除操作時(shí)，元素移動個(gè)數(shù)和移動方向是非常重要

的考點(diǎn)。

【例題?填空題】向一個(gè)長度為n的111頁序表中第i(l<i<n)個(gè)元素之前插入一

個(gè)元素時(shí)，需向后移動個(gè)元素。

隱藏答案

【答案】n-i+1

【解析】II質(zhì)序表上的插入運(yùn)算，時(shí)間主要消耗在了數(shù)據(jù)的移動上，在第i個(gè)位

置上插入X,從Hi到an都要向下移動一個(gè)位置，共需要移動n-i+1個(gè)元素。

2.順序表操作算法設(shè)計(jì)

令這類題目可能作為算法設(shè)計(jì)題出現(xiàn)，如對一個(gè)N頁序表進(jìn)行劃分、進(jìn)行兩個(gè)順

序表的合并、比較等；也可以結(jié)合其它數(shù)據(jù)結(jié)構(gòu)一起出現(xiàn)，因此順序表的插入、刪

除、定位等算法要非常熟練。

第三節(jié)線性表的鏈接存儲

一、單鏈表的類型定義

1.思路

令鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，那么怎樣表

示出數(shù)據(jù)元素之間的線性關(guān)系呢？

令單鏈表表示法的基本思想一用指針表示結(jié)點(diǎn)間邏輯關(guān)系

令為建立起數(shù)據(jù)元素之間的線性關(guān)系，單鏈表對每個(gè)數(shù)據(jù)元素,，除了存放數(shù)

據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼元素ai+i所在的存儲單

元的地址，這兩部分信息組成一個(gè)“結(jié)點(diǎn)"，結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示，每個(gè)元素都如

此。

datanext

令由數(shù)據(jù)域和指針域兩部分組成：數(shù)據(jù)域是用于存儲線性表的一個(gè)數(shù)據(jù)元素

的，指針域是用于存放一個(gè)指針的，該指針指向本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所

在的結(jié)點(diǎn)。

令n個(gè)元素的線性表可以通過每個(gè)結(jié)點(diǎn)的指針域拉成了一個(gè)"鏈"，稱之為單鏈

表。如下圖所示:

存儲地址存儲內(nèi)容指針

2000H2002K行|2CC2

2002H'C20AOK'C2Q.AD

????........

202OH'A'2000H2000

?.................?

20A0H'D'NULL

?head稱為頭指針變量，該變量的值是指向單鏈表的第一個(gè)結(jié)點(diǎn)的指針。單鏈

表的第一個(gè)結(jié)點(diǎn)稱為鏈表的首結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)稱為尾結(jié)點(diǎn)或終端結(jié)點(diǎn)。尾結(jié)點(diǎn)

的指針域的值NULL稱為空指針。

令若head等于NULL,則表示空的單鏈表。

2.單鏈表的類型定義：

typedefstructnode

{DataTypedata;〃數(shù)據(jù)域

structnode*next;〃指針域

}Node,*LinkList;

3.舉例

?學(xué)生檔案信息表的鏈接存儲實(shí)現(xiàn)

令學(xué)生檔案信息鏈表的類型完整描述如下：

typedefstruct

{intnum;〃學(xué)號

charname[8];〃姓名

intage;〃年齡

}DataType;〃定義結(jié)點(diǎn)類型

typedefstructnode

{datatypedata;〃數(shù)據(jù)域

structnode*next;;〃性表的實(shí)際長度

}Node,*LinkList;〃Node是鏈表結(jié)點(diǎn)的類型

令為了運(yùn)算的方便，我們?nèi)藶榈卦阪湵淼拈_始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)一稱為

頭結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)。這樣，不論鏈表是否為空，頭指針

總是非空的，而且頭結(jié)點(diǎn)的設(shè)置使得對鏈表的首結(jié)點(diǎn)的操作和在其他位置上的操作

一致，它們的地址都在前一個(gè)結(jié)點(diǎn)的next域中。

head

二、線性表的基本運(yùn)算在單鏈表上的實(shí)現(xiàn)

i.初始化

InitiateLinkList的功能是建立一個(gè)帶頭結(jié)點(diǎn)的空表。

算法主要步驟：

①創(chuàng)建一個(gè)頭結(jié)點(diǎn)并將其指針域設(shè)為NULL;

②用一個(gè)LinkList類型的變量(即頭指針)指向新創(chuàng)建的結(jié)點(diǎn)。

算法描述：

LinkListInitiateLinkList()〃建立一個(gè)空的單鏈表

(

LinkListhead;〃頭指針

head=malloc(sizeof(Node));〃動態(tài)構(gòu)建一結(jié)點(diǎn)，它是頭結(jié)點(diǎn);

head->next=NULL;

returnhead;

)

2.求表長

算法主要步驟：

掃描指針：要訪問到單鏈表中的所有結(jié)點(diǎn)，需要逐個(gè)掃描指針。

算法描述：

intLengthLinkListl(LinkListhead)

{Node*p=head;〃p指向頭結(jié)點(diǎn)

intcnt=0;〃計(jì)數(shù)器設(shè)初值

while(p->next!=NULL)〃判斷是否為尾結(jié)點(diǎn)

{p=p->next;〃指針移到下一個(gè)結(jié)點(diǎn)

cnt++;}

returnent;〃返回表長

)

3.讀表元素

算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是第i個(gè)，若是，

則返回該結(jié)點(diǎn)的指針，否則繼續(xù)后一個(gè)，表結(jié)束為止。沒有第i個(gè)結(jié)點(diǎn)時(shí)返回空指

針。

算法描述：

Node*GetLinkList(LinkListhead,inti)

〃在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)，找到返回其指針，否則返回空

{Node*p;//p是工作指針

p=head->next;〃初始時(shí)，p指向首結(jié)點(diǎn)

intc=l;

while((c<i)&&(p!=NULL))

{p=p->next;C++;}

if(c==i)returnp;〃找到

elsereturnNULL;〃查找失敗

)

4.定位

算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)值是否等于X,若是，返

回該結(jié)點(diǎn)的序號，否則繼續(xù)后一個(gè)，表結(jié)束為止。找不到時(shí)返回0o

算法描述：

IntLocateLinkList(LinkListhead,DataTypex)

〃在單鏈表head中查找第一個(gè)值為x的結(jié)點(diǎn)，找到后返回其序號，否則返回0

{Node*p=head;

p=p->next;

inti=0;

while(p!=NULL&&p->data!=x)

{i++；

p=p->next;}

if(p!=NULL)returni+1;

elsereturn0;

)

5.插入

算法思路：插入運(yùn)算是要在第i個(gè)結(jié)點(diǎn)前插入值為x的元素?；静襟E：

①找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)②，否則返回錯(cuò)誤信息結(jié)束；

②申請、填裝新結(jié)點(diǎn)；

③將新結(jié)點(diǎn)插入，結(jié)束。

算法描述：

voidInsertLinkList(LinkListhead,DataTypex,inti)

〃在單鏈表head的第i個(gè)位置上插入值為x的元素

{Node*p,*q;

if(i==l)q=head;

elseq=GetLinkList(head,i-1);〃查找第i-1個(gè)結(jié)點(diǎn)

if(q==NULL)

exit("找不到插入位置)〃第i-1個(gè)不存在不能插入

else

{p=malloc(sizeof(Node));〃申請、填裝結(jié)點(diǎn)

p->data=x;

p->next=q->next;〃新結(jié)點(diǎn)插入在第i-1個(gè)結(jié)點(diǎn)的后面

q->next=p;

)

)

6.刪除

算法思路：

①找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)②，否則返回錯(cuò)誤結(jié)束；

②若存在第i個(gè)結(jié)點(diǎn)則繼續(xù)③，否則返回錯(cuò)誤結(jié)束；

③刪除第i個(gè)結(jié)點(diǎn)，結(jié)束。

算法描述：

voidDeleteLinkList(LinkListhead,inti)

〃刪除單鏈表head上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)

{Node*q,*p

if(i==l)q=head;

elseq=GetLinkList(head,i-1);〃查找第i-1個(gè)結(jié)點(diǎn)

if(q!=NULL&&q->next!=NULL)

{p=q->next;//p指向第i個(gè)結(jié)點(diǎn)

q->next=p->next;〃從鏈表中刪除p

free(p);〃釋放*p

）

elseexit（"第i個(gè)結(jié)點(diǎn)不存在）

）

三、考點(diǎn)提示

1.線性表鏈?zhǔn)酱鎯Φ慕Y(jié)構(gòu)特點(diǎn)

【例題?單選題】在單鏈表中，存儲每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另

一個(gè)是指針域，指針域指向該結(jié)點(diǎn)的（）

A.直接前趨

B.直接后繼

C開始結(jié)點(diǎn)

D.終端結(jié)點(diǎn)

隱藏答案

【答案】B

【解析】單鏈表的基本概念，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩部分組成：數(shù)據(jù)域

是用于存儲線性表的一個(gè)數(shù)據(jù)元素的，指針域是用于存放一個(gè)指針的，該指針指向

本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所在的結(jié)點(diǎn)。

2.帶頭結(jié)點(diǎn)與不帶頭結(jié)點(diǎn)單鏈表的區(qū)別

如判空條件、第一個(gè)結(jié)點(diǎn)的插入與刪除等要注意。

3.單鏈表的插入、刪除等操作的特點(diǎn)

【例題?單選題】設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,若要?jiǎng)h除A的直接后繼，則所

需修改指針的操作為（）

A.p->next=p->next->next

B.p=p->next

C.p=p->next->next

D.p->next=p

隱藏答案

【答案】A

【解析】單鏈表刪除的關(guān)鍵步驟，讓p的next域(A的直接后繼)為p的

next域的next域(A的直接后繼的直接后繼)。

【例題?單選題】在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法

所需的時(shí)間復(fù)雜度為()

A.O(l)

B.0(log2n)

C.0(n)

D.0(n2)

隱藏答案

【答案】C

【解析】因?yàn)橐业阶詈笠粋€(gè)結(jié)點(diǎn)才能插入新結(jié)點(diǎn)，所以要遍歷整個(gè)單鏈表，

所以時(shí)間復(fù)雜度為0(n)。

第四節(jié)其他運(yùn)算在單鏈表上的實(shí)現(xiàn)

一、尾插法建表

算法思路：每次在鏈表的尾部增加新的結(jié)點(diǎn).設(shè)數(shù)據(jù)元素的類型為im,利用

InsertLinkList(LinkListhead,intx,inti)來實(shí)現(xiàn)，依次增大插入位置，使新的結(jié)點(diǎn)

鏈入到鏈表中。

算法實(shí)現(xiàn)：

LinkListCreatLinkListl()

{LinkListhead;

intx,i;

head=InitiateLinkList()〃建空表

i=l；〃插入位置初值

scanf("%d",&x);〃讀入第一個(gè)元素

while(x!=flag)//flag表示結(jié)束標(biāo)志

{InsertLinkList(head,x,i)

i++

scanf("%d",&x);}

returnhead;}

時(shí)間復(fù)雜度為0(?)

二、尾插法建表

算法思路：每次在鏈表的尾部增加新的結(jié)點(diǎn).用一個(gè)指針指向表尾，為新的結(jié)點(diǎn)

鏈入指明了位置。

算法實(shí)現(xiàn)：

LinkListCreatLinkList2()

{LinkListhead;

Node

intx;

head=malloc(sizeof(Node));〃生成頭結(jié)點(diǎn)

q=head;〃尾指針置初值

scanf("%d",&x);

while(x!=flag)//flag表示結(jié)束標(biāo)志

{t=malloc(sizeof(Node));〃生成新結(jié)點(diǎn)

t->data=x;

q->next=t;〃新結(jié)點(diǎn)鏈入

q=t；〃修改尾指針

scanf("%d",&x);

)

q->next=NULL;returnhead;//q指向尾指針，置尾結(jié)點(diǎn)標(biāo)志

)

該算法的時(shí)間復(fù)雜度為0(n)。

頭插法建表

算法思路：每次在鏈表的頭部增加新的結(jié)點(diǎn).

算法實(shí)現(xiàn)：

LinkListCreatLinkList3()

LinkListhead;

Node*p;

intx;

head=malloc(sizeof(Node));〃生成頭結(jié)點(diǎn)

head->next=NULL;

scanf("%dn,&x);

while(x!=flag)//flag為根據(jù)實(shí)際情況設(shè)定的結(jié)束

數(shù)據(jù)輸入的標(biāo)志數(shù)據(jù)

{p=malloc(sizeof(Node));

p->data=x;〃申請結(jié)點(diǎn)，添裝數(shù)據(jù)

p->next=head->next;〃頭插：插入新結(jié)點(diǎn)在第一個(gè)結(jié)點(diǎn)

處

head->next=p;

scant("%d",&x);

)

returnhead;

)

該算法的時(shí)間復(fù)雜度為0(n)，但其形成的鏈表數(shù)據(jù)111頁序與數(shù)據(jù)輸入II褥相反。

四、刪除重復(fù)結(jié)點(diǎn)

算法思路：用指針q指向第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，從它的后繼結(jié)點(diǎn)開始到表的結(jié)

束，查找與其值相同的結(jié)點(diǎn)并刪除之；q指向下一個(gè)結(jié)點(diǎn)；依此類推，q指向最后

結(jié)點(diǎn)時(shí)算法結(jié)束。

voidPurgeLinkList(LinkListhead)

{Node*p,*q,*r;

q=head->next;〃q指向第一個(gè)結(jié)點(diǎn)

while(q!=NULL)

{p=q；

while(p->next!=NULL)〃從*q的后繼開始找重復(fù)結(jié)點(diǎn)

if(p->next->data==q->data)

{r=p->next;//找到重復(fù)結(jié)點(diǎn)，用r指向，刪除*r

p->next=r->next;

free(r);

)

elsep=p->next;

q=q->next;}//q指向下一個(gè),繼續(xù)

)

五、考點(diǎn)提示

1.應(yīng)用單鏈表解決實(shí)際問題

如求一個(gè)單鏈表的逆序、合并兩個(gè)單鏈表等；這部分容易出現(xiàn)算法設(shè)計(jì)題，也

有一些對應(yīng)用的功能和性能分析。

【例題?單選題】：將長度為n的單鏈表連接在長度為m的單鏈表之后，其算

法的時(shí)間復(fù)雜度為()

A.0(1)

B.0(m)

C.0(n)

D.0(m+n)

隱藏答案

【答案】B

【解析】只需找到長度為m的單鏈表的表尾結(jié)點(diǎn)就可以直接連接，因此需要遍

歷長度為m的單鏈表，算法的時(shí)間復(fù)雜度為O(m)o

2.各種建表方法的時(shí)間復(fù)雜度分析及關(guān)犍步驟等。

第五節(jié)其他鏈表

一、循環(huán)鏈表

1.思路

?對于單鏈表而言，最后一個(gè)結(jié)點(diǎn)的指針域是空指針，如果將該鏈表頭指針置

入該指針域，則使得鏈表頭尾結(jié)點(diǎn)相連，就構(gòu)成了單循環(huán)鏈表。

2.特點(diǎn)

令無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈

活：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率。

3.圖示

二、雙向循環(huán)鏈表

1.思路

令每個(gè)結(jié)點(diǎn)包含兩個(gè)指針域，一個(gè)指向直接前趨(prior),一個(gè)指向直接后繼

(next)o

令雙鏈表由頭指針唯一確定。

令將雙鏈表中的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來可以構(gòu)成循環(huán)鏈表，并稱之為雙向循

環(huán)鏈表。

2.圖示

3.類型說明

structdbnode

{DataTypedata;

structdbnode*prior,*next;

)

typedefstructdbnode,*dbpointer;

typedefdbpointerDLinkList;

4.雙向循環(huán)鏈表的基本運(yùn)算

1）刪除

設(shè)p指向待刪結(jié)點(diǎn)，刪除*p可通過以下語句完成

p->prior->next=p->next;//p前驅(qū)的后繼為p的后繼

p->next->prior=p->prior;//p后繼的前驅(qū)為p的前驅(qū)

free(p);〃釋放*p的空間

2）插入

在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t,需要修改4個(gè)指針，而且要注意語句的

順序。

t->prior=p;

t->next=p->next;

p->next->prior=t;

1.循環(huán)鏈表及雙鏈表的插入與刪除等操作的關(guān)鍵步驟要特別注意；

2.基于特殊鏈表的算法設(shè)計(jì)

【例題?算法設(shè)計(jì)題】若循環(huán)單鏈表長度大于1,p為指向鏈表中某結(jié)點(diǎn)的指

針，試編寫一算法刪除p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

隱藏答案

【答案】

Node*delete(p)

Node*P;

Node*q,*r;

q=p；

While(q->next!=p)q=q->next;〃找到p的前驅(qū)q

r=q；

while(r->next!=q)r=r->next;〃找到q的前驅(qū)r

r->next=p;〃從鏈中摘掉q

free(q);

return(p);

)

【解析】算法的思路是先找到p的前驅(qū)q,再找到q的前驅(qū)。然后刪除q,因?yàn)?/p>

是循環(huán)鏈表，所以不必判斷是否到達(dá)表尾，比較簡單。大家也可對此算法進(jìn)行改

進(jìn)。

第六節(jié)順序?qū)崿F(xiàn)與鏈接實(shí)現(xiàn)的比較

1.從空間上考慮

令當(dāng)線性表的長度變化較大時(shí),難以估計(jì)其存儲規(guī)模，以采取動態(tài)鏈表作為存

儲結(jié)構(gòu)為好。

令當(dāng)線性表的長度變化不大時(shí)，為了提高存儲密度，以采取順序表作為存儲結(jié)

構(gòu)。

，存儲密度是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲量和整個(gè)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲量之

比。

2.從時(shí)間上考慮

令如果線性表的操作主要是進(jìn)行按序號訪問數(shù)據(jù)元素，很少做插入、刪除操

作，采用111頁序表為宜。

令對于頻繁地進(jìn)行插入和刪除的線性表，采用鏈表存儲結(jié)構(gòu)為宜。

3.考點(diǎn)提示

令掌握線性表各種存儲結(jié)構(gòu)的特點(diǎn)，選擇合適的結(jié)構(gòu)解決實(shí)際問題

【例題?單選題】在線性表的下列存儲結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算，花費(fèi)時(shí)間最

多的是()

A.單鏈表

B.雙鏈表

C.順序表

D.單循環(huán)鏈表

隱藏答案

【答案】C

【解析】因?yàn)?11頁序表與鏈表相比不僅要比較還要移動元素，所以花費(fèi)時(shí)間最

多。

本章典型考題

【例題?填空題】向一個(gè)長度為n的111頁序表中第i(l<i<n)個(gè)元素之前插入一

個(gè)元素時(shí)，需向后移動個(gè)元素。

隱藏答案

【答案】n-i+1

【解析】順序表插入的特點(diǎn)，向一個(gè)長度為n的順序表中第i(l<i<n)個(gè)元素

之前插入一個(gè)元素時(shí)，需要將ai~an依次向后移動一個(gè)元素的位置，共需要移動n

-i+1個(gè)元素

【例題?填空題】對II質(zhì)序表執(zhí)行刪除操作，其刪除算法的平均時(shí)間復(fù)雜性為

隱藏答案

【答案】0(n)

【解析】刪除運(yùn)算時(shí)間也主要消耗在數(shù)據(jù)的移動上，刪除第i個(gè)元素時(shí)，其后

面的元素都要向上移動一個(gè)位置,共移動了個(gè)元素，所以平均移動

ai+i~ann-i

數(shù)據(jù)元素的次數(shù)為，時(shí)間復(fù)雜度為

(n-l)/2O(n)o

【例題?單選題】在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則

在結(jié)點(diǎn)p、q之間插入結(jié)點(diǎn)s的正確操作是()

A.s->next=q;p->next=s->next

B.s->next=q;p->next=s

C.s->next=q->next;p->next=s

D.s->next=q->next;p->next=s->next

隱藏答案

【答案】B

【解析】插入結(jié)果應(yīng)是的直接后繼是的直接后繼是所以的應(yīng)

ps;sqosnext

賦值為；的域賦值為

qpnextso

【例題?填空題】若head表示循環(huán)鏈表的頭指針，t表示尾結(jié)點(diǎn)，則頭指針

head與尾結(jié)點(diǎn)t之間的關(guān)系可表示為。

隱藏答案

【答案】t->next=head

【解析】循環(huán)鏈表的特點(diǎn)，將表尾的next域指向表頭。

第三章棧、隊(duì)列和數(shù)組本章概覽

一、知識結(jié)構(gòu)

二、本章重難點(diǎn)

重點(diǎn)：棧和隊(duì)列的特征力I酹棧和鏈棧上基本運(yùn)算的算法；順序隊(duì)列和鏈隊(duì)列

上基本運(yùn)算的算法。

難點(diǎn)：循環(huán)隊(duì)列的組織；隊(duì)滿和隊(duì)空的條件及循環(huán)隊(duì)列的基本運(yùn)算的算法。

主要題型：單項(xiàng)選擇題，填空題，應(yīng)用題,算法設(shè)計(jì)題。

往年分值：8-18分

第一節(jié)棧

一、棧的基本概念

1.棧的定義

令限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。

令棧頂(top)和棧底(bottom):允許插入、刪除的一端稱