当前位置:首页 >> 理学 >> c++程序设计谭浩强第5章2013修订

c++程序设计谭浩强第5章2013修订


第五章 数



5.1 数组的概念(P128)
在解决实际问题时,往往会需要 处理一批具有相同的数

据类型并且关系密切的变量。
例如:对一个班的学生成绩进行处理,计算其个人平均成绩、学科平均 成绩,个人名次排序等。

数组是具有一定顺序关系的若干变量的集合 体,组成数组的变量成为该数组的元素变量,简称 元素。
在 C++中, 数组的元素变量用数组名后面跟上带有方括号[ ]的下标表示。

如:a[10],data[20],s[30],b[5][6];
其中带有一个方括号的称为一维数组,带有两个以上方括号的称为二维数 组、三维数组等,统称为多维数组。方括号中的下标用来表示元素在数组中的 位臵。

数组在内存中连续分配一片存储单元
见 P128 图 5.1

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

2000

2002

2004

2006

2008

2010

2012

2014

134

5.2 一维数组的定义和引用
一、一维数组的定义 1.一维数组的定义格式: 类型标识符 数组名 [ 常量表达式 ] 例如: int data[20]
表明定义了一个名字叫 data,长度为 20 的整型一维数组,即该 数组有 20 个整数类型的元素,可以用来存储 20 个整数类型的数据。

2.说明:
①数组名的命名应符合标识符的命名规则; ②数组名后面方括号内的数据是数组的长度,也即是数组元素的 个数,它可以是常量,也可以是常量表达式,但必须是整型。不能是 变量或变量表达式(即不允许作动态定义) 。 ③C 编译系统为数组分配连续的存储单元,数组元素的相对次序 由其下标来表示。下标从 0 开始。

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

一般的,含有 n 个元素的数组,其下标范围实 0 -(n-1) ④相同类型的数组,可以放在一个说明行中,数组之间用逗号分 隔。

二、一维数组的初始化 例如: 说明: int s[5]={ 0,1,2,3,4 }

①将数组元素的初值放在一对花括号中,所赋初值的类型必须与 定义数组的类型一致,各个初值之间用逗号分隔;系统将按初值的顺 序,顺次给数组元素赋值;
135

②所赋初值的个数不能超过数组元素的个数 (数组的长度) 但可 , 以少于数组元素的个数,此时相当于给数组的前一部分元素赋值,而 后面的元素由系统自动地赋值为 0;

例如: int a[5]={1,2,3} 相当于:a[0]=1,a[1]=2,a[2]=3,a[3]=0,a[4]=0, 注: 若需要将数组全部元素初始化为 0 值, 可以用如下形式实现: int a[10]={0};
问:int a[10]={1}; 其初始化值为? ③若给数组的所有元素赋初值,可以省略数组的长度,

例如: int ar[ ]={ 3,2,4,6,8} 相当于: int ar[5]={3,2,4,6,8}
④若在数组定义之后,再初始化数组,则不能成组赋值,只能一 次给一个元素赋值。

例如: int w[4]; w[4]={23,2,34,5}
是错误的赋值方式。

三、一维数组的引用
数组必须先定义,然后再使用。C++规定,数组整体不能参加数据处理,即 不能向数组整体赋值,数组作为一个整体也不能参加各种运算 ,参加数据

处理和运算的只能是数组元素。 数组元素的表示形式为: 数组名 [下标]
其中,下标可以是整数类型的常量、变量或表达式。

例 5.1 输入 10 个整数,并按其逆序输出。 #include <iostream> using namespace std;
136

int main() { int i,a[10]; for (i=0;i<10;i++) { cout<<"please input ―<< i+1<<‖data:"; cin>>a[i]; } for (i=9;i>=0;i--) cout<<a[i]<<‖ ―; cout<<endl; return 0; } 例 5.2 编写程序,输入 10 个整数,求出其中的最 大值与最小值并输出。 #include <iostream> using namespace std; int main() { int x[10], i, max, min; cout<<"please enter"; for(i=0;i<10;i++) cin>x[i]; max=min=x[0]; for(i=1;i<10;i++) { if(x[i]>max) max=x[i];
137

if(x[i]<min)

min=x[i];

} cout<<"max=‖<<max<<endl; cout<<‖min="<<min<<endl; return 0; }
说明:
①一个数组元素就是一个变量,他的使用规则与同类型的普通变量相同。 ②定义数组时数组名后面的方括号中的内容和引用数组元素时数组名后面的方 括号中的内容的含义是不同的,前者是数组的长度,而后者是元素的下标。 ③在 C 程序运行时,编译系统不检查数组元素的下标是否越界,若下标越界, 可能会发生严重的后果。

例 5.3 编写程序,输入 10 个整数,计算其平均值并输出其中
高于平均值的数据。

#include <iostream> using namespace std; int main() { int x[10], i, aver , sum=0; cout<<"please enter numbers"; for(i=0;i<10;i++) { cin>>x[i]; sum=sum+x[i]; } aver=sum/10;
138

cout<<"aver="<<aver; for(i=0;i<10;i++) if(x[i]>=aver) cout<<i<<‖ ―<<x[i]<<endl; return 0; } 例 5.4 用数组求解 Fibonacci 数列问题 #include <iostream> #include <iomanip> using namespace std; int main() { int i; int f[20]={1,1}; for(i=2;i<20;i++) f[i]=f[i-2]+f[i-1]; for(i=0;i<20;i++) { if(i%5==0) cout<<endl; cout<<setw(8)<<f[i]; } cout<<endl; return 0;
}
139

例 5. 在一次选举中, 5 有五位候选人, 分别由 1~ 5 编号,请编程序统计出各位候选人的得票数并找 出得票数第一名的编号。
问题分析: 程序的一次运行情况如下: 请输入候选人的编号(-1 表示结束): 1 2 3 4 5 1 1 2 3 4 5 4 3 4 3 1 1 1 5 -1

