第六章 数据结构
在程序设计的过程中，数据的组织和表示是很重
要的，因为数据是程序的处理对象，数据的表示形式
关系到整个程序的运行效率和解决问题的能力，前面
我们已经初步了解了数据的最基本形式 -整数、实数、
字符、字符串 等基本数据类型，也学习了在面向对象
的程序设计环境下，类和对象的构造和组织。下面我
们进一步学习其他在基本数据类型的基础构造出来的
一些复杂数据类型，如 数组、指针、结构、共用体、
枚举类型 等。使我们在类和对象的设计过程中，可以
运用更多的数据类型。
第六章 数据结构
6.1 数组概念和一维数组 6.5 结构类型
6.4 指针概念
6.3 字符串处理
6.2 二维数组
6.7 排序和查找
6.6 共用体
6.1 数组
数组类型是一种构造型（组合型）的数据类
型。 数组是由一组具有相同数据类型的元素组成的
集合，用来描述现实世界中具有相同性质的有序事
物集合的抽象，如班级某个学生各门课的成绩，或
者整个班级某门课的成绩。数组的类型就是这组元
素的数据类型。构成数组的这组元素在内存中占用
一组 连续的存储单元 。可以用一个统一的数组名标
识这一组数据，而用下标来指明数组中各元素的序
号。根据数组的维数，分为一维数组、二维数组和
多维数组，常用的是一维和二维数组。
6.1.1 一维数组
一维数组的定义,
类型 数组名 [常量表达式 ]；
其中，类型是数组类型，即数组中各元素的数据类型，可
以是整型、浮点型、字符型等基本类型，也可以其他复杂的数
据类型。数组名是一个标识符，代表着数组元素在内存中的起
始地址，它的命名规则与变量名的命名一样。常量表达式又称
下标表达式，表示一维数组中元素的个数，即数组长度（也称
为数组大小），用一对方括号,[ ]”括起来。方括号,[ ]”的
个数代表数组的维数，一个方括号表示一维数组。
例如：下面分别定义了一个具有 10个元素的字符型数组 a、
一个具有 5个元素的整型数组 b和一个有 20个元素的实数数组 f：
char a[10];
int b[5];
float f[20];
6.1.1 一维数组
对上面定义的数组 b,也可以采用下面这种定义方法：
const int size=5;
int b[size];
注意,在定义数组时, 不能用变量来描述数组定义中的元素个
数 。 例如, 下面的定义方式是不合法的,int b[n];
下标指明了数组中每个元素的序号, 下标值为整数, 用数组
名加下标值就可以访问数组中对应的某个元素 。 下标值从 0开始,
因此对于一个具有 n个元素的一维数组来说, 它的下标值是 0~ n-
1。 例如, 对上例中定义的数组 b来说, b[0]是数组中的第一个
元素, b[1]是数组中的第二个元素, …, b[4]是数组中的最后一
个元素, 而不包含 b[5]。
数组元素在内存中是顺序存储的 。 对于一维数组, 就是简
单地按下标顺序存储 。
例如, 对上面定义的整型数组 b,在内存中的存放顺序如下
图所示,b[0] b[1] b[2] b[3] b[4]
6.1.1 一维数组初始化
一维数组的初始化：
在定义数组时对其中的全部或部分指定初始值,
这称为数组的初始化 。 初始化的语法格式为：
类型 数组名 [数组大小 ]={值 1,值 2,…, 值 n};
例如：定义一个字符数组 a并进行初始化 。
char a[5]={’a’,’b’,’c’,’d’,’e’};
或：
char a[ ]={’a’,’b’,’c’,’d’,’e’};
定义一个整数数组 b并进行初始化
int b[7]={11,22,65,87,100,42,77};
6.1.1 一维数组初始化
注意,在对数组初始化时，也可以只对数组中的部分元素指
定初始值。也即，初始化值的个数可以少于或等于数组定义
的元素的个数，但不可以多于数组元素的个数，否则会引起
编译错误。
当初始化值的个数少于数组元素个数时，前面的元素按
顺序初始化相应的值，后面不足的部分由系统自动初始化为
零（对数值数组）或空字符‘ \0?（对字符数组）。
int b[7]={11,22,65,87};
一维数组的赋值
1,用, =”赋值
与数组元素的初始化不同, 在给数组元素进行赋值时,
必须逐一赋值 。
例如：对于下述的数组初始化：
int a[3]={1,2,3};
6.1.2 一维数组赋值
其等价的赋值形式如下：
int a[3];
a[0]=1;
a[1]=2;
a[2]=3;
若要在数组之间进行赋值, 也只能一个一个元素地赋值 。
例如：将上述数组 a的值赋给另一个同样大小的数组 b，
可以利用下面的循环完成赋值操作：
for (i=0;i<3;i++) b[i]=a[i];
2,用流命令赋值
其语法格式为：
cin>>数组名； // 只适合用于字符数组
或
cin>>数组名 [下标 ]；
6.1.2 一维数组赋值
例如：对一个大小为 5的字符型数组 a赋值, 可以用
下列两种方式：
char a[5]; // 只适合用于字符数组
cin>>a;
或 char a[5];
int i;
for (i=0;i<5,i++) cin>>a[I];
6.1.3 一维数组引用
一维数组元素的引用：
数组在定义后即可引用, 引用是以元素为单位的 。 其引用
形式为,数组名 [下标 ]
指明了引用数组名的数组中下标所标识的元素。下标可
以是整常数或整型表达式。例如 a[2+1],a[i+j]等（ i和 j为
整型变量）。例如：
a[2]=10; //将 10赋给数组中的 a[2]元素 。
a[5]=a[2]; //将 a[2]元素的值赋给 a[5]元素
cout<<a[5]; //打印 a[5]元素的值
注意区分定义与引用形式上的相似与含义上的区分, 定义时
是指数组的大小空间；引用时是指引用下标标识的元素 。
引用时一定要注意下标的值不要超过数组的范围, 否则会产
生数组越界问题 。 例如：定义了一个整型数组 a,int a[10];
数组 a的合法下标为 0~9。如果程序要求给 a[10]赋值，将可能
导致程序出错，甚至系统崩溃。
注意：
1,数组是一种 组合类型,是不能作为一个整体进
行访问和处理的，只能按元素进行 个别 的访问和处理。
2,C++数组第一个元素的下标为 0，而不是 1，
且下标表达方式是固定的。
3：数组元素在内存中是从低地址开始 顺序排列,
各元素的存储单元占用内存大小相同，各元素的存储
单元之间 没有空隙,可以从数组第一个元素存储单元
的起始地址计算出任意一个元素存储单元的起始地址。
6.1.4 一维数组例子
找出一个整型数组各数组元素中的最大数和最小数, 数组中的数由随机数
函数 rand()产生 。 这是很典型的基本算法, 细讲 。
const SIZE=15;
void main()
{ int arr[SIZE]; int i,high,low;
for(i=0; i<SIZE; i++) arr[i]=rand()%100;
for(i=0; i<SIZE; i++) cout<<arr[i]<<'\t';
cout<<endl;
high=arr[0]; //最大和最小值均为数组的第 0个元素
low=arr[0];
for(i=1; i<SIZE; i++) {
if(arr[i]>high) high=arr[i];
if(arr[i]<low) low=arr[i];
}
cout<<"highest value is "<<high<<endl;
cout<<"lowest value is "<<low<<endl;
return;
}
6.2 二维数组
二维数组的定义：
二维数组也称为矩阵, 需要两个下标才能标识某个元素
的位置, 通常称第一个下标为行下标, 称第二个下标为列下标 。
定义二维数组的语法格式为：
类型 数组名 [常量表达式 1][常量表达式 2]；
定义二维数组的格式与定义一维数组的格式相同，只是
必须指定两个常量表达式，第一个常量表达式标识数组的行数，
第二个常量表达式标识数组的列数。
例如,int a[2][3]；
上面定义了一个二维数组 a,它在逻辑上的空间形式为 2
行 3列, 也可以这么说, 定义了两个一维数组 a[0]和 a[1],而
a[0]和 a[1]每个又是一个有 3个元素的一维数组 。 每一个数组
元素都是整型数据, 因此 a数组的各元素如下：
a[0] a[0][0] a[0][1] a[0][2]
a[1] a[1][0] a[1][1] a[1][2]
// 每一维的下标都是从 0开始
可见, 二维数组中每个元素都是用下列方式标识：
数组名 [行下标 ][列下标 ]
二维数组在内存中的排列顺序是, 先行后列,,
即在内存中先存第一行的元素，然后再存第二行的元
素。从数组下标变化来看，先变第二个下标，第一个
下标先不变化（即 a[0][0],a[0][1],a[0][2]），待第
二个下标变到最大值时，才改变第一个下标，第二个
下标又从 0开始变化。比如上面定义的 2行 3列的二维
数组 a，在内存中的存放顺序上图所示。
6.2 二维数组
6.2 二维数组
由于二维数组在内存中是线性排列的, 引用一维
数组和引用二维数组都是引用相应存储地址的内容,
因此可以计算出一个二维数组元素在对应一维数组中
的顺序号, 从而将对二维数组元素的引用转变为对一
维数组元素的引用, 这个过程称为, 降维处理, （ 经
常在向函数传递数组时用到 ） 。
举例来说, 假设有一个 m x n的二维数组 a,其中第
i行第 j列元素 a[i][j]在数组中的位置公式为：
i*n+j
例如有一个 3*4的矩阵 a：
a00 a01 a02 a03
a= a10 a11 a12 a13
a20 a21 a22 a23
a21元素在数组中的位置是 2*4+1=9。 即它在数
组中是第 9个元素 。 对一个 aij元素 （ 在 C++语言中表
示为 a[i][j]）, 在它前面有 i行 （ 对 a21来说它前面有
两个整行 ）, 这 i行共有 i*n个元素 。 在 aij所在行中,
aij前面还有 j个元素, 因此在数组 a中 aij前面共有
（ i*n+j） 个元素 。 那么 aij就是第 （ i*n+j） 个元素,
计算方法是从 0开始的 。
6.2 二维数组
6.2.1 二维数组初始化
二维数组初始化：
和一维数组一样, 二维数组也能在定义时被初始
化, 只是要注意必须按照前面所讲的存储顺序列出数
组元素的值 。 常见有如下一些初始化方式：
（ 1） 分别对各元素赋值, 每一行的初始值用一对花
括号括起来 。 例如：
int a[2][3]={{1,2,3},{4,5,6}};
将第一对花括号内的三个初始值分别赋给 a数组
第一行三个元素, 第二对花括号内的三个初始值赋给
第二行元素 。 数组中各元素为：
1 2 3
4 5 6
6.2.1 二维数组初始化
（ 2） 将各初始值全部连续地写在一个花括号内, 在
程序编译时会按内存中排列的顺序将各初始值分别赋
给数组元素 。 例如
int a[2][3]={1,2,3,4,5,6};
数组中各元素为：
1 2 3
4 5 6
（ 3） 只对数组的部分元素赋值 。 例如：
int a[2][3]={1,2,3,4};
数组共有 6个元素, 但只对前面 4个元素赋初值,
后面两个未赋初值, 其值为 0。 数组中各元素为：
1 2 3
4 0 0
6.2.1 二维数组初始化
（ 4） 可以在分行赋初值时, 只对该行中一部分元
素赋初值, 例如：
static int a[2][3]={{1,2},{4}};
对第一行中的第一, 二列元素赋初值, 而第三个
元素未赋初值 。 第二行中只有第一列元素赋初值 。
数组中各元素为：
1 2 0
4 0 0
6.2.2 二维数组省略定义
省略第一维大小定义,
若在定义数组时给出了全部数组元素的初值, 则
数组的第一维下标可以省略, 但第二维下标不能省略 。
例如：下面两种定义方式等价：
static int a[2][3]={1,2,3,4,5,6};
static int a[ ][3]={1,2,3,4,5,6};
编译器会根据元素的总个数分配空间, 每行 3列,
共 6个元素, 故该数组行数为 6/3=2行 。
但上例不能写成：
static int a[2][ ]={1,2,3,4,5,6};
6.2.3 二维数组例子
编写一个程序，统计某个班三门课语文、数学、
英语的成绩，先输入学生人数，然后按编号从小到大
顺序依次输入各个学生的成绩，最后统计每个学生的
课程总成绩和平均成绩，及每门课的平均成绩，并列
表输出。
分析,每个同学需要处理的包括三门课成绩和总分、
平均分共 5个实数类型数据，而一个班级可能有若干
个学生，所以处理这个班级用二维数组来处理是最方
便的，定义 float score[100][5]; 第一维表示学生，
第二维表示成绩，所以例如第 3个学生的数学成绩是
score[3][1]这个元素。另外，定义一个一维数组
total[3]用来处理三门课的平均成绩。既然数据已经
表示好，下面的实现相对就简单多了。
6.2.3 二维数组例子
#include <iostream.h> // 6-1-2.cpp
#include <iomanip.h>
void main()
{ float score[100][5],total[3]={0,0,0};
int i,j,n;
cout<<"请输入学生人数,";
cin>>n;
for(i=0; i < n; i++) {
cout<<"输入第 "<<i+1<<" 个学生三门课成绩,";
score[i][3] = 0;
for(j=0; j<3;j++) {
cin>>score[i][j];
score[i][3] += score[i][j];
total[j] += score[i][j];
}
score[i][4] = score[i][3]/3.0;
}
6.2.3 二维数组例子
cout<<"学号 语文 数学 英语 总分 平均分 "<<endl;
cout<<"---------------------------------------- "<<endl;
for(i=0; i<n; i ++) {
cout<<setw(4)<<i;
for(j= 0; j<5; j++)
cout<<setw(8)<<score[i][j];
cout<<endl;
}
cout<<"平均分 ";
for(i=0; i<3; i++)
cout<<setw(8)<<total[i];
cout<<endl;
}
6.3,字符串处理
前面讨论的有关数组时，仅涉及到数值型数组，现在专门
讨论一下字符数组：
字符数组的定义, 用来存放字符数据的数组，就是说，字
符数组中的每个元素存放一个字符。字符数组用来存放字符和
字符串，其区别在于：在一个字符数组中，如果有字符串结束
符’ \0?，那么，该数组存放的是一个字符串。字符数组也有
一维，二维，三维数组。
字符数组的初始化,初始化跟数值型数组一样，如：
char c1[4] = {?a?,?b?,?c?,?d?};
char c1[][3] = {?a?,?b?,?c?,?d?,?e?,?f?}; 那么应该第
一个下标为 2
char c1[][3] = {?a?,?b?,?c?,?d?,?e?,?f?,?g?}; 那么应
该第一个下标为 3
而 c1[2][0] = ?g? c1[2][1] = ?\0?,c[2][2] = ?\0?;
6.3 字符串处理
我们曾经介绍过字符串的概念，每个字符串最后都有一
个字符串结束标志 ’ \0?，就是一个, 空操作符,,即它什么
也不做，只是用来判别字符串是否已结束，所以用字符数组
来表示字符串时，长度就显的不是很重要，在程序中一般是
用 ’ \0?来判断字符串是否已结束。但必须保证数组长度一定
大于字符串长度。
了解 C语言对字符串处理方法之后，我们可以用字符串
给字符数组初始化，如：
char c[] =,China” 相当于
char c[6] = {?C?,?h?,?i?,?n?,?a?,?/0?}
而不是 char c[5] = {?C?,?h?,?i?,?n?,?a?};
char c[10] =,China” 相当于
char c[10] = {?C?,?h?,?i?,?n?,?a?,?\0?,?\0?,?\0?,?\0?,
?\0?}
6.3 字符串处理
字符数组的引用：
分析结果：
main()
{ char s1[5] = {?a?,?b?,?c?,?d?,?\0?};
s1[2] = ?g?;
cout<< s1[0]<<s1[2]<<endl;
cout<<s1<<endl;
}
a,g
abgd
6.3 字符串处理
字符数组的输入输出：
#include <iostream.h>
main()
{ char x[3][10];
cout<<“Input String:”<<endl;
cin>>x[0]>>x[1]>>x[2];
cout<<“Output String:”;
cout<<x[0]<<“,”<<x[1]<<“,”<<x[2]<<endl;
}
如输入,how are you?
那么,x[0] =,how”,x[1] =,are”,x[2] =,you?”,在内
存中是这样存放的。
H o w\0
A r e \0
Y o u \0
6.3 字符串处理
用 cout输出字符数组时，系统从字符数组的第 0个字符开始
逐个输出，遇到字符串结束符’ \0?时，就停止输出，不管后面
是是什么字符。但如果我们这么定义，那结果会是如何呢？
char c[5] =,China”;
printf(“%s\n”,c);
程序会在’ a?之后继续寻找’ \0?,直到找到为止。
字符串处理函数
puts(字符数组 ),输出一个字符串，也可以用 cout输出
gets(字符数组 ),从键盘输入 一行字符串 到字符数组中
// 上面两个函数需要包含 #include <stdio.h>
l strcat(字符数组 1,字符数组 2),字符串连接函数
将字符串 2接到字符串 1后面，并把结果放在字符串 1中，所
以字符串 1要足够大容纳新字符串内容，二是连接时将字符串 1
的’ \0?取消，只在新串中保留一个’ \0?;
main()
{ char s1[30] =,Zhong Shan,;
char s2[] =,University”;
strcat(s1,s2);
cout<<s1<<endl;
}
6.3 字符串处理
strcpy(字符数组 1,字符数组 2),字符串拷贝，复制函数
将字符串 2完全复制到字符串 1，即字符串 1和字符串 2内
容完全一样。这里有几点需要说明：
1,是字符串 1足够大，能够容纳；
2,是字符串 2可以是常量，也可以是字符数组
3,不能用赋值语句将字符串常量或字符数组给字符数组
赋值，如
str1 =,China”
str2 = str1
只能用 strcpy 函数
4,可以用 strcpy函数将字符串 2中前面若干个字符复制
到字符串 1中，如 strcpy(str1,str2,2),如果 str2=“China”,
那么 str1等于” Ch”
6.3 字符串处理
strcmp(字符串 1，字符串 2), 字符串比较函数
比较的规则是自左至右逐个字符（按 ASCII码值）比
较，直到出现不同字符或’ \0?为止，如果全部相同，那么我
们认为这两个字符串是相同的，返回值为 0，若出现不同，
那么以第一个不同的字符大小为准，如果大，则返回一个正
整数，小则返回一个负整数。
,A” <,B”,“computer”>,compare”,“DOG” <
“cat”
记住，比较两个字符串，不能用
if(str1 == str2) cout<<“OK”<<endl;
strlen(字符数组 ),计算字符串的长度，不是数组的大
小，而是字符串实际长度，就是说到’ \0?前面的长度。
Char str[10] =,china”;
cout<<strlen(str)<<endl;
应该是 5，而不是 10
strwr(字符串 ),将字符串中大写字母转换为小写
strup(字符串 ),将字符串中小写字母转换为大写
编写一个函数 insert(char s1[],char s2[],in p) 实
现将 s2字符串插入到 S1字符串 p的位置上。
#include <string.h>
insert(char s1[],char s2[],int p)
{ char buf[100];
int i = 0;
while(s1[p+i]) {
buf[i] = s1[p+i];
i ++l
}
buf[i]=?\0?;
s1[p]=?\0?;
strcat(s1,s2);
strcat(s1,buf);
}
while(buf[i]=s1[p+i])
i++;
6.4 指针的概念
今天我们讲的, 指针, 是 C和 C++语言中一个非常重要的概
念，因为很多语言都没有指针概念，如 BASIC,PASCAL等。
并且, 指针, 也是 C 程序的最大难点。刚开始学习, 指针,
概念时，同学们或许会感到指针很难理解，但当你深入学习
时，你就会发现它是个很奇妙的运用。
那怎么样才能掌握好指针呢？
首先要从指针的概念入手，要搞清楚什么是指针，它是如
何定义和说明的，怎么样给指针赋值和指针有那些合法的运
算。
其次要掌握指针在数组和函数中的很多应用及如何表示
复杂的数据结构
● 可以有效的表示复杂的数据结构
● 能动态分配内存
● 能方便地使用字符串
● 有效而方便地使用数组
● 能直接处理内存地址等
6.4 指针的概念
为了说清楚指针的概念，我们必须了解数据在内存中是如何存储
的，又是如何读取的。我们知道，数据变量的定义和存储都在系统
的用户内存数据区中，包含静态和动态数据区。
我们定义
int i=3,j=6,k=9; 内存用户数据区
那么系统在编译时就给三 2000 变量 i
个变量分配内存空间。 2002 变量 j
一般系统 int占 2个 2004 变量 k
字节，分配如图所示：
而内存区中每个字节都 3010 指针变量 i_pt
有编号，这个编号就是
,地址, 概念，如图中的 2000就是变量 I的地址,2002是 j的地址，
2004是 k地址 …… 3010是 I_pt地址等等 。 地址就好象是房间号，
而地址中存放的值就好象是房间中的旅客。所以同学们一定分清一
个变量的地址和变量的值是不同的，在图中变量 I的地址是 2000，
而变量的值（或内容）则是 3.
3
6
9
2000
6.4 指针的概念
通过上面,我们已经了解地址的概念,其实在程序中,对某个
变量的存取都是通过对该变量的地址操作实现的,变量名和地址
的对应关系,在变量定义时或临时申请内存空间时就已确定的,
如有语句, k=i+j;
那么系统首先从 2000,2001中取出变量 i的值 3,再从
2002,2003中取变量 j的值 6,将他们相加后的值 9送回到变量 k的
地址 2004,2005中,这种按地址存取变量值的方式叫, 直接访问
方式,,
另一种是, 间接访问方式,, 就是我们定义一个变量, 该
变量的内容是其它变量的地址, 如图中的 i_pt,它里面存放的
2000就是变量 I所占单元的起始地址, 那么访问 i的值, 我们首
先通过 i_pt知道变量 I的地址, 然后再进行存取 。 这就是, 间
接方式, 。 由于是通过地址找到所需的变量单元, 也可以说是
,地址, 指向该变量单元, 所以我们形象地称, 地址, 为, 指
针, 。
2000 k
2010 p
我们可以这么说：
变量 ——存放数据的地方
变量的地址 ——指针
指针变量 ——存放地址的变量 /* 就是 i_pt */
指针变量的定义：
类型 *指针名；
int k,j,*p; p=&k;
float *fp1,*fp2,f; fp1 = &f;
char *str;
要注意：
（ 1） 指针变量前的 *,表示该变量的类型是指针型变量, 指
针变量名本身是不包括 *的 。
（ 2） 定义指针变量时必须指定类型, 因为每种数据类型所占
的字节数不同, 指针值的变化是以数据类型为对象进行操作的 。
P++,字符类型指针每次移动一个字节, 整数类型指针每次移
动 2个字节, 而实数类型每次移动 4个字节
6.4.1 指针定义
2000
6.4.2 指针的运算符
2000 k
2010 p
指针变量的运算：
两个相关运算符 int k,*p; p=&k;
& 取地址运算符
* 指针运算符（间接访问）
*p 等价 k
&*p 等价 &k
*&k 等价 k
例子：
main()
{ int x,y;
int *p1 = &x,*p;
p2 = &y;
*p1 = 10;
y = 20;
printf(“%d,%d\n”,x,*p2);
}
8
2000
同类型的指针可以相互赋值，如有说明
int val1=18,val2=20;
int *p_val1,*p_val2;
p_val1=&val1;
p_val2=&val2; 则 p_val1指向 val1,p_val2指向 val2，
执行 p_val1=p_val2后，则 p_val1也指向 val2，而没有指针
指向 val1了。参见下图。
20
18
20
18
va11P_va11
P_va12 va12
P_va11
P_va12
va11
va12
指针间赋值后的变化
6.4.2 指针的运算符
6.4.2 指针运算例子
例子：
main()
{ int i;
char s[] =,string”;
char *p1 = s,*p2;
p2 = s;
i = 0;
while(s[i++] != ?\0?) p2 ++;
printf(“%d\n”,p2-p1);
}
两个指针相减，在一定条件下才有意义，这个例子中两
个指针相减，其差值表示两个指针间的相距的元素个数。所
以一般在同一数组内有效。
a
s
t
r
i
n
g
\0
p1
p2
6.4.3 指针和数组的关系和运算
指针和数组的关系：
数组,一组同类型变量的集合，用一个名字表示，内存中连
续存放。
既然数组中的每个元素都占存储单元，它们都有相应的地址，
并且其地址还是连续的，所以，用指针来处理数组更体现出方
便性和高效性。 数组名 被看作该数组的第一个元素在内存中的
首地址。
数组名在表达式中被自动转换为一个指向数组第一个元素的
指针常量 。数组名中所放的地址是不可改变的，所以称指针常
量（即隐含说明“元素类型 * const数组名”）。
数组名可以由指针来代替, 非常方便, 但是却 丢失 了数组
另一个 要素, 数组的大小, 即数组元素的数量 。 编译器按数组
定义时的大小分配内存, 但 运行时 （ run time） 对数组的边界
不加检测 。 这会带来无法预知的严重错误 。
6.4.3 指针和数组的关系和运算
C++提供根据数组的存储地址访问数组元素的方
法。右图定义 int a[10],*p=a; a是数组第一个元
素的地址，所以 *a是数组的第 0个元素 a[0]，而 a+1
是数组第 1个元素的地址,*(a+1)是第 1个元素 a[1]
本身 … 。 尽管不同的计算机系统中整数所占的字节数
可能并不相同,但我们不必去考虑这个差异,C++的
编译系统保证了对数组运算的正确性,指针加 1，则地
址移动一个数组元素所占字节数 。
C++语言的下标运算符 [ ]是以指针作为操作数的，
a[i]被编译系统解释为 *(a+i)，即表示为 a所指 (固定
不可变 )元素向后第 i个元素。无论我们是以下标方式或
指针方式存取数组元素时，系统都是转换为指针方法
实现。
p=a 表示把 a数组的首地址赋给 p，即 p指针指向
数组 a的首地址。 p+i,a+i和 &a[i]都是第 i个元素的
地址,那么 *(a+i),*( p+i ),a[i],p[i]等价
a[0]
a[1]
a[2]
a[9]
p
a
a+1
a+2
6.4.3 指针和数组的关系和运算
了解指针后，对一个数组的元素进行遍历，有以下几种方法：
（ １） 下标法：比较直观
main()
{ int a[10],i;
for(i = 0; i < 10; i ++) cin >> a[i];
cout << endl;
for(i = 0; i < 10; i ++) cout << a[i] <<,,;
}
（２） 通过数组名计算元素地址
printf(“%d,,*(a+I));
3）用指针变量指向数组元素：效率最高，因为它不需每次重新计算元素地
址
int *p;
for(p = a; p < (a+10); p ++) cin >> *p;
for(p = a; p < (a+10); p ++) cout << *p <<,,;
6.4.3 指针和数组的关系和运算
那如果是以下程序，那么有何结果呢？
int i; for(p = a; p < (a+10); p ++) cin >> *p;
for(i = 0; i < 10; i ++,p ++) cout << *p <<,,;
由于 p指针已经指向数组的末位，再执行第二个循环，会出现
意想不到的数据，要想得到正确答案，应该在第二个循环前加上
p = a 的赋值语句。
指针运算应注意问题：（假设 p=a,inta[10]）
1,p++ 指向下一个元素
2,*p++ 由于 ++和 *同优先级，结合从右到左,*(p++)
所以应该先取 p指向的值，然后 p++，指向下一条元素
3,*(p++)和 *(++p) 不同，先 *p，后 p++,而后面是 p++，
然后 *p
4,（ *p） ++ 内容加 1而不是指针加 1
5,如果 p指向 a数组的第 i个元素，那么：
*(p++) = a[i++]
*(++p) = a[++i]
6.4.3 指针和数组的关系和运算
上面我们讲了数值型和字符型数组指针，但都是一维的，下面
我们讲多维的数组指针是如何使用的。首先我们分析一下多维数组
在内存中的存储方式。
ü 多维数组的地址
static int a[3][4]={{1,3,5,7},{9,11,13,15},{17,19,21,23}};
a[0](2000)?
a[1](2008)?
a[2](2016)?
相当于二维数组 a包含三个一维数组,a[0],a[1],a[2]，而他们
又分别包含四个元素。所以 a表示整个数组的首地址，而 a+1表示第
一行的首地址，而 a[1]也是第一行的首地址 &a[1][0]，所以两者地
址是相同的。同样,a+2跟 a[2]是一样的，都是第二行的首地址。
那么如何表示第 0行第一列的元素地址呢？ a[0]+1（ 2002），就是
&a[0][1]
而 *(a+1) 是什么呢？首先我们知道 a+1是第一行的首地址，根
据上面介绍的,*（ a+1）应该是 a+1所指向的内容，由于 a+1实际上
并不是一个变量，也谈不上它的内容，所以 *(a+1)就是 a[1]，即第
一行的首地址。
1 3 5 7
9 11 13 15
17 19 21 23
6.4.4 指针作为函数参数
C++中函数的参数的基本使用方法是 传值 。 为了弥补单纯
传值的不足, 以 引用作为函数的参数, 从逻辑上讲引用是别名,
在函数中对参数的操作, 就是对实参的操作, 而在 物理上是传
实参的地址 。
将 指针用作函数的参数 时，传的仍然是值，指针的值，这
个值就是指针所指向的变量或对象的内存首地址，在物理上讲
我们传的是指针的值，与传其它变量是没有差异的，函数获得
的是另一个变量的地址，在逻辑上讲我们是把另一个变量的地
址传过去了，可以看作 传地址 。
6.4.4 指针作为函数参数
例子：输入两个整数，按大小顺序输出。
swap(int *p1,int *p2)
{ int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
main()
{ int a,b,*p_1 = &a,*p_2 = &b;
cin >> a >> b;
if(a<b) swap(p_1,p_2);
cout << a << b; /* cout << *p_1 << *p_2; */
}
6.4.4 指针作为函数参数
分析如下程序，
swap(p1,p2)
int *p1,*p2;
{ int *temp;
*temp = *p1;
*p1 = *p2;
*p2 = temp;
}
分析如下程序，
swap(p1,p2)
int *p1,*p2;
{ int *temp;
temp = p1;
p1 = p2;
p2 = temp;
}
6.4.5 数组名作为函数参数
数组作为函数参数传递有两种表现形式：
（ 1）以前我们讲过将 数组元素 作为实参传递给函数，属于
“值传递”
（ 2）数组名作为实际参数，因为 数组名 也是指针常量，当然
可以作为函数的参数。在函数调用时 传递实参数组的首地址,
所以在被调函数中对形参数组的处理实际就是对调用函数的
实参数组的处理。在被调函数中作为形式参数的一组数组不
需要说明长度，即使说明了大小也不起作用，因为 C++只传
递数组首地址，而对数组边界不加检查 。这带来的好处是，
函数对长度不等的同类数组都通用。如要 指定长度可以设定
另一个参数来传递数组元素的个数。
6.4.5 数组名作为函数参数
我们也可以直接将数组名作为实参传递给函
数，属于“地址传递”，地址传递后，在函数中数
组元素的值变化会影响实参中各个元素的值。
main()
{ int array[10];
……
array[2] = 7;
……
fun(array,10);
……
}
7(10)
array
fun(int ap[],int n)
{ ……
ap[2] = 10;
……
}
ap
6.4.5 数组名作为函数参数
实参、形参分别可用数组名或指针变量四种情况：
数组 --,数组 数组 --,指针 指针 --,数组 指针 --,指针
下面用指针的方式来说明求 10个数中的最大值和最小值
（因为需要求两个返回值，我们设两个全局变量来处理 )
int max,min;
main()
{ int i,num[10];
for(i = 0; i < 10; i ++) cin >> num[i];
max_min_value(num,10);
cout <<,Max =, << max <<,Min =, << min;
}
void max_min_value(int array[],int n)
{ int *p,*array_end;
array_end = array + n;
max = min = *array;
for(p = array+1; p < array_end; p ++) {
if(*p > max) max = *p;
if(*p < min) min = *p;
}
}
6.4.6 指针作为函数参数返回值
函数的返回值也可以是指针。如希望返回多个值，可以用
引用参数或指针参数来等效实现，如果我们希望 返回一个数组
或字符串,并且这个数组生命期不在该函数中消亡，我们可以
返回一个指向该数组的指针 。
设计一个 input函数中输入数据，然后在主函数中输出
void main()
{ float *input(),*data;
data = input();
for(int i = 0; i < 10; i ++) cout << data[i];
delete data;
}
float *input()
{ float *buf = new float[10];
for(int i = 0; i < 10; i++) cin >> buf[i];
return buf;
}
6.4.7 指针的注意事项
*指针与引用
C语言的指针容易失控，所以在 C++中增加了引用类型，
它具有指针的主要功能，但限制了灵活性，使用更加安全。
引用并非简单的指针常量（作为别名，它不能在使用中指
向其他对象），它又可以作为左值，这点却又象指针的间
接引用，功能更加强大。建议 在函数参数传递中，能用
,引用, 时绝不用, 指针, 。
6.4.8 指针在字符串中的应用
在 C++语言中, 可以定义一个字符数组, 将字符串存放在
该数组中, 通过数组下标来访问所需的字符；也可以定义一个
字符指针, 通过指针的指向来访问所需的字符 。
定义方式如下,char * 指针名 ;
main()
{ char *sp =,I love China!”;
cout << sp;
sp = "You love China!";
cout << sp;
}
I love China! You love China!
sp
6.4.8 指针在字符串中的应用
用字符指针将两个字符串连接
#include <iostream.h>
void strcat(char *s,char *t)
{ int i=0,j=0;
while (* s) s++;
while (* t) s++ = *t++;
*s = '\0';
}
void main (void){
char a[40]="李明 ";
char b[20]="是东南大学学生 ";
strcat(a,b);
cout<<a<<endl; //打印字符数组 a
}
6.4.9 指针数组
数组的内容, 就是数组元素既可以是普通类型的数据, 也可
以是指针 。
指针数组的定义 类型标识 *数组名 ［ 数据长度 ］ ；
如 int *p[4],表示 4个元素都是指针变量的指针数组 。
指针数组相当于二维数组, 为什么这么说呢？ 因为我们知道,
一个指针可以指向一个一维数组, 那么指针数组可以理解为多
维数组 。 那为什么不用二维数组, 而用指针数组呢？ 因为它适
合于处理多个字符串, 譬如我们用一二维数组来处理人名：
char name[3][12] = {“ZhangSan”,“LiSI”,“ShunWU”};
char *name[3] ={“ZhangSan”,“LiSI”,“ShunWU”};
引用 name[0] ->“ZhangShan”,
name[1] ->”LiSi”,
name[2]->”ShunWU“
也可以引用 name[0][2]（ ‘ a?） ;
可以节省空间, 并且用
指针处理, 更加方便灵活 ！
Name[0]
Name[1]
Name[2]
Zhang San
Li Si
Shun Wu
6.4.9 指针数组main()
{ void sort(char *name[],int n);
char *name[] = {“ViusalC++”,“Basic”,
“Pascal”,“Delphi”};
sort(name,4);
for(int i=0; i<4; i ++) cout << name[i];
cout << endl;
}
void sort(char *name[],int n)
{ char *temp; int i,j,k;
for(i=0; i<n-1;i++) {
k=i;
for(j=i+1; j<n; j++)
if(strcmp(name[k],name[j]) > 0) k = j;
if(k != i) { temp = name[i],
name[i] = name[k]; name[k] = temp }
}
}
6.4.10 this 指针
当在对象的外部访问该对象的公有成员时, 必须指明是
哪一个对象 。 但是当我们用对象的成员函数来访问本对象的
成员时, 在成员函数中只要给出成员名就可以实现对该对象
成员的访问 。 再进一步可用同一个类创建很多个对象, 但它
们共用同一份成员函数的拷贝 。 既然是同一份拷贝, 那么成
员函数又怎么知道是取哪一个对象的成员数据呢？ 其实 当调
用一个成员函数时, 系统自动产生一个隐藏的指针, 这个指
针称为 this指针, 它始终指向产生这个调用的对象, 并将该
指针作为一个参数自动传递给该成员函数 。 这就是说, 成员
操作符总是要使用的, 只不过在对象内是隐式的, 而在对象
外是显式的 。 即在对象内省略了 this指针 。
6.4.10 this 指针
实际上编译器是这样实现 this指针的
1,改变类成员函数的定义, 用附加参数 this指针来定义每个
成员函数 。 如：
void Circle::OutputArea(Circle *this)
{
cout<<“圆的面积为,”<<PI*this->mfR*this->mfR<<endl;
}
2,每个类成员函数的调用, 加上一个附加的实参 ——被调用
对象的地址 。 如：
cs1.OutputArea ( );
改变为：
cs1.OutputArea ( &cs1);
6.4.10 this 指针
在上例中,this指针不必写成显式的，但是 有时
必须写成显式 的，如在以后要学的某些类型的链表管
理中，在需要返回当前调用的对象时（对复数类的赋
值号重载中 ），等等。但必须指出 静态成员函数没
有 this指针 。因为普通成员函数虽然在物理上只有一
份拷贝，但在逻辑上都认为一个对象有一份拷贝，所
以有 this指针，而静态成员函数在逻辑上也只有一份
拷贝，不属于具体的对象，当然没有 this指针。
6.5 结构类型
我们知道数组是一种构造数据类型, 今天我们讲另一种
更复杂的构造数据类型, 就是, 结构体,, 跟数组一样, 它们都是
从基本的数据类型演变而来的, 那什么是, 结构体, 呢, 所谓的
,结构体, 就是由多种数据类型的变量构成的一个集合 。 当只使用
数据成员, 而且这些数据成员的类型往往互不相同时, 总是采用结
构类型, 而不采用类 。
结构体的类型的定义
struct 结构体名 {
结构成员说明；
}；
其中 struct是关键字,,结构体名, 是用来标识结构体类型的，
,结构成员说明, 是若干个成员的说明，每个成员都有类型和名字，
每个成员名的命名规则与变量名相同；数据类型可以是基本变量类
型和数组类型，也可以是指针变量类型，或者是一个结构体类型；
用分号“；”作为结束符。整个结构的定义也用分号作为结束符。
类型名 成员名 ；
成员也可称为域表
6.5 结构类型
这样, 我们可以用一个结构来表示学生的情况
例如,struct student {
int num;
char name[20];
char sex;
int age;
float score;
char addr[20];
};
注意：上面我们定义的只是一种由用户自行定义的结构类
型, 是一种新的数据类型, 它跟 int,float一样, 只有定义变量
之后, 系统才分配具体的内存空间, 存储具体的数据 。 在程序
文件中, 并且 强烈推荐将结构类型的定义放在所有函数的外面 。
结构体变量的定义 （ 三种方法 ）,
1,先定义类型, 后定义变量
struct student s1,s2;
s1
S2
分配的空间就是所有成员的字节数之和
2,类型与变量同时定义
struct 结构体名 {
结构成员说明；
} 变量序列；
3,直接定义变量
struct {
结构成员说明；
} 变量序列；
6.5 结构类型
10001 Zhang San M 19 90.5 Shang Hai
10002 Wang Li F 20 87 Bei Jing
6.5 结构类型结构体变量的使用：
结构体变量的引用有两种形式：
1,对其成员进行操作
访问成员是通过,,” 的成员运算符进行的,,,”优先级是很高
的
,结构体变量名,,,成员名,
对于学生结构来说, 我们可以
s1.no = 10001;
strcpy(s1.name,“ZhangShan”;
average = (s1.score + s2.score)/2;
s2.age ++;
cin >> s1.age >> s2.name;
2,访问整个结构体变量
可以在相同类型的结构类型变量之间进行赋值, s2 = s1; 表示
将 s1中的每个成员内容相对应地赋给 s2中的成员 。
但要注意,C++不允许用 cin,cout对结构体变量进行整体输入
或输出, 如 cin >> s1; 是不行的, 不能对整个结构进行赋值
6.5 结构类型
结构体变量的初始化,
结构变量赋初值跟数组一样, 可以用初始化值表, 如,
例如,struct student {
int num;
char name[20];
char sex;
int age;
float score;
char addr[20]
} s1 = {10000,“LiMing”,?M?,
19,88,“BeijingRoad”};
结构体数组,
定义方式和普通数组一样, 与普通数组不同的是, 结构数组中
的所有元素都是结构数据类型 。 例如：
struct student std[100]；
定义一个有 100个结构类型元素的结构数组
引用方式,数组元素,成员名 ；
如,std[0].no,std[1].name 等
数据在内存中的存放方式是一个元素接着一个元素连续存放
数组名是首地址
std
结构体数组适合处理由若干个具有相同属性的对象数据组成的
数据集合 。 用结构体数组处理数据时可以使用循环, 从而使程
序十分简炼 。
举例：对候选人得票的统计程序 。 设有三个候选人, 每次输入
一个得票候选人名字, 要求最后输出个人的得票数
6.5 结构类型
10001 Zhang San M 19 90.5 Shang Hai
10002 Wang Li F 20 87 Bei Jing
6.5 结构类型
#include <iostram.h>
struct person {
char name[10];
int count; //结构体数组初始化
} leader[3] = {{“Li”,0},{“Zhang”,0},{“Liu”,0}};
main()
{ int i,j;
char lead_name[10];
for(int i=0; i <= 10; i++) {
cin >> lead_name;
for(int j=0; j > 3; j++) {
if(strcmp(lead_name,leader[j].name) == 0)
leader[j].count ++;
}
}
for(i=0; i < 3; i ++)
cout <<,候选人：, << leader[i].name <<
“得票数：, << leader[i].count << endl;
}
6.5 结构类型
1 指向结构体类型数据的指针
2 结构体成员在内存中要占据一定的内存空间, 那么它肯定有起
始地址, 那么我们可以用指针指向这个地址来处理和引用结构
体成员数据
3 1,指向结构体变量的指针 ps
4 struct student stu_1
5 struct student *ps;
6 ps=&stu_1;
7 以下三种引用形式等价
8 stu_1.name (*ps).nmae ps->name
9 这里又多一种运算符, ->”,它跟,,”优先级都是最高的, 叫做
,指向运算符,, 格式为,结构体指针变量 ->成员变量名
p->age ++
++ p->age
假设 stu_1.age原始内容为 18,那么经过以上运算, 表达式
值和 age值分别是多少？
1000
Li Ming
6.5 结构类型
指向结构体数组的指针
跟数组一样, 我们知道数组名就是它们数据的首地址, 那
么结构体数组名一样是它所分配的数据内存首地址, 所以我们也
可以采用指针方式来处理结构体数组
struct student std[100],*p; p
p = std; p++;
指向结构体的指针作函数参数
与数组在函数间传递一样, 结构体传递给函数时,
一般采用地址传递方式, 即把结构体变量
（ 或数组 ） 的存储地址作为参数向函数传递,
函数中用指向相同结构体类型的指针接收该
地址值 。 然后, 在函数中通过这个结构体指针来
处理结构体变量 （ 或数组 ） 中的各项数据
fun(struct student *sp)
fun(std); { cout << sp->name;
}
1001
Li MIng
88.5
1002
Liu Hua
77.8
6.5 结构类型
指向结构变量的指针做函数返回值
在前面课中, 指针可以函数返回值, 那么结构体变量指针也
一样可以作为函数返回值
举例：输入四个学生的某门课成绩, 找出其中分数最高的学生,
并输出名字和分数
struct student {
int num; char name[20]; float score;
};
main()
{ struct student *max(),*ss;
struct student std[4];
for(int i = 0; i < 4; i ++)
cin << std[i].name << std[i].score;
ss = max(std,4);
cout >>,Name =, >> ss->name >>,Score =,
>> ss->score >> endl;
}
6.5 结构类型
struct student *max(struct student *pd,int n)
{ int i,t = 0,m; std
m = pd[0].score; pd
for(i = 1; i < n; i ++)
if(pd[i].score > m) {
m = pd[i].score;
t = i;
}
return(pd+t);
}
1001
Li MIng
88.5
1002
Liu Hua
77.8
Std[0]
Std[1]
Std[2]
6.6 共用体
共用体和结构有很多相似之处, 在定义的形式上和成员的
表示上都一样, 其区别在于结构是异址的, 而共用体是同址的,
就是说各个成员的地址是相同 。 即共用体的成员都是从同一地址
开始, 共用一段存储单元 。
定义形式：
union 共用体类型名 {
成员列表 ；
} 变量表列；
例如：
union data { 2000
int i; 2000
char ch; 2000
float f;
} a,b,c,*p;
i
Ch
f
6.6 共用体
定义共用体变量也有三种方法, 跟结构体变量定义一样
从成员变量的存储方式来看, 结构体所占的内存长度是全部成员
长度之和, 而共用体的内存长度则是最大成员的长度 。
共用体变量的引用, 跟结构体一样, 要用成员运算符,,”或指向运
算符, ->”,如,a.f b.ch p->i p->f 等等
那共用体相对结构体来说, 有何特点呢？
1,同一时间, 它只能存放一种成员的数据
2,起作用的成员也是最后一次存放的成员, 如：
a.i = 1;
a.c = ?a?;
a.f = 1.5
那么赋值后, 最后起作用的是 f成员, cout << a.i 打印出
来的数据是不可预料的
3,共用体的各成员起始地址都是同一地址, 所以
&a.i,&a.ch,&a.f 结果是一样的
6.6 共用体
举例：设计学校人员管理卡片的数据结构
我们知道一个学校主要有三类人员：
1 是学生, 2 是老师, 3 是行政干部
如果我们设计三个结构来表达这三类人员, 当然是可以的, 不过在以后
的数据处理和管理中, 就重复和累赘 。 因为每类人都有编号, 姓名, 年龄是相
同的, 而不同的是对学生来说要处理年级, 对老师来说要描述职称, 而对行政
干部来说, 要描述职务, 所以, 在数据的统一处理中, 我们可以采用共用体概
念进行描述数据 。
为了统一对数据进行管理, 我们对这三种人设计一个结构：
struct person {
long no;
char name[12];
int age;
char profession; // 如果 profession 为 0,表示该数据为学生数据,
1（ 老师 ） 2（ 行政干部 ）
union level {
int grade; // 对学生的年级
char rank[8]; // 对行政干部的职务
char title[10]; // 对老师的职称
} scl;
}
6.7 排序与查找
6.7.2 常用的排序法
6.7.1 常用查找方法
数据排序 （ sorting） 是最重要的计算应用之一。
例如查字典，字典中的词条是按序存放的，我们
才能按字母顺序找到要查的字。又如图书馆的藏
书也是按书的编号有序排列的。在计算机上数据
库里的资料也是有序排列的。
查找 （ search） 当然也是最常见的运算，就是
在数据集合中寻找满足条件的数据对象，找到后
进一步给出对象的具体信息，在数据库技术中称
为 检索 （ retrieval）。
6.7.1 常用查找方法
最简单的查找 —— 顺序查找,即从数组第一个元素开始，一个一个
顺序查下去直到找到或查到最后一个元素为止。
查找是按 关键字 （ key word）进行的，可以唯一地把资料区分出来
的数据被称为 主关键字 。如学生的资料，该资料是一个结构体变量；
struct student{
int id ; //学号
char name[20]; // 姓名
char sex; // 性别
int age; // 年龄
char address[60]; //家庭地址
float eng,phy,math,computer; //英语,物理,数学和计算机成绩
};
在这里 学号 可作为主关键字。
如果关键字小的排在前面，我们称为升序排列，反之为降序排列。这
时可以采用 对半查找（ binary search） 。
一般查找是对普通数据类型数组或结构体数组进行的
6.7.1 常用查找方法
下 图是描述对半查找是怎样进行的。这里是升序的有序表。
算法如下：
1、首先安排两个下标变量 low和 high指向首尾两元素
2、取 mid=(low+high)/2，如 mid指向元素是所查找的，则
结束。如果被查找的数比该元素关键字大，说明被查找的数在
后面，则取 low=mid +1,high不变，继续查找步骤 2；如果
被查找的数比该元素关键字小，说明被查找的数在前面，则取
high=mid-1,low不变，继续查找步骤 2。
3、如果查到 low>high仍未找到，则说明找不到该数，查找失
败，停止。
这里有一步 非常重要,就是 low=mid+1和 high=mid-1，
是在查找过程的范围越来越小，最终找到结果。
6.7.1 常用查找方法
2 5 7 8 11 13 179 19 20 2321 26 29 31 3710
查找 low
39
mid high
2 5 7 8 11 13 179
low mid high
11 13 179
low mid high
9
low mid high
查找失败例
low
8 9 171311 207 19 21 23 3126 292 5 37 3923
查找 low mid high
20 21 292623 31 37 39
mid highlow
20 21 23
mid hig
h23
low mid high 成功
查找成功例
6.7.1 常用查找方法
对半查找递归算法,// 6-7-1.cpp
#include <iostream.h>
#include <stdlib.h>
class BinSearch {
private:
double *Plist;
public:
BinSearch(double *list,int n)
{ Plist = new double[n];
for(int i=0; i < n; i ++) Plist[i] = list[i];
}
~BinSearch()
{ delete []Plist;
}
void BinFind(int,int,double);
};
6.7.1 常用查找方法
void BinFind(int low,int high,double x)
{ int mid = (low+high)/2;
if(Plist[mid] == x) {
cout <<,the position is:, << mid << endl;
return;
}
else if(low >= high) {
cout << x <<, is not found !” << endl;
return;
}
else if(x > Plist[i])
BinFind(low+1,high,x);
else
BinFind(low,high-1,x);
}
6.7.1 常用查找方法
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 low = 0,high = 9;
BinSearch bs(a,10);
bs.BinFind(low,high,x);
bs.BinFind(low,high,1.6);
}
那么程序的运行结果是,the position is,6
1.6 is not found !
6.7.1 常用查找方法
对半查找迭代算法：
void BinFind(int low,int high,double x)
{ int mid;
while(low<=high) {
mid=(low+high)/2;
if(Plist[mid] > x) high = mid-1; //左缩查找区间
else if(Plist[mid] < x) low=mid+1;//右缩查找区间
else return mid;
}
return -1;
}
该例中 迭代算法 的可读性也不差，效率要高于递归。
6.7.1 常用查找方法
散列 （ hash） 查找是最快的查找方法 。 前两种
查找方法都是将查找关键字与表中的数据元素的值
直接进行比较而达到查找目的的 。 如果能找到一个
函数 f(key),将关键字经过函数的运算转换为数据
表中的位置, 直接将数据元素插入在该位置上 。 在
查找中直接用该位置的数据元素与关键字值比较,
以确定是否查到所要的数据元素 。 这样的组织称为
散列, 利用散列技术查找的方法称为散列查找, 散
列查找是一种直接查找 。 亦用音译称 哈希查找 。
6.7.2 常用的排序法
排序（ sorting） 是数据处理中经常使用的一种重要运算。
其功能是将数据元素的无序序列调整为一个有序序列。数据元
素中一般有多个数据项，排序可选择其中一个可排序的数据项
（可进行比较运算）作为依据，称为 排序关键字 。比如我们对
高考考生的统计表进行排序，可根据考生的准考证号，这样的
关键字可以 保证排序结果的唯一性，称主关键字 。但为了便于
录取，我们也可以按高考总分排序，只可称 关键字,这样同一
分数的人很多，这些人的排名可再取一个 次关键字 如数学或语
文分来排序，以减少重复排名的随意性。从小到大排序称升序，
反之为降序。
最常见的三类是插入排序、选择排序和交换排序，下面介
绍三类排序中最基本的方法。
6.7.2 常用的排序法
1,插入排序 (Insert Sorting)
(1)直接插入排序 的思想是,(以升序为例 )当插入第 i(i>=1)个元素 sl[i]时,前
面的元素 sl[0],sl[1],…,sl[i -1]已经排好序,我们将 sl[i]的关键字与 sl[i-1],
sl[i-2],…,的关键码顺序进行比较,找到第一个比它小的,则 sl[i]插到该元素
之后。那么怎么保证前面的元素排好序呢?可以从第一号元素开始，前面只
有第 0号元素,这 一个元素肯定是排好序的 ！参见下图。
i 0 1 2 3 4 5 6 temp
初始序列 [8] 6 7 9 4 5 2 6
1 [6 8] 7 9 4 5 2 7
2 [6 7 8] 9 4 5 2 9
3 [6 7 8 9] 4 5 2 4
4 [4 6 7 8 9] 5 2 5
5 [4 5 6 7 8 9] 2 2
6 [2 4 5 6 7 8 9]
直接插入排序算法中用了一个临时变量 temp，要插入的元
素放到 temp中，这样插入前各元素后移时允许将该元素冲
掉。
6.7.2 常用的排序法
升序直接插入排序算法,// 6-7-2.cpp
void InsertSort(int slist[],int n)
{ int temp;
int i,j;
for (i=1; i < n; i++) {
temp = slist[i];
j=i;
while (j>0 && temp < slist[j-1]) {
slist[j]=slist[j-1];
j--;
} //查找与移动同时做
slist[j] = temp;
}
}
void main()
{ int a[] = {8,6,7,9,4,5,2};
InsertSort(a,7); cout <<,排序后的数据是：” ;
for(int i=0; i < 7; i ++) cout << a[i] <<,,”;
cout << endl;
}
6.7.2 常用的排序法
从下往上扫描的冒泡程序
2．交换排序
交换排序的基本思想是按关键字两两排
序对象，如果发生逆序则交换之，直到
所有的对象都排好序为止。这里介绍 冒
泡排序（ Bubble Sort） 。
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49’ 49’ 49’ 49’ 49’
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49’ 49’ 49’ 76 97 97 97 97
冒泡排序基本思想 参见
右。最左列为最初的情
况，最右列为完成后的
情况。首先我们从一列
数据底部开始，相邻的
两数据进行比较，小的
数放上面，一趟比较下
来，最小的数据冒到了
最上面。再缩小区域，
按同样方法继续下一趟
交换，如果有一趟比较
中没有 发生交换，则已
排好序 。图中，第 5列就
已排好序，若再继续下
一趟就不会发生交换。
6.7.2 常用的排序法
冒泡排序算法：
void BubbleSort(int slist[],int n) {
bool noswap;
int i,j;
int temp;
for (i=0; i<last; i++){ //最多做 n-1趟
noswap=true; //未交换标志为真
for(j=n-1; j>i; j--) { //从下往上冒泡
if(slist[j] < slist[j-1]) {
temp = slist[j];
slist[j] = slist[j-1];
slist[j-1] = temp;
noswap = false;
}
}
if(noswap) break; //本趟无交换，则终止算法
}
}
6.7.2 常用的排序法
3．选择排序
选择排序（ Selection Sort） 的基本思想是：每一趟从待排序
的记录中选出关键字最小的元素，顺序放在已排好序的子序列的后
面，直到全部记录排序完成。直接选择排序（ Straight Selection
Sort）是最简单的，参见下图。此方法的最大优点是非常 易读 。
[49 38 65 97 76 13 27 49’]
13 [38 65 97 76 49 27 49’]
13 27 [65 97 76 49 38 49’]
13 27 38 [97 76 49 65 49’]
13 27 38 49 [76 97 65 49’]
13 27 38 49 49’ [97 65 76]
13 27 38 49 49’ 65 [97 76]
13 27 38 49 49’ 65 76 97
直接选择排序的过程
6.7.2 常用的排序法
选择排序：
void SelectSort(int slist[],int n) {
int i,j,k;
int temp;
for (i=0; i<n-1; i++){
k = i;
for(j=i+1; j<n; j++)
if(slist[j] < slist[k]) k = j;
if(k != i) {
temp = slist[i];
slist[i] = slist[k];
slist[k] = temp;
}
}
}
例题：
// 6-7-all.cpp
编写一个程序：将用户输入的由数字字符和非数字
字符组成的字符串中的整数提取出来，存放在数组
a 中，例如输入,asd764rt143,fg6746 则产生数字
764,143,6746
在程序设计的过程中，数据的组织和表示是很重
要的，因为数据是程序的处理对象，数据的表示形式
关系到整个程序的运行效率和解决问题的能力，前面
我们已经初步了解了数据的最基本形式 -整数、实数、
字符、字符串 等基本数据类型，也学习了在面向对象
的程序设计环境下，类和对象的构造和组织。下面我
们进一步学习其他在基本数据类型的基础构造出来的
一些复杂数据类型，如 数组、指针、结构、共用体、
枚举类型 等。使我们在类和对象的设计过程中，可以
运用更多的数据类型。
第六章 数据结构
6.1 数组概念和一维数组 6.5 结构类型
6.4 指针概念
6.3 字符串处理
6.2 二维数组
6.7 排序和查找
6.6 共用体
6.1 数组
数组类型是一种构造型（组合型）的数据类
型。 数组是由一组具有相同数据类型的元素组成的
集合，用来描述现实世界中具有相同性质的有序事
物集合的抽象，如班级某个学生各门课的成绩，或
者整个班级某门课的成绩。数组的类型就是这组元
素的数据类型。构成数组的这组元素在内存中占用
一组 连续的存储单元 。可以用一个统一的数组名标
识这一组数据，而用下标来指明数组中各元素的序
号。根据数组的维数，分为一维数组、二维数组和
多维数组，常用的是一维和二维数组。
6.1.1 一维数组
一维数组的定义,
类型 数组名 [常量表达式 ]；
其中，类型是数组类型，即数组中各元素的数据类型，可
以是整型、浮点型、字符型等基本类型，也可以其他复杂的数
据类型。数组名是一个标识符，代表着数组元素在内存中的起
始地址，它的命名规则与变量名的命名一样。常量表达式又称
下标表达式，表示一维数组中元素的个数，即数组长度（也称
为数组大小），用一对方括号,[ ]”括起来。方括号,[ ]”的
个数代表数组的维数，一个方括号表示一维数组。
例如：下面分别定义了一个具有 10个元素的字符型数组 a、
一个具有 5个元素的整型数组 b和一个有 20个元素的实数数组 f：
char a[10];
int b[5];
float f[20];
6.1.1 一维数组
对上面定义的数组 b,也可以采用下面这种定义方法：
const int size=5;
int b[size];
注意,在定义数组时, 不能用变量来描述数组定义中的元素个
数 。 例如, 下面的定义方式是不合法的,int b[n];
下标指明了数组中每个元素的序号, 下标值为整数, 用数组
名加下标值就可以访问数组中对应的某个元素 。 下标值从 0开始,
因此对于一个具有 n个元素的一维数组来说, 它的下标值是 0~ n-
1。 例如, 对上例中定义的数组 b来说, b[0]是数组中的第一个
元素, b[1]是数组中的第二个元素, …, b[4]是数组中的最后一
个元素, 而不包含 b[5]。
数组元素在内存中是顺序存储的 。 对于一维数组, 就是简
单地按下标顺序存储 。
例如, 对上面定义的整型数组 b,在内存中的存放顺序如下
图所示,b[0] b[1] b[2] b[3] b[4]
6.1.1 一维数组初始化
一维数组的初始化：
在定义数组时对其中的全部或部分指定初始值,
这称为数组的初始化 。 初始化的语法格式为：
类型 数组名 [数组大小 ]={值 1,值 2,…, 值 n};
例如：定义一个字符数组 a并进行初始化 。
char a[5]={’a’,’b’,’c’,’d’,’e’};
或：
char a[ ]={’a’,’b’,’c’,’d’,’e’};
定义一个整数数组 b并进行初始化
int b[7]={11,22,65,87,100,42,77};
6.1.1 一维数组初始化
注意,在对数组初始化时，也可以只对数组中的部分元素指
定初始值。也即，初始化值的个数可以少于或等于数组定义
的元素的个数，但不可以多于数组元素的个数，否则会引起
编译错误。
当初始化值的个数少于数组元素个数时，前面的元素按
顺序初始化相应的值，后面不足的部分由系统自动初始化为
零（对数值数组）或空字符‘ \0?（对字符数组）。
int b[7]={11,22,65,87};
一维数组的赋值
1,用, =”赋值
与数组元素的初始化不同, 在给数组元素进行赋值时,
必须逐一赋值 。
例如：对于下述的数组初始化：
int a[3]={1,2,3};
6.1.2 一维数组赋值
其等价的赋值形式如下：
int a[3];
a[0]=1;
a[1]=2;
a[2]=3;
若要在数组之间进行赋值, 也只能一个一个元素地赋值 。
例如：将上述数组 a的值赋给另一个同样大小的数组 b，
可以利用下面的循环完成赋值操作：
for (i=0;i<3;i++) b[i]=a[i];
2,用流命令赋值
其语法格式为：
cin>>数组名； // 只适合用于字符数组
或
cin>>数组名 [下标 ]；
6.1.2 一维数组赋值
例如：对一个大小为 5的字符型数组 a赋值, 可以用
下列两种方式：
char a[5]; // 只适合用于字符数组
cin>>a;
或 char a[5];
int i;
for (i=0;i<5,i++) cin>>a[I];
6.1.3 一维数组引用
一维数组元素的引用：
数组在定义后即可引用, 引用是以元素为单位的 。 其引用
形式为,数组名 [下标 ]
指明了引用数组名的数组中下标所标识的元素。下标可
以是整常数或整型表达式。例如 a[2+1],a[i+j]等（ i和 j为
整型变量）。例如：
a[2]=10; //将 10赋给数组中的 a[2]元素 。
a[5]=a[2]; //将 a[2]元素的值赋给 a[5]元素
cout<<a[5]; //打印 a[5]元素的值
注意区分定义与引用形式上的相似与含义上的区分, 定义时
是指数组的大小空间；引用时是指引用下标标识的元素 。
引用时一定要注意下标的值不要超过数组的范围, 否则会产
生数组越界问题 。 例如：定义了一个整型数组 a,int a[10];
数组 a的合法下标为 0~9。如果程序要求给 a[10]赋值，将可能
导致程序出错，甚至系统崩溃。
注意：
1,数组是一种 组合类型,是不能作为一个整体进
行访问和处理的，只能按元素进行 个别 的访问和处理。
2,C++数组第一个元素的下标为 0，而不是 1，
且下标表达方式是固定的。
3：数组元素在内存中是从低地址开始 顺序排列,
各元素的存储单元占用内存大小相同，各元素的存储
单元之间 没有空隙,可以从数组第一个元素存储单元
的起始地址计算出任意一个元素存储单元的起始地址。
6.1.4 一维数组例子
找出一个整型数组各数组元素中的最大数和最小数, 数组中的数由随机数
函数 rand()产生 。 这是很典型的基本算法, 细讲 。
const SIZE=15;
void main()
{ int arr[SIZE]; int i,high,low;
for(i=0; i<SIZE; i++) arr[i]=rand()%100;
for(i=0; i<SIZE; i++) cout<<arr[i]<<'\t';
cout<<endl;
high=arr[0]; //最大和最小值均为数组的第 0个元素
low=arr[0];
for(i=1; i<SIZE; i++) {
if(arr[i]>high) high=arr[i];
if(arr[i]<low) low=arr[i];
}
cout<<"highest value is "<<high<<endl;
cout<<"lowest value is "<<low<<endl;
return;
}
6.2 二维数组
二维数组的定义：
二维数组也称为矩阵, 需要两个下标才能标识某个元素
的位置, 通常称第一个下标为行下标, 称第二个下标为列下标 。
定义二维数组的语法格式为：
类型 数组名 [常量表达式 1][常量表达式 2]；
定义二维数组的格式与定义一维数组的格式相同，只是
必须指定两个常量表达式，第一个常量表达式标识数组的行数，
第二个常量表达式标识数组的列数。
例如,int a[2][3]；
上面定义了一个二维数组 a,它在逻辑上的空间形式为 2
行 3列, 也可以这么说, 定义了两个一维数组 a[0]和 a[1],而
a[0]和 a[1]每个又是一个有 3个元素的一维数组 。 每一个数组
元素都是整型数据, 因此 a数组的各元素如下：
a[0] a[0][0] a[0][1] a[0][2]
a[1] a[1][0] a[1][1] a[1][2]
// 每一维的下标都是从 0开始
可见, 二维数组中每个元素都是用下列方式标识：
数组名 [行下标 ][列下标 ]
二维数组在内存中的排列顺序是, 先行后列,,
即在内存中先存第一行的元素，然后再存第二行的元
素。从数组下标变化来看，先变第二个下标，第一个
下标先不变化（即 a[0][0],a[0][1],a[0][2]），待第
二个下标变到最大值时，才改变第一个下标，第二个
下标又从 0开始变化。比如上面定义的 2行 3列的二维
数组 a，在内存中的存放顺序上图所示。
6.2 二维数组
6.2 二维数组
由于二维数组在内存中是线性排列的, 引用一维
数组和引用二维数组都是引用相应存储地址的内容,
因此可以计算出一个二维数组元素在对应一维数组中
的顺序号, 从而将对二维数组元素的引用转变为对一
维数组元素的引用, 这个过程称为, 降维处理, （ 经
常在向函数传递数组时用到 ） 。
举例来说, 假设有一个 m x n的二维数组 a,其中第
i行第 j列元素 a[i][j]在数组中的位置公式为：
i*n+j
例如有一个 3*4的矩阵 a：
a00 a01 a02 a03
a= a10 a11 a12 a13
a20 a21 a22 a23
a21元素在数组中的位置是 2*4+1=9。 即它在数
组中是第 9个元素 。 对一个 aij元素 （ 在 C++语言中表
示为 a[i][j]）, 在它前面有 i行 （ 对 a21来说它前面有
两个整行 ）, 这 i行共有 i*n个元素 。 在 aij所在行中,
aij前面还有 j个元素, 因此在数组 a中 aij前面共有
（ i*n+j） 个元素 。 那么 aij就是第 （ i*n+j） 个元素,
计算方法是从 0开始的 。
6.2 二维数组
6.2.1 二维数组初始化
二维数组初始化：
和一维数组一样, 二维数组也能在定义时被初始
化, 只是要注意必须按照前面所讲的存储顺序列出数
组元素的值 。 常见有如下一些初始化方式：
（ 1） 分别对各元素赋值, 每一行的初始值用一对花
括号括起来 。 例如：
int a[2][3]={{1,2,3},{4,5,6}};
将第一对花括号内的三个初始值分别赋给 a数组
第一行三个元素, 第二对花括号内的三个初始值赋给
第二行元素 。 数组中各元素为：
1 2 3
4 5 6
6.2.1 二维数组初始化
（ 2） 将各初始值全部连续地写在一个花括号内, 在
程序编译时会按内存中排列的顺序将各初始值分别赋
给数组元素 。 例如
int a[2][3]={1,2,3,4,5,6};
数组中各元素为：
1 2 3
4 5 6
（ 3） 只对数组的部分元素赋值 。 例如：
int a[2][3]={1,2,3,4};
数组共有 6个元素, 但只对前面 4个元素赋初值,
后面两个未赋初值, 其值为 0。 数组中各元素为：
1 2 3
4 0 0
6.2.1 二维数组初始化
（ 4） 可以在分行赋初值时, 只对该行中一部分元
素赋初值, 例如：
static int a[2][3]={{1,2},{4}};
对第一行中的第一, 二列元素赋初值, 而第三个
元素未赋初值 。 第二行中只有第一列元素赋初值 。
数组中各元素为：
1 2 0
4 0 0
6.2.2 二维数组省略定义
省略第一维大小定义,
若在定义数组时给出了全部数组元素的初值, 则
数组的第一维下标可以省略, 但第二维下标不能省略 。
例如：下面两种定义方式等价：
static int a[2][3]={1,2,3,4,5,6};
static int a[ ][3]={1,2,3,4,5,6};
编译器会根据元素的总个数分配空间, 每行 3列,
共 6个元素, 故该数组行数为 6/3=2行 。
但上例不能写成：
static int a[2][ ]={1,2,3,4,5,6};
6.2.3 二维数组例子
编写一个程序，统计某个班三门课语文、数学、
英语的成绩，先输入学生人数，然后按编号从小到大
顺序依次输入各个学生的成绩，最后统计每个学生的
课程总成绩和平均成绩，及每门课的平均成绩，并列
表输出。
分析,每个同学需要处理的包括三门课成绩和总分、
平均分共 5个实数类型数据，而一个班级可能有若干
个学生，所以处理这个班级用二维数组来处理是最方
便的，定义 float score[100][5]; 第一维表示学生，
第二维表示成绩，所以例如第 3个学生的数学成绩是
score[3][1]这个元素。另外，定义一个一维数组
total[3]用来处理三门课的平均成绩。既然数据已经
表示好，下面的实现相对就简单多了。
6.2.3 二维数组例子
#include <iostream.h> // 6-1-2.cpp
#include <iomanip.h>
void main()
{ float score[100][5],total[3]={0,0,0};
int i,j,n;
cout<<"请输入学生人数,";
cin>>n;
for(i=0; i < n; i++) {
cout<<"输入第 "<<i+1<<" 个学生三门课成绩,";
score[i][3] = 0;
for(j=0; j<3;j++) {
cin>>score[i][j];
score[i][3] += score[i][j];
total[j] += score[i][j];
}
score[i][4] = score[i][3]/3.0;
}
6.2.3 二维数组例子
cout<<"学号 语文 数学 英语 总分 平均分 "<<endl;
cout<<"---------------------------------------- "<<endl;
for(i=0; i<n; i ++) {
cout<<setw(4)<<i;
for(j= 0; j<5; j++)
cout<<setw(8)<<score[i][j];
cout<<endl;
}
cout<<"平均分 ";
for(i=0; i<3; i++)
cout<<setw(8)<<total[i];
cout<<endl;
}
6.3,字符串处理
前面讨论的有关数组时，仅涉及到数值型数组，现在专门
讨论一下字符数组：
字符数组的定义, 用来存放字符数据的数组，就是说，字
符数组中的每个元素存放一个字符。字符数组用来存放字符和
字符串，其区别在于：在一个字符数组中，如果有字符串结束
符’ \0?，那么，该数组存放的是一个字符串。字符数组也有
一维，二维，三维数组。
字符数组的初始化,初始化跟数值型数组一样，如：
char c1[4] = {?a?,?b?,?c?,?d?};
char c1[][3] = {?a?,?b?,?c?,?d?,?e?,?f?}; 那么应该第
一个下标为 2
char c1[][3] = {?a?,?b?,?c?,?d?,?e?,?f?,?g?}; 那么应
该第一个下标为 3
而 c1[2][0] = ?g? c1[2][1] = ?\0?,c[2][2] = ?\0?;
6.3 字符串处理
我们曾经介绍过字符串的概念，每个字符串最后都有一
个字符串结束标志 ’ \0?，就是一个, 空操作符,,即它什么
也不做，只是用来判别字符串是否已结束，所以用字符数组
来表示字符串时，长度就显的不是很重要，在程序中一般是
用 ’ \0?来判断字符串是否已结束。但必须保证数组长度一定
大于字符串长度。
了解 C语言对字符串处理方法之后，我们可以用字符串
给字符数组初始化，如：
char c[] =,China” 相当于
char c[6] = {?C?,?h?,?i?,?n?,?a?,?/0?}
而不是 char c[5] = {?C?,?h?,?i?,?n?,?a?};
char c[10] =,China” 相当于
char c[10] = {?C?,?h?,?i?,?n?,?a?,?\0?,?\0?,?\0?,?\0?,
?\0?}
6.3 字符串处理
字符数组的引用：
分析结果：
main()
{ char s1[5] = {?a?,?b?,?c?,?d?,?\0?};
s1[2] = ?g?;
cout<< s1[0]<<s1[2]<<endl;
cout<<s1<<endl;
}
a,g
abgd
6.3 字符串处理
字符数组的输入输出：
#include <iostream.h>
main()
{ char x[3][10];
cout<<“Input String:”<<endl;
cin>>x[0]>>x[1]>>x[2];
cout<<“Output String:”;
cout<<x[0]<<“,”<<x[1]<<“,”<<x[2]<<endl;
}
如输入,how are you?
那么,x[0] =,how”,x[1] =,are”,x[2] =,you?”,在内
存中是这样存放的。
H o w\0
A r e \0
Y o u \0
6.3 字符串处理
用 cout输出字符数组时，系统从字符数组的第 0个字符开始
逐个输出，遇到字符串结束符’ \0?时，就停止输出，不管后面
是是什么字符。但如果我们这么定义，那结果会是如何呢？
char c[5] =,China”;
printf(“%s\n”,c);
程序会在’ a?之后继续寻找’ \0?,直到找到为止。
字符串处理函数
puts(字符数组 ),输出一个字符串，也可以用 cout输出
gets(字符数组 ),从键盘输入 一行字符串 到字符数组中
// 上面两个函数需要包含 #include <stdio.h>
l strcat(字符数组 1,字符数组 2),字符串连接函数
将字符串 2接到字符串 1后面，并把结果放在字符串 1中，所
以字符串 1要足够大容纳新字符串内容，二是连接时将字符串 1
的’ \0?取消，只在新串中保留一个’ \0?;
main()
{ char s1[30] =,Zhong Shan,;
char s2[] =,University”;
strcat(s1,s2);
cout<<s1<<endl;
}
6.3 字符串处理
strcpy(字符数组 1,字符数组 2),字符串拷贝，复制函数
将字符串 2完全复制到字符串 1，即字符串 1和字符串 2内
容完全一样。这里有几点需要说明：
1,是字符串 1足够大，能够容纳；
2,是字符串 2可以是常量，也可以是字符数组
3,不能用赋值语句将字符串常量或字符数组给字符数组
赋值，如
str1 =,China”
str2 = str1
只能用 strcpy 函数
4,可以用 strcpy函数将字符串 2中前面若干个字符复制
到字符串 1中，如 strcpy(str1,str2,2),如果 str2=“China”,
那么 str1等于” Ch”
6.3 字符串处理
strcmp(字符串 1，字符串 2), 字符串比较函数
比较的规则是自左至右逐个字符（按 ASCII码值）比
较，直到出现不同字符或’ \0?为止，如果全部相同，那么我
们认为这两个字符串是相同的，返回值为 0，若出现不同，
那么以第一个不同的字符大小为准，如果大，则返回一个正
整数，小则返回一个负整数。
,A” <,B”,“computer”>,compare”,“DOG” <
“cat”
记住，比较两个字符串，不能用
if(str1 == str2) cout<<“OK”<<endl;
strlen(字符数组 ),计算字符串的长度，不是数组的大
小，而是字符串实际长度，就是说到’ \0?前面的长度。
Char str[10] =,china”;
cout<<strlen(str)<<endl;
应该是 5，而不是 10
strwr(字符串 ),将字符串中大写字母转换为小写
strup(字符串 ),将字符串中小写字母转换为大写
编写一个函数 insert(char s1[],char s2[],in p) 实
现将 s2字符串插入到 S1字符串 p的位置上。
#include <string.h>
insert(char s1[],char s2[],int p)
{ char buf[100];
int i = 0;
while(s1[p+i]) {
buf[i] = s1[p+i];
i ++l
}
buf[i]=?\0?;
s1[p]=?\0?;
strcat(s1,s2);
strcat(s1,buf);
}
while(buf[i]=s1[p+i])
i++;
6.4 指针的概念
今天我们讲的, 指针, 是 C和 C++语言中一个非常重要的概
念，因为很多语言都没有指针概念，如 BASIC,PASCAL等。
并且, 指针, 也是 C 程序的最大难点。刚开始学习, 指针,
概念时，同学们或许会感到指针很难理解，但当你深入学习
时，你就会发现它是个很奇妙的运用。
那怎么样才能掌握好指针呢？
首先要从指针的概念入手，要搞清楚什么是指针，它是如
何定义和说明的，怎么样给指针赋值和指针有那些合法的运
算。
其次要掌握指针在数组和函数中的很多应用及如何表示
复杂的数据结构
● 可以有效的表示复杂的数据结构
● 能动态分配内存
● 能方便地使用字符串
● 有效而方便地使用数组
● 能直接处理内存地址等
6.4 指针的概念
为了说清楚指针的概念，我们必须了解数据在内存中是如何存储
的，又是如何读取的。我们知道，数据变量的定义和存储都在系统
的用户内存数据区中，包含静态和动态数据区。
我们定义
int i=3,j=6,k=9; 内存用户数据区
那么系统在编译时就给三 2000 变量 i
个变量分配内存空间。 2002 变量 j
一般系统 int占 2个 2004 变量 k
字节，分配如图所示：
而内存区中每个字节都 3010 指针变量 i_pt
有编号，这个编号就是
,地址, 概念，如图中的 2000就是变量 I的地址,2002是 j的地址，
2004是 k地址 …… 3010是 I_pt地址等等 。 地址就好象是房间号，
而地址中存放的值就好象是房间中的旅客。所以同学们一定分清一
个变量的地址和变量的值是不同的，在图中变量 I的地址是 2000，
而变量的值（或内容）则是 3.
3
6
9
2000
6.4 指针的概念
通过上面,我们已经了解地址的概念,其实在程序中,对某个
变量的存取都是通过对该变量的地址操作实现的,变量名和地址
的对应关系,在变量定义时或临时申请内存空间时就已确定的,
如有语句, k=i+j;
那么系统首先从 2000,2001中取出变量 i的值 3,再从
2002,2003中取变量 j的值 6,将他们相加后的值 9送回到变量 k的
地址 2004,2005中,这种按地址存取变量值的方式叫, 直接访问
方式,,
另一种是, 间接访问方式,, 就是我们定义一个变量, 该
变量的内容是其它变量的地址, 如图中的 i_pt,它里面存放的
2000就是变量 I所占单元的起始地址, 那么访问 i的值, 我们首
先通过 i_pt知道变量 I的地址, 然后再进行存取 。 这就是, 间
接方式, 。 由于是通过地址找到所需的变量单元, 也可以说是
,地址, 指向该变量单元, 所以我们形象地称, 地址, 为, 指
针, 。
2000 k
2010 p
我们可以这么说：
变量 ——存放数据的地方
变量的地址 ——指针
指针变量 ——存放地址的变量 /* 就是 i_pt */
指针变量的定义：
类型 *指针名；
int k,j,*p; p=&k;
float *fp1,*fp2,f; fp1 = &f;
char *str;
要注意：
（ 1） 指针变量前的 *,表示该变量的类型是指针型变量, 指
针变量名本身是不包括 *的 。
（ 2） 定义指针变量时必须指定类型, 因为每种数据类型所占
的字节数不同, 指针值的变化是以数据类型为对象进行操作的 。
P++,字符类型指针每次移动一个字节, 整数类型指针每次移
动 2个字节, 而实数类型每次移动 4个字节
6.4.1 指针定义
2000
6.4.2 指针的运算符
2000 k
2010 p
指针变量的运算：
两个相关运算符 int k,*p; p=&k;
& 取地址运算符
* 指针运算符（间接访问）
*p 等价 k
&*p 等价 &k
*&k 等价 k
例子：
main()
{ int x,y;
int *p1 = &x,*p;
p2 = &y;
*p1 = 10;
y = 20;
printf(“%d,%d\n”,x,*p2);
}
8
2000
同类型的指针可以相互赋值，如有说明
int val1=18,val2=20;
int *p_val1,*p_val2;
p_val1=&val1;
p_val2=&val2; 则 p_val1指向 val1,p_val2指向 val2，
执行 p_val1=p_val2后，则 p_val1也指向 val2，而没有指针
指向 val1了。参见下图。
20
18
20
18
va11P_va11
P_va12 va12
P_va11
P_va12
va11
va12
指针间赋值后的变化
6.4.2 指针的运算符
6.4.2 指针运算例子
例子：
main()
{ int i;
char s[] =,string”;
char *p1 = s,*p2;
p2 = s;
i = 0;
while(s[i++] != ?\0?) p2 ++;
printf(“%d\n”,p2-p1);
}
两个指针相减，在一定条件下才有意义，这个例子中两
个指针相减，其差值表示两个指针间的相距的元素个数。所
以一般在同一数组内有效。
a
s
t
r
i
n
g
\0
p1
p2
6.4.3 指针和数组的关系和运算
指针和数组的关系：
数组,一组同类型变量的集合，用一个名字表示，内存中连
续存放。
既然数组中的每个元素都占存储单元，它们都有相应的地址，
并且其地址还是连续的，所以，用指针来处理数组更体现出方
便性和高效性。 数组名 被看作该数组的第一个元素在内存中的
首地址。
数组名在表达式中被自动转换为一个指向数组第一个元素的
指针常量 。数组名中所放的地址是不可改变的，所以称指针常
量（即隐含说明“元素类型 * const数组名”）。
数组名可以由指针来代替, 非常方便, 但是却 丢失 了数组
另一个 要素, 数组的大小, 即数组元素的数量 。 编译器按数组
定义时的大小分配内存, 但 运行时 （ run time） 对数组的边界
不加检测 。 这会带来无法预知的严重错误 。
6.4.3 指针和数组的关系和运算
C++提供根据数组的存储地址访问数组元素的方
法。右图定义 int a[10],*p=a; a是数组第一个元
素的地址，所以 *a是数组的第 0个元素 a[0]，而 a+1
是数组第 1个元素的地址,*(a+1)是第 1个元素 a[1]
本身 … 。 尽管不同的计算机系统中整数所占的字节数
可能并不相同,但我们不必去考虑这个差异,C++的
编译系统保证了对数组运算的正确性,指针加 1，则地
址移动一个数组元素所占字节数 。
C++语言的下标运算符 [ ]是以指针作为操作数的，
a[i]被编译系统解释为 *(a+i)，即表示为 a所指 (固定
不可变 )元素向后第 i个元素。无论我们是以下标方式或
指针方式存取数组元素时，系统都是转换为指针方法
实现。
p=a 表示把 a数组的首地址赋给 p，即 p指针指向
数组 a的首地址。 p+i,a+i和 &a[i]都是第 i个元素的
地址,那么 *(a+i),*( p+i ),a[i],p[i]等价
a[0]
a[1]
a[2]
a[9]
p
a
a+1
a+2
6.4.3 指针和数组的关系和运算
了解指针后，对一个数组的元素进行遍历，有以下几种方法：
（ １） 下标法：比较直观
main()
{ int a[10],i;
for(i = 0; i < 10; i ++) cin >> a[i];
cout << endl;
for(i = 0; i < 10; i ++) cout << a[i] <<,,;
}
（２） 通过数组名计算元素地址
printf(“%d,,*(a+I));
3）用指针变量指向数组元素：效率最高，因为它不需每次重新计算元素地
址
int *p;
for(p = a; p < (a+10); p ++) cin >> *p;
for(p = a; p < (a+10); p ++) cout << *p <<,,;
6.4.3 指针和数组的关系和运算
那如果是以下程序，那么有何结果呢？
int i; for(p = a; p < (a+10); p ++) cin >> *p;
for(i = 0; i < 10; i ++,p ++) cout << *p <<,,;
由于 p指针已经指向数组的末位，再执行第二个循环，会出现
意想不到的数据，要想得到正确答案，应该在第二个循环前加上
p = a 的赋值语句。
指针运算应注意问题：（假设 p=a,inta[10]）
1,p++ 指向下一个元素
2,*p++ 由于 ++和 *同优先级，结合从右到左,*(p++)
所以应该先取 p指向的值，然后 p++，指向下一条元素
3,*(p++)和 *(++p) 不同，先 *p，后 p++,而后面是 p++，
然后 *p
4,（ *p） ++ 内容加 1而不是指针加 1
5,如果 p指向 a数组的第 i个元素，那么：
*(p++) = a[i++]
*(++p) = a[++i]
6.4.3 指针和数组的关系和运算
上面我们讲了数值型和字符型数组指针，但都是一维的，下面
我们讲多维的数组指针是如何使用的。首先我们分析一下多维数组
在内存中的存储方式。
ü 多维数组的地址
static int a[3][4]={{1,3,5,7},{9,11,13,15},{17,19,21,23}};
a[0](2000)?
a[1](2008)?
a[2](2016)?
相当于二维数组 a包含三个一维数组,a[0],a[1],a[2]，而他们
又分别包含四个元素。所以 a表示整个数组的首地址，而 a+1表示第
一行的首地址，而 a[1]也是第一行的首地址 &a[1][0]，所以两者地
址是相同的。同样,a+2跟 a[2]是一样的，都是第二行的首地址。
那么如何表示第 0行第一列的元素地址呢？ a[0]+1（ 2002），就是
&a[0][1]
而 *(a+1) 是什么呢？首先我们知道 a+1是第一行的首地址，根
据上面介绍的,*（ a+1）应该是 a+1所指向的内容，由于 a+1实际上
并不是一个变量，也谈不上它的内容，所以 *(a+1)就是 a[1]，即第
一行的首地址。
1 3 5 7
9 11 13 15
17 19 21 23
6.4.4 指针作为函数参数
C++中函数的参数的基本使用方法是 传值 。 为了弥补单纯
传值的不足, 以 引用作为函数的参数, 从逻辑上讲引用是别名,
在函数中对参数的操作, 就是对实参的操作, 而在 物理上是传
实参的地址 。
将 指针用作函数的参数 时，传的仍然是值，指针的值，这
个值就是指针所指向的变量或对象的内存首地址，在物理上讲
我们传的是指针的值，与传其它变量是没有差异的，函数获得
的是另一个变量的地址，在逻辑上讲我们是把另一个变量的地
址传过去了，可以看作 传地址 。
6.4.4 指针作为函数参数
例子：输入两个整数，按大小顺序输出。
swap(int *p1,int *p2)
{ int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
main()
{ int a,b,*p_1 = &a,*p_2 = &b;
cin >> a >> b;
if(a<b) swap(p_1,p_2);
cout << a << b; /* cout << *p_1 << *p_2; */
}
6.4.4 指针作为函数参数
分析如下程序，
swap(p1,p2)
int *p1,*p2;
{ int *temp;
*temp = *p1;
*p1 = *p2;
*p2 = temp;
}
分析如下程序，
swap(p1,p2)
int *p1,*p2;
{ int *temp;
temp = p1;
p1 = p2;
p2 = temp;
}
6.4.5 数组名作为函数参数
数组作为函数参数传递有两种表现形式：
（ 1）以前我们讲过将 数组元素 作为实参传递给函数，属于
“值传递”
（ 2）数组名作为实际参数，因为 数组名 也是指针常量，当然
可以作为函数的参数。在函数调用时 传递实参数组的首地址,
所以在被调函数中对形参数组的处理实际就是对调用函数的
实参数组的处理。在被调函数中作为形式参数的一组数组不
需要说明长度，即使说明了大小也不起作用，因为 C++只传
递数组首地址，而对数组边界不加检查 。这带来的好处是，
函数对长度不等的同类数组都通用。如要 指定长度可以设定
另一个参数来传递数组元素的个数。
6.4.5 数组名作为函数参数
我们也可以直接将数组名作为实参传递给函
数，属于“地址传递”，地址传递后，在函数中数
组元素的值变化会影响实参中各个元素的值。
main()
{ int array[10];
……
array[2] = 7;
……
fun(array,10);
……
}
7(10)
array
fun(int ap[],int n)
{ ……
ap[2] = 10;
……
}
ap
6.4.5 数组名作为函数参数
实参、形参分别可用数组名或指针变量四种情况：
数组 --,数组 数组 --,指针 指针 --,数组 指针 --,指针
下面用指针的方式来说明求 10个数中的最大值和最小值
（因为需要求两个返回值，我们设两个全局变量来处理 )
int max,min;
main()
{ int i,num[10];
for(i = 0; i < 10; i ++) cin >> num[i];
max_min_value(num,10);
cout <<,Max =, << max <<,Min =, << min;
}
void max_min_value(int array[],int n)
{ int *p,*array_end;
array_end = array + n;
max = min = *array;
for(p = array+1; p < array_end; p ++) {
if(*p > max) max = *p;
if(*p < min) min = *p;
}
}
6.4.6 指针作为函数参数返回值
函数的返回值也可以是指针。如希望返回多个值，可以用
引用参数或指针参数来等效实现，如果我们希望 返回一个数组
或字符串,并且这个数组生命期不在该函数中消亡，我们可以
返回一个指向该数组的指针 。
设计一个 input函数中输入数据，然后在主函数中输出
void main()
{ float *input(),*data;
data = input();
for(int i = 0; i < 10; i ++) cout << data[i];
delete data;
}
float *input()
{ float *buf = new float[10];
for(int i = 0; i < 10; i++) cin >> buf[i];
return buf;
}
6.4.7 指针的注意事项
*指针与引用
C语言的指针容易失控，所以在 C++中增加了引用类型，
它具有指针的主要功能，但限制了灵活性，使用更加安全。
引用并非简单的指针常量（作为别名，它不能在使用中指
向其他对象），它又可以作为左值，这点却又象指针的间
接引用，功能更加强大。建议 在函数参数传递中，能用
,引用, 时绝不用, 指针, 。
6.4.8 指针在字符串中的应用
在 C++语言中, 可以定义一个字符数组, 将字符串存放在
该数组中, 通过数组下标来访问所需的字符；也可以定义一个
字符指针, 通过指针的指向来访问所需的字符 。
定义方式如下,char * 指针名 ;
main()
{ char *sp =,I love China!”;
cout << sp;
sp = "You love China!";
cout << sp;
}
I love China! You love China!
sp
6.4.8 指针在字符串中的应用
用字符指针将两个字符串连接
#include <iostream.h>
void strcat(char *s,char *t)
{ int i=0,j=0;
while (* s) s++;
while (* t) s++ = *t++;
*s = '\0';
}
void main (void){
char a[40]="李明 ";
char b[20]="是东南大学学生 ";
strcat(a,b);
cout<<a<<endl; //打印字符数组 a
}
6.4.9 指针数组
数组的内容, 就是数组元素既可以是普通类型的数据, 也可
以是指针 。
指针数组的定义 类型标识 *数组名 ［ 数据长度 ］ ；
如 int *p[4],表示 4个元素都是指针变量的指针数组 。
指针数组相当于二维数组, 为什么这么说呢？ 因为我们知道,
一个指针可以指向一个一维数组, 那么指针数组可以理解为多
维数组 。 那为什么不用二维数组, 而用指针数组呢？ 因为它适
合于处理多个字符串, 譬如我们用一二维数组来处理人名：
char name[3][12] = {“ZhangSan”,“LiSI”,“ShunWU”};
char *name[3] ={“ZhangSan”,“LiSI”,“ShunWU”};
引用 name[0] ->“ZhangShan”,
name[1] ->”LiSi”,
name[2]->”ShunWU“
也可以引用 name[0][2]（ ‘ a?） ;
可以节省空间, 并且用
指针处理, 更加方便灵活 ！
Name[0]
Name[1]
Name[2]
Zhang San
Li Si
Shun Wu
6.4.9 指针数组main()
{ void sort(char *name[],int n);
char *name[] = {“ViusalC++”,“Basic”,
“Pascal”,“Delphi”};
sort(name,4);
for(int i=0; i<4; i ++) cout << name[i];
cout << endl;
}
void sort(char *name[],int n)
{ char *temp; int i,j,k;
for(i=0; i<n-1;i++) {
k=i;
for(j=i+1; j<n; j++)
if(strcmp(name[k],name[j]) > 0) k = j;
if(k != i) { temp = name[i],
name[i] = name[k]; name[k] = temp }
}
}
6.4.10 this 指针
当在对象的外部访问该对象的公有成员时, 必须指明是
哪一个对象 。 但是当我们用对象的成员函数来访问本对象的
成员时, 在成员函数中只要给出成员名就可以实现对该对象
成员的访问 。 再进一步可用同一个类创建很多个对象, 但它
们共用同一份成员函数的拷贝 。 既然是同一份拷贝, 那么成
员函数又怎么知道是取哪一个对象的成员数据呢？ 其实 当调
用一个成员函数时, 系统自动产生一个隐藏的指针, 这个指
针称为 this指针, 它始终指向产生这个调用的对象, 并将该
指针作为一个参数自动传递给该成员函数 。 这就是说, 成员
操作符总是要使用的, 只不过在对象内是隐式的, 而在对象
外是显式的 。 即在对象内省略了 this指针 。
6.4.10 this 指针
实际上编译器是这样实现 this指针的
1,改变类成员函数的定义, 用附加参数 this指针来定义每个
成员函数 。 如：
void Circle::OutputArea(Circle *this)
{
cout<<“圆的面积为,”<<PI*this->mfR*this->mfR<<endl;
}
2,每个类成员函数的调用, 加上一个附加的实参 ——被调用
对象的地址 。 如：
cs1.OutputArea ( );
改变为：
cs1.OutputArea ( &cs1);
6.4.10 this 指针
在上例中,this指针不必写成显式的，但是 有时
必须写成显式 的，如在以后要学的某些类型的链表管
理中，在需要返回当前调用的对象时（对复数类的赋
值号重载中 ），等等。但必须指出 静态成员函数没
有 this指针 。因为普通成员函数虽然在物理上只有一
份拷贝，但在逻辑上都认为一个对象有一份拷贝，所
以有 this指针，而静态成员函数在逻辑上也只有一份
拷贝，不属于具体的对象，当然没有 this指针。
6.5 结构类型
我们知道数组是一种构造数据类型, 今天我们讲另一种
更复杂的构造数据类型, 就是, 结构体,, 跟数组一样, 它们都是
从基本的数据类型演变而来的, 那什么是, 结构体, 呢, 所谓的
,结构体, 就是由多种数据类型的变量构成的一个集合 。 当只使用
数据成员, 而且这些数据成员的类型往往互不相同时, 总是采用结
构类型, 而不采用类 。
结构体的类型的定义
struct 结构体名 {
结构成员说明；
}；
其中 struct是关键字,,结构体名, 是用来标识结构体类型的，
,结构成员说明, 是若干个成员的说明，每个成员都有类型和名字，
每个成员名的命名规则与变量名相同；数据类型可以是基本变量类
型和数组类型，也可以是指针变量类型，或者是一个结构体类型；
用分号“；”作为结束符。整个结构的定义也用分号作为结束符。
类型名 成员名 ；
成员也可称为域表
6.5 结构类型
这样, 我们可以用一个结构来表示学生的情况
例如,struct student {
int num;
char name[20];
char sex;
int age;
float score;
char addr[20];
};
注意：上面我们定义的只是一种由用户自行定义的结构类
型, 是一种新的数据类型, 它跟 int,float一样, 只有定义变量
之后, 系统才分配具体的内存空间, 存储具体的数据 。 在程序
文件中, 并且 强烈推荐将结构类型的定义放在所有函数的外面 。
结构体变量的定义 （ 三种方法 ）,
1,先定义类型, 后定义变量
struct student s1,s2;
s1
S2
分配的空间就是所有成员的字节数之和
2,类型与变量同时定义
struct 结构体名 {
结构成员说明；
} 变量序列；
3,直接定义变量
struct {
结构成员说明；
} 变量序列；
6.5 结构类型
10001 Zhang San M 19 90.5 Shang Hai
10002 Wang Li F 20 87 Bei Jing
6.5 结构类型结构体变量的使用：
结构体变量的引用有两种形式：
1,对其成员进行操作
访问成员是通过,,” 的成员运算符进行的,,,”优先级是很高
的
,结构体变量名,,,成员名,
对于学生结构来说, 我们可以
s1.no = 10001;
strcpy(s1.name,“ZhangShan”;
average = (s1.score + s2.score)/2;
s2.age ++;
cin >> s1.age >> s2.name;
2,访问整个结构体变量
可以在相同类型的结构类型变量之间进行赋值, s2 = s1; 表示
将 s1中的每个成员内容相对应地赋给 s2中的成员 。
但要注意,C++不允许用 cin,cout对结构体变量进行整体输入
或输出, 如 cin >> s1; 是不行的, 不能对整个结构进行赋值
6.5 结构类型
结构体变量的初始化,
结构变量赋初值跟数组一样, 可以用初始化值表, 如,
例如,struct student {
int num;
char name[20];
char sex;
int age;
float score;
char addr[20]
} s1 = {10000,“LiMing”,?M?,
19,88,“BeijingRoad”};
结构体数组,
定义方式和普通数组一样, 与普通数组不同的是, 结构数组中
的所有元素都是结构数据类型 。 例如：
struct student std[100]；
定义一个有 100个结构类型元素的结构数组
引用方式,数组元素,成员名 ；
如,std[0].no,std[1].name 等
数据在内存中的存放方式是一个元素接着一个元素连续存放
数组名是首地址
std
结构体数组适合处理由若干个具有相同属性的对象数据组成的
数据集合 。 用结构体数组处理数据时可以使用循环, 从而使程
序十分简炼 。
举例：对候选人得票的统计程序 。 设有三个候选人, 每次输入
一个得票候选人名字, 要求最后输出个人的得票数
6.5 结构类型
10001 Zhang San M 19 90.5 Shang Hai
10002 Wang Li F 20 87 Bei Jing
6.5 结构类型
#include <iostram.h>
struct person {
char name[10];
int count; //结构体数组初始化
} leader[3] = {{“Li”,0},{“Zhang”,0},{“Liu”,0}};
main()
{ int i,j;
char lead_name[10];
for(int i=0; i <= 10; i++) {
cin >> lead_name;
for(int j=0; j > 3; j++) {
if(strcmp(lead_name,leader[j].name) == 0)
leader[j].count ++;
}
}
for(i=0; i < 3; i ++)
cout <<,候选人：, << leader[i].name <<
“得票数：, << leader[i].count << endl;
}
6.5 结构类型
1 指向结构体类型数据的指针
2 结构体成员在内存中要占据一定的内存空间, 那么它肯定有起
始地址, 那么我们可以用指针指向这个地址来处理和引用结构
体成员数据
3 1,指向结构体变量的指针 ps
4 struct student stu_1
5 struct student *ps;
6 ps=&stu_1;
7 以下三种引用形式等价
8 stu_1.name (*ps).nmae ps->name
9 这里又多一种运算符, ->”,它跟,,”优先级都是最高的, 叫做
,指向运算符,, 格式为,结构体指针变量 ->成员变量名
p->age ++
++ p->age
假设 stu_1.age原始内容为 18,那么经过以上运算, 表达式
值和 age值分别是多少？
1000
Li Ming
6.5 结构类型
指向结构体数组的指针
跟数组一样, 我们知道数组名就是它们数据的首地址, 那
么结构体数组名一样是它所分配的数据内存首地址, 所以我们也
可以采用指针方式来处理结构体数组
struct student std[100],*p; p
p = std; p++;
指向结构体的指针作函数参数
与数组在函数间传递一样, 结构体传递给函数时,
一般采用地址传递方式, 即把结构体变量
（ 或数组 ） 的存储地址作为参数向函数传递,
函数中用指向相同结构体类型的指针接收该
地址值 。 然后, 在函数中通过这个结构体指针来
处理结构体变量 （ 或数组 ） 中的各项数据
fun(struct student *sp)
fun(std); { cout << sp->name;
}
1001
Li MIng
88.5
1002
Liu Hua
77.8
6.5 结构类型
指向结构变量的指针做函数返回值
在前面课中, 指针可以函数返回值, 那么结构体变量指针也
一样可以作为函数返回值
举例：输入四个学生的某门课成绩, 找出其中分数最高的学生,
并输出名字和分数
struct student {
int num; char name[20]; float score;
};
main()
{ struct student *max(),*ss;
struct student std[4];
for(int i = 0; i < 4; i ++)
cin << std[i].name << std[i].score;
ss = max(std,4);
cout >>,Name =, >> ss->name >>,Score =,
>> ss->score >> endl;
}
6.5 结构类型
struct student *max(struct student *pd,int n)
{ int i,t = 0,m; std
m = pd[0].score; pd
for(i = 1; i < n; i ++)
if(pd[i].score > m) {
m = pd[i].score;
t = i;
}
return(pd+t);
}
1001
Li MIng
88.5
1002
Liu Hua
77.8
Std[0]
Std[1]
Std[2]
6.6 共用体
共用体和结构有很多相似之处, 在定义的形式上和成员的
表示上都一样, 其区别在于结构是异址的, 而共用体是同址的,
就是说各个成员的地址是相同 。 即共用体的成员都是从同一地址
开始, 共用一段存储单元 。
定义形式：
union 共用体类型名 {
成员列表 ；
} 变量表列；
例如：
union data { 2000
int i; 2000
char ch; 2000
float f;
} a,b,c,*p;
i
Ch
f
6.6 共用体
定义共用体变量也有三种方法, 跟结构体变量定义一样
从成员变量的存储方式来看, 结构体所占的内存长度是全部成员
长度之和, 而共用体的内存长度则是最大成员的长度 。
共用体变量的引用, 跟结构体一样, 要用成员运算符,,”或指向运
算符, ->”,如,a.f b.ch p->i p->f 等等
那共用体相对结构体来说, 有何特点呢？
1,同一时间, 它只能存放一种成员的数据
2,起作用的成员也是最后一次存放的成员, 如：
a.i = 1;
a.c = ?a?;
a.f = 1.5
那么赋值后, 最后起作用的是 f成员, cout << a.i 打印出
来的数据是不可预料的
3,共用体的各成员起始地址都是同一地址, 所以
&a.i,&a.ch,&a.f 结果是一样的
6.6 共用体
举例：设计学校人员管理卡片的数据结构
我们知道一个学校主要有三类人员：
1 是学生, 2 是老师, 3 是行政干部
如果我们设计三个结构来表达这三类人员, 当然是可以的, 不过在以后
的数据处理和管理中, 就重复和累赘 。 因为每类人都有编号, 姓名, 年龄是相
同的, 而不同的是对学生来说要处理年级, 对老师来说要描述职称, 而对行政
干部来说, 要描述职务, 所以, 在数据的统一处理中, 我们可以采用共用体概
念进行描述数据 。
为了统一对数据进行管理, 我们对这三种人设计一个结构：
struct person {
long no;
char name[12];
int age;
char profession; // 如果 profession 为 0,表示该数据为学生数据,
1（ 老师 ） 2（ 行政干部 ）
union level {
int grade; // 对学生的年级
char rank[8]; // 对行政干部的职务
char title[10]; // 对老师的职称
} scl;
}
6.7 排序与查找
6.7.2 常用的排序法
6.7.1 常用查找方法
数据排序 （ sorting） 是最重要的计算应用之一。
例如查字典，字典中的词条是按序存放的，我们
才能按字母顺序找到要查的字。又如图书馆的藏
书也是按书的编号有序排列的。在计算机上数据
库里的资料也是有序排列的。
查找 （ search） 当然也是最常见的运算，就是
在数据集合中寻找满足条件的数据对象，找到后
进一步给出对象的具体信息，在数据库技术中称
为 检索 （ retrieval）。
6.7.1 常用查找方法
最简单的查找 —— 顺序查找,即从数组第一个元素开始，一个一个
顺序查下去直到找到或查到最后一个元素为止。
查找是按 关键字 （ key word）进行的，可以唯一地把资料区分出来
的数据被称为 主关键字 。如学生的资料，该资料是一个结构体变量；
struct student{
int id ; //学号
char name[20]; // 姓名
char sex; // 性别
int age; // 年龄
char address[60]; //家庭地址
float eng,phy,math,computer; //英语,物理,数学和计算机成绩
};
在这里 学号 可作为主关键字。
如果关键字小的排在前面，我们称为升序排列，反之为降序排列。这
时可以采用 对半查找（ binary search） 。
一般查找是对普通数据类型数组或结构体数组进行的
6.7.1 常用查找方法
下 图是描述对半查找是怎样进行的。这里是升序的有序表。
算法如下：
1、首先安排两个下标变量 low和 high指向首尾两元素
2、取 mid=(low+high)/2，如 mid指向元素是所查找的，则
结束。如果被查找的数比该元素关键字大，说明被查找的数在
后面，则取 low=mid +1,high不变，继续查找步骤 2；如果
被查找的数比该元素关键字小，说明被查找的数在前面，则取
high=mid-1,low不变，继续查找步骤 2。
3、如果查到 low>high仍未找到，则说明找不到该数，查找失
败，停止。
这里有一步 非常重要,就是 low=mid+1和 high=mid-1，
是在查找过程的范围越来越小，最终找到结果。
6.7.1 常用查找方法
2 5 7 8 11 13 179 19 20 2321 26 29 31 3710
查找 low
39
mid high
2 5 7 8 11 13 179
low mid high
11 13 179
low mid high
9
low mid high
查找失败例
low
8 9 171311 207 19 21 23 3126 292 5 37 3923
查找 low mid high
20 21 292623 31 37 39
mid highlow
20 21 23
mid hig
h23
low mid high 成功
查找成功例
6.7.1 常用查找方法
对半查找递归算法,// 6-7-1.cpp
#include <iostream.h>
#include <stdlib.h>
class BinSearch {
private:
double *Plist;
public:
BinSearch(double *list,int n)
{ Plist = new double[n];
for(int i=0; i < n; i ++) Plist[i] = list[i];
}
~BinSearch()
{ delete []Plist;
}
void BinFind(int,int,double);
};
6.7.1 常用查找方法
void BinFind(int low,int high,double x)
{ int mid = (low+high)/2;
if(Plist[mid] == x) {
cout <<,the position is:, << mid << endl;
return;
}
else if(low >= high) {
cout << x <<, is not found !” << endl;
return;
}
else if(x > Plist[i])
BinFind(low+1,high,x);
else
BinFind(low,high-1,x);
}
6.7.1 常用查找方法
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 low = 0,high = 9;
BinSearch bs(a,10);
bs.BinFind(low,high,x);
bs.BinFind(low,high,1.6);
}
那么程序的运行结果是,the position is,6
1.6 is not found !
6.7.1 常用查找方法
对半查找迭代算法：
void BinFind(int low,int high,double x)
{ int mid;
while(low<=high) {
mid=(low+high)/2;
if(Plist[mid] > x) high = mid-1; //左缩查找区间
else if(Plist[mid] < x) low=mid+1;//右缩查找区间
else return mid;
}
return -1;
}
该例中 迭代算法 的可读性也不差，效率要高于递归。
6.7.1 常用查找方法
散列 （ hash） 查找是最快的查找方法 。 前两种
查找方法都是将查找关键字与表中的数据元素的值
直接进行比较而达到查找目的的 。 如果能找到一个
函数 f(key),将关键字经过函数的运算转换为数据
表中的位置, 直接将数据元素插入在该位置上 。 在
查找中直接用该位置的数据元素与关键字值比较,
以确定是否查到所要的数据元素 。 这样的组织称为
散列, 利用散列技术查找的方法称为散列查找, 散
列查找是一种直接查找 。 亦用音译称 哈希查找 。
6.7.2 常用的排序法
排序（ sorting） 是数据处理中经常使用的一种重要运算。
其功能是将数据元素的无序序列调整为一个有序序列。数据元
素中一般有多个数据项，排序可选择其中一个可排序的数据项
（可进行比较运算）作为依据，称为 排序关键字 。比如我们对
高考考生的统计表进行排序，可根据考生的准考证号，这样的
关键字可以 保证排序结果的唯一性，称主关键字 。但为了便于
录取，我们也可以按高考总分排序，只可称 关键字,这样同一
分数的人很多，这些人的排名可再取一个 次关键字 如数学或语
文分来排序，以减少重复排名的随意性。从小到大排序称升序，
反之为降序。
最常见的三类是插入排序、选择排序和交换排序，下面介
绍三类排序中最基本的方法。
6.7.2 常用的排序法
1,插入排序 (Insert Sorting)
(1)直接插入排序 的思想是,(以升序为例 )当插入第 i(i>=1)个元素 sl[i]时,前
面的元素 sl[0],sl[1],…,sl[i -1]已经排好序,我们将 sl[i]的关键字与 sl[i-1],
sl[i-2],…,的关键码顺序进行比较,找到第一个比它小的,则 sl[i]插到该元素
之后。那么怎么保证前面的元素排好序呢?可以从第一号元素开始，前面只
有第 0号元素,这 一个元素肯定是排好序的 ！参见下图。
i 0 1 2 3 4 5 6 temp
初始序列 [8] 6 7 9 4 5 2 6
1 [6 8] 7 9 4 5 2 7
2 [6 7 8] 9 4 5 2 9
3 [6 7 8 9] 4 5 2 4
4 [4 6 7 8 9] 5 2 5
5 [4 5 6 7 8 9] 2 2
6 [2 4 5 6 7 8 9]
直接插入排序算法中用了一个临时变量 temp，要插入的元
素放到 temp中，这样插入前各元素后移时允许将该元素冲
掉。
6.7.2 常用的排序法
升序直接插入排序算法,// 6-7-2.cpp
void InsertSort(int slist[],int n)
{ int temp;
int i,j;
for (i=1; i < n; i++) {
temp = slist[i];
j=i;
while (j>0 && temp < slist[j-1]) {
slist[j]=slist[j-1];
j--;
} //查找与移动同时做
slist[j] = temp;
}
}
void main()
{ int a[] = {8,6,7,9,4,5,2};
InsertSort(a,7); cout <<,排序后的数据是：” ;
for(int i=0; i < 7; i ++) cout << a[i] <<,,”;
cout << endl;
}
6.7.2 常用的排序法
从下往上扫描的冒泡程序
2．交换排序
交换排序的基本思想是按关键字两两排
序对象，如果发生逆序则交换之，直到
所有的对象都排好序为止。这里介绍 冒
泡排序（ Bubble Sort） 。
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49’ 49’ 49’ 49’ 49’
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49’ 49’ 49’ 76 97 97 97 97
冒泡排序基本思想 参见
右。最左列为最初的情
况，最右列为完成后的
情况。首先我们从一列
数据底部开始，相邻的
两数据进行比较，小的
数放上面，一趟比较下
来，最小的数据冒到了
最上面。再缩小区域，
按同样方法继续下一趟
交换，如果有一趟比较
中没有 发生交换，则已
排好序 。图中，第 5列就
已排好序，若再继续下
一趟就不会发生交换。
6.7.2 常用的排序法
冒泡排序算法：
void BubbleSort(int slist[],int n) {
bool noswap;
int i,j;
int temp;
for (i=0; i<last; i++){ //最多做 n-1趟
noswap=true; //未交换标志为真
for(j=n-1; j>i; j--) { //从下往上冒泡
if(slist[j] < slist[j-1]) {
temp = slist[j];
slist[j] = slist[j-1];
slist[j-1] = temp;
noswap = false;
}
}
if(noswap) break; //本趟无交换，则终止算法
}
}
6.7.2 常用的排序法
3．选择排序
选择排序（ Selection Sort） 的基本思想是：每一趟从待排序
的记录中选出关键字最小的元素，顺序放在已排好序的子序列的后
面，直到全部记录排序完成。直接选择排序（ Straight Selection
Sort）是最简单的，参见下图。此方法的最大优点是非常 易读 。
[49 38 65 97 76 13 27 49’]
13 [38 65 97 76 49 27 49’]
13 27 [65 97 76 49 38 49’]
13 27 38 [97 76 49 65 49’]
13 27 38 49 [76 97 65 49’]
13 27 38 49 49’ [97 65 76]
13 27 38 49 49’ 65 [97 76]
13 27 38 49 49’ 65 76 97
直接选择排序的过程
6.7.2 常用的排序法
选择排序：
void SelectSort(int slist[],int n) {
int i,j,k;
int temp;
for (i=0; i<n-1; i++){
k = i;
for(j=i+1; j<n; j++)
if(slist[j] < slist[k]) k = j;
if(k != i) {
temp = slist[i];
slist[i] = slist[k];
slist[k] = temp;
}
}
}
例题：
// 6-7-all.cpp
编写一个程序：将用户输入的由数字字符和非数字
字符组成的字符串中的整数提取出来，存放在数组
a 中，例如输入,asd764rt143,fg6746 则产生数字
764,143,6746
