計算機網(wǎng)絡(luò)各章各界重點難點

◎〈教學目的和要求〉◎〈重點和難點〉◎（第?節(jié)〉

◎〈第二節(jié)〉◎〈第三節(jié)〉◎（課堂練習＞

※〈教學目的和要求〉

本章主要介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以

及學習數(shù)據(jù)結(jié)構(gòu)的意義。要求了解本章介紹的各種基本

概念和術(shù)語，掌握算法描述和分析的方法。

※（重點和難點〉

本章重點是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及

數(shù)據(jù)的運算三方面的概念及相互關(guān)系。難點是算法時間

復雜度的分析方法和抽象數(shù)據(jù)類型的概念。

※〈第一節(jié)〉

1.1什么是數(shù)據(jù)結(jié)構(gòu)

作為一門課程，數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程,

數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機硬件的研究范圍，而

且和計算機軟件的研究有密切的關(guān)系，無論是編譯程序

還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問

題。其介于數(shù)學、計算機硬件和計算機軟件三者之間。

程序設(shè)計的實質(zhì)就是選擇一個好的數(shù)據(jù)結(jié)構(gòu)與一個好的

算法。一個好的算法在很大程度上依賴于所選的數(shù)據(jù)結(jié)

構(gòu)，選擇一個恰當?shù)臄?shù)據(jù)結(jié)構(gòu)是程序設(shè)計的關(guān)鍵步驟，

所以說數(shù)據(jù)結(jié)構(gòu)不僅是應用軟件的基礎(chǔ)、而且是系統(tǒng)軟

件設(shè)計的基礎(chǔ)。本課程所介紹的數(shù)據(jù)結(jié)構(gòu)在應用軟件、

系統(tǒng)軟件設(shè)計各種中有著廣泛的應用。

※〈第二節(jié)〉

1.2基本概念和術(shù)語

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項

(1)數(shù)據(jù)是信息的載體，它能夠被計算機識別、和

加工處理。它是計算機加工的原料。

(2)數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它是對客體的完

整描述。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂

點、記錄。

(3)數(shù)據(jù)項是數(shù)據(jù)的具有獨立含義的最小標識單

位，它是對客體屬性的描述。

數(shù)據(jù)是一個全集的概念，數(shù)據(jù)元素是數(shù)據(jù)這?全集

中的元素，數(shù)據(jù)元素可以由一個數(shù)據(jù)項或多個數(shù)據(jù)項構(gòu)

成。

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

(1)邏輯結(jié)構(gòu)是指元素之間的邏輯關(guān)系。在不引起

混淆的情況下，我們常常將邏輯結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。

(2)存儲結(jié)構(gòu)是指數(shù)據(jù)元素及其關(guān)系在計算機上的

表示(也稱為存儲映像)。

(3)數(shù)據(jù)的運算是指對數(shù)據(jù)施加的操作。

(4)數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及數(shù)據(jù)之間存在的一種或多

種特定關(guān)系。雖然至今為止，計算機界尚未給出數(shù)據(jù)結(jié)

構(gòu)的標準定義，但它一般包括以下三方面的內(nèi)容：數(shù)據(jù)

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

3.邏輯結(jié)構(gòu)的類別

數(shù)據(jù)的邏輯結(jié)構(gòu)可分為兩大類：

(1)線性結(jié)構(gòu)：線性結(jié)構(gòu)是指若數(shù)據(jù)結(jié)構(gòu)是非空集

合，則其有且僅有一個終端結(jié)點和一個開始結(jié)點，其它

結(jié)點有且僅有一個直接前趨和一個直接后繼，開始結(jié)點

沒有直接前趨，終端結(jié)點沒有直接后繼。線性表、棧和

隊列、串均為線性結(jié)構(gòu)。

(2)非線性結(jié)構(gòu)：是指若數(shù)據(jù)結(jié)構(gòu)是非空集合，則每

個結(jié)點可以有多個直接前趨區(qū)和直接后繼。數(shù)組、廣義

表、樹和圖均為非線性結(jié)構(gòu)。

非線性結(jié)構(gòu)又可分為三類:樹型結(jié)構(gòu),圖狀結(jié)構(gòu)和集

合型結(jié)構(gòu)。

4.存儲結(jié)構(gòu)的四種存儲方法

（1）順序存儲方法

在一片地址連續(xù)的存儲單元中，把邏輯上相鄰的數(shù)

據(jù)元素存儲在物理位置上也相鄰的存儲單元里，元素間

的邏輯關(guān)系由存儲單元的相鄰關(guān)系來體現(xiàn)。由此得到的

存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)。

（2）鏈式存儲方法

元素間的邏輯關(guān)系由附加的指針字段來表示。存儲

單元的地址不要求連續(xù)，但存儲一個數(shù)據(jù)元素時既要存

儲數(shù)據(jù)元素又要存儲與本元素有關(guān)聯(lián)的數(shù)據(jù)元素的地

址。由此得到的存儲結(jié)構(gòu)稱為鏈式存儲結(jié)構(gòu)。

（3）索引存儲方法

該方法是在存儲數(shù)據(jù)元素的同時，建立一張附加的

索引表，用索引表中的索引項來指示各數(shù)據(jù)元素的存儲

位置。索引項的一般形式為：關(guān)鍵字，地址。若每個數(shù)

據(jù)元素在索引表中都有一個索引項則該索引表稱為稠密

索引。若一組數(shù)據(jù)元素在索引表中只對應一個索引項則

稱該索引表為稀疏索引。

（4）散列存儲方法

該方法的基本思想是建立數(shù)據(jù)元素的關(guān)鍵字與存儲

位置之間的映像關(guān)系，從而根據(jù)關(guān)鍵字值計算出該數(shù)據(jù)

元素的存儲位置。

5.數(shù)據(jù)類型

所謂數(shù)據(jù)類型是?個值得集合以及在這些值上定

義的一組操作的總稱。按值是否可分解可將數(shù)據(jù)類型

劃分為兩類：其值不可分解的稱為原子類型，其值可

分解為若干個成分的稱為結(jié)構(gòu)類型。

6.抽象數(shù)據(jù)類型（DAT）

