全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言公共基礎(chǔ)知識(shí)輔導(dǎo)

1、目錄全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義 . 1 第一章 數(shù)據(jù)結(jié)構(gòu)與算法 . 1 第二章 程序設(shè)計(jì)基礎(chǔ) . . 6 第三章 軟件工程基礎(chǔ) . . 9 第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) . 15全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法1描述。 *:算法不等于程序,也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)。2、算法的基本特征(1可行性。針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法,執(zhí)行后能夠得到滿(mǎn)意的結(jié)果。(2確定性。每一條指令的含義明確,無(wú)二義性。并且在任何條件下,算法只有唯一的一 條執(zhí)行路徑,即相同的輸入只能得出相同的輸出。(3有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義

2、,一是算法中的操作步驟為有限 個(gè),二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。(4擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上,而這些運(yùn)算對(duì)象又 可能具有某種初始狀態(tài), 這就是算法執(zhí)行的起點(diǎn)或依據(jù)。 因此, 一個(gè)算法執(zhí)行的結(jié)果總是與 輸入的初始數(shù)據(jù)有關(guān), 不同的輸入將會(huì)有不同的結(jié)果輸出。 當(dāng)輸入不夠或輸入錯(cuò)誤時(shí), 算法 將無(wú)法執(zhí)行或執(zhí)行有錯(cuò)。一般說(shuō)來(lái),當(dāng)算法擁有足夠的情報(bào)時(shí),此算法才是有效的;而當(dāng)提 供的情報(bào)不夠時(shí),算法可能無(wú)效。*:綜上所述,所謂算法,是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,并且每一個(gè)規(guī)則都是有效的, 且是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。3(1 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念12、

3、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題: (1數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含:1表示數(shù)據(jù)元素的信息; 2表示各數(shù)據(jù)元素之間的前后件關(guān)系。(2在對(duì)數(shù)據(jù)進(jìn)行處理時(shí),各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系,即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。1順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里,結(jié)點(diǎn)間的邏輯 關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)。2鏈接存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰,結(jié)點(diǎn)間的邏輯關(guān)系是由附 加的指針字段表示的。由此得到的存儲(chǔ)表示稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3索引存儲(chǔ):除建立

4、存儲(chǔ)結(jié)點(diǎn)信息外,還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。*:數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系, 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) (也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu) 是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。 同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的 存儲(chǔ)結(jié)構(gòu),但影響數(shù)據(jù)處理效率。(3對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外, 還可以直觀地用圖形表示。 在數(shù)據(jù)結(jié)構(gòu)的圖形表示中, 對(duì)于數(shù)據(jù)集合 D 中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示,一般稱(chēng)之為數(shù)據(jù)結(jié)點(diǎn), 并簡(jiǎn)稱(chēng)為結(jié)點(diǎn); 為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系, 對(duì)于關(guān)系 R 中的每一個(gè)二元 組,用一條有向線(xiàn)段從前件結(jié)點(diǎn)指向

5、后件結(jié)點(diǎn)。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型:線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。(11有且只有一個(gè)根結(jié)點(diǎn); 2每一個(gè)結(jié)點(diǎn)最多有 一個(gè)前件,也最多有一個(gè)后件。 *:常見(jiàn)的線(xiàn)性結(jié)構(gòu)有線(xiàn)性表、棧、隊(duì)列和線(xiàn)性鏈表等。(2*:常見(jiàn)的非線(xiàn)性結(jié)構(gòu)有樹(shù)、二叉樹(shù)和圖等。 1.3 線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu) 1線(xiàn)性表是由 n(n 0 個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列, 表中的每一個(gè)數(shù)據(jù)元素, 除了第一個(gè)外,有且只有一個(gè)前件,除了最后一個(gè)外,有且只有一個(gè)后件。線(xiàn)性表中數(shù)據(jù)元 素的個(gè)數(shù)稱(chēng)為線(xiàn)性表的長(zhǎng)度。線(xiàn)性表可以為空表。*:線(xiàn)性表是一種存儲(chǔ)結(jié)構(gòu),它的存儲(chǔ)方式:順序和鏈?zhǔn)健?、線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn):(1線(xiàn)性表中所有元素所占的存儲(chǔ)空間

6、是連 續(xù)的;(2線(xiàn)性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。*:由此可以看出, 在線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)中, 其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的, 且前件元素一定存儲(chǔ)在后件元素的前面,可以通過(guò)計(jì)算機(jī)直接確定第 i 個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。3、順序表的插入、刪除運(yùn)算(1順序表的插入運(yùn)算:在一般情況下,要在第 i (1 i n 個(gè)元素之前插入一個(gè)新元素 時(shí),首先要從最后一個(gè)(即第 n 個(gè)元素開(kāi)始,直到第 i 個(gè)元素之間共 n-i+1個(gè)元素依次向 后移動(dòng)一個(gè)位置,移動(dòng)結(jié)束后,第 i 個(gè)位置就被空出,然后將新元素插入到第 i 項(xiàng)。插入結(jié) 束后,線(xiàn)性表的長(zhǎng)度就增加了 1。*:順性表的插入運(yùn)算時(shí)需要移

7、動(dòng)元素,在等概率情況下,平均需要移動(dòng) n/2個(gè)元素。(2順序表的刪除運(yùn)算:在一般情況下,要?jiǎng)h除第 i (1 i n 個(gè)元素時(shí),則要從第 i+1個(gè)元素開(kāi)始, 直到第 n 個(gè)元素之間共 n-i 個(gè)元素依次向前移動(dòng)一個(gè)位置。 刪除結(jié)束后, 線(xiàn)性 表的長(zhǎng)度就減小了 1。*:進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素,在等概率情況下,平均需要移動(dòng)(n-1 /2個(gè)元素。插入、刪除運(yùn)算不方便。1.4 棧和隊(duì)列1、棧及其基本運(yùn)算 在棧中, 允許插入與刪除的一端稱(chēng)為棧頂, 不允許插入與刪除的另一端稱(chēng)為棧底。 棧頂元素 總是最后被插入的元素, 棧底元素總是最先被插入的元素。 即棧是按照“先進(jìn)后出”或“后 進(jìn)先出”的原則

8、組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運(yùn)算:1插入元素稱(chēng)為入棧運(yùn)算; 2刪除元素稱(chēng)為退棧運(yùn)算; 3讀棧頂元素是 將棧頂元素賦給一個(gè)指定的變量,此時(shí)指針無(wú)變化。棧的存儲(chǔ)方式和線(xiàn)性表類(lèi)似,也有兩種,即順序棧和鏈?zhǔn)綏！?Rear 指向隊(duì)尾元素,頭指針(front 指向排頭元素的前一個(gè)位置(隊(duì)頭。 隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線(xiàn)性表。隊(duì)列運(yùn)算包括:1入隊(duì)運(yùn)算:從隊(duì)尾插入一個(gè)元素; 2退隊(duì)運(yùn)算:從隊(duì)頭刪除一個(gè)元素。 循環(huán)隊(duì)列及其運(yùn)算:所謂循環(huán)隊(duì)列,就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置, 形成邏輯上的環(huán)狀空間,供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中,用隊(duì)尾指針 rear 指向隊(duì)列中的 隊(duì)尾元素, 用排

9、頭指針 front 指向排頭元素的前一個(gè)位置, 因此, 從頭指針 front 指向的后 一個(gè)位置直到隊(duì)尾指針 rear 指向的位置之間,所有的元素均為隊(duì)列中的元素。*:循環(huán)隊(duì)列中元素的個(gè)數(shù) =rear-front。1.5 線(xiàn)性鏈表1、線(xiàn)性表順序存儲(chǔ)的缺點(diǎn):(1插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線(xiàn)性表中,插 入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素;(2線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)下,線(xiàn)性表的 存儲(chǔ)空間不便于擴(kuò)充;(3線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。2、線(xiàn)性鏈表:線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線(xiàn)性鏈表,是一種物理存儲(chǔ)單元上非連續(xù)、非順 序的存儲(chǔ)結(jié)構(gòu), 數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈

10、接來(lái)實(shí)現(xiàn)的。 因此, 在鏈?zhǔn)酱鎯?chǔ) 方式中,每個(gè)結(jié)點(diǎn)由兩部分組成:一部分用于存放數(shù)據(jù)元素的值,稱(chēng)為數(shù)據(jù)域;另一部分用 于存放指針,稱(chēng)為指針域,用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件,如下 圖所示: 線(xiàn)性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類(lèi)型。在單鏈表中, 每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域, 由這個(gè)指針只能找到其后件結(jié)點(diǎn), 而不能找到其 前件結(jié)點(diǎn)。因此,在某些應(yīng)用中,對(duì)于線(xiàn)性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針,一個(gè)稱(chēng)為左指 針,指向其前件結(jié)點(diǎn);另一個(gè)稱(chēng)為右指針,指向其后件結(jié)點(diǎn),這種鏈表稱(chēng)為雙向鏈表,如下 圖所示: 3、線(xiàn)性鏈表的基本運(yùn)算(1在線(xiàn)性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。*:在線(xiàn)

11、性鏈表中插入元素時(shí),不需要移動(dòng)數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點(diǎn)指針即可,也不 會(huì)出現(xiàn)“上溢”現(xiàn)象。(2在線(xiàn)性鏈表中刪除包含指定元素的結(jié)點(diǎn)。*:在線(xiàn)性鏈表中刪除元素時(shí),也不需要移動(dòng)數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點(diǎn)指針即可。(3將兩個(gè)線(xiàn)性鏈表按要求合并成一個(gè)線(xiàn)性鏈表。(4將一個(gè)線(xiàn)性鏈表按要求進(jìn)行分解。(5逆轉(zhuǎn)線(xiàn)性鏈表。(6復(fù)制線(xiàn)性鏈表。(7線(xiàn)性鏈表的排序。(8線(xiàn)性鏈表的查找。*:線(xiàn)性鏈表不能隨機(jī)存取。4、循環(huán)鏈表及其基本運(yùn)算在線(xiàn)性鏈表中, 其插入與刪除的運(yùn)算雖然比較方便, 但還存在一個(gè)問(wèn)題, 在運(yùn)算過(guò)程中對(duì)于 空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮, 使空表與非空表的運(yùn)算不統(tǒng)一。 為了克服線(xiàn)性鏈 表的這個(gè)缺

12、點(diǎn),可以采用另一種鏈接方式,即循環(huán)鏈表。數(shù) 據(jù) 域 指 針 域 H EAD (a結(jié) 點(diǎn) 結(jié) 構(gòu) (b一 個(gè) 非 空 的 線(xiàn) 性 鏈 表 示 意 圖右 指 針左 指 針 數(shù) 據(jù) 域 (a結(jié) 點(diǎn) 結(jié) 構(gòu) H EAD (b一 個(gè) 非 空 的 雙 向 鏈 表 示 意 圖與前面所討論的線(xiàn)性鏈表相比,循環(huán)鏈表具有以下兩個(gè)特點(diǎn):1在鏈表中增加了一個(gè)表頭 結(jié)點(diǎn), 其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置, 指針域指向線(xiàn)性表的第一個(gè)元素的結(jié)點(diǎn), 而循 環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn); 2循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空,而是指向表 頭結(jié)點(diǎn)。即在循環(huán)鏈表中,所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。下圖 a 是一個(gè)非空的循環(huán)鏈表,

13、圖 b 是一個(gè)空的循環(huán)鏈表: 循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方面:一是在循環(huán)鏈表中, 只要指出表中任何一個(gè)結(jié)點(diǎn)的位 置, 就可以從它出發(fā)訪(fǎng)問(wèn)到表中其他所有的結(jié)點(diǎn), 而線(xiàn)性單鏈表做不到這一點(diǎn); 二是由于在 循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn), 在任何情況下, 循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在, 從而使 空表與非空表的運(yùn)算統(tǒng)一。*:循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個(gè)表頭結(jié)點(diǎn),其插入和刪除運(yùn)算與單鏈表相同。 但它可以從任一結(jié)點(diǎn)出發(fā)來(lái)訪(fǎng)問(wèn)表中其他所有結(jié)點(diǎn),并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一。1.6 樹(shù)與二叉樹(shù)1、樹(shù)的基本概念層次特性。 (1什么是二叉樹(shù)它具有以下兩個(gè)特點(diǎn):1 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn);2每一個(gè)結(jié)點(diǎn)最

14、多有兩棵子樹(shù),且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。 *:根據(jù)二叉樹(shù)的概念可知,二叉樹(shù)的度可以為 0(葉結(jié)點(diǎn)、 1(只有一棵子樹(shù)或 2(有 2棵子樹(shù)。(2二叉樹(shù)的基本性質(zhì)性質(zhì) 1 在二叉樹(shù)的第 k 層上,最多有 個(gè)結(jié)點(diǎn)。性質(zhì) 2 深度為 m 的二叉樹(shù)最多有個(gè) 個(gè)結(jié)點(diǎn)。 性質(zhì) 3 在任意一棵二叉樹(shù)中,度數(shù)為 0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn)總比度為 2的結(jié)點(diǎn)多一個(gè)。 性質(zhì) 4 具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù),其深度至少為 ,其中 表示取 的整數(shù)部分。3、滿(mǎn)二叉樹(shù)與完全二叉樹(shù)滿(mǎn)二叉樹(shù):除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹(shù):除最后一層外, 每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值; 在最后一層上只缺少右邊的 若

15、干結(jié)點(diǎn)。*:根據(jù)完全二叉樹(shù)的定義可得出:度為 1的結(jié)點(diǎn)的個(gè)數(shù)為 0或 1。下圖 a 表示的是滿(mǎn)二叉樹(shù),下圖 b 表示的是完全二叉樹(shù):1(21-k k 12-m 1log2+n log2n n 2log 完全二叉樹(shù)還具有如下兩個(gè)特性:性質(zhì) 5 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為 。性質(zhì) 6 設(shè)完全二叉樹(shù)共有 n 個(gè)結(jié)點(diǎn),如果從根結(jié)點(diǎn)開(kāi)始,按層序(每一層從左到右用自 然數(shù) 1, 2, n 給結(jié)點(diǎn)進(jìn)行編號(hào),則對(duì)于編號(hào)為 k (k=1, 2, n 的結(jié)點(diǎn)有以下結(jié)論: 若 k=1, 則該結(jié)點(diǎn)為根結(jié)點(diǎn), 它沒(méi)有父結(jié)點(diǎn); 若 k>1, 則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為 INT(k/2。 若 2k n , 則編

16、號(hào)為 k 的左子結(jié)點(diǎn)編號(hào)為 2k ; 否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn) (顯然也沒(méi)有右子結(jié) 點(diǎn)。若 2k+1 n ,則編號(hào)為 k 的右子結(jié)點(diǎn)編號(hào)為 2k+1;否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。4、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中,二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。與線(xiàn)性鏈表類(lèi)似,用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成:數(shù)據(jù)域和指針域。 但在二叉樹(shù)中,由于每一個(gè)元素可以有兩個(gè)后件(即兩個(gè)子結(jié)點(diǎn),因此,用于存儲(chǔ)二叉樹(shù) 的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè):一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址,稱(chēng)為左指針域; 另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址,稱(chēng)為右指針域。*:一般二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),對(duì)于滿(mǎn)二叉樹(shù)與完全二叉樹(shù)來(lái)說(shuō),可以按

17、層序進(jìn)行 順序存儲(chǔ)。5、二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指不重復(fù)地訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。二叉樹(shù)的遍歷可以分為以下三種:(1前序遍歷(DLR :若二叉樹(shù)為空,則結(jié)束返回。否則:首先訪(fǎng)問(wèn)根結(jié)點(diǎn),然后遍歷左 子樹(shù),最后遍歷右子樹(shù);并且,在遍歷左右子樹(shù)時(shí),仍然先訪(fǎng)問(wèn)根結(jié)點(diǎn),然后遍歷左子樹(shù), 最后遍歷右子樹(shù)。(2中序遍歷(LDR :若二叉樹(shù)為空,則結(jié)束返回。否則:首先遍歷左子樹(shù),然后訪(fǎng)問(wèn)根 結(jié)點(diǎn), 最后遍歷右子樹(shù); 并且, 在遍歷左、 右子樹(shù)時(shí), 仍然先遍歷左子樹(shù), 然后訪(fǎng)問(wèn)根結(jié)點(diǎn), 最后遍歷右子樹(shù)。(3后序遍歷(LRD :若二叉樹(shù)為空,則結(jié)束返回。否則:首先遍歷左子樹(shù),然后遍歷右 子樹(shù), 最后訪(fǎng)問(wèn)根結(jié)點(diǎn),

18、 并且, 在遍歷左、 右子樹(shù)時(shí), 仍然先遍歷左子樹(shù), 然后遍歷右子樹(shù), 最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。1.7 查找技術(shù)查找:根據(jù)給定的某個(gè)值,在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 查找結(jié)果:(查找成功:找到;查找不成功:沒(méi)找到。平均查找長(zhǎng)度:查找過(guò)程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序查找基本思想:從表中的第一個(gè)元素開(kāi)始, 將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較, 直到 兩者相符,查到所要找的元素為止。否則就是表中沒(méi)有要找的元素,查找不成功。在平均情況下, 利用順序查找法在線(xiàn)性表中查找一個(gè)元素, 大約要與線(xiàn)性表中一半的元素進(jìn) 行比較,最壞情況下需要比較 n 次。順序查找一個(gè)具有 n 個(gè)元素

19、的線(xiàn)性表,其平均復(fù)雜度為 O (n 。下列兩種情況下只能采用順序查找:1log2 n1如果線(xiàn)性表是無(wú)序表(即表中的元素是無(wú)序的,則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ) 結(jié)構(gòu),都只能用順序查找。2即使是有序線(xiàn)性表,如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),也只能用順序查找。2、二分法查找思想:先確定待查找記錄所在的范圍, 然后逐步縮小范圍, 直到找到或確認(rèn)找不到該記錄為 止。前提:必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。查找過(guò)程:1若中間項(xiàng)(中間項(xiàng) mid=(n-1/2, mid 的值四舍五入取整的值等于 x ,則說(shuō)明已查到;2若 x 小于中間項(xiàng)的值,則在線(xiàn)性表的前半部分查找;3若 x 大于中間項(xiàng)的值,則在線(xiàn)性表的后半部分

20、查找。特點(diǎn):比順序查找方法效率高。最壞的情況下,需要比較 log2n 次。*:二分法查找只適用于順序存儲(chǔ)的線(xiàn)性表,且表中元素必須按關(guān)鍵字有序(升序排列。 對(duì)于無(wú)序線(xiàn)性表和線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。 在長(zhǎng)度為 n 的有序線(xiàn)性表中進(jìn)行 二分法查找,其時(shí)間復(fù)雜度為 O (log2n 。1.8 排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列, 即是將無(wú)序的記錄序列調(diào) 整為有序記錄序列的一種操作。1、交換類(lèi)排序法(方法:冒泡排序,快速排序。2、插入類(lèi)排序法(方法:簡(jiǎn)單插入排序,希爾排序。3、選擇類(lèi)排序法(方法:簡(jiǎn)單選擇排序,堆排序 ?？偨Y(jié):各種排序法比較:本章應(yīng)考點(diǎn)撥:本章內(nèi)

21、容在筆試中會(huì)出現(xiàn) 5-6個(gè)題目,是公共基礎(chǔ)知識(shí)部分出題量比較多 的一章,所占分值也比較大,約 10分。第二章 程序設(shè)計(jì)基礎(chǔ)2.1 程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào):“清晰第一,效率第二” 。主要應(yīng)注重和考慮下述一些因素: (1源程序文檔化。 1符號(hào)名的命名。符號(hào)名能反映它所代表的實(shí)際東西,應(yīng)有一定的實(shí)際含義。2程序的注釋。分為序言性注釋和功能性注釋。序言性注釋:位于程序開(kāi)頭部分,包括程序標(biāo)題、程序功能說(shuō)明、主要算法、接口說(shuō)明、程 序位置、開(kāi)發(fā)簡(jiǎn)歷、程序設(shè)計(jì)者、復(fù)審者、復(fù)審日期及修改日期等。功能性注釋:嵌在源程序體之中,用于描述其后的語(yǔ)句或程序的主要功能。3視覺(jué)組織。利用空格、空行、縮進(jìn)等技巧

22、使程序?qū)哟吻逦?2數(shù)據(jù)說(shuō)明。 1數(shù)據(jù)說(shuō)明的次序規(guī)范化; 2說(shuō)明語(yǔ)句中變量安排有序化; 3使用注釋 來(lái)說(shuō)明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。(3語(yǔ)句的結(jié)構(gòu)。 1在一行內(nèi)只寫(xiě)一條語(yǔ)句; 2程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性; 3程序編 寫(xiě)要做到清晰第一,效率第二; 4在保證程序正確的基礎(chǔ)上再要求提高效率; 5避免使用 臨時(shí)變量而使程序的可讀性下降; 6避免不必要的轉(zhuǎn)移; 7盡量使用庫(kù)函數(shù); 8避免采 用復(fù)雜的條件語(yǔ)句; 9盡量減少使用“否定”條件語(yǔ)句; 10數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn) 化; 11要模塊化,使模塊功能盡可能單一化; 12利用信息隱蔽,確保每一個(gè)模塊的獨(dú)立 性; 13從數(shù)據(jù)出發(fā)去構(gòu)造程序; 14不要修補(bǔ)不好的程序

23、,要重新編寫(xiě)。(4輸入和輸出。 1對(duì)輸入數(shù)據(jù)檢驗(yàn)數(shù)據(jù)的合法性; 2檢查輸入項(xiàng)的各種重要組合的合 法性; 3輸入格式要簡(jiǎn)單,使得輸入的步驟和操作盡可能簡(jiǎn)單; 4輸入數(shù)據(jù)時(shí),應(yīng)允許使 用自由格式; 5應(yīng)允許缺省值; 6輸入一批數(shù)據(jù)時(shí),最好使用輸入結(jié)束標(biāo)志; 7在以交 互式輸入 /輸出方式進(jìn)行輸入時(shí),要在屏幕上使用提示符明確提示輸入的請(qǐng)求,同時(shí)在數(shù)據(jù) 輸入過(guò)程中和輸入結(jié)束時(shí),應(yīng)在屏幕上給出狀態(tài)信息; 8當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán) 格要求時(shí), 應(yīng)保持輸入格式與輸入語(yǔ)句的一致性; 給所有的輸出加注釋, 并設(shè)計(jì)輸出報(bào)表格 式。2.2 結(jié)構(gòu)化程序設(shè)計(jì)(面向過(guò)程的程序設(shè)計(jì)方法1、結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則

24、可以概括為:自頂向下,逐步求精,模塊化,限制使用 goto 語(yǔ)句。(1自頂向下。程序設(shè)計(jì)時(shí),應(yīng)先考慮總體,后考慮細(xì)節(jié);先考慮全局目標(biāo),后考慮局部 目標(biāo)。 不要一開(kāi)始就過(guò)多追求眾多的細(xì)節(jié), 先從最上層總目標(biāo)開(kāi)始設(shè)計(jì), 逐步使問(wèn)題具體化。(2逐步求精。對(duì)復(fù)雜問(wèn)題,應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡,逐步細(xì)化。(3模塊化。一個(gè)復(fù)雜問(wèn)題,肯定是由若干稍簡(jiǎn)單的問(wèn)題構(gòu)成。模塊化是把程序要解決的 總目標(biāo)分解為分目標(biāo),再進(jìn)一步分解為具體的小目標(biāo),把每個(gè)小目標(biāo)稱(chēng)為一個(gè)模塊。(4限制使用 goto 語(yǔ)句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu):順序結(jié)構(gòu),選擇結(jié)構(gòu),重復(fù)結(jié)構(gòu)。1順序結(jié)構(gòu)。一種簡(jiǎn)單的程序設(shè)計(jì),即按照程序語(yǔ)句行的自然順序,一條語(yǔ)

25、句一條語(yǔ)句地 執(zhí)行程序,它是最基本、最常用的結(jié)構(gòu)。2選擇結(jié)構(gòu)。又稱(chēng)分支結(jié)構(gòu),包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu),可根據(jù)條件,判斷應(yīng)該選 擇哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列。3重復(fù)結(jié)構(gòu)。又稱(chēng)循環(huán)結(jié)構(gòu),可根據(jù)給定的條件,判斷是否需要重復(fù)執(zhí)行某一相同的或類(lèi) 似的程序段。僅僅使用順序、 選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu), 從而實(shí)現(xiàn)任何 單入口 /單出口的程序。2.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象, 面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世 界固有的事物出發(fā)來(lái)構(gòu)造系統(tǒng), 提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來(lái)認(rèn)識(shí)、 理解和描述客觀 事物, 強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問(wèn)題

26、域。 也就是說(shuō), 系統(tǒng)中的對(duì)象及對(duì)象之間的關(guān)系能 夠如實(shí)地反映問(wèn)題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn):(1與人類(lèi)習(xí)慣的思維方法一致; (2穩(wěn)定性好; (3可重用性好; (4易于開(kāi)發(fā)大型軟件產(chǎn)品; (5可維護(hù)性好。*:面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。 的抽象。 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體, 是構(gòu)成 系統(tǒng)的一個(gè)基本單位, 由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 對(duì)象是屬 對(duì)象的基本特點(diǎn):標(biāo)識(shí)惟一性,分類(lèi)性,多態(tài)性,封裝性,模塊獨(dú)立性好。(1標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的,并且由對(duì)象的內(nèi)在本質(zhì)來(lái)區(qū)分,而不是通過(guò)描述來(lái) 區(qū)

27、分。(2分類(lèi)性。指可以將具有相同屬性的操作的對(duì)象抽象成類(lèi)。 (3多態(tài)性。指同一個(gè)操作可以是不同對(duì)象的行為。(4封裝性。從外面看只能看到對(duì)象的外部特性,即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該 數(shù)據(jù)施加的操作, 根本無(wú)需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。 對(duì)象的內(nèi)部, 即處理 能力的實(shí)行和內(nèi)部狀態(tài),對(duì)外是不可見(jiàn)的。 從外面不能直接使用對(duì)象的處理能力, 也不能直 接修改其內(nèi)部狀態(tài),對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。*:信息隱蔽是通過(guò)對(duì)象的封裝性來(lái)實(shí)現(xiàn)的。(5模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K,它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施 加的操作所組成的統(tǒng)一體, 而且對(duì)象是以數(shù)據(jù)為中心的, 操作圍繞對(duì)其數(shù)據(jù)

28、所需做的處理來(lái) 設(shè)置,沒(méi)有無(wú)關(guān)的操作。從模塊的獨(dú)立性考慮,對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密,內(nèi)聚 性強(qiáng)。 (1 接收消息的對(duì)象的 名稱(chēng); (2消息標(biāo)識(shí)符,也稱(chēng)消息名; (3零個(gè)或多個(gè)參數(shù)。承。單繼承指一個(gè)類(lèi)只允許有一個(gè)父類(lèi),多重繼承指一個(gè)類(lèi)允許有多個(gè)父類(lèi)。 *:類(lèi)的繼承性是類(lèi)之間共享屬性和操作的機(jī)制,它提高了軟件的可重用性。 本章應(yīng)考點(diǎn)撥:本章在考試中會(huì)出現(xiàn)約 1個(gè)題目,所占分值大約占 2分,是出題量較小的 一章。本章內(nèi)容比較少,也很簡(jiǎn)單,掌握住基本的概念就可以輕松應(yīng)對(duì)考試了,所以在這 部分丟分,比較可惜。第三章 軟件工程基礎(chǔ)3.1 軟件工程基本概念1、軟件的相關(guān)概念計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)

29、及相關(guān)文檔的完整集合。軟件的特點(diǎn)包括:1軟件是一種邏輯實(shí)體,而不是物理實(shí)體,具有抽象性; 2軟件的生產(chǎn) 與硬件不同, 它沒(méi)有明顯的制作過(guò)程; 3 軟件在運(yùn)行、 使用期間不存在磨損、 老化問(wèn)題; 4 軟件的開(kāi)發(fā)、 運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性, 受計(jì)算機(jī)系統(tǒng)的限制, 這導(dǎo)致了軟件移植的問(wèn) 題; 5軟件復(fù)雜性高,成本昂貴; 6軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。2、軟件危機(jī)與軟件工程軟件工程源自軟件危機(jī)。 所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一 系列嚴(yán)重問(wèn)題。具體的說(shuō),在軟件開(kāi)發(fā)和維護(hù)過(guò)程中,軟件危機(jī)主要表現(xiàn)在:1軟件需求的增長(zhǎng)得不到滿(mǎn)足。用戶(hù)對(duì)系統(tǒng)不滿(mǎn)意的情況經(jīng)常發(fā)生。2軟件開(kāi)發(fā)成本和

30、進(jìn)度無(wú)法控制。開(kāi)發(fā)成本超出預(yù)算,開(kāi)發(fā)周期大大超過(guò)規(guī)定日期的情況 經(jīng)常發(fā)生。3軟件質(zhì)量難以保證。4軟件不可維護(hù)或維護(hù)程度非常低。5軟件的成本不斷提高。6軟件開(kāi)發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)?？傊?可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。 它所包含的內(nèi)容概括為以下兩點(diǎn):1軟件開(kāi)發(fā)技術(shù),主要有軟件開(kāi)發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。2軟件工程管理,主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。軟件工程的主要思想是將工程化原則運(yùn)用到軟件開(kāi)發(fā)過(guò)程, 它包括 3個(gè)要素:方法、 工具和 過(guò)程。方法是完成軟件工程項(xiàng)目的技術(shù)手段;工具是支持軟件的開(kāi)發(fā)、管理、文檔生成;過(guò) 程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控

31、制、管理。軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。3、軟件生命周期 軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段:1軟件定義階段:包括制定計(jì)劃和需求分析。制定計(jì)劃:確定總目標(biāo);可行性研究;探討解決方案;制定開(kāi)發(fā)計(jì)劃。需求分析:對(duì)待開(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。2軟件開(kāi)發(fā)階段:軟件設(shè)計(jì):分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。軟件實(shí)現(xiàn):把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。軟件測(cè)試:在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。3軟件運(yùn)行維護(hù)階段:軟件投入運(yùn)行,并在使用中不斷地維護(hù),進(jìn)行必要的擴(kuò)充和刪改。 *:軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階

32、段。4、軟件工程的目標(biāo)和與原則(1軟件工程目標(biāo):在給定成本、進(jìn)度的前提下,開(kāi)發(fā)出具有有效性、可靠性、可理解性、 可維護(hù)性、 可重用性、 可適應(yīng)性、 可移植性、 可追蹤性和可互操作性且滿(mǎn)足用戶(hù)需求的產(chǎn)品。(2軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是:付出較低的開(kāi)發(fā)成本;達(dá)到要求的軟件功能;取 得較好的軟件性能;開(kāi)發(fā)的軟件易于移植;需要較低的維護(hù)費(fèi)用;能按時(shí)完成開(kāi)發(fā),及時(shí)交 付使用。(3軟件工程原則:抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn) 證性。逐層細(xì)化的辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性。 2 3模塊的大小要適中, 模塊過(guò)大會(huì)使模塊內(nèi)部的復(fù)雜性增加, 不利于模塊的理解和修改, 也不 利于模

33、塊的調(diào)試和重用; 模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過(guò)于復(fù)雜, 不利于控制系統(tǒng)的復(fù)雜性。45 6785、軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境(1軟件開(kāi)發(fā)工具軟件開(kāi)發(fā)工具的完善和發(fā)展將促使軟件開(kāi)發(fā)方法的進(jìn)步和完善, 促進(jìn)軟件開(kāi)發(fā)的高速度和高 質(zhì)量。 軟件開(kāi)發(fā)工具的發(fā)展是從單項(xiàng)工具的開(kāi)發(fā)逐步向集成工具發(fā)展的, 軟件開(kāi)發(fā)工具為軟 件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境。 同時(shí), 軟件開(kāi)發(fā)方法的有效應(yīng)用也必須 得到相應(yīng)工具的支持,否則方法將難以有效的實(shí)施。(2軟件開(kāi)發(fā)環(huán)境 軟件開(kāi)發(fā)環(huán)境(或稱(chēng)軟件工程環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。 CASE , Computer Aided Software Engi

34、neering將各種軟件工具、 開(kāi)發(fā)機(jī)器和一個(gè)存放開(kāi)發(fā)過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái), 形成軟件工程環(huán)境。 它將極大降 低軟件開(kāi)發(fā)的技術(shù)難度并保證軟件開(kāi)發(fā)的質(zhì)量。3.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。1、需求分析需求分析方法有:1結(jié)構(gòu)化需求分析方法; 2面向?qū)ο蟮姆治龇椒ā?:需求分析一般分為需求獲取、 需求分析、 編寫(xiě)需求規(guī)格說(shuō)明書(shū)和需求評(píng)審四個(gè)步驟進(jìn)行。 2、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析方法的實(shí)質(zhì):著眼于數(shù)據(jù)流,自頂向下,逐層分解,建立系統(tǒng)的處理流程,以數(shù) 據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。1數(shù)

35、據(jù)流圖(DFD ; 2數(shù)據(jù)字典(DD ; 3判定樹(shù); 4判定表。 輯功能,是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。 上圖是數(shù)據(jù)流圖的基本圖形元素:加 工數(shù) 據(jù) 流 存 儲(chǔ) 文 件 源 、 潭:輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。:表示處理過(guò)程中存放各種數(shù)據(jù)的文件。畫(huà)數(shù)據(jù)流圖的基本步驟:自外向內(nèi),自頂向下,逐層細(xì)化,完善求精。 下圖是一個(gè)數(shù)據(jù)流圖的示例: 使得用戶(hù)和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。 *:數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。*:數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。3、軟件需求規(guī)格說(shuō)明書(shū)(SRS 和行為描述、性能需求和設(shè)計(jì)約束的說(shuō)

36、明、合適的驗(yàn)收標(biāo)準(zhǔn),給出對(duì)目標(biāo)軟件的各種需求。 3.3 結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)的基礎(chǔ)*:需求分析主要解決“做什么”的問(wèn)題,而軟件設(shè)計(jì)主要解決“怎么做”的問(wèn)題。從技術(shù)觀點(diǎn)來(lái)看,軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。 從工程角度來(lái)看,軟件設(shè)計(jì)分兩步完成,即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。 結(jié)構(gòu)或數(shù)據(jù)庫(kù)模式。 軟件設(shè)計(jì)的基本原理包括:抽象、模塊化、信息隱蔽和模塊獨(dú)立性。1抽象。抽象是一種思維工具,就是把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。2模塊化。解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小的、相對(duì)獨(dú)立 但又不相互關(guān)聯(lián)的模塊的過(guò)程。3信息隱蔽。每個(gè)模塊的實(shí)施細(xì)節(jié)對(duì)于其他

37、模塊來(lái)說(shuō)是隱蔽的。4模塊獨(dú)立性。軟件系統(tǒng)中每個(gè)模塊只涉及軟件要求的具體的子功能,而和軟件系統(tǒng)中其 他的模塊的接口是簡(jiǎn)單的。*:模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。*:按內(nèi)聚性由弱到強(qiáng)排列,內(nèi)聚可以分為以下幾種:偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過(guò) 程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。 *:按耦合性由高到低排列,耦合可以分為以下幾種:內(nèi)容耦合、公共耦合、外部耦合、控 制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。在結(jié)構(gòu)化程序設(shè)計(jì)中,模塊劃分的原則是:模塊內(nèi)具有高內(nèi)聚度,模塊間具有低耦合度。2、總體設(shè)計(jì)(概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)(1總體設(shè)計(jì)(概要設(shè)計(jì)

38、軟件概要設(shè)計(jì)的基本任務(wù)是:1設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu); 2數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì); 3編寫(xiě) 概要設(shè)計(jì)文檔; 4概要設(shè)計(jì)文檔評(píng)審。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖,也稱(chēng)程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符:模塊用一個(gè)矩形表示, 箭頭表示模塊間的調(diào)用關(guān)系。 在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示 模塊調(diào)用過(guò)程中來(lái)回傳遞的信息。 還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息, 空心圓箭 心表示傳遞的是數(shù)據(jù)信息。 經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類(lèi)型:傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表示形 式如下圖: 它們的含義分別是: 程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語(yǔ)列舉如下: 上級(jí)模塊、從屬模塊:上、下兩層模塊a 和b ,且有a 調(diào)用 b

39、 ,則 a 是上級(jí)模塊, b 是從屬 模塊。 原子模塊:樹(shù)中位于葉子結(jié)點(diǎn)的模塊。一 般 模 塊 數(shù) 據(jù) 信 息 控 制 信 息面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法, 利用這些方法可以把數(shù)據(jù)流圖變換成結(jié) 構(gòu)圖表示軟件的結(jié)構(gòu)。數(shù)據(jù)流的類(lèi)型:大體可以分為兩種類(lèi)型,變換型和事務(wù)型。A 、變換型:變換型數(shù)據(jù)處理問(wèn)題的工作過(guò)程大致分為三步,即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出 數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。B 、 事務(wù)型:事務(wù)型數(shù)據(jù)處理問(wèn)題的工作機(jī)理是接受一項(xiàng)事務(wù), 根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì), 選擇分派一個(gè)適當(dāng)?shù)奶幚韱卧?然后給出結(jié)果。(2詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)是為軟件結(jié)構(gòu)圖中的每一個(gè)模

40、塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu), 用某種選定的表達(dá) 工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。*:詳細(xì)設(shè)計(jì)的任務(wù)是確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu),不同于編碼或編程。常用的過(guò)程設(shè)計(jì)(即詳細(xì)設(shè)計(jì)工具有以下幾種:圖形工具:程序流程圖、 N-S (方盒圖 、 PAD (問(wèn)題分析圖和 HIPO (層次圖 +輸入 /處理 /輸出圖 。表格工具:判定表。語(yǔ)言工具:PDL (偽碼3.4 軟件測(cè)試1、軟件測(cè)試定義:使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程,其目的在于檢驗(yàn)它 是否滿(mǎn)足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。*:軟件測(cè)試的目的:盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤,不能也不可能證明程序沒(méi)有錯(cuò)誤。軟 件測(cè)試的關(guān)鍵是設(shè)

41、計(jì)測(cè)試用例,一個(gè)好的測(cè)試用例能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤。2、軟件測(cè)試方法:靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。 (1白盒測(cè)試白盒測(cè)試方法也稱(chēng)為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。 它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過(guò)程, 檢查內(nèi) 部成分,以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。白盒測(cè)試的基本原則:保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次; 保證所測(cè)模塊所有判斷 的每一分支至少執(zhí)行一次; 保證所測(cè)模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一 次;驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。*:白盒測(cè)試法的測(cè)試用例是根據(jù)程序的內(nèi)部邏輯來(lái)設(shè)計(jì)的,主要用軟件的單元測(cè)試,主要 方法有邏輯覆蓋、基本路徑測(cè)試等。A 、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內(nèi)部

42、的邏輯結(jié)構(gòu)為基礎(chǔ)的測(cè)試用例設(shè)計(jì)技術(shù)。通 常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。語(yǔ)句覆蓋:選擇足夠的測(cè)試用例,使得程序中每一個(gè)語(yǔ)句至少都能被執(zhí)行一次。路徑覆蓋:執(zhí)行足夠的測(cè)試用例,使程序中所有的可能的路徑都至少經(jīng)歷一次。判定覆蓋:使設(shè)計(jì)的測(cè)試用例保證程序中每個(gè)判斷的每個(gè)取值分支 (T 或 F 至少經(jīng)歷一次。 條件覆蓋:設(shè)計(jì)的測(cè)試用例保證程序中每個(gè)判斷的每個(gè)條件的可能取值至少執(zhí)行一次。 判斷 -條件覆蓋:設(shè)計(jì)足夠的測(cè)試用例,使判斷中每個(gè)條件的所有可能取值至少執(zhí)行一次, 同時(shí)每個(gè)判斷的所有可能取值分支至少執(zhí)行一次。*:邏輯覆蓋的強(qiáng)度依次是:語(yǔ)句覆蓋 <路徑覆蓋 <判定覆蓋

43、<條件覆蓋 <判斷 -條件覆蓋。 B 、基本路徑測(cè)試。其思想和步驟是,根據(jù)軟件過(guò)程性描述中的控制流程確定程序的環(huán)路復(fù) 雜性度量, 用此度量定義基本路徑集合, 并由此導(dǎo)出一組測(cè)試用例, 對(duì)每一條獨(dú)立執(zhí)行路徑 進(jìn)行測(cè)試。(2黑盒測(cè)試黑盒測(cè)試方法也稱(chēng)為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。 黑盒測(cè)試是對(duì)軟件已經(jīng)實(shí)現(xiàn)的功能是否滿(mǎn)足 需求進(jìn)行測(cè)試和驗(yàn)證。黑盒測(cè)試主要診斷功能不對(duì)或遺漏、 接口錯(cuò)誤、 數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)錯(cuò)誤、 性能錯(cuò)誤、 初始化和終止條件錯(cuò)誤。黑盒測(cè)試不關(guān)心程序內(nèi)部的邏輯, 只是根據(jù)程序的功能說(shuō)明來(lái)設(shè)計(jì)測(cè)試用例, 主要方法有等 ,然后從每個(gè)等價(jià)類(lèi)中選取數(shù)據(jù)作為測(cè)試用例。BC 編寫(xiě)檢查這

44、些錯(cuò)誤的用例。3、軟件測(cè)試過(guò)程一般按 4個(gè)步驟進(jìn)行:單元測(cè)試、集成測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試。(1單元測(cè)試 發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。 單元測(cè)試根據(jù)程序的內(nèi)部結(jié)構(gòu)來(lái)設(shè)計(jì)測(cè)試用例, 其依據(jù)是詳細(xì)設(shè)計(jì)說(shuō)明書(shū)和源程序。 單元測(cè) 試的技術(shù)可以采用靜態(tài)分析和動(dòng)態(tài)測(cè)試。 對(duì)動(dòng)態(tài)測(cè)試通常以白盒測(cè)試為主, 輔之以黑盒測(cè)試。 單元測(cè)試的內(nèi)容包括:模塊接口測(cè)試、局部數(shù)據(jù)結(jié)構(gòu)測(cè)試、錯(cuò)誤處理測(cè)試和邊界測(cè)試。*:在進(jìn)行單元測(cè)試時(shí),要用一些輔助模塊去模擬與被測(cè)模塊相聯(lián)系的其他模塊,即為被測(cè) 子模塊的所有功能帶入。 (2集成測(cè)試 主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。 集成測(cè)試的依據(jù)是概要設(shè)計(jì)說(shuō)明書(shū)。集成測(cè)試所涉及的內(nèi)容包

45、括:軟件單元的接口測(cè)試、 全局?jǐn)?shù)據(jù)結(jié)構(gòu)測(cè)試、 邊界條件和非法輸 入的測(cè)試等。集成測(cè)試通常采用兩種方式:非增量方式組裝與增量方式組裝。所有模塊組裝在一起進(jìn)行測(cè)試,最終得到要求的軟件系統(tǒng)。 在組裝的過(guò)程中邊連接邊測(cè)試, 以發(fā)現(xiàn)連接過(guò)程中產(chǎn)生的問(wèn)題。 最 后通過(guò)增殖逐步組裝成要求的軟件系統(tǒng)。 增量方式組裝又包括自頂向下、 自底向上、 自頂向 下與自底向上相結(jié)合等三種方式。(3確認(rèn)測(cè)試 確認(rèn)測(cè)試的主要依據(jù)是軟件需求規(guī)格說(shuō)明書(shū)。確認(rèn)測(cè)試主要運(yùn)用黑盒測(cè)試法。(4系統(tǒng)測(cè)試矛盾的地方。 系統(tǒng)測(cè)試的測(cè)試用例應(yīng)根據(jù)需求分析規(guī)格說(shuō)明來(lái)設(shè)計(jì),并在實(shí)際使用環(huán)境下來(lái)運(yùn)行。系統(tǒng)測(cè)試的具體實(shí)施一般包括:功能測(cè)試、 性能測(cè)試、

46、 操作測(cè)試、 配置測(cè)試、 外部接口測(cè)試、 安全性測(cè)試等。3.5 程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤, 主要在開(kāi)發(fā)階段進(jìn)行, 調(diào)試程序應(yīng)該由編制源 程序的程序員來(lái)完成。程序調(diào)試的基本步驟:(1錯(cuò)誤定位; (2糾正錯(cuò)誤; (3回歸測(cè)試。*:軟件的調(diào)試后要進(jìn)行回歸測(cè)試,防止引進(jìn)新的錯(cuò)誤。軟件調(diào)試可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。 靜態(tài)調(diào)試主要是指通過(guò)人的思維來(lái)分析源程序代碼和 排錯(cuò),是主要的調(diào)試手段,而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。對(duì)軟件主要的調(diào)試方法可以采用:(1強(qiáng)行排錯(cuò)法。主要方法有:通過(guò)內(nèi)存全部打印來(lái)排錯(cuò);在程序特定部位設(shè)置打印語(yǔ)句; 自動(dòng)調(diào)試工具。(2回溯法。發(fā)現(xiàn)了錯(cuò)誤,分析錯(cuò)誤征兆,確定發(fā)

47、現(xiàn)“癥狀”的位置。一般用于小程序。(3原因排除法。是通過(guò)演繹、歸納和二分法來(lái)實(shí)現(xiàn)的。1演繹法。根據(jù)已有的測(cè)試用例,設(shè)想及枚舉出所有可能出錯(cuò)的原因作為假設(shè);然后再用 原始測(cè)試數(shù)據(jù)或新的測(cè)試, 從中逐個(gè)排除不可能正確的假設(shè); 最后, 再用測(cè)試數(shù)據(jù)驗(yàn)證余下 的假設(shè)確定出錯(cuò)的原因。2歸納法。從錯(cuò)誤征兆著手,通過(guò)分析它們之間的關(guān)系來(lái)找出錯(cuò)誤。大致分四步:收集有 關(guān)的數(shù)據(jù);組織數(shù)據(jù);提出假設(shè);證明假設(shè)。3二分法。在程序的關(guān)鍵點(diǎn)給變量賦正確值,然后運(yùn)行程序并檢查程序的輸出。如果輸出 結(jié)果正確,則錯(cuò)誤原因在程序的前半部分;反之,錯(cuò)誤原因在程序的后半部分。本章應(yīng)考點(diǎn)撥:本章在筆試中一般占 8分左右,約 3道選擇

48、題, 1道填空題,是公共基礎(chǔ)部 分比較重要的一章。從出題的深度來(lái)看,本章主要考察對(duì)基本概念的識(shí)記,有少量對(duì)基本 原理的理解,沒(méi)有實(shí)際運(yùn)用,因此考生在復(fù)習(xí)本章時(shí),重點(diǎn)應(yīng)放在基本概念的記憶和基本 原理的理解上。第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)管理系統(tǒng)(1數(shù)據(jù):實(shí)際上就是描述事物的符號(hào)記錄。數(shù)據(jù)的特點(diǎn):有一定的結(jié)構(gòu),有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類(lèi)型,如整型、實(shí) 型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值,如整型(INT 值 15。(2 多種應(yīng)用數(shù)據(jù)的集成,并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的, 具有集成與共享的特點(diǎn)

49、, 亦即是數(shù)據(jù)庫(kù) 集中了各種應(yīng)用的數(shù)據(jù),進(jìn)行統(tǒng)一的構(gòu)造和存儲(chǔ),而使它們可被不同應(yīng)用程序所使用。( 3據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等,是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能:1數(shù)據(jù)模式定義。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫(kù)構(gòu)建模式,也就是為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框 架。2數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。3數(shù)據(jù)操縱。數(shù)據(jù)庫(kù)管理系統(tǒng)為用戶(hù)使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)提供方便,它一般提供如查詢(xún)、 插入、修改以及刪除數(shù)據(jù)的功能。此外,它自身還具有做簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)的能力,而 且還可以與某些過(guò)程性語(yǔ)言結(jié)合,使其具有強(qiáng)大的過(guò)程性操作能力。4 數(shù)據(jù)的完整性、 安生性定義與檢

50、查。 數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有內(nèi)在語(yǔ)義上的關(guān)聯(lián)性與一致性, 它們構(gòu)成了數(shù)據(jù)的完整性, 數(shù)據(jù)的完整性是保證數(shù)據(jù)庫(kù)中數(shù)據(jù)正確的必要條件, 因此必須經(jīng) 常檢查以維護(hù)數(shù)據(jù)正確。 數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有共享性, 而數(shù)據(jù)共享可能會(huì)引發(fā)數(shù)據(jù)的非法使 用, 因此必須要對(duì)數(shù)據(jù)正確使用做出必要的規(guī)定, 并在使用時(shí)做檢查, 這就是數(shù)據(jù)的安全性。 數(shù)據(jù)完整性與安全性的維護(hù)是數(shù)據(jù)庫(kù)系統(tǒng)的基本功能。5數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫(kù)是一個(gè)集成、共享的數(shù)據(jù)集合體,它能為多個(gè)應(yīng) 用程序服務(wù), 所以就存在著多個(gè)應(yīng)用程序?qū)?shù)據(jù)庫(kù)的并發(fā)操作。 在并發(fā)操作中如果不加控制 和管理,多個(gè)應(yīng)用程序間就會(huì)相互干擾,從而對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)造成破壞。因此

51、,數(shù)據(jù)庫(kù)管 理系統(tǒng)必須對(duì)多個(gè)應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破壞, 這就是數(shù)據(jù)庫(kù)的 并發(fā)控制。 數(shù)據(jù)庫(kù)中的數(shù)據(jù)一旦遭到破壞, 數(shù)據(jù)庫(kù)管理系統(tǒng)必須有能力及時(shí)進(jìn)行恢復(fù), 這就 是數(shù)據(jù)庫(kù)的故障恢復(fù)。6數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫(kù)管理系統(tǒng)提供對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)的多種服務(wù)功能,如數(shù)據(jù)拷貝、轉(zhuǎn)存、 重組、性能監(jiān)測(cè)、分析等。(4 (5(人員、硬件平臺(tái)(硬件、軟件平臺(tái)(軟件五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。(6數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng):由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。*:數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題。2、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展數(shù)據(jù)庫(kù)管理發(fā)展至今已經(jīng)歷了三個(gè)階段:人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。 下表是數(shù)

52、據(jù)管理三個(gè)階段的比較: 3、數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn) (1數(shù)據(jù)的高集成性。(2數(shù)據(jù)的高共享性與低冗余性。*:數(shù)據(jù)庫(kù)系統(tǒng)可以減少數(shù)據(jù)冗余,但無(wú)法避免一切冗余。(3 程序而不依賴(lài)于應(yīng)用程序。 也就是說(shuō), 數(shù)據(jù)的邏輯結(jié)構(gòu)、 存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影 響應(yīng)用程序。數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性?xún)杉?jí)。 1物理存儲(chǔ)的更換、 存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu), 從而不 致引起應(yīng)用程序的變化。 2數(shù)據(jù)間聯(lián)系等,不需要相應(yīng)修改應(yīng)用程序,這就是數(shù)據(jù)的邏輯獨(dú)立性。 (4數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個(gè)方面:1數(shù)據(jù)的完整性檢查:檢查數(shù)據(jù)庫(kù)中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。 2數(shù)據(jù)

53、的安全性保護(hù):檢查數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)者以防止非法訪(fǎng)問(wèn)。3并發(fā)控制:控制多個(gè)應(yīng)用的并發(fā)訪(fǎng)問(wèn)所產(chǎn)生的相互干擾以保證其正確性。 4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 (1數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式:1(應(yīng)用公共數(shù)據(jù)視圖。 2它是用戶(hù)的數(shù)據(jù)視圖, 也就是用戶(hù)所見(jiàn)到的數(shù)據(jù)模式, 它由概念模式推導(dǎo)而出。3 性主要體現(xiàn)在操作系統(tǒng)及文件級(jí)上,它還未深入到設(shè)備級(jí)上(如磁盤(pán)及磁盤(pán)操作 。內(nèi)模式 對(duì)一般用戶(hù)是透明的,但它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能。 (2數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射:1 結(jié)構(gòu)發(fā)生變化時(shí),通過(guò)修改相應(yīng)的概念模式 /內(nèi)模式的映射,使得數(shù)據(jù)庫(kù)的邏輯模式不變, 其外模式不變,應(yīng)用程序不用修改,從而保證數(shù)據(jù)具有很高的物理獨(dú)立性。 2變化時(shí)

54、,通過(guò)修改相應(yīng)的外模式 /邏輯模式映射,使得用戶(hù)所使用的那部分外模式不變,從 而應(yīng)用程序不必修改,保證數(shù)據(jù)具有較高的邏輯獨(dú)立性。 4.2 數(shù)據(jù)模型 1、數(shù)據(jù)模型(1數(shù)據(jù)模型的概念:是數(shù)據(jù)特征的抽象,它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài) 行為和約束條件,為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。(2數(shù)據(jù)模型所描述的內(nèi)容有三個(gè)部分,它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。 1數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)是所研究的對(duì)象類(lèi)型的集合,包括與數(shù)據(jù)類(lèi)型、內(nèi)容、性質(zhì)有關(guān)的 對(duì)象,以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對(duì)象。它用于描述系統(tǒng)的靜態(tài)特性。2數(shù)據(jù)操作:數(shù)據(jù)操作是對(duì)數(shù)據(jù)庫(kù)中各種對(duì)象(型的實(shí)例(值允許執(zhí)行的操作的集合, 包

55、括操作的含義、符號(hào)、操作規(guī)則及實(shí)現(xiàn)操作的語(yǔ)句等。它用于描述系統(tǒng)的動(dòng)態(tài)特性。3數(shù)據(jù)的約束條件:數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù) 模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則, 用以限定符號(hào)數(shù)據(jù)模型的數(shù)據(jù)庫(kù)狀態(tài)及狀態(tài) 的變化,以保證數(shù)據(jù)的正確、有效和相容。(3數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類(lèi):1概念數(shù)據(jù)模型:簡(jiǎn)稱(chēng)概念模型,是對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián) 系的刻畫(huà)。概念模型主要有:E-R 模型 (實(shí)體聯(lián)系模型 、擴(kuò)充的 E-R 模型、面向?qū)ο竽Ｐ图?謂詞模型等。2邏輯數(shù)據(jù)模型:又稱(chēng)數(shù)據(jù)模型,是一種面向數(shù)據(jù)庫(kù)系統(tǒng)的模型,該模型著重于在數(shù)據(jù)庫(kù) 系統(tǒng)一級(jí)的實(shí)現(xiàn)。 邏輯數(shù)據(jù)模型主要有:層次模型、 網(wǎng)狀模型、 關(guān)系模型、 面向?qū)ο竽Ｐ偷取?3物理數(shù)據(jù)模型:又稱(chēng)物理模型,它是一種面向計(jì)算機(jī)物理表示的模型,此模型給出了數(shù) 據(jù)模型在計(jì)算機(jī)上物理結(jié)構(gòu)的表示。2、實(shí)體聯(lián)系模型及 E-R 圖(1 E-R 模型的基本概念:1實(shí)體:現(xiàn)實(shí)世界中的事物。2屬性:事物的特性。3聯(lián)系:現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。 E-R 模型三個(gè)基本概念之間的聯(lián)接關(guān)系:1實(shí)體集(聯(lián)系與屬性間的聯(lián)接關(guān)系; 2實(shí)體 (集與聯(lián)系。*:E-R 模型的基本成分是實(shí)體和聯(lián)系。(2 E-R 模型的圖示法:1實(shí)體集:用矩