第01章：緒論(第1講)

1、嚴(yán)蔚敏 吳偉民清華大學(xué)出版社（C語言版）語言版）數(shù)據(jù)結(jié)構(gòu)課程地位 數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫數(shù)據(jù)庫人工智能人工智能專業(yè)基礎(chǔ)課專業(yè)基礎(chǔ)課操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理非線性程序設(shè)計(jì)非線性程序設(shè)計(jì)離散數(shù)學(xué)離散數(shù)學(xué)語言程序設(shè)計(jì)語言程序設(shè)計(jì)計(jì)算機(jī)原理設(shè)計(jì)計(jì)算機(jī)原理設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的基本概念基本概念（第（第1 1章）章）基本的數(shù)據(jù)結(jié)構(gòu)基本的數(shù)據(jù)結(jié)構(gòu) 線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)基本的基本的數(shù)據(jù)處理技術(shù)數(shù)據(jù)處理技術(shù) 查找技術(shù)查找技術(shù)（第（第9 9章）章）關(guān)于本書內(nèi)容編寫說明關(guān)于本書內(nèi)容編寫說明基基本本結(jié)結(jié)構(gòu)構(gòu)（三部分）（三部分）排

2、序技術(shù)排序技術(shù)（第（第1010章）章）線性表（第線性表（第2 2章）章）棧和隊(duì)列（第棧和隊(duì)列（第3 3章）章）串（第串（第4 4章）章）數(shù)組和廣義表（第數(shù)組和廣義表（第5 5章）章）樹樹 （第（第6 6章）章）圖圖 （第（第7 7章）章）第1章 緒 論登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L(zhǎng)01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號(hào)高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表成績(jī)表

3、.CEDABABACADBABCBDDADBDCEAEBECED數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算就是要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算根據(jù)數(shù)據(jù)元素間關(guān)系根據(jù)數(shù)據(jù)元素間關(guān)系(結(jié)構(gòu)結(jié)構(gòu))的基本特性劃分，有四種基本數(shù)據(jù)結(jié)構(gòu)的基本特性劃分，有四種基本數(shù)據(jù)結(jié)構(gòu): 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)算法設(shè)計(jì) 邏輯結(jié)構(gòu)算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)分為：線性結(jié)構(gòu) 線性表、棧、隊(duì)列、字符串、數(shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)樹、圖元素元素n n.元素元素i i

4、.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存儲(chǔ)順序存儲(chǔ)1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存儲(chǔ)地址存儲(chǔ)地址 存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容 指針指針 13451345 元素元素1 1 14001400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 15361536 . . . . . 15361536 元素元素3 3 13461346 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) h 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存

