C++程序設(shè)計(jì)第6章 模板與數(shù)據(jù)結(jié)構(gòu)

第六章模板與數(shù)據(jù)結(jié)構(gòu)模板——建立與數(shù)據(jù)類型無(wú)關(guān)的通用算法利用模板建立表，描述排序與查找的算法。voidmain(){

int

a,b,c;doublex,y,z;chars1[20],s2[20],s3[20];……//讀入數(shù)據(jù)

cout<<max(a,b,c)<<endl;

cout<<max(x,y,z)<<endl;

cout<<max(s1,s2,s3)<<endl;}如何完成此要求？6.1模板

問(wèn)題：重載若有如下需求int

max(int,int,int){}doublemax(double,double,double){}char*max(char*,char*,char*){}模板通用參數(shù)化程序設(shè)計(jì)：

通用的代碼就必須不受數(shù)據(jù)類型的限制，可以把數(shù)據(jù)類型改為一個(gè)設(shè)計(jì)參數(shù)。這種類型的程序設(shè)計(jì)稱為參數(shù)化程序設(shè)計(jì)。

模板：包括函數(shù)模板和類模板。6.1.1函數(shù)模板及應(yīng)用函數(shù)模板：創(chuàng)建一個(gè)通用函數(shù)，支持多種不同類型形參。函數(shù)模板定義：template<模板參數(shù)表>返回類型函數(shù)名(形式參數(shù)表){……；//函數(shù)體}注：尖括號(hào)中不能為空，參數(shù)可以有多個(gè)，用逗號(hào)分開(kāi)。模板

——數(shù)據(jù)類型參數(shù)化，實(shí)現(xiàn)通用性int

max(int

a,int

b,intc);doublemax(double

x,doulbe

y,doublez):char*max(char*s1,char*s2,char*s3);

template<typenameT>T

max(Ta,Tb,Tc){}

重載函數(shù)函數(shù)模板template<typename

T>Tmax(Ta[],intn){}

對(duì)數(shù)組求最大值的函數(shù)模板：模板的使用——模板實(shí)例化

(templateinstantiation)inta[5];doubled[10];strings[20];…;//數(shù)據(jù)輸入inti=max(a,5);intj=max(d,10);intk=max(s,20);

顯式調(diào)用：

i=max<int>(a,5);j=max<double>(d,10);k=max<string>(s,20);【例6.1】用函數(shù)模板求數(shù)組元素中最大值template<typename

T>Tmax(const

T*array,intsize){

inti;

Tmax=array[0];for(i=1;i<size;++i)

if(array[i]>max)max=array[i];

returnmax;

}類型參數(shù)T在程序運(yùn)行中會(huì)被各種基本類型或用戶定義類型置換。模板參數(shù)表的使用與函數(shù)形式參數(shù)表的使用相同，都是位置對(duì)應(yīng)。類型和值的置換過(guò)程稱為模板實(shí)例化。形參size

表示array數(shù)組的長(zhǎng)度。intia[5]={10,7,14,3,25};doubleda[6]={10.2,7.1,14.5,3.2,25.6,16.8};stringsa[5]={"上海","北京","沈陽(yáng)","廣州","武漢"};intmain(){

int

i=max(ia,5);//隱式顯示

cout<<"整數(shù)最大值為："<<i<<endl;

doubled=max(da,6);//隱式顯示

cout<<"實(shí)數(shù)最大值為："<<d<<endl;strings=max(sa,5);//隱式顯示

cout<<"字典排序最大為："<<s<<endl;

return0;}也可以顯式指定：i=max<int>(ia,5);d=max<double>(da,6);在main()函數(shù)中，由調(diào)用函數(shù)模板而生成的函數(shù)，稱為模板函數(shù)。這兩個(gè)概念須分清楚。函數(shù)模板與模板函數(shù)：多維數(shù)組作為函數(shù)參數(shù)的方法有三種：第一種是函數(shù)的形參定義為多維數(shù)組，調(diào)用函數(shù)時(shí)的實(shí)參為多維數(shù)組名。

第二種方法是把多維數(shù)組作為一維數(shù)組來(lái)處理，函數(shù)的形參定義為一維數(shù)組或一級(jí)指針變量，另一個(gè)參數(shù)指明數(shù)組的元素個(gè)數(shù)；對(duì)應(yīng)的實(shí)參給出數(shù)組的起始地址。

第三種方法是用指向一維數(shù)組的指針變量作為函數(shù)的參數(shù)。floatave1(floatp[][4],intn){floatsum=0;

inti,j;for(i=0;i<n;i++)for(j=0;j<4;j++)sum+=p[i][j];returnsum/(n*4);}floatx;x=ave1(score,3)第一個(gè)形參是二維數(shù)組，第二個(gè)形參為二維數(shù)組的行數(shù)。對(duì)應(yīng)的第一個(gè)實(shí)參為二維數(shù)組名score。floatscore[3][4]={{65,67,70,60},{80,87,90,81},{90,99,100,98}};例1：floatave2(float*p,intn){floatsum=0;

inti;for(i=0;i<n;i++)sum+=*p++;returnsum/n;}floatscore[3][4]={{65,67,70,60},{80,87,90,81},{90,99,100,98}};floatx;x=ave2(*score,12)第一個(gè)參數(shù)是一級(jí)指針，它把二維數(shù)組作為一維數(shù)組來(lái)處理，第二個(gè)參數(shù)是二維數(shù)組中的元素個(gè)數(shù)。其對(duì)應(yīng)的第一個(gè)實(shí)參應(yīng)是第0行第0列元素的地址，即*score。例2：floatave3(float(*p)[4],intn){floatsum=0;

inti,j;for(i=0;i<n;i++){for(j=0;j<4;j++)sum+=(*p)[j]; p++;}returnsum/(n*4);}floatscore[3][4]={{65,67,70,60},{80,87,90,81},{90,99,100,98}};floatx;x=ave3(&score[0],3)第一個(gè)形參為指向一維數(shù)組的指針變量，第二個(gè)形參為二維數(shù)組的行數(shù)，對(duì)應(yīng)的第一個(gè)實(shí)參為指向第0行的列地址，即&score[0]。例3：請(qǐng)注意：與函數(shù)聲明不同，函數(shù)模板的聲明必須含變量名。因?yàn)閮烧呔幾g過(guò)程不一樣，函數(shù)模板必須先轉(zhuǎn)換為模板函數(shù)。template<typenameT1,typenameT2>voidinverse(T1*mat1,T2*mat2,int

a,int

b);template<typenameT1,typenameT2>voidmulti(T1*mat1,T2*mat2,T2*result,int

a,

int

b,int

c);template<typename

