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

第9章公共基礎(chǔ)知識(shí)

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

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