1、計算機軟件基礎知識第三講 基本組成3.1數據結構與算法 1.1 算法算法：是一組有窮指令集，是解題方案的準確而完整的描述。通俗地說，算法就是計算機解題的過程。算法不等于程序，也不等于計算方法，程序的編制不可能優于算法的設計。 算法是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所以其四個基本特征包括： (1) 確定性，算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許有多義性； (2) 有窮性，算法必須能在有限的時間內做完，即能在執行有限個步驟后終止； (3) 可行性，算法原則上能夠精確地執行； (4) 擁有足夠的情報。 算法的基本要素

2、：一是對數據對象的運算和操作；二是算法的控制結構。 指令系統：一個計算機系統能執行的所有指令的集合。 基本運算和操作包括：算術運算、邏輯運算、關系運算、數據傳輸。 算法的三種基本控制結構：順序結構、選擇結構、循環結構。 算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法。 算法效率的度量算法復雜度：算法時間復雜度和算法空間復雜度。 算法時間復雜度：指執行算法所需要的計算工作量。即算法執行過程中所需要的基本運算次數。通常，一個算法所用的時間包括編譯時間和運行時間。 算法空間復雜度：指執行這個算法所需要的內存空間。包括算法程序所占的空間，輸入的初始數據所占的空間，算法執行過程中所需

3、的額外空間。1.2 數據結構的基本概念數據結構：指相互有關聯的數據元素的集合。 數據結構研究的三個方面： (1) 數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構； (2) 在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構； (3) 對各種數據結構進行的運算。數據的邏輯結構應包含： (1) 表示數據元素的信息； (2) 表示各數據元素之間的前后件關系(指邏輯關系，與存儲位置無關)。 數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構,也稱數據物理結構。 數據的存儲結構有順序、鏈接、索引等。 線性結構的條件，(一個非空數據結構)： (1) 有且只有一個根結

4、點； (2) 每一個結點最多有一個前件，也最多有一個后件。 非線性結構：不滿足線性結構條件的數據結構。 1.3棧和隊列 棧：限定在一端進行插入與刪除的線性表。 其允許插入與刪除的一端稱為棧頂，用指針top表示棧頂位置。 不允許插入與刪除的另一端稱為棧底，用指針bottom表示棧底。 棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數據，棧具有記憶作用。 棧的存儲方式有順序存儲和鏈式存儲。 棧的基本運算：（1）入棧運算，在棧頂位置插入元素； （2） 退棧運算，刪除元素(取出棧頂元素并賦給一個指定的變量)；（3） 讀棧頂元素，將棧頂元素賦給一個指定的變量，此時指針無變化。 隊列：指允許

5、在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。 用rear指針指向隊尾，用front指針指向隊頭元素的前一個位置。 隊列是“先進先出”（FIFO）或“后進后出”（LILO）的線性表。 隊列運算包括：(1) 入隊運算：從隊尾插入一個元素； (2) 退隊運算：從隊頭刪除一個元素。 隊列的順序存儲結構一般采用隊列循環的形式。 循環隊列s=0表示隊列空；s=1且front=rear表示隊列滿。 計算循環隊列的元素個數：“尾指針減頭指針”，若為負數，再加其容量即可。 計算循環隊列長度： front=rear，隊列長度0； frontrear，隊列長度rear+size -front1.4

6、樹與二叉樹 樹是一種簡單的非線性結構，其所有元素之間具有明顯的層次特性。 在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。 在樹結構中，一個結點所擁有的直接后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點： (1) 非空二叉樹只有一個根結點；(2) 每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。 滿二叉樹是指除最后一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點，深度為m的滿二叉樹有2m-1個結

7、點。 完全二叉樹是指除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干結點。 二叉樹基本性質： (1) 在二叉樹的第k層上，最多有2k-1(k1)個結點； (2) 深度為m的二叉樹最多有2m-1個結點； (3) 度為0的結點（即葉子結點）總是比度為2的結點多一個；即n0=n2+1 (4) 具有n個結點的二叉樹，其深度至少為log2n+1,其中log2n表示取log2n的整數部分 (5) 具有n個結點的完全二叉樹的深度為log2n+1；(6) 設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1,2,n給結點進行編號（k=1,2.n），有以下結論：

