軟件技術(shù)基礎(chǔ)

1、第十三章第十三章 軟件技術(shù)基礎(chǔ)軟件技術(shù)基礎(chǔ)主講：張明旺主講：張明旺13.1 13.1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1 1、基本概念、基本概念 數(shù)據(jù)數(shù)據(jù)所有能被計(jì)算機(jī)處理的符號(hào)的集合所有能被計(jì)算機(jī)處理的符號(hào)的集合包括：常數(shù)、字母、程序、圖形、語(yǔ)言等。包括：常數(shù)、字母、程序、圖形、語(yǔ)言等。 數(shù)據(jù)元素?cái)?shù)據(jù)元素給定數(shù)據(jù)集合中的個(gè)體給定數(shù)據(jù)集合中的個(gè)體設(shè)給定數(shù)據(jù)集合為：設(shè)給定數(shù)據(jù)集合為： D=d1D=d1，d2d2，dndn 則則didi屬于屬于D D，并稱(chēng)，并稱(chēng)didi為為數(shù)據(jù)數(shù)據(jù)元素。元素。例如例如給定數(shù)據(jù)集合給定數(shù)據(jù)集合班級(jí)班級(jí)A=A=學(xué)生學(xué)生a,a,學(xué)生學(xué)生b b 學(xué)生學(xué)生nn則班級(jí)中的每一個(gè)學(xué)生稱(chēng)為數(shù)據(jù)元

2、素。則班級(jí)中的每一個(gè)學(xué)生稱(chēng)為數(shù)據(jù)元素。 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)數(shù)據(jù)元素常常還可分為若干個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)具數(shù)據(jù)元素常常還可分為若干個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)具有意義的最小單位。有意義的最小單位。例如：學(xué)生例如：學(xué)生a a的姓名、性別、年齡等都是數(shù)據(jù)項(xiàng)的姓名、性別、年齡等都是數(shù)據(jù)項(xiàng) 數(shù)據(jù)之間的邏輯結(jié)構(gòu)數(shù)據(jù)之間的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的關(guān)系反映數(shù)據(jù)元素之間的關(guān)系線性結(jié)構(gòu)線性結(jié)構(gòu)： 僅有一個(gè)開(kāi)始和結(jié)束數(shù)據(jù)元素，每個(gè)數(shù)據(jù)元素最多僅有一個(gè)開(kāi)始和結(jié)束數(shù)據(jù)元素，每個(gè)數(shù)據(jù)元素最多只有一個(gè)直接前驅(qū)和直接后繼。（數(shù)組）只有一個(gè)直接前驅(qū)和直接后繼。（數(shù)組）非線性結(jié)構(gòu)：非線性結(jié)構(gòu)： 數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和直接后繼（樹(shù)、

3、圖）數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和直接后繼（樹(shù)、圖）13.2 13.2 線性表及其基本運(yùn)算線性表及其基本運(yùn)算1 1、線性表（、線性表（linear_listlinear_list） 線性表是線性表是n n個(gè)數(shù)據(jù)元素的有限序列，記為：個(gè)數(shù)據(jù)元素的有限序列，記為： L=L=（a a1 1,a,a2 2, , ,a,an n） 數(shù)據(jù)元素之間的關(guān)系是：數(shù)據(jù)元素之間的關(guān)系是： ai-1ai-1領(lǐng)先于領(lǐng)先于aiai，aiai領(lǐng)先于領(lǐng)先于ai+1ai+1。 稱(chēng)稱(chēng)ai-1ai-1是是aiai的直接的直接前驅(qū)前驅(qū)元素；元素；ai+1ai+1是是aiai的直接的直接后繼后繼元素。元素。 除除a1a1外，每個(gè)元素有且

4、僅有一個(gè)直接前驅(qū)元素外，每個(gè)元素有且僅有一個(gè)直接前驅(qū)元素; ; 除除anan外，每個(gè)元素有且僅有一個(gè)直接后繼元素外，每個(gè)元素有且僅有一個(gè)直接后繼元素; ; 線性表中數(shù)據(jù)元素的個(gè)數(shù)線性表中數(shù)據(jù)元素的個(gè)數(shù)n(nn(n=0)=0)稱(chēng)為線性表的稱(chēng)為線性表的長(zhǎng)度長(zhǎng)度; ; 當(dāng)當(dāng)n=0n=0時(shí)，稱(chēng)為時(shí)，稱(chēng)為空表空表。2 2、基本運(yùn)算、基本運(yùn)算INITIATEINITIATE（L L） 初始化操作初始化操作 設(shè)定一個(gè)空的線性表設(shè)定一個(gè)空的線性表L LLENGTHLENGTH（L L） 求長(zhǎng)度函數(shù)求長(zhǎng)度函數(shù) 值為值為L(zhǎng) L中數(shù)中數(shù) 據(jù)元素的個(gè)數(shù)據(jù)元素的個(gè)數(shù)GETGET（L L，i i） 取元素函數(shù)取元素函數(shù)

5、1=i=LENGTH(L)1=i=LENGTH(L)時(shí)返回時(shí)返回L L中中第第i i個(gè)數(shù)據(jù)元素，否則為空元素個(gè)數(shù)據(jù)元素，否則為空元素NULLNULL。 i i稱(chēng)為該數(shù)據(jù)元素在稱(chēng)為該數(shù)據(jù)元素在L L中的中的位序位序LOCATELOCATE（L L，x x） 定位函數(shù)定位函數(shù) 給定值給定值x x，若，若x x不在表中，則返不在表中，則返回回-1-1，否則，返回，否則，返回x x在表中第一次出現(xiàn)時(shí)的位序在表中第一次出現(xiàn)時(shí)的位序INSERTINSERT（L, i , bL, i , b）前插操作前插操作 在第在第i i個(gè)元素之前插入新元素個(gè)元素之前插入新元素b b，i i 的取值范圍為：的取值范圍為：

6、1=i=n+11=i=n+1；i =n+1i =n+1表示在表尾插入，表示在表尾插入， n n為表長(zhǎng)為表長(zhǎng) DELETEDELETE（L L，i i）刪除操作刪除操作 刪除線性表刪除線性表L L中的第中的第i i個(gè)元素，個(gè)元素， 1=i=n1=i=nEMPTY(L)EMPTY(L)判空表函數(shù)判空表函數(shù)若若L L為空表，則返回布爾值為空表，則返回布爾值“true”true”，否則返回布爾值否則返回布爾值“false”false”CLEARCLEAR（L L） 表置空操作表置空操作 將將L L置為空表置為空表a1a2aian b b+k b+(i-1)k b+(n-1)k3 3、線性表的順序存儲(chǔ)結(jié)

7、構(gòu)、線性表的順序存儲(chǔ)結(jié)構(gòu) 1 1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素。設(shè)每的存儲(chǔ)單元依次存儲(chǔ)線性表的元素。設(shè)每個(gè)元素占用個(gè)元素占用k k個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元， Loc(aLoc(a1 1) )為線性表的起址，則為線性表的起址，則第第i i個(gè)元素個(gè)元素a ai i 的存儲(chǔ)位置為：的存儲(chǔ)位置為：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)* *k k 2 2）插入運(yùn)算）插入運(yùn)算 INSERTINSERT（L, i, bL, i, b） 插入前：插入前：L=L=（a a1 1, . , a, . , ai-

