C語言-公共基礎(chǔ)

1、Linyi university Department of Computer Science公共基礎(chǔ)知識公共基礎(chǔ)知識臨沂大學(xué)信息學(xué)院臨沂大學(xué)信息學(xué)院 公共基礎(chǔ)知識公共基礎(chǔ)知識 公共基礎(chǔ)知識公共基礎(chǔ)知識 公共基礎(chǔ)知識公共基礎(chǔ)知識 公共基礎(chǔ)知識公共基礎(chǔ)知識程序設(shè)計的基本概念程序設(shè)計的基本概念CPU內(nèi)存磁盤程序設(shè)計的基本概念程序設(shè)計的基本概念v人和計算機交流的語言，但計算機值只識別人和計算機交流的語言，但計算機值只識別0和和1。程序設(shè)計的基本概念程序設(shè)計的基本概念n給定一個問題n分析問題（算法）n編程（用一種計算機語言）n編程的方法：結(jié)構(gòu)化的方法、面向?qū)ο蟮姆椒ň幊痰姆椒ǎ航Y(jié)構(gòu)化的方法、面向?qū)ο蟮?/p>

2、方法 第第1章數(shù)據(jù)結(jié)構(gòu)與算法章數(shù)據(jù)結(jié)構(gòu)與算法algorithm1 1、算法的基本概念、算法的基本概念 算法算法解題方案的準(zhǔn)確而完整的描述解題方案的準(zhǔn)確而完整的描述 算法具有可行性、可行性、確定性確定性、有窮性有窮性、輸入輸入和輸出輸出（擁有足夠的情報）等4個重要特性。第第1章數(shù)據(jù)結(jié)構(gòu)與算法章數(shù)據(jù)結(jié)構(gòu)與算法（1 1）時間復(fù)雜度）時間復(fù)雜度v時間復(fù)雜度時間復(fù)雜度指執(zhí)行算法所需要的基本元算次數(shù)來度量v常用的度量方法：平均性態(tài)、最壞情況復(fù)雜性第第1章數(shù)據(jù)結(jié)構(gòu)與算法章數(shù)據(jù)結(jié)構(gòu)與算法（2 2）空間復(fù)雜度）空間復(fù)雜度n 一般是指執(zhí)行這個算法所需要的內(nèi)存空間。n所需內(nèi)存空間包括：n算法程序所占的空間、n輸入的

3、初始數(shù)據(jù)所占的存儲空間n算法執(zhí)行過程所需要的額外存儲空間。第第1章數(shù)據(jù)結(jié)構(gòu)與算法章數(shù)據(jù)結(jié)構(gòu)與算法-1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)Data Structure1 1、數(shù)據(jù)結(jié)構(gòu)的基本概念、數(shù)據(jù)結(jié)構(gòu)的基本概念n數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合n數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和和數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（1 1）數(shù)據(jù)的邏輯結(jié)構(gòu)：）數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的前后件關(guān)系指數(shù)據(jù)元素之間的前后件關(guān)系冬冬春春夏夏秋秋例例1：一年四季的邏輯結(jié)構(gòu)：一年四季的邏輯結(jié)構(gòu) 父親父親兒子兒子女兒女兒例2：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（2 2）數(shù)據(jù)的物理結(jié)

4、構(gòu)）數(shù)據(jù)的物理結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的存放形式稱為數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)（也稱為數(shù)據(jù)的存儲結(jié)構(gòu)）數(shù)據(jù)的物理結(jié)構(gòu)（也稱為數(shù)據(jù)的存儲結(jié)構(gòu)）1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)2、幾個術(shù)語：n前件（或前驅(qū)）n后件（或后繼）n根結(jié)點n葉子結(jié)點冬冬春春夏夏秋秋父親父親兒子兒子女兒女兒1.2數(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)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)：3 3、線性結(jié)構(gòu)與非線性結(jié)構(gòu)：、線性結(jié)構(gòu)與非線性結(jié)構(gòu)：n線性結(jié)構(gòu)線性結(jié)構(gòu)n有且只有一個根結(jié)點有且只有一個根結(jié)點n每一個結(jié)點最多有一個前件，也最多有一個后件。每一個結(jié)點最多有一個前件，也最多有一個后

