數據結構與STL-第1章-緒論

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

2、紀80年代至今：面向對象(OO)技術出現 數據結構與面向對象具有天然的對應 4數據結構與STL第一章 緒論學習內容：1.1 數據結構的起源 1.2 數據結構的基本概念 1.3 算法和算法分析 1.4 STL與數據結構1.5 實例分析5數據結構與STL1.2 數據結構的基本概念數據（data）信息的載體分為兩類：數值型數據、非數值型數據數據元素（data element）也稱為元素、結點、頂點或記錄是數據的基本單位，在計算機程序中通常作為一個整體進行處理。數據項（data item）也稱為字段或域構成數據元素的不可分割的最小單位。每個數據元素可以包含多個不同的數據項。數據類型（data type

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

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

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

6、每條指令必須有確切的含義，無二義性?？尚行裕好織l指令的執(zhí)行時間都是有限的。 常見的算法描述方法：自然語言流程圖偽代碼程序設計語言 12數據結構與STL歐幾里得算法描述舉例輾轉相除法求兩個自然數m和n的最大公約數，假定mn 自然語言描述： 流程圖描述：(1) 輸入m和n；(2) 取得m除以n的余數r；(3) 若r=0，則n為最大公約數，算法結束；否則執(zhí)行第(4)步；(4) 將n放到m中，r放到n中；(5) 重復執(zhí)行第(2)步。13數據結構與STL歐幾里得算法描述舉例偽代碼描述： 程序設計語言描述： 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數據結構與STL歐幾里得算法描述舉例采用面向對象的方法描述： class NaturalNumberpublic: unsigned long int EUCLID(NaturalNumber & n); /歐幾里德算法求解最大公約數 /其它外部接口private: unsigned long int num; /存儲真正的自然數;/返回歐幾里德算法求解最大公約數un

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

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

10、法的漸進時間復雜度簡稱為T(n)與n2是同階的 T(n)與n2是同數量級的記作T(n)=O(n2) 稱T(n)=O(n2)為算法的時間復雜度時間復雜度也可以利用算法中的基本語句計算 基本語句：執(zhí)行次數與算法的執(zhí)行次數成正比的語句。 18數據結構與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數據結構與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數據結構與STL特殊情況下的算法時間復雜度最好時間復雜度最壞時間復雜度平均時間復雜度 在數組an中查找值為k的元素，若找到返回其位置i（0in），否則返回-1。int i=n-1;while(i=0 & ai!=k) i-;return i;O(1) O(n) O(n) 21數據結構與STL時間復雜度的思考？多項式時間問題(polynomial time problem)存在以問題規(guī)模n為變量的多項式函數p(n)，解決問題的算法的時間復雜度為O(p(n) P問題指數時間算法

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

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

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

15、空間管理器迭代器泛函適配器容器算法27數據結構與STLSTL與數據結構的關系 STL與數據結構的關系密不可分STL的基礎就是算法和數據結構的基本理論和研究成果目前兩者仍然處于不斷發(fā)展的過程中。使用STL進行編程時，程序員往往不需要花太多精力考慮一般數據的存儲和常見算法的優(yōu)化有了STL，算法和數據結構的基礎知識不再重要？復雜數據的處理還需要程序員自己來設計高效的存儲方法和算法了解算法和數據結構的知識才能更好的使用STLSTL自身就來源于算法和數據結構錯！28數據結構與STLSTL應用舉例 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數據結構與STL第一章 緒論學習內容：1.1 數據結構的起源 1.2 數據結構的基本概念 1.3 算法和算法分析 1.4 STL與數據結構1.5 實例分析30數據結構與STL電話號碼查詢問題電話號碼簿，n個人名和對應的電話號碼。要求：設計一個算法，當給定任何一個人名時，該算法能打印出此人的電話號碼，若沒有此人，則報告標志。數據：人名和電話號碼。數據表示：（1）無規(guī)則的任意排列。 （2）將人名按拼音的字母順序排列，或按姓氏筆劃排列。操作：查找。算法設計：與結構有關，如何設計。31數據結構與STL電話號碼查詢問題如果要求按電話號碼查詢人名呢？如何設計數據結構。順序查找索引查找 32數據結構與STL田徑運動會的時間安排問題 七個項目：分別為10