#include<iostream> #include<iomanip> using namespace std; int main() { int a[6]={0},x,max,k,k1; cout<<"请输入候选人的编号(-1 表示结束)"; cin>>x; while(x>0&&x<6) { a[x]=a[x]+1; cin>>x; } max=a[1],k1=1; for(k=2;k<6;k++) if(a[k]>max) max=a[k],k1=k;
140

for(k=1;k<6;k++) cout<<setw(5)<<a[k];
cout<<"\n 票数最高的候选人编号是:"<<k1<<" 号。\n"; }

例 5.6 用数组存放一组统计数据,然后用―*‖表示的条形图
输出这组数据。程序输出效果如下所示: Element 1 2 3 4 5 #include<iostream> #define ArrSize 5 using namespace std; Value 11 3 7 10 20 Striation *********** *** ******* ********** ********************

void main() { int k,m,arr[ArrSize]={11,3,7,10,20}; cout<<"Element\tValue\t Striation\n"; for(k=0;k<ArrSize;k++)
//外层循环按照数组元素的个数控制输出行数

{ cout<<k+1<<"\t"<<arr[k]<<"\t "; for(m=0;m<arr[k];m++) //内层循环按照每一数组元素值输出指定的星号个数 cout<<"*";
141

cout<<"\n"; } }

5.3 二维数组的定义和引用(P132)
一、二维数组的定义 1.二维数组引入的意义 平面坐标 、二维表格、矩阵 2. 二维数组定义的一般形式
类型说明符 数组名 [常量表达式][ 常量表达式];

例如: 说明:

float a[3][4],s[5][10];

①在 C++中,二维数组中元素在内存中的排列顺序是:

按行存放。 a[0][0],a[0][1],a[0][2],a[0][3],a[1][0],a[1][1],a[1][2], ……
②二维数组中,数组名的命名、数据类型的定义方式、数组长度与类型的选取 与一维数组相同; ③数组元素的个数就是两维长度之积;

二、二维数组的初始化(P134~135)
142

1.分行给二维数组赋初值

例如:
初值。

int a[2][3]={{1,2,3},{4,5,6}};

2.将所有数据写在一个花括号内,按数组排列顺序对各元素赋

例如: 例如

int a[2][3]={1,2,3,4,5,6}; c[4][4]={{1,2,3,4},{4,5,6},{7,8}};

3.部分元素赋初值,则剩余的元素自动赋初值为 0;

4.如果对全部元素都赋初值,则可省略数组第一维的长度,但 应分行赋初值。

例如:

int a[][3]={{1,2,3},{},{4}};

此时,编译系统会根据赋初值的情况,自动得到第一维的长度,上例,编译系 统分析出第一维的长度为 3。 注意:若是在定义二维数组后,再给其元素赋值,则需要逐个赋值,不能成组 赋值。

三、二维数组元素的引用
二维数组元素的引用方式:

数组名[下标 1] [下标 2] 例如: int a[6][3]; 合法引用: a[0][2], a[3][0], a[2+3][1], a[i][j] 不合法引用: a[2][3], a[1.2][2], a[6][0]

(其中,i,j 为整型变量)

说明: ①二维数组的下标范围和一维数组类似,可以是整型的变量、常量、表达式。 ②二维数组元素的表示方式不能写成 b[1, 2]等, 并且两个下标之间不能有空格。
143

四、二维数组应用举例 例 5.7 通过键盘给 2*3 的数组输入数据。 第一行:1,2,3。 第二行:10,20,30。 然后按行输出此二维数组。 #include <iostream> using namespace std; int main() { int a[2][3], i, j; cout<<―enter data by line :‖<<endl; for(i=0;i<2;i++) for(j=0;j<3;j++) cin>>a[i][j]; cout<<―output a-arraydata :‖<<endl; for(i=0;i<2;i++) { for(j=0;j<3;j++) cout<<a[i][j]; cout<<endl; } return 0;

}
144

例 5.8 有一个 3*4 矩阵,编一程序求全部元素的平 均值。并把高出平均值的元素的值以及他们所在的 行号和列号打印出来。 69 88 90 50 70 82 96 100 60 92 2 66 #include <iostream> using namespace std; int main() {
int arr[3][4]={{69,88,90,50},{70,82,96,100},{60,90,2,66}};

int i,j; float aver,sum=0; for(i=0;i<3;i++) for(j=0;j<4;j++) sum=sum+arr[i][j]; aver=sum/(3*4); cout<<"aver="<<aver<<endl; cout<<"value row column:"<<endl; for(i=0;i<3;i++) for(j=0;j<4;j++)
145

if(arr[i][j]>aver) cout<<arr[i][j]<<‖,‖<<i<<‖,‖<<j<<endl; return 0; } 例 5.9 有一个 3*4 的矩阵,求出其中值最大的那个 元素的值及其所在行号和列号。 1 2 3 4 9 8 7 6 -10 10 –5 2 #include <iostream> using namespace std; int main() { int i,j,row=0,colum=0,max; int a[3][4]={{1,2,3,4},{9,8,7,6},{-10,10,-5,2}}; max=a[0][0]; for(i=0;i<=2;i++) for(j=0;j<=3;j++) if(a[i][j]>max) { max=a[i][j]; row=i;
146

colum=j; } cout<<"max=‖<<max<<endl; cout<<"row=‖<<row<<endl; cout<<"colum=‖<<colum<<endl; return 0; } 例 5.10 在二维数组 a[3][4]中依次选出各行最大元 素值存入一维数组 b[3]对应元素中。 程序运行结果: array a: 3 16 87 65 4 32 11 108 10 25 12 27 array b: 87 108 27 #include <iostream> #include<iomanip> using namespace std; void main() { int a[][4]={3,16,87,65,4,32,11,108,10,25,12,27};
147