5、件。n注意：在線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還注意：在線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性的。應(yīng)是線性的。D DA AB BC Cn非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。1.3線性表（線性表（Linear List）三、線性表三、線性表：具有線性結(jié)構(gòu)的有限序列。 1 1、線性表的特點：、線性表的特點： （1 1）有且只有一個根結(jié)點，它無前件；）有且只有一個根結(jié)點，它無前件； （2 2）有且只有一個終端結(jié)點，它無后件；有且只有一個終端結(jié)點，它無后件； （3 3）除根結(jié)點和終端結(jié)點外，其它所有結(jié)點有且）除根結(jié)點和終端結(jié)點外，其它所有結(jié)點有且 僅有一個前件也有且

6、只有一個后件。僅有一個前件也有且只有一個后件。 冬冬春春夏夏秋秋1.3線性表（線性表（Linear List）2、線性表的、線性表的 順序存儲結(jié)構(gòu)n順序存儲結(jié)構(gòu)特點：順序存儲結(jié)構(gòu)特點：（1）所有元素所占的存儲空間是連續(xù)的。）所有元素所占的存儲空間是連續(xù)的。（2）各數(shù)據(jù)元素在存儲空間中是按邏輯順序）各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。依次存放的。1.3線性表（線性表（Linear List）3 3、 插入 與與 刪除 操作操作（1 1）插入）插入（假設(shè)原表中有（假設(shè)原表中有n個元算）個元算）n插入插入一個元素時移動元素的數(shù)目：插入插入一個元素時移動元素的數(shù)目：n最少移動的元素數(shù)目：最少

7、移動的元素數(shù)目：0 0個個n插入時最多移動的元素數(shù)目：插入時最多移動的元素數(shù)目：n個個n插入時平均移動的元素數(shù)目：插入時平均移動的元素數(shù)目：n/2個個1.3線性表（線性表（Linear List）（2）刪除（假設(shè)原表中有）刪除（假設(shè)原表中有n個元算）個元算）n刪除一個元素時移動的數(shù)據(jù)元素數(shù)目刪除一個元素時移動的數(shù)據(jù)元素數(shù)目n刪除時最少移動的元素數(shù)目：刪除時最少移動的元素數(shù)目：0個個n刪除時最多移動的元素數(shù)目：刪除時最多移動的元素數(shù)目：n-1個個n刪除時平均移動的元素數(shù)目：刪除時平均移動的元素數(shù)目：n-1/2個個1.4棧和隊列棧和隊列四、堆棧和隊列的定義四、堆棧和隊列的定義1、棧、棧n棧是限定只

8、能在表的一端進行插入和刪除的特殊的棧是限定只能在表的一端進行插入和刪除的特殊的線性表。線性表。n棧是：先進后出棧是：先進后出(FILO)ntop、bottom指針指針nbottom指針不動、指針不動、top指針根據(jù)入棧和出棧來回移動指針根據(jù)入棧和出棧來回移動 a1 a2 . an進棧進棧出棧出棧棧頂棧頂棧底棧底topbottom1.4棧和隊列棧和隊列n棧的運算（1）入棧（2）出棧（或退棧）（3）讀棧n上溢、下溢上溢、下溢隊列隊列2 2、隊列：、隊列：n限定只能在一端進行插入，在表的另一端進行刪除的限定只能在一端進行插入，在表的另一端進行刪除的線性表線性表 。（隊頭出隊，隊尾入隊）。（隊頭出隊，

9、隊尾入隊）n此種結(jié)構(gòu)稱為此種結(jié)構(gòu)稱為先進先出（先進先出（FIFO）表）表。 a1 , a2 , a3 , a4 , an-1 , an 隊頭隊尾n front和 rear指針nFront總是指向隊頭元素的前一個空間nrear指向隊尾最后一個元素n隊列的主要運算隊列的主要運算（1）入隊）入隊 從隊尾入隊從隊尾入隊（2）退隊（出隊）退隊（出隊） 從對頭出隊從對頭出隊FEDCBAH12345678910frontrear隊頭隊尾n循環(huán)隊列 FEDCBAH12345678910frontrearFEDCBAH12345678910front入隊X,Y,Z 元素后的指針變化XYZrear初始隊列YXFE

