數(shù)據(jù)結(jié)構(gòu)與算法、模板

1、領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值數(shù)據(jù)結(jié)構(gòu)與算法Page 1第一章 概念介紹第二章 常用數(shù)據(jù)結(jié)構(gòu)第三章 常用算法第四章 模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值n 什么是數(shù)據(jù)結(jié)構(gòu)？第一章 概念介紹Page 2從計算機的角度看，數(shù)據(jù)是所有能被輸入到計算機中，且能被計算機處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)中的一個“個體”，是數(shù)據(jù)的基本單位。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及互相之間的聯(lián)系，是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第一章 概念介紹n 案例分析1學生表如下圖所示，其中數(shù)據(jù)元素是學生記錄，每個數(shù)據(jù)元素包括4個數(shù)據(jù)項（學號、姓名、性別和班級

2、）。請用計算機語言實現(xiàn)上面數(shù)據(jù)的存儲請用計算機語言實現(xiàn)上面數(shù)據(jù)的存儲?Page 3學號姓名性別班級1劉麗女1115陳華男712王琦男75王萍女2領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第一章 概念介紹 方法一：順序存儲struct int nNum;/學號 char name8;/名字 char sex3;/性別 int nCls;/班級Student4 = 1, “劉麗”, “女”, 11, 15, “陳華”, “男”, 7, 12, “王琦”, “男”, 7, 5, “王萍”, “女”, 2 ;Page 41劉麗女1115陳華 男712王琦 男75王萍女2領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè)

3、 知識提升價值知識提升價值第一章 概念介紹 方法二：鏈表存儲struct StudentNode int nNum;/學號 char name8;/名字 char sex3;/性別 int nCls;/班級 struct StudentNode *pNext;Page 51劉麗女115王萍女2NULL15陳華男712王琦男7Head領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值n 案例分析2有一種數(shù)據(jù)結(jié)構(gòu)如右圖所示：第一章 概念介紹Page 6這是什么數(shù)據(jù)這是什么數(shù)據(jù)結(jié)構(gòu)呢結(jié)構(gòu)呢?領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第一章 概念介紹n 數(shù)據(jù)類型正式開始學習之前，我們先來回顧一

4、下C/C+常用數(shù)據(jù)類型，如下：1、基本類型short/long/unsigned int, float/double/long double, char2、指針：*是指針符，&是取址符。 int n = 5; int *p = &n;3、數(shù)組int a5 = 1,2,3,4,5;4、結(jié)構(gòu)體、共用體、自定義類struct、union、classPage 7領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值數(shù)據(jù)結(jié)構(gòu)與算法Page 8第一章 概念介紹第二章 常用數(shù)據(jù)結(jié)構(gòu)第三章 常用算法第四章 模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 常用數(shù)據(jù)結(jié)構(gòu)類型Page 9L

5、istSetverctor樹樹棧棧數(shù)據(jù)結(jié)構(gòu)map隊列隊列領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 順序表：vector vector是STL中提供的一種數(shù)據(jù)結(jié)構(gòu)，它是一個模板類，可以存放任意同一類型的對象； vector對象可以在運行時高效地添加元素； vector是連續(xù)存儲的，可以認為這是一個直接數(shù)組功能的類； vector的元素訪問需要通過iterator迭代器進行。Page 10領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 關(guān)鍵函數(shù)vector提供的主要函數(shù)如下：Page 11函數(shù)說明empty()如果vector是空的則返回tr

6、ue size() 返回容器中元素個數(shù)front()返回容器中第一個元素的引用back()返回容器中最后一個元素的引用push_back()向容器末尾添加一個元素pop_back()彈出容器中最后一個元素insert()在指定節(jié)點之前插入元素 clear()清空容器領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析vector的使用實例參見：DataStructExampleDataStructExampleVectorExample.cppPage 12領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 鏈表：listlist是雙向循環(huán)鏈表

7、，每一個元素都知道前面一個元素和后面一個元素。在STL中，list和vector一樣，是兩個常被使用的容器。Page 13領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 關(guān)鍵函數(shù)list提供的主要函數(shù)如下：Page 14函數(shù)說明函數(shù)說明empty()如果list是空的則返回true pop_back()刪除最后一個元素 size()返回list中的元素個數(shù)pop_front()刪除第一個元素 begin() 返回指向第一個元素的迭代器 push_back()在list的末尾添加一個元素 end()返回末尾的迭代器 push_front() 在list的頭部添加一個元素f