5、儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲(chǔ)順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表?xiàng)ｊ?duì)隊(duì)樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 數(shù)據(jù)類型高級(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 struct int num; char n

6、ame20; float score;STUDENT;STUDENT stu1,stu2, *p;類描述算法的語言選擇 類語言：類語言是接近于高級(jí)語言而又不是嚴(yán)格的高級(jí)語言，類語言是接近于高級(jí)語言而又不是嚴(yán)格的高級(jí)語言，具有高級(jí)語言的一般語句設(shè)施，撇掉語言中的細(xì)節(jié)，具有高級(jí)語言的一般語句設(shè)施，撇掉語言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述以便把注意力主要集中在算法處理步驟本身的描述上。上。對(duì)C語言作以下描述：1.預(yù)定義常量和類型 # define TRUE 1 # define FALSE 0 # define MAXSIZE 100 # define OK 1 # defin

7、e ERROR 0對(duì)C語言作以下描述： 數(shù)據(jù)類型 函數(shù)名（形式參數(shù)及說明） 內(nèi)部數(shù)據(jù)說明； int max(a,b) 執(zhí)行語句組； if (a=b) return a; /*函數(shù)名*/ else return b; 2.函數(shù)的表示形式：3.賦值語句賦值語句對(duì)C語言作以下描述：（1）簡(jiǎn)單賦值簡(jiǎn)單賦值 1）變量名）變量名=表達(dá)式表達(dá)式 eg: a=b+1; 2） 變量變量+， eg: i+; 3） 變量變量- -， eg: i-;（2）串聯(lián)賦值串聯(lián)賦值變量變量1=變量變量2=變量變量3=變量變量k=表達(dá)式表達(dá)式 eg: a=b=c=d=eg: a=b=c=d= =k+1;對(duì)C語言作以下描述：（4）

8、條件賦值條件賦值變量名變量名=條件表達(dá)式？表達(dá)式條件表達(dá)式？表達(dá)式1:表達(dá)式表達(dá)式2 eg: a=1 b=2 ? 0:1eg: a=1 b=2 ? 0:1 （3）成組賦值成組賦值(, 變量變量k=(, , , )數(shù)組名數(shù)組名1 1 下標(biāo)下標(biāo)11下標(biāo)下標(biāo)2=2=數(shù)組名數(shù)組名2 2 下標(biāo)下標(biāo)11下標(biāo)下標(biāo)22 eg: a12=b124.條件選擇語句對(duì)C語言作以下描述：if () 語句; if (ab) k+;if () 語句1; if(ab) k+; else 語句2; else k-;情況語句switch (） case 判斷值1: 語句組 1； break; case 判斷值2: 語句組 2；

9、break; case 判斷值n: 語句組n; break; default: 語句組； break; 對(duì)C語言作以下描述：eg：switch (B) case 0: printf(“請(qǐng)輸入0”）； break; case 1: printf(“請(qǐng)輸入1”）； break; default printf(“錯(cuò)誤”）； break; 對(duì)C語言作以下描述：對(duì)C語言作以下描述：5.循環(huán)語句循環(huán)語句for 語句語句for (；）循環(huán)體語句；循環(huán)體語句；for（i=2；i=20;i+) k=i+1;while 語句語句while (） 循環(huán)體語句；循環(huán)體語句； while(i=10) i-;對(duì)C語言作以

10、下描述：do while 語句語句do 循環(huán)體語句循環(huán)體語句 while (）dodoi-; while(i=10)while(i=10) 對(duì)C語言作以下描述：6.輸入、輸出函數(shù)輸入、輸出函數(shù)scanf getchar、printf putchar7.其它一些語句其它一些語句 return、break、continue8.注釋語句注釋語句 /*字符串字符串*/9.一些基本的函數(shù)一些基本的函數(shù) max，min，abs，eof1.4 算法的描述和算法分析n算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列算法特性1. 有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)2. 確

11、定性：算法中的每一個(gè)步驟必須有確定含義，無二 義性得以實(shí)現(xiàn)。 3. 輸 入： 有多個(gè)或0個(gè)輸入 4. 輸 出： 至少有一個(gè)或多個(gè)輸出。5. 可行性：原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)基本 運(yùn)算執(zhí)行有限次而完成。 算法設(shè)計(jì)的要求 l 正確性正確性 l 易讀性易讀性 l 健壯性健壯性 l 高效率和低存儲(chǔ)量高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問題給出算法如下： max:=0; for（i=1 ；imax) max=x; 算法、語言、程序的關(guān)系1. 算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存儲(chǔ)關(guān)系描述）。2. 描述算法的工具：算法可用自然語言、框圖或高級(jí)程序設(shè)計(jì)語言進(jìn)行描述。3.程序

12、是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。設(shè)計(jì)實(shí)現(xiàn)算法過程步驟1. 找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系2. 確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算3. 考慮數(shù)據(jù)元素的存儲(chǔ)表示4. 選擇描述算法的語言5.設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語言加以描述。評(píng)價(jià)算法的標(biāo)準(zhǔn) 評(píng)價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。算法效率用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來度量。（1）事后統(tǒng)計(jì)利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分。 缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序。 所得時(shí)間統(tǒng)

13、計(jì)量依賴于硬件、軟件等環(huán)境 因素，掩蓋算法本身的優(yōu)劣。（2）事前分析估計(jì)一個(gè)高級(jí)語言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于： 依據(jù)的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產(chǎn)生機(jī)器代碼質(zhì)量 機(jī)器執(zhí)行指令速度 同一個(gè)算法用不同的語言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，所以使用絕對(duì)時(shí)間單位衡量算法效率不合適。性能評(píng)價(jià)性能評(píng)價(jià)定義：定義： 對(duì)問題規(guī)模與該算法在運(yùn)行時(shí)所占的空間對(duì)問題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所與所耗費(fèi)的時(shí)間耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。 問題規(guī)模問題規(guī)模N對(duì)不同的問題其含義不同：對(duì)不同的問題其含義不同： 對(duì)矩陣是階數(shù)；對(duì)矩陣是

14、階數(shù)； 對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)； 對(duì)圖是頂點(diǎn)個(gè)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)； 對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。語句頻度 定義：定義：語句頻度是指該語句在一個(gè)算法中重復(fù)執(zhí)行的次語句頻度是指該語句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。數(shù)。例如：例如：兩個(gè)兩個(gè)矩陣矩陣相乘相乘算法語句算法語句 對(duì)應(yīng)的對(duì)應(yīng)的語句頻度語句頻度 1 1forfor（i=0i=0；i n;i+i n;i+） n n 2 2for for （j=0j=0；jn;j+jn;j+） n n2 2 3 cij=0; n 3 cij=0; n2 2 4 for (k=0;k n; k+) n 4 for

15、 (k=0;k n; k+) n3 3 cij=cij+aik cij=cij+aik* *bkj; nbkj; n3 3 總執(zhí)行次數(shù)：總執(zhí)行次數(shù)：Tn=2n3+2n2 +n算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：做： T(n)=O(f(n)例如給出例如給出X=X+1（1）x=x+1 ；時(shí)間復(fù)雜度為；時(shí)間復(fù)雜度為O(1)，稱為常量階；，稱為常量階；（2）for (i=1; i= n; i+) x=x+1; 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)，稱為線性階；，稱為線性階；（3）for (i=1; i= n; i+)for (j=1;j= n;

16、 j+) x=x+1; 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n2), 稱為平方階。稱為平方階。 一個(gè)算法由控制結(jié)構(gòu)（順序、分支和循環(huán)）和基本操作構(gòu)成。所謂基本操作是指數(shù)據(jù)類型固有的操作，如加、減、乘、除等。通常以基本操作重復(fù)的次數(shù)來作為時(shí)間復(fù)雜度的度量。常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè):O(1) 常數(shù)型常數(shù)型 O(n)線性型線性型 O(n2)平方型平方型 O(n3)立方型立方型 O(2n)指數(shù)型指數(shù)型 O(log2n)對(duì)數(shù)型對(duì)數(shù)型O(nlog2n)二維型二維型按時(shí)間復(fù)雜度由小到大排列的頻率表：按時(shí)間復(fù)雜度由小到大排列的頻率表：常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 常用的時(shí)間復(fù)雜度

17、頻率表：常用的時(shí)間復(fù)雜度頻率表：loglog2 2n nn nnlognlog2 2n nn n2 2n n3 32 2n n一般講：前一般講：前3種可實(shí)現(xiàn)，種可實(shí)現(xiàn)，后后3種雖理種雖理論上是可實(shí)論上是可實(shí)現(xiàn)的，實(shí)際現(xiàn)的，實(shí)際上只有對(duì)上只有對(duì)N限制在很小限制在很小范圍才有意范圍才有意義，當(dāng)義，當(dāng)N較較大時(shí)，不可大時(shí)，不可能實(shí)現(xiàn)。能實(shí)現(xiàn)。 0 01 10 01 11 12 21 12 22 24 48 84 42 24 48 81616646416163 38 8242464645125122562564 4161664642562565096509665536655365 5323216016010241024327683276821474836482147483648不必追求高效算法，不必追求高效算法，低效算法可由高速低效算法可由高速計(jì)算機(jī)來彌補(bǔ)的看計(jì)算機(jī)來彌補(bǔ)的看法是錯(cuò)誤的。法是錯(cuò)誤的。最壞時(shí)間復(fù)雜度 定義：定義：討論算法在最壞情況下的時(shí)間復(fù)雜度，討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。間的上界。例如起泡排序算法例如起泡排序算法void bubble(int a, int length)將將a中整數(shù)數(shù)