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

1、第一章第一章 緒論緒論11 根本術(shù)語(yǔ)根本術(shù)語(yǔ)12 數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容121 數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)的邏輯構(gòu)造122 數(shù)據(jù)的存儲(chǔ)構(gòu)造數(shù)據(jù)的存儲(chǔ)構(gòu)造123 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算13 算法算法131 算法的概念及特性算法的概念及特性132 算法的描畫(huà)算法的描畫(huà)133 算法的評(píng)價(jià)算法的評(píng)價(jià)14 學(xué)習(xí)數(shù)據(jù)構(gòu)造的意義和目的學(xué)習(xí)數(shù)據(jù)構(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)展思索和處置，在不同的情況下

2、，又可以稱(chēng)為元素、結(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è)數(shù)據(jù)元素可再分，那么數(shù)據(jù)元素是由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成；如數(shù)據(jù)元素不可再分，數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)是同一概念，如整型數(shù)據(jù)就是不可再分的。 數(shù)據(jù)類(lèi)型Data Type是一個(gè)值的集合和定義在這個(gè)值集上一組操作的總稱(chēng)。按值的不同特性，高級(jí)程序設(shè)計(jì)言語(yǔ)中的數(shù)據(jù)類(lèi)型可分為原子類(lèi)型和構(gòu)造類(lèi)型兩類(lèi)。 第一章第一章 緒論緒論12 數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容數(shù)據(jù)構(gòu)造Data Structure：按照某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，用一定的存儲(chǔ)方式存儲(chǔ)在計(jì)算

3、機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義一個(gè)運(yùn)算的集合，就稱(chēng)為一個(gè)數(shù)據(jù)構(gòu)造Data Structure。數(shù)據(jù)構(gòu)造重點(diǎn)研討的內(nèi)容：1數(shù)據(jù)的邏輯構(gòu)造：即數(shù)據(jù)之間的邏輯關(guān)系。2數(shù)據(jù)的存儲(chǔ)構(gòu)造：即數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。3數(shù)據(jù)的運(yùn)算：即對(duì)數(shù)據(jù)施加的各種操作。 數(shù)據(jù)的邏輯構(gòu)造 數(shù)據(jù)的邏輯構(gòu)造Logical Structure：的是數(shù)據(jù)元素之間的邏輯關(guān)系。它是人們根據(jù)實(shí)踐問(wèn)題的需求和問(wèn)題本身所含數(shù)據(jù)之間的內(nèi)在聯(lián)絡(luò)而籠統(tǒng)出來(lái)的數(shù)學(xué)模型，與如何利用計(jì)算機(jī)存儲(chǔ)和處置無(wú)關(guān)，所以被稱(chēng)為數(shù)據(jù)的邏輯構(gòu)造。由于數(shù)據(jù)的邏輯構(gòu)造是數(shù)學(xué)模型，可以借助數(shù)學(xué)方法來(lái)表示，詳細(xì)的可以用離散數(shù)學(xué)中關(guān)系代數(shù)的二元組表示：Dat

4、a_Structure =D，S通常取S中的一個(gè)關(guān)系rj來(lái)進(jìn)展討論，rj可以表示為數(shù)據(jù)元素的序偶的集合。假設(shè)集合中有序偶，表示數(shù)據(jù)元素di和dj之間有rj這種關(guān)系。用二元組表示的數(shù)據(jù)的邏輯構(gòu)造，有如下的常用術(shù)語(yǔ)1前趨結(jié)點(diǎn)、后繼結(jié)點(diǎn)、相鄰結(jié)點(diǎn)2開(kāi)場(chǎng)結(jié)點(diǎn)、終端結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)數(shù)據(jù)的邏輯構(gòu)造還可以利用更籠統(tǒng)的圖形表示 v數(shù)據(jù)的邏輯構(gòu)造有兩大類(lèi)：數(shù)據(jù)的邏輯構(gòu)造有兩大類(lèi)：v1線性構(gòu)造：經(jīng)典的線性構(gòu)造是線性表。線性構(gòu)造：經(jīng)典的線性構(gòu)造是線性表。v 線性構(gòu)造的邏輯特征是：有且僅有一個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)線性構(gòu)造的邏輯特征是：有且僅有一個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其他的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)

