C语言数组的应用

只看该作者 · 2024-11-13 11:05

数组排序
排序算法是程序设计中最基本的、最重要的算法之一。
排序算法有很多，比较常用的有选择法、冒泡法、比较法和插入法等。
选择排序法
1.从n个数中选出最小数的下标,然后将最小数与第一个数交换位置；
2.除第1个数外，其余n-1个数再按步骤1的方法选出次小的数，与第2个数交换位置；
3.重复步骤n-1遍，最后构成递增序列。
排序过程图

例如：

#include <stdio.h>
#define N 10

void main()
{
int i,j,x,min,a[N];
printf("随机输入10整数：\n");
for (i = 0; i < N; i++) {
      scanf_s("%d", &a[i]);
}

for (i = 0; i < N - 1; i++) {
      min = i;
      for (j = i+1; j < N; j++){
         if (a[j] < a[min]) {
            min = j;
            x = a[i];
            a[i] = a[min];
            a[min] = x;
         }
      }
}
for (i = 0; i < 10; i++) {
      printf("%d,", a[i]);
}
}

冒泡排序法
1.从第一个数开始，与相邻的数比较,若大于该数，则交换位置。
2.一轮排序后,最大数换到了最下面（即小数往上冒,大数往下沉）;
3.除最后一个数外,其他n-1个数按步骤:的方法使次大的数下沉;
4.重复步骤n-1遍，最后构成递增序列。
排序过程图

例子

#include <stdio.h>
#define N 10

main(){
int a[10];
int i,j,t;
printf("输入十个整数:\n");
for (i = 0; i<N; i++) {
      scanf_s("%d", &a[i]);
}

for (j = 0;j < N-1; j++) {
      for (i = 0; i < N -1-j; i++) {
         if (a[i] > a[i + 1])
         {
            t = a[i];
            a[i] = a[i + 1];
            a[i + 1] = t;
         }
      }
}
for (i = 0; i < N; i++) {
      printf("%d，", a[i]);
}
}

数组中元素的插入和删除
插入排序子过程的算法(基于有序数组):
假设输入的数为 a ；
找到 a 应在数组中的位置；
从该位置开始将它及其后面的数依次往后移,将位置腾出；
将 a 放入该位置。
例如

#include <stdio.h>

main(){
int a[11] = {1,3,6,9,14,16,21,33,40,50};
int i,j,x=0;
for (i = 0; i<10; i++) {
      printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要插入的整数：");

scanf_s("%d", &x);
for (i = 0; i <= 10; i++) {
      if (a[i] > x) {
         for (j = 10; j > i; j--) {
            a[j] = a[j - 1];
         }
            a[i] = x;
            break;
      }
}
for (i = 0; i <=10; i++) {
      printf("%d ", a[i]);
}
}

删除排序过程的算法:
假设删除的数为num
找到num应在数组中的位置;
从该位置开始将它后面的数依次往前移即可
例如：

#include <stdio.h>

main(){
int a[11] = {1,3,6,9,14,16,21,33,40,50};
int i,j,num=0;
for (i = 0; i<10; i++) {
      printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要删除的整数：");

scanf_s("%d", &num);
for (i = 0; i < 10; i++) {
      if (a[i] == num) {
         break;
      }
}
for (j = i; j <10; j++) {
         a[j] = a[j + 1];
}
for (i = 0; i <9; i++) {
      printf("%d ", a[i]);
}
}

查找
顺序查找思路:
将查找关键值与数组中的元素一一比较，
  若相同，则查找成功，否则查找失败。
例如

#include <stdio.h>

main() {
int a[11] = { 1,3,6,9,14,16,21,33,40,50 };
int i, j, x = 0,y = 0;
for (i = 0; i < 10; i++) {
      printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要查找的整数：");

scanf_s("%d", &x);
for (i = 0; i <11; i++) {
      if (a[i] == x) {
         y = 1;
         printf("找到数字%d,它的下标是%d", x, i);
         break;
      }
}
if (y == 0) printf("没有找到你输入的数字！");
}

二分法查找(折半查找)
可大大提高查找的速度,必须是有序数组。
查找过程图

例如

#include <stdio.h>

main() {
int a[] = { 1,3,6,9,14,16,21,33,40,50,100};
int i,find=0, mid,x=0, top = 0,bot = 10;
for (i = 0; i <=10; i++) {
      printf("%d ", a[i]);
}
printf("\n");
printf("输入一个要查找的整数：");

scanf_s("%d", &x);
do {
      mid = (top + bot) / 2;
      if (x > a[mid]) top = mid + 1;
      if (x == a[mid]) find = 1;
      if (x < a[mid]) bot = mid - 1;
      printf("%d,%d,%d\n", top, mid, bot);
} while (top <= bot && find == 0);
      if (find == 1)
         printf("找到数字%d\n", x);
      else
         printf("没有找到你输入的数字！\n");
}

二维数组的鞍点
一个元素在该行最大，在该列最小的话,称其为数组的鞍点
思路：
按行求出各行最大的元素位置
某行最大的元素与该元素所在列的所有元素比较，
  判断是否为最小元素，是则是鞍点，否则不是鞍点。
例如：

#include<stdio.h>
#define N 3
#define M 3

main(){
int i, j, k, a[N][M], max, maxj, flag;
printf("请输入数组：\n");
for (i = 0; i < N; i++){
      for (j = 0; j < M; j++){
         scanf_s("%d", &a[i][j]);
      }
}
      printf("\n");
for (i = 0; i < N; i++){
      max = a[i][0];             // 开始时假设a[i][0]最大
      maxj = 0; //将列号0赋给maxj保存
      for (j = 0; j < M; j++){    // 找出第i行中的最大数
         if (a[i][j] > max){
            max = a[i][j];  // 将本行最大的数放在max中
            maxj = j;    // 将最大数所在的列号存放在maxj中
         }
      }
      flag = 1;  // 先假设是鞍点，以flag为1代表
      for (k = 0; k < N; k++){
         if (max > a[k][maxj]){ // 将最大的数和其同列元素相比
            flag = 0;    // 如果max不是同列最小，表示不是鞍点
            continue;
         }
      }
      if (flag){
         printf("a[%d][%d]=%d\n", i, maxj, max); //输出鞍点的值和所在行列号
         break;
      }
}
if (!flag){
      printf("鞍点不存在!\n");
}
}

改良版(上面的算法无法判断一些特殊的数组矩阵)

#include<stdio.h>
#define N 3
#define M 3

main() {
int i, j, k,p, a[N][M], max, maxj, flag=0;
printf("请输入数组：\n");
for (i = 0; i < N; i++) {
      for (j = 0; j < M; j++) {
         scanf_s("%d", &a[i][j]);
      }
}
printf("\n");
for (i = 0; i < N; i++) {
      max = a[i][0];             // 开始时假设a[i][0]最大
      maxj = 0; //将列号0赋给maxj保存
      for (j = 0; j < M; j++) {    // 找出第i行中的最大数
         if (a[i][j] > max) {
            max = a[i][j];  // 将本行最大的数放在max中
         }
      }
      for (j = 0; j < M; j++) { // 检测最大值是否是鞍点
         if (a[i][j] == max) {
            k = j;
            p = 0;
            while (p < N && max <= a[p][k]) {
                  p++;
            }
            if (p == N) {
                  printf("a[%d][%d]=%d\n", i, k, max);
                  flag = 1;
            }
         }
      }
      if (flag == 0) {
         printf("鞍点不存在!\n");
      }
}
}

只看该作者 · 2024-11-19 17:55

排序是最基本的算法