考研期末數(shù)據(jù)結(jié)構(gòu)第一章緒論_1

1、第一章 緒論1.1 什么是數(shù)據(jù)結(jié)構(gòu)一般來講，用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要下列幾個(gè)步驟：首先從具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終答案。例1-1圖書館的書目檢索系統(tǒng)自動(dòng)化問題001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L(zhǎng)01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02.高等數(shù)學(xué)001，003樊映川001,L002,理論力學(xué)002,華羅庚003,S001,003,線性代數(shù)004,欒汝書004,   圖1.1 圖書目錄文件示例由這四張表構(gòu)成的文件便是書目自動(dòng)檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主

2、要操作便是按照某個(gè)特定要求對(duì)書目文件進(jìn)行查詢。在這類文檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種最簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。例1-2 計(jì)算機(jī)和人對(duì)弈算法：?對(duì)弈的規(guī)則和策略模型：?棋盤及棋盤的格局例1-3 多叉路口交通燈的管理問題算法：?需要管理的項(xiàng)目？如何管理？ 用戶界面？模型：?各種圖概括地說：數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科?；蛘哒f，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史v 1968年美國(guó)唐歐克努特教授開

3、創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系v 從20世紀(jì)70年代中期到80年代初，各種版本的數(shù)據(jù)結(jié)構(gòu)著作就相繼出現(xiàn)。v 未來發(fā)展的兩個(gè)方向：（1）面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)（2）抽象數(shù)據(jù)類型的觀點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語(yǔ)一、 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù):所有能輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)程序處理的符號(hào)的總稱。是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素：是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合。例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是稱之為組合項(xiàng)姓名俱樂部名稱出生日期參

4、加日期職務(wù)業(yè)績(jī)年月日數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 例如，整數(shù)數(shù)據(jù)對(duì)象是集合N=0，1，-1，2，-2，字母字符數(shù)據(jù)對(duì)象是集合C=A，B，Z。數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。假設(shè)用三個(gè)4位的十進(jìn)制數(shù)表示一個(gè)含 12 位數(shù)的十進(jìn)制數(shù)。例如:3214,6587,9345 a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序”關(guān)系 <a1,a2>、<a2,a3>3214，6587，93456587，3214，9345a1a2a3 a2a1a3又例，

5、在2行3列的二維數(shù)組a1, a2, a3, a4, a5, a6 中六個(gè)元素之間存在兩個(gè)關(guān)系:行的次序關(guān)系:row = <a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>列的次序關(guān)系:col = <a1,a4>,<a2,a5>,<a3,a6>a1a3a5a1a2a3a2a4a6 a4a5a6再例，在一維數(shù)組 a1, a2, a3, a4, a5, a6 的數(shù)據(jù)元素之間存在如下的次序關(guān)系:<ai, ai+1>| i=1, 2, 3, 4, 5可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”?；蛘哒f，

6、數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組:Data_Structures = (D, S)其中:D 是數(shù)據(jù)元素的有限集，S 是 D上關(guān)系的有限集數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象 ？“關(guān)系”的映象 ？數(shù)據(jù)元素的映象方法：例：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2A = (101)8 = (001000001)2關(guān)系的映象方法：（表示<x, y>的方法）順序映象以相對(duì)的存

7、儲(chǔ)位置表示后繼關(guān)系。例如:令 y 的存儲(chǔ)位置和 x 的存儲(chǔ)位置之間差一個(gè)常量 C。而 C 是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。 x y鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系。需要用一個(gè)和 x 在一起的附加信息指示 y 的存儲(chǔ)位置。 y x在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。例如:以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用 C 語(yǔ)言中提供的整數(shù)數(shù)組類型。定義長(zhǎng)整數(shù)為:typedef int Long_int 3二、 數(shù)據(jù)類型在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或

