时间戳

首页 > 解决方案 > C中字符串单链表的实现

c - C中字符串单链表的实现

问题描述

我想在每个节点中创建一个包含字符串而不是整数的单链表。

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

#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;
}

标签： cdata-structureslinked-listsingly-linked-list

解决方案

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

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

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

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

保存字符串的另一种方法可能是按值，即不是像您在答案中那样只有一个字符，而是可以保存一个数组 -请参阅此问题的另一个答案以了解如何做到这一点。通过指针拥有字符串与将其作为值拥有之间的选择在介绍性教学代码中并不重要，因为您不会在实际用例中测量数据结构的性能。所以没有“一个真正的选择”：每一个在某些用例中都有好处。

一些含糊的建议（总是要经过测量！）可能是：

  • 如果值是恒定的，那么按值将字符串保持为固定大小或可变大小通常会在性能上获胜

  • 如果值的大小范围很小（例如，所有字符串都是“短”），那么拥有一个固定大小的节点并将其分配到一个连续的内存池中可能会提高性能

  • 如果值发生变化，那么按值保存字符串并不总是可行的：可能需要重新分配节点以调整其大小，然后您需要一个双向链表来调整相邻节点的指针以反映新地址节点

  • 最通用且可能性能最差的选项是通过拥有指针保存字符串，因此节点可以保持在固定地址，但字符串可以移动；在这种情况下，如果有很多小字符串，小字符串优化可能会进一步改进：将字符串保存在节点的固定大小的 char 数组中（如果适合），否则将其分配在单独的内存块中；这就是通常在实现中所做的std::string，它可以提高性能。想法是，由于字符串是“大”的，因此与使用该字符串的实际值所做的任何工作相比，必须引用其他地址来获取其数据的开销将是微不足道的。

推荐阅读