第一章 數據結構與算法
1.1 算法
1.算法的基本概念
(1) 概念:算法是指一系列解決問題的清晰指令。
(2) 4個基本特征:可行性、确定性、有窮性、擁有足夠的情報。
(3) 兩種基本要素:對數據對象的運算和操作、算法的控制結構(運算和操作時問的順序)。
(4) 設計的基本方法:列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。
2.算法的複雜度
(1) 算法的時間複雜度:執行算法所需要的計算工作量。
(2) 算法的空間複雜度:執行算法所需的内存空間。
1.2 數據結構的基本概念
數據結構指相互有關聯的數據元素的集合,即數據的組織形式。其中邏輯結構反映數據元素之間邏輯關系;存儲結構為數據的邏輯結構在計算機存儲空間中的存放形式,有順序存儲、鍊式存儲、索引存儲和散列存儲4種方式。
數據結構按各元素之間前後件關系的複雜度可劃分為:
(1) 線性結構:有且隻有一個根節點,且每個節點最多有一個直接前驅和一個直接後繼的非空數據結構。
(2) 非線性結構:不滿足線性結構的數據結構。
1.3 線性表及其順序存儲結構
1.線性表的基本概念
線性結構又稱線性表,線性表是最簡單也是最常用的一種數據結構。
2.線性表的順序存儲結構
元素所占的存儲空間必須連續。
元素在存儲空間的位置是按邏輯順序存放的。
3.線性表的插入運算
在第i個元素之前插入一個新元素的步驟如下:
步驟一:把原來第n個節點至第i個節點依次往後移一個元素位置。
步驟二:把新節點放在第i個位置上。
步驟三:修正線性表的節點個數。
在最壞情況下,即插入元素在第一個位置,線性表中所有元素均需要移動。
4.線性表的删除運算
删除第i個位置的元素的步驟如下:
步驟一:把第i個元素之後不包括第i個元素的n-i個元素依次前移一個位置;
步驟二:修正線性表的結點個數。
1.4 棧和隊列
1.棧及其基本運算
(1) 基本概念:棧是一種特殊的線性表,其插入運算與删除運算都隻在線性表的一端進行,也被稱為“先進後出”表或“後進先出”表。
棧頂:允許插入與删除的一端。
棧底:棧頂的另一端。
空棧:棧中沒有元素的棧。
(2) 特點。
棧頂元素是最後被 插入和最早被删除的元素。
棧底元素是最早被 插入和最後被删除的元素。
棧有記憶作用。
在順序存儲結構下,棧的插入和删除運算不需移動表中其他數據元素。
棧頂指針top動态反映了棧中元素的變化情況
(3) 順序存儲和運算:入棧運算、退棧運算和讀棧頂運算。
2.隊列及其基本運算
(1) 基本概念:隊列是指允許在一端進行插入,在另一端進行删除的線性表,又稱“先進先出”的線性表。
隊尾:允許插入的一端,用尾指針指向隊尾元素。
排頭:允許删除的一端,用頭指針指向頭元素的前一位置。
(2) 循環隊列及其運算。
所謂循環隊列,就是将隊列存儲空間的最後一個位置繞到第一個位置,形成邏輯上的環狀空間。
入隊運算是指在循環隊列的隊尾加入一個新元素。
當循環隊列非空(s=1)且隊尾指針等于隊頭指針時,說明循環隊列已滿,不能進行人隊運算,這種情況稱為“上溢”。
退隊運算是指在循環隊列的隊頭位置退出一個元素并賦給指定的變量。首先将隊頭指針進一,然後将排頭指針指向的元素賦給指定的變量。當循環隊列為空(s=0)時,不能進行退隊運算,這種情況稱為“下溢”。
1.5 線性鍊表
在定義的鍊表中,若隻含有一個指針域來存放下一個元素地址,稱這樣的鍊表為單鍊表或線性鍊表。
在鍊式存儲方式中,要求每個結點由兩部分組成:一部分用于存放數據元素值,稱為數據域;另一部分用于存放指針,稱為指針域。其中指針用于指向該結點的前一個或後一個結點(即前件或後件)。
1.6 樹和二叉樹
1.樹的基本概念
樹是簡單的非線性結構,樹中有且僅有一個沒有前驅的節點稱為“根”,其餘節點分成m個互不相交的有限集合T1,T2,…,T}mm,每個集合又是一棵樹,稱T1,T2,…,T}mm為根結點的子樹。
父節點:每一個節點隻有一個前件,無前件的節點隻有一個,稱為樹的根結點(簡稱樹的根)。
子節點:每~個節點可以後多個後件,無後件的節點稱為葉子節點。
樹的度:所有節點最大的度。
樹的深度:樹的最大層次。
2.二叉樹的定義及其基本性質
(1) 二叉樹的定義:二叉樹是一種非線性結構,是有限的節點集合,該集合為空(空二叉樹)或由一個根節點及兩棵互不相交的左右二叉子樹組成。可分為滿二叉樹和完全二叉樹,其中滿二叉樹一定是完全二叉樹,但完全二叉樹不一定是滿二叉樹。二叉樹具有如下兩個特點:
二叉樹可為空,空的二叉樹無節點,非空二叉樹有且隻有一個根結點;
每個節點最多可有兩棵子樹,稱為左子樹和右子樹。
(2) 二叉樹的基本性質。
性質1:在二叉樹的第k層上至多有2k-1個結點(k≥1)。
性質2:深度為m的二叉樹至多有2m-1個結點。
性質3:對任何一棵二叉樹,度為0的結點(即葉子結點)總是比度為2的結點多一個。
性質4:具有n個結點的完全二叉樹的深度至少為[log2n] 1,其中[log2n]表示log2n的整數部分。
3.滿二叉樹與完全二叉樹
(1) 滿二叉樹:滿二叉樹是指這樣的一種二叉樹:除最後一層外,每一層上的所有結點都有兩個子結點。滿二叉樹在其第i層上有2i-1個結點。
從上面滿二叉樹定義可知,二叉樹的每一層上的結點數必須都達到最大,否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個結點。
(2) 完全二叉樹:完全二叉樹是指這樣的二叉樹:除最後一層外,每一層上的結點數均達到最大值;在最後一層上隻缺少右邊的若幹結點。
如果—棵具有n個結點的深度為k的二叉樹,它的`每—個結點都與深度為k的滿二叉樹中編号為1~n的結點——對應。
3.二叉樹的存儲結構
二叉樹通常采用鍊式存儲結構,存儲節點由數據域和指針域(左指針域和右指針域)組成。二叉樹的鍊式存儲結構也稱二叉鍊表,對滿二叉樹和完全二叉樹可按層次進行順序存儲。
4.二叉樹的遍曆
二叉樹的遍曆是指不重複地訪問二叉樹中所有節點,主要指非空二叉樹,對于空二叉樹則結束返回。二叉樹的遍曆包括前序遍曆、中序遍曆和後序遍曆。
(1) 前序遍曆。
前序遍曆是指在訪問根結點、遍曆左子樹與遍曆右子樹這三者中,首先訪問根結點,然後遍曆左子樹,最後遍曆右子樹;并且,在遍曆左右子樹時,仍然先訪問根結點,然後遍曆左子樹,最後遍曆右子樹。前序遍曆描述為:若二叉樹為空,則執行空操作;否則①訪問根結點;②前序遍曆左子樹;③前序遍曆右子樹。
(2) 中序遍曆。
中序遍曆是指在訪問根結點、遍曆左子樹與遍曆右子樹這三者中,首先遍曆左子樹,然後訪問根結點,最後遍曆右子樹;并且,在遍曆左、右子樹時,仍然先遍曆左子樹,然後訪問根結點,最後遍曆右子樹。中序遍曆描述為:若二叉樹為空,則執行空操作;否則①中序遍曆左子樹;②訪問根結點;③中序遍曆右子樹。
(3) 後序遍曆。
後序遍曆是指在訪問根結點、遍曆左子樹與遍曆右子樹這三者中,首先遍曆左子樹,然後遍曆右子樹,最後訪問根結點,并且,在遍曆左、右子樹時,仍然先遍曆左子樹,然後遍曆右子樹,最後訪問根結點。後序遍曆描述為:若二叉樹為空,則執行空操作;否則①後序遍曆左子樹;②後序遍曆右子樹;③訪問根結點。
1.7 查找技術
(1) 順序查找:在線性表中查找指定的元素。
(2) 最壞情況下,最後一個元素才是要找的元素,則需要與線性表中所有元素比較,比較次數為n。
(3) 二分查找:二分查找也稱折半查找,它是一種高效率的查找方法。但二分查找有條件限制,它要求表必須用順序存儲結構,且表中元素必須按關鍵字有序(升序或降序均可)排列。對長度為n的有序線性表,在最壞情況下,二分查找法隻需比較log2n次。
1.8 排序技術
(1) 交換類排序法。
冒泡排序:通過對待排序序列從後向前或從前向後,依次比較相鄰元素的排序碼,若發現逆序則交換,使較大的元素逐漸從前部移向後部或較小的元素逐漸從後部移向前部,直到所有元素有序為止。在最壞情況下,對長度為n的線性表排序,冒泡排序需要比較的次數為n(n-1)/2。
快速排序:是迄今為止所有内排序算法中速度最快的一種。它的基本思想是:任取待排序序列中的某個元素作為基準(一般取第一個元素),通過一趟排序,将待排元素分為左右兩個子序列,左子序列元索的排序碼均小于或等于基準元素的排序碼,右子序列的排序碼則大于基準元素的排序碼,然後分别對兩個子序列繼續進行排序,直至整個序列有序。最壞情況下,即每次劃分,隻得到一個序列,時間效率為O(n2)。
(2) 插人類排序法。
簡單插入排序法:把n個待排序的元素看成為一個有序表和一個無序表,開始時有序表中隻包含一個元素,無序表中包含有n-1個元素,排序過程中每次從無序表中取出第一個元素,把它的排序碼依次與有序表元素的排序碼進行比較,将它插入到有序表中的适當位置,使之成為新的有序表。在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。
希爾排序法:先将整個待排元素序列分割成若幹個子序列(由相隔某個“增量”的元素組成的)分别進行直接插入排序。待整個序列中的元素基本有序(增量足夠小)時,再對全體元素進行一次直接插入排序。
(3) 選擇類排序法。
簡單選擇排序法:掃描整個線性表。從中選出最小的元素。将它交換到表的最前面;然後對剩下的子表采用同樣的方法,直到子表空為止。最壞情況下需要比較n(n-1)/2次。
堆排序的方法:首先将一個無序序列建成堆;然後将堆頂元素(序列中的最大項)與堆中最後一個元素交換(最大項應該在序列的最後)。不考慮已經換到最後的那個元素,隻考慮前n-1個元素構成的子序列,将該子序列調整為堆。反複做步驟②,直到剩下的子序列空為止。在最壞情況下,堆排序法需要比較的次數為0(nlog2n)
第二章 程序設計基礎
2.1 程序設計方法與風格
(1)設計方法:指設計、編制、調試程序的方法和過程,主要有結構化程序設計方法、軟件工程方法和面向對象方法。
(2)設計風格:良好的設計風格要注重源程序文檔化、數據說明方法、語句的結構和輸入輸出。
2.2 結構化程序設計
1.結構化程序設計的原則
結構化程序設計強調程序設計風格和程序結構的規範化,提倡清晰的結構。。
(1)自頂向下:即先考慮總體,後考慮細節;先考慮全局目标,後考慮局部目标。
(2)逐步求精:對複雜問題,應設計一些子目标做過渡,逐步細化。
(3)模塊化:把程序要解決的總目标分解為分目标,再進一步分解為具體的小目标,把每個小目标稱為一個模塊;
(4)限制使用GOT0語句。
2.結構化程序的基本結構與特點
(1)順序結構:自始至終嚴格按照程序中語句的先後順序逐條執行,是最基本、最普遍的結構形式。
(2)選擇結構:又稱為分支結構,包括簡單選擇和多分支選擇結構。
(3)重複結構:又稱為循環結構,根據給定的條件,判斷是否需要重複執行某一相同的或類似的程序段。
結構化程序設計中,應注意事項:
(1)使用程序設計語言中的順序、選擇、循環等有限的控制結構表示程序的控制邏輯。
(2)選用的控制結構隻準許有一個人口和一個出口。
(3)程序語言組成容易識别的塊,每塊隻有一個入口和一個出口。
(4)複雜結構應該用嵌套的基本控制結構進行組合嵌套來實現。
(5)語言中所沒有的控制結構,應該采用前後一緻的方法來模拟。
(6)盡量避免GOT0語句的使用。
2.3 面向對象的程序設計
面向對象方法的本質是主張從客觀世界固有的事物出發來構造系統,強調建立的系統能映射問題域。
對象:用來表示客觀世界中任何實體,可以是任何有明确邊界和意義的東西。
類:具有共同屬性、共同方法的對象的集合。
實例:一個具體對象就是其對應分類的一個實例。
消息:實例間傳遞的信息,它統一了數據流和控制流。
繼承:使用已有的類定義作為基礎建立新類的定義技術。
多态性:指對象根據所接受的信息而作出動作,同樣的信息被不同的對象接收時有不同行動的現象。面向對象程序設計的優點:與人類習慣的思維方法一緻、穩定性好、可重用性好、易于開發大型軟件産品、可維護性好。
第三章 軟件工程基礎
3.1 軟件工程基本概念
1.軟件的定義與特點
(1)定義:軟件是指與計算機系統的操作有關的計算機程序、規程、規則,以及可能有的文件、文檔和數據。
(2)特點。
是邏輯實體,有抽象性。
生産沒有明顯的制作過程。
運行使用期間不存在磨損、老化問題。
開發、運行對計算機系統有依賴性,受計算機系統的限制,導緻了軟件移植問題。
複雜性較高,成本昂貴。
開發涉及諸多社會因素。
2.軟件的分類
軟件可分應用軟件、系統軟件和支撐軟件3類。
(1)應用軟件是特定應用領域内專用的軟件。
(2)系統軟件居于計算機系統中最靠近硬件的一層,是計算機管理自身資源,提高計算機使用效率并為計算機用戶提供各種服務的軟件。
(3)支撐軟件介于系統軟件和應用軟件之間,是支援其它軟件的開發與維護的軟件。
3.軟件危機與軟件工程
軟件危機指在計算機軟件的開發和維護中遇到的一系列嚴重問題。軟件工程是應用于計算機軟件的定義、開發和維護的一整套方法、工具、文檔、實踐标準和工序,包括軟件開發技術和軟件工程管理。
4.軟件生命周期
軟件産品從提出、實現、使用維護到停止使用的過程稱為軟件生命周期。
在國家标準中,軟件生命周期劃分為8個階段①軟件定義期:包括問題定義、可行性研究和需求分析3個階段。②軟件開發期:包括概要設計、詳細設計、實現和測試4個階段。③運行維護期:即運行維護階段。
5.軟件工程的原則
軟件工程的原則包括:抽象、信息隐蔽、模塊化、局部化、确定性、一緻性、完備性和可驗證性。
3.2 結構化分析方法
需求分析的任務是發現需求、求精、建模和定義需求的過程,可概括為:需求獲取、需求分析、編寫需求規格說明書和需求評審。
1.常用的分析方法
結構化分析方法:其實質着眼于數據流,自頂向下,逐層分解,建立系統的處理流程。
面向對象分析方法。
2.結構化分析常用工具
結構化分析常用工具包括數據流圖、數字字典(核心方法)、判斷樹和判斷表。
(1)數據流圖:即DFD圖,以圖形的方式描繪數據在系統中流動和處理的過程,它隻反映系統必須完成的邏輯功能。是一種功能模型。
符号名稱作用:
箭頭代表數據流,沿箭頭方向傳送數據的通道
圓或橢圓代表加工,輸入數據經加工變換産生輸出
雙杠代表存儲文件,表示處理過程中存放各種數據文件
方框代表源和潭,表示系統和環境的接口
(2)數據字典:結構化分析方法的核心。數據字典是對所有與系統相關的數據元素的一個有組織的列表。以及精确的、嚴格的定義,使得用戶和系統分析員對于輸入、輸出、存儲成分和中間計算結果有共同的理解。
(3)判定樹:使用判定樹進行描述時,應先從問題定義的文字描述中分清判定的條件和判定的結論,根據描述材料中的連接詞找出判定條件之問的從屬關系、并列關系、選擇關系,根據它們構造判定樹。
(4)判定表:與判定樹相似,當數據流圖中的加工要依賴于多個邏輯條件的取值,即完成該加工的一組動作是由于某一組條件取值的組合引發的,使用判定表比較适宜。
3.軟件需求規格說明書
軟件需求規格說明書是需求分析階段的最後成果,是軟件開發的重要文檔之一。
(1)軟件需求規格說明書的作用:①便于用戶、開發人員進行理解和交流;②反映出用戶問題的結構,可以作為軟件開發工作的基礎和依據;③作為确認測試和驗收的依據。
(2)軟件需求規格說明書的内容:①概述;②數據描述;③功能描述;④性能描述;⑤參考文獻;⑥附錄。
(3)軟件需求規格說明書的特點:①正确性;②無歧義性;③完整性;④可驗證性;⑤一緻性;⑥可理解性;⑦可修改性;⑧可追蹤性。
3.3 結構化設計方法
1.軟件設計的基本概念和方法
軟件沒計是一個把軟件需求轉換為軟件表示的過程。
(1)基本原理:抽象、模塊化、信息隐藏、模塊獨立性(度量标準:耦合性和内聚性,高耦合、低内聚)。
(2)基本思想:将軟件設計成由相對獨立、單一功能的模塊組成的結構。
2.概要設計
(1)4個任務:設計軟件系統結構、數據結構及數據庫設計、編寫概要設計文檔、概要設計文檔評審。
(2)面向數據流的設計方法:數據流圖的信息分為交換流和事物流,結構形式有交換型和事務型。
3.詳細設計的工具
詳細設計的工具包括:
圖形工具:程序流程圖、N-S、PAD、HIPO。
表格工具:判定表。
語言工具:PDL(僞碼)。
3.4 軟件測試
1.目的
為了發現錯誤而執行程序的過程。
2.準則
所有測試應追溯到用戶需求。
嚴格執行測試計劃,排除測試的随意性。
充分注意測試中的群集現象。
程序員應避免檢查自己的程序。
窮舉測試不可能。
妥善保存設計計劃、測試用例、出錯統計和最終分析報告。
3.軟件測試技術和方法
軟件測試的方法按是否需要執行被測軟件的角度,可分為靜态測試和動态測試,按功能分為白盒測試和黑盒測試。
(1)白盒測試:根據程序的内部邏輯設計測試用例,主要方法有邏輯覆蓋測試、基本路徑測試等。
(2)黑盒測試:根據規格說明書的功能來設計測試用例,主要診斷方法有等價劃分法、邊界值分析法、錯誤推測法、因果圖法等,主要用于軟件确認測試。
4.軟件測試的實施
軟件測試是保證軟件質量的重要手段,軟件測試是一個過程,其測試流程是該過程規定的程序,目的是使軟件測試工作系統化。
軟件測試過程分4個步驟,即單元測試、集成測試、驗收測試和系統測試。
單元測試是對軟件設計的最小單位——模塊(程序單元)進行正确性檢驗測試。
單元測試的目的是發現各模塊内部可能存在的各種錯誤。
單元測試的依據是詳細的設計說明書和源程序。
單元測試的技術可以采用靜态分析和動态測試。
3.5 程序的調試
(1)任務:診斷和改正程序中的錯誤。
(2)調試方法:強行排錯法、回溯法和原因排除法。
第四章 數據庫設計基礎
4.1 數據庫系統的基本概念
(1) 數據(Data):描述事物的符号記錄。
(2) 數據庫(DataBase):長期存儲在計算機内的、有組織的、可共享的數據集合。
(3) 數據庫管理系統的概念
數據庫管理系統(DataBase Management System,DBMS)是數據庫的機構,它是一種系統軟件,負責數據庫中的數據組織、數據操作、數據維護、數據控制及保護和數據服務等。為完成以上6個功能,DBMS提供了相應的數據語言;數據定義語言(負責數據的模式定義與數據的物理存取構建);數據操縱語言(負責數據的操縱);數據控制語言(負責數據完整性、安全性的定義)。數據庫管理系統是數據庫系統的核心,它位于用戶和操作系統之間,從軟件分類的角度來說,屬于系統軟件。
(4) 數據庫技術發展經曆了3個階段。
人工管理階段→文件系統階段→數據庫系統階段
(5) 數據庫系統的特點:集成性、高共享性、低冗餘性、數據獨立性、數據統一管理與控制等。
(6) 數據庫系統的内部機構體系:三級模式(概念模式、内模式、外模式)和二級映射(外模式/概念模式的映射、概念模式/内模式的映射)構成了數據庫系統内部的抽象結構體系。
4.2 數據模型
數據模型是數據特征的抽象,從抽象層次上描述了系統的靜态特征、動态行為和約束條件,描述的内容有數據結構、數據操作和數據約束。有3個層次:概念數據模型、邏輯數據模型和物理數據模型。
(1) E—R模型:提供了表示實體、屬性和聯系的方法。實體間聯系有“一對一”、“一對多”和“多對多”。
(2) 層次模型:利用樹形結構表示實體及其之問聯系。其中節點是實體,樹枝是聯系,從上到下是一對多關系。
(3) 網狀模型:用網狀結構表示實體及其之間聯系。是層次模型的擴展。網絡模型以記錄型為節點,反映現實中較為複雜的事物聯系。
(5) 關系模型:采用二維表(由表框架和表的元組組成)來表示,可進行數據查詢、增加、删除及修改操作。關系模型允許定義“實體完整性”、“參照完整性”和“用戶定義的完整性”三種約束。
鍵(碼):二維表中唯一能标識元組的最小屬性集。
候選鍵(候選碼):二維表中可能有的多個鍵。
主鍵:被選取的一個使用的鍵。
4.3 關系代數
(1) 關系代數的基本運算:投影、選擇、笛卡爾積。
(2) 關系代數的擴充運算:交、連接與自然連接、除。
4.4 數據庫設計與管理
1.數據庫設計概述
基本思想:過程叠代和逐步求精。
方法:面向數據的方法和面向過程的方法。
設計過程:需求分析→概念設計→邏輯設計→物理設計→編碼→測試→運行→進→步修改。
2.數據庫設計的需求分析
需求收集和分析是數據庫設計的第一階段,常用結構化分析方法(自頂向下、逐層分解)和面向對象的方法,主要工作有繪制數據流程圖、數據分析、功能分析、确定功能處理模塊和數據間關系。
數據字典:包括數據項、數據結構、數據流、數據存儲和處理過程,是對系統中數據的詳盡描述。
3.數據庫的設計
(1) 數據庫的概念設計:分析數據問内在的語義關聯,以建立數據的抽象模型。
(2) 數據庫的邏輯設計:從E-R圖向關系模型轉換,邏輯模式規範化,關系視圖設計可以根據用戶需求随時創建。實體轉換為元組,屬性轉換為關系的屬性,聯系轉換為關系。
(3) 數據庫的物理設計:是數據在物理設備上的存儲結構與存取方法,目的是對數據庫内部物理結構作出調整并選擇合理的存取路徑,以提高速度和存儲空間。
4.數據庫管理
數據庫管理包括數據庫的建立、數據庫的調整、數據庫的重組、數據庫的安全性與完整性控制、數據庫故障恢複和數據庫的監控。
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!