數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程

書(shū)名：數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程ISBN：978-7-111-24128-7作者：高佳琴出版社：機(jī)械工業(yè)出版社本書(shū)配有電子課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)與算法實(shí)用教程主編高佳琴數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第2頁(yè)。第1章概述本章要點(diǎn)：1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的概念以及邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系。2)算法的定義、特性，算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。3)C語(yǔ)言指針的定義、指針的基本操作、動(dòng)態(tài)分配函數(shù)等。本章難點(diǎn)：1)數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系。2)算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第3頁(yè)。1)從具體問(wèn)題分析入手找出解決該問(wèn)題的方法(數(shù)據(jù)模型)。2)設(shè)計(jì)解決該問(wèn)題的具體步驟(算法)。3)選擇程序設(shè)計(jì)語(yǔ)言和數(shù)據(jù)類(lèi)型，編寫(xiě)代碼(源程序)，源程序經(jīng)編譯后得到可直接運(yùn)行的程序(目標(biāo)程序)。第1章概述圖1-1計(jì)算機(jī)解決問(wèn)題的一般步驟數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第4頁(yè)。第1章概述1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2基本概念和術(shù)語(yǔ)1.3算法和算法分析

1.4C語(yǔ)言基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第5頁(yè)。1.1什么是數(shù)據(jù)結(jié)構(gòu)從一個(gè)簡(jiǎn)單的學(xué)生檔案管理系統(tǒng)入手，引入數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念。問(wèn)題描述：學(xué)生檔案管理系統(tǒng)的主要功能包括：輸入、修改、插入、刪除、查找學(xué)生檔案，并進(jìn)行數(shù)據(jù)的統(tǒng)計(jì)(如統(tǒng)計(jì)男、女生比例等)。將存儲(chǔ)順序與邏輯順序保持一致的存儲(chǔ)結(jié)構(gòu)就是順序存儲(chǔ)結(jié)構(gòu)，如圖1-2所示，而在用鏈表存儲(chǔ)信息時(shí)，信息在內(nèi)存中存儲(chǔ)的順序與邏輯順序不要求一致。它是通過(guò)為每一條記錄增加一個(gè)存儲(chǔ)下一個(gè)學(xué)生信息地址的信息項(xiàng)來(lái)表示學(xué)生的次序，這就是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，如圖1-3所示。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第6頁(yè)。1.1什么是數(shù)據(jù)結(jié)構(gòu)圖1-3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第7頁(yè)。1.2基本概念和術(shù)語(yǔ)(1)數(shù)據(jù)(2)數(shù)據(jù)元素(3)數(shù)據(jù)項(xiàng)(4)數(shù)據(jù)邏輯結(jié)構(gòu)

(5)數(shù)據(jù)物理結(jié)構(gòu)(6)數(shù)據(jù)類(lèi)型數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第8頁(yè)。(1)數(shù)據(jù)指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第9頁(yè)。(2)數(shù)據(jù)元素在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理的基本數(shù)據(jù)單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，也可以只由一個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素又被稱(chēng)為元素、結(jié)點(diǎn)或記錄。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專(zhuān)ppt課件數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第10頁(yè)。(3)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也被稱(chēng)字段或域。學(xué)生檔案信息表中每一行記錄了一個(gè)學(xué)生的檔案信息，在數(shù)據(jù)操作中作為一個(gè)整體考慮，對(duì)應(yīng)為一個(gè)數(shù)據(jù)元素。這個(gè)記錄中包含有學(xué)號(hào)、姓名、性別等若干個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)操作的基本單位是數(shù)據(jù)元素，如學(xué)生的插入或刪除一定是對(duì)應(yīng)于一個(gè)學(xué)生的全部信息，而不是對(duì)應(yīng)于其中的某個(gè)數(shù)據(jù)項(xiàng)。結(jié)論：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)實(shí)際上反映了數(shù)據(jù)組織的三個(gè)層次：數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成，而數(shù)據(jù)元素又可以由一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第11頁(yè)。(4)數(shù)據(jù)邏輯結(jié)構(gòu)1)線(xiàn)性結(jié)構(gòu)。

