群體類(lèi)和群體數(shù)據(jù)的組織

群體類(lèi)和群體數(shù)據(jù)的組織第一頁(yè)，共三十七頁(yè)，2022年，8月28日 類(lèi)模板用于設(shè)計(jì)一個(gè)通用類(lèi)，使這個(gè)類(lèi)的數(shù)據(jù)成員的類(lèi)型、成員函數(shù)的參數(shù)能夠按照需要進(jìn)行改變（即參數(shù)化） 聲明類(lèi)模板的一般形式為：

template<classTtype> classclass_name { }

其中，Ttype是一個(gè)標(biāo)識(shí)符，代表所聲明的類(lèi)模板中參數(shù)化的類(lèi)型名。注意：模板類(lèi)的成員函數(shù)必須是函數(shù)模板。定義了類(lèi)模板以后，就可以創(chuàng)建這個(gè)類(lèi)的實(shí)例：

Class_name<type>對(duì)象1，…，對(duì)象n；

type用具體的數(shù)據(jù)類(lèi)型代入，系統(tǒng)根據(jù)代入的數(shù)據(jù)類(lèi)型生成所需的類(lèi)，并創(chuàng)建該類(lèi)的對(duì)象。9.1類(lèi)模板第二頁(yè)，共三十七頁(yè)，2022年，8月28日//EX9_1.cpp:演示類(lèi)模板的定義和使用#include<iostream.h>#include<stdlib.h>structstudent //聲明一個(gè)結(jié)構(gòu)體類(lèi)型{intid;intscore;};template<classT> //聲明一個(gè)類(lèi)模板classbuffer{private: Ta; intempty;public: buffer(void); //聲明buffer類(lèi)的構(gòu)造函數(shù)

Tget(void); voidput(Tx);};第三頁(yè)，共三十七頁(yè)，2022年，8月28日template<classT> //定義buffer類(lèi)的構(gòu)造函數(shù)模板buffer<T>::buffer(void):empty(0){}template<classT> //定義成員函數(shù)get模板Tbuffer<T>::get(void){if(empty==0){ cout<<"thebufferisempty!"<<endl; exit(1);}returna;}template<classT> //定義成員函數(shù)put模板voidbuffer<T>::put(Tx){empty++;a=x;}第四頁(yè)，共三十七頁(yè)，2022年，8月28日voidmain(void){students={1022,78};buffer<int>i1,i2; //聲明整型對(duì)象i1,i2buffer<student>stu1; //聲明結(jié)構(gòu)體對(duì)象stu1buffer<double>d; //聲明雙精度對(duì)象di1.put(13); //對(duì)象i1調(diào)用put執(zhí)行了empty++i2.put(-101); //對(duì)象i2調(diào)用put執(zhí)行了empty++cout<<i1.get()<<""<<i2.get()<<endl;stu1.put(s); //對(duì)象stu1調(diào)用put執(zhí)行了empty++cout<<"thestudent'sidis"<<stu1.get().id<<endl;cout<<"thestudent'sscoreis"<<stu1.get().score<<endl;cout<<d.get()<<endl; //對(duì)象d沒(méi)有調(diào)用put去執(zhí)行empty++} //，可能直接exit而不執(zhí)行returna第五頁(yè)，共三十七頁(yè)，2022年，8月28日程序運(yùn)行結(jié)果為：

13-101 thestudent’sidis1022 thestudent’sscoreis78 thebufferisempty!第六頁(yè)，共三十七頁(yè)，2022年，8月28日1.string類(lèi)對(duì)象的定義與初始化形式1：string對(duì)象名[("字符串")]

//[]表示可選項(xiàng) 或string對(duì)象名[="字符串"]

//[]表示可選項(xiàng)形式2：（生成由n個(gè)“字符”組成的字符串）

string對(duì)象名(n，‘字符’)2.string類(lèi)對(duì)象的操作

通過(guò)string類(lèi)對(duì)象的成員函數(shù)調(diào)用與重載運(yùn)算符(>>、<<、+等)