T>void

output(T*mat,char*s,int

a,int

b);注意：mat2和result屬同一類型，均為由具有相同元素?cái)?shù)量的一維數(shù)組所組成的二維數(shù)組。

記住數(shù)組最高維是不檢查邊界的。函數(shù)模板的聲明：【例6.2】矩陣運(yùn)算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參數(shù)傳遞。解決例5.5程序的通用性問(wèn)題。int

main(){

intmiddle[6][3],result[6][4];

intmatrix1[3][6]={8,10,12,23,1,3,5,7,9,2,4,6,34,45,56,2,4,6};

intmatrix2[3][4]={3,2,1,0,-1,-2,9,8,7,6,5,4};

char*s1="result";

char*s2="middle";inverse(matrix1,middle,6,3);

//顯式：inverse<int[6],int[3]>(matrix1,middle,6,3);multi(middle,matrix2,result,6,3,4);

//顯式：multi<int[3],int[4]>(middle,matrix2,result,6,3,4);output(matrix1,"matrix1",3,6);output(middle,s2,6,3);output(matrix2,"matrix2",3,4);output(result,s1,6,4);return0;}template<typenameT1,typenameT2>voidinverse(T1*mat1,T2*mat2,inta,intb){

int

i,j;

for(i=0;i<b;i++)

for(j=0;j<a;j++)

mat2[j][i]=mat1[i][j];

return;}inverse(matrix1,middle,6,3);810122313853457924610745344556246129562322144366matrix1[3][6]middle[6][3]template<typenameT1,typenameT2>voidmulti(T1*mat1,T2*mat2,T2*result,int

a,intb,

int

c){

int

i,j,k;

for(i=0;i<a;i++)

for(j=0;j<c;j++){

result[i][j]=0;

for(k=0;k<b;k++)

result[i][j]+=mat1[i][k]*mat2[k][j];}

return;}8534107451295623221443663210-1-2987654*25721022317627629823634237329654512418574845308772middle[6][3]matrix2[3][4]result[6][4]multi(middle,matrix2,result,6,3,4);template<typenameT>void

output(T*mat,char*s,

int

a,intb){

int

i,j;

cout<<s<<endl;

for(i=0;i<a;i++){

for(j=0;j<b;j++)

cout<<setw(4)<<mat[i][j]<<"";

cout<<endl;}

return;}output(matrix1,"matrix1",3,6);output(middle,s2,6,3);output(matrix2,"matrix2",3,4);output(result,s1,6,4);6.1.2類模板與線性表類模板定義：template<模板參數(shù)表>

