图文加代码讲解C语言链表

鸣涧

图文加代码讲解C语言链表

摘要：明明我们在之前已经接触了数组，感到数组已经是万能的数据存储位置了。但是，如果我们如果一直在使用比较复杂的数据（也就是比较多的数据时），我们肯定会感到很反感，因为对于数组这种数据结构，在你自己使用之前，一定要对其大小进行一番定义，这样一来，它的存储空间在数据处理过程中显得极为不方便，因为谁也不想对将要处理的数据做一个空间的预算，这是我们每一个程序员都很忌讳的，并且还要让其空间足够大，这样才能满足我们的要求(但是如果分配的太多，难免会浪费内存)。

所以这就是为啥你要用链表，学链表。

链表是一种数据结构，它弥补了数组带来的诸多不便，让我们可以任意为一些数据进行空间的分配，根据需要进行内存单元的开辟。

提到链表就必须要提到一个比较重要的知识点就是指针，因为前后数据要有关联，必须要进行一系列的连接和指向处理，那么扮演这个角色的就是指针，并且，在现在的编程语言中，指针是任何东西都没有办法去替代的。

如果你不太理解指针，我强烈建议你看这一篇文章：手把手教你写单片机的指针。

当然学习链表前，你还要有结构体的基本概念和知识，为啥？因为链表就是通过指针连接的多个结构体。每一个结构体中有一个存放指针的成员变量，并且，这个成员的类型是该结构体类型。每一个链表，都有这个自己的结点，这些结点是结构体的变量，当然，他们也是结构体类型的变量。

如果你不太理解结构体，我强烈建议你看这一篇文章：手把手教你写单片机的结构体。

当你看完理解了指针和结构体，那么如果你想进步学习一下链表，然后再看这篇文章，你一定会有一种恍然大悟的感觉，你会发现，指针、结构体、链表也没有真难。

话不多说，开始：

一、链表1、链表基础知识

我们假设有三个特务，ABC。A的下线是B，B的下线是C。换句话说，就是A有B的地址，B有C的地址。写成代码就是这样：

//注：:如果这个结构体你看不懂，回去补结构体的知识
typedef struct spy
{
char *name;
struct spy *next;
}spy, *p_spy;

spy A = {"A", NULL};
spy B = {"B", NULL};
spy C = {"C", NULL};
spy D = {"D", NULL};

int main( void )
{
p_spy pHead = NULL;

A.next = &B;  //A的下线是B
B.next = &C;  //B的下线是C
C.next = NULL;//C没有下线

pHead = &A;
}

画一个图

首先我们定义了三个结构体，ABC。在内存里面就必定有这三个结构体。再看看下面这句话，它会导致什么结果：A.next_addr=&B。

记住上面这个图，结构体A里面的next_address，等于B的地址。那蓝色箭头是我画出来的，只是给我们形象的认识而已，结构体A里面保存有B的地址。链表的核心就是：

这个链表结构体里面有一个指针，这个指针，等于其他结构体的地址。

用人类形象化的话来说，就是结构体A里面的某一个指针，指向结构体B。

首先作为一个链表，肯定有头部呀，我们怎么来确定这个链表的头部？实际上我们用一个指针来表示链表头，代码如下:

typedef struct spy {
char *name;
struct spy *next;
}spy, *p_spy;
p_spy pHead = NULL;

看一下这段代码，我们定义了三个结构体，还有一个结构体指针。它们都是变量，在内存里面都有对应的空间。

在上面的图里面，在红色方框里，我们用那个指针来表示链表头，现在这个链表头，它的值它是空的，也就是说它里面保存的地址是空的：这是一个空链表。

那么我们怎么往这个链表里面添加一个元素呢？先用一个图来表示，假设把结构体A放到列表里面去：

再看一下插入第一项非常简单，我让这个链表头直接等于结构体A的地址就可以了。我们用箭头来表示，让我们更加形象的去了解这个链表：

在这个图里面加了这个箭头，在代码里面可没有什么箭头，它只是pHead这个变量，它的值等于结构体A的地址。

2、链表的插入

现在再把一个结构体B放入链表。有两种方法，你是放在链表头部？还是放在链表尾部？画出一个图：

