計算機軟件技7性礎安喙機能件也喳礎.一四密盤曲易1的一

第四章數據結構

長嫡學信息工程學院計算機基礎教學部

............1

計算機軟件技才基礎計算機軟件拉尤基礎

§4.1數據結構概述

?§4.1.1數據結構的定義

1、數據(data)：數據是一些可以輸入到計算機中的描述客觀事物的符

號，即信息的載體。這些符號可以是數值、字符、圖象等。在計算機領

域，人們把能夠被計算機加工的對象，或者說能夠被計算機輸入、存

儲、處理、輸出的一切信息都叫做數據。

2、數據元素(element)：數據元素是算法可以處理的最小數據單位，是

一個數據整體中相對獨立的元素。數據元素可以是簡單數據，也可以由

若干個簡單數據(數據項)組成數據元素。數據和數據元素是相對而言

的，是整體和個體之間的關系。例如，對一個字符串來說，每個字符都

是它的數據元素；對一個數組來說，每個數組元素都是它的數據元素。

本書中，經常將數據元素、數據結點、結點、記錄這些概念不加區別的

使用，它們表示的是同一概念。

長蛇學信息工程學院—^算機荃礎教學部2

計算機軟件技本若礎計菖“底件歸基此―一^計皿器傕版

3、數據項：數據元素由更小的單位——數據項Qtem)(或成員)所組成，一

個記錄一般包括一個或若干個數據項。

4、數據之間的聯系：現實世界中的客觀對象在計算機中是用數據來描述

的，在現實世界當中，客觀對象是有聯系的，因此數據之間也是有聯系的，

數據聯系是數據本身所具有的特性。

5、數據結構(datastructure)：簡單的說，數據結構就是研究數據和數據

之間聯系的一門學科，它包括三個方面。

①數據的邏輯結構

②數據的物理結構

③數據的運算

數據結構通常用二元組表示，其形式如下：

Data_struct=(D,R)

其中5為數據元素的集合，R為數據元素之間關系的集合。即：

D={ai|1WiWn,nNO}

R={rj|1WjWm,mN1}

ai為第i個數據元素，n為數據元素的個數，特別地，當n=0,D為空集，則

無結構可言。rj表示第j個關系，m為關系的個數。

計算機基礎教學部3

計算機軟件裝木基礎_安奧/絲件拉比基礎一皿IMk園儂砒

§4.1.2數據結構的基本內容

數據結構的基本內容包括數據的邏輯結構、數據的存儲結構和數據的運

算。

1、數據的邏輯結構

數據元素之間的邏輯關系就是數據的邏輯結構。

一般情況下，一組數據元素并不是雜亂無章的，而是具有某種聯系形式。這

里的聯系形式指數據元素與元素間的相互關系。數據之間的聯系可以是固

有的，也可以是根據數據處理的需要人為定義的。數據元素之間的聯系方

式可分為一對一、一對多和多對多三種，根據數據元素之間聯系的不同特

性，數據的邏輯結構通常有以下三種基本結構。

①線性結構數據結構中數據元素之間的聯系方式是一對一的。

②樹形結構數據結構中數據元素之間的聯系方式是一對多的。

③圖形結構或網狀結構數據結構中數據元素之間的聯系方式是多對多一

的。

通常&們也把數據的邏輯結構分為線性結構和非線性結構，樹形結構和圖形

結構統稱為非線性結構。

研究數據結構的目的是為了在計算機上實現對它的操作，因此還需研究如何

在計算機中表示數據結構。

長蟒學信息工程學院一一二會算機基礎教學部4

計算機軟件技才基礎一ghg機軟件皮忙基礎.計竟狐窿盤麗9為ik

2、數據的物理結構

數據結構（包括數據及其數據之間的關系）在計算機存儲器上的存儲表示稱為

數據的物理結構或存儲結構。數據結構研究的是數據及其數據之間聯系的學

科，因此在研究數據的存儲結構時，要求數據的存儲方式既能表示數據又能表

示數據之間的聯系。常用數據的存儲結構有：

順序存儲

鏈式存儲

索引存儲

哈希存儲

順序存儲結構的特點是借助元素在存儲器中的相對位置來表示數據元素之間的

關系；鏈式存儲結構是借助指示元素存儲位置的指針表示數據元素之間的關

系；索引存儲結構是為存儲的數據建立一個索引表，訪問數據時先在索引表中

查找，再根據索引表的相關信息訪問數據；哈希存儲是建立數據的關鍵字和存

儲地址之間的對應關系（哈希函數），這樣訪問一個數據時丁可根據哈希函數

直接獲得該數據在計算機中的存儲地址，到該地址訪問數據。

長鎮學信息工程學院――二會算機基礎教學部5

計算機軟件技木基礎計算機軟件技才基礎

由于數據的存儲結構有多種，所以一種數據的邏輯結構可以根據需要表示成

