群體類和群體數(shù)據(jù)的組織ppt課件

1、第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織1本章主要內(nèi)容本章主要內(nèi)容l函數(shù)模板函數(shù)模板l類模板類模板lString類類l群體類群體類l群體數(shù)據(jù)的組織群體數(shù)據(jù)的組織第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織29.0 函數(shù)模板函數(shù)模板 函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能的函數(shù)，函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。數(shù)體設(shè)計(jì)。聲明方法：聲明方法：template 函數(shù)聲明函數(shù)聲明 函 數(shù) 模 板第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織3模板參數(shù)表模板參數(shù)表模

2、板參數(shù)表由用逗號(hào)分隔的模板參數(shù)構(gòu)成，可以包括以下形式內(nèi)模板參數(shù)表由用逗號(hào)分隔的模板參數(shù)構(gòu)成，可以包括以下形式內(nèi)容：容：1typename/class 標(biāo)識(shí)符標(biāo)識(shí)符 如如typename T,指明可以接收一個(gè)類型參數(shù)。這些類型參數(shù)代指明可以接收一個(gè)類型參數(shù)。這些類型參數(shù)代表的是類型，可以是內(nèi)部類型或者自定義類型。表的是類型，可以是內(nèi)部類型或者自定義類型。2類型說明符類型說明符 標(biāo)志符標(biāo)志符如如 int val，指明可以接收一個(gè)由類型說明符所規(guī)定類型的常，指明可以接收一個(gè)由類型說明符所規(guī)定類型的常量作為參數(shù)。量作為參數(shù)。3template class 標(biāo)志符標(biāo)志符如如templateclass C

3、ontainer指明可以接收一個(gè)指明可以接收一個(gè)類模板作為參數(shù)。類模板作為參數(shù)。第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織4求絕對(duì)值函數(shù)的模板求絕對(duì)值函數(shù)的模板#includeusing namespace std;templateT abs(T x) return x0?-x:x; void main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl;運(yùn)行結(jié)果：運(yùn)行結(jié)果：55.5第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織5求絕對(duì)值函數(shù)的模板分析求絕對(duì)值函數(shù)的模板分析編譯器從調(diào)用編譯器從調(diào)用abs

4、()時(shí)實(shí)參的類型，推導(dǎo)出函時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表達(dá)數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表達(dá)式式abs(n)，由于實(shí)參，由于實(shí)參n為為int型，所以推導(dǎo)型，所以推導(dǎo)出模板中類型參數(shù)出模板中類型參數(shù)T為為int。當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個(gè)函數(shù)：模板為樣板，生成一個(gè)函數(shù)：int abs(int x) return x0?-x:x; 第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織6 類模板用于設(shè)計(jì)一個(gè)通用類，使這個(gè)類的數(shù)據(jù)成員的類類模板用于設(shè)計(jì)一個(gè)通用類，使這個(gè)類的數(shù)據(jù)成員的類型、成員函數(shù)的

5、參數(shù)能夠按照需要進(jìn)行改變即參數(shù)化）型、成員函數(shù)的參數(shù)能夠按照需要進(jìn)行改變即參數(shù)化）聲明類模板的一般形式為：聲明類模板的一般形式為： template class class_name其中，其中，Ttype是一個(gè)標(biāo)識(shí)符，代表所聲明的類模板中參數(shù)是一個(gè)標(biāo)識(shí)符，代表所聲明的類模板中參數(shù)化的類型名。留意：模板類的成員函數(shù)必須是函數(shù)模板?；念愋兔?。留意：模板類的成員函數(shù)必須是函數(shù)模板。 定義了類模板以后，就可以創(chuàng)建這個(gè)類的實(shí)例：定義了類模板以后，就可以創(chuàng)建這個(gè)類的實(shí)例：Class_name 對(duì)象對(duì)象1，對(duì)象，對(duì)象n；type用具體的數(shù)據(jù)類型代入，系統(tǒng)根據(jù)代入的數(shù)據(jù)類型生用具體的數(shù)據(jù)類型代入，系統(tǒng)根據(jù)代