對(duì)字符串進(jìn)行賦值、連接、復(fù)制、查找、交換等?；拘问綖?/p>

<對(duì)象名>.<成員函數(shù)>string類(lèi)第七頁(yè)，共三十七頁(yè)，2022年，8月28日//EX9_2.cpp:演示string類(lèi)的應(yīng)用#include<iostream.h>#include<string>usingnamespacestd;voidmain(){strings1("Hello"),s2,s3,s4; //定義string對(duì)象

s2=s1; //用"="號(hào)進(jìn)行賦值(重載運(yùn)算符=)s3.assign(s1); //調(diào)用成員函數(shù)assign()進(jìn)行賦值

cout<<"s1="<<s1.data()<<",s2="<<s2.data()<<",s3="<<s3.data()<<endl;cout<<"s1的長(zhǎng)度="<<s1.length()<<endl;//輸出字符串長(zhǎng)度

chara[]="China!",b[6];s1=a; //string對(duì)象s1接收字符數(shù)組a的賦值

cout<<"s1="<<s1.data()<<endl;for(inti=0;i<5;i++)b[i]=s2[i]; //此語(yǔ)句也可表示為:b[i]=s2.at(i);第八頁(yè)，共三十七頁(yè)，2022年，8月28日

b[5]='\0';cout<<"字符數(shù)組b="<<b<<endl; //字符串的連接

s4=s2+""+s1;//用"+"進(jìn)行字符串的連接(重載運(yùn)算符+)s3=s2.append(s1);//s2與s1連接并賦給s3，注意連接后的s2結(jié)果

cout<<"s2="<<s2.data()<<",s3="<<s3.data()<<",s4="<<s4.data()<<endl;intf=pare(6,5,s4,7,5);//將s3的第6個(gè)開(kāi)始的5個(gè)字符與 //s4的第7個(gè)開(kāi)始的5個(gè)字符進(jìn)行比較

if(f==0)cout<<"s3與s4比較的部分相等"<<"\n";else cout<<"s3與s4比較的部分不相等"<<"\n";//取子字符串操作第九頁(yè)，共三十七頁(yè)，2022年，8月28日

stringsz=s2.substr(5,5);//取s2的第5個(gè)開(kāi)始的5個(gè)字符

cout<<"子字符串sz="<<sz.data()<<endl;s1.swap(s4); //交換s1與s4cout<<"s1="<<s1.data()<<",s4="<<s4.data()<<endl;cout<<“字符串China在s1中的位置為：”<<s1.find("China")<<endl;intlen=s1.length();char*pt=newchar[len+1];//定義字符型指針并動(dòng)態(tài)分配空間

s1.copy(pt,len,0);//將s1復(fù)制到pt所指的數(shù)組(相當(dāng)于pt=&s1[0];)pt[len]='\0';cout<<pt<<endl;s2=pt; //string類(lèi)對(duì)象s2接收字符型指針的賦值

cout<<s2.data()<<endl;}第十頁(yè)，共三十七頁(yè)，2022年，8月28日程序運(yùn)行結(jié)果為:

s1=Hello,s2=Hello,s3=Hello s1的長(zhǎng)度=5 s1=China!

字符數(shù)組b=Hello s2=HelloChina!,s3=HelloChina!,s4=HelloChina! s3與s4比較的部分相等子字符串sz=China s1=HelloChina!,s4=China!