5、點(diǎn)，也就是，其他的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)，也就是說(shuō)構(gòu)造中的數(shù)據(jù)元素間存在著一對(duì)一的相互關(guān)系。說(shuō)構(gòu)造中的數(shù)據(jù)元素間存在著一對(duì)一的相互關(guān)系。v2非線性構(gòu)造：經(jīng)典的非線性構(gòu)造有樹(shù)形構(gòu)造和圖形構(gòu)造。非線性構(gòu)造：經(jīng)典的非線性構(gòu)造有樹(shù)形構(gòu)造和圖形構(gòu)造。v 樹(shù)形構(gòu)造的邏輯特征是：有且僅有一個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)，可有假設(shè)干樹(shù)形構(gòu)造的邏輯特征是：有且僅有一個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)，可有假設(shè)干個(gè)終端結(jié)點(diǎn)，其他的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)，可以有假設(shè)個(gè)終端結(jié)點(diǎn)，其他的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)，可以有假設(shè)干個(gè)后繼結(jié)點(diǎn)，也就是說(shuō)構(gòu)造中的數(shù)據(jù)元素間存在著一對(duì)多的層次關(guān)干個(gè)后繼結(jié)點(diǎn)，也就是說(shuō)構(gòu)造中的數(shù)據(jù)元素間存在著

6、一對(duì)多的層次關(guān)系。系。v 圖形構(gòu)造的邏輯特征是：可有假設(shè)干個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)和終端結(jié)點(diǎn)，圖形構(gòu)造的邏輯特征是：可有假設(shè)干個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)和終端結(jié)點(diǎn)，其他的內(nèi)部結(jié)點(diǎn)可以有假設(shè)干個(gè)前趨結(jié)點(diǎn)和假設(shè)干個(gè)后繼結(jié)點(diǎn)，也就其他的內(nèi)部結(jié)點(diǎn)可以有假設(shè)干個(gè)前趨結(jié)點(diǎn)和假設(shè)干個(gè)后繼結(jié)點(diǎn)，也就是說(shuō)構(gòu)造中的數(shù)據(jù)元素間存在著多對(duì)多的網(wǎng)狀關(guān)系。是說(shuō)構(gòu)造中的數(shù)據(jù)元素間存在著多對(duì)多的網(wǎng)狀關(guān)系。表1.1 某校圍棋社團(tuán)學(xué)生簡(jiǎn)表學(xué)號(hào)姓名性別出生日期職務(wù)01黃家正男1982-08-05團(tuán)長(zhǎng)02趙 芳女1981-08-15組長(zhǎng)03王 明女1983-04-01組長(zhǎng)04王 紅女1982-06-28組員05張小才男1984-03-17組員06馬立偉男1983

7、-10-12組員07孫 剛男1982-07-05組員08劉 永男1982-12-09組員 例例1.1 在表在表1.1中，八名學(xué)生按學(xué)號(hào)從小到大陳中，八名學(xué)生按學(xué)號(hào)從小到大陳列，構(gòu)成一個(gè)線性構(gòu)造。假設(shè)表示這種邏輯構(gòu)列，構(gòu)成一個(gè)線性構(gòu)造。假設(shè)表示這種邏輯構(gòu)造的關(guān)系為造的關(guān)系為r1，那么，那么r1可以定義為學(xué)生按學(xué)號(hào)可以定義為學(xué)生按學(xué)號(hào)順序遞增陳列的關(guān)系，該線性構(gòu)造的邏輯構(gòu)造順序遞增陳列的關(guān)系，該線性構(gòu)造的邏輯構(gòu)造可用二元組表示為：可用二元組表示為：L =D，S，r1SD =01，02，03，04，05，06，07，08 r 1 =， ，圖1.1 線性構(gòu)造的圖示 例例1.2 在表在表1.1中，學(xué)生之

