數(shù)據(jù)結(jié)構(gòu) 基本概念

數(shù)據(jù)結(jié)構(gòu)基本概念第一頁，共四十頁，編輯于2023年，星期三第一章基本概念什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的抽象層次算法定義性能分析與度量第二頁，共四十頁，編輯于2023年，星期三“學生”表格初等項：如學生性別、籍貫等，不能再分割的最小數(shù)據(jù)單位。組合項：如一組成績，可以再劃分為物理成績、化學成績等更小的項。第三頁，共四十頁，編輯于2023年，星期三

選課關(guān)系包含如下信息

學號課程編號成績

學生選課系統(tǒng)中實體構(gòu)成的網(wǎng)狀關(guān)系第四頁，共四十頁，編輯于2023年，星期三UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖在應用程序中涉及到各種各樣的數(shù)據(jù)，為了存儲它們，組織它們，需要討論它們的歸類及它們之間的關(guān)系，從而建立相應的數(shù)據(jù)結(jié)構(gòu)，并依此實現(xiàn)要求的軟件功能。第五頁，共四十頁，編輯于2023年，星期三數(shù)據(jù)：信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。數(shù)值性數(shù)據(jù)如整數(shù)、實數(shù)、雙精度數(shù)等主要用于工程和科學計算，及商業(yè)事務處理中使用。非數(shù)值性數(shù)據(jù)如字符串、多媒體信息（文字、圖形、語音）等。數(shù)據(jù)對象：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。整數(shù)數(shù)據(jù)對象N={0,1,2,…}英文字母數(shù)據(jù)對象LETTER={‘A’,‘B’,…,‘Z’}學生數(shù)據(jù)對象第六頁，共四十頁，編輯于2023年，星期三什么是數(shù)據(jù)結(jié)構(gòu)？定義:一組數(shù)據(jù)對象及數(shù)據(jù)對象之間的關(guān)系組成。記為：

Data_Structure={D,R}其中，D是數(shù)據(jù)對象的有限集合，R是該集合中所有數(shù)據(jù)對象之間的關(guān)系的有限集合。

n個網(wǎng)站之間的連通關(guān)系以最小代價將n個網(wǎng)站連通樹形關(guān)系任一網(wǎng)站出現(xiàn)故障而整個網(wǎng)絡暢通網(wǎng)狀關(guān)系第七頁，共四十頁，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)的分類

根據(jù)數(shù)據(jù)對象之間的關(guān)系不同，分為兩大類：線性結(jié)構(gòu)非線性結(jié)構(gòu)線性結(jié)構(gòu)中各個數(shù)據(jù)對象依次排列在一個線性序列中；非線性結(jié)構(gòu)中各個數(shù)據(jù)對象不再保持在一個線性序列中，每個數(shù)據(jù)對象可能與零個或多個其它數(shù)據(jù)對象有某種特定的聯(lián)系。第八頁，共四十頁，編輯于2023年，星期三根據(jù)考慮問題的角度不同，分為兩大類：邏輯結(jié)構(gòu)物理結(jié)構(gòu)邏輯結(jié)構(gòu)是指從解決問題出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)結(jié)構(gòu)，屬于用戶視圖，面向問題，根據(jù)問題所要實現(xiàn)的功能建立；物理結(jié)構(gòu)是指數(shù)據(jù)應該如何在計算機中存放，是數(shù)據(jù)邏輯結(jié)構(gòu)的存儲方式，是屬于具體實現(xiàn)的視圖，面向計算機，根據(jù)問題所要求的響應速度、處理時間、修改時間、存儲空間和單位時間的處理量等建立。 第九頁，共四十頁，編輯于2023年，星期三抽象數(shù)據(jù)類型數(shù)據(jù)類型

定義：一組性質(zhì)相同的值的集合,以及定義于這個值集合上的一組操作的總稱.由用戶定義，用以表示應用問題的數(shù)據(jù)模型，由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務（或稱操作）特征是使用與實現(xiàn)相分離，實行信息隱蔽和數(shù)據(jù)封裝。在抽象數(shù)據(jù)類型設(shè)計時，把類型的聲明與其實現(xiàn)分離開來。第十頁，共四十頁，編輯于2023年，星期三抽象數(shù)據(jù)類型第十一頁，共四十頁，編輯于2023年，星期三嚴格區(qū)分抽象數(shù)據(jù)類型的兩個不同視圖從使用者角度只要了解該抽象數(shù)據(jù)類型的規(guī)格說明，就可以利用其公共界面中的服務來使用這個類型，而不必關(guān)心其物理實現(xiàn)，這樣使用者可以在開發(fā)過程中抓住重點，集中精力考慮如何解決應用問題，使問題得到簡化。從實現(xiàn)者角度把抽象數(shù)據(jù)類型的物理實現(xiàn)封裝起來，有利于編碼、測試以及將來修改。因為這樣做可以使錯誤局部化，一旦出現(xiàn)錯誤，其傳播范圍不至于影響其它模塊。如果為了提高效率希望改進數(shù)據(jù)結(jié)構(gòu)，可能需要改變抽象數(shù)據(jù)類型的物理實現(xiàn)，但只要界面中的服務的使用方式不變，其它所有使用該數(shù)據(jù)類型的程序都可以不變，從而大大提高系統(tǒng)穩(wěn)定性。第十二頁，共四十頁，編輯于2023年，星期三

