《Hello算法》5、创建链表

lugl4313820

《Hello算法》5、创建链表 [复制链接]

 

链表在单片机中也是经常使用的，特别是象在操作系统中，对一个设备初始等，都是使用的链表。

作者对链表的定义如下：

“链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。”

链表的优点就是他的设计可以使得各个节点可以分散存储在内存各处，它们的内存地址无线连续，这跟数组就是最大的区别。

在书有如下图示，非常生动的展示：

 

链表的组成单位节点（node）对象。每个节点都包含两项数据：节点的“值和指向下一节点的”引用“。

链表的首个节点称为”头节点“，最后一个被称为”尾节点“。

尾节点指向的是”NULL“，

在C中语言中，引用”为指针“，即指向存储的地址。

根据书，我创建了测试文件node_test.c内存如下：

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

typedef struct ListNode {
   int val;
   struct ListNode *next;
} ListNode;

ListNode *newListNode(int val) {
   ListNode *node;
   node = (ListNode *) malloc(sizeof(ListNode));
   node->val = val;
   node->next = NULL;
   return node;
}

int main(void)
{
  ListNode* n0 = newListNode(1);
  printf("Node n0 val:%d\r\n\r\n",n0->val);

  free(n0);

  return 0;
}

编译后效如果下：

liujianhuadeiMac:hello_book liujianhua$ gcc node_test.c 
liujianhuadeiMac:hello_book liujianhua$ ./a.out 
Node n0 val:1

可以看到创建一个单链表就是申请一块内存，然后给val 填值，给指针写入null

为了实现多个链接，并把他们接起来，添加代码如下：

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

typedef struct ListNode {
   int val;
   struct ListNode *next;
} ListNode;

ListNode *newListNode(int val) {
   ListNode *node;
   node = (ListNode *) malloc(sizeof(ListNode));
   node->val = val;
   node->next = NULL;
   return node;
}

int main(void)
{
  ListNode* n0 = newListNode(1);
  ListNode* n1 = newListNode(31);
  ListNode* n2 = newListNode(21);
  ListNode* n3 = newListNode(4);
  ListNode* n4 = newListNode(5);
  //构建节点之间的引用
  n0->next = n1;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;

  //打印出所有值
  ListNode *p;
  p = n0;
  while(p)
  {
    printf("Node val: %d \r\n",p->val);
    p = p->next;

  }


  free(n0);
  free(n1);
  free(n2);
  free(n3);
  free(n4);
  printf("free all");
  return 0;
}

编译后输出如下：

liujianhuadeiMac:hello_book liujianhua$ gcc node_test.c 
liujianhuadeiMac:hello_book liujianhua$ ./a.out 
Node val: 1 
Node val: 31 
Node val: 21 
Node val: 4 
Node val: 5 
free all

通以上的试验，我们可以看到，链表的创建相比数组要复杂，访问速也复杂。