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

《 C++ 程序设计》课内实验 谭毓银

03 曾悦 数学与应用数学 2014

16 6 4

实验 09 群体类与群体数据的组织（ 4 学时）

（第 9 章 群体类与群体数据的组织）

一、实验目的

掌握函数模板与类模板。

了解线性群体与群体数据的组织。

二、实验任务

9_1 求绝对值的函数模板及其应用

#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) << endl;

cout << fun(d) << endl;

return 0;

}

1

9_2 函数模板的示例。

#include <iostream>

using namespace std;

template <class T> // 定义函数模板

void outputArray(const T *array, int count){

for (int i = 0; i < count; i++)

cout << array[i] << " ";

cout << endl;

}

int main(){ // 主函数

const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20; int a [A_COUNT] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // 定义 int 数组

double b[B_COUNT] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 }; // 定义 double 数组 char c[C_COUNT] = "Welcome to see you!"; //定义 char 数组 cout << " a array contains:" << endl;

outputArray(a, A_COUNT); // 调用函数模板

cout << " b array contains:" << endl;

outputArray(b, B_COUNT); // 调用函数模板

cout << " c array contains:" << endl;

outputArray(c, C_COUNT); // 调用函数模板

return 0;

}

2

9_3 类模板应用举例。

#include <iostream>

#include <cstdlib>

using namespace std;

结构体 Student struct Student {

int id; //学号

float gpa; // 平均分

};

template <class T>

class Store {//类模板：实现对任意类型数据进行存取

private:

T item; // item 用于存放任意类型的数据

bool haveValue; // haveValue 标记 item 是否已被存入内容

public:

Store(); // 缺省形式（无形参）的构造函数

T &getElem(); // 提取数据函数

void putElem(const T &x); // 存入数据函数

};

//以下实现各成员函数。

template <class T> // 缺省构造函数的实现

Store<T>::Store(): haveValue(false) { }

template <class T> //提取数据函数的实现

T &Store<T>::getElem() {

//如试图提取未初始化的数据，则终止程序

if (!haveValue) {

cout << "No item present!" << endl;

exit(1); //使程序完全退出，返回到操作系统。

}

return item; // 返回 item 中存放的数据

}

template <class T> // 存入数据函数的实现

void Store<T>::putElem(const T &x) {

// 将 haveValue 置为 true ，表示 item 中已存入数值 haveValue = true;

item = x; // 将 x 值存入 item

}

int main() {

Store<int> s1, s2;

s1.putElem(3);

s2.putElem(-7);

cout << s1.getElem() << " " << s2.getElem() << endl;

3

Student g = { 1000, 23 };

Store<Student> s3;

s3.putElem(g);

cout << "The student id is " << s3.getElem().id << endl;

Store<double> d;

cout << "Retrieving object D... ";

cout << d.getElem() << endl;

//由于 d 未经初始化 ,在执行函数 D.getElement() 过程中导致程序终止

return 0;

}

9_4 动态数据类模板示例

//Array.h

#ifndef ARRAY_H

#define ARRAY_H

#include <cassert>

//数组类模板定义

template <class T>

class Array {

private:

T* list; //T 类型指针，用于存放动态分配的数组内存首地址

int size; // 数组大小（元素个数）

public:

Array(int sz = 50); //构造函数

Array(const Array<T> &a); // 拷贝构造函数

~Array(); //析构函数

Array<T> & operator = (const Array<T> &rhs); // 重载 "=" 使数组对象可以整体赋

值

T & operator [] (int i); // 重载 "[]" ，使 Array 对象可以起到 C++ 普通数组的作用

const T & operator [] (int i) const; //"[]" 运算符的 const 版本

operator T * (); // 重载到 T* 类型的转换，使 Array 对象可以起到 C++ 普通数组

的作用

4

operator const T * () const; //到 T* 类型转换操作符的 const版本 int getSize() const; // 取数组的大小 void resize(int sz); // 修改数组的大小

};

//构造函数

template <class T>

Array<T>::Array(int sz) {

assert(sz >= 0); //sz 为数组大小（元素个数） ，应当非负 size = sz; // 将元素个数赋值给变量 size

list = new T [size]; // 动态分配 size 个 T 类型的元素空间

}

//析构函数

template <class T>

Array<T>::~Array() {

delete [] list;

}

//拷贝构造函数

template <class T>

