模板與群體類

模板與群體類第一頁，共八十頁，編輯于2023年，星期六本章主要內(nèi)容模板群體類群體數(shù)據(jù)的組織2第二頁，共八十頁，編輯于2023年，星期六第一部分—模板函數(shù)模板類模板3第三頁，共八十頁，編輯于2023年，星期六函數(shù)模板函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡化重載函數(shù)的函數(shù)體設(shè)計。聲明方法：template<typename標(biāo)識符>函數(shù)聲明函數(shù)模板4第四頁，共八十頁，編輯于2023年，星期六求絕對值函數(shù)的模板#include<iostream>usingnamespacestd;template<typenameT>Tabs(Tx){returnx<0?-x:x;}voidmain(){intn=-5;doubled=-5.5;cout<<abs(n)<<endl;cout<<abs(d)<<endl;}函數(shù)模板運行結(jié)果：55.55第五頁，共八十頁，編輯于2023年，星期六求絕對值函數(shù)的模板分析編譯器從調(diào)用abs()時實參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對于調(diào)用表達(dá)式abs(n)，由于實參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)：

intabs(intx)

{returnx<0?-x:x;}函數(shù)模板6第六頁，共八十頁，編輯于2023年，星期六類模板的作用使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。類模板7第七頁，共八十頁，編輯于2023年，星期六類模板的聲明類模板：template<模板參數(shù)表>class類名{類成員聲明}如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式：template<模板參數(shù)表>類型名類名<T>::函數(shù)名（參數(shù)表）類模板8第八頁，共八十頁，編輯于2023年，星期六例9-2類模板應(yīng)用舉例#include<iostream>#include<cstdlib>usingnamespacestd;//結(jié)構(gòu)體StudentstructStudent{intid;//學(xué)號

floatgpa;//平均分};類模板9第九頁，共八十頁，編輯于2023年，星期六template<classT>//類模板：實現(xiàn)對任意類型數(shù)據(jù)進(jìn)行存取classStore{private:Titem;//用于存放任意類型的數(shù)據(jù)

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

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

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

voidPutElem(Tx);//存入數(shù)據(jù)函數(shù)};//默認(rèn)形式構(gòu)造函數(shù)的實現(xiàn)template<classT>Store<T>::Store(void):haveValue(0){}10第十頁，共八十頁，編輯于2023年，星期六template<classT>//提取數(shù)據(jù)函數(shù)的實現(xiàn)TStore<T>::GetElem(void){//如果試圖提取未初始化的數(shù)據(jù)，則終止程序

if(haveValue==0){cout<<"Noitempresent!"<<endl;exit(1);}returnitem;//返回item中存放的數(shù)據(jù)}template<classT>//存入數(shù)據(jù)函數(shù)的實現(xiàn)voidStore<T>::PutElem(Tx){haveValue++;//將haveValue置為TRUE，表示item中已存入數(shù)值

item=x;//將x值存入item}11第十一頁，共八十頁，編輯于2023年，星期六voidmain(void){Studentg={1000,23}; Store<int>S1,S2;Store<Student>S3;Store<double>D;

S1.PutElem(3);S2.PutElem(-7);cout<<S1.GetElem()<<""<<S2.GetElem()<<endl;

S3.PutElem(g);cout<<"Thestudentidis"<<S3.GetElem().id<<endl;

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

//由于D未經(jīng)初始化,在執(zhí)行函數(shù)D.GetElement()時出錯}12第十二頁，共八十頁，編輯于2023年，星期六第二部分—群體數(shù)據(jù)線性群體線性群體的概念直接訪問群體--數(shù)組類順序訪問群體--鏈表類棧類隊列類13第十三頁，共八十頁，編輯于2023年，星期六群體的概念群體是指由多個數(shù)據(jù)元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。非線性群體不用位置順序來標(biāo)識元素。14第十四頁，共八十頁，編輯于2023年，星期六線性群體的概念線性群體中的元素次序與其位置關(guān)系是對應(yīng)的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。在本章我們只介紹直接訪問和順序訪問?！谝粋€元素第二個元素第三個元素最后一個元素15第十五頁，共八十頁，編輯于2023年，星期六數(shù)組靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。缺點：大小在編譯時就已經(jīng)確定，在運行時無法修改。動態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。優(yōu)點：其元素個數(shù)可在程序運行時改變。動態(tài)數(shù)組類模板：例9-3（9_3.h）直接訪問的線性群體16第十六頁，共八十頁，編輯于2023年，星期六#ifndefARRAY_CLASS#defineARRAY_CLASSusingnamespacestd;#include<iostream>#include<cstdlib>#ifndefNULLconstintNULL=0;#endif//NULLenumErrorType{invalidArraySize,memoryAllocationError,indexOutOfRange};char*errorMsg[]={"Invalidarraysize","Memoryallocationerror","Invalidindex:"};動態(tài)數(shù)組類模板程序17第十七頁，共八十頁，編輯于2023年，星期六template<classT>classArray{private:T*alist;intsize;voidError(ErrorTypeerror,intbadIndex=0)const;public:Array(intsz=50);Array(constArray<T>&A);~Array(void);Array<T>&operator=(constArray<T>&rhs);T&operator[](inti);operatorT*(void)const;intListSize(void)const;voidResize(intsz);};18第十八頁，共八十頁，編輯于2023年，星期六數(shù)組類模板的構(gòu)造函數(shù)//構(gòu)造函數(shù)template<classT>Array<T>::Array(intsz){if(sz<=0)//sz為數(shù)組大?。ㄔ貍€數(shù)），若小于0，則輸出錯誤信息

