數(shù)據(jù)結構與算法應用教程

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

1.2基本概念和術語1.3算法和算法分析

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

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

2)非線性結構。

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

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

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

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

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

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

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

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

1)正確性。

2)易讀性。

3)健壯性。

①合法輸入。當輸入的三條邊a，b，c滿足構成三角形的條件(a+b>c，a+c>b，b+c>a)時，算法應能得到正常的結果。

②非法輸入。當輸入的三條邊a，b，c有不滿足構成三角形的條件(a+b>c，a+c>b，b+c>a)時，算法應給出相應的提示信息。

4)高效率。數(shù)據(jù)結構與算法應用教程全文共41頁，當前為第24頁。1.4C語言基礎1.4.1數(shù)組

1.4.2指針

1.4.3結構體類型

1.4.4C程序的調試方法數(shù)據(jù)結構與算法應用教程全文共41頁，當前為第25頁。1.4.1數(shù)組1.一維數(shù)組的定義

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

2)常量表達式表示數(shù)組元素的個數(shù)，用方括號括起來。

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

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

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

4)人們習慣使用單循環(huán)(for循環(huán)結構)，通過控制循環(huán)變量對一維數(shù)組進行訪問。數(shù)據(jù)結構與算法應用教程全文共41頁，當前為第28頁。1.4.2指針1.指針變量定義

2.指針引用

3.指針與數(shù)組

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

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

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

2.結構體變量的定義

3.結構體成員的引用

4.指向結構體的指針變量數(shù)據(jù)結構與算法應用教程全文共41頁，當前為第34頁。1.結構體類型的定義1)上述形式定義的結構體類型名為structstudent，而非student。

2)若想為結構體類型定義一個簡單的名稱，可使用typedef命令。

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

4)結構體類型在定義時，可直接使用typedef為自定義數(shù)據(jù)類型取名。數(shù)據(jù)結構與算法應用教程全文共41頁，當前為第35頁。2.結構體變量的定義如同標準數(shù)據(jù)類型int一樣，自定義數(shù)據(jù)類型后，并沒有在內存開辟存儲空間，必須定義變量才能引用其成員數(shù)據(jù)項。結構體變量占用實際內存的大小可用sizeof(變量名|類型名)函數(shù)求出。數(shù)據(jù)結構與算法應用教程全文共41頁，當前為第36頁。3.結構體成員的引用1)結構體變量的成員可以看成是與普通變量一樣進行各種運算。

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

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