大學(xué)計算機基礎(chǔ)案例教程課件第7章

1、第7章 公共基礎(chǔ)知識算法的基本概念?；緮?shù)據(jù)結(jié)構(gòu)及其操作?；九判蚝筒檎宜惴?。逐步求精的結(jié)構(gòu)化程序設(shè)計方法。軟件工程的基本方法,具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)的能力。數(shù)據(jù)庫的基本知識,了解關(guān)系數(shù)據(jù)庫的設(shè)計。主要知識點7.1.1 算法1.算法的基本概念（1）概念：算法是指解決方案的準(zhǔn)確而完整的描述。（2）基本特征：可行性、確定性、有窮性、擁有足夠的情報。（3）基本要素：對數(shù)據(jù)對象的運算和操作、算法的控制結(jié)構(gòu)（運算和操作時間的順序）。2.算法復(fù)雜度（1）時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量。（2）空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.1.2

2、 數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。2.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)，是反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示為多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存?種方式。3.數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，用方框表示數(shù)據(jù)結(jié)點，用一條有向線段表示數(shù)據(jù)結(jié)點的前后件關(guān)系。4.線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)按各元素之間前后關(guān)系的復(fù)雜程度可劃分為線性

3、結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)有且只有一個根節(jié)點,且每個節(jié)點最多有一個直接前驅(qū)和一個直接后續(xù)的非空數(shù)據(jù)結(jié)構(gòu)；非線性結(jié)構(gòu)是不滿足線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.1.3 線性表及其順序存儲結(jié)構(gòu)1.線性表的定義線性結(jié)構(gòu)又稱線性表，線性表是最簡單也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是由n（n=0）個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。2.線性表的順序存儲結(jié)構(gòu)元素所占的存儲空間必須連續(xù)，元素在存儲空間的位置是按邏輯順序存放的。3.線性表的插入運算4.線性表的刪除運算第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)

4、構(gòu)與算法7.1.4 棧和隊列1. 棧和隊列的定義棧是一種特殊的線性表，其插入運算與刪除運算都只在線性表的一端進行，也被稱為(先進后出)表或(后進先出)表。隊列是指允許在一端進行插入，在另一端進行刪除的線性表，又稱(先進先出)的線性表。2.棧的基本運算棧的基本運算有三種：入棧、退棧與讀棧頂元素。第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.1.5 線性鏈表在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表。在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié)

5、點（即前件或后件）。第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.1.6 數(shù)和二叉樹1.樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)，樹中有且僅有一個沒有前驅(qū)的節(jié)點稱為“根”，其余節(jié)點分成m個互不相交的有限集合T1、T2、，Tm，每個集合又是一棵樹，稱 T1、T2、，Tm為根結(jié)點的子樹。父節(jié)點：每一個節(jié)點只有一個前件，無前件的節(jié)點只有一個，稱為樹的根結(jié)點（簡稱樹的根）。子節(jié)點：每一個節(jié)點可以有多個后件，無后件的節(jié)點稱為葉子節(jié)點。樹的度：所有節(jié)點最大的度。樹的深度：樹的最大層次。2.二叉樹的定義及其基本性質(zhì)3.二叉樹的存儲結(jié)構(gòu)4.二叉樹的遍歷第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.1.7 查找技術(shù)

6、1.順序查找順序查找又稱順序搜索，一般是指在線性表中查找指定的元素。在最壞情況下，最后一個元素才是要找的元素，對于長度為n的有序線性表，需要比較n次。2.二分法查找二分法查找也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制，它要求表必須用順序存儲結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序（升序或降序均可）排列。對長度為n的有序線性表，在最壞情況下，二分查找法只需比較log2n次。第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.1.8 排序技術(shù)1.交換類排序法（1）冒泡排序法（2）快速排序法2.插入類排序法（1）簡單插入排序法（2）希爾排序法3.選擇類排序法（1）簡單選擇排序法（2）堆排序的方法