數(shù)據(jù)結(jié)構(gòu)的抽象層次最高的數(shù)據(jù)抽象是一個聚集類，其作用是把所有的數(shù)據(jù)抽象關(guān)聯(lián)在一起，代表數(shù)據(jù)結(jié)構(gòu)，并給出數(shù)據(jù)結(jié)構(gòu)都具有的操作——初始化(initial)、插入(insert)、刪除(delete)和查找(search)。第十三頁，共四十頁，編輯于2023年，星期三線性聚類——線性表類中所有數(shù)據(jù)成員都按某種次序排列在一個序列中。根據(jù)對聚集中元素存取方法的不同：直接存取類數(shù)組、記錄、文件直接存取某一指定項而不須先訪問其前驅(qū)。順序存取類棧、隊列、表只能從序列中第一個元素起，按序逐個訪問到指定的元素。廣義索引類散列表、詞典“關(guān)鍵碼——值”偶對的集合。第十四頁，共四十頁，編輯于2023年，星期三非線性聚類所有數(shù)據(jù)元素與其它數(shù)據(jù)元素之間不存在簡單的線性關(guān)系。根據(jù)關(guān)系的不同：層次聚集類樹，二叉樹，堆按層次劃分的數(shù)據(jù)元素的集合，指定層次上元素可以有零個或多個處于下一層次上的直接后繼。群聚集類集合，圖所有元素之間沒有任何順序關(guān)系。第十五頁，共四十頁，編輯于2023年，星期三線性聚集類中各數(shù)據(jù)成員之間的線性關(guān)系樹形結(jié)構(gòu)樹二叉樹二叉搜索樹第十六頁，共四十頁，編輯于2023年，星期三堆結(jié)構(gòu)“最大”堆“最小”堆第十七頁，共四十頁，編輯于2023年，星期三群聚類圖結(jié)構(gòu)網(wǎng)絡結(jié)構(gòu)第十八頁，共四十頁，編輯于2023年，星期三算法定義定義：一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列。特性：輸入

必須有0個或多個輸入，是算法開始運算前給于算法的量。輸出應有一個或多個輸出(處理結(jié)果)，輸出的量是算法計算的結(jié)果。確定性每步定義都是確切、無歧義的，對于每一種情況，需要執(zhí)行的動作都應嚴格地、清晰地規(guī)定。有窮性算法應在執(zhí)行有窮步后結(jié)束。有效性每一條運算應足夠基本，原則上能夠精確執(zhí)行，甚至人們僅用筆和紙做有限次運算就能完成。第十九頁，共四十頁，編輯于2023年，星期三事例學習：選擇排序問題明確問題：非遞減排序解決方案：逐個選擇最小數(shù)據(jù)算法框架：

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

從a[i]檢查到a[n-1];

若最小的整數(shù)在a[k],交換a[i]與a[k];

}細化程序：程序SelectSort

如何選擇值最小的數(shù)據(jù)；如何交換兩個數(shù)據(jù)的值。算法設(shè)計

自頂向下，逐步求精

第二十頁，共四十頁，編輯于2023年，星期三