一種或多種存儲結構，只要存儲結構既能表示數據，也能表示數據之間的聯

系或者存儲結構能滿足用戶對數據的某種操縱要求即可。在后面的章節中，

讀者可根據具體的存儲實例了解到一種數據的邏輯結構可以采用不同的存儲

方式進行存儲。

數據的邏輯結構和物理結構是數據結構兩個密切相關的方面，以后讀者可看

到，一個算法的設計取決于選定的邏輯結構，而算法的實現依賴于采取的存

儲結構。算法的設計取決于數據的邏輯結構，算法的實現依賴于采用的存儲

結構，在不產生誤解的情況下我們也將數據的邏輯結構稱為數據結構

如何描述存儲結構呢？雖然存儲結構涉及數據元素及其關系在存儲器中的存

儲方式，但由于本書是在高級語言的層次上討論數據結構的操作，因此可以

借助高級語言中提供的“數據類型’來描述它。例如可以用C語言中提供的“數組

類型”來描述順序存儲結構，用“指針”來構造鏈式存儲結構。

長鎮學信息工程學院――二會算機基礎教學部6

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

3、數據的運算

研究數據結構，除了研究數據結構本身以外，還要研究與數據結構相關聯的運

算。這里的運算是指對數據結構中的數據元素進行的操作處理，而這些操作與

數據的邏輯結構和物理結構有直接的關系，結構不同，則實現方法也不同。運

算的種類很多，但常用的有以下幾種：

檢索（查找）：在給定的數據結構中，找出滿足一定條件的結點來，這個條件往

往是一個或幾個數據項的值。

排序：根據給定的條件，將數據結構中所有結點重新排列順序

插入：在給定的數據結構中，根據某些條件，將一個結點插入到一個合適的位

置。

刪除「在給定的數據結構中，根據某些條件，將一個結點刪除。

修改：修改數據結構中某些結點的值。

運算的種類很多，同一種運算也存在各種各樣的算法。在一種數據結構中要進行

那一種或那幾種運算，往往取決于要解決的實際問題。完成一種指定的運

算，當然要選一種最好的算法。但對一種具體的數據結構來說，完成一種運

算的效率較高，完成另外一種則可能較低，對另一種數據結構來說，情況可

能正好相反。因此，要解決一個實際問題，數據結構的設計和算法的選擇要

結合起來考慮，對各種情況要反復比較，最終選擇一個較好的數據結構和高

效率的算法。

長蟒學信息工程學院一一二會算機基礎教學部7

計算機軟件技木基礎計算機軟件技刁七基礎

§4.2線性表

?§4.2.1線性表的邏輯結構

線性表(linearlist)是具有相同特性的數據元素的一個有限序列。該序列中

所含元素的個數叫線性表的長度，用n表示，n^Oo當n=0時，線性表是一個

空表，即表中不包含任何元素。當nWO時，設序列中的第i個元素為ai

(1WWn),則線性表的一般表示為：

(a1,a2,.......,ai,.......，an)

其中，a1為第一個元素，又稱為表頭元素，an為最后一個元素，又稱為表尾

元素。每一個元素在表中的位置用其下標來表示。線性表具有如下特點：

長嫡學信息工程學院做算機整礎教學部8

計算機軟件技才基礎計算機軟件按方基僦一計篡，業隱露由匿匐限

1)線性表的數據元素ai具有相同特性，在不同的情況下含義不同。可以為一個

數、一個字符或更復雜的信息；在一個表中，ai類型必須相同。

2)表非空的情況下，除第一個元素以外，每個元素都有且僅有一個直接前驅；除

最后一個元素以外，每個元素都有且僅有一個直接后繼。

線性表中的元素在邏輯上是有序的，即第i個元素處在第i-1和第i+1個元素的中

間，這種邏輯上的有序性就是一種線性關系，所以線性表的邏輯結構是線性結

構。

用二元組表示為：

Linear_list=(D,R)

D={ai|1WiWn,n20,aieelemtype}/*elemtype為任何數據類型*/

R={r|r=<ai,ai+1>1WiWn-1}

下面給出幾個線性表的例子：

