數(shù)據(jù)結(jié)構(gòu)是計算機處理加工的對象

第一章緒論

數(shù)據(jù)結(jié)構(gòu)是計算機處理加工的對象，而計算機處理的數(shù)據(jù)決不是雜亂無章的堆積，而

是有著內(nèi)在聯(lián)系的，只有分析清蘢他們的內(nèi)在聯(lián)系，對■大量的數(shù)據(jù)才能有效的處理，數(shù)據(jù)

結(jié)構(gòu)正是研究數(shù)據(jù)之間的關(guān)系以及對數(shù)據(jù)如何進(jìn)行有效處理的學(xué)科。

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

我們首先回顧一下數(shù)據(jù)結(jié)構(gòu)學(xué)科發(fā)展歷史：

在計算機發(fā)展的初期他的主要用途是用于處理數(shù)值問題，解決人們難以用手二和機械

計算難以完成的的科學(xué)計算，隨著計算機應(yīng)用領(lǐng)域的擴大和深入，解決非數(shù)值問題越來越

受到人們的關(guān)注，例如，金融和工商領(lǐng)域的信息管理系統(tǒng)，網(wǎng)絡(luò)與通訊，圖形化界面等。

解決此類問題所用的數(shù)學(xué)工具不再是分析數(shù)學(xué)及計算方法，而是更多地用到離散數(shù)學(xué)和計

算機的相關(guān)知識，所涉及的數(shù)據(jù)也更復(fù)雜。其突出特點是：數(shù)據(jù)之間所具有的聯(lián)系已不能

用分析數(shù)學(xué)的方程式來簡單描述。

例如，在幾個居民點銃設(shè)煤氣管道，每兩個居民點之間的鋪設(shè)費是可以估算的。設(shè)計

一個方案，使鋪設(shè)費用最小。用圖的模型來表達(dá)這類問題。

費用核算圖

例2酒店管理系統(tǒng)當(dāng)中的客房分配問題。

酒店要求每一個客房出租率均等，以保證維持每個客房的磨損率相當(dāng)。我們可以把

所有的空房間排成一個隊，當(dāng)有客人入住時，從隊頭分配客房；當(dāng)客人結(jié)帳離去時，將

退掉的房間排回隊尾，這就保證每個房間出租的機會均等，維護(hù)的機會也均等。

401402405201---305312211

A

V211房回退棹，棒回隊尾

準(zhǔn)備出相401房間

例3某學(xué)院的行政管理機構(gòu)的組織結(jié)構(gòu)可以用如下的結(jié)構(gòu)形式表示出來:

綜上可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹

和圖之類的數(shù)據(jù)結(jié)構(gòu)，因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問

題中的計算機的操作對象之間的關(guān)系和操作等的學(xué)科。

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

本節(jié)中，我們將對一些概念和術(shù)語賦以確定的含義，這些概念和術(shù)語將在以后的章

節(jié)中多次出現(xiàn)。

1.數(shù)據(jù)(data)能輸入到計算機當(dāng)中并被計算機程序處理的符號的集合。

或數(shù)據(jù)是對客觀事物采用計算機能夠識別、存儲和處理的形式所進(jìn)行的描述。

對計算機科學(xué)而言，數(shù)據(jù)的含義極為廣泛，除了數(shù)值、字符之外，圖形、聲音等

也屬于數(shù)據(jù)的范疇。

2.數(shù)據(jù)元素(dataelement)是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中的一個個體。

關(guān)鍵媽：其值能唯一確定一個結(jié)點(記錄)的字段或字段的組合。

3.數(shù)據(jù)對象(dataobject)是具有相同特征的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子

集。如整數(shù)數(shù)據(jù)對象是集合N=(0,±1,±2,±3,…}

4.算法(algorithm)是精確定義的一系列規(guī)則，指出怎樣從給定的輸入信息，經(jīng)過

有限步驟產(chǎn)生所求的輸出信息。