8、間還存在著指點(diǎn)與被指中，學(xué)生之間還存在著指點(diǎn)與被指點(diǎn)關(guān)系，其中點(diǎn)關(guān)系，其中01號(hào)學(xué)生為團(tuán)長(zhǎng)，直接指點(diǎn)號(hào)學(xué)生為團(tuán)長(zhǎng)，直接指點(diǎn)02和和03號(hào)學(xué)生，他們分別是組長(zhǎng)，號(hào)學(xué)生，他們分別是組長(zhǎng)，02號(hào)學(xué)生直接指點(diǎn)號(hào)學(xué)生直接指點(diǎn)04和和05號(hào)學(xué)生，號(hào)學(xué)生，03號(hào)學(xué)生直接指點(diǎn)號(hào)學(xué)生直接指點(diǎn)06、07和和08號(hào)學(xué)生號(hào)學(xué)生，假設(shè)表示這種邏輯構(gòu)造的關(guān)系為，假設(shè)表示這種邏輯構(gòu)造的關(guān)系為r2，那么，那么r2可以可以定義為學(xué)生之間的指點(diǎn)與被指點(diǎn)關(guān)系，該數(shù)據(jù)構(gòu)造定義為學(xué)生之間的指點(diǎn)與被指點(diǎn)關(guān)系，該數(shù)據(jù)構(gòu)造的邏輯構(gòu)造可用二元組表示為：的邏輯構(gòu)造可用二元組表示為：T =D，S，r2SD =01，02，03，04，05，06，0

9、7，08r2 =， ， 0 10 20 30 40 50 60 70 8圖1.2 樹(shù)形構(gòu)造的圖示例例1.3 在表在表1.1中，學(xué)生之間還有好友關(guān)系，如中，學(xué)生之間還有好友關(guān)系，如01和和02、03、05號(hào)是好友，號(hào)是好友，02和和04號(hào)是好友，號(hào)是好友，03和和05號(hào)是好友，號(hào)是好友，04和和05、06號(hào)是好友，號(hào)是好友，06和和07之間是好友，之間是好友，08無(wú)好友，假設(shè)表示無(wú)好友，假設(shè)表示這種邏輯構(gòu)造的關(guān)系為這種邏輯構(gòu)造的關(guān)系為r3，那么，那么r3可以定義為學(xué)生之間的好可以定義為學(xué)生之間的好友關(guān)系，該數(shù)據(jù)構(gòu)造的邏輯構(gòu)造可用二元組表示為：友關(guān)系，該數(shù)據(jù)構(gòu)造的邏輯構(gòu)造可用二元組表示為：G =D

10、，S，r3SD =01，02，03，04，05，06，07，08r3 =，數(shù)據(jù)的存儲(chǔ)構(gòu)造 數(shù)據(jù)的存儲(chǔ)構(gòu)造Storage Structure，是指數(shù)據(jù)的邏輯構(gòu)造到計(jì)算機(jī)存儲(chǔ)器的映射。對(duì)于數(shù)據(jù)的邏輯構(gòu)造G =D，S，在映射中，一方面要將數(shù)據(jù)集D中的數(shù)據(jù)元素存放到存儲(chǔ)器中，另一方面還要表達(dá)關(guān)系集S，常見(jiàn)的表達(dá)關(guān)系S的方式有顯示和隱含兩種。常用的實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)構(gòu)造的方法有如下四種：1順序存儲(chǔ)2鏈接存儲(chǔ)3索引存儲(chǔ)4散列存儲(chǔ)四種存儲(chǔ)方法，可以單獨(dú)運(yùn)用，也可以組合起來(lái)對(duì)數(shù)據(jù)構(gòu)造進(jìn)展存儲(chǔ)映象。同一種邏輯構(gòu)造采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)構(gòu)造。針對(duì)詳細(xì)的運(yùn)用，某種數(shù)據(jù)構(gòu)造選擇何種存儲(chǔ)構(gòu)造主要思索運(yùn)算的方便

