0

这些代码之间有什么区别？

1)

struct MyStruct
{
    int num;
} ms[2];

ms[0].num = 5;
ms[1].num = 15;

2)

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = new MyStruct;
ms->num = 5;
ms->next = new MyStruct;
ms->next->num = 15;

一般来说，我可能对链表和列表有点困惑，它们对某些东西特别有用吗？请向我解释更多。

4

6 回答 6

4

你的第一个定义...

struct MyStruct
{
    int num;
} ms[1];

...使用单个元素创建一个静态分配的数组。程序运行时不能更改数组的大小；这个数组永远不会包含一个以上的元素。您可以通过直接索引访问数组中的项目；例如，假设您已经定义了一个适当大小的数组，您ms[5]将获得数组中的第六个元素（请记住，C 和 C++ 数组是 0 索引的，所以第一个元素是）。ms[0]

你的第二个定义...

struct MyStruct
{
    int num;
    MyStruct *next;
};

...创建一个动态分配的链表。此列表的内存在运行时动态分配，并且链表可以在程序的生命周期内增长（或缩小）。与数组不同，您不能直接访问列表中的任何元素；要到达第六个元素，您必须从第一个元素开始，然后迭代 5 次。

于 2012-05-04T19:04:10.833 回答
2

关于代码中的错误，第一个构造了静态数量的 MyStruct 元素并将它们存储在 ms 数组中，因此 ms 是 MyStruct 结构的数组，当然在这里你的意思是它只有 2 个元素，稍后您不能将任何其他元素添加到 ms 数组中，尽管您限制了 MyStruct 元素的数量，而在第二种情况下，当您有一个链表时，您可以链接任意数量的 MyStruct 元素，这将导致动态数字的 MyStruct 元素，第二种情况允许您在运行时添加任意数量的 MyStruct，第二种情况在内存中的概念上应该如下所示：

[ MyStruct#1 ] ----> [ MyStruct#2 ] ----> [ NULL ]

例如，NULL 虽然可能是 MyStruct#3，而第一个：

[ MyStruct#1 ] ----> [ MyStruct#2 ]

就是这样，不能添加 MyStruct#3。

现在让我们看一下您编写的代码：

struct MyStruct
{
    int num;
} ms[1];

ms[1]真的意味着为我创建一个包含一个 MyStruct 元素的 ms 数组。
接下来的代码假设您创建了两个：

ms[0].num = 5;
ms[1].num = 15

因此它应该是：

struct MyStruct
{
    int num;
} ms[2];

它会正常工作！并记住我为它制作的简单插图：
[ MyStruct#1 ] ----> [ MyStruct#2 ]

第二种情况：

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = new MyStruct;
ms->num = 5;
ms->next = new MyStruct;
ms->next->num = 15;

new如果您保存源代码，则此代码使用 C++ 运算符，因为.cpp您将能够编译为 C++ 应用程序而没有错误，而对于 C，语法应更改如下：

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = (MyStruct *) malloc(sizeof MyStruct);
ms->num = 5;
ms->next = (MyStruct *) malloc(sizeof MyStruct);
ms->next->num = 15;

并且不要忘记包含#include <stdlib.h>该功能，您可以在此处malloc()阅读有关此功能的更多信息。 作为第一种情况，回想一下我对链表的说明： 其中 NULL 实际上是 ms->next MyStruct 结构的下一个元素，为了更详细地解释它，请回想一下 ms->next 是 MyStruct 的指针，我们已经分配了它堆中的一个空间，所以现在它指向一个与 MyStruct structure 大小相同的内存块。最后，这里有一个关于何时使用链表以及何时使用数组的Stackoverflow问题，这样您就可以准确了解为什么世界各地的人们有时更喜欢链表而有时更喜欢数组。

[ MyStruct#1 ] ----> [ MyStruct#2 ] ----> [ NULL ]

于 2012-05-04T19:15:06.460 回答
1

哦，我的朋友，有几十种不同类型的数据结构几乎只包含一堆num值或其他什么。程序员不只是对所有事情都使用数组的原因是所需内存量的差异，以及执行对您的特定需求最重要的任何操作的便利性。

链接列表恰好在添加或删除单个项目方面非常快。权衡是在列表中间查找项目相对较慢，并且next指针需要额外的内存。适当大小的数组在内存中非常紧凑，您可以非常快速地访问中间的项目，但要在最后添加新项目，您必须事先知道最大元素数，这通常是不可能的或浪费内存，或重新分配一个更大的数组并复制所有内容，这很慢。

因此，那些不知道他们的列表需要多大，并且大多只需要处理列表开头或结尾的项目或总是循环整个列表的人，并且更关心执行速度而不是保存一个几个字节的内存，很可能会选择链表而不是数组。

于 2012-05-04T19:22:11.477 回答
1

一般来说，列表和数组之间的主要区别：

  • 列表中的排序是明确的；每个元素存储前一个/后一个元素的位置。数组中的排序是隐式的；假定每个元素都有一个前面/后面的元素。请注意，单个列表可能包含多个排序。例如，你可以有类似的东西

    struct dualList {
T data1;
K data2;
struct dualList *nextT;
struct dualList *nextK;
};
    这允许您以两种不同的方式订购同一个列表，一种是 by data1，另一种是 by data2。

  • 相邻的数组元素位于相邻的内存位置；相邻列表元素不必位于相邻位置。

  • 数组提供对其元素的随机访问；列表仅提供顺序访问（即，您必须遍历列表才能找到元素）。

  • 数组（通常）长度固定为1 - 向数组添加元素或从数组中删除元素不会改变数组的大小。列表可以根据需要扩大或缩小。

列表非常适合维护动态变化的值序列，尤其是在值需要保持有序的情况下。它们对于存储需要快速和频繁检索的相对静态数据并不那么热门，因为您无法随机访问元素。

  1. 您可以通过动态声明内存来解决此问题，然后根据需要使用它realloc来调整该内存块的大小，但需要小心完成，并且可能有点像 PITA。
于 2012-05-04T19:26:19.503 回答
0

当元素排序很重要并且事先不知道元素的数量时，链表很有用。此外，访问链表中的元素需要 O(n) 时间。当您在列表中查找元素时，在最坏的情况下，您将不得不查看列表中的每个元素。

对于数组，必须事先知道数量。当你在 C 中定义一个数组时，你必须传递它的大小。另一方面，访问一个数组元素需要 O(1) 时间，因为一个元素可以通过索引来寻址。使用链表，这是不可能的。

但是，这与 C++ 无关，因为链表和数组的概念与 C++ 无关。

于 2012-05-04T19:04:08.593 回答
0

数组是一个连续的预分配内存块，而链表是运行时分配的（malloc）内存块（不一定是连续的）通过指针（*next）相互链接的集合。structs如果您在编译时知道需要存储的最大元素数，则通常会使用数组。structs但是，如果您不知道需要存储的最大元素数，则链接列表很有用。同样对于链表，元素的数量可能会更改、添加和删除元素。

于 2012-05-04T19:10:59.703 回答