《數(shù)據(jù)結(jié)構(gòu)》本科教學(xué)課件

《數(shù)據(jù)結(jié)構(gòu)》本科第一章緒論2

目前，計(jì)算機(jī)業(yè)在飛速發(fā)展，其應(yīng)用領(lǐng)域也早不限于科學(xué)計(jì)算，而是廣泛深入到社會(huì)的各個(gè)部門。從應(yīng)用的角度來看，計(jì)算機(jī)在各部門的應(yīng)用大致可歸納為以下幾類：

（1）科學(xué)計(jì)算與分析

（2）計(jì)算機(jī)管理

（3）計(jì)算機(jī)實(shí)時(shí)控制

（4）計(jì)算機(jī)輔助設(shè)計(jì)/制造（CAD/CAM）及繪圖

（5）計(jì)算機(jī)通訊網(wǎng)絡(luò)

（6）辦公自動(dòng)化

（7）人工智能

（8）機(jī)器仿真

（9）計(jì)算機(jī)輔助教育（CAI）和娛樂緒論（續(xù)）

隨著計(jì)算機(jī)應(yīng)用的廣泛深入，計(jì)算機(jī)應(yīng)用領(lǐng)域會(huì)越來越廣，計(jì)算機(jī)要處理的數(shù)據(jù)更加多樣化，而數(shù)據(jù)之間的關(guān)系和對(duì)數(shù)據(jù)處理的要求也更為復(fù)雜。這就要求我們?cè)趶氖戮唧w的計(jì)算機(jī)應(yīng)用時(shí)，要用較科學(xué)的方式描述、存儲(chǔ)和處理數(shù)據(jù)，從而使計(jì)算機(jī)高效率地去完成預(yù)期的任務(wù)。

本章主要討論數(shù)據(jù)結(jié)構(gòu)、算法及算法分析方面的一些基本概念。

31.1數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容和方法41.1.1數(shù)據(jù)結(jié)構(gòu)的含義 數(shù)據(jù)結(jié)構(gòu)（DataStructure）簡(jiǎn)稱DS，研究的是計(jì)算機(jī)所處理數(shù)據(jù)元素間的關(guān)系及其操作實(shí)現(xiàn)的算法。包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及數(shù)據(jù)的操作。 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)機(jī)制等）、計(jì)算機(jī)軟件的研究(無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題)。數(shù)據(jù)結(jié)構(gòu)的含義

因此可以認(rèn)為，數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程，如圖1.1：5

圖1.1“數(shù)據(jù)結(jié)構(gòu)”所處的地位

代數(shù)系統(tǒng)數(shù)據(jù)表示法數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)存取

機(jī)器組織

編碼理論

數(shù)據(jù)的操作

算子關(guān)系數(shù)學(xué)

數(shù)據(jù)類型

存儲(chǔ)裝置硬件（計(jì)算機(jī)系統(tǒng)設(shè)計(jì)）軟件（計(jì)算機(jī)程序設(shè)計(jì)）

文件系統(tǒng)

數(shù)據(jù)組織

信息檢索1.1.2數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容1. 數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）指數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)（Data），客觀事物的符號(hào)表示。是指輸入到計(jì)算機(jī)并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。如方程中的整數(shù)、實(shí)數(shù)，源程序中的字符串，以及文字、圖像和聲音信號(hào)等等，都可作為計(jì)算機(jī)中的數(shù)據(jù)。數(shù)據(jù)元素（DataElement），數(shù)據(jù)的基本單位。簡(jiǎn)單的數(shù)據(jù)元素可以是整數(shù)、字符等形式。一般，數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)（DataItem）組成，常稱為記錄（Record）。6數(shù)據(jù)的邏輯結(jié)構(gòu)（續(xù)）

例如表1.1的圖書管理表，其中

a1，……，an對(duì)應(yīng)的每一行各是一個(gè)數(shù)據(jù)元素，而編號(hào)、書名等就是數(shù)據(jù)項(xiàng)。在計(jì)算機(jī)存取數(shù)據(jù)時(shí)，數(shù)據(jù)項(xiàng)是不可分割的最小存取單位。表1.1圖書管理表編號(hào)書名作者出版社出版日期……001數(shù)據(jù)庫周志逵科教1998.7……002數(shù)據(jù)結(jié)構(gòu)夏克儉王紹斌國(guó)防工業(yè)2007.2………………………………………………………………7a1a2..an數(shù)據(jù)的邏輯結(jié)構(gòu)（續(xù)）

上表（List）中每一行為一個(gè)數(shù)據(jù)元素（或記錄），記為ai(1≤i≤n)，元素之間呈現(xiàn)的是一種線性關(guān)系。此表可表示為： list=(a1,a2,……,an)

顯然表中每一數(shù)據(jù)元素包含的許多值是非數(shù)值性的（如文字、日期等數(shù)據(jù)），對(duì)其進(jìn)行的操作（或運(yùn)算）也不再是加、減、乘、除等數(shù)學(xué)運(yùn)算，而是諸如：

查詢（查找一本書的信息）、 插入（增加一本書的信息）、 修改（某書修訂后，修改元素中某些信息）、 刪除（某書不再版了，做刪除標(biāo)記）、 分類（按某數(shù)據(jù)項(xiàng)的值建立索引） 等這樣的運(yùn)算。8數(shù)據(jù)的邏輯結(jié)構(gòu)（續(xù)）9

具有相同性質(zhì)的數(shù)據(jù)元素組成的集合，稱為數(shù)據(jù)對(duì)象（DataObject），它是數(shù)據(jù)的一個(gè)子集。 計(jì)算機(jī)要處理的數(shù)據(jù)元素不是相互孤立的，而是有著各種各樣的聯(lián)系，這種數(shù)據(jù)元素之間的關(guān)系就稱作邏輯結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，歸納出四類基本的邏輯結(jié)構(gòu)：（1）集合結(jié)構(gòu)中的數(shù)據(jù)元素除了“屬于同一集合”的關(guān)系外，沒有其他關(guān)系（如例1–1）。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系（如例1–2）。（3）層次結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系（如例1–3）。（4）網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在若干個(gè)多對(duì)多關(guān)系（如例1–4）。例1-1集合10

例1–1學(xué)校舉辦了英語演講比賽和歌曲演唱比賽，參賽者可以獲得優(yōu)勝獎(jiǎng)和參與獎(jiǎng)。問多少學(xué)生在兩個(gè)競(jìng)賽中都獲得了優(yōu)勝獎(jiǎng)？求解這個(gè)問題可以將在兩個(gè)競(jìng)賽中獲得優(yōu)秀獎(jiǎng)的人分別構(gòu)成一個(gè)整體，問題便成了求兩個(gè)集合的交集。

英語

歌曲丁1優(yōu)勝王2優(yōu)勝?gòu)?優(yōu)勝李4參與張3參與李4優(yōu)勝例1-2表例1–2到醫(yī)院看病的病人需要排隊(duì)，而醫(yī)院實(shí)行先來先服務(wù)的原則。每個(gè)病人都有自己的病歷，病歷上有病歷的編號(hào)還有病人的其他具體信息。如表1.2所示。表1.2病人信息表 這張表中的元素存在一個(gè)順序關(guān)系，即誰在誰前，誰在誰后的信息（即病人診斷順序依次為張立，田方，……）。所以，可以用線性結(jié)構(gòu)來刻畫這種關(guān)系。編號(hào)

