計(jì)算機(jī)CH09 群體類與模板

C++語言程序設(shè)計(jì)

第九章群體類

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

★★

★

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

本章主要內(nèi)容

?模板

?群體類

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

★年

*

2

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

第一部分一模板

函數(shù)模板

類模板

3

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

函

函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能

數(shù)的函數(shù)，以支持多種不同形參，進(jìn)一

出步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。

?聲明方法：

一

template<typename標(biāo)識(shí)符》

函數(shù)聲明

4

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

求絕對(duì)值函數(shù)的模板

函#include<iostream>

usingnamespacestd;

數(shù)tempiate<typenameT>

Tabs(Tx)

returnx<O?-x:x;}

模

voidmain()

板^{intn=-5;

doubled=-5.5;

cout?abs(n)?endl;

cout?abs(d)?endl;

}■

5

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

求絕對(duì)值函數(shù)的模板分析

函

編譯器從調(diào)用abs()時(shí)實(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;}■*”

6

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

類模板的作用

模使用類模板使用戶可以為類聲明一

板種模式，使得類中的某些數(shù)據(jù)成員、

某些成員函數(shù)的參數(shù)、某些成員函數(shù)

的返回值，能取任意類型（包括基本

類型的和用戶自定義類型）。

★★

7

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

類模板的聲明

類

模類模板：

板template＜模板參數(shù)表,

class類名

｛類成員聲明｝

如果需要在類模板以外定義其成員

函數(shù)，則要采用以下的形式：

templatev模板參數(shù)表〉.

類型名類名＜T＞::函數(shù)名（參數(shù)表）★★

8

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

例9?2類模板應(yīng)用舉例

類

模#include<iostream>

#include<cstdlib>

板usingnamespacestd;

II結(jié)構(gòu)體Student

structStudent

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

floatgpa;〃平均分

｝；★￥

★

9

template<classT>

〃類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取

classStore

{private:

Titem;II用于存放任意類型的數(shù)據(jù)

inthaveValue;II用于標(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(O){}

10

template<classT>II提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)

TStore<T>::GetElem(void)

(〃如果試圖提取未初始化的數(shù)據(jù)，則終止程序

if(haveValue==0)

{cout?"Noitempresent!"?endl;

exit⑴；

)

returnitem;II返回item中存放的數(shù)據(jù)

}

template<classT>II存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn)

voidStore<T>::PutElem(Tx)

{haveValue++;〃將haveValue置為TRUE,表示

item中已存入數(shù)值

item=x;〃將x值存入item

)

ii

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;〃輸出對(duì)象D的數(shù)據(jù)成員

II由于D未經(jīng)初始化，在執(zhí)行函數(shù)D.GetElement。時(shí)出錯(cuò)

)

12

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

第二部分一畔體數(shù)據(jù)

?線性群體

-線性群體的概念

-直接訪問群體-數(shù)組類

-順序訪問群體-鏈表類

-棧類

-隊(duì)列類

★★

*

13

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

群體的概念

群體是指由多個(gè)數(shù)據(jù)元素組成的集

合體。群體可以分為兩個(gè)大類：線性群

體和非線性群體。

線性群體中的元素按位置排列有序,

可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。

非線性群體不用位置順序來標(biāo)識(shí)元

素。

■

14

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

線性群體的概念

線性群體中的元素次序與其位置關(guān)

系是對(duì)應(yīng)的。在線性群體中，又可按照

訪問元素的不同方法分為直接訪問、順

序訪問和索引訪問。

在本章我們只介紹直接訪問和順序

訪問。

czz>CZZ^??.1

第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素★

15

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

數(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)/

■

16

#ifndefARRAY_CLASS

動(dòng)態(tài)數(shù)組類模板程序

#defineARRAY_CLASS

usingnamespacestd;

#include<iostream>

#include<cstdlib>

#ifndefNULL

constintNULL=0;

#endif//NULL

enumErrorType

{irivalidArraysize,memoryAllocationError,

indexOutOfRange);

char*errorMsg[]=

