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

第一章緒論一、數(shù)據(jù)結(jié)構(gòu)討論的范疇二、基本概念三、算法和算法的量度一、數(shù)據(jù)結(jié)構(gòu)討論的范疇(數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的地位)系統(tǒng)分析系統(tǒng)設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)系統(tǒng)維護(hù)系統(tǒng)設(shè)計(jì)NiklausWirth

Algorithm

+DataStructures=Programs程序設(shè)計(jì):算法:數(shù)據(jù)結(jié)構(gòu):為計(jì)算機(jī)處理問(wèn)題編制一組指令集

處理問(wèn)題的策略問(wèn)題的數(shù)學(xué)模型

結(jié)構(gòu)靜力分析計(jì)算例如:數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題─━線性代數(shù)方程組─━環(huán)流模式方程

(球面坐標(biāo)系)全球天氣預(yù)報(bào)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例一:求一組(n個(gè))整數(shù)中的最大值算法:?模型：？基本操作是“比較兩個(gè)數(shù)的大小”取決于整數(shù)值的范圍例二：旅館客房的管理算法：?模型：?先來(lái)先服務(wù)隊(duì)列例三：鋪設(shè)城市的煤氣管道算法：?模型：?如何規(guī)劃使得總投資花費(fèi)最少？圖概括地說(shuō)，

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

所有能被輸入到計(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”等。

----是不可分割的“原子”

其中每個(gè)款項(xiàng)稱為一個(gè)“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。例如：描述一個(gè)學(xué)生的數(shù)據(jù)元素稱之為組合項(xiàng)年月日姓名學(xué)號(hào)班號(hào)性別出生日期入學(xué)成績(jī)?cè)禹?xiàng)數(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)系例如，當(dāng)用三個(gè)

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

12位數(shù)的十進(jìn)制數(shù)時(shí)，3214,6587,9345

─

a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素a1、a2和a3

之間存在著“次序”關(guān)系

a1,a2

、

a2,a3

3214，6587，93456587，3214，9345例如:a1a2a3a2a1a3又例，在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>}

a1a2a3a4a5a6列的次序關(guān)系:

若在

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ù)元素的集合?？梢?，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”則構(gòu)成一維數(shù)組的定義。從關(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)系的描述，它可以應(yīng)一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來(lái)表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”。數(shù)據(jù)結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。例如:定義“課題組”為一個(gè)數(shù)據(jù)結(jié)構(gòu)Group=(P,R)P={T,G1,…,Gn,S11,…Snm}R={R1,R2}R1={<T,G1>,…,<T,Gn>}R2={<Gi,Sij>|i=1,…,n,j=1,…,m}數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

——

邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像“數(shù)據(jù)元素”的映像？“關(guān)系”的映像？數(shù)據(jù)元素的映像方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關(guān)系的映像方法：（表示

x,y

的方法）順序映像以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy鏈?zhǔn)接诚褚愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置yx在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通常可用高級(jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。例如:

以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中提供的整數(shù)數(shù)組類型，

typedefintLong_int[3];定義長(zhǎng)整數(shù)為:typedefstruct{

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

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

intd;//日號(hào)Day}DateType;//日期類型定義“日期”為:定義“學(xué)生”為:typedefstruct{

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

charname[16];//姓名

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

DateTypebdate;//出生日期}Student;//學(xué)生類型2、數(shù)據(jù)類型

在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明它們所

屬的數(shù)據(jù)類型。例如，C

語(yǔ)言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型bool（C++語(yǔ)言）雙精度型double實(shí)型（C++語(yǔ)言）

數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。例如：整型值的范圍是：-32768~32767操作是：+，-，*，/，%各種高級(jí)程序設(shè)計(jì)語(yǔ)言中都擁有“整數(shù)”類型，盡管它們?cè)诓煌幚砥魃蠈?shí)現(xiàn)的方法不同，但對(duì)程序員而言是“相同的”，因?yàn)樗鼈兊臄?shù)學(xué)特性相同。從“數(shù)學(xué)抽象”的角度看，可稱它為一個(gè)“抽象數(shù)據(jù)類型”。3、抽象數(shù)據(jù)類型