class類名{……

//類體};

template<模板參數(shù)表>返回類型類名<模板參數(shù)名表>::成員函數(shù)名1(形參表){……；//成員函數(shù)定義體}……template<模板參數(shù)表>返回類型類名<模板參數(shù)名表>::成員函數(shù)名n(形參表){……；//成員函數(shù)n定義體}

模板參數(shù)有兩種：模板類型參數(shù)和模板非類型參數(shù)。6.1.2類模板與線性表類模板含義——成員的類型參數(shù)化數(shù)組類classArray{

inta[100];

intsize;//數(shù)組長(zhǎng)度public:Array(){size=100;}voidprint();......};

數(shù)組類模板template<typename

T,int

n>Tnn模板類型參數(shù)T模板非類型參數(shù)n,常量,不能修改

模板應(yīng)用（實(shí)例化）：

Array<int,100>list1;list1.print();Array<double,20>list2;list2.print();類模板中的成員函數(shù)均為函數(shù)模板。即：template<typename

T,int

i>voidArray<T,i>::print(){

for(inti=0;i<size;i++)cout<<a[i]<<‘,’;}#include<iostream>//類模板應(yīng)用舉例#include<cstdlib>usingnamespacestd;structStudent{//結(jié)構(gòu)體Student

intid;//學(xué)號(hào)

floatgpa;//平均分};template<classT>//類模板，實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取classStore{Titem;//存放任意類型數(shù)據(jù)

int

haveValue;//標(biāo)記item是否已被存入內(nèi)容

public:Store();//默認(rèn)形式的構(gòu)造函數(shù)

TGetElem();//提取數(shù)據(jù)函數(shù)

voidPutElem(Tx);//存入數(shù)據(jù)函數(shù)};template<classT>Store<T>::Store():haveValue(0){}//構(gòu)造函數(shù)，haveValue初值賦0template<classT>TStore<T>::GetElem(){//提取數(shù)據(jù)函數(shù)

if(haveValue==0){cout<<"Noitempresent!"<<endl; exit(1);//使程序完全退出，返回操作系統(tǒng)

}returnitem;//返回item中存放的數(shù)據(jù)}template<classT>voidStore<T>::PutElem(Tx){//存入數(shù)據(jù)函數(shù)

haveValue++;//將此置為ture，表示item中已存入數(shù)值

item=x;//將x值存入item }列表方式intmain(){Studentg={1000,23};//聲明Student類型結(jié)構(gòu)體變量的同時(shí)賦以處置

Store<int>S1,S2;//聲明兩個(gè)Store<int>類對(duì)象，其中數(shù)據(jù)成員item為int類型

Store<Student>S3;//聲明Store<Student

>類對(duì)象S3，其中數(shù)據(jù)成員item為Student類型

Store<double>D;//聲明Store<double

>類對(duì)象D，其中數(shù)據(jù)成員item為double類型

S1.PutElem(3);//向?qū)ο骃1中存入數(shù)據(jù)(初始化對(duì)象S1)S2.PutElem(-7);//向?qū)ο骃2中存入數(shù)據(jù)(初始化對(duì)象S2)

cout<<S1.GetElem()<<""<<S2.GetElem()<<endl;//S1和S2的數(shù)據(jù)成員

S3.PutElem(g);//向?qū)ο骃3中存入數(shù)據(jù)(初始化對(duì)象Student)

cout<<S3.GetElem().id<<endl;//輸出對(duì)象S3的數(shù)據(jù)成員

cout<<"RetrievingobjectD";

cout<<D.GetElem()<<endl;//輸出對(duì)象D的數(shù)據(jù)成員

//由于D未初始化，在執(zhí)行函數(shù)D.GetElem()過(guò)程中導(dǎo)致程序終止

return0;}

線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個(gè)元素外，其他元素有且僅有一個(gè)直接前驅(qū)，第一個(gè)元素沒(méi)有前驅(qū)；除最后一個(gè)元素外，其他元素有且僅有一個(gè)直接后繼，最后一個(gè)元素?zé)o后繼。這樣的特性稱為線性關(guān)系。所議稱數(shù)組元素在一個(gè)線性表中。線性表實(shí)際包括順序表（數(shù)組）和鏈表。對(duì)順序表的典型操作包括：計(jì)算表長(zhǎng)度，尋找變量或?qū)ο髕（其類型與表元素相同）在表中的位置（下標(biāo)值），判斷x是否在表中，刪除x，將x插入列表中第i個(gè)位置，尋找x的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿（表滿不能再插入數(shù)據(jù)，否則會(huì)溢出，產(chǎn)生不可預(yù)知的錯(cuò)誤），取第i個(gè)元素的值。這些操作與數(shù)組封裝在一起可以定義一個(gè)類，考慮到數(shù)組元素的類型可以各不相同，所以定義為類模板。線性表：6.1.2類模板與線性表線性表的概念及存儲(chǔ)形式：封裝一個(gè)順序表類（數(shù)組類）模板順序表的常用操作即特點(diǎn)：插入元素刪除元素查找元素排序……順序表（數(shù)組）、鏈表由編譯器編譯時(shí)分配內(nèi)存的數(shù)組稱為靜態(tài)數(shù)組，數(shù)組的長(zhǎng)度是不可改變的。如果定義了30個(gè)元素的數(shù)組，后來(lái)需要40個(gè)元素，是不可能續(xù)上10個(gè)的，必然產(chǎn)生溢出。因系統(tǒng)不檢查數(shù)組邊界，進(jìn)而產(chǎn)生不可預(yù)知的運(yùn)行時(shí)錯(cuò)誤，所以一般采用“大開(kāi)小用”的方法，即數(shù)組定義的較大，而實(shí)用較小。為防止不可避免的溢出，應(yīng)在添加新數(shù)據(jù)時(shí)判斷表是否滿。靜態(tài)數(shù)組：1431341096587241621892771185112110131234i圖a下標(biāo)1431341096587241621897118511211013圖b下標(biāo)圖6.1從表中刪除一個(gè)數(shù)據(jù)當(dāng)需要在順序表中刪除一個(gè)元素時(shí)，必須把它后面的元素的數(shù)據(jù)全部順序前移一個(gè)位置，否則表中前驅(qū)后繼關(guān)系被破壞。圖6.1表中有11個(gè)數(shù)據(jù)。刪去第i個(gè)元素的數(shù)據(jù)，就是把第i+1個(gè)元素拷入第i個(gè)元素，把第i+2個(gè)元素拷入第i+1個(gè)元素,依此類推，直到最后一個(gè)元素（下標(biāo)為10），現(xiàn)在表長(zhǎng)度為10。刪除順序表元素：1431341096587241621892771185112110135432i圖a下標(biāo)1273134109658724162189711511181214x013圖b下標(biāo)圖6.2向表中插入一個(gè)數(shù)據(jù)當(dāng)需要在順序表的指定位置i插入一個(gè)數(shù)據(jù)x時(shí)，必須為它騰出這個(gè)位置，把從該位置開(kāi)始向后的所有元素?cái)?shù)據(jù)，后移一個(gè)位置，最后才插入。后移時(shí)從最后一個(gè)元素開(kāi)始，參見(jiàn)圖6.2。現(xiàn)在長(zhǎng)度為12，這樣的移動(dòng)也是不可少的，否則新插入的數(shù)據(jù)x會(huì)沖掉原來(lái)的數(shù)據(jù)，或先移的數(shù)據(jù)沖掉未移的數(shù)據(jù)。添加順序表元素：如：

