數(shù)據(jù)結(jié)構(gòu)(清華大學(xué)課件)-清華大學(xué)

第一章1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2與數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念1.3算法和算法的量度軟件開發(fā)的過程:系統(tǒng)分析系統(tǒng)實(shí)現(xiàn)系統(tǒng)維護(hù)系統(tǒng)設(shè)計(jì)系統(tǒng)設(shè)計(jì)確定系統(tǒng)所要達(dá)到的目標(biāo)確定實(shí)現(xiàn)方案并生成系統(tǒng)實(shí)地安裝調(diào)試系統(tǒng)修整完善NiklausWirth

Algorithm

+DataStructures=Programs程序設(shè)計(jì):算法:

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

為計(jì)算機(jī)處理問題編制一組指令集

處理問題的策略問題的數(shù)學(xué)模型例如:雞兔同籠問題二元一次代數(shù)方程組結(jié)構(gòu)靜力分析問題全球天氣預(yù)報(bào)高次線性代數(shù)方程組球面坐標(biāo)系下的環(huán)流模式方程非數(shù)值計(jì)算的程序設(shè)計(jì)問題例一求一組(n個(gè))整數(shù)中的最大值例二交叉路口的交通管制問題例三煤氣管道的鋪設(shè)問題例四數(shù)據(jù)庫中表格管理問題概括地說，

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。一、基本概念和術(shù)語二、數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)類型和抽象數(shù)據(jù)類型

所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)(數(shù)字、字符等)的集合。數(shù)據(jù)是計(jì)算機(jī)操作的對(duì)象的總稱。

是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。

是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”,在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)元素例如，整數(shù)“5”,字符“N”等。

----是不可分割的“原子”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。又如,描述一個(gè)學(xué)生的數(shù)據(jù)元素由多個(gè)款項(xiàng)構(gòu)成，其中每個(gè)款項(xiàng)稱為一個(gè)“數(shù)據(jù)項(xiàng)”。稱之為組合項(xiàng)年月日姓名學(xué)號(hào)班號(hào)性別出生日期入學(xué)成績(jī)?cè)禹?xiàng)關(guān)鍵字能識(shí)別一個(gè)或幾個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。若能起唯一識(shí)別作用，則被稱為“主”關(guān)鍵字，否則稱為“次”關(guān)鍵字。數(shù)據(jù)對(duì)象具有相同特性的數(shù)據(jù)元素的集合。如:整數(shù)、實(shí)數(shù)等。數(shù)據(jù)結(jié)構(gòu)帶結(jié)構(gòu)的數(shù)據(jù)元素的集合有一個(gè)特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。指的是數(shù)據(jù)元素之間存在的關(guān)系例如，可用三個(gè)

4位的十進(jìn)制數(shù)表示一個(gè)含

12位數(shù)的“長整數(shù)”。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)對(duì)長整數(shù)進(jìn)行運(yùn)算的程序中的操作對(duì)象是一個(gè)含三個(gè)數(shù)據(jù)元素{a1,a2,a3}的集合，且三者之間存在下列

“次序”關(guān)系:

{a1,a2、a2,a3}

。又如，在2行3列的二維數(shù)組中六個(gè)元素

{a1,a2,a3,a4,a5,a6}之間存在著兩個(gè)關(guān)系:“行”的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}“列”的次序關(guān)系:a1a2a3a4a5a6

在含

6個(gè)數(shù)據(jù)元素{a1,a2,a3,a4,a5,a6}的集合上存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}

“數(shù)據(jù)結(jié)構(gòu)”

是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合?？梢姡煌摹瓣P(guān)系”構(gòu)成不同的“結(jié)構(gòu)”則構(gòu)成“一維數(shù)組”

