《全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)1》由會(huì)員分享，可在線閱讀，更多相關(guān)《全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)1（134頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、求存儲(chǔ)空間?。?空間復(fù)雜度,）,評(píng)價(jià)算法標(biāo)準(zhǔn),,1,時(shí)間復(fù)雜度,T,（,n,）,以求解問題的基本操作的,執(zhí)行次數(shù),作為算法時(shí)間的度量。,算法與算法分析,O,（,n,3,）,,稱為矩陣相乘算法時(shí)間復(fù)雜度；,O,（,n,3,）表示矩陣相乘算法執(zhí)行時(shí)間與,n,3,成正比,,,即,O,（,n,3,）與,n,3,同一數(shù)量級(jí)；,,例：,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í)行次數(shù)均為,n,3,,,矩陣相乘的基本運(yùn)算：乘法 加法；,,數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有,7,個(gè)：,,O(1),常數(shù)型,O(n),線性型,O(n,2,),平方型,,O(n,3,),立方型,O(2,n,),指數(shù)型,,O(log,2,n),對(duì)數(shù)型,O(nlog,2,n),二維型,2,算法空間復(fù)雜度 用執(zhí)行算法所需的,內(nèi)存空間的大小,作為算法所需空間的度量。 設(shè)執(zhí)行算法所需的內(nèi)存空間是問題規(guī)模,n,的某個(gè)函數(shù),g(n),,則算法空間復(fù)雜度記作

5、：,S,（,n,）,= O(g(n)),表示算法內(nèi)存空間的增長(zhǎng)率,與,g(n),的增長(zhǎng)率相同,例計(jì)算,,解法,1,先計(jì)算,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]*

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

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

8、則其時(shí)間復(fù)雜度必定小,,C,）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小,,D,）上述三種說法都不對(duì),(D),計(jì)算工作量,(A),(D),數(shù)據(jù)結(jié)構(gòu),大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。,數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，既按某種邏輯關(guān)系把一批數(shù)據(jù)組織起來，按一定的映象方式把它存放在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義一個(gè)運(yùn)算的集合。,,歸納為三部分：,,邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合,。,,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ù)元素的信

9、息；,（,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)中的每個(gè)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；,線性表、棧、隊(duì)、字符串、數(shù)組,② 樹形結(jié)構(gòu) （非線性）

10、,結(jié)構(gòu)中的每個(gè)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；,③ 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)（非線性）,結(jié)構(gòu)中的每個(gè)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。,,2.,存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）,計(jì)算機(jī)在實(shí)際進(jìn)行數(shù)據(jù)處理時(shí)，被處理的各數(shù)據(jù)元素總是被存放在計(jì)算機(jī)的存儲(chǔ)空間中，并且，各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。,如：一年四季,家庭成員 計(jì)算機(jī)存儲(chǔ)空間怎樣存放？,存儲(chǔ)結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的具體實(shí)現(xiàn)。,常見的存儲(chǔ)結(jié)構(gòu)有：,順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 索引存儲(chǔ)結(jié)構(gòu),3.,數(shù)據(jù)的運(yùn)算,檢索,插入,刪除,更新,排序,,通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能

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