voidGettime()const;

//注意const的位置在函數(shù)名和括號(hào)之后注：

聲明函數(shù)和定義函數(shù)時(shí)要有const關(guān)鍵字，調(diào)用時(shí)不必加const。常成員函數(shù)可以引用const數(shù)據(jù)成員，也可以引用非const的數(shù)據(jù)成員。const數(shù)據(jù)成員可以被const成員函數(shù)引用，也可以被非const的成員函數(shù)引用。常成員函數(shù)一般的成員函數(shù)可以引用本類中的非const數(shù)據(jù)成員，也可以修改它們。如果將成員函數(shù)聲明為常成員函數(shù)，則只能引用本類中的數(shù)據(jù)成員，而不能修改它們。若一個(gè)類中，有些數(shù)據(jù)成員的值允許改變，有些數(shù)據(jù)成員的值不允許改變，可以將一部分?jǐn)?shù)據(jù)成員聲明為const，保證其值不被改變，可以用非const的成員函數(shù)引用這些數(shù)據(jù)成員的值，并修改非const數(shù)據(jù)成員的值。(2)若要求所有的數(shù)據(jù)成員的值都不允許改變，則可以將所有的數(shù)據(jù)成員聲明為const，或?qū)?duì)象聲明為const(常對(duì)象)，然后用const成員函數(shù)引用數(shù)據(jù)成員。(3)若已定義了一個(gè)常對(duì)象，則只能調(diào)用其中的const成員函數(shù)，而不能調(diào)用非const成員函數(shù)。常成員函數(shù)不能調(diào)用另一個(gè)非const成員函數(shù)。常成員函數(shù)的使用：【例6.3】順序表類模板template<typename

T,int

