第五章 数组
一、一维数组
1.一维数组的格式
类型标识符 数组名 [常量表达式 ]；
注:
- 1类型标识符可以是任何基本数据类型，也可以是结构体等构造类型，相同类型的数组可以一起定义。
- .数组名必须是合法的标识符。
- 常量表达式的值即为数组元素的个数。
- 定义数组时不能超过最大值，且它们的编号从零开始，每个元素都是int类型。
举例
①.
②.#define N 50 int b[N];
注:这是定义符号常量。表示此段程序从此行开始，所有的N都表示50。在预编译的时候，预处理器会对程序进行扫描，把其中所有的N都换成50 ，且行末不加分号。
2.一维数组的元素引用
- 不能一次引用整个数组，只能逐个引用数组的单个元素。
- 值必须在数组定义的下标范围内，否则会出现下标越界错误。
3.一维数组的输入和输出
对于一个数组a来说
cout<<a；
错误
(一维数组的输出)
int a[20];
for(int i=0;i<20;i++) cout<<a [i];
(一维数组的输入)
int a[20];
for(int i=0;i<20;i++) cout<<a[i];
(给所有或者部分元素赋值)
int a[10]={ 0,1,2,3,4,5,6,7,8,9};
int a[10]={0,1,2,3,4};//部分赋初值，后面的元素自动初始化为0
int a[ ]={1,2,3,4,5};//不定义数组长度直接根据赋值个数定
直接赋值
int h[100]，a[20];
for(i=0;i<100;i++) h[i];
for(i=0;i<20;i++) a[i]=i2+1;*
①memse 函数
memet函数是数字节进行赋值，一般用在char型数组如果是int类型的数组，一般赋值为0和1。使用前须包含头文件:#include＜cstring＞。
②fill
fill函数是给数组“按元素”进行赋值,可以是整个数组,可以是部分连续元素,可以赋任何值。使用前需要包含头文件:# include< algorithm>。如,“fil(a,a+10,5);”就是将a数组的前10个元素赋值为5。
#include< iostream>
#include<cstring>
using namespace std
int main()(
inta[10],b[10],c[10],d[10],i;
memset(a,0, sizeof(a));//将a数组所有元素均赋值为0
for(i= 0; i < 9; 1++) cout <<a[i] <<" ";
cout << a[9]<< endl;
memset(b, 1, sizeof(b));//将b数组所有元素均赋值为二进制数2^0+2^8+2^16+2^24=16843009
for(i= 0; 1<9: 1++) cout << b[i]<<" ";
cout << b[9]< <endl;memset(c,0, 5);//将c数组前5个字节都赋值为0,所以只能确定c[0]=0,其他元素值不确定
for(i=0;i<9;i++)cout<<c[i]<<" ";
cout << c[9]<< endl;
3.一维数组的存储结构
数组在计算机内存单元中是连续存储的。程序一旦执行到数组的定义语句，就会开辟出若干字节的内存单元。如果每个元素都是int类型则占用四个字节。
二、 二维数组
1.二维数组的定义和初始化
二维数组的一般格式:
类型标识符 数组名 [常量表达式1][常量表达式2]
注:1.常量表达式1的值表示第一维大小,常量表达式2的值表示第二维大小,常量表达式1和常量表达式2的乘积就是二维数组的元素个数。
例如int h[4][5]；
2.二维数组的初始化赋值
例如
①
int a[2][3]={{1,2,}},{4,5,6}};//分行初始化
int a[2][3]={1,2,3,4,5,6)//不分行初始化
以上两种初始化都相当于下面6个语句:
a[0][1]=1;a[0][1]=2;a[0][2]=3；
a[1][0]=4;a[1][1]=5;a[1][2]=6；
也可以给数组中的部分元素初始化。
例如:
②
int a[2][3]={{1,2}，{4}}；
第一行只有2个初值,按顺序分别赋值给a[0][0]和a[1][1],第二行的初值4赋值给a[1][0],其他元素默认为0。
在定义二维数组时,可以省略第一维的大小,但是第二维的大小不能省略。例如"int a[ ][5];”是允许的,被省略的第一维大小根据初值的个数由系统来确定。
int a[ ][ 4 ]={1，2，3，4，5，6，7，8，9，10，11，12}；
系统根据{ }中的个数，自动确定a数组的第一维大小为3。
3.二维数组的存储及引用
因为二维数组本质上是一维数组的每一个元素又是一个一维数组,而计算机内部存储一维数组采用的是连续存储单元。所以,二维数组的存储方式是“行优先”的连续存储,先逐个存储第0行上的所有元素,再逐个存储第1行上的所有元素,依此类推。
4.二维数组的输出输入
二维数组的输入和输出操作也是针对每一个元素进行，结合两个维度的下标变化，用循环嵌套实现。
法一:
#include<iostream>
using namespace std；
int main( ){
for(i=1;i<=(n+1)/2;i++)
for(j=1;j<=(n+1)/2;j++){
a[i][j]=min(i,j)；
a[i][n+1-j]=a[n+1-j]=a[n+1-i][n+1-j]=a[i][j]；
}
for(i=1；i <= n: i++){
for(j=1;j<=n-1;j++)cout < a[1][3] <<" "；
}
cout < <a[i][n]<< endl；
}return 0；
}
法二:
#include<iostream>
using namespace std;
int n,i,i,k, a[10][10]
int main(){
cin > n;
for(k=1;k<=(n+1)/2;k++)
for(i=k;i < n+1-k; i++)
for(j=k;j<=n+1-k;j++)
a[i]]3]= k;
for(i=1;i<=n:1++){
for(j=1;j<n;j++)
cout<<a[i][j]<<" ";
cout < a[i][n] <<endl;
}
return 0;
}
三、字符数组
1定义:如果数组中的每个元素都是一个字符，这样的数组称为"字符数组"。
2.定义字符数组的方法与定义其他类型数组的方法类似。
3.
注意:1.在用scanf的%格式或gets读入字符串时，会在字符串末尾自动添加一个空字符‘ \0 ’。而使用getchar等方法读入字符串时，则要在字符串后手动加‘\0’。
举例:
#include <cstdio>
using namespace std；
int main(){
char s1[20],s2[20];
scanf("%s",s1);
scanf("%s",s2)
printf("%s\n”,s1);
printf("%s\n",s2)
return 0;
}
运行程序,输入“ Hello world！"
输出为:
Hello
world!
问题分析
scanf函数读取一个字符串时,是把回车符空格符、Tab符作为字符串的结束符号。所以Hello world!,第一个scanf语句只会读取"Hello”,而第二个 scanf语句会接着读入" world”。
如果程序改为用gets输人puts输出:
#include<cstdio>
using namespace std；
int main(){
char s1[20],s2[20]
gets(s1)；
gets(s2)；
puts(s1)；
puts(s2)；
return 0；
}
输入:“Hello world！”
输出:“Hello world！”
分析gets，scanf，getchar的优缺点:
- gets函数没有限制读取的字符串长度，如果输入的字符串太长可能会导致堆栈溢出。输入一行字符串后仅以回车符结束输入。
- scanf函数用来读取一个字符串时，字符串不能出现空格，因为scanf是以回车符、空格符、Tab符作为字符串的结束一次输入，但需要输入输出大量数据时，效率很低，容易超时
- getchar很高效
例:
int scan(){
int res= 0, flag =0;
char ch；
if((ch= getchar ())=="-") flag= 1;
else if(ch >='0'&& ch <='9') res= ch -'0'；
while((ch= getchar()) >='0'&& ch <='9')
res= res *10+(ch -'0')；
return flag ?-res:res；
}
四 排序问题
①插队
#include<cstdio>
using namespace std；
int main(){
int n,i,x,q[102];
scanf("%d" , &n)
for(i =1; i <= n; i++)
scanf ("%d" ,&q[i]);
scanf("%d",&x);
for(i= n; i >= x; i--) q[i+1]= q[i];
q[x]=q[n+1];
for(i =1; i< n; 1++) printf("%d",q[i]);
printf("%d\n"q[i]);
return 0;
}
②.离开
#include<cstdio>
using namespace std；
int main(){int n,i,x,q[102];
scanf ("%d",&n);
for(i= 1; i <=n; 1++) scanf("%d",&q[i]);
scanf("%d",&x);
for(i= x; i< n; i++) q[i]= q[i+1];
n--;
for(i= i; i <n; i++) printf("%d",q[i])
printf("%d\n",q[n]);
return 0;
}
算法1. 选择排序
选择排序的基本思想是:每一趟从待排序的数据中,通过“打擂台”比较选出最小元素,放在这些数据的最前面。这样,第一趟把n个数中(第1个到第n个)最小的放在第一个位置,第二趟把剩余的n-1个数中(第2个到第n个)最小的放在第二个位置,第三趟把剩余的n-2个数中(第3个到第n个)最小的放在第三个位置,…第n-1趟把剩下的2个数中(第n-1到第n个)最小的放在第n-1个位置,剩下的最后一个数(第n个)一定最大,自然落在了第n个位置。
算法2 冒泡排序
冒泡排序的基本思想是:从第一个数开始,依次不断比较相邻的两个元素,如果“逆序”交换。这样,一趟排序结束后,最大的元素就放在了第n个位置了。
算法3 插入排序
插入排序的基本思想是:把所有待排序元素分成前后两段,前一段是已经排好序的,后一段是待排序的。每一趟都是把后一段的第一个数“插入”到前一段的某一个位置,保证前一段仍是有序的。开始时,第1个数作为前一段肯定是有序的;第一趟,把第2个数插入进去,保证前个数有序;第二趟,把第3个数插入进去,保证前3个数有序;…第n-1趟,把第n个数插入进去，保证n个数都有序。
#include<iostream>
using namespace std;
int main(){
int n,i,j,k, temp, h[101];
cin>> n;
for(i= 1; i <= n;i++)
cin > h[i];
for(i =1;i <= n:i++){
k=i;
for(j=i+1;j<=n;j++)
if(h[j]<h[k])k=j;//在i-n之间的最小元素
temp= h[i];
h[i]=h[k];
h[k]=temp;//将i-n之间的最小元素放到第i个位置
}
for(i= 1;1< n;i++)
cout < h[il <<" ";
cout<< hin]<< endl;
return 0;
}
#include<iostream>
using namespace std;
int main(){
int.n,i,j,temp,h[101];
cin>>n;for(i=1;1<=n;1++)
cin>>h[i];for (i= 1:;1< n; i++)
for(i=1;j<=n-i;j++)
if(h[j]>h[j+1])
{
temp= h[j];
h[j]=h[j+1];
h[j+1]=temp;
}
for(i= 1;i< n; i++)
cout < h[i] <<" ";
cout <<h[n]<< endl;
return 0;
}
#include<iostream>
using namespace std;
int main(){
int n, i,j, k, temp, h[101];
cin>> n;
for(i= 1;1<= n; i++) cin >>h[i];
for(i=2;i<=n;i++){
temp= h[i];
k=1;
while(h[k]<= temp && k< 1) k++;
for(j=i-1;j>=k;j--) h[j+1]=h[j];
h[k]= temp;
for(i= 1;1< n; i++) cout < h[i] <<" ";
cout < h[n] < endl;
return 0;
}
快速排序
#include<iostream>
#include<algorithm>
using namespace std;
bool complare ( int a,int b)//比较函数
{
return a>b;
}
补充:桶排序
桶排序:通过分类来计数排序
五 查找问题
顺序查找和二分查找
顺序查找
按照从前往后的顺序。将数组中的元素x依次要查找的进行比较。
二分查找
如果，中的元素是有序的(递增或者递减)，也可以采用二分查找。
优点:比较次数少，查找速度快。
在寻找某特别元素时可以用两种方法
法一:穷举法
法二:筛选法
六、数字方阵
1.定义:数字方阵就是一个行列相等的二维数组，其中每个元素都是数组。
2.解决此类问题的方法有两种:解析法和模拟法。
解析法
解析法就是找出每一个方阵元素f[i][j]与i、j和数组规模n的通项公式,然后直接用两重循环给数组元素赋值,相对比较容易,一般用在初始化等场合。
模拟法
模拟法就是把数字方阵看成一个动态的填数过程,把n²个数依次填入数组中,每填好一个数，就定位好下一个数的位置i和j。
举例
一 蛇形填充数组
#include <iostream>
using namespace std;
int main()
{
int n, i, j, x=1;
int a[10][10]={0};
cin >> n;
for(i=0;i<=2*n-2;i++){
for(j=i;j>=0;j--){
if(j<n&i-j<n){
if(i%2!=0)
a[i-j][j] = x++;
else
a[j][i-j] = x++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++)
cout << a[i][j] << " ";
cout << endl;
}
return 0;
}
感想
一个学期快要结束，c++的学习也快结束。在数组这一节中，感觉难度又加大了一步，不仅需要c++的知识还要用到数学上的知识。
在做类似数字方阵这类习题时很容易忘记某种情况致使程序错误，然后就又要从头开始检查。所以在做题时，我可是学会讲题目内容捋顺然后一点点分析内容，然后到最后对不合适的地方在进行细微的修改。
除了课本上的知识，我们还应在做题或者课下学习新的知识，并且通过做题来巩固。课本上的习题也要多看，因为课本上有许多经典的例题可以在其他的程序中应用。
期末考试快要来临 ，要更认真的学习和复习。
上一篇： 数据挖掘比赛预备知识