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

1、數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)課程的重要性 如何學(xué)習(xí)和掌握課程內(nèi)容課程的基本要求 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語(yǔ) 1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 1.4 算法和算法分析第一章 緒論 計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問(wèn)題,信息表示和信息處理。 而信息的表示和組又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問(wèn)題。 1.1 什么是數(shù)據(jù)結(jié)構(gòu)用計(jì)算機(jī)解決具體問(wèn)題的基

2、本步驟:從具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型設(shè)計(jì)一解此數(shù)學(xué)模型的算法編制計(jì)算機(jī)程序,調(diào)試輸出結(jié)果 數(shù)據(jù)結(jié)構(gòu)研究和求解的數(shù)學(xué)模型問(wèn)題 1. 數(shù)學(xué)模型問(wèn)題分類: * 數(shù)值計(jì)算問(wèn)題 (數(shù)值分析和計(jì)算方法) 如線性方程組、微分方程等 * 非數(shù)值計(jì)算問(wèn)題 (數(shù)據(jù)結(jié)構(gòu)) 如表、樹(shù)、圖等 2. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算問(wèn)題 的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象 以及它們之間關(guān)系和操作等的學(xué)科.例1 書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表算法：需要檢索的書目？如何檢索？用戶界面？ 模型：？非數(shù)值計(jì)算數(shù)學(xué)模型的算法設(shè)計(jì)問(wèn)題例2 人

3、機(jī)對(duì)奕問(wèn)題樹(shù).算法：對(duì)奕的規(guī)則 和策略模型：？教學(xué)計(jì)劃編排問(wèn)題 圖課程代號(hào)課程名稱先修課程C1計(jì)算機(jī)導(dǎo)論無(wú)C2數(shù)據(jù)結(jié)構(gòu)C1,C4C3匯編語(yǔ)言C1C4C語(yǔ)言C1C5計(jì)算機(jī)圖形學(xué)C2,C3,C4C6接口技術(shù)C3C7數(shù)據(jù)庫(kù)原理C2,C9C8編譯原理C4C9操作系統(tǒng)C2C1C3C4C7C6C5C2C8C9 算法：如何確定課程的次序關(guān)系? 模型：？ 以上例子可以表明：數(shù)據(jù)結(jié)構(gòu)所研究和定義的非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型(表、樹(shù)、圖)中包括了操作對(duì)象和對(duì)象之間關(guān)系兩大集合等數(shù)學(xué)特性,同時(shí)定義了操作的數(shù)學(xué)上的特性 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 除了定義問(wèn)題的數(shù)學(xué)特性外,用計(jì)算機(jī)解決具體問(wèn)題,還應(yīng)給出數(shù)學(xué)模型在計(jì)算機(jī)中的

4、表示(映象到計(jì)算機(jī)內(nèi)存)和實(shí)現(xiàn)基于某種表示的操作(算法設(shè)計(jì)和算法評(píng)價(jià)).計(jì)算機(jī)軟件鼻祖唐毆克勞特給出了經(jīng)典觀點(diǎn): 邏輯結(jié)構(gòu)+物理結(jié)構(gòu)+操作 * 貫穿本書各章節(jié)對(duì)應(yīng)的是某某數(shù)據(jù)結(jié)構(gòu)的 定 義、表示和實(shí) 現(xiàn)數(shù)據(jù)（data)所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號(hào)的集合 ，是計(jì)算機(jī)操作的對(duì)象的總稱。數(shù)據(jù)元素（data element）是數(shù)據(jù)的基本單位，由若干個(gè)數(shù)據(jù)項(xiàng)組成，也稱結(jié)點(diǎn)、元素、頂點(diǎn)或記錄。數(shù)據(jù)項(xiàng)（data item）是數(shù)據(jù)的不可分割的最小單位，有時(shí)也稱為域（field），即數(shù)據(jù)表中的字段。數(shù)據(jù)對(duì)象(data object)：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如大寫字母字符數(shù)據(jù)

