实验09群体类与群体数据的组织资料

1、海南大学信息科学技术学院实验报告成绩指导教师宇验课程：C+程序设计课内实验谭毓银学号.03姓名-曾悦班级-数学与应用数学2014同组成员：完成日期：2016年6月4日实验09群体类与群体数据的组织(4学时)(第9章 群体类与群体数据的组织)一、实验目的(1) 掌握函数模板与类模板。(2) 了解线性群体与群体数据的组织。二、实验任务9_1求绝对值的函数模板及其应用#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函数模板的示例。#include viostreamusing namespace std;template vclass T /定义函数模板 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 /类模板：实现对任意类型数据进行存取private:T item; / item用于存放任意类型的数据bool haveValue; / haveValue标记item是否已被存入内容public:Store(); /缺省形式(无形参)的构造函数T & getElem();/提取数据函数void putElem(const T &x);/ 存入数据函数;/以下实现各成员函数。template /缺省构造函数的实现Stor

4、e:Store(): haveValue(false) template 提取数据函数的实现T &Store:getElem() /如试图提取未初始化的数据，则终止程序if (!haveValue) cout No item present! endl;exit(1); 使程序完全退出，返回到操作系统。return item; 返回item中存放的数据template /存入数据函数的实现void Store:putElem(const T &x) / 将 haveValue 置为 true，表示 item 中已存入数值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未经初始化，在执行函数D.getElement()过程中导致程序终止 return

6、 0;C:Windowssystem32c md. exe aX1!rhe student id is 1000 object D. . . No iten present ?语援任意键继续搜狗拼音输入法全*Ai9_4动态数据类模板示例/Array.h#ifndef ARRAY_H#define ARRAY_H#include vcassert/数组类模板定义template vclass Tclass Array private:T* list;T类型指针，用于存放动态分配的数组内存首地址int size; /数组大小(元素个数)public:Array(int sz = 50);/ 构造函

7、数Array(const Array &a);/ 拷贝构造函数Array();/析构函数Array & operator = (const Array &rhs); /重载=使数组对象可以整体赋值T & operator (int i);/重载，使Array对象可以起到 C+普通数组的作用const T & operator (int i) const; /运算符的 const版本operator T * ();/重载到T*类型的转换，使 Array对象可以起到 C+普通数组的作用operator const T * () const; /到T*类型转换操作符的const版本int getSi

8、ze() const;/ 取数组的大小 void resize(int sz); /修改数组的大小；/构造函数template vclass TArrayvT:Array(int sz) assert(sz = 0);/sz为数组大小(元素个数)，应当非负size = sz; /将元素个数赋值给变量sizelist = new T size; /动态分配 size个T类型的元素空间析构函数template vclass T Array:Array() delete list;/拷贝构造函数template vclass T Array:Array(const Array &a) /从对象x取得

9、数组大小，并赋值给当前对象的成员size = a.size;/为对象申请内存并进行出错检查list = new Tsize; /动态分配 n个T类型的元素空间从对象X复制数组元素到本对象for (int i = 0; i v size; i+)listi = a.listi;/重载=运算符，将对象rhs赋值给本对象。实现对象之间的整体赋值template vclass TArrayvT &ArrayvT:operator = (const ArrayvT & rhs) if (&rhs != this) 如果本对象中数组大小与rhs不同，则删除数组原有内存，然后重新分配if (size !=

10、rhs.size) delete list;/删除数组原有内存size = rhs.size;/设置本对象的数组大小list = new Tsize; /重新分配 n个元素的内存从对象X复制数组元素到本对象for (int i = 0; i v size; i+)Iisti = rhs.listi;return *this; /返回当前对象的引用/重载下标运算符，实现与普通数组一样通过下标访问元素，并且具有越界检查功能 template vclass TT &ArrayvT:operato 叩(int n) assert(n = 0 & n size); /检查下标是否越界 return li