8、1i-1, a, ai i, . ,a, . ,an n） 插入后：插入后：L=L=（a a1 1, . , a, . , ai-1i-1, , b b, a, ai i, . ,a, . ,an n ） 算法思想：算法思想： 進(jìn)行合法性檢查，進(jìn)行合法性檢查，1=i=n+11=i=n+1； 判斷線性表是否已滿；判斷線性表是否已滿； 將第將第n n個(gè)至第個(gè)至第i i個(gè)元素逐一后移一個(gè)單元；個(gè)元素逐一后移一個(gè)單元； 在第在第i i個(gè)位置處插入新元素；個(gè)位置處插入新元素； 將表的長(zhǎng)度加將表的長(zhǎng)度加1 1。 3 3）刪除運(yùn)算）刪除運(yùn)算DELETEDELETE（L,iL,i） 刪除前：刪除前：L=L=（

9、a a1 1,.,a,.,ai-1i-1, ,a ai i,a,ai+1i+1,.,a,.,an n） 刪除后：刪除后：L=L=（a a1 1,.,a,.,ai-1i-1,a,ai+1i+1,.,a,.,an n） 算法思想：算法思想： 進(jìn)行合法性檢查，進(jìn)行合法性檢查，i i是否滿足是否滿足1=i=n1=inextnextp p-nextnext；p p-next=snext=s； 順序不可換順序不可換 x xy yp pb bs sx xb by ys sp p ）DELETE(LDELETE(L，i)i)刪除運(yùn)算刪除運(yùn)算 刪除前刪除前 刪除后刪除后 刪除運(yùn)算可以由定位和修改指針來(lái)完成：刪除

10、運(yùn)算可以由定位和修改指針來(lái)完成： 定位：得到指向定位：得到指向第第i i個(gè)元素個(gè)元素的前驅(qū)的指針的前驅(qū)的指針p p； 修改指針：修改指針：p-nextp-nextp p-next next -next next ；pp6 6、循環(huán)鏈表、循環(huán)鏈表令鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，使整個(gè)鏈令鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，使整個(gè)鏈表形成一個(gè)環(huán)，稱(chēng)這樣的鏈表為循環(huán)鏈表。表形成一個(gè)環(huán)，稱(chēng)這樣的鏈表為循環(huán)鏈表。 循環(huán)鏈表循環(huán)鏈表H=(aH=(a1 1，a a2 2，a an n) )邏輯表示為：邏輯表示為：a1anH空表時(shí)：空表時(shí)：H= H-nextH= H-next；13.3 13.3 棧

11、棧( Stack )( Stack )定義定義: :是限定僅在表尾進(jìn)行插入或刪除操作的線性表。是限定僅在表尾進(jìn)行插入或刪除操作的線性表。允許插入和刪除的一端允許插入和刪除的一端稱(chēng)為棧頂稱(chēng)為棧頂(top)(top)，另一端，另一端稱(chēng)為棧底稱(chēng)為棧底(bottom)(bottom)特點(diǎn)：特點(diǎn)：后進(jìn)先出后進(jìn)先出 (LIFO)(LIFO)a1topbottoman.進(jìn)棧進(jìn)棧 出棧出棧1 1、棧的表示和實(shí)現(xiàn)、棧的表示和實(shí)現(xiàn) 順序棧：順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針指針top指

12、向指向棧頂元素在順序棧中的下一個(gè)位置，棧頂元素在順序棧中的下一個(gè)位置，base為棧底指針，為棧底指針，指向棧底的位置。指向棧底的位置。toptopabcdee 進(jìn)棧abcdef 進(jìn)棧溢出abde 出出棧cbasebasebasetop空?？諚 a 進(jìn)棧進(jìn)棧b b 進(jìn)棧進(jìn)棧a aa ab btoptopbasebasetoptopbasebasetoptopbase13.3 13.3 隊(duì)列隊(duì)列定義定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。素的線性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear）允許刪除的一

13、端稱(chēng)為對(duì)頭允許刪除的一端稱(chēng)為對(duì)頭(front)。特點(diǎn)：特點(diǎn)：先進(jìn)先出先進(jìn)先出 (FIFO) a1 ，a2， a3，an出隊(duì)列出隊(duì)列入隊(duì)列入隊(duì)列隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾鏈隊(duì)列：隊(duì)列的鏈?zhǔn)奖硎炬滉?duì)列：隊(duì)列的鏈?zhǔn)奖硎炬滉?duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈隊(duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。data nextfrontreardata nextfrontrearfrontrearx元素元素x入隊(duì)入隊(duì)frontrearxy元素元素y入隊(duì)入隊(duì)frontrearxy元素元素x出隊(duì)出隊(duì)frontrear空隊(duì)列空隊(duì)列front

14、rearNULL空隊(duì)列空隊(duì)列隊(duì)列的進(jìn)隊(duì)和出隊(duì)：隊(duì)列的進(jìn)隊(duì)和出隊(duì)：front rear空隊(duì)列空隊(duì)列frontrearA,B,C, D進(jìn)隊(duì)進(jìn)隊(duì)A B C DfrontrearA,B出隊(duì)出隊(duì)C DfrontrearE,F,G進(jìn)隊(duì)進(jìn)隊(duì)C D E F GC D E F GfrontrearH進(jìn)隊(duì)進(jìn)隊(duì),溢溢出出13.4 13.4 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)1 1、樹(shù)的定義、樹(shù)的定義 樹(shù)樹(shù)是是n n個(gè)數(shù)據(jù)元素的有限集個(gè)數(shù)據(jù)元素的有限集( (記為記為T(mén))T)，對(duì)任意一棵樹(shù)，對(duì)任意一棵樹(shù)T T有：有： 1) 1) 存在唯一一個(gè)稱(chēng)為存在唯一一個(gè)稱(chēng)為根根 的數(shù)據(jù)元素；的數(shù)據(jù)元素； 2) 2) 當(dāng)當(dāng)n n1 1時(shí)，其它數(shù)據(jù)

15、元素可分為時(shí)，其它數(shù)據(jù)元素可分為m(mm(m0) 0) 個(gè)互不相交個(gè)互不相交的有限集的有限集T T1 1,T,T2 2,T,Tm m，其中每個(gè)集合，其中每個(gè)集合T Ti i(i=1,2,(i=1,2,m),m)本本身又是一棵樹(shù)，并稱(chēng)樹(shù)身又是一棵樹(shù)，并稱(chēng)樹(shù) T Ti i是根的是根的子樹(shù)子樹(shù). .2 2、樹(shù)的基本術(shù)語(yǔ)、樹(shù)的基本術(shù)語(yǔ) 1) 1) 樹(shù)的結(jié)點(diǎn)樹(shù)的結(jié)點(diǎn): :包含一個(gè)包含一個(gè)DEDE和指向其子樹(shù)的所有分支和指向其子樹(shù)的所有分支; ; 2) 2) 結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :一個(gè)結(jié)點(diǎn)擁有的子樹(shù)的個(gè)數(shù)一個(gè)結(jié)點(diǎn)擁有的子樹(shù)的個(gè)數(shù), ,度為零的結(jié)點(diǎn)度為零的結(jié)點(diǎn)稱(chēng)為稱(chēng)為葉結(jié)點(diǎn)葉結(jié)點(diǎn); ; 3) 3) 樹(shù)的度樹(shù)

