1、第1章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法的復(fù)雜度 1. 算法的基本概念 .算法：即解題方案的準(zhǔn)確而完整的描述【注意：算法不等于程序，也不等于計(jì)算方法，通常，程序的編制不可能優(yōu)于算法的設(shè)計(jì)】.利用計(jì)算機(jī)算法為計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法。 （1）算法的基本特征 算法一般具有4個(gè)基本特征：可行性、確定性、有窮性（包括精度要求確定的計(jì)算過程和合理的執(zhí)行時(shí)間的含義）、擁有足夠的情報(bào)。 （2）算法的基本要素 .對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作計(jì)算機(jī)算法就是計(jì)算機(jī)能處理的操作所組成的指令序列。通常，計(jì)算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的，一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合稱為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。其中

2、基本的運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸（賦值、輸入、輸出等）。.控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。 .描述算法的工具通常有：傳統(tǒng)流程圖、NS結(jié)構(gòu)化流程圖、算法描述語言。 .一個(gè)算法的3種基本控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 （3）算法基本設(shè)計(jì)方法 算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推（逐成分解）、遞歸、減半遞推技術(shù)、回溯法。 2. 算法復(fù)雜度 算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。注意兩者的區(qū)別，不要混淆，見表1-11.2 數(shù)據(jù)結(jié)構(gòu) 1.2.1 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 1. 數(shù)據(jù)結(jié)構(gòu)的基本概念 （1）數(shù)據(jù)結(jié)構(gòu)：指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 （

3、2）數(shù)據(jù)處理：指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、查找、更改等運(yùn)算、也包括對(duì)數(shù)據(jù)元素進(jìn)行分析。（3）數(shù)據(jù)結(jié)構(gòu)研究的3個(gè)方面 .數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu); .在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu); .對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 2. 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成：B=(D,R

4、)其中，B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間的這種固有的關(guān)系簡單地用前后件關(guān)系（或直接前驅(qū)或直接后繼關(guān)系）來描述。例如，假設(shè)a與b是D中的；兩個(gè)數(shù)據(jù)，則二元組（a，b）表示a是b的前件，b是a的后件例如，如果把一年四季看作一個(gè)數(shù)據(jù)結(jié)構(gòu)，則可表示成：B =(D,R) D =春季,夏季,秋季,冬季 R =(春季,夏季),(夏季,秋季),(秋季,冬季) 3. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。 由于數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，

5、為了表示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是在每個(gè)結(jié)點(diǎn)中至少包含一個(gè)指針域，用指針來體現(xiàn)數(shù)據(jù)元素之間邏輯上的聯(lián)系。 1.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示父親一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中

6、，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后向結(jié)點(diǎn)。例如，一年四季的數(shù)據(jù)結(jié)構(gòu)可以用如圖的圖形表示女兒兒子 又如，反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)可以用如圖的圖形表示在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（也稱葉子結(jié)點(diǎn)）。例如，在數(shù)據(jù)結(jié)構(gòu)一年四季中，“春”所在的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)“春”，下同）為根結(jié)點(diǎn)，結(jié)點(diǎn)“冬”為終端結(jié)點(diǎn)。通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是在動(dòng)態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個(gè)數(shù)據(jù)結(jié)構(gòu)中增加一

7、個(gè)新結(jié)點(diǎn)（稱為插入運(yùn)算），也可以刪除數(shù)據(jù)結(jié)構(gòu)中某個(gè)結(jié)點(diǎn)（稱為刪除運(yùn)算）插入與刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。除此之外，對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改等等。1.2.3 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。 （1）如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件： .有且只有一個(gè)根結(jié)點(diǎn)； .每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。棧、隊(duì)列、串等都為線性結(jié)構(gòu)。 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱

8、之為非線性結(jié)構(gòu)。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 （2）線性表的順序存儲(chǔ)（也稱順序分配）結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)： .線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的； .線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 元素ai的存儲(chǔ)地址為：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)為第一個(gè)元素的地址，k代表每個(gè)元素占的字節(jié)數(shù)。 （3）順序表的運(yùn)算有查找、插入、刪除3種。 1.3 棧 （zhn）1. 棧的基本概念 棧（stack）是一種特殊的線性表，是限定只在一端進(jìn)行插入與刪除的線性表。 在棧中，一端是封閉的，既不允許進(jìn)行插入元素，也不允許刪除元素；另一端是開口的

9、，允許插入和刪除元素。通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。 棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用通常用指針top來表示棧頂?shù)奈恢?，用指針botton指向棧底。往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素（即刪除棧頂元素）稱為退棧運(yùn)算。棧頂指針top動(dòng)態(tài)反應(yīng)了棧中的元素變化情況。（如右圖所示）棧這種數(shù)據(jù)結(jié)構(gòu)在日常生活中也是常見的。例如，槍械的子彈匣就

10、可以用來形象的表示棧結(jié)構(gòu)。子彈匣的一端是完全封閉的，最后被壓入彈匣的子彈總是最先被彈出，而最先被壓入的子彈最后才能被彈出。2. 棧的順序存儲(chǔ)及其運(yùn)算 棧的基本運(yùn)算有3種：入棧、退棧與讀棧頂元素。 .入棧運(yùn)算：在棧頂位置插入一個(gè)新元素；即先將棧頂指針進(jìn)一（即top加1），然后將新元素插入到棧頂指針指向的位置當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說明?？臻g已滿，不可能再進(jìn)行入棧操作，這種情況稱為“上溢”錯(cuò)誤。.退棧運(yùn)算：取出棧頂元素并賦給一個(gè)指定的變量；即先將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量，然后將棧頂指針退一（即top減1）。當(dāng)棧頂指針為0時(shí)，說明?？?，不可能再進(jìn)行退棧操作

