一、算法的基本概念算法是解題方案的準確而完整的描述，它不等于程序，也不等計算方法。1．算法的基本特征可行性(effectiveness)

每一步要能實現(xiàn)

執(zhí)行的結(jié)果達到預(yù)期的目的確定性(definiteness)---非多義性有窮性(finiteness)擁有足夠的情報----輸入數(shù)據(jù)結(jié)構(gòu)與算法一、算法的基本概念2．算法的基本要素算法中對數(shù)據(jù)的運算和操作算術(shù)運算邏輯運算關(guān)系運算數(shù)據(jù)傳輸算法的控制結(jié)構(gòu)順序選擇循環(huán)一、算法的基本概念3．算法設(shè)計基本方法列舉法（工作量大找規(guī)律分類優(yōu)化）歸納法（列舉少量找出一般關(guān)系可能是錯的）遞推（也是歸納從初始條件逐次推出中間結(jié)果或最后結(jié)果）遞歸（也是歸納從算法本身到達遞歸邊界）減半遞推技術(shù)（分而治之規(guī)模減半重復(fù)減半）回溯法（試探八皇后問題）一、算法的基本概念算法的復(fù)雜度1.時間復(fù)雜度指執(zhí)行算法所需要的計算工作量算法工作量=f(n)n是問題的規(guī)模與下列因素無關(guān)：書寫算法的程序設(shè)計語言編譯產(chǎn)生的機器語言，代碼質(zhì)量機器執(zhí)行指令的速度算法工作量的分析方法：第一種情況：在同一個問題規(guī)模下，算法執(zhí)行所需的基本運算次數(shù)可能與輸入有關(guān)（例如順序查找），可以用兩種方法分析算法工作量(1)平均性態(tài)

當問題規(guī)模一定時，如果算法執(zhí)行所需的基本運算次數(shù)取決于某一個特定的輸入時，用此方法分析工作量

A(n)=

pi是某個元素(x)出現(xiàn)的概率,ti

是在輸入某個元素(x)時所執(zhí)行的基本運算次數(shù)n+1∑i=1piti(2)最壞情況復(fù)雜性

是指當問題規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)

W(n)=max(ti)

W(n)比A(n)更有實用價值第二種情況：算法的計算工作量也可能與輸入無關(guān)（例如n階矩陣相乘），在所有可能的輸入下，算法所執(zhí)行的基本運算次數(shù)是一定的，此時A(n)=W(n)2.空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間內(nèi)存空間包括：1）算法程序占用空間2）輸入的初始數(shù)據(jù)占用空間3）算法執(zhí)行中所需的額外空間二、數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)研究三個問題:(1)邏輯結(jié)構(gòu):數(shù)據(jù)集合中各元素之間所固有的邏輯關(guān)系(2)存儲結(jié)構(gòu):各數(shù)據(jù)元素在計算機中的存儲關(guān)系(3)運算:對各種數(shù)據(jù)結(jié)構(gòu)進行運算數(shù)據(jù)結(jié)構(gòu)研究的目的:(1)提高數(shù)據(jù)處理速度(2)節(jié)省存儲空間1.什么是數(shù)據(jù)結(jié)構(gòu)例如:無序表的順序查找和有序表的對分查找3516788543293321544616212933354346547885無序表:若查找的元素正好是第一個,次數(shù)少若查找的元素是最后一個或查找的元素不在表中的情況,無序表有序表則次數(shù)多(1)數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素的信息(即數(shù)據(jù)元素的集合,記為D)和各數(shù)據(jù)元素之間的前后件關(guān)系(記為R)。與它們在計算機中的存儲位置無關(guān).記B為數(shù)據(jù)結(jié)構(gòu),則

B=(D,R)例如:一年四季的數(shù)據(jù)結(jié)構(gòu)表示為:

B=(D,R)

D={春,夏,秋,冬}

R={(春,夏),(夏,秋),(秋,冬)}

用二元組表示數(shù)據(jù)元素之間的前后件關(guān)系(2)數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式注意:各數(shù)據(jù)在計算機中的存儲位置關(guān)系與它們的邏輯關(guān)系不一定是相同的.

一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有：

順序

鏈接

索引

2、數(shù)據(jù)結(jié)構(gòu)的圖形表示例1:一年四季春夏秋冬結(jié)點

例2:家庭成員父親

兒子女兒

