高等教育自學考試 （自考）數據結構導論 全冊講義

第一章概論

一、學習目的與要求

理解數據、數據元素和數據項的概念及其相互關系；

理解數據結構的含義；

理解邏輯結構、基本運算和存儲結構的概念，意義和分類；

理解存儲結構與邏輯結構的關系；

理解算法的概念：

理解衡量一個算法效率的兩個標準：時間復雜度和空間復雜度。

二、課程內容

1.1引言

計算機處理問題的-?般步驟：

（1）從具體的問題抽象出一個適當的數學模型；

（2）設計一個求解該數學模型的算法；

（3）用某種計算機語言編寫實現該算法的程序，調試和運行程序直至最終得到問題的解答。

數據結構編程數據結構

原始數據（邏輯結構）（存錯結構）

處理要求*,

--程序語句序列

實際問題數學模型計算機程序實現

算法+數據結構:程序

1.2基本概念和術語

1.2.1數據、數據元素和數據項

數據：所有被計算機存儲、處理的對象。數值、布爾值等擴展到字符串、表格、圖像甚至聲音等。

數據元素（元素）：數據的基本單位，在程序中作為一個整體而加以考慮和處理。

數據項：一般情況下，數據元素由數據項組成。在數據庫中數據項又稱為字段或域。.它是數據的不可

分割的最小標識單位。

結合表1T,理解數據、數據元素、數據項三個概念及之間的聯系

表1-1學生檔案信息表

學號姓名性別年齡入學成績

1001王韜男2()589

1002潘小欣女21580

1003張艷女19568

1004趙李軍男185S0

1005劉勇男22585

1.2.2數據的邏輯結構

數據的邏輯結構是指數據元素之間的邏輯關系。所謂邏輯關系是指數據元素之間的關聯方式或“鄰接關

系”

四種基本的邏輯結構：

?集合：集合中任意兩個結點之間都沒有鄰接關系，組織形式松散。

?線性結構：一對一

?樹形結構：一對多

?圖結構：多對多

a）集合b）線性結構C）樹形結構d）圖結構

1.2.3數據的存儲結構

數據的邏輯結構在計算機中的實現稱為數據的存儲結構（或物理結構）。一般情況下，一個存儲結構包

括以下兩個部分：

（1）存儲數據元素；

（2）數據元素之間的關聯方式。

主要的存儲方式：順序存儲、鏈式存儲。順序存儲方式是指所有存儲結點存放在一個連續(xù)的存儲區(qū)里。

利用結點在存儲器中的相對位置來表示數據元素之間的邏輯關系。鏈式存儲方式是指每個存儲結點除了含

有一個數據元素外，還包含指針，每個指針指向一個與本結點有邏輯關系的結點，用指針表示數據元素之

間的邏輯關系。

除了上述兩種存儲方式之外，還有索引存儲方式和散列存儲方式。

1.2.4運算

運算是指在某種邏輯結構上施加的操作，即對邏輯結構的加工。這種加工以數據的邏輯結構為對象。一

般來說，在每個邏輯結構上，都定義了一組基本運算，這些運算包括：建立、查找、讀取、插入和刪除等。

1.3算法及描述

一個算法給規(guī)定了求解給定問題所需的處理步驟及其執(zhí)行順序，使得給定問題能夠在有限的時間內被求

解。本書采用類C語言來描述算法

1）函數描述形式.

函數類型函數名（函數參數表）〃算法說明

{

語句序列

）

2）輸入、輸出語句

輸入語句：scanf（格式串，變量1,變量n）；

輸出語句：printf（格式串，變量1,變量n）；

3）賦值語句變量名=表達式；

4）選擇語句

1＞條件語句：

if（表達式）語句：

或

if（表達式）語句；

else語句；

2》分支語句：

switch

{case條件1：語句序列；break；

case條件2：語句序列;break；

case條件n：語句序列；break；

default：語句序列；}

其中“default：語句序列；”可以省略。

5）循環(huán)語句

for（賦初值表達式序列；條件；修改表達式序列）語句；

while（條件）語句；

do,

語句；

}while（條件）；

6）結束語句

1＞函數結束語句：return表達式；

2＞case結束語句break；

3》異常結束語句：exit（異常代碼）；

7）出錯語句：error（"錯誤描述"）

8）注釋

單行注釋：〃注釋內容

多行注釋：/*注釋內容*/

1.4算法分析

通常評價算法好壞的因素包括以下幾個方面：

1)正確性：能正確地實現預定的功能，滿足具體問題的需要。

2)易讀性：易于閱讀、理解和交流，便于調試、修改和擴充。