Error(invalidArraySize);

size=sz;//將元素個數(shù)賦值給變量sizealist=newT[size];//動態(tài)分配size個T類型的元素空間

if(alist==NULL)//如果分配內(nèi)存不成功，輸出錯誤信息

Error(memoryAllocationError);}直接訪問的線性群體19第十九頁，共八十頁，編輯于2023年，星期六數(shù)組類的拷貝構(gòu)造函數(shù)template<classT>Array<T>::Array(constArray<T>&X){intn=X.size;size=n;alist=newT[n];if(alist==NULL)Error(memoryAllocationError);T*srcptr=X.alist;//X.alist是對象X的數(shù)組首地址

T*destptr=alist;//alist是本對象中的數(shù)組首地址

while(n--)//逐個復(fù)制數(shù)組元素*destptr++=*srcptr++;}直接訪問的線性群體20第二十頁，共八十頁，編輯于2023年，星期六淺拷貝

alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝前

alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝后

alistsizeBvoidmain(void){Array<int>A(10);......Array<int>B(A);......}template<classT>Array<T>::Array(constArray<T>&X){size=X.size;alist=X.alist;}21第二十一頁，共八十頁，編輯于2023年，星期六深拷貝

alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝前

alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝后

alistsizeBB的數(shù)組元素占用的內(nèi)存22第二十二頁，共八十頁，編輯于2023年，星期六數(shù)組類的重載"="運算符函數(shù)template<classT>Array<T>&Array<T>::operator=(constArray<T>&rhs){intn=rhs.size;if(size!=n){delete[]alist;alist=newT[n];if(alist==NULL)Error(memoryAllocationError);size=n;}T*destptr=alist;T*srcptr=rhs.alist;while(n--)*destptr++=*srcptr++;return*this;}直接訪問的線性群體23第二十三頁，共八十頁，編輯于2023年，星期六數(shù)組類的重載下標(biāo)操作符函數(shù)template<classT>T&Array<T>::operator[](intn){//檢查下標(biāo)是否越界

if(n<0||n>size-1)Error(indexOutOfRange,n);//返回下標(biāo)為n的數(shù)組元素

returnalist[n];}直接訪問的線性群體24第二十四頁，共八十頁，編輯于2023年，星期六為什么有的函數(shù)返回引用如果一個函數(shù)的返回值是一個對象的值，它就被認(rèn)為是一個常量，不能成為左值。如果返回值為引用。由于引用是對象的別名，所以通過引用當(dāng)然可以改變對象的值。直接訪問的線性群體25第二十五頁，共八十頁，編輯于2023年，星期六重載指針轉(zhuǎn)換操作符template<classT>Array<T>::operatorT*(void)const{//返回當(dāng)前對象中私有數(shù)組的首地址

returnalist;}直接訪問的線性群體26第二十六頁，共八十頁，編輯于2023年，星期六指針轉(zhuǎn)換運算符的作用#include<iostream>usingnamespacestd;voidmain(){

inta[10];voidread(int*p,intn);read(a,10);}voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}voidmain(){

Array<int>a(10);voidread(int*p,n);read(a,10);}voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}直接訪問的線性群體27第二十七頁，共八十頁，編輯于2023年，星期六Array類的應(yīng)用例9-4求范圍2~N中的質(zhì)數(shù)，N在程序運行時由鍵盤輸入。直接訪問的線性群體28第二十八頁，共八十頁，編輯于2023年，星期六#include<iostream>#include<iomanip>#include"9_3.h"usingnamespacestd;voidmain(void){Array<int>A(10);intn;intprimecount=0,i,j;cout<<"Enteravalue>=2asupperlimitforprimenumbers:";cin>>n;A[primecount++]=2;//2是一個質(zhì)數(shù)

