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

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

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

3、 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第一章 概念介紹 方法二：鏈表存儲(chǔ)struct StudentNode int nNum;/學(xué)號(hào) char name8;/名字 char sex3;/性別 int nCls;/班級(jí) struct StudentNode *pNext;Page 51劉麗女115王萍女2NULL15陳華男712王琦男7Head領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值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è) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第一章 概念介紹n 數(shù)據(jù)類型正式開(kāi)始學(xué)習(xí)之前，我們先來(lái)回顧一

4、下C/C+常用數(shù)據(jù)類型，如下：1、基本類型short/long/unsigned int, float/double/long double, char2、指針：*是指針?lè)?amp;是取址符。 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í)提升價(jià)值知識(shí)提升價(jià)值數(shù)據(jù)結(jié)構(gòu)與算法Page 8第一章 概念介紹第二章 常用數(shù)據(jù)結(jié)構(gòu)第三章 常用算法第四章 模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 常用數(shù)據(jù)結(jié)構(gòu)類

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

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

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

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

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

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

11、et容器內(nèi)所有元素領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第二章 常用數(shù)據(jù)結(jié)構(gòu) 實(shí)例分析set的使用實(shí)例參見(jiàn)：DataStructExampleDataStructExampleSetExample.cppPage 19領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第二章 常用數(shù)據(jù)結(jié)構(gòu) 特點(diǎn)1）不能直接改變?cè)刂?，因?yàn)槟菢訒?huì)打亂原本正確的順序；2）不提供直接存取元素的任何操作函數(shù)，只能通過(guò)迭代器進(jìn)行間接存?。?）元素比較動(dòng)作只能用于類型相同的容器。Page 20領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第二章 常用數(shù)據(jù)結(jié)構(gòu)n 集合：mapmap是c+的一個(gè)鍵值對(duì)容器，它提

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

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

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

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

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

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

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

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

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

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

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

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

24、SortExample.cppPage 49領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 快速排序Page 50領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第四章 模板實(shí)例分析快速排序的實(shí)例參見(jiàn)：DataStructExampleDataStructExampleQuickSortExample.cppPage 51領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 應(yīng)用場(chǎng)景1）若n較小(如n50)，可采用直接插入或直接選擇排序。當(dāng)記錄規(guī)模較小時(shí)，選用直接插入排序、直接選擇排序?yàn)橐耍詈?jiǎn)單。2）若文件初始狀態(tài)基本有序(指正序)，選用直接插人、冒泡或隨

25、機(jī)的快速排序?yàn)橐耍?）若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序?？焖倥判蚴悄壳盎诒容^的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短。Page 52領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 排序算法總結(jié)Page 53排序方法時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性復(fù)雜性直接插入排序O(n2)O(1)穩(wěn)定簡(jiǎn)單希爾排序O(nlog2n)O(1)不穩(wěn)定復(fù)雜直接選擇排序O(nlog2n)O(1)不穩(wěn)定簡(jiǎn)單堆排序O(nlog2n)O(1)不穩(wěn)定復(fù)雜冒泡排序O(n2)O(1)穩(wěn)定簡(jiǎn)單快速排序O(nlog2n)O(n

26、log2n)不穩(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è) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值n 時(shí)間復(fù)雜度和空間復(fù)雜度 時(shí)間復(fù)雜度算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作 T(n)=O(f(n)，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 空間復(fù)雜度是指算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記作：S(n)=O(f(n) 其中：n為問(wèn)題的規(guī)模(或大小)。第三章 常用算法Page 54領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法n STL算法STL算法部分主要由頭文

27、件,組成，算法大致分為四類：Page 55可變序列算法非可變序列算法數(shù)值算法排序算法領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 STL非可變序列算法這是一組不破壞操作數(shù)據(jù)的模板函數(shù)，用來(lái)對(duì)序列數(shù)據(jù)進(jìn)行逐個(gè)處理、元素查找、子序列搜索、統(tǒng)計(jì)和匹配,具有極為廣泛的適用性。l 關(guān)鍵函數(shù)Page 56類型函數(shù)說(shuō)明循環(huán)for_each()對(duì)序列中的每個(gè)元素執(zhí)行某操作。查找find()在序列中找出某個(gè)值的第一次出現(xiàn)的位置。find_if()在序列中找出符合某謂詞的第一個(gè)元素。find_end()在序列中找出一子序列的最后一次出現(xiàn)的位置。find_first_of()在序列中找出第一次

28、出現(xiàn)指定值集中之值的位置。計(jì)數(shù)count()在序列中統(tǒng)計(jì)某個(gè)值出現(xiàn)的次數(shù)。count_if()在序列中統(tǒng)計(jì)與某謂詞匹配的次數(shù)。搜索search()找出兩個(gè)序列相異的第一個(gè)元素。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 STL可變序列算法這是一組能夠修改容器元素?cái)?shù)據(jù)的模板函數(shù)。l 關(guān)鍵函數(shù)Page 57類型函數(shù)說(shuō)明復(fù)制copy()從序列的第一個(gè)元素起進(jìn)行復(fù)制。交換swap()交換兩個(gè)元素。transform將某操作應(yīng)用于指定范圍的每個(gè)元素變換replace()用一個(gè)給定值替換一些值。replace_if()替換滿足謂詞的一些元素填充fill_n()用一給定值取代前n個(gè)元

