《數(shù)據(jù)結構》本科教學課件

《數(shù)據(jù)結構》本科第一章緒論2

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

（1）科學計算與分析

（2）計算機管理

（3）計算機實時控制

（4）計算機輔助設計/制造（CAD/CAM）及繪圖

（5）計算機通訊網(wǎng)絡

（6）辦公自動化

（7）人工智能

（8）機器仿真

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

隨著計算機應用的廣泛深入，計算機應用領域會越來越廣，計算機要處理的數(shù)據(jù)更加多樣化，而數(shù)據(jù)之間的關系和對數(shù)據(jù)處理的要求也更為復雜。這就要求我們在從事具體的計算機應用時，要用較科學的方式描述、存儲和處理數(shù)據(jù)，從而使計算機高效率地去完成預期的任務。

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

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

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

圖1.1“數(shù)據(jù)結構”所處的地位

代數(shù)系統(tǒng)數(shù)據(jù)表示法數(shù)據(jù)結構

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

機器組織

編碼理論

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

算子關系數(shù)學

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

存儲裝置硬件（計算機系統(tǒng)設計）軟件（計算機程序設計）

文件系統(tǒng)

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

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

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

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

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

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

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

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

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

英語

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

姓名性別

年齡-------172張立女30-------091田方男20------------------------------------------11例1-3大學系級行政機構12

大學系級行政機構，如圖1.2所示：

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

設田徑比賽項目有：A(跳高)、

B(跳遠)、C(標槍)、D(鉛球)、E(100m跑)、F(200m跑)。參賽選手的項目表如下：問如何安排比賽時間，才能使得：

(1)每個比賽項目都能順利進行（無沖突）；

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

姓名

項目1

項目2

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

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

FCEABDFCEABD

圖1.3即：紅色時間段(如8~10點)—A、C項目；淺藍—B、D項目；深藍—E項目；紫色—F項目。數(shù)據(jù)邏輯結構（續(xù)）15

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

（線性關系）（層次關系）（網(wǎng)狀關系） 圖1.42．數(shù)據(jù)的存儲結構（或物理結構）（PhysicalStructure）

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

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

鏈式結構是本課程的一個重點，因為元素之間的關系在計算機內部很大程度上是通過地址或指針來建立的。（3）索引存儲（IndexedStorage）：在存儲數(shù)據(jù)的同時，建立一個附加的索引表，即索引存儲結構=數(shù)據(jù)文件+索引表。17a1

a2…………an圖1.5

(存儲器)

a1

a2

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

姓名

電話

丁一62331234…………

王二62345678…………

張三63450987…………

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

姓氏

地址

丁

王

張…………

索引表數(shù)據(jù)的存儲結構（續(xù)）19

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

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

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

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

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

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

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

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

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

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

操作結果：<操作結果描述>

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

231.3學習數(shù)據(jù)結構的目的1.3.1數(shù)據(jù)結構的發(fā)展簡史及在計算機科學中的地位

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

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

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

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

mnr1042420(停止)

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

(1)

有窮性

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

(2)

確定性

——每個計算步驟無二義性；

(3)

可行性

——每個計算步驟能夠在有限的時間內完成；

(4)

輸入

——算法有一個或多個外部輸入；

(5)

輸出

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

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

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

}}28算法轉換成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ù)錯，存儲分配失敗等）導致算法無法繼續(xù)執(zhí)行下去時，約定調用函數(shù)ERROR()進行出錯處理。 討論了數(shù)據(jù)結構與算法的基本概念后，有必要提到瑞士科學家沃思（N.Wirth）的著名公式：數(shù)據(jù)結構+算法=程序 數(shù)據(jù)結構是研究從具體問題中抽象出來的數(shù)學模型如何在計算機存儲器中表示出來；而算法研究的是對數(shù)據(jù)處理的步驟。如果對問題的數(shù)據(jù)表示和數(shù)據(jù)處理都做出了具體的設計，就相當于完成了相應的程序。291.4.3算法的設計目標算法的設計應滿足以下五點： 正確性算法應當滿足具體問題的需求，一般包括對輸入、輸出、處理等的明確的無歧義性的描述。 可讀性可讀性有助于對算法的理解及幫助排除算法中隱藏的錯誤，也有助于算法的交流和移植。 健壯性當輸入不合法的數(shù)據(jù)時，算法應能做出相應的處理，而不產(chǎn)生不可預料的結果。 高效率算法的效率指算法執(zhí)行時間的長短，稱作算法的時間復雜度。 低存儲量需求算法的存儲量需求指算法執(zhí)行期間所需要的最大存儲空間，稱作算法的空間復雜度。