有向箭頭前件指向后件例3:用圖形表示數(shù)據(jù)結(jié)構(gòu)B=(D,R)D={d1,d2,d3,d4,d5,d6,d7}R={(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)}d1d2d3d7d4d6d5

根結(jié)點(無前件)終端結(jié)點(葉子結(jié)點無后件)內(nèi)部結(jié)點3.線性結(jié)構(gòu)與非線性結(jié)構(gòu)（1）線性結(jié)構(gòu):有且只有一個根結(jié)點每個結(jié)點最多有一個前件,也最多有一個后件注意:在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)該是線性結(jié)構(gòu)如:

ABCD將A刪除就不滿足了(2)非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)就是非線性結(jié)構(gòu)例如：家庭成員關(guān)系對非線性結(jié)構(gòu)的存儲與處理比線性結(jié)構(gòu)復(fù)雜得多三、線性表及其順序存儲結(jié)構(gòu)1、線性表的基本概念例如：一個N維向量、英文字母表、一年中的四季，一個一維數(shù)組等都是線性表，其中的每一個值都是線性表的一個數(shù)據(jù)元素（結(jié)點）。此時的數(shù)據(jù)元素是一個簡單項。又如：一個學(xué)生表也是線性表，其中的每條記錄就是線性表的一個數(shù)據(jù)元素（結(jié)點）。此時的數(shù)據(jù)元素是一個復(fù)雜項。2、線性表的順序存儲結(jié)構(gòu)兩個基本特點:（1）線性表中所有元素所占存儲空間是連續(xù)的（2）線性表中所有元素在存儲空間中是按邏輯順序依次存放的2、線性表的順序存儲結(jié)構(gòu)線性表中每一個數(shù)據(jù)元素的存儲地址ADR(ai)由該元素在線性表中的位置序號i唯一確定ADR(ai)=ADR(a1)+(i-1)k

k表示每個元素占用的字節(jié)數(shù)3、順序表的插入運算（元素后移、上溢）291856633524314712345678910872918566335243147123456789101429871856633524314712345678910如再插入，將上溢1234567思考：在末尾插入一個元素，在表頭插入一個元素，在表中i位置處插入一個元素，表中其他元素移動情況。結(jié)論：在線性表的存儲情況下，要插入一個元素，效率低；特別是在大表中，消耗的時間更多。4、順序表的刪除運算2918566335243147123456789101856633524314712345678910185663352447123456789101256734思考：在末尾刪除一個元素，在表頭刪除一個元素，在表中i位置處刪除一個元素，表中其他元素移動情況。結(jié)論：在線性表的存儲情況下，要刪除一個元素，效率低；特別是在大表中，消耗的時間更多。故：線性表在順序存儲結(jié)構(gòu)下的插入與刪除運算，比較適合小線性表或者其中元素不常變動的線性表。四、棧和隊列1、棧（stack）及其基本運算它是限定在一端進行插入與刪除的線性表此端稱為棧頂，用指針top來指示；另一端不允許做任何操作，稱為棧底，用指針bottom來指示。所謂“先進后出”表或者“后進先出”表。插入一個元素稱為入棧，刪除一個元素成為退棧。棧示意圖an……a2a1入棧退棧棧頂top棧底bottom2、隊列（queue）及其運算它是在一端（隊尾）插入，用尾指針rear指示；另一端（隊頭）刪除，用頭指針front指示的線性表。所謂“先進先出”表或者“后進后出”表往隊列的隊尾插入一個元素稱為入隊運算，從隊列的隊頭刪除一個元素稱為退隊運算。隊列示意圖ABCDEFfrontrear退隊入隊五、線性鏈表一個存儲單元對應(yīng)一個數(shù)據(jù)結(jié)點，這個存儲單元稱為存儲結(jié)點，簡稱結(jié)點。1、線性鏈表線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表數(shù)據(jù)域指針域存儲序號12…I…m線性鏈表的存儲空間數(shù)據(jù)域指針域V（i）NEXT(i)存儲序號i線性鏈表的一個存儲結(jié)點數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)nNull……h(huán)ead線性鏈表的邏輯結(jié)構(gòu)例：設(shè)線性表為（a1,a2,a3,a4,a5）,存儲空間有10個存儲結(jié)點，則存儲情況如圖：a29a11a410a35a50123456789103head物理狀態(tài)圖a1head線性鏈表的邏輯狀態(tài)圖a2a3a4a50319510以上是線性單鏈表，特點是：每個結(jié)點只有一個指針域，由它只能找到后件結(jié)點，而不能找到前件結(jié)點。為彌補此缺點，每個結(jié)點設(shè)兩個指針，即左指針（Llink）用來指向其前件；右指針(Rlink)用來指向其后件。此線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖：0DRLDRLD0…………h(huán)ead域中值為0，表示為空Null,即不指向任何結(jié)點2、帶鏈的棧AnAn-1A10Top…AnAn-1A10Top…An+1AnAn-1A10Top…入棧操作退棧操作3、帶鏈的隊列A1A2An0front…A1A2An…An+10A1A2An0…rearfrontrearrearfront入隊操作退隊操作六、樹與二叉樹1、樹的基本概念樹（tree）是一種非線性結(jié)構(gòu)。RKPQDBENOTCHXYSWZAMFGL根結(jié)點葉子結(jié)點根結(jié)點、父結(jié)點、子結(jié)點、葉子結(jié)點結(jié)點的度、樹的度（后件個數(shù)）樹的深度（層次個數(shù)）子樹重要概念2、二叉樹及其基本性質(zhì)特點：（1）非空的二叉樹只有一個根結(jié)點（2）每個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹；沒有左右子樹的結(jié)點就是葉子結(jié)點