10、DCBAZ12345678910frontrear H元算退隊后的指針變化H隊列隊列總結(jié)（假設(shè)隊列的總空間個數(shù)為m）：n循環(huán)隊列采用順序存儲結(jié)構(gòu)n隊尾rear指針值可以比對頭front指針值大，隊尾rear指針值可以比對頭front指針值小。n如rear=front則隊列為空，或滿隊，元素個數(shù)為0或mn如rearfront則對中的元素個數(shù)為rear-frontn如rearfront則對中的元素個數(shù)為m-front+rear1.5線性鏈表線性鏈表1 1、線性鏈表的基本概念：、線性鏈表的基本概念：n線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 單向鏈表單向鏈表雙向鏈表雙向鏈表1.5線性鏈表線性鏈表v循環(huán)鏈表

11、：循環(huán)鏈表：1.5線性鏈表線性鏈表v 鏈接存儲結(jié)構(gòu)特點鏈接存儲結(jié)構(gòu)特點：n比順序存儲結(jié)構(gòu)占用的空間多(每個節(jié)點都由數(shù)據(jù)域和指針域組成)。n邏輯上相鄰的節(jié)點物理上不必相鄰：即存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系順序可以不一致。n插入、刪除靈活： (不必移動節(jié)點，只要改變節(jié)點中的指針)。n查找結(jié)點時鏈?zhǔn)酱鎯σ软樞虼鎯β?.6樹與二叉樹樹與二叉樹n樹的基本概念：樹的基本概念：n樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每一個結(jié)點，都可以有不止一個后件，除根外的所有結(jié)點，都有且只有一個前件。42316789101213145An基本概念n度：一個結(jié)點所擁有的后件個數(shù)為該結(jié)點的度n樹的

12、度：在一棵樹中所有結(jié)點中的最大的度n深度：樹的最大層次42316789101213155n一棵二叉樹每個結(jié)點的度有幾種情況？n三種情況：度為0，度為1，度為2n所以一棵二叉樹的總結(jié)點數(shù)為：n度為0的結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為2的結(jié)點數(shù)n二叉樹1.6樹與二叉樹樹與二叉樹n二叉樹的性質(zhì)：二叉樹的性質(zhì)：l在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多 一個。l例子例子1 1：某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有 19 19 個葉子結(jié)點。1.6樹與二叉樹樹與二叉樹n滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹l滿二叉樹是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。l完

13、全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。l注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。v完全二叉樹的特點：完全二叉樹的特點：除最后一層外，每一層都取最大結(jié)點數(shù)，除最后一層外，每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置最后一層結(jié)點都集中在該層最左邊的若干位置1.6樹與二叉樹樹與二叉樹性質(zhì)性質(zhì)2 2：滿二叉樹的第i層上有2 i-1（i 1）個結(jié)點423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。1.6樹與二叉樹樹與二叉樹性質(zhì)性質(zhì)

14、3 3：深度為深度為h h的滿二叉樹中含有的滿二叉樹中含有2 2h h-1 -1個結(jié)點個結(jié)點423167891011121314155此樹的深度此樹的深度h=4h=4，共有，共有2 24 4-1=15-1=15個節(jié)點。個節(jié)點。1.6樹與二叉樹樹與二叉樹n二叉樹的遍歷n二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。1、前序遍歷2、中序遍歷3、后序遍歷1.6樹與二叉樹樹與二叉樹考試題目：考試題目：1 1、設(shè)一棵二叉樹的中序遍歷結(jié)果為、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,DBEAFC, 前序遍歷結(jié)果為前序遍歷結(jié)果為ABDECFABDECF，則后序遍歷結(jié)，則后序遍歷結(jié) 果為：果為： DEBFC

15、ADEBFCA 1.6樹與二叉樹樹與二叉樹2、一棵二叉樹有25個結(jié)點，其中5個是葉子結(jié)點，則度為1的結(jié)點數(shù)為（ ） 例題講解例題講解1、設(shè)一棵完全二叉樹共有700個結(jié)點，則 在該二叉樹中有 350 350 個葉子結(jié)點。2、在深度為5的滿二叉樹中，葉子結(jié)點的 個數(shù)為（ C C ） A) 32 B) 31 C) 16 D) 15例題講解例題講解1 1、設(shè)一棵二叉樹的中序遍歷結(jié)果為、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,DBEAFC, 前序遍歷結(jié)果為前序遍歷結(jié)果為ABDECFABDECF，則后序遍歷結(jié)，則后序遍歷結(jié) 果為：果為： DEBFCADEBFCA 2 2、已知一棵二叉樹前序遍歷和中序遍歷

