大學(xué)計算機(jī)基礎(chǔ)課件第8章 軟件技術(shù)基礎(chǔ)

算法的定義與基本特征

算法是一組有窮指令集，是解題方案的準(zhǔn)確而完整的描述。

基本特征：可行性:算法中的每一步操作都能夠通過執(zhí)行有限次的基本運(yùn)算在有限時間內(nèi)實現(xiàn)。

確定性:算法的每一步操作都必須有確切定義，不得有任何歧義性。有窮性:算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止。輸入:一個算法有n(n≥0)個初始數(shù)據(jù)的輸入。輸出:一個算法有一個或多個與有效信息的輸出。

算法的基本要素數(shù)據(jù)對象的運(yùn)算和操作

通常，一個計算機(jī)系統(tǒng)包含的基本的運(yùn)算和操作有如下四類：算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。邏輯運(yùn)算：主要包括與、或、非等運(yùn)算。關(guān)系運(yùn)算：主要包括大于、小于、等于、不等于等運(yùn)算。數(shù)據(jù)傳輸：主要包括輸入、輸出、賦值等運(yùn)算。算法的控制結(jié)構(gòu)一個算法通常都可以由順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。

8.1.2算法評價的準(zhǔn)則正確性可讀性健壯性算法復(fù)雜度

算法復(fù)雜度

算法的時間復(fù)雜度算法的空間復(fù)雜度8.1.3數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系（即聯(lián)系）的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。記為：

Data_Structure={D，R}

其中，D是數(shù)據(jù)元素的集合，R是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。

數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)(或稱物理結(jié)構(gòu))。

數(shù)據(jù)的邏輯結(jié)構(gòu)

反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，而與它們在計算機(jī)中的存儲位置無關(guān)。

集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)集合線性樹圖

數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)（又稱為物理結(jié)構(gòu)）是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式。順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點(diǎn)由兩部分組成：一部分存儲結(jié)點(diǎn)本身的值，稱為數(shù)據(jù)域；另一部分存儲該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的存儲單元地址，稱為指針域。數(shù)據(jù)域指針域結(jié)點(diǎn)的結(jié)構(gòu)

線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)

非線性結(jié)構(gòu)

線性結(jié)構(gòu)示意圖樹圖8.1.4線性表

線性表是具有相同數(shù)據(jù)類型的n(n≥0)個數(shù)據(jù)元素的有限集(a1，a2，…，an)，每個元素的位置是線性(一維)的。線性表(a1，a2，…，an)的邏輯特征：

有且僅有一個開始結(jié)點(diǎn)a1(無直接前趨)；有且僅有一個終端結(jié)點(diǎn)an(無直接后繼)；其余的結(jié)點(diǎn)ai(1<i<n)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。線性表的兩種結(jié)構(gòu):

順序存儲結(jié)構(gòu)(順序表)

鏈?zhǔn)酱鎯Y(jié)構(gòu)(鏈表)

線性表的順序存儲結(jié)構(gòu)

線性表的順序存儲結(jié)構(gòu)是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個數(shù)據(jù)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的元素存儲在相鄰的物理存儲單元中。可見，線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點(diǎn)：（1）線性表中的所有數(shù)據(jù)元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。順序存儲結(jié)構(gòu)下的線性表操作

線性表的插入線性表的刪除線性表的查找線性表的復(fù)制線性表的排序線性表的分解與合并8.1.5線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，對邏輯上相鄰的數(shù)據(jù)元素不要求其物理位置相鄰。因此，為了表示每個數(shù)據(jù)元素ai與其直接后繼ai+1之間的邏輯關(guān)系，對各個數(shù)據(jù)元素來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。這兩部分信息組成數(shù)據(jù)元素ai的存儲映象，稱為存儲結(jié)點(diǎn)。它包括兩個域：其中存儲數(shù)據(jù)元素本身信息的域稱為數(shù)據(jù)域；存儲其直接后繼存儲位置的域稱為指針域。

8.1.6棧和隊列

