數(shù)據(jù)結(jié)構(gòu)-課件-胡學(xué)鋼

1、2021/8/61數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C(C語(yǔ)言版語(yǔ)言版) )2021/8/62目目 錄錄概概 論論第第 1 章章線線 性性 表表第第 2 章章棧、隊(duì)列和數(shù)組棧、隊(duì)列和數(shù)組第第 3 章章樹(shù)樹(shù)第第 4 章章圖圖第第 5 章章查查 找找第第 6 章章排排 序序第第 7 章章文文 件件第第 8 章章2021/8/63第第 1 章章 概概 論論數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.1基基 本本 術(shù)術(shù) 語(yǔ)語(yǔ)1.2算算 法法 描描 述述 及及 分分 析析1.32021/8/641.1 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.1.1 用計(jì)算機(jī)解決實(shí)際問(wèn)題的過(guò)程用計(jì)算機(jī)解決實(shí)際問(wèn)題的過(guò)程建立建立 模型模型構(gòu)造求構(gòu)造求解算法解算

2、法選擇存儲(chǔ)選擇存儲(chǔ)結(jié)構(gòu)型結(jié)構(gòu)型編寫編寫程序程序測(cè)試測(cè)試思考思考：你認(rèn)為數(shù)據(jù)結(jié)構(gòu)課程會(huì)涉及到上述哪些步驟呢？2021/8/65數(shù)據(jù)結(jié)構(gòu)課程在問(wèn)題求解過(guò)程中的作用： 與建立模型的關(guān)系 與算法設(shè)計(jì)的關(guān)系 與選擇存儲(chǔ)結(jié)構(gòu)的關(guān)系 與編程之間的關(guān)系2021/8/661.1.2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。 目前在我國(guó)，數(shù)據(jù)結(jié)構(gòu)不僅是計(jì)算機(jī)專業(yè)的核心課程之一，而且是一些非計(jì)算機(jī)專業(yè)的主要選修課程之一。 瑞士計(jì)算機(jī)科學(xué)家沃斯（N.Wirth）曾以“算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

3、程序程序”作為他的一本著作的名稱?？梢?jiàn)，程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)一個(gè)好的算法。因此，若僅僅掌握幾種計(jì)算機(jī)語(yǔ)言和程序設(shè)計(jì)方法，而缺乏數(shù)據(jù)結(jié)構(gòu)知識(shí)，則難以應(yīng)付眾多復(fù)雜的課題，且不能有效地利用計(jì)算機(jī)。 2021/8/67 數(shù)據(jù)結(jié)構(gòu) 是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。是介于數(shù)學(xué)、計(jì)算機(jī)軟件、計(jì)算機(jī)硬件的 一門核心課程。2021/8/681.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算

4、的實(shí)現(xiàn)2021/8/691.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)是指信息的載體，是能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)的集合。數(shù)據(jù)的形式較多，例如我們前面所述的工資報(bào)表、學(xué)生成績(jī)表，一個(gè)家族關(guān)系的表示形式，表示一個(gè)群體中個(gè)體之間關(guān)系的圖形描述等。 2021/8/6101.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)

5、數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)中具有獨(dú)立意義的個(gè)體。例如工資表中的個(gè)人工資信息，成績(jī)表中的學(xué)生成績(jī)信息，家族關(guān)系中的個(gè)人等。在有些場(chǎng)合下，也稱之為元素元素、記錄記錄、結(jié)點(diǎn)結(jié)點(diǎn)、頂點(diǎn)頂點(diǎn)等。 2021/8/6111.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)雖然將具有獨(dú)立意義的個(gè)體用元素來(lái)表示，但在許多情況下還需要特定個(gè)體的具體信息，因而涉及到了元素的字段信息。字段是對(duì)元素的詳細(xì)描述，通常情況下，元素可能包含多個(gè)字段。 2021/8/612