5、對(duì)象是集合C=A,B,C,，Z ，整數(shù)數(shù)據(jù)對(duì)象是集合 N = 0, 1, 2, 1.2 基本概念和術(shù)語(yǔ)根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)： 集 合 數(shù)據(jù)元素間 “同屬于一個(gè)集合” 線性結(jié)構(gòu) 一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列 樹(shù)形結(jié)構(gòu) 一個(gè)對(duì)多個(gè)，如樹(shù) 圖狀結(jié)構(gòu) 多個(gè)對(duì)多個(gè)，如圖數(shù)據(jù)結(jié)構(gòu)(data structure)：是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。例：一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示 3214,6587,9345 a1(3214),a2(6587),a3(9345)在a1、a2和a3 之間存在“次序”關(guān)系 a1,a

6、2、a2,a3 a1 a2 a3 a3 a2 a1 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,描述一個(gè)數(shù)據(jù)結(jié)構(gòu)中的數(shù)學(xué)模型包括以下兩大集合: 數(shù)據(jù)元素的集合(數(shù)據(jù))+關(guān)系的集合(結(jié)構(gòu)) * 本書中關(guān)于數(shù)學(xué)模型(邏輯結(jié)構(gòu))的定義部分都包含兩大集合數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 Data-Structure=（D，S） 其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu) Complex=（C，R） 其中，C是含兩個(gè)實(shí)數(shù)集合c1，c2；R=P，P是定義在集合C上的一種關(guān)系，其中有序偶表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛

7、部。邏輯結(jié)構(gòu)描述了數(shù)學(xué)模型中數(shù)據(jù)元素”關(guān)系”定義的邏輯關(guān)系。存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)形式（或稱映象）。 元素/結(jié)點(diǎn)：用于表示數(shù)據(jù)元素的二進(jìn)制位(bit)的位串。 數(shù)據(jù)域：用于表示數(shù)據(jù)項(xiàng)的二進(jìn)制位(bit)的位串。例（321）10（501）8（101000001）2 A（101）8（001000001）2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有兩種不同的機(jī)內(nèi)表示:順序表示(順序映象)和非順序表示(非順序映象),因此存儲(chǔ)結(jié)構(gòu)分為: 順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系元素n.元素i.元素2元素1Lo

8、Lo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)1536元素21400元素11346元素3 元素41345h存儲(chǔ)地址 存儲(chǔ)內(nèi)容 指針 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 1346 鏈?zhǔn)酱鎯?chǔ) h 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 操作：查找、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)：完?duì)列串樹(shù)結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)組和廣義表 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是緊密相關(guān)的,任何一個(gè)算法的設(shè)計(jì)取決于與邏輯結(jié)構(gòu),而算法的實(shí)現(xiàn)取決

9、于與存儲(chǔ)結(jié)構(gòu)。將邏輯結(jié)構(gòu)映象到內(nèi)存得到存儲(chǔ)結(jié)構(gòu)的方法和工具很多,本書是在高級(jí)程序語(yǔ)言(C語(yǔ)言)層次上討論和實(shí)現(xiàn)的.主要借助于C指令和C數(shù)據(jù)類型,而映象過(guò)程對(duì)我們是透明的.數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱。例：C語(yǔ)言中，提供int, char, float, double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef 自己定義數(shù)據(jù)類型 typedef struct int num; char name20; float score; STUDENT; STUDENT為新的結(jié)構(gòu)類型 如: STUDENT st

10、u1,stu2, *p; 1.3 抽象數(shù)據(jù)類型表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型ADT（Abstract Data Type)定義：指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。將一個(gè)具體問(wèn)題的數(shù)學(xué)模型和一組特定操作封裝成一個(gè)ADT,來(lái)定義一個(gè)數(shù)據(jù)結(jié)構(gòu). 例：矩陣 +（求轉(zhuǎn)置、加、乘、求逆、求特征值）構(gòu)成一個(gè)矩陣的抽象數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu) + 定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作 = 抽象數(shù)據(jù)類型描述方法形式定義：我們用一個(gè)三元組 （D，S，P）來(lái)表示一個(gè) 抽象數(shù)據(jù)類型 ，其中D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。 格式： ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)

