软件技术基础课件.ppt

8.3.5佇列插入在表一端進行，而刪除在表的另一端進行，將這種數據結構稱為隊或佇列。佇列的物理存儲可以用順序存儲結構，也可以用鏈式存儲結構。佇列的基本運算有入隊、出隊、取隊頭、判佇列空、插入和刪除等。a2a1a3an出佇列入隊列頭尾佇列的示意8.3.6樹與二叉樹樹和二叉樹的定義二叉樹的幾個基本性質二叉樹的存儲二叉樹的遍曆樹和二叉樹的定義樹是由一個或多個結點組成的有限集合。它很像一株倒懸著的樹，從樹根到大、小枝幹、直到葉子，將數據聯繫起來，這樣的數據結構稱為樹結構(簡稱為樹)。二叉樹是有限個元素的集合，該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結點。二叉樹的幾個基本性質性質1：在二叉樹第i層上至多有2i–1個結點 (i≥1)。性質2：深度為k的二叉樹中，最多有2k–1 個結點(k≥1)。性質3：具有n個結點的完全二叉樹的深度 是:[log2n]+1。性質4：在任意一棵二叉樹中，若其葉子 結點數為n0,度為2的結點數為 n2，則：n0=n2+1。二叉樹的存儲二叉樹的存儲通常採用鏈接方式。它是指用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關係。鏈表中每個結點由三個域組成，除了數據域外，還有兩個指針域，分別用來給出該結點左子樹和右子樹所在的鏈結點的存儲地址。結點的存儲的結構為：lchilddaterchild二叉樹的遍曆三種重要的二叉樹遍曆的方法：先序遍曆法中序遍曆法後序遍曆法二叉樹的遍曆例：給出如圖8-20所示的一棵二叉樹，寫出對應的遍曆序列。按先序遍曆序列：abdecfgh按中序遍曆序列：按後序遍曆序列：debfcgahedfgcbhacdehgfba樹的結構8.3.7查找查找就是在某種數據結構中找出滿足條件的結點。兩種基本的查找方法：二分法查找順序查找順序查找的方法順序查找方法為：從表的一端開始，向另一端逐個按給定值kx與表中各結點的關鍵碼進行比較，若找到，查找成功，並給出數據元素在表中的位置；若整個表檢索完之後，仍未找到與給定值kx相同的關鍵碼，則查找失敗，給出失敗資訊。二分法查找的方法二分法查找的方法是：在有序表中，取中間元素作為比較對象，若給定值與中間元素的關鍵碼相等，則查找成功：若給定值小於中間元素的關鍵碼，則在中間元素的左半區繼續查找；若給定值大於中間元素的關鍵碼，則在中間元素的右半區繼續查找。不斷重複上述查找過程，直到查找成功，或所查找的區域無數據元素，查找失敗。順序查找的優缺點順序查找的優點：一是對線性表的結點的邏輯次序不作要求，無需按關鍵碼值先排序。二是對線性表的存儲結構不作要求，順序存儲、鏈式存儲均可。其缺點是：平均檢索長度大二分法查找的優缺點二分法查找的優點：平均檢索長度小，即每經過一次關鍵碼比較，則將查找範圍縮小一半，經過次比較就可完成查找過程。其缺點是排序線性表費時間8.3.8排序排序是電腦程式設計中的一種重要操作，它是將一個無序序列整理成按關鍵字遞增(或遞減)的有序序列的處理過程。幾種最常用的內排序方法：直接插入排序冒泡排序選擇排序快速排序8.4資料庫技術基礎8.4.1資料庫技術的發展人工管理階段檔系統階段應用程式1應用程式2應用程式n數據1數據2數據n人工管理階段應用程式1應用程式2應用程式n檔1檔2檔n存取檔系統階段資料庫系統階段應用程式1應用程式2應用程式n資料庫管理系統數據庫資料庫系統階段資料庫系統階段資料庫的發展趨勢*軟體技術基礎8.1軟體工程基礎8.1.1軟體工程的基本概念軟體的發展過程軟體工程的定義軟體工程的內容軟體工程過程與軟體生命週期軟體工程的基本目標與原則軟體開發工具與開發環境軟體的發展過程軟體的發展大致可劃分為四個階段：程式設計階段程式系統階段軟體工程階段(結構化方法)軟體工程階段(面向對象方法)軟體工程的定義軟體工程就是採用工程化的原理、技術和方法來開發、運行和維護軟體。軟體工程包含三個要素：方法(M