c - 为什么要在链表中声明指针？

Question

我是 C 语言的新手。

学习链表，发现用指针很难理解。

(我理解链表与数组相比的好处。)

假设我有 3 个客户和每个客户的具体值(value)。

struct linknode{
  int data;
  struct linknode *next
}; 

为什么我们像 (case1) 这样使用指针

linknode *a = malloc(sizeof(Node));
linknode *b = malloc(sizeof(Node));
a->value = 1;
b->value = 2;

a->next = b;
b->next = NULL;

只是(case2)怎么样

linknode a, b;
a.value = 1;
b.value = 2;

a.next = &b;
b.next = NULL;

用case 2做链表不行吗？还可以插入、删除吗？

谢谢。

Answer 1

Isn't it possible to make linked list with case 2? also insert, delete being possible?

有可能，只是用处不大。列表的最大大小受限于声明的变量数量，我怀疑您是否会想要声明超过一打的单独变量。

您可以做的是使用一个数组作为您的后备存储——而不是声明单独的变量 a 和 b 您可以声明一个 10、100 或 1000 的数组元素，然后做类似的事情:

a[i].next = &a[j];

但您仍然受到限制 - 您的列表永远不能大于数组。使用动态内存的优点是列表大小不受限制(至少，没有一些固定的编译时限制)；但是，这意味着要弄乱指针。

指针是 C 语言编程的基本组成部分 - 如果不以某种方式使用指针，就无法编写有用的 C 代码。

编辑:更现实的链表实现将使用 insert 函数，例如

/**
 * Inserts items into the list in ascending order.
 *
 * If the list is empty (head is NULL) or if the value
 * of the new node is less than the value of the current
 * head, then the new node becomes the new head of the
 * list.
 *
 * Returns the pointer to the new node.  If the allocation
 * was unsuccessful, it returns NULL.
 */
struct linknode *insert( struct linknode **head, int val )
{
  struct linknode *newnode = calloc( 1, sizeof *newnode );

  if ( !newnode )
    return NULL;

  newnode->data = val;
    
  if ( !*head )    
  {
    /**
     * list is empty, newnode becomes the head of the list.
     */
    *head = newnode;
  }
  else if ( newnode->data < (*head)->data )
  {
    /**
     * Value stored in newnode is less than the
     * value stored at the list head, newnode
     * becomes the new list head.
     */
    newnode->next = *head;
    *head = newnode;
  }
  else
  {
    /**
     * Iterate through the list and insert the 
     * newnode in the correct location. 
     */
    struct linknode *cur = *head;
    while ( cur->next && cur->next->data < newnode->data )
      cur = cur->next;
    newnode->next = cur->next;
    cur->next = newnode;
  }
  return newnode;
} 

它会像这样使用:

int main( void )
{
  struct linknode *list = NULL;
  int val;

  while ( scanf( "%d", &val ) == 1 )
  {
    if ( !insert( &list, val ) )
    { 
      fprintf( stderr, "Could not add %d to list, not taking any more input...\n", val );
      break;
    }
  }
  ...
}

因此列表的元素是动态分配和添加的，您仅受可用内存量的限制。