11、及效率。存儲(chǔ)構(gòu)造的描畫(huà)：數(shù)據(jù)的存儲(chǔ)構(gòu)造是數(shù)據(jù)的邏輯構(gòu)造用計(jì)算機(jī)言語(yǔ)的實(shí)現(xiàn)，它是依賴(lài)于計(jì)算機(jī)言語(yǔ)的，因此可以借用高級(jí)言語(yǔ)中提供的數(shù)據(jù)類(lèi)型如數(shù)組、指針等來(lái)描畫(huà)它。l1順序存儲(chǔ)順序存儲(chǔ)l根本思想是：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相鄰的根本思想是：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里。存儲(chǔ)單元里。l數(shù)據(jù)元素間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)表達(dá)，也就是說(shuō)數(shù)據(jù)元素間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)表達(dá)，也就是說(shuō)邏輯關(guān)系上相鄰物理位置上也相鄰，數(shù)據(jù)元素的邏輯次序與物理邏輯關(guān)系上相鄰物理位置上也相鄰，數(shù)據(jù)元素的邏輯次序與物理次序一致。這是一種隱含表達(dá)關(guān)系的存儲(chǔ)方法，關(guān)系隱含在存儲(chǔ)次

12、序一致。這是一種隱含表達(dá)關(guān)系的存儲(chǔ)方法，關(guān)系隱含在存儲(chǔ)位置上。位置上。 l數(shù)據(jù)元素在存儲(chǔ)區(qū)域中是延續(xù)存放的，這種存儲(chǔ)方法稱(chēng)為順序存數(shù)據(jù)元素在存儲(chǔ)區(qū)域中是延續(xù)存放的，這種存儲(chǔ)方法稱(chēng)為順序存儲(chǔ)構(gòu)造儲(chǔ)構(gòu)造Sequential Storage Structure，通常用計(jì)算機(jī)高級(jí)，通常用計(jì)算機(jī)高級(jí)言語(yǔ)中的數(shù)組來(lái)描畫(huà)。言語(yǔ)中的數(shù)組來(lái)描畫(huà)。 l2鏈接存儲(chǔ)鏈接存儲(chǔ)l根本思想是：經(jīng)過(guò)附加指針域表示數(shù)據(jù)元素之間的關(guān)系。根本思想是：經(jīng)過(guò)附加指針域表示數(shù)據(jù)元素之間的關(guān)系。l這種存儲(chǔ)方法不要求邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)位置上也相鄰，這種存儲(chǔ)方法不要求邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)位置上也相鄰，數(shù)據(jù)元素間的邏輯關(guān)系是經(jīng)過(guò)附加指

13、示其他數(shù)據(jù)元素位置的地址數(shù)據(jù)元素間的邏輯關(guān)系是經(jīng)過(guò)附加指示其他數(shù)據(jù)元素位置的地址信息指針而得到的，這是一種顯示表達(dá)關(guān)系的存儲(chǔ)方法。信息指針而得到的，這是一種顯示表達(dá)關(guān)系的存儲(chǔ)方法。l數(shù)據(jù)元素在存儲(chǔ)區(qū)域中可以是延續(xù)的，也可以是不延續(xù)的，通常數(shù)據(jù)元素在存儲(chǔ)區(qū)域中可以是延續(xù)的，也可以是不延續(xù)的，通常用計(jì)算機(jī)高級(jí)言語(yǔ)中的指針來(lái)描畫(huà)，稱(chēng)為鏈接存儲(chǔ)構(gòu)造用計(jì)算機(jī)高級(jí)言語(yǔ)中的指針來(lái)描畫(huà)，稱(chēng)為鏈接存儲(chǔ)構(gòu)造Linked Storage Structure。 l由于不要求存儲(chǔ)空間的延續(xù)性，很適宜動(dòng)態(tài)存儲(chǔ)管理由于不要求存儲(chǔ)空間的延續(xù)性，很適宜動(dòng)態(tài)存儲(chǔ)管理 例例1.4 用上述兩種方法存儲(chǔ)有序序列用上述兩種方法存儲(chǔ)有序序

