1、晉中高教職業技能培訓中心學員內部資料 公共基礎課本總結第1章數據結構與算法1.1算法算法：是指解題方案的準確而完整的描述。算法的基本特征：可行性、確定性、有窮性(有限的時間)、擁有足夠的情報。*算法的控制結構：算法中各操作之間的執行順序。包括：順序、選擇、循環算法設計的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法算法的復雜度：時間復雜度（算法所需要的計算工作量，即算法所執行的基本運算次數）、空間復雜度（執行這個算法所需要的內存空間）1.2數據結構的基本概念數據結構：是指相互有關聯的數據元素的集合。所謂結構就是指數據元素之間的前后件關系。在數據結構中沒有前件的結點稱為根結點，沒有后

2、件的結點為葉子結點（終端結點）。數據結構研究的三個問題：1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。3）對各種數據結構進行的運算。*數據的邏輯結構：指反應數據元素之間邏輯關系的數據結構。*數據的存儲結構（物理結構）：數據的邏輯結構在計算機存儲空間中的存放形式。（常用：順序、鏈接、索引等結構） 數據處理：是指對數據集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數據元素進行分析空的數據結構：一個元素都沒有的數據結構。數據結構分類：線性結構、非線性結構。*線性結構：有且只有一個

3、根結點，每一個結點最多有一個前件，也最多有一個后件。（線性表、棧、隊列、線性鏈表） *非線性結構：不滿足線性結構特點的數據結構。樹、二叉樹、圖1.3線性表及其順序存儲線性表由一組數據元素組成。線性表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數據元素的個數n稱為線性表的長度。線性表可以為空表：n=0。線性表是一種存儲結構，它的存儲方式：順序和鏈式。線性表的順序存儲結構有兩個基本特點：1. 所有元素所占的存儲空間是連續的。2.各元素在存儲空間中是按邏輯順序依次存放的，前后件兩個元素在存儲空間中是緊鄰的。在長度為n的順序存儲的線性表中，當在任何位置

4、上插入或刪除一個元素概率都相等時，它們所需移動元素的平均個數是為n/2。1.4棧和隊列棧是限定在一端進行插入與刪除的線性表。 棧頂：允許插入與刪除的一端。 棧底：不允許插入與刪除的一端。棧是按照“先進后出”或“后進先出”的原則組織數據的。 棧中元素個數：棧底-棧頂+1棧的基本運算：入棧運算（上溢）、退棧運算（下溢）、讀棧頂元素棧的存儲方式和線性表類似，也有兩種：順序棧和鏈式棧。隊列允許在一端進行插入、而在另一端進行刪除的線性表。隊尾（rear）：允許插入的一端。 隊頭（front）：允許刪除的一端。隊列是按照“先進先出”或“后進后出”的原則組織數據的。 隊中元素個數：隊尾-對頭（隊尾>對

5、頭） 隊中元素個數：隊尾-對頭+容量（隊尾<對頭）隊列的基本運算：入隊運算、退隊運算 循環隊列：將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間1.5線性鏈表線性鏈表：線性表的鏈式存儲結構，是一種物理存儲單元上非連續、非順序的存儲結構*在鏈式存儲結構中，每個數據結點由兩部分組成：數據域（存放數據元素的值）、指針域（存放下一結點的存儲地址）。*在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。*線性鏈表的優點：在線性鏈表中插入或刪除一個元素時，不需要移動元素的位置，只需改變指針

6、的指向就行了。*循環鏈表的優點：只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點。棧和隊列也可采用鏈式存儲結構線性鏈表基本運算：插入、刪除、合并、分解、逆轉、復制、排序、查找1.6樹與二叉樹父結點：每一個結點只有一個前件，稱為父結點。 根結點：沒有前件的結點只有一個，稱為根結點，簡稱為根。子結點：每一個結點可以有多個后件，這些后件稱為子結點。葉子結點：沒有后件的結點。結點的度：一個結點所擁有的后件個數。 樹的度：所有結點中的最大的度。 樹的深度：樹的最大層次（幾層）*根結點在第1層。葉子結點沒有子樹。二叉樹的特點：非空二叉樹只有一個根結點，每一個