3)健壯性：即使輸入非法數據，算法也能適當地做出反應或進行處理，不會產生預料不到的運行結果。

4)時空性：一個算法的時空性是指該算法的時間性能(或時間效率)和空間性能(或空間效率)，前

者是算法包含的計算量，后者是算法需要的存儲量。

1.4.1時間復雜度

【例1-4】編制函數求1!+制+...求!。

【分析】對于這個問題，可以寫出兩個算法，如圖所示。

intfactl(intn)intfact2(intn)

{intirj,temp,s;{intirjrtemp,s;

s-0;s-0;temp-1:

fori++)for(i-1;i<-n;i+*)

{temp-1;{temp-temp*i;

for(j-1;j<-i；j++)s-s+temp;

temp-temp*j;).

s-s+temp;returns;

))

returns;

兩個算法的計算量不同，如何估算算法的計算量?可在算法中合理地選擇一種或幾種操作作為“基本操

作”，對給定的輸入，確定算法共執(zhí)行了多少次基本操作，可將基本操作次數作為該算法的時間度量。

假如問題的輸入規(guī)模為n,一般情況下，一個算法的計算量是問題規(guī)模n的函數。設函數factl中乘法、

加法司賦值的次數記為T(n),則

T(n)=n(n+1)/2+n+n(n+1)/2+2n-l=2(n2+n)/2+3n+l=n2+4n+l

當n充分大時，i?這一項對T(n)的值起著支配作用，采用數學記號0(n2)表示T(n)的近似值，寫

為T(n)=0(n2),這種表示法稱為大0表示法，它的含義是：當n充分大時，算法的執(zhí)行時間與產成

正比,大。表示法的具體提法是：當且僅當存在正常數c和n。，使得：T(n)<=cf(n)。

對所有n>n。成立。其中，f(n)為問題的規(guī)模n的某個函數，大0表示法也稱為漸進表示法，它不考慮

具體的運行時間，只給出算法在問題規(guī)模n下執(zhí)行時間的上界。

T(n)=0(f(n))稱為算法的漸進時間復雜度，簡稱時間復雜度。

3

常見的時間復雜度有：常數階0(1),對數階0(log2n),線性階0(n),多項式階0(M)、0(n),

指數階0(20)

最壞時間復雜度、平均時間復雜度、最好時間復雜度

1.4.2空間復雜度

一個算法的空間復雜度定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數。通?？捎洖椋篠(n)

=0(g(n))其中，g(n)為問題規(guī)模n的某個函數?？臻g復雜度是對一個算法在運行過程中臨時占用存

儲空間大小的量度。

一個算法在執(zhí)行期間所需要的存儲空間量應包括以下三個部分：

(1)程序代碼所占用的空間

(2)輸入數據所占用的空間

(3)輔助變量所占用的空間

三、考核的知識點與考核要求

1.數據結構、數據、數據元素和數據項的概念

識記：數據結構；數據；數據元素；數據項。

領會：數據結構的作用；數據、數據元素、數據項三者關系。

2.數據邏輯結構和數據存儲結構

識記：數據邏輯結構、數據存儲結構。

領會：四類基本邏輯結構的特點；順序存儲結構；鏈式存儲結構；邏輯結溝與存儲結構的關系。

3.運算、算法和算法分析

識記：運算；基本運算；算法分析；時間復雜度；空間復雜度。

領會：運算與數據結構的關系；算法的描述方法；算法的評價因素；時間復雜度分析方法；空間復雜度

分析方法。

簡單應用：運用類C語言描述算法；簡單算法時間復雜度分析：簡單算法的空間復雜度分析。

四、本章重點、難點

本章重點：數據結構、數據邏輯結構、數據存儲結構以及運算等概念。

本章難點：算法時間復雜度分析。

五、練習

【例題?單選題】與數據元素本身的形式、內容、相對位置、個數無關的是數據的()。

A.存儲結構

B.邏輯結構

C.類型

D.運算實現

I1正確答案JB

『答案解析』數據的物理存儲、數據類型、運算實現與數據元素本身的形式、內容、相對位置，個數都

密切相關，而邏輯結構反映的是數據元素之間的鄰接方式。參見教材P25。

【例題?單選題】算法時間復雜度指的是()。

A.一個算法的確切執(zhí)行時間

B.一個程序的確切執(zhí)行時間

C.算法在給定輸入下的計算量

D.算法在給定時間下的計算量

『正確答案」C

『答案解析』首先算法的時間復雜度是對計算量的估算，其含義是對給定的輸入，確定算法共執(zhí)行了多

少次基本操作。參見教材P29。

【例題?單選題】下面幾種算法時間復雜度階數中()最小。