11、，這種情況稱為“下溢”錯(cuò)誤。.讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。必須注意，這個(gè)運(yùn)算不刪除棧頂元素，只是將它的值賦給一個(gè)變量，因此，在這個(gè)運(yùn)算中，棧頂指針不會(huì)改變。當(dāng)棧頂指針為0時(shí)，說明?？?，讀不到棧頂元素。1.4 隊(duì)列 1. 隊(duì)列的基本概念 隊(duì)列是只允許在一端進(jìn)行刪除，在另一端進(jìn)行插入的順序表，通常將允許刪除的這一端稱為隊(duì)頭或排頭（通常用排頭指針【front】指向排頭元素的前一個(gè)位置），允許插入的這一端稱為隊(duì)尾（通常用一個(gè)稱為尾指針【rear】的指針指向隊(duì)尾元素，即尾指針總是指向最后被插入的元素）。當(dāng)表中沒有元素時(shí)稱為空隊(duì)列。隊(duì)列的修改是依照先進(jìn)先出的原則進(jìn)行的，因此隊(duì)列也稱為先進(jìn)先出

12、的線性表，或者后進(jìn)后出的線性表。例如：火車進(jìn)遂道，最先進(jìn)遂道的是火車頭，最后是火車尾，而火車出遂道的時(shí)候也是火車頭先出，最后出的是火車尾。若有隊(duì)列：Q =(q1,q2,qn)那么，q1為隊(duì)頭元素（排頭元素），qn為隊(duì)尾元素。隊(duì)列中的元素是按照q1，q2，qn的順序進(jìn)入的，退出隊(duì)列也只能按照這個(gè)次序依次退出，即只有在q1，q2，qn-1都退隊(duì)之后，qn才能退出隊(duì)列。因最先進(jìn)入隊(duì)列的元素將最先出隊(duì)，所以隊(duì)列具有先進(jìn)先出的特性，體現(xiàn)“先來先服務(wù)”的原則。 隊(duì)頭元素q1是最先被插入的元素，也是最先被刪除的元素。隊(duì)尾元素qn是最后被插入的元素，也是最后被刪除的元素。因此，與棧相反，隊(duì)列又稱為“先進(jìn)先出”

13、（First In First Out，簡稱FIFO）或“后進(jìn)后出”（Last In Last Out，簡稱LILO）的線性表。2.循環(huán)隊(duì)列.循環(huán)隊(duì)列：將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。.循環(huán)隊(duì)列的兩種基本運(yùn)算：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用隊(duì)列循環(huán)的形式，即循環(huán)隊(duì)列。循環(huán)隊(duì)列s=0表示隊(duì)列空。s=0且front=rear表示隊(duì)列滿。計(jì)算循環(huán)隊(duì)列的元素個(gè)數(shù)：“尾指針減頭指針”，若為負(fù)數(shù)，再加其容量即可。假設(shè)循環(huán)隊(duì)列初始狀態(tài)為空,即：s=0,且front=rear=m。.入隊(duì)運(yùn)算：指往隊(duì)列（循環(huán)隊(duì)列）隊(duì)尾插入一個(gè)數(shù)據(jù)元素；即將隊(duì)尾

14、指針進(jìn)一（即rear=rear+1），并當(dāng)rear=m+1時(shí)置rear=1，然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空（s=1）且隊(duì)尾指針等于排頭指針時(shí)，說明循環(huán)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。.退隊(duì)運(yùn)算：指從隊(duì)列（循環(huán)隊(duì)列）的隊(duì)頭刪除一個(gè)數(shù)據(jù)元素，并賦給指定的變量；即將將排頭指針進(jìn)一（front=front+1），并當(dāng)front=m+1時(shí)置front=1。然后將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空（s=0）是不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為“下溢”。1.5 鏈表 在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于

15、存放指針，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件）。 鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 （1）線性鏈表 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。 在某些應(yīng)用中，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用以指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針，用以指向其后件結(jié)點(diǎn)。這樣的表稱為雙向鏈表。 在線性鏈表中，各數(shù)據(jù)元素結(jié)點(diǎn)的存儲(chǔ)空間可以是不連續(xù)的，且各數(shù)據(jù)元素的存儲(chǔ)順序與邏輯順序可以不一致。在線性鏈表中進(jìn)行插入與刪除，不需要移動(dòng)鏈表中的元素。 線性單鏈表中，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表。 如果是雙項(xiàng)鏈表的兩指針：左指針（

