C中字符串单向链表的实现

Question

我想制作一个单向链表，每个节点都包含字符串，而不是整数。

但是，我无法实现它。有人可以告诉我实施有什么问题吗？

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

struct node {
  char data;
  struct node* next;
};

struct node* create(struct node* head, const char* data) {
  struct node* newnode, * temp;
  newnode = (struct node*)malloc(sizeof(struct node));
  newnode->data = data;
  newnode->next = NULL;
  if (head == NULL) {
    head = newnode;
    temp = newnode;
  }
  else {
    temp->next = newnode;
    temp = temp->next;
  }
  temp->next = NULL;
  return head;
}

struct node* display(struct node* head) {
  struct node* temp;
  temp = head;
  while (temp != NULL) {
    printf("%d->", temp->data);
    temp = temp->next;
  }
  printf("NULL");
  return head;
}

int main() {
  struct node* head;
  head = NULL;
  int size, i;
  char str[5];
  printf("\nSize of linked list you want: ");
  scanf("%d", &size);
  for (i = 0; i < size; i++) {
    gets(str);
    head = create(head, str);
  }
  display(head);
  return 0;
}

Answer 1

char data 包含一个字符。那不是你想要的，对吧？您想要保存一个 字符串 ，即指向第一个字符的指针：

struct node {
  char *data;
  struct node* next;
};

这通过指针保存字符串 - 不清楚您是否希望此指针成为拥有指针（即如果节点消失则字符串也消失）或引用（即其他人拥有该字符串并管理其生命周期）。

还有其他错误，但这是一个很好的起点。并启用来自编译器的所有警告，并理解它们，因为万一你的代码，它们中的大多数实际上是 C 语言允许的错误（因为它不能确定你真正想要的是什么）——但事实并非如此表示代码正确。

保存字符串的另一种方法可能是按值，即不是像您在回答中那样只有一个字符，您可以保存这些字符的数组 - 。在通过指针拥有字符串还是将其作为值拥有之间的选择在介绍性教学代码中并不重要，在这些代码中您不会在实际用例中衡量数据结构的性能。所以没有“一个真正的选择”：每个选择在某些用例中都有好处。

一些模糊的建议（总是以测量为准！）可能是：

如果值是常量，则按值将字符串保持为固定大小或可变大小通常会在性能上获胜
如果值的大小范围很小（例如，所有字符串都是“短”），那么拥有固定大小的节点并将其分配到连续的内存池中可能会提高性能
如果值发生变化，那么按值保存字符串并不总是可行的：节点可能需要重新分配以调整它的大小，然后你需要一个双向链表来调整为指针相邻节点的数量以反映节点的新地址
最通用但性能可能最差的选项是通过拥有指针保存字符串，因此节点可以保持在固定地址，但字符串可以移动；在这种情况下，如果有很多小字符串，小字符串优化可能会进一步改善：如果字符串适合节点，则将其保存在节点的固定大小 char 数组中，否则将其分配到单独的内存块中；这就是 std::string 的实现中通常所做的，它提高了性能。想法是，由于字符串“大”，因此与使用该字符串的实际值完成的任何工作相比，必须引用其他地址以获取其数据的开销将是微不足道的。

Answer 2

有几个问题：

您的结构中需要一个 char 数组，而不是 c char
create函数过于复杂且错误

OTOH 你的 display 函数是正确的。

你想要这个：

解释看评论。

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXSTRINGSIZE 100                  // maximum allowed size of strings

struct node {
  char data[MAXSTRINGSIZE];                // we need an array of char her, not a char
  struct node* next;
};

struct node* create(struct node* head, const char* data) {
  struct node* newnode = malloc(sizeof(struct node));   // no cast is needed with malloc
  strcpy(newnode->data, data);             // copy the string

  newnode->next = head;  
  return newnode;
}

struct node* display(struct node* head) {
  struct node* temp;
  temp = head;
  while (temp != NULL) {
    printf("%s->", temp->data);
    temp = temp->next;
  }

  printf("NULL");
  return head;
}

int main() {
  struct node* head;
  head = NULL;
  int size;
  char str[MAXSTRINGSIZE];
  printf("\nSize of linked list you want: ");
  scanf("%d", &size);

  getchar();             // absorb \n, scanf and gets don't mix well

  for (int i = 0; i < size; i++) {
    gets(str);
    head = create(head, str);
  }

  display(head);
  return 0;
}

备注

您可以使用一个指针并仅分配存储字符串所需的内存量，而不是在您的结构中使用固定大小的 data 成员。我让你自己想办法。
而不是 gets 这是一个已弃用的函数，您应该使用 fgets。阅读 this 了解更多信息。

C中字符串单向链表的实现

Implementation of a string singly linked list in C

c

linked-list

data-structures

singly-linked-list