高级语言程序设计（CC++版） 课件 第5章 数组

第5章

数组目录一维数组数组排序数组查找字符数组与字符串二维数组216:12为了方便存储和处理批量数据，提高程序设计的效率，通常把具有相同类型的批量元素按有序的形式组织起来，这些有序排列的同类数据元素的集合就称为数组，组成数组的各个变量就称为数组的元素。数组明确地反映了数据间的联系，含义清晰且使用方便，将其与循环有机结合处理批量数据，有利于提高程序设计的效率，增强了程序的可读性。316:121．一维数组（定义与引用）在C语言中使用数组必须先定义后使用，定义一维数组的一般格式如下：类型说明符数组名[常量表达式];其中，类型说明符是任意一种基本数据类型或构造数据类型，它定义了全体数组成员的数据类型；数组名是标识数组的名称，与变量命名规则相同；方括号中的常量表达式代表数组元素的个数，也称为数组的长度。注意，数组元素的下标从0开始计算。例如：int

a[10];

//定义一个10个元素的整型数组a，其元素是a[0]~a[9]double

b[10]; //定义一个10个元素的浮点型数组b，其元素分别是b[0]~b[9]char

c[30];

//定义一个30个元素的字符数组c，其元素是c[0]~c[29]返回416:121．一维数组（初始化）可以在定义数组时为元素赋初值，若定义数组时未赋初值则元素值是无意义的随机值。若仅给部分元素赋初值，则整型数组中未被赋值的元素自动赋值0，字符数组中未被赋值的元素自动赋值'\0'。如：int

a[10]={0,1,2,3,4,5,6,7,8,9}; //全体元素赋值，a[0]~a[9]分别赋值为0~9int

a[10]={1,2,3}; //前3个元素赋值为1，2，3，后7个元素值为0char

c[20]={'C','+','+'}; //前3个元素赋值，其余元素值为'\0‘int

a[3]={1,2,3,4}; //赋值数目不允许超过数组容量，否则编译时会报错516:12例5.1：输入一个非负十进制整数，将其转换为二进制形式输出。

输入：一个非负整数n(0<=n<2^31)。

输出：对应的二进制形式。#include<iostream>usingnamespacestd;intmain(){ intn,i,a[32]; cin>>n; if(n==0){cout<<"0"<<endl;return0;} for(i=0;n!=0;i++) { a[i]=n%2; n=n/2; } for(i--;i>=0;i--)cout<<a[i];return0;}616:12例5.2：一个非递减有序的整型数组有n个元素，给定一个整数num，将num插入该序列的适当位置，使序列仍保持非递减有序。

输入：输入有三行。第一行是一个正整数n(n<=1000)。第二行是n个整数，第三行是待插入整数num。

输出：输出非递减有序的n+1个整数，数据之间用空格隔开。输出占一行。#include<iostream>usingnamespacestd;intmain(){ intn,i,num; cin>>n; inta[1001]; for(i=0;i<n;i++) cin>>a[i]; cin>>num; for(i=n-1;i>=0&&a[i]>num;i--) a[i+1]=a[i]; a[i+1]=num; for(i=0;i<=n;i++) cout<<a[i]<<""; return0;}716:122．数组排序在实际开发中，经常需要将数组元素按照从大到小（或者从小到大）的顺序排列，这样在查阅数据时会更加方便直观。数组元素进行排序的方法有很多种，如选择排序、冒泡排序、插入排序、快速排序、归并排序等。返回816:12例5.3：对一维数组按照从小到大的顺序排序。

输入：第一行输入一个整数n（1<=n<=100)表示数组有n个整数；第二行输入n个整数。

输出：对这n个整数按照从小到大的顺序输出，数据之间用一个空格隔开。#include<iostream> //解法1：选择排序usingnamespacestd;intmain(){ intn,a[100],i,j; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++){ intmin=i; for(j=i+1;j<n;j++)