16、的度: :樹(shù)中所有結(jié)點(diǎn)的度的最大值樹(shù)中所有結(jié)點(diǎn)的度的最大值Max(D(I)Max(D(I)含義含義: :樹(shù)中最大分支數(shù)為樹(shù)的度樹(shù)中最大分支數(shù)為樹(shù)的度; ; 4) 4) 結(jié)點(diǎn)的結(jié)點(diǎn)的層次層次及樹(shù)的及樹(shù)的深度深度: :根為第一層根為第一層, ,根的孩子為第二根的孩子為第二層層, ,若某結(jié)點(diǎn)為第若某結(jié)點(diǎn)為第k k層層, ,則其孩子為則其孩子為k+1k+1層層. .樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度或高度深度或高度 5) 5) 森林森林: :是是m(m=0)m(m=0)棵互不相的樹(shù)的集合棵互不相的樹(shù)的集合 森林與樹(shù)概念相近森林與樹(shù)概念相近, ,相互很容易轉(zhuǎn)換相互很容易轉(zhuǎn)換. .

17、樹(shù)的根為樹(shù)的根為? ? 葉子結(jié)點(diǎn)為葉子結(jié)點(diǎn)為? ? 分支結(jié)點(diǎn)為分支結(jié)點(diǎn)為? ? A,B,CA,B,C的度為的度為? ? D,E,F,GD,E,F,G的度為的度為? ? 樹(shù)的度為樹(shù)的度為? ? A A的子節(jié)點(diǎn)包括？的子節(jié)點(diǎn)包括？. E. E的父結(jié)點(diǎn)是的父結(jié)點(diǎn)是 ? ? A A結(jié)點(diǎn)位于第結(jié)點(diǎn)位于第? ?層層 ，F(xiàn) F結(jié)點(diǎn)位于第結(jié)點(diǎn)位于第? ?層層 樹(shù)的深度為樹(shù)的深度為? ?DCGFEBA3 3、二叉樹(shù)概念及性質(zhì)、二叉樹(shù)概念及性質(zhì) 1 1） 二叉樹(shù)概念二叉樹(shù)概念 二叉樹(shù)是二叉樹(shù)是結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為0 0或每個(gè)結(jié)點(diǎn)最多只有左右兩棵子樹(shù)的樹(shù)?；蛎總€(gè)結(jié)點(diǎn)最多只有左右兩棵子樹(shù)的樹(shù)。二叉樹(shù)是一種特殊的樹(shù)，它的特

18、點(diǎn)是：二叉樹(shù)是一種特殊的樹(shù)，它的特點(diǎn)是： 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)，即不存結(jié)點(diǎn)度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)，即不存結(jié)點(diǎn)度大于2 2的結(jié)的結(jié)點(diǎn)；點(diǎn)； 子樹(shù)有左右之分，不能顛倒。子樹(shù)有左右之分，不能顛倒。 2 2） 樹(shù)與二叉樹(shù)的區(qū)別樹(shù)與二叉樹(shù)的區(qū)別 樹(shù)至少應(yīng)該有一個(gè)結(jié)點(diǎn)，二叉樹(shù)可以是空。樹(shù)至少應(yīng)該有一個(gè)結(jié)點(diǎn)，二叉樹(shù)可以是空。二叉樹(shù)要二叉樹(shù)要區(qū)分分左右子樹(shù)區(qū)分分左右子樹(shù)3 3）二叉樹(shù)性質(zhì)）二叉樹(shù)性質(zhì)性質(zhì)性質(zhì)1 1：在二叉樹(shù)的第在二叉樹(shù)的第i i層上至多有層上至多有2 2i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i1)(i1)。性質(zhì)性質(zhì)2 2：深度為：深度為k k的二叉樹(shù)至多有的二叉樹(shù)至多有2 2k k-1-1個(gè)結(jié)

19、點(diǎn)個(gè)結(jié)點(diǎn)(k)(k)。（深度一定，二叉樹(shù)的最大結(jié)點(diǎn)數(shù)也確定）（深度一定，二叉樹(shù)的最大結(jié)點(diǎn)數(shù)也確定）性質(zhì)性質(zhì)3 3：二叉樹(shù)中：二叉樹(shù)中, ,終端結(jié)點(diǎn)（葉節(jié)點(diǎn)）數(shù)終端結(jié)點(diǎn)（葉節(jié)點(diǎn)）數(shù)n n0 0與度為與度為2 2的結(jié)點(diǎn)的結(jié)點(diǎn)數(shù)數(shù)n n2 2有如下關(guān)系有如下關(guān)系: n: n0=0=n n2 2+1+14 4、滿二叉樹(shù)、滿二叉樹(shù) 滿二叉樹(shù)滿二叉樹(shù)：深度為：深度為k k，且有，且有2 2k k-1-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。個(gè)結(jié)點(diǎn)的二叉樹(shù)。 特點(diǎn)：特點(diǎn)：1 1）每一層上結(jié)點(diǎn)數(shù)都達(dá)到最大）每一層上結(jié)點(diǎn)數(shù)都達(dá)到最大2 2）度為）度為1 1的結(jié)點(diǎn)的結(jié)點(diǎn)n n1 1=0=0 結(jié)點(diǎn)層序編號(hào)方法：從根結(jié)點(diǎn)起從上到下逐層（層

20、內(nèi)從左到結(jié)點(diǎn)層序編號(hào)方法：從根結(jié)點(diǎn)起從上到下逐層（層內(nèi)從左到右）對(duì)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。右）對(duì)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。1 12 23 37 76 65 54 4K=3K=3n=2n=23 3-1=7-1=7滿二叉樹(shù)滿二叉樹(shù)5 5、完全二叉樹(shù)、完全二叉樹(shù) 深度為深度為k k，結(jié)點(diǎn)數(shù)為，結(jié)點(diǎn)數(shù)為n n的二叉樹(shù)，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)的二叉樹(shù)，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹(shù)中從都與相同深度的滿二叉樹(shù)中從1 1到到n n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為為完全二叉樹(shù)完全二叉樹(shù)。 滿二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿二滿二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是

21、滿二叉樹(shù)。叉樹(shù)。4521 13 完全二叉樹(shù)完全二叉樹(shù)D DC CG GF FE EB BA A6 6、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 1 1）順序存儲(chǔ)結(jié)構(gòu)）順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹(shù)的數(shù)據(jù)用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹(shù)的數(shù)據(jù)元素，結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。元素，結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。 bt3 bt3的雙親為的雙親為3/23/2=1=1， 即在即在b t1b t1中；中； 其左孩子在其左孩子在bt2i=bt6bt2i=bt6中；中； 其右孩子在其右孩子在bt2i+1=bt7bt2i+1=bt7中。中。1 2 3 4 5

