數(shù)據(jù)結(jié)構(gòu)基本概念第1頁，課件共40頁，創(chuàng)作于2023年2月第一章基本概念什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的抽象層次算法定義性能分析與度量第2頁，課件共40頁，創(chuàng)作于2023年2月“學(xué)生”表格初等項(xiàng)：如學(xué)生性別、籍貫等，不能再分割的最小數(shù)據(jù)單位。組合項(xiàng)：如一組成績(jī)，可以再劃分為物理成績(jī)、化學(xué)成績(jī)等更小的項(xiàng)。第3頁，課件共40頁，創(chuàng)作于2023年2月

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

學(xué)號(hào)課程編號(hào)成績(jī)

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

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

n個(gè)網(wǎng)站之間的連通關(guān)系以最小代價(jià)將n個(gè)網(wǎng)站連通樹形關(guān)系任一網(wǎng)站出現(xiàn)故障而整個(gè)網(wǎng)絡(luò)暢通網(wǎng)狀關(guān)系第7頁，課件共40頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)的分類

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

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

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

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

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

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

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

}細(xì)化程序：程序SelectSort

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

自頂向下，逐步求精

第20頁，課件共40頁，創(chuàng)作于2023年2月

voidselectSort(

inta[],constintn){

//對(duì)n個(gè)整數(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指示當(dāng)前找到的最小整數(shù)

int

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

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

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

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

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

注釋：0聲明語句：0

表達(dá)式：1賦值語句：>0第30頁，課件共40頁，創(chuàng)作于2023年2月例以迭代方式求累加和的函數(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

}

程序步確定方法

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

建表，列出程序內(nèi)各個(gè)語句的程序步數(shù)。第31頁，課件共40頁，創(chuàng)作于2023年2月

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

float

sum(

floata[],

constint

n) {floats=0.0;count++;

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

for(

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

{

count++; //針對(duì)for語句

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

}

//針對(duì)賦值語句

count++; //針對(duì)for的最后一次

count++; //針對(duì)return語句

returns;}

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

n+3第32頁，課件共40頁，創(chuàng)作于2023年2月程序的簡(jiǎn)化形式

void

sum(

float

a[],

constint

n){for

(

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

第33頁，課件共40頁，創(chuàng)作于2023年2月注意：

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

例如：賦值語句

x=sum(R,n);

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

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

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

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

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

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

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

c<log2n<n<nlog2n<n2<n3<2n<3n<n!取c、log2n、n、nlog2n時(shí)間效率比較高；取n2、n3時(shí)間效率差強(qiáng)人意；取2n、3n、n!當(dāng)n稍微大一點(diǎn)，算法的時(shí)間代價(jià)變?yōu)楹艽?，以至于不能?jì)算。第37頁，課件共40頁，創(chuàng)作于2023年2月兩個(gè)并列循環(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，漸進(jìn)時(shí)間復(fù)雜度為O(m*n)。

}

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

printf(

"

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

}//根據(jù)大o表示法的加法規(guī)則，漸進(jìn)時(shí)間復(fù)雜度為O(max(m*n,m))第38頁，課件共40頁，創(chuàng)作于2023年2月多層的嵌套循環(huán)關(guān)鍵操作應(yīng)該在最內(nèi)層循環(huán)中，先自外向內(nèi)層層分析每層循環(huán)的時(shí)間漸進(jìn)復(fù)雜度，然后利用大O表示法的乘法規(guī)則來計(jì)算漸進(jìn)時(shí)間復(fù)雜度。大O表示法的乘法規(guī)則當(dāng)兩個(gè)嵌套的程序段的時(shí)間代價(jià)分別為T1(n)=O(f(n))和T2(m)=O(g(m))時(shí)，整個(gè)程序的時(shí)間代價(jià)為

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