11、stn;/返回下标为n的数组元素template const T &Array:operator (int n) const assert(n = 0 & n size); /检查下标是否越界 return listn;/返回下标为n的数组元素/重载指针转换运算符，将Array类的对象名转换为 T类型的指针，/指向当前对象中的私有数组。因而可以象使用普通数组首地址一样使用Array类的对象名template Array:operator T * () return list;返回当前对象中私有数组的首地址template Array:operator const T * () const re

12、turn list;返回当前对象中私有数组的首地址/取当前数组的大小template int ArrayvT:getSize() const return size;/将数组大小修改为sztemplate vclass Tvoid Array:resize(int sz) assert(sz = 0);/检查sz是否非负if (sz = size) 如果指定的大小与原有大小一样，什么也不做return;T* newList = new T sz;/申请新的数组内存int n = (sz size) ? sz : size; /将 sz与 size 中较小的一个赋值给n/将原有数组中前 n个元素

13、复制到新数组中for (int i = 0; i n; i+)newListi = listi;delete list;/删除原数组list = newList; / 使 list指向新数组size = sz; /更新 size#endif ARRAY_H9_4.cpp#include #include #include Array.h using namespace std;int main() Array a(10); /用来存放质数的数组，初始状态有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是否能被比它小的质数整除bool isPrime = true;for (int j = 0; j count; j+)if (i % aj = 0) 若i被aj整除，说明i不是质数 isPrime = false;break;把i写入质数表中if (isPrime) /如果质数表满了，将其空间加倍if (count = a.getSize()a.resize(count * 2); acount+ = i;for (int i = 0; i count; i+) / 输出质数cout setw(8) ai;cout =

15、2 as 23i膏援任意键继统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; /数据域Node (const T & data, Node *next = 0);/ 构造函数void insertAfter(Node *p);/在本结点之后插入一个同类结点pNode *deleteAfter

16、();删除本结点的后继结点，并返回其地址Node *nextNode();获取后继结点的地址const Node *nextNode() const;/ 获取后继结点的地址;/类的实现部分/构造函数，初始化数据和指针成员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:数据成员：Node *front, *rear;表头和表尾指针Node *prevPtr, *currPtr;记录表当前遍历位置的指针，由插入和删除操作更新int size; /表中的元素个数int position; /当前元素在表中的位置序号。由函数reset使用/函数成员

19、：/生成新结点，数据域为item，指针域为ptrNextNode *newNode(const T &item,Node *ptrNext=NULL);/释放结点void freeNode(Node *p);/将链表L拷贝到当前表(假设当前表为空)。被拷贝构造函数、operator =调用void copy(const LinkedListvT & L);public:LinkedList(); / 构造函数LinkedList(const LinkedListvT& L);拷贝构造函数LinkedList();/ 析构函数LinkedListvT& operator = (const Lin

20、kedListvT& L); /重载赋值运算符int getSize() const;/返回链表中元素个数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();/返回对当前结点成员数据的引用const T & data() const;返回对当前结点成员数据的常引用/清空链表：释放所有结点的内存空间。被析构函数、operator=调用void clear();#endif LINKEDLIST H9_7.cpp#include viostream#includ

