網(wǎng)絡(luò)互聯(lián)技術(shù)

1、數(shù)據(jù)結(jié)構(gòu)計算機(jī)科學(xué)系 張紅軍1課時安排：數(shù)據(jù)結(jié)構(gòu)48學(xué)時上機(jī)16學(xué)時雙周，周三第3、4節(jié)網(wǎng)絡(luò)技術(shù)實驗室教材：數(shù)據(jù)結(jié)構(gòu)簡明教程 徐翠霞 北京航空航天大學(xué)出版社參考書：數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏、吳偉民 清華大學(xué)出版社第一章計算機(jī)科學(xué)系 張紅軍3案例1.1 數(shù)據(jù)模型的確定案例說明對于下面三個問題，試分別設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)圖書館的書目檢索系統(tǒng)自動化問題計算機(jī)和人對弈問題多叉路口交通燈的管理問題案例目的了解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，能夠根據(jù)需求為實際問題確定合適的數(shù)據(jù)模型了解線性表、樹和圖3種數(shù)據(jù)結(jié)構(gòu)的基本特點。1.1 基本概念和術(shù)語技術(shù)要點書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出

2、版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表人機(jī)對奕問題樹.多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖相關(guān)知識及注意事項數(shù)據(jù)（data)所有能輸入到計算機(jī)中去的描述客觀事物的符號數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱節(jié)點（node）或記錄（record）數(shù)據(jù)項（data item）有獨立含義的數(shù)據(jù)最小單位，也稱域(field)數(shù)據(jù)結(jié)構(gòu)（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu)一個對一個，如

3、線性表、棧、隊列樹形結(jié)構(gòu)一個對多個，如樹圖狀結(jié)構(gòu)多個對多個，如圖(1)數(shù)據(jù)的邏輯結(jié)構(gòu) 只抽象反映數(shù)據(jù)元素的邏輯關(guān)系(2)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)算法設(shè)計 邏輯結(jié)構(gòu)算法實現(xiàn) 存儲結(jié)構(gòu)存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)借助元素在存儲器中的相對位置來表示 數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)借助指示元素存儲地址的指針表示數(shù)據(jù) 元素間的邏輯關(guān)系元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲1536元素21400元素11346元素3 元素41345h存儲地址 存

4、儲內(nèi)容 指針 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 1346 鏈?zhǔn)酱鎯?h 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲 鏈?zhǔn)酱鎯?線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)類型高級語言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱例 C語言中，提供int, char, float, double等基本 數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉 等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類 型等。用戶也可用typedef 自己定義數(shù)據(jù)類型typedef st

5、ruct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;案例1.2 矩陣乘法算法的時間復(fù)雜度分析案例說明已知兩個n階方陣A和B，乘積為C=AB，算法代碼如下：for(i=1;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 1.2 算法和算法分析案例目的了解算法的特性和算法描述的方法。掌握計算語句頻度和估算算法時間復(fù)雜度的方法。技術(shù)要點cij+=aik*bkj 頻度最大，為f(n)=n3。該算法的時間復(fù)雜度為T(n)=O(n3)。1.2 算法

6、和算法分析相關(guān)知識及注意事項1.算法及其特性算法（algorithm） 解決某一特定問題的具體步驟的描述，是指令的有限序列算法特性輸出一個算法有零個或多個輸出輸入一個算法有零個或多個輸入算法是能行的可行性義性切定義的，不能產(chǎn)生二算法的每一步必須是確確定性限步驟之后結(jié)束一個算法必須在執(zhí)行有有窮性2.算法描述自然語言程序流程圖N-S圖程序設(shè)計語言3.算法評價 正確性(correctness)、可讀性(readability)、健壯性(robustness)、效率與低存儲量時間復(fù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)的階數(shù) T(n)=o(f(n)空間復(fù)雜度：s(n)=o(f(n)算法效率用依據(jù)該算法編制的程序

7、在計算機(jī)上執(zhí)行所消耗的時間來度量1.事后統(tǒng)計 所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣 2.事前分析估計 依據(jù)的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產(chǎn)生機(jī)器代碼質(zhì)量 機(jī)器執(zhí)行指令速度 同一個算法用不同的語言、不同的編譯程序、在不同的計算機(jī)上運行，效率均不同，所以使用絕對時間單位衡量算法效率不合適（1）時間復(fù)雜度 一般情況下，算法中頻度最大的語句的執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作 T(n)=O(f(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度簡稱時間復(fù)雜度。 語句頻度指的是該語句重復(fù)執(zhí)行的

8、次數(shù)k=0;for(i=1;i=n;i+) for(j=1;j=n;j+) k+;k=0;for(i=1;i=n;i+) for(j=i;j=n;j+) k+;k=0;for(i=1;i=n;i+) for(j=1;j=n;j+) k+;k=0;for(i=1;i=n;i+) for(j=i;j=n;j+) k+;例 求下列程序段的時間復(fù)雜度：for(i=1;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=1 & change; -i) change=0; for(j=0;jaj+1) temp=aj; aj=aj+1; aj+1=temp; change=1; 最好情況：O(n)最壞情況：O(n2)以下六種計算算法時間的多項式是最常用的。其關(guān)系為： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時間的關(guān)系為：