?？捎萌缦碌臄?shù)據(jù)結(jié)構(gòu)描述“班集體”:{班主任，班長1，班長2，舍長1，……，舍長p,

學(xué)生1，學(xué)生2，……，學(xué)生n}{<班主任，班長1>，<班主任，班長2>，<班長1，舍長1>，

……，<班長2，舍長p>,<舍長1，學(xué)生1>，

<舍長1，學(xué)生2>，……，<舍長p，學(xué)生n>}班主任班長1班長2舍長1舍長k舍長k+1舍長p學(xué)生1學(xué)生2學(xué)生3學(xué)生4學(xué)生n-3學(xué)生n-2學(xué)生n-1學(xué)生n…………數(shù)據(jù)結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Data_Structures=

(D,S)其中:D

是數(shù)據(jù)元素的有限集，

S

是D上關(guān)系的有限集。從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”

和“物理結(jié)構(gòu)”兩個(gè)方面(層次):邏輯結(jié)構(gòu)

是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)

是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2

A=(101)8=(001000001)2“關(guān)系”的兩種映象方法：（表示x,y的方法）順序映象以x和y之間相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間相差一個(gè)預(yù)設(shè)常量C，而C是一個(gè)隱含值，存儲(chǔ)結(jié)構(gòu)中只包含數(shù)據(jù)元素本身的信息

xy鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x綁定在一起的附加信息(指針)指示y的存儲(chǔ)位置yx以“由數(shù)據(jù)元素x的存儲(chǔ)映象和附加的指針合成的結(jié)點(diǎn)”表示數(shù)據(jù)元素。存儲(chǔ)結(jié)構(gòu)的描述方法隨編程環(huán)境的不同而不同，當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。

typedef

int

Long_int[3]例如，當(dāng)以“順序映象”表示長整數(shù)時(shí)，可定義為:定義“日期”為:

typedef

struct{

inty;//年號(hào)Year

intm;//月號(hào)Month

intd;//日號(hào)Day}

DateType;//日期類型定義“學(xué)生”為:

typedef

struct{charid[8];//學(xué)號(hào)

charname[16];//姓名

charsex;//性別‘M/F’:男/女

DateType

bdate;//出生日期}Student;//學(xué)生類型何謂“數(shù)據(jù)類型”？在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。例如，C++

語言中的基本數(shù)據(jù)類型有:邏輯型

bool、字符型

char、整型

int

和實(shí)型(浮點(diǎn)型

float和雙精度型

double)

數(shù)據(jù)類型是一個(gè)“值”的集合和定義在此集合上的“一組操作”的總稱。對(duì)程序員而言，各種語言中的整數(shù)類型都是一樣的，因?yàn)樗鼈兊臄?shù)學(xué)特性相同。從這個(gè)意義上可稱“整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型和數(shù)據(jù)類型的實(shí)質(zhì)相同，范疇更廣，不局限于語言中的數(shù)據(jù)類型。抽象數(shù)據(jù)類型

(AbstractDataType

簡(jiǎn)稱ADT)

是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。通常稱語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型為固有數(shù)據(jù)類型。抽象數(shù)據(jù)類型有兩個(gè)重要特征:“數(shù)據(jù)抽象”和“數(shù)據(jù)封裝”數(shù)據(jù)抽象數(shù)據(jù)封裝

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)抽象數(shù)據(jù)類型的描述方法ADT=（D，S，P）其中:D

是數(shù)據(jù)對(duì)象，

S

是D上的關(guān)系集，

P

是對(duì)D的基本操作集。

數(shù)據(jù)對(duì)象是特性相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如,抽象數(shù)據(jù)類型“復(fù)數(shù)”的定義:R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{數(shù)據(jù)對(duì)象：D＝{e1,e2｜e1,e2∈RealSet}數(shù)據(jù)關(guān)系：基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)Z已存在。操作結(jié)果：用realPart

返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart

返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。

}ADTComplex……#include<iostream.h>#include"complex.h"voidmain(){

}……complexz1,z2,z3,z4,z;floatRealPart,ImagPart;InitComplex(z1,8.0,6.0);InitComplex(z2,4.0,3.0);Add(z1,z2,z3);Multiply(z1,z2,z4);if(Division(z4,z3,z)){

GetReal(z,RealPart);

GetImag(z,ImagPart);}//ifADT

抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

賦值參數(shù)

只為操作提供輸入值；引用參數(shù)

以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件

描述操作執(zhí)行之前的數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果

說明在操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。初始條件可以為空，并可省略。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對(duì)之前定義的復(fù)數(shù)類型typedef

struct{

float

realpart；

float

imagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

Assign(complex&Z,

float

realval,float

imagval)；//

構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval

和imagval

的值float

GetReal(cpmplexZ)；

//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(cpmplexZ)；

//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和……//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;

sum.imagpart=z1.imagpart+z2.imagpart;}

……一、算法的定義二、算法設(shè)計(jì)的原則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求是為了解決某類問題而規(guī)定的一個(gè)有限長的操作序列。3．可行性一個(gè)算法必須滿足以下五個(gè)重要特性：算法1．有窮性2．確定性5．有輸出4．有輸入有窮性

對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束。算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。確定性

對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑?？尚行?/p>

算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。有輸入

作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。有輸出

它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性2.

可讀性3．健壯性4．高效率與低存儲(chǔ)量需求正確性

首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。

其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．不含語法錯(cuò)誤；b．對(duì)于某幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；

c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第

c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；可讀性

算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試；健壯性

當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。高效率與低存儲(chǔ)量需求存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。兩者都與問題的規(guī)模有關(guān)。效率指的是算法執(zhí)行時(shí)間；通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1.必須執(zhí)行程序

2.

其它因素掩蓋算法本質(zhì)優(yōu)點(diǎn)：可以預(yù)先比較各種算法，以便均衡利弊從中選優(yōu)。和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度算法選用的策略問題的規(guī)模

一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱

T(n)

為算法的(漸近)時(shí)間復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間

=∑(原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間)

算法的執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和

成正比

從算法中選取一種對(duì)于所研究的問題來說是

基本操作

的原操作，以該基本操作

在算法中重復(fù)執(zhí)行的次數(shù)

作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則?！盎静僮鳌敝傅氖?，該操作重復(fù)執(zhí)行次數(shù)和算法的運(yùn)行時(shí)間成正比。例一兩個(gè)矩陣相乘voidmult(inta[],intb[],int&c[]){//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積

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

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

{c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作時(shí)間復(fù)雜度:

O(n3)forforfor*

void

select_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sortfor(i=0;i<n-1;++i){

}例二選擇排序基本操作:

比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:

O(n2)j=i;//

選擇第i個(gè)最小元素for

(k=i+1;k<n;++k)

if

(a[k]<a[j]

)

j=k;if(j!=i)a[j]←→a[i];例三起泡排序void

bubble_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort基本操作:

賦值操作時(shí)間復(fù)雜度:

O(n2){change=FALSE;//change為元素進(jìn)行交換標(biāo)志

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

if(a[j]>a[j+1])

{a[j]←→a[j+1];change=TRUE;}}//一趟起泡←→forfor算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率相同。S(n)=O(g(n))算法的存儲(chǔ)量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間；3．輔助變量所占空間。若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是個(gè)常量，則稱此算法為原地工作。

若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。1.

熟悉各名詞、術(shù)語的含義，掌握基本概念。2.

理解算法五個(gè)要素的確切含義。本章學(xué)習(xí)要點(diǎn)3.掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法。提幾點(diǎn)要求:1.課前預(yù)習(xí)，了解本堂課內(nèi)容;2.課后復(fù)習(xí)，在理解教學(xué)內(nèi)容的基礎(chǔ)上做練習(xí)題;3.獨(dú)立完成作業(yè);4.勤答疑，多問“為什么”。(n-1)+(n-2)+……+1=n(n-1)/2=n2/2+n/2312597132357912357519732159793915297372715352513231297532第二章

線性結(jié)構(gòu)的基本特征:1．集合中必存在唯一的一個(gè)“第一元素”2．集合中必存在唯一的一個(gè)“最后元素”3．除最后元素在外，均有唯一的后繼4．除第一元素之外，均有唯一的前驅(qū)線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集2.1

線性表的類型定義2.3線性表類型的實(shí)現(xiàn)

鏈?zhǔn)接诚?.4一元多項(xiàng)式的表示2.2線性表類型的實(shí)現(xiàn)

順序映象ADTList{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

{稱

n

為線性表的表長;

稱

n=0

時(shí)的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai

在線性表中的位序。}

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

}ADTList

{結(jié)構(gòu)初始化}

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。

CreateList(&L,A[],n)

初始條件：A[]中存在線性表的n個(gè)數(shù)據(jù)元素。操作結(jié)果：構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的線性表L。

{銷毀結(jié)構(gòu)}

DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。

ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit()){引用型操作}

