全國計算機等級考試二級公共基礎知識1

《全國計算機等級考試二級公共基礎知識1》由會員分享，可在線閱讀，更多相關《全國計算機等級考試二級公共基礎知識1（134頁珍藏版）》請在裝配圖網上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,*,計算機二級考試公共基礎之,《,數據結構與算法,》,1,．,4,算法與算法分析,算法與算法分析,一 算法的概念,,算法是對特定問題求解步驟的一種描述,,算法的基本特征：,,1,）,可行性,：組成算法的操作必須能夠在計算機上實現。,2,）,確定性,：算法的每一步操作必須清晰無二義性。,3,）,有窮性,：算法必須在有限步內結束；,4,）,有足夠的情報,：,0,個或多個輸入；,1,個或多個輸出；,算法描述的方法很多，如

2、自然語言、框圖、類,C,等,,例,:,求兩個正整數,m,，,n,中的最大數,MAX,的算法,（,1,）,若,m > n,則,max=m,（,2,）,若,m <= n,則,max=n,,程序,=,算法,+,數據結構,,1,、,正確性,：,(1),沒有語法錯誤； ,(2),對于幾組輸入數據能夠得出滿足要求的結果；,(3),對于精心選擇的典型而苛刻的幾組輸入數據能夠得到滿足要求的結果。,(4),對于一切合法的輸入數據都能產生滿足要求的結果。,2,、,可讀性：,便于閱讀、理解、調試、修改；,3,、,健壯性：,對不合法的輸入能作出正確的反映與處理；,4,、,高效性：,執(zhí)行時間短（,時間復雜度,）、,需

3、求存儲空間?。?空間復雜度,）,評價算法標準,,1,時間復雜度,T,（,n,）,以求解問題的基本操作的,執(zhí)行次數,作為算法時間的度量。,算法與算法分析,O,（,n,3,）,,稱為矩陣相乘算法時間復雜度；,O,（,n,3,）表示矩陣相乘算法執(zhí)行時間與,n,3,成正比,,,即,O,（,n,3,）與,n,3,同一數量級；,,例：,n,階矩陣相乘的算法,For ( i = 1; i<=n; i++ ) For (j = 1; j<=n; j++ ),{ c[ i ][ j ] = 0 ; For (k = 1; k<= n; k++ )

4、 c[ i ][ j ] += a[ i ][ k ] * b[ k ] [ j ],},,乘法 加法,執(zhí)行次數均為,n,3,,,矩陣相乘的基本運算：乘法 加法；,,數據結構中常用的時間復雜度頻率計數有,7,個：,,O(1),常數型,O(n),線性型,O(n,2,),平方型,,O(n,3,),立方型,O(2,n,),指數型,,O(log,2,n),對數型,O(nlog,2,n),二維型,2,算法空間復雜度 用執(zhí)行算法所需的,內存空間的大小,作為算法所需空間的度量。 設執(zhí)行算法所需的內存空間是問題規(guī)模,n,的某個函數,g(n),,則算法空間復雜度記作

5、：,S,（,n,）,= O(g(n)),表示算法內存空間的增長率,與,g(n),的增長率相同,例計算,,解法,1,先計算,x,的冪,,,存于,power[ ],中,,,再分別乘以相應的系數,,# define N 100,float evaluate (float coef[ ], float x , int n ),{ float power[N], f; int i;,for (power[ 0]=1, i = 1; i<=n; i++ ) power[i]=x*power[i-1];  for (f = 0, i=0; i<=N; i ++) f=f+coef[i]*

6、power[i];,return(f);,},問題規(guī)模為,n,,算法時間復雜度,: O(n),空間復雜度：,O(N),(1),在計算機中，算法是指（ ）。,A.,查詢方法,B.,加工方法,C.,解題方案的準確而完整的描述,D.,排序方法,(2),下列敘述中正確的是（ ）。,A),算法的效率只與問題的規(guī)模有關，而與數據的存儲結構無關,B),算法的時間復雜度是指執(zhí)行算法所需要的計算工作量,C),數據的邏輯結構與存儲結構是一一對應的,D),算法的時間復雜度與空間復雜度一定相關,(3),算法的有窮性是指（ ）。,A,）算法程序的運行時間是有限的,B,）算法程序所處理的數據量是有限的,

7、C,）算法程序的長度是有限的,D,）算法只能被有限的用戶使用,(c),(B),算法習題,(A),(4),算法的時間復雜度是指,( ),,A),算法的執(zhí)行時間,,B),算法所處理的數據量,,C),算法程序中的語句或指令條數,,D),算法在執(zhí)行過程中所需要的基本運算次數,(5),算法的空間復雜度是指,( ),A,）算法在執(zhí)行過程中所需要的計算機存儲空間,B,）算法所處理的數據量,C,）算法程序中的語句或指令條數,D,）算法在執(zhí)行過程中所需要的臨時工作單元數,(6),下列敘述中正確的是,( ),,A,）一個算法的空間復雜度大，則其時間復雜度也必定大,,B,）一個算法的空間復雜度大，

8、則其時間復雜度必定小,,C,）一個算法的時間復雜度大，則其空間復雜度必定小,,D,）上述三種說法都不對,(D),計算工作量,(A),(D),數據結構,大量的數據元素在計算機中如何組織，以便提高數據處理的效率，并且節(jié)省計算機的存儲空間，這是進行數據處理的關鍵問題。,數據結構是指相互有關聯的數據元素的集合，既按某種邏輯關系把一批數據組織起來，按一定的映象方式把它存放在計算機的存儲器中，并在這些數據上定義一個運算的集合。,,歸納為三部分：,,邏輯結構、存儲結構和運算集合,。,,1.,邏輯結構,,數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。,,數據的邏輯結構包含：,（,1,）表示數據元素的信