RKDENOTBB只有根結(jié)點的二叉樹二叉樹的基本性質(zhì)

性質(zhì)1：在二叉樹的第K層上，最多有2k-1(k>=1)個結(jié)點。

性質(zhì)2：深度為m的二叉樹最多有2m-1個結(jié)點。（等比數(shù)列求和：S=a1(1-qn)

/(1-q)）

性質(zhì)3：在任意一棵二叉樹中，（出）度為0的結(jié)點（即葉子結(jié)點）總是比（出）度為2的結(jié)點多一個。（所有的出度=所有入度+1）

性質(zhì)4：具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分。（由性質(zhì)2得出）滿二叉樹與完全二叉樹（1）滿二叉樹即除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。也就是說，每一層上的結(jié)點數(shù)都達到最大值。(即：除葉子結(jié)點外的所有結(jié)點均有兩個子結(jié)點)滿二叉樹非滿（2）完全二叉樹即除最后一層外，每一層上的結(jié)點數(shù)都達到最大值；在最后一層上只缺少右邊的若干結(jié)點。

兩者關(guān)系：滿二叉樹也是完全二叉樹，反之則不一定。完全二叉樹的基本性質(zhì)

性質(zhì)5：具有n個結(jié)點的完全二叉樹的深度為[log2n]+1（由性質(zhì)4得出）

性質(zhì)6：設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每層從左到右）用自然數(shù)1，2，3，…，n給結(jié)點進行編號，則對編號為k（k=1,2,3,…,n）的結(jié)點有以下結(jié)論：（1）若k=1,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1,則該結(jié)點的父結(jié)點編號為int(k/2)（2）若2k<=n,則編號為k的結(jié)點的左子結(jié)點編號為2k;否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）（3）若2k+1<=n,則編號為k的結(jié)點的右子結(jié)點

3、二叉樹的存儲結(jié)構(gòu)FCEDHGPAB4F6C90E2A08D0130H010P05G110B0BT二叉樹二叉鏈表的邏輯狀態(tài)iL(i)V(i)R(i)LchildRchildValue二叉樹存儲結(jié)點結(jié)構(gòu)10P020A0346F9513G162C87811D090E510110B012130H0BT二叉鏈表的物理狀態(tài)4、二叉樹的遍歷（1）前序遍歷（DLR）

根左右（2）中序遍歷（LDR）

左根右（3）后序遍歷（LRD）

