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

數(shù)據(jù)結(jié)構(gòu)

DATASTRUCTURE

教材2數(shù)據(jù)結(jié)構(gòu)〔C語言篇〕－－習題與解析李春葆清華大學出版社參考教材1數(shù)據(jù)結(jié)構(gòu)題集〔C語言版〕嚴蔚敏吳偉民清華大學出版社數(shù)據(jù)結(jié)構(gòu)〔C語言版〕嚴蔚敏吳偉民清華大學出版社2002課程學時課程總學時數(shù)：72〔講課：56，實驗：16〕課程設(shè)計〔1周〕目錄第一章緒論第二章線性表第三章棧與隊列第五章數(shù)組和廣義表第七章圖第八章查找第九章排序第六章樹與二叉樹C語言相關(guān)知識回憶數(shù)據(jù)處理輸入、輸出、加工、存儲模塊化函數(shù)聲明與調(diào)用參數(shù)傳遞其它typedef使用指針操作：malloc，free第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2根本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)1.4算法和算法分析1.4.1算法1.4.2算法設(shè)計的要求1.4.3算法效率的度量1.4.4算法的存儲空間的需求

非數(shù)值問題1.1什么是數(shù)據(jù)結(jié)構(gòu)例1學生信息檢索系統(tǒng)學號姓名性別專業(yè)年級980001吳承志男計算機科學與技術(shù)98級980002李淑芳女信息與計算科學98級990301劉麗女數(shù)學與應(yīng)用數(shù)學99級990302張會友男信息與計算科學99級990303石寶國男計算機科學與技術(shù)99級000801何文穎女計算機科學與技術(shù)2000級000802趙勝利男數(shù)學與應(yīng)用數(shù)學2000級000803崔文靖男信息與計算科學2000級010601劉麗女計算機科學與技術(shù)2001級010602魏永鳴男數(shù)學與應(yīng)用數(shù)學2001級1.1什么是數(shù)據(jù)結(jié)構(gòu)1968年美國唐·歐·克努特〔DonaldE.Knuth〕教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系：它所著的?計算機程序設(shè)計技巧?〔TheArtofComputerProgramming〕第一卷?根本算法?是第一本系統(tǒng)闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。1.2根本概念和術(shù)語數(shù)據(jù)(Data):是對客觀事物的符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)值數(shù)據(jù)、非數(shù)值數(shù)據(jù)〔文字、圖像、聲音等〕數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的根本單位，在計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由假設(shè)干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。1.2根本概念和術(shù)語數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。在某個具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)〔元素值不一定相等〕，屬于同一數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 －－－－數(shù)據(jù)的邏輯結(jié)構(gòu)1.2根本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的分類：一、線性結(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)系。（a）線性結(jié)構(gòu)（b）樹型結(jié)構(gòu)（c）圖形結(jié)構(gòu)三類根本結(jié)構(gòu)的示意圖1.2根本概念和術(shù)語例：某班學生根本情況登記表，學號姓名 專業(yè) 政治面藐 001 王洪 計算機黨員

002孫文計算機團員

003 謝軍 計算機團員

004 李輝 計算機團員

005 沈祥福計算機黨員006 余斌 計算機團員

007 鞏力 計算機團員

008 孔令輝計算機團員學生間學號順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系1.2根本概念和術(shù)語例：家族的族譜

假設(shè)某家族有10個成員A，B，C，D，E，F(xiàn)，G，H，I，J，他們之間的血緣關(guān)系可以用如以下圖表示。JIACBDHGFE1.2根本概念和術(shù)語對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：1〕數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的根本操作；

2〕數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)根本操作的實現(xiàn)。1.2根本概念和術(shù)語一、數(shù)據(jù)〔邏輯〕結(jié)構(gòu)的表示圖示表示

001003002004006005008007學生根本情況表的圖示表示JIACBDHGFE家族樹的圖示表示1.2根本概念和術(shù)語一、數(shù)據(jù)〔邏輯〕結(jié)構(gòu)的表示二元組表示

Data_Structrue=〔D，S〕其中:D是數(shù)據(jù)元素集合，S是D上關(guān)系的集合。

