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

1、海南大學信息科學技術學院實驗報告成績指導教師宇驗課程：C+程序設計課內實驗譚毓銀學號.03姓名-曾悅班級-數(shù)學與應用數(shù)學2014同組成員：完成日期：2016年6月4日實驗09群體類與群體數(shù)據(jù)的組織(4學時)(第9章 群體類與群體數(shù)據(jù)的組織)一、實驗目的(1) 掌握函數(shù)模板與類模板。(2) 了解線性群體與群體數(shù)據(jù)的組織。二、實驗任務9_1求絕對值的函數(shù)模板及其應用#include viostream using namespace std; templatevtypename T T fun(T x) return x v 0? -x : x;int main() int n = -5; dou

2、ble d = -5.5; cout vv fun(n) vv endl; cout vv fun(d) vv endl; return 0;55 5話按任意犍燈押狗拼音輸入袪全=BC:Wi n dowssystem32c rmd,exe9_2函數(shù)模板的示例。#include viostreamusing namespace std;template vclass T /定義函數(shù)模板 void outputArray(const T *array, int count)for (int i = 0; i count; i+)cout arrayi ”;cout #include using n

3、amespace std;/結構體 Studentstruct Student int id; 學號float gpa; / 平均分;template class Store /類模板：實現(xiàn)對任意類型數(shù)據(jù)進行存取private:T item; / item用于存放任意類型的數(shù)據(jù)bool haveValue; / haveValue標記item是否已被存入內容public:Store(); /缺省形式(無形參)的構造函數(shù)T & getElem();/提取數(shù)據(jù)函數(shù)void putElem(const T &x);/ 存入數(shù)據(jù)函數(shù);/以下實現(xiàn)各成員函數(shù)。template /缺省構造函數(shù)的實現(xiàn)Stor

4、e:Store(): haveValue(false) template 提取數(shù)據(jù)函數(shù)的實現(xiàn)T &Store:getElem() /如試圖提取未初始化的數(shù)據(jù)，則終止程序if (!haveValue) cout No item present! endl;exit(1); 使程序完全退出，返回到操作系統(tǒng)。return item; 返回item中存放的數(shù)據(jù)template /存入數(shù)據(jù)函數(shù)的實現(xiàn)void Store:putElem(const T &x) / 將 haveValue 置為 true，表示 item 中已存入數(shù)值haveValue = true;item = x;/ 將 x 值存入 i

5、temint main() Store s1, s2;s1.putElem(3);s2.putElem(-7);cout s1.getElem() s2.getElem() endl;Student g = 1000, 23 ;Store s3;s3.putElem(g);cout vv The student id is vv s3.getElem().id vv endl;Store d;cout vv Retrieving object D.;cout vv d.getElem() vv endl;/由于d未經(jīng)初始化，在執(zhí)行函數(shù)D.getElement()過程中導致程序終止 return

6、 0;C:Windowssystem32c md. exe aX1!rhe student id is 1000 object D. . . No iten present ?語援任意鍵繼續(xù)搜狗拼音輸入法全*Ai9_4動態(tài)數(shù)據(jù)類模板示例/Array.h#ifndef ARRAY_H#define ARRAY_H#include vcassert/數(shù)組類模板定義template vclass Tclass Array private:T* list;T類型指針，用于存放動態(tài)分配的數(shù)組內存首地址int size; /數(shù)組大小(元素個數(shù))public:Array(int sz = 50);/ 構造函

7、數(shù)Array(const Array &a);/ 拷貝構造函數(shù)Array();/析構函數(shù)Array & operator = (const Array &rhs); /重載=使數(shù)組對象可以整體賦值T & operator (int i);/重載，使Array對象可以起到 C+普通數(shù)組的作用const T & operator (int i) const; /運算符的 const版本operator T * ();/重載到T*類型的轉換，使 Array對象可以起到 C+普通數(shù)組的作用operator const T * () const; /到T*類型轉換操作符的const版本int getSi

8、ze() const;/ 取數(shù)組的大小 void resize(int sz); /修改數(shù)組的大小；/構造函數(shù)template vclass TArrayvT:Array(int sz) assert(sz = 0);/sz為數(shù)組大小(元素個數(shù))，應當非負size = sz; /將元素個數(shù)賦值給變量sizelist = new T size; /動態(tài)分配 size個T類型的元素空間析構函數(shù)template vclass T Array:Array() delete list;/拷貝構造函數(shù)template vclass T Array:Array(const Array &a) /從對象x取得