链表里面只有元素A，我们可以在A的左边插入这个新的元素B，也可以在A的右边插入这个新的元素B。也就是说，我们可以在链表的头部插入新的节点，也可以在列表的尾部插入新的节点。在图里面，上面那个就是把B插在链表的尾部，下面那个就是把B插在链表的头部。怎么写代码呢？

我们先来看看，把B插在链表的头部：

void InsertNodeToHead(spy newNode）
{
newNode->next_addr = pHead;//新插入节点的下一个节点为空
pHead = newNode; //头结点指向新插入的节点
}

画个图演示一下

在这个图里面，左边是代码，右边是结果。假设一开始的时候先插入结构体A，执行图中标号为2的代码的时候，就是：A.next_addr=pHead等于初始值NULL。执行上图中标号为3的代码的时候，就是：pHead=A的地址。结果在上图里面右边地方，在图里面也写出了标号2、标号3。标号2那里A的next.address等于NULL，标号3那里pHead等于结构体A的地址。

下面我们再来增加第2个元素B，我们在链表的头部插入元素B.

在这个图里面用蓝色的标号，把调用过程给标了出来。在左边是代码，看标号为4的代码，要用这个函数把元素B插入链表。怎么做呢？也分为两步：

• 第1步
  

不是插到头部去吗？那我就让B指向头部

但头部等于A，也实际上就是B指向了A

也就说现在B指向了A，头部也指向了A。

• 第二步：
  

让头部要指向B：

这就是一个完整的插入过程。这个图还要补充一下，让结尾指向NULL

把链表，想成一个手拉着手的队伍，就容易理解了。刚才我们讲的是在链表的头部插入一个元素，那怎么在一个链表的尾部插入一个元素呢？

我们假设这个图里面它有好几个元素，我们在最后面一个元素的右边，再插入新元素

得到的结果如下图：

tmp假设是最后一个元素，B是新元素。

tmp->next.addr=&B;
B.next addr = NULL;

问题的关键在于，我怎么在原来的列表里面找出最后一个元素。

主要是需要定义一个临时节点，然后使用一个while循环：

void insertNodeToTail(p_spy newNode)
{
p_spy  temp;//定义一个临时节点
temp = head;//让头结点指向临时节点
while(temp)//在原来的列表里面找出最后一个元素
{
  if (temp ->next == NULL)//找到了最后一个节点 temp就是最后一个节点
   break;
  else
   temp = temp ->next;
}
temp ->next = newspy;//最后一个节点插入新节点
newspy->next = NULL;//新节点的下一个节点为空，这样就将新节点插入最后了
}

图中红圈处，它的特征是什么：它的next.addr等于NULL。如果不是最后一项的话，我们就取出他右边的那一项：temp = temp -> next.addr。这句话可能有些同学理解起来困难，这里画个图解释一下：

插入尾部的代码

void InsertNodeToTail(p_spy newNode）
{
p_spy  temp;//定义一个临时节点
if(pHead == NULL)//如果链表为空
{
  pHead = newNode;
  newNode->next = NULL;
}
else
{
  temp= pHead ;//让头结点指向临时节点
  while (temp)
  {
   if (temp->next == NULL) //找到了最后一个节点 temp就是最后一个节点
    break;
   else
    temp= temp->next;
  }
  temp->next = newNode;//最后一个节点插入新节点
  newNode->next = NULL;//新节点的下一个节点为空，这样就将新节点插入最后了
}
}
3、链表的删除

在链表中，怎么删除一个元素?

再看这个图，在链表中我们要删除红色方框的这个节点。再想象一下，在一个手牵着手的队伍里面，有一个人要走了，是不是他前面那个人要跟后面那个人牵手？

所以我们要找出前面那个人和后面那个人。假设temp是前面那个人，后面那个人是谁？needDeleteNode->next，needDeleteNode表示要删除的节点。代码怎么写呢：temp->next = 后面的人 = needDeleteNode->next所以关键在于我们怎么找到前面的人：temp。这也比较简单，遍历链表：

void RemoveNode(p_spy needDeleteNode)
{
p_spy temp;//定义一个临时的节点，用来遍历
if (pHead == needDeleteNode)//如果被删除的节点正好是头结点指向的那一个节点
{
  pHead = needDeleteNode->next;//直接让头节点指向被删除节点的下一个节点
  return;//返回
}
else
{
  /* 找出NeedDeleteNode的上一个节点 */
  temp = pHead;//让头结点指向临时节点temp
  while(temp)
  {
   if (temp->next == needDeleteNode)//找到了，要删除的节点就是temp的下一个节点
    break;
   else
    temp= temp->next;//继续找
  }  
  if (temp)
  {
   temp->next = needDeleteNode-> next;//让被删除的上一个节点temp的下一个节点指向被删除节点的下一个节点，那么就把原来的要删除的节点给从链表中删除了。
  }
}
}

也是一个循环，如果我的下一项就等于你的话，我就是你的前一个。找到之后，就执行这条指令：temp->next=后面的人=needDeleteNode->next。

4、链表的使用/*------------------------1.链表和结点的定义----------------------------*/

/*结点结构体*/
typedef struct LIST_NODE {
    int data;                        /*用于存放结点数据*/
    struct LIST_NODE *pxNext;        /*用于指向下一个结点*/
    struct LIST_NODE *pxPrevious;    /*用于指向上一个结点*/
}ListNode;


/*链表结构体*/
typedef struct LIST {
    unsigned int NumberOfNodes;      /*用于记录链表结点数量*/
    ListNode RootNode;               /*用于作为循环链表的参考点*/
}List;

/*------------------------2.链表和结点的初始化---------------------------*/
/*结点初始化*/
void ListInitialiseItem(ListNode *pxListNode, int value)
{  
pxListNode->data = value;       /*结点数据赋值*/
}

/*链表初始化*/
void ListInitialise(List *pxList)
{
    pxList->RootNode.pxNext = &(pxList->RootNode);     /*由于此时链表中没有结点,第一个结点指向自己*/
    pxList->RootNode.pxPrevious = &(pxList->RootNode); /*由于此时链表中没有结点,第一个结点指向自己*/

    pxList->NumberOfNodes = 1;                         /*链表结点计数初始化为1,也就是只有一个根结点*/     
}

/*------------------------3.1结点插入链表---------------------------*/
void ListInsertEnd(List *pxList, ListNode *pxInsertListNode)
{
    ListNode *pxNextNode = &(pxList->RootNode);                /*插入结点的后结点*/
    ListNode *pxPreviosNode = pxList->RootNode.pxPrevious;     /*插入结点的前结点*/


    pxInsertListNode->pxNext = pxNextNode;                     /*插入结点指向后结点*/
    pxInsertListNode->pxPrevious = pxPreviosNode;              /*插入结点指向前结点*/

    pxPreviosNode->pxNext = pxInsertListNode;                  /*前结点指向插入结点*/   
    pxNextNode->pxPrevious = pxInsertListNode;                 /*后结点指向插入结点*/   

    (pxList->NumberOfNodes)++;                                  /*链表结点计数加1*/
}

/*------------------------3.2链表删除结点---------------------------*/
void ListRemove(List *pxList, ListNode *pxIListToRemove)
{
  ListNode *pxPreviosNode = pxIListToRemove->pxPrevious;     /*删除结点的前结点*/
  ListNode *pxNextNode = pxIListToRemove->pxNext;            /*删除结点的后结点*/

  pxNextNode->pxPrevious = pxPreviosNode;                    /*后结点指向前结点*/
  pxPreviosNode->pxNext = pxNextNode;                        /*前结点指向后结点*/

  (pxList->NumberOfNodes)--;                                 /*链表结点计数减1*/
}


int main(void)
{
/*1.定义链表、结点*/
List      list;         //定义链表
ListNode  list_node1;   //定义结点1
ListNode  list_node2;   //定义结点2

/*2.初始化链表、结点*/
ListInitialise(&list);

ListInitialiseItem(&list_node1, 100);
ListInitialiseItem(&list_node2, 200);

/*3.插入链表*/
ListInsertEnd(&list, &list_node1);
ListInsertEnd(&list, &list_node2);

/*4.删除结点*/
ListRemove(&list, &list_node1);

return 0;
}

首先我们定义了一个结构体ist list。它是一个变量，在内存里面必定有对应的空间。初始化完这个链表之后，它的结果就像上面的图表示的那样。因为这个链表内部有一个根节点，所以把它的节点个数设置为1。这个链表一开始的时候只有一个元素，它的下一个元素是它自己，它的上一个元素也是它自己。这是一个双向的循环链表，双向循环链表稍微复杂一点，但是再怎么复杂，也就是使用两个单向链表组成的。

怎么样？链表是不是也没有那么难？