001003002004006005008007D={001，002，003，004，005，006，007，008}S={R}R={<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}1.2根本概念和術(shù)語一、數(shù)據(jù)〔邏輯〕結(jié)構(gòu)的表示

數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學模型，它與數(shù)據(jù)的存儲無關(guān)1.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 1定義數(shù)據(jù)結(jié)構(gòu)在計算機中的表示或?qū)崿F(xiàn)稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。 包括數(shù)據(jù)元素的表示及元素間關(guān)系的表示。1.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 2表示i)數(shù)據(jù)元素的表示 在計算機中，可用二進制位串表示一個數(shù)據(jù)元素，稱這個位串為元素〔Element〕或結(jié)點〔Node〕。ii)元素間關(guān)系的表示1.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 3分類

根據(jù)數(shù)據(jù)元素之間的關(guān)系在計算機中的不同表示方法，數(shù)據(jù)的存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)1.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 3分類①順序存儲結(jié)構(gòu)用元素在存儲器中的相對位置表示數(shù)據(jù)元素之間的邏輯關(guān)系k1k2k3k4200201202203k1k2k3k4M1.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 3分類 ②鏈式存儲方法 用指針表示數(shù)據(jù)元素之間的邏輯關(guān)系k1k2k3k1400k3nullk2300200300400MK1K1nullK11.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 3分類 其它存儲方式： 1〕索引存儲張三?數(shù)據(jù)結(jié)構(gòu)?李四?離散數(shù)學?張三200李四300100101200300結(jié)點表索引表……….1.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 3分類 其它存儲方式：2〕散列存儲