9、數(shù)組大小，并賦值給當前對象的成員size = a.size;/為對象申請內存并進行出錯檢查list = new Tsize; /動態(tài)分配 n個T類型的元素空間從對象X復制數(shù)組元素到本對象for (int i = 0; i v size; i+)listi = a.listi;/重載=運算符，將對象rhs賦值給本對象。實現(xiàn)對象之間的整體賦值template vclass TArrayvT &ArrayvT:operator = (const ArrayvT & rhs) if (&rhs != this) 如果本對象中數(shù)組大小與rhs不同，則刪除數(shù)組原有內存，然后重新分配if (size !=

10、rhs.size) delete list;/刪除數(shù)組原有內存size = rhs.size;/設置本對象的數(shù)組大小list = new Tsize; /重新分配 n個元素的內存從對象X復制數(shù)組元素到本對象for (int i = 0; i v size; i+)Iisti = rhs.listi;return *this; /返回當前對象的引用/重載下標運算符，實現(xiàn)與普通數(shù)組一樣通過下標訪問元素，并且具有越界檢查功能 template vclass TT &ArrayvT:operato 叩(int n) assert(n = 0 & n size); /檢查下標是否越界 return li

11、stn;/返回下標為n的數(shù)組元素template const T &Array:operator (int n) const assert(n = 0 & n size); /檢查下標是否越界 return listn;/返回下標為n的數(shù)組元素/重載指針轉換運算符，將Array類的對象名轉換為 T類型的指針，/指向當前對象中的私有數(shù)組。因而可以象使用普通數(shù)組首地址一樣使用Array類的對象名template Array:operator T * () return list;返回當前對象中私有數(shù)組的首地址template Array:operator const T * () const re

12、turn list;返回當前對象中私有數(shù)組的首地址/取當前數(shù)組的大小template int ArrayvT:getSize() const return size;/將數(shù)組大小修改為sztemplate vclass Tvoid Array:resize(int sz) assert(sz = 0);/檢查sz是否非負if (sz = size) 如果指定的大小與原有大小一樣，什么也不做return;T* newList = new T sz;/申請新的數(shù)組內存int n = (sz size) ? sz : size; /將 sz與 size 中較小的一個賦值給n/將原有數(shù)組中前 n個元素

13、復制到新數(shù)組中for (int i = 0; i n; i+)newListi = listi;delete list;/刪除原數(shù)組list = newList; / 使 list指向新數(shù)組size = sz; /更新 size#endif ARRAY_H9_4.cpp#include #include #include Array.h using namespace std;int main() Array a(10); /用來存放質數(shù)的數(shù)組，初始狀態(tài)有10個元素。int count = 0;int n;cout = 2 as upper limit for prime numbers:;