9、息；,（,2,）表示各數據元素之間的前后件關系。,例：,1.,一年四季的數據結構,,B=(D,R),D={,春，夏，秋，冬,},R={(,春，夏,) ,(,夏，秋,),(,秋，冬,)},2.,家庭成員的數據結構,,B=(D,R),D={,父親，兒子，女兒,},R={(,父親，兒子,) ,(,父親，女兒,)},,春,夏,秋,冬,數據結構的圖形表示,父親,兒子,女兒,常見的,邏輯結構,有：,線性結構、樹形結構和圖形結構。,,,,,,,,,,,,,,,,,線性結構,樹形結構,圖形結構,① 線性結構,結構中的每個元素之間存在一個對一個的關系；,線性表、棧、隊、字符串、數組,② 樹形結構 （非線性）

10、,結構中的每個元素之間存在一個對多個的關系；,③ 圖形結構或網狀結構（非線性）,結構中的每個元素之間存在多個對多個的關系。,,2.,存儲結構（物理結構）,計算機在實際進行數據處理時，被處理的各數據元素總是被存放在計算機的存儲空間中，并且，各數據元素在計算機存儲空間中的位置與它們的邏輯關系不一定是相同的，而且一般也不可能相同。,如：一年四季,家庭成員 計算機存儲空間怎樣存放？,存儲結構指數據結構在計算機存儲空間中的具體實現。,常見的存儲結構有：,順序存儲結構 鏈式存儲結構 索引存儲結構,3.,數據的運算,檢索,插入,刪除,更新,排序,,通常，一個數據結構中的元素結點可能

11、是動態(tài)變化的。根據需要或在處理過程中，可以在一個數據結構中增加一個新結點（插入運算），也可以刪除某個結點（刪除運算），除此之外，對數據結構的運算還有查找、分類、合并、分解、復制和修改。,數據結構是研究數據和數據之間關系的一門學科，研究以下三方面內容：,數據的邏輯結構,數據的存儲結構,數據的運算,常見的數據結構,,,1.,線性表,,,2.,棧和隊列,,,3.,樹,１． 線性表（,Linear List,）,線性表是由,n,（,n≥0,）個數據元素,,a,1,，,a,2,，,…,，,a,i,，,…,，,a,n,組成的一個有限序列。,線性表是最簡單、最常用的數據結構。,,棧、隊列、串,是特殊的線性表

12、,數組和廣義表,是線性表的擴展,--,線性結構,,,例、英文字母表（,A, B, C, D, E,?,Z,）。 某單位的電話號碼簿。,線性表的概念,設,A=,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）是一線性表，,1,） 同一線性表中的元素必須是,同一類型,的；,2,） 在表中,a,i-1,,領先于,a,i,，,a,i,,領先于,a,i+1,,，稱,a,i-1,,是,a,i,,的前件，,a,i+1,,是,a,i,,的后件；,3,） 在線性表中，除第一個元素和最后一個元素之外，其他元素都有且,僅有一個

13、前件，有且僅有一個后件,；,4,） 線性表中元素的個數,n,稱為線性表的長度，,n=0,時稱為空表；,,用,一組連續(xù)的內存單元依次存放,線性表的數據元素。,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,,線性表（,a,1,,a,2,,a,3,,... a,n,,）,的順序存儲結構,用順序存儲結構存儲的線性表,——,稱為順序表,線性表的順序存儲和實現,一 、 線性表的順序存儲結構,,線性表的順序存儲和實現,說明：,元素之間的邏輯關系，通過元素的存儲順序表示出來,.,設線性表中每個數據元素占,t,個存儲單元，那么，在順序存儲結構中，線性表的第,i,個元素的存儲位置與第,1,個元

14、素的存儲位置的關系是：,,,Loc(a,i,) = Loc( a,1,)+ ( i – 1),,t,其中,Loc( a,1,),基地址，隨機存取,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,,t,個單元,Loc( a,1,),Loc(a,i,),線性表的順序存儲和實現,,插入位置 移動元素個數,1???????????????????????????? n 2???????????????????????????? n-1? i n

15、-i+1? n 1 n+1 0,插入算法時間復雜度分析,算法時間復雜度取決于移動元素的個數，移動元素的個數不僅與表長有關，而且與插入位置有關。,,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,0,1,i-1,i-2,n-1,.,.,由此可見在順序表中插入一個元素 ，平均要移動表的一半元素。表長為,n,的順序表，插入算法的時間復雜度為,O,（,n,）,假設在線性表的任何位置插入元素的概率相

16、同，即,,pi= 1/(n+1),,設,p,i,為在第,i,個元素之前插入元素的概率，在長度為,n,的順序表中插入一個元素，所需移動元素個數數學期望值為：,,刪除算法時間復雜度分析,假設在線性表的任何位置刪除元素的概率相同，即,,pi= 1/n,刪除,所需移動元素個數的數學期望值：,,,線性表的順序存儲和實現,,順序表是線性表最簡單的一種存儲結構,,,小結,順序表的特點：,1,通過元素的存儲順序反映 線性表中,數據元素之間的邏輯關系；,2,可隨機存取順序表的元素；,3,順序表的插入、刪除操作要通過,移動,元素實現；,線性表的鏈式存儲和實現,,線性表的鏈式存儲結構是用一組任意的存儲單元存儲線性表

17、的各個數據元素。,為了表示線性表中元素的先后關系，每個元素除需要存儲自身的信息外，還要保存直接前趨元素或直接后繼元素的存儲位置。,,a,i,+1,,a,1,,a,i-,1,,a,2,,a,i,,a,n,一 線性鏈表的概念,,1,線性鏈表,,a,4,,a,3,,a,1,a,2,,,,0,,1010,,,,1024,,,1014,1010,1012,1014,1016,1018,1020,1022,1024,1026,,用一組任意的存儲單元存儲線性表中的數據元素，對每個數據元素保存自身信息和直接后繼元素的存儲位置。,,用鏈表存儲線性表時，數據元素之間的關系是通過,保存直接后繼元素的存儲位置來表