('O',T,2,3',4,5,5,6,7',8,‘9‘，

(12,34,56,78,89,54,76,32,98)

("basic"，“fortran"，“pascal"，“cobol")”

其中，第一個線性表數據元素為字符型，第二個線性表數據元素為數值型，第

三個線性表數據元素為字符串。

長鎮學信息工程學院――二會算機基礎教學部9

?§4.2.2線性表的存儲結構

線性表的存儲結構有兩種，即順序存儲結構和鏈式存儲結構。具有順序存

儲結構的線性表稱為順序表，具有鏈式存儲結構的線性表稱為線性鏈

表。根據不同的需要對線性表可以進行多種操作，其基本運算有：

1.清表清除表中的結點使其成為空表。

2.排序根據給定的條件，將表中結點重新排列順序。

3.插入根據條件在表中插入一個結點。

4.刪除根據某些條件，將一個結點刪除。

5.修改修改表中給定結點的值。

6.檢索（查找）查找表中某一特征的結點。

7.求長求線性表的長度。

對線性表所采取的存儲結構不同，其實現方法也不一樣。下面分別介紹。

長嫡學信息工程學院做算機整礎教學部10

計算機軟件技才基礎計算機軟件拉尤基礎

1、線性表的順序存儲結構及其算法

線性表的順序存儲結構是線性表的一種最簡單的存儲結構，其存儲方法是：在

內存中為線性表開辟一塊連續的存儲空間，該存儲空間所包含的存儲單元數要

大于等于線性表的長度(假定每個存儲單元存儲線性表中的一個元素)。

因為一個數組在內存中占據一段連續的存儲單元，所以可以借助數組來為線性

表的順序存儲開辟空間，如圖4.1所示。其中L為每個元素占據的字節數，

Loc(a1)為線性表的起始地址。

另外為了存儲線性表的長度，還要定

義一個整型變量。若將線性表的順序

存儲結構定義為一個數組與一個整型

變量，則可將它們放在一個結構體

中，C語言定義形式為：

#defineN1000/*N為線性表的最

大元素個數*/

typedefstructlist

{elemtypev[N];

intlen;

}LIST;

其中，N為線性表開辟的存儲單元

數，可以根據需要改變其大下。

elemtype為線性表中元素的類型。

長頓學信息工程學院――算峨礎教學部11

計算機軟件技才基礎計算方破隹拄本基礎一計算址密編的透A礎

|拿湖瞄洞本笑熏器搦睡海您泓的涮腳隅腳湖售海踞海腮涌湖㈱貨附眼黑輜袋。陽藤㈱陽率過舟淞皓抵瞄網錦湖㈱湖㈱泌㈱裝舟除淵樂捻湖群焚哥海涮舟網新

1|數犯下產01.i-li…L.康出

L.v@+L.V[1]P…?L.v[i-1]^L.v[i)^…―|Lv[L.Len?li

(a)插入前。

!防蛆下標01…i-lii+1L!至北

Lv叨/L.v[l]...「L.v[i-1]^x/L.v[i+1]^...?|L.Y[Llen?l]o-

(b)插入后。

圖4.2順序存儲結構插入運邕示意圖“

[&娜那觸蝌履軸溺腐凝撇薄海燃微解剛息液瓣溺燃潮魂趣題旗源施軸,舞蝴㈱◎攜舟除鼓腕勰弱獴廉赧建㈱海版耕浦海誨蟠睇薄懈腕蜩辛海期解談源通轉㈱回從算法中可見，當i的位置不

①插入運算合適時，插入無法進行。當

根據給定的條件不同，插入算法也不一樣，如果要表中有L.len個元素時，插入

在線性表L的第i(OWiWL.Ien)個位置上插入一個元位置可以是從0到L.len。當

素x,那么只需要將第i個元素及其以后的所有元素插入位置在最后一個元素的

后移一位，第i個位置上存入x,線性表的長度加后邊(即下標L.len)時，不

1,如圖4.2所示。需要移動元素。

LISTinslist(LISTL,inti,elemtypex)如果插入條件是：在線性表

{if(L.len==N)

中的某一元素之前(或之

printf("OVERFLOW\n")；

elseif(i<O)||(i>L.len)后)插入一一兀素，則應先查

printfC'positionERROR\n!,);找該元素的位置，然后利用

else上述方法實現即可。從圖4.2

{for(j=L.len-1;j>=i;j-)讀者可以看到在數據x插入

L.v[j+1]=L.v[j];L.v[i]=x;L.len++;}前后，線性表的有效元素都

returnL是從下表0到下標L.len-1。

讀者可自行編寫該算法。

長蟒學信息工程學院一一二會算機基礎教學部13

計算機軟件技木基礎計算機軟件技才基礎

②刪除運算

將線性表中的第i個元素刪除的情況，可以用圖4.3所示的方法實現。

下標01................7i................L.len-2VLSz.SlAeAAn/V-1^

L.v[O]。LM1]P…dLv[i-1]^ILvfil^??)LArfLJen-2]^L.vKJen-1]^

(a)刪除前。

下標0----------------1-------------------------------卜1-------------------1---------------------------------UerfelUen

Lv[i-l]pILv[i]^Ly[L.len-l]^L.v[L.len]-k

LylO]^Ly[lp???SAAAz**\WVV*V,???~

(b)刪除后。

圖4.3順序存儲結構刪除運算示意圖“

只要將從第i+1個元素到最后一個元素向前各移動

從算法中可見，當i的位置不合

一個元素，表的長度減一即可。相應的算法為：

適時，刪除無法進行。

LISTdellist(LISTL,inti)/*刪除線性表L中的第i

從圖4.3讀者同樣可以看到，在

個元素*/

第i個元素刪除前后，線性表的

{if(i<O)||(i>=L.len)

有效元素都是從下表0到下標

printfC'positionERROR'n")；

L.len-1o

else

如果刪除條件是：刪除線性表

{for(j=i+1;j<=L.len-1;j++)

中某一特定元素x,則應先查找

L.v[j-1]=L.v[j];

該元素x的位置，然后利用上述

L.len-;

方法實現即可。讀者可自行編

)

寫該算法。

returnL

}

長蟒學信息工程學院「一二會算機基礎教學部14

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

③檢索(查找)

在線性表而t橐值為x的元素，檢索的方法很多，有順序檢索、折半檢

索、分塊檢索、散列檢索等。下面僅介紹順序檢索，方法是，從線

性表的第一個元素起，依次使每一個元素與值為x的元素進行比

較，直到某個元素與X相等(既查找成功)或查完所有元素都找不

到值為X的元素(查找失敗)為止。算法為：

intsearchlist(LISTL,elemtypex)

{for(i=0;i<L.len-1&&L.v[i]!=x;i++);

if(i==L.len)

{printfC'notfound\n,");return-1;}

else

returni;

}

2、線性表的鏈式存儲結構及其算法

所謂鏈式存儲結構是用戶在編寫程序時，利用高級語言提供的功能自己構建

的存儲結構。用戶根據自己存儲數據的需要，向計算機系統申請隨機的存儲

單元，再將這些存儲單元利用指針聯系起來，構成鏈表。利用鏈式存儲結構

存儲線性表，把線性表的第一個元素存儲在鏈表的第一個結點，線性表的第

二個元素存儲在鏈表的第二個結點，…，線性表的最后一個元素存儲在鏈表

最后一個結點。

長蟒學信息工程學院一一二會算機基礎教學部15

計算機軟件技7座礎計冬山法件也匕基礎一分強加德偏位卮

結點地址■結點示意結點序號

［以”:頭結點

dl_^*ZZ第一個結點

ald2

d2第二個結點

第三個結點

第n個結點

這樣邏輯在前的元素，在鏈表中的位置鏈式存儲結構不要求邏輯上相鄰的元

也在前（注意：不是地址單元在前，實素物理位置（存儲地址）也相鄰。它

際上d1,d2,…,dn為隨機值，di與di+1的值的存儲特點是，用隨機的存儲單元存

之間沒有誰大誰小的關系），利用指針儲線性表中的元素，其存儲空間可連

訪問鏈表中的結點時，通常是通過頭指續、也可以不連續。因為存儲空間不

針獲得邏輯上的第一個結點的地址，通要求連續性，所以在存儲完每一個數

過第一個結點獲得第二個結點的地據元素的內容以后，還應指出下一元

址，…，因次對鏈式存儲的線性表訪問素的存儲位置，將這兩部分信息共同

時，邏輯在在前的元素訪問也在前。我稱為一個結點。，因此我們說，在線

們稱隨機存儲順序訪問。性表的鏈式存儲結構中利用指針表示

了元素之間邏輯上的順序關系。

長嫡學信息工程學院工營算機基礎教學部

計算機軟件技才基礎計算機軟件按方基僦一計篡，業隱露由匿匐限

一個鏈接表由n(n20)個結點組成，當n=0時稱為空表。每一個結點中

的指針域可以有一個，也可以有兩個。有一個指針域的鏈表稱為單鏈

表，其中的指針域存儲數據元素的后繼結點的位置。有兩個指針域的鏈

表稱為雙鏈表，其中一個指針域存儲數據元素的后繼結點的位置，另一

個指針域存儲數據元素的前驅結點的位置。下面我們介紹單鏈表幾個常

見的算法。

單鏈表的定義如下：

typedefstructnode

{elemtypedata;

structnode*next;

}NODE;

NODE*H;

設單鏈表H中有n個元素，分別為(a1,a2,……an),可以用圖4.4描述單鏈

表的結構。

長蟒學信息工程學院「一二會算機基礎教學部17

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

其中H為單鏈表中第一個結點的地址，稱為頭指針。最后一個元素an所

在的結點不存在后繼，因此其指針域的值為空(NULL),從上面的結構中

可以看到，鏈表在存儲空間上的要求比線性表要付出更大的代價，因為

它除了存儲數據元素外，還要存儲每個元素的后繼元素的位置。

判斷一個鏈表為空的條件為：H==NULLO

為了便于計算機算法編寫，在單鏈表的第一個元素所在的結點之前附設

一個結點一頭結點。頭結點的指針域存放第一個元素所在結點的存儲

位置，數據域不存儲任何信息，因此單鏈表的頭指針指向頭結點，如圖

4.5(a)為帶頭結點的單鏈表的一般形式。如圖4.5(b)為帶頭結點的

單鏈表為空時的形式。

H-*----------->a1-----?a2------*.=----------*anNULL

(a)帶頭結點的單鏈表

H—>/y/S?JLL

(b)帶頭結點的空單鏈表

圖4.5帶頭結點的單鏈表示意圖

長鎮學信息工程學院一—二會算機基礎教學部18

計算機軟件技才基礎計算機軟件按方基僦一計篡，業隱露由匿匐限

判斷一個鏈表是否為空的條件是：H->next==NULL

鏈表加上頭結點以后將空表和非空表的處理統一起來，因而簡化了單鏈表的

實現算法。

下面介紹在這種存儲結構上鏈表的幾個主要操作。

①帶頭結點單鏈表的查找

設H為一帶頭結點的單鏈表的頭指針，在線性表中查找第i(i>0)個元素所在的結點。

要查找單鏈表中的某一結點，必須從頭指針出發，沿結點的指針域往后找直到找到

所要結點為止。算法如下：

NODE*get(NODE*H,inti)

{NODE*p;

intj=1;

p=H->next;

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

{p=p->next;

j++；

)

if(p!=NULL)

returnp;/*返回指向待查找結點的指針*/

else

returnNULL;/*查找的位置不合適*/

)

查找元素的時間復雜度為0(n)。

長蟒學信息工程學院「一二下算機基礎教學部19

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

②帶頭結點單鏈表的插入

設H為一帶頭結點的單鏈表的頭指針，在線性表的兩個元素a和c之間插入一個

元素b,設p為存儲數據元素a結點地址的指針變量，設q為存儲數據元素b結

點地址的的指針變量，如圖4.6(a)所示

在一個以鏈式存儲的線性表的某個位置上插入一個結點，只需要改變其鏈

接關系就可以。從圖中可以看出插入結點b時，需要修改兩個指針，將a結

點的指針域的值由指向結點c改為指向結點b,再使結點b的指針域的值指

向結點c,從而實現改變a,b和c之間的鏈接關系，插入后各元素的關系如

圖4.6(b)所示。修改指針關系的語句為：

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

長鎮學信息工程學院一—二會算機基礎教學部20

計算機軟件技木基礎計算機軟件技才基礎

下面的算法是在鏈表H中第i個位置上插入一元素為x的結點：

voidinsnode(NODE*H,inti,intx)

{NODE*p,*q;

if(i==1)p=H;

else

p=get(H,i-1);/*查找插入元素的位置*/

if(p!=NULL)

{q=(NODE*)malloc(sizeof(NODE));

q->date=x;

q->next=p->next;p->next=q;/*實現插入*/

)

else

printf("iv1或者i>表長，插入位置錯誤\rT);

)

與順序表的插入比較，鏈表的插入更容易實現，不需要移動元素，只須修改

兩個指針，時間復雜度為0(1)。但是為了找到插入位置，需花費的時間復雜

度為。(n)。

長蟒學信息工程學院「一二會算機基礎教學部21

計算機軟件裝本勢礎_安奧/座件拉比基礎一皿IMk園儂砒

③帶頭結點單鏈表的刪除

刪除操作而插入基本相Q,應先找到待刪結點的前驅結點的位置后再完成刪

除。如圖4.7(a)所示，設b為待刪除的元素，p為指向待刪元素的前一結點

的指針，刪除結束后元素a的后繼由b改為c,操作中將b所在結點的地址記為

q,以便處理和回收結點，如圖4.7(b)所示。

刪除語句為：

q=p->next;p->next=q->next;free(q);

長鎮學信息工程學院一—二會算機基礎教學部22

計算機軟件技木基礎計算機軟件技才基礎

下面的算法是在頭指針為H的帶頭結點的單鏈表中刪除第i個結點：

voiddelnode(NODE*H,inti)

{NODE*p,*q;

if(i==i)p=H；

else

p=get(H,i-1);/*查找刪除元素的位置*/

if((p==NULL)||(p->next==NULL))

printf("表中無E匕結點\n");

else

{q=p->next;

p->next=q->next;

free(q);

)

)

與順序表的刪除比較，鏈表的刪除也更容易實現，不需要移動元素，

只須修改幾個指針，時間復雜度為0(1)。同樣為了找到刪除位置，需

花費的時間復雜度為0(n)。

長蟒學信息工程學院「一二會算機基礎教學部23

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

?§423算法評價及改進算法的各種策略

在前面兩節我們講解了線性表的兩中存儲方式，在這兩種存儲方式中我

們采用了不同的方式將線性表表示到計算機中。用這兩種存儲方式存儲

線性表時，既表示了數據，也表示了數據之間的聯系，同時我們看到，

在實現線性表的相關運算（查找、插入、刪除）時，兩種存儲結構采用

的算法完全不同，正如我們在§4.1.1.中所講：算法的設計取決于數據的

邏輯結構，算法的實現依賴于采用的存儲結構。下面我們分析線性表的

順序存儲和鏈式存儲在完成線性表的插入和刪除算法的時間復雜度和空

間復雜度。

1、算法評價

①時間復雜度

前面在§2.2.3節中，我們講到算法的時間復雜度的估算通常有兩中方法：

平均運算量和最壞的情況，對于具有n個元素的線性表的插入算法，在線

性表第12…,i,i+1個位置任意一個位置進行插入在實際運行時都有

可能，一個算法在實際使用的過程中，運行的次數很大，因此在任意一

個位置的插入運算可以看做是一個隨機量，在進行平均運算量的估算

時，按在每個位置插入的概率是均等的。

■■計算機基礎教學部24

計算機軟件技后若礎力啰機能1的座礎一±匕算四/盤函■1通—

下面我們估算線性表的順序存儲結構和鏈式存儲結構的時間復雜度。

順序存儲結構：順序存儲的線性表在第i個位置進行插入時，應將i到n個位置上的

元素依次向后移動，將要插入的元素存儲到第i個存儲單元，實現在線性表的第i

個位置插入元素的運算。

插入的位置數據移動的次數

n+10

n1

n-12

n-23

in-i+1

1n

在等概率的情況下，順序存儲的線性表中插入運算的平均運算量為：，

?+1X+111?+1y.

ASL=FjCj=------j+1|=------▽-j4-1,=—

H+1%+1H2

從上面的分析我們看到，線性表的順序存儲結構，在等概率的前提下平均運算量和數據

規模n是線性關系，也就是說平均運算量隙鰥規模的噌大線性噌長，其時間復雜度可表示

為：0(n)。0

長嫡學信息工程學院工次算機基礎教學部25

計算機軟件技木基礎計算機軟件技才基礎

鏈式存儲結構：在鏈式存儲的線性表的第i個位置插入元素，只要能夠獲得一個

指向第i-1個元素的指針，插入運算只需要進行下列面的兩個基本運算：

q->next=p->next;

p->next=q;

換句話說，線性表的鏈式存儲結構的插入運算的基本運算量，和插入的位置

無關，在線性表的任意位置插入元素的基本運算量均為2,基本運算量不隨數

據規模的增長而變化，其時間復雜度為：0(1)

②空間復雜度

假設線性/的每個元素存儲到計算機中，向系統申請的字節數為k,線性

表長度為n。

用順序存儲結構存儲線性表，則相應的算法運行時，向系統申請的臨時

空間字節數為：

k*n

用鏈式存儲結構存儲線性表，每個結點的指針域向系統申請的字節數為

2,則相應的算法在運行時向系統申請的臨時空間字節數為：

(k+2)*n

長蟒學信息工程學院「一二會算機基礎教學部26

計算機軟件技木基礎計算機軟件技才基礎

用線性表兩種不同的存儲方式設計算法時，從向系統申請的總的字節數來說，

鏈式存儲結構由于每個結點除存儲線性表的元素外，還需開辟存儲下一個結點

地址的指針，因此鏈式存儲結構向系統申請的總字節數比順序存儲結構多

（（k+2）*n>k*n）,但是，順序存儲的線性表向系統申請的是連續的存儲單

元（地址號連續的k*n個字節），而鏈式存儲的線性表向系統申請的是隨機的

存儲單元（n個隨機的（k+2）字節單元），從這一點上說，順序存儲的線性

表比鏈式存儲的線性表對系統存儲空間的要求高，鏈式存儲的線性表的空間復

雜度比順序存儲的線性表的空間復雜度小，即從空間復雜度上講，鏈式存儲的

線性表優于順序存儲的線性表。

比較線性表的鏈式存儲結構和順序存儲結構編寫的線性表的插入算法，我們可

以看到，鏈式存儲的線性表的算法的編寫對編程者有更高的要求。

綜上所述，線性表的鏈式存儲和順序存儲各有自己的特點，程序設計者在實際

編程中可根據實際情況選擇相應的存儲方式存儲線性表、操縱線性表。

查找算法的復雜度讀者可自行分析。

長蟒學信息工程學院「一二會算機基礎教學部27

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

2、算法的策略

①不帶頭結點的單鏈表和帶頭結點的單鏈表

通過前面的研究我們知道，鏈接存儲結構是線性表的一種存儲方式。在構造

鏈式存儲時我們采用的是將線性表的第1個元素存放放在單鏈表的第2個結

點，線性表的第2個元素存放放在單鏈表的第3個結點，…，線性表的第i個元

素存放放在單鏈表的第i+1個結點，…，這樣構造的單鏈表我們稱為帶頭結點的

單鏈表，當然在構造單鏈表時我們也可以將線性表的第1個元素存放在單鏈表

的第1個結點，線性表的第2個元素存放放在單鏈表的第2個結點，…，線性表

的第i個元素存放放在單鏈表的第i個結點，…，這樣構造的單鏈表我們稱為不

帶頭結點的單鏈表，因此我們說在構造線性表的鏈式存儲結構時;是否帶頭

結點是一種構造存儲的策略，在§4.2.2線性表的插入、刪除、查找運算中，

鏈式存儲的線性表采用的是帶頭結點的單鏈表，下面我們給出用不帶頭結點

的單鏈表存儲線性表插入運算的算法。用此算法和上面帶頭結點的單鏈表中

刪除第i個元素的算法進行比較，讀者可發現兩種方法的不同之處。

在不帶頭結點的單鏈表中進行操作時，要區分第一個結點和表中結點，因

為第一個結點的地址值發生變化后，表示鏈表的頭指針H的值也會發生變化

(參考圖4.4),比如刪除操作，若刪除的元素為a1,則刪除后H的值為a2

的地址，若是在帶頭結點的單鏈表中進行操作則不同(參考圖4.5

(a)),此時即使刪除的元素為a1,刪除后H的值也不會發生變化。

長鎮學信息工程學院一—二會算機基礎教學部28

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

voiddel(NODE*H,inti)/*將H為頭指針的鏈表中第i個結點刪除7

{NODE*p,*q;intm=1;

if(H!=NULL)

{q=H；

if(i==1)

{H=H->next;/*刪除表頭結點*/

free(q);)

else

{while(q!=NULL&&m<i)/*查找待刪結點q,q為第i個結點的前一結點7

{p=q;q=q->next;m++;}

if(q==NULL)

printf("%dnotbeenfound\n",i);/*沒找到待刪結點*/

else

{p->next=q->next;/*刪除結點q*/

free(q);}}}

else

printf("thelistempty\n");/*表空*/

)