16、Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。 線性鏈表的基本運(yùn)算：查找、插入、刪除、排序、復(fù)制、逆轉(zhuǎn)、分解、合并等。 （2）帶鏈的棧 棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。 1.6 樹與二叉樹 1.6.1 樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)，在數(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性如圖所示。在樹的圖形表示中，總是認(rèn)為在用直線連起來的兩端結(jié)點(diǎn)中，上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件，這樣，表示前后件關(guān)系的箭頭就可以省略。（現(xiàn)實(shí)生活中的例子很多，如學(xué)校的行政關(guān)系結(jié)構(gòu)圖1.27）在樹結(jié)構(gòu)

17、中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。如右圖結(jié)點(diǎn)R樹的根結(jié)點(diǎn)。在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度，如根結(jié)點(diǎn)R的度為4，結(jié)點(diǎn)T的度為3。在樹中，所有結(jié)點(diǎn)中最大的度稱為樹的度，如上圖樹的度為4樹的最大層次稱為數(shù)的深度如圖1.26所示的樹的深度為5，根結(jié)點(diǎn)在第一層，葉子結(jié)點(diǎn)沒有子樹在計(jì)算機(jī)中，可以用樹結(jié)構(gòu)來表示算術(shù)表達(dá)式（這里不詳講解）1.6.2 二叉樹概念及其基本性質(zhì) 1. 二叉樹及其基本概念 二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個(gè)特點(diǎn)： .非空

18、二叉樹只有一個(gè)根結(jié)點(diǎn)； .每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹和右子樹。 在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹。另外，二叉樹中的每個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹和右子樹。 在二叉樹中，一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當(dāng)一個(gè)結(jié)點(diǎn)既沒有左子樹也沒有右子樹時(shí)，該結(jié)點(diǎn)即為葉子結(jié)點(diǎn)。 例如，一個(gè)家族中的族譜關(guān)系如圖1-1所示： A有后代B，C；B有后代D，E；C有后代F。 圖1-1典型的二叉樹如圖右圖1-1所示： 詳細(xì)講解二叉樹的基本概念，見下表1-2。 2. 二叉樹基本性質(zhì)。二叉樹具有以下幾個(gè)性質(zhì)： 性質(zhì)1：在二叉

19、樹的第k層上，最多有（k1）個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為m（即二叉樹有m層）的二叉樹最多有-個(gè)結(jié)點(diǎn)。性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為+1，其中表示取的整數(shù)部分。 3. 滿二叉樹與完全二叉樹 .滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有-個(gè)結(jié)點(diǎn)。如下圖的a、b、c分別是深度為2、3、4的滿二叉樹。.完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上

20、只缺少右邊的若干結(jié)點(diǎn)。如下圖所示的a、b分別是深度為3、4的完全二叉樹。對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)：對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為p，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜，或?yàn)閜+1。 完全二叉樹具有以下兩個(gè)性質(zhì)： 性質(zhì)1：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為+1。性質(zhì)2：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層次（每一層從左到右）用自然數(shù)1，2，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1，2，n）的結(jié)點(diǎn)有以下結(jié)論： 若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT（k/2）； 若2kn，則編號(hào)為k的結(jié)點(diǎn)的左

21、子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）； 若2k+1n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。.在計(jì)算機(jī)中，二叉樹的存儲(chǔ)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（也稱為二叉鏈表）。其中，用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域，指針域（指針域有2個(gè)：一是用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域；另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域）。1.6.3 二叉樹（是一種非線性結(jié)構(gòu)）的遍歷（指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)） 在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷分為三類

22、：前序遍歷、中序遍歷和后序遍歷。 （1）前序遍歷（DLR） 先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且在遍歷左、右子樹時(shí)，仍需先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。例如，對(duì)右圖1-1中的二叉樹進(jìn)行前序遍歷的結(jié)果（或稱為該二叉樹的前序序列）為：A，B，D，E，C，F(xiàn)。 （2）中序遍歷（LDR）先遍歷左子樹、然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。例如，對(duì)右圖1-1中的二叉樹進(jìn)行中序遍歷的結(jié)果（或稱為該二叉樹的中序序列）為： D，B，E，A，C，F(xiàn)。 （3）后序遍歷（LRD）先遍歷左子樹、然后遍歷右子樹，最后訪問根

23、結(jié)點(diǎn)；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。例如，對(duì)右圖1-1中的二叉樹進(jìn)行后序遍歷的結(jié)果（或稱為該二叉樹的后序序列）為： D， E，B， F，C，A。 1.7 查找 1.7.1 順序查找 查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。順序查找（順序搜索）是指從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進(jìn)行了比較但都不相等，則表示查找失敗。 例如，在一維數(shù)組21，46，24，99，57，77，86中，查找數(shù)據(jù)元素99，首先從第1個(gè)元素21開始進(jìn)行比較，比較結(jié)果與要查找的數(shù)據(jù)

24、不相等，接著與第2個(gè)元素46進(jìn)行比較，以此類推，當(dāng)進(jìn)行到與第4個(gè)元素比較時(shí)，它們相等，所以查找成功。如果查找數(shù)據(jù)元素100，則整個(gè)線性表掃描完畢，仍未找到與100相等的元素，表示線性表中沒有要查找的元素。 在下列兩種情況下也只能采用順序查找： 如果線性表為無序表（表中的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，只能用順序查找；即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。 1.7.2 二分法查找 二分法查找，也稱拆半查找，是一種高效的查找方法。能使用二分法查找的線性表必須滿足用順序存儲(chǔ)結(jié)構(gòu)和線性表是有序表兩個(gè)條件?！坝行颉笔翘刂冈匕捶沁f減排列，即從小到大排列，但允許相

25、鄰元素相等。下一節(jié)排序中，有序的含義也是如此。 對(duì)于長度為n的有序線性表，利用二分法查找元素X的過程如下：步驟1：將X與線性表的中間項(xiàng)比較；步驟2：如果X的值與中間項(xiàng)的值相等，則查找成功，結(jié)束查找；步驟3：如果X小于中間項(xiàng)的值，則在線性表的前半部分以二分法繼續(xù)查找；步驟4：如果X大于中間項(xiàng)的值，則在線性表的后半部分以二分法繼續(xù)查找。例如，長度為8的線性表關(guān)鍵碼序列為：6，13，27，30，38，46，47，70，被查元素為38，首先將與線性表的中間項(xiàng)比較，即與第4個(gè)數(shù)據(jù)元素30相比較，38大于中間項(xiàng)30的值，則在線性表38，46，47，70中繼續(xù)查找；接著與中間項(xiàng)比較，即與第2個(gè)元素46相比較