6、入的數(shù)據(jù)類型生成所需的類，并創(chuàng)建該類的對(duì)象。成所需的類，并創(chuàng)建該類的對(duì)象。9.1 類模板類模板第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織7/EX9_1.cpp : 演示類模板的定義和使用演示類模板的定義和使用#include #include struct student/聲明一個(gè)結(jié)構(gòu)體類型聲明一個(gè)結(jié)構(gòu)體類型 int id ; int score ; ;template/聲明一個(gè)類模板聲明一個(gè)類模板class buffer /實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)的存取實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)的存取 private: T a ; int empty ; public: buffer( void ) ;/

7、聲明聲明buffer類的構(gòu)造函數(shù)類的構(gòu)造函數(shù) T get( void ) ; void put( T x) ;第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織8template/定義定義buffer類的構(gòu)造函數(shù)模板類的構(gòu)造函數(shù)模板buffer:buffer( void ):empty(0) template/定義成員函數(shù)定義成員函數(shù)get模板模板T buffer:get(void) if (empty=0) coutthe buffer is empty!endl; exit(1); return a;template/定義成員函數(shù)定義成員函數(shù)put模板模板void buffer:p

8、ut(T x) empty+; a = x;第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織9void main(void) student s = 1022, 78 ; buffer i1, i2 ;/聲明整型對(duì)象聲明整型對(duì)象i1, i2 buffer stu1 ;/聲明結(jié)構(gòu)體對(duì)象聲明結(jié)構(gòu)體對(duì)象stu1 buffer d ;/聲明雙精度對(duì)象聲明雙精度對(duì)象d i1.put(13) ;/對(duì)象對(duì)象i1調(diào)用調(diào)用put執(zhí)行了執(zhí)行了empty+ i2.put(-101) ;/對(duì)象對(duì)象i2調(diào)用調(diào)用put執(zhí)行了執(zhí)行了empty+ couti1.get( ) i2.get( ) endl ; stu

9、1.put( s ) ;/對(duì)象對(duì)象stu1調(diào)用調(diào)用put執(zhí)行了執(zhí)行了empty+ coutthe students id is stu1.get( ).idendl ; coutthe students score is stu1.get( ).scoreendl ; coutd.get( )、+等等) 對(duì)字符串進(jìn)行賦值、銜接、復(fù)制、查找、交換對(duì)字符串進(jìn)行賦值、銜接、復(fù)制、查找、交換等。等。 基本形式為基本形式為 . string類類第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織12/EX9_2.cpp : 演示演示string類的應(yīng)用類的應(yīng)用#include #include u

10、sing namespace std ;void main( ) string s1(Hello), s2, s3, s4 ;/定義定義string對(duì)象對(duì)象 s2 = s1 ; /用用=號(hào)進(jìn)行賦值號(hào)進(jìn)行賦值(重載運(yùn)算符重載運(yùn)算符=) s3.assign(s1); /調(diào)用成員函數(shù)調(diào)用成員函數(shù)assign( )進(jìn)行賦值進(jìn)行賦值 couts1=s1.data( ), s2=s2.data( ) , s3=s3.data( )endl ; couts1的長(zhǎng)度的長(zhǎng)度=s1.length( )endl; /輸出字符串長(zhǎng)輸出字符串長(zhǎng)度度 char a =China!, b6 ; s1 = a ;/strin

11、g對(duì)象對(duì)象s1接收字符數(shù)組接收字符數(shù)組a的賦值的賦值 couts1=s1.data( )endl ; for( int i=0; i5; i+ ) bi = s2i ;/b5= 0; cout字符數(shù)組字符數(shù)組b= bendl ; /字符串的連接字符串的連接 s4=s2+ +s1; /用用+進(jìn)行字符串的連接進(jìn)行字符串的連接(重載運(yùn)算符重載運(yùn)算符+)s3=s2.append( s1 ) ; /s2與與s1連接并賦給連接并賦給s3，注意連接后的，注意連接后的s2結(jié)果結(jié)果第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織13couts2=s2.data( ), s3=s3.data( ), s