(AbstractDataType

簡(jiǎn)稱ADT)

是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作例如:“整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。

其數(shù)學(xué)特性和具體的計(jì)算機(jī)或語(yǔ)言無(wú)關(guān)。“抽象”的意義在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。抽象數(shù)據(jù)類型還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。在構(gòu)造軟件系統(tǒng)的各個(gè)相對(duì)獨(dú)立的模塊時(shí)，定義一組數(shù)據(jù)和施與這些數(shù)據(jù)之上的一組操作，并在模塊內(nèi)部給出它們的表示和實(shí)現(xiàn)細(xì)節(jié)，在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”

數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,

e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作：

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

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

GetReal(Z,&RealPart)初始條件：復(fù)數(shù)已存在。操作結(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有兩個(gè)重要特征:數(shù)據(jù)抽象

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

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

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

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

抽象數(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é)果說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。類C語(yǔ)言詳見10-11頁(yè)。例如，對(duì)以上定義的復(fù)數(shù)typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說(shuō)明voidInitComplex(complex&Z,

floatrealval,floatimagval)；//

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

和imagval

的值float

GetReal(complexZ)；

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

GetImag(complexZ)；

//返回復(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;}

{其它省略}三、算法和算法的衡量1、算法2、算法設(shè)計(jì)的原則3、算法效率的衡量方法和準(zhǔn)則4、算法的存儲(chǔ)空間需求

算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：①有窮性

②確定性③可行性④有輸入⑤有輸出1、算法①

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

②

確定性

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

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

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

⑤

有輸出它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。2、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：①正確性②可讀性③健壯性④高效率與低存儲(chǔ)量需求①

正確性

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

其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語(yǔ)法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(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ù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。④高效率與低存儲(chǔ)量需求

通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。兩者都與問(wèn)題的規(guī)模有關(guān)。3、算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:

事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1。必須執(zhí)行程序

2。其它因素掩蓋算法本質(zhì)和算法執(zhí)行時(shí)間相關(guān)的因素：①算法選用的策略②問(wèn)題的規(guī)模③編寫程序的語(yǔ)言④編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量⑤計(jì)算機(jī)執(zhí)行指令的速度

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

假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：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ì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。例一兩個(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)1.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是：

【合肥工業(yè)大學(xué)1999三、1（2分）】i=1;while(i<n)i=i*2;

2.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是()?！竞戏使I(yè)大學(xué)2000三、1（2分）】i=1;while(i<n){for(j=0;j<n;j++)x=x+1;i=i*2；}3.下面程序段中帶有下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是()【合肥工業(yè)大學(xué)2001三、1（2分）】

i=n*n; while(i!=1)i=i/2;

4．設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。【南京郵電大學(xué)2000一、1】m=0;for(i=0;i<n;i++)for(j=2*i;j<=n;j++)m=m+1;5.分析下面程序段的時(shí)間復(fù)雜度。

intfact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}例二選擇排序voidselect_sort(int&a[],intn){

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

}//select_sort基本操作:

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

O(n2)j=i;//

選擇第i個(gè)最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}例三起泡排序voidbubble_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;}}//一趟起泡按數(shù)量階遞增排列，常見的時(shí)間復(fù)雜度有：O(1)≤O(log2n)≤

O(n)≤

O(nlog2n)≤

O(n2)≤

O(n3)≤…≤

O(nk)≤

O(2n)4、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。S(n)=O(g(n))算法的存儲(chǔ)量包括:①輸入數(shù)據(jù)所占空間;②程序本身所占空間；③輔助變量所占空間。

若輸入數(shù)據(jù)所占空間只取決與問(wèn)題本身，和算法無(wú)關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。