通過帶頭結點和不帶頭結點兩種不同的存儲線性表的策略，我們明顯地看到，

在線性表的插入、刪除運算中，帶頭結點的單鏈表比不帶頭結點的單鏈表算法

思路簡潔、結構簡單。

長鎮學信息工程學院一—二會算機基礎教學部29

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

②循環單鏈表和雙向鏈表

采用鏈式存儲的線性表在算法設計中，對線性表的操作我們總是利用頭指針

找到被訪問的結點，對該結點進行訪問，而且這種訪問是單方向的（如果我

們需要訪問該結點的前一個結點，又必須從頭結點開始），這種情況下采用

單鏈表的存儲方式，運算的效率低。如果我們構建循環單鏈表和雙向鏈表來

存儲線性表，這樣對上述情況將會有所改觀。

循環單鏈表

如果有一個單鏈表其表尾元素的指針域的值不為NULL,而讓它指向頭結

點，這樣的鏈表叫循環單鏈表或環形鏈表。圖4.8為帶頭結點的循環鏈表

示意圖：Halan...（a）循環單鏈表a2空的表循環單鏈表

圖4.8循環單鏈表示意圖H

（空的表循環單鏈表

圖4.8循環單鏈表示意圖

長鎮學信息工程學院一—二會算機基礎教學部30