ListEmpty(L)（線性表判空）初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。ListLength(L)（求線性表的長度）初始條件：操作結(jié)果：線性表L已存在。返回線性表L

中元素個(gè)數(shù)。

PriorElem(L,cur_e,&pre_e)（求前驅(qū)）初始條件：操作結(jié)果：線性表L已存在。若cur_e是L中的元素，則以pre_e帶回它的前驅(qū)，否則操作失敗，pre_e無定義。NextElem(L,cur_e,&next_e)（求后繼）初始條件：操作結(jié)果：線性表L已存在。若cur_e是L中的元素，則以next_e帶回它的后繼，否則操作失敗，next_e無定義。

GetElem(L,i,&e)（求線性表中某個(gè)元素）初始條件：操作結(jié)果：線性表L已存在以e

帶回L

中第i

個(gè)數(shù)據(jù)元素值。LocateElem(L,e,compare())（定位函數(shù)）初始條件：操作結(jié)果：線性表L已存在,compare()為判定函數(shù)。返回L中第1個(gè)與e滿足關(guān)系

compare()的元素的位序，若不存在這樣的元素，則返回

0。且1≤i≤LengthList(L)。

ListTraverse(L,visit())（遍歷線性表）初始條件：操作結(jié)果：線性表L已存在,visit()為數(shù)據(jù)元素的訪問函數(shù)。依次對(duì)L

的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()，一旦visit()失敗，則遍歷操作失敗。ClearList(&L)

(線性表置空)ListInsert(&L,i,e) (插入數(shù)據(jù)元素)PutElem(&L,i,&e) (改變數(shù)據(jù)元素的值)ListDelete(&L,i,&e) (刪除數(shù)據(jù)元素){加工型操作}

ClearList(&L)初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。PutElem(&L,i,e)初始條件：操作結(jié)果：L中第i個(gè)元素賦值和e相同。線性表L已存在，且1≤i≤LengthList(L)。

ListInsert(&L,i,e)初始條件：操作結(jié)果：線性表L已存在在L的第i個(gè)元素之前插入新的元素e,L的長度增1。

ListDelete(&L,i,e)初始條件：操作結(jié)果：線性表L已存在刪除L中第i個(gè)元素，并以e帶回其值,L的長度減1。,1≤i≤LengthList(L)+1。,1≤i≤LengthList(L)。例2-1

假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。

現(xiàn)要求一個(gè)新的集合A＝A∪B。即:需對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。1．取得線性表LB中一個(gè)數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在，則插入之。ListDelete(Lb,1,e);

LocateElem(LA,e,equal());

ListInsert(LA,n+1,e);(n表示線性表LA當(dāng)前長度)操作步驟：ListDelete(Lb,1,e);

//刪除Lb中第1個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和

e相同的數(shù)據(jù)元素，則插入之La_len=ListLength(La);

//求線性表La的長度while(!ListEmpty(Lb)){}//while}//unionvoidunion(List&La,ListLb){