18、示的,,ai-1,,a,i,,a,2,,a1,,a,i+,1,n,,a,n,,結點：,數據元素及直接后繼的存儲位置（地址）組成一個數據元素的存儲結構，稱為一個結點；,結點的數據域 ：,保存數據元素,;,結點的指針域 ：,保存數據元素直接后繼的存儲地址,;,,線性鏈表有關術語,存儲數據元素,存儲后繼結點,存儲地址,,結點,數據域,指針域,頭指針：,存放線性鏈表中第一個結點的存儲地址,;,空指針：,不指向任何結點，線性鏈表最后一個結點的指針通常是空指針,;,頭結點：,鏈表的第一個元素結點前的附加結點；,帶頭結點的線性鏈表,：第一個元素結點前增加一個附加結點的線性鏈表稱為 帶頭結點的線性鏈表；,,h

19、ead,是頭指針,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,頭結點,,空指針,head,線性鏈表的每個結點中只有一個指針域,故也稱為,單鏈表,插入結點,(,存,a,),q=(LNODE *)malloc(sizeof(LNODE));,q->deta=‘a’;,q->next=p-> next;,p-> next =q;,head,,z,,y,,x,,p,,y,,x,,z,,p,head,,a,q,插入操作功能：在線性鏈表的第,i,個元素結點之前插入一個新元素結點,e,；,插入操作圖示：,插入前,插入后,,,a,i-,1,,a,i,,a,2,,a,1,,a

20、,i+,1,n,,a,n,,head,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,e,head,,4,）,刪除結點,q=p->next;,p-> next =q-> next;,free(q);,head,,z,,y,,x,,q,,y,,x,,z,,q,head,p,p,刪除前,刪除后,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,head,,a,i-,1,,ai,,a,2,,a,1,,a,i+,1,n,,a,n,,,head,p,p,q,q,線性鏈表小結,線性鏈表是線性表的一種鏈式存儲結構,,線性鏈表的特點,,,1,通過保存

21、直接后繼元素的存儲位置來表示,數據元素之間的邏輯關系；,,2,插入、刪除操作通過修改結點的指針實現；,,3,不能隨機存取元素,；,1,循環(huán)鏈表的概念,循環(huán)鏈表的特點是將線性鏈表的最后一個結點的指針指向鏈表的第一個結點（首尾相連的單鏈表）,2,循環(huán)鏈表圖示,循環(huán)鏈表,(a),非空表 （,b,）空表,,head,,,,,,,head,a,1,a,n,循環(huán)鏈表,說明,,在解決某些實際問題時循環(huán)鏈表可能要比線性鏈表方便些。如將一個鏈表鏈在另一個鏈表的后面；,對循環(huán)鏈表，有時不給出頭指針，而是給出尾指針,,a,,,,a1,an,a->next,給出尾指針的循環(huán)鏈

22、表,,,,雙向鏈表,,循環(huán)單鏈表，雖然從任一結點出發(fā)沿著指針鏈能找到其前件，但時間耗費是,O(n),。如果希望從表中快速確定某一個結點的前件，另一個解決方法是在鏈表的每個結點里再增加一個指向其前件的指針域,prior,。 這樣形成的鏈表中就有兩條方向不同的鏈，稱為雙向鏈表。,線性表小結,,線性表的順序存儲結構,—,順序表，,鏈式存儲結構,----,線性鏈表,,,循環(huán)鏈表,,,雙向鏈表,.,不同的存儲結構，線性表的同一操作的算法是不同的,:,,在順序存儲結構下，線性表的插入、刪除操作，通過移動元素實現,;,,在線性鏈表存儲結構下，線性表的插入、刪除操作，通過修改指針實現。,2,棧,棧是限定僅能

23、在表尾一端進行插入、刪除操作的線性表,,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）,插入,刪除,棧的概念,一??? 什么是棧,?,將表中允許進行插入、刪除操作的一端稱為,棧頂,(Top),，,棧頂的當前位置是動態(tài)變化的，由一個棧頂指針指示其位置。,表的另一端稱為棧底,(Bottom),。,當棧中沒有元素時稱為空棧。,棧的插入操作稱為,進?；蛉霔?，刪除操作稱為,出?；蛲藯?。,,棧,,棧的示意圖,出棧,進棧,棧的特點,后進先出,第一個進棧的元素在棧底，最后一個進棧的元素在棧頂，,第一個出棧的元素為棧頂元素，,最后一個出棧的元

24、素為棧底元素,,,棧頂,棧底,a,n,a,2,a,1,,,小 結,,,1,棧是限定僅能在表尾一端進行插入、,刪除操作的線性表；,,2,棧的元素具有后進先出的特點；,,3,棧頂元素的位置由一個稱為棧頂指針的,變量指示，,進棧、出棧操作要修改棧頂指針；,,,2,棧,3,隊列,3.1,隊列的概念,一 什么是隊列,隊列是限定僅能在表頭進行刪除，表尾進行插入的線性表,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）,插入,刪除,3,隊列,,a,1,a,2,a,3,,a,n,入隊列,隊頭,隊尾,出隊列,隊 列 的 示 意 圖,隊列的特點,先

25、進先出,第一個入隊的元素在隊頭，最后一個入隊的元素在隊尾，,第一個出隊的元素為隊頭元素，,最后一個出隊的元素為隊尾元素,,rear,front,J1,,rear,front,J2,（,a),空隊列,(b)J1,J2,相繼入隊列,(c)J1,出隊,(d)J3,J4, J5,和,J6,相繼入隊之后,,J2,出隊,rear,front,,0,1,2,3,4,5,,rear,front,J5,J4,J3,front,rear,為整數,,,又有,J7,入隊,,,怎么辦？,,？,J2,J6,3 .,循環(huán)隊列,,front,,rear,,,J6,J4,J5,3 1,2,4 0,5,rear,,,5

