數(shù)據(jù)結(jié)構(gòu)在計算機中的標識課件

1課程介紹教材：

《數(shù)據(jù)結(jié)構(gòu)》（C語言版）

嚴蔚敏、吳偉民編清華大學出版社

學時：48學時上機：48學時

學習方法：多思考、多練習課外2課程性質(zhì)及學習方法課程性質(zhì)：專業(yè)基礎(chǔ)課核心課程學習方法多思考、多練習多寫程序多讀程序多上機少背書3第一章緒論1.1數(shù)據(jù)結(jié)構(gòu)的概念1.2抽象數(shù)據(jù)類型1.3算法和算法分析

1.3.1算法

1.3.2算法描述

1.3.3算法性能分析與度量4

第一章緒論計算機科學是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題：信息的表示信息的處理而信息的表示和處理又直接關(guān)系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應用程序的規(guī)模很大，結(jié)構(gòu)又相當復雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。51.1數(shù)據(jù)結(jié)構(gòu)的概念1.1.1

為什么要學習數(shù)據(jù)結(jié)構(gòu)

眾所周知，計算機的程序是對信息進行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個例子。例1、電話號碼查詢系統(tǒng)設(shè)有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分別表示某人的名字和對應的電話號碼要求設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠給出報告沒有這個人的標志。6

算法的設(shè)計，依賴于計算機如何存儲人的名字和對應的電話號碼，或者說依賴于名字和其電話號碼的結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題?？蓪⒚趾蛯碾娫捥柎a設(shè)計成：二維數(shù)組、表結(jié)構(gòu)、向量。假定名字和其電話號碼邏輯上已安排成N元向量的形式，它的每個元素是一個數(shù)對(ai，bi)，1≤i≤n

數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運算的算法。7除電話號碼自動查號系統(tǒng)外，還有許多諸如此類的問題，如：學生信息檢索系統(tǒng)

、考試查分系統(tǒng)、倉庫庫存管理系統(tǒng)等。在這類文檔管理的數(shù)學模型中，計算機處理的對象之間通常存在著的是一種簡單的線性關(guān)系，這類數(shù)學模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。

學生信息檢索系統(tǒng)：當我們需要查找某個學生的有關(guān)情況的時候；或者想查詢某個專業(yè)或年級的學生的有關(guān)情況的時候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實現(xiàn)計算機自動檢索。由此，可以在學生信息檢索系統(tǒng)中建立一張按學號順序排列的學生信息表和分別按姓名、專業(yè)、年級順序排列的索引表，如圖1.1所示。由這四張表構(gòu)成的文件便是學生信息檢索的數(shù)學模型，計算機的主要操作便是按照某個特定要求（如給定姓名）對學生信息文件進行查詢。8學生信息檢索系統(tǒng)：

學號

姓名性別專業(yè)年級980001吳承志

男計算機科學與技術(shù)

98級

980002李淑芳

女信息與計算科學

98級

990301劉

麗

女數(shù)學與應用數(shù)學

99級

990302張會友

男信息與計算科學99級

990303石寶國

男計算機科學與技術(shù)99級

000801何文穎

女計算機科學與技術(shù)2000級

000802趙勝利

男數(shù)學與應用數(shù)學

2000級

000803崔文靖

男信息與計算科學

2000級

010601劉

麗

女計算機科學與技術(shù)2001級

010602魏永鳴

男數(shù)學與應用數(shù)學2001級

（a）學生信息表

9崔文靖

8何文穎

6李淑芳

2劉

麗

3，9石寶國

5魏永鳴

10吳承志

1趙勝利

7張會有

4（b）姓名索引表

計算機科學與技術(shù)

1，5，6，9信息與計算科學

2，4，8數(shù)學與應用數(shù)學

3，7，102000級

6，7，82001級

9，1098級

1，2，399級

4，5

（c）專業(yè)索引表

（d）年級索引表