字符串China在s1中的位置為:6 HelloChina! HelloChina!第十一頁(yè)，共三十七頁(yè)，2022年，8月28日9.2群體數(shù)據(jù)群體的概念群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類(lèi)：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。非線性群體不用位置順序來(lái)標(biāo)識(shí)元素?！谝粋€(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素第十二頁(yè)，共三十七頁(yè)，2022年，8月28日9.2.1線性群體的概念線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照訪問(wèn)元素的不同方法分為直接訪問(wèn)、順序訪問(wèn)和索引訪問(wèn)。9.2.2直接訪問(wèn)群體—數(shù)組靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過(guò)下標(biāo)直接訪問(wèn)。缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無(wú)法修改。動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類(lèi)型的元素組成。優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。動(dòng)態(tài)數(shù)組類(lèi)模板舉例參見(jiàn)P293～301第十三頁(yè)，共三十七頁(yè)，2022年，8月28日9.2.3順序訪問(wèn)群體—鏈表鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)表示順序訪問(wèn)的線性群體。鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每一個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和指向鏈表中下一個(gè)結(jié)點(diǎn)的指針（即下一個(gè)結(jié)點(diǎn)的地址）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表。

鏈表模板和應(yīng)用舉例參見(jiàn)P302～307第十四頁(yè)，共三十七頁(yè)，2022年，8月28日9.2.4特殊的線性群體——棧棧是只能從一端訪問(wèn)的線性群體，可以訪問(wèn)的這一端稱棧頂，另一端稱棧底。an┆a2a1入棧出棧棧頂棧底第十五頁(yè)，共三十七頁(yè)，2022年，8月28日1.棧的應(yīng)用舉例——函數(shù)調(diào)用main{}調(diào)fun(參數(shù))結(jié)束fun(參數(shù))返回①②⑤⑦⑧參數(shù)當(dāng)前現(xiàn)場(chǎng)返回地址③⑥入棧當(dāng)前現(xiàn)場(chǎng)返回地址出棧參數(shù)④出棧當(dāng)前現(xiàn)場(chǎng)返回地址第十六頁(yè)，共三十七頁(yè)，2022年，8月28日2.棧的基本狀態(tài)棧空： 棧中沒(méi)有元素棧滿： 棧中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)：棧中有元素，但未達(dá)到棧滿狀態(tài)第十七頁(yè)，共三十七頁(yè)，2022年，8月28日棧頂┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（?？眨﹎axn10棧頂amax┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)18第十八頁(yè)，共三十七頁(yè)，2022年，8月28日3.棧的基本操作初始化入棧出棧清空棧訪問(wèn)棧頂元素檢測(cè)棧的狀態(tài)（滿、空）棧類(lèi)模板和應(yīng)用舉例參見(jiàn)P307～313第十九頁(yè)，共三十七頁(yè)，2022年，8月28日9.2.5特殊的線性群體——隊(duì)列隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體a1a2an-1an……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)a0第二十頁(yè)，共三十七頁(yè)，2022年，8月28日1.隊(duì)列的基本狀態(tài)隊(duì)空： 隊(duì)列中沒(méi)有元素隊(duì)滿： 隊(duì)列中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)：隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)第二十一頁(yè)，共三十七頁(yè)，2022年，8月28日a0a1an-1an……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(一般狀態(tài))元素移動(dòng)方向……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(隊(duì)空狀態(tài))

a0a1

an-1anamax……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(隊(duì)滿狀態(tài))元素移動(dòng)方向第二十二頁(yè)，共三十七頁(yè)，2022年，8月28日2.循環(huán)隊(duì)列在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開(kāi)頭。隊(duì)列類(lèi)模板參見(jiàn)P313～316第二十三頁(yè)，共三十七頁(yè)，2022年，8月28日1234……m-1m-2m-30amam+1am+2a3隊(duì)頭隊(duì)尾a4am-2am-3am-1隊(duì)滿狀態(tài)元素個(gè)數(shù)=m1234……m-1m-2m-30隊(duì)尾隊(duì)頭隊(duì)空狀態(tài)元素個(gè)數(shù)=0隊(duì)尾1234……m-1m-2m-30a0a1a2a3隊(duì)頭一般狀態(tài)24第二十四頁(yè)，共三十七頁(yè)，2022年，8月28日9.3群體數(shù)據(jù)的組織插入排序選擇排序交換排序順序查找折半查找第二十五頁(yè)，共三十七頁(yè)，2022年，8月28日排序（sorting）排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。關(guān)鍵字：

數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素。