{"Invalidarraysize","Memoryallocationerror",

"Invalidindex:"

｝；17

template<classT>

classArray

{private:

T*alist;

intsize;

voidError(ErrorTypeerror,intbadlndex=O)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

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

數(shù)組類模板的構(gòu)造函數(shù)

直

接〃構(gòu)造函數(shù)

template<classT>

訪Array<T>::Array(intsz)

問(

if(sz<=0)

的〃sz為數(shù)組大小(元素個(gè)數(shù))，若小于0,則輸出錯(cuò)誤信息

線Error(invaIidArraySize);

性

size=sz;II將元素個(gè)數(shù)賦值給變量size

群alist=newT[size];〃動(dòng)態(tài)分配size個(gè)T類型的元素空間

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

體

Error(memoryAllocationError);★)

)

19

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

數(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;IIX.alist是對(duì)象X的數(shù)組首地址

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

體while(n-)II逐個(gè)復(fù)制數(shù)組元素

*destptr++=*srcptr++;

)

20

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

淺拷貝

A的數(shù)組元素A的數(shù)組元素

A

B

voidmain(void)

拷貝前{Array<int>A(10);拷貝后

★

Array<int>B(A);■

21

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

深拷貝

A的數(shù)組元素

B的數(shù)組元素

占用的內(nèi)存

拷貝前拷貝后

22

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

數(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;★￥

)

23

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

數(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

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

引用

直

接如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的

訪值，它就被認(rèn)為是一個(gè)常量，不能成

問為左值。

的

如果返回值為引用。由于引用是對(duì)象

線

的別名，所以通過引用當(dāng)然可以改變

性

對(duì)象的值。

群

體

■

25

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

重載指針轉(zhuǎn)換操作符

直

接template<classT>

訪

Array<T>::operatorT*(void)const

問

的(

線II返回當(dāng)前對(duì)象中私有數(shù)組的首地址

性returnalist;

群

}

體★￥

26

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

#include<iostream>voidmain()

吉妾usingnamespacestd;

訪voidmain()Array<int>a(10);

voidread(int*p,n);

問inta[10];read(a,10);

的voidread(int*p,intn);)

read(a,10);voidread(int*p,intn)

線)

性voidread(int*p,intn)for(inti=0;i<n;i++)

cin?p[i];

群for(inti=0;i<n;i++))

體cin?p[i];★￥

)

27

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

Array類的應(yīng)用

直

接例9?4求范圍2~N中的質(zhì)數(shù)，N在程序

訪運(yùn)行時(shí)由鍵盤輸入。

問

的

線

性

群

體

28

#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是一個(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;

if0>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

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

鏈表

順

序鏈表是一種動(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)的指針，則該鏈表稱

體為單鏈表?！铩?/p>

■

30

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

單鏈表

順

序

訪

問

的

線

性

群

體

★￥

31

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

單鏈表的結(jié)點(diǎn)類模板

卻頁(yè)template<classT>

序classNode

訪｛private:

間Node<T>*next;

的public:

線Tdata;

性Node(constT&item,Node<T>*ptrnext=NULL);

群voidlnsertAfter(Node<T>*p);

Node<T>*DeleteAfter(void);

體

Node<T>*NextNode(void)const;★*

);*

32

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)

順

序

訪

問

的

線template<classT>

voidNode<T>::lnsertAfter(Node<T>*p)

性

群〃p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

體p->next=next;AJ

next=p;〃當(dāng)前節(jié)點(diǎn)的指針域指向p￥

}

33

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)

順

序

訪

問

的

線Node<T>*Node<T>::DeleteAfter(void)

(

性Node<T>*tempPtr=next;

群if(next==NULL)

returnNULL;

體

next=tempPtr->next;★￥

returntempPtr;

)

34

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

鏈表的基本操作

順

序生成結(jié)點(diǎn)

訪

插入結(jié)點(diǎn)

問

的查找結(jié)點(diǎn)

線刪除結(jié)點(diǎn)

性

遍歷鏈表

群

體清空鏈表

35

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

鏈表類模板（例9?6）

順

〃9_6.h

序

#ifndefLINKEDLIST_CLASS

訪

#defineLINKEDLIST_CLASS

問

#include<iostream>

的

#include<cstdlib>

線

usingnamespacestd;

性

#ifndefNULL

群

constintNULL=0;

體#endif//NULL

include''9_5.h”

36

template<classT>

classLinkedList