7、結點最多有2顆子樹，且分別稱為該結點的左子樹與右子樹。二叉樹的度：可以為0（葉子結點）、1（只有1顆子樹）或2（有2顆子樹）二叉樹的性質：1.在二叉樹的第k層上，最多有2k-1（k>=1）個結點 2.深度為m的二叉樹最多有2m-1個結點3.度為0的結點（葉子結點）總是比度為2的結點多一個4.具有n個結點的二叉樹，其深度至少為log2n+1 5.具有n個結點的完全二叉樹，深度為log2n+1滿二叉樹：除最后一層外，每一層上的所有結點都有2各子結點。完全二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。*根據完全二叉樹的定義可得出：度為1的結點的個數為0或

8、1。*一般二叉樹采用鏈式存儲結構，對于滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲。二叉樹的遍歷：是指不重復的訪問二叉樹中的所有結點。分類：前序遍歷（根左右）、中序遍歷（左根右）、后序遍歷（左右根）*當完全二叉樹總結點n為偶數時，葉子節點的個數為：n/2 *當完全二叉樹總結點n為奇數時，葉子節點的個數為：(n+1)/21.7查找技術順序查找：n（最壞）。 適用范圍：無序線性表、線性表的鏈式存儲結構。二分法查找：log2n（最壞）。適用范圍：順序存儲的線性表。1.8排序技術交換類排序：冒泡排序法：n(n-1)/2（最壞） 快速排序法：n(n-1)/2（最壞） O(nlog2n)（平均）插入類

9、排序：簡單插入排序法：n(n-1)/2（最壞） 希爾排序法：O(n1. 5)（最壞）選擇類排序：簡單選擇排序法：n(n-1)/2（最壞） 堆排序法：O(nlog2n) （最壞）第2章程序設計基礎2.1程序設計方法與風格程序設計風格：清晰第一，效率第二注釋一般分為：序言性注釋和功能性注釋2.2結構化程序設計結構化程序設計的原則：自頂向下，逐步求精，模塊化，限制使用 goto 語句結構化程序的基本結構：順序結構、選擇結構、重復結構（循環結構）2.3面向對象的程序設計面向對象方法的優點：與人類習慣的思維方法一致、穩定性好、可重用性好（主要考慮）、易于開發大型軟件產品、可維護性好面向對象思想中的三個主

10、要特征是：封裝性、繼承性、多態性。對象：客觀世界中的任何實體。 *對象是屬性和方法的封裝體。 *對象是類的一個實例。對象特點：標志唯一性、分類性、多態性、封裝性（信息隱蔽是通過對象的封裝性來實現的）、模塊獨立性好類：具有共同屬性、共同方法的對象的集合。消息：是一個實例與另一個實例之間傳遞的信息，請求對象執行某一處理或回答某一要求的信息，它統一了數據流和控制流。繼承：能夠直接獲得已有的性質和特性，而不必重復定義他們。 *類的繼承性是類之間共享屬性和操作的機制。繼承性的優點：相似的對象可以共享程序的代碼和數據結構,從而大大減少了程序中的冗余信息,提高軟件的可重用性,便于軟件修改維護多態性：是指同樣

11、的消息被不同的對象接受時可導致完全不同的行動的現象。第3章軟件工程基礎3.1軟件工程基本概念軟件：包括程序、數據及相關文檔的完整集合。 *軟件按功能分為：應用軟件、系統軟件、支撐軟件（或工具軟件）軟件工程概念的出現源自軟件危機。軟件危機：是泛指在計算機軟件的開發和維護過程中所遇到的一系列嚴重問題。 *軟件危機歸結為成本、質量、生產率等問題。 軟件工程：是應用于計算機軟件的定義、開發和維護的一整套方法、工具、文檔、實踐標準和工序。軟件工程的目的：1.軟件開發技術：軟件開發方法學、開發過程、開發工具和軟件工程環境。（主體內容：軟件開發方法學） 2.軟件工程管理：軟件管理學、軟件工程經濟學、軟件心理

