设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 请使用二分拆入排序,编写函数实现将一个整数int a 插入 ...
返回列表 发新帖
查看: 398|回复: 3

[已解决]请使用二分拆入排序,编写函数实现将一个整数int a 插入到一个升序数组int [6]，让....

[复制链接]
syjcss
发表于 2024-7-18 09:10:14 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
请使用二分拆入排序,编写函数实现将一个整数int a 插入到一个升序数组int [6]，最后使得他依然升序。
#include <stdio.h>

void Insert(int a, int b[], int n)
{
    int left = 0, right = n - 1, mid;
    int i, j;

    // 使用二分查找找到插入位置
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (a > b[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    // 将插入位置及其后面的元素依次向后移动一位
    for (i = n - 1; i >= left; i--)
    {
        b[i + 1] = b[i];
    }

    // 插入新元素
    b[left] = a;
}

int main()
{
    int b[6] = {1, 3, 5, 7, 9};
    int a = 4;
    int n = 5;

    Insert(a, b, n);

    printf("After insertion: ");
    for (int i = 0; i <= n; i++)
    {
        printf("%d ", b[i]);
    }

    return 0;
}
我觉得这个代码可能想简单了，是否需要动态分布内存来完成这个题目，但是我无法写出这个代码。1求帮助
最佳答案
月排行榜 / 总排行榜
行客
2024-7-18 12:44:08
FishC 发表于 2024-7-18 09:10
好的，咱们来一起解决这个问题。你需要实现一个函数，将一个整数 `a` 插入到一个升序数组 `b` 中，并确保插 ...

在上述代码中，确实存在一个问题，那就是数组b的大小是固定的，如果插入操作会导致元素数量超过数组的初始大小，那么直接在原数组中进行插入将会导致越界访问。为了处理这种动态增长的需求，我们可以考虑使用动态内存分配来解决这个问题。
下面是修改后的代码示例，其中使用了realloc&#917610; 函数来重新分配数组的空间：
#include <stdio.h>
#include <stdlib.h>

void Insert(int a, int **b, int *n)
{
    int left = 0, right = *n - 1, mid;
    int i;

    // 使用二分查找找到插入位置
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (a > (*b)[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    // 为新的数组分配空间，增加一个元素的位置
    *b = realloc(*b, sizeof(int) * (*n + 1));
    if (*b == NULL)
    {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }

    // 将插入位置及其后面的元素依次向后移动一位
    for (i = *n; i > left; i--)
    {
        (*b)[i] = (*b)[i - 1];
    }

    // 插入新元素
    (*b)[left] = a;
    (*n)++;
}

int main()
{
    int *b = malloc(5 * sizeof(int));
    if (b == NULL)
    {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    
    *b = 1;
    *(b+1) = 3;
    *(b+2) = 5;
    *(b+3) = 7;
    *(b+4) = 9;
    int a = 4;
    int n = 5;

    Insert(a, &b, &n);

    printf("After insertion: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", b[i]);
    }

    free(b);  // 释放动态分配的内存
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

FishC
发表于 2024-7-18 09:10:37 | 显示全部楼层
好的，咱们来一起解决这个问题。你需要实现一个函数，将一个整数 `a` 插入到一个升序数组 `b` 中，并确保插入后数组仍然有序。这个过程我们可以使用二分查找来找到插入位置，然后移动数组元素并插入新元素。

以下是完整的实现代码：
#include <stdio.h>

void Insert(int a, int b[], int n)
{
    int left = 0, right = n - 1, mid;

    // 使用二分查找找到插入位置
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (b[mid] == a)
        {
            left = mid;
            break;
        }
        else if (b[mid] < a)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    // 将插入位置及其后面的元素依次向后移动一位
    for (int i = n; i > left; i--)
    {
        b[i] = b[i - 1];
    }

    // 插入新元素
    b[left] = a;
}

int main()
{
    int b[] = {1, 3, 5, 7, 9};
    int a = 4;
    int n = sizeof(b) / sizeof(b[0]);

    // 需要将数组的长度增加1以容纳新元素
    int newB[n + 1];
    for (int i = 0; i < n; i++)
    {
        newB[i] = b[i];
    }

    Insert(a, newB, n);

    printf("After insertion: ");
    for (int i = 0; i < n + 1; i++)
    {
        printf("%d ", newB[i]);
    }
    printf("\n");

    return 0;
}

### 解释

1. **二分查找插入位置**：通过 `while (left <= right)` 循环，找出 `a` 应该插入的位置。`mid` 是中间位置，根据 `b[mid]` 和 `a` 的比较，调整 `left` 和 `right` 的值，最终 `left` 会指向应插入的位置。

2. **元素后移**：从数组的最后一个元素开始，依次将每个元素后移一位，直到腾出插入位置。

3. **插入新元素**：将 `a` 插入到正确的位置。

4. **数组扩展**：因为插入操作需要额外的空间，因此在 `main` 函数中，创建了一个新数组 `newB`，长度为原数组长度加1，然后复制原数组的内容。

运行这段代码，你将看到新元素 `4` 被正确地插入到数组中，保持数组的有序性。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

行客
发表于 2024-7-18 12:44:08 | 显示全部楼层    本楼为最佳答案   
FishC 发表于 2024-7-18 09:10
好的，咱们来一起解决这个问题。你需要实现一个函数，将一个整数 `a` 插入到一个升序数组 `b` 中，并确保插 ...

在上述代码中，确实存在一个问题，那就是数组b的大小是固定的，如果插入操作会导致元素数量超过数组的初始大小，那么直接在原数组中进行插入将会导致越界访问。为了处理这种动态增长的需求，我们可以考虑使用动态内存分配来解决这个问题。
下面是修改后的代码示例，其中使用了realloc&#917610; 函数来重新分配数组的空间：
#include <stdio.h>
#include <stdlib.h>

void Insert(int a, int **b, int *n)
{
    int left = 0, right = *n - 1, mid;
    int i;

    // 使用二分查找找到插入位置
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (a > (*b)[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    // 为新的数组分配空间，增加一个元素的位置
    *b = realloc(*b, sizeof(int) * (*n + 1));
    if (*b == NULL)
    {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }

    // 将插入位置及其后面的元素依次向后移动一位
    for (i = *n; i > left; i--)
    {
        (*b)[i] = (*b)[i - 1];
    }

    // 插入新元素
    (*b)[left] = a;
    (*n)++;
}

int main()
{
    int *b = malloc(5 * sizeof(int));
    if (b == NULL)
    {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    
    *b = 1;
    *(b+1) = 3;
    *(b+2) = 5;
    *(b+3) = 7;
    *(b+4) = 9;
    int a = 4;
    int n = 5;

    Insert(a, &b, &n);

    printf("After insertion: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", b[i]);
    }

    free(b);  // 释放动态分配的内存
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-7-18 12:44:31 | 显示全部楼层
行客 发表于 2024-07-18 12:44
在上述代码中，确实存在一个问题，那就是数组b的大小 ...


您提出的改进非常好，下面是修正后的代码，使用动态内存分配来处理数组大小的动态增长问题：
#include <stdio.h>
#include <stdlib.h>

void Insert(int a, int **b, int *n)
{
    int left = 0, right = *n - 1, mid;
    int i;

    // 使用二分查找找到插入位置
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (a > (*b)[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    // 为新的数组分配空间，增加一个元素的位置
    *b = realloc(*b, sizeof(int) * (*n + 1));
    if (*b == NULL)
    {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }

    // 将插入位置及其后面的元素依次向后移动一位
    for (i = *n; i > left; i--)
    {
        (*b)[i] = (*b)[i - 1];
    }

    // 插入新元素
    (*b)[left] = a;
    (*n)++;
}

int main()
{
    int *b = malloc(5 * sizeof(int));
    if (b == NULL)
    {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    
    b[0] = 1;
    b[1] = 3;
    b[2] = 5;
    b[3] = 7;
    b[4] = 9;
    int a = 4;
    int n = 5;

    Insert(a, &b, &n);

    printf("After insertion: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", b[i]);
    }
    printf("\n");

    free(b);  // 释放动态分配的内存
    return 0;
}

### 解释
1. **动态内存分配**: `malloc` 用于分配初始数组的内存，`realloc` 用于在需要时增加数组的大小。
2. **二分查找**: 通过二分查找找到需要插入的位置。
3. **数组元素移动**: 从插入位置开始，将数组元素向后移动一位以腾出插入位置。
4. **插入新元素**: 在找到的位置插入新元素。
5. **内存释放**: 使用 `free` 释放动态分配的内存，以避免内存泄漏。

这种方法确保了数组在插入元素后仍然是升序的，并且处理了数组动态增长的问题。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-21 21:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表