5.數(shù)據(jù)結(jié)構(gòu)(datastructure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的

集合。

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：

(1)集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個集合的關(guān)系外，別無其他關(guān)

系。

(2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。

(3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一公對多公的關(guān)系。

(4)圖形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系。

數(shù)據(jù)結(jié)構(gòu)的形式定義為一個二元組：

Data-structure=(D,S)

其中，D是數(shù)據(jù)元素的有限集合，S是D上關(guān)系的有限集合。

例1線性結(jié)構(gòu)：

Data-structure二(D,S)

D={d1,d2,...dn}

S=(r),r=(<di-1,di>|diGD,1<i^n}

d1—d2—d3—...dn-1-dn

例2樹形結(jié)構(gòu)

Data-structure=(D,S)

D=(d1,d2,d3,d4,d5,d6},S={r)

R=Kd4,d5>,<d4,d3>,<d4,d1>,<d3,d2>,<d5,d6?

例3圖形結(jié)構(gòu)

Data-structure=(D,S)

D={d1,d2,d3,d4,d5,d6},S={r}

R=(<d4,d1>,<d4,d3>,<d4,d5>,<d3,d2>,<d5,d6>,<d1,d2>,<d2,d6?

6.邏輯結(jié)構(gòu)：對數(shù)據(jù)間關(guān)系的描述是數(shù)據(jù)的邏輯結(jié)構(gòu)。

7.物理結(jié)構(gòu)(存儲結(jié)構(gòu))：是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機的存儲器里的實現(xiàn)，它依賴于

計算機，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。

數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序映象和非順序映象，具

體有四種不同的存儲結(jié)構(gòu)：

(1)順序方法：把邏輯上相鄰的結(jié)點存儲在物理上鄰接的存儲單元里。結(jié)點之間的相

鄰關(guān)系由結(jié)點之間的鄰接關(guān)系來體現(xiàn)。這種方法主要用于存儲線性的數(shù)據(jù)結(jié)構(gòu)。

例Data-structure=(D,S)

D={d1,d2,d3,d4,d5,d6},S={r}

R=?d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>,<d5,d6?

dld2d3d4d5d6

⑵鏈接存儲方法：利用指針項指出其后繼結(jié)點所在的存儲單元的地址。

如：Data-structure=(D,S)

D=(d1,d2,d3,d4,d5,d61,S=[r)

R={<d1,d2>,<d1,d3>,<d2,d4>,<d2,d5>,<d3,d6>]

結(jié)構(gòu)的存儲密度二數(shù)據(jù)本身所占有的存儲量

整個結(jié)構(gòu)所占有的存儲量

⑶索引存儲

在線性的機構(gòu)里，結(jié)點可以排成一個序列;d1,d2,d3,???,dn,每個結(jié)點di在序

列里都有對應(yīng)的位置數(shù)i,這個位置數(shù)就是結(jié)點的索引。索引的存儲結(jié)構(gòu)就是用結(jié)點的

索引號i來確定結(jié)點的存儲地址的。

在實際的應(yīng)用中，這種存儲實除上是分兩步進(jìn)行的：

①在輸入數(shù)據(jù)時建立了一個索引表；

②將所建的索引表，按索引關(guān)鍵字值由小到大排列；

例結(jié)點號（No.）關(guān)鍵字(keyword)姓名（name）職務(wù)(Title)地址

(address)

129張珊程序員1011

205李兵系統(tǒng)員1031

302王紅程序員1041

438劉琪系統(tǒng)員1051

輸入時的索引表：排序：

No.KeywordAddressNo.KeywordAddress

12910113021041

20510312051031

30210411291011

43810514381051

（4）散列存儲

是根據(jù)結(jié)點的值來確定它的存儲地址。其關(guān)鍵在于散列函數(shù)的選擇和如何解決碰撞問

題。

一般數(shù)據(jù)結(jié)構(gòu)的存儲映像都是這四種基本映象之一或是它們的組合。同一邏輯結(jié)構(gòu)可

以有幾種不同的映象方法，選擇哪一種要根據(jù)實際運算的方便性來確定。

8.數(shù)據(jù)類型（datatype）

一個值的集合和定義在這個值集上的一組操作的總稱。

數(shù)據(jù)類型可分為兩類：原子類型（初等類型）和結(jié)構(gòu)類型（組合類型）。

/整型，枚舉型

原子類型實型，子界型

字符型，指針型

\布爾型

結(jié)構(gòu)類型：記錄類型，數(shù)組類型。

9.抽象數(shù)據(jù)類型（abstractdatatype）

是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作

例如：矩陣+（求轉(zhuǎn)置、加、乘、求逆、求特征值）

構(gòu)成一個矩陣的抽象數(shù)據(jù)類型

數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作=抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型的描述方法

抽象數(shù)據(jù)類型可用（D,S,P）三元紙表示

其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集，

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

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

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

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

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

其中，數(shù)據(jù)對柒和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為

基本操作名（參數(shù)表）

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

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

基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返

回操作結(jié)果。

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

錯信息。

“操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略

之。

例一抽象數(shù)據(jù)類型三元組的定義：

ADTComplex{

數(shù)據(jù)對象：D={el,e2Iel,e2ERealSet}

數(shù)據(jù)關(guān)系：Rl={vel,e2>|el是復(fù)數(shù)的實數(shù)部分，

|c2是員數(shù)的虛數(shù)部分)

基本操作：

InitComplex(&Z,v1,v2)

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

DestroyComplex(&Z)

操作絹果：復(fù)數(shù)Z被銷段。

GetReal(Z,&realPart)

初始條件：復(fù)數(shù)已存在。

操作結(jié)果：用realPart返回復(fù)數(shù)Z的實部值。

Gctlmag(Z.&ImagPart)

初始條件：復(fù)數(shù)已存在。

操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(zl,z2.&sum)

初始條件：zl,z2是復(fù)數(shù)c

操作結(jié)果：用sum返回兩個復(fù)數(shù)z1,z2的和值。

}ADTComplex

例二抽象數(shù)據(jù)類型三元組的定義：

ADTTriplet(

數(shù)據(jù)對象：D={el,e2,e3Iel,e2,e3eElemSet}

數(shù)據(jù)關(guān)系：Rl={<el,e2>,<e2,e3>}

基本操作：

InitTriplet(&T,vl,v2,v3)

操作結(jié)果：構(gòu)造三元組T,元素e1,e2和e3分別被賦以參數(shù)v1,v2和v3的值。

DestroyTriplet(&T)

操作結(jié)果：三元組T被銷毀。

Get(T,i,&e)

初始條件：三元組T已存在，1WiW3。

操作結(jié)果：用e返回T的第i元的值。

Put(&T,i,c)

初始條件：三元組T已存在，1WiW3。

操作結(jié)果：改變T的第i元的值為e0

IsAscending(T)

初始條件：三元組T已存在。

操作結(jié)果：如果T的三個元素按升序排列，則返回1,否則返回0.

IsDescending(T)

初始條件：三元組T已存在。

操作結(jié)果：如果T的三個元素按降序排列，則返回1,否則返回0。

Max(T,&e)

初始條件；三元組T已存在。

操作結(jié)果：用e返回T的三個元素中的最大值。

Min(T,&e)

初始條件：三元組T已存在。

操作結(jié)果：用e返回T的三個元素中的最小值。

}ADTTriplet

抽象數(shù)據(jù)類型的兩個特征:

數(shù)據(jù)抽象

對程序處理的實體的描述強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部養(yǎng)護(hù)的接口(即外界

使用它的方法)。

數(shù)據(jù)封裝

將實體的外部特性和其內(nèi)部實現(xiàn)細(xì)節(jié)分離，并且對外部養(yǎng)護(hù)隱藏其內(nèi)部實現(xiàn)細(xì)節(jié)。

抽象數(shù)據(jù)類型的表示和實現(xiàn)

抽象數(shù)據(jù)類型可以通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)

抽象數(shù)據(jù)類型#class

數(shù)據(jù)對象數(shù)據(jù)成員

基本操作成員函數(shù)(方法)

類中的實例被稱為對象，對象的狀態(tài)是唯一的，它由數(shù)據(jù)成員(屬性)的當(dāng)前值定義，成員函數(shù)可通

過修改數(shù)據(jù)成員類改變對象的狀態(tài)。

在C++中，類的成分(數(shù)提成員和成員函數(shù))可以有三種訪問級別：

private私有成分(只允許類的成員函數(shù)進(jìn)行訪問)

protected保護(hù)成分(只允許類的成員函數(shù)及其子孫類進(jìn)行訪問)

public公有成分(允許類的成員函數(shù)、類的實例及其子孫類、子

孫類的實例進(jìn)行訪問)

例如:ADT復(fù)數(shù)的描述

classComplex

{//類的聲明

protected:

doublerealpart:

doubleimagpart;

public:

Complex();

Complex(doublerealVai,doubleimagVal);

Complex(Complex&z){assign(z);)

-Complex0;

voidassign(Complex&z);

doublegctRcal(void)const{returnrcalpart；}

doublegetlmag(void)const{returnimagpart;}

friendComplexadd(Complcx&zl,complcx&z2):

)：

〃類的實現(xiàn)部分

Complex：：Complex(doublerealVai,doubleimagVai)

{

realpart=realVal;

imagpart=imagVal:

)

voidComplex::assign(Complcx&z)

(

rcalpart=z.rcalVal;

imagpart=z.iniagVal：

}

Complexadd(Complex&zl,complex&z2);

(

Complexsum(zl);

sum.realpart=z2.realVai:

sum.imagpart=z2.imagVal：

returnsum;

三、面向?qū)ο蟮某绦蛟O(shè)計

所謂“程序設(shè)計”即是用計異機模擬現(xiàn)實世界的活動。

從傳統(tǒng)的角度看，程序是“活動”的集合，

程序:過程+調(diào)用

稱這種程序設(shè)計方法為面向過程的程序設(shè)計

現(xiàn)實世界是由許許多多的實體或?qū)ο髽?gòu)成的。這些對象彼此相關(guān)并能相互通訊，對象的活動構(gòu)成

了現(xiàn)實世界的活動。

從面向?qū)ο蟮慕嵌瓤矗?/p>

程序是對象的集合；

對象之間的相互作用構(gòu)成了一個軟件系統(tǒng)。

對象參與的交互動作稱為事件，在事件中消息在對象之間發(fā)送，接收消息的對象調(diào)用相應(yīng)的方法進(jìn)行

響應(yīng)。

例如：為圖書館的出納臺編一個管理程序

假設(shè)程序的需求如下所述：

學(xué)校圖書館（Iibrary）有數(shù)十萬本藏書（books）和數(shù)千位讀者（readers）。每本書具有書號（id）、書名

（name）、作者（author）、專業(yè)（speciaIity）和借閱人（borrower）等登記項，其中各書的書號不重復(fù)。每位讀

者具有讀者號（id）、姓名（name）、專業(yè)（speciaIity）和所借圖書（hoIding）等登■記項，讀者都是本校的教師

（teachers）和學(xué)生（students）。出納臺的功能有：

（1）注冊（join）新讀者；

（2）查詢（acquire）某書下落；

（3）借出（lend）某書給某人；

（4）妝回（receive）某人歸還的某書。

按照圖書借閱規(guī)則（rules）,教師可同時借本專業(yè)書5本和其它書3本，借期最長3個月；學(xué)生可同時

借本專業(yè)書3本和其它書1本，借期最長1個月。

按傳統(tǒng)的分析方法，程序中應(yīng)該包含四個函數(shù)：

join（注冊新讀者）、acquire（查詢圖書）、lend（出借）、receive（歸還）

兩個結(jié)構(gòu)：讀者和圖書

功能優(yōu)先分解的抽象系統(tǒng)

按對象的分析方法，整個活動在三個實體（讀者群、書庫和出納臺）之間進(jìn)行

1.3算法和算法的衡量

一、算法

算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。

一個算法必須滿足以下五個重要特性：

1.有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在

有限時間內(nèi)完成：

2.確定性對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能

明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；

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

4.有檢入作為算法加工對跳的量值，通常體現(xiàn)為拜法中的一組變量.有些榆入量需要在作法執(zhí)行過程

中輸入，而有的算法表面上可以沒有輸入，實陸上已被嵌入算法之中：

5.有輸出它是一組與“輸入”與確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即

為算法的功能。

二、算法設(shè)計的原則

設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：

1.正確性

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

其次，對算法是否“正確”的理解可以有以下四個層次：

a.程序中不含語法錯識：

b.程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果：

c.程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿

足要求的結(jié)果；

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

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

2.可讀性

算法主要是為了人的閱讀與交流,其次才是為計算機執(zhí)行。因此算法應(yīng)該易于人的理解；另一方

面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試；

3.健壯性

當(dāng)輸人的數(shù)據(jù)非法時，笄法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生英名小妙的輸山結(jié)

果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更

高的抽象層次上進(jìn)行處理。

4.高效率與低存儲量需求

通常，效率指的是算法執(zhí)行時間：存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與

問題的規(guī)模有關(guān)。

三、算法效率的衡量方法和準(zhǔn)則

通常有兩種衡量算法效率的方法:

事后統(tǒng)計法

缺點：1。必須執(zhí)行程序

2.其它因素掩蓋算法本質(zhì)

事前分析估算法

和算法執(zhí)行時間相關(guān)的因素：

1.算法選用的策略

2.問題的規(guī)模

3.編寫程序的語言

4.編譯程序產(chǎn)生的機器代碼的質(zhì)量

5.計算機執(zhí)行指令的速度

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

說，它是問題規(guī)模的函數(shù)。

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

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

稱T(n)為算法的(漸近)時間復(fù)雜度

算法=控制結(jié)構(gòu)+原操作

(固有數(shù)據(jù)類理的操作)

從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行

的次數(shù)作為算法運行時間的衡量準(zhǔn)則

a)x:=x+l;O(1)