12、學。軟件工程3要素：方法（完成軟件工程項目的技術手段）、工具（支持軟件的開發、管理、文檔、生成）、過程（支持軟件開發的各個環節的控制、管理）*軟件工程過程：是把輸入轉化為輸出的一組彼此相關的資源和活動。*軟件工程基本活動： P(Plan)軟件規格說明、D (Do)軟件開發、C(Check)軟件確認、A(Action)軟件演進軟件生命周期：將軟件產品從提出、實現、使用維護到停止使用退役的過程。軟件生命周期分為：軟件定義、軟件開發、軟件運行和維護（花費時間最長）*軟件定義：可行性研究與計劃制定（軟件開發費用）、需求分析（確定軟件系統功能）*軟件開發：1.軟件設計（概要設計和詳細設計）、2.軟件實現

13、（軟件開發工具）、3.軟件測試*軟件開發方法（分析方法、設計方法、程序設計方法）*軟件維護活動包括：改正性維護、適應性維護、完善性維護和預防性維護。軟件工程需要達到的基本目標應是：付出較低的開發成本、達到要求的軟件功能、取得較好的軟件性能、開發的軟件易于移植、需要較低的維護費用、能按時完成開發，及時交付使用軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗證性*軟件開發工具、軟件開發環境（或稱軟件工程環境是全面支持軟件開發全過程的軟件工具集合）*軟件開發模型包括：瀑布模型、快速原型法模型、螺旋模型3.2結構化分析方法軟件需求：是指用戶對目標軟件系統在功能、行為、性能、設

14、計約束等方面的期望。需求分析的任務：發現需求、求精、建模和定義需求的過程需求分析的工作：需求獲取、需求分析、編寫規格需求說明書、需求評審需求分析方法：結構化分析方法（面向數據結構的Jackson方法）、面向對象的分析方法（靜態分析方法和動態分析方法）結構化分析方法：是使用數據流圖(DFD)、數據字典(DD)、結構化英語、判定表、判定樹等工具，來建立一種新的、稱為結構化規格說明的目標文檔。 結構化分析的常用工具：數據流圖（DFD：描述數據處理過程的工具）、數據字典（DD：結構化分析方法的核心）、判定樹、判定表*數據流圖以圖形的方式描繪數據在系統中流動和處理的過程，它反映了系統必須完成的邏輯功能圓

15、圈：加工（轉換） 箭頭：數據流 兩條橫線：存儲文件 矩形：源，潭軟件需求規格說明書：是需求分析階段的最后成果，是軟件開發中的重要文檔之一。*軟件需求規格說明書的作用：便于用戶、開發人員進行理解和交流、反映出用戶問題的結構，可以作為軟件開發工作的基礎和依據、 作為確認測試和驗收的依據*軟件需求規格說明書的特點：正確性、無歧義性（最重要）、完整性、可驗證性、一致性、可理解性、可修改性、可追蹤性3.3結構化設計方法軟件設計從技術觀點看，軟件設計包括軟件結構設計、數據設計、接口設計、過程設計軟件設計從工程管理角度看，軟件設計分兩步完成：概要設計和詳細設計軟件設計的基本原理：抽象、模塊化 、信息隱蔽、模

16、塊獨立性 *衡量軟件獨立性依據：耦合性（是模塊間互相連接的緊密程度的度量）內聚性（是一個模塊內部各個元素間彼此結合的緊密程度的度量）*內聚：偶然內聚、邏輯內聚、時間內聚、過程內聚、通信內聚、順序內聚、功能內聚*耦合：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數據耦合、非直接耦合*優秀的軟件設計應做到“高內聚，低耦合”。 模塊劃分的原則：模塊內具有高內聚度，模塊間具有低耦合度。與結構化需求分析方法對應的是結構化設計方法。*常用的軟件結構設計工具是結構圖（程序結構圖）。其中箭頭表示模塊間的調用關系。典型的數據流類型有兩種：變換型和事務型。詳細設計的任務，是為軟件結構圖中的每一個模塊確定實現

17、算法和局部數據結構，用某種選定的工具表示算法和數據結構的細節。常見的過程設計工具：1.圖形工具（程序流程圖、NS、PAD：問題分析圖、HIPO）、2.表格工具（判定表）、3.語言工具（PDL：偽碼、過程設計語言）*程序流程圖是一種傳統的、應用廣泛的軟件過程設計表示工具，通常也稱為程序框圖。程序流程圖表達直觀、清晰，易于學習掌握，且獨立于任何一種程序設計語言。構成程序流程圖的最基本的圖符及含義如下：箭頭表示控制流 矩形表示加工步驟；菱形表示邏輯條件N-S圖：為了避免流程圖在描述程序邏輯時的隨意性與靈活性，提出了用方框圖代替傳統的程序流程圖，通常也把這種圖稱為NS圖。3.4軟件測試軟件測試的目的：