在排序過(guò)程中需要完成兩種基本操作：比較兩個(gè)數(shù)的大小調(diào)整元素在序列中的位置第二十六頁(yè)，共三十七頁(yè)，2022年，8月28日內(nèi)部排序與外部排序內(nèi)部排序：

待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過(guò)程。內(nèi)部排序方法:

插入排序 選擇排序 交換排序外部排序：

待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。第二十七頁(yè)，共三十七頁(yè)，2022年，8月28日9.3.1插入排序每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]第二十八頁(yè)，共三十七頁(yè)，2022年，8月28日直接插入排序//9_11.h:直接插入排序函數(shù)模板template<classT>voidInsertionSort(TA[],intn){inti,j;Ttemp;for(i=1;i<n;i++){j=i;temp=A[i];while(j>0&&temp<A[j-1]) //逐個(gè)比較

{A[j]=A[j-1];//將元素逐個(gè)后移，以便找到插入位置

j--;}A[j]=temp; //插入位置找到，立即插入

}}第二十九頁(yè)，共三十七頁(yè)，2022年，8月28日9.3.2選擇排序每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。[541020123]待排序序列：3[41020125]34[1020125]第i次選擇后，將選出的那個(gè)元素與第i個(gè)元素做交換。345[201210]......第三十頁(yè)，共三十七頁(yè)，2022年，8月28日直接選擇排序//9_12.h:直接選擇排序函數(shù)模板template<classT>voidSwap(T&x,T&y) //輔助函數(shù)：交換x和y的值{Ttemp;temp=x;x=y;y=temp;}template<classT>voidSelectionSort(TA[],intn){intsmallIndexinti,j;for(i=0;i<n-1;i++){smallIndex=i; //最小元素之下標(biāo)初值設(shè)為ifor(j=i+1;j<n;j++) //逐個(gè)比較

if(A[j]<A[smallIndex])smallIndex=j; //記錄當(dāng)前找到的最小值的下標(biāo)

Swap(A[i],A[smallIndex]);//將這一趟找到的最小元素與A[I]交換

}}第三十一頁(yè)，共三十七頁(yè)，2022年，8月28日9.3.3交換排序兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。

最簡(jiǎn)單的交換排序方法——起泡排序。對(duì)具有n個(gè)元素的序列按升序進(jìn)行起泡排序的步驟：首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則將兩元素交換。然后比較第二、第三個(gè)元素，依次類(lèi)推，直到第n-1和第n個(gè)元素進(jìn)行了比較和交換。此過(guò)程稱為第一趟起泡排序。經(jīng)過(guò)第一趟，最大的元素便被交換到第n個(gè)位置。對(duì)前n-1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個(gè)位置。如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。對(duì)n個(gè)元素的序列，起泡排序最多需要進(jìn)行n-1趟。第三十二頁(yè)，共三十七頁(yè)，2022年，8月28日起泡排序舉例：對(duì)整數(shù)序列85243按升序排序8524352438243582345823458初始狀態(tài)第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果小的逐漸上升每趟沉下一個(gè)最大的第三十三頁(yè)，共三十七頁(yè)，2022年，8月28日//9_13.h:起泡排序函數(shù)模板template<classT>voidSwap(T&x,T&y){Ttemp;temp=x;x=y;y=temp;}template<classT>voidBubbleSort(TA[],intn){inti,j;intlastExchangeIndex;i=n-1;while(i>0){lastExchangeIndex=0;for(j=0;j<I;j++)if(A[j+1]<A[j]){Swap(A[j],A[j+1]);lastExchangeIndex=j;}i=lastExchangeIndex;}}第三十四頁(yè)，共三十七頁(yè)，2022年，8月28日9.3.4順序查找基本思想是從序列的首元素開(kāi)始，逐個(gè)元素與待查找的關(guān)鍵字進(jìn)行比較，直到找到相等的。若整個(gè)序列中沒(méi)有與待查找關(guān)鍵字相等的元素，就是查找不成功。//9_14.h:順序