求助一道数组问题,得用C++的方法解决,要求使用指针或引用?

问题,

已知两个数组有序实现一个方法将他们合并任然有序
void MergeSort( int *pMerge, int *p1, int p1len, int *p2, int p2len )

我的解法

#include <iostream>
#include <stdio.h>
using namespace std;
void Print(int len, int* pTarget) {
    for (int i = 0; i < len; ++i) {
        cout << pTarget[i] << ' ';
    }
    cout << endl;
    delete[] pTarget;
}
int* MergeSort(int* p1, int p1len, int* p2, int p2len) {
    if (p1 == nullptr) {
        return p2;
    }
    if (p2 == nullptr) {
        return p1;
    }
    int* pMerge = new int[p1len + p2len];
    int idMerge = p2len + p1len - 1;
    int ida = p1len - 1;
    int idb = p2len - 1;
    while (idMerge >= 0) {
        if (idb < 0) {
            pMerge[idMerge--] = p1[ida--];
        } else if (ida < 0 || p1[ida] < p2[idb]) {
            pMerge[idMerge--] = p2[idb--];
        } else {
            pMerge[idMerge--] = p1[ida--];
        }
    }
    return pMerge;
}

int main() {
    int n1, n2;
    cin >> n1 >> n2;
    int a[n1], b[n2];
    for (int i = 0; i < n1; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n2; ++i) {
        cin >> b[i];
    }
    cout << endl;
    Print(n1 + n2, MergeSort(a, n1, b, n2));
    return 0;
}
回复
阅读 633
1 个回答

思路是对的,有些细节上的问题,我写注释了。

#include<iostream>
#include<stdio.h>
using namespace std;
  
void MergeSort( int *pMerge, int *p1, int p1len, int *p2, int p2len ){
  // 思路正确:如果 p1 或 p2 有一个是空,则取另一个
  // 但做法不正确,应该是拷贝数组内容,而不是直接赋值,
  // 就算是直接赋值,这里也要用 int*& 或者 int** 才能把赋的值带出去
  // 或者把返回类型改为 int*,直接返回出去
  if(p1 == nullptr ){
    pMerge = p2;
    return;
  }
  if(p2 == nullptr ){
    pMerge = p1;
    return;
  }
  
  // 看样子是逆序处理,不过建议变量取得意义更明确一些
  // ina 和 idb 看起来就是 index,但 strNew 不像……只能从取值分析应该是个 index
  // 建议 strNew 更名为 idTarget,或者 idMerge,简写 idm 也行(简写的话最好写个注释)
  int strNew = p2len + p1len - 1;
  int ida = p1len-1;
  int idb = p2len-1;
  while(strNew >= 0){
    // 这里要把 idb < 0 的判断往前放,一定 idb < 0 了,就不会去比较两个值的大小了
    // 另外在 ida 或者 idb 小于 0 的时候,px[idx] 取值会取错,
    // 你可以试试输出 p1[-1] 和 p2[-1] 看看
    if(p1[ida] >= p2[idb] || idb<0){
      pMerge[strNew--] = p1[ida--];
    }
    else if(p1[ida] < p2[idb] || ida<0){
      pMerge[strNew--] = p2[idb--];
    }
  }
  return;
}
 
int main() 
{
// 这里懒得去手输,所以提前准备好了两组有序的数组。

//   int n1,n2;
//   cin>>n1>>n2;
//  int a[n1],b[n2];
//   for(int i = 0; i<n1; ++i){
//     cin>>a[i];
//   }
//   for(int i=0;i<n2;++i){
//     cin>>b[i];
//   }
  int n1 = 4;
  int n2 = 3;
  int a[n1] = { 1, 3, 5, 7 };
  int b[n2] = { 2, 4, 5 };

  // 确定要在这里空间,而不是在 MergeSort 里去分配?
  // 这里分配空间必须保证大小。对于 MergeSort 来说,它是不清楚 pMerge 的大小的
  // 所以只看 MergeSort 的情况下,会发现存在内存不安全操作的可能性。
  // 注意:如果在 MergeSort 里分配空间,需要用 new 来分配,不能用声明方式分配,
  // 而且理论上,在使用之后需要在合适的地方回收分配的内存
  // (这个简单的程序可以忽略回收这件事,但必须要养成有分配就有回收的思维习惯)
  int c[n1+n2];
  MergeSort(c, a, n1, b,  n2);
  for(int i=0; i<n1+n2; ++i){
    cout<< c[i]<<' ';
  }
}
推荐问题
宣传栏