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

數(shù)據(jù)結(jié)構(gòu)總學(xué)時：36（考試課）

教材：《數(shù)據(jù)結(jié)構(gòu)（C語言版）》嚴蔚敏、吳偉民編著

清華大學(xué)出版社

課程安排教學(xué)內(nèi)容第1章緒論第2章線性表第3章棧和隊列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序考查方式20%作業(yè)70%考試10%考勤第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型1.4算法和算法分析“數(shù)據(jù)結(jié)構(gòu)”學(xué)科形成和發(fā)展背景1946年第一臺計算機問世，計算機產(chǎn)業(yè)的飛速發(fā)展，深入到人類社會的各個領(lǐng)域。計算機的應(yīng)用已不再局限于科學(xué)計算，而更多地用于控制、管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作。計算機加工處理的對象由純粹的數(shù)值發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就給程序設(shè)計帶來一些新的問題。為了編寫一些“好”的程序，必須分析待處理對象的特性以及各處理對象間的關(guān)系。這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)值計算解決問題的一般步驟：數(shù)學(xué)模型→選擇計算機語言→編出程序→測試→最終解答。數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。非數(shù)值計算問題中，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述。8例1-1

書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表樹……..……..…...…...…...…...例1-2

井字棋例1-3多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖綜上三個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，簡單說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科。形成階段：60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學(xué)計算機科學(xué)系的教學(xué)計劃。發(fā)展階段：數(shù)據(jù)結(jié)構(gòu)的概念不斷擴充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。70年代后期，我國高校陸續(xù)開設(shè)該課程。數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展數(shù)據(jù)結(jié)構(gòu)所處的地位數(shù)據(jù)(Data):對客觀事物的符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)值型數(shù)據(jù)：整數(shù)、實數(shù)等；非數(shù)值型數(shù)據(jù)：圖像、聲音等。1.2基本概念和術(shù)語數(shù)據(jù)元素(DataElement):數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（dataitem）組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小標識單位。1.2基本概念和術(shù)語數(shù)據(jù)對象(DataObject)：性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。整數(shù)數(shù)據(jù)對象N={0,1,2,…}字母字符數(shù)據(jù)對象

C={‘A’,‘B’,‘C’,…‘Z’}1.2基本概念和術(shù)語定義1----數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。定義2----按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機語言并按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的集合。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素間的四類基本結(jié)構(gòu)：集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系，如線性表、棧、隊列。樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系，如樹。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組

Data__Structure(D,S)其中：D是數(shù)據(jù)元素的有限集

