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

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

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

3、）具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合以及在這個(gè)數(shù)據(jù)集合上的一組操作?？煞譃楹?jiǎn)單類(lèi)型和構(gòu)造類(lèi)型。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ù)項(xiàng)、數(shù)據(jù)類(lèi)型？6數(shù)據(jù)結(jié)構(gòu)與STL數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)（data structure）是指按照某種邏輯關(guān)系組織起來(lái)的一組數(shù)據(jù)，按一定的存儲(chǔ)方式存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一組運(yùn)算的集合。通常人們認(rèn)為數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容：對(duì)數(shù)據(jù)的操作或運(yùn)算 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)

4、據(jù)的存儲(chǔ)結(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ì)特點(diǎn)常常將數(shù)據(jù)的邏輯結(jié)構(gòu)直接稱(chēng)為數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，與存儲(chǔ)方式無(wú)關(guān)，可認(rèn)為是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。數(shù)據(jù)元素之間不同的邏輯特點(diǎn)代表不同的邏輯結(jié)構(gòu)四 種 常 見(jiàn) 的 邏 輯 結(jié) 構(gòu)(a)集合 (b)線性結(jié)構(gòu) (c)樹(shù)結(jié)構(gòu) (d)圖結(jié)構(gòu)8數(shù)據(jù)結(jié)構(gòu)與STL數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 考慮如何在計(jì)算機(jī)的存儲(chǔ)器中存儲(chǔ)各個(gè)數(shù)據(jù)元素，并且同時(shí)反映數(shù)據(jù)元素間的邏輯關(guān)系。對(duì)于每種邏輯結(jié)構(gòu)，都可以設(shè)計(jì)多種存儲(chǔ)方法基本的兩種存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)9數(shù)據(jù)結(jié)構(gòu)與STL每學(xué)習(xí)一種數(shù)據(jù)

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

6、每條指令必須有確切的含義，無(wú)二義性?？尚行裕好織l指令的執(zhí)行時(shí)間都是有限的。 常見(jiàn)的算法描述方法：自然語(yǔ)言流程圖偽代碼程序設(shè)計(jì)語(yǔ)言 12數(shù)據(jù)結(jié)構(gòu)與STL歐幾里得算法描述舉例輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m和n的最大公約數(shù)，假定mn 自然語(yǔ)言描述： 流程圖描述：(1) 輸入m和n；(2) 取得m除以n的余數(shù)r；(3) 若r=0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第(4)步；(4) 將n放到m中，r放到n中；(5) 重復(fù)執(zhí)行第(2)步。13數(shù)據(jù)結(jié)構(gòu)與STL歐幾里得算法描述舉例偽代碼描述： 程序設(shè)計(jì)語(yǔ)言描述： 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; /存儲(chǔ)真正的自然數(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算法好壞的評(píng)價(jià):算法的時(shí)間復(fù)雜度算法的空間復(fù)雜度算法的可讀性.算

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

10、法的漸進(jìn)時(shí)間復(fù)雜度簡(jiǎn)稱(chēng)為T(mén)(n)與n2是同階的 T(n)與n2是同數(shù)量級(jí)的記作T(n)=O(n2) 稱(chēng)T(n)=O(n2)為算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度也可以利用算法中的基本語(yǔ)句計(jì)算 基本語(yǔ)句：執(zhí)行次數(shù)與算法的執(zhí)行次數(shù)成正比的語(yǔ)句。 18數(shù)據(jù)結(jié)構(gòu)與STL分析算法的時(shí)間復(fù)雜度 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í)間復(fù)雜度最好時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度 在數(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時(shí)間復(fù)雜度的思考？多項(xiàng)式時(shí)間問(wèn)題(polynomial time problem)存在以問(wèn)題規(guī)模n為變量的多項(xiàng)式函數(shù)p(n)，解決問(wèn)題的算法的時(shí)間復(fù)雜度為O(p(n) P問(wèn)題指數(shù)時(shí)間算法

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

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

14、板類(lèi)是C+語(yǔ)言提供的一個(gè)基礎(chǔ)模板集合，包含了各種常用的存儲(chǔ)數(shù)據(jù)的模板類(lèi)及相應(yīng)的操作函數(shù)，為開(kāi)發(fā)者提供了一種快速有效的訪問(wèn)機(jī)制L最初由惠普實(shí)驗(yàn)室（Hewett-Packard Labs）開(kāi)發(fā)，并于1998年被定為國(guó)際標(biāo)準(zhǔn)，正式成為C+語(yǔ)言的標(biāo)準(zhǔn)庫(kù)。是一些容器、算法和其他一些組件的集合，這些容器有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ā)展的過(guò)程中。使用STL進(jìn)行編程時(shí)，程序員往往不需要花太多精力考慮一般數(shù)據(jù)的存儲(chǔ)和常見(jiàn)算法的優(yōu)化有了STL，算法和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)不再重要？復(fù)雜數(shù)據(jù)的處理還需要程序員自己來(lái)設(shè)計(jì)高效的存儲(chǔ)方法和算法了解算法和數(shù)據(jù)結(jié)構(gòu)的知識(shí)才能更好的使用STLSTL自身就來(lái)源于算法和數(shù)據(jù)結(jié)構(gòu)錯(cuò)！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第一章 緒論學(xué)習(xí)內(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 實(shí)例分析30數(shù)據(jù)結(jié)構(gòu)與STL電話(huà)號(hào)碼查詢(xún)問(wèn)題電話(huà)號(hào)碼簿，n個(gè)人名和對(duì)應(yīng)的電話(huà)號(hào)碼。要求：設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人名時(shí)，該算法能打印出此人的電話(huà)號(hào)碼，若沒(méi)有此人，則報(bào)告標(biāo)志。數(shù)據(jù)：人名和電話(huà)號(hào)碼。數(shù)據(jù)表示：（1）無(wú)規(guī)則的任意排列。 （2）將人名按拼音的字母順序排列，或按姓氏筆劃排列。操作：查找。算法設(shè)計(jì)：與結(jié)構(gòu)有關(guān)，如何設(shè)計(jì)。31數(shù)據(jù)結(jié)構(gòu)與STL電話(huà)號(hào)碼查詢(xún)問(wèn)題如果要求按電話(huà)號(hào)碼查詢(xún)?nèi)嗣兀咳绾卧O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)。順序查找索引查找 32數(shù)據(jù)結(jié)構(gòu)與STL田徑運(yùn)動(dòng)會(huì)的時(shí)間安排問(wèn)題 七個(gè)項(xiàng)目：分別為10