12、4= s4.data( )endl ; int f=pare( 6, 5, s4, 7, 5 ) ;/將將s3的第的第6個(gè)開始的個(gè)開始的5個(gè)字符與個(gè)字符與/s4的第的第7個(gè)開始的個(gè)開始的5個(gè)字符進(jìn)行比較個(gè)字符進(jìn)行比較 if ( f=0 ) couts3與與s4比較的部分相等比較的部分相等n; else couts3與與s4比較的部分不相等比較的部分不相等n; /取子字符串操作取子字符串操作 string sz=s2.substr( 5, 5 ) ; /取取s2的第的第5個(gè)開始的個(gè)開始的5個(gè)字符個(gè)字符 cout子字符串子字符串sz=sz.data( )endl ; s1.swap(s4) ;/交

13、換交換s1與與s4 couts1=s1.data(), s4=s4.data()endl ; cout字符串字符串China在在s1中的位置為：中的位置為： s1.find(China)endl; int len=s1.length( ) ; char *pt=new charlen+1 ; /定義字符型指針并動(dòng)態(tài)分配空間定義字符型指針并動(dòng)態(tài)分配空間 s1.copy(pt,len,0) ; /將將s1復(fù)制到復(fù)制到pt所指的數(shù)組，從所指的數(shù)組，從s10處開始復(fù)制處開始復(fù)制len個(gè)個(gè)字符字符 ptlen= 0 ; coutptendl ; s2 = pt ; /string類對(duì)象類對(duì)象s2接收字符

14、型指針的賦值接收字符型指針的賦值 couts2.data( )endl ;第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織14程序運(yùn)行結(jié)果為程序運(yùn)行結(jié)果為:s1=Hello, s2=Hello, s3=Hellos1的長(zhǎng)度的長(zhǎng)度=5s1=China!字符數(shù)組字符數(shù)組b= Hellos2=HelloChina!, s3=HelloChina!, s4=Hello China!s3與與s4比較的部分相等比較的部分相等 子字符串子字符串sz=Chinas1=Hello China!, s4=China!字符串字符串China在在s1中的位置為中的位置為: 6Hello China!Hell

15、o China!第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織9.2 群體數(shù)據(jù)群體數(shù)據(jù)群體的概念群體的概念群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類：線性群體和非線性群體。以分為兩個(gè)大類：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區(qū)分為線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。第一個(gè)元素、第二個(gè)元素等。非線性群體不用位置順序來標(biāo)識(shí)元素。非線性群體不用位置順序來標(biāo)識(shí)元素。第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織169.2.1 線

16、性群體的概念線性群體的概念 線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照訪問元素的不同方法分為直在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。接訪問、順序訪問和索引訪問。9.2.2 直接訪問群體直接訪問群體數(shù)組數(shù)組 靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。缺陷：大小在編譯時(shí)就已素可以通過下標(biāo)直接訪問。缺陷：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無法修改。經(jīng)確定，在運(yùn)行時(shí)無法修改。 動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類動(dòng)態(tài)數(shù)組由一系列位置連

17、續(xù)的，任意數(shù)量相同類型的元素組成。優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改型的元素組成。優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。動(dòng)態(tài)數(shù)組類模板舉例參見變。動(dòng)態(tài)數(shù)組類模板舉例參見P293301第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織17#ifndef ARRAY_CLASS#define ARRAY_CLASSusing namespace std;#include #include #ifndef NULLconst int NULL = 0;#endif / NULLenum ErrorType invalidArraySize, memoryAllocationError, inde

18、xOutOfRange ;char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;動(dòng)態(tài)數(shù)組類模板程序17第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織18template class Array private: T* alist; int size; void Error(ErrorType error) const; public: Array(int sz = 50); Array(const Array& A); Array(void); Array& ope

19、rator= (const Array& rhs); T& operator(int i); operator T* (void) const; int ListSize(void) const; void Resize(int sz); ;#endif18第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織1919數(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(inva

20、lidArraySize); 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)存不成功，輸出錯(cuò)誤信息 Error(memoryAllocationError);直接訪問的線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2020數(shù)組類的拷貝構(gòu)造函數(shù)數(shù)組類的拷貝構(gòu)造函數(shù)template Array:Array(const Array& X) int n = X.siz