是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作，它可以

看作是數(shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操

作。它是描述問題的模型，獨立于具體實現(xiàn)。它的優(yōu)

點是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通

過在DAT里定義的操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)

了信息隱藏。

※〈第三節(jié)〉

1.3算法的描述和分析

i.算法及算法的特點

算法：是對特定問題求解步驟的描述,即一系列將

輸入轉(zhuǎn)換為輸出的指令的有限序列。

算法的特性：

(1)有窮性：一個算法必須總是在執(zhí)行有限步之

后結(jié)束，每一步都可在有限時間內(nèi)完成。

(2)確定性：算法中每一條指令必須有確切的含

義，讀者理解時不會產(chǎn)生二義性。并且，在任何條件

下，算法只有唯一的一條執(zhí)行路徑。

(3)可行性：-個算法是能行的，即算法中描述

的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次

來實現(xiàn)。

(4)輸入：一個算法可以有零個或多個數(shù)輸入，

這些輸入取之于特定的對象的集合。

(5)輸出：一個算法有一個或多個輸出。這些輸

出是同輸入有某種特定關(guān)系的量。

2.算法的描述和算法評價

(1)算法的描述方法

一個算法可以用自然語言、標準程序設(shè)計語言、

流通圖以及偽代碼(偽語言)來說明。唯一的要求是該

說明必須精確地描述計算過程。一般而言，描述算法

最合適的語言是界于自然語言和程序設(shè)計語言之間的

偽語言，它的控制結(jié)構(gòu)類似于C、Pascal等程序語

言，但其中可使用任何表達能力強的方法使算法表達

更加清晰和簡潔，而不致于陷入具體的程序語言的某

些細節(jié)(教材采用c語言描述算法)。

(2)算法的評價標準

正確性：算法應當滿足具體問題的要求。其正確

性評價分為4個層面(詳見教材).

可讀性：算法應當易于理解、易于調(diào)試、易于維

護、易于擴充等

健壯性：當輸入數(shù)據(jù)是非法時，算法也能適當?shù)?/p>

作出反應或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)

果。

時間特性和空間特性：執(zhí)行算法所耗費的時間和

執(zhí)行算法所占用的空間。通常，空間特性和時特性難

以兼顧，要提高算法的時間特性往往以犧牲空間特性

為代價，要提高算法的空間特性往往以犧牲時間特性

為代價。

3.算法的分析(本教材主要討論時間特性，有

時討論空間特性)

(1)語句的頻度：算法中語句執(zhí)行的次數(shù)。

(2)問題的規(guī)模：算法求解問題的輸入量。例

如，矩陣乘法問題的規(guī)模是矩陣的階，圖論問題的規(guī)

模是頂點數(shù)或邊數(shù)。

(3)時間復雜度和漸進時間復雜度：一個算法的

時間復雜度是該算法的時間耗費，它是該算法求解問

題規(guī)模n的函數(shù)。通常，我們用算法中各語句的頻度

和來表示算法的時間耗費。當問題的規(guī)模趨向無窮大

時，我們將時間復雜度的數(shù)量級稱為算法的漸進時間

復雜度。例如兩個n階矩陣相乘算法如下

算法語句頻度

voidmatmult(inta[n][n],int

b[n][n],intc[n][n])

{inti,j,k；

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

For(j=O;j<n;j++)n(n+l)

{c[I][j]=0;n2

for(k=0;k〈n;k++)n2(n+l)

c[i][j]=c[i][j]+a[i][k]*b[k][j];}n3

)

該算法的時間復雜度為：T(n)=2n3+3n2+2n+l

當n趨向無窮大時n3與T(n)是同階的(同數(shù)量

級)，所以，算法的漸進時間復雜度為：T(n)=0(n3)

在算法分析時，評價一個算法的時間性能時主要

標準是算法時間復雜度的數(shù)量級，即算法的漸進時間

復雜度。因此，往往對算法的漸進時間復雜度和時間

復雜度不作區(qū)分，簡稱為時間復雜度。

算法的時間復雜度不僅僅依賴于問題的規(guī)模，也

取決于輸入實例的初始狀態(tài)。平均時間復雜度是指所

有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的

期望運行時間。最壞時間復雜度是指最壞情況下，算

法的期望運行時間，?般而言，不作特殊說明，忖間

復雜度即指最差時間復雜度。

4.常見的時間復雜度

常量階0(1)、對數(shù)階0(log2n))、線性階0(n)、

平方階0(二)、立方階0(0)多項式階00

...、指數(shù)階0(2n)

※〈課堂練習〉

課堂練習

1.閱讀程序題，估計時間復雜度

x=0；y=0；

for(k=l；k<=n；k++)

x=x+l；

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