8、 若k=1，則該結點為根結點，它沒有父結點；若k1，則該結點的父結點編號為INT(k/2)； 若2kn，則k結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）； 若2k+1n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。 補充：增加度為1的結點不會影響二叉樹的葉子結點數，每增加一個度為2的結點便會增加一個葉子結點，沒有度為2的結點時葉子結點數為1。 二叉樹的遍歷： (1) 前序遍歷（DLR），首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；（樹根在第一，下走不跳結點）(2) 中序遍歷（LDR），首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；（有左先左，再尋根，

9、后找右。最左邊的結點最先遍歷，最右邊的結點最后遍歷） (3) 后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結點。（有左先左，再找右，后尋根，到最右一路上行，樹根在最后） 二叉樹中度為 0 的節點的個數比度為 2 的節點的個數多一。二叉樹遍歷總結： 前序遍歷：最左邊的一定是根節點；中序遍歷：根節點左側是左子樹，右側是右子樹；后續遍歷：最右邊是根結點。 3.2 軟件工程基本概念 計算機軟件是包括程序、數據及相關文檔的完整集合。 軟件的特點包括： (1) 軟件是一種邏輯實體，具有抽象性； (2) 軟件的生產與硬件不同，它沒有明顯的制作過程； 軟件在運行、使用期間不存在磨損、老化問

10、題； (4) 軟件的開發、運行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟件移植的問題； 軟件復雜性高，成本昂貴； (6) 軟件開發涉及諸多的社會因素。 軟件按功能分為應用軟件、系統軟件、支撐軟件(或工具軟件)。 軟件危機主要表現在成本、質量、生產率等問題。 軟件工程是應用于計算機軟件的定義、開發和維護的一整套方法、工具、文檔、實踐標準和工序。簡單的說就是使軟件走向工程化。軟件工程的核心思想是把軟件產品看作是一個工程產品來處理。 軟件工程包括3個要素：方法、工具和過程。軟件生命周期分三個階段：軟件定義、軟件開發、運行維護 。 結構化分析方法結構化方法的核心和基礎是結構化程序設計理論。

11、結構化分析的常用工具：數據流圖；數據字典；判定樹；判定表。 (1) 數據流圖（DFD圖）：描述數據處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統功能建模。 加工（轉換）圓框，輸入數據經加工變換產生的輸出。 數據流箭頭，沿箭頭方向傳遞數據的通道，一般在旁邊標注數據流名。 存儲文件（數據源）雙橫線，表示處理過程中存放各種數據的文件。 源、潭方框，表示系統和環境的接口，屬系統之外的實體。 (2) 數據字典：對所有與系統相關的數據元素的一個有組織的列表，以及精確的、嚴格的定義，使得用戶和系統分析員對于輸入、輸出、存儲成分和中間計算結果有共同的理解。 數據字典是結構化分析的核心。(3)

12、判定樹：從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結論，根據描述材料中的連接詞找出判定條件之間的從屬關系、并列關系、選擇關系，根據它們構造判定樹。 (4) 判定表：與判定樹相似，當數據流圖中的加工要依賴于多個邏輯條件的取值，即完成該加工的一組動作是由于某一組條件取值的組合而引發的，使用判定表描述比較適宜。 結構化設計方法 軟件設計是確定系統的物理模型。 軟件設計的基本目標是用比較抽象概括的方式確定目標系統如何完成預定的任務。 從技術觀點來看，軟件設計包括軟件結構設計、數據設計、接口設計、過程設計。 結構設計：定義軟件系統各主要部件之間的關系。數據設計：將分析時創建的模型轉化為數據

13、結構的定義。 接口設計：描述軟件內部、軟件和協作系統之間以及軟件與人之間如何通信。 過程設計：把系統結構部件轉換成軟件的過程描述。 從工程管理角度來看，軟件設計分兩步：概要設計和詳細設計。 軟件設計的基本原理是：(1) 抽象； (2) 模塊化； (3) 信息隱蔽； (4) 模塊獨立性。 衡量軟件模塊獨立性使用耦合性和內聚性兩個定性的度量標準。 耦合性是模塊見相互連接的緊密程度的度量。耦合程度取決于各個模塊之間接口的復雜程度、調用方式以及哪些信息通過接口。 內聚性是一個模塊內部各個元素間彼此結合的緊密程度的度量。在程序結構中各模塊的內聚性越強，則耦合性越弱。優秀軟件應高內聚，低耦合，有利于提高模