301.4.4算法效率的度量

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

1.語句的頻度(FrequencyCount)

語句頻度定義為可執(zhí)行語句在算法（或程序）中重復執(zhí)行的次數(shù)。若某語句執(zhí)行一次的時間為t，執(zhí)行次數(shù)為f，則該語句所耗時間的估計為t·f。31例1-7求兩個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.算法的時間復雜度(TimeComplexity)

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

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

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

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

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

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

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

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

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

O(2n)

O(n3)

O(n2)

O(n)

O(n*log2n)

O(log2n)

O(c)

n

算法分析

對較為復雜的算法，可分段分析其時間復雜度。如某算法可分為兩部分，其時間復雜度分別為：

T1(n)=O(f(n)),T2(n)=O(g(n))此時兩部分問題的體積一致，則總的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))。 另外，算法空間復雜度的定義： 設算法對應問題的體積（或規(guī)模）為n,執(zhí)行算法所占存儲空間的量級為D(n)，則D(n)為算法的空間復雜度(SpaceComplexity)。36第一章小結

37DS時間復雜度T(n)空間復雜度D(n)邏輯結構線性結構樹型結構網(wǎng)狀結構存儲結構鏈式存儲索引存儲順序存儲散列存儲查詢DS上的操作插入刪除更新算法算法定義、性質算法分析第一章作業(yè)1.試用DS=（D，R）形式說明字符串:S=“s1,s2,……,sn”(si∈char)是一個數(shù)據(jù)結構，即S=（D，R）中D=？R=？2.設五叉口：其中E、C道為單行線。試構造使該路口行駛車輛不碰撞的交通管理模型。（提示:找出路口各行車路線(AB,BC,….),若兩行車路線不能對駛,則將其連線。)3.設n為正整數(shù)，求下列算法段的時間復雜度，即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ù)元素之間滿足線性關系的表稱為線性表，是一種最基本、最簡單的數(shù)據(jù)結構類型。本章討論線性表的邏輯和存儲結構、相關算法的實現(xiàn)以及線性表應用舉例。2.1線性表的定義及基本操作2.1.1定義：線性表(LinearList)是若干數(shù)據(jù)元素的一個線性序列，記為：

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

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

時，L為非空表，否則為空表。2.1.2線性表的邏輯結構和特征

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

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

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

表長n=0時，L為空表；關系符<ai,ai+1>在這里稱為有序對，表示任意相鄰的兩個元素之間的一種先后次序關系，稱ai是ai+1的直接前驅,ai+1是ai的直接后繼，當表長n≤1時，關系集R為空集。39例2-1線性表的例子

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

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

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

學號

姓名性別

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

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

基本操作集：PListInit(&L)

操作結果：構造一個空的線性表L。ListDestroy(&L)

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

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

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

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

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

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

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

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

初始條件：線性表L存在，且e∈datatype。 操作結果：若0≤i≤n-1，將e插入到ai之前，若i=n，將e插到表尾，表長增加1，函數(shù)返回TURE；i為其他值時返回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存在。 操作結果：若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存在。操作結果：依次對表中的元素利用visit()函數(shù)進行訪問。}ADTList；43線性表的操作

以上運算是對線性表L施加的一些基本運算，對線性表L的運算還有：

合并、拆分、復制、排序等等。例2-2設線性表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等運算的算法。44

1357La

57911

Lb線性表的操作例2-3

設計清除線性表L=(a0,a1,---,ai,-------,an-1)中重復元素的算法。算法思路：對當前表L中的每個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))結果：L=（1，3，5，7）

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

線性表的順序存儲結構 線性表在計算機存儲器中的映象（或表示）一般有兩種形式，一種是順序映象，一種是鏈式映象。452.2.1順序表

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

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

… Loc(a1)=b+1*d

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

b+n*d:

圖2.2

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

…ai…an-1線性表順序存儲結構

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

typedefstruct//表的類型

