實驗09 群體類與群體數(shù)據(jù)的組織

1、C+程序設(shè)計課內(nèi)實驗03數(shù)學(xué)與應(yīng)用數(shù)學(xué)201446譚毓銀曾悅16實驗09 群體類與群體數(shù)據(jù)的組織（4學(xué)時）（第9章 群體類與群體數(shù)據(jù)的組織）一、實驗?zāi)康?1) 掌握函數(shù)模板與類模板。(2) 了解線性群體與群體數(shù)據(jù)的組織。二、實驗任務(wù)9_1求絕對值的函數(shù)模板及其應(yīng)用#include <iostream>using namespace std;template<typename T>T fun(T x) return x < 0? -x : x;int main() int n = -5;double d = -5.5;cout << fun(n) <

2、;< endl;cout << fun(d) << endl;return 0;9_2函數(shù)模板的示例。#include <iostream>using namespace std;template <class T>/定義函數(shù)模板void outputArray(const T *array, int count)for (int i = 0; i < count; i+)cout << arrayi << " "cout << endl;int main() /主函數(shù)const

3、 int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;int a A_COUNT = 1, 2, 3, 4, 5, 6, 7, 8 ;/定義int數(shù)組double bB_COUNT = 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)

4、;/調(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;9_3類模板應(yīng)用舉例。#include <iostream>#include <cstdlib>using namespace std;/ 結(jié)構(gòu)體Studentstruct Stud

5、ent int id; /學(xué)號 float gpa; /平均分; template <class T>class Store /類模板：實現(xiàn)對任意類型數(shù)據(jù)進行存取private:T item;/ item用于存放任意類型的數(shù)據(jù)bool haveValue; / haveValue標(biāo)記item是否已被存入內(nèi)容public:Store();/ 缺省形式（無形參）的構(gòu)造函數(shù)T &getElem();/提取數(shù)據(jù)函數(shù)void putElem(const T &x); /存入數(shù)據(jù)函數(shù);/以下實現(xiàn)各成員函數(shù)。template <class T>/缺省構(gòu)造函數(shù)的實現(xiàn) S

6、tore<T>:Store(): haveValue(false) template <class T> /提取數(shù)據(jù)函數(shù)的實現(xiàn)T &Store<T>:getElem() /如試圖提取未初始化的數(shù)據(jù)，則終止程序if (!haveValue) cout << "No item present!" << endl;exit(1);/使程序完全退出，返回到操作系統(tǒng)。return item; / 返回item中存放的數(shù)據(jù) template <class T>/存入數(shù)據(jù)函數(shù)的實現(xiàn) void Store<

7、;T>:putElem(const T &x) / 將haveValue 置為true，表示item中已存入數(shù)值haveValue = true;item = x;/ 將x值存入itemint main() Store<int> s1, s2;s1.putElem(3);s2.putElem(-7);cout << s1.getElem() << " " << s2.getElem() << endl;Student g = 1000, 23 ;Store<Student> s3;s3.p

8、utElem(g); cout << "The student id is " << s3.getElem().id << endl;Store<double> d;cout << "Retrieving object D. "cout << d.getElem() << endl;/由于d未經(jīng)初始化,在執(zhí)行函數(shù)D.getElement()過程中導(dǎo)致程序終止return 0;9_4動態(tài)數(shù)據(jù)類模板示例/Array.h#ifndef ARRAY_H#define ARRAY_

9、H#include <cassert>/數(shù)組類模板定義template <class T> class Array private:T* list;/T類型指針，用于存放動態(tài)分配的數(shù)組內(nèi)存首地址int size;/數(shù)組大小（元素個數(shù)）public:Array(int sz = 50);/構(gòu)造函數(shù)Array(const Array<T> &a);/拷貝構(gòu)造函數(shù)Array();/析構(gòu)函數(shù)Array<T> & operator = (const Array<T> &rhs); /重載"="使數(shù)組對

10、象可以整體賦值T & operator (int i);/重載""，使Array對象可以起到C+普通數(shù)組的作用const T & operator (int i) const;/""運算符的const版本operator T * ();/重載到T*類型的轉(zhuǎn)換，使Array對象可以起到C+普通數(shù)組的作用operator const T * () const;/到T*類型轉(zhuǎn)換操作符的const版本int getSize() const;/取數(shù)組的大小void resize(int sz);/修改數(shù)組的大小;/構(gòu)造函數(shù)template <

11、class T>Array<T>:Array(int sz) assert(sz >= 0);/sz為數(shù)組大?。ㄔ貍€數(shù)），應(yīng)當(dāng)非負(fù)size = sz;/ 將元素個數(shù)賦值給變量sizelist = new T size;/動態(tài)分配size個T類型的元素空間/析構(gòu)函數(shù)template <class T>Array<T>:Array() delete list;/拷貝構(gòu)造函數(shù)template <class T>Array<T>:Array(const Array<T> &a) /從對象x取得數(shù)組大小，并賦值

12、給當(dāng)前對象的成員size = a.size;/為對象申請內(nèi)存并進行出錯檢查list = new Tsize;/ 動態(tài)分配n個T類型的元素空間/從對象X復(fù)制數(shù)組元素到本對象 for (int i = 0; i < size; i+)listi = a.listi;/重載"="運算符，將對象rhs賦值給本對象。實現(xiàn)對象之間的整體賦值template <class T>Array<T> &Array<T>:operator = (const Array<T>& rhs) if (&rhs != this

13、) /如果本對象中數(shù)組大小與rhs不同，則刪除數(shù)組原有內(nèi)存，然后重新分配if (size != rhs.size) delete list;/刪除數(shù)組原有內(nèi)存size = rhs.size;/設(shè)置本對象的數(shù)組大小list = new Tsize;/重新分配n個元素的內(nèi)存/從對象X復(fù)制數(shù)組元素到本對象 for (int i = 0; i < size; i+)listi = rhs.listi;return *this;/返回當(dāng)前對象的引用/重載下標(biāo)運算符，實現(xiàn)與普通數(shù)組一樣通過下標(biāo)訪問元素，并且具有越界檢查功能template <class T>T &Array<

14、;T>:operator (int n) assert(n >= 0 && n < size);/檢查下標(biāo)是否越界return listn;/返回下標(biāo)為n的數(shù)組元素template <class T>const T &Array<T>:operator (int n) const assert(n >= 0 && n < size);/檢查下標(biāo)是否越界return listn;/返回下標(biāo)為n的數(shù)組元素/重載指針轉(zhuǎn)換運算符，將Array類的對象名轉(zhuǎn)換為T類型的指針，/指向當(dāng)前對象中的私有數(shù)組。/因而可以

15、象使用普通數(shù)組首地址一樣使用Array類的對象名template <class T>Array<T>:operator T * () return list;/返回當(dāng)前對象中私有數(shù)組的首地址template <class T>Array<T>:operator const T * () const return list;/返回當(dāng)前對象中私有數(shù)組的首地址/取當(dāng)前數(shù)組的大小template <class T>int Array<T>:getSize() const return size;/ 將數(shù)組大小修改為sztempla

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

17、wList;/ 使list指向新數(shù)組size = sz;/更新size#endif /ARRAY_H/9_4.cpp#include <iostream>#include <iomanip>#include "Array.h"using namespace std;int main() Array<int> a(10);/ 用來存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有10個元素。int count = 0;int n;cout << "Enter a value >= 2 as upper limit for prime n

18、umbers: "cin >> n;for (int i = 2; i <= n; i+) /檢查i是否能被比它小的質(zhì)數(shù)整除bool isPrime = true;for (int j = 0; j < count; j+)if (i % aj = 0) /若i被aj整除，說明i不是質(zhì)數(shù)isPrime = false;break;/把i寫入質(zhì)數(shù)表中if (isPrime) /如果質(zhì)數(shù)表滿了，將其空間加倍if (count = a.getSize()a.resize(count * 2);acount+ = i;for (int i = 0; i < co

19、unt; i+)/輸出質(zhì)數(shù)cout << setw(8) << ai;cout << endl;return 0;9_5鏈表類應(yīng)用案例/Node.h#ifndef NODE_H#define NODE_H/類模板的定義template <class T>class Node private:Node<T> *next;/指向后繼結(jié)點的指針public:T data;/數(shù)據(jù)域Node (const T &data, Node<T> *next = 0); /構(gòu)造函數(shù)void insertAfter(Node<T