計算機軟件技術基礎計算“附件拉本基礎一計翦扎次年拉展A礎

循環單鏈表與單鏈表的大部分操作相同，如插入、刪除、查找等。與單鏈表比較有

以下不同點。

a)判斷鏈表結束的條件不同。設p為鏈表中任意一結點的指針，在單鏈表中當某

一結點p的next域指向NULL時，則說明鏈表操作結束(p->next==NULL)。而

在循環單鏈表中沒有指向NULL的指針，鏈表操作結束的條件應為：某一結點p

的next域指向表頭結點(p->next==H)。

b)從單鏈表的某一結點出發只能訪問到其后繼結點，所需的時間復雜度為

0(1),而循環單鏈表除了能訪問結點p的后繼結點外，也能訪問其前驅結

點，其方法是從此結點出發，找到滿足條件(q->next==p)的結點q,則q

為p的前驅結點，時間復雜度為0(n)。

c)采用單鏈表的形式存儲一個線性表，從一個結點出發只能夠訪問到該結點

的后繼結點，而采用循環單鏈表的形式存儲一個線表，從一個結點出發既

可以訪問到該結點的后繼結點，也可以訪問到該結點的前驅結點，也就是

說，從循環單鏈表的任意一個結點出發，可以訪問該鏈表的任意一個結