for(j=l；j<=n；

y++；

解：

一般情況下，對步進循環(huán)語句只需考慮循環(huán)體中語

句的執(zhí)行次數(shù)，而忽略循環(huán)控制語句等成分。因此，算

法中y++；語句的頻度為n:所以該序段的時間復雜度

是平方階。。(廠)

2.閱讀程序題，估計時間復雜度

x=0；

for(i=l,j=l；i+j<=n；i++,j++)

x++；

解：

循環(huán)體X++；語句的執(zhí)行頻度n/2,算法的時間復雜度

T(n)=O(f(n))=O(n)

3.閱讀程序題，估計時間復雜度

x=l；

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

for(j=l；j<=i；j++)

for(k=Lk<=j；k++)

x++；

解：循環(huán)體x++；語句的執(zhí)行頻度

f(n)=

[n(n+l)(2n+l)/6+n(n+l)/2]/2

算法的時間復雜度T(n)=0(|')

返回頁首

第二章線性表

◎〈教學H的及要求〉◎〈重點難點〉◎〈第?節(jié)〉

◎〈第二節(jié)〉

※〈教學目的及要求〉

本章目的是介紹線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及定義在邏輯結(jié)構(gòu)上的各種

基本運算和這些基本運算在存儲結(jié)構(gòu)上的實現(xiàn)(即算法)。要求學生在掌握這些內(nèi)

容的基礎(chǔ)上，能夠針對具體應用問題的要求和性質(zhì)，選擇恰當?shù)拇鎯Y(jié)構(gòu)設(shè)計出相

應的有效上算法，解決與線性表相關(guān)的實際問題。

※〈垂點難點>

本章重點是熟練掌握順序表和單鏈表上實現(xiàn)的各種基本算法及相關(guān)的時間性能

分析。難點是能夠使用本章所學到的基本知識設(shè)計有效算法解決與線性表相關(guān)的應

用問題。

※〈第一節(jié)〉

2.1線性表的邏輯結(jié)構(gòu)

i.線性表：

是山n(n》O)各數(shù)據(jù)元素al,a2,…，an組成的有限序列。其中，數(shù)據(jù)元素

的個數(shù)定義為表長。當n=0時線性表稱為空表，非空線性表通常記為(al,

a2,???,an)例子(見教材)。

2.線性表的邏輯特征：

線性表是一種線性結(jié)構(gòu)。對于非空線性表，有且僅有一個開始結(jié)點，它沒有直

接前趨，僅有一個直接后繼；有且僅有一個終端結(jié)點，它沒有直接后繼，僅有一個

直接前趨；其它結(jié)點有且僅有一個直接前趨和一個直接后繼。元素間的邏輯關(guān)系是

線性的。

3.線性表的基本運算：

(1)InitList(L)

線性表的初始化，即構(gòu)造一個空表。

(2)ListLength(L)

求表長，即求線性表L中的元素個數(shù)?？毡淼拈L度為0。

(3)GetNode(L,i)

取線性表中的第i元素,要求1WiWListLength(L)。

(4)Locate(L,x)

在線性表L中查找值為x的元素，并返回該元素在線性表L中的位置

(5)InsertList(L,x,i)

在線性表的第i個位置插入新元素X。插入后的表長加1。

(6)DeleteList(L,i)

刪除線性表L的第i個元素，刪除后的表長減1。

上述運算并不是線性表的全部運算。對于實際問題中涉及的其他更為復雜的運

算，可以用基本運算的組合來實現(xiàn)。

※〈第二節(jié)〉

2.2線性表的順序表示和實現(xiàn)

1.順序表示

(1)順序表示：采用順序存貯方法，把線性表中的元素按邏輯次序依次存放

在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表即為線性表的順序標示，

簡稱為順序表.

(2)順序表的特點：

①邏輯上相鄰的元素在物理位置上也相鄰；

②順序表是一種隨機存取結(jié)構(gòu)。

順序表中的第i個結(jié)點ai的存儲地址LOC(ai)可通過下式計算：

LOC(ai)=LOC(al)+(i-l)XcIWiWn

其中，LOC(al)是開始結(jié)點al的存儲地址(即順序表的基地址)，c是每個結(jié)點

占用的存儲單元數(shù)。也就是說，在順序表中，每個結(jié)點的存儲地址是該結(jié)點在表中

的位置i的線性函數(shù),只要知道基地址LOC(al)和結(jié)點的大小c,就可以在相同時間

里求出任意結(jié)點的存儲地址。由此可見，順序表是一種隨機存儲結(jié)構(gòu)。

(3)順序表在程序設(shè)計語言上的表示

程序設(shè)計語言中的一維數(shù)組也是采用順序存儲，故可用數(shù)組存儲線性表中的元

素，用一個變量來表示線性表的長度。把這二者結(jié)合起來構(gòu)成結(jié)構(gòu)類型作為順序表

在程序設(shè)計語言環(huán)境下的實現(xiàn)。定義如下：

defineListsize100〃順序表可能的最大存儲空間，可根據(jù)實際需要法定，

現(xiàn)設(shè)為100。

typedefintdatatype；//datatype表示數(shù)據(jù)元素的類型，現(xiàn)假設(shè)為int。

typedefstruct{

datatypedata[Listsize]；//一維數(shù)組data用于存儲元素。

intlength；〃當前表的長度。

}Seqlist；

Seqlist是我們定義的一個結(jié)構(gòu)類型，可以把它看作是順序表在程序設(shè)計語言

上的實現(xiàn)。即線性表的順序存儲結(jié)構(gòu)。我們將在該結(jié)構(gòu)上介紹各種上算法。

2.順序表上基本運算的實現(xiàn)

(1)插入算法insertlist(Seqlist*L,Datatypex,intI)

算法思想：

判斷上溢和i值合法性，即IWiWn+1；

②將第i個到第n個元素從后往前依次后移；

將元素插入第個位置；

表長加1?

算法：

voidinsertlist(Seqlist*L,Datatypex,inti)

{〃將新結(jié)插入L所指的順序表的第i個結(jié)點之前

intj;

if(i<lIi>L->length+l||L->length>=Listsize)

error(z/positionerrororoverflow");

for(j=L->legth-l;j>=i-l;j—)

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

L->data[i-l]=x;

l->length++;

)

時間特性分析：

影響算法時間特性的主要因素是元素的后移，插入位置不同，后移操作的次數(shù)

也不同。最好情況是在表末插入，不需要移動元素，時間復雜度是0(1);最壞

情況是在表頭插入，需要移動全部n個元素，最壞時間復雜度是0(n)；通常，

我們通過計算元素的來反映算法時間特性。

在長度為n的線性表中第i個元素前插入一個元素，須移動n-i+1個元素，考

慮不同位置的插入概率pi,移動平均次數(shù)(移動次數(shù)的數(shù)學期望值)為：

-I

--：血

不失一般性，在等概率情況下pi=l/(n+l),所以

故，算法平均時間復雜度仍然是0(n)。

(2)刪除算法Deletelist(seqlist*L,inti)

算法思想：

判斷i值合法性，即IWiWn；

②將第i+1個到第n個元素從前往后依次前移;

表長減lo

算法：

voidDeletelist(Seqlist*L,inti)

{〃刪除L所指的順序表的第i個結(jié)點

intj;

if(i<lIIi>L->length)

error(,zpositionerror");

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

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

L->data[i-l]=x;

l->length一;

)

時間特性分析：

刪除算法的時間復雜度與插入算法的時間度基本相似，最好情況是刪除表末元

素，不需要移動元素，時間復雜度是0(1);最壞情況是刪除表頭元素，需要移

動n-1個元素，最壞時間復雜度是0(n)

在長度為n的線性表中刪除第i個元素，須移動n-i個元素，考慮不同位置的

插入概率pi,移動平均次數(shù)(移動次數(shù)的數(shù)學期望值)為：

J=工以吵

不失一般性，在等概率情況下pi="(n+l),所以

-口,n-1

E&=V-(n-z)=,

故，算法平均時間復雜度仍然是0(n)。

說明：

①插入算法中結(jié)點后移必須從后向前依次進行，刪除算法中結(jié)點前

移必須從前向后依次進行；

②結(jié)點邏輯序號由1開始，存儲位置(即向量下標)由0開始，應

注意算法中的對應。我們完全可以約定均從0開始將兩者統(tǒng)一起

來，這樣，算法將更簡單。插入、刪除算法均存在此問題。

③從時間復雜度分析可以看出，在順序表上進行插入或刪除操作，

幾乎要平均移動表中一半元素，所以，當表長較大且頻繁進行插

入和刪除操作時不宜采用順序存儲結(jié)構(gòu)。

※〈第三節(jié))

2.3線性表的鏈式存儲結(jié)構(gòu)

線性表的鏈式存儲結(jié)構(gòu)是采用鏈式存儲方法存儲線性表所形成的存

儲結(jié)構(gòu)，簡稱為鏈表。鏈表通常分為三類，即單鏈表(也稱為線性連

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

1.單鏈表

(1)單鏈表

為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個元素(結(jié)點值)的

同時還必須存儲其后繼結(jié)點的地址信息，這兩部分信息組成了鏈表中的

結(jié)點結(jié)構(gòu)：

其中，data域是數(shù)據(jù)域，用來存儲數(shù)據(jù)元素(結(jié)點值)，next域稱

為指針域，用來存儲結(jié)點的直接后繼結(jié)點的地址。線性表中的每個元素

均采用這樣的結(jié)點結(jié)構(gòu)存儲，通過每個結(jié)點的指針域?qū)⒕€性表中的個結(jié)

點按其邏輯順序鏈結(jié)在一?起，所形成的存儲結(jié)構(gòu)稱為單鏈表。并引入一

個指針變量指向表頭結(jié)點，稱為頭指針。頭指針唯一的確定一個單鏈

表。

為了運算方便，我們通常在開始結(jié)點之前引入一個附加結(jié)點，稱為

頭結(jié)點。

引入頭結(jié)點有如下優(yōu)點：

①第一個位置上的操作和在表的其他位置上的操作一致，無須特殊

處理；

②無論是否為空表，頭指針總是指向頭結(jié)點的非空指針，這樣，空

表和非空表的處理就可以統(tǒng)一為一種模式。

不帶頭結(jié)點和帶頭結(jié)點的單鏈表可用下圖表示

非空表：

卿*___

|凱，?*----------?刎八2

￡蠢…

head，

teal?

帶頭結(jié)點的空表的判定條件為：head==NULL；

帶頭結(jié)點的空表的判定條件為：head->next==NULLo

(2)特點

①表中各結(jié)點的存儲地址可以是連續(xù)的、也可以是不連續(xù)的，接點

的邏輯次序和物理次序不一定相同；

②便于進行插入和刪除操作。

(3)單鏈表的高級語言描述

typedefchardatatype;

typedefstructnode{

datatypedata;

structnode*next;

}Listnode;

typedefListnode*Linklist;

這里，我們定義了Listnode、Linklist等數(shù)據(jù)類型，前者為結(jié)構(gòu)類型，

后者是指向這種結(jié)構(gòu)類型結(jié)點的指針類型。通常用Linklist定義

頭指針變量,代表單鏈表用Listnode*定義工作指針以實現(xiàn)對單鏈

表中結(jié)點的操作。

在C語言中，分配結(jié)點和釋放結(jié)點的函數(shù)：

p=(Listnode*)malloc(sizeof(Listnode));

free(p);

函數(shù)malloc()可以動態(tài)地分配一個類型為Listnode的結(jié)點變量的空間

并返回其首地址賦予指針變量p；函數(shù)free(p)釋放p所指的結(jié)點

變量空間。

(4)線性表基本運算在單鏈表上的實現(xiàn)

①建立單鏈表

單鏈表分為帶頭結(jié)點和不帶頭結(jié)點兩類，建立單鏈表的方法分為頭

插法和尾插法兩種。

【算法1】(不帶頭結(jié)點、頭插法)

C語言算法見教材

【分析】首先建立空表：head=NULL；依次輸入線性表元素，生成

新結(jié)點*s,將新結(jié)點插入在開始結(jié)點(第?個表結(jié)點)之前，作

為新的開始結(jié)點：s->next=head;head=s;；

這種建表方法所建鏈表的結(jié)點次序與輸入元素次序正好相反，所

以，線性表中元素應逆序輸入。

【算法2】(帶頭結(jié)點、頭插法)

Linklistgreatlistf(viod)

{〃建立帶頭結(jié)點的單鏈表，返回單鏈表的頭指針

charch;

Linklisthead;〃定義頭指針head

Listnode*s;〃定義工作指針s

head=(Listnode*)malloc(sizeof(Listnode));

head-〉next=NULL;〃建立帶頭結(jié)點的空表

ch=getchar();//讀入第一個元素

while(ch!=,\n,){

s=(Listnode*)malloc(sizeof(Listnode));〃創(chuàng)建新結(jié)點

s->data=ch〃將讀入的值放入結(jié)點的數(shù)據(jù)

s->next=head->next;

head->next=s;//完成插入操作

ch=getchar();〃讀入下一個元素

return(head);〃返回頭指針

)

【分析】該算法與不帶頭結(jié)點的建表算法的區(qū)別在于建立初始空表

時，要建立頭結(jié)點，其它均相同。

上述兩算法時間復雜度取決于循環(huán)體中語句的執(zhí)行頻度，也就是線

性表的長度n,所以，時間復雜度為0(n)。

【算法3】(尾插法建表，)

C語言算法見教材。

【分析】不帶頭結(jié)點算法：首先建立空表，設(shè)置尾指針初值：head

=NULL;r=NULL;；依次輸入數(shù)據(jù)元素，生成新結(jié)點*s,若是

第一個結(jié)點，作特殊處理：head=s;r=s;,其他情況，依靠尾指

針r將新結(jié)點插入在表末，尾指針后移指向新的表末結(jié)點：r-

>next=s;：r=s;；最后讓表尾結(jié)點指針域為空。

若帶頭結(jié)點，算法簡化為：

初始設(shè)置：首先建立一個帶頭結(jié)點的空表，頭指針，尾指針均指向

頭結(jié)點；依次輸入數(shù)據(jù)元素，生成新結(jié)點*s,依靠尾指針r將新

結(jié)點插入在表末，尾指針后移指向新的表末結(jié)點：r->next=s;：r

=s;；最后讓表尾結(jié)點指針域為空。

算法的時間復雜度取決于線性表的長度n，為0(n)。

查找運算

【算法1】按序號查找：已知結(jié)點序號i,在單鏈表中查找，返回該

結(jié)點在鏈表中的位置。

C語言算法見教材。

【分析】在帶頭結(jié)點單鏈表中查找，首先，引入工作指針變量p指

向頭結(jié)點和計數(shù)變量j并初始化：p=head;j=O;；然后指針變量

p從前向后掃描鏈表中各結(jié)點，變量j同時計數(shù)，當j=i時查找

成功，指針變量p所指結(jié)點即為所找結(jié)點，當p->next=

NULL&&j!=i或j>i時查找失敗，說明i值指定不當(p->next=

NULL&&j!=i說明指針變量p已指向最后結(jié)點，尚未到第i個結(jié)

點,i值大于表長n,當j>i時，i小于0)。

算法中語句：p=p->next;是鏈表操作的典型操作，其功能是指針p

由所指結(jié)點移向其后繼結(jié)點。

時間特性分析：算法時間復雜度取決于循環(huán)語句的頻度，其和i值有

關(guān)，在等概率情況下，平均值為：

故，時間復雜度為：O(n)

【算法2】按值查找：給定特定值key,在鏈表中查找結(jié)點值等于特

定值key的結(jié)點，返回首次找到的結(jié)點的位置。

C語言算法見教材。

【分析】引入工作指針變量p指向鏈表的開始結(jié)點：p=head-

>next；依次掃描各結(jié)點，查找結(jié)點值與特定值key相等的結(jié)點，

若某結(jié)點滿足條件，則返回該結(jié)點的位置，若無此類結(jié)點，則返

回NULLo

與按序號查找算法一樣，時間復雜度為0(n)。

②插入運算

將值為x的新結(jié)點插入在鏈表的第i個結(jié)點之前。如下圖所示：

【分析】算法由三個基本步驟構(gòu)成：

首先將工作指針p定位于第i-1個結(jié)點(p=getnode(head,i-l)；若定位成

功，則構(gòu)成新結(jié)點(s=malloc(sizeof(linknode));s->data=x;)；第三步完成插

入，借助工作指針P將新結(jié)點插入在P所指結(jié)點之后，即第i-1個結(jié)點之

后(①s->next=p->next;②p->next=s;)。

算法的時間主要耗費在P指針的定位上，故時間復雜度與按序號查找算

法相同,為0(n)。

插入位置i的有效范圍是：lWiWn+1。插入操作的兩條語句必須按所標

次序進行。

刪除運算

將指定的第i個結(jié)點從鏈表中刪除。

如下圖所示：

c語言算法見教材。

【分析】算法由四個基本步驟構(gòu)成：

首先將工作指針P定位于第i-1個結(jié)點(①p=getnode(head,i-l)；

若定位成功,則將輔助指針s指向待刪除結(jié)點(②s=p->next;)；

第三步完成刪除(③p->next=s->next;)；

最后釋放被刪除結(jié)點(free(s);),將所占空間歸還給系統(tǒng)備用空間，即“存

儲池”。

算法的時間主要耗費在P指針的定位上，故時間復雜度與按序號查找算

法相同為0(n)o

刪除位置的有效范圍是：iWiWn。函數(shù)getnode(head,i-l)返回值為NULL

時，說明i<l或i>n+l,當i=n+l將返回最后一個結(jié)點的位置，即p-

>next=NULL,所以，可用p!=NULL&&p-〉next!=NULL來判定i值指

定的有效性。

2.循環(huán)鏈表

循環(huán)鏈表是種首尾相接的鏈表。在單鏈表上，將終端結(jié)點的指針

域指向表頭結(jié)點(不代頭結(jié)點時指向開始結(jié)點)，就形成了單循環(huán)鏈表。

在多種鏈表的基礎(chǔ)上，也可以構(gòu)成多重循環(huán)鏈表。單循環(huán)鏈表非空表和

空表如下圖所示：

非空表?

空賽”,

head3-

單循環(huán)鏈表為空的判定條件：head->next==head；

循環(huán)鏈表的特點：從表中任一結(jié)點出發(fā)，可訪問表中每一個結(jié)點。

鏈表操作經(jīng)常在表頭和表尾進行，利用循環(huán)鏈表的特點，通常引入尾指針

rear,以方便操作。這樣，表頭和表尾操作的時間復雜度均為0(1)

基本運算在循環(huán)鏈表上的實現(xiàn)和線性鏈表基本相同，區(qū)別在于終止

判定條件，即在線性鏈表上為p==null(或為p->next==null)改為

p==head(或p->next==head)o初始設(shè)置適當注意即可。

3.雙鏈表

(1)雙鏈表結(jié)構(gòu)

在單鏈表的基礎(chǔ)上增加一個指向前趨結(jié)點的指針域便形成了雙鏈

表。其結(jié)點結(jié)構(gòu)如下:

priordata

(2)雙鏈表的特點：通過前趨指針prior可以快速確定?個結(jié)點的直接

前趨位置(p-〉prior),所需時間是0(1),而這種操作在單鏈表上實現(xiàn)需從

頭結(jié)點進行查找，所需時間是0(n)。

將雙鏈表首尾相接亦可形成雙循環(huán)鏈表。

(3)基本運算在雙鏈表上的實現(xiàn)

刪除運算

將指定結(jié)點從鏈表中刪除。

如下圖所示：

花—--1

c語言算法見教材

【分析】首先修改指針刪除P所指結(jié)點：?p->next->prior=p-

>prior；(2)p->prior->next=p->next;；

然后釋放P所指的結(jié)點。

插入運算

將值為x的新結(jié)點插入在鏈表的指定結(jié)點*p之前。如下圖所示

C語言算法見教材

【分析】將新結(jié)點*s插入在p所指結(jié)點之前，應修改相應指針如圖

中標號所示。步驟為：

①s->prior=p->prior;②s->next=p->next;(3)p-prior->next=s;④p-

>prior=s;

雙鏈表中完成插入操作的操作步驟可以有多種組合，但應注意不能

首先完成步驟④，這樣將、導致無法找到前趨結(jié)點，使后續(xù)步驟無法完

成。

在操作位置已確定的情況下，雙鏈表中插入和刪除算法的時間復雜

度為。⑴。

4.順序表和鏈表的比較

順序表和鏈表各有優(yōu)缺點，通常從時間特性和空間特性兩方面來進

行分析。

基于空間特性的考慮

順序表的存儲空間是靜態(tài)分配的，要求事先明確規(guī)定它的存儲規(guī)

模。鏈表的存儲空間是動態(tài)分配的。當線性表的長度變化較大，存儲規(guī)

模難以預先確定時，宜采用鏈式存儲結(jié)構(gòu)；

順序表的存儲密度=1,鏈表的存儲密度<1；

基于時間特性的考慮

順序表是一種隨機存取結(jié)構(gòu)，適宜于直接存取，而不適合進行插入

和刪除操作；鏈表是一種動態(tài)存取結(jié)構(gòu)，適宜于動態(tài)的插入和刪除操

作，而不適合作直接存取操作。

當表的插入和刪除操作發(fā)生在表頭和表尾時，可采用循環(huán)鏈表并引

入尾指針。

在實際應用究竟選用哪種存儲結(jié)構(gòu)，要根據(jù)具體問題的要求和性質(zhì)

來決定。

※〈課堂練習>

課堂練習題

1.假設(shè)以帶頭結(jié)點的單鏈表作非遞減有序線性表的存儲結(jié)構(gòu)。請設(shè)

計一個時間復雜度為0(n)的算法，刪除表中所有數(shù)值相同的多余元素，

并釋放結(jié)點空間。例如：

(7,10,10,21,30,42,42,42,51,70)

經(jīng)算法操作后變?yōu)?/p>

(7,10,21,30,42,51,70)

【分析】算法思想：引入輔助指針p指向表中第一個元素結(jié)點；循

環(huán)與后繼結(jié)點比較，若相等則刪除后繼結(jié)點，否則，指針后移指向其后

繼結(jié)點，直到p指向鏈表的最后一個結(jié)點。

【答案】算法如下：

voiddellinklist(Linklisth){

p=h->next;

while(p!=NULL&&p->next!=NULL)

{s=p->next;

if(p->data==s->data){

p->next=s->next;

free(s);

)

elsep=p->next;

}endwhile

}//dellinklist

2.設(shè)A和B是兩個單鏈表，其表中元素遞增有序。試寫一個算法

將A和B歸并成一個按元素值遞減有序的單鏈表，并要求輔助空間為

0(1),請分析算法的時間復雜度。

【答案】算法如下：

voidllistmerge(LinklistA,LinklistB,Linklist*L)

{//A和B分別指向兩個單鏈表的頭結(jié)點，合并后頭指針由二級指針L

帶回

Listnode*p,*p;

*L=A；

(*L)->next=NULL;

A=A->next;

P=B;

B=B->next;

while(A&&B){

if(A->data<=B->data){

p=A->next;

A->next=(*L)->next;

(*L)->next=A;

A=p；}

else

{p=B->next;

B->next=(*L)->next;

(*L)->next=B;

B=p；}

while(B)

{p=B->next;

B->next=(*L)->next;

(*L)->next=B;

B=p；}

while(A)

{p=A->next;

A->next=(*L)->next;

(*L)->next=A;

A=p；}

)

時間復雜度分析留做課后習題。

3..閱讀下面的算法

Linklistmynode(LinklistL)

{〃L是不帶頭結(jié)點的單鏈表的頭指針

if(L&&L->next){

q=L;L=L->next;p=L;

SI:while(p->next)p=p->next;

S2:p->next=q;q->next=NULL;

)

returnL;

請回答下列問題：

(l)說明語句SI的功能；

(2)說明語句組S2的功能；

(3)用鏈表表示的線性表為(al,a2,…，an),寫出算法執(zhí)行后

的返回值所表示的線性表。

【分析】

題目所給算法的功能為：改變鏈表的結(jié)構(gòu)，將所給單鏈表的頭指針

移向第二個結(jié)點，將第二個結(jié)點作為鏈表的第一個結(jié)點，將原來的第一

個結(jié)點接在尾結(jié)點之后作為新的尾結(jié)點。

具體過程是：當表不為空或超過一個結(jié)點時，q指向第一個結(jié)點，

以便于將其追加在表末，頭指針L后移，指向第二個結(jié)點；p初值指向第

一個結(jié)點，通過循環(huán)語句(S1:所示)最后定位于最后一個結(jié)點上；S2:

所示語句組完成第一個結(jié)點追加在表末操作。

【答案】

(1)語句S1的功能：通過循環(huán)語句將P定位于最后一個結(jié)點上；

(2)語句組S2的功能：將q第一個結(jié)點追加在表末,應將其next域置

空。

(3)(a2,a3,…，an,al)

4.閱讀程序指出程序功能

voiddelnode(linknode*p)

{〃p指向帶頭結(jié)點循環(huán)鏈表中某結(jié)點

linknode*q;

q=p->next;

while(q->next!=p)

q=q->next;

q->data=p->data;

q->next=p->next;

free(p);

【答案】刪除循環(huán)鏈表中P所指結(jié)點的前趨結(jié)點。

5.以下函數(shù)中，h是帶頭結(jié)點的雙向循環(huán)鏈表的頭指針。

(1)說明程序的功能；

(2)當鏈表中結(jié)點數(shù)分別為1和6(不包括頭結(jié)點)時，請寫出程序中

while循環(huán)體的執(zhí)行次數(shù)。

intf(DListNode*h)

(

DListNode*p,*q;

intj=l;

p=h->next;

q=h->prior;

while(p!=q&&p->prior!=q)

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

(

p=p->next;

q=q->prior;

)

elsej=0;

returnj;

)

【分析】該算法功能是判斷鏈表中各結(jié)點的值是否以鏈表中間為軸

對稱相等，即表中第i個結(jié)點和第n-i+l個結(jié)點逐一比較，(其中，i=

1,2,…,)若均相同則返回1,否則返回0。算法引入兩個指針變量p、q分

別指向表中第一個元素結(jié)點和最后一個結(jié)點，然后循環(huán)逐一將對應元素

比較，直到中間位置。

【答案】(1)程序功能：該算法功能是判斷鏈表中各結(jié)點的值是否

以鏈表中間的結(jié)點為軸對稱相等。

(2)當鏈表中結(jié)點數(shù)為1時p=q直接退出循環(huán)，while循環(huán)體執(zhí)行

次數(shù)為0；當鏈表中結(jié)點數(shù)為6時，while循環(huán)體執(zhí)行次數(shù)為3。

返回頁首

第三章棧和隊列

◎〈教學目的和要求＞◎〈重點難點〉◎〈第一節(jié)〉

◎〈第二節(jié)〉◎(課堂練習＞

※〈教學目的和要求＞

本章的目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及在兩種結(jié)構(gòu)上如

何實現(xiàn)棧和隊列的基本運算。要求在掌握上和隊列的特點的基

礎(chǔ)上，懂得在什么樣的情況下能夠使用棧和隊列。

※(重點難點,

本章重點是掌握計算和隊列的兩種存儲結(jié)構(gòu)上實現(xiàn)的基本

運算，難點是循環(huán)隊列中對邊界條件的處理。

※〈第一節(jié),

3.1棧

3.1.1棧的定義及其運算

(1)棧：

是限制僅在表的一端進行插入和刪除運算的線性表。允許

進行插入和刪除的這一端稱為棧頂，另一端稱為棧底。當表中

沒有元素時稱為空棧。

(2)棧的特點：

從定義不難看出棧具有后進先出(Lastinfirstout)

的特點，簡稱為LIFO表。

(3)棧的基本運算：

Initstack(S)構(gòu)造一個空棧。

Stackempty(S)判定棧是否為空，若為空返回true,否

則，返回false?

Stackfull(S)判定棧是否已滿，若已滿返回true,否

則，返回false。該函數(shù)只適合于順序棧。

Push(S,x)進棧操作。若棧不滿，則將元素x壓入棧頂。

Pop(S)出棧操作。若棧S非空，則刪除棧頂元素并將該

元素返回。

Stacktop(S)讀取棧頂元素。若棧S非空，則返回棧頂元

素。

3.1.2順序棧

1.棧的順序表示與實現(xiàn)

由于棧是操作受限制的線性表，所以，線性表的存儲結(jié)構(gòu)

對棧的也適合。

順序棧類型定義如下：

#defineStacksize100//假定預分配的棧空間最多為

100個元素

typedefchardatatype;〃假定棧元素的數(shù)據(jù)類型為

char

tefstruct{

datatypedata[Stacksize];//用一維向量data作為棧

的存儲空間

inttop;//top為棧頂指針

}Seqstack;

可以看出棧被定義為結(jié)構(gòu)類型。在實際應用中，可根據(jù)具

體情況使用結(jié)構(gòu)型變量或指向結(jié)構(gòu)型變量的指針變量來表示

棧。

2.棧操作中應注意的問題：(設(shè)S是指向棧的指針)

①棧頂指針：S->top;棧頂元素：S->data[S->top];

②?？盏呐卸l件：S->top==-l；棧滿的判定條件：S-

top==StacksizeT；

③棧中的元素個數(shù)：S->top+l；

④若S是結(jié)構(gòu)型變量則所涉及操作中的S->應改為S.；

3.棧的基本運算在順序棧上的實現(xiàn)

(1)進棧操作(push(Seqstack*S,datatypex))

基本步驟：

若棧不滿，則

棧頂指針加1：S->top++;

元素入棧：S->data[S-top]=x；

(2)出棧操作(pop(Seqstack*S))

基本步驟：

若棧非空，則

讀取棧頂元素：x=S->data[S->top];

棧頂指針減1：S->top—；

返回棧頂元素：return(x)；

【分析】出棧操作和入棧操作是棧的兩種重要操作，應注

意操作的判定條件。棧的有效使用空間是0到Stacksize-1,

所以，當S->top==T時，表示棧空；當S->top==

Stacksize-1時,表示棧滿。時間復雜度均為0(1)。

3.1.3鏈棧

1.鏈棧及類型定義

棧以鏈式存儲方式存儲所形成的存儲結(jié)構(gòu)，稱為鏈棧。就

是單鏈表。

其數(shù)據(jù)類型定義如下：

typedefstructstacknode(

datatypedata;

structstacknode*next;

}Stacknode;

typedefstruct{

Stacknode*stop;

}Linkstack;

Linkstack*s;

2,鏈棧操作應注意的問題

與鏈表不同，鏈棧的插入和刪除操作僅限定在表頭位置進

行，所以，鏈棧不需要附加頭結(jié)點.

鏈表的頭指針就是鏈棧的棧頂指針：S->top；

棧頂元素為：S->top->datao

空棧的判定條件是：S->top==null.；

只要系統(tǒng)的備用空間能夠分配出存儲結(jié)點就不會發(fā)生上

溢。所以，程序員不必考慮鏈棧棧滿的問題。

鏈棧的操作就是單鏈表的操作，只需注意棧本身的操作要

求即可。如：進棧、出棧操作就是在表頭進行插入和刪除；求

棧中的元素個數(shù)就是求鏈表中的結(jié)點個數(shù)。

3.1.4棧的應用舉例

1.設(shè)計算法判斷一個算術(shù)表達式的圓括號是否正確配

對。(提示：凡遇'(’就進棧，遇')'就退掉棧頂?shù)?/p>

'(表達式掃描完畢，棧應為空)

算法

intbracketsmatch(chara[])

{〃設(shè)算術(shù)表達式以字符串形式存儲在數(shù)組中

Seqstack*S;

Initstack(S);

intk=0;

while(a[k]!=,\09)

if(a[k]==,(')Push(S,'(');

elseif(a[k]==,)')

if(Stackempty(S))return0;

elsePop(S);

if(Stackempty(S))return1;

elsereturn0;

}

2.一個雙向棧S是在同一向量空間里實現(xiàn)的兩個棧，它

們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計初始化

Initstack(S)、入棧push(S,x,i)和出棧pop(i)算法，其中,

i為0或1用于指示棧號。

算法

#definmaxsize100

typedefstructnode{

datatypedata[maxsize];

inttopi,top2;

}Seqstack;

(1)雙向棧的初始化

viodInitstack(Seqstack*S)

(

S->topl=-1;S->top2=maxsize;

)

(2)雙向棧入棧算法

viodpush(Seqstack*S,datatypex,inti)

{if(S->topl+l==S->top2)

erroe(overflow);

else

if(i==0)

{S->topl++;

S->data[S->topl]=x;}

else

{S_>top2--；

S->data[S->top2]=x;}

)

(3)雙向棧出棧算法

datatypepop(Seqstack*S,inti)

{if(i==0)

if(S->topl==-l)

error(downflow);

else

{returnS->data[S->topl]}

else

if(S->top2==maxsize)

error(downflow);

else

returnS->data[S->top2];

)

3.Ackerman函數(shù)的定義如下：

:n+1當m=0時

V

AKM(%9=文AKM(m-l,l)當mWO,n=

IAKM(m-l,AKM(mn-l))

5當mWO,n；

請寫出遞歸算法。

算法如下：

intakm(intn,intm)

{if(m==0)

returnn+1;

elseif(n==0&&m!=0)

returnakm(m-l,1);

else

returnakm(m-l,akm(m,n-1));

)

※〈第二節(jié)》

3.2隊列

3.2.1隊列的定義及其基本運算

1.隊列的概念

隊列：是一種操作受限的線性表。它只允許在表的一端進

行插入，在表的另一端進行刪除。允許刪除的一端稱為的隊頭

(front),允許插入的一端稱為隊尾(rear)。

當隊列中沒有元素時稱為空隊列。

隊列中包含的元素數(shù)稱為隊列的長度?？贞犃械拈L度為

0。

2.隊列的特點:

從定義不難看出隊列具有先進先出(firstinfirst

out)的特點，簡稱為FIFO表。

3.隊列的基本運算：

Initqueue(Q)：

置空隊。構(gòu)造一個供空隊列；

Queueempty(Q)：

判定隊列Q是否為空，為空返回真值，否則返回價假值;

Queuefull(Q)：

判定隊列Q是否已滿，若已滿返回真值，否則返回價假

值；

Enqueue(Q,x)：

入對操作。如果隊列不滿，則將元素x插入隊列Q；

Dequeue(Q)：

出隊操作。若隊列非空，則刪除隊頭元素并將其返回；

Queuefront(Q)：

讀取隊頭元素。若隊列非空，則返回隊頭元素。

3.2.2順序隊列

1.順序隊列與循環(huán)隊列

隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運

算受限的順序表。由于隊列的操作總是在表的兩端進行，所以

設(shè)置兩個指針分別指向?qū)︻^和隊尾位置。

順序隊列存在的“假溢出”現(xiàn)象，使得被刪除元素的存儲

空間永遠無法被重新利用，所以順序隊列不能充分利用存儲空

間。為解決假溢出現(xiàn)象，我們可以將向量空間想象為一個首尾

相接的環(huán)形結(jié)構(gòu)，并稱這種向量為循環(huán)向量，存儲在其中的隊

列稱為循環(huán)隊列。通常，我們總是在循環(huán)隊列上完成隊列的操

作。

2.循環(huán)隊列的類型定義：

#defineQueuesize100

typedefchardatatype;

typedefstruct{

datatypedata[Queuesize];

intfront,rear;

intcount;

}Cirqueue;

這里我們將循環(huán)隊列的存儲結(jié)構(gòu)定義為結(jié)構(gòu)類型

Cirqueueo應用時，可根據(jù)具體需要將隊列定義為結(jié)構(gòu)體變量

或指向結(jié)構(gòu)的指針變量。例如：Cirqueue*Q,Q1;其中，Q為指

針變量,Q1為結(jié)構(gòu)體變量注意二者訪問成員的方法不同。

3.循環(huán)隊列應注意的幾個問題

①隊頭指針和隊尾指針在循環(huán)意義下加1操作的實現(xiàn)：

(向量下標的有效范圍下界是0,上界是Queuesize-1)

Q->front=(Q->front+l)%Queuesize;

Q->rear=(Q->rear+l)%Queuesize;

②循環(huán)隊列隊滿、隊空的判定：

為了區(qū)別隊滿和隊空，有三種方法可供采用，分別為：

方法1：引入一個布爾變量以區(qū)別隊列的空和滿兩種狀

態(tài)；

方法2：采用少用一個元素的空間的策略，例如：隊頭指

針指向隊頭元素，隊尾指針指向隊尾元素下一個位置，則

隊空的判定條件為：Q-ront==Q->rear

隊滿的判定條件為：Q->front==(Q-

>rear+1)%Queuesize1；

但方法3：引入一個計數(shù)器記錄隊列元素的總數(shù)。

在眾多的參考書中更多地采用的方法2,應對方法2給予

足夠的重視。

4.基本運算在循環(huán)隊列上的實現(xiàn)(隊滿、隊空的判定采用方

法2)

(1)入隊操作

voidEnqueue(Cirqueue*Q,datatypex){

if(Q->front==(Q->rear+1)%Queuesize)

error("Queueoverflow");

else

{Q->data[Q->rear]=x;

Q->rear=(Q->rear+l)%Queuesize;}

)

(2)出隊操作

datatypeDequeue(Cirqueue*Q){