姓名性別

年齡-------172張立女30-------091田方男20------------------------------------------11例1-3大學(xué)系級(jí)行政機(jī)構(gòu)12

大學(xué)系級(jí)行政機(jī)構(gòu)，如圖1.2所示：

其中系、辦公室、……教師、學(xué)生可視為數(shù)據(jù)元素。元素之間呈現(xiàn)的是一種層次關(guān)系，即系級(jí)下層機(jī)構(gòu)為辦公室、教研室和班級(jí)，而辦公室、教研室和班級(jí)等單位又由若干個(gè)管理人員、教師、實(shí)驗(yàn)員和學(xué)生組成。管理員教師實(shí)驗(yàn)員學(xué)生辦公室班級(jí)教研室系例1-4田徑比賽的時(shí)間安排問題13

設(shè)田徑比賽項(xiàng)目有：A(跳高)、

B(跳遠(yuǎn))、C(標(biāo)槍)、D(鉛球)、E(100m跑)、F(200m跑)。參賽選手的項(xiàng)目表如下：?jiǎn)柸绾伟才疟荣悤r(shí)間，才能使得：

(1)每個(gè)比賽項(xiàng)目都能順利進(jìn)行（無沖突）；

(2)盡可能縮短比賽時(shí)間。

姓名

項(xiàng)目1

項(xiàng)目2

項(xiàng)目3丁一ABE馬二CD張三CEF李四DFA王五BF例1-4（續(xù)）14

此問題可歸納為圖的“染色“問題：設(shè)項(xiàng)目A∽F各表示一數(shù)據(jù)元素，以○表示。若兩個(gè)項(xiàng)目不能同時(shí)舉行，則將其連線。由此得到如圖1.3所示的結(jié)構(gòu)。若用四種顏色表示四個(gè)時(shí)間段，一種著色方案如圖所示。

FCEABDFCEABD

圖1.3即：紅色時(shí)間段(如8~10點(diǎn))—A、C項(xiàng)目；淺藍(lán)—B、D項(xiàng)目；深藍(lán)—E項(xiàng)目；紫色—F項(xiàng)目。數(shù)據(jù)邏輯結(jié)構(gòu)（續(xù)）15

上面的例子中所描述的邏輯結(jié)構(gòu)都是從具體問題中抽象出來的數(shù)據(jù)模型，是獨(dú)立于計(jì)算機(jī)存儲(chǔ)器的。數(shù)據(jù)元素并不是孤立存在的，它們之間存在著某種關(guān)系（或聯(lián)系、結(jié)構(gòu)）。對(duì)于例1-2，數(shù)據(jù)元素之間呈現(xiàn)的是一種線性關(guān)系，或線性(linear)結(jié)構(gòu)；對(duì)于例1-3，呈現(xiàn)的是一種層次關(guān)系，或樹(Tree)結(jié)構(gòu)；對(duì)于例1-4，呈現(xiàn)的是一種網(wǎng)狀關(guān)系，或圖(Graph)結(jié)構(gòu)。如圖1.4所示。

（線性關(guān)系）（層次關(guān)系）（網(wǎng)狀關(guān)系） 圖1.42．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（或物理結(jié)構(gòu)）（PhysicalStructure）

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素的表示 計(jì)算機(jī)中表示信息的最小單位是比特（Bit），即二進(jìn)制數(shù)中的一位。數(shù)據(jù)元素由若干位組成的位串來表示，通常稱這個(gè)位串為節(jié)點(diǎn)（Node）或元素（Element）。當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，數(shù)據(jù)項(xiàng)的取值范圍稱為數(shù)據(jù)域（DataField）。關(guān)系的表示在存儲(chǔ)器物理位置上如何反映數(shù)據(jù)元素之間的關(guān)系。目前，對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)常用的有四種存儲(chǔ)表示：（1）順序存儲(chǔ)（SequentialStorage

）：將數(shù)據(jù)結(jié)構(gòu)中各元素按照其邏輯順序存放于存儲(chǔ)器一片連續(xù)的存儲(chǔ)空間中（如c語言的一維數(shù)組）。如表L=(a1,a2，……,an)的順序結(jié)構(gòu)如圖1.5所示。16數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（續(xù)）（2）鏈?zhǔn)酱鎯?chǔ)（LinkedStorage）：將數(shù)據(jù)結(jié)構(gòu)中各元素分布到存儲(chǔ)器的不同點(diǎn)(稱為節(jié)點(diǎn))，用地址（或鏈指針）方式建立它們之間的聯(lián)系，由此得到的存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。如表L=(a1,a2，……,an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖1.6：

鏈?zhǔn)浇Y(jié)構(gòu)是本課程的一個(gè)重點(diǎn)，因?yàn)樵刂g的關(guān)系在計(jì)算機(jī)內(nèi)部很大程度上是通過地址或指針來建立的。（3）索引存儲(chǔ)（IndexedStorage）：在存儲(chǔ)數(shù)據(jù)的同時(shí)，建立一個(gè)附加的索引表，即索引存儲(chǔ)結(jié)構(gòu)=數(shù)據(jù)文件+索引表。17a1

a2…………an圖1.5

(存儲(chǔ)器)

a1

a2

an^數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（續(xù)）18例1-5電話號(hào)碼查詢問題。 為便于提高查詢的速度，在存儲(chǔ)用戶數(shù)據(jù)文件的同時(shí)，建立一張姓氏索引表，如圖1.7所示。這樣，查找一個(gè)電話就可以先查找索引表，再查找相應(yīng)的數(shù)據(jù)文件，無疑加快了查詢的速度。

姓名

電話

丁一62331234…………

王二62345678…………

張三63450987…………

數(shù)據(jù)文件

姓氏

地址

丁

王

張…………

索引表數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（續(xù)）19

（4）散列存儲(chǔ)(HashStructure)：根據(jù)數(shù)據(jù)元素的特殊字段(稱為關(guān)鍵字key)，計(jì)算數(shù)據(jù)元素的存放地址，然后數(shù)據(jù)元素按地址存放，所得到的存儲(chǔ)結(jié)構(gòu)為散列存儲(chǔ)結(jié)構(gòu)(或Hash結(jié)構(gòu))。3.數(shù)據(jù)的操作