20、> *p);/在本結(jié)點之后插入一個同類結(jié)點p Node<T> *deleteAfter();/刪除本結(jié)點的后繼結(jié)點，并返回其地址Node<T> *nextNode(); /獲取后繼結(jié)點的地址const Node<T> *nextNode() const; /獲取后繼結(jié)點的地址;/類的實現(xiàn)部分/構(gòu)造函數(shù)，初始化數(shù)據(jù)和指針成員template <class T>Node<T>:Node(const T& data, Node<T> *next/* = 0 */) : data(data), next(next)

21、/返回后繼結(jié)點的指針template <class T>Node<T> *Node<T>:nextNode() return next;/返回后繼結(jié)點的指針template <class T>const Node<T> *Node<T>:nextNode() const return next; /在當(dāng)前結(jié)點之后插入一個結(jié)點p template <class T>void Node<T>:insertAfter(Node<T> *p) p->next = next;/p結(jié)點指針域指

22、向當(dāng)前結(jié)點的后繼結(jié)點 next = p;/當(dāng)前結(jié)點的指針域指向p /刪除當(dāng)前結(jié)點的后繼結(jié)點，并返回其地址template <class T>Node<T> *Node<T>:deleteAfter() Node<T> *tempPtr = next;/將欲刪除的結(jié)點地址存儲到tempPtr中if (next = 0)/如果當(dāng)前結(jié)點沒有后繼結(jié)點，則返回空指針return 0;next = tempPtr->next;/使當(dāng)前結(jié)點的指針域指向tempPtr的后繼結(jié)點return tempPtr;/返回被刪除的結(jié)點的地址#endif /NODE_