{private:

Node<T>*front,*rear;

Node<T>*prevPtr5*currPtr;

intsize;

intposition;

Node<T>*GetNode(constT&item,

Node<T>*ptrNext=NULL);

voidFreeNode(Node<T>*p);

voidCopyList(constLinkedList<T>&L);

37

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

voidlnsertFront(constT&item);

voidlnsertRear(constT&item);

voidlnsertAt(constT&item);

voidlnsertAfter(constT&item);

TDeleteFront(void);

voidDeleteAt(void);

T&Data(void);

voidClearList(void);

)；

#endifIILINKEDLIST_CLASS

39

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

鏈表類應(yīng)用舉例(例9?7)

順

序#include<iostream>

訪usingnamespacestd;

問include"9_6h'

#include"9_6.cpp”

的

voidmain(void)

線

{LinkedList<int>Link;

性

inti,key,item;

群for(i=0;i<10;i++)

體{cin?item;

Link.lnsertFront(item);★￥

)★

40

cout?"List:

Link.Reset();

while(!Link.EndOfList())

(

cout?Link.Data()?"

Link.Next();

)

cout?endl;

coutw”請(qǐng)輸入一個(gè)需要?jiǎng)h除的整數(shù)：

cin?key;

Link.ResetQ;

41

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

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特特殊的線性群體----棧

殊

的棧是只能從一端訪問的線性群體,

線可以訪問的這一端稱棧頂,另一端稱棧

性底。

群入棧出棧

體

——

棧

43

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特

殊

的入棧出棧

線④|

I參數(shù)

性fUn（參數(shù)）

群

返回地力

體

返回

棧

44

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

棧的應(yīng)用舉例-----表達(dá)式處理

d

bc*

a___tltl=a/b+tl+

群a/b+c*da/b+c*da/b+c*d

(c)

體

t2t2=c*d__

五IL±

棧a/b+c*da/b+c*d★￥

(d)(e)

45

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特棧的基本狀態(tài)

殊

的??？?/p>

線

-棧中沒有元素

性

?棧滿

群

-棧中元素個(gè)數(shù)達(dá)到上限

體

——?一般狀態(tài)

棧中有元素，但未達(dá)到棧滿狀態(tài)

?！铮?/p>

46

入棧入棧出棧

棧頂

棧頂

初始狀態(tài)（?？眨?/p>

入棧出棧

棧頂

棧滿狀態(tài)

47

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特棧的基本操作

殊

的初始化

線

性入棧

群出棧

體清空棧

訪問棧頂元素

檢測(cè)棧的狀態(tài)（滿、空）

棧

48

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特棧類模板（例9?8）

殊

的//9-8.hpublic:

Stack(void);

線#ifndefSTACK_CLASS

voidPush(constT&item);

#defineSTACK_CLASS

性TPop(void);

#include<iostream>voidClearStack(void);

群#include<cstdlib>TPeek(void)const;

體usingnamespacestd;intStackEmpty(void)

const;

constintMaxStackSize=50;intStackFull(void)const;

)；

template<classT>〃類的實(shí)現(xiàn)略

classStack

{private:

棧Tstacklist[MaxStackSize];

inttop;★

49

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特

殊

的例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é)果清除，可鍵入當(dāng)鍵

入時(shí)程序結(jié)束。

棧?9-9.h9-9.cpp★￥

50

//9_9.h

#include<iostream>

#include<cmath>

#include<cstdlib>

#include<cstring>

usingnamespacestd;

enumBoolean{False,True};

include"9_8h'

classCalculator

{private:

Stack<int>S;

voidEnter(intnum);

BooleanGetTwoOperands(int&opndl,int&opnd2);

voidCompute(charop);

public:

voidRun(void);

voidClear(void);

）；

5l

voidCalculator::Enter(intnum)

{S.Push(num);}

BooleanCalculator::GetTwoOperands(int&opndl,int&opnd2)

(

if(S.StackEmptyO)

(

cerr?"Missingoperand!"?endl;

returnFalse;

)

opndl=S.Pop();

if(S.StackEmptyO)

(

cerr?"Missingoperand!"?endl;

returnFalse;

)

opnd2=S.Pop();

returnTrue;

)

52

voidCalculator::Compute(charop)

{Booleanresult;

intoperandl,operand2;

result=GetTwoOperands(operand1,operand2);

if(result)

{switch(op)

{case'+*:S.Push(operand2+operand1);break;

caseS.Push(operand2-operand1);break;

caseS.Push(operand2*operand1);break;

case71:if(operandl==0)

{cerr?"Divideby0!"?endl;S.CIearStack();}

else

S.Push(operand2/operand1);

break;

case，A，:S.Push(pow(operand2,operandl));break;

)

cout?,='?S.Peek()?,

)

else

S.CIearStack();

)53

voidCalculator::Run(void)

{charc[20];

while(cin?c,*c!='q')

switch(*c)

{case"c1:S.CIearStack();break;

case

if(strlen(c)>1)Enter(atoi(c));

elseCompute(*c);

break;

case

case

case7:

case，A，:

Compute(*c);break;

default:

Enter(atoi(c));break;

)

)54

voidCalculator::Clear(void)

{S.CIearStack();}

〃9_9,cpp

include”9?9.h''

voidmain(void)

(

CalculatorCALC;

CALC.RunQ;

}

55

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特隊(duì)列的基本狀態(tài)

殊

的

線?隊(duì)空

性-隊(duì)列中沒有元素

群?隊(duì)滿

體-隊(duì)列中元素個(gè)數(shù)達(dá)到上限

?一般狀態(tài)

隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)