14、塊的獨立性。 軟件概要設計的基本任務是： (1) 設計軟件系統結構；(2) 數據結構及數據庫設計；(3) 編寫概要設計文檔；(4) 概要設計文檔評審。 詳細設計：是為軟件結構圖中的每一個模塊確定實現算法和局部數據結構，用某種選定的表達工具表示算法和數據結構的細節。 常見的過程設計工具有： 圖形工具（程序流程圖(PFD)、N-S圖、 PAD圖、），表格工具（判定表），語言工具（PDL）。 程序流程圖中：箭頭為控制流、方框為加工步驟、菱形為邏輯條件。 軟件測試軟件測試定義：使用人工或自動手段來運行或測定某個系統的過程，其目的在于檢驗它是否滿足規定的需求或是弄清預期結果與實際結果之間的差別。 軟件測

15、試的目的：發現錯誤而執行程序的過程。 軟件測試方法：靜態測試和動態測試。 靜態測試包括代碼檢查、靜態結構分析、代碼質量度量。不實際運行軟件，主要通過人工進行。 動態測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。 白盒測試：也稱結構測試或邏輯測試。在程序內部進行，主要用于完成軟件內部操作的驗證。白盒測試主要考慮內部的邏輯結構。主要方法有邏輯覆蓋、基本路徑測試。 黑盒測試：也稱功能測試或數據驅動測試。是在軟件接口處進行，完成功能驗證。黑盒測試完全不考慮程序內部的邏輯結構和內部特性，只依據程序的需求和功能規格說明，檢查程序的功能是否符合它的設計要求。主要診斷功能不對或遺漏、界面錯誤、

16、數據結構或外部數據庫訪問錯誤、性能錯誤、初始化和終止條件錯，用于軟件確認測試。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。程序的調試程序調試的任務是診斷和改正程序中的錯誤，主要在開發階段進行。程序調試的基本步驟：(1) 錯誤定位；(2) 修改設計和代碼，以排除錯誤；(3) 進行回歸測試，防止引進新的錯誤。軟件調試可分為靜態調試和動態調試。靜態調試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設計手段，而動態調試是輔助靜態調試。主要調試方法有：(1) 強行排錯法；(2) 回溯法；(3) 原因排除法。 3.3數據庫設計基礎 數據：實際上就是描述事物的符號記錄。 軟件的數據是有

17、一定的結構，有型與值之分，如整型、實型、字符型等。而數據的值給出了符合定型的值，如整型值15。 數據庫：是指在已有數據庫管理系統的基礎上建立數據庫，是數據的集合，具有統一的結構形式并存放于統一的存儲介質內，是多種應用數據的集成，并可被各個應用程序共享。 數據庫存放數據是按數據所提供的數據模式存放的，具有集成與共享的特點。 數據庫管理系統：一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等，數據庫系統中實現各種數據管理功能的核心軟件稱為數據庫管理系統。 數據庫管理系統提供以下的數據語言： (1) 數據定義語言(DDL)：負責數據的模式定義與數據的物理存取構建；(2)

18、 數據操縱語言(DML)：負責數據的操縱，如查詢與增、刪、改等； (3) 數據控制語言(DCL)：負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等。 數據語言按其使用方式具有兩種結構形式： 交互式命令(又稱自含型或自主型語言)；宿主型語言（一般可嵌入某些宿主語言中）。 數據庫管理員：對數據庫進行規劃、設計、維護、監視等的專業管理人員。 數據庫系統：由數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構成的運行實體。 對數據庫系統需要操作系統的支持。數據庫應用系統：由數據庫系統、應用軟件及應用界面三者組成。 數據管理發展的三個階段：人工管理階段，文件系統階段，數據庫系統階段。數據獨立性最高的是數據庫系統。 文件系統階段：提供了簡單的數據共享與數據管理能力，但是它無法提供完整的、統一的、管理和數據共享的能力。 層次數據庫與網狀數據庫系統階段 ：為統一與共享數據提供了有力支撐。 數據庫系統的基本特點：數據的集成性 、數據的高共享性與低冗余性 、數據獨立性（物理獨立性與邏輯獨立性）、數據統一管理與控制。 物理獨立性：用戶的應用程序與存儲在磁盤在磁盤等介質上的數據庫是相互獨立的。 數據庫系統的三級模式： (1) 概念模式：數據庫系統中全局數