22、e LinkedList.h using namespace std;int main() LinkedListvint list;II输入10个整数依次向表头插入for (int i = 0; i item;list.insertFront(item);II输出链表cout List:;list.reset();/输出各结点数据，直到链表尾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输出各结点数据，直到链表尾while (!list.endOfList() cout vv list.data() vv ;list.next(); II使游标指向下一个结点cout vv endl;return 0;9_6栈的应用（一个简单的整数计算器）/Stack.h#ifndef STACK_H #define STACK_H #include 模板的定义，SIZE为栈的大小template vclass T, int SIZE = 50 class Stack privat

24、e:T listSIZE; 数组，用于存放栈的元素int top; /栈顶位置(数组下标)public:Stack(); /构造函数，初始化栈void push(const T &item); 将元素 item 压入栈T pop(); 将栈顶元素弹出栈void clear(); 将栈清空const T &peek() const; / 访问栈顶元素 bool isEmpty() const; / 测试是否栈满 bool isFull() const;/测试是否栈空;/模板的实现template vclass T, int SIZEStackvT, SIZE:Stack() : top(-1)

25、/ 构造函数，栈顶初始化为 -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; / 操作数栈void enter(double num);将操作数 num 压入栈连续将两个操作数弹出栈，放在opndl和opnd2中bool getTwoOperands(double &opnd1, double &opnd2);void compute(char op); /执行由操作

28、符 op指定的运算 public:void run();/运行计算器程序void clear(); 清空操作数栈;#endif /CALCULATOR#include Calculator.h#include viostream#include vsstream#include vcmathusing namespace std;void Calculator:enter(double num) /将操作数 num 压入栈 s.push(num);连续将两个操作数弹出栈，放在opndl和opnd2中如果栈中没有两个操作数，则返回False并输出相关信息bool Calculator:getTw

29、oOperands(double &opnd1, double & opnd2) if (s.isEmpty() 检查栈是否空cerr Missing operand! endl; return false;opnd1 = s.pop(); 将右操作数弹出栈 if (s.isEmpty() /检查栈是否空cerr Missing operand! endl; return false;opnd2 = s.pop(); 将左操作数弹出栈 return true;void Calculator:compute(char op) /执行运算 double operand1, operand2;将两个

30、操作数弹出栈bool result = getTwoOperands(operand1, operand2);if (result) /如果成功，执行运算并将运算结果压入栈switch(op) case +:s.push(operand2 + operand; break;case -:s.push(operand2 - operand1); break;case *:s.push(operand2 * operand1); break;case /:if (operand1 = 0) /检查除数是否为 0cerr Divided by 0! endl; s.clear(); /除数为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清空操作数栈break;case -:

32、 遇-需判断是减号还是负号if (str.size() 1)若字符串长度1，说明读到的是负数的负号enter(stringToDouble(str); II将字符串转换为整数，压入栈 elsecompute(str0);II若是减号则执行计算break;case +: 遇到其它操作符时case *:case I: case A: compute(str0);执行计算break;default: 若读入的是操作数，转换为整型后压入栈enter(stringToDouble(str); break;void Calculator:clear() / 清空操作数栈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; /队头指针、队尾指针、元素个数T listSIZE; /队列元素数组public:Queue();/构造函数，初始化队头指针、队尾指针、元素个数void insert(const T &item); /新元素入队T remove(); /元

34、素出队void clear(); / 清空队列const T &getFront() const; /访问队首元素/测试队列状态int getLength() const; /求队列长度(元素个数)bool isEmpty() const; / 判队队列空否bool isFull() const;/ 判断队列满否;/构造函数，初始化队头指针、队尾指针、元素个数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+; /元素个数增1 listrear = item;/向队尾插入元素rear = (rear + 1) % SIZE;/队尾指针增1，用取余运算实现循环队列template vclass T, int SIZET QueuevT, SIZE:remove() 删除队首元素，并返回该元素的值(出队)assert(count != 0);int temp = front; /记录下原先的队首指针count-;/元素个数自减front = (front + 1) % SIZE; /队首指针增1。取

36、余以实现循环队列 return listtemp; /返回首元素值template vclass T, int SIZEconst T &Queue:getFront() const / 访问队列首元素(返回其值) return listfront;template vclass T, int SIZEint QueuevT, SIZE:getLength() const / 返回队列元素个数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直接插入排序函数模板9_11.h#ifndef HEADER_9_11_H#define HEADER_9_11_H/用直接插入排序法对数组A中的元素进行升序排列template vclass Tvoid inser

38、tionSort(T a, int n) int i, j;T temp;将下标为1n-1的元素逐个插入到已排序序列中适当的位置for (int i = 1; i 0 & temp = aj - 1时，j便是应插入的位置。/若达到j = 0 ,则0是应插入的位置。aj = aj - 1;将元素逐个后移，以便找到插入位置时可立即插入。j-;插入位置已找到，立即插入。aj = temp;#endif HEADER 9 11 H9_9直接选择排序函数模板9_12.h#ifndef HEADER_9_12_H #define HEADER_9_12_H/辅助函数：交换x和y的值 template vo

39、id mySwap(T &x, T &y) T temp = x;x = y;y = temp;II用选择法对数组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