第九章 群体类和群体数据的组织清华大学 郑 莉
C++语言程序设计
C++语言程序设计 清华大学 郑莉
2
本章主要内容
模板
群体类
群体数据的组织
C++语言程序设计 清华大学 郑莉
3
第一部分 — 模板
函数模板
类模板
C++语言程序设计 清华大学 郑莉
4
函数模板
函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。
声明方法：
template <typename 标识符 >
函数声明函数模板
C++语言程序设计 清华大学 郑莉
5
求绝对值函数的模板
#include<iostream>
using namespace std;
template<typename T>
T abs(T x)
{ return x<0?-x:x; }
void main()
{ int n=-5;
double d=-5.5;
cout<<abs(n)<<endl;
cout<<abs(d)<<endl;
}
函数模板 运行结果：
5
5.5
C++语言程序设计 清华大学 郑莉
6
求绝对值函数的模板分析
编译器从调用 abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式 abs(n)，由于实参 n为
int型，所以推导出模板中类型参数 T
为 int。
当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：
int abs(int x)
{ return x<0?-x:x; }
函数模板
C++语言程序设计 清华大学 郑莉
7
类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、
某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。
类模板
C++语言程序设计 清华大学 郑莉
8
类模板的声明
类模板：
template <模板参数表 >
class 类名
{类成员声明 }
如果需要在类模板以外定义其成员函数，则要采用以下的形式：
template <模板参数表 >
类型名 类名 <T>::函数名（参数表）
类模板
C++语言程序设计 清华大学 郑莉
9
例 9-2 类模板应用举例
#include <iostream>
#include <cstdlib>
using namespace std;
// 结构体 Student
struct Student
{
int id; //学号
float gpa; //平均分
};
类模板
template <class T>
//类模板：实现对任意类型数据进行存取
class Store
{ private:
T item; // 用于存放任意类型的数据
int haveValue; // 用于标记 item是否已被存入内容
public:
Store(void); // 默认形式（无形参）的构造函数
T GetElem(void); //提取数据函数
void PutElem(T x); //存入数据函数
};
// 默认形式构造函数的实现
template <class T>
Store<T>::Store(void),haveValue(0) {}
10
template <class T> // 提取数据函数的实现
T Store<T>::GetElem(void)
{ // 如果试图提取未初始化的数据，则终止程序
if (haveValue == 0)
{ cout << "No item present!" << endl;
exit(1);
}
return item; // 返回 item中存放的数据
}
template <class T> // 存入数据函数的实现
void Store<T>::PutElem(T x)
{ haveValue++; // 将 haveValue 置为 TRUE，表示
item中已存入数值
item = x; // 将 x值存入 item
}
11
void main(void)
{ Student g= {1000,23};
Store<int> S1,S2;
Store<Student> S3;
Store<double> D;
S1.PutElem(3);
S2.PutElem(-7);
cout << S1.GetElem() << " " << S2.GetElem() << endl;
S3.PutElem(g);
cout << "The student id is " << S3.GetElem().id << endl;
cout << "Retrieving object D " ;
cout << D.GetElem() << endl; //输出对象 D的数据成员
// 由于 D未经初始化,在执行函数 D.GetElement()时出错
}
12
C++语言程序设计 清华大学 郑莉
13
第二部分 — 群 体数据
线性群体
– 线性群体的概念
– 直接访问群体 --数组类
– 顺序访问群体 --链表类
– 栈类
– 队列类
C++语言程序设计 清华大学 郑莉
14
群体的概念群体 是指由多个数据元素组成的集合体。群体可以分为两个大类,线性群体 和 非线性群体 。
线性群体中的元素按位置排列有序，
可以区分为第一个元素、第二个元素等。
非线性群体不用位置顺序来标识元素。
C++语言程序设计 清华大学 郑莉
15
线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为 直接访问,顺序访问 和 索引访问 。
在本章我们只介绍直接访问和顺序访问。
…
第一个元素 第二个元素 第三个元素 最后一个元素
C++语言程序设计 清华大学 郑莉
16
数组
静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。
– 缺点：大小在编译时就已经确定，在运行时无法修改。
动态数组由一系列位置连续的，任意数量相同类型的元素组成。
– 优点：其元素个数可在程序运行时改变。
动态数组类模板：例 9-3（ 9_3.h）
直接访问的线性群体
#ifndef ARRAY_CLASS
#define ARRAY_CLASS
using namespace std;
#include <iostream>
#include <cstdlib>
#ifndef NULL
const int NULL = 0;
#endif // NULL
enum ErrorType
{ invalidArraySize,memoryAllocationError,
indexOutOfRange };
char *errorMsg[] =
{ "Invalid array size","Memory allocation error",
"Invalid index,"
};
动态数组类模板程序
17
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);
};
18
C++语言程序设计 清华大学 郑莉
19
数组类模板的构造函数
// 构造函数
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);
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
20
数组类的拷贝构造函数
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++;
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
21
浅拷贝
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;
}
C++语言程序设计 清华大学 郑莉
22
深拷贝
alist
size
A
A的数组元素占用的内存拷贝前
alist
size
A
A的数组元素占用的内存拷贝后
alist
size
B
B的数组元素占用的内存
C++语言程序设计 清华大学 郑莉
23
数组类的重载 "="运算符函数
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;
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
24
数组类的重载下标操作符函数
template <class T>
T& Array<T>::operator[] (int n)
{
// 检查下标是否越界
if (n < 0 || n > size-1)
Error(indexOutOfRange,n);
// 返回下标为 n的数组元素
return alist[n];
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
25
为什么有的函数返回引用
如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。
如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
26
重载指针转换操作符
template <class T>
Array<T>::operator T* (void) const
{
// 返回当前对象中私有数组的首地址
return alist;
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
27
指针转换运算符的作用
#include <iostream>
using namespace std;
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];
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
28
Array类的应用
例 9-4求范围 2~N中的质数,N在程序运行时由键盘输入。
直接访问的线性群体
#include <iostream>
#include <iomanip>
#include "9_3.h"
using namespace std;
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;
} 29
C++语言程序设计 清华大学 郑莉
30
链表
链表是一种动态数据结构，可以用来表示顺序访问的线性群体。
链表是由系列 结点 组成的，结点可以在运行时动态生成。
每一个结点包括 数据域 和指向链表中下一个结点的 指针 （即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
31
单链表
data1 data2 data3 datan NULL…
head rear
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
32
单链表的结点类模板
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;
};
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
33
在结点之后插入一个结点
data1 data2 …
p data
…
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
//p节点指针域指向当前节点的后继节点
p->next = next;
next = p; //当前节点的指针域指向 p
}
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
34
删除结点之后的结点顺序访问的线性群体
data1 data2 data3 ……
Node<T> *Node<T>::DeleteAfter(void)
{
Node<T> *tempPtr = next;
if (next == NULL)
return NULL;
next = tempPtr->next;
return tempPtr;
}
tempPtr
C++语言程序设计 清华大学 郑莉
35
链表的基本操作
生成结点
插入结点
查找结点
删除结点
遍历链表
清空链表顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
36
链表类模板 (例 9-6)
//9_6.h
#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
const int NULL = 0;
#endif // NULL
#include "9_5.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);
37
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;
38
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
39
C++语言程序设计 清华大学 郑莉
40
链表类应用举例 (例 9-7)
#include <iostream>
using namespace std;
#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();
41
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;
}
42
C++语言程序设计 清华大学 郑莉
43
特殊的线性群体 —— 栈栈是只能从一端访问的线性群体，
可以访问的这一端称栈顶，另一端称栈底。
an
┆
a2
a1
入栈 出栈栈顶栈底特殊的线性群体——
栈
C++语言程序设计 清华大学 郑莉
44
栈的应用举例 —— 函数调用特殊的线性群体——
栈
main{}
调 fun(参数 )
结束
fun(参数 )
返回
① ②
⑤
⑦
⑧
参数当前现场返回地址
③
⑥
入栈当前现场返回地址出栈参数
④
出栈当前现场返回地址
C++语言程序设计 清华大学 郑莉
45
栈的应用举例 —— 表达式处理
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)
特殊的线性群体——
栈
C++语言程序设计 清华大学 郑莉
46
栈的基本状态
栈空
– 栈中没有元素
栈满
– 栈中元素个数达到上限
一般状态
– 栈中有元素，但未达到栈满状态特殊的线性群体——
栈栈顶
┆
an
┆
a1
a0
入栈 出栈数组下标
max
n
1
0
一般状态栈顶入栈 出栈数组下标初始状态（栈空）
max
n
1
0
栈顶amax┆
an
┆
a1
a0
入栈 出栈数组下标 max
n
1
0
栈满状态
47
C++语言程序设计 清华大学 郑莉
48
栈的基本操作
初始化
入栈
出栈
清空栈
访问栈顶元素
检测栈的状态（满、空）
特殊的线性群体——
栈
C++语言程序设计 清华大学 郑莉
49
栈类模板 (例 9-8)特殊的线性群体——
栈
//9-8.h
#ifndef STACK_CLASS
#define STACK_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
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;
};
//类的实现略
C++语言程序设计 清华大学 郑莉
50
栈的应用
例 9.9 一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算
"3+5"则输入 "3 5 +"。乘方运算符用 "^"表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入 "c"。当键入 "q"时程序结束。
9-9.h 9-9.cpp
特殊的线性群体——
栈
//9_9.h
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
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:
void Run(void);
void Clear(void);
};
51
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;
}
52
void Calculator::Compute(char op)
{ Boolean result;
int operand1,operand2;
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)
{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();
} 53
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;
}
} 54
void Calculator::Clear(void)
{ S.ClearStack(); }
//9_9.cpp
#include "9-9.h"
void main(void)
{
Calculator CALC;
CALC.Run();
}
55
C++语言程序设计 清华大学 郑莉
56
特殊的线性群体 —— 队列队列是只能向一端添加元素，从另一端删除元素的线性群体
a1 a2 an-1 an……
队头 队尾入队出队 a0
C++语言程序设计 清华大学 郑莉
57
队列的基本状态
队空
– 队列中没有元素
队满
– 队列中元素个数达到上限
一般状态
– 队列中有元素，但未达到队满状态特殊的线性群体——
队列
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
(队满状态 )
元素移动方向元素移动方向
58
C++语言程序设计 清华大学 郑莉
59
循环队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。
特殊的线性群体——
队列
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
队头一般状态
60
C++语言程序设计 清华大学 郑莉
61
例 9-10 队列类模板特殊的线性群体——
队列
#ifndef QUEUE_CLASS
#define QUEUE_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
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;
};
//成员函数的实现略
C++语言程序设计 清华大学 郑莉
62
第三部分 — 群 体数据的组织
插入排序
选择排序
交换排序
顺序查找
折半查找
C++语言程序设计 清华大学 郑莉
63
排序（ sorting）
排序 是计算机程序设计中的一种重要操作，
它的功能是将一个 数据元素 的任意序列，重新排列成一个按 关键字 有序的序列。
– 数据元素,数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。
– 关键字,数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。
在排序过程中需要完成两种基本操作：
– 比较两个数的大小
– 调整元素在序列中的位置群体数据的组织
C++语言程序设计 清华大学 郑莉
64
内部排序与外部排序
内部排序,待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序,待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。
群体数据的组织
C++语言程序设计 清华大学 郑莉
65
内部排序方法
插入排序
选择排序
交换排序群体数据的组织
C++语言程序设计 清华大学 郑莉
66
插入排序的基本思想
每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。
初始状态,[5] 4 10 20 12 3
插入操作,1 [4] [4 5] 10 20 12 3
2 [10] [4 5 10] 20 12 3
3 [20] [4 5 10 20] 12 3
4 [12] [4 5 10 12 20] 3
5 [3] [3 4 5 10 12 20]
C++语言程序设计 清华大学 郑莉
67
直接插入排序
在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，
这里我们只介绍最简单的直接插入排序算法。
例 9-11 直接插入排序函数模板（ 9_11.h）
群体数据的组织
template <class T>
void InsertionSort(T A[],int n)
{ int i,j;
T temp;
for (i = 1; i < n; i++)
{ j = i;
temp = A[i];
while (j > 0 && temp < A[j-1])
{ A[j] = A[j-1];
j--;
}
A[j] = temp;
}
}
直接插入排序函数模板（ 9_11.h）
68
C++语言程序设计 清华大学 郑莉
69
选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。
[5 4 10 20 12 3]初始状态：
3 [4 10 20 12 5]
3 4 [10 20 12 5]
第 i 次选择后，将选出的那个记录与第 i 个记录做 交换 。
3 4 5 [20 12 10]
...,..
C++语言程序设计 清华大学 郑莉
70
直接选择排序
在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。
例 9-12 直接选择排序函数模板（ 9-
12.h）
群体数据的组织
template <class T>
void Swap (T &x,T &y)
{ T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void SelectionSort(T A[],int n)
{ int smallIndex;
int i,j;
for (i = 0; i < n-1; i++)
{ smallIndex = i;
for (j = i+1; j < n; j++)
if (A[j] < A[smallIndex])
smallIndex = j;
Swap(A[i],A[smallIndex]);
}
}
直接选择排序函数模板（ 9-12.h）
71
C++语言程序设计 清华大学 郑莉
72
交换排序的基本思想两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。
群体数据的组织
C++语言程序设计 清华大学 郑莉
73
最简单的交换排序方法
—— 起泡排序对具有 n个元素的序列按升序进行起泡排序的步骤：
– 首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，
依次类推，直到第 n-1和第 n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第 n个位置。
– 对前 n-1个元素进行第二趟起泡排序，将其中最大元素交换到第 n-1个位置。
– 如此继续，直到某一趟排序未发生任何交换时，排序完毕。对 n个元素的序列，起泡排序最多需要进行 n-1趟。
群体数据的组织
C++语言程序设计 清华大学 郑莉
74
起泡排序举例对整数序列 8 5 2 4 3 按升序排序
8
5
2
4
3
5
2
4
3
8
2
4
3
5
8
2
3
4
5
8
2
3
4
5
8
初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织
C++语言程序设计 清华大学 郑莉
75
例 9-13 起泡排序函数模板
template <class T>
void Swap (T &x,T &y)
{
T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void BubbleSort(T A[],int n)
{ int i,j;
int lastExchangeIndex;
i = n-1;
while (i > 0)
{ lastExchangeIndex = 0;
for (j = 0; j < i; j++)
if (A[j+1] < A[j])
{ Swap(A[j],A[j+1]);
lastExchangeIndex = j;
}
i = lastExchangeIndex;
}
}
群体数据的组织
C++语言程序设计 清华大学 郑莉
76
顺序查找
其基本思想
– 从序列的首元素开始,逐个元素与待查找的关键字进行比较,直到找到相等的 。
若整个序列中没有与待查找关键字相等的元素,就是查找不成功 。
顺序查找函数模板
– 例 9-14
群体数据的组织
template <class T>
int SeqSearch(T list[],int n,T key)
{
for(int i=0;i < n;i++)
if (list[i] == key)
return i;
return -1;
}
顺序查找函数模板
77
C++语言程序设计 清华大学 郑莉
78
折半查找的基本思想对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，
逐步缩小查找范围，直至找到或找不到为止。
群体数据的组织
C++语言程序设计 清华大学 郑莉
79
折半查找举例用折半查找法，在下列序列中查找值为 21的元素：
L=1
5 13 19 21 37 56 64 75 80 88 92
H=11M =INT((L+H)/2)=6
5 13 19 21 37
L=1 H=M-1=5 M=INT((L+H)/2)=3M
21 37
H
L=M+1=4
L
M=INT((L+H)/2)=4
M
C++语言程序设计 清华大学 郑莉
80
例 10-5 折半查找函数模板
template <class T>
int BinSearch(T list[],int n,T key)
{ int mid,low,high;
T midvalue;
low=0;
high=n-1;
while (low <= high)
{ mid = (low+high)/2;
midvalue = list[mid];
if (key == midvalue) return mid;
else if (key < midvalue) high = mid-1;
else low = mid+1;
}
return -1;
}
群体数据的组织
C++语言程序设计
C++语言程序设计 清华大学 郑莉
2
本章主要内容
模板
群体类
群体数据的组织
C++语言程序设计 清华大学 郑莉
3
第一部分 — 模板
函数模板
类模板
C++语言程序设计 清华大学 郑莉
4
函数模板
函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。
声明方法：
template <typename 标识符 >
函数声明函数模板
C++语言程序设计 清华大学 郑莉
5
求绝对值函数的模板
#include<iostream>
using namespace std;
template<typename T>
T abs(T x)
{ return x<0?-x:x; }
void main()
{ int n=-5;
double d=-5.5;
cout<<abs(n)<<endl;
cout<<abs(d)<<endl;
}
函数模板 运行结果：
5
5.5
C++语言程序设计 清华大学 郑莉
6
求绝对值函数的模板分析
编译器从调用 abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式 abs(n)，由于实参 n为
int型，所以推导出模板中类型参数 T
为 int。
当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：
int abs(int x)
{ return x<0?-x:x; }
函数模板
C++语言程序设计 清华大学 郑莉
7
类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、
某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。
类模板
C++语言程序设计 清华大学 郑莉
8
类模板的声明
类模板：
template <模板参数表 >
class 类名
{类成员声明 }
如果需要在类模板以外定义其成员函数，则要采用以下的形式：
template <模板参数表 >
类型名 类名 <T>::函数名（参数表）
类模板
C++语言程序设计 清华大学 郑莉
9
例 9-2 类模板应用举例
#include <iostream>
#include <cstdlib>
using namespace std;
// 结构体 Student
struct Student
{
int id; //学号
float gpa; //平均分
};
类模板
template <class T>
//类模板：实现对任意类型数据进行存取
class Store
{ private:
T item; // 用于存放任意类型的数据
int haveValue; // 用于标记 item是否已被存入内容
public:
Store(void); // 默认形式（无形参）的构造函数
T GetElem(void); //提取数据函数
void PutElem(T x); //存入数据函数
};
// 默认形式构造函数的实现
template <class T>
Store<T>::Store(void),haveValue(0) {}
10
template <class T> // 提取数据函数的实现
T Store<T>::GetElem(void)
{ // 如果试图提取未初始化的数据，则终止程序
if (haveValue == 0)
{ cout << "No item present!" << endl;
exit(1);
}
return item; // 返回 item中存放的数据
}
template <class T> // 存入数据函数的实现
void Store<T>::PutElem(T x)
{ haveValue++; // 将 haveValue 置为 TRUE，表示
item中已存入数值
item = x; // 将 x值存入 item
}
11
void main(void)
{ Student g= {1000,23};
Store<int> S1,S2;
Store<Student> S3;
Store<double> D;
S1.PutElem(3);
S2.PutElem(-7);
cout << S1.GetElem() << " " << S2.GetElem() << endl;
S3.PutElem(g);
cout << "The student id is " << S3.GetElem().id << endl;
cout << "Retrieving object D " ;
cout << D.GetElem() << endl; //输出对象 D的数据成员
// 由于 D未经初始化,在执行函数 D.GetElement()时出错
}
12
C++语言程序设计 清华大学 郑莉
13
第二部分 — 群 体数据
线性群体
– 线性群体的概念
– 直接访问群体 --数组类
– 顺序访问群体 --链表类
– 栈类
– 队列类
C++语言程序设计 清华大学 郑莉
14
群体的概念群体 是指由多个数据元素组成的集合体。群体可以分为两个大类,线性群体 和 非线性群体 。
线性群体中的元素按位置排列有序，
可以区分为第一个元素、第二个元素等。
非线性群体不用位置顺序来标识元素。
C++语言程序设计 清华大学 郑莉
15
线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为 直接访问,顺序访问 和 索引访问 。
在本章我们只介绍直接访问和顺序访问。
…
第一个元素 第二个元素 第三个元素 最后一个元素
C++语言程序设计 清华大学 郑莉
16
数组
静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。
– 缺点：大小在编译时就已经确定，在运行时无法修改。
动态数组由一系列位置连续的，任意数量相同类型的元素组成。
– 优点：其元素个数可在程序运行时改变。
动态数组类模板：例 9-3（ 9_3.h）
直接访问的线性群体
#ifndef ARRAY_CLASS
#define ARRAY_CLASS
using namespace std;
#include <iostream>
#include <cstdlib>
#ifndef NULL
const int NULL = 0;
#endif // NULL
enum ErrorType
{ invalidArraySize,memoryAllocationError,
indexOutOfRange };
char *errorMsg[] =
{ "Invalid array size","Memory allocation error",
"Invalid index,"
};
动态数组类模板程序
17
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);
};
18
C++语言程序设计 清华大学 郑莉
19
数组类模板的构造函数
// 构造函数
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);
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
20
数组类的拷贝构造函数
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++;
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
21
浅拷贝
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;
}
C++语言程序设计 清华大学 郑莉
22
深拷贝
alist
size
A
A的数组元素占用的内存拷贝前
alist
size
A
A的数组元素占用的内存拷贝后
alist
size
B
B的数组元素占用的内存
C++语言程序设计 清华大学 郑莉
23
数组类的重载 "="运算符函数
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;
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
24
数组类的重载下标操作符函数
template <class T>
T& Array<T>::operator[] (int n)
{
// 检查下标是否越界
if (n < 0 || n > size-1)
Error(indexOutOfRange,n);
// 返回下标为 n的数组元素
return alist[n];
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
25
为什么有的函数返回引用
如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。
如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
26
重载指针转换操作符
template <class T>
Array<T>::operator T* (void) const
{
// 返回当前对象中私有数组的首地址
return alist;
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
27
指针转换运算符的作用
#include <iostream>
using namespace std;
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];
}
直接访问的线性群体
C++语言程序设计 清华大学 郑莉
28
Array类的应用
例 9-4求范围 2~N中的质数,N在程序运行时由键盘输入。
直接访问的线性群体
#include <iostream>
#include <iomanip>
#include "9_3.h"
using namespace std;
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;
} 29
C++语言程序设计 清华大学 郑莉
30
链表
链表是一种动态数据结构，可以用来表示顺序访问的线性群体。
链表是由系列 结点 组成的，结点可以在运行时动态生成。
每一个结点包括 数据域 和指向链表中下一个结点的 指针 （即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
31
单链表
data1 data2 data3 datan NULL…
head rear
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
32
单链表的结点类模板
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;
};
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
33
在结点之后插入一个结点
data1 data2 …
p data
…
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
//p节点指针域指向当前节点的后继节点
p->next = next;
next = p; //当前节点的指针域指向 p
}
顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
34
删除结点之后的结点顺序访问的线性群体
data1 data2 data3 ……
Node<T> *Node<T>::DeleteAfter(void)
{
Node<T> *tempPtr = next;
if (next == NULL)
return NULL;
next = tempPtr->next;
return tempPtr;
}
tempPtr
C++语言程序设计 清华大学 郑莉
35
链表的基本操作
生成结点
插入结点
查找结点
删除结点
遍历链表
清空链表顺序访问的线性群体
C++语言程序设计 清华大学 郑莉
36
链表类模板 (例 9-6)
//9_6.h
#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
const int NULL = 0;
#endif // NULL
#include "9_5.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);
37
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;
38
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
39
C++语言程序设计 清华大学 郑莉
40
链表类应用举例 (例 9-7)
#include <iostream>
using namespace std;
#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();
41
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;
}
42
C++语言程序设计 清华大学 郑莉
43
特殊的线性群体 —— 栈栈是只能从一端访问的线性群体，
可以访问的这一端称栈顶，另一端称栈底。
an
┆
a2
a1
入栈 出栈栈顶栈底特殊的线性群体——
栈
C++语言程序设计 清华大学 郑莉
44
栈的应用举例 —— 函数调用特殊的线性群体——
栈
main{}
调 fun(参数 )
结束
fun(参数 )
返回
① ②
⑤
⑦
⑧
参数当前现场返回地址
③
⑥
入栈当前现场返回地址出栈参数
④
出栈当前现场返回地址
C++语言程序设计 清华大学 郑莉
45
栈的应用举例 —— 表达式处理
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)
特殊的线性群体——
栈
C++语言程序设计 清华大学 郑莉
46
栈的基本状态
栈空
– 栈中没有元素
栈满
– 栈中元素个数达到上限
一般状态
– 栈中有元素，但未达到栈满状态特殊的线性群体——
栈栈顶
┆
an
┆
a1
a0
入栈 出栈数组下标
max
n
1
0
一般状态栈顶入栈 出栈数组下标初始状态（栈空）
max
n
1
0
栈顶amax┆
an
┆
a1
a0
入栈 出栈数组下标 max
n
1
0
栈满状态
47
C++语言程序设计 清华大学 郑莉
48
栈的基本操作
初始化
入栈
出栈
清空栈
访问栈顶元素
检测栈的状态（满、空）
特殊的线性群体——
栈
C++语言程序设计 清华大学 郑莉
49
栈类模板 (例 9-8)特殊的线性群体——
栈
//9-8.h
#ifndef STACK_CLASS
#define STACK_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
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;
};
//类的实现略
C++语言程序设计 清华大学 郑莉
50
栈的应用
例 9.9 一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算
"3+5"则输入 "3 5 +"。乘方运算符用 "^"表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入 "c"。当键入 "q"时程序结束。
9-9.h 9-9.cpp
特殊的线性群体——
栈
//9_9.h
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
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:
void Run(void);
void Clear(void);
};
51
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;
}
52
void Calculator::Compute(char op)
{ Boolean result;
int operand1,operand2;
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)
{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();
} 53
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;
}
} 54
void Calculator::Clear(void)
{ S.ClearStack(); }
//9_9.cpp
#include "9-9.h"
void main(void)
{
Calculator CALC;
CALC.Run();
}
55
C++语言程序设计 清华大学 郑莉
56
特殊的线性群体 —— 队列队列是只能向一端添加元素，从另一端删除元素的线性群体
a1 a2 an-1 an……
队头 队尾入队出队 a0
C++语言程序设计 清华大学 郑莉
57
队列的基本状态
队空
– 队列中没有元素
队满
– 队列中元素个数达到上限
一般状态
– 队列中有元素，但未达到队满状态特殊的线性群体——
队列
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
(队满状态 )
元素移动方向元素移动方向
58
C++语言程序设计 清华大学 郑莉
59
循环队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。
特殊的线性群体——
队列
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
队头一般状态
60
C++语言程序设计 清华大学 郑莉
61
例 9-10 队列类模板特殊的线性群体——
队列
#ifndef QUEUE_CLASS
#define QUEUE_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
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;
};
//成员函数的实现略
C++语言程序设计 清华大学 郑莉
62
第三部分 — 群 体数据的组织
插入排序
选择排序
交换排序
顺序查找
折半查找
C++语言程序设计 清华大学 郑莉
63
排序（ sorting）
排序 是计算机程序设计中的一种重要操作，
它的功能是将一个 数据元素 的任意序列，重新排列成一个按 关键字 有序的序列。
– 数据元素,数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。
– 关键字,数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。
在排序过程中需要完成两种基本操作：
– 比较两个数的大小
– 调整元素在序列中的位置群体数据的组织
C++语言程序设计 清华大学 郑莉
64
内部排序与外部排序
内部排序,待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序,待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。
群体数据的组织
C++语言程序设计 清华大学 郑莉
65
内部排序方法
插入排序
选择排序
交换排序群体数据的组织
C++语言程序设计 清华大学 郑莉
66
插入排序的基本思想
每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。
初始状态,[5] 4 10 20 12 3
插入操作,1 [4] [4 5] 10 20 12 3
2 [10] [4 5 10] 20 12 3
3 [20] [4 5 10 20] 12 3
4 [12] [4 5 10 12 20] 3
5 [3] [3 4 5 10 12 20]
C++语言程序设计 清华大学 郑莉
67
直接插入排序
在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，
这里我们只介绍最简单的直接插入排序算法。
例 9-11 直接插入排序函数模板（ 9_11.h）
群体数据的组织
template <class T>
void InsertionSort(T A[],int n)
{ int i,j;
T temp;
for (i = 1; i < n; i++)
{ j = i;
temp = A[i];
while (j > 0 && temp < A[j-1])
{ A[j] = A[j-1];
j--;
}
A[j] = temp;
}
}
直接插入排序函数模板（ 9_11.h）
68
C++语言程序设计 清华大学 郑莉
69
选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。
[5 4 10 20 12 3]初始状态：
3 [4 10 20 12 5]
3 4 [10 20 12 5]
第 i 次选择后，将选出的那个记录与第 i 个记录做 交换 。
3 4 5 [20 12 10]
...,..
C++语言程序设计 清华大学 郑莉
70
直接选择排序
在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。
例 9-12 直接选择排序函数模板（ 9-
12.h）
群体数据的组织
template <class T>
void Swap (T &x,T &y)
{ T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void SelectionSort(T A[],int n)
{ int smallIndex;
int i,j;
for (i = 0; i < n-1; i++)
{ smallIndex = i;
for (j = i+1; j < n; j++)
if (A[j] < A[smallIndex])
smallIndex = j;
Swap(A[i],A[smallIndex]);
}
}
直接选择排序函数模板（ 9-12.h）
71
C++语言程序设计 清华大学 郑莉
72
交换排序的基本思想两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。
群体数据的组织
C++语言程序设计 清华大学 郑莉
73
最简单的交换排序方法
—— 起泡排序对具有 n个元素的序列按升序进行起泡排序的步骤：
– 首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，
依次类推，直到第 n-1和第 n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第 n个位置。
– 对前 n-1个元素进行第二趟起泡排序，将其中最大元素交换到第 n-1个位置。
– 如此继续，直到某一趟排序未发生任何交换时，排序完毕。对 n个元素的序列，起泡排序最多需要进行 n-1趟。
群体数据的组织
C++语言程序设计 清华大学 郑莉
74
起泡排序举例对整数序列 8 5 2 4 3 按升序排序
8
5
2
4
3
5
2
4
3
8
2
4
3
5
8
2
3
4
5
8
2
3
4
5
8
初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织
C++语言程序设计 清华大学 郑莉
75
例 9-13 起泡排序函数模板
template <class T>
void Swap (T &x,T &y)
{
T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void BubbleSort(T A[],int n)
{ int i,j;
int lastExchangeIndex;
i = n-1;
while (i > 0)
{ lastExchangeIndex = 0;
for (j = 0; j < i; j++)
if (A[j+1] < A[j])
{ Swap(A[j],A[j+1]);
lastExchangeIndex = j;
}
i = lastExchangeIndex;
}
}
群体数据的组织
C++语言程序设计 清华大学 郑莉
76
顺序查找
其基本思想
– 从序列的首元素开始,逐个元素与待查找的关键字进行比较,直到找到相等的 。
若整个序列中没有与待查找关键字相等的元素,就是查找不成功 。
顺序查找函数模板
– 例 9-14
群体数据的组织
template <class T>
int SeqSearch(T list[],int n,T key)
{
for(int i=0;i < n;i++)
if (list[i] == key)
return i;
return -1;
}
顺序查找函数模板
77
C++语言程序设计 清华大学 郑莉
78
折半查找的基本思想对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，
逐步缩小查找范围，直至找到或找不到为止。
群体数据的组织
C++语言程序设计 清华大学 郑莉
79
折半查找举例用折半查找法，在下列序列中查找值为 21的元素：
L=1
5 13 19 21 37 56 64 75 80 88 92
H=11M =INT((L+H)/2)=6
5 13 19 21 37
L=1 H=M-1=5 M=INT((L+H)/2)=3M
21 37
H
L=M+1=4
L
M=INT((L+H)/2)=4
M
C++语言程序设计 清华大学 郑莉
80
例 10-5 折半查找函数模板
template <class T>
int BinSearch(T list[],int n,T key)
{ int mid,low,high;
T midvalue;
low=0;
high=n-1;
while (low <= high)
{ mid = (low+high)/2;
midvalue = list[mid];
if (key == midvalue) return mid;
else if (key < midvalue) high = mid-1;
else low = mid+1;
}
return -1;
}
群体数据的组织