12、,數(shù)組和廣義表,是線性表的擴(kuò)展,--,線性結(jié)構(gòu),,,例、英文字母表（,A, B, C, D, E,?,Z,）。 某單位的電話號(hào)碼簿。,線性表的概念,設(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,） 在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且,僅有一個(gè)

13、前件，有且僅有一個(gè)后件,；,4,） 線性表中元素的個(gè)數(shù),n,稱為線性表的長(zhǎng)度，,n=0,時(shí)稱為空表；,,用,一組連續(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,,）,的順序存儲(chǔ)結(jié)構(gòu),用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表,——,稱為順序表,線性表的順序存儲(chǔ)和實(shí)現(xiàn),一 、 線性表的順序存儲(chǔ)結(jié)構(gòu),,線性表的順序存儲(chǔ)和實(shí)現(xiàn),說明：,元素之間的邏輯關(guān)系，通過元素的存儲(chǔ)順序表示出來,.,設(shè)線性表中每個(gè)數(shù)據(jù)元素占,t,個(gè)存儲(chǔ)單元，那么，在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第,i,個(gè)元素的存儲(chǔ)位置與第,1,個(gè)元

14、素的存儲(chǔ)位置的關(guān)系是：,,,Loc(a,i,) = Loc( a,1,)+ ( i – 1),,t,其中,Loc( a,1,),基地址，隨機(jī)存取,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,,t,個(gè)單元,Loc( a,1,),Loc(a,i,),線性表的順序存儲(chǔ)和實(shí)現(xiàn),,插入位置 移動(dòng)元素個(gè)數(shù),1???????????????????????????? n 2???????????????????????????? n-1? i n

15、-i+1? n 1 n+1 0,插入算法時(shí)間復(fù)雜度分析,算法時(shí)間復(fù)雜度取決于移動(dòng)元素的個(gè)數(shù)，移動(dòng)元素的個(gè)數(shù)不僅與表長(zhǎng)有關(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,.,.,由此可見在順序表中插入一個(gè)元素 ，平均要移動(dòng)表的一半元素。表長(zhǎng)為,n,的順序表，插入算法的時(shí)間復(fù)雜度為,O,（,n,）,假設(shè)在線性表的任何位置插入元素的概率相

16、同，即,,pi= 1/(n+1),,設(shè),p,i,為在第,i,個(gè)元素之前插入元素的概率，在長(zhǎng)度為,n,的順序表中插入一個(gè)元素，所需移動(dòng)元素個(gè)數(shù)數(shù)學(xué)期望值為：,,刪除算法時(shí)間復(fù)雜度分析,假設(shè)在線性表的任何位置刪除元素的概率相同，即,,pi= 1/n,刪除,所需移動(dòng)元素個(gè)數(shù)的數(shù)學(xué)期望值：,,,線性表的順序存儲(chǔ)和實(shí)現(xiàn),,順序表是線性表最簡(jiǎn)單的一種存儲(chǔ)結(jié)構(gòu),,,小結(jié),順序表的特點(diǎn)：,1,通過元素的存儲(chǔ)順序反映 線性表中,數(shù)據(jù)元素之間的邏輯關(guān)系；,2,可隨機(jī)存取順序表的元素；,3,順序表的插入、刪除操作要通過,移動(dòng),元素實(shí)現(xiàn)；,線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn),,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表

17、的各個(gè)數(shù)據(jù)元素。,為了表示線性表中元素的先后關(guān)系，每個(gè)元素除需要存儲(chǔ)自身的信息外，還要保存直接前趨元素或直接后繼元素的存儲(chǔ)位置。,,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,,用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，對(duì)每個(gè)數(shù)據(jù)元素保存自身信息和直接后繼元素的存儲(chǔ)位置。,,用鏈表存儲(chǔ)線性表時(shí)，數(shù)據(jù)元素之間的關(guān)系是通過,保存直接后繼元素的存儲(chǔ)位置來表

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

19、ead,是頭指針,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,頭結(jié)點(diǎn),,空指針,head,線性鏈表的每個(gè)結(jié)點(diǎn)中只有一個(gè)指針域,故也稱為,單鏈表,插入結(jié)點(diǎn),(,存,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,個(gè)元素結(jié)點(diǎn)之前插入一個(gè)新元素結(jié)點(diǎn),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,）,刪除結(jié)點(diǎn),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é),線性鏈表是線性表的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),,線性鏈表的特點(diǎn),,,1,通過保存

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

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

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

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

25、進(jìn)先出,第一個(gè)入隊(duì)的元素在隊(duì)頭，最后一個(gè)入隊(duì)的元素在隊(duì)尾，,第一個(gè)出隊(duì)的元素為隊(duì)頭元素，,最后一個(gè)出隊(duì)的元素為隊(duì)尾元素,,rear,front,J1,,rear,front,J2,（,a),空隊(duì)列,(b)J1,J2,相繼入隊(duì)列,(c)J1,出隊(duì),(d)J3,J4, J5,和,J6,相繼入隊(duì)之后,,J2,出隊(duì),rear,front,,0,1,2,3,4,5,,rear,front,J5,J4,J3,front,rear,為整數(shù),,,又有,J7,入隊(duì),,,怎么辦？,,？,J2,J6,3 .,循環(huán)隊(duì)列,,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),隊(duì)空,(a),隊(duì)滿,J7,,,rear,判分隊(duì)空、隊(duì)滿方法：,1,）另設(shè)一個(gè)標(biāo)志,S,以區(qū)分隊(duì)空、隊(duì)滿。,2,）,S=0,隊(duì)空：,front=rear;,S=1,隊(duì)滿：,front=rear;,或少用一個(gè)空間,Real+1=front,為滿,,,front,,,5,4 0,3 1,2,J6,J7,J8,J4,J5,（,c,）,rear,,入隊(duì)操作,,：,將元素,x,插入隊(duì)尾,,,,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,入隊(duì)前,元素,x,入隊(duì)后,出隊(duì)操作,,：刪除隊(duì)頭,元素；,,,,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,出隊(duì)操作前,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,出隊(duì)操作后,,,小 結(jié),,1,隊(duì)列是限定僅能在表尾一端進(jìn)行插入，表頭一端刪除 操作的線性表；,,2,隊(duì)列中的元素具有先進(jìn)先出的特點(diǎn)；,,3,隊(duì)頭、隊(duì)尾元素的位置分別由稱為隊(duì)頭指針和隊(duì)尾指針的變量指示，,,4,入隊(duì)操作要修改隊(duì)尾指針，出隊(duì)操作要

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

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

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

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

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

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

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