voidselectSort(

inta[],constintn){

//對n個整數(shù)a[0],a[1],…,a[n-1],

按非遞減順序排序

for(

inti=0;i<n-1;i++){

int

k=i;

//從a[i]檢查到a[n-1],找最小的整數(shù),在a[k]

for(

intj=i+1;j<n;j++)

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

//k指示當前找到的最小整數(shù)

int

temp=a[i];a[i]=a[k];a[k]=temp;

//交換a[i]與a[k]}}

第二十一頁，共四十頁，編輯于2023年，星期三算法的性能分析與度量算法的性能標準算法的空間復雜性算法的時間復雜性第二十二頁，共四十頁，編輯于2023年，星期三算法的性能標準數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣與算法直接有關(guān)，其性能由實現(xiàn)其各個服務的算法來體現(xiàn)。對數(shù)據(jù)結(jié)構(gòu)的分析實質(zhì)上是對實現(xiàn)其各個服務的算法的性能的分析。判斷一個算法的優(yōu)劣的標準：正確性——最重要標準要求算法能夠正確地執(zhí)行預先規(guī)定的功能和性能要求。要求算法的編寫者對問題要求有正確的理解；正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)對算法的要求。第二十三頁，共四十頁，編輯于2023年，星期三可使用性——用戶友好性要求算法能夠很方便地使用。為了便于用戶使用，要求算法具有良好的界面，完備的用戶文檔。算法設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求；最好所有的輸入和輸出數(shù)據(jù)都通過參數(shù)表顯示地傳遞，少用公共變量；每一個算法只完成一個功能。第二十四頁，共四十頁，編輯于2023年，星期三可讀性算法應當可讀，是理解、測試和修改算法的需要。為了達到這一要求，算法邏輯必須清晰、簡單和結(jié)構(gòu)化：所有的變量名、函數(shù)名的命名必須有實際含義，讓人見名知義；在算法中必須加入注釋，簡要說明：算法的功能；輸入與輸出參數(shù)的使用規(guī)則；重要數(shù)據(jù)的作用；算法中各程序段完成的功能等。第二十五頁，共四十頁，編輯于2023年，星期三效率算法執(zhí)行時計算機資源的消耗，包括存儲（空間代價）和運行時間（時間代價）的開銷。與多種因素有關(guān)：計算機系統(tǒng)、可用存儲容量和算法復雜性。健壯性——容錯性或例外處理要求在算法中加入對輸入?yún)?shù)、打開文件、讀文件記錄、子程序調(diào)用狀態(tài)進行自動檢錯、報錯并通過與用戶對話來糾錯的功能。一個算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行檢查。在算法初寫時可暫不管，待算法成熟時再追加。第二十六頁，共四十頁，編輯于2023年，星期三算法的運行時間依賴于所使用的計算機系統(tǒng)、編譯器、可用存儲空間大小等。同樣的算法在速度不同的計算機上，執(zhí)行速度相差非常大。算法用不同的編譯器編譯出的目標代碼不一樣長，完成同樣功能所需時間不同。如果可用存儲空間不夠，算法需要的運行時間很多；如果空間足夠大，則時間明顯減少。通過比較算法的復雜性來評價。算法復雜性與具體運行環(huán)境和編譯器無關(guān)。第二十七頁，共四十頁，編輯于2023年，星期三空間復雜性(SpaceComplexity)當問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所占的存儲空間也以某種單位由1增加到f(n)。問題的規(guī)?？梢詮膯栴}的描述中找到。因為算法針對某一實例（類的對象），問題規(guī)模可視為實例的特性。在有n個記錄的學生文件中查找某個學生，或者對一個n階線性方程求解，n即為問題的規(guī)模。空間單位一般規(guī)定為一個工作單元所占的存儲空間的大小。第二十八頁，共四十頁，編輯于2023年，星期三空間復雜性度量存儲空間的固定部分

主要包括程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成分等)變量所占的空間等，屬靜態(tài)空間，只要做簡單的統(tǒng)計就可估算?？勺儾糠?/p>

主要包括尺寸與實例特性有關(guān)的成分變量所占空間、引用變量所占空間、以及遞歸棧所用的空間，還有在算法運行過程中通過動態(tài)分配和動態(tài)刪除動態(tài)使用的內(nèi)存空間。第二十九頁，共四十頁，編輯于2023年，星期三時間復雜性和度量編譯時間與編譯程序有關(guān)，與實例特性無關(guān)。運行時間從程序結(jié)構(gòu)著手，統(tǒng)計算法的程序步數(shù)。語法上或語義上有意義的一段指令序列執(zhí)行時間與實例特性無關(guān)程序步數(shù)舉例：

注釋：0聲明語句：0

表達式：1賦值語句：>0第三十頁，共四十頁，編輯于2023年，星期三例以迭代方式求累加和的函數(shù)行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

for(

inti=0;i<n;i++)

4

s+=a[i];

5

returns;

6

}

程序步確定方法

在程序中插入計數(shù)全局變量count；

建表，列出程序內(nèi)各個語句的程序步數(shù)。第三十一頁，共四十頁，編輯于2023年，星期三

在求累加和程序中加入count語句

float