線形結(jié)構(gòu)10例2、八皇后問題。

在八皇后問題中，處理過程不是根據(jù)某種確定的計算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計算機中要存儲布局的當前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進行試探，每試探一步形成一個新的狀態(tài)，整個試探過程形成了一棵隱含的狀態(tài)樹。如圖1.2所示（為了描述方便，將八皇后問題簡化為四皇后問題）?；厮莘ㄇ蠼膺^程實質(zhì)上就是一個遍歷狀態(tài)樹的過程。在這個問題中所出現(xiàn)的樹也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應用在許多非數(shù)值計算的問題中。

11圖1.2四皇后問題中隱含的狀態(tài)樹

樹型結(jié)構(gòu)12例3教學計劃編排問題一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些必須按規(guī)定的先后次序進行，有些則沒有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個課程之間的次序關(guān)系可用一個稱作圖的數(shù)據(jù)結(jié)構(gòu)來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先于課程j進行。

13

（a）計算機專業(yè)的課程設(shè)置

14圖1.3教學計劃編排問題的數(shù)據(jù)結(jié)構(gòu)圖型結(jié)構(gòu)

（b）表示課程之間優(yōu)先關(guān)系的有向圖

15

由以上幾個例子可以直接地認為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應的運算，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的類型。

由以上幾個例子可見，描述這類非數(shù)值計算問題的數(shù)學模型不再是數(shù)學方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。學習數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。與此同時，通過算法訓練來提高思維能力，通過程序設(shè)計的技能訓練來促進綜合應用能力和素質(zhì)的提高。

161.1.2有關(guān)概念和術(shù)語

數(shù)據(jù)（Data）：是信息的載體，它能夠被計算機識別、存儲和加工處理。計算機科學中，所謂數(shù)據(jù)就是計算機加工處理的對象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。

數(shù)據(jù)元素（DataElement）：是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。

數(shù)據(jù)對象（DataObject）或數(shù)據(jù)元素類（DataElementClass）：是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對象（數(shù)據(jù)元素類），數(shù)據(jù)元素是數(shù)據(jù)元素類的一個實例。例、整數(shù)的數(shù)據(jù)對象是{…-3，-2，-1，0，1，2，3，…}數(shù)據(jù)結(jié)構(gòu)（DataStructure）：指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不會是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。

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

集合結(jié)構(gòu)

線形結(jié)構(gòu)樹狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)有兩個要素。一個是數(shù)據(jù)元素的集合，另一個是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通?？梢圆捎靡粋€二元組來表示。

18數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：Data_Structure＝（D，R）其中：D是數(shù)據(jù)元素的有限集

R是D上關(guān)系的有限集

19數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學模型，它與數(shù)據(jù)的存儲無關(guān)。我們研究數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機中實現(xiàn)對它的操作，為此還需要研究如何在計算機中表示一個數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)在計算機中的標識（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。

數(shù)據(jù)的存儲結(jié)構(gòu)可采用順序存儲方法:是用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。

鏈式存儲方法:在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針字段來表示，鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針類型來實現(xiàn)。

除了通常采用的順序存儲方法和鏈式存儲方法外，有時為了查找的方便還采用索引存儲方法和散列存儲方法。

201.1.3：數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容

方面層次數(shù)據(jù)表示數(shù)據(jù)處理抽象

邏輯結(jié)構(gòu)

基本運算實現(xiàn)

存儲結(jié)構(gòu)

算法評價

不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析211.2抽象數(shù)據(jù)類型

1.2.1數(shù)據(jù)類型:在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。

類型顯式地或隱含地規(guī)定了在程序執(zhí)行期間變量或表達式所有可能的取值范圍，以及在這些值上允許進行的操作。數(shù)據(jù)類型（DataType）是一個值的集合和定義在這個值集上的一組操作的總稱。例1、在FORTRAN語言中：變量的數(shù)據(jù)類型有整型、實型、和復數(shù)型例2、在C語言中，數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義221.2.2抽象數(shù)據(jù)類型