29、素。生成generate()用一操作的結(jié)果取代所有元素刪除remove_if()刪除滿足謂詞的元素。唯一unique()刪除相鄰的重復(fù)元素。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 STL排序算法提供元素排序策略。l 關(guān)鍵函數(shù)Page 58類型函數(shù)說(shuō)明排序sort()以很好的平均效率排序二分檢索lower_bound()找到大于等于某值的第一次出現(xiàn)。binary_search()在有序序列中確定給定元素是否存在歸并merge()歸并兩個(gè)有序序列。includes()一序列為另一序列的子序列時(shí)為真。堆操作sort_heap()給堆排序。最大和最小max()取得兩個(gè)值中較

30、大的。min()取得兩個(gè)值中較小的。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 STL數(shù)值算法對(duì)容器內(nèi)容進(jìn)行數(shù)值計(jì)算。此種算法不多，涉及到專業(yè)領(lǐng)域中有用的算術(shù)操作，獨(dú)立包涵于頭文件中。l 關(guān)鍵函數(shù)Page 59函數(shù)說(shuō)明Accumulate對(duì)標(biāo)識(shí)的序列段元素之和，加到一個(gè)由val指定的初始值上。partial_sum創(chuàng)建一個(gè)新序列，其中每個(gè)元素值代表指定范圍內(nèi)該位置前所有元素之和。 inner_product對(duì)兩個(gè)序列做內(nèi)積(對(duì)應(yīng)元素相乘，再求和)并將內(nèi)積加到一個(gè)輸入的初始值上。 adjacent_difference創(chuàng)建一個(gè)新序列，新序列中每個(gè)新值代表當(dāng)前元素與上一個(gè)元

31、素的差。領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法 STL算法實(shí)例STL算法的部分實(shí)例參見(jiàn)：DataStructExampleDataStructExampleSTLAlgorithmExample.cppPage 60領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第三章 常用算法n 小結(jié)我們的日常工作中一定會(huì)接觸到各種算法，因而掌握一些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)及算法是十分必要的。在本章的所有算法中，基礎(chǔ)的查找和排序算法是一定要掌握的，請(qǐng)大家在課后注意多加練習(xí)。Page 61領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值數(shù)據(jù)結(jié)構(gòu)與算法Page 62第一章 概念介紹第二章

32、常用數(shù)據(jù)結(jié)構(gòu)第三章 常用算法第四章 模板領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第四章 模板n 什么是模板？模板（Template），是根據(jù)參數(shù)類型生成函數(shù)和類的機(jī)制（有時(shí)稱為“參數(shù)決定類型”），通過(guò)使用模板，可以只設(shè)計(jì)一個(gè)類來(lái)處理多種類型的數(shù)據(jù)，而不必為每一種類型分別創(chuàng)建類。Page 63領(lǐng)先源自專業(yè)領(lǐng)先源自專業(yè) 知識(shí)提升價(jià)值知識(shí)提升價(jià)值第四章 模板n 案例分析針對(duì)int、long、char三種類型創(chuàng)建函數(shù)來(lái)返回兩個(gè)參數(shù)中較小的一個(gè)，如果不使用template，必須要編寫一系列如下的函數(shù)：然而，使用template，可以減少重復(fù)部分，形成一個(gè)函數(shù)：Page 64領(lǐng)先源自專業(yè)領(lǐng)先源自

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