c“加”“加”9群體類和群體數(shù)據(jù)的組織

1、ABAB第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織C+語言程序設(shè)計(jì)2本章主要內(nèi)容本章主要內(nèi)容l模板模板l群體類群體類l群體數(shù)據(jù)的組織群體數(shù)據(jù)的組織3第一部分第一部分模板模板l函數(shù)模板函數(shù)模板l類模板類模板4函數(shù)模板函數(shù)模板l函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一的函數(shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。l聲明方法：聲明方法：template 函數(shù)聲明 函 數(shù) 模 板5求絕對(duì)值函數(shù)的模板求絕對(duì)值函數(shù)的模板#includeusing namespace std;templateT

2、 abs(T x) return x0?-x:x; int main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; 函 數(shù) 模 板運(yùn)行結(jié)果：運(yùn)行結(jié)果：55.56求絕對(duì)值函數(shù)的模板分析求絕對(duì)值函數(shù)的模板分析l編譯器從調(diào)用編譯器從調(diào)用abs()時(shí)實(shí)參的類型，推時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表達(dá)式于調(diào)用表達(dá)式abs(n)，由于實(shí)參，由于實(shí)參n為為int型，所以推導(dǎo)出模板中類型參數(shù)型，所以推導(dǎo)出模板中類型參數(shù)T為為int。l當(dāng)類型參數(shù)的含義確定后，編譯器將當(dāng)類型參數(shù)的含義確定

3、后，編譯器將以函數(shù)模板為樣板，生成一個(gè)函數(shù)：以函數(shù)模板為樣板，生成一個(gè)函數(shù)：int abs(int x) return x0?-x:x; 函 數(shù) 模 板7類模板的作用類模板的作用使用類模板使用戶可以為類聲明一使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。類型的和用戶自定義類型）。類 模 板8類模板的聲明類模板的聲明l類模板：類模板：template class 類名類成員聲明l如果需要在類模板以

4、外定義其成員如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式：函數(shù)，則要采用以下的形式：template 類型名 類名:函數(shù)名（參數(shù)表）類 模 板9例例9-2 類模板應(yīng)用舉例類模板應(yīng)用舉例#include #include using namespace std;/ 結(jié)構(gòu)體結(jié)構(gòu)體Studentstruct Student int id; /學(xué)號(hào)學(xué)號(hào) float gpa; /平均分平均分; 類 模 板template /類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取class Store private: T item; / 用于存放任意類型的數(shù)據(jù)用于存放任意類型的數(shù)

5、據(jù) int haveValue; / 用于標(biāo)記用于標(biāo)記item是否已被存入內(nèi)容是否已被存入內(nèi)容 public: Store(void); / 默認(rèn)形式（無形參）的構(gòu)造函數(shù)默認(rèn)形式（無形參）的構(gòu)造函數(shù) T GetElem(void); /提取數(shù)據(jù)函數(shù)提取數(shù)據(jù)函數(shù) void PutElem(T x); /存入數(shù)據(jù)函數(shù)存入數(shù)據(jù)函數(shù);/ 默認(rèn)形式構(gòu)造函數(shù)的實(shí)現(xiàn)默認(rèn)形式構(gòu)造函數(shù)的實(shí)現(xiàn)template Store:Store(void): haveValue(0) 10template / 提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)T Store:GetElem(void) / 如果試圖提取未初始化的數(shù)據(jù)，則終

6、止程序如果試圖提取未初始化的數(shù)據(jù)，則終止程序 if (haveValue = 0) cout No item present! endl; exit(1); return item; / 返回返回item中存放的數(shù)據(jù)中存放的數(shù)據(jù) template / 存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn)存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn) void Store:PutElem(T x) haveValue+; / 將將haveValue 置為置為 TRUE，表示，表示item中已存入數(shù)值中已存入數(shù)值 item = x; / 將將x值存入值存入item11int main() Student g= 1000, 23; Store S1, S2;