一般而言，必須對(duì)數(shù)據(jù)進(jìn)行加工處理，才能得到問題的解。在非數(shù)值性問題中，對(duì)數(shù)據(jù)的操作（或運(yùn)算）已不限于對(duì)數(shù)據(jù)進(jìn)行加、減、乘、除等數(shù)學(xué)運(yùn)算。數(shù)據(jù)的操作是定義在邏輯結(jié)構(gòu)上的，而操作的具體實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的?；镜臄?shù)據(jù)操作主要有以下幾種： （1）查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定條件的數(shù)據(jù)元素的位置或值。數(shù)據(jù)的操作（2）插入：在數(shù)據(jù)結(jié)構(gòu)中添加新的數(shù)據(jù)元素。（3）刪除：刪去數(shù)據(jù)結(jié)構(gòu)中指定的數(shù)據(jù)元素。（4）更新：改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)數(shù)據(jù)元素一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的值。（5）排序：重新安排數(shù)據(jù)元素之間的邏輯順序，使之按（某個(gè)數(shù)據(jù)項(xiàng)的）值由小（大）到大（小）的次序排列。 其中，查找是一種引用型操作，即它不改變現(xiàn)有結(jié)構(gòu)，而其余四種均會(huì)改變現(xiàn)有結(jié)構(gòu)，被稱為加工型操作。 綜上所述，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間關(guān)系和操作的學(xué)科。在本書中，對(duì)數(shù)據(jù)結(jié)構(gòu)的詳細(xì)討論，都是從數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的操作這三方面展開的，讀者應(yīng)掌握住這個(gè)規(guī)律，以便以后知識(shí)的學(xué)習(xí)。201.1.3研究數(shù)據(jù)結(jié)構(gòu)的方法

研究數(shù)據(jù)結(jié)構(gòu)是為了編寫解決問題（或完成任務(wù)）的程序。用計(jì)算機(jī)求解一個(gè)實(shí)際問題的過程，一般可以用圖1.8所示的模型加以描述。圖1.8計(jì)算機(jī)求解問題的流程

即首先要從現(xiàn)實(shí)問題出發(fā)，抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)求解此數(shù)學(xué)模型的算法，最后根據(jù)這個(gè)算法編出程序，經(jīng)過測(cè)試、排錯(cuò)、運(yùn)行直至得到最終的解答?，F(xiàn)實(shí)問題、數(shù)學(xué)模型、算法和程序是問題求解過程中出現(xiàn)的四個(gè)重要環(huán)節(jié)。21現(xiàn)實(shí)問題數(shù)學(xué)模型算法程序解1.2抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

抽象數(shù)據(jù)類型（AbstractDataType,簡(jiǎn)稱ADT）是指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在其上的一組操作。本書采用類C語言作為描述算法，這使得數(shù)據(jù)結(jié)構(gòu)的描述和討論簡(jiǎn)明清晰，不拘泥于C語言的細(xì)節(jié)，又容易轉(zhuǎn)換為C或C++程序。以下面的形式描述ADT：

ADT=（D，R，P） 其中，D是數(shù)據(jù)元素的有限集；R是D上關(guān)系的有限集，（D，R）構(gòu)成了一個(gè)數(shù)據(jù)結(jié)構(gòu)；P是對(duì)該數(shù)據(jù)結(jié)構(gòu)的基本操作集。用以下格式定義抽象的數(shù)據(jù)類型：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)元素集：<元素集的定義>

數(shù)據(jù)關(guān)系集：<關(guān)系集的定義>

基本操作集：<基本操作的定義> }ADT抽象數(shù)據(jù)類型名；22抽象數(shù)據(jù)類型

其中，基本操作的定義格式是： 基本操作名(參數(shù)表)

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>

基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&開頭，除了可提供輸入值外，還可返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前的數(shù)據(jù)結(jié)構(gòu)及參數(shù)應(yīng)滿足的條件，“操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化和應(yīng)返回的結(jié)果。

231.3學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的1.3.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及在計(jì)算機(jī)科學(xué)中的地位

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容來源于圖論、操作系統(tǒng)、編譯系統(tǒng)、編碼理論和檢索與分類技術(shù)的相關(guān)領(lǐng)域。20世紀(jì)60年代末，美國(guó)一些大學(xué)把上述領(lǐng)域中的技術(shù)歸納為《數(shù)據(jù)結(jié)構(gòu)》課程。美國(guó)人D.E.克勞特《計(jì)算機(jī)程序設(shè)計(jì)技巧》一書，對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及算法進(jìn)行了系統(tǒng)的闡述。我國(guó)從70年代末在各大專院校陸續(xù)開設(shè)數(shù)據(jù)結(jié)構(gòu)課程，目前該課程已經(jīng)是計(jì)算機(jī)專業(yè)的核心課程之一。 關(guān)于計(jì)算機(jī)科學(xué)的概念，計(jì)算機(jī)界的權(quán)威人士認(rèn)為： 其一，計(jì)算機(jī)科學(xué)是信息結(jié)構(gòu)轉(zhuǎn)換的科學(xué)，構(gòu)造有關(guān)信息結(jié)構(gòu)的轉(zhuǎn)換模型，對(duì)其進(jìn)行研究是計(jì)算機(jī)科學(xué)中最根本性的問題。而構(gòu)造出現(xiàn)實(shí)問題中的數(shù)據(jù)結(jié)構(gòu)模型，并合理地將其映象到計(jì)算機(jī)存儲(chǔ)裝置中，是這種觀點(diǎn)的具體體現(xiàn)。24學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的

其二，計(jì)算機(jī)科學(xué)是算法的學(xué)問，研究的是對(duì)數(shù)據(jù)處理的方法或規(guī)則。要用計(jì)算機(jī)完成具體任務(wù)，離不開對(duì)算法的研究。因而，“數(shù)據(jù)結(jié)構(gòu)”+“算法”是計(jì)算機(jī)科學(xué)研究中的基礎(chǔ)課題，其理論基礎(chǔ)是離散數(shù)學(xué)中的圖論、集合論和關(guān)系理論等等，實(shí)踐基礎(chǔ)是程序設(shè)計(jì)技術(shù)。1.3.2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的在分析、開發(fā)系統(tǒng)與應(yīng)用軟件中要用到的數(shù)據(jù)結(jié)構(gòu)知識(shí)。 如操作系統(tǒng)、編譯系統(tǒng)、數(shù)據(jù)庫和人工智能中涉及到：棧和隊(duì)列、存儲(chǔ)管理表、目錄樹、語法樹、索引樹、搜索樹、散列表、有向圖等等。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了提高程序設(shè)計(jì)水平。 我們知道，不論計(jì)算機(jī)從事哪方面的應(yīng)用，一般都是由計(jì)算機(jī)運(yùn)行程序來實(shí)現(xiàn)的，而任何一個(gè)程序都是建立和運(yùn)行在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的。這就要求在做程序設(shè)計(jì)時(shí)，一方面要描述好對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，另一方面要設(shè)計(jì)正確、精確和快速處理數(shù)據(jù)的算法（或程序）。做到這兩點(diǎn)，無疑程序設(shè)計(jì)水平將會(huì)有一個(gè)大的提高。251.4算法的定義及其特性1.4.1算法的定義

算法（Algorithm）是一個(gè)有窮規(guī)則（或語句、指令）的有序集合。它確定了解決某一問題的一個(gè)運(yùn)算序列。對(duì)于問題的初始輸入，通過算法有限步的運(yùn)行，產(chǎn)生一個(gè)或多個(gè)輸出。例1-6求兩正整數(shù)m、n的最大公因子的算法如下：