26、,4 0,3 1,2,,,front,J6,J7,J8,J9,J4,J5,,front,,rear,,,5,4 0,3 1,2,,,,(b),隊空,(a),隊滿,J7,,,rear,判分隊空、隊滿方法：,1,）另設一個標志,S,以區(qū)分隊空、隊滿。,2,）,S=0,隊空：,front=rear;,S=1,隊滿：,front=rear;,或少用一個空間,Real+1=front,為滿,,,front,,,5,4 0,3 1,2,J6,J7,J8,J4,J5,（,c,）,rear,,入隊操作,,：,將元素,x,插入隊尾,,,,front,,rear,,,5,4 0,3

27、 1,2,J1,J3,J2,x,front,,,rear,,,5,4 0,3 1,2,J1,J3,J2,元素,x,入隊前,元素,x,入隊后,出隊操作,,：刪除隊頭,元素；,,,,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,出隊操作前,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,出隊操作后,,,小 結,,1,隊列是限定僅能在表尾一端進行插入，表頭一端刪除 操作的線性表；,,2,隊列中的元素具有先進先出的特點；,,3,隊頭、隊尾元素的位置分別由稱為隊頭指針和隊尾指針的變量指示，,,4,入隊操作要修改隊尾指針，出隊操作要

28、修改隊頭指針；,,,數據存儲結構方面的考題,,1,：數據的存儲結構是指 （,,）。,,A),存儲在外存中的數據,B),數據所占的存儲空間量,,C),數據在計算機中的順序存儲方式,D),數據的邏輯結構在計算機中的表示,2.,下列敘述中正確的是 （,,）。,,A,）棧是“先進先出”的線性表,,B,）隊列是“先進后出”的線性表,,C,）循環(huán)隊列是非線性結構,,D,）有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構,3.,數據結構分為線性結構和非線性結構，帶鏈的隊列屬于（ ）。,4.,下列數據結構中，屬于非線性結構的是（ ）。,A,）循環(huán)隊列,B),帶鏈隊列,C),二叉樹,D,

29、）帶鏈棧,答案：,D,。,答案：,D,。,答案：線性結構。,答案：,c,5.,下列敘述中正確的是（ ）。,,A,）順序存儲結構的存儲一定是連續(xù)的，鏈式存儲結構的存儲空間不一定是連續(xù)的,,B,）順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構,,C,）順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表,,D,）鏈式存儲結構比順序存儲結構節(jié)省存儲空間,答案：,A,。,6.,下列關于棧的敘述正確的是,（,,）,,,A,）棧按“先進先出”組織數據,B),棧按“先進后出”組織數據,,C,）只能在棧底插入數據,D,）不能刪除數據,,答案：,B,。,7.,一個隊列的初始狀態(tài)為空。現將元素,A,，,

30、B,，,C,，,D,，,E,，,F,，,5,，,4,，,3,，,2,，,1,依次入隊，然后再依次退隊，則元素退隊的順序為,【1】,。（,,）,,答案：,A，B，C，D，E，F，5，4，3，2，1,9.,設某循環(huán)隊列的容量為,50,，如果頭指針,front=45(,指向隊頭元素的前一位置,),，尾指針,rear=10(,指向隊尾元素,),，則該循環(huán)隊列中共有,【2】,個元素。,（,,）,,8.,假設用一個長度為,50,的數組（數組元索的下標從,0,到,49,）作為棧的存儲空間，棧底指針,bottom,指間棧底元素，棧頂指針,top,指向棧頂元素，如果,bottom=49,，,top=30,（數組

31、下標），則棧中具有,【 】,個元素。,（,2009,年,3,月）,,答案：,19,答案：,15,4,樹和二叉樹,,1,．樹的定義,,樹是,n,個結點的有限集合,T,，當,n=0,時，稱為空樹；當,n>0,時，,T,滿足如下條件：在任一棵非空樹中：（,1,）有且僅有一個稱為根的結點。（,2,）其余結點可分為,M,個互不相交的子集合，而且這些子集中的每一個本身又是一棵樹，也稱為根的子樹。,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,2,．樹的實例樹可表示具有分枝結構關系的對象,,例,1,．家族族譜,設某家庭有,13,個成員,A,、,B,、,C,、,D,、

32、,E,、,F,、,G,、,H,、,I,、,J,、,K,、,L,、,M,，他們之間的關系可用樹表示：,,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,計算機中樹是常用的數據組織形式,盡管有些應用中數據元素之間并不存在分支結構關系，但為了便于管理和使用數據，將它們用樹的形式來組織。,例,2,計算機的文件系統 不論是,DOS,文件系統還是,window,文件系統，所有的文件都是用樹的形式來組織的。,文件夾,1,文件夾,n,文件,1,文件,2,文件夾,11,文件夾,12,文件,11,文件,12,C,盤,3,、樹的 基本術語,,樹的結點：包含一個數據元素及

33、若干指,向子樹的分支；,孩子結點：結點的子樹的根稱為該結點,的孩子，,B,、,C,是,A,的孩子；,雙親結點：,B,結點是,A,結點的孩子，則,A,,結點是,B,結點的雙親；,兄弟結點：同一雙親的孩子結點，,,H,、,I,、,J,互為兄弟；,堂兄結點,：,同一層上結點，,E,、,F,、,G,、,H,、,I,、,J,、,互為堂兄弟；,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,,3,、樹的 基本術語,結點的層次：根結點的層次定義為,1,；根的孩子為第二層，依此類推；,樹的深度：,樹中所有結點的層次的最大值,結點的度：,結點子樹的個數,樹的度：,樹中結點度的最大值