for(i=3;i<n;i++){if(primecount==A.ListSize())A.Resize(primecount+10);if(i%2==0)continue;j=3;while(j<=i/2&&i%j!=0)j+=2;if(j>i/2)A[primecount++]=i;}for(i=0;i<primecount;i++){cout<<setw(5)<<A[i];if((i+1)%10==0)cout<<endl;}cout<<endl;}29第二十九頁，共八十頁，編輯于2023年，星期六鏈表鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。鏈表是由系列結(jié)點組成的，結(jié)點可以在運行時動態(tài)生成。每一個結(jié)點包括數(shù)據(jù)域和指向鏈表中下一個結(jié)點的指針（即下一個結(jié)點的地址）。如果鏈表每個結(jié)點中只有一個指向后繼結(jié)點的指針，則該鏈表稱為單鏈表。順序訪問的線性群體30第三十頁，共八十頁，編輯于2023年，星期六單鏈表

data1

data2

data3

datanNULL…h(huán)eadrear順序訪問的線性群體31第三十一頁，共八十頁，編輯于2023年，星期六單鏈表的結(jié)點類模板template<classT>classNode{private:Node<T>*next;public:Tdata;Node(constT&item,Node<T>*ptrnext=NULL);voidInsertAfter(Node<T>*p);Node<T>*DeleteAfter(void);Node<T>*NextNode(void)const;};順序訪問的線性群體32第三十二頁，共八十頁，編輯于2023年，星期六在結(jié)點之后插入一個結(jié)點

data1

data2…

p

data…template<classT>voidNode<T>::InsertAfter(Node<T>*p){//p節(jié)點指針域指向當(dāng)前節(jié)點的后繼節(jié)點

p->next=next;next=p;//當(dāng)前節(jié)點的指針域指向p}順序訪問的線性群體33第三十三頁，共八十頁，編輯于2023年，星期六刪除結(jié)點之后的結(jié)點順序訪問的線性群體

data1

data2

data3……Node<T>*Node<T>::DeleteAfter(void){Node<T>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}tempPtr34第三十四頁，共八十頁，編輯于2023年，星期六鏈表的基本操作生成結(jié)點插入結(jié)點查找結(jié)點刪除結(jié)點遍歷鏈表清空鏈表順序訪問的線性群體35第三十五頁，共八十頁，編輯于2023年，星期六鏈表類模板(例9-6)//9_6.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;#ifndefNULLconstintNULL=0;#endif//NULL#include"9_5.h"順序訪問的線性群體36第三十六頁，共八十頁，編輯于2023年，星期六template<classT>classLinkedList{private:Node<T>*front,*rear;Node<T>*prevPtr,*currPtr;intsize;intposition;Node<T>*GetNode(constT&item,Node<T>*ptrNext=NULL);voidFreeNode(Node<T>*p);voidCopyList(constLinkedList<T>&L);37第三十七頁，共八十頁，編輯于2023年，星期六

public:LinkedList(void);LinkedList(constLinkedList<T>&L);~LinkedList(void);LinkedList<T>&operator=(constLinkedList<T>&L);intListSize(void)const;intListEmpty(void)const;voidReset(intpos=0);voidNext(void);intEndOfList(void)const;intCurrentPosition(void)const;38第三十八頁，共八十頁，編輯于2023年，星期六

voidInsertFront(constT&item);voidInsertRear(constT&item);voidInsertAt(constT&item);voidInsertAfter(constT&item);TDeleteFront(void);voidDeleteAt(void);T&Data(void);voidClearList(void);};#endif//LINKEDLIST_CLASS39第三十九頁，共八十頁，編輯于2023年，星期六鏈表類應(yīng)用舉例(例9-7)#include<iostream>usingnamespacestd;#include"9_6.h"#include"9_6.cpp"voidmain(void){LinkedList<int>Link;inti,key,item;for(i=0;i<10;i++){cin>>item;Link.InsertFront(item); }順序訪問的線性群體40第四十頁，共八十頁，編輯于2023年，星期六

cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<Link.Data()<<"";Link.Next();}cout<<endl;cout<<"請輸入一個需要刪除的整數(shù):";cin>>key;Link.Reset();41第四十一頁，共八十頁，編輯于2023年，星期六