21、e; 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ù)組首地址 while (n-) / 逐個(gè)復(fù)制數(shù)組元素逐個(gè)復(fù)制數(shù)組元素 *destptr+ = *srcptr+;直接訪問的線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2121淺拷貝淺拷貝 alist sizeAA的數(shù)組元素占用的內(nèi)存拷

22、貝前 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝后 alist sizeBvoid main(void) Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2222深拷貝深拷貝 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝前 alist sizeAA的數(shù)組元素占用的內(nèi)存拷貝后 alist sizeBB的數(shù)組元素占用的內(nèi)存第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2

23、323數(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+ = *srcptr+; return *this;直接訪問的

24、線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織24錯(cuò)誤報(bào)告函數(shù)錯(cuò)誤報(bào)告函數(shù)template void Array: Error(ErrorType error) const cout errorMsgerror endl; throw error;第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2525數(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)為返回

25、下標(biāo)為n的數(shù)組元素的數(shù)組元素 return alistn;直接訪問的線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2626為什么有的函數(shù)返回引用為什么有的函數(shù)返回引用如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，它如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，它就被認(rèn)為是一個(gè)常量，不能成為左值。就被認(rèn)為是一個(gè)常量，不能成為左值。如果返回值為引用。由于引用是對(duì)象的別名，如果返回值為引用。由于引用是對(duì)象的別名，所以通過引用當(dāng)然可以改變對(duì)象的值。所以通過引用當(dāng)然可以改變對(duì)象的值。直接訪問的線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2727重載指針轉(zhuǎn)換操作符重載指針轉(zhuǎn)換操作符t

26、emplate Array:operator T* (void) const / 返回當(dāng)前對(duì)象中私有數(shù)組的首地址返回當(dāng)前對(duì)象中私有數(shù)組的首地址 return alist;直接訪問的線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織28指針轉(zhuǎn)換運(yùn)算符的作用指針轉(zhuǎn)換運(yùn)算符的作用#include using namespace std;void main() int a10; void read(int *p, int n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;void main() Array a(10);

27、 void read(int *p, n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;直接訪問的線性群體右邊右邊read(a, 10);中中a是是Array類型對(duì)象，編譯類型對(duì)象，編譯器會(huì)為其尋找一個(gè)可以將其器會(huì)為其尋找一個(gè)可以將其轉(zhuǎn)換為轉(zhuǎn)換為int指針的函數(shù)或規(guī)則指針的函數(shù)或規(guī)則，試圖執(zhí)行，試圖執(zhí)行(int *)a,，以匹配，以匹配void read(int *p, int n)函數(shù)函數(shù)，若找不到，則編譯出錯(cuò)，若找不到，則編譯出錯(cuò)，由于類中重載了指針轉(zhuǎn)換符由于類中重載了指針轉(zhuǎn)換符，因此，因此 (int *)a 將得到將得到

28、a中數(shù)中數(shù)組指針，匹配成功。組指針，匹配成功。第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織2929Array類的應(yīng)用類的應(yīng)用例例9-4求范圍求范圍2N中的質(zhì)數(shù)，中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。在程序運(yùn)行時(shí)由鍵盤輸入。直接訪問的線性群體第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織30void main(void) Array A(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è)

29、質(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 setw(5) Ai; if (i+1) % 10 = 0) cout endl; 30第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織319.2.3 順序訪問群體順序訪問群體鏈表鏈表 鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪鏈表

30、是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。問的線性群體。 鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。態(tài)生成。 每一個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和指向鏈表中下一個(gè)結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)包括數(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)的指針，則該鏈表稱為單鏈表。表。 鏈表模板和應(yīng)用舉例參見鏈表模板和應(yīng)用舉例參見P302307第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織329.2.4 特殊的線性群體特殊的線性

31、群體棧棧棧是只能從一端訪問的線性群體，可以訪問的這一棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。端稱棧頂，另一端稱棧底。ana2a1入棧出棧棧頂棧底第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織331. 棧的應(yīng)用舉例棧的應(yīng)用舉例函數(shù)調(diào)用函數(shù)調(diào)用main調(diào)fun(參數(shù))終了fun(參數(shù))前往參數(shù)當(dāng)前現(xiàn)場(chǎng)返回地址入棧當(dāng)前現(xiàn)場(chǎng)返回地址出棧參數(shù)出棧當(dāng)前現(xiàn)場(chǎng) 返回地址第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織342. 棧的基本狀態(tài)棧的基本狀態(tài)棧空：?？眨簵Ｖ袥]有元素棧中沒有元素棧滿：棧滿：棧中元素個(gè)數(shù)達(dá)到上限棧中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)：棧中有元素，但

