（数据结构）C语言求最大值

用图中的这个方法求最大值的话，代码思路是咋样的噢。🤔（数字个数是2的k次方个）

img

线段树

每个节点存最大和次大，比较时是 4 个数比较

底层单独处理一下

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7617189
  • 你也可以参考下这篇文章：实现给定实数的k次方根，基于牛顿法（迭代）实现。（C语言）
  • 除此之外, 这篇博客: 【C语言】实现一个函数，可以左旋字符串中的K个字符中的 解法一： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

    解题思路：

    拿到一组字符串之后，我们首先设置一个临时变量，存放字符串中的第一个字符。
    然后把字符串中的其余字符通过循环依次前移一位，最后再把临时变量的值赋给字符串的最后的一位。

    以上是字符串的一次左旋，要左旋几次就可以通过循环重复以上过程几次就可以了。

    图解如下所示：

    这里写图片描述

    程序源码：

    #include<iostream>
#include<assert.h>
#include<stdio.h>
#include<Windows.h>

using namespace std;

void string_reverse(char* arr, int len){
    assert(arr);
    assert(len > 0);
    char temp;
    temp = arr[0];
    for (int i = 0; i < len - 1; ++i){
        arr[i] = arr[i + 1];
    }
    arr[len - 1] = temp;
}

void Print(char* arr, int len){
    for (int i = 0; i < len; ++i){
        cout << arr[i] << "   ";
    }
    cout << endl;
}

void test(){
    char arr[] = { 'A', 'B', 'C', 'D', '1', '2', '3', '4' };
    //这里用数组来表示字符串，如果用字符串来表示字符串会产生一个错误
    //char *arr = "ABCD1234";
    int count = 0;
    int len = 0;
    len = sizeof(arr) / sizeof(arr[0]);
    //len = strlen(arr);
    Print(arr, len);
    cout << "请输入要左旋的次数：>" << endl;
    cin >> count;
    count %= len;
    while (count--){
        string_reverse(arr, len);
    }
    Print(arr, len);
}

int main(){
    test();
    system("pause");
    return 0;
}

    程序运行结果：

    这里写图片描述

    【注意】

    如果向程序中所标注的直接用字符串来表示的话，会造成以下后果：

    这里写图片描述

    原因：

    我们先来看一个内存分配示意图：
    这里写图片描述

    假如现在执行以下代码：

       int a,b,c,d;
   a=0;
   b=1;
   c=2;
   d=3;

    这里写图片描述

    则a的地址最高，d的地址最低，因为这是一个压栈的过程。

    这里写图片描述

    但是如果执行以下语句的话：

    char arr[] = { 'A', 'B', 'C', 'D', '1', '2', '3', '4' };

    内存分配如图所示：

    这里写图片描述

    这时我们可以发现数组内存放的数据的地址是依次增加的，也就是说开始的元素地址最小，结束的元素地址最大。这是为什么呢？

    原来数组在申请内存的时候不是为他的元素一个个申请内存，而是一次性的把数组所需要的内存申请好，再依次存放数组元素。

    而如果我们在代码中用的是以字符串的形式的话，就会造成问题了：

    char *arr = "ABCD1234";

    这里写图片描述

  • 您还可以看一下 李飞老师的C语言开发之数据结构与算法一课程中的 查找链表中的倒数第k个元素小节, 巩固相关知识点
  • 以下回答来自chatgpt:
    1. 这个图中的方法是用来求最大值的。
    2. 在使用这个方法来求最大值时，需要使用C语言中一些基本的数组操作，比如数组下标访问、元素赋值、元素交换等。
    3. 使用C语言实现这个图表中的方法来求出最大值，可以分为以下几个步骤：
    4. 定义一个包含待查找数组和左右下标的结构体。
    5. 定义一个包含将两个数组合并的函数。
    6. 定义一个包含求解最大值的递归函数。
    7. 最后在主函数中调用递归函数并输出结果。 具体代码实现如下：
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义一个包含待查找数组和左右下标的结构体
struct Data{
    int* array;
    int left;
    int right;
};

//定义一个包含将两个数组合并的函数
void Merge(int* array, int left, int mid, int right) {
    int temp[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (array[i] > array[j]) {
            temp[k++] = array[i++];
        }
        else {
            temp[k++] = array[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = array[i++];
    }
    while (j <= right) {
        temp[k++] = array[j++];
    }
    memcpy(array + left, temp, sizeof(int) * (right - left + 1));
}

//定义一个包含求解最大值的递归函数
int RecurMax(struct Data* data) {
    int left = data->left;
    int right = data->right;
    int* array = data->array;
    if (left == right) {
        return array[left];
    }
    int mid = (left + right) / 2;
    struct Data left_data = { array, left, mid };
    struct Data right_data = { array, mid + 1, right };
    int left_max = RecurMax(&left_data);
    int right_max = RecurMax(&right_data);
    Merge(array, left, mid, right);
    return left_max > right_max ? left_max : right_max;
}

int main() {
    int arr[10] = { 1,2,3,4,5,8,9,6,7,10 };
    struct Data data = { arr, 0, 9 };
    printf("原数组为:\n");
    for (int i = 0; i < 10; ++i) {
        printf("%d\t", arr[i]);
    }
    printf("\n");
    int result = RecurMax(&data);
    printf("最大值为：%d\n", result);
    system("pause");
    return 0;
}

    1. 在使用这个图中的方法来求最大值时，没有数字个数的限制，可以任意输入数字个数，只不过随着数组中数字个数的增多，递归深度也会相应增加，可能会影响程序效率，但理论上并不会影响程序正确性。

    2. 这个方法的实现原理其实就是利用归并排序的思想，在递归的过程中将数组分成两个子数组，并将它们分别通过递归求出最大值，最后对求出的两个最大值进行比较得到最终结果。具体实现过程中，首先定义一个包含待查找数组和左右下标的结构体，然后定义一个包含将两个数组合并的函数，最后定义一个包含求解最大值的递归函数，在递归的过程中，通过该递归函数不断划分数组范围，把相邻的两个子数组进行合并（按照从大到小排序），最终得到的第一个元素即为这组输入数字的最大值，这样迭代到最后，即可得到整个数组中的最大值。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^