22、 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 0A B C D E F G 0 0 0 0 這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹(shù)，既不浪費(fèi)存儲(chǔ)空間，又能這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹(shù)，既不浪費(fèi)存儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存放位置，但對(duì)一般二叉樹(shù)，可能造成存儲(chǔ)空間的浪費(fèi)。放位置，但對(duì)一般二叉樹(shù)，可能造成存儲(chǔ)空間的浪費(fèi)。D D 二叉樹(shù)二叉樹(shù)C CG GF FE EB BA A1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0

23、0 0 F G 0 0 0 0 一般二叉樹(shù)也按完全二叉樹(shù)形式存儲(chǔ)一般二叉樹(shù)也按完全二叉樹(shù)形式存儲(chǔ), ,沒(méi)結(jié)點(diǎn)處用沒(méi)結(jié)點(diǎn)處用0 0表示。表示。二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) lchild data rchild lchild data rchildD D 二叉樹(shù)二叉樹(shù)C CE EB BA AA AC CB BD DE E二叉鏈表二叉鏈表 2 2） 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。常設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。常用的有：用的有： 二叉鏈表二叉鏈表 3 3）遍歷二叉樹(shù)）遍歷二叉樹(shù) 遍歷二叉樹(shù)是指遍歷二叉樹(shù)是指按一定的規(guī)律按一定的規(guī)律

24、對(duì)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，對(duì)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，訪問(wèn)訪問(wèn)且僅訪問(wèn)一次的處理過(guò)程。且僅訪問(wèn)一次的處理過(guò)程。 一次遍歷后，使樹(shù)中結(jié)點(diǎn)的非線性排列，按訪問(wèn)的先后順一次遍歷后，使樹(shù)中結(jié)點(diǎn)的非線性排列，按訪問(wèn)的先后順序變?yōu)槟撤N線性排列。序變?yōu)槟撤N線性排列。 遍歷的次序遍歷的次序：若設(shè)二叉樹(shù)根為：若設(shè)二叉樹(shù)根為D D，左子樹(shù)為，左子樹(shù)為L(zhǎng) L，右子樹(shù)為，右子樹(shù)為R R，并限定先左后右，則有以下三種遍歷次序：并限定先左后右，則有以下三種遍歷次序：LDR LDR 中序遍歷；中序遍歷；LRD LRD 后序遍歷；后序遍歷；DLR DLR 先序遍歷先序遍歷 （1 1）中序遍歷二叉樹(shù)中序遍歷二叉樹(shù) 算法思想算法思想: : 若

25、二叉樹(shù)非空，則：若二叉樹(shù)非空，則： 1 1）中序遍歷左子樹(shù)）中序遍歷左子樹(shù) 2 2）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) 3 3）中序遍歷右子樹(shù)）中序遍歷右子樹(shù) （2 2）后序遍歷二叉樹(shù)后序遍歷二叉樹(shù) 算法思想算法思想: : 若二叉樹(shù)非空，則：若二叉樹(shù)非空，則： 1 1）后序遍歷左子樹(shù)）后序遍歷左子樹(shù) 2 2）后序遍歷右子樹(shù)）后序遍歷右子樹(shù) 3 3）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) （3 3）先序遍歷二叉樹(shù)先序遍歷二叉樹(shù) 算法思想算法思想: : 若二叉樹(shù)非空，則：若二叉樹(shù)非空，則： 1 1）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) 2)2)先序遍歷左子樹(shù)先序遍歷左子樹(shù) 3 3）先序遍歷右子樹(shù)）先序遍歷右子樹(shù)例：表達(dá)式例：表達(dá)式a+b

26、a+b (c-d)-e/f(c-d)-e/fa ac cd de ef fb b+ +遍歷結(jié)果遍歷結(jié)果: :中序中序: a+b : a+b c c d d e /fe /f后序后序: abcd : abcd +ef / +ef / 先序先序: : +a +a b b cd /efcd /ef1 1、圖的基本概念、圖的基本概念圖定義圖定義：圖是由頂點(diǎn)集合：圖是由頂點(diǎn)集合(vertex)(vertex)及頂點(diǎn)間的關(guān)系集合組及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：成的一種數(shù)據(jù)結(jié)構(gòu)： GraphGraph( V, E )( V, E ) 其中其中 V = x | x V = x | x 某個(gè)數(shù)據(jù)對(duì)象某個(gè)

27、數(shù)據(jù)對(duì)象 是頂點(diǎn)的有窮非空集合；是頂點(diǎn)的有窮非空集合； E1 = (x, y) | x, y E1 = (x, y) | x, y V V 或或 E2 = | x, y E2 = | x, y V & Path (x, y) V & Path (x, y) 其中，其中， E1E1是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)(edge)集合，此時(shí)的圖稱(chēng)為無(wú)向圖。集合，此時(shí)的圖稱(chēng)為無(wú)向圖。 E2 E2 表示從表示從 x x 到到 y y 的一條的一條弧，且稱(chēng)弧，且稱(chēng)x x為弧尾，為弧尾，y y為弧頭，這樣的圖稱(chēng)為有向圖。為弧頭，這樣的圖稱(chēng)為有向圖

28、。13.5 13.5 圖圖n有向圖與無(wú)向圖有向圖與無(wú)向圖在有向圖中，頂點(diǎn)對(duì)在有向圖中，頂點(diǎn)對(duì) 是有序的。是有序的。在無(wú)向圖中，頂點(diǎn)對(duì)在無(wú)向圖中，頂點(diǎn)對(duì)(x, y)(x, y)是無(wú)序的。是無(wú)序的。n完全圖完全圖若有若有 n n 個(gè)頂點(diǎn)的無(wú)向圖有個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2n(n-1)/2 條邊條邊, , 則則此圖為此圖為無(wú)向完全圖無(wú)向完全圖。有。有 n n 個(gè)頂點(diǎn)的有向圖有個(gè)頂點(diǎn)的有向圖有n(n-1)n(n-1) 條邊條邊, , 則此圖為則此圖為有向完全圖有向完全圖。01201201265430123n鄰接頂點(diǎn)鄰接頂點(diǎn)如果如果 (u, v) (u, v) 是是 E(G) E(G) 中的一條

29、邊，則稱(chēng)中的一條邊，則稱(chēng) u u 與與 v v 互為鄰接頂點(diǎn)?；猷徑禹旤c(diǎn)。n子圖：子圖：設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖 G G(V, E) (V, E) 和和 GG(V, E)(V, E)。若。若 VV V V 且且 EE E, E, 則稱(chēng)則稱(chēng) 圖圖G G 是是 圖圖G G 的子圖。的子圖。n權(quán)：權(quán)：某些圖的邊具有與它相關(guān)的數(shù)某些圖的邊具有與它相關(guān)的數(shù), , 稱(chēng)之為權(quán)。這種帶稱(chēng)之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。權(quán)圖叫做網(wǎng)絡(luò)。0 01 12 23 3子圖子圖0 01 13 30 01 12 23 30 02 23 3n頂點(diǎn)的度頂點(diǎn)的度一個(gè)頂點(diǎn)一個(gè)頂點(diǎn)v v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作的度是與它相關(guān)聯(lián)的邊的

