第14講 群體類和群體數(shù)據(jù)的組織(1)

1、第1414講 群體類和群體數(shù)據(jù)的組織（1 1）目錄n函數(shù)模板與類模板n線性群體-數(shù)組類n小結(jié)23函數(shù)重載#include using namespace std;int abs(int x) return x 0? -x : x;double abs(double x) return x 0? -x : x;int main() int n = -5;double d = -5.5;cout abs(n) endl;cout abs(d) endl;return 0;函數(shù)重載實(shí)現(xiàn)了函數(shù)重載實(shí)現(xiàn)了重重載多態(tài)載多態(tài)，但需要定，但需要定義多個(gè)重載函數(shù)義多個(gè)重載函數(shù)如何簡化如何簡化函數(shù)重載？函數(shù)重載？

2、函數(shù)模板套模板或?qū)嵗瘜?duì)一組函數(shù)的描述，不是一個(gè)真實(shí)的函數(shù)，編譯器不會(huì)產(chǎn)生任何代碼模板函數(shù)返回值類型 abs(形參類型 x)return x 0? -x : x;int main() int n = -5;double d = -5.5;cout abs(n) endl;cout abs(d) endl;return 0;當(dāng)編譯器發(fā)現(xiàn)在程序中有與函數(shù)模板相匹配的函數(shù)調(diào)用時(shí)，便生成一個(gè)模板函數(shù)，該函數(shù)的函數(shù)體與函數(shù)模板的函數(shù)體相同9.1.1 函數(shù)模板函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡化重載函數(shù)的函數(shù)體設(shè)計(jì)。定義方法：template 函數(shù)定義模板參數(shù)表的內(nèi)容類型

3、參數(shù)：class（或typename） 標(biāo)識(shí)符常量參數(shù)：類型說明符 標(biāo)識(shí)符模板參數(shù)：template class 標(biāo)識(shí)符59.1 函數(shù)模板與類模板例：求絕對(duì)值函數(shù)的模板#include using namespace std;templateT abs(T x) return x 0? -x : x;int main() int n = -5;double d = -5.5;cout abs(n) endl;cout abs(d) endl;return 0;T表示一種抽象數(shù)據(jù)類型編譯時(shí)生成相應(yīng)的模板函數(shù)定義方法：定義方法：template 函數(shù)定義函數(shù)定義定義方法：定義方法：template

4、 函數(shù)定義函數(shù)定義例9-1函數(shù)模板的示例/9_1.cpp#include using namespace std; template /定義函數(shù)模板，輸出數(shù)組中各元素的值void outputArray(const T *array, int count) for (int i = 0; i count; i+)cout arrayi ;cout endl; int main() /主函數(shù)const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;int a A_COUNT = 1, 2, 3, 4, 5, 6, 7, 8 ; double bB_COUN

5、T = 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 ;/定義double數(shù)組char cC_COUNT = Welcome to see you!;/定義char數(shù)組 cout a array contains: endl;outputArray(a, A_COUNT); /調(diào)用函數(shù)模板cout b array contains: endl;outputArray(b, B_COUNT); /調(diào)用函數(shù)模板cout c array contains: endl;outputArray(c, C_COUNT); /調(diào)用函數(shù)模板return 0;89.1.2 類模板

6、類模板的作用使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。9類模板套模板或?qū)嵗０孱悆H是一個(gè)模板，并非實(shí)實(shí)在在的類實(shí)實(shí)在在的類例9-2 類模板示例#include #include using namespace std;struct Student int id; /學(xué)號(hào) float gpa; /平均分; template class Store /類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取private:T item;/ item用于存放任意類型的數(shù)據(jù)bool haveValue; / ha

7、veValue標(biāo)記item是否已被存入內(nèi)容public:Store();/ 缺省形式（無形參）的構(gòu)造函數(shù)T &getElem();/提取數(shù)據(jù)函數(shù)void putElem(const T &x); /存入數(shù)據(jù)函數(shù);10類模板聲明：template class 類名類成員聲明11template /默認(rèn)構(gòu)造函數(shù)的實(shí)現(xiàn) Store:Store(): haveValue(false) template /提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)T &Store:getElem() /如試圖提取未初始化的數(shù)據(jù)，則終止程序if (!haveValue) cout No item present! end