int b[3],i,j,max; for(i=0;i<=2;i++) { max =a[i][0]; //以下程序段求出i中的最大元素值 for(j=1;j<=3;j++) if(a[i][j]>max) max =a[i][j]; b[i]= max; //i中的最大元素值存入b的i号元素 } cout<<"array a:\n"; for(i=0;i<=2;i++) //按照矩阵的形式输出数组a的元素值 { for(j=0;j<=3;j++) cout<<setw(5)<<a[i][j]; cout<<"\n"; } cout<<"\narray b:\n"; for(i=0;i<=2;i++) //依次输出矩阵a中每行的最大元素值 cout<<setw(5)<<b[i]; cout<<endl; }

例 5.11 某班有 6 个学生,每个学生有 5 门成绩。编
148

一程序,统计每个学生的平均成绩和每门课的平均 成绩。
学生序号 语文成绩 数学成绩 英语成绩 物理成绩 化学成绩

1 2 3 4 5 6

68 88 60 65 80 90

89 99 68 68 65 98

78 77 65 80 56 67

98 80 40 90 70 85

90 86 50 78 88 74

问题分析:定义数组: score[6][5]用于存放学生各课的成绩; saver[6] 用于存放每个学生的平均成绩; taver[5] 用于存放每课的平均成绩; #include <iostream> #include <iomanip> using namespace std; int main() { int score[6][5]={{68,89,78,98,90}, {87,99,77,80,86},
149

{60,68,65,40,50}, {65,68,80,90,78}, {80,65,56,70,88}, {90,60,67,85,74}}; int saver[6],taver[5]; int i,j,sum; for(i=0;i<6;i++) { sum=0; for(j=0;j<5;j++) sum=sum+score[i][j]; saver[i]=sum/5; } for(j=0;j<5;j++) { sum=0; for(i=0;i<6;i++) sum=sum+score[i][j]; taver[j]=sum/6; } cout<<endl;
cout<<"No. chinese math english physics chemistry aver"<<endl;

for(i=0;i<6;i++) { cout<<setw(3)<<i+1; for(j=0;j<5;j++)
150

cout<<setw(8)<<score[i][j]; cout<<setw(8)<<saver[i]<<endl; } cout<<" aver"; for(j=0;j<5;j++) cout<<setw(7)<<taver[j]; cout<<endl; return 0; } 例 5.12 输出以下的扬辉三角形 (要求打印出 10 行)

说明:为了简化对应关系(避免使用 0 号元素对应第一个数据)使用了一个 11 个元素的数组进行处理。

#include <iostream> #include <iomanip> using namespace std;
151

int main() { int i, j, a[11][11]; for(i=1;i<11;i++) { a[i][i]=1; a[i][1]=1; } for(i=3;i<11;i++) for(j=2;j<=i-1;j++) a[i][j]=a[i-1][j-1]+a[i-1][j]; for(i=1;i<11;i++) { for(j=1;j<=i;j++) cout<<setw(6)<<a[i][j]; cout<<endl; } cout<<endl; return 0;

}

5.4 数组的简单应用
一、 数组元素值的随机生成
为了能够在学习程序设计的过程中深刻体会被处理数据的多样性和不 可预见性,有必要用某种方法来模拟所处理的数据。让计算机自动生成

?随机数?就是一种比较好的模拟数据方法。
152

为了能够在程序中产生随机生成的数据,需要使用 C 语言提供的 srand、rand 和 time 等 3 个标准库函数。

1.

srand 函数
其功能是初始化随机数发生器,函数原型在头文件

stdlib.h



声明,其原型为:

2.

void srand( unsigned int seed ); rand 函数
其功能是随机产生一个在 0 到 RAND_MAX(0x7fff)之间的一个正整数,

函数的原型在头文件 stdlib.h 中声明如下所示:

int rand( void ); 3. time 函数
其功能是获取系统时间,函数原型在头文件 time.h 中声明,其原 型为:

time_t time( time_t

*timer );

其中的数据类型 time_t 是一个系统定义好的一个长整型数据类型, 其变量用于存放从系统中取出的以秒为单位的整型数据,参数 time_t *timer 表示用 timer 数据对象保存取出的时间值,调用时用空(NULL) 作为参数(即调用形式为:time(NULL))则表示只需要用其返回的长整数 值而不需要保存该值。 下面通过两个示例讨论随机生成一维数组和二维数组元素值的问题。

例 5.13 随机生成 20 个 3 位以内的整数序列存放在 一维数组中, 然后按每行 5 个数输出所有数组元素。
153

(注:程序每次运行产生不同的随机数) #include<iostream> #include< iomanip > #include <cstdlib> #include <cstdio> #include <ctime> #define N 20 using namespace std; double AverageRandom(double min,double max); int main() { int i,arr[N]; srand((unsigned) time(NULL)); //初始化随机数发生器 for(i=0;i<N;i++) //按要求生成随机数放入数组 arr[i]=(rand())%1000; arr[i]=(int)AverageRandom(100,999); for(i=0;i<N;i++) //按要输出所有随机产生的数组元素值 { if(i%5==0) cout<<"\n"; cout<<setw(6)<<arr[i]; } cout<<"\n"; }

154

double AverageRandom(double min,double max) {
int minInteger = (int)(min*10000); int maxInteger = (int)(max*10000); int randInteger = rand()*rand(); int diffInteger = maxInteger - minInteger; int resultInteger = randInteger % diffInteger + minInteger; return resultInteger/10000.0;

} 例 5.14 编程序实现如图 3.10 所示的矩阵转置功 能,即将 N×M 矩阵转换为 M×N 矩阵。
(要求被处理的二维数组元素值(2 位数以内)随机产生)

#include<iostream> #include< iomanip > #include <cstdlib> #include <ctime> #define M 2
155

#define N 3 using namespace std; void main() { int a1[M][N],a2[N][M],i,j; srand(time(NULL)); for(i=0;i<M;i++) for(j=0;j<N;j++) a1[i][j]=rand()%100; cout<<"Array a1:\n"; for(i=0;i<M;i++) { for(j=0;j<N;j++) cout<<setw(4)<<a1[i][j]; cout<<"\n"; } for(i=0;i<M;i++) for(j=0;j<N;j++) a2[j][i]=a1[i][j]; cout<<"Array changed a2:\n";
156

//初始化随机数发生器

//随机产生数组 a1 的所有元素值

//按照矩阵的形式输出数组 a1

//依次交换所有元素的行列下标

