軟件技術(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ù)、字母、程序、圖形、語言等。包括：常數(shù)、字母、程序、圖形、語言等。 數(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，并稱，并稱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é)生稱為數(shù)據(jù)元

2、素。則班級(jí)中的每一個(gè)學(xué)生稱為數(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è)開始和結(jié)束數(shù)據(jù)元素，每個(gè)數(shù)據(jù)元素最多僅有一個(gè)開始和結(jié)束數(shù)據(jù)元素，每個(gè)數(shù)據(jù)元素最多只有一個(gè)直接前驅(qū)和直接后繼。（數(shù)組）只有一個(gè)直接前驅(qū)和直接后繼。（數(shù)組）非線性結(jié)構(gòu)：非線性結(jié)構(gòu)： 數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和直接后繼（樹、

3、圖）數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和直接后繼（樹、圖）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。 稱稱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)稱為線性表的稱為線性表的長度長度; ; 當(dāng)當(dāng)n=0n=0時(shí)，稱為時(shí)，稱為空表空表。2 2、基本運(yùn)算、基本運(yùn)算INITIATEINITIATE（L L） 初始化操作初始化操作 設(shè)定一個(gè)空的線性表設(shè)定一個(gè)空的線性表L LLENGTHLENGTH（L L） 求長度函數(shù)求長度函數(shù) 值為值為L 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稱為該數(shù)據(jù)元素在稱為該數(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為表長為表長 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è)位置處插入新元素； 將表的長度加將表的長度加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)算可以由定位和修改指針來完成：刪除

10、運(yùn)算可以由定位和修改指針來完成： 定位：得到指向定位：得到指向第第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)，稱這樣的鏈表為循環(huán)鏈表。表形成一個(gè)環(huán)，稱這樣的鏈表為循環(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)行插入或刪除操作的線性表。允許插入和刪除的一端允許插入和刪除的一端稱為棧頂稱為棧頂(top)(top)，另一端，另一端稱為棧底稱為棧底(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 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、端稱為對(duì)頭允許刪除的一端稱為對(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í)無隊(duì)滿問題，但有隊(duì)空問題。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。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 樹和二叉樹樹和二叉樹1 1、樹的定義、樹的定義 樹樹是是n n個(gè)數(shù)據(jù)元素的有限集個(gè)數(shù)據(jù)元素的有限集( (記為記為T)T)，對(duì)任意一棵樹，對(duì)任意一棵樹T T有：有： 1) 1) 存在唯一一個(gè)稱為存在唯一一個(gè)稱為根根 的數(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)本本身又是一棵樹，并稱樹身又是一棵樹，并稱樹 T Ti i是根的是根的子樹子樹. .2 2、樹的基本術(shù)語、樹的基本術(shù)語 1) 1) 樹的結(jié)點(diǎn)樹的結(jié)點(diǎn): :包含一個(gè)包含一個(gè)DEDE和指向其子樹的所有分支和指向其子樹的所有分支; ; 2) 2) 結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :一個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)一個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù), ,度為零的結(jié)點(diǎn)度為零的結(jié)點(diǎn)稱為稱為葉結(jié)點(diǎn)葉結(jié)點(diǎn); ; 3) 3) 樹的度樹

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

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

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

