軟件技術基礎

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

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

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

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

5、1=i=LENGTH(L)1=i=LENGTH(L)時返回時返回L L中中第第i i個數(shù)據(jù)元素，否則為空元素個數(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)時的位序在表中第一次出現(xiàn)時的位序INSERTINSERT（L, i , bL, i , b）前插操作前插操作 在第在第i i個元素之前插入新元素個元素之前插入新元素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個元素，個元素， 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、線性表的順序存儲結

7、構、線性表的順序存儲結構 1 1）順序存儲結構順序存儲結構 用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次存儲線性表的元素。設每的存儲單元依次存儲線性表的元素。設每個元素占用個元素占用k k個存儲單元，個存儲單元， Loc(aLoc(a1 1) )為線性表的起址，則為線性表的起址，則第第i i個元素個元素a ai i 的存儲位置為：的存儲位置為：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)* *k k 2 2）插入運算）插入運算 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 ） 算法思想：算法思想： 進行合法性檢查，進行合法性檢查，1=i=n+11=i=n+1； 判斷線性表是否已滿；判斷線性表是否已滿； 將第將第n n個至第個至第i i個元素逐一后移一個單元；個元素逐一后移一個單元； 在第在第i i個位置處插入新元素；個位置處插入新元素； 將表的長度加將表的長度加1 1。 3 3）刪除運算）刪除運算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） 算法思想：算法思想： 進行合法性檢查，進行合法性檢查，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)刪除運算刪除運算 刪除前刪除前 刪除后刪除后 刪除運算可以由定位和修改指針來完成：刪除

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

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

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

13、端稱為對頭允許刪除的一端稱為對頭(front)。特點：特點：先進先出先進先出 (FIFO) a1 ，a2， a3，an出隊列出隊列入隊列入隊列隊頭隊頭隊尾隊尾鏈隊列：隊列的鏈式表示鏈隊列：隊列的鏈式表示鏈隊列中，有兩個分別指示隊頭和隊尾的指針。鏈隊列中，有兩個分別指示隊頭和隊尾的指針。鏈式隊列在進隊時無隊滿問題，但有隊空問題。鏈式隊列在進隊時無隊滿問題，但有隊空問題。data nextfrontreardata nextfrontrearfrontrearx元素元素x入隊入隊frontrearxy元素元素y入隊入隊frontrearxy元素元素x出隊出隊frontrear空隊列空隊列front

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

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

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

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

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

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

20、內從左到結點層序編號方法：從根結點起從上到下逐層（層內從左到右）對二叉樹的結點進行連續(xù)編號。右）對二叉樹的結點進行連續(xù)編號。1 12 23 37 76 65 54 4K=3K=3n=2n=23 3-1=7-1=7滿二叉樹滿二叉樹5 5、完全二叉樹、完全二叉樹 深度為深度為k k，結點數(shù)為，結點數(shù)為n n的二叉樹，當且僅當每個結點的編號的二叉樹，當且僅當每個結點的編號都與相同深度的滿二叉樹中從都與相同深度的滿二叉樹中從1 1到到n n的結點一一對應時，稱的結點一一對應時，稱為為完全二叉樹完全二叉樹。 滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是

21、滿二叉樹。叉樹。4521 13 完全二叉樹完全二叉樹D DC CG GF FE EB BA A6 6、二叉樹的存儲結構、二叉樹的存儲結構 1 1）順序存儲結構）順序存儲結構 用一組地址連續(xù)的存儲單元，以層序順序存放二叉樹的數(shù)據(jù)用一組地址連續(xù)的存儲單元，以層序順序存放二叉樹的數(shù)據(jù)元素，結點的相對位置蘊含著結點之間的關系。元素，結點的相對位置蘊含著結點之間的關系。 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 這種存儲結構適合于完全二叉樹，既不浪費存儲空間，又能這種存儲結構適合于完全二叉樹，既不浪費存儲空間，又能很快確定結點的存放位置、以及結點的雙親和左右孩子的存很快確定結點的存放位置、以及結點的雙親和左右孩子的存放位置，但對一般二叉樹，可能造成存儲空間的浪費。放位置，但對一般二叉樹，可能造成存儲空間的浪費。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 一般二叉樹也按完全二叉樹形式存儲一般二叉樹也按完全二叉樹形式存儲, ,沒結點處用沒結點處用0 0表示。表示。二叉鏈表的結點結構二叉鏈表的結點結構 lchild data rchild lchild data rchildD D 二叉樹二叉樹C CE EB BA AA AC CB BD DE E二叉鏈表二叉鏈表 2 2） 鏈式存儲結構鏈式存儲結構 設計不同的結點結構，可以構成不同的鏈式存儲結構。常設計不同的結點結構，可以構成不同的鏈式存儲結構。常用的有：用的有： 二叉鏈表二叉鏈表 3 3）遍歷二叉樹）遍歷二叉樹 遍歷二叉樹是指遍歷二叉樹是指按一定的規(guī)律按一定的規(guī)律

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

