數(shù)據(jù)結(jié)構(gòu)與STL-第1章-緒論

1、第一章 緒論北京郵電大學信息與通信工程學院數(shù)據(jù)結(jié)構(gòu)與STL1數(shù)據(jù)結(jié)構(gòu)與STL第一章 緒論學習內(nèi)容：1.1 數(shù)據(jù)結(jié)構(gòu)的起源 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3 算法和算法分析 1.4 STL與數(shù)據(jù)結(jié)構(gòu)1.5 實例分析2數(shù)據(jù)結(jié)構(gòu)與STL1.1 數(shù)據(jù)結(jié)構(gòu)的起源程序設(shè)計的兩個重要問題： 待處理的數(shù)據(jù)存儲到計算機內(nèi)存設(shè)計相應(yīng)的算法操作這些數(shù)據(jù)數(shù)據(jù)表示數(shù)據(jù)處理 對數(shù)據(jù)的處理 數(shù)據(jù)的邏輯表示數(shù)據(jù)的存儲方法數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容3數(shù)據(jù)結(jié)構(gòu)與STL起源數(shù)據(jù)結(jié)構(gòu)是計算機及其相關(guān)專業(yè)的重要課程計算機發(fā)展初期：處理數(shù)值計算問題 不重視數(shù)據(jù)結(jié)構(gòu) 20世紀6080年代：非數(shù)值處理問題 沃思：算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序 20世

2、紀80年代至今：面向?qū)ο?OO)技術(shù)出現(xiàn) 數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο缶哂刑烊坏膶?yīng) 4數(shù)據(jù)結(jié)構(gòu)與STL第一章 緒論學習內(nèi)容：1.1 數(shù)據(jù)結(jié)構(gòu)的起源 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3 算法和算法分析 1.4 STL與數(shù)據(jù)結(jié)構(gòu)1.5 實例分析5數(shù)據(jù)結(jié)構(gòu)與STL1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)（data）信息的載體分為兩類：數(shù)值型數(shù)據(jù)、非數(shù)值型數(shù)據(jù)數(shù)據(jù)元素（data element）也稱為元素、結(jié)點、頂點或記錄是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行處理。數(shù)據(jù)項（data item）也稱為字段或域構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。每個數(shù)據(jù)元素可以包含多個不同的數(shù)據(jù)項。數(shù)據(jù)類型（data type

3、）具有相同性質(zhì)的計算機數(shù)據(jù)的集合以及在這個數(shù)據(jù)集合上的一組操作?？煞譃楹唵晤愋秃蜆?gòu)造類型。struct Studentint No;char name10;float score;int age;char sex;stu10=1,張三,90,19,M,2,張莉,95,18,F;分析上述代碼，哪些是：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)類型？6數(shù)據(jù)結(jié)構(gòu)與STL數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)（data structure）是指按照某種邏輯關(guān)系組織起來的一組數(shù)據(jù)，按一定的存儲方式存儲在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一組運算的集合。通常人們認為數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容：對數(shù)據(jù)的操作或運算 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)

4、據(jù)的存儲結(jié)構(gòu) 7數(shù)據(jù)結(jié)構(gòu)與STL數(shù)據(jù)的邏輯結(jié)構(gòu)描述數(shù)據(jù)相互間的關(guān)聯(lián)形式或鄰接形式反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式定義了數(shù)據(jù)的本質(zhì)特點常常將數(shù)據(jù)的邏輯結(jié)構(gòu)直接稱為數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于計算機，與存儲方式無關(guān)，可認為是從具體問題抽象出來的數(shù)學模型。數(shù)據(jù)元素之間不同的邏輯特點代表不同的邏輯結(jié)構(gòu)四 種 常 見 的 邏 輯 結(jié) 構(gòu)(a)集合 (b)線性結(jié)構(gòu) (c)樹結(jié)構(gòu) (d)圖結(jié)構(gòu)8數(shù)據(jù)結(jié)構(gòu)與STL數(shù)據(jù)的存儲結(jié)構(gòu) 考慮如何在計算機的存儲器中存儲各個數(shù)據(jù)元素，并且同時反映數(shù)據(jù)元素間的邏輯關(guān)系。對于每種邏輯結(jié)構(gòu)，都可以設(shè)計多種存儲方法基本的兩種存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)9數(shù)據(jù)結(jié)構(gòu)與STL每學習一種數(shù)據(jù)

5、結(jié)構(gòu)各種數(shù)據(jù)結(jié)構(gòu)的學習主線其邏輯結(jié)構(gòu)是什么？可有哪些運算？有哪些存儲結(jié)構(gòu)？C+如何描述各種存儲結(jié)構(gòu)基于每種存儲結(jié)構(gòu)，各種運算如何實現(xiàn)？各種存儲結(jié)構(gòu)的優(yōu)缺點對比10數(shù)據(jù)結(jié)構(gòu)與STL第一章 緒論學習內(nèi)容：1.1 數(shù)據(jù)結(jié)構(gòu)的起源 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3 算法和算法分析 1.4 STL與數(shù)據(jù)結(jié)構(gòu)1.5 實例分析11數(shù)據(jù)結(jié)構(gòu)與STL1.3 算法和算法分析算法解題的方法數(shù)據(jù)的運算是通過算法（algorithm）描述的討論算法的效率和性能是數(shù)據(jù)結(jié)構(gòu)課程的重要內(nèi)容算法通常滿足5個準則：輸入：具有0個或多個輸入的參數(shù)。輸出：算法執(zhí)行要有輸出結(jié)果。有窮性：算法中每條指令的執(zhí)行次數(shù)必須是有限的。確定性：