7、第7章 公共基礎(chǔ)知識7.1 數(shù)據(jù)結(jié)構(gòu)與算法7.2.1 程序設(shè)計方法與風(fēng)格1.設(shè)計方法程序設(shè)計方法指設(shè)計、編制、調(diào)試程序的方法和過程，主要有結(jié)構(gòu)化程序設(shè)計方法、軟件工程方法和面向?qū)ο蠓椒ā?.設(shè)計風(fēng)格良好的設(shè)計風(fēng)格要注重源程序文檔化、數(shù)據(jù)說明方法、語句的結(jié)構(gòu)和輸入輸出。第7章 公共基礎(chǔ)知識7.2 程序設(shè)計基礎(chǔ)7.2.2 結(jié)構(gòu)化程序設(shè)計1.結(jié)構(gòu)化程序設(shè)計的原則結(jié)構(gòu)化程序設(shè)計強調(diào)程序設(shè)計風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。（1）自頂向下（2）逐步求精（3）模塊化（4）限制使用 GoTo語句2.結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點（1）順序結(jié)構(gòu)（2）選擇結(jié)構(gòu)（3）循環(huán)結(jié)構(gòu)第7章 公共基礎(chǔ)知識7.2 程序設(shè)計

8、基礎(chǔ)7.2.3 面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蠓椒ǖ谋举|(zhì)是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，強調(diào)建立的系統(tǒng)能映射問題域。面向?qū)ο蠓椒ǖ幕靖拍畎ǎ簩ο螅河脕肀硎究陀^世界中任何實體，是對問題域中某個實體的抽象。類：具有共同屬性、共同方法的對象的集合。實例：一個具體對象就是其對應(yīng)分類的一個實例。消息：實例間傳遞的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。繼承：使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)，廣義的講，繼承就是指能夠直接獲得已有的性質(zhì)和特征，不必重新定義。多態(tài)性：指對象根據(jù)所接受的信息而作出動作，同樣的信息被不同的對象接收時有不同行動的現(xiàn)象。第7章 公共基礎(chǔ)知識7.2 程序設(shè)計基礎(chǔ)7.3.1 軟

9、件工程基本概念1.軟件的定義與特點（1）定義軟件是與計算機系統(tǒng)的操作有關(guān)的計算機程序、規(guī)則及相關(guān)文檔的完整集合。（2）特點2.軟件的分類3.軟件危機與軟件工程4.軟件生命周期5.軟件工程的原則第7章 公共基礎(chǔ)知識7.3 軟件工程基礎(chǔ)7.3.2 結(jié)構(gòu)化分析方法需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過程，可概括為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審。1.常用的分析方法（1）結(jié)構(gòu)化分析方法。（2）面向?qū)ο蠓治龇椒ā?.結(jié)構(gòu)化分析常用工具結(jié)構(gòu)化分析常用工具包括:（1）數(shù)據(jù)流圖（2）數(shù)據(jù)字典（3）判定樹（4）判定表3.軟件需求規(guī)格說明書第7章 公共基礎(chǔ)知識7.3 軟件工程基礎(chǔ)7.3

10、.3 結(jié)構(gòu)化設(shè)計方法1.軟件設(shè)計的基本概念和方法軟件設(shè)計是一個把軟件需求轉(zhuǎn)換為軟件表示的過程。（1）基本原理：抽象、逐步求精和模塊化、信息隱蔽和局部化、模塊獨立性。（2）基本思想：將軟件設(shè)計成由相對獨立、單一功能的模塊組成的結(jié)構(gòu)。2.概要設(shè)計（1）基本任務(wù)：設(shè)計軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計、編寫概要設(shè)計文檔、概要設(shè)計文檔評審。（2）面向數(shù)據(jù)流的設(shè)計方法：數(shù)據(jù)流圖的信息分為變換流和事物流，結(jié)構(gòu)形式有變換型和事務(wù)型。3.詳細(xì)設(shè)計常見的過程設(shè)計工具有：圖形工具：程序流程圖、N-S圖、PAD圖、HIPO圖表格工具：判定表語言工具：PDL（偽碼）第7章 公共基礎(chǔ)知識7.3 軟件工程基礎(chǔ)7.3.4