25、二叉樹非空，則：若二叉樹非空，則： 1 1）中序遍歷左子樹）中序遍歷左子樹 2 2）訪問根結點）訪問根結點 3 3）中序遍歷右子樹）中序遍歷右子樹 （2 2）后序遍歷二叉樹后序遍歷二叉樹 算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則： 1 1）后序遍歷左子樹）后序遍歷左子樹 2 2）后序遍歷右子樹）后序遍歷右子樹 3 3）訪問根結點）訪問根結點 （3 3）先序遍歷二叉樹先序遍歷二叉樹 算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則： 1 1）訪問根結點）訪問根結點 2)2)先序遍歷左子樹先序遍歷左子樹 3 3）先序遍歷右子樹）先序遍歷右子樹例：表達式例：表達式a+b

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

27、數(shù)據(jù)對象 是頂點的有窮非空集合；是頂點的有窮非空集合； 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是頂點之間關系的有窮集合，也叫做邊是頂點之間關系的有窮集合，也叫做邊(edge)(edge)集合，此時的圖稱為無向圖。集合，此時的圖稱為無向圖。 E2 E2 表示從表示從 x x 到到 y y 的一條的一條弧，且稱弧，且稱x x為弧尾，為弧尾，y y為弧頭，這樣的圖稱為有向圖。為弧頭，這樣的圖稱為有向圖

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

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

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

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

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

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

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

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

36、示一個數(shù)據(jù)元素的數(shù)據(jù)項。如學生的學號、居民的身份證號碼等。如學生的學號、居民的身份證號碼等。 查找表查找表：一組待查數(shù)據(jù)元素的集合。：一組待查數(shù)據(jù)元素的集合。1 1、順序查找、順序查找從查找表中第一個數(shù)據(jù)元素開始，從查找表中第一個數(shù)據(jù)元素開始，逐個把數(shù)據(jù)元素的關逐個把數(shù)據(jù)元素的關鍵字值與給定值比較鍵字值與給定值比較，若某個元素的關鍵字的值與給定，若某個元素的關鍵字的值與給定值相等，則查找成功，否則查找失敗。值相等，則查找成功，否則查找失敗。適合：順序存儲的查找表，鏈式存儲的查找表適合：順序存儲的查找表，鏈式存儲的查找表查找過程查找過程: : 算法分析算法分析: : 2 2、 二分查找二分查找有

37、序表有序表 : : 查找表中記錄按關鍵字有序排列的表查找表中記錄按關鍵字有序排列的表. .即即: ri.key=ri+1.key i=1,2,: ri.key21,21,則說明，待查元素若存在，必在則說明，待查元素若存在，必在low,mid-1low,mid-1區(qū)間中，則在該區(qū)間中進行二分查找區(qū)間中，則在該區(qū)間中進行二分查找: :令令highig=mid-1, =mid-1, 重新計算重新計算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ù)元素分成若干塊，塊內的元素按照關鍵字是將所有數(shù)據(jù)元素分成若干塊，塊內的元素按照關鍵字是無序的，但無序的，但塊與塊之間是按照關鍵字有序塊與塊之間是按照關鍵字有序的，即第一塊中的，即第一塊中的所有元素大于（或者小于）第二塊中的所有元素，依次的所有元素大于（或者小于）第二塊中的所有元素，依次類推。類推。

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

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

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

42、的( (這一點由過程中這一點由過程中WHILEWHILE語句的條語句的條件件“”保證的保證的) )。 4 4、快速排序、快速排序 快速排序是目前內部排序中最快的方法。快速排序是目前內部排序中最快的方法。 1 1）基本思想基本思想：選取某個記錄：選取某個記錄( (通常選文件的第一個記錄通常選文件的第一個記錄) )，將所有關鍵字不大于它的記錄放在它的前面，將所有關鍵將所有關鍵字不大于它的記錄放在它的前面，將所有關鍵字不小于它的記錄放在它的后面，這樣遍歷一趟文件后，字不小于它的記錄放在它的后面，這樣遍歷一趟文件后，將文件以該記錄為界分為兩部分，然后對各部分重復上述將文件以該記錄為界分為兩部分，然后對

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

44、個關鍵字大于直到遇到第一個關鍵字大于x x的記錄，的記錄，(7) (7) 并將并將riri移至移至rjrj；(8) (8) 重復重復(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) 重復重復(1)(1)至至(10)(10)，直到每一部分只剩上一個記錄，整個文，直到每一部分只剩上一個記錄，整個文件已有序，快速排序算法結束。件已有序，快速排序算法結束。 例如：例如： x初始關鍵字初始關鍵

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) 結束結束 結束結束 49 (65) 結束結束 結束結束最后最后 （13 27 38 49 49 65 79 97）5 5、簡單選擇排序、簡單選擇排序1 1）基本思想基本思想：對文件進行：對文件進行n-1n-1趟排序，第趟排序，第i i趟趟(i=1,2,.n-(i=1,2,.n-1)1)是在從是在從i i到到 n n的的n-i+1n-i+1個記錄中選擇關鍵字最小的記錄，并個

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

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

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

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

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

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

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

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

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

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

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