Array<T>::Array(const Array<T> &a) {

//从对象 x 取得数组大小，并赋值给当前对象的成员

size = a.size;

//为对象申请内存并进行出错检查

list = new T[size]; // 动态分配 n 个 T 类型的元素空间

//从对象 X 复制数组元素到本对象

for (int i = 0; i < size; i++)

list[i] = a.list[i];

}

//重载 "=" 运算符，将对象 rhs 赋值给本对象。实现对象之间的整体赋值 template <class T>

Array<T> &Array<T>::operator = (const Array<T>& rhs) {

if (&rhs != this) {

//如果本对象中数组大小与 rhs 不同，则删除数组原有内存，然后重新分配

if (size != rhs.size) {

delete [] list; //删除数组原有内存

size = rhs.size; //设置本对象的数组大小

list = new T[size]; //重新分配 n 个元素的内存

}

//从对象 X 复制数组元素到本对象

for (int i = 0; i < size; i++)

5

list[i] = rhs.list[i];

}

return *this; //返回当前对象的引用

}

//重载下标运算符，实现与普通数组一样通过下标访问元素，并且具有越界检查功能 template <class T>

T &Array<T>::operator[] (int n) {

assert(n >= 0 && n < size); //检查下标是否越界

return list[n]; // 返回下标为 n 的数组元素

}

template <class T>

const T &Array<T>::operator[] (int n) const {

assert(n >= 0 && n < size); //检查下标是否越界

return list[n]; // 返回下标为 n 的数组元素

}

//重载指针转换运算符，将 Array 类的对象名转换为 T 类型的指针，

//指向当前对象中的私有数组。

//因而可以象使用普通数组首地址一样使用 Array 类的对象名

template <class T>

Array<T>::operator T * () {

return list; //返回当前对象中私有数组的首地址

}

template <class T>

Array<T>::operator const T * () const {

return list; //返回当前对象中私有数组的首地址

}

//取当前数组的大小

template <class T>

int Array<T>::getSize() const {

return size;

}

将数组大小修改为 sz

template <class T>

void Array<T>::resize(int sz) {

assert(sz >= 0); // 检查 sz 是否非负

if (sz == size) //如果指定的大小与原有大小一样，什么也不做

return;

T* newList = new T [sz]; //申请新的数组内存

6

int n = (sz < size) ? sz : size; //将 sz 与 size 中较小的一个赋值给 n

//将原有数组中前 n 个元素复制到新数组中

for (int i = 0; i < n; i++)

newList[i] = list[i];

delete[] list; // 删除原数组

list = newList; // 使 list 指向新数组

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); // 用来存放质数的数组，初始状态有 10 个元素。

int count = 0;

int n;

cout << "Enter a value >= 2 as upper limit for prime numbers: "; cin >> n;

for (int i = 2; i <= n; i++) {

//检查 i 是否能被比它小的质数整除

bool isPrime = true;

for (int j = 0; j < count; j++)

if (i % a[j] == 0) { //若 i 被 a[j] 整除，说明 i 不是质数

isPrime = false;

break;

}

//把 i 写入质数表中

if (isPrime) {

如果质数表满了，将其空间加倍

if (count == a.getSize())

a.resize(count * 2);

a[count++] = i;

}

}

for (int i = 0; i < count; i++) // 输出质数

cout << setw(8) << a[i];

cout << endl;

7

return 0;

}

9_5 链表类应用案例

//Node.h

#ifndef NODE_H

#define NODE_H

//类模板的定义

template <class T>

class Node {

private:

Node<T> *next; // 指向后继结点的指针

public:

T data; // 数据域

Node (const T &data, Node<T> *next = 0); // 构造函数

void insertAfter(Node<T> *p); // 在本结点之后插入一个同类结点 p

Node<T> *deleteAfter(); //删除本结点的后继结点，并返回其地址

Node<T> *nextNode(); //获取后继结点的地址

const Node<T> *nextNode() const; //获取后继结点的地址

};

//类的实现部分

//构造函数，初始化数据和指针成员

template <class T>

Node<T>::Node(const T& data, Node<T> *next/* = 0 */) : data(data), next(next) { }

//返回后继结点的指针

template <class T>

Node<T> *Node<T>::nextNode() {

return next;

}

//返回后继结点的指针

8

template <class T>

const Node<T> *Node<T>::nextNode() const {

return next;

}

//在当前结点之后插入一个结点 p

template <class T>