7、Store S3; Store D; S1.PutElem(3); S2.PutElem(-7); cout S1.GetElem() S2.GetElem() endl; S3.PutElem(g); cout The student id is S3.GetElem().id endl; cout Retrieving object D ;cout D.GetElem() endl; /輸出對(duì)象輸出對(duì)象D的數(shù)據(jù)成員的數(shù)據(jù)成員/ 由于由于D未經(jīng)初始化未經(jīng)初始化,在執(zhí)行函數(shù)在執(zhí)行函數(shù)D.GetElement()時(shí)出錯(cuò)時(shí)出錯(cuò)1213第二部分第二部分群群體數(shù)據(jù)體數(shù)據(jù)l線性群體線性群體 線性群體的概

8、念 直接訪問群體-數(shù)組類 順序訪問群體-鏈表類 棧類 隊(duì)列類14群體的概念群體的概念群體群體是指由多個(gè)數(shù)據(jù)元素組成的集是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類：合體。群體可以分為兩個(gè)大類：線性群線性群體體和和非線性群體非線性群體。線性群體中的元素按位置排列有序，線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。非線性群體不用位置順序來標(biāo)識(shí)元非線性群體不用位置順序來標(biāo)識(shí)元素。素。15線性群體的概念線性群體的概念線性群體中的元素次序與其位置關(guān)線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照系是對(duì)應(yīng)的。在線性群體中，又

9、可按照訪問元素的不同方法分為訪問元素的不同方法分為直接訪問直接訪問、順順序訪問序訪問和和索引訪問索引訪問。在本章我們只介紹直接訪問和順序在本章我們只介紹直接訪問和順序訪問。訪問。第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素16數(shù)組數(shù)組l靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。中的元素可以通過下標(biāo)直接訪問。 缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無法修改。l動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。相同類型的元素組成。 優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。l動(dòng)態(tài)數(shù)組類模板：例動(dòng)態(tài)數(shù)組類模

10、板：例9-3（9_3.h）直接訪問的線性群體#ifndef ARRAY_CLASS#define ARRAY_CLASSusing namespace std;#include #include #ifndef NULLconst int NULL = 0;#endif / NULLenum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange ;char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;動(dòng)態(tài)數(shù)組類模板

11、程序17template class Array private: T* alist; int size; void Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array& A); Array(void); Array& operator= (const Array& rhs); T& operator(int i); operator T* (void) const; int ListSize(void) const; void Re

12、size(int sz); ;1819數(shù)組類模板的構(gòu)造函數(shù)數(shù)組類模板的構(gòu)造函數(shù)/ 構(gòu)造函數(shù)構(gòu)造函數(shù)template Array:Array(int sz) if (sz = 0) /sz為數(shù)組大小（元素個(gè)數(shù)），若小于為數(shù)組大?。ㄔ貍€(gè)數(shù)），若小于0，則輸出錯(cuò)誤信息，則輸出錯(cuò)誤信息 Error(invalidArraySize); size = sz; / 將元素個(gè)數(shù)賦值給變量將元素個(gè)數(shù)賦值給變量size alist = new Tsize; /動(dòng)態(tài)分配動(dòng)態(tài)分配size個(gè)個(gè)T類型的元素空間類型的元素空間 if (alist = NULL) /如果分配內(nèi)存不成功，輸出錯(cuò)誤信息如果分配內(nèi)存不成功，輸

13、出錯(cuò)誤信息 Error(memoryAllocationError);直接訪問的線性群體20數(shù)組類的拷貝構(gòu)造函數(shù)數(shù)組類的拷貝構(gòu)造函數(shù)template Array:Array(const Array& X) int n = X.size; size = n; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); T* srcptr = X.alist; / X.alist是對(duì)象是對(duì)象X的數(shù)組首地址的數(shù)組首地址 T* destptr = alist; / alist是本對(duì)象中的數(shù)組首地址是本對(duì)象中的數(shù)組首地址 whi