b)FORI:=ltonDOx:=x+l;O(n)

c)FORj:=ltonDO

ForK:=lTONDOX:=K+1;0(/)

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

for(j=l;j<=n;++j){

cfi,j]=O;

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

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

voidselect_sort(inta[],intn)(

〃將a中金數(shù)序列重新排列成自小至大

〃有序的整數(shù)序列。

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

j=i；

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

if(a[kl<a[j])j=k;

a[j]-a[i]

}//select_sorc

voidbubble_sort(inta[],intn){

〃將a中就數(shù)序列重新排列成自小至大

〃有序的整數(shù)序列。

for(i=n-1.change=TRUE;i>l&&change;-i){

change=FALSE;

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

if(aO]>aU+l]){aU]*--a[j+l];

change=TRUE}

)

}//bubblc_sort

四、算法的存儲空間需求

算法的空間復(fù)雜度

S(n)=O(g(n))

表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。

算法的存儲量包括：

1.揄入數(shù)據(jù)所占空間；

2.程序本身所占空間；

3.輔助變量所占空間。

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

間。

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

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

第二章線性表

線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序(次序)集

線性結(jié)構(gòu)的基本特征：

1.集合中必存在唯一的一個“第一元素”；

2.集合中必存在唯一的一個“最后元素”；