35、,,(a),的左子樹有四個(gè)結(jié)點(diǎn),，,(b),的左子樹有兩個(gè)結(jié)點(diǎn),(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,個(gè)結(jié)點(diǎn),(i≥1),。 ,,性質(zhì),2:,深度為,k,的二叉樹至多有,2,k,-1,個(gè)結(jié)點(diǎn)（,k≥1,）。,,,性質(zhì),3:,,對(duì)任意一棵二叉樹,T,，若葉結(jié)點(diǎn)數(shù)為,n,0,，而其度為,2,

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

37、,深度為,k,，結(jié)點(diǎn)數(shù)為,n,的二叉樹，如果其結(jié)點(diǎn),1~n,的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn),1~n,的位置序號(hào)一一對(duì)應(yīng)，則為完全二叉樹， 如上圖,(b),所示。,,滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。,,,性質(zhì),4,：具有,n,個(gè)結(jié)點(diǎn)的完全二叉樹的深度為［,log,2,n,］,+1,。,,,性質(zhì),5:,,對(duì)于有,n,個(gè)結(jié)點(diǎn)的完全二叉樹， 按照從上到下、從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從,1,開始順序編號(hào)， 則對(duì)于任意的序號(hào)為,i,的結(jié)點(diǎn)有：,,（,1,） 如,i=1,，則序號(hào)為,i,的結(jié)點(diǎn)是根結(jié)點(diǎn)， 無雙親結(jié)點(diǎn)； 如,i>1,， 則序號(hào)為,i,的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為［,

38、i/2,］,（下取整）,,（,2,） 如,2i>n,，則序號(hào)為,i,的結(jié)點(diǎn)無左孩子；如,2i≤n,，則序號(hào)為,i,的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為,2i,。 ,（,3,） 如,2i,＋,1>n,，則序號(hào)為,i,的結(jié)點(diǎn)無右孩子；如,2i,＋,1≤n,， 則序號(hào)為,i,的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為,2i,＋,1,。,,,二叉樹,存儲(chǔ)結(jié)構(gòu),---,二叉鏈表,二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域,,,A,,,F,,,E,,,D,,,C,,,B,,二叉鏈表圖示,,∧,,D,,,,A,,B ∧,,C,,∧,,∧,E ∧,,∧,F ∧,,若一個(gè)二叉樹含有,n,個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有,2

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

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

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

42、子樹：即按,,L,R,T,,的順序遍歷,左子樹,,（,2,）后序遍歷右子樹：即按,,L,R,T,,的順序遍歷,右子樹,,（,3,）訪問根結(jié)點(diǎn),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,二叉樹： 或?yàn)榭諛?，或由根及兩顆互不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹；,,2,二叉樹可以用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；,遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)僅被訪問一次。,,二叉樹的遍歷可以分解為：訪問根，遍歷,左子樹和,遍歷,右子樹，常用的三種遍歷算法：,先序遍歷、中序遍歷、后序遍歷；,,5,查找,,5.1,查找的基本概念,,查找（列）表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合， 可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。 ,關(guān)鍵字：,數(shù)據(jù)元素的

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

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

46、找的基本思想,,,高效率的查找方法。要求表中元素按關(guān)鍵字有序,(,升序或降序,),。假設(shè)表中元素為升序排列。,二分查找的基本思想是：,首先將表,中間位置記錄的關(guān)鍵字與查找關(guān)鍵字,比較，如果兩者相等，則查找成功；,否則利用中間位置記錄,將表分成前、后兩個(gè)子表， 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，,則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。,重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。,例如，假設(shè)給定有序表中關(guān)鍵字為：,{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.,二分查找的性能分析,二分查找的過程可以用二叉樹來描述。把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn)，左子區(qū)間和右子區(qū)間分別作為根的左子樹和右子樹，左子