18、是為了發現錯誤而執行程序的過程 軟件測試的準則：所有測試都應追溯到需求、嚴格執行測試計劃，排除測試的隨意性、充分注意測試中的群集現象、程序員應避免檢查自己的程序、窮舉測試不可能（測試只能證明程序中有錯誤，不能證明程序中沒有錯誤）、妥善保存測試計劃、測試用例、出錯統計和最終分析報告，為維護提供方便軟件測試的方法：靜態測試和動態測試：設計設計高效合理的測試用例（輸入值集，輸出值集）（包括白盒測試和黑盒測試）白盒測試：也稱結構測試或邏輯測試。根據程序的內部邏輯來設計，主要用軟件的單元測試*白盒測試的基本原則：保證所側模塊中每一獨立路徑至少執行一次（窮舉路徑測試） *白盒測試的方法：邏輯覆蓋測試（語句

19、、路徑、判定、條件、判斷條件覆蓋）、基本路徑測試黑盒測試：也稱功能測試或數據驅動測試。根據程序的功能說明來設計，主要用軟件的確認測試 *黑盒測試的方法：等價類劃分法、邊界值分析法、錯誤推測法、因果圖軟件測試的過程：單元測試（發現可能的錯誤）、集成測試、確認測試（驗證軟件是否滿足了需求規格說明中確定的各種需求）、系統測試3.5程序的調試程序調試的任務：診斷和改正程序中的錯誤（主要在開發階段）。 軟件測試是盡可能多地發現軟件中的錯誤。程序調試的基本步驟：錯誤定位、糾正錯誤（修改設計和代碼，以排除錯誤）、回歸測試（進行回歸測試，防止引進新的錯誤）程序調試的方法：強行排錯發、回溯法、原因排除法第4章數

20、據庫設計基礎4.1數據庫系統的基本概念1.數據：是描述事物的符號記錄。有型和值之分。2.數據庫(DB)：數據的集合。 *數據庫中的數據具有“集成”、“共享”的特點。3.數據庫管理系統(DBMS)：是一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等。 是數據庫系統的核心，位于用戶和操作系統（OS）之間。*DBMS功能：數據模式定義、數據存取的物理構建、數據操縱、數據的完整性、安全性定義與檢查、數據庫的并發控制與故障恢復、數據的服務。*數據定義語言（DDL）：負責數據的模式定義與數據的物理存取構建。*數據操縱語言（DML）：負責數據的操作，包括查詢及增、刪、改等操作

21、。*數據控制語言（DCL）：負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等功能。4.數據庫管理員（DBA）：數據庫設計、數據庫維護、改善系統性能，提高系統效率。5.數據庫系統（DBS）：數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）6.數據庫應用系統（DBAS）：是數據庫系統再加上應用軟件及應用界面這三者所組成。*數據庫管理經歷階段：人工管理階段、文件系統階段、數據庫系統階段（共享性高，冗余度小）數據庫系統基本特點：數據的集成性、數據的高共享性與低冗余性、數據獨立性（物理獨立性與邏輯獨立性）、數據統一管理與控制*物理獨立性：數據的物

22、理結構（包括存儲結構和存取方式等）的改變，不影響數據庫的邏輯結構，從而不致引起應用程序的變化。*邏輯獨立性：數據庫總體邏輯結構的改變，如修改數據模式、增加新的數據類型等，不需要相應修改應用程序。數據庫系統三級模式：概念模式：全體用戶（應用）公共數據視圖、外模式：子模式、用戶模式，用戶的數據視圖、內模式：物理模式數據庫系統二級映射：概念模式到內模式的映射（保證數據物理獨立性）、外模式到概念模式的映射（保證數據邏輯獨立性）4.2數據模型數據模型描述的內容：數據結構、數據操作、數據約束數據模型分類：概念數據模型（ER模型即實體聯系模型）、邏輯數據模型(層次模型、網狀模型、關系模型)、物理數據模型ER模型基本概念：實體：現實世界中的事物、屬性：事物的特性、