C语言实现大整数乘法和冒泡排序算法

本文介绍如何使用 C 语言实现大整数乘法和冒泡排序算法。由于 C 语言的整型变量存储空间有限，本文利用一维数组来实现大整数乘法，并使用冒泡排序算法对多个大整数进行排序。

算法原理

大整数乘法：

由于 VC 对整型变量只分配了 4 个字节存储空间，因此需要利用一维数组实现大整数相乘，比如 123456789 * 987654321。

算法提示：举一个简单的例子，就是先不算任何的进位，也就是说，将每一位相乘，相加的结果保存到同一个位置，到最后再计算进位。最后的到的 (18) (25) (8) 转化为：2058。

进一步提示：result[] 数组为的最后一位空置，不可能被占用，我们就响应地把 num1[ ] 的第 i 位与 num2[ ] 的第 j 位相乘，结果应该存放在结果的第 i+j 位上的这个结果往后顺移一位，即放到 result[] 数组第 i+j+1 位，最后从右向左累加时就多了一个空间，以便来存储最高位的进位。

冒泡排序：

冒泡排序是一种简单的排序算法，它通过比较相邻元素的大小，并将较大的元素交换到后面，直到所有元素都排好顺序。

代码实现

#include <stdio.h>
#include <string.h>

#define MAX_LEN 1000 // 最大位数

void multiply(char *num1, char *num2, char *result); // 两个大整数相乘的函数
void bubble_sort(char arr[][MAX_LEN+1], int n); // 冒泡排序函数

int main() {
    int n;
    char arr[100][MAX_LEN+1]; // 存放大整数的二维数组
    char result[MAX_LEN*2+1]; // 存放两个大整数相乘的结果

    scanf('%d', &n); // 输入要排序的大整数个数
    for (int i = 0; i < n; i++) {
        scanf('%s', arr[i]); // 输入每个大整数
    }

    bubble_sort(arr, n); // 冒泡排序

    printf('排序后的结果：\n');
    for (int i = 0; i < n; i++) {
        printf('%s\n', arr[i]); // 输出排序后的结果
    }

    return 0;
}

void multiply(char *num1, char *num2, char *result) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int len = len1 + len2;

    int *temp = new int[len](); // 分配动态数组存放每一位相乘的结果

    for (int i = len1-1; i >= 0; i--) {
        for (int j = len2-1; j >= 0; j--) {
            int mul = (num1[i]-'0') * (num2[j]-'0');
            int sum = mul + temp[i+j+1];
            temp[i+j] += sum / 10;
            temp[i+j+1] = sum % 10;
        }
    }

    int index = 0;
    while (index < len-1 && temp[index] == 0) {
        index++; // 去掉前导零
    }

    for (int i = index; i < len; i++) {
        result[i-index] = temp[i] + '0'; // 转化为字符
    }
    result[len-index] = '\0';

    delete[] temp; // 释放动态数组
}

void bubble_sort(char arr[][MAX_LEN+1], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-1-i; j++) {
            char result1[MAX_LEN*2+1], result2[MAX_LEN*2+1];
            multiply(arr[j], arr[j+1], result1); // 计算相邻两个大整数的乘积
            multiply(arr[j+1], arr[j], result2); // 计算相邻两个大整数的乘积
            if (strcmp(result1, result2) > 0) { // 如果前者大于后者，则交换两个大整数的位置
                char temp[MAX_LEN+1];
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[j+1]);
                strcpy(arr[j+1], temp);
            }
        }
    }
}

总结

本文介绍了如何使用 C 语言实现大整数乘法和冒泡排序算法。代码中使用了动态数组来存储大整数的乘积结果，并通过比较乘积结果的大小来进行排序。该代码简单易懂，可以作为学习 C 语言算法的参考。