16、分別、已知一棵二叉樹前序遍歷和中序遍歷分別 為為ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，則該二叉樹，則該二叉樹 的后序遍歷為（的后序遍歷為（ B B ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCA B) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG1.7查找技術(shù)查找技術(shù)n查找查找又稱為檢索又稱為檢索 1 1、查找的概念、查找的概念 2 2、查找的分類、查找的分類l查找可分為查找可分為順序查找順序查找和和二分法查找二分法查找兩種。兩種。l順序查找比較的次數(shù)最壞情況下為順序

17、查找比較的次數(shù)最壞情況下為n n次次l二分查找的次數(shù)最壞情況下為二分查找的次數(shù)最壞情況下為log2n次次.l二分查找的前提是：二分查找的前提是：數(shù)據(jù)必須是有序的。數(shù)據(jù)必須是有序的。1.7查找技術(shù)查找技術(shù)3、查找的注意事項n如采用順序存儲，如果是有序線性表有序線性表，則可以采用二分法查找或順序查找，二分查找最壞查找次數(shù)為二分查找最壞查找次數(shù)為：loglog2 2n n次，順序查找最壞查找次數(shù)為：次，順序查找最壞查找次數(shù)為：n n次次；如果是無；如果是無序的序的只能用順序查找，最壞查找次數(shù)為：n次。n如采用鏈?zhǔn)酱鎯?，不管?shù)據(jù)是有序的還是無序的，則只能采用順序查找，最壞查找次數(shù)為：n n次次1.8排

18、序技術(shù)排序技術(shù)1 1、交換類排序：、交換類排序：（1 1）冒泡排序法：最壞比較次數(shù)為）冒泡排序法：最壞比較次數(shù)為n(n-1)/2n(n-1)/2（2 2）快速排序法：是對冒泡排序的改進）快速排序法：是對冒泡排序的改進, ,最壞比較最壞比較次數(shù)為次數(shù)為n(n-1)/2n(n-1)/21.8排序技術(shù)排序技術(shù)2 2、插入類排序、插入類排序：(1)簡單插入排序法最壞情況需要n(n-1)/2次比較；(2)希爾排序法最壞情況需要o（n 1.5）次比較。1.8排序技術(shù)排序技術(shù)3 3、選擇類排序：、選擇類排序： （1）簡單選擇排序法最壞情況需要n(n-1)/2次比較；（2）堆排序法最壞情況需要o（nlog2

19、n）次比較。第第2章程序設(shè)計基礎(chǔ)章程序設(shè)計基礎(chǔ)一、程序設(shè)計方法與風(fēng)格一、程序設(shè)計方法與風(fēng)格 1 1、程序設(shè)計方法、程序設(shè)計方法n結(jié)構(gòu)化方法結(jié)構(gòu)化方法n面向?qū)ο蟮姆椒嫦驅(qū)ο蟮姆椒?、程序設(shè)計的良好風(fēng)格、程序設(shè)計的良好風(fēng)格n清晰第一、效率第二清晰第一、效率第二n程序應(yīng)簡單、可讀性好、易于使用和維護，程序應(yīng)簡單、可讀性好、易于使用和維護，第第2章程序設(shè)計基礎(chǔ)章程序設(shè)計基礎(chǔ)1、原則、原則n自頂向下、逐步求精、模塊化、限制使用自頂向下、逐步求精、模塊化、限制使用GOTO語句語句2、結(jié)構(gòu)化程序的、結(jié)構(gòu)化程序的基本結(jié)構(gòu)基本結(jié)構(gòu)程序結(jié)構(gòu)僅由程序結(jié)構(gòu)僅由順序順序、選擇選擇和和循環(huán)循環(huán)3種結(jié)構(gòu)復(fù)合而成種結(jié)構(gòu)復(fù)合