①輸入m,n； ②m/n（整除），余數(shù)→r(0≤r≤n)； ③若r=0,則當(dāng)前n=結(jié)果，輸出n,算法停止；否則，轉(zhuǎn)④； ④n→m,r->n；轉(zhuǎn)②。如初始輸入m=10,n=4,則m,n,r在算法中的變化如下：

mnr1042420(停止)

即10和4的最大公因子為2。26算法特性1.4.2算法的性質(zhì)

(1)

有窮性

——算法執(zhí)行的步驟（或規(guī)則）是有限的；

(2)

確定性

——每個(gè)計(jì)算步驟無二義性；

(3)

可行性

——每個(gè)計(jì)算步驟能夠在有限的時(shí)間內(nèi)完成；

(4)

輸入

——算法有一個(gè)或多個(gè)外部輸入；

(5)

輸出

——算法有一個(gè)或多個(gè)輸出。 這里要說明的是，算法與程序有聯(lián)系又有區(qū)別。二者都是為完成某個(gè)任務(wù)，或解決某個(gè)問題而編制的規(guī)則（或語句）的有序集合，這是它們的共同點(diǎn)。區(qū)別在于：其一，算法與計(jì)算機(jī)無關(guān)，但程序依賴于具體的計(jì)算機(jī)語言。其二，算法必須是有窮盡的，但程序可能是無窮盡的。其三，算法可忽略一些語法細(xì)節(jié)問題，重點(diǎn)放在解決問題的思路上，但程序必須嚴(yán)格遵循相應(yīng)語言工具的語法。算法轉(zhuǎn)換成程序后才能在計(jì)算機(jī)上運(yùn)行。另外，在設(shè)計(jì)算法時(shí)，一定要考慮它的確定性，即算法的每個(gè)步驟都是無二義性的（即一條規(guī)則不能有兩種以上的解釋）。27例1-6中的算法轉(zhuǎn)換成C語言將例1-6中的算法轉(zhuǎn)換成C語言程序如下：#include“stdio.h”intmaxog();main(){intm,n,j;charflag=‘Y’;while(flag==‘y’||flag==‘Y’) {printf(“\n”);scanf(“input=%d%d”,&m,&n);//輸入兩個(gè)整數(shù)m,n if(m>0&&n>0){j=maxog(m,n);//求m,n的最大公因子

printf(“output=%d\n”,j);}//輸出結(jié)果

printf(“continue?(y/n)”); flag=getchar();//輸入’y’或’Y’繼續(xù)，否則停止

}}28算法轉(zhuǎn)換成C語言 intmaxog(intm,intn)//求m、n的最大公因子算法（或函數(shù)）

{intr=m%n; while(r!=0) {m=n;n=r;r=m%n;} return(n);}

以后章節(jié)中的算法均以C語言的函數(shù)形式描述，而main()和數(shù)據(jù)I/O就不描述了。另外，由于某種原因（如參數(shù)錯(cuò)，存儲(chǔ)分配失敗等）導(dǎo)致算法無法繼續(xù)執(zhí)行下去時(shí)，約定調(diào)用函數(shù)ERROR()進(jìn)行出錯(cuò)處理。 討論了數(shù)據(jù)結(jié)構(gòu)與算法的基本概念后，有必要提到瑞士科學(xué)家沃思（N.Wirth）的著名公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序 數(shù)據(jù)結(jié)構(gòu)是研究從具體問題中抽象出來的數(shù)學(xué)模型如何在計(jì)算機(jī)存儲(chǔ)器中表示出來；而算法研究的是對(duì)數(shù)據(jù)處理的步驟。如果對(duì)問題的數(shù)據(jù)表示和數(shù)據(jù)處理都做出了具體的設(shè)計(jì)，就相當(dāng)于完成了相應(yīng)的程序。291.4.3算法的設(shè)計(jì)目標(biāo)算法的設(shè)計(jì)應(yīng)滿足以下五點(diǎn)： 正確性算法應(yīng)當(dāng)滿足具體問題的需求，一般包括對(duì)輸入、輸出、處理等的明確的無歧義性的描述。 可讀性可讀性有助于對(duì)算法的理解及幫助排除算法中隱藏的錯(cuò)誤，也有助于算法的交流和移植。 健壯性當(dāng)輸入不合法的數(shù)據(jù)時(shí)，算法應(yīng)能做出相應(yīng)的處理，而不產(chǎn)生不可預(yù)料的結(jié)果。 高效率算法的效率指算法執(zhí)行時(shí)間的長(zhǎng)短，稱作算法的時(shí)間復(fù)雜度。 低存儲(chǔ)量需求算法的存儲(chǔ)量需求指算法執(zhí)行期間所需要的最大存儲(chǔ)空間，稱作算法的空間復(fù)雜度。

301.4.4算法效率的度量

算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來度量。這個(gè)時(shí)耗與下面因素有關(guān)：書寫算法的程序設(shè)計(jì)語言；編譯產(chǎn)生的機(jī)器語言代碼質(zhì)量；機(jī)器執(zhí)行指令的速度；問題的規(guī)模。 這四個(gè)因素中，前三個(gè)都與機(jī)器有關(guān)。當(dāng)度量一個(gè)算法的效率拋開具體的機(jī)器、僅考慮算法本身的效率高低時(shí)，算法效率僅與問題的規(guī)模有關(guān)，也就是說，算法效率是問題規(guī)模的函數(shù)。為了詳細(xì)描述這個(gè)函數(shù)，我們引入以下幾個(gè)概念：

1.語句的頻度(FrequencyCount)

語句頻度定義為可執(zhí)行語句在算法（或程序）中重復(fù)執(zhí)行的次數(shù)。若某語句執(zhí)行一次的時(shí)間為t，執(zhí)行次數(shù)為f，則該語句所耗時(shí)間的估計(jì)為t·f。31例1-7求兩個(gè)n階方陣乘積

c[0][0]c[0][1]···········c[0][j]···········c[0][n-1] c[1][0]c[1][1]···········c[1][j]···········c[1][n-1] ···········

Cn·n=An·nBn·n= ··········· c[i][0]c[i][1]···········c[i][j]···········c[i][n-1] ··········· c[n-1][0]c[n-1][1]·······c[n-1][j]·······c[n-1][n-1]

其中：n-1

c[i][j]=∑A[i][k]B[k][j]

k=032例1-7（序）voidMATRIXM(A,B,C) floatA[n][n],B[n][n],c[n][n]; {inti,j,k; 語句頻度

for(i=0;i<n;i++) n+1 for(j=0;j<n;j++) n(n+1){c[i][j]=0; n2 for(k=0;k<n;k++) n2(n+1) c[i][j]=c[i][j]+A[i][k]*B[k][j];}} n32.算法的時(shí)間復(fù)雜度(TimeComplexity)

算法的時(shí)間復(fù)雜度定義為算法中可執(zhí)行語句的頻度之和，記為T(n)。T(n)是算法所需時(shí)間的一種估計(jì)，n為問題的規(guī)模（或大小、體積）。如例1-7中，問題的規(guī)模n為矩陣的階，該算法的時(shí)間復(fù)雜度為：

T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