32、未達(dá)到棧滿狀態(tài)一般狀態(tài)：棧中有元素，但未達(dá)到棧滿狀態(tài)第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織棧頂ana1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)?？眨﹎axn10棧頂amaxana1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)35第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織3. 棧的基本操作棧的基本操作初始化初始化入棧入棧出棧出棧清空棧清空棧訪問棧頂元素訪問棧頂元素檢測(cè)棧的狀態(tài)滿、空）檢測(cè)棧的狀態(tài)滿、空）棧類模板和應(yīng)用舉例參見棧類模板和應(yīng)用舉例參見P307313第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織379.2.5 特殊

33、的線性群體特殊的線性群體隊(duì)列隊(duì)列隊(duì)列是只能向一端添加元素，從另一端刪除元素隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體的線性群體a1 a2an-1 an隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)a0第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織381. 隊(duì)列的基本狀態(tài)隊(duì)列的基本狀態(tài)隊(duì)空：隊(duì)空：隊(duì)列中沒有元素隊(duì)列中沒有元素隊(duì)滿：隊(duì)滿：隊(duì)列中元素個(gè)數(shù)達(dá)到上限隊(duì)列中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)：隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)一般狀態(tài)：隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織a0 a1an-1 an隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(一般狀態(tài))元

34、素移動(dòng)方向隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(隊(duì)空狀態(tài)) a0 a1 an-1 an amax隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(隊(duì)滿狀態(tài))元素移動(dòng)方向第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織402. 循環(huán)隊(duì)列循環(huán)隊(duì)列 在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開頭。，便再回到數(shù)組開頭。隊(duì)列類模板參見隊(duì)列類模板參見P313316第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織1234m-1m-

35、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)第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織429.3 群體數(shù)據(jù)的組織群體數(shù)據(jù)的組織l插入排序插入排序l選擇排序選擇排序l交換排序交換排序l順序查找順序查找l折半查找折半查找第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織43排序排序sorting） 排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素的任意序列

36、，重新排列成一個(gè)按功能是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。關(guān)鍵字有序的序列。數(shù)據(jù)元素：數(shù)據(jù)元素： 數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。關(guān)鍵字：關(guān)鍵字： 數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)識(shí)數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)識(shí)別一個(gè)數(shù)據(jù)元素。別一個(gè)數(shù)據(jù)元素。 在排序過程中需要完成兩種基本操作：在排序過程中需要完成兩種基本操作：比較兩個(gè)數(shù)的大小比較兩個(gè)數(shù)的大小調(diào)整元素在序列中的位置調(diào)整元素在序列中的位置第九章第九章 群體類群體類和群體

37、數(shù)據(jù)的組織和群體數(shù)據(jù)的組織44內(nèi)部排序與外部排序內(nèi)部排序與外部排序內(nèi)部排序：內(nèi)部排序： 待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過程。內(nèi)部排序方法序過程。內(nèi)部排序方法:插入排序插入排序選擇排序選擇排序交換排序交換排序外部排序：外部排序： 待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行訪不能容納全部數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程。問的排序過程。第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織459.3.1 插入排序插入排序 每一步將一個(gè)待排序元