11、軟件測試1.目的軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。2.準(zhǔn)則3.軟件測試技術(shù)和方法（1）白盒測試（2）黑盒測試4.軟件測試的實施第7章 公共基礎(chǔ)知識7.3 軟件工程基礎(chǔ)7.3.5 程序的調(diào)試（1）任務(wù)：診斷和改正程序中的錯誤。（2）調(diào)試方法：強行排錯法、回溯法和原因排除法。第7章 公共基礎(chǔ)知識7.3 軟件工程基礎(chǔ)7.4.1 數(shù)據(jù)庫系統(tǒng)的基本概念1.數(shù)據(jù):數(shù)據(jù)是描述事物的符號記錄。2.數(shù)據(jù)庫:數(shù)據(jù)庫是長期存儲在計算機內(nèi)的、有組織的、可共享的數(shù)據(jù)集合。3.數(shù)據(jù)庫管理系統(tǒng)的概念:數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心，它位于用戶和操作系統(tǒng)之間，從軟件分類的角度來說，屬于系統(tǒng)軟件。4.數(shù)據(jù)庫技術(shù)的發(fā)展數(shù)

12、據(jù)庫技術(shù)發(fā)展經(jīng)歷了3個階段：人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段。5.數(shù)據(jù)庫系統(tǒng)的特點集成性、高共享性與低冗余性、數(shù)據(jù)獨立性、數(shù)據(jù)統(tǒng)一管理與控制等。6.數(shù)據(jù)庫系統(tǒng)的內(nèi)部機構(gòu)體系三級模式（概念級模式、內(nèi)模式、外模式）和二級映射（外模式到概念級模式的映射、概念級模式到內(nèi)模式的映射）構(gòu)成了數(shù)據(jù)庫系統(tǒng)內(nèi)部的抽象結(jié)構(gòu)體系。第7章 公共基礎(chǔ)知識7.4 數(shù)據(jù)庫設(shè)計基礎(chǔ)7.4.2 數(shù)據(jù)模型目前較為成熟的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型、關(guān)系模型和面向?qū)ο竽Ｐ汀?.E-R模型 E-R模型提供了表示實體、屬性和聯(lián)系的方法。實體間聯(lián)系有“一對一”、“一對多”和“多對多”。E-R模型用E-R圖來表示。2.層次模型層次模

13、型利用樹形結(jié)構(gòu)表示實體及其之間聯(lián)系，其中節(jié)點是實體，樹枝是聯(lián)系，從上到下是一對多關(guān)系。3.網(wǎng)狀模型網(wǎng)狀模型用網(wǎng)狀結(jié)構(gòu)表示實體及其之間聯(lián)系，是層次模型的擴展。網(wǎng)絡(luò)模型以記錄型為節(jié)點，反映現(xiàn)實中較為復(fù)雜的事物聯(lián)系。4.關(guān)系模型關(guān)系模型采用二維表(由表框架和表的元組組成)來表示，可進行數(shù)據(jù)查詢、增加、刪除及修改操作。關(guān)系模型允許定義“實體完整性”、“參照完整性”和“用戶定義的完整性”三種約束。第7章 公共基礎(chǔ)知識7.4 數(shù)據(jù)庫設(shè)計基礎(chǔ)7.4.3 關(guān)系代數(shù)關(guān)系是由若干個不同的元素所組成，因此關(guān)系可視為元素的集合。(1)關(guān)系模型的基本運算:插入、刪除、修改、查詢；(2)關(guān)系代數(shù)中的擴充運算：交、除、連接及自然連接。第