26、，38小于46，則在線性表38中繼續(xù)查找，最后一次比較相等，查找成功。順序查找法每一次比較，只將查找范圍減少1，而二分法查找，每比較一次，可將查找范圍減少為原來的一半，效率大大提高。對(duì)于長度為n的有序線性表，在最壞情況下，二分法查找只需比較次，而順序查找需要比較n次。 1.8 排序 排序：將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。排序可以在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，在本節(jié)所介紹的排序方法中，其排序的對(duì)象一般認(rèn)為是順序存儲(chǔ)的線性表，在程序設(shè)計(jì)語言中就是一維數(shù)組。1. 交換類排序法（借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序）（1）冒泡排序法（通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序）首先，從表頭開

27、始往后掃描線性表，逐次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的大者往后移動(dòng)，最后最大者到了線性表的最后。然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的小者往前移動(dòng)，最后最小者到了線性表的最前面。對(duì)剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)已經(jīng)排好序。在最壞的情況下，冒泡排序需要比較次數(shù)為n(n-1)/2。（2）快速排序法 任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過一次排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于

28、基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。在快速排序過程中，隨著對(duì)各個(gè)子表不斷進(jìn)行分割，劃分出的子表會(huì)越來越多，但一次有只能對(duì)一個(gè)子表進(jìn)行再分割處理，需要將暫時(shí)不分割的子表記憶起來，這就要用一個(gè)棧來實(shí)現(xiàn)2. 插入類排序法.簡單插入排序法：將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。最壞情況需要n(n-1)/2次比較；.希爾排序法：將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序，最壞情況需要O()次比較。 3. 選擇類排序法 .簡單選擇排序法：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面（這是它應(yīng)有的位置）

29、，然后對(duì)剩下的子表采用同樣的方法，直到子表為空為止。最壞情況需要n(n-1)/2次比較； 堆排序法 點(diǎn))元素必為序列的n個(gè)元素中的最大項(xiàng)。堆排序法對(duì)于規(guī)模較小的線性表并不適合，但對(duì)于較大規(guī)模的線性表來說是很有效的，最壞情況需要O(n)次比較。 相比以上幾種（除希爾排序法外），堆排序法的時(shí)間復(fù)雜度最小。 第2章 程序設(shè)計(jì)基礎(chǔ)2.1 程序設(shè)計(jì)的方法與風(fēng)格 程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、技術(shù)、方法和工具來支持，就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。除此之外，程序設(shè)計(jì)風(fēng)格也很重要，它會(huì)深刻的影響軟件的質(zhì)量和可維護(hù)性，因此，程序設(shè)計(jì)風(fēng)格對(duì)保證程序的質(zhì)量很

30、重要一般來講，程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)的特點(diǎn)、習(xí)慣和邏輯思路。程序就設(shè)計(jì)風(fēng)格總體而言應(yīng)該強(qiáng)調(diào)簡單和清晰，程序必須是可以理解的可以認(rèn)為，著名的“清晰第一，效率第二”的論點(diǎn)已成為當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。養(yǎng)成良好的程序設(shè)計(jì)風(fēng)格，主要考慮下述因素：（1）源程序文檔化.符號(hào)名的命名：符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的理解；.程序注釋：在源程序中添加正確的注釋可幫助人們理解程序。程序注釋可分為序言性注釋和功能性注釋。語句結(jié)構(gòu)清晰第一、效率第二；.視覺組織：通過在程序中添加一些空格、空行和縮進(jìn)等，使人們?cè)谝曈X上對(duì)程序的結(jié)構(gòu)一目了然。 （2）數(shù)據(jù)說明的方法 為使程序中的數(shù)據(jù)說明易于理

31、解和維護(hù)，可采用下列數(shù)據(jù)說明的風(fēng)格，見表2-1。 （3）語句的結(jié)構(gòu)程序 語句的結(jié)構(gòu)程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接。 （4）輸入和輸出 在設(shè)計(jì)和編程時(shí)應(yīng)考慮如下原則: .對(duì)所有的輸入數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性； .檢查輸入項(xiàng)的各種重要組合的合理性； .輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式；應(yīng)允許缺省值； .輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志； .在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入放入請(qǐng)求，同時(shí)在數(shù)據(jù)輸入過程中和輸入結(jié)束時(shí)，應(yīng)當(dāng)在屏幕上給出狀態(tài)信息； .當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一致性，給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式

32、，2.2 結(jié)構(gòu)化程序設(shè)計(jì) 1. 結(jié)構(gòu)化程序設(shè)計(jì)的原則 結(jié)構(gòu)化程序設(shè)計(jì)方法引入了工程思想和結(jié)構(gòu)化思想，使大型軟件的開發(fā)和編程得到了極大的改善。結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則為：自頂向下、逐步求精、模塊化和限制使用goto語句。.自頂向上：先考慮整體，再考慮細(xì)節(jié)；先考慮全局目標(biāo)，再考慮局部目標(biāo)； .逐步求精：對(duì)復(fù)雜問題應(yīng)設(shè)計(jì)一些子目標(biāo)作為過渡，逐步細(xì)化； .模塊化：把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。 .限制使用goto語句：在程序開發(fā)過程中要限制使用goto語句。2. 結(jié)構(gòu)化程序的基本結(jié)構(gòu) 結(jié)構(gòu)化程序的基本結(jié)構(gòu)有三種類型：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)

33、結(jié)構(gòu)。 順序結(jié)構(gòu)：是最基本最普通的結(jié)構(gòu)形式，按照程序中的語句行的先后順序逐條執(zhí)行； 選擇結(jié)構(gòu)：又稱為分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)； .循環(huán)結(jié)構(gòu)【重復(fù)結(jié)構(gòu)】：根據(jù)給定的條件，判斷是否要重復(fù)執(zhí)行某一相同的或類似的程序段。循環(huán)結(jié)構(gòu)對(duì)應(yīng)兩類循環(huán)語句：先判斷后執(zhí)行的循環(huán)體稱為當(dāng)型循環(huán)結(jié)構(gòu)；先執(zhí)行循環(huán)體后判斷的稱為直到型循環(huán)結(jié)構(gòu)。 2.3 面向?qū)ο蠓椒?面向?qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題區(qū)域，也就是說，系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)反映問題區(qū)域中固有事物及其關(guān)系