8、ront()返回第一個元素back()返回最后一個元素 insert()插入一個元素到list中 clear()刪除所有元素 領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析list的使用實例參見：DataStructExampleDataStructExampleListExample.cppPage 15領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) list與vector的區(qū)別1）list不支持對元素的任意存??；verctor則支持任意存取。2）list提供對表首元素的操作push_front、pop_front；vector不具備

9、。3）list的迭代器不會存在失效的情況；vector的迭代器可能會失效。4）list允許快速的插入和刪除；verctor不允許。5）list不存在重新申請內(nèi)存的情況，成本是恒定的；vector存在構(gòu)造成本。另外，在銷毀舊內(nèi)存的時候， vector會調(diào)用析構(gòu)函數(shù)，存在析構(gòu)成本。所以在存儲復(fù)雜類型和大量元素的情況下，list比vector更有優(yōu)勢！Page 16領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 集合：setset的含義是集合。 它是一個有序的容器，能夠?qū)⒉迦氲脑匕凑真I值自動排序； 它能保證集合中的元素不重復(fù)； 它的檢索效率高于list和隊列。 應(yīng)用場景構(gòu)

10、造set集合主要目的是為了快速檢索，不可直接去修改鍵值。Page 17領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 關(guān)鍵函數(shù)set提供的主要函數(shù)如下：Page 18函數(shù)說明pair insert(value)插入value，返回pair配對對象iterator insert(&pos, value)在pos位置之前插入value，返回新元素位置size_type erase(value) 移除set容器內(nèi)元素值為value的所有元素，返回移除的元素個數(shù)void erase(&pos) 移除pos位置上的元素void clear()移除set容器內(nèi)所有元素領(lǐng)先源自專業(yè)領(lǐng)

11、先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析set的使用實例參見：DataStructExampleDataStructExampleSetExample.cppPage 19領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 特點1）不能直接改變元素值，因為那樣會打亂原本正確的順序；2）不提供直接存取元素的任何操作函數(shù)，只能通過迭代器進行間接存取；3）元素比較動作只能用于類型相同的容器。Page 20領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 集合：mapmap是c+的一個鍵值對容器，它提供了很好一對一的關(guān)系，在一些程序

12、中建立一個map可以起到事半功倍的效果。 關(guān)鍵函數(shù)map提供的主要函數(shù)如下：Page 21函數(shù)說明根據(jù)key獲取valueinsert()插入鍵值對 find()查找元素，函數(shù)返回一個迭代器，指向鍵值為key的元素，如果沒找到就返回指向map尾部的迭代器。 領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析map的使用實例參見：DataStructExampleDataStructExampleMapExample.cppPage 22領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 樹樹是由n(n0)個結(jié)點組成的有限集合。其中：樹的定義是

13、遞歸的，一顆樹是由若干個子樹構(gòu)成的，每一個子樹由更小的若干子樹構(gòu)成。 結(jié)點25、64是48的孩子結(jié)點25是36的父親結(jié)點25、64是兄弟結(jié)點 特點每一個節(jié)點都可以有不止一個后繼，都有且只有一個前驅(qū)。Page 23領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析樹的使用實例參見：DataStructExampleDataStructExampleTreeExample.cppPage 24領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 棧棧是最常用、最重要的數(shù)據(jù)結(jié)構(gòu)之一。它是一種特殊的線性表，只能在表的一端進行插入和刪除操作。通常稱插入刪

14、除這一端為棧頂，另一端稱為棧底。數(shù)據(jù)從棧頂插入，從棧頂取出。 棧遵循后進先出的原則：Page 25領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析用S表示進棧操作，用P表示出棧操作，如果元素進棧順序是1234，為了得到1342出棧順序，請給出相應(yīng)的S和P操作串？解：其操作過程如下圖所示：可知，操作串是SPSSPSPP。Page 26領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 棧的應(yīng)用棧結(jié)構(gòu)比較常用的場景有：1）表達式求值，例如(69-9)/(4+6) 2）二叉樹的各種算法3）遞歸、非遞歸轉(zhuǎn)換Page 27領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識