8、表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。例如，C 語(yǔ)言中提供的基本數(shù)據(jù)類型有:整型 int浮點(diǎn)型 float雙精度型 double 實(shí)型（ C+語(yǔ)言）字符型 char邏輯型 bool （ C+語(yǔ)言）不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。數(shù)據(jù)類型:是一個(gè)值的集合和定義在此集合上的一組操作的總稱。三、 抽象數(shù)據(jù)類型(Abstract Data Type 簡(jiǎn)稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADT Complex 數(shù)據(jù)對(duì)象：De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：R1<e1,e2> | e1是復(fù)數(shù)的實(shí)數(shù)部分

9、 | e2 是復(fù)數(shù)的虛數(shù)部分 基本操作：AssignComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部 分別被賦以參數(shù) v1 和 v2 的值。DestroyComplex( &Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。GetImag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)

10、數(shù)z1, z2 的和值 ADT Complex假設(shè):z1和z2是上述定義的復(fù)數(shù)則 Add(z1, z2, z3) 操作的結(jié)果即為用戶企求的結(jié)果z3 = z1 + z2ADT 有兩個(gè)重要特征:數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。其中：D 是數(shù)據(jù)對(duì)象； S 是 D 上的關(guān)系集； P 是對(duì) D 的基本操作集。ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)

11、系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述 賦值參數(shù) 只為操作提供輸入值。引用參數(shù) 以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。例16 抽象數(shù)據(jù)類型三元組的定義：ADT Triplet 數(shù)據(jù)對(duì)象：D= e1,e2,e3|e1,e2,e3ElemSet (定義了關(guān)系運(yùn)算的某個(gè)集合) 數(shù)據(jù)關(guān)

12、系：R1=<e1,e2>,<e2,e3> 基本操作： InitTriplet( &T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三元組T，元素e1,e2和e3分別被賦以參數(shù) v1，v2 和 v3 的值。 DestroyTriplet( &T) 操作結(jié)果：三元組T被銷毀。 Get(T,I,&e) 初始條件：三元組已存在，i<=3. 操作結(jié)果：用e返回的第i元的值Put(&T,i,e) 初始條件：三元組已存在，i 操作結(jié)果：改變的第i元的值為eIsAscending(T) 初始條件：三元組已存在 操作結(jié)果：如果的個(gè)元素按升序排列，則返回，否則

13、返回IsDescending(T) 初始條件：三元組已存在 操作結(jié)果：如果的個(gè)元素按降序排列，則返回，否則返回Ma(T,&e) 初始條件：三元組已存在 操作結(jié)果：用e返回的個(gè)元素中的最大值A(chǔ)DTTriplet多形數(shù)據(jù)類型是指其值的成分不確定的數(shù)據(jù)類型。例如，例16中定義的抽象數(shù)據(jù)類型Triplet，其元素e1、e2和e3可以是整數(shù)或字符或字符串，甚至更復(fù)雜的由多種成分構(gòu)成。從抽象數(shù)據(jù)類型的角度看，具有相同的數(shù)學(xué)抽象特性，故稱之為多形數(shù)據(jù)類型。1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。以下對(duì)類C語(yǔ)言的描述作簡(jiǎn)要說明。（1）預(yù)

14、定義常量和類型/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼Typedef int Status; （2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（typedef)描述。數(shù)據(jù)元素類型約定ElemType,由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。（3）基本操作的算法都用以下形式的函數(shù)描述：函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） / 算法說明 語(yǔ)名序列 / 函數(shù)名 除了函數(shù)的參數(shù)需要說明類型外，算法中使

15、用的輔助變量可以不作變量說明，必要時(shí)對(duì)其作用給予注釋。一般而言，a、b、c、d、e等用作數(shù)據(jù)元素名，i、j、k、l、m、n等用作整形變量名，p、q、r等用作指針變量名。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時(shí)，函數(shù)定義為Status類型。為了便于算法描述，除了值調(diào)用方式外，增添了C+語(yǔ)言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。（4）賦值語(yǔ)名有簡(jiǎn)單賦值 變量名=表達(dá)式；串聯(lián)賦值 變量名 1=變量名2=變量名k=表達(dá)式；成組賦值 （變量名1，變量名k）=（表達(dá)式1， ，表達(dá)式k）； 結(jié)構(gòu)名=結(jié)構(gòu)名； 結(jié)構(gòu)名=（值1，值k）； 變量名 =表達(dá)式； 變量名起始下標(biāo).終止下標(biāo)=

