C语言——链表的实现

置顶

精

活动

什么是链表？

链表是一种基础的数据结构类型，一种能够动态维护数据的线性数据表。链表的数据以结点形式存储信息，并通过结点之间的指针实现结点之间的衔接。在学习完动态内存分配之后，我们就可以尝试着去使用链表。

单链表存放着两个数据，第一个是链表本身存储的数据，第二个是下一个链表的地址，通过指针的方式去链接下一个链表~

为什么要用链表？

链表和数组类似，但是数组的长度固定并且不能修改，而链表的长度可以由我们自己创建并且数组插入元素时异常麻烦，而链表插入、删除元素就相对简单。

如何实现链表？

在C语言中我们可以使用结构体创建一个链表单位，结构体中包含着两个元素——链表数据、下一个链表的地址。

#include 
#include 
  

struct node {
  int data;
  node* address;
};

  
 

包含标准C语言头文件以及动态内存分配头文件

• 初始化

创建结构体node ，包含我们要存储的数据int 以及node * 下一个链表的地址。

node * NodeInit()
{
  node* head = (node*)malloc(sizeof(node));
  head->address = NULL;
  head->data = 0;
  return head;
}

初始化链表函数，创建一个链表单位。

• 尾插

我们接下来写一个尾部添加元素的函数。

  node* Node_add( node * head , int Data)
{
   node* old = head;
   int number = 0;
   node* new_node = (node*)malloc(sizeof(node));
   new_node->data = Data;
   new_node->address = NULL;
   while((head)->address!=NULL)
   { 
     head = head->address;
     number++;
   }
   head->address = new_node;
   return head;
 }

当末尾不是NULL时，向下迭代，直到搜索到末尾链表，该链表的address指向NULL。

我们创建一个新的链表，让最后一个链表的address指向新链表。这样子就实现在末尾插入链表。

我们可以利用上述的方法实现，这种一个一个向下搜寻的方式叫做迭代

  int Node_Index(node* head,int i)
{
    int number = 0;
    node* adc = (node*)malloc(sizeof(node));
    adc = head;
    while (number < i)
    {
      if (adc->address == NULL)
      {
        return NULL;//溢出
      }
      adc = adc->address;
      number++;
    }
    return adc->data;
  }

• 插入

和上述同理，利用同一种迭代的方法，我们可以在链表的任意位置插入我们想要的数据。

我们只需要断开其中的某个链接，将我们的新链接插入其中，

void Node_Insert(node* head, int index,int Data)
{
   int number = 0;
   node* nenode = (node*)malloc(sizeof(node));
   while (number < index)
   {
     if (head->address == NULL)
     {
       return;//溢出
     }
     head = head->address;
     number++;
   }
   nenode->data = Data;
   nenode->address = head->address;
   head->address = nenode;
 }

相较于数组，链表的插入更节省逻辑，也从侧面强调了，链表是逻辑上的连续，并不是空间上的连续

这样子一个具备插入、索引、尾插、显示的链表就创建完成啦、之后我们可以封装入更多的功能，例如排序、首插等等。也可以扩大数据类型，增加数据内容实现更多的功能！