while(!Link.EndOfList()){if(Link.Data()==key)Link.DeleteAt(); Link.Next(); }cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<Link.Data()<<"";Link.Next();}cout<<endl;}42第四十二頁，共八十頁，編輯于2023年，星期六特殊的線性群體——棧棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。an┆a2a1入棧出棧棧頂棧底特殊的線性群體——棧43第四十三頁，共八十頁，編輯于2023年，星期六棧的應(yīng)用舉例——函數(shù)調(diào)用特殊的線性群體——棧main{}調(diào)fun(參數(shù))結(jié)束fun(參數(shù))返回①②⑤⑦⑧參數(shù)當(dāng)前現(xiàn)場返回地址③⑥入棧當(dāng)前現(xiàn)場返回地址出棧參數(shù)④出棧當(dāng)前現(xiàn)場返回地址44第四十四頁，共八十頁，編輯于2023年，星期六棧的應(yīng)用舉例——表達(dá)式處理ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的線性群體——棧45第四十五頁，共八十頁，編輯于2023年，星期六棧的基本狀態(tài)?？諚Ｖ袥]有元素棧滿棧中元素個數(shù)達(dá)到上限一般狀態(tài)棧中有元素，但未達(dá)到棧滿狀態(tài)特殊的線性群體——棧46第四十六頁，共八十頁，編輯于2023年，星期六棧頂┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（?？眨﹎axn10棧頂amax┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)47第四十七頁，共八十頁，編輯于2023年，星期六棧的基本操作初始化入棧出棧清空棧訪問棧頂元素檢測棧的狀態(tài)（滿、空）特殊的線性群體——棧48第四十八頁，共八十頁，編輯于2023年，星期六棧類模板(例9-8)特殊的線性群體——棧//9-8.h#ifndefSTACK_CLASS#defineSTACK_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;constintMaxStackSize=50;

template<classT>classStack{private:Tstacklist[MaxStackSize];inttop;public:Stack(void);voidPush(constT&item);TPop(void);voidClearStack(void);TPeek(void)const;intStackEmpty(void)const;intStackFull(void)const;};//類的實現(xiàn)略49第四十九頁，共八十頁，編輯于2023年，星期六棧的應(yīng)用例9.9一個簡單的整數(shù)計算器實現(xiàn)一個簡單的整數(shù)計算器，能夠進(jìn)行加、減、乘、除和乘方運算。使用時算式采用后綴輸入法，每個操作數(shù)、操作符之間都以空白符分隔。例如，若要計算"3+5"則輸入"35+"。乘方運算符用"^"表示。每次運算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運算結(jié)果清除，可鍵入"c"。當(dāng)鍵入"q"時程序結(jié)束。9-9.h9-9.cpp特殊的線性群體——棧50第五十頁，共八十頁，編輯于2023年，星期六//9_9.h#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>usingnamespacestd;enumBoolean{False,True};#include"9_8.h"classCalculator{private:Stack<int>S;voidEnter(intnum);BooleanGetTwoOperands(int&opnd1,int&opnd2);voidCompute(charop);public:voidRun(void);voidClear(void);};51第五十一頁，共八十頁，編輯于2023年，星期六voidCalculator::Enter(intnum){S.Push(num);}BooleanCalculator::GetTwoOperands(int&opnd1,int&opnd2){if(S.StackEmpty()){cerr<<"Missingoperand!"<<endl;returnFalse;}opnd1=S.Pop();if(S.StackEmpty()){cerr<<"Missingoperand!"<<endl;returnFalse;}opnd2=S.Pop();returnTrue;}52第五十二頁，共八十頁，編輯于2023年，星期六voidCalculator::Compute(charop){Booleanresult;intoperand1,operand2; result=GetTwoOperands(operand1,operand2);if(result) {switch(op){case'+':S.Push(operand2+operand1);break;case'-':S.Push(operand2-operand1);break;case'*':S.Push(operand2*operand1);break;case'/':if(operand1==0){cerr<<"Divideby0!"<<endl;S.ClearStack();}elseS.Push(operand2/operand1);break;case'^':S.Push(pow(operand2,operand1));break; }cout<<'='<<S.Peek()<<''; }elseS.ClearStack();}53第五十三頁，共八十頁，編輯于2023年，星期六voidCalculator::Run(void){charc[20];while(cin>>c,*c!='q')switch(*c){case'c':S.ClearStack();break;case'-': if(strlen(c)>1)Enter(atoi(c)); elseCompute(*c); break;case'+':case'*':case'/':case'^':Compute(*c);break;default:Enter(atoi(c));break;}}54第五十四頁，共八十頁，編輯于2023年，星期六voidCalculator::Clear(void){S.ClearStack();}//9_9.cpp#include"9-9.h"voidmain(void){CalculatorCALC;CALC.Run();}55第五十五頁，共八十頁，編輯于2023年，星期六特殊的線性群體——隊列隊列是只能向一端添加元素，從另一端刪除元素的線性群體a1a2an-1an……隊頭隊尾入隊出隊a056第五十六頁，共八十頁，編輯于2023年，星期六隊列的基本狀態(tài)隊空隊列中沒有元素隊滿隊列中元素個數(shù)達(dá)到上限一般狀態(tài)隊列中有元素，但未達(dá)到隊滿狀態(tài)特殊的線性群體——隊列57第五十七頁，共八十頁，編輯于2023年，星期六a0a1an-1an……隊頭隊尾入隊出隊數(shù)組下標(biāo)01n-1nmax(一般狀態(tài))……隊頭隊尾入隊出隊數(shù)組下標(biāo)01n-1nmax(隊空狀態(tài))