隊(duì)

列

57

隊(duì)頭隊(duì)尾

兀系移動(dòng)方向

一1

出隊(duì)------..........o口入隊(duì)

數(shù)組下標(biāo)01n-lnmax

（一般狀態(tài)）

隊(duì)頭隊(duì)尾

出隊(duì)＜入隊(duì)

數(shù)組下標(biāo)0in-lnmax

（隊(duì)空狀態(tài)）

隊(duì)頭隊(duì)尾

兀系移動(dòng)方向

V

Hmax]

出隊(duì)VFL..........匚入隊(duì)

數(shù)組下標(biāo)01n-lnmax

（隊(duì)滿狀態(tài)）

58

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特

殊

的

線在想象中將數(shù)組彎曲成環(huán)形，元素

性出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)

群

體到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組

頭

開

——

隊(duì)

列

59

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

特例9?10隊(duì)列類模板

殊

的

#ifndefQUEUE_CLASSpublic:

線

#defineQUEUE_CLASSQueue(void);

性#include<iostream>voidQlnsert(constT&

群#include<cstdlib>item);

usingnamespacestd;TQDelete(void);

體

constintMaxQSize=50;voidClearQueue(void);

TQFront(void)const;

template<classT>intQLength(void)

classQueueconst;

intQEmpty(void)const;

{private:

隊(duì)intQFull(void)const^

intfront,rear,count;

列Tqlist[MaxQSize];成員函數(shù)的實(shí)現(xiàn)略★

61

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

第三部分一群體數(shù)據(jù)的組織

插入排序

?選擇排序

?交換排序

?順序查找

折半查找

62

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

排序(sorting)

群

體排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，

它的功能是將一個(gè)數(shù)據(jù)元素的任意序列，重

數(shù)新排列成一個(gè)按關(guān)鍵字有序的序列。

據(jù)數(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)整元素在序列中的位置★

63

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

群

體

內(nèi)部排序：待排序的數(shù)據(jù)元素存放在

數(shù)

據(jù)計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過程。

的?外部排序：待排序的數(shù)據(jù)元素?cái)?shù)量很

組大，以致內(nèi)存存中一次不能容納全部

織

數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行

訪問的排序過程。

■

64

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

群

體

數(shù)插入排序

據(jù)?選擇排序

的

組交換排序

織

65

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排

序序列的適當(dāng)位置上，直到待排序元素插入完為止。

初始狀態(tài):

插入操作：1

66

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

直接插入排序

群

體

在插入排序過程中，由于尋找插入位置的

數(shù)

據(jù)方法不同又可以分為不同的插入排序算法,

的這里我們只介紹最簡(jiǎn)單的直接插入排序算

組法。

織

例9」1直接插入排序函數(shù)模板（9例.h）

67

template<classT>直接插入排序函數(shù)模板（9」l.h）

voidlnsertionSort(TA[],intn)

{intij;

Ttemp;

for(i=1;i<n;i++)

{j=i；

temp=A[i];

whileG>0&&temp<A[j-1])

{AU]=AU-1];

j-；

)

A[j]=temp;

)

)

68

C++語言程序設(shè)計(jì)清華大學(xué)鄭莉

選擇排序的基本思想

每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，

（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的

最后，直至全部排完。

初始狀態(tài):[541020123]

3[41020125]

341020125]

345:201210]