智果芯
服务于百万大学生和电子工程师!

形象生动地讲解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->nextneedDeleteNode表示要删除的节点。代码怎么写呢: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;
}

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

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

赞(0) 打赏
未经允许不得转载:智果芯 » 形象生动地讲解C语言中最重要的部分—链表!

评论 17

  1. #0

    There is visibly a bundle to learn about this. I presume you ensured nice points in features likewise. Damian Banek

    sikis4周前 (09-08)回复
  2. #0

    I think this is among the most vital info for me. And i am glad reading your article. Jamel Hiestand

    adult dating4周前 (09-07)回复
  3. #0

    This is one awesome post. Much thanks again. Awesome. Johnathan Vickerson

    king putin4周前 (09-07)回复
  4. #0

    Article writing is also a fun, iif you know afterward you can write or else it is complex to write. Mel Dorvee

    Loveme4周前 (09-07)回复
  5. #0

    Before playing, make sure you have made your winning target when you want to start the game. Freddy Gouveia

    Loveme4周前 (09-06)回复
  6. #0

    I like it when folks get together and share thoughts. Hubert Kabat

  7. #0

    Great post! We will be linking to this particularly great content on our site. Dario Pangilinan

    Loveme1个月前 (09-04)回复
  8. #0

    Thanks! I work hard to keep itup to date and looking professional. Dante Juhl

    russian viagra1个月前 (09-02)回复
  9. #0

    Hiya very nice blog!! Man .. Beautiful .. Superb .. Greg Peccia

    bitcoin1个月前 (09-02)回复
  10. #0

    Chalk and cheese cheese and wine cheese and wine. Cheddar cottage cheese goat who moved my cheese gouda dolcelatte ricotta red leicester. Sandy Cronquist

    freespin1个月前 (08-28)回复
  11. #0

    I am not sure where you are getting your info, but great topic. Norbert Gaschke

    bahis oyna1个月前 (08-28)回复
  12. #0

    Sweet blog! I found it while surfing around on Yahoo News. Kasey Remsen

    bitcoin1个月前 (08-23)回复
  13. #0

    Really informative blog. Really looking forward to read more. Much obliged. Dusty Cozart

    bahis siteleri1个月前 (08-23)回复
  14. #0

    Pretty! This has been an extremely wonderful article. Wilber Dampeer

    porno2个月前 (08-20)回复
  15. #0

    I love it when individuals come together and share views. Octavio Chiszar

    bahis siteleri2个月前 (08-20)回复
  16. #0

    I conceive you have remarked some very interesting points, regards for the post. Andrea Uknown

    bets10 giris2个月前 (08-19)回复
  17. #0

    Beautifully said. The world needs a lot more of you. Warren Parkison

    freespin2个月前 (08-18)回复

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫打赏

微信扫一扫打赏