11、據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名 基本操作的定義格式： 基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述 1.賦值參數(shù)2.引用參數(shù)，以“”打頭例：抽象數(shù)據(jù)類型三元組的定義： ADT Triplet 數(shù)據(jù)對(duì)象：D=e1,e2,e3 |e1,e2,e3Elemset 數(shù)據(jù)關(guān)系：R1=, 基本操作： InitTriplet(&T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三元組T， 元素e1，e2和e3分別被賦以 參數(shù)v1,v2和v3的值。 DestroyTriplet（&T） 操作結(jié)果：三元組T被銷毀。 Get（T,i,&e）

12、初始條件：三元組T已存在， 1=i=3. 操作結(jié)果：用e返回T的第i元的值。 Put(&T,i,e) 初始條件：三元組T已存在，1=i=3. 操作結(jié)果：改變T的第i元的值為e。 IsAscending(T) 初始條件：三元組T已存在。 操作結(jié)果：如果T的3個(gè)元素按升序排列，則返回1，否則返回0。IsDescending(T) 初始條件：三元組T已存在。 操作結(jié)果：如果T的3個(gè)元素按降序排列，則 返回1，否則返回0。Max(T,&e) 初始條件：三元組T已存在。 操作結(jié)果：用e返回T的3個(gè)元素中的最大值。Min(T,&e) 初始條件：三元組T已存在。 操作結(jié)果：用e返回T的3個(gè)元素中的最小值。A

13、DT Triplet 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) ADT可通過(guò)固有數(shù)據(jù)類型來(lái)表示和實(shí)現(xiàn),即用已存在的數(shù)據(jù)類型來(lái)說(shuō)明邏輯結(jié)構(gòu),用已實(shí)現(xiàn)操作來(lái)組合新的操作 本書采用“類C”(類似C語(yǔ)言)語(yǔ)言來(lái)表示和實(shí)現(xiàn)ADT 類C = C語(yǔ)言核心子集+偽碼+ C+某些擴(kuò)充 偽碼:類似于自然語(yǔ)言描述,能簡(jiǎn)明表示數(shù)據(jù)類型和算法。且易移植成C或C+語(yǔ)句和程序,例如: ElemType A; 偽碼ElemType是描述數(shù)據(jù)元素類型,編程 時(shí)應(yīng)根據(jù)具體問(wèn)題轉(zhuǎn)換成C語(yǔ)言中的固有數(shù)據(jù)類型,如: int A ; char A; real A;等C+引用調(diào)用參數(shù)傳遞(“&”):實(shí)參和形參的雙向傳遞,如: int i; increme

14、nt ( i ); printf( i ) void increment( int & j ) : j=j+1; : ? 調(diào)用后 i的值抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)(P11) 數(shù)據(jù)類型(動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)) typedef ElemType *Triplet; 基本操作的實(shí)現(xiàn)中initTriplet函數(shù)用 到了malloc( )動(dòng)態(tài)分配函數(shù) ADT的表示和實(shí)現(xiàn)很容易轉(zhuǎn)換成C+中 的類(class)即對(duì)象(object),如: Class Type type var 1; type var 2; : type var m public member function 1 membe

15、r function 2 : member function n name associated with class type; ADT定義了解即可。逐步掌握從具體問(wèn)題定義數(shù)學(xué)模型重點(diǎn)掌握邏輯結(jié)構(gòu)的表示,既C數(shù)據(jù)類型和結(jié)構(gòu)體重點(diǎn)掌握基本操作的實(shí)現(xiàn),即算法的設(shè)計(jì)(算法思想)和算法的實(shí)現(xiàn)(編制C程序)包括下節(jié)算法評(píng)價(jià)也應(yīng)重點(diǎn)掌握 以后各章節(jié)都應(yīng)注意1.4 算法和算法分析有窮性：對(duì)于任意一組合法輸入值，在執(zhí)行有窮步之后結(jié)束，即算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；確定性：每條指令都有確切的含義，在任何條件下算法都只有一條執(zhí)行路徑；不存在二義性算法五個(gè)重要特性：算法：是對(duì)特定問(wèn)題求解步驟的描述，是指