16、變量名起始下標(biāo).終止下標(biāo)；交換賦值 變量名（）變量名；條件賦值 變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F；（5）選擇語(yǔ)句有條件語(yǔ)句1 if (表達(dá)式) 語(yǔ)句；條件語(yǔ)句2 if (表達(dá)式) 語(yǔ)句； else 語(yǔ)句；開關(guān)語(yǔ)句1 switch （表達(dá)式） case值1: 語(yǔ)句序列break; case 值n：語(yǔ)句序列n;break ; default; 語(yǔ)句序列n+1； 開關(guān)語(yǔ)句2 switch case 條件1：語(yǔ)句序列1;break; default:語(yǔ)句序列n+1； （6）循環(huán)語(yǔ)句有for語(yǔ)句 for（賦初值表達(dá)式序列；條件；修改 表達(dá)式序列）語(yǔ)句；while語(yǔ)句 while（條件）語(yǔ)句； do

17、-while語(yǔ)句 do 語(yǔ)句序列； while（條件）；（7）結(jié)束語(yǔ)句有函數(shù)結(jié)束語(yǔ)句 return表達(dá)式； return; case結(jié)束語(yǔ)句 break;異常結(jié)束語(yǔ)句 exit（異常代碼）；（8）輸入和輸出語(yǔ)句有輸入語(yǔ)句 scanf（格式串，變量1，變量n）；輸出語(yǔ)句 printf （格式串，表達(dá)式1，表達(dá)式n）；通常省略格式串。（9）注釋單行注釋 / 文字序列（10）基本函數(shù)有求最大值 max（表達(dá)式1，表達(dá)式n)求最小值 min（表達(dá)式1，表達(dá)式n） 求絕對(duì)值 abs（表達(dá)式）求不足整數(shù)值 floor（表達(dá)式）求進(jìn)位整數(shù)值 ceil （表達(dá)式）判定文件結(jié)束 eof（文件變量）或eof判定行

18、結(jié)束 eoln（文件變量）或eoln(11)邏輯運(yùn)算約定 與運(yùn)算&&：對(duì)于A&&B，當(dāng)A的值為0時(shí)，不再對(duì)B求值。 或運(yùn)算|：對(duì)于A|B，當(dāng)A的值為非0時(shí)，不再對(duì)B求值。例如，對(duì)以上定義的復(fù)數(shù)。/ -存儲(chǔ)結(jié)構(gòu)的定義typedef struct float realpart； float imagpart；complex；/ -基本操作的函數(shù)原型說明void Assign( complex &Z, float realval, float imagval )；/ 構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) / realval 和 imagval 的值floa

19、t GetReal( cpmplex Z )； / 返回復(fù)數(shù) Z 的實(shí)部值float Getimag( cpmplex Z )； / 返回復(fù)數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 / -基本操作的實(shí)現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart

20、= z1.imagpart + z2.imagpart; 其它省略 例1-7 抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)。 /- - - - 采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)- - - - - typedef ElemType *Triplet; / 由InitTriplet分配3個(gè)元素存儲(chǔ)空間/- - - - 基本操作的函數(shù)原型說明- - - - - Status InitTriplet (Triplet &T, ElemType v1, ElemType v2, ElemType v3); /操作結(jié)果：構(gòu)造了三元組，元素e1,e2和e3分別被賦以參數(shù) v1，v2 和 v3 的值。 Statu

21、s DestroyTriplet ( Triplet &T); /操作結(jié)果：三元組T被銷毀。Status Get ( Triplet T , int i , ElemType &e); /初始條件：三元組已存在，<=i<=3. /操作結(jié)果：用e返回的第i元的值Status Put (Triplet &T , int i , ElemType e); /初始條件：三元組已存在，<=i<= /操作結(jié)果：改變的第i元的值為e Status IsAscending (Triplet T); / 初始條件：三元組已存在 / 操作結(jié)果：如果的個(gè)元素按升序排列