當(dāng)n->∞時(shí)，lim(T(n)/n3)=2，故T(n)與n3為同階無窮大，或說T(n)與n3成正比、T(n)的量級(jí)為n3，記為：T(n)=O(n3)

。33例1-8在數(shù)組中查找

在數(shù)組（A[1],A[2],..........,A[n]）中查找最后一個(gè)與給定值k相等的元素的序號(hào)的算法。

intsearch(datatypeA[n+1],datatypek) {inti=n;A[0]=k;while(i>0&&A[i]!=k)i--; return(i); }

本例應(yīng)以平均查找次數(shù)為算法的T(n)。設(shè)查找每個(gè)元素的概率pi(1≤i≤n)均等，即pi=1/n，查找元素k時(shí)，k與A[i]的比較次數(shù)（即執(zhí)行while循環(huán)語句的次數(shù)）Ci=n-(i-1)，則查找次數(shù)的平均值（或期望值）：

因n->∞時(shí)，lim(T(n)/n)=1/2，故T(n)=O(n)，此時(shí)又稱T(n)為算法的漸進(jìn)時(shí)間復(fù)雜度。34T(n)=T(n)的量級(jí)T(n)的量級(jí)通常有：O(c)——常數(shù)級(jí)，不論問題規(guī)模多大，T(n)一致，因而是理想的T(n)量級(jí)；O(n)——線性級(jí)；O(n2),O(n3)——平方、立方級(jí)；O(log2n),O(n*log2n)——對(duì)數(shù)、線性對(duì)數(shù)級(jí)；O(2n)——指數(shù)級(jí)，時(shí)間復(fù)雜度最差。以上幾種常見的T(n)隨n變化

的增長(zhǎng)率如圖1.9所示：35T(n)

O(2n)

O(n3)

O(n2)

O(n)

O(n*log2n)

O(log2n)

O(c)

n

算法分析

對(duì)較為復(fù)雜的算法，可分段分析其時(shí)間復(fù)雜度。如某算法可分為兩部分，其時(shí)間復(fù)雜度分別為：

T1(n)=O(f(n)),T2(n)=O(g(n))此時(shí)兩部分問題的體積一致，則總的T(n)=T1(n)+T2(n)=O(max(f(n),g(n)),表示取f(n)、g(n)中最大者。 但若T1(m)=O(f(m)),T2(n)=O(g(n)),兩部分的體積不一致，則： T(m,n)=T1(m)+T2(n)=O(f(m)+g(n))。 另外，算法空間復(fù)雜度的定義： 設(shè)算法對(duì)應(yīng)問題的體積（或規(guī)模）為n,執(zhí)行算法所占存儲(chǔ)空間的量級(jí)為D(n)，則D(n)為算法的空間復(fù)雜度(SpaceComplexity)。36第一章小結(jié)

37DS時(shí)間復(fù)雜度T(n)空間復(fù)雜度D(n)邏輯結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)順序存儲(chǔ)散列存儲(chǔ)查詢DS上的操作插入刪除更新算法算法定義、性質(zhì)算法分析第一章作業(yè)1.試用DS=（D，R）形式說明字符串:S=“s1,s2,……,sn”(si∈char)是一個(gè)數(shù)據(jù)結(jié)構(gòu)，即S=（D，R）中D=？R=？2.設(shè)五叉口：其中E、C道為單行線。試構(gòu)造使該路口行駛車輛不碰撞的交通管理模型。（提示:找出路口各行車路線(AB,BC,….),若兩行車路線不能對(duì)駛,則將其連線。)3.設(shè)n為正整數(shù)，求下列算法段的時(shí)間復(fù)雜度，即T(n)=O(?)(1)i=1;k=0;(2)i=1;j=0;(3)for(i=n-1;i>=1;i--)while(i<n) while(i+j<=n)for(j=0;j<=i-1;j++){k=k+10*i;i++;}{if(i>j)j++;{temp=A[j];A[j]=A[j+1]; elsei++;} A[j+1]=temp;}38

CBAED第二章線性表

數(shù)據(jù)元素之間滿足線性關(guān)系的表稱為線性表，是一種最基本、最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)類型。本章討論線性表的邏輯和存儲(chǔ)結(jié)構(gòu)、相關(guān)算法的實(shí)現(xiàn)以及線性表應(yīng)用舉例。2.1線性表的定義及基本操作2.1.1定義：線性表(LinearList)是若干數(shù)據(jù)元素的一個(gè)線性序列，記為：

L=(a0,????ai-1aiai+1??????an-1)

其中：L為表名，ai(0≤i≤n-1)為數(shù)據(jù)元素；n為表長(zhǎng)，n>0

時(shí)，L為非空表，否則為空表。2.1.2線性表的邏輯結(jié)構(gòu)和特征

線性表L可用二元組形式描述：L=(D,R)

數(shù)據(jù)元素集合:D={ai|ai∈datatype,i=0,1,2,?????????n-1,n≥0}

關(guān)系集合:R={<ai,ai+1>|ai,ai+1∈D,0≤i≤n-2}

表長(zhǎng)n=0時(shí)，L為空表；關(guān)系符<ai,ai+1>在這里稱為有序?qū)?，表示任意相鄰的兩個(gè)元素之間的一種先后次序關(guān)系，稱ai是ai+1的直接前驅(qū),ai+1是ai的直接后繼，當(dāng)表長(zhǎng)n≤1時(shí)，關(guān)系集R為空集。39例2-1線性表的例子

L1=(A,B,……,Z)元素為字符；L2=(6,7,……,105)元素為整數(shù)； 學(xué)生記錄表：

線性表的特征：對(duì)非空表,a0是表頭,無前驅(qū)；an-1是表尾,無后繼；其它的每個(gè)元素ai有且僅有一個(gè)直接前驅(qū)(ai-1)和一個(gè)直接后繼(ai+1)。2.1.3線性表的抽象數(shù)據(jù)類型表示

設(shè)線性表L=(a0,a1,……,an-1)，對(duì)L的抽象數(shù)據(jù)類型表示：40

學(xué)號(hào)

姓名性別

