0

我一直有一个问题，我无法调试很长一段时间。我正在尝试通过遵循 Robert Sedgewick 在“C++ 中的算法”一书中的算法来实现没有额外的数组复制步骤的 MergeSort 算法。
算法的简短描述：

递归程序设置为对 b 进行排序，将结果留在 a 中。因此，编写递归调用以将其结果保留在 b 中，我们使用基本的合并程序将这些文件从 b 合并到 a 中。这样，所有数据移动都在合并过程中完成。

问题是我找不到任何逻辑错误，但排序没有正确完成。数据在某处被覆盖，我无法确定是什么逻辑错误导致了这种情况。当程序完成时，数据被排序，但它不再是相同的数据。
例如，输入数组：{ A, Z, W, B, G, C }生成数组：{ A, G, W, W, Z, Z }。

我显然可以看出它一定是某个地方的逻辑错误，但我一直在尝试调试它很长一段时间，我认为一双新的眼睛可能会看到我错过了什么，因为我真的找不到任何东西错误的。

我正在运行的完整代码：

//Here is my complete code that I run and that behaves as specified above.

#include <iostream>
#include <stdlib.h>

using namespace std;

// function to print the array
void print(char * a[],int l, int r)
{ for(int i=l;i<=r;i++) cout << (i+1) << ": " << a[i] << endl; }

static const int M = 1;

void insertion(char** a, int l, int r)
{ int i,j;
  char * temp;
  for(i=1;i<r+1;i++)
  { temp = a[i];
    j = i;
    while((j>0) && strcmp(a[j-1],temp)>0)
    { a[j] = a[j-1];
      j = j - 1; }
     a[j] = temp; } }

//merging a and b into c
void merge(char ** c,char ** a, int N, char ** b, int M)
{ for (int i=0, j=0, k=0; k<(N+M); k++)
  { if(i == N) {c[k] = b[j++]; continue; }
if(j == M) {c[k] = a[i++]; continue; }
c[k] = strcmp(a[i], b[j])<0 ? a[i++] : b[j++]; } }

 void mergesortAux(char ** a, char ** b, int l, int r)
 { if(r-l <= M) { insertion(a, l, r); return; }
   int m = (l+r)/2;
   mergesortAux(b, a, l, m);        //merge sort left
   mergesortAux(b, a, m+1, r);      //merge sort right
   merge(a+l,b+l,m-l+1,b+m+1,r-m);  }       //merge

void mergesort(char ** a,int l, int r, int size)
{ static char ** aux = (char**)malloc(size*sizeof(char*));
  for(int i = l; i<size; i++) aux[i] = a[i];
  mergesortAux(a,aux,l,r); }
 //free(aux); } I removed this piece of code as suggested, I realize it's unnecessary 

int main(int argc, char * argv[]) 
{ int size = 6;
  char **data = (char**)malloc(size*sizeof(char*));
  data[0] = "A";
  data[1] = "Z";
  data[2] = "W";
  data[3] = "B";
  data[4] = "G";
  data[5] = "C";

  print(data,0,size-1);
  printf("---------------------------\n");

  mergesort(data,0,size-1,size);

  printf("---------------------------\n");
  print(data,0,size-1);
  return 0;
}

输出：

1: A
2: Z
3: W
4: B
5: G
6: C
---------------------------
---------------------------
1: A
2: G
3: W
4: W
5: Z
6: Z
4

1 回答 1

2

你的整个代码完全搞砸了。

您将输入数组与输出数组混淆，并试图始终就地排序。你的代码格式很糟糕。你的变量名很糟糕。您正在使用冗余参数（您正在传递size索引范围l和r）。您混淆了索引范围的含义。这段代码有很多问题，我可以在这里描述一整晚。

但是，这里只有最后一个是关键的：

在这一行：

{ if(r-l <= M) { insertion(a, l, r); return; }

您尝试对数组的l部分r进行排序a。但是，该函数中未使用l索引，因此它从包含修改为包含。表明它是正确的索引，但在此方法中用作数组的大小。insertiona0rr

最简单的解决方法是将其更改为：

if(r-l <= M) { insertion(a+l, l, r-l); return; }

但是修复insertion正确处理索引的方法可能是一个更好的主意。

另外，我强烈建议您清理整个代码。这是不可维护的。这是不可读的。这是最黑暗的一面C。我永远无法理解为什么人们不能使用可理解的函数/变量名称，使用结构来表示复合概念并将逻辑划分为小的可读部分。好像写入C迫使您认为您正在设置处理器寄存器中的各个位，并且不能使用长度超过 1 个字符的变量名。

即使是你——这段代码的作者也有理解它的问题。这是一个强烈的建议，它存在一些严重的问题:)

很抱歉让我感到沮丧，我无法抗拒这个谜题，为此浪费了很多时间:)

于 2013-10-20T23:25:28.017 回答