34、。,葉子結點,：度為,0,的結點；,分枝結點：,度不為,0,的結點；,,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,,一 二叉樹的概念,,1,二叉樹的定義,二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹。,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,一 二叉樹的概念,二叉樹,說明,1,）二叉樹中每個結點最多有兩個子樹；,既：二叉樹每個結點度小于等于,2;,2,）左、右子樹不能顛倒,——,有序樹,;,3,）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念,;,,,(a),、,(b),是不同的二叉樹，

35、,,(a),的左子樹有四個結點,，,(b),的左子樹有兩個結點,(a),(b),,,,,G,,E,,,,D,,,C,,B,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,F,A,,2,． 二叉樹的基本形態(tài),,,,,,,,,,φ,(a),空樹,(b),只有根,(c),右子樹空,(e),左子樹空,(d),左、右子樹非空,,二、 二叉樹的性質,,,性質,1:,在二叉樹的第,i,層上至多有,2,i-1,個結點,(i≥1),。 ,,性質,2:,深度為,k,的二叉樹至多有,2,k,-1,個結點（,k≥1,）。,,,性質,3:,,對任意一棵二叉樹,T,，若葉結點數為,n,0,，而其度為,2,

36、的結點數為,n,2,，則,n,0,=n,2,+1,,。,,兩種特殊的二叉樹,滿二叉樹：深度為,k,的二叉樹，如有,2,k,-1,個結點則稱為滿二叉樹；,,,A,,,G,,,F,,,E,,,D,,,C,,,B,,,A,,,C,,,B,K=3,的滿二叉樹,K=2,的滿二叉樹,,滿二叉樹的順序表示：,,從二叉樹的根開始， 從上到下， 從左到右，逐層進行編號（,1,，,2,，,…,，,n,）。例如圖（,a,）所示的滿二叉樹的順序表示為,:,(1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,，,11,，,12,，,13,，,14,，,15),。,,,,,完全二叉樹：,

37、,深度為,k,，結點數為,n,的二叉樹，如果其結點,1~n,的位置序號分別與滿二叉樹的結點,1~n,的位置序號一一對應，則為完全二叉樹， 如上圖,(b),所示。,,滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。,,,性質,4,：具有,n,個結點的完全二叉樹的深度為［,log,2,n,］,+1,。,,,性質,5:,,對于有,n,個結點的完全二叉樹， 按照從上到下、從左到右的順序對二叉樹中的所有結點從,1,開始順序編號， 則對于任意的序號為,i,的結點有：,,（,1,） 如,i=1,，則序號為,i,的結點是根結點， 無雙親結點； 如,i>1,， 則序號為,i,的結點的雙親結點序號為［,

38、i/2,］,（下取整）,,（,2,） 如,2i>n,，則序號為,i,的結點無左孩子；如,2i≤n,，則序號為,i,的結點的左孩子結點的序號為,2i,。 ,（,3,） 如,2i,＋,1>n,，則序號為,i,的結點無右孩子；如,2i,＋,1≤n,， 則序號為,i,的結點的右孩子結點的序號為,2i,＋,1,。,,,二叉樹,存儲結構,---,二叉鏈表,二叉鏈表中每個結點包含三個域：數據域、左指針域、右指針域,,,A,,,F,,,E,,,D,,,C,,,B,,二叉鏈表圖示,,∧,,D,,,,A,,B ∧,,C,,∧,,∧,E ∧,,∧,F ∧,,若一個二叉樹含有,n,個結點，則它的二叉鏈表中必含有,2

39、n,個指針域， 其中必有,n+1,個空的指針域。,,,,二、二叉樹的遍歷（必考）,遍歷,：,按某種順序訪問二叉樹的每個結點，而且每個結點僅被訪問一次。,訪問：,含義很廣，可以是對結點的各種處理,，如修改結點數據、輸出結點數據。,,,如何訪問二叉樹的每個結點，,而且每個結點僅被訪問一次？,？,,二叉樹的遍歷方法（必考）,,二叉樹由根、左子樹、右子樹三部分組成,二叉樹的遍歷,可以分解為：訪問根，遍歷,左子樹,和,遍歷,右子樹,令,：,L,：,遍歷左子樹,,T,：,訪問根結點,,R,：,遍歷右子樹,,約定先左后右,,,有三種遍歷方法：,,T,L R,前序遍歷、,,,L,T,R,中序遍歷,、,,L

40、R,T,后序遍歷。,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,,,先序遍歷,（,T,,L,R,）,,若二叉樹非空 （,1,）訪問根結點；,（,2,）先序遍歷左子樹； （,3,）先序遍歷右子樹,；,,先序遍歷序列,：,A,,,B,D,,E,,G,,C,,,F,例：先,序遍歷右圖所示的二叉樹,（,1,）訪問根結點,A,,（,2,）先序遍歷左子樹：即按,,T,,L,R,的順序遍歷,左子樹,（,3,）先序遍歷右子樹：即按,,T,,L,R,的順序遍歷,右子樹,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,中序遍歷（,L,T,,R,）,若二叉樹非空（,1,）中序遍歷左

41、子樹（,2,）訪問根結點,（,3,）中序遍歷右子樹,,中序遍歷序列,：,,D,B,G,,E,,,A,,,C,F,例：,中序遍歷右圖所示的二叉樹,（,1,）中序遍歷左子樹：即按,,L,T,,R,的順序遍歷,左子樹,,（,2,）訪問根結點,A,,（,3,）中序遍歷右子樹：即按,,L,T,,R,的順序遍歷,右子樹,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,后序遍歷（,L,R,T,）,若二叉樹非空（,1,）后序遍歷左子樹（,2,）后序遍歷右子樹,（,3,）訪問根結點,,后序遍歷序列：,,D,G,,E,,B,,F,C,,,A,例：后,序遍歷右圖所示的二叉樹,（,1,）后序遍歷左