14、列A=99， 123，134，假設(shè)每個(gè)數(shù)據(jù)元素占，假設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)字個(gè)字 節(jié)，即一個(gè)存儲(chǔ)單元為兩個(gè)字節(jié)。節(jié)，即一個(gè)存儲(chǔ)單元為兩個(gè)字節(jié)。圖1.4 關(guān)系的映像方法l 3索引存儲(chǔ)索引存儲(chǔ)l 根本思想是：除了存儲(chǔ)數(shù)據(jù)元素，還要建立一個(gè)或假設(shè)干個(gè)附加的根本思想是：除了存儲(chǔ)數(shù)據(jù)元素，還要建立一個(gè)或假設(shè)干個(gè)附加的索引表來(lái)標(biāo)識(shí)數(shù)據(jù)元素的地址。索引表來(lái)標(biāo)識(shí)數(shù)據(jù)元素的地址。l 索引表中的每一項(xiàng)稱(chēng)為索引項(xiàng)，是用來(lái)標(biāo)識(shí)一個(gè)或一組數(shù)據(jù)元素的索引表中的每一項(xiàng)稱(chēng)為索引項(xiàng)，是用來(lái)標(biāo)識(shí)一個(gè)或一組數(shù)據(jù)元素的存儲(chǔ)位置。索引項(xiàng)普通方式為關(guān)鍵字，地址，其中的關(guān)鍵字是存儲(chǔ)位置。索引項(xiàng)普通方式為關(guān)鍵字，地址，其中的關(guān)鍵字是用來(lái)標(biāo)識(shí)數(shù)

15、據(jù)元素的數(shù)據(jù)項(xiàng)。用來(lái)標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。l 假設(shè)每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一個(gè)索引項(xiàng)，那么該索引表為稠密索引假設(shè)每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一個(gè)索引項(xiàng)，那么該索引表為稠密索引Dense Index。假設(shè)一組數(shù)據(jù)元素對(duì)應(yīng)一個(gè)索引項(xiàng)，那么該索引。假設(shè)一組數(shù)據(jù)元素對(duì)應(yīng)一個(gè)索引項(xiàng)，那么該索引表稱(chēng)為稀疏索引表稱(chēng)為稀疏索引Sparse Index。l 索引存儲(chǔ)方法主要是用于實(shí)現(xiàn)快速查找而設(shè)計(jì)的一種存儲(chǔ)方式。索引存儲(chǔ)方法主要是用于實(shí)現(xiàn)快速查找而設(shè)計(jì)的一種存儲(chǔ)方式。l 4散列存儲(chǔ)散列存儲(chǔ)l 根本思想是：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址根本思想是：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，通常稱(chēng)為關(guān)鍵字地址轉(zhuǎn)換

16、法。在此方法中需求設(shè)計(jì)一個(gè)散列函，通常稱(chēng)為關(guān)鍵字地址轉(zhuǎn)換法。在此方法中需求設(shè)計(jì)一個(gè)散列函數(shù)，以關(guān)鍵字為自變量，散列函數(shù)值即為地址。數(shù)，以關(guān)鍵字為自變量，散列函數(shù)值即為地址。l 用這種存儲(chǔ)方法設(shè)計(jì)的存儲(chǔ)構(gòu)造最適宜按關(guān)鍵字進(jìn)展查找，但數(shù)據(jù)用這種存儲(chǔ)方法設(shè)計(jì)的存儲(chǔ)構(gòu)造最適宜按關(guān)鍵字進(jìn)展查找，但數(shù)據(jù)元素之間的關(guān)系曾經(jīng)無(wú)法在存儲(chǔ)構(gòu)造上表達(dá)。元素之間的關(guān)系曾經(jīng)無(wú)法在存儲(chǔ)構(gòu)造上表達(dá)。 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算也稱(chēng)操作是指對(duì)數(shù)據(jù)元素進(jìn)展加工和處置。運(yùn)算的種類(lèi)很多，詳細(xì)視運(yùn)用的要求而設(shè)置運(yùn)算的種類(lèi)。對(duì)每種數(shù)據(jù)構(gòu)造設(shè)置一些根本運(yùn)算操作，使得不同運(yùn)用都能經(jīng)過(guò)這些操作實(shí)現(xiàn)對(duì)數(shù)據(jù)構(gòu)造的各種訪問(wèn)，是數(shù)據(jù)構(gòu)造中研討的一個(gè)重要方

