第九章 群体类
清华大学计算机与信息管理中心
郑 莉
C++语言程序设计
前一页 休息 2
本章主要内容
? 线性群体
– 线性群体的概念
– 直接访问群体 --数组类
– 顺序访问群体 --链表类
– 栈类
– 队列类
前一页 休息 3
群体的概念
群体 是指由多个数据元素组成的集
合体。群体可以分为两个大类,线性群
体 和 非线性群体 。
线性群体中的元素按位置排列有序，
可以区分为第一个元素、第二个元素等。
非线性群体不用位置顺序来标识元
素。
前一页 休息 4
线性群体的概念
线性群体中的元素次序与其位置关
系是对应的。在线性群体中，又可按照
访问元素的不同方法分为 直接访问, 顺
序访问 和 索引访问 。
在本章我们只介绍直接访问和顺序
访问。
…
第一个元素 第二个元素 第三个元素 最后一个元素
前一页 休息 5
数组
? 静态数组是具有固定元素个数的群体，
其中的元素可以通过下标直接访问。
– 缺点：大小在编译时就已经确定，在运
行时无法修改。
? 动态数组由一系列位置连续的，任意
数量相同类型的元素组成。
– 优点：其元素个数可在程序运行时改变。
直
接
访
问
线
性
群
体
前一页 休息 6
动态数组类模板
? 数组类模板：
例 9.1（ 9_1.h）
直
接
访
问
线
性
群
体
#ifndef ARRAY_CLASS
#define ARRAY_CLASS
#include <iostream.h>
#include <stdlib.h>
#ifndef NULL
const int NULL = 0;
#endif // NULL
enum ErrorType
{ invalidArraySize,memoryAllocationError,
indexOutOfRange };
char *errorMsg[] =
{ "Invalid array size","Memory allocation error",
"Invalid index,"
};
template <class T>
class Array
{ private:
T* alist;
int size;
void Error(ErrorType error,int badIndex=0) const;
public:
Array(int sz = 50);
Array(const Array<T>& A);
~Array(void);
Array<T>& operator= (const Array<T>& rhs);
T& operator[](int i);
operator T* (void) const;
int ListSize(void) const;
void Resize(int sz);
};
前一页 休息 9
数组类模板部分成员函数的实现
// 构造函数
template <class T>
Array<T>::Array(int sz)
{
if (sz <= 0)
//sz为数组大小（元素个数），若小于 0，则输出错误信息
Error(invalidArraySize);
size = sz; // 将元素个数赋值给变量 size
alist = new T[size]; //动态分配 size个 T类型的元素空间
if (alist == NULL) //如果分配内存不成功，输出错误信息
Error(memoryAllocationError);
}
前一页 休息 10
拷贝构造函数
template <class T>
Array<T>::Array(const Array<T>& X)
{
int n = X.size;
size = n;
alist = new T[n];
if (alist == NULL) Error(memoryAllocationError);
T* srcptr = X.alist; // X.alist是对象 X的数组首地址
T* destptr = alist; // alist是本对象中的数组首地址
while (n--) // 逐个复制数组元素
*destptr++ = *srcptr++;
}
前一页 休息 11
浅拷贝
alist
size
A
A的数组元素
占用的内存
拷贝前
alist
size
A
A的数组元素
占用的内存
拷贝后
alist
size
B
void main(void)
{ Array<int> A(10);
......
Array<int> B(A);
......
}
template <class T>
Array<T>::Array(
const Array<T>& X)
{ size = X.size;
alist= X.alist;
}
前一页 休息 12
深拷贝
alist
size
A
A的数组元素
占用的内存
拷贝前
alist
size
A
A的数组元素
占用的内存
拷贝后
alist
size
B
B的数组元素
占用的内存
前一页 休息 13
重载 "="运算符
template <class T>
Array<T>& Array<T>::operator= (const Array<T>& rhs)
{ int n = rhs.size;
if (size != n)
{ delete [] alist;
alist = new T[n];
if (alist == NULL) Error(memoryAllocationError);
size = n;
}
T* destptr = alist;
T* srcptr = rhs.alist;
while (n--)
*destptr++ = *srcptr++;
return *this;
}
前一页 休息 14
重载下标操作符
template <class T>
T& Array<T>::operator[] (int n)
{
// 检查下标是否越界
if (n < 0 || n > size-1)
Error(indexOutOfRange,n);
// 返回下标为 n的数组元素
return alist[n];
}
前一页 休息 15
为什么有的函数返回引用
? 如果一个函数的返回值是一个对象的
值，它就被认为是一个常量，不能成
为左值。
? 如果返回值为引用。由于引用的实质
就是对象的地址，所以通过引用当然
可以改变对象的值。
前一页 休息 16
重载指针转换操作符
template <class T>
Array<T>::operator T* (void) const
{
// 返回当前对象中私有数组的首地址
return alist;
}
前一页 休息 17
指针转换运算符的作用
#include <iostream.h>
void main()
{
int a[10];
void read(int *p,int n);
read(a,10);
}
void read(int *p,int n)
{
for (int i=0; i<n; i++)
cin>>p[i];
}
void main()
{
Array<int> a(10);
void read(int *p,n);
read(a,10);
}
void read(int *p,int n)
{
for (int i=0; i<n; i++)
cin>>p[i];
}
前一页 休息 18
Array类的应用
? 例 9.2 求范围 2~N中的质数,N在程序
运行时由键盘输入。
直
接
访
问
线
性
群
体
#include <iostream.h>
#include <iomanip.h>
#include "9_1.h"
void main(void)
{
Array<int> A(10);
int n;
int primecount = 0,i,j;
cout << "Enter a value >= 2 as upper limit for
prime numbers,";
cin >> n;
A[primecount++] = 2; // 2是一个质数
for(i = 3; i < n; i++)
{ if (primecount == A.ListSize())
A.Resize(primecount + 10);
if (i % 2 == 0) continue;
j = 3;
while (j <= i/2 && i % j != 0) j += 2;
if (j > i/2) A[primecount++] = i;
}
for (i = 0; i < primecount; i++)
{ cout << setw(5) << A[i];
if ((i+1) % 10 == 0) cout << endl;
}
cout << endl;
}
前一页 休息 21
链表
? 链表是一种动态数据结构，可以用来
表示顺序访问的线性群体。
? 链表是由系列 结点 组成的，结点可以
在运行时动态生成。
? 每一个结点包括 数据域 和指向链表中
下一个结点的 指针 （即下一个结点的
地址）。如果链表每个结点中只有一
个指向后继结点的指针，则该链表称
为单链表。
顺
序
访
问
线
性
群
体
前一页 休息 22
单链表
顺
序
访
问
线
性
群
体
data1 data2 data3 datan NULL…
head rear
前一页 休息 23
单链表的结点类模板 (例 9-3)
template <class T>
class Node
{ private:
Node<T> *next;
public:
T data;
Node(const T& item,Node<T>* ptrnext = NULL);
void InsertAfter(Node<T> *p);
Node<T> *DeleteAfter(void);
Node<T> *NextNode(void) const;
};
顺
序
访
问
线
性
群
体
前一页 休息 24
在结点之后插入一个结点
顺
序
访
问
线
性
群
体
data1 data2 …
p data
…
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
//p节点指针域指向当前节点的后继节点
p->next = next;
next = p; //当前节点的指针域指向 p
}
前一页 休息 25
删除结点之后的结点
顺
序
访
问
线
性
群
体
data1 data2 data3 ……
Node<T> *Node<T>::DeleteAfter(void)
{
Node<T> *tempPtr = next;
if (next == NULL)
return NULL;
next = tempPtr->next;
return tempPtr;
}
tempPtr
前一页 休息 26
链表的基本操作
? 生成结点
? 输出链表
? 查找结点
? 插入结点
? 删除结点
? 清空链表
顺
序
访
问
线
性
群
体
前一页 休息 27
实现链表操作函数 (例 9-4)
#ifndef NODE_LIBRARY
#define NODE_LIBRARY
#include <iostream.h>
#include <stdlib.h>
#include "9_3.h"
顺
序
访
问
线
性
群
体
// 生成节点
template <class T>
Node<T> *GetNode(const T& item,
Node<T> *nextPtr = NULL)
{ Node<T> *newNode;
newNode = new Node<T>(item,nextPtr);
if (newNode == NULL)
{
cerr << "Memory allocation failure!" << endl;
exit(1);
}
return newNode;
}
enum AppendNewline {noNewline,addNewline};
// 输出链表
template <class T>
void PrintList(Node<T> *head,
AppendNewline addnl = noNewline)
{ Node<T> *currPtr = head;
while(currPtr != NULL)
{ if(addnl == addNewline)
cout << currPtr->data << endl;
else
cout << currPtr->data << " ";
currPtr = currPtr->NextNode();
}
}
//查找节点
template <class T>
int Find(Node<T> *head,T& item,Node<T>* &prevPtr)
{
Node<T> *currPtr = head;
prevPtr = NULL;
while(currPtr != NULL)
{
if (currPtr->data == item) return 1;
prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
return 0;
}
//在表头插入节点
template <class T>
void InsertFront(Node<T>* & head,T item)
{ head = GetNode(item,head); }
//在表尾添加节点
template <class T>
void InsertRear(Node<T>* & head,const T& item)
{ Node<T> *newNode,*currPtr = head;
if (currPtr == NULL) InsertFront(head,item);
else
{ while(currPtr->NextNode() != NULL)
currPtr = currPtr->NextNode();
newNode = GetNode(item);
currPtr->InsertAfter(newNode);
}
}
// 删除链表的第一个节点
template <class T>
void DeleteFront(Node<T>* & head)
{
Node<T> *p = head;
if (head != NULL)
{
head = head->NextNode();
delete p;
}
}
// 删除链表中第一个数据域等于 key的节点
template <class T>
void Delete (Node<T>* & head,T key)
{ Node<T> *currPtr = head,*prevPtr = NULL;
if (currPtr == NULL) return;
while (currPtr != NULL && currPtr->data != key)
{ prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
if (currPtr != NULL)
{ if(prevPtr == NULL) head = head->NextNode();
else
prevPtr->DeleteAfter();
delete currPtr;
}
}
// 在有序链表中插入一个节点
template <class T>
void InsertOrder(Node<T>* & head,T item)
{ Node<T> *currPtr,*prevPtr,*newNode;
prevPtr = NULL;
currPtr = head;
while (currPtr != NULL)
{ if (item < currPtr->data) break;
prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
if (prevPtr == NULL) InsertFront(head,item);
else
{ newNode = GetNode(item);
prevPtr->InsertAfter(newNode);
}
}
//清空链表 --删除链表中的所有节点
template <class T>
void ClearList(Node<T> * &head)
{
Node<T> *currPtr,*nextPtr;
currPtr = head;
while(currPtr != NULL)
{ nextPtr = currPtr->NextNode();
delete currPtr;
currPtr = nextPtr;
}
head = NULL;
}
#endif // NODE_LIBRARY
前一页 休息 36
链表应用举例
? 例 9.5
从键盘输入 10个整数，用这些整数值
作为结点数据，生成一个链表，按顺序输
出链表中结点的数值。然后从键盘输入一
个待查找整数，在链表中查找该整数，若
找到则删除该整数所在的结点（如果出现
多次，全部删除），然后输出删除结点以
后的链表。在程序结束之前清空链表。
9-5.cpp
顺
序
访
问
线
性
群
体
#include <iostream.h>
#include "9_3.h"
#include "9_4.h"
void main(void)
{ Node<int> *head = NULL,*prevPtr,*delPtr;
int i,key,item;
for (i=0;i < 10;i++)
{ cin>>item;
InsertFront(head,item);
}
cout << "List,";
PrintList(head,noNewline);
cout << endl;
cout << "请输入一个需要删除的整数, ";
cin >> key;
prevPtr = head;
while (Find(head,key,prevPtr) != NULL)
{ if(prevPtr == NULL) head = head->NextNode();
else delPtr=prevPtr->DeleteAfter();
delete delPtr;
}
cout << "List,";
PrintList(head,noNewline);
cout << endl;
ClearList(head);
}
前一页 休息 39
链表类模板 (例 9-6)
//9_6.h
#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS
#include <iostream.h>
#include <stdlib.h>
#ifndef NULL
const int NULL = 0;
#endif // NULL
#include "9_3.h"
顺
序
访
问
线
性
群
体
template <class T>
class LinkedList
{ private:
Node<T> *front,*rear;
Node<T> *prevPtr,*currPtr;
int size;
int position;
Node<T> *GetNode(const T& item,
Node<T> *ptrNext=NULL);
void FreeNode(Node<T> *p);
void CopyList(const LinkedList<T>& L);
public:
LinkedList(void);
LinkedList(const LinkedList<T>& L);
~LinkedList(void);
LinkedList<T>& operator=
(const LinkedList<T>& L);
int ListSize(void) const;
int ListEmpty(void) const;
void Reset(int pos = 0);
void Next(void);
int EndOfList(void) 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);
void DeleteAt(void);
T& Data(void);
void ClearList(void);
};
#endif // LINKEDLIST_CLASS
前一页 休息 43
链表类应用举例 (例 9-7)
#include <iostream.h>
#include "9_6.h"
#include "9_6.cpp"
void main(void)
{ LinkedList<int> Link;
int i,key,item;
for (i=0;i < 10;i++)
{ cin>>item;
Link.InsertFront(item);
}
顺
序
访
问
线
性
群
体
cout << "List,";
Link.Reset();
while(!Link.EndOfList())
{
cout <<Link.Data() << " ";
Link.Next();
}
cout << endl;
cout << "请输入一个需要删除的整数, ";
cin >> key;
Link.Reset();
while (!Link.EndOfList())
{ if(Link.Data() == key) Link.DeleteAt();
Link.Next();
}
cout << "List,";
Link.Reset();
while(!Link.EndOfList())
{ cout <<Link.Data() << " ";
Link.Next();
}
cout << endl;
}
前一页 休息 46
特殊的线性群体 —— 栈
栈是只能从一端访问的线性群体，
可以访问的这一端称栈顶，另一端称栈
底。
an
┆
a2
a1
入栈 出栈
栈顶
栈底
前一页 休息 47
栈的应用举例 —— 函数调用特
殊
的
线
性
群
体——
栈
main{}
调 fun(参数 )
结束
fun(参数 )
返回
① ②
⑤
⑦
⑧
参数
当前现场
返回地址
③
⑥
入栈
当前现场
返回地址
出栈
参数
④
出栈
当前现场
返回地址
前一页 休息 48
栈的应用举例 —— 表达式处理
b
a /
a/b+c*d
(a)
t1 +
a/b+c*d
t1=a/b
(b)
d
c
t1
*
+
a/b+c*d
(c)
t3
a/b+c*d
t3=t1+t2
(e)
t2
t1 +
a/b+c*d
t2=c*d
(d)
特
殊
的
线
性
群
体——
栈
前一页 休息 49
栈的基本状态
? 栈空
– 栈中没有元素
? 栈满
– 栈中元素个数达到上限
? 一般状态
– 栈中有元素，但未达到栈满状态
特
殊
的
线
性
群
体——
栈
栈顶
┆
an
┆
a1
a0
入栈 出栈
数组下标
max
n
1
0
一般状态
栈顶
入栈 出栈
数组下标
初始状态（栈空）
max
n
1
0
栈顶amax┆
an
┆
a1
a0
入栈 出栈
数组下标 max
n
1
0
栈满状态
前一页 休息 51
栈的基本操作
? 初始化
? 入栈
? 出栈
? 清空栈
? 访问栈顶元素
? 检测栈的状态（满、空）
特
殊
的
线
性
群
体——
栈
前一页 休息 52
栈类模板 (例 9-8)
//9-8.h
#ifndef STACK_CLASS
#define STACK_CLASS
#include <iostream.h>
#include <stdlib.h>
const int MaxStackSize = 50;
特
殊
的
线
性
群
体——
栈
template <class T>
class Stack
{ private:
T stacklist[MaxStackSize];
int top;
public:
Stack (void);
void Push (const T& item);
T Pop (void);
void ClearStack(void);
T Peek (void) const;
int StackEmpty(void) const;
int StackFull(void) const;
};
//类的实现略
前一页 休息 54
栈的应用
? 例 9.9 一个简单的整数计算器
实现一个简单的整数计算器，能够进
行加、减、乘、除和乘方运算。使用时算
式采用后缀输入法，每个操作数、操作符
之间都以空白符分隔。例如，若要计算
"3+5"则输入 "3 5 +"。乘方运算符用 "^"表
示。每次运算在前次结果基础上进行，若
要将前次运算结果清除，可键入 "c"。当键
入 "q"时程序结束。
? 9-9.h 9-9.cpp
特
殊
的
线
性
群
体——
栈
//9_9.h
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
enum Boolean {False,True};
#include "9_8.h"
class Calculator
{ private:
Stack<int> S;
void Enter(int num);
Boolean GetTwoOperands(int& opnd1,
int& opnd2);
void Compute(char op);
public:
Calculator(void) {}
void Run(void);
void Clear(void);
};
void Calculator::Enter(int num)
{ S.Push(num); }
Boolean Calculator::GetTwoOperands
(int& opnd1,int& opnd2)
{ if (S.StackEmpty())
{ cerr << "Missing operand!" << endl;
return False;
}
opnd1 = S.Pop();
if (S.StackEmpty())
{ cerr << "Missing operand!" << endl;
return False;
}
opnd2 = S.Pop();
return True;
}
void Calculator::Compute(char op)
{ Boolean result;
int operand1,operand2;
result = GetTwoOperands(operand1,operand2);
if (result == True)
{ switch(op)
{ case '+',S.Push(operand2+operand1);
break;
case '-',S.Push(operand2-operand1);
break;
case '*',S.Push(operand2*operand1);
break;
case '/',if (operand1 == 0)
{ cerr << "Divide by 0!" << endl;
S.ClearStack();
}
else
S.Push(operand2/operand1);
break;
case '^',S.Push(pow(operand2,operand1));
break;
}
cout<<'='<<S.Peek()<<' ';
}
else
S.ClearStack();
}
void Calculator::Run(void)
{ char c[20];
while(cin >> c,*c != 'q')
switch(*c)
{ case 'c',S.ClearStack();
break;
case '-':
if (strlen(c)>1) Enter(atoi(c));
else Compute(*c);
break;
case '+':
case '*':
case '/':
case '^':
Compute(*c);
break;
default,
Enter(atoi(c));
break;
}
}
void Calculator::Clear(void)
{ S.ClearStack(); }
//9_9.cpp
#include "9-9.h"
void main(void)
{
Calculator CALC;
CALC.Run();
}
前一页 休息 63
特殊的线性群体 —— 队列
队列是只能向一端添加元素，从另
一端删除元素的线性群体
a1 a2 an-1 an……
队头 队尾
入队出队 a0
前一页 休息 64
队列的基本状态
? 队空
– 队列中没有元素
? 队满
– 队列中元素个数达到上限
? 一般状态
– 队列中有元素，但未达到队满状态
特
殊
的
线
性
群
体——
队
列
a0 a1 an-1 an……
队头 队尾
入队出队
数组下标 0 1 n-1 n max
(一般状态 )
……
队头 队尾
入队出队
数组下标 0 1 n-1 n max
(队空状态 )
a0 a1 an-1 an amax……
队头 队尾
入队出队
数组下标 0 1 n-1 n max
(队满状态 )
元素移动方向
元素移动方向
前一页 休息 66
循环队列
在想象中将数组弯曲成环形，元素
出队时，后继元素不移动，每当队尾达
到数组最后一个元素时，便再回到数组
开头。
特
殊
的
线
性
群
体——
队
列
1
2
3
4
……
m-1
m-2
m-3
0
amam+1
am+2
a3
队头
队尾
a4
am-2
am-3
am-1
队满状态 元素个数 =m
1
2
3
4
……
m-1
m-2
m-3
0
队尾
队头
队空状态 元素个数 =0
队尾
1
2
3
4
……
m-1
m-2
m-3
0
a0a1
a2
a3
队头
一般状态
前一页 休息 68
例 9-10 队列类模板
#ifndef QUEUE_CLASS
#define QUEUE_CLASS
#include <iostream.h>
#include <stdlib.h>
const int MaxQSize = 50;
特
殊
的
线
性
群
体——
队
列
template <class T>
class Queue
{ private:
int front,rear,count;
T qlist[MaxQSize];
public:
Queue (void);
void QInsert(const T& item);
T QDelete(void);
void ClearQueue(void);
T QFront(void) const;
int QLength(void) const;
int QEmpty(void) const;
int QFull(void) const;
};
//成员函数的实现略
前一页 休息 70
作业
? 复习第九章，预习第十章
? 实验九
清华大学计算机与信息管理中心
郑 莉
C++语言程序设计
前一页 休息 2
本章主要内容
? 线性群体
– 线性群体的概念
– 直接访问群体 --数组类
– 顺序访问群体 --链表类
– 栈类
– 队列类
前一页 休息 3
群体的概念
群体 是指由多个数据元素组成的集
合体。群体可以分为两个大类,线性群
体 和 非线性群体 。
线性群体中的元素按位置排列有序，
可以区分为第一个元素、第二个元素等。
非线性群体不用位置顺序来标识元
素。
前一页 休息 4
线性群体的概念
线性群体中的元素次序与其位置关
系是对应的。在线性群体中，又可按照
访问元素的不同方法分为 直接访问, 顺
序访问 和 索引访问 。
在本章我们只介绍直接访问和顺序
访问。
…
第一个元素 第二个元素 第三个元素 最后一个元素
前一页 休息 5
数组
? 静态数组是具有固定元素个数的群体，
其中的元素可以通过下标直接访问。
– 缺点：大小在编译时就已经确定，在运
行时无法修改。
? 动态数组由一系列位置连续的，任意
数量相同类型的元素组成。
– 优点：其元素个数可在程序运行时改变。
直
接
访
问
线
性
群
体
前一页 休息 6
动态数组类模板
? 数组类模板：
例 9.1（ 9_1.h）
直
接
访
问
线
性
群
体
#ifndef ARRAY_CLASS
#define ARRAY_CLASS
#include <iostream.h>
#include <stdlib.h>
#ifndef NULL
const int NULL = 0;
#endif // NULL
enum ErrorType
{ invalidArraySize,memoryAllocationError,
indexOutOfRange };
char *errorMsg[] =
{ "Invalid array size","Memory allocation error",
"Invalid index,"
};
template <class T>
class Array
{ private:
T* alist;
int size;
void Error(ErrorType error,int badIndex=0) const;
public:
Array(int sz = 50);
Array(const Array<T>& A);
~Array(void);
Array<T>& operator= (const Array<T>& rhs);
T& operator[](int i);
operator T* (void) const;
int ListSize(void) const;
void Resize(int sz);
};
前一页 休息 9
数组类模板部分成员函数的实现
// 构造函数
template <class T>
Array<T>::Array(int sz)
{
if (sz <= 0)
//sz为数组大小（元素个数），若小于 0，则输出错误信息
Error(invalidArraySize);
size = sz; // 将元素个数赋值给变量 size
alist = new T[size]; //动态分配 size个 T类型的元素空间
if (alist == NULL) //如果分配内存不成功，输出错误信息
Error(memoryAllocationError);
}
前一页 休息 10
拷贝构造函数
template <class T>
Array<T>::Array(const Array<T>& X)
{
int n = X.size;
size = n;
alist = new T[n];
if (alist == NULL) Error(memoryAllocationError);
T* srcptr = X.alist; // X.alist是对象 X的数组首地址
T* destptr = alist; // alist是本对象中的数组首地址
while (n--) // 逐个复制数组元素
*destptr++ = *srcptr++;
}
前一页 休息 11
浅拷贝
alist
size
A
A的数组元素
占用的内存
拷贝前
alist
size
A
A的数组元素
占用的内存
拷贝后
alist
size
B
void main(void)
{ Array<int> A(10);
......
Array<int> B(A);
......
}
template <class T>
Array<T>::Array(
const Array<T>& X)
{ size = X.size;
alist= X.alist;
}
前一页 休息 12
深拷贝
alist
size
A
A的数组元素
占用的内存
拷贝前
alist
size
A
A的数组元素
占用的内存
拷贝后
alist
size
B
B的数组元素
占用的内存
前一页 休息 13
重载 "="运算符
template <class T>
Array<T>& Array<T>::operator= (const Array<T>& rhs)
{ int n = rhs.size;
if (size != n)
{ delete [] alist;
alist = new T[n];
if (alist == NULL) Error(memoryAllocationError);
size = n;
}
T* destptr = alist;
T* srcptr = rhs.alist;
while (n--)
*destptr++ = *srcptr++;
return *this;
}
前一页 休息 14
重载下标操作符
template <class T>
T& Array<T>::operator[] (int n)
{
// 检查下标是否越界
if (n < 0 || n > size-1)
Error(indexOutOfRange,n);
// 返回下标为 n的数组元素
return alist[n];
}
前一页 休息 15
为什么有的函数返回引用
? 如果一个函数的返回值是一个对象的
值，它就被认为是一个常量，不能成
为左值。
? 如果返回值为引用。由于引用的实质
就是对象的地址，所以通过引用当然
可以改变对象的值。
前一页 休息 16
重载指针转换操作符
template <class T>
Array<T>::operator T* (void) const
{
// 返回当前对象中私有数组的首地址
return alist;
}
前一页 休息 17
指针转换运算符的作用
#include <iostream.h>
void main()
{
int a[10];
void read(int *p,int n);
read(a,10);
}
void read(int *p,int n)
{
for (int i=0; i<n; i++)
cin>>p[i];
}
void main()
{
Array<int> a(10);
void read(int *p,n);
read(a,10);
}
void read(int *p,int n)
{
for (int i=0; i<n; i++)
cin>>p[i];
}
前一页 休息 18
Array类的应用
? 例 9.2 求范围 2~N中的质数,N在程序
运行时由键盘输入。
直
接
访
问
线
性
群
体
#include <iostream.h>
#include <iomanip.h>
#include "9_1.h"
void main(void)
{
Array<int> A(10);
int n;
int primecount = 0,i,j;
cout << "Enter a value >= 2 as upper limit for
prime numbers,";
cin >> n;
A[primecount++] = 2; // 2是一个质数
for(i = 3; i < n; i++)
{ if (primecount == A.ListSize())
A.Resize(primecount + 10);
if (i % 2 == 0) continue;
j = 3;
while (j <= i/2 && i % j != 0) j += 2;
if (j > i/2) A[primecount++] = i;
}
for (i = 0; i < primecount; i++)
{ cout << setw(5) << A[i];
if ((i+1) % 10 == 0) cout << endl;
}
cout << endl;
}
前一页 休息 21
链表
? 链表是一种动态数据结构，可以用来
表示顺序访问的线性群体。
? 链表是由系列 结点 组成的，结点可以
在运行时动态生成。
? 每一个结点包括 数据域 和指向链表中
下一个结点的 指针 （即下一个结点的
地址）。如果链表每个结点中只有一
个指向后继结点的指针，则该链表称
为单链表。
顺
序
访
问
线
性
群
体
前一页 休息 22
单链表
顺
序
访
问
线
性
群
体
data1 data2 data3 datan NULL…
head rear
前一页 休息 23
单链表的结点类模板 (例 9-3)
template <class T>
class Node
{ private:
Node<T> *next;
public:
T data;
Node(const T& item,Node<T>* ptrnext = NULL);
void InsertAfter(Node<T> *p);
Node<T> *DeleteAfter(void);
Node<T> *NextNode(void) const;
};
顺
序
访
问
线
性
群
体
前一页 休息 24
在结点之后插入一个结点
顺
序
访
问
线
性
群
体
data1 data2 …
p data
…
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
//p节点指针域指向当前节点的后继节点
p->next = next;
next = p; //当前节点的指针域指向 p
}
前一页 休息 25
删除结点之后的结点
顺
序
访
问
线
性
群
体
data1 data2 data3 ……
Node<T> *Node<T>::DeleteAfter(void)
{
Node<T> *tempPtr = next;
if (next == NULL)
return NULL;
next = tempPtr->next;
return tempPtr;
}
tempPtr
前一页 休息 26
链表的基本操作
? 生成结点
? 输出链表
? 查找结点
? 插入结点
? 删除结点
? 清空链表
顺
序
访
问
线
性
群
体
前一页 休息 27
实现链表操作函数 (例 9-4)
#ifndef NODE_LIBRARY
#define NODE_LIBRARY
#include <iostream.h>
#include <stdlib.h>
#include "9_3.h"
顺
序
访
问
线
性
群
体
// 生成节点
template <class T>
Node<T> *GetNode(const T& item,
Node<T> *nextPtr = NULL)
{ Node<T> *newNode;
newNode = new Node<T>(item,nextPtr);
if (newNode == NULL)
{
cerr << "Memory allocation failure!" << endl;
exit(1);
}
return newNode;
}
enum AppendNewline {noNewline,addNewline};
// 输出链表
template <class T>
void PrintList(Node<T> *head,
AppendNewline addnl = noNewline)
{ Node<T> *currPtr = head;
while(currPtr != NULL)
{ if(addnl == addNewline)
cout << currPtr->data << endl;
else
cout << currPtr->data << " ";
currPtr = currPtr->NextNode();
}
}
//查找节点
template <class T>
int Find(Node<T> *head,T& item,Node<T>* &prevPtr)
{
Node<T> *currPtr = head;
prevPtr = NULL;
while(currPtr != NULL)
{
if (currPtr->data == item) return 1;
prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
return 0;
}
//在表头插入节点
template <class T>
void InsertFront(Node<T>* & head,T item)
{ head = GetNode(item,head); }
//在表尾添加节点
template <class T>
void InsertRear(Node<T>* & head,const T& item)
{ Node<T> *newNode,*currPtr = head;
if (currPtr == NULL) InsertFront(head,item);
else
{ while(currPtr->NextNode() != NULL)
currPtr = currPtr->NextNode();
newNode = GetNode(item);
currPtr->InsertAfter(newNode);
}
}
// 删除链表的第一个节点
template <class T>
void DeleteFront(Node<T>* & head)
{
Node<T> *p = head;
if (head != NULL)
{
head = head->NextNode();
delete p;
}
}
// 删除链表中第一个数据域等于 key的节点
template <class T>
void Delete (Node<T>* & head,T key)
{ Node<T> *currPtr = head,*prevPtr = NULL;
if (currPtr == NULL) return;
while (currPtr != NULL && currPtr->data != key)
{ prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
if (currPtr != NULL)
{ if(prevPtr == NULL) head = head->NextNode();
else
prevPtr->DeleteAfter();
delete currPtr;
}
}
// 在有序链表中插入一个节点
template <class T>
void InsertOrder(Node<T>* & head,T item)
{ Node<T> *currPtr,*prevPtr,*newNode;
prevPtr = NULL;
currPtr = head;
while (currPtr != NULL)
{ if (item < currPtr->data) break;
prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
if (prevPtr == NULL) InsertFront(head,item);
else
{ newNode = GetNode(item);
prevPtr->InsertAfter(newNode);
}
}
//清空链表 --删除链表中的所有节点
template <class T>
void ClearList(Node<T> * &head)
{
Node<T> *currPtr,*nextPtr;
currPtr = head;
while(currPtr != NULL)
{ nextPtr = currPtr->NextNode();
delete currPtr;
currPtr = nextPtr;
}
head = NULL;
}
#endif // NODE_LIBRARY
前一页 休息 36
链表应用举例
? 例 9.5
从键盘输入 10个整数，用这些整数值
作为结点数据，生成一个链表，按顺序输
出链表中结点的数值。然后从键盘输入一
个待查找整数，在链表中查找该整数，若
找到则删除该整数所在的结点（如果出现
多次，全部删除），然后输出删除结点以
后的链表。在程序结束之前清空链表。
9-5.cpp
顺
序
访
问
线
性
群
体
#include <iostream.h>
#include "9_3.h"
#include "9_4.h"
void main(void)
{ Node<int> *head = NULL,*prevPtr,*delPtr;
int i,key,item;
for (i=0;i < 10;i++)
{ cin>>item;
InsertFront(head,item);
}
cout << "List,";
PrintList(head,noNewline);
cout << endl;
cout << "请输入一个需要删除的整数, ";
cin >> key;
prevPtr = head;
while (Find(head,key,prevPtr) != NULL)
{ if(prevPtr == NULL) head = head->NextNode();
else delPtr=prevPtr->DeleteAfter();
delete delPtr;
}
cout << "List,";
PrintList(head,noNewline);
cout << endl;
ClearList(head);
}
前一页 休息 39
链表类模板 (例 9-6)
//9_6.h
#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS
#include <iostream.h>
#include <stdlib.h>
#ifndef NULL
const int NULL = 0;
#endif // NULL
#include "9_3.h"
顺
序
访
问
线
性
群
体
template <class T>
class LinkedList
{ private:
Node<T> *front,*rear;
Node<T> *prevPtr,*currPtr;
int size;
int position;
Node<T> *GetNode(const T& item,
Node<T> *ptrNext=NULL);
void FreeNode(Node<T> *p);
void CopyList(const LinkedList<T>& L);
public:
LinkedList(void);
LinkedList(const LinkedList<T>& L);
~LinkedList(void);
LinkedList<T>& operator=
(const LinkedList<T>& L);
int ListSize(void) const;
int ListEmpty(void) const;
void Reset(int pos = 0);
void Next(void);
int EndOfList(void) 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);
void DeleteAt(void);
T& Data(void);
void ClearList(void);
};
#endif // LINKEDLIST_CLASS
前一页 休息 43
链表类应用举例 (例 9-7)
#include <iostream.h>
#include "9_6.h"
#include "9_6.cpp"
void main(void)
{ LinkedList<int> Link;
int i,key,item;
for (i=0;i < 10;i++)
{ cin>>item;
Link.InsertFront(item);
}
顺
序
访
问
线
性
群
体
cout << "List,";
Link.Reset();
while(!Link.EndOfList())
{
cout <<Link.Data() << " ";
Link.Next();
}
cout << endl;
cout << "请输入一个需要删除的整数, ";
cin >> key;
Link.Reset();
while (!Link.EndOfList())
{ if(Link.Data() == key) Link.DeleteAt();
Link.Next();
}
cout << "List,";
Link.Reset();
while(!Link.EndOfList())
{ cout <<Link.Data() << " ";
Link.Next();
}
cout << endl;
}
前一页 休息 46
特殊的线性群体 —— 栈
栈是只能从一端访问的线性群体，
可以访问的这一端称栈顶，另一端称栈
底。
an
┆
a2
a1
入栈 出栈
栈顶
栈底
前一页 休息 47
栈的应用举例 —— 函数调用特
殊
的
线
性
群
体——
栈
main{}
调 fun(参数 )
结束
fun(参数 )
返回
① ②
⑤
⑦
⑧
参数
当前现场
返回地址
③
⑥
入栈
当前现场
返回地址
出栈
参数
④
出栈
当前现场
返回地址
前一页 休息 48
栈的应用举例 —— 表达式处理
b
a /
a/b+c*d
(a)
t1 +
a/b+c*d
t1=a/b
(b)
d
c
t1
*
+
a/b+c*d
(c)
t3
a/b+c*d
t3=t1+t2
(e)
t2
t1 +
a/b+c*d
t2=c*d
(d)
特
殊
的
线
性
群
体——
栈
前一页 休息 49
栈的基本状态
? 栈空
– 栈中没有元素
? 栈满
– 栈中元素个数达到上限
? 一般状态
– 栈中有元素，但未达到栈满状态
特
殊
的
线
性
群
体——
栈
栈顶
┆
an
┆
a1
a0
入栈 出栈
数组下标
max
n
1
0
一般状态
栈顶
入栈 出栈
数组下标
初始状态（栈空）
max
n
1
0
栈顶amax┆
an
┆
a1
a0
入栈 出栈
数组下标 max
n
1
0
栈满状态
前一页 休息 51
栈的基本操作
? 初始化
? 入栈
? 出栈
? 清空栈
? 访问栈顶元素
? 检测栈的状态（满、空）
特
殊
的
线
性
群
体——
栈
前一页 休息 52
栈类模板 (例 9-8)
//9-8.h
#ifndef STACK_CLASS
#define STACK_CLASS
#include <iostream.h>
#include <stdlib.h>
const int MaxStackSize = 50;
特
殊
的
线
性
群
体——
栈
template <class T>
class Stack
{ private:
T stacklist[MaxStackSize];
int top;
public:
Stack (void);
void Push (const T& item);
T Pop (void);
void ClearStack(void);
T Peek (void) const;
int StackEmpty(void) const;
int StackFull(void) const;
};
//类的实现略
前一页 休息 54
栈的应用
? 例 9.9 一个简单的整数计算器
实现一个简单的整数计算器，能够进
行加、减、乘、除和乘方运算。使用时算
式采用后缀输入法，每个操作数、操作符
之间都以空白符分隔。例如，若要计算
"3+5"则输入 "3 5 +"。乘方运算符用 "^"表
示。每次运算在前次结果基础上进行，若
要将前次运算结果清除，可键入 "c"。当键
入 "q"时程序结束。
? 9-9.h 9-9.cpp
特
殊
的
线
性
群
体——
栈
//9_9.h
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
enum Boolean {False,True};
#include "9_8.h"
class Calculator
{ private:
Stack<int> S;
void Enter(int num);
Boolean GetTwoOperands(int& opnd1,
int& opnd2);
void Compute(char op);
public:
Calculator(void) {}
void Run(void);
void Clear(void);
};
void Calculator::Enter(int num)
{ S.Push(num); }
Boolean Calculator::GetTwoOperands
(int& opnd1,int& opnd2)
{ if (S.StackEmpty())
{ cerr << "Missing operand!" << endl;
return False;
}
opnd1 = S.Pop();
if (S.StackEmpty())
{ cerr << "Missing operand!" << endl;
return False;
}
opnd2 = S.Pop();
return True;
}
void Calculator::Compute(char op)
{ Boolean result;
int operand1,operand2;
result = GetTwoOperands(operand1,operand2);
if (result == True)
{ switch(op)
{ case '+',S.Push(operand2+operand1);
break;
case '-',S.Push(operand2-operand1);
break;
case '*',S.Push(operand2*operand1);
break;
case '/',if (operand1 == 0)
{ cerr << "Divide by 0!" << endl;
S.ClearStack();
}
else
S.Push(operand2/operand1);
break;
case '^',S.Push(pow(operand2,operand1));
break;
}
cout<<'='<<S.Peek()<<' ';
}
else
S.ClearStack();
}
void Calculator::Run(void)
{ char c[20];
while(cin >> c,*c != 'q')
switch(*c)
{ case 'c',S.ClearStack();
break;
case '-':
if (strlen(c)>1) Enter(atoi(c));
else Compute(*c);
break;
case '+':
case '*':
case '/':
case '^':
Compute(*c);
break;
default,
Enter(atoi(c));
break;
}
}
void Calculator::Clear(void)
{ S.ClearStack(); }
//9_9.cpp
#include "9-9.h"
void main(void)
{
Calculator CALC;
CALC.Run();
}
前一页 休息 63
特殊的线性群体 —— 队列
队列是只能向一端添加元素，从另
一端删除元素的线性群体
a1 a2 an-1 an……
队头 队尾
入队出队 a0
前一页 休息 64
队列的基本状态
? 队空
– 队列中没有元素
? 队满
– 队列中元素个数达到上限
? 一般状态
– 队列中有元素，但未达到队满状态
特
殊
的
线
性
群
体——
队
列
a0 a1 an-1 an……
队头 队尾
入队出队
数组下标 0 1 n-1 n max
(一般状态 )
……
队头 队尾
入队出队
数组下标 0 1 n-1 n max
(队空状态 )
a0 a1 an-1 an amax……
队头 队尾
入队出队
数组下标 0 1 n-1 n max
(队满状态 )
元素移动方向
元素移动方向
前一页 休息 66
循环队列
在想象中将数组弯曲成环形，元素
出队时，后继元素不移动，每当队尾达
到数组最后一个元素时，便再回到数组
开头。
特
殊
的
线
性
群
体——
队
列
1
2
3
4
……
m-1
m-2
m-3
0
amam+1
am+2
a3
队头
队尾
a4
am-2
am-3
am-1
队满状态 元素个数 =m
1
2
3
4
……
m-1
m-2
m-3
0
队尾
队头
队空状态 元素个数 =0
队尾
1
2
3
4
……
m-1
m-2
m-3
0
a0a1
a2
a3
队头
一般状态
前一页 休息 68
例 9-10 队列类模板
#ifndef QUEUE_CLASS
#define QUEUE_CLASS
#include <iostream.h>
#include <stdlib.h>
const int MaxQSize = 50;
特
殊
的
线
性
群
体——
队
列
template <class T>
class Queue
{ private:
int front,rear,count;
T qlist[MaxQSize];
public:
Queue (void);
void QInsert(const T& item);
T QDelete(void);
void ClearQueue(void);
T QFront(void) const;
int QLength(void) const;
int QEmpty(void) const;
int QFull(void) const;
};
//成员函数的实现略
前一页 休息 70
作业
? 复习第九章，预习第十章
? 实验九
