第01章：緒論(第1講)

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

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

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

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

5、儲結構數(shù)據(jù)的存儲結構 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結構線性結構 非線性結構非線性結構 順序存儲順序存儲 鏈式存儲鏈式存儲 線性表線性表棧棧隊隊樹形結構樹形結構圖形結構圖形結構數(shù)據(jù)結構的三個方面：數(shù)據(jù)結構的三個方面： 數(shù)據(jù)類型高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱例 C語言中，提供int, char, float, double等基本 數(shù)據(jù)類型，數(shù)組、結構體、共用體、枚舉 等構造數(shù)據(jù)類型，還有指針、空(void)類 型等。用戶也可用typedef 自己定義數(shù)據(jù)類型typedef struct int num; char n

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

7、e ERROR 0對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.賦值語句賦值語句對C語言作以下描述：（1）簡單賦值簡單賦值 1）變量名）變量名=表達式表達式 eg: a=b+1; 2） 變量變量+， eg: i+; 3） 變量變量- -， eg: i-;（2）串聯(lián)賦值串聯(lián)賦值變量變量1=變量變量2=變量變量3=變量變量k=表達式表達式 eg: a=b=c=d=eg: a=b=c=d= =k+1;對C語言作以下描述：（4）

8、條件賦值條件賦值變量名變量名=條件表達式？表達式條件表達式？表達式1:表達式表達式2 eg: a=1 b=2 ? 0:1eg: a=1 b=2 ? 0:1 （3）成組賦值成組賦值(, 變量變量k=(, , , )數(shù)組名數(shù)組名1 1 下標下標11下標下標2=2=數(shù)組名數(shù)組名2 2 下標下標11下標下標22 eg: a12=b124.條件選擇語句對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; 對C語言作以下描述：eg：switch (B) case 0: printf(“請輸入0”）； break; case 1: printf(“請輸入1”）； break; default printf(“錯誤”）； break; 對C語言作以下描述：對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-;對C語言作以

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

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

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

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

14、階數(shù)； 對多項式運算是多項式項數(shù)；對多項式運算是多項式項數(shù)； 對圖是頂點個數(shù)；對圖是頂點個數(shù)； 對集合運算是集合中元素個數(shù)。對集合運算是集合中元素個數(shù)。語句頻度 定義：定義：語句頻度是指該語句在一個算法中重復執(zhí)行的次語句頻度是指該語句在一個算法中重復執(zhí)行的次數(shù)。數(shù)。例如：例如：兩個兩個矩陣矩陣相乘相乘算法語句算法語句 對應的對應的語句頻度語句頻度 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算法的時間復雜度 算法的時間復雜度，即是算法的時間量度記算法的時間復雜度，即是算法的時間量度記做：做： T(n)=O(f(n)例如給出例如給出X=X+1（1）x=x+1 ；時間復雜度為；時間復雜度為O(1)，稱為常量階；，稱為常量階；（2）for (i=1; i= n; i+) x=x+1; 時間復雜度為時間復雜度為O(n)，稱為線性階；，稱為線性階；（3）for (i=1; i= n; i+)for (j=1;j= n;

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

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