1.1算法
1.1算法的基本概念（P1-P4）
所謂算法，是指對解的準確、完整的描述。
1.算法的基本特征
（1）可行性（2）確定性（3）貧困性（4）充分的信息。
2.算法的基本要素
壹個算法通常由兩個基本元素組成:壹個是數據對象的操作和運算，另壹個是算法的控制結構。
（1）算法中數據的算術和運算（插入和刪除）。
②算法的控制結構
壹個算法通常可以由三個基本控制結構組成:順序、選擇和循環。
1.1.2算法復雜度（P4-P6）
算法的復雜度主要包括時間復雜度和空間復雜度。
1.算法的時間復雜度
所謂算法的時間復雜度是指執行算法所需的計算工作量。
算法的工作量可以通過算法執行期間所需的基本操作的數量來衡量。
3.算法的空間復雜度
算法的空間復雜度通常指執行該算法所需的內存空間。
1.2數據結構的基本概念
數據結構，主要研究和討論以下三個方面:
①數據的邏輯結構；
②數據的存儲結構；
③對各種數據結構的操作。（插入、刪除）
主要目的是提高數據處理效率。所謂提高數據處理效率主要包括兩個方面:壹是提高數據處理速度，二是盡可能節省數據處理時占用的計算機存儲空間。（空間復雜性）
什麽是數據結構（P6-P11）？
1.數據的邏輯結構
數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。
2.數據存儲結構
數據的邏輯結構在計算機存儲空間中的存儲形式稱為數據的存儲結構（也稱為數據的物理結構）。
壹個數據的邏輯結構可以根據需要表現為各種存儲結構，常用的存儲結構有順序、鏈接、索引等。然而，不同的存儲結構處理數據的效率是不同的。
1.2.3線性結構和非線性結構（P12）
通常，數據分為兩種類型:線性結構和非線性結構。
線性結構也稱為線性表。
如果壹個數據結構不是線性的，它被稱為非線性結構。
1.3線性表及其順序存儲結構
1.3.1線性表的基本概念（P12—P13）
線性表是由n（n≥0）個數據元素組成的有限序列a1，a2，...，安。表中的每個數據元素除了第壹個只有壹個前因，除了最後壹個只有壹個後果。即線性表或空表，也可以表示為。
（a1，a2，…，ai，…，an）
非空線性表具有以下結構特征:
①只有壹個根節點a1，沒有前件；
（2）只有壹個端點an，它沒有後綴；
③除了根節點和終端節點外，其他所有節點都有且只有壹個前因和壹個後果。
1.3.2線性表的順序存儲結構（P13—P14）
在計算機中存儲線性表的最簡單方法之壹是順序存儲，也稱為順序分配。
線性表的順序存儲結構有以下兩個基本特征:
①線性表中所有元素占用的存儲空間是連續的；
②線性表中的數據元素按邏輯順序存儲在存儲空間中。
假設線性表中第壹個數據元素的存儲地址為ADR（a 1），每個數據元素占用k個字節，則線性表中第I個元素ai在計算機存儲空間中的存儲地址為
ADR（a 1）= ADR（a 1）+（I-1）K
1.3.3序列表的插入操作（P14—P15）
平均而言，要在線性表格中插入新元素，需要移動表格中壹半的元素。因此，在線性表順序存儲的情況下插入新元素是低效的。
1.3.4序列表刪除操作（P15—P16）
平均來說，要刪除線性表中的壹個元素，需要移動表中壹半的元素。因此，在線性表順序存儲的情況下，刪除壹個元素是低效的。
從存儲結構下線性表的插入和刪除操作可以看出，線性表的順序存儲結構適用於小型線性表或元素不經常變化的線性表，因為順序存儲結構相對簡單。但是，這種順序存儲方法不適合元素經常需要更改的大型線性表，因為插入和刪除的效率相對較低。
1.4堆棧和隊列
1.4.1堆棧及其基本操作（P16—P18）
1.什麽是堆棧
堆棧僅限於壹端用於插入和刪除，另壹端稱為堆棧的底部。即堆棧按照“FILO”或“LIFO”的原則組織數據，因此堆棧也稱為“LIFO”表或“LIFO”表。可以看出，堆棧具有記憶功能。
2.堆棧順序存儲及其操作（具有順序存儲結構的堆棧稱為順序堆棧）。
棧的基本操作有三種:棧入口、棧出口和棧頂元素讀取。
（1）堆棧入口操作（2）堆棧出口操作（3）讀取堆棧的頂部元素
1.4.2隊列及其基本操作（P18—P20）
1.什麽是隊列
隊列是壹個線性表，壹端允許插入，另壹端允許刪除。允許插入的末端稱為隊列的末端，通常有壹個指針稱為末端指針（後置）指向隊列的末端元素，末端稱為隊列的頭部（也稱為隊列頭）通常有壹個前置指針指向頭部元素的前壹個位置。
隊列被稱為“先進先出”或“後進先出”線性表。
3.循環隊列及其操作
在實際應用中，隊列的順序存儲結構壹般采用循環隊列的形式。
所謂循環隊列就是將隊列存儲空間的最後壹個位置環繞在第壹個位置周圍，形成壹個邏輯環形空間供隊列循環使用。
（1）入隊操作
②退出運行
1.5線性鏈表
1.5.1線性鏈表的基本概念（P20—P23）
由於線性表順序存儲結構的上述缺點，對於大型線性表，尤其是元素變化頻繁的大型線性表，不宜采用順序存儲結構，而應采用下面要介紹的鏈式存儲結構。
在鏈式存儲模式下，要求每個節點由兩部分組成:壹部分用於存儲數據元素的值，稱為數據字段；另壹部分用於存儲指針，稱為指針字段。
在鏈式存儲結構中，用於存儲數據結構的存儲空間可以是連續的，每個數據節點的存儲順序可以與數據元素之間的邏輯關系不壹致，數據元素之間的邏輯關系由指針字段確定。
鏈式存儲可用於表示線性和非線性結構。
1.線性鏈表
線性表的鏈式存儲結構稱為線性鏈表。
2.帶鏈堆棧
棧也是線性表，也可以采用鏈式存儲結構。
3.帶鏈隊列
與堆棧類似，隊列也是壹個線性表，它也可以采用鏈式存儲結構。
1.5.2線性鏈表的基本操作（P23—P25）
在插入線性鏈表的過程中，數據元素不移動，只需要改變相關節點的指針，提高了插入的效率。
從線性鏈表的刪除過程可以看出，在線性鏈表中刪除壹個元素後，不需要移動表的數據元素，只需要改變被刪除元素之前的節點的指針字段。
1.5.3循環鏈表及其基本操作（P25—P26）
循環鏈表有以下兩個特點:
（1）循環鏈表中添加了壹個頭節點，指針字段指向線性鏈表第壹個元素的節點。循環鏈表的頭指針指向頭節點。
（2）循環鏈表中最後壹個節點的指針字段不為空，而是指向header節點。也就是說，在循環鏈表中，所有節點的指針形成了壹個循環鏈。
1.6樹和二叉樹
1.6.1樹的基本概念（P26—P28）
在樹結構中，每個節點只有壹個前件，稱為父節點，只有壹個沒有前件的節點，稱為樹的根節點。
在樹形結構中，每個節點可以有多個後繼節點，這些後繼節點被稱為節點的子節點。沒有後繼節點的節點稱為葉節點。
在樹結構中，壹個節點擁有的剩余部分的數量稱為該節點的度。
在樹中，所有節點中最大的度稱為樹的度。
根節點位於第1層。
樹的最高級別稱為樹的深度。
1.6.2二叉樹及其基本性質（P28-P31）
1.什麽是二叉樹？
二叉樹有以下兩個特征:
①非空二叉樹只有壹個根節點；
②每個節點最多有兩個子樹，分別稱為該節點的左子樹和右子樹。
2.二叉樹的基本性質
屬性1在二叉樹的第K層，最多有2K-1（K≥1）個節點。
性質2深度為m的二叉樹最多有2m-1個節點。
屬性3在任何二叉樹中，度為0的節點（即葉節點）總是比度為2的節點多壹個。
3.完全二叉樹和完全二叉樹
（1）完全二叉樹
所謂全二叉樹是指這樣壹種二叉樹:除了最後壹層以外，每層上的所有節點都有兩個子節點，也就是說，在全二叉樹中，每層的節點數達到最大值，即全二叉樹的第k層有2K-1個節點，深度為m的全二叉樹有2m-1個節點。
②完全二叉樹
所謂完全二叉樹是指這樣壹種二叉樹:除最後壹層外，每層節點數達到最大；在最後壹層，只有右邊的幾個節點缺失。
完全二叉樹也是完全二叉樹，完全二叉樹壹般不是完全二叉樹。
屬性6讓壹棵完整的二叉樹* * *有n個節點。從根節點開始，按照順序對自然數為1，2，…n的節點進行編號，對於編號為k（k = 1，2，…n）的節點得出以下結論:
（1）如果k=1，則該節點是根節點，並且它沒有父節點；如果k & gt1，這個節點的父節點號是INT（k/2）。
（2）如果2k≤n，編號為k的節點的左子節點號為2k；否則，該節點沒有左子節點。
（3）如果2k+1≤n，則編號為k的節點的右子節點號為2k+1；否則，該節點沒有右子節點。
1.6.3二叉樹（P31—P32）的存儲結構
在計算機中，二叉樹通常采用鏈式存儲結構。
1.6.4二叉樹的遍歷（P32—P33）
二叉樹遍歷可以分為三種類型:前序遍歷、中間遍歷和後序遍歷。
1.序遍歷（DLR）
2.中值遍歷性（LDR）
3.後序列遍歷（LRD）
1.7搜索技術
1.7.1順序搜索（P33）
順序搜索也稱為順序搜索。
對於大型線性表，順序搜索的效率很低。雖然順序搜索的效率不高，但它只能用於以下兩種情況:
（1）如果線性表是無序的，那麽順序存儲結構和鏈式存儲結構都只能按順序搜索。
（2）即使是有序線性表，如果采用鏈式存儲結構，也只能按順序查找。
1.7.2二分法搜索（P33—P34）
二分法查找僅適用於順序存儲的有序表。
顯然，當有序線性表按順序存儲時，可以使用二分搜索法，並且二分搜索法的效率遠遠高於順序搜索。可以證明，對於長度為n的有序線性表，在最壞的情況下，二分搜索法只需要比較log2n次，而順序搜索需要比較n次。
1.8排氣和充電技術
1.8.1交換排序法（P34—P35）
1.氣泡分選法
冒泡排序是交換類最簡單的排序方法。
假設線性表的長度為n，在最壞的情況下，冒泡排序所需的比較次數為n（n-1）/2。
2.快速分類方法
快速排序方法也是壹種可互換類的排序方法，但它被稱為快速排序方法，因為它比冒泡排序方法更快。
1.8.2插入類排序方法（P35—P37）
1.簡單插入排序法
自以為插入排序是指將無序序列中的每個元素依次插入到有序線性表中。
在簡單插入排序方法中，這種排序方法的效率與冒泡排序方法相同。在最壞的情況下，證券交易的插入排序需要n（n-1）/2次比較。
2.希爾分類方法
希爾排序法屬於插入排序，但它大大改進了簡單插入排序。
1.8.3選擇類排序方法（P37—P38）
1.簡單選擇排序法
選擇最小的元素並將其切換到表格的前面。
簡單選擇排序法在最壞的情況下需要比較n（n-2）/2次。
2.堆分類方法
堆排序法屬於選擇類的排序方法。
堆排序方法不適用於小型線性表，但對於大型線性表非常有效。
分享到搜狐微博
第2章編程基礎（P40—P45）
2.1編程方法和風格
壹般來說，編程的風格應該強調簡單明了，程序必須易於理解。可以認為“清晰第壹，效率第二”的著名論點已經成為當今占主導地位的編程風格。
記錄源程序應考慮以下幾點:
（1）符號名的命名:符號名的命名應具有壹定的實際意義，以便於理解程序功能。
（2）節目評論:正確的評論可以幫助讀者理解節目。註釋壹般分為前言註釋和功能註釋。
（3）視覺組織:為了使程序的結構壹目了然，可以在程序中使用空格、空行和縮進等技巧，使程序層次清晰。
2.2結構化程序設計
2.2.1結構化程序設計原理（P41—P42）
結構化編程方法的主要原則可以概括為自頂向下、逐步細化、模塊化和限制使用goto語句。
2.2.2結構化程序的基本結構和特征（P42—P43）
1.序列結構
2.選擇結構:選擇結構也稱為分支結構。
3.重復結構:重復結構也叫循環結構。
2.3面向對象編程
今天，面向對象方法已經發展成為主流的軟件開發方法。
壹些著名的面向對象語言（如C++、Java）
2.3.2面向對象方法的基本概念（P45—P48）
1.目標
對象是面向對象方法中最基本的概念。壹個對象可以用來表示客觀世界中的任何實體。
面向對象編程方法中涉及的對象由壹組表示其靜態特征的屬性和壹組可以執行的操作組成。
④封裝。
2.類別和實例
將具有相似屬性和操作的對象分類為類，即類是具有* * *相同屬性和* * *相同方法的對象的集合。因此，類是對象的抽象，而對象是其對應類的實例。
3.新聞
對象之間的這種相互協作需要壹種機制的協助，這種機制被稱為“消息”。消息是在壹個實例和另壹個實例之間傳遞的信息。
4.遺產
繼承是面向對象方法的壹個主要特征。
第3章軟件工程基礎
3.1軟件工程的基本概念
3.1.1軟件定義和軟件功能（P50）
計算機軟件是程序、數據和相關文檔的完整集合。
可見軟件由兩部分組成:壹部分是機器可執行文件和程序及數據；第二，與機器不可執行的軟件開發、操作、維護和使用相關的文檔。
軟件的功能:
①軟件是邏輯實體，不是物理實體，是抽象的。
②軟件的生產不同於硬件的生產，沒有明顯的生產過程。
③軟件在運行和使用過程中不存在磨損和老化問題。
④軟件的開發和運行依賴於計算機系統並受其限制，這導致了軟件移植的問題。
⑤軟件復雜且昂貴。
⑥軟件開發涉及許多社會因素。
3.1.2軟件危機和軟件工程（P51-P52）
軟件工程的概念起源於軟件危機。
20世紀60年代末以後，出現了“軟件危機”。所謂軟件危機是指計算機軟件在開發和維護過程中遇到的壹系列嚴重問題。
1968年，在北大西洋公約組織會議（北約會議）上，討論了擺脫軟件危機的途徑，首次提出了軟件工程的概念。
軟件工程包括三個要素，即方法、工具和過程。
3.1.3軟件工程過程和軟件生命周期（P52—P53）
2.軟件生存期
通常，軟件產品從呈現、實現、使用和維護到退役的過程稱為軟件生命周期。
3.1.4軟件工程的目標和原則（P53—P54）
1.軟件工程的目標
軟件工程主要包括:軟件開發技術和軟件工程管理。
3.1.5軟件開發工具和軟件開發環境（P54）
1.軟件開發工具（VB、VC++、VFP）
2.軟件開發環境
軟件開發環境或軟件工程環境是完全支持軟件開發全過程的軟件工具的集合。
計算機輔助軟件工程
3.2結構化方法
3.2.1需求分析和需求分析方法（P53—P59）
1.需求分析
（1）需求分析階段工作
需求分析階段的工作可以概括為四個方面:
①需求獲取
②需求分析
（3）編寫需求說明書。
④需求審查
2.需求分析方法
常見的需求分析方法有:
①結構化方法。主要包括:數據流結構化方法（SA）、數據結構Jackson方法（JSD）、數據結構結構化數據系統開發方法（DSSD）。
②面向對象的分析方法
3.2.2結構化方法（P55—P59）
2.結構化分析的常用工具
（1）數據流圖（DFD）
②數據字典
數據字典是結構化方法的核心。
③決策樹
④決策表
3.2.3軟件要求規範（P59—P60）
軟件規格說明是需求分析的最終結果，是軟件開發中的重要文檔。
軟件需求規格的作用是:
①便於用戶和開發人員理解和交流。
②反映用戶問題的結構，可以作為軟件開發的基礎和依據。
③作為確認測試和驗收的依據。
3.3結構化設計方法
3.3.1軟件設計的基本概念（P60—P62）
1.軟件設計基礎
軟件設計分兩步完成:總體設計和詳細設計。
2.軟件設計的基本原則
（1）摘要
②模塊化
③信息隱藏
④模塊獨立性
模塊的獨立程度是評價設計質量的重要尺度。為了度量軟件的模塊獨立性，使用了兩個定性度量:耦合和內聚。
內聚性:內聚性是模塊中元素相互結合緊密程度的度量。
②耦合度:耦合度是衡量模塊之間互連緊密程度的指標。
耦合和內聚是模塊獨立性的兩個定性標準，耦合和內聚是相互關聯的。在程序結構中，各個模塊的內聚性越強，耦合性越弱。壹般來說，優秀的軟件設計應該盡量實現高內聚和低耦合。
詳細設計（P67—P71）
幾個主要工具:
1.程序流程圖
2.南北向（箱線圖）
3.PAD diagram PAD diagram是問題分析圖的英文縮寫。
4.PDL
過程設計語言（PDL）也稱為結構化英語和偽代碼。
3.4軟件測試
軟件測試的投入通常占軟件開發總工作量和成本的40%以上。
軟件測試是保證軟件質量的重要手段，其主要過程涵蓋了整個軟件生命周期。
軟件測試的目的（P71）
關於軟件測試的目的，軟件測試是為了發現錯誤而執行程序的過程。
3.4.3軟件測試技術和方法概述（P71—P77）
它可以分為靜態測試和動態測試方法。根據功能可分為白盒測試和黑盒測試方法。
1.靜態測試和動態測試
（1）靜態測試
靜態測試可以手動完成，充分發揮人的邏輯思維優勢。
②動態測試
靜態測試並不實際運行軟件，而是主要手動進行。動態測試是壹種基於計算機的測試，是壹種執行程序以發現錯誤的過程。
2.白盒測試
白盒測試方法也稱為結構測試或邏輯驅動測試。
3.黑盒測試方法
黑盒測試方法也稱為功能測試或黑盒測試。黑盒測試是測試和驗證軟件實現的功能是否滿足要求。黑盒測試完全忽略了程序的內部和邏輯結構以及內部特征。
3.4.4軟件測試的實施（P77—P80）
軟件測試是保證軟件質量的重要手段。
軟件測試過程通常分四步進行。
1.單元測試
單元測試是檢查模塊（程序單元）正確性的測試，模塊是軟件設計的最小單元。
2.集成測試
集成測試是測試和組裝軟件的過程。
3.確認測試
4.系統試驗
3.5程序調試
3.5.1基本概念（P80—P81）
程序調試的任務是診斷和糾正程序中的錯誤。它不同於軟件測試，軟件測試是在軟件中找到盡可能多的錯誤。
軟件測試貫穿整個軟件生命周期，調試主要在開發階段。
3.5.2軟件調試方法（P81—P82）
1.強制調試方法
2.追溯方法
3.原因排除法
第四章數據庫設計基礎（P84-P111）
4.1數據庫系統的基本概念
4.1.1數據、數據庫和數據庫管理系統（P84—P87）
1.data
數據實際上是描述事物的符號記錄。
2.數據庫?資料庫
數據庫（簡稱DB）是數據的集合。
3.數據庫管理系統
數據庫管理系統是壹種軟件。
數據庫管理系統是數據庫系統的核心。
目前流行的DBMS都是關系型數據庫系統，如微軟的Visual FoxPro和Access。
4.數據庫管理員（簡稱DBA）
5.數據庫系統
數據庫系統（簡稱DBS）由以下部分組成:數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）和系統平臺之壹的軟件平臺（軟件），它們構成了壹個以數據庫為核心的完整的操作實體，稱為數據庫系統。
4.1.2數據庫系統開發（P87—P88）
數據管理的發展經歷了三個階段:人工管理階段、文件系統階段和數據庫系統階段。
1.關系數據庫系統階段
數據管理三個階段的比較
手動管理文件系統數據庫系統
沒有* * *享受特色數據。
冗余大，觀賞性差
冗余和享受都很棒。
低冗余
數據獨立性不是獨立的，它完全依賴於較差的程序獨立性。它具有高度的物理獨立性和壹定程度的邏輯獨立性。
4.1.3數據庫系統的基本特性（P88—P890
該數據庫系統具有以下特征:
1.數據集成
2.高* * *享受和低數據冗余
3.數據獨立性
數據獨立是數據和程序之間的相互依賴。數據獨立壹般分為兩個層次:物理獨立和邏輯獨立。
（1）物理獨立:物理獨立意味著數據物理結構的改變，從而不會引起應用程序的改變。
（2）邏輯獨立性:當數據庫的整體邏輯結構發生變化時，應用程序不需要進行相應的修改，這就是數據的邏輯獨立性。
4.統壹的數據管理和控制
4.1.4數據庫系統內部結構體系（P89-P91）
1.數據庫系統的三層模式
（1）概念模式。概念模式是數據庫系統中全局數據邏輯結構的描述，是所有用戶（應用程序）的公共數據視圖。
②外部模式。外部模式也稱為子模式或用戶模式。它是用戶的數據視圖。
③內部模式。內部模式也稱為物理模式，它給出了數據庫的物理存儲結構和物理訪問方法。
2.數據庫系統的兩級映射
（1）從概念模式映射到內部模式。
（2）外部圖式到概念圖式的映射。
4.2數據模型
數據模型的基本概念（P91）
根據不同的應用層次，數據模型分為三種類型:概念數據模型、邏輯模型、物理數據模型，
概念模型包括E-R模型和邏輯數據模型，也稱為數據模型。
分層模型、網格模型、關系模型，
物理數據模型也稱為物理模型。
1.2.2 E-R型號（P91—P95）
概念模型是E-R模型（或實體聯系模型）。
1的基本概念。E-R模型
（1）實體
現實世界中的事物可以抽象成實體。
②屬性
現實世界有壹些特征，可以用屬性來表示。屬性描述實體的特征。
⑶聯系方式
壹對壹聯系人，縮寫為1: 1。
壹對多或多對壹連接，縮寫為1:m（1:m）或m:1（m:1）。
多對多接觸，簡單的高度就是m: n或者m:n。
3.E-R模型的圖解法
屬性在E-R圖中用省略號表示。
這種聯系在E-R圖中用菱形表示。
4.2.3層次模型的基本結構是樹形結構（P95）。
4.2.4網格模型（P95—P96）
網格模型是沒有任何條件的無向圖。
4.2.5關系模型（P96—P98）
1.關系的數據結構
關系模型由二維表表示。
4.3關系代數
⑷調查
①投影操作
②選擇操作
③笛卡爾積運算
然後用笛卡爾積將r和S的關系記為R×S。
3.關系代數中的擴張運算
（1）交集運算（和與差）
R和S之間的關系由同時在R和S中的那些階組成，記為R ∩ S..
⑵除運算
如果笛卡爾乘積運算被視為乘法運算，那麽除運算就是它的運算。
T÷R=S或R/R=S
4.4數據庫設計和管理
數據庫設計是數據庫應用核心。
4.4.1數據庫設計概述（P104）
整個數據庫應用系統的開發分為幾個具有獨立目標的階段。它們是:需求分析階段、概念設計階段、邏輯設計階段和物理設計階段。
4.4.2數據庫設計需求分析（P104—P105）
4.4.3數據庫的概念設計（繪制E-R圖）（P105—P108）
4.4.4數據庫的邏輯設計（P108—P109）
1.從E-R圖到關系模式的轉換。
4.4.5數據庫的物理設計（P110）