第1章數據結構和算法
1.1算法
算法:指對解決方案的準確和完整描述。
算法不等於程序，也不等於計算機方法，所以編程不可能比算法設計更好。
算法的基本特征:它是壹組嚴格定義操作順序的規則，並且每個規則都是有效和明確的，並且這個順序將在有限的次數內終止。功能包括:
（1）可行性；
（2）確定性，算法中的每壹步都必須明確定義，不允許有模棱兩可的解釋和歧義；
（3）存在有限性，算法必須在有限時間內完成，即執行有限步數後即可終止，包括合理執行時間的含義；
（4）掌握足夠的信息。
算法的基本要素:壹是數據對象的運算和操作；第二是算法的控制結構。
指令集:計算機系統可以執行的所有指令的集合。
基本運算和操作包括:算術運算、邏輯運算、關系運算和數據傳輸。
算法的控制結構:順序結構、選擇結構和循環結構。
算法的基本設計方法有枚舉法、歸納法、遞歸法、遞歸法、桶縮減遞歸技術和回溯法。
算法復雜度:算法時間復雜度和算法空間復雜度。
算法的時間復雜度是指執行算法所需的計算工作量。
算法空間復雜度是指執行該算法所需的內存空間。
1.2數據結構的基本概念
數據結構研究的三個方面:
（1）數據集中數據元素之間的內在邏輯關系，即數據的邏輯結構；
（2）處理數據時，計算機中各數據元素的存儲關系，即數據的存儲結構；
（3）各種數據結構的操作。
數據結構是指相互關聯的數據元素的集合。
數據的邏輯結構包括:
（1）表示數據元素的信息；
②表示數據元素之間的關系。
數據的存儲結構包括順序、鏈接、索引等。
線性結構條件:
（1）有且只有壹個根節點；
（2）每個節點最多有壹個前片和壹個後片。
非線性結構:不滿足線性結構條件的數據結構。
1.3線性表及其順序存儲結構
線性表由壹組數據元素組成，數據元素的位置僅取決於它們自己的序列號，元素之間的相對位置是線性的。
在復雜的線性表中，由多個數據元素組成的數據元素稱為記錄，而由多個記錄組成的線性表也稱為文件。
非空線性表的結構特征；
（1）並且只有壹個根節點a1，它沒有前件；
（2）只有壹個終端節點an，它沒有後置部分；
（3）除了根節點和終端節點之外，所有其他節點都有且只有壹個前件和壹個後件。節點數n稱為線性表的長度，當n=0時稱為空表。
線性表的順序存儲結構有以下兩個基本特征:
線性表中所有元素占用的存儲空間是連續的；
（2）線性表中的數據元素按邏輯順序存儲在存儲空間中。
ai的存儲地址為:ADR（AI）= ADR（a 1）+（I-1）k，其中ADR（a 1）是第壹個元素的地址，k表示每個元素占用的字節數。
序列表的操作:插入和刪除。（詳情請參見第14-16頁）
1.4堆棧和隊列
Stack是壹個線性表，只有壹端用於插入和刪除。允許插入和刪除的壹端稱為堆棧的頂部，不允許插入和刪除的另壹端稱為堆棧的底部。
棧按照“FILO”或“LIFO”組織數據，棧具有記憶功能。使用top表示堆棧頂部的位置，使用bottom表示堆棧底部的位置。
棧的基本操作:（1）插入元素稱為棧操作；（2）刪除元素稱為回棧操作；（3）讀取棧頂元素是將棧頂元素賦給指定變量，此時指針不變。
Queue指的是壹個線性表，它允許在壹端（隊列的末端）插入，在另壹端（隊列的頭部）刪除。後指針指向行尾，前指針指向行首。
隊列是FIFO或LILO的線性表。
隊列操作包括（1）入隊操作:從隊列末尾插入壹個元素；（2）退出操作:從隊列頭刪除壹個元素。
循環隊列:s=0表示隊列為空，s=1，front=rear表示隊列已滿。
1.5線性鏈表
數據結構中的每個節點對應壹個存儲單元，稱為存儲節點。
壹個節點由兩部分組成:（1）用於存儲數據元素值，稱為數據字段；（2）用於存儲指針，稱為指針字段，用於指向上壹個節點或下壹個節點。
在鏈式存儲結構中，用於存儲數據結構的存儲空間可以是不連續的，每個數據節點的存儲順序可以與數據元素之間的邏輯關系不壹致，數據元素之間的邏輯關系由指針字段確定。
鏈式存儲可用於表示線性和非線性結構。
對於線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表。如果有兩個指針，左指針（Llink）指向前壹個節點，右指針（Rlink）指向後壹個節點。
線性鏈表的基本操作:查找、插入和刪除。
1.6樹和二叉樹
樹是壹種簡單的非線性結構，所有元素都具有明顯的層次特征。
在樹結構中，每個節點只有壹個前件，稱為父節點，只有壹個沒有前件的節點，稱為樹的根節點。每個節點可以有多個後繼節點，這些後繼節點稱為該節點的子節點。沒有後繼節點的節點稱為葉節點。
在樹結構中，壹個節點所擁有的續集的數量稱為該節點的度，所有節點中最大的度稱為樹的度。樹的最高級別稱為樹的深度。
二叉樹的特征:（1）非空二叉樹只有壹個根節點；（2）每個節點最多有兩個子樹，分別稱為節點的左子樹和右子樹。
二叉樹的基本屬性:
（1）二叉樹的第k層最多有2k-1（k≥1）個節點；
（2）深度為m的二叉樹最多有2m-1個節點；
（3）度為0的節點（即葉節點）總是比度為2的節點多壹個；
（4）具有n個節點的二叉樹，其深度至少為【log2n】+1，其中【log2n】表示log2n的整數部分；
（5）n個節點的完全二叉樹的深度為【log2n】+1；
（6）設壹棵完整的二叉樹* * *有n個節點。如果從根節點開始，節點編號為自然數1，2，...n按照順序（每層從左到右）（k = 1，2...n），得出以下結論:
（1）如果k=1，則該節點是根節點，並且它沒有父節點；如果k & gt1，該節點的父節點號為int（k/2）；
（2）如果2k≤n，編號為k的節點的左子節點號為2k；否則，該節點沒有左子節點（也沒有右子節點）；
（3）如果2k+1≤n，則編號為k的節點的右子節點號為2k+1；否則，該節點沒有右子節點。
全二叉樹意味著除了最後壹層之外的每壹層上的所有節點都有兩個子節點，因此K層上深度為m的全二叉樹有2k-1個節點和2m-1個節點。
完整的二叉樹是指除最後壹層外，每壹層的節點數達到最大值，最後壹層只缺少右邊的幾個節點。
二叉樹存儲結構采用鏈式存儲結構，全二叉樹和完全二叉樹可以按順序存儲。
二叉樹的遍歷:
（1）前言遍歷（DLR）:首先訪問根節點，然後遍歷左子樹，最後遍歷右子樹；
（2）中間順序遍歷（LDR），首先遍歷左子樹，然後訪問根節點，最後遍歷右子樹；
（3）後序遍歷（LRD）首先遍歷左子樹，然後訪問右子樹，最後訪問根節點。
1.7搜索技術
順序搜索的用法:
（1）線性表是無序的；
（2）表采用鏈式存儲結構。
二分法搜索只適用於按順序存儲的有序表。對於長度為n的有序線性表，在最壞的情況下，它只需要比較log2n次。
1.8排序技術
排序是指將無序序列排序為按值的非降序排列的有序序列。
交換排序法:（1）冒泡排序法，比較次數為n（n-1）/2；（2）快速排序法。
插入排序法:（1）簡單插入排序法，最壞情況下需要n（n-1）/2次比較；（2）希爾排序法，在最壞的情況下需要O（n 1.5）次比較。
選擇排序法:（1）簡單選擇排序法，
最壞的情況需要n（n-1）/2次比較；（2）堆排序方法，在最壞的情況下需要O（nlog2n）次比較。
-
第二章編程基礎
2.1編程設計方法和風格
如何形成良好的編程風格
1，源程序文檔；2.數據解釋方法；
3.陳述的結構；4.輸入和輸出。
註釋分為前言註釋和功能註釋，首先是句子結構清晰，其次是效率。
2.2結構化程序設計
結構化程序設計方法的四個原則是:1。自上而下；2.逐步改善；3.模塊化；4.限制goto語句的使用。
結構化程序的基本結構和特征；
（1）序列結構:簡單的編程，最基本最常用的結構；
（2）選擇結構:又稱分支結構，包括簡單選擇和多分支選擇結構，根據條件選擇哪個分支執行相應的句子序列；
（3）重復結構:又稱循環結構，它可以根據給定的條件判斷是否需要重復執行同壹程序段。
2.3面向對象編程
面向對象程序設計:以奧斯陸大學和挪威計算機中心在20世紀60年代末開發的SIMULA語言為標誌。
面向對象方法的優勢:
（1）與人類使用的思維方法壹致；
②穩定性好；
（3）復用性好；
④易於開發大型軟件產品；
（5）維護性好。
對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是實體的抽象。
面向對象編程方法中的對象是用於描述系統中客觀事物的實體，是系統的基本單元。它由壹組表示其靜態特征的屬性和壹組可以執行的操作組成。
屬性是包含在對象中的信息，操作描述對象執行的功能。操作也稱為方法或服務。
對象的基本特征:
（1）標識唯壹性；
（2）分類；
③多態性；
④封裝；
（5）模塊具有良好的獨立性。
類是指具有* * *相同屬性和* * *相同方法的對象的集合。因此，類是對象的抽象，而對象是相應類的實例。
消息是在壹個實例和另壹個實例之間傳遞的信息。
消息的組成包括（1）接收消息的對象的名稱；（2）消息標識符，也稱為消息名；③零個或多個參數。
繼承是指直接獲得現有屬性和特征的能力，而不必重復定義它們。
繼承分為單繼承和多繼承。單壹繼承意味著壹個類只能有壹個父類，而多重繼承意味著壹個類可以有多個父類。
多態是指同壹條消息被不同的對象接受時會導致完全不同的動作的現象。
-
第三章軟件工程基礎
3.1軟件工程的基本概念
計算機軟件是程序、數據和相關文檔的完整集合。
該軟件的功能包括:
（1）軟件是壹個邏輯實體；
（2）軟件的生產不同於硬件的生產，它沒有明顯的生產過程；
（3）軟件在運行和使用過程中沒有磨損和老化問題；
（4）軟件的開發和運行依賴於計算機系統並受其限制，從而導致軟件移植問題；
（5）軟件復雜昂貴；
（6）軟件開發涉及許多社會因素。
軟件按功能分為應用軟件、系統軟件和支撐軟件（或工具軟件）。
軟件危機主要表現在成本、質量、生產率等問題上。
軟件工程是壹套用於定義、開發和維護計算機軟件的方法、工具、文檔、實踐標準和程序。
軟件工程包括三個要素:方法、工具和過程。
軟件工程過程是壹組將軟件轉化為輸出的相互關聯的資源和活動，包括四個基本活動:
（1）p-軟件規範；
②d-軟件開發；
（3）軟件驗證；
（4）軟件進化。
軟件周期:軟件產品從提出、實現、使用和維護到停止使用和退役的過程。
軟件生命周期有三個階段:軟件定義、軟件開發和運維。主要活動階段包括:
（1）可行性研究及規劃；
②需求分析；
③軟件設計；
（4）軟件實現；
⑤軟件測試；
（6）運行維護。
軟件工程的目標和原則；
目標:在給定成本和進度的前提下，開發具有有效性、可靠性、可理解性、可維護性、可重用性、適應性、可移植性、可追溯性和互操作性的產品，並滿足用戶的需求。
基本目標:支付較低的開發成本；滿足軟件功能要求；獲得更好的軟件性能；開發軟件易於移植；需要更低的成本；能夠按時完成開發並及時交付。
基本原則:抽象性、信息隱蔽性、模塊化、本地化、確定性、壹致性、完整性和可驗證性。
軟件工程的理論和技術研究內容主要包括:軟件開發技術和軟件工程管理。
軟件開發技術包括:軟件開發方法學、開發過程、開發工具和軟件工程環境。
軟件工程管理包括:軟件管理、軟件工程經濟學、軟件心理學等。
軟件管理包括人員組織、進度、質量保證、配置管理、項目規劃等。
軟件工程的原則包括抽象、信息隱藏、模塊化、本地化、確定性、壹致性、完整性和可驗證性。
3.2結構化方法
結構化方法的核心和基礎是結構化程序設計理論。
需求分析方法包括（1）結構化需求分析方法；（2）面向對象分析法。
從需求分析所建立模型的特點來看，分為靜態分析和動態分析。
結構化方法的本質是以數據流為中心，自上而下進行分解，建立系統的處理流程，以數據流圖和數據字典為主要工具建立系統的邏輯模型。
結構化分析的常用工具
（1）數據流圖；（2）數據字典；（3）決策樹；④決策表。
數據流圖:描述數據處理過程的工具，是需求理解邏輯模型的圖形化表示，直接支持系統功能建模。
數據字典:與系統相關的所有數據元素的有組織的列表和精確而嚴格的定義使用戶和系統分析人員對輸入、輸出、存儲組件和中間計算結果有相同的理解。
決策樹:從問題定義的文本描述中區分判斷哪些條件和判斷哪些結論，根據描述材料中的連接詞找出判斷條件之間的從屬關系、並列關系和選擇關系，並根據它們構建決策樹。
決策表:與決策樹類似，當數據流圖中的處理依賴於多個邏輯條件的值時，即完成處理的壹組動作是由壹組條件的值的組合引起的時，用決策表來描述它更合適。
數據字典是結構化分析的核心。
軟件需求規格的特點:
（1）正確性；
（2）沒有歧義；
（3）誠信；
⑷可驗證性；
⑤壹致性；
（6）易懂性；
（7）追溯性。
3.3結構化設計方法
軟件設計的基本目標是以更抽象和概括的方式確定目標系統如何完成預定任務，軟件設計是確定系統的物理模型。
軟件設計是開發階段最重要的步驟，也是將需求準確轉換為完整軟件產品或系統的唯壹方法。
從技術角度來看，軟件設計包括軟件結構設計、數據設計、界面設計和流程設計。
結構設計:定義軟件系統主要組件之間的關系。
數據設計:將分析過程中創建的模型轉換為數據結構的定義。
界面設計:描述軟件如何在內部、軟件與協作系統之間以及軟件與人之間進行通信。
過程設計:將系統結構組件轉換為軟件的過程描述。
從項目管理的角度來看:總體設計和詳細設計。
軟件設計的壹般過程:軟件設計是壹個叠代的過程；壹是進行高層次結構設計；然後進行底層流程設計；穿插數據設計和界面設計。
為了度量軟件模塊的獨立性，使用了兩個定性度量:耦合和內聚。
程序結構中各模塊的內聚性越強，耦合性越弱。優秀的軟件應該具有高內聚和低耦合。
軟件概要設計的基本任務是:
（1）設計軟件系統結構；（2）數據結構和數據庫設計；
③撰寫簡要的設計文檔；（4）審查概要設計文件。
模塊用矩形表示，箭頭表示模塊之間的調用關系。
在結構圖中，您還可以使用帶註釋的箭頭來表示模塊調用期間來回傳遞的信息。您還可以使用實心圓箭頭來表示控制信息已傳輸，空心圓箭頭中心表示數據已傳輸。
結構圖的基本形式:基本形式、順序形式、重復形式和選擇形式。
結構圖中有四種模塊類型:輸入模塊、輸出模塊、轉換模塊和協調模塊。
有兩種典型的數據流類型:轉換類型和事務類型。
變換系統的結構圖由輸入、中心變換和輸出三部分組成。
事務性數據流的特點是:接受壹個事務，根據事務處理的特點和性質選擇和調度合適的處理單元，然後給出結果。
詳細設計:是為軟件結構圖中的各個模塊確定實現算法和局部數據結構，並用壹些選定的表達工具表達算法和數據結構的細節。
常用的工藝設計工具包括:圖形工具（程序流程圖）、表格工具（判斷表）和語言工具（PDL）。
3.4軟件測試
軟件測試的定義:通過手動或自動方式運行或測試系統的過程，其目的是檢查系統是否滿足規定的要求或找出預期結果與實際結果之間的差異。
軟件測試的目的:發現錯誤和執行程序的過程。
軟件測試方法:靜態測試和動態測試。
靜態測試包括代碼檢查、靜態結構分析和代碼質量度量。不實際運行軟件，主要是手工操作。
動態測試:是對計算機基礎的測試，主要包括白盒測試法和黑盒測試法。
白盒測試:在程序內部進行，主要用於驗證軟件的內部操作。主要方法是邏輯覆蓋和基本基本路徑測試。
黑盒測試:主要診斷不正確或省略的功能、接口錯誤、數據結構或外部數據庫訪問錯誤、性能錯誤、初始化和終止條件錯誤，用於軟件驗證。主要方法有等價類劃分、邊界值分析、錯誤推測、因果圖等。
軟件測試過程壹般分四步進行:單元測試、集成測試、驗收測試（確認測試）和系統測試。
3.5程序調試
程序調試的任務是診斷和糾正程序中的錯誤，主要是在開發階段。
程序調試的基本步驟:
（1）定位錯誤；
②修改設計和代碼以消除錯誤；
（3）進行回歸測試以防止引入新的錯誤。
軟件調試可分為靜態調試和動態調試。靜態調試主要是指分析源代碼並通過人的思維進行調試，這是主要的設計手段，而動態調試是壹種輔助的靜態調試。主要的調試方法有:
（1）強制調試方法；
（2）回溯法；
（3）原因排除法。
-
4.1數據庫系統的基本概念
數據:事實上，它是描述事物的符號記錄。
數據的特性:有壹定的結構，有類型和值，如整數、實數和字符。數據的值給出了壹個符合原型的值，例如整數值15。
數據庫:它是數據的集合，具有統壹的結構並存儲在統壹的存儲介質中。它是各種應用程序數據的集成，所有應用程序都可以使用。
存儲在數據庫中的數據是按照數據提供的數據模式存儲的，具有集成和共享的特點。
數據庫管理系統:壹種系統軟件，負責數據庫中的數據組織、數據操作、數據維護、控制和保護以及數據服務，是數據庫的核心。
數據庫管理系統功能:
（1）數據模式定義:即構建數據庫的數據框架；
（2）數據訪問的物理構建:為數據模式的物理訪問和構建提供有效的訪問方法和手段；
（3）數據操作:為用戶使用數據庫中的數據提供方便，如查詢、插入、修改、刪除以及簡單的算術運算和統計；
數據完整性和安全性的定義和檢查；
（5）數據庫並發控制和故障恢復；
（6）數據服務:如復制、傳輸、重組、性能監控和分析。
為了完成上述六個功能，數據庫管理系統提供了以下數據語言:
（1）數據定義語言:負責數據模式定義和數據物理訪問構建；
（2）數據操作語言:負責數據操作，如查詢、增加、刪除和修改；
（3）數據控制語言:負責數據完整性和安全性的定義和檢查、並發控制、故障恢復等。
數據語言根據其用法有兩種結構形式:交互式命令（也稱為獨立或自主語言）宿主語言（壹般嵌入在某些宿主語言中）。
數據庫管理員:負責規劃、設計、維護和監控數據庫的專業管理員。
數據庫系統:由數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）和軟件平臺（軟件）五部分組成的操作實體。
數據庫應用系統:由數據庫系統、應用軟件和應用界面組成。
文件系統階段:提供簡單的數據共享和數據管理功能，但無法提供完整、統壹的管理和數據共享功能。
分層數據庫和網狀數據庫系統階段:為數據的統壹和共享提供了強有力的支持。
關系數據庫系統階段
數據庫系統的基本特征是:數據集成、高數據享受和低冗余、數據獨立（物理獨立和邏輯獨立）、統壹的數據管理和控制。
數據庫系統的三層模式:
（1）概念模式:數據庫系統中全局數據邏輯結構的描述，所有用戶的公共數據視圖；
（2）外部模式:也稱為子模式和用戶模式。是用戶的數據視圖，即用戶看到的數據模式；
（3）內部模式:也稱為物理模式，它給出了數據庫的物理存儲結構和物理訪問方法。
數據庫系統的兩級映射；
（1）概念模式到內部模式的映射；
（2）外部圖式到概念圖式的映射。
4.2數據模型
數據模型的概念是對數據特征的抽象，從抽象層面描述系統的靜態特征、動態行為和約束條件，為數據庫系統的信息表和操作提供抽象框架。描述了數據結構、數據操作和數據約束。
E-R模型的基本概念
（1）實體:現實世界中的事物；
（2）屬性:事物的特征；
（3）聯系:現實世界事物之間的關系。實體集的關系有壹對壹、壹對多和多對多的聯系。
E-R模型三個基本概念之間的聯系:實體是概念世界中的基本單位，屬性具有屬性域，每個實體都可以取屬性域中的值。壹個實體的所有屬性值稱為元組。
E-R模型的圖形表示:（1）實體集表示；（2）屬性表法；（3）聯系表示。
分層模型的基本結構是樹形結構，具有以下特征:
（1）每棵樹有且只有壹個無父節點，稱為根；
（2）樹中除根以外的所有節點只有壹個父節點。
從圖論的角度來看，網格模型是壹個沒有任何條件的無向圖。
關系模型用二維表表示，簡稱表，由表框架和表元組組成。二維表是壹種關系。
能夠在二維表中唯壹標識元組的最小屬性稱為鍵或代碼。從所有候選項中選擇壹個鍵作為用戶的主鍵。如果表A中的屬性是表B的鍵，則屬性集被稱為A的外鍵或外鍵代碼..
關系中的數據約束:
（1）實體完整性約束:約束關系主鍵中的屬性值不能為空；
（2）參照完備性約束:是關系之間的基本約束；
（3）自定義完整性約束:它反映了特定應用中數據的語義要求。
4.3關系代數
關系數據庫系統的特點之壹是以數據理論為基礎，能夠表示關系模型數據操作的數據理論有很多，其中最著名的是關系代數和關系演算。
關系模型的基本操作:
（1）插入（2）刪除（3）修改（4）查詢（包括投影、選擇和笛卡爾積運算）
4.4數據庫設計和管理
數據庫設計是數據應用的核心。
數據庫設計的兩種方法:
（1）數據導向:優先考慮信息需求，兼顧處理需求；
（2）面向流程:優先處理需求，兼顧信息需求。
數據庫的生命周期:需求分析階段、概念設計階段、邏輯設計階段、物理設計階段、編碼階段、測試階段、運行階段和進壹步修改階段。
需求分析常用的方法有結構分析法和面向對象法。結構分析（SA）方法通過自上而下和逐層分解來分析系統。使用數據流圖來表達數據和處理之間的關系。對於數據庫設計，數據字典是詳細數據收集和數據分析的主要結果。
數據字典是各種數據描述的集合，包括五個部分:數據項、數據結構、數據流（數據項或數據結構）、數據存儲和處理。
數據庫概念設計的目的是分析數據的內在語義關系。設計有兩種方式。
（1）集中模式設計法（適用於小型或不復雜的單位或部門）；
（2）視圖集成設計方法。
設計方法:E-R模型和視圖集成。
視圖設計通常有三種設計順序:自上而下、自下而上和自內而外。
視圖集成的幾種沖突:命名沖突、概念沖突、領域沖突和約束沖突。
關系視圖設計:關系視圖的設計也稱為外部模式設計。
關系視圖的主要功能:
（1）提供數據邏輯獨立性；
（2）能夠滿足用戶對數據的不同需求；
（3）具備壹定的數據安全功能。
數據庫物理設計的主要目標是調整數據的內部物理結構並選擇合理的訪問路徑，從而提高數據庫的訪問速度並有效利用存儲空間。壹般來說，在RDBMS中留給用戶參與物理設計的內容是索引設計、集成簇設計和分區設計。
數據庫管理的內容:
（1）數據庫的建立；
②數據庫的調整；
③數據庫的重組；
④數據庫安全和完整性控制；
（5）數據庫故障恢復；
6 .數據庫監控。