實(shí)用技巧與模版庫(kù)ppt課件

第八章C+實(shí)用技巧與模版庫(kù),1,在本章中將介紹各種各樣實(shí)用的提高我們編程效率的小技巧和模版庫(kù)。其中絕大多數(shù)依靠C+自帶類(lèi)和函數(shù)實(shí)現(xiàn)。,2,第一節(jié)排序算法,排序算法為競(jìng)賽中最常用的算法之一，我們可以利用C+自帶的庫(kù)函數(shù)進(jìn)行排序。,3,使用排序算法必須包含algorithm頭文件自帶排序算法的一般形式為：/將數(shù)組arr的下標(biāo)為m的元素到下標(biāo)為n-1的元素進(jìn)行從小到大排序sort(arr+m,arr+n);sort(arr+m,arr+n,comp);/與sort(arr+m,arr+n);相比，這個(gè)/寫(xiě)法可以自己定義排序的規(guī)則/其中，comp為自定義的函數(shù),4,對(duì)于sort(arr+m,arr+n)我們舉個(gè)簡(jiǎn)單的例子：/這個(gè)程序?qū)崿F(xiàn)從鍵盤(pán)讀入10個(gè)數(shù)，然后從小到大輸出的功能#include#includeusingnamespacestd;inta10;intmain()for(inti=0;i>ai;sort(a+0,a+10);for(inti=0;i<10;+i)cout<<ai<<cout<>n;for(inti=0;i>ai.name;cin>>ai.score;sort(a+0,a+n,score_comp);for(inti=0;i<n;+i)cout<<ai.name<<<<ai.score<<endl;return0;,11,第二節(jié)重載運(yùn)算符,在之前的高精度運(yùn)算的章節(jié)，我們學(xué)習(xí)過(guò)使用高精度算法進(jìn)行高精度數(shù)的計(jì)算。當(dāng)我們多次使用高精時(shí)，我們就會(huì)把它寫(xiě)成函數(shù)。或許你會(huì)疑問(wèn)，我們難道不能向像inta=3,b=4,c;c=a+b;一樣進(jìn)行運(yùn)算嗎？答案是肯定的。接下來(lái)我們將介紹如何利用重載運(yùn)算符進(jìn)行高精計(jì)算。,12,為方便學(xué)習(xí)，我們將假設(shè)我們所進(jìn)行運(yùn)算的數(shù)字為非負(fù)整數(shù)。首先我們需要定義一個(gè)結(jié)構(gòu)，使得我們的高精數(shù)可以存儲(chǔ)。constintMAXN=4000;/高精度數(shù)的長(zhǎng)度structBIGNUMintlen,sMAXN;BIGNUM()len=1;memset(s,0,sizeof(s);結(jié)構(gòu)體里面有一個(gè)BIGNUM()的函數(shù)，它稱為“構(gòu)造函數(shù)（Constructor）”。構(gòu)造函數(shù)是C+中特有的，作用就是進(jìn)行初始化。每當(dāng)我們定義一個(gè)BIGNUM類(lèi)型的變量時(shí)，這個(gè)變量就會(huì)被初始化。例如定義BIGNUMx時(shí)，我們將會(huì)得x.len=1,x.s中的所有元素均為0。,13,我們知道，結(jié)構(gòu)體之間是可以相互賦值的。但我們?nèi)绾文苡谩?”將字符串?dāng)?shù)字賦給BIGNUM的變量？很簡(jiǎn)單，只要在結(jié)構(gòu)體里面寫(xiě)如下運(yùn)算符重載：BIGNUMoperator=(constchar*num)/operator是關(guān)鍵字len=strlen(num);for(inti=0;i”，和重載”>(istream,16,我們已經(jīng)可以實(shí)現(xiàn)高精度數(shù)的存儲(chǔ)，賦值，初始化，輸入，輸出了?，F(xiàn)在一定迫不及待的想知道如何實(shí)現(xiàn)高精度的運(yùn)算了吧。由于篇幅有限，本文僅展示”+”、”+=”重載。這個(gè)也是寫(xiě)在結(jié)構(gòu)體里面：BIGNUMoperator+(constBIGNUM,17,對(duì)于數(shù)字，我們不僅會(huì)對(duì)它們進(jìn)行計(jì)算，有時(shí)我們還會(huì)對(duì)他它們進(jìn)行比較，當(dāng)然這個(gè)也要進(jìn)行運(yùn)算符重載，依然是在結(jié)構(gòu)體里面補(bǔ)充相關(guān)代碼：我們先重載下“=0;-i)if(si!=x.si)returnsi<x.si;returnfalse;/全部都相等，說(shuō)明小于不成立,18,現(xiàn)在用”(constBIGNUM,19,例8.2運(yùn)用重載的例子：給出n和m，求出1!+2!+3!+.+n!是否大于m.大于m的話輸出”yes”，否則輸出”no”.其中0<n<101,m<10500.【輸入格式】只有一行，包括一個(gè)n和一個(gè)m【輸出格式】如果1!+2!+3!+.+n!大于m，則輸出”yes”,否則輸出”no”【輸入樣例】338954945705218228090637347680100940313【輸出樣例】no,20,【參考程序】#include#include#include#includeusingnamespacestd;constintMAXN=4000;structBIGNUMintlen,sMAXN;BIGNUM()memset(s,0,sizeof(s);len=1;,21,BIGNUMoperator=(constchar*num)len=strlen(num);for(inti=0;i>n>>m;for(inti=1;im)cout<<"yes"<<endl;elsecout<<"no"<>s)cout<<+tot<<<<s<<endl;return0;,30,我們用下劃線_代替空格，讀入時(shí)記得使用空格輸入樣例:_Hello_world!_Today_輸出樣例:1Hello2world!3Today,31,正如介紹的那樣，讀入時(shí)忽略了空字符，讀者可以將其記作cin讀字符串讀的是單詞。當(dāng)然，有時(shí)我們更希望讀取的是句子。幸好C+提供了getline函數(shù)以供使用。getline的原型是：getline(cin,s);cin指的是讀入流，一般情況下我們直接寫(xiě)cin即可，s是字符串，即我們讀入的東西要存放的字符串。,32,我們用getline來(lái)讀取上面的數(shù)據(jù)：程序：#include#includeusingnamespacestd;intmain()strings;inttot=0;while(getline(cin,s)/getline()讀入會(huì)舍棄換行符cout<<+tot<<<<s<<endl;return0;我們依舊使用下劃線_代替空格.輸出為：1_Hello_world!_2_Today_,33,string類(lèi)型的操作,34,字符串類(lèi)型相加：strings1(“hello”);/等價(jià)于strings1=”hello”;strings2(“worldn”);s1+=s2/等價(jià)于s1=s1+s2，此時(shí)s1=”helloworldn”字符串“+”操作符的左右操作數(shù)必須有一個(gè)為字符串類(lèi)型。strings1=”hello”;strings2=”world”;strings3=s1+”,”;/合法strings4=”hello”+”world”;/非法法strings5=s1+”,”+”world”;/合法，根據(jù)從左至右的結(jié)合法則/s1+”,”變成一個(gè)字符串類(lèi)型，然后再與”world”相連。strings6=”hello”+”,“+s2;/非法，因?yàn)椤県ello”與”,”都是字符數(shù)組類(lèi)型,35,字符串的下標(biāo)操作：stringstr=”2+2=4”;cout<<str1<<endl;/將輸出+str1=*;/現(xiàn)在str1變成了*其它一些常用操作：,36,將字符串類(lèi)型的變量轉(zhuǎn)化為數(shù)字：/錯(cuò)誤方法#include#include#includeusingnamespacestd;intmain()strings1="1234",s2="4321"cout<<s1+s2<<endl;return0;正如前面所講s1+s2是將兩個(gè)字符串類(lèi)型相連,37,/正確方法#include#include#includeusingnamespacestd;intmain()strings1="1234",s2="4321"inta,b;sscanf(s1.c_str(),"%d",同樣也可以利用sprintf()將數(shù)據(jù)輸入到sprintf()。sscanf()/sprintf()的用法與scanf()/printf相同，只是在參數(shù)中第一個(gè)加個(gè)字符數(shù)組。,38,第四節(jié)FIFO隊(duì)列和優(yōu)先隊(duì)列,在實(shí)際應(yīng)用中，我們將會(huì)大量使用到FIFO隊(duì)列和優(yōu)先隊(duì)列，本節(jié)將介紹這兩個(gè)C+自帶算法。,39,當(dāng)然，使用他們必須包含queue頭文件。定義FIFO隊(duì)列queue變量名queueque/定義que為一個(gè)int類(lèi)型的FIFO隊(duì)列queuea/定義a為一個(gè)char類(lèi)型的FIFO隊(duì)列queuec/定義c為一個(gè)data類(lèi)型的FIFO隊(duì)列/其中data為自定義的數(shù)據(jù)類(lèi)型，可以為結(jié)構(gòu)體定義簡(jiǎn)單的優(yōu)先隊(duì)列priority_queueheap;/定義heap為一個(gè)int類(lèi)型的優(yōu)先隊(duì)列priority_queuek;/定義k為一個(gè)double類(lèi)型的優(yōu)先隊(duì)列這兩種定義方式都是大根堆，想要使其變成小根堆，可以將每個(gè)數(shù)據(jù)都乘以-1,40,定義結(jié)構(gòu)體的優(yōu)先隊(duì)列structdataintx;booloperatorq;/q優(yōu)先隊(duì)列的優(yōu)先規(guī)則由data重載小于號(hào)決定,41,FIFO隊(duì)列和優(yōu)先隊(duì)列的操作,42,利用C+自帶優(yōu)先隊(duì)列的合并果子代碼：#include#include#includeusingnamespacestd;priority_queueque;intmain()intn;scanf("%d",return0；,43,第五節(jié)動(dòng)態(tài)數(shù)組為了節(jié)省空間，有時(shí)我們會(huì)使用動(dòng)態(tài)數(shù)組vector。定義動(dòng)態(tài)數(shù)組vector變量名vectorque/定義que為一個(gè)int類(lèi)型的動(dòng)態(tài)數(shù)組vectora/定義a為一個(gè)char類(lèi)型的動(dòng)態(tài)數(shù)組vectorc/其中data為自定義的數(shù)據(jù)類(lèi)型，可以為結(jié)構(gòu)體,44,45,利用C+動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的排序代碼：#include#include#include#includeusingnamespacestd;intmain()vectora;/動(dòng)態(tài)數(shù)組intn;scanf("%d",46,第六節(jié)關(guān)聯(lián)式容器map在實(shí)際應(yīng)用中，我們可以使用map容器來(lái)作為一個(gè)有序的映射表，可以將其看做是一個(gè)下標(biāo)可以是任何類(lèi)型的數(shù)組。對(duì)map單次操作的時(shí)間復(fù)雜度為O(lgn)。定義mapmap變量名;mapma;/定義ma為一個(gè)從string到int的一個(gè)映射訪問(wèn)map中的元素mapma;/定義mama“abc”=2;/將字符串”abc”映射到整數(shù)”2”上cout<<ma“abc”<<endl;/屏幕上將輸出整數(shù)2同時(shí)，map中的類(lèi)型可以是自己定義的結(jié)構(gòu)體，此時(shí)結(jié)構(gòu)體中應(yīng)該有重載小于符號(hào)。,47,map的操作：,48,注意：一旦map中的一個(gè)元素被訪問(wèn)，不論它之前是否已經(jīng)被賦值，它都將被視為已經(jīng)存在，例如：if(ma“abc”)/*dosomething*/;if(ma.count(“abc”)cout#include#includeusingnamespacestd;mapma;,49,intmain()ma"apple"=1;ma"banana"=2;ma"lemon"=3;coutfirstsecond<<endl;/輸出ma"lemon"，即輸出3return0;,50,