1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 主講：張 靜 二系二教,學(xué)習(xí)內(nèi)容及要求,數(shù)據(jù)結(jié)構(gòu) 掌握數(shù)據(jù)結(jié)構(gòu)的類型、算法及編程技巧，能用形式語言描述算法和簡單評估算法性能，并且能用自己熟悉的語言(推薦：C語言)編程實(shí)現(xiàn)算法。 操作系統(tǒng) 掌握操作系統(tǒng)的基本功能、主要組成部分，多道程序環(huán)境下出現(xiàn)的問題及解決方法，以及并行程序設(shè)計(jì)的有關(guān)概念和方法。 課堂教學(xué)、思考題、上機(jī)實(shí)踐、考試,數(shù)據(jù)結(jié)構(gòu)C唐策善等 高等教育出版社 數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏 清華大學(xué)出版社 操作系統(tǒng)精髓與設(shè)計(jì)原理William Stallings 著，清華大學(xué)出版社 操作系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)(第二版) Andrew S.Tanenbarm 清華大學(xué)出版社,參考書,是設(shè)計(jì)和

2、實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)以及其他系統(tǒng)程序和應(yīng)用程序的基礎(chǔ)。 它不僅僅是計(jì)算機(jī)專業(yè)的核心課程，也是其他非計(jì)算機(jī)專業(yè)的主要選修課程之一。 課程抽象，內(nèi)容豐富，學(xué)習(xí)難度較大。,數(shù)據(jù)結(jié)構(gòu)課程的地位和特點(diǎn),CHAP. 2 數(shù)據(jù)結(jié)構(gòu),(1) 把具體問題抽象成相應(yīng)模型，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)(邏輯結(jié)構(gòu))； (2) 選擇合適的存儲結(jié)構(gòu)，即如何將問題中所用到的數(shù)據(jù)存儲到計(jì)算機(jī)中去； (3) 根據(jù)具體的問題在相應(yīng)的存儲結(jié)構(gòu)上進(jìn)行操作或運(yùn)算，并得出結(jié)果； (4) 檢查算法的正確性，進(jìn)行效率分析。,解決具體問題的基本步驟：,CHAP. 2 數(shù)據(jù)結(jié)構(gòu),2.1.2 概念、術(shù)語,數(shù)據(jù)(Data)：是信息的載體，是描述

3、客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號的集合。 數(shù)值性數(shù)據(jù)(整數(shù)、定點(diǎn)數(shù)、浮點(diǎn)數(shù)) 非數(shù)值性數(shù)據(jù)(圖像、聲音、文字?jǐn)?shù)據(jù)),信息與數(shù)據(jù)的關(guān)系： 信息是具有一定含義的數(shù)據(jù) 信息是經(jīng)過加工(處理)后的數(shù)據(jù) 信息是對決策有價(jià)值的數(shù)據(jù),2.1.2 概念、術(shù)語,數(shù)據(jù)元素(Data Element)：數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的一個(gè)個(gè)體，又稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。 數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)(Data Item)組成：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。,關(guān)鍵字(key)：唯一能識別一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。,數(shù)據(jù)項(xiàng)(Data Item),數(shù)據(jù)元素 Data Element,數(shù)據(jù)項(xiàng) D

4、ata Item,數(shù)據(jù)字段 Data Field,2.1.2 概念、術(shù)語,數(shù)據(jù)對象(data object)：性質(zhì)相同的數(shù)據(jù)元素集合。 如： 整數(shù)的數(shù)據(jù)對象N=0,1,2, 字母字符的數(shù)據(jù)對象C=A,B,Z。,2.1.2 概念、術(shù)語,數(shù)據(jù)類型(data type)：是變量可能取的值和能做的運(yùn)算的集合。即： 數(shù)據(jù)對象+操作(運(yùn)算) 如：矩陣(求轉(zhuǎn)置、加、乘、求逆、求特征值) 構(gòu)成一個(gè)矩陣的數(shù)據(jù)類型,2.1.2 概念、術(shù)語,1) 基本數(shù)據(jù)類型(原子數(shù)據(jù)類型) 如：C語言中的基本數(shù)據(jù)類型 int char float double void 整型 字符型 浮點(diǎn)型 雙精度型 無值 2) 結(jié)構(gòu)數(shù)據(jù)類型

5、如：數(shù)組、結(jié)構(gòu)、聯(lián)合、枚舉 struct student char name; int sex; float achievement; ,數(shù)據(jù)結(jié)構(gòu)(Data Structure) ： 是指同一數(shù)據(jù)對象的所有數(shù)據(jù)成員之間的關(guān)系。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。 如：n維向量 x=(x1,x2,xn) D=x1,x2,xn R=,2.1.2 概念、術(shù)語,1) 邏輯結(jié)構(gòu) 描述數(shù)據(jù)元素間的邏輯關(guān)系，與存儲無關(guān)，獨(dú)立于計(jì)算機(jī)，為具體問題抽象出來的數(shù)學(xué)模型。 數(shù)據(jù)的邏輯結(jié)構(gòu)有： 線性結(jié)構(gòu)：有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)

