关于c++合并排序代码调试



#include
using namespace std;
void MergeSort(int a[],int left,int right);
void Merge(int c[],int d[],int l,int m,int r);
void Copy(int a[],int b[],int left,int right);
main()
{
    cout<<"请输入一组数："<int a[4],b[4];
    for(int i=0;i<4;i++)
    cin>>a[i];
    MergeSort(a,0,3);
    for(int i=0;i<4;i++)
    cout<[i]<<" ";
}
void MergeSort(int a[],int left,int right)
{
    if(left//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[4];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}
void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
        if(i>m)
        {
            for(int p=j;p<=r;p++)
            d[k++]=c[p];
        }
        else
        {
            for(int q=i;q<=m;q++)
            d[k++]=c[q];
        }
    }
}
void Copy(int a[],int b[],int left,int right)
{
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
        //cout<
    }
}#include
using namespace std;
void MergeSort(int a[],int left,int right);
void Merge(int c[],int d[],int l,int m,int r);
void Copy(int a[],int b[],int left,int right);
main()
{
    cout<<"请输入一组数："<int a[4],b[4];
    for(int i=0;i<4;i++)
    cin>>a[i];
    MergeSort(a,0,3);
    for(int i=0;i<4;i++)
    cout<[i]<<" ";
}
void MergeSort(int a[],int left,int right)
{
    if(left//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[4];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}
void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
        if(i>m)
        {
            for(int p=j;p<=r;p++)
            d[k++]=c[p];
        }
        else
        {
            for(int q=i;q<=m;q++)
            d[k++]=c[q];
        }
    }
}
void Copy(int a[],int b[],int left,int right)
{
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
        //cout<
    }
}

输入1 3 2 4得1 2 2 4，不知道哪里有问题，猜测是b[]数组定义有问题？

该回答通过自己思路及引用到各个渠道搜索综合及思考,得到内容具体如下：
在Merge函数中，将两个有序数组合并到一个新数组d[]中，但是在合并过程中，两个for循环的条件判断有误。应该将第一个for循环的条件判断改成 j>r，将第二个for循环的条件判断改成 i>m。修改后的代码如下：

void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
    }
    if(j>r)
    {
        for(int p=i;p<=m;p++)
        d[k++]=c[p];
    }
    else
    {
        for(int q=j;q<=r;q++)
        d[k++]=c[q];
    }
}
另外，定义数组b[]的大小应该与数组a[]的大小一致，因此应该将 int b[4] 改为 int b[right-left+1]，即：

void MergeSort(int a[],int left,int right)
{
    if(left<right)//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[right-left+1];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}
修改后的代码如下：

#include<iostream>
using namespace std;

void MergeSort(int a[],int left,int right);
void Merge(int c[],int d[],int l,int m,int r);
void Copy(int a[],int b[],int left,int right);

int main()
{
    cout<<"请输入一组数："<<endl;
    int a[4],b[4];
    for(int i=0;i<4;i++)
        cin>>a[i];
    MergeSort(a,0,3);
    for(int i=0;i<4;i++)
        cout<<a[i]<<" ";
    return 0;
}

void MergeSort(int a[],int left,int right)
{
    if(left<right)//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[right-left+1];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}

void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
    }
    if(j>r)
    {
        for(int p=i;p<=m;p++)
            d[k++]=c[p];
    }
    else
    {
        for(int q=j;q<=r;q++)
            d[k++]=c[q];
    }
}

void Copy(int a[],int b[],int left,int right)
{
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
    }
}

修改后的代码可以正确地对数组进行合并排序。

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢

好问题！！抱歉我也不太懂，你问问chatGPT吧：https://new.quke123.com/
或者问下其他Python群友：https://app.yinxiang.com/fx/13ce6bbd-f36f-4e92-be53-92dd381ed729

这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/250656
这篇博客也不错, 你可以看下解析B+树比B树更加适合做数据库索引的原因
除此之外, 这篇博客: 数据结构之二叉搜索树详解（附C++代码实现查找、插入、删除操作）中的 b、删除节点没有右子树 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