if(a[j]<a[min])min=j; intt=a[min];a[min]=a[i];a[i]=t; } for(i=0;i<n;i++) cout<<a[i]<<""; return0;}916:12#include<iostream> //解法2：冒泡排序usingnamespacestd;intmain(){ intn,a[100],i,j,temp; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=n-1;i>=1;i--) for(j=0;j<i;j++) if(a[j]>a[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } for(i=0;i<n;i++) cout<<a[i]<<""; return0;}1016:12#include<iostream> //解法3：插入排序usingnamespacestd;intmain(){ intn,a[100],i,j,k,temp; cin>>n; for(i=0;i<n;i++)cin>>a[i]; for(i=0;i<n;i++){ for(j=i-1;j>=0;j--)if(a[i]>=a[j])break; //为a[i]寻找插入位置j+1 if(j!=i-1) { temp=a[i]; for(k=i-1;k>j;k--)a[k+1]=a[k]; a[k+1]=temp; } } for(i=0;i<n;i++)cout<<a[i]<<""; return0;}1116:12例5.4：已知数组a中有m个按升序排列的元素，数组b中有n个按降序排列的元素，编程将a与b中的所有元素按降序存入数组c中。输入：输入有两行，第一行首先是一个正整数m，然后是m个整数；第二行首先是一个正整数n，然后是n个整数，m,n均小于等于1000000。

输出：输出合并后的m+n个整数，数据之间用空格隔开。输出占一行。#include<iostream>usingnamespacestd;constintN=1000000;inta[N],b[N],c[2*N];intmain(){ intm,n,i,j,k; cin>>m; for(i=0;i<m;i++) cin>>a[i]; cin>>n; for(i=0;i<n;i++) cin>>b[i]; i=m-1;j=0;k=0;

while(i>=0&&j<n) { if(a[i]>b[j])c[k++]=a[i--]; elsec[k++]=b[j++]; } while(i>=0) c[k++]=a[i--]; while(j<n) c[k++]=b[j++]; for(i=0;i<m+n;i++) cout<<c[i]<<""; return0;}1216:123．数组查找例5.5：数组a有n个元素，请输出n个元素的最小值及其下标。若最小值有多个，请输出下标最小的一个。注意，有效下标从0开始。输入：输入分两行，第一行是一个正整数n（n<=1000)，第二行是n个整数。输出：输出占一行。输出数组的最小值及其下标，用空格隔开。#include<iostream>usingnamespacestd;intmain(){ inti,n; cin>>n; inta[1001]; for(i=0;i<n;i++) cin>>a[i];

intmin=0; for(i=1;i<n;i++) if(a[i]<a[min])min=i; cout<<a[min]<<""<<min<<endl; return0;}返回1316:12例5.6：学校推出了10名歌手，每个歌手都有唯一编号（0~9）。校学生会想知道这些歌手受欢迎的程序，设了一个投票箱，让每一个同学给自己喜欢的歌手投票，同学们使用歌手编号进行投票。现在学生会找你帮忙统计一下每位歌手获得的票数，并颁发“最受欢迎歌手奖”，该奖项颁发给得票最多的歌手。若有多名歌手并列第一，则均可获奖。输入：输入若干个整数，表示投票的歌手编号，以一个负数作为输入结束的标志。

输出：出现次数最多的编号。若有多个则按从小到大顺序输出选手编号(用空格隔开)。include<iostream>usingnamespacestd;intmain(){ inti,a[10]={0}; intnum; while(cin>>num&&num>=0) a[num]++; intmax=a[0]; for(i=1;i<10;i++) if(a[i]>max)max=a[i]; for(i=0;i<10;i++) if(a[i]==max)cout<<i<<""; return0;}1416:12例5.7：输入从小到大排好序的n个元素，找出某元素第一次出现的位置。

输入：输入分三行，第一行是一个正整数n（n<1000)，第二行是n个整数，第三行为一个整数x表示待查找的元素。

