C++语言程序设计第五版 - 郑莉（第九章课后习题）

第9章  群体类和群体数据的组织

9-1 编写程序提示用户输入一个班级中的学生人数 n，再依次提示用户输入 n 个人在课程 A 中的考试成绩，然后计算出平均成绩，显示出来。请使用本书第 9 章中的数组类模板 Array定义浮点型数组存储考试成绩。

//main文件

#include
#include
#include"Array.h"
using namespace std;

int main()
{
    int n;
    double averscore, totalscore = 0;
    cout << "请输入学生人数：";
    cin >> n;
    Array Score(n);
    for (int i = 0; i < n; i++)
    {
    	cout<<"请输入这"<> Score[i];
        totalscore += Score[i];
    }
    averscore = totalscore / n;
    cout << "平均成绩为：" << averscore;
    return 0;
}

//Array.h
#ifndef ARRAY_H
#define ARRAY_H

#include //提供一个assert的宏定义

template //数组类模板定义
class Array {
private:
	T* list;	//T类型指针，用于存放动态分配的数组内存首地址
	int size;	//数组大小（元素个数）
public:
	Array(int sz = 50);			//构造函数
	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 getSize() const;	//取数组的大小
	void resize(int sz);	//修改数组的大小
};

//构造函数
template 
Array::Array(int sz) {
	assert(sz >= 0);	//sz为数组大小（元素个数），应当非负
	size = sz;	// 将元素个数赋值给变量size
	list = new T [size];	//动态分配size个T类型的元素空间
}

//析构函数
template 
Array::~Array() {
	delete [] list;
}

//拷贝构造函数
template 
Array::Array(const Array &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 
Array &Array::operator = (const Array& 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++)
			list[i] = rhs.list[i];
	}
	return *this;	//返回当前对象的引用
}

//重载下标运算符，实现与普通数组一样通过下标访问元素，并且具有越界检查功能
template 
T &Array::operator[] (int n) {
	assert(n >= 0 && n < size);	//检查下标是否越界
	return list[n];			//返回下标为n的数组元素
}

template 
const T &Array::operator[] (int n) const {
	assert(n >= 0 && n < size);	//检查下标是否越界
	return list[n];			//返回下标为n的数组元素
}

//重载指针转换运算符，将Array类的对象名转换为T类型的指针，
//指向当前对象中的私有数组。
//因而可以象使用普通数组首地址一样使用Array类的对象名
template 
Array::operator T * () {
	return list;	//返回当前对象中私有数组的首地址
}

template 
Array::operator const T * () const {
	return list;	//返回当前对象中私有数组的首地址
}

//取当前数组的大小
template 
int Array::getSize() const {
	return size;
}

// 将数组大小修改为sz
template 
void 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个元素复制到新数组中
	for (int i = 0; i < n; i++)
		newList[i] = list[i];
	delete[] list;		//删除原数组
	list = newList;	// 使list指向新数组
	size = sz;	//更新size
}
#endif  //ARRAY_H

9-6 通过对从本章的链表类模板 LinkedList进行组合，编写有序链表类模板 OrderList，添加成员函数insert实现链表元素的有序（递增）插入。声明两个int类型有序链表a 和 b，分别插入 5 个元素，然后把 b 中的元素插入 a 中。

//main.c
#include
#include
#include"LinkedList.h"
using namespace std;

template       
class OrderList:public LinkedList
{
public:
	void insertOrder(const T& item);
};

template
void OrderList::insertOrder(const T& item)
{
	this->reset();
	while (!this->endOfList())
	{
		if(itemdata())
			break;
		this->next();
	}
	this->insertAt(item);
}