是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型一般可以由元素、關(guān)系及操作三種要素來定義。

抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。用三元組描述如下：（Ｄ，Ｓ，Ｐ）抽象數(shù)據(jù)類型的特征是使用與實現(xiàn)相分離，實行封裝和信息隱蔽。就是說，在抽象數(shù)據(jù)類型設(shè)計時，把類型的定義與其實現(xiàn)分離開來。

231.3算法和算法分析

1.3.1算法特性

算法（Algorithm）是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。算法的五個特征：有窮性。一個算法必須在有窮步之后結(jié)束，即必須在有限時間內(nèi)完成。確定性。算法的每一步必須有確切的定義，無二義性。算法的執(zhí)行對應著的相同的輸入僅有唯一的一條路經(jīng)。可行性（有效性）。算法中的每一步都可以通過已經(jīng)實現(xiàn)的基本運算的有限次執(zhí)行得以實現(xiàn)。輸入。一個算法具有零個或多個輸入，這些輸入取自特定的數(shù)據(jù)對象集合。輸出。一個算法具有一個或多個輸出，這些輸出是同輸入之間存在某種特定的關(guān)系的量。

24算法設(shè)計的要求

評價一個好的算法有以下幾個標準:

(1)

正確性(Correctness)

算法應滿足具體問題的需求，預先規(guī)定的功能和性能要求。

(2)

可讀性(Readability)

算法應該好讀。以有利于閱讀者對程序的理解。

(3)

健狀性(Robustness)

算法應具有容錯處理。當輸入非法數(shù)據(jù)時，算法應對其作出反應，而不是產(chǎn)年莫名其妙的輸出結(jié)果。

(4)效率與存儲量需求

效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。251.3.3算法性能分析與度量

可以從一個算法的時間復雜度與空間復雜度來評價算法的優(yōu)劣。

將一個算法轉(zhuǎn)換成程序并在計算機上執(zhí)行時，其運行所需要的時間取決于下列因素：硬件的速度

書寫程序的語言

編譯程序所生成目標代碼的質(zhì)量

問題的規(guī)模

26⒈時間復雜度

一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行時間取決于兩者的綜合效果。為了便于比較同一問題的不同的算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中原操作重復執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。

定義（大Ο記號）：如果存在兩個正常數(shù)c和n0，使得對所有的n，n≥n0，有：f(n)≤cg(n)則有：f(n)＝

Ο(g(n))指程序運行從開始到結(jié)束所需要的時間。

例:一個程序的實際執(zhí)行時間為T(n)＝2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。

使用大Ο記號表示的算法的時間復雜度，稱為算法的漸進時間復雜度（AsymptoticComplexity）。

27一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作：T(n)=O(f(n))例１、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];}由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為:n×n×n=n3時間復雜度為：T(n)=O(n3)頻度：是指語句重復執(zhí)行的次數(shù)28例２{++x;s=0;}分析：將x自增看成是基本操作，則語句頻度為１，即時間復雜度為Ｏ(1)；如果將s=0也看成是基本操作，則語句頻度為２，其時間復雜度仍為Ｏ(1)，即常量階。例３、for(I=1;I<=n;++I){++x;s+=x;}語句頻度為：2n其時間復雜度為：O(n)即時間復雜度為線性階例４、for(I=1;I<=n;++I)

for(j=1;j<=n;++j){++x;s+=x;}語句頻度為：2n2其時間復雜度為：O(n2)，即時間復雜度為平方階。29定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，則A(n)=O(nm)證略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}語句頻度為：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴時間復雜度為O(n2)即此算法的時間復雜度為平方階.一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為O(n2)的算法則由一個二次多項式來限界。30通常用Ο(1)表示常數(shù)計算時間。常見的漸進時間復雜度有:Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)這幾種計算算法時間的多項式是