6、終端結(jié)點(diǎn)，所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和一個(gè)直接后繼(線性表)。 非線性結(jié)構(gòu)：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼(樹、圖(網(wǎng)絡(luò))。,2.1.2 概念、術(shù)語,user,線性結(jié)構(gòu),樹形結(jié)構(gòu) 樹 二叉樹 二叉排序樹,堆結(jié)構(gòu),12,3,5,4,8,7,11,10,2,9,1,6,圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu),2) 物理結(jié)構(gòu)(存儲結(jié)構(gòu)) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲實(shí)現(xiàn)，其依賴于具體的計(jì)算機(jī)語言。 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示(映象)。 數(shù)據(jù)元素表示：位串,2.1.2 概念、術(shù)語,數(shù)據(jù)的存儲結(jié)構(gòu)可采用四種基本存儲方法： 順序存儲表示：把邏輯相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元。(數(shù)組) 鏈接存儲表示

7、：不要求邏輯相鄰的結(jié)點(diǎn)在物理位置上相鄰。(指針) 索引存儲表示：存儲結(jié)點(diǎn)同時(shí)，建立附加的索引表。索引項(xiàng)(關(guān)鍵字、地址) 散列存儲表示：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址，以實(shí)現(xiàn)對結(jié)點(diǎn)的存儲和訪問。,2.1.2 概念、術(shù)語,3) 運(yùn)算對數(shù)據(jù)施加的操作。,2.1.2 概念、術(shù)語,每種邏輯結(jié)構(gòu)都涉及到一些基本運(yùn)算，這些基本運(yùn)算實(shí)際上是定義在抽象的數(shù)據(jù)上的一系列操作。 最常用的運(yùn)算有： 檢索、插入、刪除、更新、排序等。,數(shù)據(jù)結(jié)構(gòu)概念說明：,2.1.2 概念、術(shù)語,同一批數(shù)據(jù)可以抽象出不同的邏輯結(jié)構(gòu) 同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)，并冠以不同的名稱； 給定數(shù)據(jù)的邏輯結(jié)構(gòu)和

8、存儲結(jié)構(gòu)，運(yùn)算不同，導(dǎo)致不同數(shù)據(jù)結(jié)構(gòu)。 存儲方法可以單獨(dú)使用，也可以結(jié)合起來使用； 數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算三個(gè)方面是一個(gè)整體； 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的重要方面,如：順序表、鏈表、散列表,如：順序棧、順序隊(duì)列、鏈棧、鏈隊(duì)列,數(shù)值的計(jì)算 數(shù)據(jù)的處理,數(shù)據(jù)結(jié)構(gòu)的發(fā)展,數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的地位,算法數(shù)據(jù)結(jié)構(gòu)程序,程序設(shè)計(jì)的實(shí)質(zhì)是對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。,2.1.1 概 述,例一：電話號碼查詢問題,電話號碼查詢問題的索引存儲,2.1.1 概 述,安排競賽項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)模型,參賽選手比賽項(xiàng)目表,例二：田競賽的時(shí)間安

9、排問題,2.1.1 概 述,2.1.3 算法描述,邏輯結(jié)構(gòu)上定義的基本運(yùn)算在存儲結(jié)構(gòu)上的實(shí)現(xiàn)是通過算法來描述的。,算法定義,算法是對特定問題求解步驟的一種描述，由有限的指令序列構(gòu)成，其中每一條指令表示一個(gè)或多個(gè)操作。,算法需滿足下述準(zhǔn)則： 1) 輸入：具有0個(gè)或多個(gè)輸入的外界量，是算法開始前對算法給出的最初量。 2) 輸出：至少產(chǎn)生一個(gè)輸出，是同輸入有某種關(guān)系的量。 3) 有窮性：每一條指令的執(zhí)行次數(shù)必須是有限的。 4) 確定性：每條指令的含義明確，無二義性。 5) 可行性：每條指令的執(zhí)行時(shí)間是有限的。,2.1.3 算法描述,算法概念說明： 算法對任何輸入，執(zhí)行有限條指令一定終止，在有限時(shí)間內(nèi)

10、必須完成，即不會(huì)陷入無限循環(huán)。 程序不一定滿足有窮性，如：OS 程序指令是機(jī)器可執(zhí)行的，算法指令無此限制。,2.1.3 算法描述,聯(lián)系：算法用機(jī)器可執(zhí)行的語言來書寫，就變成一個(gè)程序。,算法語言：自然語言、數(shù)學(xué)語言、符號語言等。 本書采用：高級語言+自然語言,評價(jià)算法優(yōu)劣標(biāo)準(zhǔn)： 正確性： 不含語法錯(cuò)誤 對幾組數(shù)據(jù)運(yùn)行正確 對典型、苛刻的數(shù)據(jù)運(yùn)行正確； 對所有數(shù)據(jù)運(yùn)行正確 效率： 高效、低存儲需要。 健壯性： 當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能作出適當(dāng)反應(yīng)，而不會(huì)出現(xiàn)莫名其妙的輸出結(jié)果。 可讀性,2.1.4 算法分析,算法運(yùn)行時(shí)間要素,（1）對源程序進(jìn)行編譯所需的時(shí)間 （2）程序運(yùn)行時(shí)所需數(shù)據(jù)輸入的時(shí)間