30、條數(shù)。記作TD(v)TD(v)。在有向圖中。在有向圖中, , 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。和。n頂點(diǎn)頂點(diǎn) v v 的入度：的入度：是以是以 v v 為終點(diǎn)的有向邊的條數(shù)為終點(diǎn)的有向邊的條數(shù), , 記作記作 ID(v); ID(v); 頂點(diǎn)頂點(diǎn) v v 的出度：的出度：是以是以 v v 為始點(diǎn)的有向邊的條數(shù)為始點(diǎn)的有向邊的條數(shù), , 記作記作 OD(v)OD(v)。n路徑：路徑：在圖在圖 G G(V, E) (V, E) 中中, , 若從頂點(diǎn)若從頂點(diǎn) vi vi 出發(fā)出發(fā), , 沿一些邊沿一些邊經(jīng)過(guò)一些頂點(diǎn)經(jīng)過(guò)一些頂點(diǎn) vp1, vp2, vp1, vp2

31、, , vpm, vpm，到達(dá)頂點(diǎn)，到達(dá)頂點(diǎn)vjvj。則稱(chēng)頂點(diǎn)。則稱(chēng)頂點(diǎn)序列序列 ( (vi vp1 vp2 . vpm vjvi vp1 vp2 . vpm vj) ) 為從頂點(diǎn)為從頂點(diǎn)vivi 到頂點(diǎn)到頂點(diǎn) vjvj 的路徑。它經(jīng)過(guò)的邊的路徑。它經(jīng)過(guò)的邊( (vi, vp1vi, vp1) )、( (vp1, vp2vp1, vp2) )、.、( (vpm, vpm, vjvj) ) 應(yīng)是屬于應(yīng)是屬于E E的邊。的邊。頂點(diǎn)的出度頂點(diǎn)的出度: : 以頂點(diǎn)以頂點(diǎn)v v 為弧尾的為弧尾的弧的數(shù)目弧的數(shù)目; ;頂點(diǎn)的入度頂點(diǎn)的入度: : 以頂點(diǎn)以頂點(diǎn)v v為弧頭的為弧頭的弧的數(shù)目?；〉臄?shù)目。A A

32、B BE EC CF F有向圖：有向圖：例如例如: :頂點(diǎn)的度頂點(diǎn)的度(TD)=(TD)=出度出度(OD)+(OD)+入度入度(ID)(ID)TD(B) =OD(B)+2ID(B) = 3TD(B) =OD(B)+2ID(B) = 3n路徑長(zhǎng)度路徑長(zhǎng)度非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。n如如: :從從A A到到F F長(zhǎng)度為長(zhǎng)度為 3 3 的路徑的路徑A,B,C,FA,B,C,FABECF2 2、圖的存儲(chǔ)結(jié)構(gòu)、圖的存儲(chǔ)結(jié)構(gòu)n鄰接矩陣鄰接矩陣 (Adjacency Matr

33、ix)(Adjacency Matrix)n在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。n設(shè)圖設(shè)圖 A = (V, E)A = (V, E)是一個(gè)有是一個(gè)有 n n 個(gè)頂點(diǎn)的圖個(gè)頂點(diǎn)的圖, , 圖的鄰接矩陣圖的鄰接矩陣是一個(gè)二維數(shù)組是一個(gè)二維數(shù)組 A.edgennA.edgenn，定義：，定義：=, ),( , , .否則否則 或或若若01AEjiEjijiEdgen無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的;n有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。有

34、向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。n在有向圖中在有向圖中, , 統(tǒng)計(jì)第統(tǒng)計(jì)第 i i 行行 1 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn) i i 的出度，的出度，統(tǒng)計(jì)第統(tǒng)計(jì)第 j j 列列 1 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn) j j 的入度。的入度。n在無(wú)向圖中在無(wú)向圖中, , 統(tǒng)計(jì)第統(tǒng)計(jì)第 i i 行行 ( (列列) 1 ) 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn)i i 的度。的度。0123012=000101010A.edge=0101101001011010A.edge 無(wú)向圖的鄰接表無(wú)向圖的鄰接表 同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)

35、代表一條邊代表一條邊( (邊結(jié)點(diǎn)邊結(jié)點(diǎn)), ), 結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo) destdest 和指和指針針 linklink。ABCDdata adjABCD0123dest linkdest link 130210有向圖的鄰接表和逆鄰接表有向圖的鄰接表和逆鄰接表ABC鄰接表鄰接表 (出邊表出邊表)逆鄰接表逆鄰接表 (入邊表入邊表)data adjA012dest linkdest link 102 BCdata adj012dest link 011ABC13.6 13.6 查找查找 關(guān)鍵字關(guān)鍵字： 是指數(shù)據(jù)元素中能夠唯一表示一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。是指數(shù)據(jù)元素中能夠唯一表

36、示一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。如學(xué)生的學(xué)號(hào)、居民的身份證號(hào)碼等。如學(xué)生的學(xué)號(hào)、居民的身份證號(hào)碼等。 查找表查找表：一組待查數(shù)據(jù)元素的集合。：一組待查數(shù)據(jù)元素的集合。1 1、順序查找、順序查找從查找表中第一個(gè)數(shù)據(jù)元素開(kāi)始，從查找表中第一個(gè)數(shù)據(jù)元素開(kāi)始，逐個(gè)把數(shù)據(jù)元素的關(guān)逐個(gè)把數(shù)據(jù)元素的關(guān)鍵字值與給定值比較鍵字值與給定值比較，若某個(gè)元素的關(guān)鍵字的值與給定，若某個(gè)元素的關(guān)鍵字的值與給定值相等，則查找成功，否則查找失敗。值相等，則查找成功，否則查找失敗。適合：順序存儲(chǔ)的查找表，鏈?zhǔn)酱鎯?chǔ)的查找表適合：順序存儲(chǔ)的查找表，鏈?zhǔn)酱鎯?chǔ)的查找表查找過(guò)程查找過(guò)程: : 算法分析算法分析: : 2 2、 二分查找二分查找有

37、序表有序表 : : 查找表中記錄按關(guān)鍵字有序排列的表查找表中記錄按關(guān)鍵字有序排列的表. .即即: ri.key=ri+1.key i=1,2,: ri.key21,21,則說(shuō)明，待查元素若存在，必在則說(shuō)明，待查元素若存在，必在low,mid-1low,mid-1區(qū)間中，則在該區(qū)間中進(jìn)行二分查找區(qū)間中，則在該區(qū)間中進(jìn)行二分查找: :令令highig=mid-1, =mid-1, 重新計(jì)算重新計(jì)算midmid。 若若smid.keysmid.key21,21 s5.key=5621 則則highig=mid-1=4,mid=(0+4)/2=2=mid-1=4,mid=(0+4)/2=2s2.key

