《 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