2)非線(xiàn)性結(jié)構(gòu)。

①樹(shù)形結(jié)構(gòu)是指該結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系，如圖1-5b所示。其特點(diǎn)是該結(jié)構(gòu)中除了有一個(gè)被稱(chēng)為根的結(jié)點(diǎn)沒(méi)有前趨外，其余元素有且只有一個(gè)直接前趨，可以有多個(gè)后繼。

②圖形結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu))是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間存在多對(duì)多聯(lián)系，如圖1-5c所示。其特點(diǎn)是該結(jié)構(gòu)中任何元素都可以有多個(gè)直接前趨，也可以有多個(gè)后繼。是指數(shù)據(jù)元素之間的抽象關(guān)聯(lián)方式。數(shù)據(jù)元素之間存在的一種或多種特定的關(guān)系被稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第12頁(yè)。(4)數(shù)據(jù)邏輯結(jié)構(gòu)圖1-4例1-2的邏輯結(jié)構(gòu)表示圖數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第13頁(yè)。圖1-5三種基本邏輯結(jié)構(gòu)

a)線(xiàn)性結(jié)構(gòu)b)樹(shù)形結(jié)構(gòu)c)圖形結(jié)構(gòu)(4)數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第14頁(yè)。(4)數(shù)據(jù)邏輯結(jié)構(gòu)圖1-6例1-3邏輯結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第15頁(yè)。(5)數(shù)據(jù)物理結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存放方式稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)，簡(jiǎn)稱(chēng)存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)元素在計(jì)算機(jī)中主要有兩種不同的存儲(chǔ)方法：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第16頁(yè)。(6)數(shù)據(jù)類(lèi)型在用高級(jí)語(yǔ)言編寫(xiě)的程序中，所有的變量、常量或表達(dá)式都具有確定的數(shù)據(jù)類(lèi)型。數(shù)據(jù)類(lèi)型包含了數(shù)據(jù)的取值范圍及基本操作運(yùn)算，可以這樣認(rèn)為：數(shù)據(jù)類(lèi)型是程序設(shè)計(jì)語(yǔ)言中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第17頁(yè)。1.3算法和算法分析1.3.1算法及其描述

1.3.2算法性能和復(fù)雜度分析數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第18頁(yè)。1.3.1算法及其描述1.算法的定義及其特征

2.算法的描述方法數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第19頁(yè)。1.算法的定義及其特征1)正確性。算法必須解決具體的問(wèn)題，完成所期望的功能，給出正確的輸出。2)確定性。算法執(zhí)行的每一步和下一步必須確定，不能有二義性。3)有限性。一個(gè)算法必須由有限步組成。無(wú)限步組成的算法無(wú)法用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)，因此算法必須可以終止，不能進(jìn)入死循環(huán)。4)輸入。一個(gè)算法有零個(gè)或多個(gè)輸入。5)輸出。一個(gè)算法有一個(gè)或多個(gè)輸出。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第20頁(yè)。2.算法的描述方法(1)圖形工具用一些基本符號(hào)表示處理、輸入、輸出等操作，比較流行的框圖有傳統(tǒng)流程圖和結(jié)構(gòu)化流程圖，如圖1-7所示，其優(yōu)點(diǎn)是直觀、易懂。圖1-7流程圖

a)傳統(tǒng)流程圖b)結(jié)構(gòu)化流程圖數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第21頁(yè)。2.算法的描述方法圖1-8例1-4流程圖

a)傳統(tǒng)流程圖b)結(jié)構(gòu)化流程圖數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第22頁(yè)。2.算法的描述方法(2)偽語(yǔ)言描述偽語(yǔ)言與高級(jí)程序設(shè)計(jì)語(yǔ)言有些類(lèi)似，有比較嚴(yán)格的外語(yǔ)法，如用if…else…表示選擇結(jié)構(gòu)，用while表示循環(huán)結(jié)構(gòu)，對(duì)內(nèi)語(yǔ)法如變量定義等無(wú)明確要求。

