《數(shù)據(jù)庫原理與應用（VFP）第二版》課件-第9章　公共基礎知識

第9章公共基礎知識

9.1數(shù)據(jù)結(jié)構(gòu)與算法9.2程序設計基礎9.3軟件工程基礎學習目標了解數(shù)據(jù)結(jié)構(gòu)和算法的基本概念、基本的數(shù)據(jù)結(jié)構(gòu)；理解基本數(shù)據(jù)結(jié)構(gòu)的操作方法；了解查找與排序的有關(guān)知識；了解程序設計方法、原則與風格；了解軟件工程的基本概念；了解軟件測試的有關(guān)知識；了解程序調(diào)試的方法。重點與難點重點在于了解各種基本概念；難點在于對基本概念的理解。9.1數(shù)據(jù)結(jié)構(gòu)與算法9.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念9.1.2算法的基本概念9.1.3線性表9.1.4線性鏈表與循環(huán)鏈表9.1.5棧和隊列9.1.6樹9.1.7查找9.1.8排序9.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)（DataStructure）作為一本學科，它是一門研究非數(shù)值性程序設計中計算機操作的對象以及它們之間的關(guān)系和運算等的科學。邏輯結(jié)構(gòu)：如圖所示。存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)、非順序存儲結(jié)構(gòu)9.1.2算法的基本概念算法：是指采用科學的方法完成某項事務的執(zhí)行過程算法具有如下5個特性：（1）有窮性。算法在有限的時間內(nèi)執(zhí)行有限個步驟后必須能終止，即具有執(zhí)行時間的合理性。（2）確定性。算法的描述必須無歧義，以保證算法的實際執(zhí)行結(jié)果是精確地符合要求或期望，通常要求實際運行結(jié)果是確定的。（3）可行性。又稱有效性，算法中描述的操作必須都是可以通過已經(jīng)實現(xiàn)的基本運算的次數(shù)有限的執(zhí)行來實現(xiàn)，即每條指令都應在有限時間內(nèi)完成。（4）輸入。一個算法必須有零個或多個輸入量。（5）輸出。一個算法應有一個或多個輸出量，輸出量是算法計算的結(jié)果。常用的計算機算法（1）列舉法。也稱枚舉法（2）歸納法。數(shù)學模型（3）遞推法。本質(zhì)上屬于歸納法（4）遞歸法。分為直接遞歸和間接遞歸兩種（5）減半遞推法。又稱分治法，也屬于歸納法（6）回溯法。通過對問題的分析，找到一個解決問題的線索，然后沿著這個線索逐步試探。對于每一步的試探，如果試探成功，就獲得了問題的解；否則逐步退回，更換其他未被試探的路線進行試探，這種逐步退回稱為回溯。算法評價算法復雜度主要包括時間復雜度和空間復雜度(1)時間復雜度是執(zhí)行算法所需的計算工作量，可以由語句執(zhí)行次數(shù)（稱為語句頻度或時間頻度）來表示。(2)空間復雜度是指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量。包括3個部分：①算法程序所占的空間；②輸入的初始數(shù)據(jù)所占的存儲空間；③算法執(zhí)行過程中所需要的額外空間。算法的質(zhì)量評價標準（1）正確性。一個好的算法必須保證運行結(jié)果正確。但程序正確性又難以給出嚴格的數(shù)學證明，所以建議多選用現(xiàn)有的、經(jīng)過時間考驗的算法和采用科學規(guī)范的算法設計方法。（2）可讀性。一個好的算法應具有可讀性強，程序中適當?shù)淖⑨?、良好的編排風格和科學規(guī)范的程序設計方法有助于提高可讀性，進而有助于保證算法的正確性。（3）通用性。一個好的算法應盡可能通用，適合一類問題的求解。（4）高效性。算法的效率包括時間和空間兩個方面。9.1.3線性表順序表是線性表的順序存儲結(jié)構(gòu)，它具有兩個基本特點：①順序表中所有元素所占的存儲空間是連續(xù)的；②順序表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。9.1.4線性鏈表與循環(huán)鏈表線性鏈表（LinearLinkedList）是線性表的鏈式存儲結(jié)構(gòu)。由于在線性鏈表操作過程中對空表和對第一個結(jié)點的處理必須單獨考慮，因而使得空表與非空鏈表的操作不統(tǒng)一。為了克服這一缺點，循環(huán)鏈表（CircularLinkedList）的結(jié)構(gòu)被提出。9.1.5棧和隊列棧和隊列都是線性結(jié)構(gòu)，從數(shù)據(jù)結(jié)構(gòu)角度看，它們是操作受限的線性表。9.1.6樹樹（Tree）是n(n≥0)個結(jié)點的有限集。當n=0時，稱為空樹。在任一非空樹(n>0)中，（1）有且僅有一個稱為根(root)的結(jié)點；（2）其余結(jié)點可分為m(m≥0)個互不相交的有限集T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(Subtree)。二叉樹（BinaryTree）是每個結(jié)點至多只有兩棵子樹，即不存在度大于2的結(jié)點，并且二叉樹的子樹有左右之分，在有序樹中，其次序不能顛倒。滿二叉樹和完全二叉樹是兩種特殊的二叉樹。二叉樹的訪問(遍歷)（1）先序遍歷(DLR)。首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。（2）中序遍歷(LDR)。首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。（3）后序遍歷(LRD)。首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。先序遍歷為：-+a*b-cd/ef；中序遍歷為：a+b*c-d-e/f；后序遍歷為：abcd-*+ef/-9.1.7查找所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定元素。(1)