for(i=0;i<N;i++) {

//按照矩阵的形式输出数组 a2

for(j=0;j<M;j++) cout<<setw(4)<<a2[i][j]; cout<<"\n";

} } 二、数组的常用排序方法
排序是用计算机处理数据的一种常见的重要操作,其作用是将数组中 的数据按照特定顺序, 如升序或降序重新排列组织。 针对不同的实际应用, 数据排序方法有很多种。

1. 排序的基本方法一:选择排序法(如:升序) 基本思想:
对于待排的 n 个数据, 在其中寻找最大 (或最小) 的数值, 并将其移动到的最前面作为其第一个数据; 在剩下的 N-1 个数 据中用相同的方法寻找最大(或最小)的数值,并将其作为第 二个数据; 以此类推, 直到将整个待排数据集合处理完为止 (只 剩下一个待处理数据) 。

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
第一步:寻找最小值,并且将其存放在 a[0]中;
将 a[0] 分别与 a[1], a[2], a[3]…………..a[9] 比较

for(j=1;j<10;j++)
157

if(a[0]>a[j]) { temp=a[0]; a[0]=a[j]; a[j]=temp ;
将 a[1] 分别与 a[2], a[3], a[4]…………..a[9] 比较

}

第二步:在剩余的 9 个数中寻找最小值,并且将其存放在 a[1]中;

for(j=2;j<10;j++)
if(a[1]>a[j]) { temp=a[1]; a[1]=a[j]; a[j]=temp ; }

。。。。 。。。。
例 5.15:

#include <iostream> using namespace std; int main() { int a[10]; int i, j, temp; for(i=0;i<10;i++) { cout<<"input the ―<< i+1<<‖ data :"; cin>>a[i]; } cout<<"the array is :"<<endl; for(i=0;i<10;i++) cout<<a[i]<<‖ ―; cout<<endl; for(i=0;i<9;i++) for(j=i+1;j<10;j++)
if(a[i]>a[j]) { temp=a[i];a[i]=a[j];a[j]=temp;}
158

cout<<"the sorted array is :"<<endl; for(i=0;i<10;i++) cout<<a[i]<<‖ ―; cout<<endl; return 0; } 2 排序的基本方法一的改进:比较选择交换排序法
说明:该方法与上一种方法比较,减少了交换的次数(注意:比较次数没有减少)

基本方法是: ⑴在所有的记录中选取关键字值最大(或最小)的记录,并将 其与第一个记录交换位置。 ⑵将上次操作完成后剩下的记录中构成一个新处理数据集。 ⑶在新处理数据集的所有记录中选取关键字值最大(或最小) 的记录,并将其与新处理数据集中第一个记录交换位置。 ⑷如果还有待处理记录,转到⑵。

例 5.16 #include<stdio.h> void main() { int a[10], temp, k; int i ,j; for(i=0;i<10;i++) { cout<<"input the ―<< i+1<<‖ data :"; cin>>a[i];
159

} cout<<"the array is :"<<endl; for(i=0;i<10;i++) cout<<a[i]<<‖ ―; cout<<endl; for(i=0;i<9;i++) { k=i; for(j=i+1;j<10;j++) if(a[k]>a[j]) k=j; { temp=a[i]; a[i]=a[k]; a[k]=temp; } cout<<"the sorted array is :"<<endl; for(i=0;i<10;i++) cout<<a[i]<<‖ ―; cout<<endl; return 0; }

}

例 5.17 进一步改进:对随机生成的 20 个整数按升序进行排 序并输出。

#include<iostream> #include< iomanip > #include <cstdlib>
160

#include <ctime> #define N 20 using namespace std; void main() { int temp,i,j,k,a[N]; srand((unsigned) time(NULL)); cout<<"Before sorting ... \n"; for(i=0;i<N;i++) //随机产生并输出未排序数组元素 cout<<setw(8)<<( a[i]=rand()%1000); for (i=0; i<N; i++) //本循环实现选择排序算法 { k=i; for(j=i+1;j<N;j++) //在剩余的排序数据中寻找最小数的位置 if(a[j]<a[k]) k=j; if(k!=i) //将找到的最小数交换到指定的位置上 temp=a[i],a[i]=a[k],a[k]=temp; } cout<<"\n After sorting ... \n"; for(i=0; i<N; i++) //输出排序后的所有数组元素值 cout<<setw(8)<<a[i]; cout<<endl; }
161

3. 排序的基本方法二:冒泡(起泡)排序 基本思想: 将相邻的两个数 a[0]和 a[1]比较,按要求将这两个数排好序,
再将 a[1]和 a[2]比较。。。依次处理,直到将最后两个相邻的数比较并处理完 。。 毕。这时最大的数已换到最后一个数了,这是第一轮的比较和处理。每进行一 轮,把剩下的数中最大的一个移到最后位臵。共进行若干轮。直至最大的数?沉 底? ,最小的数?上浮? (注:n 个记录的排序最多进行 n-1 趟) 。 。

例 5.18 #include <iostream> using namespace std; int main() { int a[10], i, j, temp;

cout<<"input 10 numbers :"<<endl; for (i=0;i<10;i++) cin>>a[i]; cout<<endl;

for (j=0;j<9;j++) for(i=0;i<9-j;i++) if (a[i]>a[i+1]) { temp=a[i];a[i]=a[i+1];a[i+1]=temp; }
162