34、。面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：.與人類習(xí)慣的思維方法一致。（面向?qū)ο蠓椒ê图夹g(shù)以對(duì)象為核心）.穩(wěn)定性好。.可重用性好。.易于開發(fā)大型軟件產(chǎn)品。.可維護(hù)性好。面向?qū)ο蠓椒êw對(duì)象及對(duì)象屬性與方法、類、繼承、多態(tài)性幾個(gè)基本要素。1. 對(duì)象：通常把對(duì)象的操作也稱為方法或服務(wù)。 屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來改變。屬性值應(yīng)該指的是純粹的數(shù)據(jù)值，而不能指對(duì)象。 操作描述了對(duì)象執(zhí)行的功能，若通過信息的傳遞，還可以為其他對(duì)象使用。 對(duì)象具有如下特征：標(biāo)識(shí)惟一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性。 2. 類和實(shí)例 類是具有共同屬性、共同方法的對(duì)象的集合。它描述了屬于該對(duì)象類

35、型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例。 類是關(guān)于對(duì)象性質(zhì)的描述，它同對(duì)象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。 3. 消息消息是實(shí)例之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。 一個(gè)消息由三部分組成：接收消息的對(duì)象的名稱、消息標(biāo)識(shí)符（消息名）和零個(gè)或多個(gè)參數(shù)。 4. 繼承 廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。繼承分為單繼承與多重繼承。單繼承是指，一個(gè)類只允許有一個(gè)父類，即類等級(jí)為樹形結(jié)構(gòu)。多重繼承是指，一個(gè)類允許有多個(gè)父類。 5. 多態(tài)性 對(duì)象根據(jù)所接受的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接受

36、時(shí)可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性。 第3章 軟件工程基礎(chǔ)3.1 軟件工程基本概念 1. 軟件定義與軟件特點(diǎn) 軟件指的是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)和相關(guān)文檔的完整集合。程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí)行的指令序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序的開發(fā)、維護(hù)和使用有關(guān)的圖文資料。 可見，軟件由兩部分組成：.機(jī)器可執(zhí)行的程序和數(shù)據(jù)；.機(jī)器不可執(zhí)行的，與軟件開發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。 軟件在開發(fā)、生產(chǎn)、維護(hù)和使用等方面與計(jì)算機(jī)硬件相比存在明顯的差異。深入理解軟件的定義需要了解軟件的特點(diǎn)：.軟件是一種

37、邏輯實(shí)體，而不是物理實(shí)體，具有抽象性。（軟件必須通過觀察、分析、思考、判斷、才能了解它的功能、性能等特性）.軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程。.軟件在運(yùn)行、使用期間不存在磨損、老化問題。.軟件在開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植問題。.軟件復(fù)雜性高，成本昂貴。軟件是人類有史以來生產(chǎn)的復(fù)雜度最高的工業(yè)產(chǎn)品。軟件的開發(fā)需要投入大量、高強(qiáng)度的腦力勞動(dòng)，成本高，風(fēng)險(xiǎn)大。.軟件的開發(fā)涉及諸多社會(huì)因素。軟件根據(jù)應(yīng)用目標(biāo)的不同，可分應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）2. 軟件工程 為了擺脫軟件危機(jī)，提出了軟件工程的概念。軟件工程學(xué)是研究軟件開發(fā)和維護(hù)的普

38、遍原理與技術(shù)的一門工程學(xué)科。所謂軟件工程是指采用工程的概念、原理、技術(shù)和方法指導(dǎo)軟件的開發(fā)與維護(hù)。軟件工程學(xué)的主要研究對(duì)象包括軟件開發(fā)與維護(hù)的技術(shù)、方法、工具和管理等方面。 軟件工程包括3個(gè)要素：方法、工具和過程，見表3-2。 軟件工程的核心思想是把軟件產(chǎn)品（就像其他工業(yè)產(chǎn)品一樣）看作是一個(gè)工程產(chǎn)品來處理。把需求計(jì)劃、可行性研究、工程審核、質(zhì)量監(jiān)督等工程化的概念引入軟件生產(chǎn)當(dāng)中，以期達(dá)到工程項(xiàng)目的三個(gè)基本要素：進(jìn)度、經(jīng)費(fèi)和質(zhì)量的目標(biāo)。3.2 軟件工程過程與軟件生命周期 軟件工程過程軟件工程過程：即把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。定義支持了軟件工程過程的兩個(gè)方面的內(nèi)涵。.軟件工程過程

39、是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動(dòng)。通常包含4種基本活動(dòng)：.P(Plan)軟件規(guī)格說明。規(guī)定軟件的功能及運(yùn)行時(shí)的限制。.D(Do)軟件開發(fā)。產(chǎn)生滿足規(guī)格說明的軟件。.C(Check)軟件確認(rèn)。確認(rèn)軟件能夠滿足客戶提出的要求。.A(Action)軟件演進(jìn).為滿足客戶的變更要求，軟件必須在使用的過程中演進(jìn). .從軟件開發(fā)的觀點(diǎn)看，它就是使用適當(dāng)?shù)馁Y源(包括人員、硬軟件工具、時(shí)間等)，為開發(fā)軟件進(jìn)行的一組開發(fā)活動(dòng)，在過程結(jié)束時(shí)將輸入(用戶要求)轉(zhuǎn)化為輸出(軟件產(chǎn)品). 所以，軟件工程的過程是將軟件工程的方法和工具綜合起來，以達(dá)到合理、及時(shí)地進(jìn)行計(jì)算機(jī)軟件開發(fā)的目