38、=1921 s2.key=1921 則則low=mid+1=3,mid=(3+4)/2=3low=mid+1=3,mid=(3+4)/2=3s3.key=21=21s3.key=21=21, ,查找成功查找成功3 3、索引順序表的查找、索引順序表的查找( (分塊查找分塊查找) )1) 1) 將所有數(shù)據(jù)元素分成若干塊，塊內(nèi)的元素按照關(guān)鍵字是將所有數(shù)據(jù)元素分成若干塊，塊內(nèi)的元素按照關(guān)鍵字是無(wú)序的，但無(wú)序的，但塊與塊之間是按照關(guān)鍵字有序塊與塊之間是按照關(guān)鍵字有序的，即第一塊中的，即第一塊中的所有元素大于（或者小于）第二塊中的所有元素，依次的所有元素大于（或者小于）第二塊中的所有元素，依次類(lèi)推。類(lèi)推。

39、2) 2) 對(duì)每塊建立一個(gè)索引項(xiàng)對(duì)每塊建立一個(gè)索引項(xiàng), , 包含以?xún)身?xiàng)內(nèi)容包含以?xún)身?xiàng)內(nèi)容: : 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng) : : 為該塊中最大關(guān)鍵字值為該塊中最大關(guān)鍵字值; ; 指針項(xiàng)指針項(xiàng) : : 為該塊第一個(gè)記錄在表中位置為該塊第一個(gè)記錄在表中位置. .3) 3) 所有索引項(xiàng)組成索引表所有索引項(xiàng)組成索引表例例: :查找表為查找表為: :22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53索引表為索引表為: :關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng)指針項(xiàng)指針項(xiàng)分塊查找表的平均查找長(zhǎng)度分塊查找表的平均查找長(zhǎng)度ASL=LASL=Lb b+L+

40、Lw w其中其中: : L Lb b為查索引表確定所在塊的平均查找長(zhǎng)度為查索引表確定所在塊的平均查找長(zhǎng)度; ; L Lw w為在塊內(nèi)查找記錄的平均查找長(zhǎng)度為在塊內(nèi)查找記錄的平均查找長(zhǎng)度; ;三種查找方法比較三種查找方法比較順序查找順序查找折半查找折半查找分塊查找分塊查找ASLASL大大小小 中中表結(jié)構(gòu)要求表結(jié)構(gòu)要求無(wú)無(wú)有序表有序表 分段有序分段有序（塊之間有序）（塊之間有序）3 3、簡(jiǎn)單插入排序、簡(jiǎn)單插入排序 ( (最簡(jiǎn)單的排序方法）最簡(jiǎn)單的排序方法） 基本思想基本思想：依次將每個(gè)待排序的記錄插入到一個(gè)有序子文件：依次將每個(gè)待排序的記錄插入到一個(gè)有序子文件的合適位置的合適位置( (有序子文件記

41、錄數(shù)增有序子文件記錄數(shù)增1)1) 例如：已有待排序文件為：例如：已有待排序文件為：3838，6565，4949，7676，9797 首先將文件的第一個(gè)記錄，視為有序文件，然后從第二個(gè)記首先將文件的第一個(gè)記錄，視為有序文件，然后從第二個(gè)記錄開(kāi)始，直到最后一個(gè)記錄，依次將他們插入到有序文件的錄開(kāi)始，直到最后一個(gè)記錄，依次將他們插入到有序文件的合適位置。合適位置。 1 1）直接插入排序的效率與待排文件的關(guān)鍵字排列有關(guān)；）直接插入排序的效率與待排文件的關(guān)鍵字排列有關(guān)； 2 2）直接插入排序的時(shí)間復(fù)雜度為）直接插入排序的時(shí)間復(fù)雜度為O(n2)O(n2)； 3 3）直接插入排序是穩(wěn)定的）直接插入排序是穩(wěn)定

42、的( (這一點(diǎn)由過(guò)程中這一點(diǎn)由過(guò)程中WHILEWHILE語(yǔ)句的條語(yǔ)句的條件件“”保證的保證的) )。 4 4、快速排序、快速排序 快速排序是目前內(nèi)部排序中最快的方法?？焖倥判蚴悄壳皟?nèi)部排序中最快的方法。 1 1）基本思想基本思想：選取某個(gè)記錄：選取某個(gè)記錄( (通常選文件的第一個(gè)記錄通常選文件的第一個(gè)記錄) )，將所有關(guān)鍵字不大于它的記錄放在它的前面，將所有關(guān)鍵將所有關(guān)鍵字不大于它的記錄放在它的前面，將所有關(guān)鍵字不小于它的記錄放在它的后面，這樣遍歷一趟文件后，字不小于它的記錄放在它的后面，這樣遍歷一趟文件后，將文件以該記錄為界分為兩部分，然后對(duì)各部分重復(fù)上述將文件以該記錄為界分為兩部分，然后對(duì)

43、各部分重復(fù)上述過(guò)程，直到每一部分僅剩一個(gè)記錄為止。過(guò)程，直到每一部分僅剩一個(gè)記錄為止。2 2）具體步驟）具體步驟(1) (1) 置變量置變量i i，j j初值分別為文件的首、尾記錄位置；選取文件初值分別為文件的首、尾記錄位置；選取文件首記錄首記錄riri，并將其關(guān)鍵字賦給變量，并將其關(guān)鍵字賦給變量x x； (2) (2) 從從j j 位置開(kāi)始向前搜索，位置開(kāi)始向前搜索，(3) (3) 直到遇到第一個(gè)關(guān)鍵字小于直到遇到第一個(gè)關(guān)鍵字小于x x的記錄，的記錄，(4) (4) 并將并將rjrj移至移至riri；(5) (5) 從從i i 位置開(kāi)始向后搜索，位置開(kāi)始向后搜索，(6) (6) 直到遇到第一

44、個(gè)關(guān)鍵字大于直到遇到第一個(gè)關(guān)鍵字大于x x的記錄，的記錄，(7) (7) 并將并將riri移至移至rjrj；(8) (8) 重復(fù)重復(fù)(2)(2)(9) (9) 直到直到i=ji=j，(10) (10) 并將并將x x移至移至riri，以，以riri為中樞將文件分為為中樞將文件分為r1.i-1r1.i-1和和ri+1.nri+1.n兩部分，完成一趟排序；兩部分，完成一趟排序；(11) (11) 重復(fù)重復(fù)(1)(1)至至(10)(10)，直到每一部分只剩上一個(gè)記錄，整個(gè)文，直到每一部分只剩上一個(gè)記錄，整個(gè)文件已有序，快速排序算法結(jié)束。件已有序，快速排序算法結(jié)束。 例如：例如： x初始關(guān)鍵字初始關(guān)鍵

45、字 49 38 65 97 76 13 27 49 i j 27 i 65 13 i 97完成一趟排序完成一趟排序 （27 38 13） 49 （76 97 65 49) （13）27 （38） （49 65）76 (97) 結(jié)束結(jié)束 結(jié)束結(jié)束 49 (65) 結(jié)束結(jié)束 結(jié)束結(jié)束最后最后 （13 27 38 49 49 65 79 97）5 5、簡(jiǎn)單選擇排序、簡(jiǎn)單選擇排序1 1）基本思想基本思想：對(duì)文件進(jìn)行：對(duì)文件進(jìn)行n-1n-1趟排序，第趟排序，第i i趟趟(i=1,2,.n-(i=1,2,.n-1)1)是在從是在從i i到到 n n的的n-i+1n-i+1個(gè)記錄中選擇關(guān)鍵字最小的記錄，并個(gè)