int main()
{
	OrderLista;
	a.insertOrder(6);
	a.insertOrder(3);
	a.insertOrder(9);
	a.insertOrder(7);
	a.insertOrder(1);
	OrderListb;
	b.insertOrder(5);
	b.insertOrder(8);
	b.insertOrder(4);
	b.insertOrder(2);
	b.insertOrder(0);
	
	cout<<"输入链表a中的元素为："; 
	a.reset();
	while (!a.endOfList())
	{
		cout<

//LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"

#include
using namespace std;

template 
class LinkedList {
private:
	//数据成员：
	Node *front, *rear;	//表头和表尾指针
	Node *prevPtr, *currPtr;   //记录表当前遍历位置的指针，由插入和删除操作更新
	int size;	//表中的元素个数
	int position;	//当前元素在表中的位置序号。由函数reset使用

	//函数成员：
	//生成新结点，数据域为item，指针域为ptrNext
	Node *newNode(const T &item,Node *ptrNext=NULL);

	//释放结点
	void freeNode(Node *p);

	//将链表L 拷贝到当前表（假设当前表为空）。
	//被拷贝构造函数、operator = 调用
	void copy(const LinkedList& L);

public:
	LinkedList();	//构造函数
	LinkedList(const LinkedList &L);  //拷贝构造函数
	~LinkedList();	//析构函数
	LinkedList & operator = (const LinkedList &L); //重载赋值运算符

	int getSize() const;	//返回链表中元素个数
	bool isEmpty() const;	//链表是否为空

	void reset(int pos = 0);//初始化游标的位置
	void next();	//使游标移动到下一个结点
	bool endOfList() const;	//游标是否到了链尾
	int currentPosition() 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();
};

template 
Node *LinkedList::newNode(const T& item, Node* ptrNext)	//生成新结点
{
	Node *p;
	p = new Node(item, ptrNext);
	if (p == NULL)
	{
		cout << "Memory allocation failure!n";
		exit(1);
	}
	return p;
}

template 
void LinkedList::freeNode(Node *p) //释放结点
{
	delete p;
}

template 
void LinkedList::copy(const LinkedList& L) //链表复制函数
{
	Node *p = L.front;	//P用来遍历L
	int pos;
	while (p != NULL)	//将L中的每一个元素插入到当前链表最后
	{
		insertRear(p->data);
		p = p->nextNode();
	}
	if (position == -1)	//如果链表空,返回
		return;
	//在新链表中重新设置prevPtr和currPtr
	prevPtr = NULL;
	currPtr = front;
	for (pos = 0; pos != position; pos++)
	{
		prevPtr = currPtr;
		currPtr = currPtr->nextNode();
	}
}

template   //构造一个新链表，将有关指针设置为空，size为0，position为-1
LinkedList::LinkedList() : front(NULL), rear(NULL),
prevPtr(NULL), currPtr(NULL), size(0), position(-1)
{}

template 
LinkedList::LinkedList(const LinkedList& L)  //拷贝构造函数
{
	front = rear = NULL;
	prevPtr = currPtr = NULL;
	size = 0;
	position = -1;
	copy(L);
}

template 
LinkedList::~LinkedList()	//析构函数
{
	clear();
}

template 
LinkedList& LinkedList::operator=(const LinkedList& L)//重载"="
{
	if (this == &L)	// 不能将链表赋值给它自身
		return *this;
	clear();
	copy(L);
	return *this;
}

template 
int LinkedList::getSize() const	//返回链表大小的函数
{
	return size;
}

template 
bool LinkedList::isEmpty() const	//判断链表为空否
{
	return size == 0;
}

template 
void LinkedList::reset(int pos)	//将链表当前位置设置为pos
{
	int startPos;
	if (front == NULL)	// 如果链表为空，返回
		return;
	if (pos < 0 || pos > size - 1)	// 如果指定位置不合法，中止程序
	{
		cerr << "Reset: Invalid list position: " << pos << endl;
		return;
	}
	// 设置与遍历链表有关的成员
	if (pos == 0)	// 如果pos为0，将指针重新设置到表头
	{
		prevPtr = NULL;
		currPtr = front;
		position = 0;
	}
	else	// 重新设置 currPtr, prevPtr, 和 position
	{
		currPtr = front->nextNode();
		prevPtr = front;
		startPos = 1;
		for (position = startPos; position != pos; position++)
		{
			prevPtr = currPtr;
			currPtr = currPtr->nextNode();
		}
	}
}

template 
void LinkedList::next()	//将prevPtr和currPtr向前移动一个结点
{
	if (currPtr != NULL)
	{
		prevPtr = currPtr;
		currPtr = currPtr->nextNode();
		position++;
	}
}

template 
bool LinkedList::endOfList() const	// 判断是否已达表尾
{
	return currPtr == NULL;
}

template 
int LinkedList::currentPosition() const  // 返回当前结点的位置
{
	return position;
}

template 
void LinkedList::insertFront(const T& item)   // 将item插入在表头
{
	if (front != NULL)	// 如果链表不空则调用Reset
		reset();
	insertAt(item);	// 在表头插入
}


template 
void LinkedList::insertRear(const T& item)   // 在表尾插入结点
{
	Node *nNode;
	prevPtr = rear;
	nNode = newNode(item);	// 创建新结点
	if (rear == NULL)	// 如果表空则插入在表头
		front = rear = nNode;
	else
	{
		rear->insertAfter(nNode);
		rear = nNode;
	}
	currPtr = rear;
	position = size;
	size++;
}


template 
void LinkedList::insertAt(const T& item)	// 将item插入在链表当前位置
{
	Node *nNode;
	if (prevPtr == NULL)	// 插入在链表头，包括将结点插入到空表中
	{
		nNode = newNode(item, front);
		front = nNode;
	}
	else	// 插入到链表之中. 将结点置于prevPtr之后
	{
		nNode = newNode(item);
		prevPtr->insertAfter(nNode);
	}
	if (prevPtr == rear)	//正在向空表中插入，或者是插入到非空表的表尾
	{
		rear = nNode;	//更新rear
		position = size;	//更新position
	}
	currPtr = nNode;	//更新currPtr
	size++;	//使size增值
}


template 
void LinkedList::insertAfter(const T& item)  // 将item 插入到链表当前位置之后
{
	Node *p;
	p = newNode(item);
	if (front == NULL)	 // 向空表中插入
	{
		front = currPtr = rear = p;
		position = 0;
	}
	else	// 插入到最后一个结点之后
	{
		if (currPtr == NULL)
			currPtr = prevPtr;
		currPtr->insertAfter(p);
		if (currPtr == rear)
		{
			rear = p;
			position = size;
		}
		else
			position++;
		prevPtr = currPtr;
		currPtr = p;
	}
	size++;              // 使链表长度增值
}


template 
T LinkedList::deleteFront()	// 删除表头结点
{
	T item;
	reset();
	if (front == NULL)
	{
		cerr << "Invalid deletion!" << endl;
		exit(1);
	}
	item = currPtr->data;
	deleteCurrent();
	return item;
}


template 
void LinkedList::deleteCurrent()	// 删除链表当前位置的结点
{
	Node *p;
	if (currPtr == NULL)	// 如果表空或达到表尾则出错
	{
		cerr << "Invalid deletion!" << endl;
		exit(1);
	}
	if (prevPtr == NULL)	// 删除将发生在表头或链表之中
	{
		p = front;	// 保存头结点地址
		front = front->nextNode();	//将其从链表中分离
	}
	else	//分离prevPtr之后的一个内部结点，保存其地址
		p = prevPtr->deleteAfter();

	if (p == rear)	// 如果表尾结点被删除
	{
		rear = prevPtr;	//新的表尾是prevPtr
		position--;	//position自减
	}
	currPtr = p->nextNode();	// 使currPtr越过被删除的结点
	freeNode(p);	// 释放结点，并
	size--;	//使链表长度自减
}

template 
T& LinkedList::data()	//返回一个当前结点数值的引用
{
	if (size == 0 || currPtr == NULL)	// 如果链表为空或已经完成遍历则出错
	{
		cerr << "Data: invalid reference!" << endl;
		exit(1);
	}
	return currPtr->data;
}

template 
void LinkedList::clear()	//清空链表
{
	Node *currPosition, *nextPosition;
	currPosition = front;
	while (currPosition != NULL)
	{
		nextPosition = currPosition->nextNode(); //取得下一结点的地址
		freeNode(currPosition);	//删除当前结点
		currPosition = nextPosition;	//当前指针移动到下一结点
	}
	front = rear = NULL;
	prevPtr = currPtr = NULL;
	size = 0;
	position = -1;
}


#endif  //LINKEDLIST_H

//Node.h
#ifndef NODE_H
#define NODE_H

//类模板的定义
template 
class Node {
private:
	Node *next;	//指向后继结点的指针
public:
	T data;	//数据域

	Node (const T &data, Node *next = 0);    //构造函数
	void insertAfter(Node *p);	//在本结点之后插入一个同类结点p
	Node *deleteAfter();	//删除本结点的后继结点，并返回其地址
	Node *nextNode();				 //获取后继结点的地址
	const Node *nextNode() const;	 //获取后继结点的地址
};

//类的实现部分
//构造函数，初始化数据和指针成员
template 
Node::Node(const T& data, Node *next) : data(data), next(next) { }

//返回后继结点的指针
template 
Node *Node::nextNode() {
	return next;
}

//返回后继结点的指针
template 
const Node *Node::nextNode() const {
	return next;
}

//在当前结点之后插入一个结点p
template 
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;	//使当前结点的指针域指向tempPtr的后继结点
	return tempPtr;			//返回被删除的结点的地址
}

#endif //NODE_H

9-10 初始化 int类型数组 datal[]={1，3，5，7，9，11，13，15，17，19，2，4，6，8，10，12，14, 16，18，20}，应用本章的直接插入排序函数模板进行排序。对此函数模板稍做修改，加入输出语句，在每插入一个待排序元素后显示整个数组，观察排序过程中数据的变化，加深对插入排序算法的理解。

#include 
using namespace std;

template
void swapData(T &a,T &b)
{
	T t=a;
    a=b; 
	b=t;
} 

template
void insertSort(T a[],int n)
{
    int i,j,k;
	int tmp;
 
    for(i=1;i=0 && tmp

9-12 初始化 int类型数组 datal[]={1，3，5，7，9，11，13，15，17，19，2，4，6，8，10，12，14， 16，18，20}，应用本章中的直接选择排序函数模板进行排序。对此函数模板稍做修改，加入输出语句，每次从待排序序列中选择一个元素添加到已排序序列后，显示整个数组，观察排序过程中数据的变化，加深对直接选择排序算法的理解。

#include 
using namespace std;

template
void swapData(T &a,T &b)
{
	T t=a;
    a=b; 
	b=t;
} 

template
void selectSort(T a[],int n)
{
    int i, j, k, t;
	int tmp;
 
    for(i=0; i 
9-14 初始化 int类型数组 datal[]={1，3，5，7，9，11，13，15，17，19，2，4，6，8，10，12，14， 16，18，20}，应用本章中的起泡排序函数模板进行排序。对此函数模板稍做修改，加入输出语句，每完成一趟起泡排序后显示整个数组，观察排序过程中数据的变化，加深对起泡排序算法的理解。
 
#include 
using namespace std;
template
//这里使用了冒泡法排序：
void swapData(T &a,T &b)
{
	T t=a;
    a=b; 
	b=t;
} 
    
template
void Bubblesort(T a[], int n)//用冒泡法对数组a的n个元素进行排序
{
	int i = n - 1;

	while (i > 0)
	{
		int lastExchangeIndex = 0;
		for (int j = 0; j < i; j++)
		    if (a[j+1]
 
本专栏为本人大二C++课程的习题作业和一些学习经验的分享，供大家参考学习。如有侵权请立即与我联系，我将及时处理。
 

参考书籍为：C++语言程序设计 第五版 -清华大学出版社- 郑莉,董渊、C++语言程序设计 第五版 -清华大学出版社- 郑莉,董渊（学生用书）
 
编译环境：Visual Studio 2019、Dev-C++