19、點(diǎn)個(gè)結(jié)點(diǎn)(k)(k)。（深度一定，二叉樹的最大結(jié)點(diǎn)數(shù)也確定）（深度一定，二叉樹的最大結(jié)點(diǎn)數(shù)也確定）性質(zhì)性質(zhì)3 3：二叉樹中：二叉樹中, ,終端結(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、滿二叉樹、滿二叉樹 滿二叉樹滿二叉樹：深度為：深度為k k，且有，且有2 2k k-1-1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。 特點(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ì)二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。右）對(duì)二叉樹的結(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滿二叉樹滿二叉樹5 5、完全二叉樹、完全二叉樹 深度為深度為k k，結(jié)點(diǎn)數(shù)為，結(jié)點(diǎn)數(shù)為n n的二叉樹，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)的二叉樹，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹中從都與相同深度的滿二叉樹中從1 1到到n n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為為完全二叉樹完全二叉樹。 滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是

21、滿二叉樹。叉樹。4521 13 完全二叉樹完全二叉樹D DC CG GF FE EB BA A6 6、二叉樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的存儲(chǔ)結(jié)構(gòu) 1 1）順序存儲(chǔ)結(jié)構(gòu)）順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹的數(shù)據(jù)用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹的數(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)適合于完全二叉樹，既不浪費(fèi)存儲(chǔ)空間，又能這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹，既不浪費(fèi)存儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存放位置，但對(duì)一般二叉樹，可能造成存儲(chǔ)空間的浪費(fèi)。放位置，但對(duì)一般二叉樹，可能造成存儲(chǔ)空間的浪費(fèi)。D D 二叉樹二叉樹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 一般二叉樹也按完全二叉樹形式存儲(chǔ)一般二叉樹也按完全二叉樹形式存儲(chǔ), ,沒結(jié)點(diǎn)處用沒結(jié)點(diǎn)處用0 0表示。表示。二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) lchild data rchild lchild data rchildD D 二叉樹二叉樹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）遍歷二叉樹）遍歷二叉樹 遍歷二叉樹是指遍歷二叉樹是指按一定的規(guī)律按一定的規(guī)律

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

25、二叉樹非空，則：若二叉樹非空，則： 1 1）中序遍歷左子樹）中序遍歷左子樹 2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) 3 3）中序遍歷右子樹）中序遍歷右子樹 （2 2）后序遍歷二叉樹后序遍歷二叉樹 算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則： 1 1）后序遍歷左子樹）后序遍歷左子樹 2 2）后序遍歷右子樹）后序遍歷右子樹 3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) （3 3）先序遍歷二叉樹先序遍歷二叉樹 算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則： 1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) 2)2)先序遍歷左子樹先序遍歷左子樹 3 3）先序遍歷右子樹）先序遍歷右子樹例：表達(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í)的圖稱為無向圖。集合，此時(shí)的圖稱為無向圖。 E2 E2 表示從表示從 x x 到到 y y 的一條的一條弧，且稱弧，且稱x x為弧尾，為弧尾，y y為弧頭，這樣的圖稱為有向圖。為弧頭，這樣的圖稱為有向圖

28、。13.5 13.5 圖圖n有向圖與無向圖有向圖與無向圖在有向圖中，頂點(diǎn)對(duì)在有向圖中，頂點(diǎn)對(duì) 是有序的。是有序的。在無向圖中，頂點(diǎn)對(duì)在無向圖中，頂點(diǎn)對(duì)(x, y)(x, y)是無序的。是無序的。n完全圖完全圖若有若有 n n 個(gè)頂點(diǎn)的無向圖有個(gè)頂點(diǎn)的無向圖有 n(n-1)/2n(n-1)/2 條邊條邊, , 則則此圖為此圖為無向完全圖無向完全圖。有。有 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、邊，則稱中的一條邊，則稱 u u 與與 v v 互為鄰接頂點(diǎn)。互為鄰接頂點(diǎn)。n子圖：子圖：設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖 G G(V, E) (V, E) 和和 GG(V, E)(V, E)。若。若 VV V V 且且 EE E, E, 則稱則稱 圖圖G G 是是 圖圖G G 的子圖。的子圖。n權(quán)：權(quán)：某些圖的邊具有與它相關(guān)的數(shù)某些圖的邊具有與它相關(guān)的數(shù), , 稱之為權(quán)。這種帶稱之為權(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)過一些頂點(diǎn)經(jīng)過一些頂點(diǎn) vp1, vp2, vp1, vp2