16、令的有限序列?？尚行裕核惴ㄖ械乃胁僮鞫急仨氉銐蚧荆伎梢酝ㄟ^(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；有輸入：有零個(gè)或多個(gè)輸入，取自特定的對(duì)象集合有輸出：有一個(gè)或多個(gè)輸出，是算法進(jìn)行信息加工后得到的結(jié)果。算法設(shè)計(jì)的原則正確性：在合理的數(shù)據(jù)輸入下，能在有限的運(yùn)算時(shí)間內(nèi)得到正確結(jié)果； 對(duì)算法是否“正確”的理解可以有以下四個(gè)層次： a程序中不含語(yǔ)法錯(cuò)誤； b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求 的結(jié)果； c程序?qū)τ诰倪x擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；可讀性：易于人對(duì)算法的理解；另一方面，晦澀難讀的程序易于隱藏較多

17、錯(cuò)誤而難以調(diào)試；健壯性： 當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。高效率與低存儲(chǔ)量需求： 通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。兩者都與問(wèn)題的規(guī)模有關(guān)。 算法效率的衡量方法和準(zhǔn)則 有兩種衡量算法效率的方法: 1.事后統(tǒng)計(jì)法：利用計(jì)算機(jī)內(nèi)記時(shí)功能，用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分。 2.事前分析估計(jì)法：求出算法的一個(gè)時(shí)間界限函數(shù)。和算法執(zhí)行時(shí)間相關(guān)的因素： 算法選用的策略 問(wèn)題的規(guī)模 編寫程序的語(yǔ)言 編

18、譯程序產(chǎn)生機(jī)器代碼質(zhì)量 機(jī)器執(zhí)行指令速度時(shí)間復(fù)雜度：程序運(yùn)行從開(kāi)始到結(jié)束所需要的時(shí)間度量(某個(gè)數(shù)量級(jí))。 設(shè)解決一個(gè)問(wèn)題的規(guī)模為n，基本操作(原操作)被重復(fù)執(zhí)行的次數(shù)是n的一個(gè)函數(shù) f（n），假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作： T (n) = O(f(n) 其中T(n)叫算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 算法控制結(jié)構(gòu)+原操作（對(duì)固有數(shù)據(jù)類型的操作） 原操作頻度f(wàn)(n) = 原操作（i）的執(zhí)行次數(shù) 算法的執(zhí)行時(shí)間原操作（i）的執(zhí)行次數(shù) 原操作（i）執(zhí)行時(shí)間 從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算

19、法運(yùn)行時(shí)間度衡量準(zhǔn)則。例1：NXN矩陣相乘(三重嵌套循環(huán))for(i=1; i=n; i+) for(j=1; j=n; j+) cij=0; for(k=1; k=n; k+) cij=cij+aik*bkj; 顯然，被稱做問(wèn)題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的原操作，多數(shù)情況下是嵌套循環(huán)中最深層循環(huán)內(nèi)的語(yǔ)句中的原操作，它的執(zhí)行次數(shù)和包含它的語(yǔ)句頻度f(wàn)(n)相同。例 2+x;s=0;例for(i=1; i=n; +i) +x; s+=x;例. for(i=2; i=n; +i) for(j=2; j=i-1; +j) +x; ai,j=x;T(n)=(1) 常量階 頻度f(wàn)(n)=2nT(n)= O(n) 線性階原操作+x語(yǔ)句頻度f(wàn)(n)為：0+1+2+3+n-2 =(n-1)(n-2)/2 =(n2-3n+2)/2 T(n)= O(n2) 平方階 例 5: for(i=1;i=n;+i) for(