打印
[技术问答]

C语言数组的应用

[复制链接]
79|0
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
mikewalpole|  楼主 | 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");
        }
    }
}


使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

34

主题

1414

帖子

0

粉丝