C程序设计的常用算法

六、查找问题

　　1．①顺序查找法（在一列数中查找某数x）

　　基本思想：一列数放在数组a[1]---a[n]中，待查找的数放在x 中，把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初值为1，使x与a[p]比较，如果x不等于a[p]，则使p=p+1，不断重复这个过程；一旦x等于a[p]则退出循环；另外，如果p大于数组长度，循环也应该停止。（这个过程可由下语句实现）
void main()
{ int a[10],p,x,i;
printf("please input the array:n");
for(i=0;i<10;i++)
scanf("%d",&a);
printf("please input the number you want find:n");
scanf("%d",&x);
printf("n");
p=0;
while(x!=a[p]&&p<10)
p++;
if(p>=10)
printf("the number is not found!n");
else
printf("the number is found the no%d!n",p);
}
思考：将上面程序改写一查找函数Find，若找到则返回下标值，找不到返回-1
②基本思想：一列数放在数组a[1]---a[n]中，待查找的关键值为key，把key与a数组中的元素从头到尾一一进行比较查找，若相同，查找成功，若找不到，则查找失败。(查找子过程如下。index：存放找到元素的下标。)
void main()
{ int a[10],index,x,i;
printf("please input the array:n");
for(i=0;i<10;i++)
scanf("%d",&a);
printf("please input the number you want find:n");
scanf("%d",&x);
printf("n");
index=-1;
for(i=0;i<10;i++)
if(x==a)
{ index=i; break;
}
if(index==-1)
printf("the number is not found!n");
else
printf("the number is found the no%d!n",index);
}

　　2．折半查找法（只能对有序数列进行查找）

　　基本思想：设n个有序数（从小到大）存放在数组a[1]----a[n]中，要查找的数为x。用变量bot、top、mid 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(top+bot)/2，折半查找的算法如下：
（1）x=a(mid)，则已找到退出循环，否则进行下面的判断；
（2）x<a(mid)，x必定落在bot和mid-1的范围之内，即top=mid-1；
（3）x>a(mid)，x必定落在mid+1和top的范围之内，即bot=mid+1；
（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot<=top。
将上面的算法写成如下程序：
void main()
{
int a[10],mid,bot,top,x,i,find;
printf("please input the array:n");
for(i=0;i<10;i++)
scanf("%d",&a);
printf("please input the number you want find:n");
scanf("%d",&x);
printf("n");
bot=0;top=9;find=0;
while(bot<top&&find==0)
{ mid=(top+bot)/2;
if(x==a[mid])
{find=1;break;}
else if(x<a[mid])
top=mid-1;
else
bot=mid+1;
}
if (find==1)
printf("the number is found the no%d!n",mid);
else
printf("the number is not found!n");
}

　　七、插入法

　　把一个数插到有序数列中，插入后数列仍然有序

　　基本思想：n个有序数（从小到大）存放在数组a(1)-a(n)中，要插入的数x。首先确定x插在数组中的位置P；（可由以下语句实现）
#define N 10
void insert(int a[],int x)
{ int p, i;
p=0;
while(x>a[p]&&p<N)
p++;
for(i=N; i>p; i--)
a=a[i-1];
a[p]=x;
}
main()
{ int a[N+1]={1,3,4,7,8,11,13,18,56,78}, x, i;
for(i=0; i<N; i++) printf("%d,", a);
printf("nInput x:");
scanf("%d", &x);
insert(a, x);
for(i=0; i<=N; i++) printf("%d,", a);
printf("n");
}

　　八、矩阵（二维数组）运算

（1）矩阵的加、减运算
C(i,j)=a(i,j)+b(i,j) 加法
C(i,j)=a(i,j)-b(i,j) 减法
（2）矩阵相乘
（矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素）。矩阵C中任一元素 (i=1,2,…,m; j=1,2,…,n)
#define M 2
#define L 4
#define N 3
void mv(int a[M][L], int b[L][N], int c[M][N])
{ int i, j, k;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
{ c[j]=0;
for(k=0; k<L; k++)
c[j]+=a[k]*b[k][j];
}
}
main()
{ int a[M][L]={{1,2,3,4},{1,1,1,1}};
int b[L][N]={{1,1,1},{1,2,1},{2,2,1},{2,3,1}}, c[M][N];
int i, j;
mv(a,b,c);
for(i=0; i<M; i++)
{ for(j=0; j<N; j++)
printf("%4d", c[j]);
printf("n");
}
}
（3）矩阵传置
例:有二维数组a(5,5)，要对它实现转置，可用下面两种方式：
#define N 3
void ch1(int a[N][N])
{ int i, j, t;
for(i=0; i<N; i++)
for(j=i+1; j<N; j++)
{ t=a[j];
a[j]=a[j];
a[j]=t;
}
}
void ch2(int a[N][N])
{ int i, j, t;
for(i=1; i<N; i++)
for(j= 0; j<i; j++)
{ t=a[j];
a[j]=a[j];
a[j]=t;
}
}
main()
{ int a[N][N]={{1,2,3},{4,5,6},{7,8,9}}, i, j;
ch1(a); /*或ch2(a);*/
for(i=0; i<N; i++)
{ for(j=0; j<N; j++)
printf("%4d", a[j]);
printf("n");
}
}
（4）求二维数组中最小元素及其所在的行和列
基本思路同一维数组，可用下面程序段实现（以二维数组a[3][4]为例）：
‘变量max中存放最大值，row,column存放最大值所在行列号
#define N 4
#define M 3
void min(int a[M][N])
{ int min, row, column, i, j;
min=a[0][0];
row=0;
column=0;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
if(a[j]<min)
{ min=a[j];
row=i;
column=j;
}
printf("Min=%dnAt Row%d,Column%dn", min, row, column);
}
main()
{ int a[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}};
min(a);
}