A.0(logn)

B.O(n)

C.O(n2)

D.O(2n)

『正確答案』A

I1答案解析』對于常見的幾種算法時間復雜度而言：0(1)<0(logn)<0(n)<0(nlogn)<0(n2)<0

(n3)<0(2n)<0(n!)<0(nn)?參見教材P30。

【例題?單選題】下面幾種算法時間復雜度階數中()最大。

A.0(logn)

B.O(n)

C.O(n2)

D.0(nlogn)

I1正確答案』C

I1答案解析』對于常見的兒種算法時間復雜度而言：0(D<0(logn)<0(n)<0(nlogn)<0(n2)<0

(n3)<0(2n)<0(n!)<0(nn)o參見教材P30。

【例題?單選題】算法的空間復雜度指的是()。

A.算法本身所占用的存儲空間的大小

B.算法中輸入數據所占用的存儲空間的大小

C.算法中所占用的所有存儲空間的大小

D.算法中除輸入數據占用的存儲空間之外所需的附加存儲空間的大小

『正確答案』D

f答案解析」算法的空間復雜度定義為該算法所耗費的存儲空間。參見教材P31。

【例題?填空題】從數據結構的觀點看，通常所說的“數據”應分成三個不同的層次，即、

___________和___________

『正確答案』數據、數據元素、數據項

I1答案解析J這道題考察關于數據的桂關概念。參見教材P24。

【例題?填空題】數據項又稱為—或,它是數據的不可分割的最小標識單位。

『正確答案』字段、域

I1答案解析』這道題考察關于數據的相關概念。參見教材P24。

【例題?填空題】根據數據元素之間關系的不同特性，通常有______、_______、________和

四類基本邏輯結構，它們反映了四種基本的數據組織形式。

『正確答案』集合、線性結構、樹形結構、圖結構

I1答案解析』這道題考察關于數據的匹種邏輯結構。參見教材P25。

【例題?填空題】一般情況下，一個算法的時間復雜度是的函數

r正確答案J算法輸入規(guī)模

『答案解析』這道題考察時間復雜度的概念"參見教材P29。

【例題?填空題】常見算法時間復雜度的階數有常數階0()、對數階0()、線性

階0(_________)、平方階0()和指數階0()。通常認為，具有指數階量級的算

法是的，而量級低于平方階的算法是。

［正確答案［1、logn.n、n\2\實原不可計算、高效

I■答案解析』這道題對考察時間復雜度的理解，應該掌握常見的幾種時間復雜度的大小關系及其含義。

參見教材P30。

【例題?填空題】下述算法的時間復雜度T(n)=

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

(

k++；

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

m+=k；

)

『正確答案』0(n2)

［答案解析］這道題考察算法時間復雜度的計算。參見教材P30。

第二章線性表

一、學習目的與要求

順序表和單鏈表分別是簡單、基本的順序存儲結構和鏈式存儲結構。順序表和單鏈表上實現基本運算的

算法是數據結構中簡單和基本的算法。這些內容構成以下各章的重要基礎，因此本章是本課程的重點之一。

本章要求：理解線性表的概念；熟練掌握順序表和鏈表的組織方法及實現基本運算的算法；掌握在順序

表和鏈表上進行算法設計的基本技能；了解順序表與鏈表的優(yōu)缺點。

二、課程內容

2.1線性表的基本概念

線性表中結點具有一對一的關系，如果結點數不為零，則除起始結點沒有直接前驅外，其他每個結點有

且僅有一個直接前驅；除終端結點沒有直接后繼外，其他每個結點有且僅有一個直接后繼。

線性表基本運算有：初始化、求表長、讀表元素、定位、插入、刪除。

2.2線性表的順序存儲

2.2.1線性表的順序存儲

線性表的順序存儲：邏輯結構相鄰的結點其存儲位置也相鄰。用順序存儲實現的線性表稱為順序表，一

般用數組來表示順序表，如圖2-1所示

空閑

---------------人--------------

3???

致俄下標：0IMaxsizc-I

圖2T順序表不意圖

【例2-1】學生檔案信息表的順序存儲實現。

【分析】根據學生檔案信息，給出順序表具體的類型定義。

constintMaxsize-7;〃頸先定義數組大小

typedefstruct

{intnum;〃學號

charname[8];〃姓名

charsex[2];〃性別

intage;〃年齡

intscore;〃入學成績

}DataType;〃定義結點的類型

typedefstruct

(DataTypedata[Maxsize];〃存放數據的數組

intlength;〃線性表的實際長度

)SeqList;〃取序表的類型

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

2.2.2線性表的基本運算在順序表上的實現

插入

順序表的插入運算InsertSeqlist(SeqListL,DataTypex,inii)是指在順序表的第i(l<=i<=n+l)

個元素之前，插入一個新元素x。使長度為n的線性表(a】，a2,,a-,a”...，a?)變?yōu)殚L度為n+1