cout<<"the sorted numbers :"<<endl; for(i=0;i<10;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
排序的基本方法二:冒泡(起泡)排序

例 5.19 进一步改进:对随机生成的 20 个整数按 升序进行排序并输出。
引用变量 flag 作为标志,每一趟排序开始时将其设臵为 0,当本趟排序过 程中有数据交换时将 flag 设臵为 1,表示数据还没有排序完成;当本趟排序过 程中没有一次数据交换时,flag 保持为 0 值,表示被排序的数据已经完全满足 排序的要求,没有必要再继续进行以后的排序过程,程序中用 break 语句退出 排序循环。

#include<iostream> #include< iomanip > #include <cstdlib> #include <ctime> #define N 20 using namespace std;
163

void main() { int temp,flag,i,j,a[N]; srand((unsigned) time(NULL)); cout<<"Before sorting ... \n"; for(i=0;i<N;i++)
//随机产生并输出未排序数组元素

cout<<setw(8)<<(a[i]=rand()%1000); for (i=0;i<N; i++) //本循环实现冒泡排序算法 { flag=0; for (j=0;j<N-i;j++) { if(a[j]<a[j-1] ) { temp=a[j],a[j]=a[j-1],a[j-1]=temp; flag=1; } } if(flag==0) break; }
164

//flag 值为 0 时表示本趟没有交换,排序已经完成

cout<<"\n After sorting ... \n"; for(i=0; i<N; i++) cout<<setw(8)<<a[i]; } 三、数组的常用查找方法
查找也称为检索,其基本概念就是在一个记录的集合中找出符合某种 条件的记录。查找的结果有两种:在表中如果找到了与给定的关键字值相 符合的记录,称为成功的查找,根据需要可以获取所找记录的数据信息或 给出记录的位臵。若在表中找不到与给定关键字值相符合的记录,则称为 不成功的查找,给出提示信息或空位臵指针。
//输出排序后的所有数组元素值

1.顺序查找
顺序查找又称为线性查找。其基本过程是:从待查表中的第一个记录 开始,将给定的关键字值与表中每一个记录的关键字值逐个进行比较。如 果找到相符合的记录时,查找成功,如果查找到标得末端都未找到相符合 的记录时,查找失败。顺序查找法适应于被查找集合无序的场合。

例 5. 编程序实现顺序查找算法, 20 在随机生成的 20 个整数中查找指定值, 要求程序能够显示出查找 进行比较的次数以及本次查找成功与否。 程序的一次运行结果为: 请输入被查找的整数值: 43 被查找数据集合如下...
165

15 5 70 43 64 17 10 58 96 39 51 5 51 67 0 49 12 12 查找'43'成功,共进行了 4 次比较。 #include<iostream> #include< iomanip > #include <cstdlib> #include <ctime> #define N 20 using namespace std; void main() { int n,key,a[N],flag=0; srand((unsigned) time(NULL)); for(n=0;n<N;n++) //随机产生被查找的数据集合 a[n]=rand()%100; cout<<"请输入被查找的整数值: "; cin>>key; cout<<"被查找数据集合如下... \n"; for(n=0;n<N;n++) cout<<setw(8)<<a[n]; for(n=0;n<N;n++) //在数据集合中寻找与 key 相同的第一个数
166

4 56

if(a[n]==key) { flag=1; break; } if(flag) else

//如果找到则设置查找成功标志并结束查找工作

cout<<"查找‖<< key <<‖成功,共进行了‖<< n+1<<‖次比较.\n";

cout<<"数据集合中不存在被查找数据,共进行了‖<<n+1<<‖次比较\n";

} 2.折半查找。
折半查找法又称为二分查找法, 该算法要求在一个对查找 关键字而言有序的数据序列上进行. 基本思想是:逐步缩小查找目标可能存在的范围,具体描 述如下:
⑴选取表中中间位臵的记录作为基准,将表分为两个子表。 ⑵当基准记录的关键字值与查找的关键字值相符合时,返回基准记录 位臵,算法结束。 ⑶当基准记录的关键字值与查找的关键字值不符合时,在处理的两个 子表中选取一个子表,重复执行⑴、⑵,直到被处理的子表中没有记 录为止。
图 3.11 示意的是在一有序序列中实现对 key=21 进行折半查找的过程。
167

例 5.21 编程序实现折半查找算法,在随机生成的 20 个整数中查找指定值, 要求程序能够显示出查找 进行比较的次数以及本次查找成功与否。
程序中首先输出随机产生、未经排序的查找数据集合,执行结果中用 数组元素形式显示出来的是排序后与查找关键字 key 值相同的元素。

#include<iostream> #include< iomanip > #include <cstdlib> #include <ctime> #define N 20 using namespace std;

void main() { int i,j,k,temp,a[N],key,flag=0,count=0; int low=0,high=N-1,middle; srand((unsigned) time(NULL));
168

//随机数初始化

for(i=0;i<N;i++) a[i]=rand()%100; cout<<"下面是未排序的查找数据集合...\n "; for(i=0;i<N;i++) cout<<setw(7)<<a[i]; cout<<"\n 请输入被查找的关键字值: "; cin>>key; for (i=0; i<N; i++) { k=i; for(j=i+1;j<N;j++) if(a[j]<a[k]) if(k!=i) temp=a[i],a[i]=a[k],a[k]=temp; } while(low<=high)
//本循环实现折半查找算法 //本循环实现选择排序算法

k=j;

{ middle=(low+high)/2; count++; if(key==a[middle])
169

{ flag=1; break; } else if(key> a[middle]) low=middle+1; else high=middle-1; } if(flag)
cout<<"查找 a[―<<middle<<‖]成功,共进行了‖<<count<<‖次比较.\n";

else
cout<<"数据集合中不存在被查找数据,共进行了‖<<count<<‖次比较.\n";

}

170

5.5 字符数组(P141) 一、字符数组的定义和初始化 所谓字符数组是指数组元素为字符型的数组, 每个数组元素存放一个字符。
注:字符数组的定义、引用、初始化方式和普通数组类似。

一维字符数组的定义形式为: char 数组名[数组长度]; 例如: char arrc[10];
表示定义了一个长度为 10(数组元素为 10 个)的一维字符数组。

说明:
①字符数组的引用也是通过数组名和下标来表示的。 如: arrc[0]=‘I‘;arrc[1]=‘ ?;arrc[2]=‘a‘;arrc[3]=‘m‘; arrc[4]=‘ ?;arrc[5]=‘h‘;arrc[6]=‘a‘;arrc[7]=‘p‘; arrc[8]=‘p‘;arrc[9]=‘y‘; ②字符数组的初始化方式与其他数组一样, 可以在定义时初始 化,也可以在定义之后,逐个给数组元素赋值,数组元素被赋 的值应是字符型常量或变量。