3.除最后元素在外，均有唯一的后繼；

4.除第一元素之外，均有唯一的前驅(qū)。

2.1線性表的類型定義

線性表(linear-list)是n個元素的有限序列。

線性表的定義如下：

Iinear-list=(D,R)

數(shù)據(jù)對象：D={ai|aieElemSet,i=GO}

數(shù)據(jù)關(guān)系：R=(<ai-i,as>|ai-i,ai€D,i=2,...,n}

記為：(al,a2,a3,a4,…,an)

2.2線性表的操作

對線性表不僅可以進(jìn)行查詢(訪問)而且可以進(jìn)行插入、刪除操作。具體有：

1.INITIATE(L):設(shè)定一個空的線性表

2.LENGTH(L):求線性表長度的函數(shù)

3.GET(L,i):取元素的函數(shù)，若1WiWLENGTH(L),則函數(shù)值為給定線性表L中的第

i個數(shù)據(jù)元素，否則為空元素NULL。稱i為該數(shù)據(jù)元素在線性表中的位序

4.PRIOR(L,elem):求前驅(qū)函數(shù)。已知eIem為給定線性表L中的一個數(shù)據(jù)元素，若

它的位序大于1,則函數(shù)值為elem的前驅(qū)，否則為空元素

5.NEXT(L,elem):求后繼函數(shù)