void Node<T>::insertAfter(Node<T> *p) {

p->next = next; //p 结点指针域指向当前结点的后继结点

next = p; //当前结点的指针域指向 p

}

//删除当前结点的后继结点，并返回其地址

template <class T>

Node<T> *Node<T>::deleteAfter() {

Node<T> *tempPtr = next; //将欲删除的结点地址存储到 tempPtr 中 if (next == 0) //如果当前结点没有后继结点，则返回空指针

return 0;

next = tempPtr->next; // 使当前结点的指针域指向 tempPtr 的后继结点

return tempPtr; //返回被删除的结点的地址

}

#endif //NODE_H

// LinkedList.h

#ifndef LINKEDLIST_H

#define LINKEDLIST_H

#include "Node.h"

template <class T>

class LinkedList {

private:

//数据成员：

Node<T> *front, *rear; //表头和表尾指针

Node<T> *prevPtr, *currPtr; //记录表当前遍历位置的指针， 由插入和删除操作

更新

int size; // 表中的元素个数

int position; //当前元素在表中的位置序号。由函数 reset 使用

//函数成员：

//生成新结点，数据域为 item，指针域为 ptrNext

Node<T> *newNode(const T &item,Node<T> *ptrNext=NULL);

//释放结点

9

void freeNode(Node<T> *p);

//将链表 L 拷贝到当前表（假设当前表为空） 。

//被拷贝构造函数、 operator = 调用

void copy(const LinkedList<T>& L);

public:

LinkedList(); // 构造函数

LinkedList(const LinkedList<T> &L); //拷贝构造函数

~LinkedList(); // 析构函数

LinkedList<T> & operator = (const LinkedList<T> &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); // 在表尾添加结点

void insertAt(const T &item); // 在当前结点之前插入结点

void insertAfter(const T &item); // 在当前结点之后插入结点

T deleteFront(); // 删除头结点

void deleteCurrent(); // 删除当前结点

T& data(); //返回对当前结点成员数据的引用

const T& data() const; //返回对当前结点成员数据的常引用

//清空链表：释放所有结点的内存空间。被析构函数、 operator= 调用

void clear();

};

#endif //LINKEDLIST_H

//9_7.cpp

#include <iostream>

#include "LinkedList.h"

using namespace std;

int main() {

LinkedList<int> list;

10

//输入 10 个整数依次向表头插入

for (int i = 0; i < 10; i++) {

int item;

cin >> item;

list.insertFront(item);

}

//输出链表

cout << "List: ";

list.reset();

//输出各结点数据，直到链表尾

while (!list.endOfList()) {

cout << list.data() << " ";

list.next(); // 使游标指向下一个结点

}

cout << endl;

//输入需要删除的整数

int key;

cout << "Please enter some integer needed to be deleted: "; cin >> key;

//查找并删除结点

list.reset();

while (!list.endOfList()) {

if (list.data() == key)

list.deleteCurrent();

list.next();

}

//输出链表

cout << "List: ";

list.reset();

//输出各结点数据，直到链表尾

while (!list.endOfList()) {

cout << list.data() << " ";

list.next(); // 使游标指向下一个结点

}

cout << endl;

return 0;

}

11

// 如果栈为空，则报错

9_6 栈的应用（一个简单的整数计算器）

//Stack.h

#ifndef STACK_H

#define STACK_H

#include <cassert>

//模板的定义， SIZE 为栈的大小

template <class T, int SIZE = 50>