8、l;exit(1);/使程序完全退出，返回到操作系統(tǒng)。return item; / 返回item中存放的數(shù)據(jù) template /存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn) void Store:putElem(const T &x) / 將haveValue 置為true，表示item中已存入數(shù)值haveValue = true;item = x;/ 將x值存入item類模板以外定義其成員函數(shù)：template 類型名 類名類名 :函數(shù)名（參數(shù)表）12int main() Store s1, s2;s1.putElem(3);s2.putElem(-7);cout s1.getElem() s2.getEl

9、em() endl;Student g = 1000, 23 ;Store s3;s3.putElem(g); cout The student id is s3.getElem().id endl;Store d;cout Retrieving object D. ;cout d.getElem() endl/由于d未經(jīng)初始化,在執(zhí)行函數(shù)D.getElement()過程中導(dǎo)致程序終止return 0;9.2 線性群體群體是指由多個(gè)數(shù)據(jù)元素組成的集合體集合體。群體可以分為兩個(gè)大類：線性群體和非線性群體。139.2.2 直接訪問群體數(shù)組類靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過下標(biāo)直

10、接訪問。缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無法修改。動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。vectorvector就是用類模板實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組。 參見6.4節(jié)動(dòng)態(tài)數(shù)組類模板動(dòng)態(tài)數(shù)組類模板：例9-3（Array.h）1415例9-3 動(dòng)態(tài)數(shù)組類模板程序#ifndef ARRAY_H#define ARRAY_H#include template /數(shù)組類模板定義class Array private:T* list;/用于存放動(dòng)態(tài)分配的數(shù)組內(nèi)存首地址用于存放動(dòng)態(tài)分配的數(shù)組內(nèi)存首地址int size;/數(shù)組大?。ㄔ貍€(gè)數(shù)）數(shù)組大?。ㄔ?/p>

11、素個(gè)數(shù)）public:Array(int sz = 50);/構(gòu)造函數(shù)Array(const Array &a); /拷貝構(gòu)造函數(shù)Array();/析構(gòu)函數(shù)Array & operator = (const Array &rhs); /重載重載=“T & operator (int i); /重載重載”const T & operator (int i) const;operator T * ();/重載到重載到T*類型的轉(zhuǎn)換類型的轉(zhuǎn)換operator const T * () const;int getSize() const;/取數(shù)組的大小void

12、resize(int sz);/修改數(shù)組的大小;template Array:Array(int sz) /構(gòu)造函數(shù)assert(sz = 0);/sz為數(shù)組大小（元素個(gè)數(shù)），應(yīng)當(dāng)非負(fù)size = sz; / 將元素個(gè)數(shù)賦值給變量sizelist = new T size;/動(dòng)態(tài)分配size個(gè)T類型的元素空間template Array:Array() /析構(gòu)函數(shù)delete list;/拷貝構(gòu)造函數(shù)template Array:Array(const Array &a) size = a.size; /從對(duì)象x取得數(shù)組大小，并賦值給當(dāng)前對(duì)象的成員/為對(duì)象申請(qǐng)內(nèi)存并進(jìn)行出錯(cuò)檢查list

13、 = new Tsize;/ 動(dòng)態(tài)分配n個(gè)T類型的元素空間for (int i = 0; i size; i+) /從對(duì)象X復(fù)制數(shù)組元素到本對(duì)象 listi = a.listi;16/重載=運(yùn)算符，將對(duì)象rhs賦值給本對(duì)象。實(shí)現(xiàn)對(duì)象之間的整體賦值template Array &Array:operator = (const Array& rhs) if (&rhs != this) /如果本對(duì)象中數(shù)組大小與rhs不同，則刪除數(shù)組原有內(nèi)存，然后重新分配if (size != rhs.size) delete list;/刪除數(shù)組原有內(nèi)存size = rhs.size;/設(shè)