點。

長鎮學信息工程學院一—二會算機基礎教學部31

計算機軟件技才基礎機能件拉市基礎.一計常訕繞噩近造A礎一一

如果一個鏈表為循環鏈表，則許多操作可只對鏈表設一個尾指針，而沒有頭指

針，因為這樣更利于鏈表的操作，如鏈表的合并等。

上面我們我們對循環單鏈表存儲線性表進行了分析，我們看到采用循環單鏈表

的形式存儲線性表，從一個結點出發，可以訪問到線性表的任意一個結點，但

如果從一個結點出發訪問該結點的前一個結點，則算法的運算量最大（需要將

線性表中的所有結點均掃描一遍），如果我們采用雙向鏈表的形式存儲線表，

這種情況可以得到改觀。

雙向鏈表

如果在每個結點上再增加一個指向線性表中每個元素的前驅結點的指針

prior,就可以很方便的找到前驅結點（p->prior）或后繼結點（p-

>next）,這樣組織的鏈表可以使得我們從一個結點出發，既可以向后

訪問該結點的后繼結點，也可以向前訪問該結點的前驅結點，因此我們

稱這樣的鏈表為雙向鏈表。有時為了滿足需要，也為了操作的方便，用

雙向鏈表對線性表進行定義和操作。

長蟒學信息工程學院「一二會算機基礎教學部32

