C语言之单向链表_单向链表的free

一、链表

链表是一种常见的数据结构，它可以动态的进行存储分配，根据需要开辟内存单元与释放内存单元，链表中的元素通常由两部份组成：数据域和指针域。

数据域用于存储数据，指针域用于节点的连接。

链表结构如下图所示：链表第一个节点是头指针，每个节点都都包含这数据域与指针域，每个节点与其下一个节点都是通过指针域进行相连的，且最后一个节点的指针域指向NULL。

二、单向链表基本操作

首先我们看看链表元素的数据结构：

typedef struct _Link_t
{
  int data;                //数据域的数据
  struct _Link_t *next;    //指向下一个节点的指针，指针域
 
} LINK_T;

成员data为链表存储的数据，成员next为指向下一个节点的指针。

在这里我们注意到一个点，链表结构中包含指针类型的结构成员，类型为指向相同类型的指针。根据C语言的语法要求，结构体的成员不能是结构体自身类型，即结构体不能自己定义自己，因为这样将会导致一个无穷的递归定义，但结构体成员可以是结构体自身的指针类型，通过指针引用自身这种类型的结构。

2.1创建节点

//data数据域存储的数据
LINK_T *Create_Node(int data)
{
  LINK_T *node;
  node = (LINK_T*)malloc(sizeof(LINK_T));
  if (node == NULL)
  {
    return -1;
  }
  memset(node, 0, sizeof(LINK_T));
  node->next = NULL;
  node->data = data;
  return node;
 
}

需要注意的是，利用malloc申请内存后，系统并不会对内存块自动进行初始化和置零操作，需要我们自己对内存进行置0。

2.2链表插入

从链表头插入：

根据图示，我们很容易分析出，每次有新的节点在链表头插入时，新节点的next将会指向原来head->next所指向的的节点，head->next将会指向新的节点。代码如下图所示

//head头指针
//node需要插入的节点
void Insert_Top(LINK_T *head, LINK_T *node)
{
  LINK_T *p = head;
 
  node->next = p->next;
 
  p->next = node;
 
}

链表尾部插入：

根据图示，我们很容易分析出，每次有新的节点在链表尾部插入时，原来链表最后一个节点的指针域将会指向新节点，新插入节点的指针域将会指向NULL。代码如下：

void Insert_Tail(LINK_T *head, LINK_T *node)
{
  LINK_T *p = head;
 
  while((p->next != NULL) && (p = p->next));    //找到链表最后一个节点
 
  p->next = node;
 
}

由于链表的结构决定了每个节点只能找到其下一个节点，所以在对链表节点查询时，只能使用轮询的方式一个一个查询。

 

2.3节点的删除

根据图示，我们很容易分析出，每次删除节点后，被删除节点的上一个节点将会指向被删除节点的下一个节点。需要注意的是，我们需要使用轮询的方式找到需要删除的节点，代码如下：

//head 头指针
//num 需要删除的节点号
void Delete_Node(LINK_T *head, int num)
{
  int i = 0;
  LINK_T *p = head;
  LINK_T *t;
 
  while((i++ < (num - 1)) && (p = p->next));//找到需要删除节点的上一个节点
	
  t = p->next;                              //需要删除的节点
  p->next = p->next->next;                  //将节点从链表中释放出来
	
  free(t);                                  //释放被删除节点的内存块
 
}

2.4链表的遍历

该部分直接看程序分析，链表需要注意的点在于需要提供头指针，且最后一个节点的指针域指向NULL，以及遍历的时候只能挨个轮询。

void Traverse_P(LINK_T *head)
{
 
  LINK_T *p = head;
 
  do
  {
    printf("%d  ", p->data);
  }
  while((NULL != p->next) && (p = p->next));
 
  printf("\n");
 
}

三、基本例程

例程功能实现，先将数组data的数据按序存到每个节点中，然后遍历并且打印，再删除第5个节点，然后再变量打印一次链表以验证各调用函数的正确性。

在该程序中，头指针的数据域的数据代表链表的节点数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
typedef struct _Link_t
{
  int data;
  struct _Link_t *next;
} LINK_T;
 
 
LINK_T *Create_Node(int data);               //创建节点
void Insert_Tail(LINK_T *head, LINK_T *node);//尾插入节点
void Insert_Top(LINK_T *head, LINK_T *node); //头插入节点
void Traverse_P(LINK_T *head);               //正序遍历
void Delete_Node(LINK_T *head, int num);     //删除节点
 
 
int main(int argc, const char *argv[])
{
  int i = 0;
  int data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
 
  LINK_T *head;                              //创建头指针
  head = (LINK_T*)malloc(sizeof(LINK_T));   
  memset(head, 0, sizeof(LINK_T));
 
  for (i = 0; i < 10; i++)                  //创建节点并插入链表           
  {
    Insert_Tail(head, Create_Node(data[i]));
    head->data++;
  }
 
  Traverse_P(head);                        //遍历并打印链表
 
  Delete_Node(head, 5);                    //删除第5个节点
 
  Traverse_P(head);                        //遍历并打印链表
  return 0;
}
 
//data 节点数据域存储的数据
LINK_T *Create_Node(int data)
{
  LINK_T *node;
  node = (LINK_T*)malloc(sizeof(LINK_T));
  memset(node, 0, sizeof(LINK_T));
  node->next = NULL;
  node->data = data;
  return node;
 
}
 
//head 链表头指针
//node 需要插入的节点
void Insert_Tail(LINK_T *head, LINK_T *node)
{
  LINK_T *p = head;
 
  while((p->next != NULL) && (p = p->next));
 
  p->next = node;
 
}
 
 
//head 链表头指针
//node 需要插入的节点
void Insert_Top(LINK_T *head, LINK_T *node)
{
  LINK_T *p = head;
 
  node->next = p->next;
 
  p->next = node;
 
}
 
//head 链表头指针
void Traverse_P(LINK_T *head) 
{
 
  LINK_T *p = head;
 
  do
  {
    printf("%d  ", p->data);
  }
  while((NULL != p->next) && (p = p->next));
 
  printf("\n");
 
}
 
//head 头指针
//num 需要删除的节点号
void Delete_Node(LINK_T *head, int num)
{
  int i = 0;
  LINK_T *p = head;
  LINK_T *t;
  while((i++ < (num - 1)) && (p = p->next));//找到需要删除节点的上一个节点
	
  t = p->next;                              //需要删除的节点
  p->next = p->next->next;                  //将节点从链表中释放出来
  head->data--;                             //节点数减一
  free(t);                                  //释放被删除节点的内存块
 
}

程序运行结果为：

10  1  2  3  4  5  6  7  8  9  10  
9  1  2  3  4  6  7  8  9  10  

结果和程序所需实现功能相匹配，头指针数据域代表节点数，程序先创建10个节点，并且数据域的数据按照data数组依次赋值，遍历并打印链表，删除第5个节点，然后再遍历并打印链表。

 

仓促成文，不当之处，尚祈方家和读者批评指正。联系邮箱1772348223@qq.com