14、le (n-) / 逐個(gè)復(fù)制數(shù)組元素逐個(gè)復(fù)制數(shù)組元素 *destptr+ = *srcptr+;直接訪問的線性群體21淺拷貝淺拷貝 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝前 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝后 alist sizeBint main() Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;22深拷貝深拷貝 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝前 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝后

15、 alist sizeBB的數(shù)組元素占用的內(nèi)存23數(shù)組類的重載數(shù)組類的重載=運(yùn)算符函數(shù)運(yùn)算符函數(shù)template Array& Array:operator= (const Array& rhs) int n = rhs.size; if (size != n) delete alist; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); size = n; T* destptr = alist; T* srcptr = rhs.alist; while (n-) *destptr+ = *srcpt

16、r+; return *this;直接訪問的線性群體24數(shù)組類的重載下標(biāo)操作符函數(shù)數(shù)組類的重載下標(biāo)操作符函數(shù)template T& Array:operator (int n) / 檢查下標(biāo)是否越界檢查下標(biāo)是否越界 if (n size-1) Error(indexOutOfRange,n); / 返回下標(biāo)為返回下標(biāo)為n的數(shù)組元素的數(shù)組元素 return alistn;直接訪問的線性群體25為什么有的函數(shù)返回引用為什么有的函數(shù)返回引用l如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，它就被認(rèn)為是一個(gè)常量，不能成值，它就被認(rèn)為是一個(gè)常量，不能成為左值。為左值。l如果返

17、回值為引用。由于引用是對(duì)象如果返回值為引用。由于引用是對(duì)象的別名，所以通過引用當(dāng)然可以改變的別名，所以通過引用當(dāng)然可以改變對(duì)象的值。對(duì)象的值。直接訪問的線性群體26重載指針轉(zhuǎn)換操作符重載指針轉(zhuǎn)換操作符template Array:operator T* (void) const / 返回當(dāng)前對(duì)象中私有數(shù)組的首地址返回當(dāng)前對(duì)象中私有數(shù)組的首地址 return alist;直接訪問的線性群體27指針轉(zhuǎn)換運(yùn)算符的作用指針轉(zhuǎn)換運(yùn)算符的作用#include using namespace std;int main() int a10; void read(int *p, int n); read(a,

18、10);void read(int *p, int n) for (int i=0; ipi;int main() Array a(10); void read(int *p, n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;直接訪問的線性群體28Array類的應(yīng)用類的應(yīng)用l例例9-4求范圍求范圍2N中的質(zhì)數(shù)，中的質(zhì)數(shù)，N在程序在程序運(yùn)行時(shí)由鍵盤輸入。運(yùn)行時(shí)由鍵盤輸入。直接訪問的線性群體#include #include #include 9_3.husing namespace std;int main() Array A

19、(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: ; cin n; Aprimecount+ = 2; / 2是一個(gè)質(zhì)數(shù)是一個(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) Aprimecount+ = i; for (i = 0; i primecount; i+) cout s

20、etw(5) Ai; if (i+1) % 10 = 0) cout endl; cout endl;2930鏈表鏈表l鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。表示順序訪問的線性群體。l鏈表是由系列鏈表是由系列結(jié)點(diǎn)結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。在運(yùn)行時(shí)動(dòng)態(tài)生成。l每一個(gè)結(jié)點(diǎn)包括每一個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域數(shù)據(jù)域和指向鏈表中和指向鏈表中下一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的指針指針（即下一個(gè)結(jié)點(diǎn)的（即下一個(gè)結(jié)點(diǎn)的地址）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一地址）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表

21、。為單鏈表。順序訪問的線性群體31單鏈表單鏈表 data1 data2 data3 datan NULLheadrear順序訪問的線性群體32單鏈表的結(jié)點(diǎn)類模板單鏈表的結(jié)點(diǎn)類模板template class Node private: Node *next; public: T data; Node(const T& item,Node* ptrnext = NULL); void InsertAfter(Node *p); Node *DeleteAfter(void); Node *NextNode(void) const; 順序訪問的線性群體33在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)在結(jié)點(diǎn)之后插

22、入一個(gè)結(jié)點(diǎn) data1 data2 p datatemplate void Node:InsertAfter(Node *p) /p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) p-next = next; next = p; /當(dāng)前節(jié)點(diǎn)的指針域指向當(dāng)前節(jié)點(diǎn)的指針域指向p 順序訪問的線性群體34 刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)順序訪問的線性群體 data1 data2 data3Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-