42、子樹：即按,,L,R,T,,的順序遍歷,左子樹,,（,2,）后序遍歷右子樹：即按,,L,R,T,,的順序遍歷,右子樹,,（,3,）訪問根結點,A,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,,后序遍歷序列,：,a,b,c,d,-,*,+,,e,f,/,,,-,中序遍歷序列,：,a,+,b,*,c,-,d,,-,,,e,/,f,,例：,中序遍歷、,后,序,遍歷下圖所示的二叉樹,,,e,,,d,,,c,,,b,,,f,,,a,,,+,,,*,,,/,,,-,,,-,例,:,已知一棵二叉樹前序遍歷和中序遍歷分別為,ABDEGCFH,和,DBGEACHF,，則該二叉樹的后序遍歷為,?

43、,,A) GEDHFBCA?????B) DGEBHFCAC) ABCDEFGH?????D) ACBFEDHG,B,,二叉樹,,1,二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹；,,2,二叉樹可以用鏈式結構存儲；,遍歷：按某種搜索路徑訪問二叉樹的每個結點，每個結點僅被訪問一次。,,二叉樹的遍歷可以分解為：訪問根，遍歷,左子樹和,遍歷,右子樹，常用的三種遍歷算法：,先序遍歷、中序遍歷、后序遍歷；,,5,查找,,5.1,查找的基本概念,,查找（列）表：由同一類型的數據元素（或記錄）構成的集合， 可利用任意數據結構實現。 ,關鍵字：,數據元素的

44、某個（幾個）數據項的值。如果一個數據項可以,唯一標識列表中的一個數據元素,， 則稱其為關鍵字。,,查找： 根據給定的關鍵字值，在特定的查找（列）表中確定一個其關鍵字與給定值相同的數據元素，并返回該數據元素在列表中的位置。,若找到相應的數據元素， 稱查找成功，否則稱查找失敗,,5,．,2,線性表的查找,5.2.1,順序查找,---,最簡單的查找方法,順序查找的基本思想,,,從表的一端開始，順序掃描線性表，,依次將掃描到的結點關鍵字和待找的值Ｋ相比較，若相等，則查找成功，若整個表掃描完畢，仍末找到關鍵字等于Ｋ的元素，則查找失敗。,順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描

45、，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無序的。,,,順序查找算法的性能。,假設列表長度為,n,，那么查找第,i,個數據元素時需進行,n-i+1,次比較，即,C,i,=n-i+1,。又假設查找每個數據元素的概率相等，即,P,i,=1/n,， 則順序查找算法的平均查找長度為：,順序查找的特點,,,,,,順序查找的,優(yōu)點是算法簡單,，對查找表結構無任何要求，無論是用向量還是用鏈表來存放結點，也無論結點之間是否按關鍵字有序或無序排，它都同樣適用。,順序查找的缺點是,查找效率低,，當,n,較大時，不宜采用順序查找,。,二分,查找（折半查找）,1.,二分查

46、找的基本思想,,,高效率的查找方法。要求表中元素按關鍵字有序,(,升序或降序,),。假設表中元素為升序排列。,二分查找的基本思想是：,首先將表,中間位置記錄的關鍵字與查找關鍵字,比較，如果兩者相等，則查找成功；,否則利用中間位置記錄,將表分成前、后兩個子表， 如果中間位置記錄的關鍵字大于查找關鍵字，,則進一步查找前一子表，否則進一步查找后一子表。,重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。,例如，假設給定有序表中關鍵字為：,{05,13,19,21,37,56,64,74,80,88,92},，查找,K=21,的情況：,,,,,0 1

47、 2 3 4 5 6 7 8 9 10,,0 1 2 3 4 5 6 7 8 9 10,,,,0 1 2 3 4 5 6 7 8 9 10,,0 1 2 3 4 5 6 7 8 9 10,3.,二分查找的性能分析,二分查找的過程可以用二叉樹來描述。把當前查找區(qū)間的中點作為根結點，左子區(qū)間和右子區(qū)間分別作為根的左子樹和右子樹，左子

48、區(qū)間和右子區(qū)間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。,例如，給定的關鍵字序列,05,13,19,21,37,56,64,74,80,88,92,，的判定樹。,,,0 1 2 3 4 5 6 7 8 9 10,,,,在長度為,n,的有序線性表中進行二分查找。最壞的情況下，需要的比較次數為,log,2,n,,,,6,排序,,6,．,1,基本概念,,6.1.1,排序定義,,排序就是把一組記錄（元素）按照某個域的值的遞增或遞減的次序重新排列的過程。,(,按學號的遞增,),表,7-1,學生檔案表,,學號,,,姓名,,,年齡,,,性別,,,9900

49、1,,,王曉佳,,,18,,,男,,,99002,,,林一鵬,,,19,,,男,,,99003,,,謝寧,,,17,,,女,,,99004,,,張麗娟,,,18,,,女,,,99005,,,周濤,,,20,,,男,,,99006,,,李小燕,,,16,,,女,,,,為討論方便，我們直接將排序碼寫成一個一維數組的形式，,并且在沒有聲明的情形下，所有排序都按排序碼的值遞增排列。,排序,,,插入排序（直插排序、希爾排序）,,,交換排序（冒泡排序、快速排序）,,,選擇排序 （直選排序、堆排序）,,歸并排序（二路歸并排序）,,,,6,．,2,插入排序,,直接插入排序,1,．直接插入排序（,Straigh

50、t Insertion Sorting,）,,基本思想：把,n,個待排序的元素看成一個有序表和一個無序表，,開始時有序表中只包含一個元素，無序表中包含有,n-1,個元素，,排序過程中每次從無序表中取出第一個元素，把它的排序碼,依次與有序表元素的排序碼進行比較，將它插入到有序表中,的適當位置，使之成為新的有序表。,,例如，,n=6,，數組,R,的六個排序碼分別為：,17,，,3,，,25,，,14,，,20,，,9,。它的直接插入排序的執(zhí)行過程如圖,7-1,所示。,,3,．直接插入排序的效率分析,直接插入排序算法十分簡單。,空間,:,只需要一個元素的輔助空間，用于元素的位置交換,。,時間,:,外