棧和隊列是軟件設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和線性表相同，但棧必須按照“先進(jìn)后出”的規(guī)則進(jìn)行操作，隊列必須按照“先進(jìn)先出”的規(guī)則進(jìn)行操作。因此，棧和隊列實際上是運(yùn)算受限制的特殊線性表。

棧

棧是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，又稱為后進(jìn)先出的線性表(LIFO表)，是一種特殊的線性表。表尾稱為棧頂(top)，表頭叫做棧底(bottom)，表中無元素時稱為空棧。進(jìn)棧出棧棧頂棧底ana2a1棧示意圖

棧的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

棧的順序存儲結(jié)構(gòu)又稱順序棧，棧的順序存儲結(jié)構(gòu)又稱順序棧，它用一組連續(xù)的存儲空間依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設(shè)指針top指示棧頂元素的當(dāng)前位置，基本運(yùn)算有下列三種：入棧運(yùn)算出棧運(yùn)算

讀棧頂元素

隊列

插入在表一端進(jìn)行，而刪除在表的另一端進(jìn)行，將這種數(shù)據(jù)結(jié)構(gòu)稱為隊或隊列。

隊列的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊列的基本運(yùn)算有入隊、出隊、取隊頭、判隊列空、插入和刪除等。a2a1a3an出隊列入隊列頭尾隊列的示意8.1.7樹、二叉樹及二叉樹的遍歷

樹的定義二叉樹的定義及基本性質(zhì)二叉樹的存儲

二叉樹的遍歷

樹的定義

樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間的關(guān)系具有明顯的層次特性。下圖表示了一棵一般的樹。

一般的樹ABEKLFCGMDHIJ層次1234

二叉樹的定義

二叉樹（binarytree）也是一種非線性數(shù)據(jù)結(jié)構(gòu)，它類似于樹結(jié)構(gòu)，但在某些方面又不同于樹結(jié)構(gòu)。二叉樹具有以下兩個特點(diǎn)：①非空二叉樹只有一個根結(jié)點(diǎn)；②每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。A只有根結(jié)點(diǎn)的二叉樹ABCDEFGH

深度為4的二叉樹

二叉樹的幾個基本性質(zhì)

性質(zhì)1：在二叉樹第i層上至多有2i–1個結(jié)點(diǎn) (i≥1)。性質(zhì)2：深度為k的二叉樹中，最多有2k–1 個結(jié)點(diǎn)(k≥1)。性質(zhì)3：具有n個結(jié)點(diǎn)的完全二叉樹的深度 是:[log2n]+1。性質(zhì)4：在任意一棵二叉樹中，若其葉子 結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為 n2，則：n0=n2+1。

二叉樹的存儲

二叉樹的存儲通常采用鏈接方式。它是指用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。鏈表中每個結(jié)點(diǎn)由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點(diǎn)左子樹和右子樹所在的鏈結(jié)點(diǎn)的存儲地址。結(jié)點(diǎn)的存儲的結(jié)構(gòu)為：lchilddaterchild

二叉樹的遍歷

先序遍歷法中序遍歷法后序遍歷法

二叉樹的遍歷是指按照一定的次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次，并且只被訪問一次。

二叉樹的遍歷舉例

例：給出如下圖所示的一棵二叉樹，寫出對應(yīng)的遍歷序列。按先序遍歷序列：

ABDHECFGI

按中序遍歷序列：DHBEAFCIG按后序遍歷序列：HDEBFIGCA二叉樹的示例EBADHCFGI8.1.8查找技術(shù)

查找就是在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足條件的結(jié)點(diǎn)。兩種基本的查找方法：

順序查找

二分法查找

順序查找

順序查找一般是在線性表中查找指定的元素，其基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若線性表中的所有元素都與被查元素進(jìn)行了比較但都不相同，則表示線性表中沒有要找的元素，即查找失敗。

順序查找的優(yōu)點(diǎn)是既適用于順序表（即線性表的順序存儲結(jié)構(gòu)），也適用于線性鏈表（即線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)）。

順序查找的缺點(diǎn)是當(dāng)線性表很大時，查找效率很低。順序查找的時間復(fù)雜度為O(n)。

二分法查找

