13

我正在编写一个合并排序函数，现在我只是在使用一个测试用例数组（没有输入 - 现在是静态的）。我不知道如何将数组作为参数传递。这是我现在的代码：

//merge sort first attempt

#include <iostream>

#include <algorithm>

#include <vector>

int mergeSort(int[]);
int main() {
    int originalarray[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    mergeSort(originalarray[]);
}

int mergeSort(int[] originalarray) {
    int num = (sizeof(originalarray) / sizeof(int));
    std::vector < int > original(num);

    if (num > 2) {
        return num;
    }

    // Fill the array using the elements of originalarray
    // This is just for demonstration, normally original will be a parameter,
    // so you won't be filling it up with anything.
    std::copy(originalarray, originalarray + num, original.begin());

    // Create farray and sarray of the appropriate size
    std::vector < int > farray(num / 2);
    std::vector < int > sarray(num - farray.size());

    // Fill those using elements from original
    std::copy(original.begin(), original.begin() + farray.size(), farray.begin());
    std::copy(original.begin() + farray.size(), original.end(), sarray.begin());

    mergeSort(farray);
    mergeSort(sarray);
}

请注意，此 mergeSort 函数不起作用，因为我还没有弄清楚如何合并它们（这是我的任务）。我想在处理它之前对我的两个向量进行排序，但我无法编译它，因为我需要将数组作为参数传递。我不明白指针，所以如果这是解决方案，我的借口是无知。我现在正在学习编程，以 C++ 作为第一语言，并且只对语言的特性有一个基本的掌握。谢谢您的帮助。

4

7 回答 7

33

只是为了扩展一点，请记住 C++ 数组正是C 数组。所以你所拥有的只是一块内存的地址，它声称（没有保证）是一个数组。

更新

好的，我们将再扩展一点。

C（以及因此 C++）实际上并没有这样的“数组”。它只有地址，指针。所以当你把某个东西变成一个“数组”时，真正发生的是你告诉编译器某个变量代表一个地址。

在 C 中区分声明和定义是很有用的。在声明中，您只是简单地给某物一个名称和一个类型；在定义中，您实际上分配了空间。

所以，如果我们从定义一个数组开始

int ar[100];

这意味着我们告诉编译器我们想要 100int的空间，我们希望它全部分配在一个块中，我们将使用ar它的名称。sizeof运算符给出类型或对象使用的字节数，因此我们的数组将ar占用 100×sizeof(int)字节。在大多数机器上，这将是 400 字节，但它因机器而异。

如果我们定义一个变量

int * ar_p;   // using '_p' as a reminder this is a pointer

我们正在为将包含地址的变量定义空间。它的大小将是sizeof(int*)，通常是 4 或 8，但在某些机器上可能是 2 到 16 之间的任何值，在某些您不太可能很快遇到的机器上。

数组的名称是ar。编译器将该名称转换为地址，因此我们可以将该地址保存为

ar_p = ar ;     // THIS WORKS

现在，为方便起见，假设我们的数组ar恰好从内存中的位置 1000 开始。

该名称ar没有分配任何空间；它就像一个常数，一个数字。所以，你不能撤销那个任务

ar = ar_p ;     // THIS WON'T WORK

出于同样的原因你不能说

1000 = ar_p ;   // THIS WON'T WORK EITHER

即，您不能更改 1000 的值。（回到 FORTRAN 的早期版本，由于复杂的原因，这个技巧会起作用。这是一个错误。直到您尝试调试一个程序“2”的值为 3。）

C 中的数组始终从零开始，即第一个索引始终为零。任何其他索引只是使用索引计算的地址。所以，ar[0]只是地址 1000 加上 0 字节的偏移量，或者说 1000. ar[1]是 1000 加上大小的 1 倍int，所以下一个int 结束。事实上，这在 C 中总是正确的。

这称为数组引用。

当我们使用语法时，*ar_p我们是在告诉编译器从ar_p. `。

这称为取消引用指针。

如果我们说

ar_p = ar;

然后*ar_p并ar[0]指同一件事。

当我们说ar[0]我们告诉编译器我们想要地址 0 字节的东西时ar。 ar[1]是来自 的地址 1int或 4 个字节ar。所以，*(ar_p+3)指的是同一个东西ar[3]。（我们需要括号，因为我们要先将地址加 3，然后再查看内容。 *ar_p+3将首先获取指向的内容ap_p，然后将其加 3。

问题是，C 不知道或不太关心数组到底有多大。如果我来做ar[365]，编译器会很高兴地生成代码来查看单元格 1000+(365× sizeof(int))。如果它在你的数组中，很好，但如果它只是随机内存，那也很好。C不在乎。

（记住 C 来自电话公司。“我们不在乎；我们不必这样做。我们是电话公司。”）

所以，现在，我们知道了一些规则，我已经把它们移到了这里。将“≡”读作“等同于”或“相同于”。

您可以依赖的：

  • foo(TYPE t[])≡foo(TYPE * t)

由于 C 不知道指针和数组之间的区别，因此您可以声明其中任何一个。当你定义一个函数时，你可以写

void foo(int[] ar){

或者

void foo(int* ar){

并获得完全相同的效果。

  • t[i]≡*(t+i)

这是上面的。任何你可能写的地方ar[i]，你都可以用*(ar+i). （实际上有一个奇怪的案例打破了这一点，但作为初学者你不会遇到它。）

  • 其中TYPE *t,(t+i)将等于tplus处的地址i*sizeof(TYPE)

上面也解释了这一点。当你索引到一个数组时，比如ar[42]，这意味着你想要从起始地址开始的第 42 个。因此，如果您使用int的是 ，那么无论宽度有多宽，您都需要移动超过 42 次int，也就是说sizeof(int)。

现在，这就是 C，而且由于 C++ 被定义为“一种”C，所以它也适用于 C++。除了

  • 除非TYPE是重载operator[]和的用户定义类型operator*。

在 C++ 中，您可以决定要定义一个新类型，其行为与任何其他类型一样，但您可以更改语言执行特定操作的方式。因此，程序员可以决定用他们自己设计的东西“重载”——即替换——数组引用和指针取消引用运算符的默认行为。作为初学者，您不应该很快面对它，但您应该意识到它。

于 2009-04-18T18:24:11.530 回答
19

你不应该那样使用sizeof(originalarray)/sizeof(int)。它仅适用于静态声明的数组（大小在编译时已知）。您必须将大小连同它一起传递。您为什么不直接vector从数组中取出并传递它呢？

旁注：根据经验，请始终注意sizeof将在编译时进行翻译。所以它不可能知道作为参数传递的数组的大小。

于 2009-04-18T18:04:15.633 回答
4

我看到你包括<vector>. 我建议你不要使用数组，只使用vector类。vector 您可以在此处查看如何使用 STL 容器的示例。

于 2009-04-18T18:07:02.990 回答
2

  • 当您将数组传递给函数时，它们会衰减为指向数组第一个元素的指针，尽管有符号。所以，你没有sizeof按预期工作。

  • 传入数组时，最好传入数组大小，这样就知道在哪里停下了。将其添加为附加参数。

于 2009-04-18T18:06:03.930 回答
0

除了上述所有答案，您可能还想查看来自 c-faq.com 的数组问答：http: //c-faq.com/aryptr/index.html

于 2009-04-18T19:42:24.837 回答
0

不幸的是，很难在 C 或 C++ 中准确地完成您想做的事情。你可以像这样传递一个固定大小的数组：

int mergeSort(int originalarray[20])
{
    // do something
}

但是，数组的大小不是由数字定义的，而是由初始化列表中的元素数定义的。

在您的情况下要做的事情（即使这确实是错误的事情）是分两步进行：

int originalarray[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
const size_t arraySize = sizeof originalarray / sizeof originalarray[0];
int mergeSort(int array[arraySize])
{
    // do something
}

太糟糕了，它不会做你需要做的事情：将数组传递给这样的函数会生成数组的副本，而排序的目的是更改原始数组。

实际上，如果不了解“指针”的概念，您将无法再进一步。

你需要开发的功能真的应该是这样的：

int originalarray[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
const size_t arraySize = sizeof originalarray / sizeof originalarray[0];

int mergeSort(int *array, const size_t size)
{
    // do something
}

mergeSort(&(originalArray[0]), arraySize);

换句话说，你传递一个指向第一个元素的指针，以及元素的数量。

或者，您可以处理向量。Vector 将相同的两件事（指向第一个元素的指针和大小）封装在一个称为“对象”的实体中。此外，它还为您管理内存，因此您可以根据需要扩展元素的数量。这是 C++ 的方式。太糟糕了，你不能像数组一样用 {...} 初始化向量。

于 2009-04-18T20:35:05.570 回答
0

看起来您同时使用了动态分配的数组和向量，而我相信仅使用 std::vector 就足够了。

首先，让您的输入数组更改为 std::vector，并用您的输入数据填充它。

int main()
{
   std::vector<int> originalarray;
   for (int data = 1; data <= 10; data++)
   {
      originalarray.push_back(data);
   }
   mergeSort(originaldata);
}

现在重要的是声明您的合并排序函数以引用 std::vector。

int mergeSort(std::vector<int>& originalarray)
{
   // The rest of your code, note that now you are passing 
   // in your array for sorting, so you can continue with your code to split
   // the vector into farray and sarray

   // then call sort on your halves.
   mergeSort(farray);
   mergeSort(sarray);

   // I'm guessing at this point you'd write code to combine your farray sarray, and
   // put it back into originalarray...don't forget to clear original array first!
}

请注意，您似乎没有进行就地排序，因此预计您的排序需要一段时间，因为您要复制大量数据。

于 2009-04-19T03:36:40.440 回答