才算機軟件技7理礎計票機婪件放江B礎一^拉血窕能攝幽抽

雙向鏈表的定義如下。

typedefstructdnode

{elemtypenum;

structnode*prior,*next;

}DNODE

其中prior為指向前趨結點的指針，next為指向后繼結點的指針。

圖4.9(a)為雙向鏈表的示意圖，圖4.9(b)為空的雙向鏈表的示意圖，

表，圖4.10(b)為空的循環雙鏈表。

長嫡學信息工程學院原版教學晶獨算機基礎教學部33

計算機軟件技才基礎計算機軟件拉尤基礎

在雙向鏈表中凡涉及一個方向的操作與單鏈表一樣。只是在做插入和刪除時的操

作不同。

1）定位刪除

設p為待刪結點的指針，如圖4.11所示，

刪除語句為：

p->prior->next=p->next;

p->next->prior=p->prev;

free(p);

長頓學信息工程學院—算理礎教學部34

計算機軟件技才基礎計算機軟件拉尤基礎

2)定位插入

設p為待插入結點的位置，待插結點指針為q,在p結點之前或之后

插入均可。如圖4.12為在p結點之前插入q結點的示意圖。

在p結點之前插入的語句可描述為：

q->prior=p->prior;P

p->prior->next=q;z

p->prior=q;1