14、置本對(duì)象的數(shù)組大小list = new Tsize; /重新分配n個(gè)元素的內(nèi)存/從對(duì)象X復(fù)制數(shù)組元素到本對(duì)象 for (int i = 0; i size; i+)listi = rhs.listi;return *this;/返回當(dāng)前對(duì)象的引用17/重載下標(biāo)運(yùn)算符，實(shí)現(xiàn)與普通數(shù)組一樣通過下標(biāo)訪問元素，并且具有越界檢查功能template T &Array:operator (int n) assert(n = 0 & n size);/檢查下標(biāo)是否越界return listn;/返回下標(biāo)為n的數(shù)組元素template const T &Array:operator (

15、int n) const assert(n = 0 & n size);/檢查下標(biāo)是否越界return listn;/返回下標(biāo)為n的數(shù)組元素 /重載指針轉(zhuǎn)換運(yùn)算符，將Array類的對(duì)象名轉(zhuǎn)換為T類型的指針template Array:operator T * () return list;/返回當(dāng)前對(duì)象中私有數(shù)組的首地址 18template Array:operator const T * () const return list; /返回當(dāng)前對(duì)象中私有數(shù)組的首地址/取當(dāng)前數(shù)組的大小template int Array:getSize() const return size;/ 將數(shù)

16、組大小修改為sztemplate void Array:resize(int sz) assert(sz = 0);/檢查sz是否非負(fù)if (sz = size)/如果指定的大小與原有大小一樣，什么也不做return;T* newList = new T sz;/申請(qǐng)新的數(shù)組內(nèi)存int n = (sz size) ? sz : size;/將sz與size中較小的一個(gè)賦值給n/將原有數(shù)組中前n個(gè)元素復(fù)制到新數(shù)組中for (int i = 0; i n; i+)newListi = listi;delete list;/刪除原數(shù)組list = newList;/ 使list指向新數(shù)組size =

17、 sz;/更新size#endif /ARRAY_H 1920問題一：為什么復(fù)制構(gòu)造函數(shù)中不直接用list=a.list？ list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后 list sizebb的數(shù)組元素占用的內(nèi)存深拷貝template Array:Array(const Array &a) size = a.size; list = new Tsize;for (int i = 0; i size; i+) listi = a.listi;為什么有的函數(shù)返回引用如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，就不應(yīng)成為左值。如果返回值為引用。由

18、于引用是對(duì)象的別名，通過引用當(dāng)然可以改變對(duì)象的值。21例：例：template T &Array:operator (int n) assert(n = 0 & n size);/檢查下標(biāo)是否越界檢查下標(biāo)是否越界return listn;/返回下標(biāo)為返回下標(biāo)為n的數(shù)組元素的數(shù)組元素指針轉(zhuǎn)換運(yùn)算符的作用#include using namespace std;void read(int *p, int n) for (int i = 0; i pi;int main() int a10; read(a, 10); return 0;#include Array.h#include

19、 using namespace std;void read(int *p, int n) for (int i = 0; i pi;int main() Array a(10); read(a, 10); return 0;22Array:operator T * () return list;Array類的應(yīng)用例9-4求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。2324#include #include #include Array.husing namespace std;int main() Array a(10);/ 用來存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有10個(gè)元素。int n, coun

20、t = 0;cout = 2 as upper limit for prime numbers: ;cin n;for (int i = 2; i = n; i+) /檢查i是否能被比它小的指數(shù)整除bool isPrime = true;for (int j = 0; j count; j+)if (i % aj = 0) /若i被aj整除，說明i不是質(zhì)數(shù)isPrime = false; break;if (isPrime) if (count = a.getSize() a.resize(count * 2);acount+ = i;for (int i = 0; i count; i+)c

21、out setw(8) ai;cout endl;return 0;例9-49.2.3 順序訪問群體鏈表類鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。259.2 線性群體26單鏈表9.2 線性群體 9.2.3 順序訪問群體鏈表類 data1 data2 data3 datan NULLheadrear鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成鏈表是由系列結(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)的地址）27單鏈表的結(jié)點(diǎn)類模板t

22、emplate class Node private: Node *next;/指向后繼結(jié)點(diǎn)的指針public: T data; /數(shù)據(jù)域 Node(const T& item,Node* next = 0);/構(gòu)造函數(shù) void insertAfter(Node *p); /在本結(jié)點(diǎn)后插入新結(jié)點(diǎn)p Node *deleteAfter(); /刪除本結(jié)點(diǎn)后繼結(jié)點(diǎn) Node *nextNode() const; /獲取后繼結(jié)點(diǎn)的地址; 9.2 線性群體 9.2.3 順序訪問群體鏈表類28在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)9.2 線性群體 9.2.3 順序訪問群體鏈表類 data1 data2 p d

23、atatemplate void Node:insertAfter(Node *p) /p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) p-next = next; next = p; /當(dāng)前節(jié)點(diǎn)的指針域指向p 29 刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)9.2 線性群體 9.2.3 順序訪問群體鏈表類 data1 data2 data3tempPtrNode *Node:deleteAfter(void) Node *tempPtr = next; if (next = 0) return 0; next = tempPtr-next; return tempPtr; 例9-5結(jié)點(diǎn)類模扳/Node.h#ifndef NOD