年齡班級(jí)-------J99001丁蘭女19計(jì)99-------J99002王林男20計(jì)99-------------------------------------------------J99032馬紅女18計(jì)99-------a0a1....a31線性表的抽象數(shù)據(jù)類型表示ADTList{數(shù)據(jù)元素集：D={ai|ai∈datatype,i=0,1,2,……n-1,n≥0}

數(shù)據(jù)關(guān)系集：R={<ai,ai+1>|ai,ai+1∈D,0≤i≤n-2}

基本操作集：PListInit(&L)

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

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

初始條件：線性表L存在。操作結(jié)果：將L置為一張空表。ListLength(L)

初始條件：線性表L存在。操作結(jié)果：返回L中元素個(gè)數(shù)(即表長(zhǎng)n)。ListEmpty(L)

初始條件：線性表L存在。操作結(jié)果：L為空表時(shí)返回TRUE，否則返回FALSE。41線性表的抽象數(shù)據(jù)類型表示GetElem(L,i)

初始條件：線性表L存在，且0≤i≤n-1。操作結(jié)果：返回L中第i個(gè)元素的值(或指針)。LocateElem(L,e)

初始條件：線性表L存在，且e∈datatype。 操作結(jié)果：若e在L中，返回e的序號(hào)(或指針)；否則返回e不在表中的信息（實(shí)際應(yīng)用中如-1或NULL）。即： i當(dāng)元素e=ai∈L,且ai是第一個(gè)與e相等時(shí)；LocateElem(L,e)=-1e不屬于L時(shí)。PreElem(L,cur)

初始條件：線性表L存在，且cur∈datatype。操作結(jié)果：若cur在L中且不是表頭，返回cur的直接前驅(qū)，否則返回NULL。SuccElem(L,cur)

初始條件：線性表L存在，且cur∈datatype。操作結(jié)果：若cur在L中且不是表尾元素，返回cur的直接后繼的值，否則返回NULL。42線性表的抽象數(shù)據(jù)類型表示ListInsert(&L,i,e)

初始條件：線性表L存在，且e∈datatype。 操作結(jié)果：若0≤i≤n-1，將e插入到ai之前，若i=n，將e插到表尾，表長(zhǎng)增加1，函數(shù)返回TURE；i為其他值時(shí)返回FALSE，L無變化。即： 插入前：(a0,a1,---,ai-1,ai,ai+1-------,an-1)

插入后：(a0,a1,---,ai-1,e,ai,ai+1-------,an-1)ListDel(&L,i)

初始條件：線性表L存在。 操作結(jié)果：若0≤i≤n-1，將第ai從表中刪除，函數(shù)返回TURE，否則函數(shù)返回FALSE，L無變化。即：刪除前:(a0,a1,---,ai-1,ai,ai+1-------,an-1)

刪除后:

(a0,a1,---,ai-1，ai+1-------,an)ListTraverse(L)

初始條件：線性表L存在。操作結(jié)果：依次對(duì)表中的元素利用visit()函數(shù)進(jìn)行訪問。}ADTList；43線性表的操作

以上運(yùn)算是對(duì)線性表L施加的一些基本運(yùn)算，對(duì)線性表L的運(yùn)算還有：

合并、拆分、復(fù)制、排序等等。例2-2設(shè)線性表La=(a0a1,……,am-1),Lb=(b0b1,……,bn-1)，求La∪Lb=>La，如圖2.1所示。

算法思路：依次取Lb中的bi(i=0,1,…,n-1)，若bi不在La中，則將其插入。算法描述：voidUnion(list*La,list*Lb) {inti,k; datatypex; for(i=0;i<ListLength(Lb);i++) {x=GetElem(Lb,i);k=LocateElem(La,x); if(k==-1)ListInsert(La,ListLength(La),x);}}類似可寫出求La–Lb,La∩Lb等運(yùn)算的算法。44

1357La

57911

Lb線性表的操作例2-3

設(shè)計(jì)清除線性表L=(a0,a1,---,ai,-------,an-1)中重復(fù)元素的算法。算法思路：對(duì)當(dāng)前表L中的每個(gè)ai（0≤i≤n-2），依次與aj(i+1≤j≤n-1)比較，若與ai相等，則刪除之。算法描述：

voidPurge(list*L) {inti=0,j;datatypex,y; 初始：L=（1，3，1，5，3，5，7）

while(i<ListLength(L)-1) i {x=GetElem(L,i);j=i+1;j while(j<ListLength(L))結(jié)果：L=（1，3，5，7）

{y=GetElem(L,j);if(y==x)ListDel(L,j);elsej++;} i++;}}2.2

線性表的順序存儲(chǔ)結(jié)構(gòu) 線性表在計(jì)算機(jī)存儲(chǔ)器中的映象（或表示）一般有兩種形式，一種是順序映象，一種是鏈?zhǔn)接诚蟆?52.2.1順序表

若將線性表L=(a0,a1,……,an-1)中的各元素依次存儲(chǔ)于計(jì)算機(jī)一片連續(xù)的存儲(chǔ)空間，如圖2.2所示。這種機(jī)內(nèi)表示為線性表的順序存儲(chǔ)結(jié)構(gòu)(順序表)。地址：b:}占d個(gè)單元

b+d: 設(shè)Loc(ai)為ai的地址，Loc(a0)=b，則：

… Loc(a1)=b+1*d

b+i*d: ........ … Loc(ai)=b+i*d

b+n*d:

圖2.2

順序表的特點(diǎn)：(1)邏輯上相鄰的元素ai,ai+1，存儲(chǔ)位置也是相鄰的；(2)對(duì)ai的存取為隨機(jī)存取或按地址存取。(3)存儲(chǔ)密度高。存儲(chǔ)密度D=(數(shù)據(jù)結(jié)構(gòu)中元素所占存儲(chǔ)空間)/(整個(gè)數(shù)據(jù)結(jié)構(gòu)所占空間)。 順序表的不足：對(duì)表的插入和刪除等運(yùn)算的時(shí)間復(fù)雜度較差。46a0a1

…ai…an-1線性表順序存儲(chǔ)結(jié)構(gòu)

在C語言中，一維數(shù)組也是存放于一片連續(xù)的存儲(chǔ)空間，故可借助于C語言中一維數(shù)組類型來描述線性表的順序存儲(chǔ)結(jié)構(gòu)，即: #definemaxsize1024//線性表的最大長(zhǎng)度

typedefstruct//表的類型

{datatypedata[maxsize];//表的存儲(chǔ)空間

intlast;//當(dāng)前表尾指針

}sqlist;*sqlink;//表說明符 如果說明sqlinkL;L=(sqlink)malloc(sizeof(sqlist));則指針L指向一個(gè)線性表：

ai表示為L(zhǎng)->data[i](0≤i≤L->last)

圖2.3

47L->data[0]..…i..…L->last->n-1maxsize-1空閑單元a0…ai

…an-12.2.2基本運(yùn)算的相關(guān)算法

關(guān)于線性表的運(yùn)算，有些實(shí)現(xiàn)起來是相當(dāng)簡(jiǎn)單的，例如： 置空表：ListClear(L),令L->last=-1；取ai:GetElem(L,i),取L->data[i]； 求表長(zhǎng)：ListLength(L),取L->last之值加1即可。 所以主要討論插入、刪除、定位等算法的實(shí)現(xiàn)。1.前插：將一給定值e插在元素ai之前，即實(shí)現(xiàn)ListInsert(L,i,e)。算法思路：若表存在空閑空間,且0≤i≤L->last+1,將(L->data[L->last]～L->data[i])順序下移一個(gè)數(shù)據(jù)單位，然后將e插入L->data[i]處。算法描述：

intListInsert(sqlinkL,inti,datatypee){if(L->last>=maxsize-1){ERROR(L);return(0);} elseif(i<0||i>L->last+1){ERROR(i);return(0);} else{for(intj=L->last;j>=i;j--) L->data[j+1]=L->data[j]; L->data[i]=e;L->last++; return(1);}}48L->data[0]..…i..…L->last->n-1maxsize-1空閑a0…ai