sum(

floata[],

constint

n) {floats=0.0;count++;

//count是全局變量，統(tǒng)計執(zhí)行語句條數(shù)

for(

inti=0;i<n;i++)

{

count++; //針對for語句

s+=a[i]; count++;

}

//針對賦值語句

count++; //針對for的最后一次

count++; //針對return語句

returns;}

執(zhí)行結(jié)束得程序步數(shù)count=2*

n+3第三十二頁，共四十頁，編輯于2023年，星期三程序的簡化形式

void

sum(

float

a[],

constint

n){for

(

inti=0;i<n;i++)count+=2;count+=3;}

第三十三頁，共四十頁，編輯于2023年，星期三注意：

一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。

例如：賦值語句

x=sum(R,n);

本身的程序步數(shù)為1；

一次執(zhí)行對函數(shù)sum(R,n)

的調(diào)用需要的程序步數(shù)為2*n+3；

一次執(zhí)行的程序步數(shù)為

1+2*n+3=2*n+4第三十四頁，共四十頁，編輯于2023年，星期三時間復雜性的漸進表示法全面分析一個算法，需要考慮在最壞、最好、平均情況下的時間代價。大O表示法——最壞情況當且僅當存在正整數(shù)c和n0，使得T(n)≤cf(n)對所有的n≥n0成立，則稱該算法的漸進時間復雜度為T(n)=O(f(n))。當實例特性n充分大時，算法的時間復雜度隨n變化，在最壞情況下若存在一個增長的上界，即cf(n)，則該算法的時間復雜度增長的數(shù)量級為f(n)，即稱該算法的漸進時間復雜度為T(n)=O(f(n))。第三十五頁，共四十頁，編輯于2023年，星期三大O表示法的使用需要考慮關(guān)鍵操作的程序步數(shù)；關(guān)鍵操作大多在循環(huán)和遞歸中；在大多數(shù)場合中，程序步驟與執(zhí)行頻度一一對應。如果給出的是漸進值，可直接考慮關(guān)鍵操作的執(zhí)行頻度，提出其與實例特性n的函數(shù)關(guān)系g(n)，從而得到漸進時間復雜度。漸進時間復雜度的計算單個循環(huán)在循環(huán)內(nèi)的簡單語句即為關(guān)鍵操作，該程序段的漸進時間復雜度應是此關(guān)鍵操作的執(zhí)行頻度的大O表示。第三十六頁，共四十頁，編輯于2023年，星期三幾個并列的循環(huán)先分析每個循環(huán)的漸進時間復雜度，然后利用大O表示法的加法規(guī)則來計算漸進時間復雜度。大O表示法的加法規(guī)則當兩個并列的程序段的時間代價分別為T1(n)=O(f(n))和T2(m)=O(g(m))時，則將兩個程序段連在一起后整個程序段的時間代價為：

T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))

所謂(max(f(n),g(m))，是指當n與m充分大時f(n)與g(m)中的大值，具有如下關(guān)系：

c<log2n<n<nlog2n<n2<n3<2n<3n<n!取c、log2n、n、nlog2n時間效率比較高；取n2、n3時間效率差強人意；取2n、3n、n!當n稍微大一點，算法的時間代價變?yōu)楹艽螅灾劣诓荒苡嬎?。第三十七頁，共四十頁，編輯?023年，星期三兩個并列循環(huán)的例子

void

example(floatx[][],intm,int

n,intk){float

sum[];for(inti=0;

i<m;i++){//x[][]中各行

sum[i]=0.0;//數(shù)據(jù)累加

for(intj=0;j<n;

j++)

sum[i]+=x[i][j];//關(guān)鍵操作1，漸進時間復雜度為O(m*n)。

}

for(i=0;i<m;i++)//打印各行數(shù)據(jù)和

printf(

"

Line%d:%d\n“,i,sum[i]);//關(guān)鍵操作2，漸進時間復雜度為O(m)。

}//根據(jù)大o表示法的加法規(guī)則，漸進時間復雜度為O(max(m*n,m))第三十八頁，共四十頁，編輯于2023年，星期三多層的嵌套循環(huán)關(guān)鍵操作應該在最內(nèi)層循環(huán)中，先自外向內(nèi)層層分析每層循環(huán)的時間漸進復雜度，然后利用大O表示法的乘法規(guī)則來計算漸進時間復雜度。大O表示法的乘法規(guī)則當兩個嵌套的程序段的時間代價分別為T1(n)=O(f(n))和T2(m)=O(g(m))時，整個程序的時間代價為

T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))如果一個程序的循環(huán)中有一個包含有循環(huán)的函數(shù)調(diào)用