8

为什么在 C 中的链表实现中使用指针很重要？

例如：

typedef struct item                                     
{
    type data;
    struct item *next;
} Item;

typedef struct list                                          
    Item *head;
} List;

如果 Ill 在没有指针的情况下使用相同的实现会发生什么？

4

7 回答 7

14

那么你最终会得到这样的东西

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

现在 C 编译器会去尝试找出有多大Item。但由于next嵌入在 中Item，它最终会得到一个像这样的等式

size-of-Item = size-of-type + size-of-Item

这是无限的。因此我们有一个问题。因此，C 需要指针，所以你有

size-of-Item = size-of-type + size-of-pointer

这是关闭的。更有趣的是，即使您使用 Java、Python 或 Haskell 等语言执行此操作，您实际上也是在隐式存储一个指针（他们说引用）来打破循环。他们只是对你隐瞒事实。

于 2013-07-16T12:42:36.333 回答
8

您实际上不需要使用指针来实现公开链表接口的数据结构，但您确实需要它们来提供链表的性能特征。

指针的替代品是什么？好吧，item需要有一些方法来参考下一项。由于各种原因，它无法聚合下一项，其中一个原因是这会使结构“递归”，因此无法实现：

// does not compile -- an item has an item has an item has an item has...
typedef struct item                                     
{
    type data;
    struct item next;
} Item;

您可以做的是拥有一组项目并在此之上实现链表：

Item *storage[100];

typedef struct item                                     
{
    type data;
    int next; // points to the index inside storage of the next item
} Item;

这看起来可行；你可以有一个函数将项目添加到列表中，另一个函数将它们删除：

void add_after(Item *new, Item *existing);
void remove(Item *existing);

这些函数要么existing从数组中删除（注意更新next前一个项目的“指针”）创建一个空槽，要么找到该existing项目并插入new一个空槽storage（更新next到那里）。

这样做的问题是，这使得add_afterandremove操作无法在恒定时间内实现，因为您现在需要搜索数组并在空间不足时重新分配它。

由于恒定时间添加/删除是人们使用链表的原因，这使得非指针方法仅作为智力练习有用。对于真正的列表，使用指针意味着您可以在恒定时间内执行这些操作。

于 2013-07-16T12:43:10.930 回答
4

指针用于动态分配内存。

您可以将列表实现为一个简单的数组，但这意味着您分配了一个连续的内存区域，这对于大型列表来说效率不高。此外，数组更难以 cu 扩展（如果达到最大大小，则必须重新分配它）。

因此，对于大型列表，动态分配是首选，并且对于每个元素，它可以将其分配到任何位置的内存中，无论是否连续，并且您可以轻松扩展它。

此外，您不能存储在struct item另一个中struct item，因为结构尚未定义并且它无法确定结构的大小：

这是无法做到的：

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

因此使用指针是因为在编译结构时可以确定指针的大小（该平台上整数的大小）。

于 2013-07-16T12:45:31.563 回答
4

如果没有指针，每个列表项都包含另一个列表项 ( next)，其中包含另一个列表项。其中又包含另一个列表项。等等。

你最终会得到一个无限大的数据结构，它会使用无限量的内存，这当然是行不通的。

于 2013-07-16T12:42:21.990 回答
3

在 C 中创建列表不需要指针。是否更可取指针列表取决于您的应用程序。人们在有了用语言实现的指针概念之前就使用了链表。有时对某些人来说更容易理解（有指针）。您也不需要包含数据的结构。

一个简单的数组就可以了。你需要：

  • 一个整数数组来保存索引（这类似于指针）。数组内容是-1（表示nil或NULL用指针术语），或者0 .. N-1，表示：链接的下一个元素的数组索引。index-array 的索引表示数据数组中 item 的索引。
  • 一个数组，用于在上面的“列表”中“连接”任何数据。

这就是你所需要的。

一个数组而不是一个指针列表可能有

  • 优势，如果您的数据量没有改变（没有增长）。在这种情况下，优势可能是巨大的。如果您知道将遇到的最大数据数并且可以预先分配数据，那么数组实现将比任何指针链表快得多。特别是，如果您只插入而不需要删除。
  • 否则的缺点。在这种情况下，缺点可能很大。

请在这里阅读。

因此，您的示例将如下所示：

type data[N];  // or: type *data = new type [N];
int links[N];  // or:  int *links = new int [N];

这应该是您从一个简单的测试用例开始所需的全部内容。

于 2013-07-16T12:49:10.470 回答
1

c中指针的重要性

优点：-

  1. 执行速度会很高。

  2. 指针允许我们访问函数外部的变量。

  3. 减少我们代码的大小。

没有指针：-

  1. 代码大小会增加。

  2. 我们无法有效地维护数据。

  3. 在列表中，指针用于指向列表中的下一项。如果未声明指针，则意味着您不能从列表中访问多个项目。

  4. 如果您在运行时动态分配一些内存，那么确实非常需要指针。

于 2013-07-16T12:47:03.667 回答
0

有不止一种“列表”。您展示的实现是“链接列表”。没有指针就没有“链接”，所以我们需要查看其他类型的列表。

所以，首先，如果你只是*从结构定义中删除会发生什么：它不会编译。您可以在另一个结构中包含一个结构，但如果存在递归，则该结构将具有无限大小，这不会发生！

将数组作为列表怎么样：

struct item list[100];

是的，这会起作用，但现在您的列表是固定大小的。

好的，让我们动态分配列表：

struct item *list = malloc(sizeof(struct item));

然后，每次您添加到列表中时，您都必须这样做：

list = realloc(list, newcount * sizeof(struct item));
list[newitem] = blah;

好的，这行得通，但是现在我们经常重新分配内存，这会导致大量的内存副本和效率低下。

另一方面，如果列表很少更新，这会更节省空间，这可能是件好事。

使用数组的另一个缺点是诸如 push、pop、sort、reverse 等操作变得更加昂贵；它们都意味着多个内存副本。

还有其他类型的“列表”，但它们都涉及指针，所以我认为我们可以在这里忽略它们。

于 2013-07-16T12:49:12.153 回答