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

群體類和群體數(shù)據(jù)的組織第一頁，共三十七頁，編輯于2023年，星期一 類模板用于設(shè)計一個通用類，使這個類的數(shù)據(jù)成員的類型、成員函數(shù)的參數(shù)能夠按照需要進行改變（即參數(shù)化） 聲明類模板的一般形式為：

template<classTtype> classclass_name { }

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

Class_name<type>對象1，…，對象n；

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

Tget(void); voidput(Tx);};第三頁，共三十七頁，編輯于2023年，星期一template<classT> //定義buffer類的構(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;}第四頁，共三十七頁，編輯于2023年，星期一voidmain(void){students={1022,78};buffer<int>i1,i2; //聲明整型對象i1,i2buffer<student>stu1; //聲明結(jié)構(gòu)體對象stu1buffer<double>d; //聲明雙精度對象di1.put(13); //對象i1調(diào)用put執(zhí)行了empty++i2.put(-101); //對象i2調(diào)用put執(zhí)行了empty++cout<<i1.get()<<""<<i2.get()<<endl;stu1.put(s); //對象stu1調(diào)用put執(zhí)行了empty++cout<<"thestudent'sidis"<<stu1.get().id<<endl;cout<<"thestudent'sscoreis"<<stu1.get().score<<endl;cout<<d.get()<<endl; //對象d沒有調(diào)用put去執(zhí)行empty++} //，可能直接exit而不執(zhí)行returna第五頁，共三十七頁，編輯于2023年，星期一程序運行結(jié)果為：

13-101 thestudent’sidis1022 thestudent’sscoreis78 thebufferisempty!第六頁，共三十七頁，編輯于2023年，星期一1.string類對象的定義與初始化形式1：string對象名[("字符串")]

//[]表示可選項 或string對象名[="字符串"]

//[]表示可選項形式2：（生成由n個“字符”組成的字符串）

string對象名(n，‘字符’)2.string類對象的操作

通過string類對象的成員函數(shù)調(diào)用與重載運算符(>>、<<、+等)

對字符串進行賦值、連接、復制、查找、交換等?；拘问綖?/p>

<對象名>.<成員函數(shù)>string類第七頁，共三十七頁，編輯于2023年，星期一//EX9_2.cpp:演示string類的應用#include<iostream.h>#include<string>usingnamespacestd;voidmain(){strings1("Hello"),s2,s3,s4; //定義string對象

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

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

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

cout<<"s1="<<s1.data()<<endl;for(inti=0;i<5;i++)b[i]=s2[i]; //此語句也可表示為:b[i]=s2.at(i);第八頁，共三十七頁，編輯于2023年，星期一

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

s4=s2+""+s1;//用"+"進行字符串的連接(重載運算符+)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個開始的5個字符與 //s4的第7個開始的5個字符進行比較

if(f==0)cout<<"s3與s4比較的部分相等"<<"\n";else cout<<"s3與s4比較的部分不相等"<<"\n";//取子字符串操作第九頁，共三十七頁，編輯于2023年，星期一

stringsz=s2.substr(5,5);//取s2的第5個開始的5個字符

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];//定義字符型指針并動態(tài)分配空間

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

cout<<s2.data()<<endl;}第十頁，共三十七頁，編輯于2023年，星期一程序運行結(jié)果為:

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

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

a0a1

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

數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標識（識別）一個數(shù)據(jù)元素。

在排序過程中需要完成兩種基本操作：比較兩個數(shù)的大小調(diào)整元素在序列中的位置第二十六頁，共三十七頁，編輯于2023年，星期一內(nèi)部排序與外部排序內(nèi)部排序：

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

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

待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進行訪問的排序過程。第二十七頁，共三十七頁，編輯于2023年，星期一9.3.1插入排序每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]第二十八頁，共三十七頁，編輯于2023年，星期一直接插入排序//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]) //逐個比較

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

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

}}第二十九頁，共三十七頁，編輯于2023年，星期一9.3.2選擇排序每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。[541020123]待排序序列：3[41020125]34[1020125]第i次選擇后，將選出的那個元素與第i個元素做交換。345[201210]......第三十頁，共三十七頁，編輯于2023年，星期一直接選擇排序//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; //最小元素之下標初值設(shè)為ifor(j=i+1;j<n;j++) //逐個比較

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

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

}}第三十一頁，共三十七頁，編輯于2023年，星期一9.3.3交換排序兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。

最簡單的交換排序方法——起泡排序。對具有n個元素的序列按升序進行起泡排序的步驟：首先將第一個元素與第二個元素進行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個位置。對前n-1個元素進行第二趟起泡排序，將其中最大元素交換到第n-1個位置。如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對n個元素的序列，起泡排序最多需要進行n-1趟。第三十二頁，共三十七頁，編輯于2023年，星期一起泡排序舉例：對整數(shù)序列85243按升序排序8524352438243582345823458初始狀態(tài)第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果小的逐漸上升每趟沉下一個最大的第三十三頁，共三十七頁，編輯于2023年，星期一//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;}}第三十四頁，共三十七頁，編輯于2023年，星期一9.3.4順序查找基本思想是從序列的首元素開始，逐個元素與待查找的關(guān)鍵字進行比較，直到找到相等的。若整個序列中沒有與待查找關(guān)鍵字相等的元素，就是查找不成功。//9_14.h:順