如:上例可改为: char arrc[10]={?I‘,‘ ?, ‘a‘,‘m‘,‘ ‘,‘h‘,‘a‘,‘p‘,‘p‘,‘y‘};
同样,如果花括号中提供的初值个数(即字符的个数)大于数组的长度,则按语法错误 处理,如果初值个数小于数组长度,则只将这些字符赋给数组中前面的元素,而其余的元素
171

自动赋值为空字符(即‘\0’;如果提供的初值个数恰与预定的数组长度相同,则在定义时 ) 可以省略数组长度,系统回自动根据初值的个数确定数组长度。

二、字符数组的赋值与引用
与普通数组一样,只能对单个字符数组元素进行赋值,而不能用赋值语句对整个字符数 组进行赋值。

例 5. 从键盘输入一行字符, 22 存放在字符数组中, 然后逆序输出。 #include <iostream> using namespace std; void main() { char a[80],c; int k=0,j; cout<<"\nplease input the chars:"<<endl; cin>>c; while(c!='\n') { a[k++]=c; cin>>c; } for(j=k-1;j>=0;j--) cout<<a[j]; cout<<endl;
172

}

三、字符串和字符串结束标志(P143)
字符串即是一连串的字符,在 C 中,字符串常量是用加双引号的形式表示。

将字符串是作为一个 整体对待的数列,存放在字符数组中。 需要注意的是: 无论是在内存中存储字符串常量, 还是用字符数组存储字符串,编译 系统在处理字符串时,都会自动在字符串的最后一 个字符之后加上‘\0’作为结束标志。也即是对于含有 n 个
在 C 中,实际上没有字符串这种数据类型,而是 字符的字符串在内存中占 n+1 个字节的存储空间(其中;第 n+1 个字节用来存放字符串结束 标志‘\0’ )

例如: “” 表示空串,在内存中占 1 个字节,存放空字符‘\0’ ; “a” 表示含有一个字母 a 的字符串, 在内存中占 2 个字节 (即字母 a 和空字符 ‘\0’; ) ‘a’ 表示字符 a,在内存中占 1 个字节;
四、通过赋初值的方式给一维字符数组赋字符串常量 1.定义字符数组的同时,用字符串常量对字符数组初始化;

例如: 或 相当于:

char a[ ]={“I am happy”}; char a[ ]=“I am happy” ;

char a[ ]={‘I’‘ ’‘a’‘m’‘ ’‘h’‘a’‘p’‘p’‘y’‘\0’}; , , , , , , , , , ,
注:数组 a 的长度是 11。

例如:char c[10]={“hello”}; h e l l o \0
173

\0

\0

\0

\0

2.注意事项 (1)字符数组本身并不要求他的最后一个字符为‘\0’ ,
也即下面的赋值是合法的:

char ar[10]={?I‘,‘ ?, ‘a‘,‘m‘,‘ ‘,‘h‘,‘a‘,‘p‘,‘p‘,‘y‘}
但在实际应用中,由于系统对字符串常量处理时自动加一个‘\0’ 。因此,为了使处理

通常在对字 符数组赋值时,人为地加上一个‘\0’ ,即: char ar[10]={?I‘,‘ ?, ‘a‘,‘m‘,‘ ‘,‘h‘,‘a‘,‘p‘,‘p‘,‘y‘,‘\0‘}
方法一致,便于测定字符串的实际长度,以及在程序中作相应的处理,

(2)若在字符数组定义之后再初始化,不能整体赋值,此时, 只能给每个元素逐个赋值。

例如: char mark[10]; mark=‖Cprogram‖; //不合法 例如: char str1[10]=‖computer‖,srt2[10]; str2=str1; //不合法 五、字符数组的输入与输出(P144) 方法一:逐个字符的输入与输出 例 5.22 方法二:将整个字符串一次输入或输出。 例如:
174

char str[20]; cin>>str; cour<<str;
注意:阅读 P152.

说明: (1)在 C/C++中通过 printf 和 scanf 函数实现:

char str[20]; scanf(―%s‖,str); printf(―%s‖,str);

或: cin>>str; 或: cout<<str;

注:在输入字符串时,当遇到空格或回车时,即认为字符串结束。

(2)在 C/C++中通过 gets 和 puts 函数实现:

char str[20]; gets(str); puts(str);
注:在输入字符串时,用回车键确认表示字符串结束。

(3)scanf 函数 gets 函数在使用时的两个不同之处
(a) 一次函数调用可以输入的字符串数据个数不同

scanf(―%s%s‖,str1, str2);
注:一次调用可以输入多个用空格分隔的字符串

gets(str1);
注:一次调用之能够输入一个字符串

(b) 空格字符的处理不同
使用标准库函数 scanf 时,由于空格字符作为两个字符串数据的分
175

隔符出现,所以在输入的字符串数据中不能含有空格字符;而使用标准库 函数 gets 时,输入的字符串数据中可以含有空格字符。

六、字符串处理函数(P146)
为了简化程序设计的复杂度,C 与 C++提供了大量的字符串处理函数。 这些函数的使用,要包括头文件:string.h

或 cstring

1.字符串连接函数 strcat() 函数一般形式为: strcat(字符数组 1,字符串 2) 其功能: 将字符串 2 连接到字符数组 1 中的字符串之 后,并且将连接后的新串存放于字符数组 1 中。 例如: char str1[20]={―Good ‖},str2 [ ]={―morning‖}; strcat(str1,str2); cout<<str1;
说明: ①字符数组 1 是已定义的足够大的字符数组,连接时,去掉字符数组 1 中 的结束标志‘\0’ ,再把字符串 2 连接到其后,新串最后保留一个‘\0’ 。
176

②字符串 2 可以是字符数组名或字符串常量。

2.字符串的复制函数 strcpy() 函数的一般形式: strcpy(字符数组 1 ,字符串 2)
目标字符数组 其功能是:将字符串 源字符串

2 复制到字符数组 1 中去。