输出：如果x在序列中，则输出x第一次出现的位置，否则输出-1。#include<iostream>usingnamespacestd;intmain(){ intn,x; cin>>n; inta[1001]; for(inti=1;i<=n;i++) cin>>a[i]; cin>>x; intlow=1,high=n,mid; while(low<=high) { mid=(low+high)/2; if(a[mid]==x)break; if(x>a[mid])low=mid+1; elsehigh=mid-1; } if(low>high)cout<<"-1"; else{ while(mid>1&&a[mid]==a[mid-1]) mid--; cout<<mid; } return0;}1516:124．字符数组与字符串（字符数组的初始化）在C语言中，字符数组是字符类型元素构成的数组。定义字符数组的一般格式如下：char数组名[常量表达式];

对于字符数组的初始化，可以在定义时对每个元素逐一初始化，也可以在定义时直接用双引号引起来的一串字符实现初始化。例如：chara[10]={‘1’,‘2’,‘3’,‘4’,‘5’,‘6’};chara[10]={“123456”}; //chara[10]=“123456”;

以上是两个等价的字符数组初始化定义。但是，在使用双引号形式初始化时，字符串常量的字符个数必须比所定义的数组容量少一个以上。因为此种情况下，系统会自动在有效字符结束时附加一个‘\0’作为结束标志。在编写程序时，通常依据当前字符与‘\0’是否相等来判断字符串是否结束。返回1616:124．字符数组与字符串（字符串的输入输出）C语言不提供“字符串”数据类型，而是运用一个字符数组来模拟存放一个字符串，只是在字符串的有效字符结束时附加一个字符‘\0’作为结束。字符数组可以使用格式符“%c”逐个输入或输出一个字符，也可以使用格式符“%s”一次输入或输出整个字符串。例如：charc[100]={“Ilovec++programming!”};printf(“%s\n”,c); //从第0个字符起依次逐个输出当前字符，若当前字符为‘\0’则结束说明：（1）使用格式符“%s”输出字符串时，printf的输出项是字符数组名，代表字符串的起始地址。不能写成

printf(“%s\n”,c[0]);

，否则编译时会报错。（2）输出时从字符数组的第0个字符起依次逐个输出当前字符，第一次遇到当前字符为‘\0’时输出自动结束，且输出字符不包括‘\0’。（3）可以使用scanf函数输入一个字符串，如

scanf(“%s”,c);

，系统检测输入的字符串，遇到换行或空格时自动加一个‘\0’字符作为结束标志。（4）若要输入其中含有空格的字符串，则须使用

gets(c);；除此之处，输出字符串时可使用

puts(c);，其功能与语句

printf(“%s\n”,c);

等价。1716:124．字符数组与字符串（C语言的字符串处理函数）C语言专门提供了一系列处理字符串的函数。几种常用的字符串处理函数见表5.1。18格式说明unsignedintstrlen(charstr[])统计str中字符的个数，不包括结束符‘\0’char*strcat(char*str1,char*str2)将字符串str2连接到str1后，str1后的‘\0’被取消char*strchr(char*str,charch)字符串str中第一次出现字符ch的位置intstrcmp(char*str1,char*str2)按字典序比较str1和str2，<返回负数、=返回0、>返回正数char*strcpy(char*str1,char*str2)将字符串str2的值复制给str116:12例5.8：输入一个以回车结束的字符串，该字符串由数字和字母组成。请过滤掉所有非数字字符，然后将数字字符串转换成十进制整数后乘以2输出。

输入：输入一个以回车符结束的字符串，长度不超过100，由数字和字母组成。

输出：将转换后的整数乘以2输出，测试数据保证结果在整数范围内输入样例：sg987aa65t498。输出样例：197530996。#include<iostream>usingnamespacestd;intmain(){ charc[200],b[200]; gets(c); //以cin.getline(c,200);代替