40、的。2. 軟件生命周期概念 軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為軟件生命周期。軟件生命周期分為3個(gè)時(shí)期共8個(gè)階段：.軟件定義期：包括問題定義、可行性研究和需求分析3個(gè)階段；.軟件開發(fā)期：包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)和測試4個(gè)階段；.運(yùn)行維護(hù)期：即運(yùn)行維護(hù)階段。軟件生命周期各個(gè)階段的活動(dòng)可以有重復(fù)，執(zhí)行時(shí)也可以有迭代，如圖3-1所示。 3. 軟件生命周期各階段的主要任務(wù) 在圖3-1中的軟件生命周期各階段的主要任務(wù)，見表3-3。 3.3 軟件設(shè)計(jì) 3.3.1 軟件設(shè)計(jì)基本概念 （1）按技術(shù)觀點(diǎn)分 從技術(shù)觀點(diǎn)上看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。 結(jié)構(gòu)設(shè)計(jì)定

41、義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過程設(shè)計(jì)則是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換為軟件的過程性描述。 （2）按工程管理角度分 從工程管理角度來看，軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。.概要設(shè)計(jì)將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式； .詳細(xì)設(shè)計(jì)確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。 3.3.2 軟件設(shè)計(jì)的基本原理 1. 軟件設(shè)計(jì)中應(yīng)該遵循的基本原理和與軟件設(shè)計(jì)有關(guān)的概念 （1）抽象：即一種思維工具，就是把事物本質(zhì)的共同特性取出

42、來而不考慮其他細(xì)節(jié)。軟件設(shè)計(jì)中考慮模塊化解決方案時(shí)，可以定出多個(gè)抽象級(jí)別。抽象的層次從概要設(shè)計(jì)到詳細(xì)設(shè)計(jì)逐步降低。 （2）模塊化 模塊是指把一個(gè)待開發(fā)的軟件分解成若干小的簡單的部分。模塊化是指解決一個(gè)復(fù)雜問題時(shí)自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過程。 （3）信息隱蔽 信息隱蔽是指在一個(gè)模塊內(nèi)包含的信息（過程或數(shù)據(jù)），對(duì)于不需要這些信息的其他模塊來說是不能訪問的。 （4）模塊獨(dú)立性 模塊獨(dú)立性是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)。內(nèi)聚性是信息隱蔽和局部

43、化概念的自然擴(kuò)展。一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模塊的模塊獨(dú)立性越強(qiáng)。一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。 2. 衡量軟件模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn) .內(nèi)聚性是度量一個(gè)模塊功能強(qiáng)度的一個(gè)相對(duì)指標(biāo)。內(nèi)聚是從功能角度來衡量模塊的聯(lián)系，它描述的是模塊內(nèi)的功能聯(lián)系。內(nèi)聚有如下種類，它們之間的內(nèi)聚度由弱到強(qiáng)排列：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚。 .耦合性是模塊之間互相連接的緊密程度的度量。耦合性取決于各個(gè)模塊之間接口的復(fù)雜度、調(diào)用方式以及哪些信息通過接口。耦合可以分為多種形勢，它們之間的耦合度由高到低排列：內(nèi)容耦合、公共耦合、外部耦

44、合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非直接耦合。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。一般較優(yōu)秀的軟件設(shè)計(jì)，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。 3.4 結(jié)構(gòu)化分析方法 1. 結(jié)構(gòu)化分析方法的定義 結(jié)構(gòu)化分析方法就是使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化英語、判定表和判定樹的工具，來建立一種新的、稱為結(jié)構(gòu)化規(guī)格說明的目標(biāo)文檔。結(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)據(jù)流、自頂向下、對(duì)系統(tǒng)的功能進(jìn)行逐層分解、以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。2. 結(jié)構(gòu)化分析方法常用工具 （1）數(shù)據(jù)流圖（DFD） 數(shù)據(jù)流圖是系統(tǒng)邏

45、輯模型的圖形表示，即使不是專業(yè)的計(jì)算機(jī)技術(shù)人員也容易理解它，因此它是分析員與用戶之間極好的通信工具。（2）數(shù)據(jù)字典（DD）【結(jié)構(gòu)化分析方法的核心】數(shù)據(jù)字典是對(duì)數(shù)據(jù)流圖中所有元素的定義的集合，是結(jié)構(gòu)化分析的核心。數(shù)據(jù)流圖和數(shù)據(jù)字典共同構(gòu)成系統(tǒng)的邏輯模型，沒有數(shù)據(jù)字典數(shù)據(jù)流圖就不嚴(yán)格，若沒有數(shù)據(jù)流圖，數(shù)據(jù)字典也難于發(fā)揮作用。 數(shù)據(jù)字典中有4種類型的條目：數(shù)據(jù)流、數(shù)據(jù)項(xiàng)、數(shù)據(jù)存儲(chǔ)和加工。 （3）判定表 有些加工的邏輯用語言形式不容易表達(dá)清楚，而用表的形式則一目了然。如果一個(gè)加工邏輯有多個(gè)條件、多個(gè)操作，并且在不同的條件組合下執(zhí)行不同的操作，那么可以使用判定表來描述。判定表由4部分組成：基本條件、條件