例如: char str1[10],str2 [ ]={“Hello”}; strcpy(str1,str2) ; 执行后,str1 的状态如下: H e l l o ?\0‘
说明: ①?字符数组 1?必须定义的足够大,以便可以容纳被复制的字符串; ②?字符数组 1?必须写成数组名形式,而?字符串 2?可以是字符数组 名,也可以是一个字符串常量。

如上例也可写为:

strcpy(str1, “Hello”; )

③不能用赋值语句将一个字符串常量或字符数组直接给一个字符数组。

如下面是不合法的: str1={“Hello”}; str2=str1;
④可以用 strcpy 函数将字符串 2 中若干字符复制到字符数组 1 中;
177

例如: strcpy(str1,str2+2) ;
其功能是: 将从 str2 中第 2 个字符开始复制到 str1 中, 然后再加一个 ‘\0’

例 5.23 编程序实现将源字符串从指定位置开始拷 贝到目标字符串的功能。 #include <iostream> #include <string> using namespace std; void main() { char s1[80],s2[80]; int pos;
//指定复制的位置

cout<<"Input the string s1:"; gets(s1); cout<<"Input the pos: "; cin>>pos; strcpy(s2,s1+pos); puts(s2); }

178

3. 字符串比较函数 strcmp() 函数的一般形式: strcmp(字符串 1,字符串 2) 功能:比较两个字符串的大小。
其中:字符串 1、字符串 2 可以是字符串常量或已赋值的字符数组。

比较规则:对两个字符串自左至右逐个字符相比(按

ASCII 码值大

小比较) ,直到出现不同的字符或遇到‘\0’为止。如全部字符相同,则认 为相符; 若出现不相同的字符, 则以第一个不相同的字符的比较结果为准。 比较结束时, 用该时刻两个字符串中对应位臵字符的 ASCII 码差值来 确定两个字符串之间的关系。设参加比较操作的两个字符串分别用 s1 和 s2 表示(其中 s1 表示前串,s2 表示后串) ,则字符串比较结果的判断规 则为:

?? 0 ? s1[i ] ? s 2[i ] ? ?? 0 ?? 0 ?
说明:

( s1 ? s 2) ( s1 ? s 2) ( s1 ? s 2)

对字符串的比较,不能用以下形式: if (str1==str2) cout<<―yes‖; 正确: if (strcmp(str1,str2)==0) cout<<―yes‖; 4. 测试字符串长度函数 strlen()
179

函数的一般形式: strlen(字符数组) 功能是:求字符数组中存放的字符串长度。 例如: char str[10]={―Hello‖}; cout<<strlen(str); 其输出结果为:5
说明: 函数值为字符串中的实际长度,不包括‘\0’在内;

也可以直接测试字符串常量的长度。 如: strlen( “Hello” ) 七、字符串应用举例 例 5.24 有 3 个字符串,要求找出其中最大者。 #include <iostream> #include < cstring> using namespace std; void main() { char string[20],str1[20],str2[20],str3[20]; cout<<"please input string:"; gets(str1); gets(str2);
180

gets(str3);
if (strcmp(str1,str2)>0) else strcpy(string,str2); strcpy(string,str3); strcpy(string,str1);

if (strcmp(str3,string)>0)

cout<<"the max string is:"<<string<<endl; } 例 5.25 输入一个由字母组成的字符串, 再分别以大 写字母和小写字母形式输出该字符串。 #include <iostream> #include < cstring> using namespace std; void main() { char c[60]; int k;

cout<<"please input the string:"; gets(c); cout<<endl; k=0; while(c[k]!='\0') { if (c[k]>='a' &&c[k]<='z')
181

putchar(c[k]-32); else putchar(c[k]); k++; } cout<<endl; k=0; while(c[k]!='\0') { if (c[k]>='A' &&c[k]<='Z') putchar(c[k]+32); else putchar(c[k]); k++; }

}
例 5.26 不用 strcat 函数实现将两个字符串连接
//不用函数 strcat 实现其功能

#include <iostream>
182

#include < cstring> using namespace std; void main() { char s1[80], s2[80]; int i=0, j=0; cout<<"Please input a string1:"; gets(s1); cout<<"Please input a string2:"; gets(s2); while(s1[i]!='\0') i++; while(s2[j]!='\0') s1[i++]=s2[j++]; s1[i]='\0'; cout<<" the new string is :"<<s1; } 例 5.27 删除某一个字符串中某个特定字符。
问题分析:将要保留的字符逐个复制一遍。

#include <iostream> #include < cstring> using namespace std; void main()
183

{

char a[]="this is a string"; char c='i'; int i,j=0; for(i=0;a[i]!='\0';i++) if(a[i]!=c) a[j++]=a[i]; a[j]='\0'; cout<<a<<endl;
//欲删除的字符

}
例 5.28 输入 10 个字符串,输出其中的最大者。 #include <iostream> #include < cstring> using namespace std; void main()

{

int i; char max[20],str[10][20];
184

gets(str[0]); strcpy(max,str[0]); for(i=1;i<10;i++) { gets(str[i]); if (strcmp(max,str[i])<0) strcpy(max,str[i]); } puts(max); }
例5.29 输入5个国家的名称, 按字母顺序排列输出。 #include <iostream> #include < cstring> using namespace std; void main() { char st[20],cs[5][20]; int i,j,p; cout<<"input country's name:";
185

for (i=0;i<5;i++) gets (cs[i]); for (i=0;i<5;i++) { p=i; strcpy(st,cs[i]); for (j=i+1;j<5;j++) if (strcmp(cs[j],st)<0) { p=j; strcpy(st,cs[j]); } if (p!=i) { strcpy(st,cs[i]); strcpy(cs[i],cs[p]); strcpy(cs[p],st); } puts(cs[i]); } }

186

5.5 C++处理字符串的方法—字符串类与字符串变量(P149)
在 C 中用字符数组的方式存储、 处理字符串的方法存在着一定的缺陷, 因此在 C++中引入了字符串类型,可通过类型变量的定义来实现对字符串 的方便处理。

c++允许其标准库中声明的一个字符串类定义一个字符串 变量。

