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

算法的定義與基本特征

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

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

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

算法的基本要素?cái)?shù)據(jù)對(duì)象的運(yùn)算和操作

通常，一個(gè)計(jì)算機(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)一個(gè)算法通常都可以由順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。

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

算法復(fù)雜度

算法的時(shí)間復(fù)雜度算法的空間復(fù)雜度8.1.3數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(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ù)的存儲(chǔ)結(jié)構(gòu)(或稱物理結(jié)構(gòu))。

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

反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.1.6棧和隊(duì)列

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

棧

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

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

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

讀棧頂元素

隊(duì)列

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

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

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

二叉樹(shù)的遍歷

樹(shù)的定義

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

一般的樹(shù)ABEKLFCGMDHIJ層次1234

二叉樹(shù)的定義

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

深度為4的二叉樹(shù)

二叉樹(shù)的幾個(gè)基本性質(zhì)

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

二叉樹(shù)的存儲(chǔ)

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

二叉樹(shù)的遍歷

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

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

二叉樹(shù)的遍歷舉例

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

ABDHECFGI

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

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

順序查找

二分法查找

順序查找

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

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

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

二分法查找

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

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

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

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

8.2.1

軟件工程的基本概念

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

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

軟件的特點(diǎn)

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

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

軟件危機(jī)

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

軟件工程

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

軟件工程過(guò)程與軟件生命周期

軟件工程過(guò)程

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

軟件生命周期

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

軟件生命周期模型

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

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

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

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

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

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

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

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

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

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

軟件測(cè)試的目的

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

軟件測(cè)試的方法

軟件測(cè)試的過(guò)程

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

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

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

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

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

對(duì)測(cè)試錯(cuò)誤結(jié)果一定要有一個(gè)確認(rèn)過(guò)程

制定嚴(yán)格的測(cè)試計(jì)劃

妥善保存測(cè)試計(jì)劃、測(cè)試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告

軟件測(cè)試的方法

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

動(dòng)態(tài)測(cè)試

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

軟件測(cè)試的過(guò)程單元測(cè)試

集成測(cè)試

確認(rèn)測(cè)試

系統(tǒng)測(cè)試

8.2.5程序的調(diào)試

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

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

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