48、區(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,,,,在長(zhǎng)度為,n,的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為,log,2,n,,,,6,排序,,6,．,1,基本概念,,6.1.1,排序定義,,排序就是把一組記錄（元素）按照某個(gè)域的值的遞增或遞減的次序重新排列的過程。,(,按學(xué)號(hào)的遞增,),表,7-1,學(xué)生檔案表,,學(xué)號(hào),,,姓名,,,年齡,,,性別,,,9900

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

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

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

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

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

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

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

56、排序是一種簡(jiǎn)單的排序方法?；舅枷胧牵旱谝淮螐?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,次，得到一個(gè)按排序碼從小到大排列的有序序

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

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

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

60、（必考）：,1.,自頂向下；,2.,逐步求精；,3.,模塊化；,4.,限制使用,goto,語句。,結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn)：,（,1,）順序結(jié)構(gòu)：一種簡(jiǎn)單的程序設(shè)計(jì)，最基本、最常用的結(jié)構(gòu)；,（,2,）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列；,（,3,）重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。,,,2,程序設(shè)計(jì)基礎(chǔ),2.3,面向?qū)ο蟪绦蛟O(shè)計(jì),1,、面向?qū)ο蠓椒ǖ?優(yōu)點(diǎn),：,（,1,）與人類習(xí)慣的思維方法一致。 （,2,）穩(wěn)定性好。,（,3,）可重用性好。

61、 （,4,）易于開發(fā)大型軟件產(chǎn)品。,（,5,）可維護(hù)性好。,,2,、面向?qū)ο蠓椒ǖ幕靖拍?（,1,）對(duì)象,-,對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。,屬性即對(duì)象所包含的信息，操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。,2,程序設(shè)計(jì)基礎(chǔ),（,2,）類和實(shí)例,——,類是指具有共同屬性、共同方法的對(duì)象的集合。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。,（,3,）消息,——,消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組成包括,1,、接收消息的對(duì)象的名稱；,2,、消息標(biāo)識(shí)符，也稱消息名；,3,、零個(gè)或多個(gè)參數(shù)。,（,4,）繼承,——,

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

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

64、環(huán)境。,軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。,軟件管理學(xué)包括人員組織、進(jìn)度安排、質(zhì)量保證、配置管理、項(xiàng)目計(jì)劃等。,軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。,3,軟件工程基礎(chǔ),3.2,結(jié)構(gòu)化分析方法,1,、需求分析,——,指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。,（,1,）結(jié)構(gòu)化需求分析方法。（,2,）面向?qū)ο蟮姆治龅姆椒ǎ?OOA,）。,,2,、結(jié)構(gòu)化分析方法,結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。,步驟：,調(diào)查原

65、系統(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ā)人員進(jìn)行交流。,（,2,）是軟件開發(fā)工作的基礎(chǔ)和依據(jù)。,（,3,）作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)。,內(nèi)容：,（,1,）概述　　　　?。?2,）數(shù)據(jù)描述,（,3,）功能描述?！　。?4,）性能描述。,（,5,）參考目錄。　?。?6,）附錄。,特點(diǎn)：,（,1,）正確性；（,2,）無岐義性；,（,3,）完整性；

66、（,4,）可驗(yàn)證性；,（,5,）一致性；（,6,）可理解性；,（,7,）可追蹤性。,3,軟件工程基礎(chǔ),3.3,結(jié)構(gòu)化設(shè)計(jì)方法,1,、軟件設(shè)計(jì)基本概念,軟件設(shè)計(jì)的基本目標(biāo)：是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。,結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(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)換成軟件的過程描述。,軟件設(shè)計(jì)的基本原理：,（,1,）抽象。,（,2,）模塊化。,（,3,）信息隱藏。,（,4,）模塊獨(dú)立性。,3,軟件工程基礎(chǔ),衡量軟件模塊獨(dú)立性使用,耦合性和內(nèi)聚,性兩個(gè)定性的度量標(biāo)準(zhǔn)。,內(nèi)聚性指一個(gè)模塊內(nèi)容各部分之間的緊密程度。內(nèi)聚性越高越好。,耦合性指模塊之間的相互依賴關(guān)系。耦合性越低越好。,在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。,按內(nèi)聚性由弱到強(qiáng)：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過程內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚。,耦合性按由高到低：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、