S是D上關(guān)系的有限集例1-4：在計算機科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)是是一種數(shù)據(jù)結(jié)構(gòu)Complex=(C,R)其中:C是含兩個實數(shù)的集合<c1，c2>，R={P},P是定義在集合C上的一種關(guān)系{<c1，c2>}，其中<c1，c2>表示c1是復(fù)數(shù)的實部，c2是復(fù)數(shù)的虛部。例1-5：假設(shè)我們需要編制一個事務(wù)管理的程序，管理學(xué)?？茖W(xué)研究課題小組的各項事務(wù)，則首先要為程序的操作對象——課題小組設(shè)計一個數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個小組由1位教師、1~3名研究生及1~6本科生組成，小組成員之間的關(guān)系是：教師指導(dǎo)研究生，而由每位研究生指導(dǎo)一至兩名本科生。則可以如下定義數(shù)據(jù)結(jié)構(gòu)：Group=(P,R)其中：P={T，G1，……，Gn，S11…Snm}1≦n≦3,1≦m≦2,R={R1，R2}R1={〈T，Gi〉∣1≦i≦n,1≦n≦3}R2={〈Gi，Sij〉

∣1≦i≦n，1≦j≦m,1≦n≦3,1≦m≦2}課堂練習(xí)：畫出下列數(shù)據(jù)結(jié)構(gòu)所對應(yīng)的結(jié)構(gòu)示意圖：(1)數(shù)據(jù)結(jié)構(gòu)structure1=（D,R）D={1，2，3，4，5，6}R={r}r={<1，2>,<2，5>,<5，3>,<3，6>,<6，4>}(2)數(shù)據(jù)結(jié)構(gòu)structure2=（D,R）D={1，2，3，4，5，6}R={r}r={<1，2>,<1，3>,<1，4>,<2，5>,<2，6>}(3)數(shù)據(jù)結(jié)構(gòu)structure3=（D,R）D={1，2，3，4，5，6}R={r}r={<1，6>,<2，6>,<6，4>,<6，5>,<4，5>}課堂練習(xí)：(4)數(shù)據(jù)結(jié)構(gòu)structure4=（D,R）D={a，b，c，d，e，f}R={r1,r2}r1={<c，b>,<c，e>,<b，a>,<e，d>,<e，f>}r2={<a，b>,<b，c>,<c，d>,<d，e>,<e，f>}邏輯結(jié)構(gòu)---數(shù)據(jù)元素間抽象化的相互關(guān)系（簡稱為數(shù)據(jù)結(jié)構(gòu)）。與數(shù)據(jù)的存儲無關(guān)，獨立于計算機，它是從具體問題抽象出來的數(shù)學(xué)模型。存儲結(jié)構(gòu)（物理結(jié)構(gòu)）----數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式。是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計算機語言。1.2基本概念和術(shù)語數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈式存儲結(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個方面，任何一個算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。數(shù)據(jù)類型：是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，它最早出現(xiàn)在高級程序語言中，用以刻畫（程序）操作對象的特性。數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。按“值”的不同特性，高級程序語言中的數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型。原子類型的值是不可分解的。另一類是結(jié)構(gòu)類型。結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(AbstractDataType，簡稱ADT)：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。

ADT的定義僅是一組邏輯特性描述，與其在計算機內(nèi)的表示和實現(xiàn)無關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。

ADT的形式化定義是三元組：

ADT=(D，S，P)其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。ADT的一般定義形式是：ADT<抽象數(shù)據(jù)類型名>{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT<抽象數(shù)據(jù)類型名>其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述。基本操作的定義是：<基本操作名>(<參數(shù)表>)初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>1.4.1算法什么是算法？算法（Algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。一個算法必須滿足以下五個重要特性：1.4算法和算法分析一個算法必須滿足以下五個準則：（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出1.4.1算法1、有窮性：對于任何合法的輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間內(nèi)完成；2、確定性：對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；3、可行性：算法中的所有操作都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；五個準則：4、輸入:一個算法有零個或多個輸入，有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中；5、輸出:它是一組與“輸入”有著確定關(guān)系的量值，是算法進行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。五個準則：一個算法可以用多種方法描述，主要有：使用自然語言描述；使用形式語言描述；使用計算機程序設(shè)計語言描述。算法和程序是兩個不同的概念。一個計算機程序是對一個算法使用某種程序設(shè)計語言的具體實現(xiàn)。算法必須可終止意味著不是所有的計算機程序都是算法。1.4.2算法設(shè)計的要求設(shè)計一個“好”的算法時，通常應(yīng)考慮達到以下目標：1、正確性2、可讀性3、健壯性4、效率與低存儲量需求1、正確性（correctness）算法應(yīng)當(dāng)滿足具體問題的需求。算法是否“正確”的理解可以有以下四個層次：A.程序中不含語法錯誤；B.程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；C.程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；D.程序?qū)τ谝磺泻戏ㄝ斎霐?shù)據(jù)都能夠產(chǎn)生滿足要求的結(jié)果。通常以第C層意義的正確性作為衡量一個算法是否合格的標準。2、可讀性（readability）算法主要是為了人的閱讀與交流，其次才是為計算機執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試和修改。3.健壯性（robustness）當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。4、效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；對于同一個問題，如果有多種算法可以解決，執(zhí)行時間短的算法效率高。存儲量指的是算法執(zhí)行過程中所需要的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。1.4.3算法效率的衡量算法執(zhí)行時間通常有兩種衡量的方法：（1）事后統(tǒng)計法缺點：1.必須執(zhí)行程序;2.其它因素（計算機硬件、軟件等）掩蓋算法本身的優(yōu)劣。（2）事前分析估算法算法執(zhí)行時間取決于下列因素：1.算法選用的策略；2.問題的規(guī)模；3.編寫程序的語言；4.編譯程序產(chǎn)生的機器代碼的質(zhì)量；5.計算機執(zhí)行指令的速度。撇開軟硬件等有關(guān)部門因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間度量可記作：T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作漸進時間復(fù)雜度，簡稱時間復(fù)雜度。1.4.3算法效率的衡量一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示?！癘”的定義：若f(n)是正整數(shù)n的一個函數(shù)，則O(f(n))表示M≥0，使得當(dāng)n≥n0時，|f(n)|≤M

|f(n0)|。表示時間復(fù)雜度的階有：O(1)：常量時間階O(㏒n)：對數(shù)時間階O(n)：線性時間階O(n㏒n)：線性對數(shù)時間階O(n2)：平方時間階O(nk)：k≥2，k次方時間階1.4.3算法效率的衡量

以下六種計算算法時間的多項式是最常用的。其關(guān)系為：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指數(shù)時間的關(guān)系為：

O(2n)<O(n!)<O(nn)當(dāng)n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。例1

{++x;s=0;}將x自增看成是基本操作，則語句頻度為１，即時間復(fù)雜度為Ｏ(1)。如果將s=0也看成是基本操作，則語句頻度為２，其時間復(fù)雜度仍為Ｏ(1)，即常量階。例2兩個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時間復(fù)雜度為T(n)=O(n3)例３for(i=1;i<=n;++i){++x;s+=x;}語句頻度為：2n，其時間復(fù)雜度為：O(n)，即為線性階。例４for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}語句頻度為：2n2，其時間復(fù)雜度為：O(n2)，即為平方階。定理：若A(n)=amnm

+am-1nm-1+…+a1n+a0是一個m次多項式，則A(n)=O(n

m)例５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∴時間復(fù)雜度為O(n2)，即此算法的時間復(fù)雜度為平方階。例6冒泡排序法。Voidbubble_sort(inta[]，intn){for(i=n-1;change=TURE;i>1&&change;--i)change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE;}}

最好情況：0次最壞情況：1+2+3+?+n-1=n(n-1)/2

平均時間復(fù)雜度為：O(n2)1.4.4算法的存儲空間需求類似于算法的