size>classseqlist{

T

slist[size];//存放順序表的數(shù)組

int

Maxsize;//最大可容納項(xiàng)數(shù)

intlast;//已存表項(xiàng)的最后位置public:

seqlist(){last=-1;Maxsize=size;}//初始化為空表

intLength()const{return

last+1;}//計(jì)算表長(zhǎng)度

int

Find(T&x)const;//尋找x位置（下標(biāo)）const成員函數(shù)，該函數(shù)保證只讀

bool

IsIn(T&x);//判斷x是否在表中，形參為引用

bool

Remove(T&x);//刪除x

bool

Insert(T&x,inti);//在第i個(gè)位置插入x

int

Next(T&x);//尋找x的后繼位置

int

Prior(T&x);//尋找x的前驅(qū)位置

bool

IsEmpty(){returnlast==-1;}//判斷表是否空

bool

IsFull(){returnlast==Maxsize-1;}//判斷表是否滿

TGet(int

i){

//取第i個(gè)元素之值，帶有下標(biāo)檢查功能

returni<0||i>last?NULL:slist[i];

}

T&operator[](int

i);//重載下標(biāo)運(yùn)算符[]};

template<typename

T,int

size>int

seqlist<T,size>::Find(T&x)const{//const表示該函數(shù)的this指針為const，即被訪問(wèn)對(duì)象的數(shù)據(jù)不能被修改。如被修改編譯器會(huì)警告，防止編程時(shí)失誤。

inti=0;

while(i<=last&&slist[i]!=x)i++;//順序查找是否有x

if(i>last)return-1;//未找到，返回-1elsereturni;//找到，返回下標(biāo)}template<typename

T,intsize>bool

seqlist<T,size>::IsIn(T&x){

inti=0;

boolfound=0;

while(i<=last&&!found)//換了一種方法來(lái)查找

if(slist[i]!=x)i++;

elsefound=1;//找到

returnfound;}template<typename

T,intsize>bool

seqlist<T,size>::Insert(T&x,inti){//在第i個(gè)位置插入x

intj;if(i<0||i>last+1||last==Maxsize-1)returnfalse;//插入位置不合理，不能插入（健壯性）

else{last++;

for(j=last;j>i;j--)slist[j]=slist[j-1];

//從表最后位置向前依次移動(dòng)，空出指定位置來(lái)

slist[i]=x;returntrue;}}超出表項(xiàng)范圍末尾template<typename

T,intsize>

bool

seqlist<T,size>::Remove(T&x){

//刪除x

inti=Find(x),j;//先去找x在哪個(gè)位置

if(i>=0){last--;

for(j=i;j<=last;j++)

slist[j]=slist[j+1];//依次前移，保證表連續(xù)

returntrue;}returnfalse;//表中不存在x}template<typename

T,intsize>int

seqlist<T,size>::Next(T&x){//尋找x的后繼位置

inti=Find(x);

if(i>=0&&i<last)returni+1;//x后繼位置

elsereturn-1;//x不在表中，或在表末尾}template<typename

T,intsize>int

seqlist<T,size>::Prior(T&x){//尋找x的前驅(qū)位置

inti=Find(x);

if(i>0&&i<=last)returni-1;//x前驅(qū)的位置

elsereturn-1;}voidmain(){

seqlist<int,100>s;

//順序表對(duì)象s的元素為整型

inti,j,k,a[10]={2,3,5,7,11,13,17,19,23,29};

for(j=0;j<10;j++)

//把素?cái)?shù)寫(xiě)入

if(!s.Insert(a[j],j)){

cout<<"表太大放不下了!"<<endl;

break;

}j=s.Length();

for(i=0;i<j;i++)cout<<s.Get(i)<<'';

cout<<endl;

//打印出s.slist[]素?cái)?shù)表

k=7;//因函數(shù)IsIn(k)形參為引用，所以實(shí)參不可用整數(shù)常量7

if(s.IsIn(k))cout<<"素?cái)?shù)7在順序表中"<<endl;

else

cout<<"素?cái)?shù)7不在順序表中"<<endl;k=17;

if(s.Remove(k))cout<<"刪除素?cái)?shù)17"<<endl;//刪除素?cái)?shù)17

else

cout<<"找不到素?cái)?shù)17，無(wú)法刪除";j=s.Length();

for(i=0;i<j;i++)cout<<s.Get(i)<<'';//打印剩下的素?cái)?shù)

cout<<endl;if(s.Insert(k,j-1)){//把素?cái)?shù)17裝(插入到j(luò)-1位置)回去,成功則打印

j=s.Length();for(i=0;i<j;i++)cout<<s.Get(i)<<'';

cout<<endl;}

cout<<"打印17后一個(gè)素?cái)?shù)："<<s.Get(s.Next(k))<<endl;

cout<<"打印17前一個(gè)素?cái)?shù)："<<s.Get(s.Prior(k))<<endl;

cout<<“素?cái)?shù)17在表中位置(下標(biāo))為

"<<s.Find(k)<<endl;

if(s.IsEmpty(

))cout<<"表是空的"<<endl;elsecout<<"表不空"<<endl;if(s.IsFull())

cout<<"表是滿的"<<endl;elsecout<<"表不滿"<<endl;if(s.IsIn(k))

cout<<"素?cái)?shù)17在表中"<<endl;}輸出：

2357111317192329

素?cái)?shù)7在順序表中刪除素?cái)?shù)17235711131923292357111319231729