inti=0,j=0,sum=0; while(c[i]) { if(c[i]>='0'&&c[i]<='9')sum=sum*10+c[i]-'0'; i++; } cout<<sum*2<<endl; return0;}1916:124．字符数组与字符串（C++的字符串处理）C++兼容C的字符串表示与处理方式，同时引入了string类表示字符串类型，因此C++中可以直接定义一个字符串变量。C++中的字符串使用方式如下： strings1="c",s2="programming"; //定义字符串变量s1,s2并赋初值 s1="c++"; //s1重新赋值 s1=s1+s2; //s1值更改为"c++programming"，注意两个字符串常量不能相加C++支持"cin>>s1;"输入字符串变量的值，同时能够直接利用6种比较关系运算符实现字符串之间的按字典序比较。string类的主要函数与运算见表5.2。20格式说明size()求字符串长度，等同于length()s[i]取字符串s的第i个字符getline(cin,s)读入一整行给s直到换行，包括读入空格substr(i,len)从下标i开始，到下标i+len-1结束取长度为len的子串insert(i,s)在字符串的第i个位置插入serase(i,len)删除字符串第i个位置开始的len个字符replace(i,len,t)以字符串t替换字符串第i个位置开始的len个字符find(subs)查找子串subs第一次出现的位置16:12例5.9：输入一个1到7之间的数字，表示星期一到星期日，输出相应的英文：Mon、Tue、Wed、Thur、Fri、Sat、Sun。输入：输入一个1到7之间的数字。输出：输出与数字对应的英文。#include<iostream>usingnamespacestd;intmain(){ stringdayName[8]={"","Mon","Tue","Wed","Thur","Fri","Sat","Sun"}; intday; cin>>day; cout<<dayName[day]<<endl; return0;}2116:12例5.10：输入一个0和1字符组成的二进制字符串，请转换成十六进制。

输入：输入一个0/1字符串，长度小于100000。（如：11010100101）

输出：输出1行转换后的十六进制。（6A5）#include<iostream>usingnamespacestd;intmain(){ strings,ans=""; cin>>s; for(inti=s.size();i>0;i=i-4) { intt=0; for(intj=max(0,i-4);j<i;j++) t=t*2+(s[j]-'0'); if(t<10)ans=char(t+'0')+ans; elseans=char(t+'A'-10)+ans; } cout<<ans<<endl; return0;}2216:12例5.11：输入一行字符，统计其中有多少个单词，单词之间用空格分隔开。

输入：输入一个以空格分隔的字符串。

输出：字符串中的单词个数。#include<iostream>usingnamespacestd;intmain(){ stringstr; inti,num=0,word=0; charc; getline(cin,str); //输入一行字符串给字符字符串变量str for(i=0;(c=str[i])!='\0';i++) //只要字符不是'\0'就循环 if(c=='')word=0; //若是空格字符，使word置0 elseif(word==0) //如果不是空格字符且word原值为0 { word=1; //使word置1 num++; //num累加1，表示增加一个单词 } cout<<num<<endl; //输出单词数 return0;}2316:12例5.12：输入三个字符串，输出其中按字典序最大的字符串。

输入：输入三个字符串。

输出：输出其中最大的字符串。#include<iostream>usingnamespacestd;intmain(){ strings,str[3]; //定义字符串数组 inti; for(i=0;i<3;i++)

cin>>str[i]; //读入3个字符串，分别给str[0],str[1],str[2] if(str[0]>str[1])s=str[0]; //若str[0]大于str[1]，把str[0]的字符串赋给字符数串s elses=str[1]; //若str[0]小于等于str[1]，把str[1]的字符串赋给字符串s if(str[2]>s)s=str[2]; //若str[2]大于s，把字符串str[2]赋给字符数串s cout<<s<<endl; //输出s return0;}2416:125．二维数组（定义与引用）二维数组本质上是以一维数组为元素的数组，即“数组的数组”。二维数组又称为矩阵，行列数相等的矩阵称为方阵。二维数组的一般格式为：类型说明符数组名[常量表达式1][常量表达式2];表达式1代表二维数组的行数，表达式2代表二维数组的列数。C++中，二维数组在内存中按行优先顺序存放。注意，元素的行下标和列下标均是从0开始计算。例如：int