20、而成二、結(jié)構(gòu)化程序設(shè)計二、結(jié)構(gòu)化程序設(shè)計 第第2章程序設(shè)計基礎(chǔ)章程序設(shè)計基礎(chǔ)三、面向?qū)ο蟮某绦蛟O(shè)計方法三、面向?qū)ο蟮某绦蛟O(shè)計方法n面向?qū)ο蟮姆椒ㄒ詫ο鬄楹诵?，結(jié)構(gòu)化的程序設(shè)計方法以對象為核心，結(jié)構(gòu)化的程序設(shè)計方法以算法為核心以算法為核心第第2章程序設(shè)計基礎(chǔ)章程序設(shè)計基礎(chǔ)2 2、幾個術(shù)語：、幾個術(shù)語：n對象：n屬性：對象所包含的信息。n操作：描述了對象的功能n封裝性n類：類是一組具有相同屬性和相同操作的對象的集合。n類和對象的關(guān)系：對象是類的實例。n消息：對象之間傳遞的信息n繼承：使用已有的類定義作為基礎(chǔ)建立新類。n多態(tài)性：是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。第第3章軟件

21、工程基礎(chǔ)章軟件工程基礎(chǔ)一、基本概念一、基本概念 1、軟件的定義n軟件：是包括程序、數(shù)據(jù)和有關(guān)文檔的完整集合。n軟件分類：系統(tǒng)軟件、應(yīng)用軟件、支撐軟件第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)2、軟件危機與軟件工程、軟件危機與軟件工程n軟件危機：軟件危機：泛指在計算機軟件的開發(fā)和維護過程中所泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴(yán)重問題（遇到的一系列嚴(yán)重問題（成本高、質(zhì)量難以保證、生成本高、質(zhì)量難以保證、生產(chǎn)率低等產(chǎn)率低等）。）。 n軟件工程：軟件工程：軟件工程是指應(yīng)用工程、科學(xué)、數(shù)學(xué)的原軟件工程是指應(yīng)用工程、科學(xué)、數(shù)學(xué)的原理與方法研制、維護計算機軟件的有關(guān)技術(shù)及管理方理與方法研制、維護計算機

22、軟件的有關(guān)技術(shù)及管理方法。法。第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)3、軟件生命周期、軟件生命周期n軟件生命周期n概念：將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。n階段：分為軟件定義、軟件開發(fā)及軟件運行維護3個時期。n6個主要活動階段：個主要活動階段：n可行性研究與計劃制定可行性研究與計劃制定n需求分析需求分析n概要設(shè)計概要設(shè)計n詳細(xì)設(shè)計詳細(xì)設(shè)計n實現(xiàn)實現(xiàn)n軟件測試軟件測試n使用使用n維護維護n退役退役定義階段開發(fā)階段維護階段第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)n利用軟件工程的原理如何進行軟件開發(fā)? 首先進行：需求分析n什么是需求分析什么是需求分析 確定系統(tǒng)具備哪些功能、

23、軟件系統(tǒng)必須做什么。確定系統(tǒng)具備哪些功能、軟件系統(tǒng)必須做什么。n需求分析階段的工作需求分析階段的工作 （1）需求獲?。┬枨螳@取 （2）需求分析）需求分析 （3）編寫需求規(guī)格說明文檔）編寫需求規(guī)格說明文檔 （4）需求評審）需求評審第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)l采用的方法采用的方法 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法、面向?qū)ο蟮姆治龇椒?第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)二、結(jié)構(gòu)化分析方法二、結(jié)構(gòu)化分析方法1 1、結(jié)構(gòu)化分析方法用到的工具：、結(jié)構(gòu)化分析方法用到的工具：n數(shù)據(jù)流圖數(shù)據(jù)流圖(DFD)：用來描述數(shù)據(jù)流從輸入到輸出的變換流程。n（數(shù)據(jù)流圖：參看課本（數(shù)據(jù)流圖：參看課本69 圖圖3.4）n數(shù)