(3)C語(yǔ)言編寫(xiě)的程序或函數(shù)這是可在計(jì)算機(jī)上運(yùn)行并獲得結(jié)果的算法，使給定問(wèn)題能在有限時(shí)間內(nèi)被求解，通常這種算法也稱(chēng)程序。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第23頁(yè)。1.3.2算法性能和復(fù)雜度分析解決一個(gè)問(wèn)題可以有多種算法。例如對(duì)一組數(shù)據(jù)排序，可給出6種甚至更多種排序算法，有的排序算法適合于元素個(gè)數(shù)少的序列，有的適合于元素個(gè)數(shù)多的序列，有的則適合于基本有序的排序。因此在一個(gè)算法設(shè)計(jì)好以后，還需要對(duì)其進(jìn)行分析，確定一個(gè)“好”的算法。下面討論算法設(shè)計(jì)的目標(biāo)和算法分析的方法。

1)正確性。

2)易讀性。

3)健壯性。

①合法輸入。當(dāng)輸入的三條邊a，b，c滿(mǎn)足構(gòu)成三角形的條件(a+b>c，a+c>b，b+c>a)時(shí)，算法應(yīng)能得到正常的結(jié)果。

②非法輸入。當(dāng)輸入的三條邊a，b，c有不滿(mǎn)足構(gòu)成三角形的條件(a+b>c，a+c>b，b+c>a)時(shí)，算法應(yīng)給出相應(yīng)的提示信息。

4)高效率。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第24頁(yè)。1.4C語(yǔ)言基礎(chǔ)1.4.1數(shù)組

1.4.2指針

1.4.3結(jié)構(gòu)體類(lèi)型

1.4.4C程序的調(diào)試方法數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第25頁(yè)。1.4.1數(shù)組1.一維數(shù)組的定義

2.一維數(shù)組元素的引用數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第26頁(yè)。1.一維數(shù)組的定義1)數(shù)組名的命名規(guī)則與普通變量名相同。

2)常量表達(dá)式表示數(shù)組元素的個(gè)數(shù)，用方括號(hào)括起來(lái)。

3)定義了一維數(shù)組后，系統(tǒng)給該一維數(shù)組分配一組連續(xù)的存儲(chǔ)空間，數(shù)組名表示該段存儲(chǔ)空間的首地址。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第27頁(yè)。2.一維數(shù)組元素的引用1)數(shù)組不能整體引用，必須單個(gè)引用。

2)數(shù)組元素的下標(biāo)可以是常量、變量或表達(dá)式。

3)C程序規(guī)定，數(shù)組元素下標(biāo)的下界為0，上界為數(shù)組長(zhǎng)度減1。

4)人們習(xí)慣使用單循環(huán)(for循環(huán)結(jié)構(gòu))，通過(guò)控制循環(huán)變量對(duì)一維數(shù)組進(jìn)行訪(fǎng)問(wèn)。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第28頁(yè)。1.4.2指針1.指針變量定義

2.指針引用

3.指針與數(shù)組

4.指針作為函數(shù)參數(shù)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第29頁(yè)。1.指針變量定義1)“*”表示其后定義的變量是一個(gè)指針變量。

2)基類(lèi)型表示指針變量所指向的數(shù)據(jù)類(lèi)型，即一個(gè)指針變量只能存儲(chǔ)同一種數(shù)據(jù)類(lèi)型變量的地址。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第30頁(yè)。2.指針引用1)取址運(yùn)算符&，其作用是獲取變量所占用的存儲(chǔ)單元的首地址。

2)間接訪(fǎng)問(wèn)運(yùn)算符?，其作用是通過(guò)指針變量訪(fǎng)問(wèn)它所指向的變量。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第31頁(yè)。3.指針與數(shù)組數(shù)組名代表數(shù)組首地址，屬指針常量。用指針變量訪(fǎng)問(wèn)數(shù)組更加靈活、方便。用指針變量p訪(fǎng)問(wèn)數(shù)組a比較方便，p+2表示數(shù)組元素a［2］的地址，*(p+2)與a［2］等價(jià)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第32頁(yè)。4.指針作為函數(shù)參數(shù)指針作為函數(shù)參數(shù)的作用是將一個(gè)變量的地址傳遞到函數(shù)的指針變量形參，共享對(duì)應(yīng)的實(shí)參的存儲(chǔ)單元，因此形參值的改變將引起實(shí)參值的改變。由于數(shù)組名代表指針常量，因此指針作函數(shù)參數(shù)，通常與數(shù)組的操作相關(guān)。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第33頁(yè)。1.4.3結(jié)構(gòu)體類(lèi)型1.結(jié)構(gòu)體類(lèi)型的定義