//將線性表Lb中所有在線性表La中不存在的數(shù)據(jù)元素

//插入到線性表La中例2-2

已知一個(gè)“非純集合”B，試構(gòu)造一個(gè)純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。若仍然以線性表表示集合，則算法的策略應(yīng)該和例一基本相同,差別是什么？1.集合A的初態(tài)是“空集”2.不破壞集合Bvoidpurge(List&La,ListLb){

La_len=0;Lb_len=ListLength(Lb);}//pugre

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和

e相同的數(shù)據(jù)元素，則插入之for(i=1;i<=Lb_len;i++){}//forInitList(La);//構(gòu)造(空的)線性表LA例2-3判別兩個(gè)集合是否相等。集合相等的條件是:兩者所含元素個(gè)數(shù)相同，且所有對(duì)應(yīng)元素都相等。仍以線性表表示集合，并假設(shè)這兩個(gè)集合是“純集合”。則算法的策略為:在兩個(gè)線性表的長度相等的前提下，只要判別一個(gè)表中的元素在另一個(gè)表中都存在即可。bool

isEqual(ListLA,ListLB){

//若線性表LA和LB不僅長度相等，且所含數(shù)據(jù)

//元素也相同，則返回TRUE,否則返回FALSE

}//isEqual

La_len=Listlength(LA);Lb_len=Listlength(LB);if(La_len!=Lb_len)

returnFALSE;//兩表的長度不等else{

}

………while(i<=La_len

&&found){

}//whilereturnfound;

GetElem(LA,i,e);//取得LA中一個(gè)元素if(LocateElem(LB,e,equal())i++;//依次處理下一個(gè)elsefound=FALSE;

//LB中沒有和該元素相同的元素i=1;found=TRUE;一、順序表

---線性表的順序映象二、順序表中基本操作的實(shí)現(xiàn)三、順序表的其它操作舉例最簡(jiǎn)單的一種順序映象方法是：

令y的存儲(chǔ)位置和x的存儲(chǔ)位置相鄰。順序映象——

以x的存儲(chǔ)位置和y的存儲(chǔ)位置之間某種關(guān)系表示邏輯關(guān)系<x,y>

用一組地址連續(xù)的存儲(chǔ)單元

依次存放線性表中的數(shù)據(jù)元素線性表的起始地址，稱作線性表的基地址

a1a2

…ai-1

ai

…an以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量↑所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置

LOC(ai)=

LOC(a1)

+(i-1)×C基地址順序表的C語言描述//存儲(chǔ)結(jié)構(gòu)typedef

struct{}SqList;//俗稱順序表ElemType

*elem;//存儲(chǔ)空間基址int

length;//當(dāng)前長度int

listsize;//當(dāng)前分配的存儲(chǔ)容量

//(以sizeof(ElemType)為單位)//基本操作接口void

purge(SqList

&La,SqListLb){//構(gòu)造順序表La，使其只包含Lb中所有值不

//相同的數(shù)據(jù)元素,算法不改變順序表Lb

boolb;

int

Lb_len=Listlength(Lb);//求線性表Lb的長度

InitList(La,Lb_len);//創(chuàng)建一個(gè)空的線性表La

int

La_len=0;

for(i=1;i<=Lb_len;i++)

{

//依次處理Lb中每個(gè)元素}//for}//purge

b=GetElem(Lb,i,e);

//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()){++La_len;b=ListInsert(La,La_len,e);//

當(dāng)

La中不存在和

e值相同的數(shù)據(jù)

//元素時(shí)進(jìn)行插入

}線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(&L)//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素Status

InitList(SqList&L,int

maxsize){//構(gòu)造一個(gè)最大容量為maxsize

的順序表

}//InitList算法時(shí)間復(fù)雜度：O(1)L.elem=newElemType[maxsize];

//

為順序表分配大小為maxsize

的數(shù)組空間if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;例如：順序表23754138546217L.elemL.length=7L.listsize假設(shè)e=38pppppi=12341850p可見，基本操作是，將順序表中的元素逐個(gè)和給定值e相比較。

int

LocateElem(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0}//LocateElem

O(ListLength(L))if(i<=L.length)returni;

elsereturn0;算法的時(shí)間復(fù)雜度為：i=1;//i的初值為第1元素的位序p=L.elem;

//p的初值為第1元素的存儲(chǔ)位置while(i<=L.length&&!(*compare)(*p++,e))++i;(*compare)(*p++,e)//找到滿足條件的元素//沒有找到滿足條件的元素線性表操作

ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

(a1,…,ai-1,ai,…,an)改變?yōu)閍1a2