11、（3）機(jī)器執(zhí)行每條指令所需時(shí)間 （4）程序中的每條指令重復(fù)執(zhí)行的次數(shù),說明： 1、前三條取決運(yùn)行程序的機(jī)器的軟、硬件系統(tǒng)，不能作為評價(jià)算法時(shí)間性能的標(biāo)準(zhǔn)，僅第四條反映了算法的計(jì)算量。 2、假設(shè)每條指令執(zhí)行所需時(shí)間為單位時(shí)間。因此算法的時(shí)間耗費(fèi)可以用指令重復(fù)執(zhí)行的次數(shù)(也稱頻度T(n)進(jìn)行度量。,2.1.4 算法分析,時(shí)間復(fù)雜度： 算法時(shí)間=每條語句執(zhí)行時(shí)間之和 (該語句執(zhí)行次數(shù)(頻度)* 該語句執(zhí)行一次所需時(shí)間) =所有語句的頻度之和,2.1.4 算法分析,語句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語句執(zhí)行一次所需時(shí)間為單位時(shí)間, int i,j,k

12、; (1) for (i=0;in;i+) n+1 (2) for (j=0;jn;j+) n(n+1) (3) cij=0; n2 (4) for(k=0;kn;k+) n2(n+1) (5) cij=cij+aik*bkj; n3 ,T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1為方陣的階n的函數(shù)。 當(dāng)n趨于無窮大時(shí)，T(n)/n 32 即T(n)與n3是同階的，可記為T(n)=O(n3)，稱為該算法的(漸進(jìn))時(shí)間復(fù)雜度(time complexity) 。,# define n 自然數(shù) float ann, bnn, cnn;,例1.4 求兩個(gè)n

13、階方陣的乘積 C=AB,其算法描述如下：,2.1.4 算法分析,表示方法： T(n)=O(F(n) F(n) 表示基本操作重復(fù)執(zhí)行的次數(shù)，是n的某個(gè)函數(shù)，隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和F(n)的增長率屬于同一數(shù)量級； O 表示F(n)和T(n)只相差一個(gè)常數(shù)倍。 T(n) 稱做漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。,2.1.4 算法分析,時(shí)間復(fù)雜度分析技巧： 時(shí)間復(fù)雜度以算法中頻度最大的語句度量。 由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度F(n)決定 時(shí)間復(fù)雜度是n的函數(shù) 問題規(guī)模n：求解問題的輸入量(如：數(shù)據(jù)元素個(gè)數(shù))。 時(shí)間增長趨勢：問題規(guī)模n趨向無窮大。,2.1.4 算法分析,例

14、一：交換a和b的內(nèi)容 temp=a; a=b; b=temp; T(n)=O(1),例二：變量記數(shù)之一 (1) x=0;y=0; (2) for(k=1;k=n;k+) (3) x+; (4) for(i=1;i=n;i+) (5) for(j=1;j=n;j+) (6) y+;,頻度最大的語句是(6)，且f(n)=n2，所以該程序段的時(shí)間復(fù)雜度為T(n)=O(n2),2.1.4 算法分析,常見時(shí)間復(fù)雜度： 常數(shù)階 O(1) 對數(shù)階 O(log2n) 線性階 O(n) 線性對數(shù)階 O(nlog2n) 平方階 O(n2) 立方階 O(n3) k次方階 O(nk) 指數(shù)階 O(2n),時(shí)間復(fù)雜度遞增,2.1.4 算法分析,遞增,最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度,很多算法的時(shí)間復(fù)雜度不僅僅是問題規(guī)模的函數(shù)，還與它所處理的數(shù)據(jù)集的狀態(tài)有關(guān)，在這種情況下，通常是根據(jù)數(shù)據(jù)集中可能出現(xiàn)的最壞情況，估計(jì)出算法的最壞時(shí)間復(fù)雜度。 有時(shí)對數(shù)據(jù)集的分布作出某種假設(shè)(如等概率)，討論算法的平均時(shí)間復(fù)雜度。,2.1.4 算法分析,在數(shù)組An中查找值為K的元素，若找到，則返回位置I(0=I=n-1)；否則返回-1，算法如下：,(1)i=n-1 (2)while(I=0),最壞事件時(shí)間復(fù)雜度T(n)=n,例：,2.1.4 算法分析,空間