14、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不是質數(shù) isPrime = false;break;把i寫入質數(shù)表中if (isPrime) /如果質數(shù)表滿了，將其空間加倍if (count = a.getSize()a.resize(count * 2); acount+ = i;for (int i = 0; i count; i+) / 輸出質數(shù)cout setw(8) ai;cout =

15、2 as 23i膏援任意鍵繼統(tǒng)uippe 1 ldn 1 七 for prine nunb&rs: 丄5 S7li13捜狗拼音輸入法全：9_5鏈表類應用案例/Node.h#ifndef NODE_H #define NODE_H/類模板的定義template vclass Tclass Node private:Node *next;/指向后繼結點的指針public:T data; /數(shù)據(jù)域Node (const T & data, Node *next = 0);/ 構造函數(shù)void insertAfter(Node *p);/在本結點之后插入一個同類結點pNode *deleteAfter

16、();刪除本結點的后繼結點，并返回其地址Node *nextNode();獲取后繼結點的地址const Node *nextNode() const;/ 獲取后繼結點的地址;/類的實現(xiàn)部分/構造函數(shù)，初始化數(shù)據(jù)和指針成員template vclass TNode:Node(const T& data, Node *next/* = 0 */) : data(data), next(next) /返回后繼結點的指針template vclass TNode *Node:nextNode() return next;/返回后繼結點的指針template vclass Tconst Node *No

17、de:nextNode() const return next;在當前結點之后插入一個結點ptemplate void Node:insertAfter(Node *p) p-next = next; p結點指針域指向當前結點的后繼結點next = p;當前結點的指針域指向p刪除當前結點的后繼結點，并返回其地址template Node *Node:deleteAfter() Node *tempPtr = next; 將欲刪除的結點地址存儲到tempPtr中if (next = 0) 如果當前結點沒有后繼結點，則返回空指針return 0;next = tempPtr-next; /使當前結

18、點的指針域指向tempPtr的后繼結點return tempPtr;返回被刪除的結點的地址#endif NODE_H/ LinkedList.h#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedList private:數(shù)據(jù)成員：Node *front, *rear;表頭和表尾指針Node *prevPtr, *currPtr;記錄表當前遍歷位置的指針，由插入和刪除操作更新int size; /表中的元素個數(shù)int position; /當前元素在表中的位置序號。由函數(shù)reset使用/函數(shù)成員

19、：/生成新結點，數(shù)據(jù)域為item，指針域為ptrNextNode *newNode(const T &item,Node *ptrNext=NULL);/釋放結點void freeNode(Node *p);/將鏈表L拷貝到當前表(假設當前表為空)。被拷貝構造函數(shù)、operator =調用void copy(const LinkedListvT & L);public:LinkedList(); / 構造函數(shù)LinkedList(const LinkedListvT& L);拷貝構造函數(shù)LinkedList();/ 析構函數(shù)LinkedListvT& operator = (const Lin

20、kedListvT& L); /重載賦值運算符int getSize() const;/返回鏈表中元素個數(shù)bool isEmpty() const; / 鏈表是否為空void reset(int pos = 0);初始化游標的位置void next();使游標移動到下一個結點bool endOfList() const; / 游標是否到了鏈尾int currentPosition(void) const; /返回游標當前的位置void insertFront(const T & item);/ 在表頭插入結點void insertRear(const T & item);/ 在表尾添加結點vo

21、id insertAt(const T & item);/在當前結點之前插入結點void insertAfter(const T &item); /在當前結點之后插入結點T deleteFront();/ 刪除頭結點void deleteCurrent(); / 刪除當前結點T& data();/返回對當前結點成員數(shù)據(jù)的引用const T & data() const;返回對當前結點成員數(shù)據(jù)的常引用/清空鏈表：釋放所有結點的內存空間。被析構函數(shù)、operator=調用void clear();#endif LINKEDLIST H9_7.cpp#include viostream#includ

22、e LinkedList.h using namespace std;int main() LinkedListvint list;II輸入10個整數(shù)依次向表頭插入for (int i = 0; i item;list.insertFront(item);II輸出鏈表cout List:;list.reset();/輸出各結點數(shù)據(jù)，直到鏈表尾while (!list.endOfList() cout vv list.data() key;查找并刪除結點list.reset();while (!list.endOfList() if (list.data() = key) list.delete

23、Current();list.next();II輸出鏈表cout vv List:;list.reset();II輸出各結點數(shù)據(jù)，直到鏈表尾while (!list.endOfList() cout vv list.data() vv ;list.next(); II使游標指向下一個結點cout vv endl;return 0;9_6棧的應用（一個簡單的整數(shù)計算器）/Stack.h#ifndef STACK_H #define STACK_H #include 模板的定義，SIZE為棧的大小template vclass T, int SIZE = 50 class Stack privat

24、e:T listSIZE; 數(shù)組，用于存放棧的元素int top; /棧頂位置(數(shù)組下標)public:Stack(); /構造函數(shù)，初始化棧void push(const T &item); 將元素 item 壓入棧T pop(); 將棧頂元素彈出棧void clear(); 將棧清空const T &peek() const; / 訪問棧頂元素 bool isEmpty() const; / 測試是否棧滿 bool isFull() const;/測試是否棧空;/模板的實現(xiàn)template vclass T, int SIZEStackvT, SIZE:Stack() : top(-1)

25、/ 構造函數(shù)，棧頂初始化為 -1template vclass T, int SIZEvoid StackvT, SIZE:push(const T &item) /將元素 item 壓入棧assert(!isFull();/ 如果棧滿了，則報錯list+top = item; /將新元素壓入棧頂template vclass T, int SIZET StackvT, SIZE:pop() 將棧頂元素彈出棧assert(!isEmpty();/如果棧為空，則報錯return listtop-; /返回棧頂元素，并將其彈出棧頂template vclass T, int SIZE const

26、T &StackvT, SIZE:peek() const / 訪問棧頂元素assert(!isEmpty();/如果棧為空，則報錯return listtop;/返回棧頂元素template vclass T, int SIZEbool StackvT, SIZE:isEmpty() const / 測試棧是否空return top = -1;template bool StackvT, SIZE:isFull() const / 測試是否棧滿 return top = SIZE - 1;template vclass T, int SIZEvoid StackvT, SIZE:clear(

27、) / 清空棧top = -1;#endif STACK_H/Calculators#ifndef CALCULATOR_H#define CALCULATOR#include Stack.h /包含棧類模板定義文件class Calculator /計算器類private:Stackvdouble s; / 操作數(shù)棧void enter(double num);將操作數(shù) num 壓入棧連續(xù)將兩個操作數(shù)彈出棧，放在opndl和opnd2中bool getTwoOperands(double &opnd1, double &opnd2);void compute(char op); /執(zhí)行由操作

28、符 op指定的運算 public:void run();/運行計算器程序void clear(); 清空操作數(shù)棧;#endif /CALCULATOR#include Calculator.h#include viostream#include vsstream#include vcmathusing namespace std;void Calculator:enter(double num) /將操作數(shù) num 壓入棧 s.push(num);連續(xù)將兩個操作數(shù)彈出棧，放在opndl和opnd2中如果棧中沒有兩個操作數(shù)，則返回False并輸出相關信息bool Calculator:getTw

29、oOperands(double &opnd1, 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 op) /執(zhí)行運算 double operand1, operand2;將兩個

30、操作數(shù)彈出棧bool result = getTwoOperands(operand1, operand2);if (result) /如果成功，執(zhí)行運算并將運算結果壓入棧switch(op) case +:s.push(operand2 + operand; break;case -:s.push(operand2 - operand1); break;case *:s.push(operand2 * operand1); break;case /:if (operand1 = 0) /檢查除數(shù)是否為 0cerr Divided by 0! endl; s.clear(); /除數(shù)為0時清空

31、棧 else s.push(operand2 / operandl);break;case A:s.push(pow(operand2, operandl); break;default:cerr Unrecognized operator! endl; break;cout vv = s.peek() result; return result;void Calculator:run() II讀入并處理后綴表達式string str;while (cin str, str != q) switch(strO) case c:s.clear(); II遇c清空操作數(shù)棧break;case -:

32、 遇-需判斷是減號還是負號if (str.size() 1)若字符串長度1，說明讀到的是負數(shù)的負號enter(stringToDouble(str); II將字符串轉換為整數(shù)，壓入棧 elsecompute(str0);II若是減號則執(zhí)行計算break;case +: 遇到其它操作符時case *:case I: case A: compute(str0);執(zhí)行計算break;default: 若讀入的是操作數(shù)，轉換為整型后壓入棧enter(stringToDouble(str); break;void Calculator:clear() / 清空操作數(shù)棧s.clear();9_9.cpp#

33、include Calculator.hint main() Calculator c; c.run(); return 0;9_7隊列類模板舉例/Queue.h#ifndef QUEUE_H#define QUEUE_H#include /類模板的定義template class Queue private:int front, rear, count; /隊頭指針、隊尾指針、元素個數(shù)T listSIZE; /隊列元素數(shù)組public:Queue();/構造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)void insert(const T &item); /新元素入隊T remove(); /元

34、素出隊void clear(); / 清空隊列const T &getFront() const; /訪問隊首元素/測試隊列狀態(tài)int getLength() const; /求隊列長度(元素個數(shù))bool isEmpty() const; / 判隊隊列空否bool isFull() const;/ 判斷隊列滿否;/構造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)template QueuevT, SIZE:Queue() : front(O), rear(O), count(0) template vclass T, int SIZEvoid QueuevT, SIZE:insert (cons

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

36、余以實現(xiàn)循環(huán)隊列 return listtemp; /返回首元素值template vclass T, int SIZEconst T &Queue:getFront() const / 訪問隊列首元素(返回其值) return listfront;template vclass T, int SIZEint QueuevT, SIZE:getLength() const / 返回隊列元素個數(shù)return count;template vclass T, int SIZEbool QueuevT, SIZE:isEmpty() const / 測試隊空否return count = 0;tem

37、plate vclass T, int SIZEbool QueuevT, SIZE:isFull() const / 測試隊滿否return count = SIZE;template vclass T, int SIZEvoid QueuevT, 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_H/用直接插入排序法對數(shù)組A中的元素進行升序排列template vclass Tvoid inser

38、tionSort(T a, int n) int i, j;T temp;將下標為1n-1的元素逐個插入到已排序序列中適當?shù)奈恢胒or (int i = 1; i 0 & temp = aj - 1時，j便是應插入的位置。/若達到j = 0 ,則0是應插入的位置。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 vo

39、id mySwap(T &x, T &y) T temp = x;x = y;y = temp;II用選擇法對數(shù)組a的n個元素進行排序template vclass Tvoid selectionSort(T a, int n) for (int i = 0; i v n - 1; i+) int leastindex = i; II最小元素之下標初值設為ifor (int j = i + 1; j v n; j+) II在元素ai + 1.an - 1中逐個比較顯出最小值 if (aj v aleastlndex) IIsmalllndex 始終記錄當前找到的最小值的下標 leastindex = j;mySwap(ai, aleastlndex ); 將這一趟找到的最小元素與ai交換#endif IIHEA