若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。

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

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

理解算法五個(gè)要素的確切含義。本章學(xué)習(xí)要點(diǎn)3.

掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。思考題:

1.41.61.71.191.20補(bǔ)充：寫一函數(shù)，用不多于3n/2的平均比較次數(shù)在一個(gè)向量A中找出最大和最小值的元素。本章作業(yè):1.31.8線性表是一種最簡(jiǎn)單的線性結(jié)構(gòu)第二章線性表

線性結(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)

順序映像2.1線性表的類型定義抽象數(shù)據(jù)類型線性表的定義如下：ADTList{

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

為線性表的表長(zhǎng);

稱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

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

結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：操作結(jié)果：線性表L已存在。銷毀線性表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ù)。（求線性表的長(zhǎng)度）

PriorElem(L,cur_e,&pre_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。（求數(shù)據(jù)元素的前驅(qū)）NextElem(L,cur_e,&next_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。（求數(shù)據(jù)元素的后繼）GetElem(L,i,&e)

初始條件：

操作結(jié)果：線性表L已存在，用

e返回L中第i

個(gè)元素的值。（求線性表中某個(gè)數(shù)據(jù)元素）且1≤i≤LengthList(L)LocateElem(L,e,compare())初始條件：操作結(jié)果：線性表L已存在，e

為給定值，

compare()是元素判定函數(shù)。返回L中第1個(gè)與e滿足關(guān)系

compare()的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數(shù)）

ListTraverse(L,visit())初始條件：操作結(jié)果：線性表L已存在。Visit()為某個(gè)訪問(wèn)函數(shù)。依次對(duì)L中每個(gè)元素調(diào)用函數(shù)標(biāo)visit()。一旦visit()失敗，則操作失敗。（遍歷線性表）加工型操作

ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

ClearList(&L)初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。（線性表置空）PutElem(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在，L中第i個(gè)元素賦值e。（改變數(shù)據(jù)元素的值）且1≤i≤LengthList(L)

ListInsert(&L,i,e)初始條件：操作結(jié)果：線性表L已存在，在L的第i個(gè)元素之前插入新的元素e，L的長(zhǎng)度增1。（插入數(shù)據(jù)元素）且1≤i≤LengthList(L)+1ListDelete(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在且非空，刪除L

的第

i

個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。（刪除數(shù)據(jù)元素）1≤i≤LengthList(L)利用上述定義的線性表類型可以實(shí)現(xiàn)其它更復(fù)雜的操作例

2-2例

2-3例

2-1

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

現(xiàn)要求一個(gè)新的集合A＝A∪B。例2-1

要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表

LA中的數(shù)據(jù)元素插入到線性表LA

中去。上述問(wèn)題可演繹為：1．從線性表LB中依次察看每個(gè)數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

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

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

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之La_len=ListLength(La);//求線性表的長(zhǎng)度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){

已知一個(gè)非純集合B，試構(gòu)造一個(gè)純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。仍選用線性表表示集合例

2-2集合B集合A從集合B

取出物件放入集合A要求集合A中同樣物件不能有兩件以上因此，算法的策略應(yīng)該和例2-1基本相同,差別僅在于集合A的初始狀態(tài)是“空集”voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}//union

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若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在表中依值非遞減或非遞增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，則稱該為有序表(OrderedList)。試改變結(jié)構(gòu)，以有序表表示集合。例如：（2，3，3，5，6，6，6，8，12）對(duì)集合B而言，

值相同的數(shù)據(jù)元素必定相鄰對(duì)集合A而言，

數(shù)據(jù)元素依值從小至大的順序插入因此，數(shù)據(jù)結(jié)構(gòu)改變了，解決問(wèn)題的策略也相應(yīng)要改變。voidpurge(List&La,ListLb)

{InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長(zhǎng)度

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

}//for}//purge

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

(ListEmpty(La)||!equal(en,e))

{

ListInsert(La,++La_len,e);

en=e;}

//La中不存在和e相同的數(shù)據(jù)元素，則插入之則

歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB，求得有序表LC也具有同樣特性。設(shè)

La=(a1,…,ai,…,an),Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)歸并得

(c1,…,ck-1)例

2-3k=1,2,…,m+n1．初始化LC為空表；基本操作：2．分別從LA和LB中取得當(dāng)前元素ai

和bj；3．若ai≤bj，則將ai

插入到LC中，否則將

bj

插入到LC中；4．重復(fù)2和3兩步，直至LA或LB中元素被取完為止；5．將LA表或LB表中剩余元素復(fù)制插入到

LC表中。

//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){//將ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//將bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}voidMergeList(ListLa,ListLb,List&Lc){

//本算法將非遞減的有序表La和Lb歸并為L(zhǎng)c}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while(i<=La_len){//當(dāng)La不空時(shí)

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//當(dāng)Lb不空時(shí)

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素2.2線性表類型的實(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-1ai

…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語(yǔ)言描述typedefstruct{

}SqList;//俗稱順序表ElemType*elem;//存儲(chǔ)空間基址int

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

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

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

InitList_Sq(SqList&L,intmaxsize)

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

}//InitList_Sq算法時(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.listsizee=38pppppi12341850p可見，基本操作是，將順序表中的元素逐個(gè)和給定值e相比較。

intLocateElem_Sq(SqListL,ElemTypee,

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

//

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

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

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-1ai

…ana1a2

…ai-1

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

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

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

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

算法時(shí)間復(fù)雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長(zhǎng)增1returnOK;……元素右移考慮移動(dòng)元素的平均情況:

假設(shè)在第

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

則在長(zhǎng)度為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_Sq(L,5,66)

L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p線性表操作

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>表的長(zhǎng)度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被刪除元素之后的元素左移--L.length;//表長(zhǎng)減1returnOK;算法時(shí)間復(fù)雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

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

假設(shè)刪除第

i個(gè)元素的概率為

,則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)

p2.3線性表類型的實(shí)現(xiàn)----鏈?zhǔn)接诚褚?、單鏈表二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述三、線性表的操作在單鏈表中的實(shí)現(xiàn)四、一個(gè)帶頭結(jié)點(diǎn)的單鏈表類型五、其它形式的鏈表六、有序表類型

用一組地址任意的存儲(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>

typedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLNode*next;//指針域

}LNode,*LinkList;

二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述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ù)元素

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i){p=p->next;++j;}//

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