51、層循環(huán)要進行,n-1,次插入，每次插入最少比較一次（正序），移動兩次；最多比較,i,次，移動,i,＋,2,次（逆序）（,i=1,，,2,，,…,，,n-1,）。,直接插入排序的時間復雜度為,O,（,n,2,）。,最壞情況比較,n(n-1)/2,,希爾排序,,希爾排序,(,縮小增量排序,):1959,年由提出來的。,基本思想：先將整個待排元素序列分割成若干個子序列（由 “增量”確定）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的。,,例如，,n=8,，數組,array[ ],

52、的八個元素分別為：,91,，,67,，,35,，,62,，,29,，,72,，,46,，,57,。下面用圖,7-2,給出希爾排序算法的執(zhí)行過程。,,希爾排序的效率分析,與增量有關，,最壞情況，希爾排序的時間復雜性在,O,（,nlog,2,n,）。,,,6,．,3,交換排序,6.3.1,冒泡排序,基本思想,:,,對待排序序列從后向前（從下標較大的元素開始），依次比較相鄰元素的排序碼，若發(fā)現逆序則交換，使排序碼較小的元素逐漸從后部移向前部，就象水底下的氣泡一樣逐漸向上冒。,,例如，,n=6,，數組,R,的六個排序碼分別為：,17,，,3,，,25,，,14,，,20,，,9,。下面用圖,7-3,給

53、出冒泡排序算法的執(zhí)行過程。,,,冒泡排序的效率分析,,若待排序的元素為正序，則只需進行一趟排序，比較次數為（,n-1,）次，移動元素次數為,0,；,若待排序的元素為逆序，則需進行,n-1,趟排序，比較次數為,(n,2,-n)/2,，移動次數為,3(n,2,-n )/2,，,最壞情況比較,n(n-1)/2,因此冒泡排序算法的時間復雜度為,O,（,n,2,）。由于其中的元素移動較多，所以屬于內排序中速度較慢的一種。,6.3.2,快速排序,基本思想是：取待排序序列中的某個元素（一般第一個元素）作為基準，通過一趟排序，將待排元素分為左右兩個子序列，,左子序列元素的排序碼均小于或等于基準元素的排序碼，,

54、右子序列的排序碼則大于基準元素的排序碼，,然后分別對兩個子序列繼續(xù)進行,快速,排序，直至整個序列有序。,,元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面，排序碼較小的記錄一次就能夠交換到前面，記錄每次移動的距離較遠，因而總的比較和移動次數較少。,,例如，給定排序碼為：（,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,），具體劃分如圖,7-4,所示。,,3,．快速排序的效率分析,,若快速排序出現最好的情形（左、右子區(qū)間的長度大致相等），則結點數,n,與二叉樹深度,h,應滿足,log,2,n

55、過,(n+1) log,2,n,。因此，,快速排序的最好時間復雜度應為,O,（,nlog,2,n,）。,已經證明，快速排序的平均時間復雜度也為,O,（,nlog,2,n,）,。,若快速排序出現最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，總的比較次數為,n(n-1)/2,,。因此，,快速排序的最壞時間復雜度為,O(n,2,),。,快速排序所占用的輔助空間為棧的深度，故最好的空間復雜度為,O,（,log,2,n,），最壞的空間復雜度為,O(n),。,快速排序是一種不穩(wěn)定的排序方法。,6,．,4,選擇排序,,6 . 4.1,直接選擇排序,基本思想,直接選擇

56、排序是一種簡單的排序方法?；舅枷胧牵旱谝淮螐?array[0]~array[n-1],中選取最小值，與,array[0],交換，第二次從,array[1]~array[n-1],中選取最小值，與,array[1],交換，第三次從,array[2]~array[n-1],中選取最小值，與,array[2],交換，,…,，第,i,次從,array[i-1]~array[n-1],中選取最小值，與,array[i-1],交換，,…,,第,n-1,次從,array[n-2]~array[n-1],中選取最小值，與,array[n-2],交換，總共通過,n-1,次，得到一個按排序碼從小到大排列的有序序

57、列,。,例如，給定,n=8,，數組,R,中的,8,個元素的排序碼為：（,8,，,3,，,2,，,1,，,7,，,4,，,6,，,5,），則直接選擇排序過程如圖,7-5,所示。,,直接選擇排序的效率分析,,,在直接選擇排序中，共需要進行,n-1,次選擇和交換，每次選擇需要進行,n-i,次比較（,1≤i≤n-1,），而每次交換最,多需,3,次移動，因此，總的比較次數,C= =(n,2,-n)/2,，,總的移動次數,M= =3(n-1),。,,直接選擇排序的時間復雜度為,O(n,2,),數量級，所以當記錄占用的字節(jié)數較多時，通常比直接插入排序的執(zhí)行

58、速度要快一些,。,最壞情況比較,n(n-1)/2,,,,7,．,5,歸并排序,,,1,、,基本思想：將兩個有序子區(qū)間（有序表）合并成一個有序子區(qū)間，一次合并完成后，有序子區(qū)間的數目減少一半，而區(qū)間的長度增加一倍，當區(qū)間長度從,1,增加到,n,（元素個數）時，整個區(qū)間變?yōu)橐粋€，即為有序序列,.,,例如，給定排序碼,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,，二路歸并排序過程如圖,7-10,所示。算法,P284,歸并排序的效率分析,,歸并排序的時間復雜度為,O(nlog,2,n),。,歸并排序時，需要利用與待排序數組相同的輔助數組作臨時單元，故該排序方法的空間復雜

