單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,*,計算機二級考試公共基礎(chǔ)之,《,數(shù)據(jù)結(jié)構(gòu)與算法,》,1,．,4,算法與算法分析,算法與算法分析,一 算法的概念,,算法是對特定問題求解步驟的一種描述,,算法的基本特征：,,1,）,可行性,：組成算法的操作必須能夠在計算機上實現(xiàn)。,2,）,確定性,：算法的每一步操作必須清晰無二義性。,3,）,有窮性,：算法必須在有限步內(nèi)結(jié)束；,4,）,有足夠的情報,：,0,個或多個輸入；,1,個或多個輸出；,算法描述的方法很多，如自然語言、框圖、類,C,等,,例,:,求兩個正整數(shù),m,，,n,中的最大數(shù),MAX,的算法,（,1,）,若,m > n,則,max=m,（,2,）,若,m <= n,則,max=n,,程序,=,算法,+,數(shù)據(jù)結(jié)構(gòu),,1,、,正確性,：,(1),沒有語法錯誤； ,(2),對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；,(3),對于精心選擇的典型而苛刻的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。,(4),對于一切合法的輸入數(shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。,2,、,可讀性：,便于閱讀、理解、調(diào)試、修改；,3,、,健壯性：,對不合法的輸入能作出正確的反映與處理；,4,、,高效性：,執(zhí)行時間短（,時間復(fù)雜度,）、,需求存儲空間?。?空間復(fù)雜度,）,評價算法標準,,1,時間復(fù)雜度,T,（,n,）,以求解問題的基本操作的,執(zhí)行次數(shù),作為算法時間的度量。,算法與算法分析,O,（,n,3,）,,稱為矩陣相乘算法時間復(fù)雜度；,O,（,n,3,）表示矩陣相乘算法執(zhí)行時間與,n,3,成正比,,,即,O,（,n,3,）與,n,3,同一數(shù)量級；,,例：,n,階矩陣相乘的算法,For ( i = 1; i<=n; i++ ) For (j = 1; j<=n; j++ ),{ c[ i ][ j ] = 0 ; For (k = 1; k<= n; k++ ) c[ i ][ j ] += a[ i ][ k ] * b[ k ] [ j ],},,乘法 加法,執(zhí)行次數(shù)均為,n,3,,,矩陣相乘的基本運算：乘法 加法；,,數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度頻率計數(shù)有,7,個：,,O(1),常數(shù)型,O(n),線性型,O(n,2,),平方型,,O(n,3,),立方型,O(2,n,),指數(shù)型,,O(log,2,n),對數(shù)型,O(nlog,2,n),二維型,2,算法空間復(fù)雜度 用執(zhí)行算法所需的,內(nèi)存空間的大小,作為算法所需空間的度量。 設(shè)執(zhí)行算法所需的內(nèi)存空間是問題規(guī)模,n,的某個函數(shù),g(n),,則算法空間復(fù)雜度記作：,S,（,n,）,= O(g(n)),表示算法內(nèi)存空間的增長率,與,g(n),的增長率相同,例計算,,解法,1,先計算,x,的冪,,,存于,power[ ],中,,,再分別乘以相應(yīng)的系數(shù),,# 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]*power[i];,return(f);,},問題規(guī)模為,n,,算法時間復(fù)雜度,: O(n),空間復(fù)雜度：,O(N),(1),在計算機中，算法是指（ ）。,A.,查詢方法,B.,加工方法,C.,解題方案的準確而完整的描述,D.,排序方法,(2),下列敘述中正確的是（ ）。,A),算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān),B),算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量,C),數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的,D),算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān),(3),算法的有窮性是指（ ）。,A,）算法程序的運行時間是有限的,B,）算法程序所處理的數(shù)據(jù)量是有限的,C,）算法程序的長度是有限的,D,）算法只能被有限的用戶使用,(c),(B),算法習(xí)題,(A),(4),算法的時間復(fù)雜度是指,( ),,A),算法的執(zhí)行時間,,B),算法所處理的數(shù)據(jù)量,,C),算法程序中的語句或指令條數(shù),,D),算法在執(zhí)行過程中所需要的基本運算次數(shù),(5),算法的空間復(fù)雜度是指,( ),A,）算法在執(zhí)行過程中所需要的計算機存儲空間,B,）算法所處理的數(shù)據(jù)量,C,）算法程序中的語句或指令條數(shù),D,）算法在執(zhí)行過程中所需要的臨時工作單元數(shù),(6),下列敘述中正確的是,( ),,A,）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大,,B,）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小,,C,）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小,,D,）上述三種說法都不對,(D),計算工作量,(A),(D),數(shù)據(jù)結(jié)構(gòu),大量的數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計算機的存儲空間，這是進行數(shù)據(jù)處理的關(guān)鍵問題。,數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，既按某種邏輯關(guān)系把一批數(shù)據(jù)組織起來，按一定的映象方式把它存放在計算機的存儲器中，并在這些數(shù)據(jù)上定義一個運算的集合。,,歸納為三部分：,,邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合,。,,1.,邏輯結(jié)構(gòu),,數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。,,數(shù)據(jù)的邏輯結(jié)構(gòu)包含：,（,1,）表示數(shù)據(jù)元素的信息；,（,2,）表示各數(shù)據(jù)元素之間的前后件關(guān)系。,例：,1.,一年四季的數(shù)據(jù)結(jié)構(gòu),,B=(D,R),D={,春，夏，秋，冬,},R={(,春，夏,) ,(,夏，秋,),(,秋，冬,)},2.,家庭成員的數(shù)據(jù)結(jié)構(gòu),,B=(D,R),D={,父親，兒子，女兒,},R={(,父親，兒子,) ,(,父親，女兒,)},,春,夏,秋,冬,數(shù)據(jù)結(jié)構(gòu)的圖形表示,父親,兒子,女兒,常見的,邏輯結(jié)構(gòu),有：,線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。,,,,,,,,,,,,,,,,,線性結(jié)構(gòu),樹形結(jié)構(gòu),圖形結(jié)構(gòu),① 線性結(jié)構(gòu),結(jié)構(gòu)中的每個元素之間存在一個對一個的關(guān)系；,線性表、棧、隊、字符串、數(shù)組,② 樹形結(jié)構(gòu) （非線性）,結(jié)構(gòu)中的每個元素之間存在一個對多個的關(guān)系；,③ 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)（非線性）,結(jié)構(gòu)中的每個元素之間存在多個對多個的關(guān)系。,,2.,存儲結(jié)構(gòu)（物理結(jié)構(gòu)）,計算機在實際進行數(shù)據(jù)處理時，被處理的各數(shù)據(jù)元素總是被存放在計算機的存儲空間中，并且，各數(shù)據(jù)元素在計算機存儲空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。,如：一年四季,家庭成員 計算機存儲空間怎樣存放？,存儲結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計算機存儲空間中的具體實現(xiàn)。,常見的存儲結(jié)構(gòu)有：,順序存儲結(jié)構(gòu) 鏈式存儲結(jié)構(gòu) 索引存儲結(jié)構(gòu),3.,數(shù)據(jù)的運算,檢索,插入,刪除,更新,排序,,通常，一個數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點可能是動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點（插入運算），也可以刪除某個結(jié)點（刪除運算），除此之外，對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復(fù)制和修改。,數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，研究以下三方面內(nèi)容：,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的運算,常見的數(shù)據(jù)結(jié)構(gòu),,,1.,線性表,,,2.,棧和隊列,,,3.,樹,１． 線性表（,Linear List,）,線性表是由,n,（,n≥0,）個數(shù)據(jù)元素,,a,1,，,a,2,，,…,，,a,i,，,…,，,a,n,組成的一個有限序列。,線性表是最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)。,,棧、隊列、串,是特殊的線性表,數(shù)組和廣義表,是線性表的擴展,--,線性結(jié)構(gòu),,,例、英文字母表（,A, B, C, D, E,?,Z,）。 某單位的電話號碼簿。,線性表的概念,設(shè),A=,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）是一線性表，,1,） 同一線性表中的元素必須是,同一類型,的；,2,） 在表中,a,i-1,,領(lǐng)先于,a,i,，,a,i,,領(lǐng)先于,a,i+1,,，稱,a,i-1,,是,a,i,,的前件，,a,i+1,,是,a,i,,的后件；,3,） 在線性表中，除第一個元素和最后一個元素之外，其他元素都有且,僅有一個前件，有且僅有一個后件,；,4,） 線性表中元素的個數(shù),n,稱為線性表的長度，,n=0,時稱為空表；,,用,一組連續(xù)的內(nèi)存單元依次存放,線性表的數(shù)據(jù)元素。,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,,線性表（,a,1,,a,2,,a,3,,... a,n,,）,的順序存儲結(jié)構(gòu),用順序存儲結(jié)構(gòu)存儲的線性表,——,稱為順序表,線性表的順序存儲和實現(xiàn),一 、 線性表的順序存儲結(jié)構(gòu),,線性表的順序存儲和實現(xiàn),說明：,元素之間的邏輯關(guān)系，通過元素的存儲順序表示出來,.,設(shè)線性表中每個數(shù)據(jù)元素占,t,個存儲單元，那么，在順序存儲結(jié)構(gòu)中，線性表的第,i,個元素的存儲位置與第,1,個元素的存儲位置的關(guān)系是：,,,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,),線性表的順序存儲和實現(xiàn),,插入位置 移動元素個數(shù),1                             n 2                             n-1  i n-i+1  n 1 n+1 0,插入算法時間復(fù)雜度分析,算法時間復(fù)雜度取決于移動元素的個數(shù)，移動元素的個數(shù)不僅與表長有關(guān)，而且與插入位置有關(guān)。,,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,0,1,i-1,i-2,n-1,.,.,由此可見在順序表中插入一個元素 ，平均要移動表的一半元素。表長為,n,的順序表，插入算法的時間復(fù)雜度為,O,（,n,）,假設(shè)在線性表的任何位置插入元素的概率相同，即,,pi= 1/(n+1),,設(shè),p,i,為在第,i,個元素之前插入元素的概率，在長度為,n,的順序表中插入一個元素，所需移動元素個數(shù)數(shù)學(xué)期望值為：,,刪除算法時間復(fù)雜度分析,假設(shè)在線性表的任何位置刪除元素的概率相同，即,,pi= 1/n,刪除,所需移動元素個數(shù)的數(shù)學(xué)期望值：,,,線性表的順序存儲和實現(xiàn),,順序表是線性表最簡單的一種存儲結(jié)構(gòu),,,小結(jié),順序表的特點：,1,通過元素的存儲順序反映 線性表中,數(shù)據(jù)元素之間的邏輯關(guān)系；,2,可隨機存取順序表的元素；,3,順序表的插入、刪除操作要通過,移動,元素實現(xiàn)；,線性表的鏈式存儲和實現(xiàn),,線性表的鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元存儲線性表的各個數(shù)據(jù)元素。,為了表示線性表中元素的先后關(guān)系，每個元素除需要存儲自身的信息外，還要保存直接前趨元素或直接后繼元素的存儲位置。,,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,,用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，對每個數(shù)據(jù)元素保存自身信息和直接后繼元素的存儲位置。,,用鏈表存儲線性表時，數(shù)據(jù)元素之間的關(guān)系是通過,保存直接后繼元素的存儲位置來表示的,,ai-1,,a,i,,a,2,,a1,,a,i+,1,n,,a,n,,結(jié)點：,數(shù)據(jù)元素及直接后繼的存儲位置（地址）組成一個數(shù)據(jù)元素的存儲結(jié)構(gòu)，稱為一個結(jié)點；,結(jié)點的數(shù)據(jù)域 ：,保存數(shù)據(jù)元素,;,結(jié)點的指針域 ：,保存數(shù)據(jù)元素直接后繼的存儲地址,;,,線性鏈表有關(guān)術(shù)語,存儲數(shù)據(jù)元素,存儲后繼結(jié)點,存儲地址,,結(jié)點,數(shù)據(jù)域,指針域,頭指針：,存放線性鏈表中第一個結(jié)點的存儲地址,;,空指針：,不指向任何結(jié)點，線性鏈表最后一個結(jié)點的指針通常是空指針,;,頭結(jié)點：,鏈表的第一個元素結(jié)點前的附加結(jié)點；,帶頭結(jié)點的線性鏈表,：第一個元素結(jié)點前增加一個附加結(jié)點的線性鏈表稱為 帶頭結(jié)點的線性鏈表；,,head,是頭指針,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,頭結(jié)點,,空指針,head,線性鏈表的每個結(jié)點中只有一個指針域,故也稱為,單鏈表,插入結(jié)點,(,存,a,),q=(LNODE *)malloc(sizeof(LNODE));,q->deta=‘a(chǎn)’;,q->next=p-> next;,p-> next =q;,head,,z,,y,,x,,p,,y,,x,,z,,p,head,,a,q,插入操作功能：在線性鏈表的第,i,個元素結(jié)點之前插入一個新元素結(jié)點,e,；,插入操作圖示：,插入前,插入后,,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,head,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,e,head,,4,）,刪除結(jié)點,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,線性鏈表小結(jié),線性鏈表是線性表的一種鏈式存儲結(jié)構(gòu),,線性鏈表的特點,,,1,通過保存直接后繼元素的存儲位置來表示,數(shù)據(jù)元素之間的邏輯關(guān)系；,,2,插入、刪除操作通過修改結(jié)點的指針實現(xiàn)；,,3,不能隨機存取元素,；,1,循環(huán)鏈表的概念,循環(huán)鏈表的特點是將線性鏈表的最后一個結(jié)點的指針指向鏈表的第一個結(jié)點（首尾相連的單鏈表）,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)鏈表,,,,雙向鏈表,,循環(huán)單鏈表，雖然從任一結(jié)點出發(fā)沿著指針鏈能找到其前件，但時間耗費是,O(n),。如果希望從表中快速確定某一個結(jié)點的前件，另一個解決方法是在鏈表的每個結(jié)點里再增加一個指向其前件的指針域,prior,。 這樣形成的鏈表中就有兩條方向不同的鏈，稱為雙向鏈表。,線性表小結(jié),,線性表的順序存儲結(jié)構(gòu),—,順序表，,鏈式存儲結(jié)構(gòu),----,線性鏈表,,,循環(huán)鏈表,,,雙向鏈表,.,不同的存儲結(jié)構(gòu)，線性表的同一操作的算法是不同的,:,,在順序存儲結(jié)構(gòu)下，線性表的插入、刪除操作，通過移動元素實現(xiàn),;,,在線性鏈表存儲結(jié)構(gòu)下，線性表的插入、刪除操作，通過修改指針實現(xiàn)。,2,棧,棧是限定僅能在表尾一端進行插入、刪除操作的線性表,,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）,插入,刪除,棧的概念,一    什么是棧,?,將表中允許進行插入、刪除操作的一端稱為,棧頂,(Top),，,棧頂?shù)漠?dāng)前位置是動態(tài)變化的，由一個棧頂指針指示其位置。,表的另一端稱為棧底,(Bottom),。,當(dāng)棧中沒有元素時稱為空棧。,棧的插入操作稱為,進?；蛉霔?，刪除操作稱為,出?；蛲藯?。,,棧,,棧的示意圖,出棧,進棧,棧的特點,后進先出,第一個進棧的元素在棧底，最后一個進棧的元素在棧頂，,第一個出棧的元素為棧頂元素，,最后一個出棧的元素為棧底元素,,,棧頂,棧底,a,n,a,2,a,1,,,小 結(jié),,,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,入隊列,隊頭,隊尾,出隊列,隊 列 的 示 意 圖,隊列的特點,先進先出,第一個入隊的元素在隊頭，最后一個入隊的元素在隊尾，,第一個出隊的元素為隊頭元素，,最后一個出隊的元素為隊尾元素,,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,為整數(shù),,,又有,J7,入隊,,,怎么辦？,,？,J2,J6,3 .,循環(huán)隊列,,front,,rear,,,J6,J4,J5,3 1,2,4 0,5,rear,,,5,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,）另設(shè)一個標志,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 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,出隊操作后,,,小 結(jié),,1,隊列是限定僅能在表尾一端進行插入，表頭一端刪除 操作的線性表；,,2,隊列中的元素具有先進先出的特點；,,3,隊頭、隊尾元素的位置分別由稱為隊頭指針和隊尾指針的變量指示，,,4,入隊操作要修改隊尾指針，出隊操作要修改隊頭指針；,,,數(shù)據(jù)存儲結(jié)構(gòu)方面的考題,,1,：數(shù)據(jù)的存儲結(jié)構(gòu)是指 （,,）。,,A),存儲在外存中的數(shù)據(jù),B),數(shù)據(jù)所占的存儲空間量,,C),數(shù)據(jù)在計算機中的順序存儲方式,D),數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示,2.,下列敘述中正確的是 （,,）。,,A,）棧是“先進先出”的線性表,,B,）隊列是“先進后出”的線性表,,C,）循環(huán)隊列是非線性結(jié)構(gòu),,D,）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈式存儲結(jié)構(gòu),3.,數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于（ ）。,4.,下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（ ）。,A,）循環(huán)隊列,B),帶鏈隊列,C),二叉樹,D,）帶鏈棧,答案：,D,。,答案：,D,。,答案：線性結(jié)構(gòu)。,答案：,c,5.,下列敘述中正確的是（ ）。,,A,）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈式存儲結(jié)構(gòu)的存儲空間不一定是連續(xù)的,,B,）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)只針對非線性結(jié)構(gòu),,C,）順序存儲結(jié)構(gòu)能存儲有序表，鏈式存儲結(jié)構(gòu)不能存儲有序表,,D,）鏈式存儲結(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間,答案：,A,。,6.,下列關(guān)于棧的敘述正確的是,（,,）,,,A,）棧按“先進先出”組織數(shù)據(jù),B),棧按“先進后出”組織數(shù)據(jù),,C,）只能在棧底插入數(shù)據(jù),D,）不能刪除數(shù)據(jù),,答案：,B,。,7.,一個隊列的初始狀態(tài)為空?，F(xiàn)將元素,A,，,B,，,C,，,D,，,E,，,F,，,5,，,4,，,3,，,2,，,1,依次入隊，然后再依次退隊，則元素退隊的順序為,【1】,。（,,）,,答案：,A，B，C，D，E，F(xiàn)，5，4，3，2，1,9.,設(shè)某循環(huán)隊列的容量為,50,，如果頭指針,front=45(,指向隊頭元素的前一位置,),，尾指針,rear=10(,指向隊尾元素,),，則該循環(huán)隊列中共有,【2】,個元素。,（,,）,,8.,假設(shè)用一個長度為,50,的數(shù)組（數(shù)組元索的下標從,0,到,49,）作為棧的存儲空間，棧底指針,bottom,指間棧底元素，棧頂指針,top,指向棧頂元素，如果,bottom=49,，,top=30,（數(shù)組下標），則棧中具有,【 】,個元素。,（,2009,年,3,月）,,答案：,19,答案：,15,4,樹和二叉樹,,1,．樹的定義,,樹是,n,個結(jié)點的有限集合,T,，當(dāng),n=0,時，稱為空樹；當(dāng),n>0,時，,T,滿足如下條件：在任一棵非空樹中：（,1,）有且僅有一個稱為根的結(jié)點。（,2,）其余結(jié)點可分為,M,個互不相交的子集合，而且這些子集中的每一個本身又是一棵樹，也稱為根的子樹。,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,2,．樹的實例樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象,,例,1,．家族族譜,設(shè)某家庭有,13,個成員,A,、,B,、,C,、,D,、,E,、,F,、,G,、,H,、,I,、,J,、,K,、,L,、,M,，他們之間的關(guān)系可用樹表示：,,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,計算機中樹是常用的數(shù)據(jù)組織形式,盡管有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。,例,2,計算機的文件系統(tǒng) 不論是,DOS,文件系統(tǒng)還是,window,文件系統(tǒng)，所有的文件都是用樹的形式來組織的。,文件夾,1,文件夾,n,文件,1,文件,2,文件夾,11,文件夾,12,文件,11,文件,12,C,盤,3,、樹的 基本術(shù)語,,樹的結(jié)點：包含一個數(shù)據(jù)元素及若干指,向子樹的分支；,孩子結(jié)點：結(jié)點的子樹的根稱為該結(jié)點,的孩子，,B,、,C,是,A,的孩子；,雙親結(jié)點：,B,結(jié)點是,A,結(jié)點的孩子，則,A,,結(jié)點是,B,結(jié)點的雙親；,兄弟結(jié)點：同一雙親的孩子結(jié)點，,,H,、,I,、,J,互為兄弟；,堂兄結(jié)點,：,同一層上結(jié)點，,E,、,F,、,G,、,H,、,I,、,J,、,互為堂兄弟；,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,,3,、樹的 基本術(shù)語,結(jié)點的層次：根結(jié)點的層次定義為,1,；根的孩子為第二層，依此類推；,樹的深度：,樹中所有結(jié)點的層次的最大值,結(jié)點的度：,結(jié)點子樹的個數(shù),樹的度：,樹中結(jié)點度的最大值。,葉子結(jié)點,：度為,0,的結(jié)點；,分枝結(jié)點：,度不為,0,的結(jié)點；,,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,,一 二叉樹的概念,,1,二叉樹的定義,二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,一 二叉樹的概念,二叉樹,說明,1,）二叉樹中每個結(jié)點最多有兩個子樹；,既：二叉樹每個結(jié)點度小于等于,2;,2,）左、右子樹不能顛倒,——,有序樹,;,3,）二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念,;,,,(a),、,(b),是不同的二叉樹，,,(a),的左子樹有四個結(jié)點,，,(b),的左子樹有兩個結(jié)點,(a),(b),,,,,G,,E,,,,D,,,C,,B,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,F,A,,2,． 二叉樹的基本形態(tài),,,,,,,,,,φ,(a),空樹,(b),只有根,(c),右子樹空,(e),左子樹空,(d),左、右子樹非空,,二、 二叉樹的性質(zhì),,,性質(zhì),1:,在二叉樹的第,i,層上至多有,2,i-1,個結(jié)點,(i≥1),。 ,,性質(zhì),2:,深度為,k,的二叉樹至多有,2,k,-1,個結(jié)點（,k≥1,）。,,,性質(zhì),3:,,對任意一棵二叉樹,T,，若葉結(jié)點數(shù)為,n,0,，而其度為,2,的結(jié)點數(shù)為,n,2,，則,n,0,=n,2,+1,,。,,兩種特殊的二叉樹,滿二叉樹：深度為,k,的二叉樹，如有,2,k,-1,個結(jié)點則稱為滿二叉樹；,,,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),。,,,,,完全二叉樹：,,深度為,k,，結(jié)點數(shù)為,n,的二叉樹，如果其結(jié)點,1~n,的位置序號分別與滿二叉樹的結(jié)點,1~n,的位置序號一一對應(yīng)，則為完全二叉樹， 如上圖,(b),所示。,,滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。,,,性質(zhì),4,：具有,n,個結(jié)點的完全二叉樹的深度為［,log,2,n,］,+1,。,,,性質(zhì),5:,,對于有,n,個結(jié)點的完全二叉樹， 按照從上到下、從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從,1,開始順序編號， 則對于任意的序號為,i,的結(jié)點有：,,（,1,） 如,i=1,，則序號為,i,的結(jié)點是根結(jié)點， 無雙親結(jié)點； 如,i>1,， 則序號為,i,的結(jié)點的雙親結(jié)點序號為［,i/2,］,（下取整）,,（,2,） 如,2i>n,，則序號為,i,的結(jié)點無左孩子；如,2i≤n,，則序號為,i,的結(jié)點的左孩子結(jié)點的序號為,2i,。 ,（,3,） 如,2i,＋,1>n,，則序號為,i,的結(jié)點無右孩子；如,2i,＋,1≤n,， 則序號為,i,的結(jié)點的右孩子結(jié)點的序號為,2i,＋,1,。,,,二叉樹,存儲結(jié)構(gòu),---,二叉鏈表,二叉鏈表中每個結(jié)點包含三個域：數(shù)據(jù)域、左指針域、右指針域,,,A,,,F,,,E,,,D,,,C,,,B,,二叉鏈表圖示,,∧,,D,,,,A,,B ∧,,C,,∧,,∧,E ∧,,∧,F ∧,,若一個二叉樹含有,n,個結(jié)點，則它的二叉鏈表中必含有,2n,個指針域， 其中必有,n+1,個空的指針域。,,,,二、二叉樹的遍歷（必考）,遍歷,：,按某種順序訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次。,訪問：,含義很廣，可以是對結(jié)點的各種處理,，如修改結(jié)點數(shù)據(jù)、輸出結(jié)點數(shù)據(jù)。,,,如何訪問二叉樹的每個結(jié)點，,而且每個結(jié)點僅被訪問一次？,？,,二叉樹的遍歷方法（必考）,,二叉樹由根、左子樹、右子樹三部分組成,二叉樹的遍歷,可以分解為：訪問根，遍歷,左子樹,和,遍歷,右子樹,令,：,L,：,遍歷左子樹,,T,：,訪問根結(jié)點,,R,：,遍歷右子樹,,約定先左后右,,,有三種遍歷方法：,,T,L R,前序遍歷、,,,L,T,R,中序遍歷,、,,L R,T,后序遍歷。,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,,,先序遍歷,（,T,,L,R,）,,若二叉樹非空 （,1,）訪問根結(jié)點；,（,2,）先序遍歷左子樹； （,3,）先序遍歷右子樹,；,,先序遍歷序列,：,A,,,B,D,,E,,G,,C,,,F,例：先,序遍歷右圖所示的二叉樹,（,1,）訪問根結(jié)點,A,,（,2,）先序遍歷左子樹：即按,,T,,L,R,的順序遍歷,左子樹,（,3,）先序遍歷右子樹：即按,,T,,L,R,的順序遍歷,右子樹,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,中序遍歷（,L,T,,R,）,若二叉樹非空（,1,）中序遍歷左子樹（,2,）訪問根結(jié)點,（,3,）中序遍歷右子樹,,中序遍歷序列,：,,D,B,G,,E,,,A,,,C,F,例：,中序遍歷右圖所示的二叉樹,（,1,）中序遍歷左子樹：即按,,L,T,,R,的順序遍歷,左子樹,,（,2,）訪問根結(jié)點,A,,（,3,）中序遍歷右子樹：即按,,L,T,,R,的順序遍歷,右子樹,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,后序遍歷（,L,R,T,）,若二叉樹非空（,1,）后序遍歷左子樹（,2,）后序遍歷右子樹,（,3,）訪問根結(jié)點,,后序遍歷序列：,,D,G,,E,,B,,F,C,,,A,例：后,序遍歷右圖所示的二叉樹,（,1,）后序遍歷左子樹：即按,,L,R,T,,的順序遍歷,左子樹,,（,2,）后序遍歷右子樹：即按,,L,R,T,,的順序遍歷,右子樹,,（,3,）訪問根結(jié)點,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,，則該二叉樹的后序遍歷為,?,,A) GEDHFBCA     B) DGEBHFCAC) ABCDEFGH     D) ACBFEDHG,B,,二叉樹,,1,二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹；,,2,二叉樹可以用鏈式結(jié)構(gòu)存儲；,遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點，每個結(jié)點僅被訪問一次。,,二叉樹的遍歷可以分解為：訪問根，遍歷,左子樹和,遍歷,右子樹，常用的三種遍歷算法：,先序遍歷、中序遍歷、后序遍歷；,,5,查找,,5.1,查找的基本概念,,查找（列）表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合， 可利用任意數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。 ,關(guān)鍵字：,數(shù)據(jù)元素的某個（幾個）數(shù)據(jù)項的值。如果一個數(shù)據(jù)項可以,唯一標識列表中的一個數(shù)據(jù)元素,， 則稱其為關(guān)鍵字。,,查找： 根據(jù)給定的關(guān)鍵字值，在特定的查找（列）表中確定一個其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。,若找到相應(yīng)的數(shù)據(jù)元素， 稱查找成功，否則稱查找失敗,,5,．,2,線性表的查找,5.2.1,順序查找,---,最簡單的查找方法,順序查找的基本思想,,,從表的一端開始，順序掃描線性表，,依次將掃描到的結(jié)點關(guān)鍵字和待找的值Ｋ相比較，若相等，則查找成功，若整個表掃描完畢，仍末找到關(guān)鍵字等于Ｋ的元素，則查找失敗。,順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無序的。,,,順序查找算法的性能。,假設(shè)列表長度為,n,，那么查找第,i,個數(shù)據(jù)元素時需進行,n-i+1,次比較，即,C,i,=n-i+1,。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即,P,i,=1/n,， 則順序查找算法的平均查找長度為：,順序查找的特點,,,,,,順序查找的,優(yōu)點是算法簡單,，對查找表結(jié)構(gòu)無任何要求，無論是用向量還是用鏈表來存放結(jié)點，也無論結(jié)點之間是否按關(guān)鍵字有序或無序排，它都同樣適用。,順序查找的缺點是,查找效率低,，當(dāng),n,較大時，不宜采用順序查找,。,二分,查找（折半查找）,1.,二分查找的基本思想,,,高效率的查找方法。要求表中元素按關(guān)鍵字有序,(,升序或降序,),。假設(shè)表中元素為升序排列。,二分查找的基本思想是：,首先將表,中間位置記錄的關(guān)鍵字與查找關(guān)鍵字,比較，如果兩者相等，則查找成功；,否則利用中間位置記錄,將表分成前、后兩個子表， 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，,則進一步查找前一子表，否則進一步查找后一子表。,重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。,例如，假設(shè)給定有序表中關(guān)鍵字為：,{05,13,19,21,37,56,64,74,80,88,92},，查找,K=21,的情況：,,,,,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,,0 1 2 3 4 5 6 7 8 9 10,3.,二分查找的性能分析,二分查找的過程可以用二叉樹來描述。把當(dāng)前查找區(qū)間的中點作為根結(jié)點，左子區(qū)間和右子區(qū)間分別作為根的左子樹和右子樹，左子區(qū)間和右子區(qū)間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。,例如，給定的關(guān)鍵字序列,05,13,19,21,37,56,64,74,80,88,92,，的判定樹。,,,0 1 2 3 4 5 6 7 8 9 10,,,,在長度為,n,的有序線性表中進行二分查找。最壞的情況下，需要的比較次數(shù)為,log,2,n,,,,6,排序,,6,．,1,基本概念,,6.1.1,排序定義,,排序就是把一組記錄（元素）按照某個域的值的遞增或遞減的次序重新排列的過程。,(,按學(xué)號的遞增,),表,7-1,學(xué)生檔案表,,學(xué)號,,,姓名,,,年齡,,,性別,,,99001,,,王曉佳,,,18,,,男,,,99002,,,林一鵬,,,19,,,男,,,99003,,,謝寧,,,17,,,女,,,99004,,,張麗娟,,,18,,,女,,,99005,,,周濤,,,20,,,男,,,99006,,,李小燕,,,16,,,女,,,,為討論方便，我們直接將排序碼寫成一個一維數(shù)組的形式，,并且在沒有聲明的情形下，所有排序都按排序碼的值遞增排列。,排序,,,插入排序（直插排序、希爾排序）,,,交換排序（冒泡排序、快速排序）,,,選擇排序 （直選排序、堆排序）,,歸并排序（二路歸并排序）,,,,6,．,2,插入排序,,直接插入排序,1,．直接插入排序（,Straight Insertion Sorting,）,,基本思想：把,n,個待排序的元素看成一個有序表和一個無序表，,開始時有序表中只包含一個元素，無序表中包含有,n-1,個元素，,排序過程中每次從無序表中取出第一個元素，把它的排序碼,依次與有序表元素的排序碼進行比較，將它插入到有序表中,的適當(dāng)位置，使之成為新的有序表。,,例如，,n=6,，數(shù)組,R,的六個排序碼分別為：,17,，,3,，,25,，,14,，,20,，,9,。它的直接插入排序的執(zhí)行過程如圖,7-1,所示。,,3,．直接插入排序的效率分析,直接插入排序算法十分簡單。,空間,:,只需要一個元素的輔助空間，用于元素的位置交換,。,時間,:,外層循環(huán)要進行,n-1,次插入，每次插入最少比較一次（正序），移動兩次；最多比較,i,次，移動,i,＋,2,次（逆序）（,i=1,，,2,，,…,，,n-1,）。,直接插入排序的時間復(fù)雜度為,O,（,n,2,）。,最壞情況比較,n(n-1)/2,,希爾排序,,希爾排序,(,縮小增量排序,):1959,年由提出來的。,基本思想：先將整個待排元素序列分割成若干個子序列（由 “增量”確定）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的。,,例如，,n=8,，數(shù)組,array[ ],的八個元素分別為：,91,，,67,，,35,，,62,，,29,，,72,，,46,，,57,。下面用圖,7-2,給出希爾排序算法的執(zhí)行過程。,,希爾排序的效率分析,與增量有關(guān)，,最壞情況，希爾排序的時間復(fù)雜性在,O,（,nlog,2,n,）。,,,6,．,3,交換排序,6.3.1,冒泡排序,基本思想,:,,對待排序序列從后向前（從下標較大的元素開始），依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較小的元素逐漸從后部移向前部，就象水底下的氣泡一樣逐漸向上冒。,,例如，,n=6,，數(shù)組,R,的六個排序碼分別為：,17,，,3,，,25,，,14,，,20,，,9,。下面用圖,7-3,給出冒泡排序算法的執(zhí)行過程。,,,冒泡排序的效率分析,,若待排序的元素為正序，則只需進行一趟排序，比較次數(shù)為（,n-1,）次，移動元素次數(shù)為,0,；,若待排序的元素為逆序，則需進行,n-1,趟排序，比較次數(shù)為,(n,2,-n)/2,，移動次數(shù)為,3(n,2,-n )/2,，,最壞情況比較,n(n-1)/2,因此冒泡排序算法的時間復(fù)雜度為,O,（,n,2,）。由于其中的元素移動較多，所以屬于內(nèi)排序中速度較慢的一種。,6.3.2,快速排序,基本思想是：取待排序序列中的某個元素（一般第一個元素）作為基準，通過一趟排序，將待排元素分為左右兩個子序列，,左子序列元素的排序碼均小于或等于基準元素的排序碼，,右子序列的排序碼則大于基準元素的排序碼，,然后分別對兩個子序列繼續(xù)進行,快速,排序，直至整個序列有序。,,元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面，排序碼較小的記錄一次就能夠交換到前面，記錄每次移動的距離較遠，因而總的比較和移動次數(shù)較少。,,例如，給定排序碼為：（,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,），具體劃分如圖,7-4,所示。,,3,．快速排序的效率分析,,若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長度大致相等），則結(jié)點數(shù),n,與二叉樹深度,h,應(yīng)滿足,log,2,n<h<log,2,n+1,，所以總的比較次數(shù)不會超過,(n+1) log,2,n,。因此，,快速排序的最好時間復(fù)雜度應(yīng)為,O,（,nlog,2,n,）。,已經(jīng)證明，快速排序的平均時間復(fù)雜度也為,O,（,nlog,2,n,）,。,若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，總的比較次數(shù)為,n(n-1)/2,,。因此，,快速排序的最壞時間復(fù)雜度為,O(n,2,),。,快速排序所占用的輔助空間為棧的深度，故最好的空間復(fù)雜度為,O,（,log,2,n,），最壞的空間復(fù)雜度為,O(n),。,快速排序是一種不穩(wěn)定的排序方法。,6,．,4,選擇排序,,6 . 4.1,直接選擇排序,基本思想,直接選擇排序是一種簡單的排序方法?；舅枷胧牵旱谝淮螐?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,次，得到一個按排序碼從小到大排列的有序序列,。,例如，給定,n=8,，數(shù)組,R,中的,8,個元素的排序碼為：（,8,，,3,，,2,，,1,，,7,，,4,，,6,，,5,），則直接選擇排序過程如圖,7-5,所示。,,直接選擇排序的效率分析,,,在直接選擇排序中，共需要進行,n-1,次選擇和交換，每次選擇需要進行,n-i,次比較（,1≤i≤n-1,），而每次交換最,多需,3,次移動，因此，總的比較次數(shù),C= =(n,2,-n)/2,，,總的移動次數(shù),M= =3(n-1),。,,直接選擇排序的時間復(fù)雜度為,O(n,2,),數(shù)量級，所以當(dāng)記錄占用的字節(jié)數(shù)較多時，通常比直接插入排序的執(zhí)行速度要快一些,。,最壞情況比較,n(n-1)/2,,,,7,．,5,歸并排序,,,1,、,基本思想：將兩個有序子區(qū)間（有序表）合并成一個有序子區(qū)間，一次合并完成后，有序子區(qū)間的數(shù)目減少一半，而區(qū)間的長度增加一倍，當(dāng)區(qū)間長度從,1,增加到,n,（元素個數(shù)）時，整個區(qū)間變?yōu)橐粋€，即為有序序列,.,,例如，給定排序碼,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,，二路歸并排序過程如圖,7-10,所示。算法,P284,歸并排序的效率分析,,歸并排序的時間復(fù)雜度為,O(nlog,2,n),。,歸并排序時，需要利用與待排序數(shù)組相同的輔助數(shù)組作臨時單元，故該排序方法的空間復(fù)雜度為,O(n),，比前面介紹的其它排序方法占用的空間大。,,對于長度為,n,的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是,A),冒泡排序為,n/2,B),冒泡排序為,n,,C),快速排序為,n,D),快速排序為,n(n-1)/2,D,第二部分 程序設(shè)計,,程序設(shè)計基礎(chǔ),2.1,程序設(shè)計方法與風(fēng)格,如何形成良好的程序設(shè)計風(fēng)格，主要包含以下幾個因素：,（,1,）源程序文檔化。,（,2,）數(shù)據(jù)說明的方法。,（,3,）語句的結(jié)構(gòu)。,（,4,）輸入和輸出。,（,5,）適當(dāng)?shù)淖⑨?注,釋分序言性注釋和功能性注釋。,2,程序設(shè)計基礎(chǔ),2.2,結(jié)構(gòu)化程序設(shè)計,結(jié)構(gòu)化程序設(shè)計方法的四條原則是,（必考）：,1.,自頂向下；,2.,逐步求精；,3.,模塊化；,4.,限制使用,goto,語句。,結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：,（,1,）順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)；,（,2,）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列；,（,3,）重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。,,,2,程序設(shè)計基礎(chǔ),2.3,面向?qū)ο蟪绦蛟O(shè)計,1,、面向?qū)ο蠓椒ǖ?優(yōu)點,：,（,1,）與人類習(xí)慣的思維方法一致。 （,2,）穩(wěn)定性好。,（,3,）可重用性好。 （,4,）易于開發(fā)大型軟件產(chǎn)品。,（,5,）可維護性好。,,2,、面向?qū)ο蠓椒ǖ幕靖拍?（,1,）對象,-,對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。,屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。,2,程序設(shè)計基礎(chǔ),（,2,）類和實例,——,類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)類的一個實例。,（,3,）消息,——,消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括,1,、接收消息的對象的名稱；,2,、消息標識符，也稱消息名；,3,、零個或多個參數(shù)。,（,4,）繼承,——,繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。,（,5,）多態(tài)性,——,多態(tài)性是指同樣的操作在接受不同消息時可導(dǎo)致完全不同的行動的現(xiàn)象。,,比如汽車一個類，而具體到某輛汽車則是一個對象。圖,21,中，機動車類是對機動車特征和功能的總體描述，機動車,A,是具體到某輛車的特征。,,,3,軟件工程基礎(chǔ),3.1,軟件工程基本概念,1,、軟件定義及特點,2,、軟件危機與軟件工程,3,、軟件工程過程和軟件生命周期,軟件生命周期三個階段,:,軟件定義、軟件開發(fā)、運行維護，主要活動階段是：,（,1,）可行性研究與計劃制定；,（,2,）需求分析；,（,3,）軟件設(shè)計；,（,4,）軟件實現(xiàn)；,（,5,）軟件測試；,（,6,）運行和維護。,,,3,軟件工程基礎(chǔ),4,、軟件工程的目標和與原則,目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。,基本目標：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。,軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。,軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境。,軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟學(xué)、軟件心理學(xué)等內(nèi)容。,軟件管理學(xué)包括人員組織、進度安排、質(zhì)量保證、配置管理、項目計劃等。,軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。,3,軟件工程基礎(chǔ),3.2,結(jié)構(gòu)化分析方法,1,、需求分析,——,指用戶對目標軟件系統(tǒng)在功能、行為、性能、設(shè)計約束等方面的期望。,（,1,）結(jié)構(gòu)化需求分析方法。（,2,）面向?qū)ο蟮姆治龅姆椒ǎ?OOA,）。,,2,、結(jié)構(gòu)化分析方法,結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。,步驟：,調(diào)查原系統(tǒng)（獲得當(dāng)前系統(tǒng)如何工作）,原系統(tǒng)邏輯模型,à,需求分析（得出新系統(tǒng)應(yīng)如何工作）,新系統(tǒng)邏輯模型,結(jié)構(gòu)化分析的常用工具：（,1,）數(shù)據(jù)流圖、（,2,）數(shù)據(jù)字典（,D-D,）、（,3,）判定樹、（,4,）判定表,,,,,,,3,軟件工程基礎(chǔ),3,、軟件需求規(guī)格說明書,作用：,（,1,）便于用戶與開發(fā)人員進行交流。,（,2,）是軟件開發(fā)工作的基礎(chǔ)和依據(jù)。,（,3,）作為確認測試和驗收的依據(jù)。,內(nèi)容：,（,1,）概述　　　　?。?2,）數(shù)據(jù)描述,（,3,）功能描述?！　。?4,）性能描述。,（,5,）參考目錄?！　。?6,）附錄。,特點：,（,1,）正確性；（,2,）無岐義性；,（,3,）完整性；（,4,）可驗證性；,（,5,）一致性；（,6,）可理解性；,（,7,）可追蹤性。,3,軟件工程基礎(chǔ),3.3,結(jié)構(gòu)化設(shè)計方法,1,、軟件設(shè)計基本概念,軟件設(shè)計的基本目標：是用比較抽象概括的方式確定目標系統(tǒng)如何完成預(yù)定的任務(wù)，軟件設(shè)計是確定系統(tǒng)的物理模型。,結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。,數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。,接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。,過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。,軟件設(shè)計的基本原理：,（,1,）抽象。,（,2,）模塊化。,（,3,）信息隱藏。,（,4,）模塊獨立性。,3,軟件工程基礎(chǔ),衡量軟件模塊獨立性使用,耦合性和內(nèi)聚,性兩個定性的度量標準。,內(nèi)聚性指一個模塊內(nèi)容各部分之間的緊密程度。內(nèi)聚性越高越好。,耦合性指模塊之間的相互依賴關(guān)系。耦合性越低越好。,在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。,按內(nèi)聚性由弱到強：偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚。,耦合性按由高到低：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數(shù)據(jù)耦合、