23、H/ LinkedList.h#ifndef LINKEDLIST_H#define LINKEDLIST_H#include "Node.h"template <class T>class LinkedList private:/數(shù)據(jù)成員：Node<T> *front, *rear;/表頭和表尾指針Node<T> *prevPtr, *currPtr; /記錄表當(dāng)前遍歷位置的指針，由插入和刪除操作更新int size;/表中的元素個數(shù)int position;/當(dāng)前元素在表中的位置序號。由函數(shù)reset使用/函數(shù)成員：/生成新結(jié)點，數(shù)據(jù)

24、域為item，指針域為ptrNextNode<T> *newNode(const T &item,Node<T> *ptrNext=NULL);/釋放結(jié)點void freeNode(Node<T> *p);/將鏈表L 拷貝到當(dāng)前表（假設(shè)當(dāng)前表為空）。/被拷貝構(gòu)造函數(shù)、operator = 調(diào)用void copy(const LinkedList<T>& L);public:LinkedList();/構(gòu)造函數(shù)LinkedList(const LinkedList<T> &L); /拷貝構(gòu)造函數(shù)LinkedLis

25、t();/析構(gòu)函數(shù)LinkedList<T> & operator = (const LinkedList<T> &L); /重載賦值運算符int getSize() const;/返回鏈表中元素個數(shù)bool isEmpty() const;/鏈表是否為空void reset(int pos = 0);/初始化游標(biāo)的位置void next();/使游標(biāo)移動到下一個結(jié)點bool endOfList() const;/游標(biāo)是否到了鏈尾int currentPosition(void) const;/返回游標(biāo)當(dāng)前的位置void insertFront(cons

26、t T &item);/在表頭插入結(jié)點void insertRear(const T &item);/在表尾添加結(jié)點void insertAt(const T &item);/在當(dāng)前結(jié)點之前插入結(jié)點void insertAfter(const T &item);/在當(dāng)前結(jié)點之后插入結(jié)點T deleteFront();/刪除頭結(jié)點void deleteCurrent();/刪除當(dāng)前結(jié)點T& data();/返回對當(dāng)前結(jié)點成員數(shù)據(jù)的引用const T& data() const; /返回對當(dāng)前結(jié)點成員數(shù)據(jù)的常引用/清空鏈表：釋放所有結(jié)點的內(nèi)存空間。被

27、析構(gòu)函數(shù)、operator= 調(diào)用void clear();#endif /LINKEDLIST_H/9_7.cpp#include <iostream>#include "LinkedList.h"using namespace std;int main() LinkedList<int> list;/輸入10個整數(shù)依次向表頭插入for (int i = 0; i < 10; i+) int item;cin >> item;list.insertFront(item);/輸出鏈表cout << "List:

28、 "list.reset();/輸出各結(jié)點數(shù)據(jù)，直到鏈表尾while (!list.endOfList() cout << list.data() << " "list.next();/使游標(biāo)指向下一個結(jié)點cout << endl;/輸入需要刪除的整數(shù)int key;cout << "Please enter some integer needed to be deleted: "cin >> key;/查找并刪除結(jié)點list.reset();while (!list.endOfLis