//

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

returnERROR;//第i個(gè)元素不存在e=p->data;//取得第i個(gè)元素returnOK;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)的指針。StatusListInsert_L(LinkList&L,inti,ElemTypee){

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

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

}//LinstInsert_L算法的時(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大于表長(zhǎng)或者小于1s=newLNode;

//生成新結(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;deleteq;pqStatusListDelete_L(LinkList&L,inti,ElemType&e){

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

}//ListDelete_L算法的時(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;deleteq;returnOK;if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理操作ClearList(&L)在鏈表中的實(shí)現(xiàn):voidClearList(&L){//將單鏈表重新置為一個(gè)空表

while(L->next){

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

}}//ClearListdeletep;算法時(shí)間復(fù)雜度：O(ListLength(L))如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過(guò)程。例如：逆位序輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。（頭插法）操作步驟：一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；ananan-1四、依次類推，直至輸入a1為止。voidCreateList_L(LinkList&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=newLNode;L->next=NULL;

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

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

p->next=L->next;L->next=p;//插入}回顧2.1節(jié)中三個(gè)例子的算法，看一下當(dāng)線性表分別以順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)時(shí)，它們的時(shí)間復(fù)雜度為多少？voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);

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

GetElem(Lb,i,e);if(!LocateElem(La,e,equal())

ListInsert(La,++La_len,e);

}//for}//union控制結(jié)構(gòu)：基本操作：for循環(huán)GetElem,LocateElem