001056012004007f(key)=key%12+2000120010040072072002012040562081.2根本概念和術(shù)語二、數(shù)據(jù)的存儲結(jié)構(gòu) 4描述 本書采用在高級語言中的數(shù)據(jù)類型〔Datatype〕來描述存儲結(jié)構(gòu)。如：對數(shù)據(jù)元素，可用根本類型〔整型、字符型等〕或結(jié)構(gòu)類型來描述對關(guān)系：可用一維數(shù)組描述順序存儲結(jié)構(gòu)用“指針〞描述鏈式存儲結(jié)構(gòu)1.2根本概念和術(shù)語數(shù)據(jù)類型〔DataType〕是一個值的集合和定義在該值集上的一組操作的總稱。抽象數(shù)據(jù)類型〔AbstructDataType，簡稱ADT〕是指一個數(shù)學模型以及定義在該模型上的一組操作?！睤，S，P〕其中，D表示數(shù)據(jù)對象，S表示關(guān)系集，P表示根本操作集。本書實際用ADT來描述數(shù)據(jù)的邏輯結(jié)構(gòu)及運算。1.2根本概念和術(shù)語三、數(shù)據(jù)的運算數(shù)據(jù)的運算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。如檢索、插入、刪除等。數(shù)據(jù)的運算是在邏輯結(jié)構(gòu)上定義，在具體的存儲結(jié)構(gòu)上實現(xiàn)。小結(jié)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算間關(guān)系運算在邏輯結(jié)構(gòu)上定義，在存儲結(jié)構(gòu)上實現(xiàn)存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機內(nèi)部的映象方面層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)運算實現(xiàn)存儲結(jié)構(gòu)算法評價不同數(shù)據(jù)結(jié)構(gòu)間比較及算法分析數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型定義格式：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ù)據(jù)根本操作的定義格式： 根本操作名〔參數(shù)表〕 初始條件：〈初始條件描述〉 操作結(jié)果：〈操作結(jié)果描述〉例：ADTTriplet{數(shù)據(jù)對象：D={e1，e2,e3|e1,e2,e3∈Elemset(定義了關(guān)系運算的某個集合)}數(shù)據(jù)關(guān)系：R1={〈e1,e2>,<e2,e3>〉根本操作： InitTriplet(&T,v1,v2,v3) DestroyTriplet〔&T〕 Get〔T,i,&e〕 Put(&T,i,e) }ADTTriplet1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)數(shù)據(jù)元素的表示數(shù)據(jù)類型typedef定義新類型算法的描述類C語言函數(shù)1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)幾點說明：1typedef2數(shù)據(jù)元素的定義例：學號姓名性別專業(yè)年級980001吳承志男計算機科學與技術(shù)98級980002李淑芳女信息與計算科學98級990301劉麗女數(shù)學與應(yīng)用數(shù)學99級990302張會友男信息與計算科學99級990303石寶國男計算機科學與技術(shù)99級000801何文穎女計算機科學與技術(shù)2000級1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)幾點說明：3算法的書寫采用類C語言、函數(shù)描述算法的輸入、輸出新的參數(shù)傳遞方式：引用參數(shù)傳遞1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)例：學生信息表，寫出它的順序存儲表示以及根據(jù)學號查找學生所在專業(yè)的算法聲明。學號姓名性別專業(yè)年級980001吳承志男計算機科學與技術(shù)98級980002李淑芳女信息與計算科學98級990301劉麗女數(shù)學與應(yīng)用數(shù)學99級990302張會友男信息與計算科學99級990303石寶國男計算機科學與技術(shù)99級000801何文穎女計算機科學與技術(shù)2000級000802趙勝利男數(shù)學與應(yīng)用數(shù)學2000級000803崔文靖男信息與計算科學2000級010601劉麗女計算機科學與技術(shù)2001級010602魏永鳴男數(shù)學與應(yīng)用數(shù)學2001級1.4算法和算法分析1.4.1算法算法〔Algorithm〕是對特定問題求解步驟的一種描述，它是指令的有限序列。算法的五個特性：〔1〕有窮性〔2〕確定性〔3〕可行性〔4〕輸入〔5〕輸出1.4.2算法設(shè)計的要求要設(shè)計一個好的算法通常要考慮以下的要求。⑴正確性(Correctness)算法應(yīng)滿足具體問題的需求。⑵可讀性(Readability)算法應(yīng)該好讀。以有利于閱讀者對程序的理解。⑶健壯性(Robustness)算法應(yīng)具有容錯處理。⑷效率與低存儲量要求效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。1.4.3算法效率的度量算法執(zhí)行時間分析方法的分類：事后統(tǒng)計事前分析度量方法采用時間復雜度來估計算法的算法的執(zhí)行時間 T(n)=O(f(n)) 即：如果存在兩個正常數(shù)c和n0，對于所有的n≥n0，有︱T(n)︳≤c｜f(n)︳它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作漸近時間復雜度〔AsymptoticTimeComplexity〕，簡稱時間復雜度。時間復雜度的求法：根本操作〔原操作〕語句的頻度：語句執(zhí)行的次數(shù)定理：假設(shè)A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，那么A(n)=O(nm)方法： 確定根本操作，求各語句的頻度之和，根據(jù)定理求出最后結(jié)果。1.4.3時間復雜度的求法例如:(a)｛ ++x; s=0; ｝根本操作語句頻度根本操作112語句頻度之和：根據(jù)定理：假設(shè)A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，那么A(n)=O(nm)〔O(nm)表示A(n)與nm成正比,即O(nm)與nm同一數(shù)量級；〕得：T(n)=2=O(1) 時間復雜度為O(1)1.4.3時間復雜度的求法例如:(b)for(i=1;i<=n;++i) {++x;s+=x;}(c)for(j=1;j<=n;++j) for(k=1;k<=n;k++) {++x;s+=x;}(d)for(j=2;j<=n;++j) for(k=2;k<=j-1;k++) {++x;s+=x;}(e)i=1 while(i<=n) i=i*21.4.3時間復雜度的求法常用的時間復雜度關(guān)系： O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3) <…?O(2n)<O(n!)<O(nn)

假設(shè)算法中根本操作重復執(zhí)行的次數(shù)隨問題輸入數(shù)據(jù)集不同而不同，這時可計算最壞情況下的時間復雜度或平均時間復雜度。1.4.3時間復雜度lognnnlognn2n32n0101121224842481664`163824645122564166425640966553653216010243276842949672961.4.3時間復雜度1.4.3時間復雜度1.4.4