46、記錄中選擇關(guān)鍵字最小的記錄，并將它與第將它與第i i個(gè)記錄進(jìn)行交換。個(gè)記錄進(jìn)行交換。算法分析算法分析 交換次數(shù)：正序時(shí)交換次數(shù)最少，為交換次數(shù)：正序時(shí)交換次數(shù)最少，為0 0次，次， 逆序時(shí)最多，為逆序時(shí)最多，為n-1n-1次。次。 比較次數(shù)：與初始文件關(guān)鍵字排列無(wú)關(guān)，比較次數(shù)：與初始文件關(guān)鍵字排列無(wú)關(guān)， 為為n(n-1)/2n(n-1)/2次。次。 簡(jiǎn)單選擇排序時(shí)間復(fù)雜度為簡(jiǎn)單選擇排序時(shí)間復(fù)雜度為O(nO(n2 2) )，并且是不穩(wěn)定的排，并且是不穩(wěn)定的排序序。6 6、歸并排序、歸并排序 歸并概念：把歸并概念：把 2 2 個(gè)有序子文件合并成一個(gè)有序文件的過(guò)程個(gè)有序子文件合并成一個(gè)有序文件的過(guò)程

47、，稱(chēng)為，稱(chēng)為2-2-路歸并。路歸并。 歸并排序基本思想：歸并排序基本思想：將文件的每個(gè)記錄視為一個(gè)有序子文將文件的每個(gè)記錄視為一個(gè)有序子文件；件；然后兩兩子文件進(jìn)行然后兩兩子文件進(jìn)行2-2-路歸并；路歸并；重復(fù)重復(fù)，直到只剩，直到只剩一個(gè)長(zhǎng)度為一個(gè)長(zhǎng)度為n n的有序文件的有序文件 例：初始關(guān)鍵字：例：初始關(guān)鍵字：49 3849 38 65 97 65 97 76 1376 13 27 49 27 49 第一趟后第一趟后 38 49 65 9738 49 65 97 13 76 27 49 13 76 27 49第二趟后第二趟后 38 49 65 97 13 27 49 7638 49 65 9

48、7 13 27 49 76第三趟后第三趟后 13 27 38 49 4913 27 38 49 49 65 76 97 65 76 97 每個(gè)記錄視為一個(gè)有序子文件，兩個(gè)子文件進(jìn)行歸并，得每個(gè)記錄視為一個(gè)有序子文件，兩個(gè)子文件進(jìn)行歸并，得4 4個(gè)有序子文件。個(gè)有序子文件。 13.7 13.7 軟件工程軟件工程 1 1、軟件生存周期、軟件生存周期 軟件產(chǎn)品從形成概念開(kāi)始，經(jīng)過(guò)開(kāi)發(fā)、使用和維護(hù)，直到最軟件產(chǎn)品從形成概念開(kāi)始，經(jīng)過(guò)開(kāi)發(fā)、使用和維護(hù)，直到最后退役的全過(guò)程。后退役的全過(guò)程。Software life cycle. Software life cycle. 根據(jù)軟件狀態(tài)、根據(jù)軟件狀態(tài)、特征

49、、開(kāi)發(fā)活動(dòng)的目的，可以分為不同階段，各階段劃分尚特征、開(kāi)發(fā)活動(dòng)的目的，可以分為不同階段，各階段劃分尚未統(tǒng)一，但都包括：軟件定義、軟件開(kāi)發(fā)、軟件使用和維護(hù)未統(tǒng)一，但都包括：軟件定義、軟件開(kāi)發(fā)、軟件使用和維護(hù)三部分。下面分為十個(gè)階段進(jìn)行介紹。三部分。下面分為十個(gè)階段進(jìn)行介紹。2 2、軟件生存周期模型（軟件開(kāi)發(fā)模型）、軟件生存周期模型（軟件開(kāi)發(fā)模型） 軟件軟件生存周期生存周期模型是描述軟件開(kāi)發(fā)過(guò)程中各種活動(dòng)如何執(zhí)模型是描述軟件開(kāi)發(fā)過(guò)程中各種活動(dòng)如何執(zhí)行的模型。行的模型。 軟件生存周期模型確立了軟件開(kāi)發(fā)和演繹中各階段的次序軟件生存周期模型確立了軟件開(kāi)發(fā)和演繹中各階段的次序限制以及各階段活動(dòng)的總則，確立

50、開(kāi)發(fā)過(guò)程所遵守的規(guī)定限制以及各階段活動(dòng)的總則，確立開(kāi)發(fā)過(guò)程所遵守的規(guī)定和限制，便于各種活動(dòng)的協(xié)調(diào)以及各人員的有效通信，有和限制，便于各種活動(dòng)的協(xié)調(diào)以及各人員的有效通信，有利于活動(dòng)重用和活動(dòng)管理。利于活動(dòng)重用和活動(dòng)管理。 目前有若干種軟件生存周期模型：瀑布模型、增量模型、目前有若干種軟件生存周期模型：瀑布模型、增量模型、螺旋模型、噴泉模型、變換模型、基于知識(shí)的模型等。螺旋模型、噴泉模型、變換模型、基于知識(shí)的模型等。 1 1）瀑布模型）瀑布模型 瀑布模型瀑布模型是將軟件生存周期各活動(dòng)規(guī)定為依線性順序聯(lián)接的是將軟件生存周期各活動(dòng)規(guī)定為依線性順序聯(lián)接的若干階段的模型。包括可行性分析、項(xiàng)目開(kāi)發(fā)計(jì)劃、需求

51、分若干階段的模型。包括可行性分析、項(xiàng)目開(kāi)發(fā)計(jì)劃、需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測(cè)試和維護(hù)。它規(guī)定了由析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測(cè)試和維護(hù)。它規(guī)定了由前至后、相互銜接的固定次序，如同瀑布流水，逐級(jí)下落。前至后、相互銜接的固定次序，如同瀑布流水，逐級(jí)下落。特點(diǎn)：特點(diǎn)： 上一階段的變換結(jié)果上一階段的變換結(jié)果 是下一階段的變換的是下一階段的變換的 輸入，相鄰兩個(gè)階段輸入，相鄰兩個(gè)階段 具有因果關(guān)系，緊密具有因果關(guān)系，緊密 相聯(lián)。相聯(lián)。需求分析需求分析問(wèn)題定義問(wèn)題定義可性行研究可性行研究計(jì)劃計(jì)劃時(shí)期時(shí)期概要設(shè)計(jì)概要設(shè)計(jì)詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)編編 碼碼 測(cè)測(cè) 試試開(kāi)發(fā)開(kāi)發(fā)時(shí)期時(shí)期運(yùn)行與維護(hù)運(yùn)行與維護(hù)運(yùn)