打印17后一個(gè)素?cái)?shù)：29

打印17前一個(gè)素?cái)?shù)：23

素?cái)?shù)17在表中位置(下標(biāo))為：8

表不空表不滿素?cái)?shù)17在表中６.2排序與查找人們經(jīng)常需要在一個(gè)數(shù)據(jù)集合中搜尋滿足特定條件的數(shù)據(jù)元素。

為了提高查找效率，應(yīng)當(dāng)先對(duì)集合中的數(shù)據(jù)進(jìn)行排序查找:從一個(gè)數(shù)據(jù)集合中找出特定元素的過(guò)程。數(shù)據(jù)集合中的元素一般是同類型的對(duì)象。

特定元素:

某個(gè)域具有特定的值。用以區(qū)分各數(shù)據(jù)元素的域稱為關(guān)鍵域或關(guān)鍵字。順序查找:依次地考察數(shù)據(jù)集合中的每個(gè)元素。順序查找的執(zhí)行時(shí)間函數(shù)的階為n(線性階)。

若數(shù)據(jù)集合中的元素是有序的，并存貯在一維數(shù)組中，就可以使用效率較高的折半查找方法。6.2.1常用查找方法順序查找：從第一個(gè)元素開(kāi)始，順序查找直到找到或查到最后一個(gè)元素為止。查找是按關(guān)鍵字（keyword）進(jìn)行。可以唯一地把資料區(qū)分出來(lái)的數(shù)據(jù)被稱為主關(guān)鍵字。如學(xué)生的資料(結(jié)構(gòu)體變量):structstudent{int

id;//學(xué)號(hào)charname[20];//姓名charsex;//性別intage;//年齡charaddress[60];//家庭地址floateng,phy,math,electron;//英語(yǔ),物理,數(shù)學(xué)和電子學(xué)成績(jī)};學(xué)號(hào)可作為主關(guān)鍵字。

如果關(guān)鍵字小的排在前面，我們稱為升序排列，反之為降序排列。這時(shí)可以采用對(duì)半查找（binarysearch）。

8917131120719212331262925373923查找midlowhigh2021292623313739lowmidhigh202123lowmidhigh23lowmidhigh查找成功例有序數(shù)據(jù)——方法之一：對(duì)半查找定義兩個(gè)指針low和high指向首尾兩元素，取mid=(low+high)/2，如mid指向元素是所查找的，則結(jié)束。如果該元素關(guān)鍵字大了，則取low=mid+1，high不變，繼續(xù)查找；如果該元素關(guān)鍵字小了，則取high=mid-1，low不變，繼續(xù)查找。如果查到low>high仍未找到，則失敗，停止。low25781113179192023212629313710查找39midhigh25781113179lowmidhigh1113179lowmidhigh9lowmidhigh查找失敗例

while（區(qū)間低端值不大于高端值）{

計(jì)算區(qū)間的中點(diǎn)下標(biāo)值；

if（中點(diǎn)處的元素值等于指定值）

{返回區(qū)間中點(diǎn)的下標(biāo)

}；

else{確定下一步考察的區(qū)間}；

}

對(duì)半查找算法:【例6.4】對(duì)半查找遞歸算法，作為有序表模板類成員函數(shù)。遞歸方法易讀易懂，但效率低。（自學(xué)）【例6.5】對(duì)半查找迭代算法。該例中迭代算法的可讀性也不差，效率要高于遞歸。*本例中出現(xiàn)的成員函數(shù)Binarysearch(T&x)const

，稱為

const成員函數(shù)，該函數(shù)保證只讀。相應(yīng)節(jié)點(diǎn)對(duì)象重載的比較運(yùn)算符也必須是const。

const函數(shù)的this指針?biāo)笇?duì)象為常量，即它不能修改對(duì)象的數(shù)據(jù)成員，而且在函數(shù)體內(nèi)只能調(diào)用const成員函數(shù)，不能調(diào)用其他成員函數(shù)。如果編程時(shí)不慎修改對(duì)象的數(shù)據(jù)成員，編譯器會(huì)報(bào)錯(cuò)?！纠?.5】對(duì)半查找迭代算法。template<typename

T,intsize>int

Orderedlist<T,size>::BinarySearch(

constT&x)const{

inthigh=last,low=0,mid;

//last當(dāng)前有序表最大下標(biāo)

while(low<=high){mid=(low+high)/2;

if(x<slist[mid])high=mid-1;//左縮查找區(qū)間

elseif(slist[mid]<x)low=mid+1;//右縮查找區(qū)間

else

returnmid;}

if(slist[mid]!=x)mid=-1;

returnmid;}