46、相、基本動(dòng)作、動(dòng)作項(xiàng)。（4）判定樹 判定樹、表沒有本質(zhì)的區(qū)別，可以用判定表表示的加工邏輯都能用判定樹表示。3. 軟件需求規(guī)格說明書 軟件需求規(guī)格說明書是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。它的特點(diǎn)是具有正確性、無歧義性、完整性、可驗(yàn)證性、一致性、可理解性、可修改性和可追蹤性。 3.5 軟件測試 3.5.1 軟件測試的目的和準(zhǔn)則 1. 軟件測試的目的 Grenford.J.Myers給出了軟件測試的目的：.測試是為了發(fā)現(xiàn)程序中的錯(cuò)誤而執(zhí)行程序的過程；.好的測試用例（test case）能發(fā)現(xiàn)迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤；.一次成功的測試是能發(fā)現(xiàn)至今為止尚未發(fā)現(xiàn)的錯(cuò)誤。 測試的目的是發(fā)現(xiàn)軟

47、件中的錯(cuò)誤，但是，暴露錯(cuò)誤并不是軟件測試的最終目的，測試的根本目的是盡可能多地發(fā)現(xiàn)并排除軟件中隱藏的錯(cuò)誤。 2. 軟件測試的準(zhǔn)則 根據(jù)上述軟件測試的目的，為了能設(shè)計(jì)出有效的測試方案，以及好的測試用例，軟件測試人員必須深入理解，并正確運(yùn)用以下軟件測試的基本準(zhǔn)則：.所有測試都應(yīng)追溯到用戶需求； .在測試之前制定測試計(jì)劃，并嚴(yán)格執(zhí)行；.充分注意測試中的群集現(xiàn)象；.避免由程序的編寫者測試自己的程序；.不可能進(jìn)行窮舉測試；.妥善保存測試計(jì)劃、測試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告，為維護(hù)提供方便。 3.5.2 軟件測試的方法和實(shí)施 1. 軟件測試方法 軟件測試具有多種方法，依據(jù)軟件是否需要被執(zhí)行，可以分為靜態(tài)

48、測試和動(dòng)態(tài)測試方法。如果依照功能劃分，可以分為白盒測試和黑盒測試方法。 （1）靜態(tài)測試和動(dòng)態(tài)測試 .靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。其中代碼檢查分為代碼審查、代碼走查、桌面檢查、靜態(tài)分析等具體形式；.動(dòng)態(tài)測試。靜態(tài)測試不實(shí)際運(yùn)行軟件主要通過人工進(jìn)行分析。動(dòng)態(tài)測試就是通常所說的上機(jī)測試，是通過運(yùn)行軟件來檢驗(yàn)軟件中的動(dòng)態(tài)行為和運(yùn)行結(jié)果的正確性。 動(dòng)態(tài)測試的關(guān)鍵是使用設(shè)計(jì)高效、合理的測試用例。測試用例就是為測試設(shè)計(jì)的數(shù)據(jù)，由測試輸入數(shù)據(jù)和預(yù)期的輸出結(jié)果兩部份組成。測試用例的設(shè)計(jì)方法一般分為兩類：黑盒測試方法和白盒測試方法。 （2）黑盒測試和白盒測試 .白盒測試(也稱結(jié)構(gòu)測試或邏輯

49、驅(qū)動(dòng)測試)。白盒測試是把程序看成裝在一只透明的白盒子里，測試者完全了解程序的結(jié)構(gòu)和處理過程。它根據(jù)程序的內(nèi)部邏輯來設(shè)計(jì)測試用例，檢查程序中的邏輯通路是否都按預(yù)定的要求正確地工作；其主要的方法有：邏輯覆蓋測試(語句覆蓋，路徑覆蓋，判定覆蓋，條件覆蓋，判定條件覆蓋)、基本路徑條件測試.黑盒測試(也稱功能測試或數(shù)據(jù)驅(qū)動(dòng)測試)。黑盒測試是把程序看成一只黑盒子，測試者完全不了解，或不考慮程序的結(jié)構(gòu)和處理過程。它根據(jù)規(guī)格說明書的功能來設(shè)計(jì)測試用例，檢查程序的功能是否符合規(guī)格說明的要求。其主要方法有：類等價(jià)劃分法、邊界值分析法、錯(cuò)誤推測法、因果圖等等。2. 軟件測試的實(shí)施 軟件測試過程分4個(gè)步驟，即單元測試

50、、集成測試、驗(yàn)收(確認(rèn))測試和系統(tǒng)測試。.單元測試是對(duì)軟件設(shè)計(jì)的最小單位-模塊(程序單元)進(jìn)行正確性檢驗(yàn)測試。單元測試的技術(shù)可以采用靜態(tài)分析和動(dòng)態(tài)測試。其主要依據(jù)是詳細(xì)設(shè)計(jì)說明書和源程序.集成測試是測試和組裝軟件的過程，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤，主要依據(jù)是概要設(shè)計(jì)說明書。集成測試所設(shè)計(jì)的內(nèi)容包括：軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件和非法輸入的測試等。集成測試時(shí)將模塊組裝成程序，通常采用兩種方式：非增量方式組裝和增量方式組裝。 .確認(rèn)(驗(yàn)收)測試的任務(wù)是驗(yàn)證軟件的功能和性能，以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，包括軟件配置是否完全、正確。確認(rèn)測試的實(shí)施首先運(yùn)用黑