class Stack {

private:

T list[SIZE]; //数组，用于存放栈的元素

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 <class T, int SIZE>

Stack<T, SIZE>::Stack() : top(-1) { } // 构造函数，栈顶初始化为 -1

template <class T, int SIZE>

void Stack<T, SIZE>::push(const T &item) { //将元素 item 压入栈 assert(!isFull()); // 如果栈满了，则报错

list[++top] = item; // 将新元素压入栈顶

}

template <class T, int SIZE>

T Stack<T, SIZE>::pop() { // 将栈顶元素弹出栈

assert(!isEmpty()); // 如果栈为空，则报错

return list[top--]; // 返回栈顶元素，并将其弹出栈顶

}

template <class T, int SIZE>

const T &Stack<T, SIZE>::peek() const { // 访问栈顶元素

assert(!isEmpty());

return list[top]; // 返回栈顶元素

12

}

template <class T, int SIZE>

bool Stack<T, SIZE>::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

#include "Stack.h" // 包含栈类模板定义文件

class Calculator { //计算器类

private:

Stack<double> s; // 操作数栈

void enter(double num); //将操作数 num 压入栈

//连续将两个操作数弹出栈，放在 opnd1 和 opnd2 中

bool getTwoOperands(double &opnd1, double &opnd2);

void compute(char op); //执行由操作符 op 指定的运算

public:

void run(); // 运行计算器程序

void clear(); //清空操作数栈

};

#endif //CALCULATOR_H

#include "Calculator.h"

#include <iostream>

#include <sstream>

#include <cmath>

using namespace std;

void Calculator::enter(double num) { // 将操作数 num 压入栈 s.push(num);

13

}

//连续将两个操作数弹出栈，放在 opnd1 和 opnd2 中

//如果栈中没有两个操作数，则返回 False 并输出相关信息

bool Calculator::getTwoOperands(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;

bool result = getTwoOperands(operand1, operand2); //将两个操作数弹出栈

if (result) { //如果成功，执行运算并将运算结果压入栈

switch(op) {

case '+':

s.push(operand2 + operand1);

break;

case '-':

s.push(operand2 - operand1);

break;

case '*':

s.push(operand2 * operand1);

break;

case '/':

if (operand1 == 0) { // 检查除数是否为 0

cerr << "Divided by 0!" << endl;

s.clear(); // 除数为 0 时清空栈

} else

s.push(operand2 / operand1);

break;

case '^':

s.push(pow(operand2, operand1));

break;

default:

14

cerr << "Unrecognized operator!" << endl;

break;

}

cout << "= " << s.peek() << " "; // 输出本次运算结果

} else

s.clear(); // 操作数不够，清空栈

}

//工具函数，用于将字符串转换为实数

inline double stringToDouble(const string &str) {

istringstream stream(str); //字符串输入流

double result;

stream >> result;

return result;

}

void Calculator::run() { // 读入并处理后缀表达式

string str;

while (cin >> str, str != "q") {

switch(str[0]) {

case 'c':

s.clear(); // 遇 'c'清空操作数栈

break;

case '-': //遇 '-' 需判断是减号还是负号

if (str.size() > 1) //若字符串长度 >1，说明读到的是负数的负号 enter(stringToDouble(str)); // 将字符串转换为整数，压入栈

else

compute(str[0]); // 若是减号则执行计算

break;

case '+': //遇到其它操作符时

case '*':

case '/':

case '^':

compute(str[0]); //执行计算

break;

default: //若读入的是操作数，转换为整型后压入栈

enter(stringToDouble(str));

break;

}

}

}

15

void Calculator::clear() { // 清空操作数栈

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>

//类模板的定义

template <class T, int SIZE = 50>

class Queue {

private:

int front, rear, count; // 队头指针、队尾指针、元素个数

T list[SIZE]; //队列元素数组

public:

Queue(); // 构造函数，初始化队头指针、队尾指针、元素个数

void insert(const T &item); //新元素入队

T remove(); //元素出队

void clear(); //清空队列

const T &getFront() const; //访问队首元素

//测试队列状态

int getLength() const; // 求队列长度（元素个数）

bool isEmpty() const; // 判队队列空否

bool isFull() const; //判断队列满否

};

//构造函数，初始化队头指针、队尾指针、元素个数

template <class T, int SIZE>

Queue<T, SIZE>::Queue() : front(0), rear(0), count(0) { }

template <class T, int SIZE>

16

void Queue<T, SIZE>::insert (const T& item) { //向队尾插入元素（入队）

assert(count != SIZE);

count++; //元素个数增 1

list[rear] = item; // 向队尾插入元素

rear = (rear + 1) % SIZE; //队尾指针增 1，用取余运算实现循环队列

}

template <class T, int SIZE>

T Queue<T, SIZE>::remove() { //删除队首元素，并返回该元素的值（出队）

assert(count != 0);

int temp = front; // 记录下原先的队首指针

count--; // 元素个数自减

front = (front + 1) % SIZE; // 队首指针增 1。取余以实现循环队列 return list[temp]; // 返回首元素值

}

template <class T, int SIZE>

const T &Queue<T, SIZE>::getFront() const { // 访问队列首元素（返回其值）

return list[front];

}

template <class T, int SIZE>

int Queue<T, SIZE>::getLength() const { // 返回队列元素个数 return count;

}

template <class T, int SIZE>

bool Queue<T, SIZE>::isEmpty() const { // 测试队空否

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_H

17

9_8 直接插入排序函数模板

//9_11.h

#ifndef HEADER_9_11_H

#define HEADER_9_11_H

//用直接插入排序法对数组 A 中的元素进行升序排列

template <class T>

void insertionSort(T a[], int n) {

int i, j;

T temp;

//将下标为 1～ n-1 的元素逐个插入到已排序序列中适当的位置 for (int i = 1; i < n; i++) {

//从 a[i - 1] 开始向 a[0]方向扫描各元素 ,寻找适当位置插入 a[i] int j = i;

T temp = a[i];

while (j > 0 && temp < a[j - 1]) {

逐个比较，直到 temp >= a[j - 1] 时， j 便是应插入的位置。

若达到 j == 0 ，则 0 是应插入的位置。

a[j] = a[j - 1]; // 将元素逐个后移，以便找到插入位置时可立即插入。

j--;

}

//插入位置已找到，立即插入。

a[j] = temp;

}

}

#endif //HEADER_9_11_H

9_9 直接选择排序函数模板

//9_12.h

#ifndef HEADER_9_12_H

#define HEADER_9_12_H

//辅助函数：交换 x 和 y 的值

template <class T>

void mySwap(T &x, T &y) {

T temp = x;

x = y;

y = temp;

}

18

//用选择法对数组 a 的 n 个元素进行排序

template <class T>

void selectionSort(T a[], int n) {

for (int i = 0; i < n - 1; i++) {

int leastIndex = i; // 最小元素之下标初值设为 i

for (int j = i + 1; j < n; j++) // 在元素 a[i + 1]..a[n - 1] 中逐个比较显出最小值

if (a[j] < a[leastIndex]) //smallIndex 始终记录当前找到的最小值的下标

leastIndex = j;

mySwap(a[i], a[leastIndex ]); // 将这一趟找到的最小元素与 a[i] 交换

}

}

#endif //HEADER_9_12_H

9_10 起（冒）泡排序函数模板

//9_13.h

#ifndef HEADER_9_13_H

#define HEADER_9_13_H

//辅助函数：交换 x 和 y 的值

template <class T>

void mySwap(T &x, T &y) {

T temp = x;

x = y;

y = temp;

}

//用起泡法对数组 A 的 n 个元素进行排序

template <class T>

void bubbleSort(T a[], int n) {

int i = n - 1; // i 是下一趟需参与排序交换的元素之最大下标

while (i > 0) { // 持续排序过程，直到最后一趟排序没有交换发生，或已达 n - 1 趟

int lastExchangeIndex = 0; // 每一趟开始时，设置交换标志为 0（未交换）

for (int j = 0; j < i; j++) // 每一趟对元素 a[0]..a[i] 进行比较和交换

if (a[j + 1] < a[j]) { // 如果元素 a[j + 1] < a[j] ，交换之

mySwap(a[j], a[j + 1]);

lastExchangeIndex = j; // 记录被交换的一对元素中较小的下标

}

i = lastExchangeIndex; // 将 i 设置为本趟被交换的最后一对元素中较小的下标

}

}

#endif //HEADER_9_13_H

19

9_11 顺序查找函数模板。

//9_14.h

#ifndef HEADER_9_14_H

#define HEADER_9_14_H

用顺序查找法在数组 list 中查找值为 key 的元素

若找到，返回该元素下标，否则返回 -1 template <class T>

int seqSearch(const T list[], int n, const T &key) { for(int i = 0; i < n; i++)

if (list[i] == key) return i;

return -1;

}

#endif //HEADER_9_14_H

9_12 折半查找函数模板。

//9_15.h

#ifndef HEADER_9_15_H

#define HEADER_9_15_H

//用折半查找方法，在元素呈升序排列的数组 list 中查找值为 key 的元素

template <class T>

int binSearch(const T list[], int n, const T &key) {

int low = 0;

int high = n - 1;

while (low <= high) { //low <= high 表示整个数组尚未查找完

int mid = (low + high) / 2; // 求中间元素的下标

if (key == list[mid])

return mid; //若找到 ,返回下标

else if (key < list[mid])

high = mid - 1; //若 key < midvalue 将查找范围缩小到数组的前一半

else

low = mid + 1; //否则将查找范围缩小到数组的后一半

}

return -1; //没有找到返回 -1

}

#endif //HEADER_9_15_H

9_13 综合实例（对个人银行账户管理程序的改进）

20

21