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

數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程第1頁，共41頁，2023年，2月20日，星期五數(shù)據(jù)結(jié)構(gòu)與算法實(shí)用教程主編高佳琴數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第2頁，共41頁，2023年，2月20日，星期五第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語言指針的定義、指針的基本操作、動(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)用教程高職高專ppt課件第3頁，共41頁，2023年，2月20日，星期五1)從具體問題分析入手找出解決該問題的方法(數(shù)據(jù)模型)。2)設(shè)計(jì)解決該問題的具體步驟(算法)。3)選擇程序設(shè)計(jì)語言和數(shù)據(jù)類型，編寫代碼(源程序)，源程序經(jīng)編譯后得到可直接運(yùn)行的程序(目標(biāo)程序)。第1章概述圖1-1計(jì)算機(jī)解決問題的一般步驟數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第4頁，共41頁，2023年，2月20日，星期五第1章概述1.1什么是數(shù)據(jù)結(jié)構(gòu)

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

1.4C語言基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第5頁，共41頁，2023年，2月20日，星期五1.1什么是數(shù)據(jù)結(jié)構(gòu)從一個(gè)簡單的學(xué)生檔案管理系統(tǒng)入手，引入數(shù)據(jù)結(jié)構(gòu)的相關(guā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ǔ)的順序與邏輯順序不要求一致。它是通過為每一條記錄增加一個(gè)存儲(chǔ)下一個(gè)學(xué)生信息地址的信息項(xiàng)來表示學(xué)生的次序，這就是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，如圖1-3所示。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第6頁，共41頁，2023年，2月20日，星期五1.1什么是數(shù)據(jù)結(jié)構(gòu)圖1-3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第7頁，共41頁，2023年，2月20日，星期五1.2基本概念和術(shù)語(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ù)類型數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第8頁，共41頁，2023年，2月20日，星期五(1)數(shù)據(jù)指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第9頁，共41頁，2023年，2月20日，星期五(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ù)元素又被稱為元素、結(jié)點(diǎn)或記錄。數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用教程高職高專ppt課件第10頁，共41頁，2023年，2月20日，星期五(3)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也被稱字段或域。學(xué)生檔案信息表中每一行記錄了一個(gè)學(xué)生的檔案信息，在數(shù)據(jù)操作中作為一個(gè)整體考慮，對應(yīng)為一個(gè)數(shù)據(jù)元素。這個(gè)記錄中包含有學(xué)號(hào)、姓名、性別等若干個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)操作的基本單位是數(shù)據(jù)元素，如學(xué)生的插入或刪除一定是對應(yīng)于一個(gè)學(xué)生的全部信息，而不是對應(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)組成。第11頁，共41頁，2023年，2月20日，星期五(4)數(shù)據(jù)邏輯結(jié)構(gòu)1)線性結(jié)構(gòu)。

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

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

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

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

1.3.2算法性能和復(fù)雜度分析第18頁，共41頁，2023年，2月20日，星期五1.3.1算法及其描述1.算法的定義及其特征

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

a)傳統(tǒng)流程圖b)結(jié)構(gòu)化流程圖第21頁，共41頁，2023年，2月20日，星期五2.算法的描述方法圖1-8例1-4流程圖

a)傳統(tǒng)流程圖b)結(jié)構(gòu)化流程圖第22頁，共41頁，2023年，2月20日，星期五2.算法的描述方法(2)偽語言描述偽語言與高級(jí)程序設(shè)計(jì)語言有些類似，有比較嚴(yán)格的外語法，如用if…else…表示選擇結(jié)構(gòu)，用while表示循環(huán)結(jié)構(gòu)，對內(nèi)語法如變量定義等無明確要求。

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

1)正確性。

2)易讀性。

3)健壯性。

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

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

4)高效率。第24頁，共41頁，2023年，2月20日，星期五1.4C語言基礎(chǔ)1.4.1數(shù)組

1.4.2指針

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

1.4.4C程序的調(diào)試方法第25頁，共41頁，2023年，2月20日，星期五1.4.1數(shù)組1.一維數(shù)組的定義

2.一維數(shù)組元素的引用第26頁，共41頁，2023年，2月20日，星期五1.一維數(shù)組的定義1)數(shù)組名的命名規(guī)則與普通變量名相同。

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

3)定義了一維數(shù)組后，系統(tǒng)給該一維數(shù)組分配一組連續(xù)的存儲(chǔ)空間，數(shù)組名表示該段存儲(chǔ)空間的首地址。第27頁，共41頁，2023年，2月20日，星期五2.一維數(shù)組元素的引用1)數(shù)組不能整體引用，必須單個(gè)引用。

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

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

4)人們習(xí)慣使用單循環(huán)(for循環(huán)結(jié)構(gòu))，通過控制循環(huán)變量對一維數(shù)組進(jìn)行訪問。第28頁，共41頁，2023年，2月20日，星期五1.4.2指針1.指針變量定義

2.指針引用

3.指針與數(shù)組

4.指針作為函數(shù)參數(shù)第29頁，共41頁，2023年，2月20日，星期五1.指針變量定義1)“*”表示其后定義的變量是一個(gè)指針變量。

2)基類型表示指針變量所指向的數(shù)據(jù)類型，即一個(gè)指針變量只能存儲(chǔ)同一種數(shù)據(jù)類型變量的地址。第30頁，共41頁，2023年，2月20日，星期五2.指針引用1)取址運(yùn)算符&，其作用是獲取變量所占用的存儲(chǔ)單元的首地址。

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

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

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

4.指向結(jié)構(gòu)體的指針變量第34頁，共41頁，2023年，2月20日，星期五1.結(jié)構(gòu)體類型的定義1)上述形式定義的結(jié)構(gòu)體類型名為structstudent，而非student。

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

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

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

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

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