51、盒測試方法，對(duì)軟件進(jìn)行有效性測試，即驗(yàn)證被測軟件是否滿足需求規(guī)格說明確認(rèn)的標(biāo)準(zhǔn)。 .系統(tǒng)測試是通過測試確認(rèn)的軟件，作為整個(gè)基于計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行（使用）環(huán)境下對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行一系列的集成測試和確認(rèn)測試。 系統(tǒng)測試的具體實(shí)施一般包括：功能測試、性能測試、操作測試、配置測試、外部接口測試、安全性測試等。 3.6 程序的調(diào)試 1.基本概念在對(duì)程序進(jìn)行了成功的測試之后將進(jìn)入程序調(diào)試（通常稱Debug，即排錯(cuò)）。程序的調(diào)試任務(wù)是診斷和改正程序中的錯(cuò)誤。調(diào)試主要在開發(fā)階段進(jìn)行。 程序調(diào)試活動(dòng)由兩部分組成，一是根據(jù)錯(cuò)誤的跡象確定

52、程序中錯(cuò)誤的確切性質(zhì)、原因和位置；二是對(duì)程序進(jìn)行修改，排除這個(gè)錯(cuò)誤。 程序調(diào)試的基本步驟： .錯(cuò)誤定位。從錯(cuò)誤的外部表現(xiàn)形式入手，研究有關(guān)部分的程序，確定程序中出錯(cuò)位置，找出錯(cuò)誤的內(nèi)在原因；.修改設(shè)計(jì)和代碼，以排除錯(cuò)誤； .進(jìn)行回歸測試，防止引進(jìn)新的錯(cuò)誤。2.軟件的調(diào)試方法調(diào)試的關(guān)鍵在于推斷程序內(nèi)部的錯(cuò)誤位置及原因。軟件調(diào)試可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯(cuò)，是主要的設(shè)計(jì)手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試的。主要的調(diào)試方法有：強(qiáng)行排錯(cuò)法、回溯法和原因排除法3種。.強(qiáng)行排錯(cuò)法：其過程課概括為設(shè)置斷點(diǎn)、程序暫停、觀察程序狀態(tài)、繼續(xù)運(yùn)行程序。這是目前使用較多、效

53、率較低的調(diào)試方法涉及的調(diào)試技術(shù)主要是設(shè)置斷點(diǎn)和監(jiān)視表達(dá)式。.回溯法：該方法適合于小規(guī)模程序的排錯(cuò)。即一旦發(fā)現(xiàn)了錯(cuò)誤，先分析錯(cuò)誤征兆，確定最先發(fā)現(xiàn)“癥狀”的位置，然后，從發(fā)現(xiàn)“癥狀”的地方開始，驗(yàn)程序控制流程，逆向跟蹤程序代碼，直到找到錯(cuò)誤根源或確定錯(cuò)誤產(chǎn)生的范圍。.原因排除法：它是通過演繹和歸納，以及二分法來實(shí)現(xiàn)的。第4章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)4.1 數(shù)據(jù)庫的基本概念 1. 數(shù)據(jù)數(shù)據(jù)是數(shù)據(jù)庫中存儲(chǔ)的基本對(duì)象，它是描述事物的符號(hào)記錄。計(jì)算機(jī)中的數(shù)據(jù)分為兩部分：一般存放在計(jì)算機(jī)內(nèi)存中的臨時(shí)性數(shù)據(jù)和持久性數(shù)據(jù)，數(shù)據(jù)庫系統(tǒng)處理的就是這種持久性數(shù)據(jù)。2. 數(shù)據(jù)庫數(shù)據(jù)庫是長期儲(chǔ)存在計(jì)算機(jī)內(nèi)、有組織的、可共享的大

54、量數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享，所以數(shù)據(jù)庫技術(shù)的根本目標(biāo)是解決數(shù)據(jù)共享問題。 3. 數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)（DBMS，Database Management System）是數(shù)據(jù)庫的機(jī)構(gòu)，它是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操作、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)系統(tǒng)的核心。 為完成數(shù)據(jù)庫管理系統(tǒng)的功能，數(shù)據(jù)庫管理系統(tǒng)提供相應(yīng)的數(shù)據(jù)語言：數(shù)據(jù)定義語言、數(shù)據(jù)操縱語言、數(shù)據(jù)控制語言。 4.2 數(shù)據(jù)庫系統(tǒng)的發(fā)展和基本特點(diǎn) 1. 數(shù)據(jù)庫系統(tǒng)的發(fā)展 數(shù)據(jù)管理技術(shù)的發(fā)展經(jīng)歷了3個(gè)階段：人工管理階

55、段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。 關(guān)于數(shù)據(jù)管理三個(gè)階段中的軟硬件背景及處理特點(diǎn)，簡單概括可見表4-1。 2. 數(shù)據(jù)庫系統(tǒng)的特點(diǎn) .數(shù)據(jù)的集成性在數(shù)據(jù)庫系統(tǒng)中采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)方式，如在關(guān)系數(shù)據(jù)庫中采用二維表作為統(tǒng)一結(jié)構(gòu)方式。在數(shù)據(jù)庫系統(tǒng)中按照多個(gè)應(yīng)用的需要組織全局的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)(即數(shù)據(jù)模式)，數(shù)據(jù)模式不僅可以建立全局的數(shù)據(jù)結(jié)構(gòu)，還可以建立數(shù)據(jù)間的語義聯(lián)系從而構(gòu)成一個(gè)內(nèi)在緊密聯(lián)系的數(shù)據(jù)整體。數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)模式是多個(gè)應(yīng)用共同的、全局的數(shù)據(jù)結(jié)構(gòu)，而每個(gè)應(yīng)用的數(shù)據(jù)則是全局結(jié)構(gòu)中的一部分，稱為局部結(jié)構(gòu)(即視圖)，這種全局與局部的結(jié)構(gòu)模式構(gòu)成了數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)集成性的主要特征。.數(shù)據(jù)高度共享性與低冗余性 減少冗余性以避免數(shù)據(jù)的不同出現(xiàn)是保證系統(tǒng)一致性的基礎(chǔ)。.數(shù)據(jù)獨(dú)