a[10][10];

//定义一个10行10列的整型二维数组a，其元素是a[0][0]~a[9][9]返回2516:125．二维数组（初始化）可以在定义二维数组时给数组元素初始化赋值，若仅给部分元素赋初值，则对int数组而言未被赋值的元素自动赋值0，对char数组而言未被赋值的元素自动赋值’\0’。如：int

a[2][3]={{1,2,3},{4,5,6}}; //每个花括号中3个数据对应矩阵的1行int

a[2][3]={1,2,3,4,5,6}; //按行优先给二维数组元素赋值，效果同上int

a[][3]={1,2,3,4,5,6}; //行可缺省，系统据总数目与第2维长度计算第1维长度int

a[][3]={{1,2,3},{},{4,5,6}}; //行可缺省，系统只对部分元素赋值int

a[2][3]={{1},{4}}; //部分元素赋初值，除a[0][0]=1,a[1][0]=4外其余元素赋值02616:12例5.13：输入一个正整数n和n阶方阵a中的元素，如果a是上三角矩阵则输出“YES”，否则输出“NO”。上三角矩阵的主对角线(不包含主对角线)以下元素均为0。

输入：输入一个正整数n(1<n<10)和n阶方阵a中的元素，均为整数。

输出：若a是上三角矩阵则输出“YES”，否则输出“NO”。#include<iostream>usingnamespacestd;constintN=10;intmain(){ intn,a[N][N]; cin>>n; for(inti=0;i<n;i++) for(intj=0;j<n;j++) cin>>a[i][j]; for(inti=0;i<n;i++) for(intj=0;j<i;j++) if(a[i][j]!=0){ cout<<"NO"<<endl; return0; } cout<<"YES"<<endl; return0;}2716:12例5.14：计算两个矩阵A和B的乘积。

输入：第一行三个正整数m、p、n(1<m,n,p<10)，表示矩阵A是m行p列，矩阵B是p行n列；接下来的m行是矩阵A的内容，每行p个整数，以空格隔开；最后的p行是矩阵B的内容，每行n个整数，以空格隔开。

输出：输出乘积矩阵，输出占m行，每行n个数据，以空格隔开。#include<iostream>usingnamespacestd;constintN=10;intmain(){ inta[N][N],b[N][N],c[N][N]; intm,p,n; cin>>m>>p>>n; for(inti=0;i<m;i++) for(intj=0;j<p;j++) cin>>a[i][j]; for(inti=0;i<p;i++) for(intj=0;j<n;j++) cin>>b[i][j]; for(inti=0;i<m;i++) for(intj=0;j<n;j++){

c[i][j]=0; for(intk=0;k<p;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]; } for(inti=0;i<m;i++) { for(intj=0;j<n-1;j++)cout<<c[i][j]<<""; cout<<c[i][n-1]<<endl; } return0;}2816:12例5.15：输入一个字符串，输出字符串中出现次数最多的字母。

输入：输入一个只含有大小写字母和空格的字符串，长度不超过100，以回车结束。

输出：输出一个小写字母，表示该字符串中出现次数最多的字母。若有多个则只输出ASCII码最小的那个字母。#include<iostream>usingnamespacestd;intmain(){ strings; getline(cin,s); inta[26]={0}; for(inti=0;i<=s.length();i++) if(s[i]>='a'&&s[i]<='z')a[s[i]-'a']++; elseif(s[i]>='A'&&s[i]<='Z')a[s[i]-'A']++; intmax=0; for(inti=0;i<26;i++)if(a[max]<a[i])max=i; cout<<char(max+'a')<<endl; return0;}2916:12例5.16：输入一个日期，输出该日期是所在年的第几天。

输入：输入一个日期。

输出：输出该日期是所在年的第几天。#include<iostream>usingnamespacestd;intmain(){ intyear,month,day,leap=0,shift[2][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}};