…ai-1

ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加(a1,…,ai-1,e,ai,…,an)

Status

ListInsert(SqList

&L,inti,ElemTypee){//

在順序表L的第i個(gè)元素之前插入新的元素e,

//i的合法范圍為1≤i≤L.length+1}//ListInsert

算法時(shí)間復(fù)雜度為:for(j=L.length-1;j>=pos-1;--j)L.elem[j+1]=L.elem[j];

//插入位置及之后的元素右移L.elem[pos-1]=e;//插入e++L.length;//表長增1returnTRUE;O(ListLength(L))……元素右移考慮移動(dòng)元素的平均情況:

假設(shè)在第

i個(gè)元素之前插入的概率為pi

，

則在長度為n

的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：

若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：if(L.length>=L.listsize)returnOVERFLOW;//當(dāng)前存儲(chǔ)空間已滿

if(i<1||i>L.length+1)

returnERROR;

//

插入位置不合法2118307542568721183075例如：ListInsert(L,5,66)

L.length-10j87564266for(j=L.length-1;j>=pos-1;--j)L.elem[j+1]=L.elem[j];4jj線性表操作

ListDelete(&L,i,&e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)閍i+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)Status

ListDelete(SqList

&L,inti,ElemType

&e){}//ListDelete算法時(shí)間復(fù)雜度為:

O(ListLength(L))for(j=pos;j<L.length;++j)L.elem[j-1]=L.elem[j];//被刪除元素之后的元素左移--L.length;//表長減1return

TRUE;if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法元素左移考慮移動(dòng)元素的平均情況:

假設(shè)刪除第

i個(gè)元素的概率為qi,則在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：211830754256876321183075L.length-10j8756for(j=pos;j<L.length;++j)L.elem[j-1]=L.elem[j];例如：ListDelete(L,5,e)635jj試設(shè)計(jì)一個(gè)算法，用盡可能少的輔助空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行互換，即將線性表

(a1,a2,…,am,b1,b2,…,bn)改變成

(b1,b2,…,bn,a1,a2,…,am)。

從

b1開始，從原地刪除之后插入到a1之前直至bn。例2-4算法1

進(jìn)行三次“逆轉(zhuǎn)順序表”的操作。算法2abcdefg123451gggfffeeedddcccbbbaaa23123jijijiabcdefg12345abcdeeffg123445cbga251voidinvert(ElemType

&R[]，ints，

intt)//本算法將數(shù)組R中下標(biāo)自s到t的元素逆置，

//即將（Rs,Rs+1,…,Rt-1,Rt

）

//改變?yōu)椋≧t,Rt-1,…,Rs+1,Rs

）

voidexchange(SqList

&A;intm){

//本算法實(shí)現(xiàn)順序表中前m個(gè)元素

//和后n個(gè)元素的互換

n=A.length–m;invert(A.elem,0,A.length);invert(A.elem,0,n-1);invert(A.elem,n,m+n-1);}//exchange

算法的時(shí)間復(fù)雜度為:O(m+n)voidexchange(SqList

&A,intm){//實(shí)現(xiàn)順序表A中前m個(gè)元素和后n個(gè)元素互換}exchangefor(i=0;j=m;

j<A.length;i++,j++){}x=A.elem[j];for(k=j;k>i;k--)