59、度為,O(n),，比前面介紹的其它排序方法占用的空間大。,,對于長度為,n,的線性表，在最壞情況下，下列各排序法所對應的比較次數中正確的是,A),冒泡排序為,n/2,B),冒泡排序為,n,,C),快速排序為,n,D),快速排序為,n(n-1)/2,D,第二部分 程序設計,,程序設計基礎,2.1,程序設計方法與風格,如何形成良好的程序設計風格，主要包含以下幾個因素：,（,1,）源程序文檔化。,（,2,）數據說明的方法。,（,3,）語句的結構。,（,4,）輸入和輸出。,（,5,）適當的注釋,注,釋分序言性注釋和功能性注釋。,2,程序設計基礎,2.2,結構化程序設計,結構化程序設計方法的四條原則是,

60、（必考）：,1.,自頂向下；,2.,逐步求精；,3.,模塊化；,4.,限制使用,goto,語句。,結構化程序的基本結構和特點：,（,1,）順序結構：一種簡單的程序設計，最基本、最常用的結構；,（,2,）選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列；,（,3,）重復結構：又稱循環(huán)結構，可根據給定條件，判斷是否需要重復執(zhí)行某一相同程序段。,,,2,程序設計基礎,2.3,面向對象程序設計,1,、面向對象方法的,優(yōu)點,：,（,1,）與人類習慣的思維方法一致。 （,2,）穩(wěn)定性好。,（,3,）可重用性好。

61、 （,4,）易于開發(fā)大型軟件產品。,（,5,）可維護性好。,,2,、面向對象方法的基本概念,（,1,）對象,-,對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是實體的抽象。,屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務。,2,程序設計基礎,（,2,）類和實例,——,類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。,（,3,）消息,——,消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括,1,、接收消息的對象的名稱；,2,、消息標識符，也稱消息名；,3,、零個或多個參數。,（,4,）繼承,——,

62、繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。,（,5,）多態(tài)性,——,多態(tài)性是指同樣的操作在接受不同消息時可導致完全不同的行動的現象。,,比如汽車一個類，而具體到某輛汽車則是一個對象。圖,21,中，機動車類是對機動車特征和功能的總體描述，機動車,A,是具體到某輛車的特征。,,,3,軟件工程基礎,3.1,軟件工程基本概念,1,、軟件定義及特點,2,、軟件危機與軟件工程,3,、軟件工程過程和軟件生命周期,軟件生命周期三個階段,:,軟件定義、軟件開發(fā)、運行維護，主要活動階段是：,（,1,）可行性研究

63、與計劃制定；,（,2,）需求分析；,（,3,）軟件設計；,（,4,）軟件實現；,（,5,）軟件測試；,（,6,）運行和維護。,,,3,軟件工程基礎,4,、軟件工程的目標和與原則,目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產品。,基本目標：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。,軟件工程的理論和技術性研究的內容主要包括：軟件開發(fā)技術和軟件工程管理。,軟件開發(fā)技術包括：軟件開發(fā)方法學、開發(fā)過程、開發(fā)工具和軟件工程

64、環(huán)境。,軟件工程管理包括：軟件管理學、軟件工程經濟學、軟件心理學等內容。,軟件管理學包括人員組織、進度安排、質量保證、配置管理、項目計劃等。,軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。,3,軟件工程基礎,3.2,結構化分析方法,1,、需求分析,——,指用戶對目標軟件系統在功能、行為、性能、設計約束等方面的期望。,（,1,）結構化需求分析方法。（,2,）面向對象的分析的方法（,OOA,）。,,2,、結構化分析方法,結構化分析方法的實質：著眼于數據流，自頂向下，逐層分解，建立系統的處理流程，以數據流圖和數據字典為主要工具，建立系統的邏輯模型。,步驟：,調查原

65、系統（獲得當前系統如何工作）,原系統邏輯模型,à,需求分析（得出新系統應如何工作）,新系統邏輯模型,結構化分析的常用工具：（,1,）數據流圖、（,2,）數據字典（,D-D,）、（,3,）判定樹、（,4,）判定表,,,,,,,3,軟件工程基礎,3,、軟件需求規(guī)格說明書,作用：,（,1,）便于用戶與開發(fā)人員進行交流。,（,2,）是軟件開發(fā)工作的基礎和依據。,（,3,）作為確認測試和驗收的依據。,內容：,（,1,）概述　　　　?。?2,）數據描述,（,3,）功能描述?！　。?4,）性能描述。,（,5,）參考目錄?！　。?6,）附錄。,特點：,（,1,）正確性；（,2,）無岐義性；,（,3,）完整性；

66、（,4,）可驗證性；,（,5,）一致性；（,6,）可理解性；,（,7,）可追蹤性。,3,軟件工程基礎,3.3,結構化設計方法,1,、軟件設計基本概念,軟件設計的基本目標：是用比較抽象概括的方式確定目標系統如何完成預定的任務，軟件設計是確定系統的物理模型。,結構設計：定義軟件系統各主要部件之間的關系。,數據設計：將分析時創(chuàng)建的模型轉化為數據結構的定義。,接口設計：描述軟件內部、軟件和協作系統之間以及軟件與人之間如何通信。,過程設計：把系統結構部件轉換成軟件的過程描述。,軟件設計的基本原理：,（,1,）抽象。,（,2,）模塊化。,（,3,）信息隱藏。,（,4,）模塊獨立性。,3,軟件工程基礎,衡量軟件模塊獨立性使用,耦合性和內聚,性兩個定性的度量標準。,內聚性指一個模塊內容各部分之間的緊密程度。內聚性越高越好。,耦合性指模塊之間的相互依賴關系。耦合性越低越好。,在程序結構中各模塊的內聚性越強，則耦合性越弱。優(yōu)秀軟件應高內聚，低耦合。,按內聚性由弱到強：偶然內聚、邏輯內聚、時間內聚、過程內聚、順序內聚、功能內聚。,耦合性按由高到低：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數據耦合、