數(shù)據(jù)結(jié)構(gòu)一章緒論.ppt

第一章 緒論,11 基本術(shù)語(yǔ) 12 數(shù)據(jù)結(jié)構(gòu)的定義及研究的內(nèi)容 121 數(shù)據(jù)的邏輯結(jié)構(gòu) 122 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 123 數(shù)據(jù)的運(yùn)算 13 算法 131 算法的概念及特性 132 算法的描述 133 算法的評(píng)價(jià) 14 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義和目的,11 基本術(shù)語(yǔ) 數(shù)據(jù)（Data）是人們約定的符號(hào)，用它來(lái)表示客觀事物及其活動(dòng)，是信息的載體。數(shù)據(jù)是計(jì)算機(jī)程序加工處理的對(duì)象。 數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理，在不同的情況下，又可以稱為元素、結(jié)點(diǎn)、頂點(diǎn)或記錄。數(shù)據(jù)是由數(shù)據(jù)元素構(gòu)成的。 數(shù)據(jù)項(xiàng)（Data Item）是構(gòu)成數(shù)據(jù)元素不可分割的具有獨(dú)立含義的最小標(biāo)識(shí)單位。若數(shù)據(jù)元素可再分，則數(shù)據(jù)元素是由若干個(gè)數(shù)據(jù)項(xiàng)組成；如數(shù)據(jù)元素不可再分，數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)是同一概念，如整型數(shù)據(jù)就是不可再分的。 數(shù)據(jù)類型（Data Type）是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱。按值的不同特性，高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型可分為原子類型和結(jié)構(gòu)類型兩類。,第一章 緒論,12 數(shù)據(jù)結(jié)構(gòu)的定義及研究的內(nèi)容 數(shù)據(jù)結(jié)構(gòu)的定義及研究的內(nèi)容 數(shù)據(jù)結(jié)構(gòu)（Data Structure）：按照某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，用一定的存儲(chǔ)方式存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義一個(gè)運(yùn)算的集合，就稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)（Data Structure）。 數(shù)據(jù)結(jié)構(gòu)重點(diǎn)研究的內(nèi)容： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)：即數(shù)據(jù)之間的邏輯關(guān)系。 （2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：即數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。 （3）數(shù)據(jù)的運(yùn)算：即對(duì)數(shù)據(jù)施加的各種操作。,數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical Structure：的是數(shù)據(jù)元素之間的邏輯關(guān)系。它是人們根據(jù)實(shí)際問題的需要和問題本身所含數(shù)據(jù)之間的內(nèi)在聯(lián)系而抽象出來(lái)的數(shù)學(xué)模型，與如何利用計(jì)算機(jī)存儲(chǔ)和處理無(wú)關(guān)，所以被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。 由于數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)學(xué)模型，可以借助數(shù)學(xué)方法來(lái)表示，具體的可以用離散數(shù)學(xué)中關(guān)系代數(shù)的二元組表示： Data_Structure =（D，S） 通常取S中的一個(gè)關(guān)系rj來(lái)進(jìn)行討論，rj可以表示為數(shù)據(jù)元素的序偶的集合。如果集合中有序偶，表示數(shù)據(jù)元素di和dj之間有rj這種關(guān)系。 用二元組表示的數(shù)據(jù)的邏輯結(jié)構(gòu)，有如下的常用術(shù)語(yǔ) （1）前趨結(jié)點(diǎn)、后繼結(jié)點(diǎn)、相鄰結(jié)點(diǎn) （2）開始結(jié)點(diǎn)、終端結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn) 數(shù)據(jù)的邏輯結(jié)構(gòu)還能夠利用更形象的圖形表示,數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類： （1）線性結(jié)構(gòu)：經(jīng)典的線性結(jié)構(gòu)是線性表。 線性結(jié)構(gòu)的邏輯特征是：有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)，也就是說結(jié)構(gòu)中的數(shù)據(jù)元素間存在著一對(duì)一的相互關(guān)系。 （2）非線性結(jié)構(gòu)：經(jīng)典的非線性結(jié)構(gòu)有樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。 樹形結(jié)構(gòu)的邏輯特征是：有且僅有一個(gè)開始結(jié)點(diǎn)，可有若干個(gè)終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)，可以有若干個(gè)后繼結(jié)點(diǎn)，也就是說結(jié)構(gòu)中的數(shù)據(jù)元素間存在著一對(duì)多的層次關(guān)系。 圖形結(jié)構(gòu)的邏輯特征是：可有若干個(gè)開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)可以有若干個(gè)前趨結(jié)點(diǎn)和若干個(gè)后繼結(jié)點(diǎn)，也就是說結(jié)構(gòu)中的數(shù)據(jù)元素間存在著多對(duì)多的網(wǎng)狀關(guān)系。,表1.1 某校圍棋社團(tuán)學(xué)生簡(jiǎn)表,例1.1 在表1.1中，八名學(xué)生按學(xué)號(hào)從小到大排列，形成一個(gè)線性結(jié)構(gòu)。假設(shè)表示這種邏輯結(jié)構(gòu)的關(guān)系為r1，則r1可以定義為學(xué)生按學(xué)號(hào)順序遞增排列的關(guān)系，該線性結(jié)構(gòu)的邏輯結(jié)構(gòu)可用二元組表示為： L =（D，S），r1S D =01，02，03，04，05，06，07，08 r 1 =， ，,圖1.1 線性結(jié)構(gòu)的圖示,例1.2 在表1.1中，學(xué)生之間還存在著領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)關(guān)系，其中01號(hào)學(xué)生為團(tuán)長(zhǎng)，直接領(lǐng)導(dǎo)02和03號(hào)學(xué)生，他們分別是組長(zhǎng)，02號(hào)學(xué)生直接領(lǐng)導(dǎo)04和05號(hào)學(xué)生，03號(hào)學(xué)生直接領(lǐng)導(dǎo)06、07和08號(hào)學(xué)生，假設(shè)表示這種邏輯結(jié)構(gòu)的關(guān)系為r2，則r2可以定義為學(xué)生之間的領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)關(guān)系，該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)可用二元組表示為： T =（D，S），r2S D =01，02，03，04，05，06，07，08 r2 =， ， ,圖1.2 樹形結(jié)構(gòu)的圖示,例1.3 在表1.1中，學(xué)生之間還有好友關(guān)系，如01和02、03、05號(hào)是好友，02和04號(hào)是好友，03和05號(hào)是好友，04和05、06號(hào)是好友，06和07之間是好友，08無(wú)好友，假設(shè)表示這種邏輯結(jié)構(gòu)的關(guān)系為r3，則r3可以定義為學(xué)生之間的好友關(guān)系，該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)可用二元組表示為： G =（D，S），r3S D =01，02，03，04，05，06，07，08 r3 =，,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（Storage Structure），是指數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映射。 對(duì)于數(shù)據(jù)的邏輯結(jié)構(gòu)G =（D，S），在映射中，一方面要將數(shù)據(jù)集D中的數(shù)據(jù)元素存放到存儲(chǔ)器中，另一方面還要體現(xiàn)關(guān)系集S，常見的體現(xiàn)關(guān)系S的方式有顯示和隱含兩種。 常用的實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的方法有如下四種： 1順序存儲(chǔ) 2鏈接存儲(chǔ) 3索引存儲(chǔ) 4散列存儲(chǔ) 四種存儲(chǔ)方法，可以單獨(dú)使用，也可以組合起來(lái)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映象。同一種邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。針對(duì)具體的應(yīng)用，某種數(shù)據(jù)結(jié)構(gòu)選擇何種存儲(chǔ)結(jié)構(gòu)主要考慮運(yùn)算的方便及效率。 存儲(chǔ)結(jié)構(gòu)的描述：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，它是依賴于計(jì)算機(jī)語(yǔ)言的，因此可以借用高級(jí)語(yǔ)言中提供的數(shù)據(jù)類型（如數(shù)組、指針等）來(lái)描述它。,1順序存儲(chǔ) 基本思想是：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里。 數(shù)據(jù)元素間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，也就是說邏輯關(guān)系上相鄰物理位置上也相鄰，數(shù)據(jù)元素的邏輯次序與物理次序一致。這是一種隱含體現(xiàn)關(guān)系的存儲(chǔ)方法，關(guān)系隱含在存儲(chǔ)位置上。 數(shù)據(jù)元素在存儲(chǔ)區(qū)域中是連續(xù)存放的，這種存儲(chǔ)方法稱為順序存儲(chǔ)結(jié)構(gòu)（Sequential Storage Structure），通常用計(jì)算機(jī)高級(jí)語(yǔ)言中的數(shù)組來(lái)描述。 2鏈接存儲(chǔ) 基本思想是：通過附加指針域表示數(shù)據(jù)元素之間的關(guān)系。 這種存儲(chǔ)方法不要求邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)位置上也相鄰，數(shù)據(jù)元素間的邏輯關(guān)系是通過附加指示其他數(shù)據(jù)元素位置的地址信息（指針）而得到的，這是一種顯示體現(xiàn)關(guān)系的存儲(chǔ)方法。 數(shù)據(jù)元素在存儲(chǔ)區(qū)域中可以是連續(xù)的，也可以是不連續(xù)的，通常用計(jì)算機(jī)高級(jí)語(yǔ)言中的指針來(lái)描述，稱為鏈接存儲(chǔ)結(jié)構(gòu)（Linked Storage Structure）。 由于不要求存儲(chǔ)空間的連續(xù)性，很適合動(dòng)態(tài)存儲(chǔ)管理,例1.4 用上述兩種方法存儲(chǔ)有序序列A=（99， 123，134），假設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)字 節(jié)，即一個(gè)存儲(chǔ)單元為兩個(gè)字節(jié)。,圖1.4 關(guān)系的映像方法,3索引存儲(chǔ) 基本思想是：除了存儲(chǔ)數(shù)據(jù)元素，還要建立一個(gè)或若干個(gè)附加的索引表來(lái)標(biāo)識(shí)數(shù)據(jù)元素的地址。 索引表中的每一項(xiàng)稱為索引項(xiàng)，是用來(lái)標(biāo)識(shí)一個(gè)或一組數(shù)據(jù)元素的存儲(chǔ)位置。索引項(xiàng)一般形式為（關(guān)鍵字，地址），其中的關(guān)鍵字是用來(lái)標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。 若每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表為稠密索引（Dense Index）。若一組數(shù)據(jù)元素對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引（Sparse Index）。 索引存儲(chǔ)方法主要是用于實(shí)現(xiàn)快速查找而設(shè)計(jì)的一種存儲(chǔ)方式。 4散列存儲(chǔ) 基本思想是：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，通常稱為關(guān)鍵字地址轉(zhuǎn)換法。在此方法中需要設(shè)計(jì)一個(gè)散列函數(shù)，以關(guān)鍵字為自變量，散列函數(shù)值即為地址。 用這種存儲(chǔ)方法設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)最適合按關(guān)鍵字進(jìn)行查找，但數(shù)據(jù)元素之間的關(guān)系已經(jīng)無(wú)法在存儲(chǔ)結(jié)構(gòu)上體現(xiàn)。,數(shù)據(jù)的運(yùn)算 數(shù)據(jù)的運(yùn)算（也稱操作）是指對(duì)數(shù)據(jù)元素進(jìn)行加工和處理。 運(yùn)算的種類很多，具體視應(yīng)用的要求而設(shè)置運(yùn)算的種類。 對(duì)每種數(shù)據(jù)結(jié)構(gòu)設(shè)置一些基本運(yùn)算（操作），使得不同應(yīng)用都能通過這些操作實(shí)現(xiàn)對(duì)數(shù)據(jù)結(jié)構(gòu)的各種訪問，是數(shù)據(jù)結(jié)構(gòu)中研究的一個(gè)重要方面。數(shù)據(jù)結(jié)構(gòu)的基本操作一般包括查找、插入、刪除、更新、排序等。 這些基本運(yùn)算實(shí)際是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作，所謂抽象的操作，就是不涉及具體的應(yīng)用，只知道這些操作應(yīng)該完成的功能，但無(wú)須考慮“如何完成”。這些運(yùn)算的粒度很小，是構(gòu)造復(fù)雜運(yùn)算的基礎(chǔ)。 數(shù)據(jù)基本運(yùn)算的定義是基于數(shù)據(jù)的邏輯結(jié)構(gòu)，每種經(jīng)典的邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。 數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上而實(shí)現(xiàn)在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上的 。 數(shù)據(jù)的運(yùn)算是通過算法來(lái)描述的 。 在討論任何一種數(shù)據(jù)結(jié)構(gòu)時(shí)，都應(yīng)該將數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三方面看成一個(gè)整體，不要孤立地理解一個(gè)方面，而要注意它們之間的聯(lián)系,13 算法 算法的概念及特性 算法（Algorithm）是解決特定問題的方法和步驟，是由若干條指令組成的有限序列。 一個(gè)算法必須具有以下五個(gè)特性： （1）有窮性：對(duì)于任意一組合法輸入值，一個(gè)算法必須總是在執(zhí)行有窮步驟后結(jié)束，有限時(shí)間內(nèi)完成。 （2）確定性：算法中每條指令都確切地規(guī)定了所應(yīng)執(zhí)行的操作，使算法的執(zhí)行者或閱讀者能明確其含義及如何執(zhí)行，不致產(chǎn)生二義性或多義性；另外，在同一條件下，一個(gè)算法只能有一條執(zhí)行路徑。 （3）可行性：算法中的每一步都是可行的，都可以通過手工或機(jī)器可以接受的有限次操作在有限時(shí)間內(nèi)完成。 （4）輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，這些輸入是算法所需的初始量或待處理的對(duì)象，來(lái)自某個(gè)特定的對(duì)象集合。 （5）輸出：一個(gè)算法有1個(gè)或多個(gè)輸出，這些輸出與輸入有著某種特定的關(guān)系。,算法的描述 算法一般可以采用自然語(yǔ)言、程序流程圖、偽碼、高級(jí)程序設(shè)計(jì)語(yǔ)言等描述。 算法的評(píng)價(jià) 通常從定性和定量?jī)煞矫鎭?lái)評(píng)價(jià)一個(gè)算法 算法的定性評(píng)價(jià)，是從算法的設(shè)計(jì)者和使用者角度來(lái)衡量?jī)?yōu)劣的 （1）正確性（Correctness）是指算法應(yīng)當(dāng)滿足具體問題的需求，即對(duì)合理的輸入，算法都會(huì)得出正確的結(jié)果，這是設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的首要條件，否則其他的評(píng)價(jià)標(biāo)準(zhǔn)也就無(wú)從談起。 （2）可讀性（Readablity）是指算法被理解的難易程度。 （3）健壯性（Robustness）是指算法對(duì)輸入的非法數(shù)據(jù)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理的能力。 （4）簡(jiǎn)單性（Simplicity）是指一個(gè)算法所采用的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及處理過程的簡(jiǎn)單程度。,算法的定量評(píng)價(jià) （1）時(shí)間復(fù)雜度（Time Complexity）是一個(gè)算法運(yùn)行時(shí)所耗費(fèi)的系統(tǒng)時(shí)間，也就是算法的時(shí)間效率。 每條語(yǔ)句重復(fù)執(zhí)行的次數(shù)稱為語(yǔ)句的頻度（Frenquency count） 當(dāng)不考慮算法運(yùn)行的軟硬件環(huán)境時(shí)，算法所耗費(fèi)的時(shí)間就是該算法中所有簡(jiǎn)單語(yǔ)句的頻度之和。 一般情況，在討論算法的時(shí)間效率時(shí)，主要考慮當(dāng)問題規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)，亦稱為算法的漸近時(shí)間復(fù)雜度，則T(n)= O(f(n) 。 記號(hào)“O”是一個(gè)數(shù)學(xué)符號(hào)，其數(shù)學(xué)定義是： 設(shè)T(n)和f(n)均為正整數(shù)n的函數(shù)，若存在兩個(gè)正整數(shù)M和n0，使得當(dāng)nn0時(shí)，都有 | T(n)| M | f(n)| 存在，則T(n)= O(f(n)。,在多數(shù)情況下，當(dāng)一個(gè)算法中有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套循環(huán)中最內(nèi)層循環(huán)語(yǔ)句的頻度決定的。需要注意的是，如果算法中包括對(duì)其他函數(shù)或算法的調(diào)用，計(jì)算算法的時(shí)間復(fù)雜度時(shí)還要分析被調(diào)用算法或函數(shù)的時(shí)間復(fù)雜度。,例1.5 求一維數(shù)組元素中的最大值 int sum(int a,int n) int i,s; （1） s= a0; /*1次*/ （2） for(i=1;in; i+; ) /*n次*/ （3） if (s ai) s= ai; /*n-1次*/ （4） return s; /*1次*/ T1(n)= 1+n+n-1+1=2n+1 T1(n)=O(n) ，即f(n)=n,例1.6 兩個(gè)n階方陣相加 void Matrixadd(int a ,int b ,int c ,int n) int i,j; （1） for (i=0;in;i+) /*n+1次*/ （2） for (j=0;jn;j+) /* n(n+1)次*/ （3） cij=aij+bij; /* n2次*/ T2(n)= n+1+ n(n+1)+ n2=2n2+2n+1 T2(n)=O(n2)，即f(n)=n2,例1.7 求兩個(gè)n階方陣的乘積 void Matrixmlt(int a ,int b ,int c ,int n) int i,j,k; （1） for (i=0;in;i+) /*n+1次*/ （2） for (j=0;jn;j+) /* n(n+1)次*/ （3） cij=0; /* n2次*/ （4） for (k=0;kn;k+) /* n2(n+1)次*/ （5） cij= cij+aik*bkj; /* n3次*/ T3(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1 T3(n)= O(n3) ，即f(n)=n3,最好時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 例1.8 在一維數(shù)組中查找指定的元素 int search(int a,int x,int n) int i; （1） for(i=0;in; i+; ) （2） i