A.elem[j]=A.elem[j-1];A.elem[i]=x;算法的時(shí)間復(fù)雜度為:O(mn)試編寫算法，刪除順序表中“多余”的數(shù)據(jù)元素。例2-5

從

a1開始，檢查在它之后的數(shù)據(jù)元素，如有和它相等的，則從表中刪除之。算法1

回顧例2-2的算法，試按“構(gòu)造”一個(gè)新的順序表的思想來進(jìn)行，設(shè)想這兩個(gè)表“共享”一個(gè)存儲(chǔ)空間。算法2525334257543ij3342557437543jj3i4L.length-1L.length-1L.length-1L.length-1j525334257543ki523iiiiiiiiiiikkkk47kivoidpurge(SqList&L){//刪除順序表L中冗余元素

for(i=0;i<L.length-1;++i){//順序考察表中每個(gè)元素

j=i+1;while(j<L.length)}//for}//purgeif(L.elem[j]!=L.elem[i])++j;else

{

for(k=j+1;k<L.length;++k)L.elem[k-1]=L.elem[k];//移動(dòng)元素

--L.length;//修改表長}//else算法的時(shí)間復(fù)雜度為:O(L.length3)voidpurge(SqList&L){//刪除順序表L中的冗余元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length;++i)

{

//順序考察表中每個(gè)元素

}//forL.length=k+1;//修改表長}//purge算法的時(shí)間復(fù)雜度為:O(L.length2)j=0;while(j<=k&&L.elem[j]!=L.elem[i])++j;

//

在新表中查詢是否存在

//和L.elem[i]相同的元素if(k==-1||j>k)//k=-1

表明當(dāng)前考察的是第一個(gè)元素

L.elem[++k]=L.elem[i];一、單鏈表

---線性表的鏈?zhǔn)接诚蠖?、單鏈表中基本操作的?shí)現(xiàn)三、單鏈表的其它操作舉例四、其它形式的鏈表結(jié)構(gòu)

用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。一、單鏈表以元素(數(shù)據(jù)元素的映象)

+指針(指示后繼元素存儲(chǔ)位置)=結(jié)點(diǎn)

(表示數(shù)據(jù)元素或數(shù)據(jù)元素的映象)以“結(jié)點(diǎn)的序列”表示線性表

稱作單鏈表

以線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

//存儲(chǔ)結(jié)構(gòu)Typedef

struct

LNode

{

ElemType

data;

//

數(shù)據(jù)域

struct

LNode

*next;

//

指針域}

*LinkList;

單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針二、單鏈表操作的實(shí)現(xiàn)GetElem(L,i,e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)

//生成含n個(gè)數(shù)據(jù)元素的鏈表L

線性表的操作

GetElem(L,i,&e)在單鏈表中的實(shí)現(xiàn):211830754256∧pppj123

因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i

單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。

令指針p

始終指向線性表中第j

個(gè)數(shù)據(jù)元素

Status

GetElem(LinkListL,inti,ElemType

&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第

i個(gè)元素}//GetElem算法時(shí)間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(j<i){p=p->next;++j;}

//

順指針向后查找，直到p指向第i個(gè)元素

e=p->data;//取得第i個(gè)元素returnOK;

p&&//

或p為空if(!p||j>i)

returnERROR;//第i個(gè)元素不存在ai-1

線性表的操作

ListInsert(&L,i,e)

在單鏈表中的實(shí)現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1

因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:

找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。

可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針。

Status

ListInsert(LinkListL,inti,ElemTypee){

//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法

//在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素e

}//LinstInsert算法的時(shí)間復(fù)雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}//尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)

returnERROR;//

i大于表長或者小于1s=new

LNode;//生成新結(jié)點(diǎn)if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp線性表的操作ListDelete(&L,i,&e)在鏈表中的實(shí)現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pq

Status

