第五章 数组
数组的概念：一组相同类型数据的集合，数组中的所有元素都只能是同一个类型的，数组中的元素在内存中的空间是连续的，数组的定义、数组元素的引用和数组的初始化看书或者课件
容易错的地方：
? 数组的定义语句如：int a[10]是定义了10个整型元素的数组，表示一共有a[0]----a[9]10个元素，切记Tc中元素的下标是从0开始，所以最后一个元素的下标是9而不是10！！！！！
? 只有定义语句Int a[10] 时，表示定义了一个数组，数组名为a，一共有10个元素，其他任何地方出现a[i]都表示一个元素的引用！！！
（一）一维数组
主要算法：
1. 数组元素的遍历：数组元素的输入输出，如果a数组中数组元素有n个，那么数组元素的引用是从a[0]----a[n-1],我们的思想是通过一个变量i从0循环到n-1，那么a[i]就可以表示a[0]到a[n-1]一共n个元素了
main()
{ int a[10],i;
for(i=0;i<10;i++) /*变量i做下标，取值0～9,分别表示对第一个元素a[0]到最后一个 scanf(“%d”,&a[i]); 元素a[9]进行赋值*/
printf(“\n”);
for(i=0;i<10;i++)
printf(“%5d”,a[i]);/*从头到尾输出数组的每一个元素*/
printf(“\n”);
}
2. 从一个数组中到处最大值和最小值：算法思想是用一个变量max表示存储
最大值，那么给max赋初值为a[0],即从第一个开始，假设第一个元素是当前最大的，然后遍历数组中的每一个元素，每一个元素都跟max进行比较，如果有比max大的则修改max的值，求最小值的思路跟最大值类似。 main()
{ int i,n;
float a[10],max,min;
printf(“input data numbers:”);
for(i=0;i<10;i++)
scanf(“%f”,&a[i]);
max=min=a[0]; /*设最大数和最小数都为a[0]*/
for(i=1;i<10;i++)
{ if(a[i]>max) max=a[i];
if(a[i]<min) min=a[i];
}
printf(“\nmax=%f,min=%f\n”,max，min);
}
3. 数组元素的逆序存放，int a[5]=｛15，6，7，8，19｝,比如数组中一共有五
个元素，要求对该数组进行逆序存放即变成数组的存储顺序为19，8，7，7，15，分析这个问题的算法，要实现逆序存放，即把第一个数跟最后一个数进行交换，第二个数跟第四个数进行交换即a[0]------a[4],a[1]----a[2]这两对进行交换，也就是5个数只需要交换2次，如果是6个数则需要交换3次，也就是如果是n个数只需要交换n/2次，每次进行交换的时候，a[0]与a[4],a[1]与a[3]，发现其规律是a[i]与a[4-i]进行交换，也就是a[i]与a[n-1-i]进行交换，所以i是从0开始，一直到n/2-1为止。
main()
{ int i,t;
int a[5]= ｛15，6，7，8，19｝;
for(i=0;i<2;i++)
{ t=a[i];a[i]=a[4-i];a[4-i]=t;
}
for(i=0;i<5;i++) printf(“%3d”,a[i]);
}
4. 直接选择排序算法：如果有一个数组，int a[5]={5,2,6,1,4},
要给这五个数进行从小到大的排序， 也就是a[0]中要存放最小的，a[1]中存放次小的?? 那么我们考虑要实现五个数的按顺序排序，步骤应该是一个一个来的，也就是先考虑如何把五个数中最小的放到a[0]，定下一个最小的a[0]之后，再考虑把剩下四个数当中最小的放到a[1]，如此类推，那么五个数我们要定四趟，每一趟定一个数，从a[0]
定到a[3],那么最后当剩下一个数就不用再定了，那每一趟又是怎
么定的呢？我们考虑要把五个数当中最小的放到a[0]中，那直接选择排序的算法思想是把a[0]跟后面的每一个数进行比较，也就是从a[1]一直比到a[4], 如果有比a[0]小的那么就进行交换，这样就可以确保比完后a[0]中存放的是五个数当中最小的了，这是第一趟的思路，以此类推，定完a[0]后，要把剩下的四个数当中最小的放在a[1]中，则是把a[1]跟后面的每个数相比，也就是从也就是从a[2]一直比到a[4],这样就可以定下第二小的数，以后的每个数一次类推??
下图是对n个数进行排序时候的比较示意图，如果是n个数，那么需要定n-1趟，从a[0]一直定到a[n-2],第i趟是定下a[i],每趟要定a[i]的时候都是把a[i]与后面的的每一个数进行比较，也就是从a[i+1]到a[n-1]，有比a[i]小的就进行交换，所以一共需要n-1趟，每趟又需要比较多次，用到双重循环，外层循环控制比较的趟数，内层循环控制每一趟比较的次数。
第一趟 定a[0]
a[0]---a[1] a[0]---a[2] …………
a[0]---a[n-1]
第二趟 定a[1]
a[1]---a[2] a[1]---a[3] …………
a[1]---a[n-1]
第三趟 定a[2]
a[2]----a[3] a[2]----a[4] ………… a[1]---a[n-1]
第i趟 定a[i]
a[i]---a[i+1] a[i]---a[i+2] ………… a[i]---a[n-1]
main( )
{ int a[5],i,j,k,t; for(i=0;i<5;i++)
scanf("%d",&a[i]);
for (i=0;i<4;i++) / *外层循环控制趟数，5个数需要4趟，第i趟是定下a[i]*/
{ for(j=i+1;j<5;j++) /*内层循环控制每趟比较的次数,定a[i]时都是从a[i+1]一直比到 if(a[j]<a[i]) 最后一个a[n-1]*/ {t=a[i]; a[i]=a[j]; a[j]=t; } }
for(i=0;i<5;i++) printf("%5d",a[i]); }
5. 冒泡排序的算法：冒泡排序也是对数组中的n个元素进行排序，既然也是排
序，那么肯定也是一个一个数来定的，也就是n个数同样需要定n-1趟，剩下最后一个数的时候就不用定了，只是冒泡排序与前面说的选择排序算法所不同的是它每趟定一个数的时候思路不同，它的思想是将数组中的元素两两进行比较，比如有n个数，则将a[0]----a[1]比，把大的调到后面，再将a[1]—a[2]比，大的调到后面，a[2]---a[3],??一直比到最后一个a[n-2]—a[n-1]进行比较，这样比完一趟后就能确保n个数当中最大的就会沉底，最大的一个肯定会在最后一个数中即a[n-1]中，具体的比较动画看课件第18页PPT，这样定下一个最大的之后再按同样的思路来定次大的??具体比较思路看下图以五个数的数组元素为例：所以冒泡排序的顺序是先定a[4]放最大的数,然后定a[3]放次大的数??一直定到倒数第二个即a[1]为止，剩下最后一个数就不用定了，所以也是n个数需要n-1趟，每一趟定下
一个数，每一趟比较的次数则随着趟数的增加而减少
第一趟
a[0]---a[1]
a[1]---a[2]
a[2]---a[3] 第二趟 a[0]---a[1] a[1]---a[2] a[2]---a[3]
第三趟 a[0]---a[1] a[1]---a[2] 第四趟 a[0]---a[1]
main()
{ int i,j,t,a[5];
for(i=0;i<=4;i++) /*输入5个数*/
scanf(“%d”,&a[i]);
for(j=0;j<=3;j++) /*外层循环控制趟数，n个数需要n-1趟*/
for(i=0;i<=3-j;i++) /*内层循环控制每趟比较的次数，每趟比较的次数随着趟数的增
if(a[i]>a[i+1]) 加而减少*/
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
printf{“the sorted numbers:\n”);
for(i=0;i<=4;i++)
printf(“%d”,a[i]);
}
另外一种考虑方法是第一趟定下a[4],第二趟定下a[3],以此类推，最后一次定下的是a[1],所以也可以把外层循环的变量与每一趟定下的元素下标相关联，则外层循环的写法如下：
for(j=4;j>=1;j--)
{
}
则花括号里面应该是表示第j趟是定下a[j]的，每一趟都是从a[0]开始比到a[j]为止，所以内层循环的下标从0开始，到j-1为止，程序如下：
for(j=4;j>=1;j--)
{
for(i=0;i<=j-1;i++)
if(a[i]>a[i+1])
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
}
6. 数组的插入（具体看课件）：把一个整数x按大小顺序插入已排好序（从小
到大）的数组a中，使得数组仍然有序。则需要三步
（1）找出要插入的位置，把欲插入的数x与数组a中各数逐个比较，当找到第一个比插入数x大的元素a[i]时，该元素之前即为插入位置。
（2）由于数组原先就是连续的，所以需要腾出空的位置，才能进行插入，从数组最后一个元素开始到a[i]元素为止，逐个后移一个单元。
（3）把插入数x赋予元素a[i]即可。如果被插入数比所有的元素值都大则插入最后位置。
main()
{ int i,j,x, a[11]={3,5,7,9,10,12,15,18,22,29};
printf("input number x:");
for(i=0;i<10;i++) /*找出x在数组中的位置a[i]*/ if(x<a[i]) break;
for(j=10;j>=i+1;j--) /*将a[k]到a[9]的数向后移一个单元*/
a[j]=a[j-1];
a[i]=x;
for(i=0;i<=10;i++)
printf("%d ",a[i]);
printf("\n");
}
7、折半查找：在一个已经排好序的数组中查找一个数x，如果找到则输出该数在数组中的下标，如果没有找到则输出-1.在一个数组中查找一个数，最基本的思路是从数组的第一个开始一直往下进行查找，如果找到则终止，如果找到最后一个都没有找到则表示该数组中没有这个数，但是如果该数组已经是排好序的，那我们没有必要从头到尾的进行查找，我们可以通过折半的思路来改进查找的效果，具体查找过程看下图：
折半查找的思路是用三个变量，top、bot分别表示要查找的第一个和最后一个元素的下标，（切记，这里指的是下标）， 每次查找的时候是先进行折半，也就是mid=（top+bot）/2，也就是mid这时候指向的是所查找的所有元素的中间元素，然后把mid指向的元素a[mid]跟要查找的x进行比较，第一次时a[mid]比x大，那么我们可以发现这个数组是从大到小排列的，那么如果a[mid]比x大的话就可以排除数组的上半部分，因为上半部分是比a[mid]更大的数，所以肯定不可能找到，这时候就可以把要查找的范围缩小到mid当前所指向的元素的下一个，它的下标应该是mid+1，也就是可以移动top的指针，top=mid+1，这时候我们所要查找的范围缩小到了一半，那么同样如果a[mid]比x小的话，那么我们可以排除的是数组的下一半，也就是数组中比a[mid]更小的肯定也是找不到这个数的，那么这时候我们可以把范围缩小到mid的上一个元素，它的下标应该是mid-1，这时候应该移动bot的指针也就是bot=mid-1，接下来对新的范围循环进行折半查找，所以在折半查找的算法中我们可以把top跟bot看成是当前还没有查找的所有数的范围，只要还有数还没有查找，那么就要继续进行折半查找，也就是循环的条件是top<=bot。
main()
{int a[15]={100,93,86,84,77,73,68,60,55,51,42,39,31,25,10},key;
/*参数key表示要找的数*/
int top,bottom, mid,result;
/*分别为序列的首元素、末元素、中间元素标识,最终结果*/
scanf(“%d”,&key);
if (key>a[0]||key<a[n-1])
result= -1; /*返回-1表示没找到*/
else
{top = 0; bottom = n-1;
while(top<=bottom)
{mid =(top+bottom)/2; /*取中间元素*/
if(a[mid]==key) /*所查找的数据是否是中间元素*/
｛result= mid;break；｝ /*返回找到的位置*/
else if (a[mid]>key)
top = mid+1;
else
bottom = mid-1; }
if(top>bottom) result= -1; /*返回-1表示没找到*/} }
（二）二维数组
（具体语法和初始化看课件或者书）
二维数组的概念是矩阵，也就是既有行又有列，如果定义int a[3][4],第一维表示行下标，第二维表示列下标，那么表示这个二维数组一共有三行，每一行有四列元素，一共是12个元素，它的元素排列顺序如下图，记住数组元素的下标都是从0开始的，不管是行还是列，所以该数组元素的下标是从a[0][0]到a[2][3]：
a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
二维数组的主要算法思路也是数组元素的遍历，在一维数组中我们只要用一个变量i从0循环到n-1那么a[i]就可以表示这个一维数组的所有元素，那么二维数组我们要想遍历则必须用两个变量，i表示行下标，j表示列下标，那么我们的遍历的顺序是从第一行开始，那么一共有三行，行下标分别是从0到2，每一行又有四列分别是从0到3，所以要想遍历二维数组的每一个元素则必须用到双重循环，以下程序的功能是定义了一个二维数组，那么首先遍历每一个元素对它进行赋值，然后再按数序输出二维数组中的每一个元素。好好理解以下程序中双重循环的变化如何遍历二维数组的元素，
二维数组的输入与输出
main()
{int i,j,a[3][4];
printf("input array numbers:\n")；
for(i=0;i<3;i++) /*数组的行*/
for(j=0;j<4;j++) /*每行中数组的列数变化*/
scanf(“%d”,&a[i][j]);
printf("output array numbers:\n")；
for(i=0;i<3;i++) /*数组的行*/
{ for(j=0;j<4;j++) /*数组的列*/
printf(“%d ”,a[i][j]);
printf(“\n”);
}
}
1. 求二维数组中的最大元素及其下标，这个问题其实主要算法思想也是遍历二维数组中的所有元素，一个一个进行比较
main ( )
{ int a[3][4]={ { 1,2,3,4 } , { 9,8,7,6 } , { -10,10,-5,2 } }, i , j ;
int max , row , cloum ;
max= a[ 0 ][ 0 ];
row=0 ; colum=0 ;
for( i=0; i<3 ;i++ )
for( j=0; j<4; j++ )
if (max<a[ i ][ j ] )
{ max = a[ i ][ j ] ; row = i ; colum=j; }
printf( "max=%d,row=%d,colum=%d\n",max, row , colum);
｝
2. 矩阵转置：所谓转置就时将矩阵的行和列交换。
如:2*3矩阵a: 1, 2, 3 4, 5, 6
转置后的3*2矩阵b2, 5
3, 6
这个问题的主要算法也是对于二维数组中的每一个元素都做一个动作，即：a[i][j]=b[j][i]，所以其实也是遍历二维数组元素的问题
main()
{ int a[2][3]={{1,2,3},{4,5,6}};
int b[3][2],i,j;
for(i=0;i<2;i++)
{ for(j=0;j<3;j++)
{ printf(“%5d”,a[i][j]); b[j][i]=a[i][j]; }
printf(“\n”);
}
for(i=0;i<3;i++)
{ for(j=0;j<2;j++)
printf(“%5d”,b[i][j]);
printf(“\n”);
}
}
3. 求方阵（主）对角线元素之和* * * * * * * * * * * * * * * *
对角线的元素的特点是行下标与列下标相同，也就是a[0][0],a[1][1],a[2][2],a[3][3]即a[i][i]，则对角线的元素表示为a[i][i]，i从0循环到3，单重循环就可以实现，累加即可。
main()
{ int a[4][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16},i, sum=0;
for(i=0;i<4;i++)
sum=sum+ a[i][i] ;
printf(“sum=%d\n”,sum);
}
4.求方阵（主）对角线以上的元素之和，对角线元素是行下标i与列下标j相同，那么对角线以上，则可以考虑对于同一行的元素来说，行下标i不变，但是越往右则列下标j增加，
所以对角线以上的元素的特点是j>=i，那么如果要求对角线以上的元素之和，我们可以这么考虑，遍历二维数组中的每一个元素，但是并不是所有元素都累加，对于每一个元素都要去判断是否在对角线以上，即判断j>=i是否满足，如果满足则累加。
* * * * * * * * * * * * * * * *
main()
{ int a[4][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
int i,j, sum=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(j>=i) sum=sum+a[i][j];
printf(“sum=%d\n”,sum);
}
或者也可以考虑不要遍历每一个元素，直接列下标j就从i开始循环，所以第二种解题方法如下：main()
{ int a[4][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16},i,j, sum=0;
for(i=0;i<4;i++)
for(j=i;j<4;j++)
sum=sum+a[i][j];
printf(“sum=%d\n”,sum);}
? 对角线以下的元素分析与上相同，它们的特点是行下标i>=j（列下标），具体程序自己
考虑。