{datatypedata[maxsize];//表的存儲空間

intlast;//當前表尾指針

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

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

圖2.3

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

…an-12.2.2基本運算的相關算法

關于線性表的運算，有些實現(xiàn)起來是相當簡單的，例如： 置空表：ListClear(L),令L->last=-1；取ai:GetElem(L,i),取L->data[i]； 求表長：ListLength(L),取L->last之值加1即可。 所以主要討論插入、刪除、定位等算法的實現(xiàn)。1.前插：將一給定值e插在元素ai之前，即實現(xiàn)ListInsert(L,i,e)。算法思路：若表存在空閑空間,且0≤i≤L->last+1,將(L->data[L->last]～L->data[i])順序下移一個數(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基本運算的相關算法算法分析：算法的主要時耗在數(shù)據(jù)元素的移動上，即算法中for語句上，故以插入一個元素的平均移動次數(shù)刻畫算法的T(n)(n為表長)。設e插入ai(0≤i≤n)處的概率pi均等，即pi=1/(n+1),而插入e時的元素移動次數(shù)Ci=n-i,則平均移動次數(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基本運算的相關算法2.刪除：將表中第i個元素ai從表中刪除，即實現(xiàn)ListDel(L,i)。算法思路：若參數(shù)i滿足：0≤i≤L->last,將表中L->data[i+1]∽L->data[L->last]部分順序向上移動一個元素位置，擠掉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);}}算法分析：設刪除ai(0≤i≤n-1)的概率pi均等,即pi=1/n,刪除ai的元素移動次數(shù)Ci=n-(i+1),則平均移動次數(shù)為：

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

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

intLocateElem(sqlinkL,datatypee) {inti=0; while(i<=L->last&&L->data[i]!=e) i++; if(i<=L->last)return(i);elsereturn(-1);}算法分析：算法時耗主要在while語句中元素e與ai的比較次數(shù)上，用平均比較次數(shù)來刻畫算法的T(n)。設元素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線性表的鏈式存儲結構

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

圖2.4

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

data

next

a0

a1

an-1^

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

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

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

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

a0

an-1^

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

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

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

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

}linknode,*link;

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

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

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

data

next

PA：

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

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

linkp;p=(link)malloc(sizeof(linknode));則獲得了一個類型為linknode的節(jié)點，且該節(jié)點的地址已存入指針變量P中：1．建立單鏈表算法思路：依次讀入L=(a0,.....,an-1)中每一ai(設為整型)，若ai≠結束符(-1)，則將ai形成一節(jié)點，鏈入表尾，最后返回鏈表的頭節(jié)點指針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));//申請新節(jié)點

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

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

data

next

P

建立單鏈表設L=(2，4，8，-1)，則建表過程如下： 設表長為n，顯然此算法的時間復雜度為T(n)=O(n)。從此算法可以看到，鏈表的結構是動態(tài)形成的，即算法運行前，表結構是不存在的，而通過算法的運行，得到一個如圖所示的單鏈表。2．鏈表查找（1）按序號查找：即實現(xiàn)GetElem(L,i)。算法思路：從鏈表的a0起，判斷是否為第i節(jié)點，若是則返回該節(jié)點的指針，否則查找下一節(jié)點,依次類推。算法描述：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>表長

}56H248^單鏈表運算（2）按值查找（定位）：即實現(xiàn)LocateElem(L,e)。算法思路：從節(jié)點a0起，依次判斷某節(jié)點是否等于e,若是,返回該節(jié)點的地址，否則查找下一節(jié)點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}此算法的時間復雜度T(n)也為O(n)。3．前插即實現(xiàn)ListInsert(L,i,e)。討論將x插入表中節(jié)點ai之前的情況。算法思路：調用算法GetElem(H,i-1)，獲取節(jié)點ai-1的指針p(ai

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

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

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

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

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

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

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

p->next=q;}}

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

圖2.15

算法思路：同插入法，先調用函數(shù)GetElem(H,i-1),找到節(jié)點ai的前驅，然后如圖2.15所示，將節(jié)點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é)點存在

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

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

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

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

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

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

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

設節(jié)點data域為整型，求鏈表中相鄰兩節(jié)點data值之和為最大的第一節(jié)點的指針。如圖2.17所示的鏈表，它應返回值為4的節(jié)點所在的指針。算法思路：設p,q分別為鏈表中相鄰兩節(jié)點指針，求p->data+q->data為最大的那一組值，返回其相應的指針p即可。(本例應返回“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);//表長=1時的返回

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

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

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

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

所求結果=4

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

Y繼續(xù)？

N

停止

}

62《數(shù)據(jù)結構》上機題1H26473^例2-7

設兩單鏈表A、B按data值（設為整型）遞增有序，設計算法，將表A和B合并成一表A，且表A也按data值遞增有序。如圖2.18：算法思路：設指針p、q分別指向表A和B中的節(jié)點，若p->data≤q->data則p節(jié)點進入結果表，否則q節(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)鏈表是單鏈表的一種改進，若將單鏈表的首尾節(jié)點相連，便構成單向循環(huán)鏈表結構，如圖2.20所示:

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