TypechoJoeTheme

日志随记

统计
登录
用户名
密码

扫码登录
/
注册
用户名

此用户名将作为登录时所用的账号

邮箱

XG.孤梦

随风而动,随遇而安......

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

XG.孤梦博 主大佬
2022-02-08
/
0 评论
/
1,629 阅读
/
904 个字
/
百度已收录
02/08
本文最后更新于 2022年08月13日,已超过 783天没有更新。如果文章内容或图片资源失效,请留言反馈,我会及时处理,谢谢!

数组排序

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

选择排序法

  • 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");
        }
    }
}


数组注意问题

  • 用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 '; 正确

学习笔记C语言
朗读
赞(0)
赞赏
感谢您的支持,我会继续努力哒!
版权属于:

日志随记

本文链接:

https://www.xggm.top/archives/392.html(转载时请注明本文出处及文章链接)

评论 (0)
 
登录
X
用户名
密码