22、，則返回，否則返回Status IsDescending (Triplet T); / 初始條件：三元組已存在 / 操作結(jié)果：如果的個(gè)元素按降序排列，則返回，否則返回Status Max (Triplet T, ElemType &e) / 初始條件：三元組已存在/ 操作結(jié)果：用e返回的個(gè)元素中的最大值Status Min (Triplet T, ElemType &e) / 初始條件：三元組已存在 / 操作結(jié)果：用e返回的個(gè)元素中的最小值/- - - - 基本操作的函數(shù)原型說明- - - - -Status InitTriplet (Triplet &T, ElemT

23、ype v1, ElemType v2, ElemType v3) /構(gòu)造了三元組，依次置T的三個(gè)元素的初值 v1，v2 和 v3 。 T=(ElemType *) malloc(3 *sizeof (ElemType ); /分配三個(gè)元素的存儲(chǔ)空間 if (!T) exit ( OVERFLOW ) ; /分配存儲(chǔ)空間失敗 T0=v1; T1=v2; T2=v3; return OK; / InitTripletStatus DestroyTriplet ( Triplet &T) /銷毀三元組T。 free ( T ); T = NULL; return OK; / InitTri

24、pletStatus Get ( Triplet T , int i , ElemType &e) /1<=i<=3,用e返回的第i元的值 if ( i<1 | i>3 ) return ERROR; e = Ti-1; return OK; / GetStatus Put (Triplet &T , int i , ElemType e) /1<=i<=3,置的第i元的值為e if ( i<1 | i>3 ) return ERROR; Ti-1 = e; return OK; / PutStatus IsAscending (

25、Triplet T) / 如果的個(gè)元素按升序排列，則返回，否則返回 return ( T0 <=T1)&& T1 <=T2); / IsAscending Status IsDescending (Triplet T) / 如果的個(gè)元素按降序排列，則返回，否則返回 return ( T0 >=T1)&& T1 >=T2); / IsDescendingStatus Max (Triplet T, ElemType &e) / 用e返回的個(gè)元素中的最大值e = ( T0 >=T1)?( T0 >=T2)? T0 :T2)

26、:(T1 >=T2)? T1 :T2);return OK; / MaxStatus Min (Triplet T, ElemType &e) / 用e返回的個(gè)元素中的最小值e = ( T0 <=T1)?( T0 <=T2)? T0 :T2):(T1 <=T2)? T1 :T2);return OK; / Min1.4 算法和算法分析1.4.1 算法算法是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1有窮性 2確定性 3可行性4有輸入 5有輸出1有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟

27、都能在有限時(shí)間內(nèi)完成。2確定性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑，不允許有二義性。例如下面這句話：張三對(duì)李四講，他的兒子考上了大學(xué)。 確切含義？3可行性 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。5有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。

28、1.4.2 算法設(shè)計(jì)的原則 設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性2. 可讀性3健壯性4高效率與低存儲(chǔ)量需求1正確性首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a程序中不含語(yǔ)法錯(cuò)誤；b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；通常以第 c 層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。2. 可讀性算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程

29、序易于隱藏較多錯(cuò)誤而難以調(diào)試。3健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4高效率與低存儲(chǔ)量需求通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。1.4.3 算法效率的度量通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法缺點(diǎn)：1必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì)事前分析估算法和算法執(zhí)行時(shí)間相關(guān)的因素：1算法選用的策略2問題的規(guī)模3編寫程序的語(yǔ)言4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5計(jì)算機(jī)執(zhí)行指令

