數(shù)據(jù)結(jié)構(gòu)第1課 緒論課件

第1課緒論數(shù)據(jù)結(jié)構(gòu)第1課緒論課程介紹《數(shù)據(jù)結(jié)構(gòu)》是計算機應(yīng)用及相關(guān)專業(yè)的重要專業(yè)基礎(chǔ)課，它不僅是《操作系統(tǒng)》、《數(shù)據(jù)庫》等課程的基礎(chǔ)，也是我們編寫計算機程序的重要基礎(chǔ)，是學(xué)習(xí)計算機軟件設(shè)計必不可少的基本知識?！稊?shù)據(jù)結(jié)構(gòu)》的產(chǎn)生背景：

計算機的應(yīng)用：科學(xué)計算數(shù)據(jù)處理

處理對象：數(shù)值字符、表格、圖像等多種類型數(shù)據(jù)

要編寫出好程序，必須分析數(shù)據(jù)特性及數(shù)據(jù)間的關(guān)系。

瑞士科學(xué)家N.Wirth提出：程序＝算法＋數(shù)據(jù)結(jié)構(gòu)本課程討論常見的各種數(shù)據(jù)結(jié)構(gòu)，以及其上的算法實現(xiàn)，并用C語言實現(xiàn)。第1課緒論第一課緒論本課介紹數(shù)據(jù)結(jié)構(gòu)的一些基礎(chǔ)知識，學(xué)習(xí)完本課內(nèi)容后，要求：了解數(shù)據(jù)結(jié)構(gòu)的一些基本概念知道基本的數(shù)據(jù)結(jié)構(gòu)類型理解什么是算法，如何評價算法掌握分析算法的時間復(fù)雜度第1課緒論什么是數(shù)據(jù)結(jié)構(gòu)例1：學(xué)生成績表（線性結(jié)構(gòu)）學(xué)號姓名性別課名成績…………………………97011李軍男英語6597012趙紅女英語7897013張山男英語90…………………………第1課緒論什么是數(shù)據(jù)結(jié)構(gòu)(續(xù))例2：人機對奕（樹形結(jié)構(gòu)）第1課緒論什么是數(shù)據(jù)結(jié)構(gòu)(續(xù))城市交通網(wǎng)絡(luò)（圖狀結(jié)構(gòu)）第1課緒論基本概念數(shù)據(jù)：輸入到計算機中，并被計算機程序處理的符號數(shù)據(jù)元素：在不同數(shù)據(jù)結(jié)構(gòu)中，又稱為元素、頂點或記錄。數(shù)據(jù)項：可能稱為字段或域。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。包括四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖狀結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩種形式。集合樹圖線性第1課緒論基本概念(續(xù))算法：是對特定問題求解步驟的一種描述。是一個有窮的規(guī)則序列。算法滿足以下性質(zhì)：

有窮性：一個算法必須總是在有執(zhí)行有窮步之后結(jié)束，且每一步都可以有窮時間內(nèi)完成。

確定性：每一條指令含義正確，沒有二義性。

可行性：算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。

輸入：有零個或多個輸入

輸出：有一個或多個輸出第1課緒論算法描述與評價算法可以使用框圖、類高級語言或自然語言來描述。教材中使用類C語言描述。在課程實驗中，需要同學(xué)們用TurboC描述并實現(xiàn)。評價算法的一般原則：

正確性

可讀性

健壯性(魯棒性)

高效率與低存貯量需求(時間與空間)第1課緒論算法描述與評價(續(xù))最初，用所需要的計算時間來衡量一個算法的好壞，但不同的機器相互之間無法比較，故需要用獨立于具體計算機的客觀衡量標(biāo)準(zhǔn)?！獑栴}的規(guī)模，基本運算，算法的計算量函數(shù)。問題的規(guī)模：一個或多個整數(shù)，作為輸入數(shù)據(jù)量的測度：

a、數(shù)表的長度（數(shù)據(jù)項的個數(shù)）（問題：在一個數(shù)據(jù)表中尋找X）

b、矩陣的最大維數(shù)（階數(shù)）（問題：求兩個實矩陣相乘的結(jié)果）輸入規(guī)模通常用n來表示，也可有兩個以上的參數(shù)，如

c、圖中的頂點數(shù)和邊數(shù)（圖論中的問題）第1課緒論算法描述與評價(續(xù))

基本運算：解決給定問題時占支配地位的運算（一般一種，偶爾≥2種）：

a、在一個表中尋找數(shù)據(jù)元素x—x與表中的一個項進行比較;

b、兩個實矩陣的乘法—實數(shù)的乘法（及加法）C=AB則cij=∑aikbkj;c、將一個數(shù)表進行排序—表中的兩個數(shù)據(jù)項進行比較;

通常情況下，討論一個算法優(yōu)劣時，我們只討論基本運算的執(zhí)行次數(shù)—因為它是占支配地位的，而其它的運算可以忽略不計。第1課緒論算法描述與評價(續(xù))用輸入規(guī)模的某個函數(shù)來表示算法的基本運算量：這個表示基本運算量的函數(shù)稱為算法的時間復(fù)雜性（度），用T(n)(或T(n,m)等)來表示.如：

T(n)=5n，T(n)=3nlogn，T(n)=4n3，T(n)=2n，T(n,m)=2(n+m)等

漸近時間復(fù)雜性：當(dāng)輸入規(guī)模趨于極限情形時（相當(dāng)大）的時間復(fù)雜性，記作：T(n)=O(f(n))。如：T(n)=8n3+150n+32可記作：T(n)=O(n3)常用的時間復(fù)雜性存在以下順序：

O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)＜…＜O(2n)＜O(3n)＜…＜O(n!)第1課緒論算法分析舉例(1)例1.1temp=i;i=j;j=temp;T(n)=O(1)(2)例1.2sum=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++;T(n)=O(n2)第1課緒論算法分析舉例(續(xù))(3)例1.3：x=1;for(i=1;i<=n;i++)for(j=1;j<=i;j+