a0a1

an-1anamax……隊頭隊尾入隊出隊數(shù)組下標(biāo)01n-1nmax(隊滿狀態(tài))元素移動方向元素移動方向58第五十八頁，共八十頁，編輯于2023年，星期六循環(huán)隊列在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當(dāng)隊尾達(dá)到數(shù)組最后一個元素時，便再回到數(shù)組開頭。特殊的線性群體——隊列59第五十九頁，共八十頁，編輯于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)60第六十頁，共八十頁，編輯于2023年，星期六例9-10隊列類模板特殊的線性群體——隊列#ifndefQUEUE_CLASS#defineQUEUE_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;constintMaxQSize=50;template<classT>classQueue{private:intfront,rear,count;Tqlist[MaxQSize];public:Queue(void);voidQInsert(constT&item);TQDelete(void);voidClearQueue(void);TQFront(void)const;intQLength(void)const;intQEmpty(void)const;intQFull(void)const;};//成員函數(shù)的實現(xiàn)略61第六十一頁，共八十頁，編輯于2023年，星期六第三部分—群體數(shù)據(jù)的組織插入排序選擇排序交換排序順序查找折半查找62第六十二頁，共八十頁，編輯于2023年，星期六排序（sorting）排序是計算機(jī)程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機(jī)中通常作為一個整體進(jìn)行考慮。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。關(guān)鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素。在排序過程中需要完成兩種基本操作：比較兩個數(shù)的大小調(diào)整元素在序列中的位置群體數(shù)據(jù)的組織63第六十三頁，共八十頁，編輯于2023年，星期六內(nèi)部排序與外部排序內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計算機(jī)內(nèi)存中進(jìn)行的排序過程。外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進(jìn)行訪問的排序過程。群體數(shù)據(jù)的組織64第六十四頁，共八十頁，編輯于2023年，星期六內(nèi)部排序方法插入排序選擇排序交換排序群體數(shù)據(jù)的組織65第六十五頁，共八十頁，編輯于2023年，星期六插入排序的基本思想每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]66第六十六頁，共八十頁，編輯于2023年，星期六直接插入排序在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。例9-11

直接插入排序函數(shù)模板（9_11.h）群體數(shù)據(jù)的組織67第六十七頁，共八十頁，編輯于2023年，星期六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;}}直接插入排序函數(shù)模板（9_11.h）68第六十八頁，共八十頁，編輯于2023年，星期六選擇排序的基本思想每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。[541020123]初始狀態(tài)：3[41020125]34[1020125]第i次選擇后，將選出的那個記錄與第i個記錄做交換。345[201210]......69第六十九頁，共八十頁，編輯于2023年，星期六直接選擇排序在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。例9-12

直接選擇排序函數(shù)模板（9-12.h）群體數(shù)據(jù)的組織70第七十頁，共八十頁，編輯于2023年，星期六template<classT>voidSwap(T&x,T&y){Ttemp;temp=x;x=y;y=temp;}template<classT>voidSelectionSort(TA[],intn){intsmallIndex;inti,j;for(i=0;i<n-1;i++){smallIndex=i;for(j=i+1;j<n;j++)if(A[j]<A[smallIndex])smallIndex=j;Swap(A[i],A[smallIndex]);}}直接選擇排序函數(shù)模板（9-12.h）71第七十一頁，共八十頁，編輯于2023年，星期六交換排序的基本思想兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。群體數(shù)據(jù)的組織72第七十二頁，共八十頁，編輯于2023年，星期六最簡單的交換排序方法