31、, , vpm, vpm，到達(dá)頂點(diǎn)，到達(dá)頂點(diǎn)vjvj。則稱頂點(diǎn)。則稱頂點(diǎn)序列序列 ( (vi vp1 vp2 . vpm vjvi vp1 vp2 . vpm vj) ) 為從頂點(diǎn)為從頂點(diǎn)vivi 到頂點(diǎn)到頂點(diǎn) vjvj 的路徑。它經(jīng)過的邊的路徑。它經(jīng)過的邊( (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路徑長度路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。n如如: :從從A A到到F F長度為長度為 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無向圖的鄰接矩陣是對(duì)稱的無向圖的鄰接矩陣是對(duì)稱的;n有向圖的鄰接矩陣可能是不對(duì)稱的。有

34、向圖的鄰接矩陣可能是不對(duì)稱的。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在無向圖中在無向圖中, , 統(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 無向圖的鄰接表無向圖的鄰接表 同一個(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ù)元素開始，從查找表中第一個(gè)數(shù)據(jù)元素開始，逐個(gè)把數(shù)據(jù)元素的關(guān)逐個(gè)把數(shù)據(jù)元素的關(guān)鍵字值與給定值比較鍵字值與給定值比較，若某個(gè)元素的關(guān)鍵字的值與給定，若某個(gè)元素的關(guān)鍵字的值與給定值相等，則查找成功，否則查找失敗。值相等，則查找成功，否則查找失敗。適合：順序存儲(chǔ)的查找表，鏈?zhǔn)酱鎯?chǔ)的查找表適合：順序存儲(chǔ)的查找表，鏈?zhǔn)酱鎯?chǔ)的查找表查找過程查找過程: : 算法分析算法分析: : 2 2、 二分查找二分查找有

37、序表有序表 : : 查找表中記錄按關(guān)鍵字有序排列的表查找表中記錄按關(guān)鍵字有序排列的表. .即即: ri.key=ri+1.key i=1,2,: ri.key21,21,則說明，待查元素若存在，必在則說明，待查元素若存在，必在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)鍵字是無序的，但無序的，但塊與塊之間是按照關(guān)鍵字有序塊與塊之間是按照關(guān)鍵字有序的，即第一塊中的，即第一塊中的所有元素大于（或者小于）第二塊中的所有元素，依次的所有元素大于（或者小于）第二塊中的所有元素，依次類推。類推。

39、2) 2) 對(duì)每塊建立一個(gè)索引項(xiàng)對(duì)每塊建立一個(gè)索引項(xiàng), , 包含以兩項(xiàng)內(nèi)容包含以兩項(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)分塊查找表的平均查找長度分塊查找表的平均查找長度ASL=LASL=Lb b+L+

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

41、錄數(shù)增有序子文件記錄數(shù)增1)1) 例如：已有待排序文件為：例如：已有待排序文件為：3838，6565，4949，7676，9797 首先將文件的第一個(gè)記錄，視為有序文件，然后從第二個(gè)記首先將文件的第一個(gè)記錄，視為有序文件，然后從第二個(gè)記錄開始，直到最后一個(gè)記錄，依次將他們插入到有序文件的錄開始，直到最后一個(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)由過程中這一點(diǎn)由過程中WHILEWHILE語句的條語句的條件件“”保證的保證的) )。 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ù)上述過程，直到每一部分僅剩一個(gè)記錄為止。過程，直到每一部分僅剩一個(gè)記錄為止。2 2）具體步驟）具體步驟(1) (1) 置變量置變量i i，j j初值分別為文件的首、尾記錄位置；選取文件初值分別為文件的首、尾記錄位置；選取文件首記錄首記錄riri，并將其關(guān)鍵字賦給變量，并將其關(guān)鍵字賦給變量x x； (2) (2) 從從j j 位置開始向前搜索，位置開始向前搜索，(3) (3) 直到遇到第一個(gè)關(guān)鍵字小于直到遇到第一個(gè)關(guān)鍵字小于x x的記錄，的記錄，(4) (4) 并將并將rjrj移至移至riri；(5) (5) 從從i 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、簡單選擇排序、簡單選擇排序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)鍵字排列無關(guān)，比較次數(shù)：與初始文件關(guān)鍵字排列無關(guān)， 為為n(n-1)/2n(n-1)/2次。次。 簡單選擇排序時(shí)間復(fù)雜度為簡單選擇排序時(shí)間復(fù)雜度為O(nO(n2 2) )，并且是不穩(wěn)定的排，并且是不穩(wěn)定的排序序。6 6、歸并排序、歸并排序 歸并概念：把歸并概念：把 2 2 個(gè)有序子文件合并成一個(gè)有序文件的過程個(gè)有序子文件合并成一個(gè)有序文件的過程