順序查找。不管靜態(tài)查找表中的數(shù)據(jù)元素是否有序，從表的第一個元素開始，依次將表中的元素與被查找元素進行比較，若相等則表示已經(jīng)找到，即查找成功；若表中所有的元素都與被查找元素進行了比較但都不相等，則表示表中沒有要找的元素，即查找失敗。(2)二分法查找。又稱折半查找,首先將x與表的中間項進行比較，若中間項的值等于x，則表示已經(jīng)查找到，查找結(jié)束；其次如果x小于中間項的值，則在表的前半部分（即中間項以前的部分）以相同的方法進行查找；如果x大于中間項的值，則在表的后半部分以相同的方法進行查找。上述查找過程一直進行到查找成功或達到子表長度為0為止。9.1.8排序所謂排序是指按照關(guān)鍵字的值的大小將一個無序序列調(diào)整成為一個有序序列。排序分為內(nèi)部排序和外部排序。（1）內(nèi)部排序。在排序的整個過程中，數(shù)據(jù)全部存放在計算機的內(nèi)存，并且在內(nèi)存中調(diào)整數(shù)據(jù)元素或數(shù)據(jù)記錄的相對位置。（2）外部排序。在排序過程中，數(shù)據(jù)的主要部分存放在外部存儲器中，借助于內(nèi)存逐步調(diào)整數(shù)據(jù)元素或數(shù)據(jù)記錄的相對位置。3種內(nèi)部排序方法9.2程序設計基礎9.2.1程序設計方法9.2.2程序設計風格9.2.3結(jié)構(gòu)化程序設計9.2.4面向?qū)ο蟪绦蛟O計9.2.1程序設計方法程序設計方法學是一門討論程序的性質(zhì)以及程序設計的理論和方法的學科,是研究和構(gòu)造程序的過程的學問，是研究關(guān)于問題的分析，環(huán)境的模擬，概念的獲取，需求定義的描述，以及把這種描述變換細化和編碼成機器可以接受的表示的一般方法。常用的程序設計方法包括：結(jié)構(gòu)化程序設計方法面向?qū)ο蠓椒ㄜ浖こ谭椒?.2.2程序設計風格程序設計風格指一個人編制程序時所表現(xiàn)出來的特點，習慣邏輯思路等?！扒逦谝?、效率第二”的觀點成為當今主導的程序設計風格。9.2.3結(jié)構(gòu)化程序設計結(jié)構(gòu)化程序設計（StructuredProgramming）原則概括為自頂向下、逐步求精、模塊化和限制使用goto語句。自頂向下是指程序設計時，先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標；先從最上層總目標開始設計，逐步使問題具體化。逐步求精是指對復雜問題，應設計一些子目標作過渡，逐步細化。模塊化是把程序要解決的總目標分解為目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。9.2.4面向?qū)ο蟪绦蛟O計面向?qū)ο蟪绦蛟O計（ObjectOrientedProgramming，OOP）是一種計算機編程架構(gòu)。OOP的任務是圍繞類程序設計、對象程序設計和事件方法設計3種設計方法展開。進行面向?qū)ο笤O計時，不再單純地從代碼的第一行一直編寫到最后一行，而是考慮如何創(chuàng)建對象，利用對象來簡化程序設計，提供代碼的可重用性和提高系統(tǒng)設計的可擴展性。9.3軟件工程基礎9.3.1軟件工程概述9.3.2結(jié)構(gòu)化分析與設計9.3.3軟件測試9.3.4程序調(diào)試9.3.1軟件工程概述計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)及其相關(guān)文檔的完整集合。軟件分為系統(tǒng)軟件和應用軟件。軟件危機泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題，歸結(jié)為成本、質(zhì)量和生產(chǎn)率等問題。軟件生產(chǎn)的這種知識密集和人力密集的特點是造成軟件危機的根源所在。軟件工程軟件工程是研究和應用如何以系統(tǒng)性的、規(guī)范化的、可定量的過程化方法去開發(fā)和維護軟件，以及如何把經(jīng)過時間考驗而證明正確的管理技術(shù)和當前能夠得到的最好的技術(shù)方法結(jié)合起來，涉及到程序設計語言、數(shù)據(jù)庫、軟件開發(fā)工具、系統(tǒng)平臺、標準、設計模式等方面。軟件工程3個要素。方法是完成軟件工程項目的技術(shù)手段；工具支持軟件的開發(fā)、管理和文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。軟件生命周期（1）可行性研究與計劃制定。（2）需求分析。（3）軟件設計。（4）軟件實現(xiàn)。（5）軟件測試。（6）運行和維護。軟件工程國家標準分為8個階段：系統(tǒng)定義、可行性分析、需求分析、概念設計、詳細設計、編寫代碼、用戶測試和軟件維護。軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境可以從不同角度進行分類：（1）按軟件開發(fā)模型及開發(fā)方法分類。有支持瀑布模型、演化模型、螺旋模型、噴泉模型以及結(jié)構(gòu)化方法、信息模型方法、面向?qū)ο蠓椒ǖ炔煌Ｐ图胺椒ǖ能浖_發(fā)環(huán)境。（2）按功能及結(jié)構(gòu)特點分類。有單體型、協(xié)同型、分散型和并發(fā)型等多種類型的軟件開發(fā)環(huán)境。（3）按應用范圍分類。有通用型和專用型軟件開發(fā)環(huán)境。（4）按開發(fā)階段分類。有前端開發(fā)環(huán)境(支持系統(tǒng)規(guī)劃、分析、設計等階段的活動)、后端開發(fā)環(huán)境(支持編程、測試等階段的活動)、軟件維護環(huán)境和逆向工程環(huán)境等。9.3.2結(jié)構(gòu)化分析與設計結(jié)構(gòu)化方法（StructuredMethod，SM）是強調(diào)開發(fā)方法的結(jié)構(gòu)合理性以及所開發(fā)軟件的結(jié)構(gòu)合理性的軟件開發(fā)方法。結(jié)構(gòu)是指系統(tǒng)內(nèi)各個組成要素之間的相互聯(lián)系、相互作用的框架。結(jié)構(gòu)化開發(fā)方法提出了一組提高軟件結(jié)構(gòu)合理性的準則，如分解與抽象、模塊獨立性、信息隱蔽等。結(jié)構(gòu)化分析步驟（1）通過對用戶的調(diào)查，以軟件需求為線索，獲得當前系統(tǒng)的具體模型；（2）通過對具體模型抽象，丟棄非本質(zhì)因素獲得當前系統(tǒng)的邏輯模型；（3）依據(jù)計算機的特點分析當前系統(tǒng)與目標系統(tǒng)的差別，建立目標系統(tǒng)的邏輯模型；（4）完善目標系統(tǒng)并補充細節(jié)，撰寫目標系統(tǒng)的軟件需求規(guī)格說明；（5）評審直至確認完全符合用戶對軟件的需求。常用方法：數(shù)據(jù)流圖、數(shù)據(jù)字典、判定樹或判定表結(jié)構(gòu)化程序設計從工程管理角度來看，軟件設計分兩步完成：概要設計和詳細設計。（1）概要設計。也稱結(jié)構(gòu)設計，基本任務包括：設計軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)設計、編寫概要設計文檔和概要設計文檔評審。常用的軟件結(jié)構(gòu)設計工具是程序結(jié)構(gòu)圖。（2）詳細設計。它的任務是過程設計，為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。常見工具包括圖形工具（流程圖、N-S圖、PAD或HIPO等）、判定表和偽代碼等。9.3.3軟件測試IEEE將軟件測試定義為：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或弄清預期結(jié)果與實際結(jié)果之間的差別。測試是以查找錯誤為中心。軟件測試方法：靜態(tài)測試與動態(tài)測試；白盒測試與黑盒測試。軟件測試過程一般按4個步驟進行，即單元測試、集成測試、驗收測試（確認測試）和系統(tǒng)測試。9.3.4程序調(diào)試程序調(diào)試與軟件測試不同，它的任務是診斷和改正程序中的錯誤。程序調(diào)試包括兩部分：根據(jù)錯誤的跡象確定程序中錯誤的性質(zhì)、原因和位置；對程序進行修改以排除錯誤。程序調(diào)試方法也可以分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試是指主要通過人的思維來分析源程序代碼和排錯，是主要的調(diào)試手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試的。本章小結(jié)程序=算法+數(shù)據(jù)結(jié)構(gòu)