6.LOCATE(L,x)：定位(查詢函數(shù))，給定值x,若線性表L中存在其值和x相等的

元素，則函數(shù)值為該數(shù)據(jù)元素在線性表中的位序，否則為零(Nil)o若線性表中值和x

相等的數(shù)據(jù)元素不止一個，則函數(shù)值為這些元素在線性表中的位序的最小值。

7.INSERT(L,i,b):前插操作。在給定線性表L中第i個數(shù)據(jù)元素之前插入一個新的

數(shù)據(jù)元素b。其中1WiWn+1,結(jié)果使表的長度增加1。

8.DELETE(L,i)：刪除操作。其中1WiWLENGTH(L),使線性表的長度減1。

9.EMPTY(L):判空表函數(shù)，true為空表，false為非空。

10.CLEAR(L):表置空操作。

此外，對線性表還可以進(jìn)行：合并、拆分、第制和排序等操作。

2.2線性表的順序存儲結(jié)構(gòu)

由于線性表的結(jié)構(gòu)特點，所以采用順序的方式存儲線性表是一種最簡單的方法。這種

線性表成為順序表。

由于順序存儲將線性表存放在一段連續(xù)的存儲單元中，且一般來講數(shù)據(jù)元素的大小是

等長的。所以只要我們已知第一個元素所在的單元地址，則其他元素的地址可推知。若第