6、每條指令必須有確切的含義，無二義性?？尚行裕好織l指令的執(zhí)行時間都是有限的。 常見的算法描述方法：自然語言流程圖偽代碼程序設(shè)計語言 12數(shù)據(jù)結(jié)構(gòu)與STL歐幾里得算法描述舉例輾轉(zhuǎn)相除法求兩個自然數(shù)m和n的最大公約數(shù)，假定mn 自然語言描述： 流程圖描述：(1) 輸入m和n；(2) 取得m除以n的余數(shù)r；(3) 若r=0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第(4)步；(4) 將n放到m中，r放到n中；(5) 重復執(zhí)行第(2)步。13數(shù)據(jù)結(jié)構(gòu)與STL歐幾里得算法描述舉例偽代碼描述： 程序設(shè)計語言描述： 1. input m,n2. r=m%n;3. while (r!=0) 3.1 m=n; 3.2

7、 n=r; 3.3 r=m%n;4. output n;int EUCLID (int m, int n)int r = m % n;while (r != 0)m = n; n = r;r = m % n;return n;14數(shù)據(jù)結(jié)構(gòu)與STL歐幾里得算法描述舉例采用面向?qū)ο蟮姆椒枋觯?class NaturalNumberpublic: unsigned long int EUCLID(NaturalNumber & n); /歐幾里德算法求解最大公約數(shù) /其它外部接口private: unsigned long int num; /存儲真正的自然數(shù);/返回歐幾里德算法求解最大公約數(shù)un

8、signed long int NaturalNumber : EUCLID(NaturalNumber & n) unsigned long int m = (num n.num) ? num : n.num; /較大的自然數(shù)賦值給m unsigned long int n = (num n.num) ? num : n.num; /較小的自然數(shù)賦值給n unsigned long int r = m % n; while (r != 0) m = n; n = r; r = m % n; return n;15數(shù)據(jù)結(jié)構(gòu)與STL算法好壞的評價:算法的時間復雜度算法的空間復雜度算法的可讀性.算

9、法的執(zhí)行時間:與哪些因素相關(guān)？問題規(guī)模通常是指算法處理的數(shù)據(jù)量的大小，記作 n。運行算法所需要的時間T可看作問題規(guī)模n的函數(shù)，記作T(n)。 算法分析 計算工具 對算法執(zhí)行時間的度量算法本身 以及？問題的規(guī)模16數(shù)據(jù)結(jié)構(gòu)與STL語句的頻度（frequency count） 即：語句執(zhí)行的次數(shù) 假定每條語句執(zhí)行一次所需的時間是單位時間，則每條語句執(zhí)行的時間正比于該語句執(zhí)行的次數(shù) 算法運行時間算法中所有語句的頻度之和。 for (i=0; in; i+) n+1 for (j=0; jn; j+) n(n+1) k+; n2語句的頻度算法的總用時：T(n)=2n2+2n+1 17數(shù)據(jù)結(jié)構(gòu)與STL算

10、法的漸進時間復雜度簡稱為T(n)與n2是同階的 T(n)與n2是同數(shù)量級的記作T(n)=O(n2) 稱T(n)=O(n2)為算法的時間復雜度時間復雜度也可以利用算法中的基本語句計算 基本語句：執(zhí)行次數(shù)與算法的執(zhí)行次數(shù)成正比的語句。 18數(shù)據(jù)結(jié)構(gòu)與STL分析算法的時間復雜度 j += i;i = j - i;j = j - i;for (i=0;i100;i+) for (j=0;ji;j+)sum += j;for (i=0;in;i+) for (j=0;j=i;j+)sum += j;O(1)O(1)O(n2)19數(shù)據(jù)結(jié)構(gòu)與STLy=0;while (y+1)*(y+1)=n) y+; T

11、(n)+1)2 nT(n)=O(n1/2) i=0,j=0;while (i+jj) j+;else i+;O(n) 20數(shù)據(jù)結(jié)構(gòu)與STL特殊情況下的算法時間復雜度最好時間復雜度最壞時間復雜度平均時間復雜度 在數(shù)組an中查找值為k的元素，若找到返回其位置i（0in），否則返回-1。int i=n-1;while(i=0 & ai!=k) i-;return i;O(1) O(n) O(n) 21數(shù)據(jù)結(jié)構(gòu)與STL時間復雜度的思考？多項式時間問題(polynomial time problem)存在以問題規(guī)模n為變量的多項式函數(shù)p(n)，解決問題的算法的時間復雜度為O(p(n) P問題指數(shù)時間算法

12、：時間復雜度函數(shù)不能用多項式函數(shù)界定 O(？) 1, log2n, n1/2, n, nlog2n, n2 , n3, 2n, 3n, nn , n!, nlogn ?22數(shù)據(jù)結(jié)構(gòu)與STL常見的時間復雜度常數(shù)階O(1)、對數(shù)階O(logn)、線性階O(n)、線性對數(shù)階O(nlogn)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)等。當問題規(guī)模n較大時，具有指數(shù)階量級的算法是不可計算的NP問題非確定性多項式時間問題:non-deterministic polynomial time problem對于NP問題，人們可能還不清楚是否存在一個能在多項式的時間里解決它的算法