classElement{

intkey;

//其他域省略public:

booloperator<(Elementele)const{returnkey<ele.key;}

booloperator!=(Elementele)const{returnkey!=ele.key;}voidputkey(intk){key=k;}//要尋找的元素

voidshow(){cout<<key<<'\t';}}//重載比較運(yùn)算符，元素比較，實(shí)際是元素關(guān)鍵域的比較intmain(){constinth=19;

int

i,k=47;

Orderedlist<Element,100>ordlist;

int

a[h]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};//升序

Elementn[h],elem;

for(i=0;i<h;i++)n[i].putkey(a[i]);

for(i=0;i<h;i++)ordlist.Insert(n[i],i);//在線性表尾插入，建立升序順序表

ordlist.print();

elem.putkey(k);i=ordlist.Binarysearch(elem);

cout<<"整數(shù)"<<k<<"在表中位置（下標(biāo)）："<<i<<endl;k=33;

elem.putkey(k);i=ordlist.Binarysearch(elem);

cout<<"整數(shù)"<<k<<"在表中位置（下標(biāo)）："<<i<<endl;return0;}6.6.2常用的排序法排序功能:

將數(shù)據(jù)元素的無(wú)序序列調(diào)整為一個(gè)有序序列。數(shù)據(jù)元素中一般有多個(gè)數(shù)據(jù)項(xiàng)，排序可選擇其中一個(gè)可排序的數(shù)據(jù)項(xiàng)（可進(jìn)行比較運(yùn)算）作為依據(jù)，稱為排序關(guān)鍵字。為了能使用高效率的折半查找算法，通常希望數(shù)據(jù)序列按關(guān)鍵域有序排列。排序：將數(shù)據(jù)元素的任意序列重新排列成按關(guān)鍵域有序的序列。和查找相比，排序相對(duì)費(fèi)時(shí)。是否要對(duì)數(shù)組排序，取決于對(duì)數(shù)組的訪問(wèn)次數(shù)。從小到大排序稱升序，反之為降序。最常見(jiàn)的是插入排序、選擇排序和交換排序。

…

181024355860

24｜

8351601058

824｜

35

1601058

82435｜

1601058

182435｜

6010

581．插入排序(InsertSorting)設(shè)整數(shù)數(shù)組為a：248351601058排序目標(biāo)是使數(shù)組元素按升序排列。對(duì)具有n個(gè)元素的數(shù)組插入排序需要處理(n－1)遍。排序過(guò)程：

第i遍處理時(shí)，按冒泡方式將a[i]插入已排序部分。直接插入排序:【例6.6】升序直接插入排序算法template<typename

T,intsize>void

Orderedlist<T,size>::InsertSort(){ Ttemp;

int

i,j;

for(i=1;i<=last;i++){

//將下標(biāo)為1~last的元素逐個(gè)插入到已排序序列中適當(dāng)位置

temp=slist[i]; j=i;

while(j>0&&temp<slist[j-1]){

slist[j]=slist[j-1]; j--;

//查找與移動(dòng)同時(shí)做

}

slist[j]=temp;

//插入位置已找到，立即插入

}}classElement{ stringkey; //其他域省略public:

booloperator<(Elementele){returnkey<ele.key;}

void

putkey(string

k){key=k;}

voidshow(){cout<<key<<'\t';}};intmain(){

constinth=10;Elementn[h];

int

i; Orderedlist<Element,100>ordlist; stringmslist[h]={"cat","book","car","zoo","fish","cab","dog","cap","fox","can"};

for(i=0;i<h;i++)n[i].putkey(mslist[i]);

for(i=0;i<h;i++)ordlist.Insert(n[i],i);//建立順序表

cout<<"未排序表："<<endl;

ordlist.print();

ordlist.InsertSort();

cout<<"已排序表："<<endl;

ordlist.print();

return0;}【例6.7】升序?qū)Π氩迦肱判蛩惴ㄓ脤?duì)半查找思想取代順序查找（快于插入排序）template<typename

T,intsize>voidOrderedlist<T,size>::BinaryInsertSort(){Ttemp;

int

low,high,mid,i,j;

for(i=1;i<=last;i++){temp=slist[i];low=0;high=i-1;while(low<=high){

//請(qǐng)注意與對(duì)半查找的不同之處

mid=(low+high)/2;

if(temp<slist[mid])high=mid-1; elselow=mid+1;}

for(j=i-1;j>=low;j--)slist[j+1]=slist[j];

slist[low]=temp;}}插入排序：在每次循環(huán)中設(shè)法把一個(gè)元素插入到已經(jīng)排序的部分序列里的合適位置，是得到的序列任然是有序的。當(dāng)被處理的最后一個(gè)元素也插入到有序序列后，整個(gè)排序工作完成。優(yōu)點(diǎn)：利用一個(gè)一個(gè)元素的插入比較，將元素放入適當(dāng)?shù)奈恢檬且环N簡(jiǎn)單的排序方式。缺點(diǎn)：由于每插入一個(gè)元素都必須與之前已排序好的元素比較，需要花費(fèi)較長(zhǎng)時(shí)間。