24、據(jù)字典數(shù)據(jù)字典(DD)：對DFD中出現(xiàn)的被命名的圖形元素的確切解釋。加工（轉(zhuǎn)換）數(shù)據(jù)流存儲文件（數(shù)據(jù)源）源，潭第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)三、結(jié)構(gòu)化設(shè)計方法三、結(jié)構(gòu)化設(shè)計方法 從工程管理的觀點看，軟件設(shè)計包括：概要設(shè)計和詳細(xì)設(shè)計從工程管理的觀點看，軟件設(shè)計包括：概要設(shè)計和詳細(xì)設(shè)計1、軟件設(shè)計的基本原理、軟件設(shè)計的基本原理n模塊獨立性：模塊獨立性： n模塊獨立性度量的兩個標(biāo)準(zhǔn)：內(nèi)聚性、耦合性n模塊獨立性度量原則：高內(nèi)聚低耦合第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)2、概要設(shè)計、概要設(shè)計n概要設(shè)計任務(wù)概要設(shè)計任務(wù)n設(shè)計軟件體系結(jié)構(gòu)：設(shè)計軟件體系結(jié)構(gòu)：劃分模塊以及模塊層次結(jié)構(gòu)劃分模塊以及模塊層次結(jié)構(gòu)

25、臨沂大學(xué)教務(wù)系統(tǒng)學(xué)生管理教師管理職工管理系院管理后勤管理第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)2、詳細(xì)設(shè)計n詳細(xì)設(shè)計的任務(wù)：為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。n常用的設(shè)計工具n程序流程圖程序流程圖： n參看教材P81圖3.18n N-S圖nPAD圖：教材P81-83加工步驟控制流邏輯條件第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)n表格工具：判定表n語言工具：PDL(偽碼）第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)四、軟件測試四、軟件測試 1、軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程；2、軟件測試的方法 （1）靜態(tài)測試與動態(tài)測試 （2）白盒測試與黑盒測

26、試n白盒測試：將軟件看成透明的白盒，根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作是否符合設(shè)計規(guī)格要求。n方法有：邏輯覆蓋、基本路徑測試n黑盒測試：對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進行測試。n方法有：等價類劃分法、邊界值法、錯誤推測法、因果圖法第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)3、軟件測試的實施、軟件測試的實施n單元測試：對軟件設(shè)計的各模塊測試。n集成測試：把模塊組裝起來同時進行測試。n確認(rèn)測試：檢查軟件產(chǎn)品的功能和性能是否符合需求定義n系統(tǒng)測試：在實際運行環(huán)境下對整個系統(tǒng)進行測試第第3章軟件工程基礎(chǔ)章軟件工程基礎(chǔ)五、程序調(diào)試五、程序調(diào)試 n 任務(wù)任務(wù)任務(wù)是診斷和改正程序中的錯誤

27、任務(wù)是診斷和改正程序中的錯誤n 軟件調(diào)試方法軟件調(diào)試方法 1 1、強行排錯法、強行排錯法2 2、回溯法、回溯法3 3、原因排除法、原因排除法（演繹、歸納、二分法（演繹、歸納、二分法) )第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)（一）數(shù)據(jù)庫系統(tǒng)的基本概念（一）數(shù)據(jù)庫系統(tǒng)的基本概念 1 1、幾個術(shù)語、幾個術(shù)語n 數(shù)據(jù)庫(DB：DataBase):有結(jié)構(gòu)的數(shù)據(jù)集合n 數(shù)據(jù)庫管理系統(tǒng)(DBMS：DataBase Management System)n 數(shù)據(jù)庫管理員(DBA： DataBase Administrator)n 數(shù)據(jù)庫系統(tǒng)（DBS: DataBase System）nDB+DBMS+DBA+

28、計算機（硬件、軟件）n 數(shù)據(jù)庫應(yīng)用系統(tǒng)（DBAS: DataBase Application System）第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)2 2、 數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)庫系統(tǒng)的基本特點：n數(shù)據(jù)的高共享性與低冗余性；n數(shù)據(jù)獨立性（數(shù)據(jù)與程序間的互不依賴性）n數(shù)據(jù)的物理獨立性n數(shù)據(jù)物理結(jié)構(gòu)改變的改變不影響應(yīng)用程序n數(shù)據(jù)的邏輯獨立性n數(shù)據(jù)邏輯結(jié)構(gòu)改變的改變不影響應(yīng)用程序第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)3 3、數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系( (三級模式三級模式) )n 概念概念模式：模式：它反映了設(shè)計者的數(shù)據(jù)全局邏輯結(jié)構(gòu)它反映了設(shè)計者的數(shù)據(jù)全局邏輯結(jié)構(gòu)n 外外模

