【正文】 第 1章 數(shù)據(jù)結(jié)構(gòu)與算法 算法的復(fù)雜度 .......................................1 數(shù)據(jù)結(jié)構(gòu) ...............................................1 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) .............1 線性結(jié)構(gòu)和非線性結(jié)構(gòu) .........3 棧 ...........................................................3 隊(duì)列 .......................................................4 鏈表 .......................................................5 二叉樹 ....................................................5 二叉樹概念及其基本性質(zhì) ......5 二叉樹的遍歷 ............................8 查找 ........................................................8 順序查找 ..................................8 二分法查找 ..............................9 排序 ......................................................10 第 2章 程序設(shè)計(jì)基礎(chǔ) 程序設(shè)計(jì)的方法與風(fēng)格 .....................11 結(jié)構(gòu)化程序設(shè)計(jì) .................................12 面向?qū)ο蠓椒?.....................................12 第 3章 軟件工程基礎(chǔ) 軟件工程基本概念 .............................14 軟件生命周期 .....................................15 軟件 設(shè)計(jì) .............................................16 軟件設(shè)計(jì)基本概念 ...............16 軟件設(shè)計(jì)的基本原理 ...........17 結(jié)構(gòu)化分析方法 .................................18 軟件測試 ..............................................19 軟件測試的目的和準(zhǔn)則 ........19 軟件測試的方法和實(shí)施 ........19 程序的調(diào)試 .........................................21 第 4章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ) 數(shù)據(jù)庫的基本概念 .............................22 數(shù)據(jù)庫系統(tǒng)的發(fā)展和基本特點(diǎn) .........22 數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu) .............23 數(shù)據(jù)模型的基本概念 .........................24 ER模型 ..............................................25 關(guān)系模型 ..............................................25 關(guān)系代數(shù) ..............................................26 數(shù)據(jù)庫設(shè)計(jì)與原理 .............................27 第 1章 數(shù)據(jù)結(jié)構(gòu)與算法 算法的復(fù)雜度 1. 算法的 基本概念 利用計(jì)算機(jī)算法為計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法。 （ 1）算法的基本特征 算法一般具有 4個(gè)基本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。 （ 2）算法的基本運(yùn)算和操作 算法的基本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。 （ 3）算法的 3種基本控制結(jié)構(gòu) 算法的 3種基本控制結(jié)構(gòu)是：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 （ 4）算法基本設(shè)計(jì)方法 算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。 （ 5）指令系統(tǒng) 所謂指令系統(tǒng)指的 是一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。 2. 算法復(fù)雜度 算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。注意兩者的區(qū)別，無混淆，見 表 11。 表 11 算法復(fù)雜性 名稱 描述 時(shí)間復(fù)雜度 執(zhí)行算法所需要的計(jì)算工作量 空間復(fù)雜度 執(zhí)行這個(gè)算法所需要的內(nèi)存空間 數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 1. 數(shù)據(jù)結(jié)構(gòu)的基本概念 （ 1）數(shù)據(jù)結(jié)構(gòu) 指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 （ 2）數(shù)據(jù)結(jié)構(gòu)研究的 3個(gè)方面 ① 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固 有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； ② 在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存 儲結(jié)構(gòu)； ③ 對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 2. 邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元 素的集合和定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一 是數(shù)據(jù)元素的集合，通常記為 D；二是 D上的關(guān)系，它反映了數(shù)據(jù)元素之間的 前后件關(guān)系，通常記為 R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成： B=(D,R) 其中， B表示數(shù)據(jù)結(jié)構(gòu)。為了反映 D中各數(shù)據(jù)元素之間的前后件關(guān) 系，一般 用二元組來表示。 例如，如果把一年四季看作一個(gè)數(shù)據(jù)結(jié)構(gòu)，則可表示成： B =(D,R) D ={春季 ,夏季 ,秋季 ,冬季 } R ={(春季 ,夏季 ),(夏季 ,秋季 ),(秋季 ,冬季 )} 3. 存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱 數(shù)據(jù)的物理結(jié)構(gòu)）。 由于數(shù)據(jù)元素在計(jì)算機(jī)存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此， 為了表示存放在計(jì)算機(jī)存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān) 系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需 要存放各數(shù)據(jù) 元素之間的前后件關(guān)系的信息。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有 順序、鏈接等存儲結(jié)構(gòu)。 順序存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲在 物理上相鄰的存儲單元里，結(jié)點(diǎn)之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。 鏈?zhǔn)酱鎯Y(jié)構(gòu)就是在每個(gè)結(jié)點(diǎn)中至少包含一個(gè)指針域，用指針來體現(xiàn)數(shù)據(jù)元 素之間邏輯上的聯(lián)系。 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分 為兩大類型：線性結(jié)構(gòu)與非 線性結(jié)構(gòu)。 （ 1）如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件： ① 有且只有一個(gè)根結(jié)點(diǎn)； ② 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入 或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。棧、隊(duì)列、串等都為線性結(jié)構(gòu)。 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。數(shù)組、廣義表、樹 和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 （ 2）線性表的順序存儲結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)： ① 線性表中所有元素所占的存儲空間是連續(xù)的； ② 線性表中各 數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 元素 ai的存儲地址為： ADR(ai)=ADR(a1)+(i1)k， ADR(a1)為第一個(gè)元素的 地址， k代表每個(gè)元素占的字節(jié)數(shù)。 （ 3）順序表的運(yùn)算有查找、插入、刪除 3種。 棧 1. 棧的基本概念 棧（ stack）是一種特殊的線性表，是限定只在一端進(jìn)行插入與刪除的線性表。 在棧中，一端是封閉的，既不允許進(jìn)行插入元素，也不允許刪除元素；另一 端是開口的，允許插入和刪除元素。通常稱插入、刪除的這一端為棧頂，另一端 為棧底。當(dāng)表中沒有 元素時(shí)稱為空棧。棧頂元素總是最后被插入的元素，從而也 是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪 除的元素。 棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。例如，槍械的子 彈匣就可以用來形象的表示棧結(jié)構(gòu)。子彈匣的一端是完全封閉的，最后被壓入彈 匣的子彈總是最先被彈出，而最先被壓入的子彈最后才能被彈出。 2. 棧的順序存儲及其運(yùn)算 棧的基本運(yùn)算有 3種：入棧、退棧與讀棧頂元素。 ① 入棧運(yùn)算：在棧頂位置插入一個(gè)新元素； ② 退棧運(yùn)算：取出棧頂元素并賦給一 個(gè)指定的變量； ③ 讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。 隊(duì)列 1. 隊(duì)列的基本概念 隊(duì)列是只允許在一端進(jìn)行刪除，在另一端進(jìn)行插入的順序表，通常將允許 刪除的這一端稱為隊(duì)頭，允許插入的這一端稱為隊(duì)尾。當(dāng)表中沒有元素時(shí)稱為 空隊(duì)列。 隊(duì)列的修改是依照先進(jìn)先出的原則進(jìn)行的，因此隊(duì)列也稱為先進(jìn)先出的線 性表，或者后進(jìn)后出的線性表。例如：火車進(jìn)遂道