一個元素的地址為：Ioc(a1)

則loc(ai)=loc(a1)+(l-1)*l,I為每個元素的長度,且loc(ai+1)=loc(ai)+l,其中

Ioc(a1)通常稱為線性表的起始位置或基地址。由此，只要確定了存儲線性表的起始位

置，線性表中的任一數(shù)據(jù)元素都可隨機存取。所以，順序存儲是一種隨機存取的存儲結(jié)

構(gòu)，在PASCAL中用一維數(shù)組描述之。

CONSTmaxIen二線性表的最大長度

TYPEsqlisttp=RECORD

EIem：ARRAY[1..maxIen]OFelemtp;

Last:0..maxlen

END;

Last實陸上是表示線性表的長度。

對于線性表的其他操作很容易實現(xiàn)，這里只討論線性表的插入和刪除操作、查詢和合

并。

一、線性表的插入操作

:25i=5

1

插入前I12|1321|2428304277

12345678

24125I2fil3ol421

插入后I1?I13211771

123456789

具體實現(xiàn)算法如下：

PROCins-sqIist(VARv:sqlisttp;i:integer;b:eIemtp);

{INSERT(v,i,b)}

IF(i<1)OR(i>v.last+1)THENREEORCinfeasible')

ELSEIFv.last^maxlenTHENERROR('OVERFLOW')

ELSE[FORj:=v.lastDOWNTOiDOv.elem[j+1]:=v.el