15、提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) stack棧stack是STL中的很有用的容器適配器之一，默認基于Deque容器（雙向鏈表）實現(xiàn)。使用stack 只需要包含頭文件。關(guān)鍵函數(shù)Page 28函數(shù)說明stack構(gòu)造棧對象push()入棧pop()出棧empty()判斷棧是否為空，當?？諘r返回truesize()獲取棧中的元素個數(shù)領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析棧的使用實例參見：DataStructExampleDataStructExampleStackExample.cppPage 29 PS:需要注意的是，出棧操作只是刪除棧頂?shù)脑兀⒉?/p>

16、返回該元素。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 隊列隊列也是是一種特殊的線性表，隊列允許在表的一端進行插入，在表的另外一端進行刪除。通常把進行插入的一端稱作隊尾(rear)，進行刪除的一端稱作隊首或隊頭(front)。 隊列遵循先進先出的原則：Page 30領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析設(shè)有4個人站成一排，從左向右編號分別為1n，現(xiàn)在從左往右報數(shù)“1，2，1，2”，報數(shù)為1的人出列，數(shù)2的人不動。反復(fù)報數(shù)，直到所有人都出列為止，請給出出列順序？解：方法是構(gòu)造一個隊列，隊列元素有4個，出列一個結(jié)點，下一個節(jié)點

17、出列再入列，直到隊列為空。出列順序是：1324。Page 31領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 隊列的應(yīng)用隊列也應(yīng)用廣泛，比較常用的場景有：1）操作系統(tǒng)資源分配2）操作系統(tǒng)消息隊列Page 32領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) queue隊列queue用于模擬隊列這種數(shù)據(jù)結(jié)構(gòu)(先進先出 FIFO)。queue在頭文件中定義。關(guān)鍵函數(shù)Page 33函數(shù)說明queue構(gòu)造隊列對象push()將x元素接到隊列的末端pop()彈出隊列的第一個元素，并不會返回元素的值empty()判斷棧是否為空，當?？諘r返回truefront(

18、)訪問隊首元素back()訪問隊尾元素size()訪問隊中的元素個數(shù)領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實例分析隊列的使用實例參見：DataStructExampleDataStructExampleQueueExample.cppPage 34領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 小結(jié)數(shù)據(jù)結(jié)構(gòu)是軟件開發(fā)的基礎(chǔ)，著名的類庫皆是在這些規(guī)則的基礎(chǔ)上經(jīng)過封裝而來。掌握數(shù)據(jù)邏輯結(jié)構(gòu)，了解各種存儲結(jié)構(gòu)，并在此基礎(chǔ)上熟練使用各種類庫，才能寫出優(yōu)秀代碼。Page 35領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值數(shù)據(jù)結(jié)構(gòu)與算法Pag

19、e 36第一章 概念介紹第二章 常用數(shù)據(jù)結(jié)構(gòu)第三章 常用算法第四章 模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 算法是什么？ 數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系，對應(yīng)操作有邏輯結(jié)構(gòu)上的操作功能。把具體存儲結(jié)構(gòu)上的操作實現(xiàn)方法稱為算法。Page 37領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 算法的特性Page 38算法有輸出 有輸入可行性確定性有窮性領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 案例分析設(shè)計算法，求aX2+bX+c=0的根。Page 39算法步驟：1、計算d=b*b-4*a*c2、如果d0,轉(zhuǎn)5