23、next; return tempPtr; tempPtr35鏈表的基本操作鏈表的基本操作l生成結(jié)點(diǎn)生成結(jié)點(diǎn)l插入結(jié)點(diǎn)插入結(jié)點(diǎn)l查找結(jié)點(diǎn)查找結(jié)點(diǎn)l刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)l遍歷鏈表遍歷鏈表l清空鏈表清空鏈表順序訪問的線性群體36鏈表類模板鏈表類模板(例例9-6)/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include 9_5.h順序訪問的線性群體template class

24、 LinkedList private: Node *front, *rear; Node *prevPtr, *currPtr; int size; int position; Node *GetNode(const T& item, Node *ptrNext=NULL); void FreeNode(Node *p); void CopyList(const LinkedList& L);37 public: LinkedList(void); LinkedList(const LinkedList& L); LinkedList(void); LinkedLis

25、t& operator= (const LinkedList& L); int ListSize(void) const; int ListEmpty(void) const; void Reset(int pos = 0); void Next(void); int EndOfList(void) const; int CurrentPosition(void) const; 38 void InsertFront(const T& item); void InsertRear(const T& item); void InsertAt(const T&

26、; item); void InsertAfter(const T& item); T DeleteFront(void); void DeleteAt(void); T& Data(void); void ClearList(void);#endif / LINKEDLIST_CLASS3940鏈表類應(yīng)用舉例鏈表類應(yīng)用舉例(例例9-7)#include using namespace std;#include 9_6.h#include 9_6.cppint main() LinkedList Link; int i, key, item; for (i=0;i item;

