C語(yǔ)言程序設(shè)計(jì)群體類和群體數(shù)據(jù)的組織

會(huì)計(jì)學(xué)1C語(yǔ)言程序設(shè)計(jì)群體類和群體數(shù)據(jù)的組織2第一部分—模板函數(shù)模板類模板第1頁(yè)/共79頁(yè)3函數(shù)模板函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。聲明方法：template<typename標(biāo)識(shí)符>函數(shù)聲明

函數(shù)模板第2頁(yè)/共79頁(yè)4求絕對(duì)值函數(shù)的模板#include<iostream>usingnamespacestd;template<typenameT>Tabs(Tx){returnx<0?-x:x;}intmain(){intn=-5;doubled=-5.5;cout<<abs(n)<<endl;cout<<abs(d)<<endl;}

函數(shù)模板運(yùn)行結(jié)果：55.5第3頁(yè)/共79頁(yè)5求絕對(duì)值函數(shù)的模板分析編譯器從調(diào)用abs()時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表達(dá)式abs(n)，由于實(shí)參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個(gè)函數(shù)：

intabs(intx)

{returnx<0?-x:x;}

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

floatgpa;//平均分};類模板第7頁(yè)/共79頁(yè)template<classT>//類模板：實(shí)現(xiàn)對(duì)任意類型數(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ù)的實(shí)現(xiàn)template<classT>Store<T>::Store(void):haveValue(0){}9第8頁(yè)/共79頁(yè)template<classT>//提取數(shù)據(jù)函數(shù)的實(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ù)的實(shí)現(xiàn)voidStore<T>::PutElem(Tx){haveValue++;//將haveValue置為TRUE，表示item中已存入數(shù)值

item=x;//將x值存入item}10第9頁(yè)/共79頁(yè)intmain(){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;//輸出對(duì)象D的數(shù)據(jù)成員

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

Error(invalidArraySize);

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

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

Error(memoryAllocationError);}直接訪問的線性群體第17頁(yè)/共79頁(yè)19數(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是對(duì)象X的數(shù)組首地址

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

while(n--)//逐個(gè)復(fù)制數(shù)組元素*destptr++=*srcptr++;}直接訪問的線性群體第18頁(yè)/共79頁(yè)20淺拷貝alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝前alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝后alistsizeBintmain(){Array<int>A(10);......Array<int>B(A);......}template<classT>Array<T>::Array(constArray<T>&X){size=X.size;alist=X.alist;}第19頁(yè)/共79頁(yè)21深拷貝alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝前alistsizeAA的數(shù)組元素占用的內(nèi)存拷貝后alistsizeBB的數(shù)組元素占用的內(nèi)存第20頁(yè)/共79頁(yè)22數(shù)組類的重載"="運(yùn)算符函數(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;}直接訪問的線性群體第21頁(yè)/共79頁(yè)23數(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];}直接訪問的線性群體第22頁(yè)/共79頁(yè)24為什么有的函數(shù)返回引用如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，它就被認(rèn)為是一個(gè)常量，不能成為左值。如果返回值為引用。由于引用是對(duì)象的別名，所以通過引用當(dāng)然可以改變對(duì)象的值。直接訪問的線性群體第23頁(yè)/共79頁(yè)25重載指針轉(zhuǎn)換操作符template<classT>Array<T>::operatorT*(void)const{//返回當(dāng)前對(duì)象中私有數(shù)組的首地址

returnalist;}直接訪問的線性群體第24頁(yè)/共79頁(yè)26指針轉(zhuǎn)換運(yùn)算符的作用#include<iostream>usingnamespacestd;intmain(){

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

Array<int>a(10);voidread(int*p,n);read(a,10);}voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}直接訪問的線性群體第25頁(yè)/共79頁(yè)27Array類的應(yīng)用例9-4求范圍2~N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。直接訪問的線性群體第26頁(yè)/共79頁(yè)#include<iostream>#include<iomanip>#include"9_3.h"usingnamespacestd;intmain(){Array<int>A(10);intn;intprimecount=0,i,j;cout<<"Enteravalue>=2asupperlimitforprimenumbers:";cin>>n;A[primecount++]=2;//2是一個(gè)質(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;}28第27頁(yè)/共79頁(yè)29鏈表鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。鏈表是由系列結(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)的指針，則該鏈表稱為單鏈表。順序訪問的線性群體第28頁(yè)/共79頁(yè)30單鏈表data1data2data3datanNULL…h(huán)eadrear順序訪問的線性群體第29頁(yè)/共79頁(yè)31單鏈表的結(jié)點(diǎn)類模板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;};順序訪問的線性群體第30頁(yè)/共79頁(yè)32在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)data1data2…pdata…template<classT>voidNode<T>::InsertAfter(Node<T>*p){//p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

p->next=next;next=p;//當(dāng)前節(jié)點(diǎn)的指針域指向p}順序訪問的線性群體第31頁(yè)/共79頁(yè)33

刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)順序訪問的線性群體data1data2data3……Node<T>*Node<T>::DeleteAfter(void){Node<T>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}tempPtr第32頁(yè)/共79頁(yè)34鏈表的基本操作生成結(jié)點(diǎn)插入結(jié)點(diǎn)查找結(jié)點(diǎn)刪除結(jié)點(diǎn)遍歷鏈表清空鏈表順序訪問的線性群體第33頁(yè)/共79頁(yè)35鏈表類模板(例9-6)//9_6.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;#ifndefNULLconstintNULL=0;#endif//NULL#include"9_5.h"順序訪問的線性群體第34頁(yè)/共79頁(yè)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);36第35頁(yè)/共79頁(yè)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;37第36頁(yè)/共79頁(yè)voidInsertFront(constT&item);voidInsertRear(constT&item);voidInsertAt(constT&item);voidInsertAfter(constT&item);TDeleteFront(void);voidDeleteAt(void);T&Data(void);voidClearList(void);};#endif//LINKEDLIST_CLASS38第37頁(yè)/共79頁(yè)39鏈表類應(yīng)用舉例(例9-7)#include<iostream>usingnamespacestd;#include"9_6.h"#include"9_6.cpp"intmain(){LinkedList<int>Link;inti,key,item;for(i=0;i<10;i++){cin>>item;Link.InsertFront(item); }順序訪問的線性群體第38頁(yè)/共79頁(yè)cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<Link.Data()<<"";Link.Next();}cout<<endl;cout<<"請(qǐng)輸入一個(gè)需要?jiǎng)h除的整數(shù):";cin>>key;Link.Reset();40第39頁(yè)/共79頁(yè)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;}41第40頁(yè)/共79頁(yè)42特殊的線性群體——棧棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。an┆a2a1入棧出棧棧頂棧底特殊的線性群體——棧第41頁(yè)/共79頁(yè)43棧的應(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)返回地址第42頁(yè)/共79頁(yè)44棧的應(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)特殊的線性群體——棧第43頁(yè)/共79頁(yè)45棧的基本狀態(tài)?？諚Ｖ袥]有元素棧滿棧中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)棧中有元素，但未達(dá)到棧滿狀態(tài)特殊的線性群體——棧第44頁(yè)/共79頁(yè)棧頂┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（?？眨﹎axn10棧頂amax┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)46第45頁(yè)/共79頁(yè)47棧的基本操作初始化入棧出棧清空棧訪問棧頂元素檢測(cè)棧的狀態(tài)（滿、空）特殊的線性群體——棧第46頁(yè)/共79頁(yè)48棧類模板(例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;};//類的實(shí)現(xiàn)略第47頁(yè)/共79頁(yè)49棧的應(yīng)用例9.9一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器實(shí)現(xiàn)一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器，能夠進(jìn)行加、減、乘、除和乘方運(yùn)算。使用時(shí)算式采用后綴輸入法，每個(gè)操作數(shù)、操作符之間都以空白符分隔。例如，若要計(jì)算"3+5"則輸入"35+"。乘方運(yùn)算符用"^"表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運(yùn)算結(jié)果清除，可鍵入"c"。當(dāng)鍵入"q"時(shí)程序結(jié)束。9-9.h9-9.cpp特殊的線性群體——棧第48頁(yè)/共79頁(yè)//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);};50第49頁(yè)/共79頁(yè)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;}51第50頁(yè)/共79頁(yè)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();}52第51頁(yè)/共79頁(yè)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;}}53第52頁(yè)/共79頁(yè)voidCalculator::Clear(void){S.ClearStack();}//9_9.cpp#include"9-9.h"intmain(){CalculatorCALC;CALC.Run();}54第53頁(yè)/共79頁(yè)55特殊的線性群體——隊(duì)列隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體a1a2an-1an……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)a0第54頁(yè)/共79頁(yè)56隊(duì)列的基本狀態(tài)隊(duì)空隊(duì)列中沒有元素隊(duì)滿隊(duì)列中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)特殊的線性群體——隊(duì)列第55頁(yè)/共79頁(yè)a0a1an-1an……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(一般狀態(tài))……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(隊(duì)空狀態(tài))a0a1an-1anamax……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(隊(duì)滿狀態(tài))元素移動(dòng)方向元素移動(dòng)方向57第56頁(yè)/共79頁(yè)58循環(huán)隊(duì)列在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開頭。特殊的線性群體——隊(duì)列第57頁(yè)/共79頁(yè)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)59第58頁(yè)/共79頁(yè)60例9-10隊(duì)列類模板特殊的線性群體——隊(duì)列#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ù)的實(shí)現(xiàn)略第59頁(yè)/共79頁(yè)61第三部分—群體數(shù)據(jù)的組織插入排序選擇排序交換排序順序查找折半查找第60頁(yè)/共79頁(yè)62排序（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ù)元素。在排序過程中需要完成兩種基本操作：比較兩個(gè)數(shù)的大小調(diào)整元素在序列中的位置群體數(shù)據(jù)的組織第61頁(yè)/共79頁(yè)63內(nèi)部排序與外部排序內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過程。外部排序：待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程。群體數(shù)據(jù)的組織第62頁(yè)/共79頁(yè)64內(nèi)部排序方法插入排序選擇排序交換排序群體數(shù)據(jù)的組織第63頁(yè)/共79頁(yè)65插入排序的基本思想每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]第64頁(yè)/共79頁(yè)66直接插入排序在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡(jiǎn)單的直接插入排序算法。例9-11

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

直接選擇排序函數(shù)模板（9-12.h）群體數(shù)據(jù)的組織第68頁(yè)/共79頁(yè)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）70第69頁(yè)/共79頁(yè)71交換排序的基本思想兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。群體數(shù)據(jù)的組織第70頁(yè)/共79頁(yè)72最簡(jiǎn)單的交換排序方法