q->next=p;q-xj

(a)插入前

描述為：

q->next=p->next;

p->next->prior=q;

p->next=q;

q->prior=p;

長頓學信息工程學院—算理礎教學部35

計算機軟件技術基礎計算機軟件垓定基礎___計算如正編由透副h

3、算法舉例：

例il寫出在帶有頭結點的循環鏈表L中查找第i個元素的算法。

include<stdio.h>

NODEcreat(intn)/*創建帶頭main()/*主函數*/

typedefstructnode結點的循環單鏈表*/{NODE*p,*q;inti,n;

{intdata;{intnum;chart='y'；

structnode*next;NODE*head,*s,*p;printf("Pleaeinputthelengthof

}NODE;head=(NODE*)malloctheList

NODE*search(NODE*H(sizeof(NODE));scanf("%d",&n);

p=creat(n);

在帶頭結點的循環單鏈菜head->next=head;p=head;

inti)/*while(t=='y')

中查找第i個元素*/while(n>0)

{printf("Pleaseinputthe{printf("\nPleaseinputi=")；

{NODE*p=H->next;

datas:");scanf("%d",&i);

intj=1;scanf("%d",&num);while(i>n||i<1)

while(j<i&&p->next!=H)s=(NODE*)malloc{printf("ERROR!Pleaeinputi

{p=p->next;(sizeof(NODE));again:\n");

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

j++；s->data=num;

q=search(p,i);

)s->next=p->next;

p->next=s;p=s;printf("\nDatais:%d\n",q->data);

W==j)printf("\nContinueOrNot?(y/n)

returnp;n=n-1;

)")；

else

returnhead;scanf("\n%c",&t);

returnNULL;)})

長鎮學信息工程學院――二會算機基礎教學部36

計算機軟件技木基礎計算機軟件技才基礎

例2寫出一個將鏈表進行逆轉的算法。

#include<stdio.h>

typedefstructnode{intdata;structnode*next;}NODE;

main()

NODEturn(NODEH)/*逆轉

NODEcreat(intn)/*創建帶頭{NODE*p,*q,*t;intn,s;

函數7

結點的單鏈表*/printf("Pleaeinputthelengthof

{NODE*p=H,*q=H,*head;

{intnum;theList

head=(NODE

NODE*head,*s,*p;scanf("%d",&n);

*)malloc(sizeof(NODE));

head=(NODE*)malloct=creat(n);p=t;

while(p->next!=NULL)(sizeof(NODE));；

p=p->next;printf("Thelist'sdatais:\n")

head->next=NULL;while(p->n