17、面。數(shù)據(jù)構(gòu)造的根本操作普通包括查找、插入、刪除、更新、排序等。這些根本運(yùn)算實(shí)踐是在籠統(tǒng)的數(shù)據(jù)上所施加的一系列籠統(tǒng)的操作，所謂籠統(tǒng)的操作，就是不涉及詳細(xì)的運(yùn)用，只知道這些操作應(yīng)該完成的功能，但無(wú)須思索“如何完成。這些運(yùn)算的粒度很小，是構(gòu)造復(fù)雜運(yùn)算的根底。數(shù)據(jù)根本運(yùn)算的定義是基于數(shù)據(jù)的邏輯構(gòu)造，每種經(jīng)典的邏輯構(gòu)造都有一個(gè)運(yùn)算的集合。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯構(gòu)造上而實(shí)如今數(shù)據(jù)的存儲(chǔ)構(gòu)造上的 。 數(shù)據(jù)的運(yùn)算是經(jīng)過(guò)算法來(lái)描畫(huà)的 。在討論任何一種數(shù)據(jù)構(gòu)造時(shí)，都應(yīng)該將數(shù)據(jù)的邏輯構(gòu)造、數(shù)據(jù)的存儲(chǔ)構(gòu)造和數(shù)據(jù)的運(yùn)算這三方面看成一個(gè)整體，不要孤立地了解一個(gè)方面，而要留意它們之間的聯(lián)絡(luò) 13 算法算法的概念及特性

18、算法Algorithm是處理特定問(wèn)題的方法和步驟，是由假設(shè)干條指令組成的有限序列。一個(gè)算法必需具有以下五個(gè)特性：1有窮性：對(duì)于恣意一組合法輸入值，一個(gè)算法必需總是在執(zhí)行有窮步驟后終了，有限時(shí)間內(nèi)完成。2確定性：算法中每條指令都確切地規(guī)定了所應(yīng)執(zhí)行的操作，使算法的執(zhí)行者或閱讀者能明確其含義及如何執(zhí)行，不致產(chǎn)生二義性或多義性；另外，在同一條件下，一個(gè)算法只能有一條執(zhí)行途徑。3可行性：算法中的每一步都是可行的，都可以經(jīng)過(guò)手工或機(jī)器可以接受的有限次操作在有限時(shí)間內(nèi)完成。4輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，這些輸入是算法所需的初始量或待處置的對(duì)象，來(lái)自某個(gè)特定的對(duì)象集合。 5輸出：一個(gè)算法有1個(gè)或多個(gè)輸出

19、，這些輸出與輸入有著某種特定的關(guān)系。算法的描畫(huà)算法的描畫(huà) 算法普通可以采用自然言語(yǔ)、程序流程圖、偽碼、算法普通可以采用自然言語(yǔ)、程序流程圖、偽碼、高級(jí)程序設(shè)計(jì)言語(yǔ)等描畫(huà)。高級(jí)程序設(shè)計(jì)言語(yǔ)等描畫(huà)。算法的評(píng)價(jià)算法的評(píng)價(jià) 通常從定性和定量?jī)煞矫鎭?lái)評(píng)價(jià)一個(gè)算法通常從定性和定量?jī)煞矫鎭?lái)評(píng)價(jià)一個(gè)算法 算法的定性評(píng)價(jià)，是從算法的設(shè)計(jì)者和運(yùn)用者角度算法的定性評(píng)價(jià)，是從算法的設(shè)計(jì)者和運(yùn)用者角度來(lái)衡量?jī)?yōu)劣的來(lái)衡量?jī)?yōu)劣的 1正確性正確性Correctness是指算法該當(dāng)滿(mǎn)足是指算法該當(dāng)滿(mǎn)足詳細(xì)問(wèn)題的需求，即對(duì)合理的輸入，算法都會(huì)得出詳細(xì)問(wèn)題的需求，即對(duì)合理的輸入，算法都會(huì)得出正確的結(jié)果，這是設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的首要