2.結(jié)構(gòu)體變量的定義

3.結(jié)構(gòu)體成員的引用

4.指向結(jié)構(gòu)體的指針變量數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第34頁(yè)。1.結(jié)構(gòu)體類(lèi)型的定義1)上述形式定義的結(jié)構(gòu)體類(lèi)型名為structstudent，而非student。

2)若想為結(jié)構(gòu)體類(lèi)型定義一個(gè)簡(jiǎn)單的名稱(chēng)，可使用typedef命令。

3)typedef命令的功能是給一種數(shù)據(jù)類(lèi)型取個(gè)別名，命令格式為：

4)結(jié)構(gòu)體類(lèi)型在定義時(shí)，可直接使用typedef為自定義數(shù)據(jù)類(lèi)型取名。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第35頁(yè)。2.結(jié)構(gòu)體變量的定義如同標(biāo)準(zhǔn)數(shù)據(jù)類(lèi)型int一樣，自定義數(shù)據(jù)類(lèi)型后，并沒(méi)有在內(nèi)存開(kāi)辟存儲(chǔ)空間，必須定義變量才能引用其成員數(shù)據(jù)項(xiàng)。結(jié)構(gòu)體變量占用實(shí)際內(nèi)存的大小可用sizeof(變量名|類(lèi)型名)函數(shù)求出。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第36頁(yè)。3.結(jié)構(gòu)體成員的引用1)結(jié)構(gòu)體變量的成員可以看成是與普通變量一樣進(jìn)行各種運(yùn)算。

2)結(jié)構(gòu)體成員本身是一個(gè)結(jié)構(gòu)體類(lèi)型時(shí)，可以通過(guò)逐層分解的方法找到最低層的成員。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第37頁(yè)。4.指向結(jié)構(gòu)體的指針變量指向結(jié)構(gòu)體的指針變量定義格式為：結(jié)構(gòu)體類(lèi)型名*指針變量名；數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第38頁(yè)。1.4.4C程序的調(diào)試方法由于程序中存在著分支、循環(huán)等結(jié)構(gòu)及復(fù)雜數(shù)據(jù)類(lèi)型，因此造成了程序運(yùn)行時(shí)的變化規(guī)律和其靜態(tài)結(jié)構(gòu)之間存在著一定的差異。數(shù)據(jù)結(jié)構(gòu)中所描述的數(shù)據(jù)及算法比較復(fù)雜，程序規(guī)模也比一般C語(yǔ)言程序要大，因此僅靠閱讀程序很難掌握程序運(yùn)行過(guò)程中各變量值的動(dòng)態(tài)變化，這就給程序調(diào)試帶來(lái)了很大的困難。如果能夠在程序運(yùn)行過(guò)程中動(dòng)態(tài)地顯示程序執(zhí)行的流向和各變量的值，將有助于讀者了解程序的動(dòng)態(tài)運(yùn)行情況，從而更好、更快地調(diào)試程序。本書(shū)附錄1介紹了TurboC集成環(huán)境下的調(diào)試手段。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程全文共41頁(yè)，當(dāng)前為第39頁(yè)。1.填空題線(xiàn)性結(jié)構(gòu)中，元素之間存在___關(guān)系；樹(shù)形結(jié)構(gòu)中，元素之間存在___關(guān)系；圖形結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu))中，元素之間存在___關(guān)系。

(2)算法的五個(gè)基本特征是：___。(3)評(píng)價(jià)算法的性能從算法效率的角度看主要從__及__進(jìn)行分析