第二种是删除没有右子树的节点A，此时寻找整颗二叉树中序遍历中节点A的下一个节点，稍微复杂一点，需要利用parent指针。找到远祖父节点B，并且使得节点A在远祖父节点B的左子树中！远祖父节点B.value替换到节点A.value后，它自己也需要它的下一个节点来填充。
在这里插入图片描述
备注：\color{red}备注：备注：其实根本不需要进行删除操作，只要寻找到这个节点中序遍历序列的下一个节点，然后直接替换即可。
C++代码实现：

// 在二叉搜索树中插入value，如果二叉树中已经存在则不进行插入（简化处理逻辑）
TreeNode *deleteNode(TreeNode *root, TreeNode *targetPtr) {
    if (targetPtr == NULL || root == NULL) {
        return root;
    }
    if (root == targetPtr && root->right == NULL) {
        // 一、删除的是根节点，并且根节点没有右子树
        // 处理：切断targetPtr与左子树的关联，返回左子树，释放targetPtr
        root = root->left;
        if (root != NULL) {
            root->parent = NULL;
        }
        targetPtr->left = NULL;
        delete targetPtr;
    }
    else if (targetPtr->left == targetPtr->right) {
        // 二、删除的叶节点
        // targetPtr->left == targetPtr->right,只能是同时为NULL
        // 操作：切断parent与targetPtr的关联，返回root，释放targetPtr
        if (targetPtr->parent->left == targetPtr) {
            targetPtr->parent->left = NULL;
        } else {
            targetPtr->parent->right = NULL;
        }
        // 切断targetPtr 与targetPtr->parent的关联
        targetPtr->parent = NULL;
        delete targetPtr;
    } else if (targetPtr->right == NULL) {
        // 三、删除节点右子树为空      需要找到远祖父节点
        TreeNode *pParent = targetPtr;
        // 祖父节点B，并且使得节点targetPtr在远祖父节点B的左子树
        while (pParent->parent != NULL && pParent->parent->right == pParent) {
            pParent = pParent->parent;
        }
        if (pParent->parent == NULL) {
            // 如果targetPtr不存在一个远祖父节点B，使得leftPtr在远祖父B的左子树
            // 操作：只能删除这个节点，并且把左子树放到当前节点的位置
            targetPtr->parent->right = targetPtr->left;
            targetPtr->left->parent = targetPtr->parent;
            // 切断targetPtr与parent、left的关系
            targetPtr->parent = NULL;
            targetPtr->left = NULL;
            delete targetPtr;
        }
        else {
            // 否则pParent->parent->value替换targetPtr->value，再删除pParent->parent（递归）
            targetPtr->value = pParent->parent->value;
            root = deleteNode(root, pParent->parent);
        }
    }
    else {
        // 四、删除节点存在右子树，直接在右子树寻找中序遍历的第一个节点
        TreeNode * leftPtr = targetPtr->right;
        // 一直往left寻找
        while (leftPtr->left != NULL) {
            leftPtr = leftPtr->left;
        }
        // 将leftPtr->value替换到targetPtr->value
        targetPtr->value = leftPtr->value;
        // targetPtr->right就是leftPtr
        if (targetPtr->right == leftPtr) {
            // 将targetPtr->right指向leftPtr右子树
            targetPtr->right = leftPtr->right;
            // 如果targetPtr->right ！= NULL，还需要设置parent
            if (leftPtr->right != NULL) {
                leftPtr->right->parent = targetPtr;
            }
        }
        else {
            // 否则leftPtr->parent与leftPtr切断关系
            leftPtr->parent->left = NULL;
        }
        // 将leftPtr于其parent切断关系并释放
        leftPtr->parent = NULL;
        delete leftPtr;
    }
    return root;
}

TreeNode *deleteNodeByValue(TreeNode *root, int value) {
    // 首先查找value所在的位置
    TreeNode *targetPtr = searchNode(root, value);
    if (targetPtr == NULL) {
        // value都没找到还删除啥...
        return root;
    }
    return deleteNode(root, targetPtr);
}