的線性表(ai,a2>...?a(-i,x,ai,...?a,.)。

始入位H

空闈

ttiflF幄0i-2i-lin-lnMaxsize-1

空位空閑

敏倒下標:MAXsize-1

ftflF標:MJUMZC-I

圖2-2a)插入前b)插入前，移出空位之后c)插入x后

具體算法描述如下：

voidInsertSeqlist(SeqListL,DataTypex,int幼

(〃將元素x插入到履序表L的第i個數據元素之前

if(L.length-"Maxsize)exit('表己H;

if(1<1||i>L.len9th*l)?xitC位置榜?“〃檢杳插入位置是否合法

for(j?L.length〃初始i-L.length

L.data[j]"L.data[j-l];〃依次后移

L.data(i-l]ax;〃元素x置入到下標為1T的位置

L.length”；〃表長度加1

}

2)刪除

刪除運算DeleteSeqlist(SeqListL,inti)是指將線性表的第i(l<=i<=n)個數據元素刪去，使

長度為n的線性表(ai,a2?...,a1,at,at*t>...?an)變?yōu)殚L度為nT的線性表(ai,a2,...,al,

ai+l,?..,Hn)?

胸下*:

a)

蝴

的下標:

b)

圖2-3順序表刪除元素前、后的狀況示意圖

a)刪除前b)刪除后

具體算法描述如下:

voidDeleteSeqList(SeqListL,inc

(〃副除線性表L中的第i個數據結點

if(1<1|I1>L.length)〃檢香位置是否合法

exit(?非法位置?)；

for(j-i;j<L.length;j++)〃第i個元素的下標為i-1

L.data[j-l]?L.data[j];〃依次左移

L.length一;〃表長度充1

3)定位

定位運算LocateSeqlist(SeqListL,DataTypex)的功能是查找出線性表L中值等于x的結點序號的

最小值，當找不到值為x的結點時，返回結果0。下列算法從左往右掃描順序表中的元素，考察元素的值

是否等于X,描述算法如下：

intLocateSeqlist(SeqListL,DataTypex)

(

inti-0;

while((i<L.length)u(，&8[1]!”))〃在順序表中查找值為乂的結點

if(i<L.length)return-i+1;〃若找到值為x的元素，運回元索的序號

elsereturn0;〃未查找到值為x的元素，返回0

2.2.3順序表實現算法的分析

插入：0(n)

刪除：0(n)

定位：0(n)

2.3線性表的鏈接存儲

2.3.1單鏈表的類型定義

線性表的鏈接存儲是指它的存儲結構是鏈式的。線性表常見的鏈式存儲結構有單鏈表、循環(huán)鏈表和雙向

循環(huán)徒表，其中最簡單的是單鏈表。

下面舉個例子說明單鏈表的結構：

00000000

圖2-4

單鏈表的一個結點由兩部分組成：數據元素和指針，相當于火車的車廂和車鉤。各個結點在內存中的存

儲位置并不一定連續(xù)。鏈表的結點可以重新連接，相當于火車的編組。

圖2-5

如圖所示，data部分稱為數據域，用于存儲線性表的一個數據元素，next部分稱為指針域或鏈域，用

于存放一個指針，該指針指向本結點所含數據元素的直接后繼結點。

非空的單鏈表和空單鏈表，如圖所示

■站點尾紿點

｛』［NULL

NULL

圖2-6單捱表示例

a）非空的單鏈表b）空單鏈表

我們通常用結構體類型來定義單鏈表的結點數據類型:

單鋅表的類型定義如下：

Typedefstructnode

（

DataTypedata；//數據域

structnode*next；〃指針域

}Node,*LinkList；

【例2-2】學生檔案信息鏈表的類型完整描述

typedefstruct

{intnum;〃學號

charname[8];〃姓名

charsex[2j;〃性別

intage;〃年齡

intscore;〃入學成績

)DataType;〃定義結點的類型

typedefstructnode

(DataType.data;〃數據城

structnode?next;〃指針城

}Node,*LinkList;//Node是篋表結點的類型

LinkListhead;

則學生檔案信息鏈式存儲實現，如圖2-7所示

head-?

圖2-7

為了便于運算實現，在單鏈表的第一個結點之前增設一個類型相同的結點，稱之為頭結點，其他結點稱

為表結點。

b)

圖2-8帶頭結點的單捱表

a）帶頭結點的非空單鏈表b）帶頭結點的空單鏈表

2.3.2線性表的基本運算在單鏈表上的實現

我們首先來討論單鏈表的一些基本運算，這是使用單鏈表的開始。

初始化

初始化的工作是建立一個空表，空表由一個頭指針和一個頭結點組成。

算法描述如下：

LinkListInitiateLinkList()

〃建立一個空的單健表

(

LinkListhead;〃頭指針

head?malloc(sizeof(Node));〃動態(tài)構建一結點,它是頭結點

head->next-NULL;

returnhead;

}

2.求表長

在單鏈表存儲結構中，線性表的表長等于單鏈表中數據元素的結點個數，即除了頭結點以外的結點的個

數。圖2-9所示為數據域為整數的單鏈表，其表長為4。

圖2-9

通過結點的指針域來從頭至尾訪問每一個結點求表長，讓工作指針P通過指針域逐個結點向尾結點移動,

工作指針每向尾部移動一個結點，讓計數器加1。這樣，直到工作指針p-〉next為NULL。

算法描述如下：

intLengthLinklist(LinkListhead)

〃求單儲表表head的長度

{Node■p-head;〃p是工作指計,初始時p指向頭結點

intcnt-0;〃計數器段初值

while(p->next!-NULL)〃判斷是否為尾結點

(p?p->next;〃指針移動到F一個站點

ent+f;

returnent;〃返回表長

3.讀表元素

通常給定一個序號i,查找線性表的第i個元素。從頭指針出發(fā)，一直往后移動，直到第i個結點。

單徒表的讀表元素算法描述如下：

Node*GetLinklist(LinkListhead,int1)

〃在單處表head中查找第i個元素結點,若找到,則返回指向該結點的指針;否則返回NULL

Node*p;〃p是工作指針

p-head->next;〃初始時,P指向首結點

intc-1;

while((c<i)&&(p!-NULL))〃當未到第i結點且未到尾結點時維埃后移

(p-p->next;C++;}

if(i—c)returnp;〃找到第i個站點

elsereturnNULL;〃i<l或i>n,i值不合法,1E我失效

}

4.定位

線性表的定位運算，就是對給定表元素的值，找出這個元素的位置。從頭至尾訪問鏈表，直至找到需要

的結點，返回其序號。若未找到，返回0。

定位運算算法描述如下：

intLocateLinklist(LinkListhead,DataTypex)

〃糕head中第一個值等于x的球的序號，若不存在研軸,詆醐果為0

Node*p?head;//pftim

PT>->next;〃初始時p指向首獻

inti-0;〃i快獻的*%這星物值為0

while(p!-NULLUp-xiata!-x)〃訪問隹表

(i**;

p?p->next;

if(p!?NULL)returni+1;

elsereturn0;

)

5.插入

單性表的插入運算是將給定值為x的元素插入到鏈表head的第i個結點之前。插入結點的指針變化如

圖2-10所示。

lead

?'?:41J(JI**1>T4|NULL

帆/?

pQ—?x

圖2-10

插入算法描述如下:

插入算淵遨嚇：

voidInsertLinklist(LinkListhead>DataTypex*inti)

〃在表head的第i個數據元素結點之前插入一個以x為值的新站點

{Node*pr*q;

if(i?l)q-head;

elseq-GetLinklist(head,i-1);〃找第i-1個數碧元素結點

if(q-NULL)〃第個結點不存在

exit(哦不期I入的位加);

else

{p-malloc(sizeof(Node));p->data-x;〃生成新結點

p->next=q->next;〃新結點鏤域指向*q的后繼結點

q->next*p;〃修改*q的鞋城

注意：p>next=q>next和q>next=p兩條語句的執(zhí)行順序不能顛倒。

6.刪除

刪除運算是給定一個值i,將鏈表中第i個結點從鏈表中移出，并修改相關結點的指針域，以維持剩余

結點的鏈接關系。刪除結點的指針變化如圖2-11所示。

圖2-11

單銖表的刪除運算算法描述如下:

voidDeleteLinklist(LinkListhead,int1)

〃劇除表head的第1個結點

(Node*q;

if(i??l)q*head;

elseq-GetLinkli8t(head,i-l);〃先找持翻結點的宜族前驅

if(q!-NOLL&&q->next1-NULL)〃若直接前驅存在且待刪結點存在

(

p-q->next;〃p指向待加結點

q->next-p->next;〃移出符M結點

free(p);〃釋放已移出結點P的空間

)

elseexit「找不到要!!除的結點”)；〃結點不存在

注意，free(p)是必不可少的，無用結點需要釋放它的空間。

2.4其他運算在單鏈表上的實現

2.21建表

我們討論建立含頭結點的單鏈表。

方法一：尾插法，這個過程分為三部，首先建立帶頭結點的空表；其次建立一個新結點，然后將結點連

接到頭結點之后；重復后面兩個步驟，直到線性表中所有元素鏈接到單鏈表中。

代瑪描述如下：

LlnkLiatCreatLinkliitl<)

調用InitiateLinkllstmIns^rtllnkllst實現龍發(fā)算法?假定0是輸入結束標志

(Llnklltthead;

intx,i;

head?Initl?t?Llnklist();〃建立空哀

1-1;〃置Ml入位置初值

■c?nf《"Qd".&x);//讀入第一個斂據元素，X為整型

while(x!"0);〃必人的不是靖束標志時逑就插入

(f

InaertLinkliat(head,x,l);〃將珀入插入到h?2農足

〃修改循入位置

scant4x);//讀下一元素

returnhead;

\

方法二：上面的算法由于每次插入都從表頭開始查找，比較浪費時間。因為每次都是把新的結點鏈接到

表尾，我們可以用一個指針指向尾結點，這樣就為下一個新結點指明了插入位置。

代碼描述如下：

LinkListCreateLinklist2()

//q是一個LinkU4類型的變量,用耒揩示e入位IE

{Linklisthead;

Node

intx;

heaXalloc(sizeof(Node));〃生成頭結點

q?head;〃尾指竹I初值

scanf("Id",&x);〃讀入第一個元素

while(x!-0)〃■入的不是結束標志時維她人

(

t?^aalloc(sizeof(Node));t->data-x;〃生成一個新結點

q->next-t;〃新結點t修入

q-t;〃修改足指計q,指向新的尾結點

scanf〃讀入下一個元素

)

q->next-NULL;returnhead;〃q折角尾鰭點,置尾結點標志

方法中的鏈接操作如圖2-12,它的時間與元素個數成正比，故其時間復雜度為0(n)。

圖2-12建表算法中的表尾鏈入操作

方法三：頭插法，始終將新增加的結點插入到頭結點之后，第一個數據之前。如圖2T3所示。

圖2T3建表算法中的在表頭鍵入操作

代瑪描述如下：

LinkListCreateLinklist3()

(Linkllsthead;

Node*p;

intx;

head-malloc(sizeof(Node));〃生成頭站點

hcad->next-NULL;

scandf("%d"/&x);

while(x)//x-0時結束輸入

(

p-raalloc(sizeof(Node));

p-xlata-x;

p->next*head->next;//Itflt插入刎愈表的第一個18點處

head->next-p;

scandf("Id",&x);

)

returnhead;

2.4.2刪除重復結點

在線性表中，可能有多個結點的元素值是相同的，它們是重復結點。可以設計算法刪除重復結點，只保

留結點序號最小的那個結點。例如，線性表(4,7,2,5,2,4),刪除重復結點后結果為(4,7,2,5)。

用他表作為存儲結構，細化上述算法得到最后的算法描述：

voidPurgeLinkllst(LinkListh??d)

//???head中多余的重復結點

(Node?p,*q,*r;

q-head->next)//q指示當就檢套站點的位置，量其切值指向苜站點

while(q!-NULL)

//當前檢行特點?q不是用姑點時，尋找弁■除它的?復州點

(

p?q；〃工作指計P指向*q

while(p->next!-NULL)

//S-p的后震鰭點存在時，將其敷**與*q故招域比較

if(p->next-xiata-q->data)//若?(p->next)的質夏站點

(

r-p->next//r指向特刷結點

p->n?xt-r—>ncxt;

〃移出結點?(p->next),p->next指向原來，(p->n?xtj的后罐飾點

fre?(r)i

)

?ls?p^>->next;〃否則，讓p指向下一個結點

q-q->next;//更新依蛋結點

單徒表上刪除結點時的指針變化如圖2-14所示:

?W句?pfr_*??+->l?rNULL

圖2-14

2.5其他鏈表

2.5.1循環(huán)鏈表

在單鏈表中，如果讓最后一個結點的指針域指向第一個結點可以構成循環(huán)鏈表。在循環(huán)鏈表中，從任一

結點出發(fā)能夠掃描整個鏈表。

圖2-15給出常見的循環(huán)鏈表，圖2-15a、b分別表示帶頭結點的非空循環(huán)鏈表和空循環(huán)鏈表，頭指針

是head。在這種結構下，要找到尾結點可以從頭指針head出發(fā)掃描所有的結點。在圖2-15c、d中，鏈

表沒有設頭指針，只設尾指針rear。這樣，首結點表示為：rear->next->next,首尾結點都能方便地訪問。

rear

圖2-15

a）帶頭結點的非空循環(huán)鏈表

b）帶頭結點的空循環(huán)鏈表

c）設立尾指針的非空循環(huán)鏈表

d）設立尾指針的空循環(huán)鏈表

2.5.2雙向循環(huán)鏈表

雙向循環(huán)鏈表的結點結構如圖2-16所示:

priordatanext

圖2-16雙向循環(huán)鏈表結點結構

雙向循環(huán)鏈表示意圖如圖2-17所示，prior與next類型相同，它指向直接前驅結點。頭結點的prior

指向最后一個結點，最后一個結點的next指向頭結點。

圖2-17雙向循環(huán)鏈表示意圖

a）空表b）非空表

雙向循環(huán)鏈表與單鏈表類似，用C語言描述如下:

structdbnode

{Datatypedata;

structdbnode*prior,*next;

)

typedefstructdbnode*dbpolnter;

typedefdbpointerDLinkList;

雙向循環(huán)鏈表是一種對稱結構，可以用下列等式表示：

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

在單鏈表中，找直接后繼結點的時間復雜度是0(1)。在雙向循環(huán)鏈表中，找直接后繼結點和前驅結點

的時間復雜度都是0(1)。

雙向循環(huán)鏈表的求表長、定位、按序查找等運算的實現和單鏈表基本相同，這里我們討論它的插入和刪

除操作。

1.刪除

在單鏈表中刪除結點時，需要用一個指針指向待刪結點的前驅結點，在雙循環(huán)鏈表中，設p指向待刪結

點，刪除*P可通過下述語句完成，執(zhí)行效果如圖2T8所示。

(1)p->prior->next=p->next；

//p前驅結點的后鏈指向p的后繼結點

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

//P后繼結點的前鏈指向P的前驅結點

(3)free(p)；//釋放*p的空間

(1)、(2)這兩個語句的執(zhí)行順序可以顛倒。

■)b)

圖2-18雙向循環(huán)鏈表上結點的刪除

a)刪除結點*p之前b)刪除結點*p后

2.插入

在P所指結點的后面插入一個新結點*t,需要修改四個指針：

(1)t->prior-p；

(2)t->next=p->next；

(3)p->next->prior=t；

(4)p->next=t；

插入操作過程如圖2-19所示，注意這些語句之間的順序。

圖2-19雙向循環(huán)鏈表上結點的插入

a)插入前b)插入后

2.6順序實現與連接實現的比較

查找：對于按位置查找運算，順序表是隨機存取，時間復雜度為0(1)。單鏈表需要對表元素進行掃描,

它時間為復雜度為0(n)。

定位：基本操作是比較，順序表和單鏈表上的實現算法的時間復:雜度是相同的，均為0(n)

插入和刪除：在順序表和鏈表中，都需要進行定位。在順序表中，其基本操作是元素的比較和結點的移

動，平均時間復雜度為0(n)。在單鏈表中，由于需要定位，基本操作是元素的比較，盡管不需要移動結

點，其平均時間復雜度仍然為0(n)。

單銖表的每個結點包括數據域與指針域，指針域需要占用額外空間。從整體考慮，順序表要預分配存儲

空間，如果預先分配得過大，將造成浪費，若分配得過小，又將發(fā)生上溢；單鏈表不需要預先分配空間，

只要內存空間沒有耗盡，單鏈表中的結點個數就沒有限制。

三、考核的知識點與考核要求

1.線性表概念

識記：線性表概念；線性表的基本特征。

領會：線性表表長；線性表初始化、求表長、讀表元素、定位、插入、刪除等基本運算的功能。

2.線性表的順序存儲結構一順序表

識記：順序表表示法、特點和類C語言描述。

領會：順序表的容量；順序表表長；插入、刪除和定位運算實現的關鍵步驟。

簡單應用：順序表插入、刪除和定位運算的實現算法。

綜合應用：順序表上的簡單算法；順序表實現算法的分析。

3.線性表的鏈式存儲結構一單鏈表

識記：結點的結構；單鏈表的類C語言描述。領會：頭指針；頭結點；首結點；尾結點；空鏈表；單鏈

表插入、刪除和定位運算的關鍵步驟。

簡單應用：單鏈表插入、刪除和定位等基本運算的實現算法。

綜合應用：用單鏈表設計解決應用問題的算法。

4.循環(huán)鏈表和雙向循環(huán)鏈表

識記：循環(huán)鏈表的結點結構；雙向循環(huán)鏈表結點結構；循環(huán)鏈表和雙向循環(huán)鏈表類C語言描述。

領會：循環(huán)鏈表插入和刪除運算的關鍵步驟：雙向循環(huán)鏈表插入和刪除運算的關鍵步驟。

四、本章重點、難點

本章重點線性表概念和基本特征；線性表的基本運算;順序表和單鏈表的組織方法和算法設計。

難點：單鏈表上的算法設計。

五、練習

【例題：單選題】若某線性表最常用的操作是在最后一個結點之后插入一個新結點或刪除最后一個結點,

要使操作時間最少，應選擇()存儲結構。

A.無頭結點的單向鏈表

B.帶頭結點的單向鏈表

C.帶頭結點的雙循環(huán)鏈表

D.帶頭結點的單循環(huán)鏈表

I1正確答案』C

『答案解析』雙循環(huán)鏈表的找直接前驅和直接后繼結點的時間復雜度都是0(1)o參見教材P53。

【例題：單選題】在表長為n的順序表上做刪除運算，其平均時間復雜度為()。

A.0(1)

B.O(n)

C.0(nlog2n)

D.O（n2）

『正確答案』B

I1答案解析」在順序表上做刪除運算，需要后續(xù)結點向前移動一個位置以保證順序表的連續(xù)。參見教材

P39。

【例題：單選題】在表長為n的順序表上做插入運算，平均要移動的點數為（）。

A.n/4

B.n/3

C.n/2

D.n

r正確答案』c

『答案解析J如果在順序表的尾部插入，則移動。個結點，如果在順序表的頭部插入，則移動n個結點。

參見教材P39。

【例題：單選題】若線性表最常用的操作是存取第i個元素及其前驅的值，那么最節(jié)省操作時間的存儲

方式是（）。

A.單鏈表

B.雙向循環(huán)鏈表

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

D.順序表

『正確答案』D

I1答案解析」順序表的特點是邏輯上相鄰的在物理存儲上也相鄰。參見教材P40。

【例題：單選題】設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數為（）。

A.5

B.6

C.7

D.9

I1正確答案』C

『答案解析』第三個元素前插入一個元素，即第3到9個元素都要移動，故答案是7。參見教材P39。

【例題：單選題】從一個長度為n的順序表中刪除第i個元素（l<=i<=n）時，需向前移動的元素個數

為（）。

A.n-i

B.n-i+1

C.n-i-1

D.i

I1正確答案JA

［答案解析』刪除第i個元素，則后面n-i個元素都要前移。參見教材P39。

【例題：單選題】對于長度為n的順序表執(zhí)行刪除操作，則其結點的移動次數（）。

A.最少為0,最多為n

B.最少為1,最多為n

C.最少為0,最多為n-1

D.最少為1,最多為聯1

r正確答案JC

f答案解析』如果在順序表尾部刪除，移動次數為0,如果在順序表頭部刪除，移動次數為n-屋參見

教材P40o

【例題：單選題】設單鏈表中指針p指向結點A,要刪除A之后的結點（若存在），則修改指針的操作

為（）。

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

B.p=p->next

C.p=p->next—>next

D.p->next=p

『正確答案』A

I1答案解析』要刪除A之后的結點，即將A的指針域指向A之后的結點的下一個結點。參見教材P47。

【例題：填空題】設r指向單鏈表的最后一個結點，要在最后一個結點之后插入S所指的結點，需執(zhí)行

的語句序列是；r=s；r->next=NULLo

『正確答案』r->next=s

I1答案解析」在單鏈表中用尾插法插入一個結點，將尾結點的指針域指向待插結點，帶插結點的指針域

指向NULL參見教材P46。

【例題：填空題】在單鏈表中，指針P所指的結點為最后一個結點的條件是（）。

『正確答案Jp>next==NULL

r答案解析』最后一個結點的指針域指向空。參見教材P42。

【例題：填空題】在帶頭結點的單鏈表L中，第一個數據元素結點的指針為（）。

『正確答案』L->next

f答案解析』本題考察對單鏈表結點結構的理解。參見教材P4L

【例題：填空題】在雙向循環(huán)鏈表中，在指針P所指結點前插入指針s所指的結點，需執(zhí)行下列語句：

s->next=p；s->prior=p->prior；p->prior=s；=s0

『正確答案』（s->prior）->next

I1答案解析』在雙向循環(huán)鏈表中插入一個結點，需要做四件事情：待插結點后指針域指向P結點，P的

前指針域指向待插結點；帶插結點的前指針域指向P的前驅結點；P的前驅結點的后指針域指向待插結

點。參見教材P53。

【例題；填空題】帶頭結點的雙向循環(huán)鏈表L為空的條件是o