47、，稱為，稱為2-2-路歸并。路歸并。 歸并排序基本思想：歸并排序基本思想：將文件的每個(gè)記錄視為一個(gè)有序子文將文件的每個(gè)記錄視為一個(gè)有序子文件；件；然后兩兩子文件進(jìn)行然后兩兩子文件進(jìn)行2-2-路歸并；路歸并；重復(fù)重復(fù)，直到只剩，直到只剩一個(gè)長度為一個(gè)長度為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)品從形成概念開始，經(jīng)過開發(fā)、使用和維護(hù)，直到最軟件產(chǎn)品從形成概念開始，經(jīng)過開發(fā)、使用和維護(hù)，直到最后退役的全過程。后退役的全過程。Software life cycle. Software life cycle. 根據(jù)軟件狀態(tài)、根據(jù)軟件狀態(tài)、特征

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

50、開發(fā)過程所遵守的規(guī)定限制以及各階段活動(dòng)的總則，確立開發(fā)過程所遵守的規(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)目開發(fā)計(jì)劃、需求

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

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

53、析需求分析 設(shè)設(shè) 計(jì)計(jì) 編編 碼碼 單元測試單元測試 集成測試集成測試 確認(rèn)測試確認(rèn)測試 1 1、軟件測試設(shè)計(jì)的方法、軟件測試設(shè)計(jì)的方法 測試技術(shù)測試技術(shù)1 1、白盒測試白盒測試(White Box Testing)(White Box Testing)2 2、黑盒測試黑盒測試(Black Box Testing)(Black Box Testing) 軟件的測試設(shè)計(jì)與軟件產(chǎn)品的設(shè)計(jì)一樣，是一項(xiàng)需要花費(fèi)軟件的測試設(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）白盒測試）白盒測試(White Box Testing)(White Box Testing) 也叫玻璃盒測試也叫玻璃盒測試(Glass Box Testing)(Glass Box Testing)。 對(duì)軟件的過程性細(xì)節(jié)做細(xì)致的檢查。這一方法是把測試對(duì)對(duì)軟件的過程性細(xì)節(jié)做細(xì)致的檢查。這一方法是把測試對(duì)象看作一個(gè)打開的盒子，它允許測試人員利用程序內(nèi)部的象看作一個(gè)打開的盒子，它允許測試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息，來設(shè)計(jì)或選擇測試用例，對(duì)程序所邏輯結(jié)構(gòu)及有關(guān)信息，來設(shè)計(jì)或選擇測試用例，對(duì)程序所有邏輯路徑進(jìn)行測試。有邏輯路徑進(jìn)行測試。白盒測試白盒測試的內(nèi)容的內(nèi)容對(duì)

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

56、統(tǒng)操作系統(tǒng)1 1、操作系統(tǒng)的目標(biāo)、操作系統(tǒng)的目標(biāo) 目前存在著多種類型的目前存在著多種類型的OSOS，不同類型的，不同類型的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）開放性）開放性 2 2、操作系統(tǒng)的作用、操作系統(tǒng)的作用 OSOS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口 OSOS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過OSOS來使用計(jì)算來使用計(jì)算機(jī)

57、系統(tǒng)?；蛘哒f，用戶在機(jī)系統(tǒng)。或者說，用戶在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è)