13、，但可以在多項式的時間里驗證一個解。顯然有：PNP 23數(shù)據(jù)結(jié)構(gòu)與STL算法的空間復雜度空間復雜度算法在執(zhí)行過程中所耗費的存儲空間 也是問題規(guī)模n的函數(shù) 對空間復雜度的重視情況：早期：計算機系統(tǒng)內(nèi)存較小空間復雜度非常重視現(xiàn)代：計算機內(nèi)存儲器成本降低，存儲容量的不斷增大 空間效率換時間效率問題規(guī)模n很大，算法的空間效率也非常重要！ 24數(shù)據(jù)結(jié)構(gòu)與STL第一章 緒論學習內(nèi)容：1.1 數(shù)據(jù)結(jié)構(gòu)的起源 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3 算法和算法分析 1.4 STL與數(shù)據(jù)結(jié)構(gòu)1.5 實例分析25數(shù)據(jù)結(jié)構(gòu)與STL1.4 STL與數(shù)據(jù)結(jié)構(gòu)STL:Standard Template Library，標準模

14、板類是C+語言提供的一個基礎(chǔ)模板集合，包含了各種常用的存儲數(shù)據(jù)的模板類及相應(yīng)的操作函數(shù)，為開發(fā)者提供了一種快速有效的訪問機制L最初由惠普實驗室（Hewett-Packard Labs）開發(fā)，并于1998年被定為國際標準，正式成為C+語言的標準庫。是一些容器、算法和其他一些組件的集合，這些容器有l(wèi)ist，vector，set，map等。 26數(shù)據(jù)結(jié)構(gòu)與STLSTL構(gòu)成 適配器容器適配器，如stack、queue、priority_queue迭代器適配器泛函適配器 容器順序容器：vector、list、 deque 關(guān)聯(lián)容器：set、multiset、map、multimap、hash_set等

15、空間管理器迭代器泛函適配器容器算法27數(shù)據(jù)結(jié)構(gòu)與STLSTL與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 STL與數(shù)據(jù)結(jié)構(gòu)的關(guān)系密不可分STL的基礎(chǔ)就是算法和數(shù)據(jù)結(jié)構(gòu)的基本理論和研究成果目前兩者仍然處于不斷發(fā)展的過程中。使用STL進行編程時，程序員往往不需要花太多精力考慮一般數(shù)據(jù)的存儲和常見算法的優(yōu)化有了STL，算法和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識不再重要？復雜數(shù)據(jù)的處理還需要程序員自己來設(shè)計高效的存儲方法和算法了解算法和數(shù)據(jù)結(jié)構(gòu)的知識才能更好的使用STLSTL自身就來源于算法和數(shù)據(jù)結(jié)構(gòu)錯！28數(shù)據(jù)結(jié)構(gòu)與STLSTL應(yīng)用舉例 const int n = 10;int an;int n = 10;int * p = new int n

16、;int * temp = new int m; memcpy(temp, p, sizeo(int) * n);delete p;p = temp;vector a; for (int i=0;i10;i+) a.push_back(i); a.resize(100); a90=100; a.clear();a.resize(20, -1);29數(shù)據(jù)結(jié)構(gòu)與STL第一章 緒論學習內(nèi)容：1.1 數(shù)據(jù)結(jié)構(gòu)的起源 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3 算法和算法分析 1.4 STL與數(shù)據(jù)結(jié)構(gòu)1.5 實例分析30數(shù)據(jù)結(jié)構(gòu)與STL電話號碼查詢問題電話號碼簿，n個人名和對應(yīng)的電話號碼。要求：設(shè)計一個算法，當給定任何一個人名時，該算法能打印出此人的電話號碼，若沒有此人，則報告標志。數(shù)據(jù)：人名和電話號碼。數(shù)據(jù)表示：（1）無規(guī)則的任意排列。 （2）將人名按拼音的字母順序排列，或按姓氏筆劃排列。操作：查找。算法設(shè)計：與結(jié)構(gòu)有關(guān)，如何設(shè)計。31數(shù)據(jù)結(jié)構(gòu)與STL電話號碼查詢問題如果要求按電話號碼查詢?nèi)嗣?？如何設(shè)計數(shù)據(jù)結(jié)構(gòu)。順序查找索引查找 32數(shù)據(jù)結(jié)構(gòu)與STL田徑運動會的時間安排問題 七個項目：分別為10