29、t() if (list.data() = key) list.deleteCurrent();list.next();/輸出鏈表cout << "List: "list.reset();/輸出各結(jié)點數(shù)據(jù)，直到鏈表尾while (!list.endOfList() cout << list.data() << " "list.next(); /使游標(biāo)指向下一個結(jié)點cout << endl;return 0;9_6棧的應(yīng)用（一個簡單的整數(shù)計算器）/Stack.h#ifndef STACK_H#define S

30、TACK_H#include <cassert> /模板的定義，SIZE為棧的大小template <class T, int SIZE = 50>class Stack private:T listSIZE;/數(shù)組，用于存放棧的元素int top;/棧頂位置（數(shù)組下標(biāo)）public:Stack();/構(gòu)造函數(shù)，初始化棧void push(const T &item);/將元素item壓入棧T pop();/將棧頂元素彈出棧void clear();/將棧清空const T &peek() const;/訪問棧頂元素bool isEmpty() cons

31、t;/測試是否棧滿bool isFull() const;/測試是否?？?/模板的實現(xiàn)template <class T, int SIZE>Stack<T, SIZE>:Stack() : top(-1) /構(gòu)造函數(shù)，棧頂初始化為-1template <class T, int SIZE>void Stack<T, SIZE>:push(const T &item) /將元素item壓入棧assert(!isFull();/如果棧滿了，則報錯list+top = item;/將新元素壓入棧頂template <class T, i

32、nt SIZE>T Stack<T, SIZE>:pop() /將棧頂元素彈出棧assert(!isEmpty();/如果棧為空，則報錯return listtop-;/返回棧頂元素，并將其彈出棧頂template <class T, int SIZE>const T &Stack<T, SIZE>:peek() const /訪問棧頂元素assert(!isEmpty();/如果棧為空，則報錯return listtop;/返回棧頂元素template <class T, int SIZE>bool Stack<T, SIZ

33、E>:isEmpty() const /測試棧是否空return top = -1;template <class T, int SIZE>bool Stack<T, SIZE>:isFull() const /測試是否棧滿return top = SIZE - 1;template <class T, int SIZE>void Stack<T, SIZE>:clear() /清空棧top = -1;#endif/STACK_H/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#in

34、clude "Stack.h"/ 包含棧類模板定義文件class Calculator /計算器類private:Stack<double> s;/ 操作數(shù)棧void enter(double num);/將操作數(shù)num壓入棧/連續(xù)將兩個操作數(shù)彈出棧，放在opnd1和opnd2中bool getTwoOperands(double &opnd1, double &opnd2);void compute(char op);/執(zhí)行由操作符op指定的運算public:void run();/運行計算器程序void clear();/清空操作數(shù)棧;#en

35、dif /CALCULATOR_H#include "Calculator.h"#include <iostream>#include <sstream>#include <cmath>using namespace std;void Calculator:enter(double num) /將操作數(shù)num壓入棧s.push(num);/連續(xù)將兩個操作數(shù)彈出棧，放在opnd1和opnd2中/如果棧中沒有兩個操作數(shù)，則返回False 并輸出相關(guān)信息bool Calculator:getTwoOperands(double &opn

36、d1, double &opnd2) if (s.isEmpty() /檢查棧是否空cerr << "Missing operand!" << endl;return false;opnd1 = s.pop();/將右操作數(shù)彈出棧if (s.isEmpty() /檢查棧是否空cerr << "Missing operand!" << endl;return false;opnd2 = s.pop();/將左操作數(shù)彈出棧return true;void Calculator:compute(char

37、op) /執(zhí)行運算double operand1, operand2;bool result = getTwoOperands(operand1, operand2); /將兩個操作數(shù)彈出棧if (result) /如果成功，執(zhí)行運算并將運算結(jié)果壓入棧switch(op) case '+':s.push(operand2 + operand1);break;case '-':s.push(operand2 - operand1);break;case '*':s.push(operand2 * operand1);break;case '

38、/':if (operand1 = 0) /檢查除數(shù)是否為0cerr << "Divided by 0!" << endl;s.clear();/除數(shù)為0時清空棧 elses.push(operand2 / operand1);break;case '':s.push(pow(operand2, operand1);break;default:cerr << "Unrecognized operator!" << endl;break;cout << "= &q

39、uot; << s.peek() << " "/輸出本次運算結(jié)果 elses.clear();/操作數(shù)不夠，清空棧/工具函數(shù)，用于將字符串轉(zhuǎn)換為實數(shù)inline double stringToDouble(const string &str) istringstream stream(str);/字符串輸入流double result;stream >> result;return result;void Calculator:run() /讀入并處理后綴表達(dá)式string str;while (cin >> str,

40、 str != "q") switch(str0) case 'c':s.clear();/遇'c'清空操作數(shù)棧break;case '-':/遇'-'需判斷是減號還是負(fù)號if (str.size() > 1)/若字符串長度>1，說明讀到的是負(fù)數(shù)的負(fù)號enter(stringToDouble(str);/將字符串轉(zhuǎn)換為整數(shù)，壓入棧elsecompute(str0);/若是減號則執(zhí)行計算break;case '+':/遇到其它操作符時case '*':case '

41、;/':case '':compute(str0);/執(zhí)行計算break;default:/若讀入的是操作數(shù)，轉(zhuǎn)換為整型后壓入棧enter(stringToDouble(str);break;void Calculator:clear() /清空操作數(shù)棧s.clear(); /9_9.cpp#include "Calculator.h"int main() Calculator c;c.run();return 0;9_7隊列類模板舉例/Queue.h#ifndef QUEUE_H#define QUEUE_H#include <cassert

42、>/類模板的定義template <class T, int SIZE = 50>class Queue private:int front, rear, count;/隊頭指針、隊尾指針、元素個數(shù)T listSIZE;/隊列元素數(shù)組public:Queue(); /構(gòu)造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)void insert(const T &item);/新元素入隊T remove();/元素出隊void clear();/清空隊列const T &getFront() const;/訪問隊首元素/測試隊列狀態(tài)int getLength() cons

43、t;/求隊列長度（元素個數(shù)）bool isEmpty() const;/判隊隊列空否bool isFull() const;/判斷隊列滿否;/構(gòu)造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)template <class T, int SIZE>Queue<T, SIZE>:Queue() : front(0), rear(0), count(0) template <class T, int SIZE>void Queue<T, SIZE>:insert (const T& item) /向隊尾插入元素（入隊）assert(count !=

44、 SIZE);count+;/元素個數(shù)增1listrear = item;/向隊尾插入元素rear = (rear + 1) % SIZE;/隊尾指針增1，用取余運算實現(xiàn)循環(huán)隊列template <class T, int SIZE>T Queue<T, SIZE>:remove() /刪除隊首元素，并返回該元素的值（出隊）assert(count != 0);int temp = front;/記錄下原先的隊首指針 count-;/元素個數(shù)自減 front = (front + 1) % SIZE;/隊首指針增1。取余以實現(xiàn)循環(huán)隊列 return listtemp;/

45、返回首元素值template <class T, int SIZE>const T &Queue<T, SIZE>:getFront() const /訪問隊列首元素（返回其值）return listfront;template <class T, int SIZE>int Queue<T, SIZE>:getLength() const /返回隊列元素個數(shù)return count;template <class T, int SIZE>bool Queue<T, SIZE>:isEmpty() const /測試

46、隊空否return count = 0;template <class T, int SIZE>bool Queue<T, SIZE>:isFull() const /測試隊滿否return count = SIZE;template <class T, int SIZE>void Queue<T, SIZE>:clear() /清空隊列count = 0;front = 0; rear = 0; #endif /QUEUE_H9_8直接插入排序函數(shù)模板/9_11.h#ifndef HEADER_9_11_H#define HEADER_9_11

47、_H/用直接插入排序法對數(shù)組A中的元素進行升序排列template <class T>void insertionSort(T a, int n) int i, j;T temp;/將下標(biāo)為1n-1的元素逐個插入到已排序序列中適當(dāng)?shù)奈恢胒or (int i = 1; i < n; i+) /從ai - 1開始向a0方向掃描各元素,尋找適當(dāng)位置插入aiint j = i;T temp = ai;while (j > 0 && temp < aj - 1) /逐個比較，直到temp >= aj - 1時，j便是應(yīng)插入的位置。/若達(dá)到j(luò) = 0，則

48、0是應(yīng)插入的位置。aj = aj - 1; /將元素逐個后移，以便找到插入位置時可立即插入。j-;/插入位置已找到，立即插入。aj = temp;#endif/HEADER_9_11_H9_9直接選擇排序函數(shù)模板/9_12.h#ifndef HEADER_9_12_H#define HEADER_9_12_H/輔助函數(shù)：交換x和y的值template <class T>void mySwap(T &x, T &y) T temp = x;x = y;y = temp;/用選擇法對數(shù)組a的n個元素進行排序template <class T>void selectionSort(T a, in