…an-1基本運(yùn)算的相關(guān)算法算法分析：算法的主要時(shí)耗在數(shù)據(jù)元素的移動(dòng)上，即算法中for語句上，故以插入一個(gè)元素的平均移動(dòng)次數(shù)刻畫算法的T(n)(n為表長(zhǎng))。設(shè)e插入ai(0≤i≤n)處的概率pi均等，即pi=1/(n+1),而插入e時(shí)的元素移動(dòng)次數(shù)Ci=n-i,則平均移動(dòng)次數(shù)為：

T(n)=piCi=

n/2=O(n)。49a0…ai

…an-1L->data[0]..…i..…L->last->n-1maxsize-1pi=1/(n+1)Ci=n-i基本運(yùn)算的相關(guān)算法2.刪除：將表中第i個(gè)元素ai從表中刪除，即實(shí)現(xiàn)ListDel(L,i)。算法思路：若參數(shù)i滿足：0≤i≤L->last,將表中L->data[i+1]∽L->data[L->last]部分順序向上移動(dòng)一個(gè)元素位置，擠掉L->data[i]。算法描述：

intListDel(sqlinkL,inti){if(i<0||i>L->last){ERROR(L);return(0);} else{for(intj=i+1;j<=L->last;j++) L->data[j-1]=L->data[j];L->last--;return(1);}}算法分析：設(shè)刪除ai(0≤i≤n-1)的概率pi均等,即pi=1/n,刪除ai的元素移動(dòng)次數(shù)Ci=n-(i+1),則平均移動(dòng)次數(shù)為：

T(n)=piCi=(n-1)/2=O(n)。50a0…ai

…an-1L->data[0]..…i..…L->last->n-1maxsize-1空閑基本運(yùn)算的相關(guān)算法3.定位：確定給定元素e在表L中第一次出現(xiàn)的位置（或序號(hào)）。即實(shí)現(xiàn)LocateElem(L,e)。算法對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)如圖所示。算法思路：設(shè)一掃描變量i(初值=0)，判斷當(dāng)前表中元素ai是否等于e，若相等，則返回當(dāng)前i值（表明e落在表的第i位置）；否則i加1，繼續(xù)往下比較。若表中無一個(gè)元素與e相等，則返回-1。算法描述：

intLocateElem(sqlinkL,datatypee) {inti=0; while(i<=L->last&&L->data[i]!=e) i++; if(i<=L->last)return(i);elsereturn(-1);}算法分析：算法時(shí)耗主要在while語句中元素e與ai的比較次數(shù)上，用平均比較次數(shù)來刻畫算法的T(n)。設(shè)元素ai(0≤i≤n-1)與e相等的概率pi均等，即pi=1/n,查找ai與e相等的比較次數(shù)Ci=i+1,則平均的比較次數(shù)為：

T(n)=piCi=(n+1)/2=O(n)。51L->data[0]..…i..…L->last->n-1maxsize-1空閑a0…ai

…an-12.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)有存儲(chǔ)密度高及能夠隨機(jī)存取等優(yōu)點(diǎn)，但存在以下幾點(diǎn)不足：(1)插入、刪除等運(yùn)算耗時(shí)，且存在元素在存儲(chǔ)器中成片移動(dòng)的現(xiàn)象；(2)要求系統(tǒng)提供一片較大的連續(xù)存儲(chǔ)空間。 下面討論線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即鏈表。是第二章的重點(diǎn)。2.3.1單鏈表 將線性表L=(a0,a1,……,an-1)中各元素分布在存儲(chǔ)器的不同存儲(chǔ)塊，稱為節(jié)點(diǎn)，通過地址或指針建立它們之間的聯(lián)系，所得到的存儲(chǔ)結(jié)構(gòu)為鏈表結(jié)構(gòu)。表中元素ai的節(jié)點(diǎn)形式如圖2.4所示。

圖2.4

其中，data域存放數(shù)據(jù)元素ai，而next域是一個(gè)指針，指向ai的直接后繼ai+1所在的節(jié)點(diǎn)。于是，線性表L=(a0,a1,……,an-1)的結(jié)構(gòu)如圖2.5所示:52

data

next

a0

a1

an-1^

L ..….單鏈表例2-4

設(shè)線性表L=(趙，錢，孫，李，周，吳，鄭，王)，各元素在存儲(chǔ)器中的分布如圖2.6所示。

53地址dataNext100李142106錢112112孫100118王NULL124吳136130趙106136鄭118142周124

圖2.6帶頭節(jié)點(diǎn)的單鏈表：

a0

an-1^

H…L趙錢孫吳鄭王^周李單鏈表

節(jié)點(diǎn)描述：typedefstructnode//節(jié)點(diǎn)類型

{datatypedata;//節(jié)點(diǎn)的數(shù)據(jù)域

structnode *next;//節(jié)點(diǎn)的后繼指針域

}linknode,*link;

若說明linknodeA;linkp;則結(jié)構(gòu)變量A為所描述的節(jié)點(diǎn)，而指針變量p為指向此類型節(jié)點(diǎn)的指針（或p的值為節(jié)點(diǎn)的地址），如圖2.8所示:

設(shè)p指向鏈表中節(jié)點(diǎn)ai，如圖2.9所示:

獲取ai，寫作：p->data；而取ai+1,寫作：p->next->data。另外，若指針p的值為NULL，則它不指向任何節(jié)點(diǎn),此時(shí)取p->data或p->next是錯(cuò)誤的。54

data

next

PA：

aiai+1P2.3.2單鏈表的基本操作

可調(diào)用C中malloc()函數(shù)向編譯系統(tǒng)申請(qǐng)節(jié)點(diǎn)的存儲(chǔ)空間，若說明：

linkp;p=(link)malloc(sizeof(linknode));則獲得了一個(gè)類型為linknode的節(jié)點(diǎn)，且該節(jié)點(diǎn)的地址已存入指針變量P中：1．建立單鏈表算法思路：依次讀入L=(a0,.....,an-1)中每一ai(設(shè)為整型)，若ai≠結(jié)束符(-1)，則將ai形成一節(jié)點(diǎn)，鏈入表尾，最后返回鏈表的頭節(jié)點(diǎn)指針H。算法描述：linkCreatelist() {datatypea;linkH,p,r; H=r=(link)malloc(sizeof(linknode)); scanf(“%d”,&a);//輸入數(shù)據(jù)元素

while(a!=-1) {p=(link)malloc(sizeof(linknode));//申請(qǐng)新節(jié)點(diǎn)

p->data=a;r->next=p;r=p;//存入數(shù)據(jù),將新節(jié)點(diǎn)鏈入表尾

scanf(“%d”,&a);} r->next=NULL;return(H);}//表尾的后繼置空55

data

next

P