2.交換排序設(shè)數(shù)組有n個(gè)元素，目標(biāo)是使數(shù)組元素按升序排列。在最壞情況下，冒泡排序方法也要對(duì)數(shù)組處理(n-1)遍。

冒泡排序交換排序的基本思想是按關(guān)鍵字兩兩排序?qū)ο?，如果發(fā)生逆序則交換之，直到所有的對(duì)象都排好序?yàn)橹?。將相鄰的兩個(gè)數(shù)據(jù)加以比較，若下面一個(gè)小于上面一個(gè)，則兩數(shù)交換，若下面一個(gè)大于上面一個(gè)，則兩個(gè)位置不變。繼續(xù)將上面一個(gè)小的值與它上面的值進(jìn)行比較，重復(fù)此操作，直到比較到最上面一個(gè)值。（完成一次排序）第1遍冒泡處理過(guò)程ia[i]045451151527070334344602852860

ia[i]045454511515152707070334342846028345286060第1遍冒泡處理過(guò)程ia[i]045454545115151515270707028334342870460283434528606060第1遍冒泡處理過(guò)程ia[i]045454545451151515151527070702828334342870704602834343452860606060第1遍冒泡處理過(guò)程ia[i]第一遍處理后045454545451511515151515452707070282828334342870707046028343434345286060606060第1遍冒泡處理過(guò)程對(duì)數(shù)組a進(jìn)行各遍冒泡處理的結(jié)果第1遍第2遍第3遍第4遍ia[i]處理后處理后處理后處理后045151515151154528282827028453434334703445454603470606052860607070第1遍冒泡：a[0]~a[5]的最小元素上冒到a[0]；第2遍冒泡：a[1]~a[5]的最小元素上冒到a[1]；第i+1遍冒泡：a[i]~a[5]的最小元素上冒到a[i]；for(i=0;i<n;i++){

for(k=n;k>i;k--)//第i次冒泡

if(slist[k-1]>slist[k]){

交換兩者；

}}改進(jìn)算法——過(guò)程當(dāng)中排好序，則提前終止冒泡noswap=true;noswap=false;//發(fā)生交換if(noswap)break;//終止i循環(huán)【例6.8】冒泡排序算法template<typename

T,int

size>voidOrderedlist<T,size>::BubbleSort(){

bool

noswap;

int

i,j;Ttemp;

for(i=0;i<last;i++){

//最多做n-1趟

noswap=true; //未交換標(biāo)志為真

for(j=last;j>i;j--){

//從下往上冒泡

if(slist[j]<slist[j-1]){ temp=slist[j];

slist[j]=slist[j-1]; slist[j-1]=temp;

noswap=false;}}

if(noswap)break;

//本趟無(wú)交換，則終止算法。

}}【例6.8】冒泡排序算法學(xué)生類為數(shù)組元素

class

student{

intid;//學(xué)號(hào)

stringname;//姓名

charsex;//性別

intage;//年齡

stringaddress;//家庭地址

floateng,phy,math,electron;//英語(yǔ),物理,數(shù)學(xué)和電子學(xué)成績(jī)public: student(){}

student(int,string,char,int,string,float,float,float,float);

booloperator<(studentele){returnid<ele.id;} voidshow(){cout<<id<<'\t'<<name<<'\t'<<sex<<'\t‘<<age<<'\t'<<address<<'\t'<<eng<<'\t'<<phy<<'\t‘<<math<<'\t'<<electron<<endl;}};int

main(){

constinth=4;

inti;

Orderedlist<student,100>ordlist;studentn[h]={ student(6004327,"張菲",'m',19,"北京路58號(hào)",80,85,90,78), student(6004121,"關(guān)雨",'w',19,"天津路64號(hào)",88,75,91,68), student(6004118,"劉蓓",'w',18,"上海路37號(hào)",78,95,81,88), student(6004219,"趙昀",'m',18,"重慶路95號(hào)",78,95,81,88)};

for(i=0;i<h;i++)ordlist.Insert(n[i],i);//建立順序表

cout<<"未排序表："<<endl;

ordlist.print();

ordlist.BubbleSort();

cout<<"已排序表："<<endl;

ordlist.print();

return0;}3．選擇排序（SelectionSort）基本思想：每一趟從待排序的記錄中選出關(guān)鍵字最小的元素，順序放在已排好序的子序列的后面，直到全部記錄排序完成。[49 38 65 97 76 13 27 49’]

13 [38 65 97 76