29、式：模式：它反映了用戶部分?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)。它反映了用戶部分?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)。n 內(nèi)內(nèi)模式：模式：反映了數(shù)據(jù)在計算機中的實際存儲形式（物理存儲反映了數(shù)據(jù)在計算機中的實際存儲形式（物理存儲結(jié)構(gòu)與物理存取方法）。結(jié)構(gòu)與物理存取方法）。第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)（二）數(shù)據(jù)模型（二）數(shù)據(jù)模型 數(shù)據(jù)庫設(shè)計的核心1 1、數(shù)據(jù)模型的基本概念、數(shù)據(jù)模型的基本概念n定義：數(shù)據(jù)模型是數(shù)據(jù)特征的抽象n數(shù)據(jù)模型分類：n概念模型n邏輯數(shù)據(jù)模型（數(shù)據(jù)模型）n層次、網(wǎng)狀、關(guān)系n物理模型2、概念模型表示工具：、概念模型表示工具：E-R模型（實體聯(lián)系模型）模型（實體聯(lián)系模型）E-RE-R圖的一個實例圖的一個實例: :學(xué)

30、生課程聯(lián)系學(xué)生課程聯(lián)系的概念模型的概念模型mnn實體：用矩形框表示；n屬性：用橢圓表示n聯(lián)系：用菱形框表示n一對一（1：1）n一對多（1：M或M：1）n多對多（M：N）3 3、關(guān)系模型（具有堅實的理論基礎(chǔ)）、關(guān)系模型（具有堅實的理論基礎(chǔ)）n關(guān)系的數(shù)據(jù)結(jié)構(gòu)：關(guān)系的數(shù)據(jù)結(jié)構(gòu)：n采用二維表來表示采用二維表來表示，每一個二維表稱為一個每一個二維表稱為一個關(guān)系關(guān)系。學(xué) 號姓 名年 齡性 別系 名年 級2005004王小明王小明19女女社會學(xué)社會學(xué)20052005006黃大鵬20男商品學(xué)20052005008張文斌18女法律2005第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基

31、礎(chǔ)職工號姓名職 稱工 資扣 除實 發(fā)基 本津 貼職務(wù)房 租水 電86051陳 平講 師13051200501601122283此表是否是關(guān)系表？為什么？此表是否是關(guān)系表？為什么？第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)n基本概念：基本概念：n鍵或碼n候選鍵或候選碼n主鍵或主碼n外鍵或外碼、n全碼或全鍵學(xué) 號姓 名年 齡性 別系 名年 級2005004王小明王小明19女女社會學(xué)社會學(xué)20052005006黃大鵬20男商品學(xué)20052005008張文斌18女法律2005第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)n關(guān)系中的數(shù)據(jù)約束：關(guān)系中的數(shù)據(jù)約束：n實體完整性約束n參照完整性約束n用戶定義的完整性約束。

32、學(xué)生（學(xué)生（學(xué)號學(xué)號，姓名，性別，專業(yè)號，年齡），姓名，性別，專業(yè)號，年齡）專業(yè)（專業(yè)（專業(yè)號專業(yè)號，專業(yè)名），專業(yè)名）完整性實例完整性實例第第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)章數(shù)據(jù)庫設(shè)計基礎(chǔ)（三）關(guān)系代數(shù)（三）關(guān)系代數(shù) n關(guān)系代數(shù)的基本運算關(guān)系代數(shù)的基本運算并、差、交、投影運算 選擇運算、笛卡兒積運算、除、連接1、并（、并（Union）ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1a1b2c2a1b3c2a2b2c1ABCa1b2c2a1b3c2a2b2c1RSRS （1）兩個關(guān)系列個數(shù)必須一致（2）并運算結(jié)果：列個數(shù)列名不變；記錄為兩個表中的記錄之和并去掉重復(fù)的2. 差差(續(xù)續(xù))ABCa1b1c1a1b2c2a2b2c1ABCa1b1c1ABCa1b2c2a1b3c2a2b2c1RSR-S （1）兩個關(guān)系列數(shù)必須一致（2）差運算結(jié)果：列數(shù)列名不變；記錄為屬于關(guān)系R而不屬于S的記錄。3. 交交 (續(xù)續(xù))ABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1RSR S （1）兩個關(guān)系列數(shù)必須一致（2）交運算結(jié)果：列數(shù)列名不變；記錄為兩個表中所共有的記錄。4、投影、投影:A(R) ABa11a12a23（1）投影運算結(jié)果： 列數(shù)是原