30、的速度一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。 假如，隨著問題規(guī)模 n 的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率相同，則可記作：T(n) = O(f(n)稱T(n) 為算法的(漸近)時(shí)間復(fù)雜度。如何估算算法的時(shí)間復(fù)雜度？算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間 =原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間與 原操作執(zhí)行次數(shù)之和成正比 從算法中選取一種對(duì)于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。例一：

31、兩個(gè)矩陣相乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲(chǔ)矩陣元素，c 為 a 和 b 的乘積 for (i=1; i<=n; +i) for (j=1; j<=n; +j) ci,j = 0; for (k=1; k<=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法操作時(shí)間復(fù)雜度: O(n3)例二：選擇排序void select_sort(int& a, int n) / 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 for ( i = 0; i< n-1; +i

32、) j = i; / 選擇第 i 個(gè)最小元素for ( k = i+1; k < n; +k ) if (ak < aj ) j = k; if ( j != i ) aj ai / select_sort基本操作: 比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度: O(n2)例三：起泡排序void bubble_sort(int& a, int n) / 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for (i=n-1, change=TRUE; i>1 && change; -i) change = FALSE; / change 為元素進(jìn)行交換標(biāo)志 fo

33、r (j=0; j<i; +j) if (aj > aj+1) aj aj+1; change = TRUE ; / 一趟起泡 / bubble_sort基本操作: 賦值操作時(shí)間復(fù)雜度: O(n2)1.4.4 算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:S(n) = O(g(n)表示隨著問題規(guī)模 n 的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與 g(n) 的增長(zhǎng)率相同。算法的存儲(chǔ)量包括:1輸入數(shù)據(jù)所占空間2程序本身所占空間3輔助變量所占空間若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為

34、原地工作。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。1.5 英特爾多核技術(shù)簡(jiǎn)介1.5.1 多核計(jì)算發(fā)展趨勢(shì)1. 單核CPU的發(fā)展限制提高CPU性能的方法：1) 不二法則：提高處理器的主頻。困難：高發(fā)熱問題，會(huì)導(dǎo)致芯片運(yùn)行不穩(wěn)定，因此主頻的提升空間不大。2) 用superscalar（超標(biāo)量）處理器的方式，讓處理器在一個(gè)時(shí)鐘周期內(nèi)執(zhí)行多條指令。問題：超標(biāo)量處理器通常有兩個(gè)或多個(gè)處理單元，利用這些硬件資源，需要對(duì)軟件進(jìn)行精心設(shè)計(jì)；要適應(yīng)多流水線，需要對(duì)軟件進(jìn)行大量的修改，這些都會(huì)影響軟件的可移植性。3) 通過超流水線方式提高頻率。問題：目前超流水線已經(jīng)達(dá)到飽和，再增加超流水線是很困難的。

35、因此，從指令級(jí)上提升CPU性能已經(jīng)達(dá)到極限。單純提高單核CPU速度，還面臨著存儲(chǔ)器訪問速度匹配問題：如果CPU速度高于存儲(chǔ)器訪問速度，那么CPU的性能同樣無法發(fā)揮。而實(shí)際使用中存儲(chǔ)器訪問速度并不能與處理器速度同步提高，因此，單純提高單核CPU速度并不能促進(jìn)計(jì)算機(jī)系統(tǒng)整體性能的提高。提高單核CPU處理能力的方法來提升計(jì)算機(jī)系統(tǒng)性能，已經(jīng)到達(dá)瓶頸狀態(tài)。2. 對(duì)高性能計(jì)算的需求越來越高例如：網(wǎng)絡(luò)服務(wù)器軟件需要同時(shí)響應(yīng)大量用戶的請(qǐng)求；多媒體游戲軟件需要對(duì)圖形、動(dòng)畫進(jìn)行大量運(yùn)算；實(shí)時(shí)嵌入式系統(tǒng)的快速發(fā)展使其對(duì)計(jì)算能力的需求每年都在增長(zhǎng)；客戶端殺毒軟件中殺毒軟件、安全軟件等對(duì)計(jì)算能力的需求也在逐年增加。3. 多核計(jì)算將成為發(fā)展趨勢(shì)單個(gè)CPU的計(jì)算能力是無法與多個(gè)CPU的計(jì)算能力相比的，計(jì)算機(jī)硬件中仍然需要有多個(gè)CPU以獲取更高的性能，軟件中仍需要采取多核計(jì)算以取得更高的性能。多核計(jì)算將成為未來的發(fā)展趨勢(shì)，多核編程將成為程序員必須掌握的技術(shù)。1.5.2 什么是多核技術(shù)多內(nèi)核是指在一枚處理器中集成兩個(gè)或多個(gè)完整的計(jì)算引擎(內(nèi)核)。多核技術(shù)的開發(fā)源于工程師們認(rèn)識(shí)到，僅僅提高單核芯片的速度會(huì)產(chǎn)生過多