建立單鏈表設(shè)L=(2，4，8，-1)，則建表過程如下： 設(shè)表長(zhǎng)為n，顯然此算法的時(shí)間復(fù)雜度為T(n)=O(n)。從此算法可以看到，鏈表的結(jié)構(gòu)是動(dòng)態(tài)形成的，即算法運(yùn)行前，表結(jié)構(gòu)是不存在的，而通過算法的運(yùn)行，得到一個(gè)如圖所示的單鏈表。2．鏈表查找（1）按序號(hào)查找：即實(shí)現(xiàn)GetElem(L,i)。算法思路：從鏈表的a0起，判斷是否為第i節(jié)點(diǎn)，若是則返回該節(jié)點(diǎn)的指針，否則查找下一節(jié)點(diǎn),依次類推。算法描述：LinkGetElem(linkH,inti){intj=-1;linkp=H;if(i<0)return(NULL);while(p->next&&j<i){p=p->next;j++;}if(i==j)return(p);elsereturn(NULL);}//查找失敗,即i>表長(zhǎng)

}56H248^單鏈表運(yùn)算（2）按值查找（定位）：即實(shí)現(xiàn)LocateElem(L,e)。算法思路：從節(jié)點(diǎn)a0起，依次判斷某節(jié)點(diǎn)是否等于e,若是,返回該節(jié)點(diǎn)的地址，否則查找下一節(jié)點(diǎn)a1,依次類推。若表中不存在e,則返回NULL。算法描述：linkLocateElem(linkH,datatypee){linkp=H->next;while(p&&p->data!=e)p=p->next;return(p);//若p->data=x則返回指針p;否則p必為空，返回NULL}此算法的時(shí)間復(fù)雜度T(n)也為O(n)。3．前插即實(shí)現(xiàn)ListInsert(L,i,e)。討論將x插入表中節(jié)點(diǎn)ai之前的情況。算法思路：調(diào)用算法GetElem(H,i-1)，獲取節(jié)點(diǎn)ai-1的指針p(ai

之前驅(qū))，然后申請(qǐng)一個(gè)q節(jié)點(diǎn)，存入e，并將其插入p節(jié)點(diǎn)之后。插入時(shí)的指針變化如圖2.14所示。57單鏈表插入

圖2.14算法描述：voidListLinsert(linkH,inti,datatypee){linkp,q;

if(i==0)p=H;elsep=GetElem(H,i-1);//取節(jié)點(diǎn)ai-1的指針

if(p==NULL)ERROR(i);//參數(shù)i出錯(cuò)

else{q=(link)malloc(sizeof(linknode))；//申請(qǐng)插入節(jié)點(diǎn)

q->data=e;//存入數(shù)據(jù)

q->next=p->next;//插入新節(jié)點(diǎn)

p->next=q;}}

此算法的時(shí)間主要花費(fèi)在函數(shù)Getlist(H,i-1)上，故T(n)=O(n)，但插入時(shí)未引起元素的移動(dòng)，這一點(diǎn)優(yōu)于順序結(jié)構(gòu)的插入。58Ha0ai^anai-1Peq單鏈表刪除4．刪除即實(shí)現(xiàn)ListDel(L,i)。

圖2.15

算法思路：同插入法，先調(diào)用函數(shù)GetElem(H,i-1),找到節(jié)點(diǎn)ai的前驅(qū)，然后如圖2.15所示，將節(jié)點(diǎn)ai刪除之。算法描述：VoidLdelete(linkH,inti) {linkp,q;if(i==0)p=H;elsep=GetElem(H,i-1);//求ai-1的地址

if(p&&p->next)//若p及p->next所在的節(jié)點(diǎn)存在

{q=p->next;p->next=q->next;free(q);}//刪除

elseERROR(i);//參數(shù)i出錯(cuò)

}同插入法，此算法的T(n)=O(n)。59Ha0ai

ai-1Pai+1q例2-5將單鏈表倒置算法思路：依次取原鏈表中節(jié)點(diǎn)，將其作為新鏈表首節(jié)點(diǎn)插入H節(jié)點(diǎn)之后。

圖.16算法描述：voidL1n-Ln1(linkH) {linkp,q;p=H->next;//令指針p指向節(jié)點(diǎn)a0 H->next=NULL;//將原鏈表置空

while(p){q=p;p=p->next; q->next=H->next;//將節(jié)點(diǎn)ai插入到頭節(jié)點(diǎn)之后

H->next=q;}}60H248^H^2H42^H842^例2-6

設(shè)節(jié)點(diǎn)data域?yàn)檎停箧湵碇邢噜弮晒?jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針。如圖2.17所示的鏈表，它應(yīng)返回值為4的節(jié)點(diǎn)所在的指針。算法思路：設(shè)p,q分別為鏈表中相鄰兩節(jié)點(diǎn)指針，求p->data+q->data為最大的那一組值，返回其相應(yīng)的指針p即可。(本例應(yīng)返回“4”的地址)算法描述：linkAdjmax(linkH) {linkp,p1,q;intm0,m1;p=H->next; p1=p;if(p1==NULL)return(p1);//表空返回

q=p->next;if(q==NULL)return(p1);//表長(zhǎng)=1時(shí)的返回

m0=p->data+q->data;//相鄰兩節(jié)點(diǎn)data值之和

while(q->next) {p=q;q=q->next;//取下一對(duì)相鄰節(jié)點(diǎn)的指針

m1=p->data+q->data; if(m1>m0){p1=p;m0=m1;}}//取和為最大的第一節(jié)點(diǎn)指針

return(p1);}61H26473^《數(shù)據(jù)結(jié)構(gòu)》上機(jī)題（C語言程序）1．輸入數(shù)據(jù)（設(shè)為整型）建立單鏈表，并求相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)。例如輸入：264730（0為結(jié)束符），建立：

所求結(jié)果=4

程序結(jié)構(gòu)：類型說明； 建表函數(shù)：Creatlist(L);求值函數(shù)：Adjmax(L); main(){變量說明； 調(diào)用Creatlist(L)建表；調(diào)用Adjmax(L)求值； 打印數(shù)據(jù)；釋放鏈表空間；

Y繼續(xù)？

N

停止

}

62《數(shù)據(jù)結(jié)構(gòu)》上機(jī)題1H26473^例2-7

設(shè)兩單鏈表A、B按data值（設(shè)為整型）遞增有序，設(shè)計(jì)算法，將表A和B合并成一表A，且表A也按data值遞增有序。如圖2.18：算法思路：設(shè)指針p、q分別指向表A和B中的節(jié)點(diǎn)，若p->data≤q->data則p節(jié)點(diǎn)進(jìn)入結(jié)果表，否則q節(jié)點(diǎn)進(jìn)入結(jié)果表。算法描述：voidMerge(linkA,linkB){linkr,p,q;p=A->next;q=B->next;free(B);r=A;while(p&&q) {if(p->data<=q->data){r->next=p;r=p;p=p->next;}else{r->next=q;r=q;q=q->next;}}if(p==NULL)p=q;r->next=p;}//收尾處理63A12A135^B2^4345^2.3.3單向循環(huán)鏈表

單向循環(huán)鏈表是單鏈表的一種改進(jìn)，若將單鏈表的首尾節(jié)點(diǎn)相連，便構(gòu)成單向循環(huán)鏈表結(jié)構(gòu)，如圖2.20所示:

若操作頻繁在尾部進(jìn)行，可設(shè)表尾指針R(省去H)。這樣,為獲得表尾an-1，取R->data即