和ListInsert當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:

O(ListLength(La)×ListLength(Lb))

當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:

O(ListLength(La)×ListLength(Lb))例2-1算法時(shí)間復(fù)雜度

voidpurge(List&La,ListLb){

InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);

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

GetElem(Lb,i,e);

if(ListEmpty(La)||

!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

}//for}//purge控制結(jié)構(gòu)：基本操作：for循環(huán)GetElem

和

ListInsert當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:

O(ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:

O(Lb_len×(Lb_len+La_len))例2-2算法時(shí)間復(fù)雜度voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){

GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){

ListInsert(Lc,++k,ai);++i;}

else{

ListInsert(Lc,++k,bj);++j;}

}……控制結(jié)構(gòu)：基本操作：三個(gè)并列的while循環(huán)GetElem,ListInsert當(dāng)以順序映像實(shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:

O(ListLength(La)+ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)抽象數(shù)據(jù)類型線性表時(shí)為:

O(ListLength2(La)+ListLength2(Lb))例2-3算法時(shí)間復(fù)雜度用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：

改進(jìn)鏈表的設(shè)置：1．單鏈表的表長(zhǎng)是一個(gè)隱含的值；

1．增加“表長(zhǎng)”、“表尾指針”、“當(dāng)前位置的指針”和“當(dāng)前序號(hào)”四個(gè)數(shù)據(jù)域；2．在單鏈表的最后一個(gè)元素之后插入元素時(shí)，需遍歷整個(gè)鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)。2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型typedefstructLNode{//結(jié)點(diǎn)類型

ElemTypedata;

structLNode*next;}*Link,*Position;StatusMakeNode(Link&p,ElemTypee);

//分配由p指向的值為e的結(jié)點(diǎn)，并返回OK；

//若分配失敗，則返回ERRORvoidFreeNode(Link&p);

//

釋放p所指結(jié)點(diǎn)typedefstruct

{//鏈表類型

Linkhead,tail;

//分別指向頭結(jié)點(diǎn)和

//

最后一個(gè)結(jié)點(diǎn)的指針

intlen;

//指示鏈表長(zhǎng)度

Linkcurrent;

//指向當(dāng)前被訪問(wèn)的結(jié)點(diǎn)

//的指針，初始位置指向頭結(jié)點(diǎn)

intcurpos;//指示當(dāng)前指針位置,初值為0}LinkList;鏈表的基本操作:{結(jié)構(gòu)初始化和銷毀結(jié)構(gòu)}StatusInitList(LinkList&L);

//構(gòu)造一個(gè)空的線性鏈表L，其頭指針、

//

尾指針和當(dāng)前指針均指向頭結(jié)點(diǎn)，

//

當(dāng)前位置和表長(zhǎng)為零。StatusDestroyList(LinkList&L);

//銷毀線性鏈表L，L不再存在。O(1)O(n){引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//

求表長(zhǎng)StatusPrior(LinkListL);

//改變當(dāng)前指針指向其前驅(qū)StatusNext(LinkListL);

//改變當(dāng)前指針指向其后繼ElemTypeGetCurElem(LinkListL);

//返回當(dāng)前指針?biāo)笖?shù)據(jù)元素O(1)O(1)O(n)O(1)O(1)

StatusLocatePos(LinkListL,inti);

//改變當(dāng)前指針指向第i個(gè)結(jié)點(diǎn)StatusLocateElem(LinkListL,ElemTypee,

Status(*compare)(ElemType,ElemType));

//若存在與e滿足函數(shù)compare()判定關(guān)系的元

//素，則移動(dòng)當(dāng)前指針指向第1個(gè)滿足條件的

//元素的前驅(qū)，并返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());

//

依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit()O(n)O(n)O(n)

{加工型操作}StatusClearList(LinkList&L);