二分法查找的方法是：在有序表中，取中間元素作為比較對象，若給定值與中間元素的關(guān)鍵碼相等，則查找成功：若給定值小于中間元素的關(guān)鍵碼，則在中間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵碼，則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過程，直到查找成功，或所查找的區(qū)域無數(shù)據(jù)元素，查找失敗。

二分法查找的優(yōu)點(diǎn)：平均檢索長度小，即每經(jīng)過一次關(guān)鍵碼比較，則將查找范圍縮小一半，經(jīng)過log2n

次比較就可完成查找過程。其缺點(diǎn)是:只適用于順序存儲的有序表，不適用于鏈?zhǔn)酱鎯Φ挠行虮?，并且，在查找之前要為建立有序表付出代價。

8.2軟件工程基礎(chǔ)軟件的定義與特點(diǎn)軟件危機(jī)與軟件工程軟件工程過程與軟件生命周期軟件工程的基本目標(biāo)與原則軟件開發(fā)工具與軟件開發(fā)環(huán)境

8.2.1

軟件工程的基本概念

軟件的定義與特點(diǎn)軟件的定義

軟件并不完全等同于程序，而是包括程序、數(shù)據(jù)及相關(guān)文檔的集合，可以描述成“軟件=程序+數(shù)據(jù)+文檔”。

軟件的特點(diǎn)

軟件是計算機(jī)系統(tǒng)中的邏輯實體，具有抽象性；沒有明顯的制作過程，一旦開發(fā)成功，可以大量拷貝同一內(nèi)容的副本；軟件在運(yùn)行過程中不會因為使用時間過長而出現(xiàn)磨損、老化以及用壞等問題；出現(xiàn)了軟件移植的問題；軟件開發(fā)復(fù)雜性較高，開發(fā)周期較長，成本較大；軟件開發(fā)還涉及諸多的社會因素。

軟件危機(jī)與軟件工程

軟件危機(jī)

隨著計算機(jī)技術(shù)的發(fā)展和計算機(jī)應(yīng)用規(guī)模的不斷擴(kuò)大，軟件需求量迅速增加，軟件規(guī)模也越來越大，復(fù)雜度不斷增加，軟件已經(jīng)成為制約計算機(jī)技術(shù)發(fā)展的“瓶頸”問題。軟件危機(jī)是泛指在計算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題。

軟件工程

軟件工程就是采用工程化的原理、技術(shù)和方法來開發(fā)、運(yùn)行和維護(hù)軟件。軟件工程包含三個要素：方法(Methodologies)工具(Tools)過程(Procedures)

軟件工程過程與軟件生命周期

軟件工程過程

軟件工程過程實際上就是將軟件工程的方法、工具綜合起來，規(guī)定方法、工具使用的順序、要求交付的文檔資料、為保證質(zhì)量和適應(yīng)變化所需要的管理、軟件開發(fā)各個階段的任務(wù)，最終達(dá)到合理、及時進(jìn)行軟件開發(fā)，獲得高質(zhì)量、低成本的軟件產(chǎn)品的目的。

軟件生命周期

軟件生命周期大體可分為三個時期：定義階段、開發(fā)階段及運(yùn)行和維護(hù)階段。

軟件生命周期模型

軟件過程模型：瀑布模型、快速原型模型、螺旋模型、增量模型、噴泉模型、變換模型、面向?qū)ο笊嫫谀Ｐ偷取?/p>

瀑布模型瀑布模型——軟件工程中應(yīng)用最廣泛的軟件過程模型軟件測試軟件設(shè)計需求分析軟件維護(hù)軟件編碼軟件計劃瀑布模型

軟件工程的基本目標(biāo)與原則軟件工程的基本目標(biāo)：要付出較低的開發(fā)成本，達(dá)到要求的軟件功能，取得較好的軟件性能，開發(fā)的軟件要易于移植和維護(hù)；能按時完成開發(fā)工作，及時交付使用。軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。

結(jié)構(gòu)化方法結(jié)構(gòu)化分析結(jié)構(gòu)化設(shè)計結(jié)構(gòu)化編程軟件測試問題定義和可行性分析結(jié)構(gòu)化方法的軟件開發(fā)過程