24、E_H#define NODE_H/類模板的定義template class Node private:Node *next;/指向后繼結(jié)點(diǎn)的指針public:T data;/數(shù)據(jù)域Node (const T &data, Node *next = 0); /構(gòu)造函數(shù)void insertAfter(Node *p); /在本結(jié)點(diǎn)之后插入一個(gè)同類結(jié)點(diǎn)p Node *deleteAfter(); /刪除本結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并返回其地址Node *nextNode();/獲取后繼結(jié)點(diǎn)的地址const Node *nextNode() const; /獲取后繼結(jié)點(diǎn)的地址;309.2 線性群體

25、9.2.3 順序訪問群體鏈表類/類的實(shí)現(xiàn)部分/構(gòu)造函數(shù)，初始化數(shù)據(jù)和指針成員template Node:Node(const T& data, Node *next/* = 0 */) : data(data), next(next) /返回后繼結(jié)點(diǎn)的指針template Node *Node:nextNode() return next; /返回后繼結(jié)點(diǎn)的指針template const Node *Node:nextNode() const return next; 319.2 線性群體 9.2.3 順序訪問群體鏈表類例9-5（續(xù)）/在當(dāng)前結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)p template

26、void Node:insertAfter(Node *p) p-next = next; /p結(jié)點(diǎn)指針域指向當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) next = p; /當(dāng)前結(jié)點(diǎn)的指針域指向p /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并返回其地址template Node *Node:deleteAfter() Node *tempPtr = next;/將欲刪除的結(jié)點(diǎn)地址存儲(chǔ)到tempPtr中if (next = 0)/如果當(dāng)前結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，則返回空指針return 0;next = tempPtr-next;/使當(dāng)前結(jié)點(diǎn)的指針域指向tempPtr的后繼結(jié)點(diǎn)return tempPtr;/返回被刪除的結(jié)點(diǎn)的地址#end

27、if /NODE_H329.2 9.2 線性群體 9.2.3 9.2.3 順序訪問群體鏈表類例9-5（續(xù)）鏈表的基本操作生成結(jié)點(diǎn)插入結(jié)點(diǎn)查找結(jié)點(diǎn)刪除結(jié)點(diǎn)遍歷鏈表清空鏈表339.2 線性群體 9.2.3 順序訪問群體鏈表類例9-6 鏈表類模板#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedList private:/數(shù)據(jù)成員：Node *front, *rear;/頭尾指針Node *prevPtr, *currPtr; /當(dāng)前指針 int size;/元素個(gè)數(shù)int position;/當(dāng)前

28、原速度在鏈表中的位置序號(hào)Node *newNode(const T &item,Node *ptrNext=NULL);void freeNode(Node *p);void copy(const LinkedList& L);public:LinkedList();LinkedList(const LinkedList &L); LinkedList();LinkedList & operator = (const LinkedList &L); int getSize() const;/返回鏈表中元素個(gè)數(shù)bool isEmpty() const;/判鏈表是否為空void reset(int pos = 0);/初始化游標(biāo)位置void next();/使游標(biāo)移動(dòng)到下一個(gè)結(jié)點(diǎn)bool endOfList() const;/游標(biāo)是否到了鏈尾int currentPosition(void) const;void insertFront(const T &item);/表頭插入void insertRear(const T &item);void insertAt(const T &i