C语言数组的应用-学习十五
C语言数组的应用-学习十五
2022-02-08 / 0评论 / 293阅读 / 0点赞
-- XG.孤梦

C语言数组的应用-学习十五

XG.孤梦
2022-02-08 / 0 评论 / 293 阅读 / 正在检测是否收录...

数组排序

  • 排序算法是程序设计中最基本的、最重要的算法之一。
  • 排序算法有很多,比较常用的有选择法、冒泡法、比较法和插入法等。

选择排序法

  • 1.从n个数中选出最小数的下标,然后将最小数与第一个数交换位置;
  • 2.除第1个数外,其余n-1个数再按步骤1的方法选出次小的数,与第2个数交换位置;
  • 3.重复步骤n-1遍,最后构成递增序列。
  • 排序过程图

1.png

  • 例如:
#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]);
    }
}

20826-9z1nyjuh0i.png


冒泡排序法

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

a5b9469c0a2549aeb736b03c94b8fbfb.gif

  • 例子
#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]);
    }
}

05821-fxyww627hge.png


数组中元素的插入和删除

插入排序子过程的算法(基于有序数组):

  • 假设输入的数为 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]);
    }
}

06395-e3xj3z4zwl8.png


删除排序过程的算法:

  • 假设删除的数为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]);
    }
}

89699-knorzfuoa6r.png


查找

顺序查找思路:

  • 将查找关键值与数组中的元素一一比较,
    若相同,则查找成功,否则查找失败。
  • 例如
#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("没有找到你输入的数字!");
}

12572-53t26hfge9g.png

04484-z7lfuoly4c.png


二分法查找(折半查找)

  • 可大大提高查找的速度,必须是有序数组
  • 查找过程图
    94963-zhek8aciwr.png
  • 例如
#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");
}

60750-en3fvl4bo5m.png

52558-35tvwi95vo.png


二维数组的鞍点

  • 一个元素在该行最大,在该列最小的话,称其为数组的鞍点
  • 思路:

    • 按行求出各行最大的元素位置
    • 某行最大的元素与该元素所在列的所有元素比较,
      判断是否为最小元素,是则是鞍点,否则不是鞍点。
  • 例如:
#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");
    }
}

88027-6g2kxy7nwrk.png

  • 改良版(上面的算法无法判断一些特殊的数组矩阵)
#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");
        }
    }
}

55737-53l3o70c3su.png


数组注意问题

  • 用scanf函数向字符型数组输入数据char a[20];

    • scanf("%s",&a); 错误
    • scanf(%s",a); 正确
  • 用scanf函数向数值型数组输入数据int a[20];

    • scanf("%d",a); 错误
    • scanf(%d",&a); 正确
  • 引用数组元素要用[]

    • int i, a(10);
      for (i=0;i<10;i++) scanf(%d",&a(i)); 错误
    • int i, a(10);
      for (i=0;i<10;i++) scanf(%d",&a[i])); 正确
  • 数组元素可使用的最大下标

    • int i,a[10]={1};
      for(i=1;i<=10;i++) printf(%d",a[i]); 错误
    • int i,a[10]={1};
      for(i=1;i<=9;i++) printf(%d",a[i]); 或者 for(i=1;i<10;i++) printf(%d",a[i]); 正确
  • 二维数据或多维数组的定义和引用

    • int a[4,5]; a[1+2,2+2]=5; 错误
    • int[10]; 正确
  • 误以为数组名代表数组全部元素

    • int a[4]={1,3,5,7},b[4]; b=a;
      char str[4]; str="computer"; 错误
  • 混淆字符字符串的表示形式

    • char sex; sex="M"; 错误
    • char sex; sex= ' M '; 正确

0

评论

博主关闭了所有页面的评论