左右根例如：表達式（a+b）*d/2用下列邏輯結(jié)構(gòu)，采用前序遍歷就可以實現(xiàn)(a*b/d2+)七、查找技術(shù)1、順序查找從第一個元素開始，依次比較，若相等，則表示找到。這對于大表來說，效率較低。在最壞的情況下，順序查找需要比較n次。2、二分法查找此方法只適用于順序存儲的有序表。效率比順序查找高。對于長度為n的有序線性表，在最壞的情況下，二分法只需要比較log2n次，而順序查找需要比較n次。八、排序技術(shù)1、交換類排序（1）冒泡排序（相鄰元素比較）假設(shè)線性表的長度為n，在最壞情況下，需要比較的次數(shù)為n(n-1)/2（2）快速排序法（選取元素，不斷分割）2、插入類排序（1）簡單插入排序法（提取元素，插入有序表）將無序序列中的各元素（先保存到一個變量T中）依次插入到已經(jīng)有序的線性表。每一次比較后最多移掉一個逆序。因此其效率與冒泡法相同，在最壞情況下，需要比較的次數(shù)為n(n-1)/2（2）希爾排序法（先分割成子序列，再插入排序）將相隔某個增量h的元素構(gòu)成一個子序列。在排序的過程中，逐次減小這個增量，最后當h減到1時，進行一次插入排序，排序完成。增量一般取ht=n/2k

(k=1,2,…,[log2n])其中n為待排序序列的長度。希爾排序?qū)τ诿總€子表仍然是插入排序，但是，在子表中每進行一次比較就有可能移去整個線性表中的多個逆序，從而改善了排序性能。其效率與所選取的增量序列有關(guān)，如果選取上述增量，則在最壞情況下，需要比較次數(shù)為O（n1.5）3、選擇類排序（1）簡單選擇類排序（選擇，交換）掃描整個線性表，選取最小元素，交換到表的最前面；對剩下的子表采用同樣的方法，直到子表是空為止。最壞情況下，比較次數(shù)n(n-1)/2（2）堆排序軟件工程基礎(chǔ)一、軟件的生命周期指軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。

可行性研究需求分析概要設(shè)計詳細設(shè)計實現(xiàn)測試使用維護退役定義階段開發(fā)階段維護階段二、結(jié)構(gòu)化分析方法1、需求分析2、分析工具

a.數(shù)據(jù)流圖（DFD）

b.數(shù)據(jù)字典（DD）c.判定樹

d.判定表3、軟件需求規(guī)格說明書（SRS）加工（轉(zhuǎn)換）數(shù)據(jù)流存儲文件（數(shù)據(jù)源）源，潭（系統(tǒng)之外的實體）三、結(jié)構(gòu)化設(shè)計方法1、軟件設(shè)計的基本原理（1）抽象（2）模塊化（3）信息隱蔽（4）模塊獨立性

a.內(nèi)聚性：是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度。一個模塊的內(nèi)聚性越強，那么其獨立性就越強。

b.耦合性：是模塊間互相連接的緊密程度。一個模塊與其他模塊的耦合性越強,則其獨立性越弱。內(nèi)聚與耦合的關(guān)系：內(nèi)聚性越強那么耦合性就越弱。應(yīng)該做到高內(nèi)聚，低耦合。2、概要設(shè)計（1）基本任務(wù)：設(shè)計軟件的系統(tǒng)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計編寫概要設(shè)計文檔概要設(shè)計文檔評審（2）設(shè)計工具

a.結(jié)構(gòu)圖

b.數(shù)據(jù)流圖（變換型、事務(wù)型）（3）設(shè)計準則（P66）3、詳細設(shè)計（1）基本任務(wù)：

a.為軟件結(jié)構(gòu)中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)。

b.用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。（2）設(shè)計工具

a.圖形工具：程序流程圖PFD，N-S，PAD，HIPOPAD:問題分析圖b.表格工具：判定表

c.語言工具：PDL（偽碼）HIPO圖(hierarchyplusinput-process-output)是IBM公司于70年代中期在層次結(jié)構(gòu)圖(structurechart)的基礎(chǔ)上推出的一種描述系統(tǒng)結(jié)構(gòu)和模塊內(nèi)部處理功能的工具(技術(shù))。HIPO圖由層次結(jié)構(gòu)圖和IPO圖兩部分構(gòu)成,前者描述了整個系統(tǒng)的設(shè)計結(jié)構(gòu)以及各類模塊之間的關(guān)系,后者描述了某個特定模塊內(nèi)部的處理過程和輸入/輸出關(guān)系。

HIP0圖一般由一張總的層次化模塊結(jié)構(gòu)圖和若干張具體模塊內(nèi)部展開的IPO圖組成,如圖3.13和圖3.14所示。圖3.13是一張有關(guān)修改庫存文件部分內(nèi)容模塊的層次模塊結(jié)構(gòu)圖。圖3.14是圖3.13中若干張模塊展開圖(I