1
第 3章 数据结构
2
第 3章 数据结构
数组
指针
字符串
对象与指针
枚举
共用体
关于声明符的进一步讨论
3
数组
一维数组
二维数组
对象数组
4
一维数组的定义
一维数组（向量）是一种整体定义、个别使用的
数据结构。作为一个整体，数组有如下特征,
· 名字：用以对数组各元素的整体标识，这个名
字称为数组名；
· 类型：数组各元素的类型；
· 大小：可容纳的数组元素个数（注意，不是字
节数）；
· 存储：占有一个连续的内存空间。
与简单变量一样，上述特征要用声明语句定义，
格式如下,
类型 数组名 [大小 ]；
5
一维数组的初始化
数组的声明语句是定义性声明，在声明的
同时可以对数组各元素初始化，初始化表
达式按元素顺序依次写在一对花括号内
C + + 语言还允许使用下列初始化的省略方
式
1）初始化时也可以不指定数组的大小，
编译器会根据初始值的个数自动决定数组
大小
2）允许省略为 0的元素值
3）当最后的几个元素初值为 0时，可以只
写出前面的数列，但数组体积不可省略
6
数组元素
作为数组的个体，数组中的每个元素都有
如下特征,
它们的类型是相同的
每个元素用数组名加上括在方括号中的下
标表示。下标表示该元素在数组中的顺序，
下标以 0为起始计数
7
模拟洗扑克牌
基本思路是：将 54张扑克牌统一编号为：
0,1,2,……,52,53，然后随机地从中一一抽取
一张牌，并依次放起，形成新的序列。具
体要解决两个问题：如何存储 54张扑克牌
以及在此基础上如何一一抽取
随机抽牌算法
在 0到 53之间产生一个随机数 r，将 pk[0]与
pk[r]交换
8
类结构
#include <iostream.h>
#include <stdlib.h>
int pk[qqchyan1][] = { 501,502,
101,102,103,104,105,106,107,108,109,110,111,112,113,
201,202,203,204,205,206,207,208,209,210,211,212,213,
301,302,303,304,305,306,307,308,309,310,311,312,313,
401,402,403,404,405,406,407,408,409,410,411,412,413};
class Pack
{ public,
void makePackOnce();
};
void Pack::makePackOnce()
{
int temp,r;
for(int i = 0; i < 53; i ++) // 洗一次牌
{
r= int(float(53 - i) * rand() / RAND_MAX) + i;
temp = pk[i];
pk[i] = pk[r];
pk[r] = temp;
cout << pk[i] << ","; // 打印洗好的牌
}
cout << pk[i] << endl; // 打印洗好的最后一张牌
}
9
多次洗牌程序
void Pack::makePackAny()
{
int temp,r,times;
cout << "\nTimes for take the pack is:";
cin >> times; // 输入拟洗牌次数
cout << endl;
for(int j =1; j <= times; j ++) // 洗 times次牌
{
cout << "Time," << j <<endl;
for(int i = 0; i < 53; i ++) //一次洗牌
{r= int(float(53 - i) * rand() / RAND_MAX) + i;
temp = pk[i];
k[i] = pk[r];
pk[r] = temp;
cout << pk[i] << ",";
}
cout << pk[i] << endl;
}
}
10
动态地改变随机数序列起点
void Pack::makePackAny()
{
int temp,r,times;
cout << "\nTimes for take the pack is:";
cin >> times; // 输入拟洗牌次数
cout << endl;
srand(time(NULL)); // 用时间函数设置随机数序列的起点
for(int j =1; j <= times; j ++) // times次洗牌
{
for(int i = 0; i < 53; i ++) // 其中的一次洗牌
{
r= int(float(53 - i) * rand() / RAND_MAX) + i;
temp = pk[i];
pk[i] = pk[r];
pk[r] = temp;
cout << pk[i] << ",";
}
cout << pk[i] << endl;
}
}
11
二分查询
基本思路是：如图 3.1所示，设数列为
a1,a2,…, an，被查找的数据为 x，则查找
首先对 am(m=(1+n)/2)进行，于是得到如下
三种情形,
· 若 x>am，则 x可能在区间 [ am+1,ar]中；
· 若 x<am，则 x可能在区间 [a1,am-1]中；
· 若 x=am，则以 am为所查找数据 x，求解结
束。
12
二分查找
a1 …… a2 am am-1 …… an
x
第 1次查找区间
第 2次查找区间 第 1次测试元素
目的元素
m S? r r?
an
13
一个递归函数
BinSrch（ s,r,x）
{
m = (s + r)/2;
if(x == am) 打印找到信息后返回 ;
else if(s >= r) 打印找不到信息,结束程序执行 ;
else if(x > am) 调用函数 binsrch（ m + 1,r,x） ;
else
调用函数 binSrch（ s,m - 1,x） ;
}
14
#include <iostream.h>
#include <stdlib.h>
class BinSearch
{
private,
double *Plist;
public,
BinSearch(double *,int);
void BinSrch(int,int,double );
~BinSearch();
};
BinSearch:,BinSearch(double *list,int ListLong)
{
Plist=new double[ListLong];
for(int i=0;i<ListLong;i++)
Plist[i]=list[i];
}
BinSearch::~BinSearch()
{
delete []Plist;
}
15
void BinSearch::BinSrch(int s,int r,double x)
{
int m;
m = (s + r)/2;
if(Plist[m] == x)
{
cout << "The order of" << x << "is" << m+1 << "in this sequence.";
return;
}
else if(s >= r)
{
cout << x <<"is not exist in the seguense.";
exit(-1);
}
else if(x > Plist[m])
BinSrch(m + 1,r,x); // 递归调用
else
BinSrch(s,m - 1,x); // 递归调用
}
void main()
{
double a[]={1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9}; // 数组（模拟表）声明及初始化
double x = 2.3;
int s = 0,r = 9;
BinSearch bs(a,10); //对象声明及初始化
bs.BinSrch(s,r,x); //调用成员函数
}
16
快速排序
基本思想是：在待排序序列中选定一个元
素 X(可以任选，也可以选第一个元素 )，称
为划分元素，用它将原序列整理 —— 划分
（ partitioning）为两个子序列，使其右边
的元素不比它大（小），使其左边的元素
不比它大（小）；然后再对两个子序列进
行上述划分；经过不断划分，直至将原序
列整理完毕为止 如果是升序的话，此处应
为小
17
快速排序
5 7 9 8 1 6 3 4 2
2 4 3 1 5 6 8 9 7
1 2 3 4 6 8 9 7
3 4 7 8 9
初始状态
第 1次划分结 果
18
二分分治算法
qkSort(int m,int n) // 序列由 m到 n
{
if(m < n)
{
调用划分函数 part(m,n,i);
递归调用 qkSort(m,i - 1);
递归调用 qkSort(i + 1,m);
}
else
{
输出排序结束信息
return;
}
}
19
划分函数
int part(int low,int high)
{
int i,j;
float p;
i = low; j = high; // 准备
P = a[low];
while(i < j)
{
while(i < j && a[j] >= p) // 逐步减小 j
j --;
a[i] = a[j];
while(i < j && a[i] <= p) // 逐步增大 i
i ++;
a[j] = a[i];
}
a[i] = p; // 放置划分元素
return(i);
}
20
程序
#include <iostream.h>
#define N 10
double a[] = {2.1,1.7,1.5,2.9,2.7,2.3,1.3,2.5,1.1,1.9};
class QuickSort
{
private,
int low,high;
public,
QuickSort( int,int );
void qkSort();
int part();
void prnt();
};
QuickSort::QuickSort( int l,int h )
{ low = l;
high = h;
}
void QuickSort::qkSort()
{
int i;
if( low < high )
{
i = part();
high = i - 1;
21
qkSort();
low = i + 1;
qkSort();
}
else
return;
}
int QuickSort::part()
{ int i,j;
double p;
i = low; j = high;
p = a[low];
while(i < j)
{ while(i < j && a[j] >= p)
j --;
a[i] = a[j];
while(i < j && a[i] <= p)
i ++;
a[j] = a[i];
}
a[i] = p;
return(i);
}
22
void QuickSort::prnt()
{
cout << "\nsorted sequence is:\n";
for(int i = 0; i <= N - 1; i++)
cout << a[i] << endl;
}
void main()
{
int m = 0,n = N-1;
QuickSort qs(m,n);
qs.qkSort();
qs.prnt();
}
23
二维数组
一个大小为 m的向量
array1 [m]
当其每个元素又都是一个同类型向量（注
意，向量的类型相同是指：大小相同且各
元素的类型相同）时，可以把它描述为一
个二维数组
array1 [m] [n]
24
二维数组的定义
在使用二维数组之前，应先使用声明语句
进行定义。定义一个空的二维数组即开辟
一个二维数组的存储空间，需要在声明语
句中给出如下内容,
· 数组名
· 数组元素的类型，即数组的类型
· 各维的大小
25
二维数组的初始化
1）对全部元素初始化可以用如下两种形
式
2）对部分元素初始化
26
表格处理
学号 数学 物理 英语 总分
9901 97.2 87.7 93.6
9902 87.5 91.3 90.7
9903 78.6 81.9 91.9
27
类的设计
# include <iostream.h>
static float a[][5] = {{9901,97.2,87.7,93.6,0},
{9902,87.5,91.3,90.7,0},
{9903,78.6,81.9,91.9,0}};
class ScoreTable
{
public,
void getScoreTable()
{
cout <<,\nNo,MT PH EN SUM,; // 打印表头
cout <<,\n------------------------------“; // 打印隔线
for(int i = 0; i <= 2; i ++)
{
cout <<,\n” << a[i][0] <<" "; // 打印学号
for(int j = 1; j <= 3; j ++)
{
a[i][4] += a[i][j] <<" "; // 求总分
cout << a[i][j]; // 打印学号及单科成绩
}
cout << a[i][4]; // 打印总分
}
}
};
28
日期转换
此题的算法很简单，若给定的是第 i月，则
应将第 1,2,3,…, i-1月的天数相加，再
加上该月的天数。
由于每月的天数不同，且闰年与否,2月
份的天数也不相同。为此，可以设计一个
有两行的二维数组如下,
{{0,31,28,31,30,31,30,31,31,30,31,30,31}
{0,31,29,31,30,31,30,31,31,30,31,30,31}}
当非闰年时，选第 0行；闰年时，选第 1行。
第 0个元素取 0的目的是为了使月份与列数
一致
29
判断闰年的算法
flag =(year % 4 = = 0 && year % 100 != 0) ||
year % 400 = = 0
当 flag为 1时,year为闰年；为 0时,year为
平年
30
类设计
#include <iostream.h>
static int day_tab[][13] = {{0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31}};
class Date_Day
{ int mDay;
int mYY,mMM,mDD;
public,
Date_Day(int year,int month,int day)
{
mYY = year; mMM = month; mDD = day;}
int getDayOfYear(); // 函数原型说明
};
int Date_Day::getDayOfYear( )
{
int flag;
flag=(mYY % 4 == 0 && mYY % 100 != 0) || mYY % 400 == 0; // 判定闰年
for(int j = 1; j < mMM; j++) mDD += day_tab[flag][j]; // 累加日数
return(mDD);
}
31
迷宫问题
迷宫的表示方法很多，最直接的方法是采
用矩阵模拟法，即把迷宫用一个二维数组
来模拟。在图 3.5中，把 (a)所示的迷宫模拟
为图（ b）所示的二维数组，用, 0”表示
可通行部分，用, 2”表示不可通行部分。
后面的解法都是基于该矩阵的
32
迷宫及其表示
0 1 2 3 4 5 6
0
1
2
3
4
5
6
33
2 2 2 2 2 2 2
2
2
2 2
2 2
2 2 2 2 2 2 2
2
2 2 2
2
2 2 2
2
0 0 0 0 0 0
0 0 0
0 0
0
0 0 0 0 0 0
0
0
34
算法设计
按照下面的规则边走边放线,
· 凡是走过的路径，都铺上一条线；
· 每到一个岔口，先走没有放过线的路；
· 凡是铺有两条线的路一定是死胡同，不
应再走。
35
在一个结点上的搜索
i-1,j
i,j i,j+1 i,j-1
i+1,j
36
不可到达结点
if(maze[i-1][j] == 2 && maze[i][j+1] == 2 && maze[i+1][j] == 2)
{j--; maze[i][j] = 2;}
else if(maze[i][j+1] = =2 && maze[i+1][j] == 2 && maze[i][j-1] == 2)
{i--; maze[i][j] = 2;}
else if(maze[i+1][j] == 2 && maze[i][j-1] == 2 && maze[i-1][j] == 2)
{j++; maze[i][j] = 2;}
else if(maze[i][j-1] == 2 && maze[i-1][j] == 2 && maze[i][j+1] == 2)
{i++; maze[i][j] = 2;}
37
已通过点
if (maze[i-1][j] == 0) i--;
else if(maze[i][j+1] == 0) j++;
else if(maze[i+1][j] == 0) i++;
else if(maze[i][j-1] == 0) j--;
else if(maze[i-1][j] == 1) i--;
else if(maze[i][j+1] == 1) j++;
else if(maze[i+1][j] == 1) i++;
else if(maze[i][j-1] == 1) j--;
38
探索结束的条件
探索结束的条件为,i >= Ei && j >= Ej
继续探索的条件为,i < Ei || j < Ej
39
类的界面设计
static int maze[ ][7] = {{2,2,2,2,2,2,2},
{2,0,0,0,0,0,2},
{2,0,2,0,2,0,2},
{2,0,0,2,0,2,2},
{2,2,0,2,0,2,2},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2}};
class Maze
{
int mSx,mSy,// 迷宫入口坐标
mEx,mEy; // 迷宫出口坐标
public,
Maze (int si,int sj,int ei,int ej)
{ mSx = si; mSy = sj; mEx = ei; mEy = ej;}
void getPathReserch ( );
};
40
成员函数 getPathReserch ( )
#include <iostream.h>
void Maze::getPathReserch ( )
{
int i = mSx,j = mSy;
int count = 0; // 记录搜索步数变量
while( j < mEy || i < mEy) // 在点（ i,j）上探索，不达出口时，反复进行搜索
{
// 处理死点
if ( maze[i-1][j]==2 && maze[i][j+1]==2 && maze[i+1][j]==2)
{ maze[i][j]=2; j--;}
else if( maze[i][j+1]==2 && maze[i+1][j]==2 && maze[i][j-1]==2)
{ maze[i][j]=2; i--; }
else if( maze[i+1][j]==2 && maze[i][j-1]==2 && maze[i-1][j]==2)
{ maze[i][j]=2; j++;}
else if( maze[i][j-1]==2 && maze[i-1][j]==2 && maze[i][j+1]==2)
{ maze[i][j]=2; i++;}
else maze[i][j]=1;
// 按顺时针顺序先走没有走过的点
if ( maze[i-1][j]==0) i--;
else if( maze[i][j+1]==0) j++;
else if( maze[i+1][j]==0) i++;
else if( maze[i][j-1]==0) j--;
41
// 按顺时针顺序走走过的点
else if( maze[i-1][j]==1) i--;
else if( maze[i][j+1]==1) j++;
else if( maze[i+1][j]==1) i++;
else if( maze[i][j-1]==1) j--;
count++; // 记录走过点数
}
// 打印探索结果
for(i = 0;i<= 6;i ++)
{
for(j = 0;j <= 6;j ++)
cout << maze[i][j];
cout << endl;
}
cout << "count = " << count; // 打印搜索步数
}
42
对象数组
多个同类型的对象可以用一个数组进行组
织。下面介绍创建对象数组时的一些特殊
问题。
对象数组声明
声明一个对象数组的一个目的是为它开辟
一个存储空间。声明语句格式如下,
类名 数组名 [对象个数 ] ；
43
对象数组初始化
在声明对象数组的同时，可以对数组元素
初始化。初始化用无名对象进行。如
Person a[3]={Person("Zhang",50,'m'),
Person("Cai",35,'w'),
Person("Wang",34,'m')};
44
对象数组元素的访问
#include <iostream.h>
#include <string.h>
#include "person.hpp"
void Person::disp()
{
cout<<name<<":"<<age<<":"<<sex<<"\n";
}
main(void)
{
Person a[3] = { Person( "Zhang",50,'m'),// 创建对象数组
Person( "Cai",35,'w'),
Person( "Wang",34,'m') };
For ( int i = 0; i < 3; i ++ ) // 输出各元素值
a[i].disp(); // 访问对象数组元素
}
45
指针
指针的概念
数组的指针形式
数组和指针参数
动态内存分配的概念
实例 —— 栈类
46
指针的概念
内存区域的访问与指针变量
指针变量及其声明语句
多级指针
指针变量的间接引用
指针的运算
47
内存区域的访问与指针变量
每一个变量都保存在内存中的一个可标识
的区域，它与这个区域的联系通过下面的
3个方面进行,
· 一个名字；
· 一个该存储区域的首地址；
· 一个与该变量的类型相联系存储区域的
大小和存储方式
48
指针变量及其声明语句
存放指针的变量称为指针变量。如同使用
一个变量之前必须先用声明语句进行声明
一样，使用一个指针变量之前也先要声明。
并且声明指针时也要指定指针的类型，如
语句
float * pf1;
声明了一个指向 float型的指针变量 pf1
这样声明的指针，并不具体地指向某个实
体，而只是指向某种类型
49
多级指针
指针变量也要存放在内存的某个区域，有
起始地址，也有类型，也可以用一个指针
指向它
这个指针称为指向指针的指针
50
二级指针
ppx px x
51
指针变量的间接引用
一个变量可以直接用其标识符指称，也可以用指
向它的指针指称。用指针指称它所指向的实体，
称为指针的间接引用（递引用）。如下面的一段
程序
float f1,f2;
float *pf1 = &f1;
*pf1 = 3.1415926; // 向间接引用 f1赋值
f2 = *pf1; // 间接引用 f1赋值
中的 *pf1是指 pf1所指向的变量 f1。上述引用的是
*pf1，并不是直接引用 f1。这称为变量 f1的间接引
用。记号 *称为间接引用运算符。它与取地址运
算符具有相同的优先级别与接合性，并互为逆运
算
52
一些表达式的含义
f,变量
pf,指向 f的指针变量，其值为 f的地址
&f,变量 f的地址，与 pf等价
*pf,pf所指向的变量，与 f等价
*(&f),与 *pf（即 f）等价
&(*pf),与 &f（即 pf）等价
53
指针的运算
由于指针的值是地址，所以它应具有无符
号整数的值。指针的运算就是地址运算。
由于地址本身的特征，也给指针的运算带
来一些限制，它只能进行
· 与整数相加、减运算；
· 同一数组中各元素地址间的关系运算与
相减运算；
· 赋值运算
54
数组的指针形式
数组名的实质
二维数组的指针形式
使用指针变量操作数组元素
55
数组名的实质
C++是以指针为重要特色的语言，其中非
常重要的是它的数组名和函数名都被解释
为指针
所得到结果都是同一个地址值。说明数组
名的值与数组的起始元素的地址值相同
56
对应关系
a+1 ~ &a[1] 或 *（ a+1） ~ a[1]
a+2 ~ &a[2] *（ a+2） ~ a[2]
…… ……
a+n ~ &a[n] *（ a+n） ~ a[n]
57
下标法和指针法实现操作
#include <iostream.h>
void main()
{
int a[10];
int i;
cout << "Input array a.\n";
for(i = 0; i < 10; i ++)
cin >> a[i];
for(i = 0; i < 10; i ++)
cout << a[i];
cout << endl;
}
58
#include <iostream.h>
void main()
{
int a[10];
int * pa;
cout << "Input array a.\n";
for(pa = a; pa < a + 10; pa ++)
cin >> *pa;
for(pa = a; pa < a + 10; pa ++)
cout << *pa; // 间接引用
cout << endl;
}
59
二维数组的指针形式
C++把二维数组解释为是由多行一维数组
组成的广义向量的有序集合，即并把二维
数组的数组名解释为一个广义向量的起始
行的指针；对于最终元素来说，它是一个
多级指针
60
地址等价关系
二级指针表示 一级指针表示 地址
a *a a[0] &a[0][0]
*a+1 a[0]+1 &a[0][1]
… … …
*a+j a[0]+j &a[0][j]
a+1 *(a+1) a[1] &a[1][0]
*(a+1)+1 a[1]+1 &a[1][1]
… … …
*(a+1)+j a[1]+j &a[1][j]
… … …
a+i *(a+i) a[i] &a[i][0]
*(a+i)+1 a[i]+1 &a[i][1]
… … …
*(a+i)+j a[i]+j &a[i][j]
61
例 3.2.2
#include <iostream.h>
int main()
{ short int a[5];
cout<<"a,"<<a<<",&a[0]:"<<&a[0]<<"\n"; // 数组名 ──元素地址
cout<<"a+1:"<<a+1<<",&a[1]:"<<&a[1]<<"\n";
cout<<"a+2:"<<a+2<<",&a[2]:"<<&a[2]<<"\n";
cout<<"a+3:"<<a+3<<",&a[3]:"<<&a[3]<<"\n";
cout<<"\n";
short int b[5][2];
cout<<"b,"<<b<<",&b[0]:"<<&b[0]<<"\n"; // 数组名 ──行地址
cout<<"b+1:"<<b+1<<",&b[1]:"<<&b[1]<<"\n";
cout<<"b+2:"<<b+2<<",&b[2]:"<<&b[2]<<"\n";
cout<<"b+3:"<<b+3<<",&b[3]:"<<&b[3]<<"\n";
cout<<"\n";
short int c[3][3][3];
cout<<"c,"<<c<<",&c[0]:"<<&c[0]<<"\n"; // 数组名 ──页地址
cout<<"c+1:"<<c+1<<",&c[1]:"<<&c[1]<<"\n";
cout<<"c+2:"<<c+2<<",&c[2]:"<<&c[2]<<"\n";
cout<<"c+3:"<<c+3<<",&c[3]:"<<&c[3]<<"\n";
return 0;
}
62
数组名指针的移动规律
C[2][0][0]
C[2][1][0]
C[2][2][0] C[2][2][1]
C[2][2][2]
C[1][0][0]
C[1][1][0]
C[1][2][0] C[1][2][1]
C[1][2][2]
C[0][0][0] C[0][0][1]
C[0][0][2]
C[0][1][0] C[0][1][1]
C[0][1][2]
C[0][2][0] C[1][2][1]
C[1][2][2]
b][0][0]
b[0][1]
b[1][0]
b[1][1]
b[2][0]
b[2][1]
b[3][0]
b[3][1]
b[4][0]
b[4][1]
a[0]
a[1]
a[2]
a[3]
a[4]
b
b +1
b +2
b +3
b +4
a
a +1
a +2
a +3
a +4
c +2
c
c +1
63
使用指针变量操作数组元素
数组名是指针常量，使用起来还不够灵活。
为了灵活地引用数组元素，应当使用指向
数组元素的指针变量。它与数组名不同之
处在于，它可以通过赋值指向类型相同的
其它数组的元素，而数组名只能指向某一
特定数组的元素
64
例 3.2.3
#include <iostream.h>
void main()
{
int a[ ] = {1,2,3,4,5};
int * pa = a; // 声明并初始化一个指向一维数组的指针
for(int i = 0; i < 5; i ++)
cout << *(pa + i) << ",";
cout << endl;
}
65
例 3.2.4
#include <iostream.h>
void main()
{
int b[ ][5] = {{11,12,13,14,15},
{21,22,23,24,25},
{31,32,33,34,35}};
int (* pb)[5]; // 声明一个指针，指向每行有 5个元素的
数组
pb = b; // 将二维数组名赋值给指向一维数组的指针 pb
for( int I = 0; I < 3; I ++,pb ++)
{
for(int j = 0; j < 5; j ++)
cout << *(*pb + j) << ","; // 引用二级指针
cout << endl;
}
}
66
例 3.2.5
#include <iostream.h>
void main()
{
int b[3][5]={{11,12,13,14,15},
{21,22,23,24,25},
{31,32,33,34,35}};
int (* pb)[5];
pb=b;
for( int i=0;i<3;i++)
{
for(int j=0;j<5;j++)
cout<<pb[i][j]<<","; // 指针名代替数组名
cout<<endl;
}
}
67
数组和指针参数
前面已经讨论了用数据作参数和用指针作
参数两种情形，形成传值调用和传址调用
两种参数传送方式。当要在两个函数间传
送数组时，也可以有这两种方式,
1）传值传送：用下标变量进行。
2）传址传送：用数组名或指向数组的指
针进行。
数组元素也是变量，用数组元素作参数与
用变量作参数一样，都是传值调用，它们
的使用方法也相同前面什么时候讨论过了？
建议将, 指针, 改为引用
68
用数组元素作参数
int main()
{
float a[3];
float fAverage;
float GetAverage1(float,float,float); // 原型声明
…
fAverage = GetAverage1(a[0],a[1],a[2]); // 函数调用
…
}
float GetAverage1(float a,float b,float c);// 函数定义
{
float Aver;
return (Aver = (a + b + c)/3.);
}
69
用数组名作参数
int main()
{
float a[3];
float fAverage;
float GetAverage2(float x[3]); // 原型声明
…
fAverage = GetAverage2(a); // 函数调用,数组名作参数
…
rerurn 0;
}
float GetAverage2(float x[3]) // 函数定义
{
float Aver;
return (Aver = (x[0] + x[1] + x[2])/3.);
}
70
用数组元素指针作参数
int main()
{
float a[3];
float *pa = a;
float fAverage;
int n = 3;
float GetAverage2(float *,int); // 原型声明
…
fAverage=GetAvegage1(pa,n); // 函数调用,数组名作参数
…
}
float GetAverage2(float * px,int m); // 函数定义
{
float Aver,Sum;
int i;
for(i = 0; i< m; i ++)
Sum += *(px+i);
return (Aver = Sum / m);
}
71
动态内存分配的概念
在 C++程序中，数组具有静态性，也就是说，数
组的大小必须是编译时可知的，不能在程序运行
的过程中才决定数组的大小
C++将每个函数的动态存储区分为栈和堆两种类
型。栈用于存放函数的所有动态局部变量（ auto
类型）以及函数调用和返回的有关信息，它严格
地按先进后出（ FILO）的规则管理栈中的对象，
从而使在嵌套结构的语句结构中，在靠外层的语
句块中定义的变量比靠内层的语句块中定义的变
量的作用域大
堆可以提供比栈灵活的内存管理。程序员在任何
时候都可以（用函数 new）从中获取自己需要大
小的内存，也可以在任何需要的时候、按任意顺
序（用函数 delete）释放在堆中占用的内存
72
求两个数组和的函数
double * dAddVector(double a[ ],double b[ ],int n)
{
double *p;
p=new double[n]; // 申请动态存储块
if(p==NULL)
{ // 判断申请是否成功
cout <<,memory request failed\n");
exit(-1);
}
for(int i = 0; i < n; i ++)
p[i] = a[i] + b[i];
return p;
}
73
实例 —— 栈类
堆栈是一种, FILO”（先进后出）或, LIFO”（后
进先出）的存储实体
它占有一片连续的存储单元，有两个端点：一个
端点是固定的，称为栈底；一个端点是活动的，
称为栈顶。操作只能在栈顶进行
建立一个栈先要开辟堆栈空间，为了指示栈顶位
置还要设置一个指针，称为栈顶指针
栈有两种操作,push（压入）与 pop（弹出）。
初建栈时，栈顶指针 sp指向栈底,栈顶是用于
存放下一个元素的
74
堆栈
sp
栈
空
间
8
sp
8
5
sp
8
5
sp
75
类 myStack的接口
应有如下两种成员数据,
buffer [MYSTACKSIZE] (栈空间 )
*sp (栈顶指针 )
还应有两个成员成员函数
push() (压入操作 )
pop() (弹出操作 )
76
栈类型定义
class myStack
{
long buffer [STACKSIZE]; // 开辟栈区
long * sp; // 设置栈顶指针
public,
myStack(); // 构造函数
~ MyStack(); // 释放函数
void push(long); // 压入数据
long pop(); // 弹出数据
};
77
myStack类的实现
构造函数
释放函数
压入函数 push()
弹出函数 pop()
78
构造函数
构造函数用以对类的初始化。栈在开始使
用之前，是个空栈，栈顶指针应指向栈底，
即指向数组的起始地址，所以构造函数应
定义为
MyStack::MyStack()
{
sp=buffer; //buffer为数组起始地址
}
79
释放函数
释放函数用以撤销栈，程序中对它没什么
特别要求。故可定义为,
MyStack::~MyStack()
{ }
80
压入函数 push()
具体的压栈操作分两步,
① 将（由参数传递来的）数据 data存入栈
顶指针所指向的单元，即
*sp=data;
② 修改栈顶指针，让栈顶指针指向下一个
单元，以便下一次把数据存在那里，即
sp++;
81
压入函数
void MyStack::push(long data)
{
if(sp>=buffer+MYSTACKSIZE)
cerr<<"Stack overflow!\n";
else {
* sp++=data;
cout<<data<<"is pushed.\n";
}
}
82
弹出函数 pop()
具体的弹出操作是与压入相反的两步,
① 修改栈顶指针，使其指向前一个位置，
即
- - sp;
② 向外部返回栈顶元素值，即
return *sp;
83
弹出函数的定义
long MyStack::pop()
{
if(sp<=buffer){
cerr<<"MyStack is empty!";
return 0;
}
return * - -sp;
}
84
MyStack类的接口
#define MYSTACKSIZE 10
class MyStack
{
long buffer [MYSTACKSIZE]; //开辟栈区
long * sp; //设置栈顶指针
public,
MyStack()
{
sp=buffer;
}
~ MyStack() { } // 释放函数
void push(long); // 压入数据
long pop(); // 弹出数据
};
85
#include <iostream.h>
#include "myStack.hpp"
void MyStack::push(long data)
{
if(sp>=buffer+MYSTACKSIZE)
cerr<<"Stack overflow!\n";
else
{ * sp++=data;
cout<<data<<"is pushed.\n";
}
}
long MyStack::pop()
{
if(sp<=buffer)
{
cerr<<"MyStack is empty!";
return 0;
}
return * - -sp;
}
86
字符串
字符串及其形式
字符串数组
87
字符串及其形式
字符串的数组形式
字符串的指针形式
88
字符串的数组形式
字符串是由一个有效字符序列组成的数据
结构，在 C++ 源程序中以一对双引号来表
示其起止界限，如
"Hello!C++."
所谓, 有效字符,,是指系统所允许使用
的字符
89
字符串操作函数
C++在运行库（ run-time library）中提供了
一些常用的字符串操作函数，如,
· 字符串复制函数,strcpy()；
· 字符串连接函数,strcat()；
· 字符查找函数,strchr()；
· 字符串比较函数,strcmp()；
为了使用这些函数应当在程序的头部加上
文件包含指令,
#include <string.h>
90
字符串的指针形式
由于指针与一维数组的对应性，字符串也
可以用指向字符的指针形式表示。它们虽
然都可以用于表示字符串，但二者之间还
是有很大差别
91
两种字符串形式的比较
项目 字符数组形式 字符指针形式
本质 数组，每个元素存放一个字符 指针变量：存放字符串首地址
定义
格式
char 字符数组名 [ ] =,字符串, ;
如 char s[20]="string";
char * 字符指针变量 =,字符串, ;
如 char *s;
访问
字符
使用下标变量直接访问 使用间接引用
输入
与
输出
方式
1.整体：数组名方式,cin >> s;
cout << s;
2.个体：（ 1）下标变量方式
（ 2）间接引用方式
1.整体：指针方式,cin >>
s;
cout << s;
2.个体：（ 1）类下标变量
方式
（ 2）间接引用方式
赋值
方式
不允许赋值，只能进行字符串拷贝。如
strcpy(s,"string");
允许赋值,s="string";也可以用字
符串拷贝函数,如 s=new char[7];
strcpy(s,"string");
运算
限制
数组名不允许进行赋值、加运算 字符指针可以进行赋值、减
92
字符串数组
当要同时处理几个相关字符串时，为了处
理上的方便，可以将它们存放在一个二维
数组中。由于二维数组要统一地定义列宽，
因此要求每个字符串的最大长度相同，即
必须按要处理的字符串中的最大长度来定
义所有的字符串的空间，并且这些字符串
被存放在一个连续的存储空间中
93
一个字符串数组的存储实例
L i B i n \0
Z h a n g B o \0
L i n g H a o T i \0
S u n J i a n g \0
W a n g Q i \0
94
字符串指针数组
Zhang Bo Ling Hao Ti Sun Jiang Wan Biao
name[0]
name[1]
name[2]
name[3]
name[4]
Li Bin
95
字典序将它们排序
# include <iostream.h>
# include <string.h>
void main()
{
char * string[3]={"Data structure","Computer design","C++ Language"};
char * p;
int i;
if (strcmp(string[0],string[1])>0)
{p=string[0];string[0]=string[1];string[1]=p;}
if (strcmp(string[0],string[2])>0)
{p=string[0];string[0]=string[2];string[2]=p;}
if (strcmp(string[1],string[2])>0)
{p=string[1];string[1]=string[2];string[2]=p;}
for (i=0;i<3;i++)
cout << string[i];
}
96
对象与指针
指向对象的指针与创建动态对象
实例 —— 链表
this指针
复制构造函数
97
指向对象的指针与创建动态对象
一个对象一旦被创建，系统就给它分配一
个存储空间，该存储空间的起点可以象数
据对象的地址一样，使用指针变量操作。
一个指向类的指针被初始化后便成为一个
指向某对象的指针，即存有对象首地址的
变量。也可以用一个对象地址来初始化一
个对象指针
98
实例 —— 链表
利用指向对象的指针把对象组织成为链表。
链表中的每个节点对象至少要有两部分成
员：数据与指针
指针用以指出与其逻辑相邻、但存储位置
不一定相邻的节点的地址
当指向的对象类型都相同时，形成同质链
表；否则形成异质链表
99
三个 Person对象形成的链表
&w Zhang
50
m
NULL
zh.name
zh.age
zh.sex
zh.next
zh
Wang
35
m
&c
w.name
w.age
w.sex
w.next
w
Cai
36
w
&zh
c.name
c.age
c.sex
c.next
c
head
100
创建对象链表
为了创建上述对象链表，应做两件事,
（ 1）在每个对象中增加一个指针 next，以
指向逻辑上的下一个对象。
（ 2）设置一个头指针，以指向逻辑上的
第一个对象；将逻辑上的最后一个对象中
的 next指针置空 (NULL)，以表示后面不再
指向任何对象
101
链表节点的对象的类定义
#include <string.h>
class Person{
char * name,sex;
int age;
Person * next; // 指向下一个对象节点的指针
public,
Person( char * n,int a,char s,Person *p = NULL)
{
name=new char[strlen(n)+1];// 立动态存储
strcpy(name,n);
age=a;
sex=s;
next=p;
}
~Person(){delete name;}
void disp();
};
102
成员函数 disp
#include <iostream.h>
#include "person5.hpp"
void Person::disp()
{
Person * ps;
cout<<"Head->"
<<name<<"-" // 处理第一个节点数据
<<age<<"-"
<<sex<<"->";
if(next) //if(next !=NULL)
{ // 从第二个节点开始处理,直到 ps=NULL
for(ps=next;ps;ps=ps->next)
{
cout<<ps->name<<"-"
<<ps->age<<"-"
<<ps->sex<<"->";
}
}
cout<<"END\n";
}
103
建立对象链表
#include <iostream.h>
#include "person5.hpp"
void main(void)
{
Person zh("Zhang",50,'m',NULL); // 尾节点对象
Person c("Cai",35,'w',&zh);
Person w("Wang",34,'m',&c);
Person *head=&w; // 头指针指向 w对象
head->disp();
}
104
this指针
this指针是隐含在对象成员函数内的一种
指针。当一个对象被创建后，它的每一个
成员函数都含有一个系统自动生成的隐含
的指针 ──this，用以保存这个对象的地址。
因此 this也称为, 指向本对象的指针,,
用它来存取类成员变量的格式为,
this -> 成员变量
105
复制构造函数
缺省复制构造函数
缺省复制构造函数的问题
106
缺省复制构造函数
需要一种特殊的构造函数 ──复制构造函
数。其特殊之处在于它只有一个参数，并
且是其所在类的对象的引用。其原型为
X,,X(const X&)
其中,X为复制构造函数所在类的类名
107
复制构造函数被调用三种时刻
·声明并初始化对象变量时,
·对象作为函数参数时,
·对象作为函数值被返回时。
108
例 3.4.3
class myStack{
int myStacksize;
long * buffer;
long * sp;
public,
myStack(int size)
{
myStacksize = size;
sp=buffer = new long[size];
cout<<"Initializing a stack.\n"; // 输出语句
}
~myStack()
{ cout << "Destructor is active.\n"; } // 输出语句
void push(long data);
long pop( );
};
109
测试程序
#include <iostream.h>
#include "myStack3.hpp"
int main()
{
myStack a(2); //创建对象 a
myStack b(3); //创建对象 b
b.push(351);
b.push(7075461);
b.push(3225);
cout<<endl;
cout<<b.pop()<<" is popped.\n";
cout<<b.pop()<<" is popped.\n";
cout<<b.pop()<<" is popped.\n";
cout<<b.pop()<<" is popped.\n";
}
110
缺省复制构造函数的问题
按缺省的复制构造函数的语义，语句
myString s2 = s1;
等价于
s2.str = s1.str;
即两个对象中的指针 s2.str与 s1.str指向同一个串。
于是，当对象 s1 和 s2被撤销时，它们的释放函
数都要删除同一个串。先撤销一个，如 s2被撤销
后,s1将无所指向。同一个串被删除两次是不允
许的。在这种情况下，程序员必须定义自己的复
制构造函数，其要领是使两个对象名各有自己的
实体
111
枚举
枚举及其定义
枚举应用举例
112
枚举及其定义
枚举的概念
枚举类型的定义和变量的生成
枚举变量的初始化
枚举变量的运算
113
枚举的概念
WeekDay,Color这样的代表一组整数的数
据类型都称为枚举（ enum）类型。它们都
是用户自定义的类型
enum（枚举）类型是一种当一个变量具有
有限个可能值，并且这些值有两个特点,
· 可以取整型值,
· 每个值可以有一个名字
114
枚举类型的定义和变量的生成
定义 enum类型的基本格式为,
enum 枚举类型名 { 枚举成员表列 };
另一种形式是在定义一个枚举类型的同时，
声明一些变量属于这种类型，其形式为
enum 枚举类型名 { 枚举成员表列 } 变量
名表列 ;
115
枚举变量的初始化
C++中枚举常量的类型隐含地规定为 unsigned
char或 int类型，并且第一个枚举常量的值为 0,以
后依次增 1。 C++也允许程序员显式地在定义中指
定部分或全部枚举常量的值。如
enum week_day｛ Sunday = 7,
Monday = 1,// 下面的成员逐项加 1
Tuesday,
Wednesday,
Thursday,
Friday,
Saturday｝ ;
缺省说明的枚举常量仍按在前一枚举常量值的
基准上依次增 1
116
枚举变量的运算
枚举变量可以进行赋值（仅限于所在类型的枚举
常量）或关系运算。如
enum Coin{ Penny,
Nickel,
Dime,
Quarter,
Half_dollar,
Dollar
} money;
money= Dime;
if( money == Quarter)
…
117
枚举应用举例
# include <iostream.h>
enum WeekDay{ Mon = 1,Tue,Wed,Thu,Fri,Sat,Sun };
static char * day[ ] = {" ",
"Mon","Tue","Wed","Thu","Fri","Sat","Sun" };
class WhatDay
{
WeekDay mToday;
public,
WhatDay(int n)
{
mToday = WeekDay(n); // 必须强制类型转换
}
void thisDayIs();
}；
void WhatDay,,thisDayIs ()
{
cout << "Tomorrow is:" << day [mToday] << endl;
}
#include <iostream.h>
118
void main()
{
char f; // 标志变量
int i = 1;
do // 用户输入
{
//i = 7? i = 1, i ++;
i > 7? i = 1, i;
cout << "Totay is " << day[i++] << "?(y/n):";
cin >> f;
} while(!(f == 'y' || f == 'Y'));
WhatDay tomorrow(i);
tomorrow.thisDayIs ();
}
119
共用体
共用体及其定义
共用体变量的生成与共用体成员的引用
共用体应用举例
120
共用体及其定义
在每一个类中，所有的数据成员都要单独
占用一个存储空间。但是，有些问题中，
数据成员并不要同时出现、使用
C++为解决这类问题，提供了一种特别的
数据类型,union(共用体 )。顾名思义，它
能提供多个数据共用同一个存储空间的存
储
121
共用体的定义
union 共用体名
{
成员 1定义 ；
成员 2定义 ；
…
成员 n定义 ；
}；
122
共用体变量生成
与结构体相似，共用体变量也可以用以下
几种方式生成，并可以同时进行初始化
1）用共用体类型名说明
2）定义共用体类型的同时生成变量
3）不定义类型直接定义变量
123
共用体成员引用
用成员运算符直接引用
由指向共用体变量的指针，使用指向运算
符引用
由指向共用体变量的指针，用成员运算符
间接引用
124
共用体应用举例
制作学校的人员管理卡片
使用无名共用体作为成员的 Person类
125
制作学校的人员管理卡片
对于不同职业的人员,,级别, 的含义不
同,
· 对学生为年级 (grade),int 型
· 对教师为职称 (title),char * 型
· 对干部为职务 (rank),char * 型
126
共用体具有如下特点,
· 它以关键字 union代替关键字 class;
· 它的所有成员都是公开的；
· 它的所有数据成员都开始于同一地址。
127
Level,:level(char prfs)
{
switch(prfs)
{
case 's',
cout<<"grade:";
cin>>grad;
break;
case 'c',
cout<<"rank:";
cin>>rank;
break;
case 't',
cout<<"title:";
cin>>title;
break;
}
}
128
level::disp(char prfs)
{
switch(prfs)
{
case 's',
cout<<grade<<'\n';
break;
case 'c',
cout<<rank<<'\n';
break;
case 't',
cout<<title<<'\n';
break;
}
}
129
共用体作为类的成员
#include "string1.hpp" // 来自例 3.2.13
class Person
{ string name;
int age;
char profession;
union level
{
int grade;
char rank[8];
char title[10];
level (char); // 共用体构造函数声明
void disp(char); // 共用体成员函数
}school; // 共用体类成员,school为共用体变量
public,
Person(char *,int,char);
~Person(){}
void disp();
};
#include <iostream.h>
#include "person3.hpp"
Person::level::level(char prfs) // 共用体构造函数定义
{
switch(prfs)
{
130
case 's',
cout<<"grade:";
cin>>grade;
break;
case 'c',
cout<<"rank:";
cin>>rank;
break;
case 't',
cout<<"title:";
cin>>title;
break;
}
}
Person
::Person(char *nm,int ag,char prfs):name(nm),school(prfs) // 构造函数
{
age=ag;
profession=prfs;
}
131
void Person::level
::disp(char prfs) //共用体成员函数定义
{
switch(prfs)
{
case 's',
cout<<grade<<"\n";
break;
case 'c',
cout<<rank<<"\n";
break;
case 't',
cout<<title<<"\n";
break;
}
}
void Person::disp() // 类成员函数定义
{
name.print();
cout<<age<<"\n";
cout<<profession<<"\n";
school.disp(profession);
}
132
使用无名共用体作为成员的 Person类
#include "string1.hpp"
class Person
{
string name;
int age;
char profession;
union
{
int grade;
char rank[10];
char title[15];
}; // 无名共用体 无成员函数
public,
Person(char *,int,char);
~Person(){}
void disp();
};
133
#include <iostream.h>
#include "person4.hpp"
Person
,:Person(char *nm,int ag,char prfs):name(nm) // 构造函数
{
age=ag;
profession=prfs;
switch(prfs)
{
case 's',
cout<<"grade:";
cin>>grade;
break;
case 'c',
cout<<"rank:";
cin>>rank;
break;
case 't',
cout<<"title:";
cin>>title;
break;
}
}
134
void Person::disp() //成员函数
{
name.print();
cout<<age<<"\n";
cout<<profession<<"\n";
switch(profession)
{
case 's',
cout<<grade<<"\n";
break;
case 'c',
cout<<rank<<"\n";
break;
case 't',
cout<<title<<"\n";
break;
}
}
135
关于声明符的进一步讨论
声明符
复杂声明
类型定义符,typedef
136
声明符
（１）存储类关键字
auto register static extern
（２）类型关键字
char int signed unsigned short long foat double
* (指针 ) & (引用 ) [ ] (数组 ) ( ) (函数 )
enum (枚举 ) class (类 ) struct (构造体 ) union (共用体 )
（３）修饰符
( ) (运算优先修饰 )
const (阻止写与外部连接 )
volatile(指明一个实体可以被修改 )
inline(内嵌 )
interrupt(书写中断函数 )
friend(友元数 )
（４）其它
137
复杂声明
存储类关键字 类型声明符 逗号分隔的
声明项表 ;
其中，声明符项中名字可以是一些类型组
合
138
类型定义符,typedef
C++还允许程序员用关键字 typedef自己定
义一个类型名。定义语句的格式是,
typedef 类型符 名字 ;
第 3章 数据结构
2
第 3章 数据结构
数组
指针
字符串
对象与指针
枚举
共用体
关于声明符的进一步讨论
3
数组
一维数组
二维数组
对象数组
4
一维数组的定义
一维数组（向量）是一种整体定义、个别使用的
数据结构。作为一个整体，数组有如下特征,
· 名字：用以对数组各元素的整体标识，这个名
字称为数组名；
· 类型：数组各元素的类型；
· 大小：可容纳的数组元素个数（注意，不是字
节数）；
· 存储：占有一个连续的内存空间。
与简单变量一样，上述特征要用声明语句定义，
格式如下,
类型 数组名 [大小 ]；
5
一维数组的初始化
数组的声明语句是定义性声明，在声明的
同时可以对数组各元素初始化，初始化表
达式按元素顺序依次写在一对花括号内
C + + 语言还允许使用下列初始化的省略方
式
1）初始化时也可以不指定数组的大小，
编译器会根据初始值的个数自动决定数组
大小
2）允许省略为 0的元素值
3）当最后的几个元素初值为 0时，可以只
写出前面的数列，但数组体积不可省略
6
数组元素
作为数组的个体，数组中的每个元素都有
如下特征,
它们的类型是相同的
每个元素用数组名加上括在方括号中的下
标表示。下标表示该元素在数组中的顺序，
下标以 0为起始计数
7
模拟洗扑克牌
基本思路是：将 54张扑克牌统一编号为：
0,1,2,……,52,53，然后随机地从中一一抽取
一张牌，并依次放起，形成新的序列。具
体要解决两个问题：如何存储 54张扑克牌
以及在此基础上如何一一抽取
随机抽牌算法
在 0到 53之间产生一个随机数 r，将 pk[0]与
pk[r]交换
8
类结构
#include <iostream.h>
#include <stdlib.h>
int pk[qqchyan1][] = { 501,502,
101,102,103,104,105,106,107,108,109,110,111,112,113,
201,202,203,204,205,206,207,208,209,210,211,212,213,
301,302,303,304,305,306,307,308,309,310,311,312,313,
401,402,403,404,405,406,407,408,409,410,411,412,413};
class Pack
{ public,
void makePackOnce();
};
void Pack::makePackOnce()
{
int temp,r;
for(int i = 0; i < 53; i ++) // 洗一次牌
{
r= int(float(53 - i) * rand() / RAND_MAX) + i;
temp = pk[i];
pk[i] = pk[r];
pk[r] = temp;
cout << pk[i] << ","; // 打印洗好的牌
}
cout << pk[i] << endl; // 打印洗好的最后一张牌
}
9
多次洗牌程序
void Pack::makePackAny()
{
int temp,r,times;
cout << "\nTimes for take the pack is:";
cin >> times; // 输入拟洗牌次数
cout << endl;
for(int j =1; j <= times; j ++) // 洗 times次牌
{
cout << "Time," << j <<endl;
for(int i = 0; i < 53; i ++) //一次洗牌
{r= int(float(53 - i) * rand() / RAND_MAX) + i;
temp = pk[i];
k[i] = pk[r];
pk[r] = temp;
cout << pk[i] << ",";
}
cout << pk[i] << endl;
}
}
10
动态地改变随机数序列起点
void Pack::makePackAny()
{
int temp,r,times;
cout << "\nTimes for take the pack is:";
cin >> times; // 输入拟洗牌次数
cout << endl;
srand(time(NULL)); // 用时间函数设置随机数序列的起点
for(int j =1; j <= times; j ++) // times次洗牌
{
for(int i = 0; i < 53; i ++) // 其中的一次洗牌
{
r= int(float(53 - i) * rand() / RAND_MAX) + i;
temp = pk[i];
pk[i] = pk[r];
pk[r] = temp;
cout << pk[i] << ",";
}
cout << pk[i] << endl;
}
}
11
二分查询
基本思路是：如图 3.1所示，设数列为
a1,a2,…, an，被查找的数据为 x，则查找
首先对 am(m=(1+n)/2)进行，于是得到如下
三种情形,
· 若 x>am，则 x可能在区间 [ am+1,ar]中；
· 若 x<am，则 x可能在区间 [a1,am-1]中；
· 若 x=am，则以 am为所查找数据 x，求解结
束。
12
二分查找
a1 …… a2 am am-1 …… an
x
第 1次查找区间
第 2次查找区间 第 1次测试元素
目的元素
m S? r r?
an
13
一个递归函数
BinSrch（ s,r,x）
{
m = (s + r)/2;
if(x == am) 打印找到信息后返回 ;
else if(s >= r) 打印找不到信息,结束程序执行 ;
else if(x > am) 调用函数 binsrch（ m + 1,r,x） ;
else
调用函数 binSrch（ s,m - 1,x） ;
}
14
#include <iostream.h>
#include <stdlib.h>
class BinSearch
{
private,
double *Plist;
public,
BinSearch(double *,int);
void BinSrch(int,int,double );
~BinSearch();
};
BinSearch:,BinSearch(double *list,int ListLong)
{
Plist=new double[ListLong];
for(int i=0;i<ListLong;i++)
Plist[i]=list[i];
}
BinSearch::~BinSearch()
{
delete []Plist;
}
15
void BinSearch::BinSrch(int s,int r,double x)
{
int m;
m = (s + r)/2;
if(Plist[m] == x)
{
cout << "The order of" << x << "is" << m+1 << "in this sequence.";
return;
}
else if(s >= r)
{
cout << x <<"is not exist in the seguense.";
exit(-1);
}
else if(x > Plist[m])
BinSrch(m + 1,r,x); // 递归调用
else
BinSrch(s,m - 1,x); // 递归调用
}
void main()
{
double a[]={1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9}; // 数组（模拟表）声明及初始化
double x = 2.3;
int s = 0,r = 9;
BinSearch bs(a,10); //对象声明及初始化
bs.BinSrch(s,r,x); //调用成员函数
}
16
快速排序
基本思想是：在待排序序列中选定一个元
素 X(可以任选，也可以选第一个元素 )，称
为划分元素，用它将原序列整理 —— 划分
（ partitioning）为两个子序列，使其右边
的元素不比它大（小），使其左边的元素
不比它大（小）；然后再对两个子序列进
行上述划分；经过不断划分，直至将原序
列整理完毕为止 如果是升序的话，此处应
为小
17
快速排序
5 7 9 8 1 6 3 4 2
2 4 3 1 5 6 8 9 7
1 2 3 4 6 8 9 7
3 4 7 8 9
初始状态
第 1次划分结 果
18
二分分治算法
qkSort(int m,int n) // 序列由 m到 n
{
if(m < n)
{
调用划分函数 part(m,n,i);
递归调用 qkSort(m,i - 1);
递归调用 qkSort(i + 1,m);
}
else
{
输出排序结束信息
return;
}
}
19
划分函数
int part(int low,int high)
{
int i,j;
float p;
i = low; j = high; // 准备
P = a[low];
while(i < j)
{
while(i < j && a[j] >= p) // 逐步减小 j
j --;
a[i] = a[j];
while(i < j && a[i] <= p) // 逐步增大 i
i ++;
a[j] = a[i];
}
a[i] = p; // 放置划分元素
return(i);
}
20
程序
#include <iostream.h>
#define N 10
double a[] = {2.1,1.7,1.5,2.9,2.7,2.3,1.3,2.5,1.1,1.9};
class QuickSort
{
private,
int low,high;
public,
QuickSort( int,int );
void qkSort();
int part();
void prnt();
};
QuickSort::QuickSort( int l,int h )
{ low = l;
high = h;
}
void QuickSort::qkSort()
{
int i;
if( low < high )
{
i = part();
high = i - 1;
21
qkSort();
low = i + 1;
qkSort();
}
else
return;
}
int QuickSort::part()
{ int i,j;
double p;
i = low; j = high;
p = a[low];
while(i < j)
{ while(i < j && a[j] >= p)
j --;
a[i] = a[j];
while(i < j && a[i] <= p)
i ++;
a[j] = a[i];
}
a[i] = p;
return(i);
}
22
void QuickSort::prnt()
{
cout << "\nsorted sequence is:\n";
for(int i = 0; i <= N - 1; i++)
cout << a[i] << endl;
}
void main()
{
int m = 0,n = N-1;
QuickSort qs(m,n);
qs.qkSort();
qs.prnt();
}
23
二维数组
一个大小为 m的向量
array1 [m]
当其每个元素又都是一个同类型向量（注
意，向量的类型相同是指：大小相同且各
元素的类型相同）时，可以把它描述为一
个二维数组
array1 [m] [n]
24
二维数组的定义
在使用二维数组之前，应先使用声明语句
进行定义。定义一个空的二维数组即开辟
一个二维数组的存储空间，需要在声明语
句中给出如下内容,
· 数组名
· 数组元素的类型，即数组的类型
· 各维的大小
25
二维数组的初始化
1）对全部元素初始化可以用如下两种形
式
2）对部分元素初始化
26
表格处理
学号 数学 物理 英语 总分
9901 97.2 87.7 93.6
9902 87.5 91.3 90.7
9903 78.6 81.9 91.9
27
类的设计
# include <iostream.h>
static float a[][5] = {{9901,97.2,87.7,93.6,0},
{9902,87.5,91.3,90.7,0},
{9903,78.6,81.9,91.9,0}};
class ScoreTable
{
public,
void getScoreTable()
{
cout <<,\nNo,MT PH EN SUM,; // 打印表头
cout <<,\n------------------------------“; // 打印隔线
for(int i = 0; i <= 2; i ++)
{
cout <<,\n” << a[i][0] <<" "; // 打印学号
for(int j = 1; j <= 3; j ++)
{
a[i][4] += a[i][j] <<" "; // 求总分
cout << a[i][j]; // 打印学号及单科成绩
}
cout << a[i][4]; // 打印总分
}
}
};
28
日期转换
此题的算法很简单，若给定的是第 i月，则
应将第 1,2,3,…, i-1月的天数相加，再
加上该月的天数。
由于每月的天数不同，且闰年与否,2月
份的天数也不相同。为此，可以设计一个
有两行的二维数组如下,
{{0,31,28,31,30,31,30,31,31,30,31,30,31}
{0,31,29,31,30,31,30,31,31,30,31,30,31}}
当非闰年时，选第 0行；闰年时，选第 1行。
第 0个元素取 0的目的是为了使月份与列数
一致
29
判断闰年的算法
flag =(year % 4 = = 0 && year % 100 != 0) ||
year % 400 = = 0
当 flag为 1时,year为闰年；为 0时,year为
平年
30
类设计
#include <iostream.h>
static int day_tab[][13] = {{0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31}};
class Date_Day
{ int mDay;
int mYY,mMM,mDD;
public,
Date_Day(int year,int month,int day)
{
mYY = year; mMM = month; mDD = day;}
int getDayOfYear(); // 函数原型说明
};
int Date_Day::getDayOfYear( )
{
int flag;
flag=(mYY % 4 == 0 && mYY % 100 != 0) || mYY % 400 == 0; // 判定闰年
for(int j = 1; j < mMM; j++) mDD += day_tab[flag][j]; // 累加日数
return(mDD);
}
31
迷宫问题
迷宫的表示方法很多，最直接的方法是采
用矩阵模拟法，即把迷宫用一个二维数组
来模拟。在图 3.5中，把 (a)所示的迷宫模拟
为图（ b）所示的二维数组，用, 0”表示
可通行部分，用, 2”表示不可通行部分。
后面的解法都是基于该矩阵的
32
迷宫及其表示
0 1 2 3 4 5 6
0
1
2
3
4
5
6
33
2 2 2 2 2 2 2
2
2
2 2
2 2
2 2 2 2 2 2 2
2
2 2 2
2
2 2 2
2
0 0 0 0 0 0
0 0 0
0 0
0
0 0 0 0 0 0
0
0
34
算法设计
按照下面的规则边走边放线,
· 凡是走过的路径，都铺上一条线；
· 每到一个岔口，先走没有放过线的路；
· 凡是铺有两条线的路一定是死胡同，不
应再走。
35
在一个结点上的搜索
i-1,j
i,j i,j+1 i,j-1
i+1,j
36
不可到达结点
if(maze[i-1][j] == 2 && maze[i][j+1] == 2 && maze[i+1][j] == 2)
{j--; maze[i][j] = 2;}
else if(maze[i][j+1] = =2 && maze[i+1][j] == 2 && maze[i][j-1] == 2)
{i--; maze[i][j] = 2;}
else if(maze[i+1][j] == 2 && maze[i][j-1] == 2 && maze[i-1][j] == 2)
{j++; maze[i][j] = 2;}
else if(maze[i][j-1] == 2 && maze[i-1][j] == 2 && maze[i][j+1] == 2)
{i++; maze[i][j] = 2;}
37
已通过点
if (maze[i-1][j] == 0) i--;
else if(maze[i][j+1] == 0) j++;
else if(maze[i+1][j] == 0) i++;
else if(maze[i][j-1] == 0) j--;
else if(maze[i-1][j] == 1) i--;
else if(maze[i][j+1] == 1) j++;
else if(maze[i+1][j] == 1) i++;
else if(maze[i][j-1] == 1) j--;
38
探索结束的条件
探索结束的条件为,i >= Ei && j >= Ej
继续探索的条件为,i < Ei || j < Ej
39
类的界面设计
static int maze[ ][7] = {{2,2,2,2,2,2,2},
{2,0,0,0,0,0,2},
{2,0,2,0,2,0,2},
{2,0,0,2,0,2,2},
{2,2,0,2,0,2,2},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2}};
class Maze
{
int mSx,mSy,// 迷宫入口坐标
mEx,mEy; // 迷宫出口坐标
public,
Maze (int si,int sj,int ei,int ej)
{ mSx = si; mSy = sj; mEx = ei; mEy = ej;}
void getPathReserch ( );
};
40
成员函数 getPathReserch ( )
#include <iostream.h>
void Maze::getPathReserch ( )
{
int i = mSx,j = mSy;
int count = 0; // 记录搜索步数变量
while( j < mEy || i < mEy) // 在点（ i,j）上探索，不达出口时，反复进行搜索
{
// 处理死点
if ( maze[i-1][j]==2 && maze[i][j+1]==2 && maze[i+1][j]==2)
{ maze[i][j]=2; j--;}
else if( maze[i][j+1]==2 && maze[i+1][j]==2 && maze[i][j-1]==2)
{ maze[i][j]=2; i--; }
else if( maze[i+1][j]==2 && maze[i][j-1]==2 && maze[i-1][j]==2)
{ maze[i][j]=2; j++;}
else if( maze[i][j-1]==2 && maze[i-1][j]==2 && maze[i][j+1]==2)
{ maze[i][j]=2; i++;}
else maze[i][j]=1;
// 按顺时针顺序先走没有走过的点
if ( maze[i-1][j]==0) i--;
else if( maze[i][j+1]==0) j++;
else if( maze[i+1][j]==0) i++;
else if( maze[i][j-1]==0) j--;
41
// 按顺时针顺序走走过的点
else if( maze[i-1][j]==1) i--;
else if( maze[i][j+1]==1) j++;
else if( maze[i+1][j]==1) i++;
else if( maze[i][j-1]==1) j--;
count++; // 记录走过点数
}
// 打印探索结果
for(i = 0;i<= 6;i ++)
{
for(j = 0;j <= 6;j ++)
cout << maze[i][j];
cout << endl;
}
cout << "count = " << count; // 打印搜索步数
}
42
对象数组
多个同类型的对象可以用一个数组进行组
织。下面介绍创建对象数组时的一些特殊
问题。
对象数组声明
声明一个对象数组的一个目的是为它开辟
一个存储空间。声明语句格式如下,
类名 数组名 [对象个数 ] ；
43
对象数组初始化
在声明对象数组的同时，可以对数组元素
初始化。初始化用无名对象进行。如
Person a[3]={Person("Zhang",50,'m'),
Person("Cai",35,'w'),
Person("Wang",34,'m')};
44
对象数组元素的访问
#include <iostream.h>
#include <string.h>
#include "person.hpp"
void Person::disp()
{
cout<<name<<":"<<age<<":"<<sex<<"\n";
}
main(void)
{
Person a[3] = { Person( "Zhang",50,'m'),// 创建对象数组
Person( "Cai",35,'w'),
Person( "Wang",34,'m') };
For ( int i = 0; i < 3; i ++ ) // 输出各元素值
a[i].disp(); // 访问对象数组元素
}
45
指针
指针的概念
数组的指针形式
数组和指针参数
动态内存分配的概念
实例 —— 栈类
46
指针的概念
内存区域的访问与指针变量
指针变量及其声明语句
多级指针
指针变量的间接引用
指针的运算
47
内存区域的访问与指针变量
每一个变量都保存在内存中的一个可标识
的区域，它与这个区域的联系通过下面的
3个方面进行,
· 一个名字；
· 一个该存储区域的首地址；
· 一个与该变量的类型相联系存储区域的
大小和存储方式
48
指针变量及其声明语句
存放指针的变量称为指针变量。如同使用
一个变量之前必须先用声明语句进行声明
一样，使用一个指针变量之前也先要声明。
并且声明指针时也要指定指针的类型，如
语句
float * pf1;
声明了一个指向 float型的指针变量 pf1
这样声明的指针，并不具体地指向某个实
体，而只是指向某种类型
49
多级指针
指针变量也要存放在内存的某个区域，有
起始地址，也有类型，也可以用一个指针
指向它
这个指针称为指向指针的指针
50
二级指针
ppx px x
51
指针变量的间接引用
一个变量可以直接用其标识符指称，也可以用指
向它的指针指称。用指针指称它所指向的实体，
称为指针的间接引用（递引用）。如下面的一段
程序
float f1,f2;
float *pf1 = &f1;
*pf1 = 3.1415926; // 向间接引用 f1赋值
f2 = *pf1; // 间接引用 f1赋值
中的 *pf1是指 pf1所指向的变量 f1。上述引用的是
*pf1，并不是直接引用 f1。这称为变量 f1的间接引
用。记号 *称为间接引用运算符。它与取地址运
算符具有相同的优先级别与接合性，并互为逆运
算
52
一些表达式的含义
f,变量
pf,指向 f的指针变量，其值为 f的地址
&f,变量 f的地址，与 pf等价
*pf,pf所指向的变量，与 f等价
*(&f),与 *pf（即 f）等价
&(*pf),与 &f（即 pf）等价
53
指针的运算
由于指针的值是地址，所以它应具有无符
号整数的值。指针的运算就是地址运算。
由于地址本身的特征，也给指针的运算带
来一些限制，它只能进行
· 与整数相加、减运算；
· 同一数组中各元素地址间的关系运算与
相减运算；
· 赋值运算
54
数组的指针形式
数组名的实质
二维数组的指针形式
使用指针变量操作数组元素
55
数组名的实质
C++是以指针为重要特色的语言，其中非
常重要的是它的数组名和函数名都被解释
为指针
所得到结果都是同一个地址值。说明数组
名的值与数组的起始元素的地址值相同
56
对应关系
a+1 ~ &a[1] 或 *（ a+1） ~ a[1]
a+2 ~ &a[2] *（ a+2） ~ a[2]
…… ……
a+n ~ &a[n] *（ a+n） ~ a[n]
57
下标法和指针法实现操作
#include <iostream.h>
void main()
{
int a[10];
int i;
cout << "Input array a.\n";
for(i = 0; i < 10; i ++)
cin >> a[i];
for(i = 0; i < 10; i ++)
cout << a[i];
cout << endl;
}
58
#include <iostream.h>
void main()
{
int a[10];
int * pa;
cout << "Input array a.\n";
for(pa = a; pa < a + 10; pa ++)
cin >> *pa;
for(pa = a; pa < a + 10; pa ++)
cout << *pa; // 间接引用
cout << endl;
}
59
二维数组的指针形式
C++把二维数组解释为是由多行一维数组
组成的广义向量的有序集合，即并把二维
数组的数组名解释为一个广义向量的起始
行的指针；对于最终元素来说，它是一个
多级指针
60
地址等价关系
二级指针表示 一级指针表示 地址
a *a a[0] &a[0][0]
*a+1 a[0]+1 &a[0][1]
… … …
*a+j a[0]+j &a[0][j]
a+1 *(a+1) a[1] &a[1][0]
*(a+1)+1 a[1]+1 &a[1][1]
… … …
*(a+1)+j a[1]+j &a[1][j]
… … …
a+i *(a+i) a[i] &a[i][0]
*(a+i)+1 a[i]+1 &a[i][1]
… … …
*(a+i)+j a[i]+j &a[i][j]
61
例 3.2.2
#include <iostream.h>
int main()
{ short int a[5];
cout<<"a,"<<a<<",&a[0]:"<<&a[0]<<"\n"; // 数组名 ──元素地址
cout<<"a+1:"<<a+1<<",&a[1]:"<<&a[1]<<"\n";
cout<<"a+2:"<<a+2<<",&a[2]:"<<&a[2]<<"\n";
cout<<"a+3:"<<a+3<<",&a[3]:"<<&a[3]<<"\n";
cout<<"\n";
short int b[5][2];
cout<<"b,"<<b<<",&b[0]:"<<&b[0]<<"\n"; // 数组名 ──行地址
cout<<"b+1:"<<b+1<<",&b[1]:"<<&b[1]<<"\n";
cout<<"b+2:"<<b+2<<",&b[2]:"<<&b[2]<<"\n";
cout<<"b+3:"<<b+3<<",&b[3]:"<<&b[3]<<"\n";
cout<<"\n";
short int c[3][3][3];
cout<<"c,"<<c<<",&c[0]:"<<&c[0]<<"\n"; // 数组名 ──页地址
cout<<"c+1:"<<c+1<<",&c[1]:"<<&c[1]<<"\n";
cout<<"c+2:"<<c+2<<",&c[2]:"<<&c[2]<<"\n";
cout<<"c+3:"<<c+3<<",&c[3]:"<<&c[3]<<"\n";
return 0;
}
62
数组名指针的移动规律
C[2][0][0]
C[2][1][0]
C[2][2][0] C[2][2][1]
C[2][2][2]
C[1][0][0]
C[1][1][0]
C[1][2][0] C[1][2][1]
C[1][2][2]
C[0][0][0] C[0][0][1]
C[0][0][2]
C[0][1][0] C[0][1][1]
C[0][1][2]
C[0][2][0] C[1][2][1]
C[1][2][2]
b][0][0]
b[0][1]
b[1][0]
b[1][1]
b[2][0]
b[2][1]
b[3][0]
b[3][1]
b[4][0]
b[4][1]
a[0]
a[1]
a[2]
a[3]
a[4]
b
b +1
b +2
b +3
b +4
a
a +1
a +2
a +3
a +4
c +2
c
c +1
63
使用指针变量操作数组元素
数组名是指针常量，使用起来还不够灵活。
为了灵活地引用数组元素，应当使用指向
数组元素的指针变量。它与数组名不同之
处在于，它可以通过赋值指向类型相同的
其它数组的元素，而数组名只能指向某一
特定数组的元素
64
例 3.2.3
#include <iostream.h>
void main()
{
int a[ ] = {1,2,3,4,5};
int * pa = a; // 声明并初始化一个指向一维数组的指针
for(int i = 0; i < 5; i ++)
cout << *(pa + i) << ",";
cout << endl;
}
65
例 3.2.4
#include <iostream.h>
void main()
{
int b[ ][5] = {{11,12,13,14,15},
{21,22,23,24,25},
{31,32,33,34,35}};
int (* pb)[5]; // 声明一个指针，指向每行有 5个元素的
数组
pb = b; // 将二维数组名赋值给指向一维数组的指针 pb
for( int I = 0; I < 3; I ++,pb ++)
{
for(int j = 0; j < 5; j ++)
cout << *(*pb + j) << ","; // 引用二级指针
cout << endl;
}
}
66
例 3.2.5
#include <iostream.h>
void main()
{
int b[3][5]={{11,12,13,14,15},
{21,22,23,24,25},
{31,32,33,34,35}};
int (* pb)[5];
pb=b;
for( int i=0;i<3;i++)
{
for(int j=0;j<5;j++)
cout<<pb[i][j]<<","; // 指针名代替数组名
cout<<endl;
}
}
67
数组和指针参数
前面已经讨论了用数据作参数和用指针作
参数两种情形，形成传值调用和传址调用
两种参数传送方式。当要在两个函数间传
送数组时，也可以有这两种方式,
1）传值传送：用下标变量进行。
2）传址传送：用数组名或指向数组的指
针进行。
数组元素也是变量，用数组元素作参数与
用变量作参数一样，都是传值调用，它们
的使用方法也相同前面什么时候讨论过了？
建议将, 指针, 改为引用
68
用数组元素作参数
int main()
{
float a[3];
float fAverage;
float GetAverage1(float,float,float); // 原型声明
…
fAverage = GetAverage1(a[0],a[1],a[2]); // 函数调用
…
}
float GetAverage1(float a,float b,float c);// 函数定义
{
float Aver;
return (Aver = (a + b + c)/3.);
}
69
用数组名作参数
int main()
{
float a[3];
float fAverage;
float GetAverage2(float x[3]); // 原型声明
…
fAverage = GetAverage2(a); // 函数调用,数组名作参数
…
rerurn 0;
}
float GetAverage2(float x[3]) // 函数定义
{
float Aver;
return (Aver = (x[0] + x[1] + x[2])/3.);
}
70
用数组元素指针作参数
int main()
{
float a[3];
float *pa = a;
float fAverage;
int n = 3;
float GetAverage2(float *,int); // 原型声明
…
fAverage=GetAvegage1(pa,n); // 函数调用,数组名作参数
…
}
float GetAverage2(float * px,int m); // 函数定义
{
float Aver,Sum;
int i;
for(i = 0; i< m; i ++)
Sum += *(px+i);
return (Aver = Sum / m);
}
71
动态内存分配的概念
在 C++程序中，数组具有静态性，也就是说，数
组的大小必须是编译时可知的，不能在程序运行
的过程中才决定数组的大小
C++将每个函数的动态存储区分为栈和堆两种类
型。栈用于存放函数的所有动态局部变量（ auto
类型）以及函数调用和返回的有关信息，它严格
地按先进后出（ FILO）的规则管理栈中的对象，
从而使在嵌套结构的语句结构中，在靠外层的语
句块中定义的变量比靠内层的语句块中定义的变
量的作用域大
堆可以提供比栈灵活的内存管理。程序员在任何
时候都可以（用函数 new）从中获取自己需要大
小的内存，也可以在任何需要的时候、按任意顺
序（用函数 delete）释放在堆中占用的内存
72
求两个数组和的函数
double * dAddVector(double a[ ],double b[ ],int n)
{
double *p;
p=new double[n]; // 申请动态存储块
if(p==NULL)
{ // 判断申请是否成功
cout <<,memory request failed\n");
exit(-1);
}
for(int i = 0; i < n; i ++)
p[i] = a[i] + b[i];
return p;
}
73
实例 —— 栈类
堆栈是一种, FILO”（先进后出）或, LIFO”（后
进先出）的存储实体
它占有一片连续的存储单元，有两个端点：一个
端点是固定的，称为栈底；一个端点是活动的，
称为栈顶。操作只能在栈顶进行
建立一个栈先要开辟堆栈空间，为了指示栈顶位
置还要设置一个指针，称为栈顶指针
栈有两种操作,push（压入）与 pop（弹出）。
初建栈时，栈顶指针 sp指向栈底,栈顶是用于
存放下一个元素的
74
堆栈
sp
栈
空
间
8
sp
8
5
sp
8
5
sp
75
类 myStack的接口
应有如下两种成员数据,
buffer [MYSTACKSIZE] (栈空间 )
*sp (栈顶指针 )
还应有两个成员成员函数
push() (压入操作 )
pop() (弹出操作 )
76
栈类型定义
class myStack
{
long buffer [STACKSIZE]; // 开辟栈区
long * sp; // 设置栈顶指针
public,
myStack(); // 构造函数
~ MyStack(); // 释放函数
void push(long); // 压入数据
long pop(); // 弹出数据
};
77
myStack类的实现
构造函数
释放函数
压入函数 push()
弹出函数 pop()
78
构造函数
构造函数用以对类的初始化。栈在开始使
用之前，是个空栈，栈顶指针应指向栈底，
即指向数组的起始地址，所以构造函数应
定义为
MyStack::MyStack()
{
sp=buffer; //buffer为数组起始地址
}
79
释放函数
释放函数用以撤销栈，程序中对它没什么
特别要求。故可定义为,
MyStack::~MyStack()
{ }
80
压入函数 push()
具体的压栈操作分两步,
① 将（由参数传递来的）数据 data存入栈
顶指针所指向的单元，即
*sp=data;
② 修改栈顶指针，让栈顶指针指向下一个
单元，以便下一次把数据存在那里，即
sp++;
81
压入函数
void MyStack::push(long data)
{
if(sp>=buffer+MYSTACKSIZE)
cerr<<"Stack overflow!\n";
else {
* sp++=data;
cout<<data<<"is pushed.\n";
}
}
82
弹出函数 pop()
具体的弹出操作是与压入相反的两步,
① 修改栈顶指针，使其指向前一个位置，
即
- - sp;
② 向外部返回栈顶元素值，即
return *sp;
83
弹出函数的定义
long MyStack::pop()
{
if(sp<=buffer){
cerr<<"MyStack is empty!";
return 0;
}
return * - -sp;
}
84
MyStack类的接口
#define MYSTACKSIZE 10
class MyStack
{
long buffer [MYSTACKSIZE]; //开辟栈区
long * sp; //设置栈顶指针
public,
MyStack()
{
sp=buffer;
}
~ MyStack() { } // 释放函数
void push(long); // 压入数据
long pop(); // 弹出数据
};
85
#include <iostream.h>
#include "myStack.hpp"
void MyStack::push(long data)
{
if(sp>=buffer+MYSTACKSIZE)
cerr<<"Stack overflow!\n";
else
{ * sp++=data;
cout<<data<<"is pushed.\n";
}
}
long MyStack::pop()
{
if(sp<=buffer)
{
cerr<<"MyStack is empty!";
return 0;
}
return * - -sp;
}
86
字符串
字符串及其形式
字符串数组
87
字符串及其形式
字符串的数组形式
字符串的指针形式
88
字符串的数组形式
字符串是由一个有效字符序列组成的数据
结构，在 C++ 源程序中以一对双引号来表
示其起止界限，如
"Hello!C++."
所谓, 有效字符,,是指系统所允许使用
的字符
89
字符串操作函数
C++在运行库（ run-time library）中提供了
一些常用的字符串操作函数，如,
· 字符串复制函数,strcpy()；
· 字符串连接函数,strcat()；
· 字符查找函数,strchr()；
· 字符串比较函数,strcmp()；
为了使用这些函数应当在程序的头部加上
文件包含指令,
#include <string.h>
90
字符串的指针形式
由于指针与一维数组的对应性，字符串也
可以用指向字符的指针形式表示。它们虽
然都可以用于表示字符串，但二者之间还
是有很大差别
91
两种字符串形式的比较
项目 字符数组形式 字符指针形式
本质 数组，每个元素存放一个字符 指针变量：存放字符串首地址
定义
格式
char 字符数组名 [ ] =,字符串, ;
如 char s[20]="string";
char * 字符指针变量 =,字符串, ;
如 char *s;
访问
字符
使用下标变量直接访问 使用间接引用
输入
与
输出
方式
1.整体：数组名方式,cin >> s;
cout << s;
2.个体：（ 1）下标变量方式
（ 2）间接引用方式
1.整体：指针方式,cin >>
s;
cout << s;
2.个体：（ 1）类下标变量
方式
（ 2）间接引用方式
赋值
方式
不允许赋值，只能进行字符串拷贝。如
strcpy(s,"string");
允许赋值,s="string";也可以用字
符串拷贝函数,如 s=new char[7];
strcpy(s,"string");
运算
限制
数组名不允许进行赋值、加运算 字符指针可以进行赋值、减
92
字符串数组
当要同时处理几个相关字符串时，为了处
理上的方便，可以将它们存放在一个二维
数组中。由于二维数组要统一地定义列宽，
因此要求每个字符串的最大长度相同，即
必须按要处理的字符串中的最大长度来定
义所有的字符串的空间，并且这些字符串
被存放在一个连续的存储空间中
93
一个字符串数组的存储实例
L i B i n \0
Z h a n g B o \0
L i n g H a o T i \0
S u n J i a n g \0
W a n g Q i \0
94
字符串指针数组
Zhang Bo Ling Hao Ti Sun Jiang Wan Biao
name[0]
name[1]
name[2]
name[3]
name[4]
Li Bin
95
字典序将它们排序
# include <iostream.h>
# include <string.h>
void main()
{
char * string[3]={"Data structure","Computer design","C++ Language"};
char * p;
int i;
if (strcmp(string[0],string[1])>0)
{p=string[0];string[0]=string[1];string[1]=p;}
if (strcmp(string[0],string[2])>0)
{p=string[0];string[0]=string[2];string[2]=p;}
if (strcmp(string[1],string[2])>0)
{p=string[1];string[1]=string[2];string[2]=p;}
for (i=0;i<3;i++)
cout << string[i];
}
96
对象与指针
指向对象的指针与创建动态对象
实例 —— 链表
this指针
复制构造函数
97
指向对象的指针与创建动态对象
一个对象一旦被创建，系统就给它分配一
个存储空间，该存储空间的起点可以象数
据对象的地址一样，使用指针变量操作。
一个指向类的指针被初始化后便成为一个
指向某对象的指针，即存有对象首地址的
变量。也可以用一个对象地址来初始化一
个对象指针
98
实例 —— 链表
利用指向对象的指针把对象组织成为链表。
链表中的每个节点对象至少要有两部分成
员：数据与指针
指针用以指出与其逻辑相邻、但存储位置
不一定相邻的节点的地址
当指向的对象类型都相同时，形成同质链
表；否则形成异质链表
99
三个 Person对象形成的链表
&w Zhang
50
m
NULL
zh.name
zh.age
zh.sex
zh.next
zh
Wang
35
m
&c
w.name
w.age
w.sex
w.next
w
Cai
36
w
&zh
c.name
c.age
c.sex
c.next
c
head
100
创建对象链表
为了创建上述对象链表，应做两件事,
（ 1）在每个对象中增加一个指针 next，以
指向逻辑上的下一个对象。
（ 2）设置一个头指针，以指向逻辑上的
第一个对象；将逻辑上的最后一个对象中
的 next指针置空 (NULL)，以表示后面不再
指向任何对象
101
链表节点的对象的类定义
#include <string.h>
class Person{
char * name,sex;
int age;
Person * next; // 指向下一个对象节点的指针
public,
Person( char * n,int a,char s,Person *p = NULL)
{
name=new char[strlen(n)+1];// 立动态存储
strcpy(name,n);
age=a;
sex=s;
next=p;
}
~Person(){delete name;}
void disp();
};
102
成员函数 disp
#include <iostream.h>
#include "person5.hpp"
void Person::disp()
{
Person * ps;
cout<<"Head->"
<<name<<"-" // 处理第一个节点数据
<<age<<"-"
<<sex<<"->";
if(next) //if(next !=NULL)
{ // 从第二个节点开始处理,直到 ps=NULL
for(ps=next;ps;ps=ps->next)
{
cout<<ps->name<<"-"
<<ps->age<<"-"
<<ps->sex<<"->";
}
}
cout<<"END\n";
}
103
建立对象链表
#include <iostream.h>
#include "person5.hpp"
void main(void)
{
Person zh("Zhang",50,'m',NULL); // 尾节点对象
Person c("Cai",35,'w',&zh);
Person w("Wang",34,'m',&c);
Person *head=&w; // 头指针指向 w对象
head->disp();
}
104
this指针
this指针是隐含在对象成员函数内的一种
指针。当一个对象被创建后，它的每一个
成员函数都含有一个系统自动生成的隐含
的指针 ──this，用以保存这个对象的地址。
因此 this也称为, 指向本对象的指针,,
用它来存取类成员变量的格式为,
this -> 成员变量
105
复制构造函数
缺省复制构造函数
缺省复制构造函数的问题
106
缺省复制构造函数
需要一种特殊的构造函数 ──复制构造函
数。其特殊之处在于它只有一个参数，并
且是其所在类的对象的引用。其原型为
X,,X(const X&)
其中,X为复制构造函数所在类的类名
107
复制构造函数被调用三种时刻
·声明并初始化对象变量时,
·对象作为函数参数时,
·对象作为函数值被返回时。
108
例 3.4.3
class myStack{
int myStacksize;
long * buffer;
long * sp;
public,
myStack(int size)
{
myStacksize = size;
sp=buffer = new long[size];
cout<<"Initializing a stack.\n"; // 输出语句
}
~myStack()
{ cout << "Destructor is active.\n"; } // 输出语句
void push(long data);
long pop( );
};
109
测试程序
#include <iostream.h>
#include "myStack3.hpp"
int main()
{
myStack a(2); //创建对象 a
myStack b(3); //创建对象 b
b.push(351);
b.push(7075461);
b.push(3225);
cout<<endl;
cout<<b.pop()<<" is popped.\n";
cout<<b.pop()<<" is popped.\n";
cout<<b.pop()<<" is popped.\n";
cout<<b.pop()<<" is popped.\n";
}
110
缺省复制构造函数的问题
按缺省的复制构造函数的语义，语句
myString s2 = s1;
等价于
s2.str = s1.str;
即两个对象中的指针 s2.str与 s1.str指向同一个串。
于是，当对象 s1 和 s2被撤销时，它们的释放函
数都要删除同一个串。先撤销一个，如 s2被撤销
后,s1将无所指向。同一个串被删除两次是不允
许的。在这种情况下，程序员必须定义自己的复
制构造函数，其要领是使两个对象名各有自己的
实体
111
枚举
枚举及其定义
枚举应用举例
112
枚举及其定义
枚举的概念
枚举类型的定义和变量的生成
枚举变量的初始化
枚举变量的运算
113
枚举的概念
WeekDay,Color这样的代表一组整数的数
据类型都称为枚举（ enum）类型。它们都
是用户自定义的类型
enum（枚举）类型是一种当一个变量具有
有限个可能值，并且这些值有两个特点,
· 可以取整型值,
· 每个值可以有一个名字
114
枚举类型的定义和变量的生成
定义 enum类型的基本格式为,
enum 枚举类型名 { 枚举成员表列 };
另一种形式是在定义一个枚举类型的同时，
声明一些变量属于这种类型，其形式为
enum 枚举类型名 { 枚举成员表列 } 变量
名表列 ;
115
枚举变量的初始化
C++中枚举常量的类型隐含地规定为 unsigned
char或 int类型，并且第一个枚举常量的值为 0,以
后依次增 1。 C++也允许程序员显式地在定义中指
定部分或全部枚举常量的值。如
enum week_day｛ Sunday = 7,
Monday = 1,// 下面的成员逐项加 1
Tuesday,
Wednesday,
Thursday,
Friday,
Saturday｝ ;
缺省说明的枚举常量仍按在前一枚举常量值的
基准上依次增 1
116
枚举变量的运算
枚举变量可以进行赋值（仅限于所在类型的枚举
常量）或关系运算。如
enum Coin{ Penny,
Nickel,
Dime,
Quarter,
Half_dollar,
Dollar
} money;
money= Dime;
if( money == Quarter)
…
117
枚举应用举例
# include <iostream.h>
enum WeekDay{ Mon = 1,Tue,Wed,Thu,Fri,Sat,Sun };
static char * day[ ] = {" ",
"Mon","Tue","Wed","Thu","Fri","Sat","Sun" };
class WhatDay
{
WeekDay mToday;
public,
WhatDay(int n)
{
mToday = WeekDay(n); // 必须强制类型转换
}
void thisDayIs();
}；
void WhatDay,,thisDayIs ()
{
cout << "Tomorrow is:" << day [mToday] << endl;
}
#include <iostream.h>
118
void main()
{
char f; // 标志变量
int i = 1;
do // 用户输入
{
//i = 7? i = 1, i ++;
i > 7? i = 1, i;
cout << "Totay is " << day[i++] << "?(y/n):";
cin >> f;
} while(!(f == 'y' || f == 'Y'));
WhatDay tomorrow(i);
tomorrow.thisDayIs ();
}
119
共用体
共用体及其定义
共用体变量的生成与共用体成员的引用
共用体应用举例
120
共用体及其定义
在每一个类中，所有的数据成员都要单独
占用一个存储空间。但是，有些问题中，
数据成员并不要同时出现、使用
C++为解决这类问题，提供了一种特别的
数据类型,union(共用体 )。顾名思义，它
能提供多个数据共用同一个存储空间的存
储
121
共用体的定义
union 共用体名
{
成员 1定义 ；
成员 2定义 ；
…
成员 n定义 ；
}；
122
共用体变量生成
与结构体相似，共用体变量也可以用以下
几种方式生成，并可以同时进行初始化
1）用共用体类型名说明
2）定义共用体类型的同时生成变量
3）不定义类型直接定义变量
123
共用体成员引用
用成员运算符直接引用
由指向共用体变量的指针，使用指向运算
符引用
由指向共用体变量的指针，用成员运算符
间接引用
124
共用体应用举例
制作学校的人员管理卡片
使用无名共用体作为成员的 Person类
125
制作学校的人员管理卡片
对于不同职业的人员,,级别, 的含义不
同,
· 对学生为年级 (grade),int 型
· 对教师为职称 (title),char * 型
· 对干部为职务 (rank),char * 型
126
共用体具有如下特点,
· 它以关键字 union代替关键字 class;
· 它的所有成员都是公开的；
· 它的所有数据成员都开始于同一地址。
127
Level,:level(char prfs)
{
switch(prfs)
{
case 's',
cout<<"grade:";
cin>>grad;
break;
case 'c',
cout<<"rank:";
cin>>rank;
break;
case 't',
cout<<"title:";
cin>>title;
break;
}
}
128
level::disp(char prfs)
{
switch(prfs)
{
case 's',
cout<<grade<<'\n';
break;
case 'c',
cout<<rank<<'\n';
break;
case 't',
cout<<title<<'\n';
break;
}
}
129
共用体作为类的成员
#include "string1.hpp" // 来自例 3.2.13
class Person
{ string name;
int age;
char profession;
union level
{
int grade;
char rank[8];
char title[10];
level (char); // 共用体构造函数声明
void disp(char); // 共用体成员函数
}school; // 共用体类成员,school为共用体变量
public,
Person(char *,int,char);
~Person(){}
void disp();
};
#include <iostream.h>
#include "person3.hpp"
Person::level::level(char prfs) // 共用体构造函数定义
{
switch(prfs)
{
130
case 's',
cout<<"grade:";
cin>>grade;
break;
case 'c',
cout<<"rank:";
cin>>rank;
break;
case 't',
cout<<"title:";
cin>>title;
break;
}
}
Person
::Person(char *nm,int ag,char prfs):name(nm),school(prfs) // 构造函数
{
age=ag;
profession=prfs;
}
131
void Person::level
::disp(char prfs) //共用体成员函数定义
{
switch(prfs)
{
case 's',
cout<<grade<<"\n";
break;
case 'c',
cout<<rank<<"\n";
break;
case 't',
cout<<title<<"\n";
break;
}
}
void Person::disp() // 类成员函数定义
{
name.print();
cout<<age<<"\n";
cout<<profession<<"\n";
school.disp(profession);
}
132
使用无名共用体作为成员的 Person类
#include "string1.hpp"
class Person
{
string name;
int age;
char profession;
union
{
int grade;
char rank[10];
char title[15];
}; // 无名共用体 无成员函数
public,
Person(char *,int,char);
~Person(){}
void disp();
};
133
#include <iostream.h>
#include "person4.hpp"
Person
,:Person(char *nm,int ag,char prfs):name(nm) // 构造函数
{
age=ag;
profession=prfs;
switch(prfs)
{
case 's',
cout<<"grade:";
cin>>grade;
break;
case 'c',
cout<<"rank:";
cin>>rank;
break;
case 't',
cout<<"title:";
cin>>title;
break;
}
}
134
void Person::disp() //成员函数
{
name.print();
cout<<age<<"\n";
cout<<profession<<"\n";
switch(profession)
{
case 's',
cout<<grade<<"\n";
break;
case 'c',
cout<<rank<<"\n";
break;
case 't',
cout<<title<<"\n";
break;
}
}
135
关于声明符的进一步讨论
声明符
复杂声明
类型定义符,typedef
136
声明符
（１）存储类关键字
auto register static extern
（２）类型关键字
char int signed unsigned short long foat double
* (指针 ) & (引用 ) [ ] (数组 ) ( ) (函数 )
enum (枚举 ) class (类 ) struct (构造体 ) union (共用体 )
（３）修饰符
( ) (运算优先修饰 )
const (阻止写与外部连接 )
volatile(指明一个实体可以被修改 )
inline(内嵌 )
interrupt(书写中断函数 )
friend(友元数 )
（４）其它
137
复杂声明
存储类关键字 类型声明符 逗号分隔的
声明项表 ;
其中，声明符项中名字可以是一些类型组
合
138
类型定义符,typedef
C++还允许程序员用关键字 typedef自己定
义一个类型名。定义语句的格式是,
typedef 类型符 名字 ;
