七、与数值数组有关的常用算法
〃排序：冒泡法/选择法/插入法 〃查找：顺序查找法/折半查找法 〃矩阵运算 1、常用排序算法
①冒泡法（起泡法/气泡法）
有n个杂乱无序的数，要求将这n个数从小到大（或从大到小）排序后输出。 【例一】设n=5。排序示意图如下： 第1轮（i=1） 第2轮（i=2） 第3轮（i=3） 第4轮（i=4） ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ 后面（右边）。 比4次 比3次 比2次 比1次 共需进行n-1=4轮 从第1个开始，两两比较，大者交换到每轮从第1个比到第n-i个 这种排序方法之所以叫“冒泡法”，是因为在排序过程中，较小的数象气泡一样逐渐往前冒（向上冒），大的数逐渐向后沉，最终完成排序。 流程图如下：
将n个数存入数组a中 从第1行到第n-1行 从第1个到第n-i个 前后两个两两比较 大者调到后位 输出排序后的数组a 程序如下：
#define N 5 /*用函数形式编程示例见《试题汇编》【7.63】*/ main()
{ int i,j,t,a[N+1]; for (i=1;i<=N;i++) scanf(\ for (i=1;i<=N-1;i++) for (j=1;j<=N-i;j++) if (a[j]>a[j+1]) {t=a[j];
a[j]=a[j+1]; a[j+1]=t; }
for (i=1;i<=N;i++) printf(\}
②选择法
从算法优化的角度对“冒泡法”进行改进。
冒泡法每一轮都要将数组中的数两两比较,并根据大小交换之——效率低。
选择法改进处：两两比较后并不马上交换，而是找到最小数后记下其下标。在一轮比较完毕后，再将最小的数一次交换到位。——比较次数不变，交换次数减少。
流程图如下：
将n个数存入数组a中 从第1行到第n-1行 设一标志p，设p=i 从第i个到最后一个 前后两个两两比较 小者下标为p值 p=i? Y N
程序如下：(设要求排序的数列为5,10,-7,3,7共5个数，要求升序排列) /*用函数形式编程示例见《试题汇编》【7.64】*/ 法1：从左到右依次从小到大排放 法2：从右到左依次从大到小排放 #define N 5 main()
{ int i,j,t, ,p a[N+1] ={0,5,10,-7,3,7}; for (i=1;i<=N-1;i++) { p=i;
for (j=i+1;j<=N;j++)
if (a[p]>a[j]) p=j; /*改为<号降序*/ { t=a[p];a[p]=a[i]; a[i]=t; } }
for (i=1;i<=N;i++) printf(\printf(\}
} }
for (i=1;i<=N;i++) printf(\printf(\#define N 5 main()
{ int i,j,t,p,a[N+1]={0,5,10,-7,3,7}; for (i=1;i<=N-1;i++) { p=N-i+1;
for (j=1;j<=N-i;j++)
if (a[j]>a[p]) p=j; /*改为<号降序*/ {t=a[p];a[p]=a[N-i+1];a[N-i+1]=t;} 交换a[p]与a[i] 输出排序后的数组a
③插入法（《试题汇编》【6.94】(参看【6.25】)
如果有N个元素，也是要比较N-1轮，但每轮取第i个（i从1开始）元素的值为暂存值m，然后与左边的各数（从j=i-1开始）比较一直到左边第一个(j=0)为止。如果m比左边大，就让左边的值右移，最后将该轮的第i个数插到左边的合适位置（如果它比较大的话）。
注意：第一轮后，左边的数总是从大到小排列的，只有当第i个数大于左边的数时，才会发生交换。
main()
{ int a[5]={4,7,2,5,1}; int i,j,m;
for (i=1;i<5;i++) { m=a[i]; j=i-1;
while (j>=0&&m>a[j]) { a[j+1]=a[j]; j--; }
a[j+1]=m; }
for (i=0;i<5;i++) printf(\ printf(\}
结果：75421（插入排序——降序）
【讨论】如果要求升序（结果为12457）呢？ while (j>=0&&m
2、查找
①顺序查找法（《试题汇编》【6.92】及【6.93】）
②折半查找法（《试题汇编》【6.90】、【6.91】及【7.22】） 前提：数据已按一定规律（升或降序）排列好。
思路：先检索当中的一个数据是否所需，如不是，判断要找的数据在哪一边，缩小范围后再
按同样方法继续检索，直到找到或找遍。
方法：设要找的数为x，n+1个数据已排好序存放在数组a中。
a. 设low=a[0]，high=a[n] b. mid=(low+high)/2
c. if (x==a[mid]) 找到了；
else if (x>a[mid]) 说明x在右边，让low=mid+1； else 说明x在左边，让high=mid-1
d. 重复b和c两步操作，直到x=mid(找到)或low>high(找遍了)为止。
程序：
main()
{ int a[9]={6,12,18,42,44,52,67,94,99}; int low=0,mid,high=8,x; clrscr();
scanf(\
do { mid=(low+high)/2; if (x==a[mid])
{ printf(\ else if(x>a[mid]) low=mid+1; else high=mid-1; } while (low<=high);
if (low>high) printf(\}
3、矩阵运算（《试题汇编》【6.74】、【6.75】、【6.77】、【6.84】、【6.85】及【6.86】等） 【例一】有一3×4矩阵，编程求其元素最大值并输出其行、列号。 main()
{ int i,j,x,y,max;
int a[][4]={3,5,8,1,6,9,7,12,-6}; max=a[0][0]; for (i=0;i<3;i++) 3 5 8 1 for (j=0;j<4;j++)
6 9 7 12
if (a[i][j]>max)
-6 0 0 0 { max=a[i][j];
x=i; y=j; }
printf(\}
结果：max is a[1][3]=12
要点：用两重循环遍历所有元素。
【讨论】如果求最小值？（a[i][j] 【例二】求矩阵a、b乘积，结果存入矩阵c中并按矩阵形式输出。（《试题汇编》【6.85】） 【说明】矩阵相乘的前提：矩阵A（m×p）的列数p=矩阵B（p×n）的行数。 即：C(m×n)=A〃B 要求 a11 a12 ? a1p b11 b12 ? b1n c11 c12 ? c1n A= a21 a22? a2p B= b21 b22? b2n C= c21 c22? c2n ? ? ? bp1 bp2 ? bpn am1 am2 ? amp cm1 cm2 ? cmn pcij?aikbkj其计算公式是： ?k?1 (i=1,2,?,m j=1,2,?,n) 八、字符数组和字符串 1 2 3 4 5 \\0 【字符数组】存放字符（每个数组元素存放一个字符） P89 1、字符数组的定义 如： char a[10]; int a[10]; char a[2][3]; 字符数组——各个元素分别存放一个字符的数组。 字符串—— “??” （字符串常量）以“\\0”结尾 【注意】字符数组与字符串的区别：字符串存放在字符数组中，但字符数组与字符串可以不等长；字符串以“\\0”结尾。即：C语言中无字符串变量，但可用一个字符数组存放字符串；反之，存放在字符数组中的并非都是字符串。 【“\\0”】 “\\0”是指ASCII代码为0的字符。它既不是一个普通的可显示字符，也不是一个具有操作功能的字符，而是一个“空操作”字符。它不进行任何操作，在字符数组中仅作字符串结束标记使用。“\\0”可以用赋值方法赋给一个字符变量或字符型数组中的某个元素，如c[8]= “\\0”。运算时，按0（NULL）看待。如： #include main{ printf(“%d,%d,%d,%d”,NULL,NULL-100,?\\0?,?\\0?-100); } 结果：0，-100，0，-100 2、字符数组的初始化 单字符方式 char a[10]={?A?, ?B?, ?C?, ?D?}; char b[2][3]={ ?A?, ?B?, ?C?, ?D?, ?E?,?F?}; 【注意】如果初值个数小于数组长度，则多余的数组元素自动为空字符（?\\0?） P90 字符串方式 char a[5]={“ABCD”}; char c[ ]=”ABCD”; char a[2][5]={{?A?,?B?,?C?,?\\0?},{?x?,?y?,?\\0?}}; char a[2][5]={“ABC”,”XY”}; 二维数组可以认为由若干个一维数组组成。 【例一】比较以下字符数组长度是否相同： char a[ ]=”ABCD”; (5) char b[ ]= {“ABCD”}; (5) char c[ ]={?A?,?B?,?C?,?D?}; (4) 【例二】下列程序段的运行结果是： （ab） char a[5]={?a?,?b?, ?\\0?,?d?,?\\0?}; printf(“%s”,a); /*如果 printf(“%s”,a+1);结果是b*/ 说明：%s的作用是输出一个字符串，直到遇到?\\0?为止。 注意：在二维数组中，双下标引用——某行某列的某个元素 单下标引用——某行的字符串 【例三】分析以下程序的运行结果： main(){ char word[3][10]; int i; for (i=0;i<3;i++) scanf(\ printf(\}