27、Link.InsertFront(item);順序訪問的線性群體 cout List: ; Link.Reset(); while(!Link.EndOfList() cout Link.Data() ; Link.Next(); cout endl; cout key; Link.Reset();41 while (!Link.EndOfList() if(Link.Data() = key) Link.DeleteAt(); Link.Next(); cout List: ; Link.Reset(); while(!Link.EndOfList() cout Link.Data() ;

28、Link.Next(); cout endl;4243特殊的線性群體特殊的線性群體棧棧棧是只能從一端訪問的線性群體，棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧可以訪問的這一端稱棧頂，另一端稱棧底。底。ana2a1入棧出棧棧頂棧底特殊的線性群體棧44棧的應(yīng)用舉例棧的應(yīng)用舉例函數(shù)調(diào)用函數(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) 返回地址45棧的應(yīng)用舉例棧的應(yīng)用舉例表達(dá)式處理表達(dá)式處理ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c

29、*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的線性群體棧46棧的基本狀態(tài)棧的基本狀態(tài)l棧空?？?棧中沒有元素l棧滿棧滿 棧中元素個(gè)數(shù)達(dá)到上限l一般狀態(tài)一般狀態(tài) 棧中有元素，但未達(dá)到棧滿狀態(tài)特殊的線性群體棧棧頂ana1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（?？眨﹎axn10棧頂amaxana1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)4748棧的基本操作棧的基本操作l初始化初始化l入棧入棧l出棧出棧l清空棧清空棧l訪問棧頂元素訪問棧頂元素l檢測(cè)棧的狀態(tài)（滿、空）檢測(cè)棧的狀態(tài)（滿、空）特殊的線性群體棧49棧類模板棧類模板(例例9-8)特殊的

30、線性群體棧/9-8.h#ifndef STACK_CLASS#define STACK_CLASS#include #include using namespace std;const int MaxStackSize = 50; template class Stack private: T stacklistMaxStackSize; int top; public: Stack (void); void Push (const T& item); T Pop (void); void ClearStack(void); T Peek (void) const; int Stack

31、Empty(void) const; int StackFull(void) const;/類的實(shí)現(xiàn)略類的實(shí)現(xiàn)略50棧的應(yīng)用棧的應(yīng)用l例例9.9 一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器實(shí)現(xiàn)一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器，能夠進(jìn)行加、減、乘、除和乘方運(yùn)算。使用時(shí)算式采用后綴輸入法，每個(gè)操作數(shù)、操作符之間都以空白符分隔。例如，若要計(jì)算3+5則輸入3 5 +。乘方運(yùn)算符用表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運(yùn)算結(jié)果清除，可鍵入c。當(dāng)鍵入q時(shí)程序結(jié)束。l9-9.h 9-9.cpp特殊的線性群體棧/9_9.h#include #include #include #include using names

32、pace std;enum Boolean False, True;#include 9_8.h class Calculator private: Stack S; void Enter(int num); Boolean GetTwoOperands(int& opnd1, int& opnd2); void Compute(char op); public: void Run(void); void Clear(void); ;51void Calculator:Enter(int num) S.Push(num); Boolean Calculator:GetTwoOp

33、erands(int& opnd1, int& opnd2) if (S.StackEmpty() cerr Missing operand! endl; return False; opnd1 = S.Pop(); if (S.StackEmpty() cerr Missing operand! endl; return False; opnd2 = S.Pop(); return True;52void Calculator:Compute(char op) Boolean result; int operand1, operand2;result = GetTwoOper

34、ands(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 Divide by 0! endl; S.ClearStack(); else S.Push(operand2/operand1); break; case : S.Push(pow(op

35、erand2,operand1); break; cout=S.Peek() c, *c != q) switch(*c) case c: S.ClearStack(); break; case -: if (strlen(c)1) Enter(atoi(c); else Compute(*c); break; case +: case *: case /: case : Compute(*c); break; default: Enter(atoi(c); break; 54void Calculator:Clear(void) S.ClearStack(); /9_9.cpp#includ

36、e 9-9.hint main() Calculator CALC; CALC.Run();5556特殊的線性群體特殊的線性群體隊(duì)列隊(duì)列隊(duì)列是只能向一端添加元素，從另隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體一端刪除元素的線性群體a1 a2an-1 an隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)a057隊(duì)列的基本狀態(tài)隊(duì)列的基本狀態(tài)l隊(duì)空隊(duì)空 隊(duì)列中沒有元素l隊(duì)滿隊(duì)滿 隊(duì)列中元素個(gè)數(shù)達(dá)到上限l一般狀態(tài)一般狀態(tài) 隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)特殊的線性群體隊(duì)列a0 a1an-1 an隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(一般狀態(tài))隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(隊(duì)空狀態(tài)) a

37、0 a1 an-1 an amax隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(隊(duì)滿狀態(tài))元素移動(dòng)方向元素移動(dòng)方向5859循環(huán)隊(duì)列循環(huán)隊(duì)列在想象中將數(shù)組彎曲成環(huán)形，元素在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開頭。開頭。特殊的線性群體隊(duì)列1234m-1m-2m-30amam+1am+2a3隊(duì)頭隊(duì)尾a4am-2am-3am-1隊(duì)滿狀態(tài) 元素個(gè)數(shù)=m1234m-1m-2m-30隊(duì)尾隊(duì)頭隊(duì)空狀態(tài) 元素個(gè)數(shù)=0隊(duì)尾1234m-1m-2m-30a0a1a2a3隊(duì)頭一般狀態(tài)

38、6061例例9-10 隊(duì)列類模板隊(duì)列類模板特殊的線性群體隊(duì)列#ifndef QUEUE_CLASS#define QUEUE_CLASS#include #include using namespace std;const int MaxQSize = 50; template class Queue private: int front, rear, count; T qlistMaxQSize; public: Queue (void); void QInsert(const T& item); T QDelete(void); void ClearQueue(void); T Q

39、Front(void) const; int QLength(void) const; int QEmpty(void) const; int QFull(void) const; ;/成員函數(shù)的實(shí)現(xiàn)略成員函數(shù)的實(shí)現(xiàn)略62第三部分第三部分群群體數(shù)據(jù)的組織體數(shù)據(jù)的組織l插入排序插入排序l選擇排序選擇排序l交換排序交換排序l順序查找順序查找l折半查找折半查找63排序（排序（sorting）l排序排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)它的功能是將一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素的任意序列，重的任意序列，重新排列成一個(gè)按新排列成一個(gè)按關(guān)鍵字關(guān)鍵字有序的序列。有序的

40、序列。 數(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ù)元素。l在排序過程中需要完成兩種基本操作：在排序過程中需要完成兩種基本操作： 比較兩個(gè)數(shù)的大小 調(diào)整元素在序列中的位置群體數(shù)據(jù)的組織64內(nèi)部排序與外部排序內(nèi)部排序與外部排序l內(nèi)部排序：內(nèi)部排序：待排序的數(shù)據(jù)元素存放在待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過程。計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過程。l外部排序：外部排序：待排序的數(shù)據(jù)元素?cái)?shù)量很待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排

41、序過程中尚需對(duì)外存進(jìn)行數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程。訪問的排序過程。群體數(shù)據(jù)的組織65內(nèi)部排序方法內(nèi)部排序方法l插入排序插入排序l選擇排序選擇排序l交換排序交換排序群體數(shù)據(jù)的組織66插入排序的基本思想插入排序的基本思想l每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。序序列的適當(dāng)位置上，直到待排序元素插入完為止。初始狀態(tài)：初始狀態(tài)： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入操作：1 1 44 4 5 10 20 12 3 4 5 10 20 12 3

42、2 2 1010 4 5 10 20 12 3 4 5 10 20 12 33 3 2020 4 5 10 20 12 3 4 5 10 20 12 34 4 1212 4 5 10 12 20 3 4 5 10 12 20 35 5 33 3 4 5 10 12 20 3 4 5 10 12 2067直接插入排序直接插入排序l在插入排序過程中，由于尋找插入位置的在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡(jiǎn)單的直接插入排序算這里我們只介紹最簡(jiǎn)單的直接插入排序算法。法。l例例9-11 直接插入排序函數(shù)模板（直接

43、插入排序函數(shù)模板（9_11.h）群體數(shù)據(jù)的組織template void InsertionSort(T A, int n) int i, j; T temp; for (i = 1; i 0 & temp Aj-1) Aj = Aj-1; j-; Aj = temp; 直接插入排序函數(shù)模板（9_11.h）6869選擇排序的基本思想選擇排序的基本思想每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。最后，直至全部排完。5 4 10

44、 20 12 5 4 10 20 12 3 3 初始狀態(tài)：初始狀態(tài)：3 3 4 4 10 20 12 5 10 20 12 53 4 10 20 12 3 4 10 20 12 5 5 第 i i 次選擇后，將選出的那個(gè)記錄與第 i i 個(gè)記錄做交換交換。3 4 5 20 12 3 4 5 20 12 1010 . .70直接選擇排序直接選擇排序l在選擇類排序方法中，從待排序序列在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡(jiǎn)單的是通的選擇排序方法，其中最簡(jiǎn)單的是通過順序比較找出待排序序列中的最小過順序比較找出待排序序列中

45、的最小元素，稱為直接選擇排序。元素，稱為直接選擇排序。l例例9-12 直接選擇排序函數(shù)模板（直接選擇排序函數(shù)模板（9-12.h）群體數(shù)據(jù)的組織template void Swap (T &x, T &y) T temp; temp = x; x = y; y = temp;template void SelectionSort(T A, int n) int smallIndex; int i, j; for (i = 0; i n-1; i+) smallIndex = i; for (j = i+1; j n; j+) if (Aj AsmallIndex) smallIndex = j; Swap(Ai, AsmallIndex); 直接選擇排序函數(shù)模板（9-12.h）7172交換排序的基本思想交換排序的基本思想兩兩比較待排序序列中的元素，并兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。全部滿