ListDelete(LinkListL,inti,ElemType

&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete算法的時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨q=p->next;p->next=q->next;

//刪除并釋放結(jié)點(diǎn)e=q->data;

delete(q);returnOK;if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理操作ClearList(&L)在鏈表中的實(shí)現(xiàn):void

ClearList(&L){//將單鏈表重新置為一個(gè)空表

while(L->next){

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

}}//ClearListdelete(p);算法時(shí)間復(fù)雜度：O(ListLength(L))如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過程。例如：逆位序輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素an-1，

建立結(jié)點(diǎn)并插入；四、依次類推，直至輸入a1為止。L∧∧epdpcpbpap∧p=new

LNode;scanf(&p->data);//輸入元素值p->next=L->next;L->next=p;//插入L=new

LNode;L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表void

CreateList(LinkList

&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=new

LNode;L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){

p=new

LNode;

scanf(&p->data);//輸入元素值

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

//插入}試設(shè)計(jì)算法，將單鏈表中前m個(gè)結(jié)點(diǎn)和后n個(gè)結(jié)點(diǎn)進(jìn)行互換，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。例2-6算法設(shè)計(jì):

將(b1,b2,…,bn)從鏈表的當(dāng)前位置上刪除之后再插入a1到之前，并將am設(shè)為表尾。a1a2amb1b2bnL……∧tahbtb∧∧ta->next=NULL;tb->next=L->next;L->next=hb;voidexchange(SLink

&L,intm){//互換鏈表中前m個(gè)和后n個(gè)結(jié)點(diǎn)

ta=L;i=0;

while(ta

&&i<m){//查詢結(jié)點(diǎn)am

ta=ta->next;i++;

}//while}//exchange算法的時(shí)間復(fù)雜度為:O(ListLength(L))if(ta

&&

ta->next){//m<表長

hb=ta->next;tb=hb;while(tb->next)tb=tb->next;//查詢表尾bn

}//if修改指針例2-7試編寫算法，刪除單鏈表中“多余”的數(shù)據(jù)元素。算法一對(duì)鏈表中當(dāng)前考察的每個(gè)元素，刪除它之后的“值相同”的結(jié)點(diǎn);算法二將新表中尚未存在的“值相同”的結(jié)點(diǎn)插入到新的鏈表中。voidpurge(SLink

&L){//刪除鏈表中的“冗余”元素

p=L->next;

while(p){//p指向當(dāng)前被考察的結(jié)點(diǎn)

q=p;

while(q->next)//考察q所指后繼結(jié)點(diǎn)

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

else//修改指針并釋放結(jié)點(diǎn)空間

{

s=

q->next;q->next=s->next;deletes;} p=p->next;

}//whilep}//purge算法時(shí)間復(fù)雜度:O(ListLength2(n))voidpurge(SLink

&L){

//刪除鏈表中“冗余”元素

p=L->next;L->next=NULL;//設(shè)新表為空表

while(p){//p指向當(dāng)前被考察的結(jié)點(diǎn)

q=L->next;succ=p->next;//指向*p的后繼

while(q&&q->data<>p->data) q=q->next;//查詢是否已存在值相同的結(jié)點(diǎn)

if(q)deletep;

else//插入新表(倒插)，修改指針

{p->next=L->next;L->next=p;}

p=succ; //繼續(xù)考察下一個(gè)結(jié)點(diǎn)

}//whilep}//purge算法時(shí)間復(fù)雜度:O(ListLength2(n))

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表

循環(huán)鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。

a1a2…...an

有時(shí)還可以將頭指針設(shè)成指向尾結(jié)點(diǎn)。voidexchange(SLink

&L,intm){//互換鏈表中前m個(gè)和后n個(gè)結(jié)點(diǎn)

ta=L;i=0;

while(ta

&&i<m){//查詢結(jié)點(diǎn)am

ta=ta->next;i++;

}//while

if(ta

&&

ta->next){//m<表長

hb