結(jié)構(gòu)化分析方法

結(jié)構(gòu)化設(shè)計方法

結(jié)構(gòu)化程序設(shè)計方法

8.2.2結(jié)構(gòu)化分析方法

SA（StructuredAnalysis,結(jié)構(gòu)化分析）是20世紀(jì)70年代中期由E.Yourdon等人提出的一種面向數(shù)據(jù)流開展需求分析的結(jié)構(gòu)化分析方法。結(jié)構(gòu)化分析一般采用自頂向下，逐層分解的方法來定義系統(tǒng)的需求，即先把分析對象抽象成一個系統(tǒng)，然后采用自頂向下、逐層分解的方法，將復(fù)雜的系統(tǒng)分解成簡單的、能夠清楚地被理解和表達(dá)的若干個子系統(tǒng)。結(jié)構(gòu)化分析方法常用的工具有數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化語言、判定樹、判定表等。

結(jié)構(gòu)化設(shè)計方法（StructuredDesign，SD）給出一組幫助設(shè)計人員在模塊層次上區(qū)分設(shè)計質(zhì)量的原理與技術(shù)。它通常與結(jié)構(gòu)化分析方法銜接起來使用，以數(shù)據(jù)流圖為基礎(chǔ)得到軟件的模塊結(jié)構(gòu)。SD方法尤其適用于變換型結(jié)構(gòu)和事務(wù)型結(jié)構(gòu)的目標(biāo)系統(tǒng)。在設(shè)計過程中，它從整個程序的結(jié)構(gòu)出發(fā)，利用結(jié)構(gòu)圖（StructureChart，SC）來描述系統(tǒng)的模塊結(jié)構(gòu)。8.2.3結(jié)構(gòu)化設(shè)計方法8.2.4軟件測試的目的和方法

軟件測試的目的

軟件測試的準(zhǔn)則

軟件測試的方法

軟件測試的過程

軟件測試的目的測試是程序的執(zhí)行過程，目的在于發(fā)現(xiàn)錯誤一個好的測試用例在于能發(fā)現(xiàn)至今未發(fā)現(xiàn)的錯誤一個成功的測試是發(fā)現(xiàn)了至今未發(fā)現(xiàn)的錯誤的測試

軟件測試的準(zhǔn)則測試應(yīng)該盡早進(jìn)行，最好在需求階段就開始介入

程序員應(yīng)該避免檢查自己的程序，軟件測試應(yīng)該由第三方構(gòu)造

設(shè)計測試用例時應(yīng)考慮到合法的輸入和不合法的輸入以及各種邊界條件

充分注意測試中的群集現(xiàn)象

對測試錯誤結(jié)果一定要有一個確認(rèn)過程

制定嚴(yán)格的測試計劃

妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告

軟件測試的方法

若從是否需要執(zhí)行被測軟件的角度可分為靜態(tài)測試和動態(tài)測試兩大類。靜態(tài)測試代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。

動態(tài)測試

動態(tài)測試是基于計算機(jī)的測試，通過執(zhí)行程序來發(fā)現(xiàn)錯誤的過程。動態(tài)測試也可分為兩大類：黑盒測試和白盒測試。

軟件測試的過程單元測試

集成測試

確認(rèn)測試

系統(tǒng)測試

8.2.5程序的調(diào)試

程序調(diào)試通常也稱為Debug，是在進(jìn)行了成功的測試之后才開始的工作。它與軟件測試不同，軟件測試的目的是盡可能多地發(fā)現(xiàn)軟件中的錯誤，而調(diào)試的任務(wù)則是根據(jù)測試時所發(fā)現(xiàn)的錯誤，進(jìn)一步診斷，找出原因和具體的位置進(jìn)行改正。軟件測試貫穿整個軟件生命周期，調(diào)試工作主要在開發(fā)階段。8.3程序設(shè)計基礎(chǔ)8.3.1

程序設(shè)計方法和風(fēng)格

程序設(shè)計方法程序設(shè)