52、運(yùn) 行行時(shí)時(shí) 期期軟件生存周期模型（瀑布模型軟件生存周期模型（瀑布模型 Waterfall ModelWaterfall Model） 13.8 13.8 軟件測(cè)試軟件測(cè)試 1 1）軟件測(cè)試軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程?；蛘哒f(shuō)，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。或者說(shuō)，軟件測(cè)試是根據(jù)軟件開(kāi)發(fā)各階段的規(guī)格說(shuō)明和程序內(nèi)部結(jié)構(gòu)軟件測(cè)試是根據(jù)軟件開(kāi)發(fā)各階段的規(guī)格說(shuō)明和程序內(nèi)部結(jié)構(gòu)而精心設(shè)計(jì)的測(cè)試用例（即輸入數(shù)據(jù)及預(yù)期的輸出結(jié)果），而精心設(shè)計(jì)的測(cè)試用例（即輸入數(shù)據(jù)及預(yù)期的輸出結(jié)果），并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程. . 需求分

53、析需求分析 設(shè)設(shè) 計(jì)計(jì) 編編 碼碼 單元測(cè)試單元測(cè)試 集成測(cè)試集成測(cè)試 確認(rèn)測(cè)試確認(rèn)測(cè)試 1 1、軟件測(cè)試設(shè)計(jì)的方法、軟件測(cè)試設(shè)計(jì)的方法 測(cè)試技術(shù)測(cè)試技術(shù)1 1、白盒測(cè)試白盒測(cè)試(White Box Testing)(White Box Testing)2 2、黑盒測(cè)試黑盒測(cè)試(Black Box Testing)(Black Box Testing) 軟件的測(cè)試設(shè)計(jì)與軟件產(chǎn)品的設(shè)計(jì)一樣，是一項(xiàng)需要花費(fèi)軟件的測(cè)試設(shè)計(jì)與軟件產(chǎn)品的設(shè)計(jì)一樣，是一項(xiàng)需要花費(fèi)許多人力和時(shí)間的工作，我們希望以最少量的時(shí)間和許多人力和時(shí)間的工作，我們希望以最少量的時(shí)間和 人力人力，最大可能地發(fā)現(xiàn)最多的錯(cuò)誤，最大可能地發(fā)現(xiàn)

54、最多的錯(cuò)誤. . 1 1）白盒測(cè)試）白盒測(cè)試(White Box Testing)(White Box Testing) 也叫玻璃盒測(cè)試也叫玻璃盒測(cè)試(Glass Box Testing)(Glass Box Testing)。 對(duì)軟件的過(guò)程性細(xì)節(jié)做細(xì)致的檢查。這一方法是把測(cè)試對(duì)對(duì)軟件的過(guò)程性細(xì)節(jié)做細(xì)致的檢查。這一方法是把測(cè)試對(duì)象看作一個(gè)打開(kāi)的盒子，它允許測(cè)試人員利用程序內(nèi)部的象看作一個(gè)打開(kāi)的盒子，它允許測(cè)試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息，來(lái)設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序所邏輯結(jié)構(gòu)及有關(guān)信息，來(lái)設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序所有邏輯路徑進(jìn)行測(cè)試。有邏輯路徑進(jìn)行測(cè)試。白盒測(cè)試白盒測(cè)試的內(nèi)容的內(nèi)容對(duì)

55、程序模塊的所有對(duì)程序模塊的所有獨(dú)立獨(dú)立執(zhí)行路徑執(zhí)行路徑至少測(cè)試一次至少測(cè)試一次對(duì)所有的對(duì)所有的邏輯判定邏輯判定，取，取“真真”與取與取“假假”的兩種情況的兩種情況都能至少測(cè)試一次。都能至少測(cè)試一次。 在循環(huán)的邊界和運(yùn)行邊在循環(huán)的邊界和運(yùn)行邊界限內(nèi)執(zhí)行循環(huán)體界限內(nèi)執(zhí)行循環(huán)體 測(cè)試內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有測(cè)試內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。效性。 2 2）黑盒測(cè)試）黑盒測(cè)試(Black Box Testing)(Black Box Testing) 已知產(chǎn)品的功能設(shè)計(jì)規(guī)格，可以進(jìn)行測(cè)試證明每個(gè)實(shí)現(xiàn)了已知產(chǎn)品的功能設(shè)計(jì)規(guī)格，可以進(jìn)行測(cè)試證明每個(gè)實(shí)現(xiàn)了的功能是否符合要求。的功能是否符合要求。 13.8 13.8 操作系

56、統(tǒng)操作系統(tǒng)1 1、操作系統(tǒng)的目標(biāo)、操作系統(tǒng)的目標(biāo) 目前存在著多種類(lèi)型的目前存在著多種類(lèi)型的OSOS，不同類(lèi)型的，不同類(lèi)型的OSOS，其目標(biāo)各有所，其目標(biāo)各有所側(cè)重。通常在計(jì)算機(jī)硬件上配置的側(cè)重。通常在計(jì)算機(jī)硬件上配置的OSOS，其目標(biāo)有以下幾點(diǎn)：，其目標(biāo)有以下幾點(diǎn)： 1 1）方便性）方便性 2 2）有效性）有效性 3 3）可擴(kuò)充性）可擴(kuò)充性 4 4）開(kāi)放性）開(kāi)放性 2 2、操作系統(tǒng)的作用、操作系統(tǒng)的作用 OSOS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口 OSOS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過(guò)處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過(guò)OSOS來(lái)使用計(jì)算來(lái)使用計(jì)算機(jī)

57、系統(tǒng)?；蛘哒f(shuō)，用戶在機(jī)系統(tǒng)。或者說(shuō)，用戶在OSOS幫助下，能夠方便、快捷、安全、幫助下，能夠方便、快捷、安全、可靠地操縱計(jì)算機(jī)硬件和運(yùn)行自己的程序。應(yīng)注意，可靠地操縱計(jì)算機(jī)硬件和運(yùn)行自己的程序。應(yīng)注意，OSOS是一是一個(gè)系統(tǒng)軟件，因而這種接口是個(gè)系統(tǒng)軟件，因而這種接口是軟件接口。軟件接口。 3 3、操作系統(tǒng)的基本特性、操作系統(tǒng)的基本特性 1 1）并發(fā)并發(fā)(Concurrence)(Concurrence) 并行性和并發(fā)性是既相似又有區(qū)別的兩個(gè)概念，并行性是并行性和并發(fā)性是既相似又有區(qū)別的兩個(gè)概念，并行性是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生；而并發(fā)性是指兩個(gè)或指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生；而并發(fā)性是指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。 2 2）共享共享(Sharing)(Sharing) 在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程中多個(gè)