一、字符串变量的定义和引用
1.定义字符串变量 定义字符串变量的一般格式: string 或: 例如: string str1; string str2=‖program‖; 注意: 引用 string 类的功能,必须加载头文件#include<string> 2.对字符串变量的赋值 对字符串变量的赋值的一般格式: 字符串变量=字符串常量或字符串变量 例如: string str1,str2; str1=‖program‖;
187

字符串名; 字符串名=初始化值;

string

//定义 str1 为字符串变量 //定义 str2 字符串变量, 同时对其初始化

str2=str1;
问题:字符串变量 str1、str2 的所占的存储空间为多少?

3.字符串变量的输入输出 cout<<字符串变量; cin>>字符串变量;

二、字符串变量的运算(P151)
(1)用赋值运算符实现字符串复制 字符串变量 1=字符串变量 2 例如: str1=str2 例如: string str1=‖C++‖; string str2=‖program‖; string str3; str3=str1+str2; (3)用关系运算符实现字符串比较 string str1,str2; str1=‖zheng‖;str2=‖wang‖; cout<<(str1>str2)<<endl;
//等价于 strcpy(str1,str2)

(2)用加法运算符实现字符串连接

三、字符串数组(P151)
string 字符串数组名[字符串数组长度]
188

例如: string name[4]={―zhang‖,‖wang‖,‖li‖,‖zhao‖};
//定义一个字符串数组 name,长度为 4(包含 4 个字符串) ,并初始化

问题: (1)name 数组的存储格式; (2)数组元素 name[1]中存放的内容; 要求阅读 p158 页中的说明(1),(2),(3),(4)

四、字符串运算举例(P152)
例 5.30 输入 3 个字符串,按字母大小顺序输出 #include<iostream> #include<string> using namespace std; int main() { string str1,str2,str3,temp; cout<<‖please input three strings:‖; cin>>str1>>str2>>str3; if(str2>str3) { temp=str2;str2=str3;str3=temp;}
//使串 2<=串 3

if(str1<=str2) cout<<str1<<‖,‖<<str2<<‖,‖<<str3<<endl; else if(str1<=str3) cout<<str2<<‖,‖<<str1<<‖,‖<<str3<<endl; else cout<<str2<<‖,‖<<str3<‖,‖<<str1<<endl; return 0; }
189

例 5.31(P153 例 5.12)一个班有 n 个学生,将每个学生的姓 名、学号在计算机中存储,而后按姓名查询其相关资料,若找 到此人,则将其姓名和学号输出,若没找到,则输出“查无此 人” 。

#include <iostream> #include <string> using namespace std; string name[50],num[50]; //定义 name 姓名(全局) 学号(全局) ,num int n; // 定义学生个数(全局) int main() { void input_data(); // 数据输入函数声明 void search(string find_name); // 查询函数声明 string find_name; // 定义查询变量 cout<<"please input number of this class:"; cin>>n; // 输入学生个数 input_data(); //调用输入函数输入学生记录 cout<<"please input name you want find:"; cin>>find_name; // 输入欲查找的姓名 search(find_name); // 调用查询函数进行查找处理 return 0; } void input_data()
190

{ int i; for (i=0;i<n;i++) { cout<<"input name and number of student "<<i+1<<":"; cin>>name[i]>>num[i];} } void search(string find_name) { int i; bool flag=false; for(i=0;i<n;i++) if(name[i]==find_name) { cout<<name[i]<<" "<<num[i]<<endl;flag=true;break; if(flag==false) cout<<"can't find this name"; }

}

191


更多相关文档:

C++程序设计谭浩强第2章2013修订

C++程序设计谭浩强第2章2013修订_计算机软件及应用_IT/计算机_专业资料。c++课件...27 例如: int i; i=3*(4+5) //i 的值变为 27 说明: ①赋值运算符...

C++程序设计谭浩强第1章2013修订

C++程序设计谭浩强第1章2013修订_理学_高等教育_教育专区。c++课件C++语言程序设计学习目的: 1. 程序设计是计算机及其相关专业学生必备的技能之一。 2. 通过本课程...

c++程序设计_谭浩强_答案_修改版

c++程序设计_谭浩强_答案_修改版_电子/电路_工程科技_专业资料。第一章 1.5 题 #include <iostream> using namespace std; int main() { cout<<This<<is; ...

《c++程序设计》谭浩强_答案 完整版

c++程序设计谭浩强_答案 完整版_计算机软件及应用_IT/计算机_专业资料。《c++程序设计谭浩强_答案 完整版第一章 1.5 题 #include <iostream> using namespace...

c++程序设计 谭浩强 答案 完整版

c++程序设计 谭浩强 答案 完整版_理学_高等教育_教育专区。c++程序设计 谭浩强 答案 完整版 第一章 1.5 题 #include <iostream> using namespace std; int main...

c++程序设计谭浩强课后习题答案(完整版)

c++程序设计谭浩强课后习题答案(完整版)_工学_高等教育_教育专区。第一章 1.5 ...=p) &&((p+5*i+j)!=(p+4)) && ((p+5*i+j)!=(p+20)) && (...

《c++程序设计》谭浩强_答案

举报文档 蒲磊1989贡献于2013-12-16 0.0分 (0人评价)暂无用户评价 我要评价...《c++程序设计谭浩强_答案 隐藏>> 第一章 1.5 题 #include <iostream> using...

c++程序设计(谭浩强)答案

c++程序设计(谭浩强)答案_计算机软件及应用_IT/计算机_专业资料。第一章 1.5 题...=(p+4)) ((p+5*i+j)!=(p+20)) && (*pmin>*(p+5*i+j))) ...

《c++程序设计》谭浩强版

c++程序设计谭浩强版_工学_高等教育_教育专区。第一章 1.5 题 #include ...(num>9999) place=5; else if (num>999) place=4; else if (num>99) ...

《c++程序设计》谭浩强课后习题答案

c++程序设计谭浩强课后习题答案_理学_高等教育_教育专区。第一章 1.5 题 #...声明修改函数 //定义构造函数 void BirthDate::display() //定义输出函数 {...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com