20、條件正確的結(jié)果，這是設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的首要條件，否那么其他的評(píng)價(jià)規(guī)范也就無(wú)從談起。，否那么其他的評(píng)價(jià)規(guī)范也就無(wú)從談起。2可讀性可讀性Readablity是指算法被了解的難是指算法被了解的難易程度。易程度。3強(qiáng)壯性強(qiáng)壯性Robustness是指算法對(duì)輸入的非是指算法對(duì)輸入的非法數(shù)據(jù)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)展相應(yīng)處置的才干。法數(shù)據(jù)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)展相應(yīng)處置的才干。4簡(jiǎn)單性簡(jiǎn)單性Simplicity是指一個(gè)算法所采用的是指一個(gè)算法所采用的邏輯構(gòu)造、存儲(chǔ)構(gòu)造以及處置過(guò)程的簡(jiǎn)單程度。邏輯構(gòu)造、存儲(chǔ)構(gòu)造以及處置過(guò)程的簡(jiǎn)單程度。 l 算法的定量評(píng)價(jià)l1時(shí)間復(fù)雜度Time Complexity是一個(gè)算法運(yùn)轉(zhuǎn)時(shí)所

21、耗費(fèi)的系統(tǒng)時(shí)間，也就是算法的時(shí)間效率。 l每條語(yǔ)句反復(fù)執(zhí)行的次數(shù)稱(chēng)為語(yǔ)句的頻度Frenquency countl當(dāng)不思索算法運(yùn)轉(zhuǎn)的軟硬件環(huán)境時(shí)，算法所耗費(fèi)的時(shí)間就是該算法中一切簡(jiǎn)單語(yǔ)句的頻度之和。 l普通情況，在討論算法的時(shí)間效率時(shí)，主要思索當(dāng)問(wèn)題規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)，亦稱(chēng)為算法的漸近時(shí)間復(fù)雜度，那么T(n)= O(f(n) 。l 記號(hào)“O是一個(gè)數(shù)學(xué)符號(hào)，其數(shù)學(xué)定義是： l 設(shè)T(n)和f(n)均為正整數(shù)n的函數(shù)，假設(shè)存在兩個(gè)正整數(shù)M和n0，使得當(dāng)nn0時(shí)，都有 | T(n)| M | f(n)| 存在，那么T(n)= O(f(n)。lim T(n) / f(n) =

22、 Mnu在多數(shù)情況下，當(dāng)一個(gè)算法中有假設(shè)干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套循環(huán)中最內(nèi)層循環(huán)語(yǔ)句的頻度決議的。需求留意的是，假設(shè)算法中包括對(duì)其他函數(shù)或算法的調(diào)用，計(jì)算算法的時(shí)間復(fù)雜度時(shí)還要分析被調(diào)用算法或函數(shù)的時(shí)間復(fù)雜度。例例1.5 求一維數(shù)組元素中的最大值求一維數(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) ，即

23、，即f(n)=n例例1.6 兩個(gè)兩個(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+1T2(n)=O(n2)，即，即f(n)=n2 例例1.7 求兩個(gè)求兩個(gè)n階方陣的乘積階方陣的乘積void Matrixmlt(int a ,int b ,int c ,int n) int i,j,k;1 for

24、(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+1T3(n)= O(n3) ，即，即f(n)=n3 l最好時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 l例例1.8 在一維數(shù)組中查找指定的元素在一維數(shù)組中查找指定的元素l int search(int a,int x,int n)l int i;l1 for(i=0;in; i+; ) l2 if (ai=x) ruturn i+1; l3 return 0; l l最好時(shí)間復(fù)雜度為最好時(shí)間復(fù)雜度為O(1)l最壞時(shí)間復(fù)雜度為最壞時(shí)間復(fù)雜度為O(n)l平均