20、3、如果d=5,轉(zhuǎn)94、如果d0,轉(zhuǎn)125、計算x1 = (-b+sqrt(d)/(2*a)6、計算x2 = (-b-sqrt(d)/(2*a)7、顯示兩個實根x1和x28、轉(zhuǎn)139、計算x=(-b)/(2*a)10、顯示一個實根x11、轉(zhuǎn)1312、顯示沒有實根13、算法結(jié)束 領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 算法設(shè)計的目標Page 40算法正確性高效率與低存儲健壯性可使用性領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 遞歸在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本身的情況，稱為遞歸。 直接遞歸： P調(diào)用P自身； 間接遞歸：函數(shù)P調(diào)用q，q調(diào)用

21、P。Page 41領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 應(yīng)用場景1）定義是遞歸的，例如求和n!和斐波那契數(shù)列2）數(shù)據(jù)結(jié)構(gòu)是遞歸的，例如單鏈表3）問題求解方法是遞歸的 實例分析遞歸函數(shù)算法的實例參見：DataStructExampleDataStructExampleRecursiveExample.cppPage 42領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 查找算法 順序查找法在給定的數(shù)據(jù)結(jié)構(gòu)中找出某個指定的元素是指在給定的數(shù)據(jù)結(jié)構(gòu)中找出某個指定的元素。最好情況下只做一次比較，最差情況下要與所有的元素進行比較。在平均情況下大約要與表中

22、的一般元素進行比較。對于較大的線性表，順序查找效率低下。應(yīng)用場景1）線性表是無序表2）鏈式存儲結(jié)構(gòu)的表Page 43領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 實例分析（順序查找）順序查找算法的實例參見：DataStructExampleDataStructExampleSearchInOrderExample.cppPage 44領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 二分查找法（折半查找）查找過程：每次將待查記錄所在區(qū)間縮小一半使用條件：采用順序存儲結(jié)構(gòu)的有序靜態(tài)查找表時間復(fù)雜度：O(log2n)Page 45領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知

23、識提升價值知識提升價值第三章 常用算法 實例分析（二分查找）順序查找算法的實例參見：DataStructExampleDataStructExampleSearchInHalfExample.cppPage 46領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 排序算法Page 47排序算法直接插入排序冒泡排序歸并排序基數(shù)排序直接選擇排序希爾排序堆排序快速排序領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 冒泡排序Page 48領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板實例分析冒泡排序的實例參見：DataStructExampleDa

24、taStructExampleBubbleSortExample.cppPage 49領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 快速排序Page 50領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板實例分析快速排序的實例參見：DataStructExampleDataStructExampleQuickSortExample.cppPage 51領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 應(yīng)用場景1）若n較小(如n50)，可采用直接插入或直接選擇排序。當記錄規(guī)模較小時，選用直接插入排序、直接選擇排序為宜，最簡單。2）若文件初始狀態(tài)

25、基本有序(指正序)，選用直接插人、冒泡或隨機的快速排序為宜；3）若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內(nèi)部排序中被認為是最好的方法，當待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短。Page 52領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 排序算法總結(jié)Page 53排序方法時間復(fù)雜度空間復(fù)雜度穩(wěn)定性復(fù)雜性直接插入排序O(n2)O(1)穩(wěn)定簡單希爾排序O(nlog2n)O(1)不穩(wěn)定復(fù)雜直接選擇排序O(nlog2n)O(1)不穩(wěn)定簡單堆排序O(nlog2n)O(1)不穩(wěn)定復(fù)雜冒泡排序O(n2)O(1

26、)穩(wěn)定簡單快速排序O(nlog2n)O(nlog2n)不穩(wěn)定復(fù)雜歸并排序O(nlog2n)O(n)穩(wěn)定復(fù)雜基數(shù)排序O(d(n+r)O(n+r)穩(wěn)定復(fù)雜領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值n 時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間量度記作 T(n)=O(f(n)，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。空間復(fù)雜度是指算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量。記作：S(n)=O(f(n) 其中：n為問題的規(guī)模(或大小)。第三章 常用算法Page 54領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法

27、n STL算法STL算法部分主要由頭文件,組成，算法大致分為四類：Page 55可以修改它們所操作的容器內(nèi)容的算法可變序列算法不直接修改其所操作的容器內(nèi)容的算法非可變序列算法對容器內(nèi)容進行數(shù)值計算數(shù)值算法包括對序列進行排序和合并的算法、搜索算法以及有序序列上的集合操作。排序算法領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 STL非可變序列算法這是一組不破壞操作數(shù)據(jù)的模板函數(shù)，用來對序列數(shù)據(jù)進行逐個處理、元素查找、子序列搜索、統(tǒng)計和匹配,具有極為廣泛的適用性。l 關(guān)鍵函數(shù)Page 56類型函數(shù)說明循環(huán)for_each()對序列中的每個元素執(zhí)行某操作。查找find()在序列中

28、找出某個值的第一次出現(xiàn)的位置。find_if()在序列中找出符合某謂詞的第一個元素。find_end()在序列中找出一子序列的最后一次出現(xiàn)的位置。find_first_of()在序列中找出第一次出現(xiàn)指定值集中之值的位置。計數(shù)count()在序列中統(tǒng)計某個值出現(xiàn)的次數(shù)。count_if()在序列中統(tǒng)計與某謂詞匹配的次數(shù)。搜索search()找出兩個序列相異的第一個元素。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 STL可變序列算法這是一組能夠修改容器元素數(shù)據(jù)的模板函數(shù)。l 關(guān)鍵函數(shù)Page 57類型函數(shù)說明復(fù)制copy()從序列的第一個元素起進行復(fù)制。交換swap()交換

29、兩個元素。transform將某操作應(yīng)用于指定范圍的每個元素變換replace()用一個給定值替換一些值。replace_if()替換滿足謂詞的一些元素填充fill_n()用一給定值取代前n個元素。生成generate()用一操作的結(jié)果取代所有元素刪除remove_if()刪除滿足謂詞的元素。唯一unique()刪除相鄰的重復(fù)元素。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 STL排序算法提供元素排序策略。l 關(guān)鍵函數(shù)Page 58類型函數(shù)說明排序sort()以很好的平均效率排序二分檢索lower_bound()找到大于等于某值的第一次出現(xiàn)。binary_search(

30、)在有序序列中確定給定元素是否存在歸并merge()歸并兩個有序序列。includes()一序列為另一序列的子序列時為真。堆操作sort_heap()給堆排序。最大和最小max()取得兩個值中較大的。min()取得兩個值中較小的。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 STL數(shù)值算法對容器內(nèi)容進行數(shù)值計算。此種算法不多，涉及到專業(yè)領(lǐng)域中有用的算術(shù)操作，獨立包涵于頭文件中。l 關(guān)鍵函數(shù)Page 59函數(shù)說明Accumulate對標識的序列段元素之和，加到一個由val指定的初始值上。partial_sum創(chuàng)建一個新序列，其中每個元素值代表指定范圍內(nèi)該位置前所有元素之和。

31、 inner_product對兩個序列做內(nèi)積(對應(yīng)元素相乘，再求和)并將內(nèi)積加到一個輸入的初始值上。 adjacent_difference創(chuàng)建一個新序列，新序列中每個新值代表當前元素與上一個元素的差。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法 STL算法實例STL算法的部分實例參見：DataStructExampleDataStructExampleSTLAlgorithmExample.cppPage 60領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第三章 常用算法n 小結(jié)我們的日常工作中一定會接觸到各種算法，因而掌握一些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)及算法是十分必要的。在本

32、章的所有算法中，基礎(chǔ)的查找和排序算法是一定要掌握的，請大家在課后注意多加練習。Page 61領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值數(shù)據(jù)結(jié)構(gòu)與算法Page 62第一章 概念介紹第二章 常用數(shù)據(jù)結(jié)構(gòu)第三章 常用算法第四章 模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板n 什么是模板？模板（Template），是根據(jù)參數(shù)類型生成函數(shù)和類的機制（有時稱為“參數(shù)決定類型”），通過使用模板，可以只設(shè)計一個類來處理多種類型的數(shù)據(jù)，而不必為每一種類型分別創(chuàng)建類。Page 63領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板n 案例分析針對int、long、char

33、三種類型創(chuàng)建函數(shù)來返回兩個參數(shù)中較小的一個，如果不使用template，必須要編寫一系列如下的函數(shù)：然而，使用template，可以減少重復(fù)部分，形成一個函數(shù)：Page 64領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板n 模板的優(yōu)點模板具有以下幾個優(yōu)勢：Page 65開發(fā)容易 你可以只為你的類或函數(shù)創(chuàng)建一個普通的版本代替手工創(chuàng)建特殊情況處理。理解容易 模板為抽象類型信息提供了一個直截了當?shù)姆椒āｎ愋桶踩?模板使用的類型在編譯時是明確的，編譯器可以在發(fā)生錯誤之前進行類型檢查。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板n 應(yīng)用場景模板經(jīng)常被用來實現(xiàn)如下功能：創(chuàng)

34、建一個類型安全的集合類（例如，堆棧）用來處理各種類型的數(shù)據(jù)；為函數(shù)添加額外的類型檢查以避免獲得空指針；合并操作符重載組來修改類型行為（例如智能指針）； 實際上，大多數(shù)以上應(yīng)用可以不用模板實現(xiàn)。Page 66領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板n 模板的應(yīng)用模板通常有兩種使用方式，也就是函數(shù)模板和類模板。下面，我們就針對函數(shù)模板和類模板的使用進行學習。Page 67函數(shù)模板類模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識提升價值知識提升價值第四章 模板n 函數(shù)模板概念使用函數(shù)模板，你可以指定一組基于相同代碼但是處理不同類型或類的函數(shù)。定義模板關(guān)鍵自字為template，定義如圖所示：這段代碼定義了一個函數(shù)家族來交換函數(shù)的參數(shù)值。從這個函數(shù)模板你可以產(chǎn)生一系列函數(shù)，不僅可以交換int、lon