38、素按其關(guān)鍵字值的大小插入到已排每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。序序列的適當(dāng)位置上，直到待排序元素插入完為止。初始狀態(tài)：初始狀態(tài)： 5 4 10 20 12 3 5 4 10 20 12 3插入操作：插入操作：1 4 4 5 10 20 12 31 4 4 5 10 20 12 32 10 4 5 10 20 12 32 10 4 5 10 20 12 33 20 4 5 10 20 12 33 20 4 5 10 20 12 34 12 4 5 10 12 20 34 12 4 5 10 12 20 35 3 3 4 5 10 1

39、2 205 3 3 4 5 10 12 20第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織46直接插入排序直接插入排序/9_11.h : 直接插入排序函數(shù)模板直接插入排序函數(shù)模板template void InsertionSort(T A , int n) int i, j ; T temp; for (i = 1; i 0 & temp A j-1 ) /逐個(gè)比較逐個(gè)比較 A j = A j-1 ; /將元素逐個(gè)后移，以便找到插入位置將元素逐個(gè)后移，以便找到插入位置 j - - ; A j = temp ;/ 插入位置找到，立即插入插入位置找到，立即插入 第九章第九章

40、群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織479.3.2 選擇排序選擇排序每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。全部排完。5 4 10 20 12 35 4 10 20 12 3待排序序列：待排序序列：3 4 10 20 12 53 4 10 20 12 53 4 10 20 12 53 4 10 20 12 5第第 i i 次選擇后，將選出的那個(gè)元素與第次選擇后，將選出的那個(gè)元素與第 i i 個(gè)元素做交換。個(gè)元素

41、做交換。3 4 5 20 12 103 4 5 20 12 10. .第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織48直接選擇排序直接選擇排序/9_12.h : 直接選擇排序函數(shù)模板直接選擇排序函數(shù)模板template void Swap ( T &x, T &y )/ 輔助函數(shù)：交換輔助函數(shù)：交換x和和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

42、; i+ ) smallIndex = i ; /最小元素之下標(biāo)初值設(shè)為最小元素之下標(biāo)初值設(shè)為i for ( j = i+1; j n; j+ )/逐個(gè)比較逐個(gè)比較 if ( A j A smallIndex ) smallIndex = j ;/記錄當(dāng)前找到的最小值的下標(biāo)記錄當(dāng)前找到的最小值的下標(biāo) Swap ( A i , A smallIndex ) ; / 將這一趟找到的最小元素與將這一趟找到的最小元素與A I 交換交換 第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織499.3.3 交換排序交換排序 兩兩比較待排序序列中的元素，并交換不滿足順序要求的各兩兩比較待排序序列中的元

43、素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。對(duì)元素，直到全部滿足順序要求為止。 最簡(jiǎn)單的交換排序方法最簡(jiǎn)單的交換排序方法起泡排序。起泡排序。 對(duì)具有對(duì)具有n個(gè)元素的序列按升序進(jìn)行起泡排序的步驟：個(gè)元素的序列按升序進(jìn)行起泡排序的步驟： 首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則將首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則將兩元素交換。然后比較第二、第三個(gè)元素，依次類推，直到第兩元素交換。然后比較第二、第三個(gè)元素，依次類推，直到第n-1和第和第n個(gè)元素進(jìn)行了比較和交換。此過程稱為第一趟起泡排序。個(gè)元素進(jìn)行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元

44、素便被交換到第經(jīng)過第一趟，最大的元素便被交換到第n個(gè)位置。個(gè)位置。 對(duì)前對(duì)前n-1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第到第n-1個(gè)位置。個(gè)位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。對(duì)對(duì)n個(gè)元素的序列，起泡排序最多需要進(jìn)行個(gè)元素的序列，起泡排序最多需要進(jìn)行n-1趟。趟。第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織50起泡排序舉例：對(duì)整數(shù)序列起泡排序舉例：對(duì)整數(shù)序列 8 5 2 4 3 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初初始始狀狀態(tài)態(tài)第第一一趟趟結(jié)結(jié)果果第第二二趟趟結(jié)結(jié)果果第第三三趟趟結(jié)結(jié)果果第第四四趟趟結(jié)結(jié)果果小小的的逐逐漸漸上上升升每趟沉下一個(gè)最大的第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織51/9_13.h : 起泡排序函數(shù)模板起泡排序函數(shù)模板template v