6、1.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)是指組成數(shù)據(jù)的元素之間的結(jié)構(gòu)關(guān)系。線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中的幾類常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)形式。如果數(shù)據(jù)中的元素之間沒(méi)有關(guān)系，則構(gòu)成集合集合，這也是一種結(jié)構(gòu)。 2021/8/6131.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)我們將線性結(jié)構(gòu)、樹(shù)型結(jié)

7、構(gòu)和圖結(jié)構(gòu)這幾類結(jié)構(gòu)稱為邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。因?yàn)閮H考慮了元素之間的邏輯關(guān)系，而沒(méi)有考慮到其在計(jì)算機(jī)中的具體實(shí)現(xiàn)。2021/8/6141.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)為所涉及的數(shù)據(jù)結(jié)構(gòu)選擇一種存儲(chǔ)形式，并將其存儲(chǔ)到計(jì)算機(jī)中，這樣就得到了數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的物理結(jié)構(gòu)物理結(jié)構(gòu)（有時(shí)也稱為存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)）。一種邏輯結(jié)構(gòu)可能會(huì)有多種存儲(chǔ)結(jié)構(gòu)。例如，可以采用順序存儲(chǔ)，也可采用連接形式的存儲(chǔ)。不同存儲(chǔ)結(jié)構(gòu)上所實(shí)現(xiàn)的運(yùn)

8、算的性能可能有一定的差異。 2021/8/6151.2 基本術(shù)語(yǔ)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)。一個(gè)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。在選擇了數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)之后，就可以實(shí)現(xiàn)所給出的運(yùn)算了。 2021/8/6161.2 小 結(jié)數(shù)數(shù) 據(jù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素 字段字段( (域域) ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)運(yùn)算的數(shù)據(jù)

9、結(jié)構(gòu)運(yùn)算的實(shí)現(xiàn)實(shí)現(xiàn)所以，由于不同的存儲(chǔ)形式對(duì)算法的時(shí)間性能、空間性能等有較大影響，即使是相同的存儲(chǔ)結(jié)構(gòu)也可能會(huì)存在不同的算法實(shí)現(xiàn)，為此，需要解決這樣的問(wèn)題：究竟何種存儲(chǔ)結(jié)構(gòu)更為合適？什么算法更有效？為此，需要對(duì)算法進(jìn)行分析，有關(guān)算法分析部分將在本章的后面部分討論。通過(guò)分析，可以知道所實(shí)現(xiàn)的算法的性能及所選擇的存儲(chǔ)結(jié)構(gòu)是否符合要求。 2021/8/6171.3 算法描述及分析1.3.1 算法描述語(yǔ)言概述算法描述語(yǔ)言概述描述：描述：算法可采用多種描述語(yǔ)言來(lái)描述，如自然語(yǔ)言、計(jì)算機(jī)語(yǔ)言或某些偽語(yǔ)言。各種描述語(yǔ)言在對(duì)問(wèn)題的描述能力方面存在一定的差異：自然語(yǔ)言較為靈活，但不夠嚴(yán)謹(jǐn)；而計(jì)算機(jī)語(yǔ)言雖然嚴(yán)格，

10、但由于語(yǔ)法方面的限制，使得靈活性不足。因此，許多教材中采用的是以一種計(jì)算機(jī)語(yǔ)言為基礎(chǔ)，適當(dāng)添加某些功能或放寬某些限制而得到的一種類語(yǔ)言，如類PASCAL語(yǔ)言、C語(yǔ)言等，這些類語(yǔ)言既具有計(jì)算機(jī)語(yǔ)言的嚴(yán)格性，又具有某些靈活性，同時(shí)也容易上機(jī)實(shí)現(xiàn)，因而被廣泛接受。 定義定義:是對(duì)特定問(wèn)題求解步驟的一種描述,是指令的有限序列,其中每一條指令表示一個(gè)或多個(gè) 操作。特性特性: 有窮性 確定性 可行性 輸入 輸出2021/8/618算法設(shè)計(jì)的要求：算法設(shè)計(jì)的要求：u 正確性：算法是否正確,是否符合具體問(wèn)題的需求。u 可讀性：有利于人機(jī)交流，機(jī)器執(zhí)行。u 健壯性：對(duì)錯(cuò)誤能適當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行處理。u 效率與低

11、存儲(chǔ)量的要求。2021/8/6191.3 算法描述及分析1.3.2 算法分析算法分析 衡量算法的主要性能指標(biāo)包括時(shí)間性能、空間性能等，其中時(shí)間性能是指運(yùn)行算法所需的時(shí)間的度量，而空間性能則是指運(yùn)行算法所需要的輔助空間的規(guī)模。 度量運(yùn)行時(shí)間的方法：事后統(tǒng)計(jì)，事前分析估算（常用后一種）。2021/8/620 時(shí)間的復(fù)雜度時(shí)間的復(fù)雜度是指算法中包含簡(jiǎn)單操作重復(fù)執(zhí)行的次數(shù)，而某個(gè)語(yǔ)句重復(fù)執(zhí)行的次數(shù)就是該語(yǔ)句的頻度。 可以記做：T(n)=O( f(n) ) 其中f(n）是問(wèn)題規(guī)模n的某個(gè)函數(shù)，一般是算法中頻度最大的語(yǔ)句頻度。 例如： s:=0; for (k=1 ; k=n;k+) for( j=0;j

12、= n;j+) s:=s+2; 語(yǔ)句的頻度是n*(n+1) * 存在循環(huán)嵌套語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套最深層的語(yǔ)句頻度決定。 評(píng)價(jià)一個(gè)算法的時(shí)間性能主要標(biāo)準(zhǔn)是時(shí)間復(fù)雜度的數(shù)量級(jí)。這個(gè)程序段的時(shí)間復(fù)雜度為：T(n)=O(n2+n)=O(n2)所謂數(shù)量級(jí)是這樣定義的：如果變量如果變量n的函數(shù)的函數(shù)f(n)和和g(n)滿足：滿足：lim =常數(shù)常數(shù)k(k0)，則稱，則稱f(n)和和g(n)是同一數(shù)量級(jí)的，并用是同一數(shù)量級(jí)的，并用f(n)=O(g(n)的形式來(lái)表示。的形式來(lái)表示。)()(ngnf2021/8/621 按數(shù)量級(jí)遞增的順序排列，常見(jiàn)的時(shí)間復(fù)雜度為： 常數(shù)階O（1） 對(duì)數(shù)階 O（2n）

13、 線性階O（n） 線性對(duì)數(shù)階O（n 2n ） 平方階O（n2） 立方階O（n3） K次方階O（nk） 指數(shù)階O（2n）2021/8/622例：程序段 語(yǔ)句頻度 時(shí)間復(fù)雜度1. x=x+1; FOR( i=0; i= n;i+) x:=x+1; 3. FOR( i=1; in;i+) FOR(j=0; jn;j+) x:=x+1; 1 O(1) 常數(shù)階 n+1 O(n) 線性階(n-1)*nO(n2) 平方階2021/8/623 算法與程序的區(qū)別算法是解決問(wèn)題的一種方法或一個(gè)過(guò)程，考慮如何將輸入轉(zhuǎn)換成輸出，一個(gè)問(wèn)題可以有多種算法。程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn)。主要區(qū)別在：有窮性和描述方法 程序可以是無(wú)窮的，例如OS，算法是有窮的； 程序是用程序設(shè)計(jì)語(yǔ)言描述，在機(jī)器上可以執(zhí)行； 算法還可以用框圖、自然語(yǔ)言等方式描述。2021/8/624思考題 下面程序段的時(shí)間復(fù)雜度為（）(a) x=x+1;(b) FOR( i=0; i=n;i+) x=x+1;(c) FOR( i=1; i n;i+) FOR( j