menu Alkaid #二进制初学者 / 网络安全 / 大龄CTF退役选手
数据结构之:链表详解
383 浏览 | 2017-10-18 | 分类:数据结构 | 标签:数据结构

链表是 数据结构中很重要的基础 部分,下面 我通过简单的故事来将链表的内容串起来解释一下,同时也是总结一下自己的学习内容:

故事:

某一天,乐乐,丰丰,呆子,星星,领领,小韦6位小朋友带领着8个小朋友一起去山上玩耍。当玩耍过后,天下起了大雨 !!于是 14位小朋友赶紧返回,不幸的是山口处山洪暴发。如果想要 过去,14位 小朋友需要连在一起,单个过河的小朋友会被山洪冲走(因为经过试验证明了这一点,而且小韦在试验过程中被洪水冲走了) 。

我们将每位小朋友看做是一个节点

typedef struct Lnode  
{  
    int data;    //小朋友数据  
    struct Lnode *next;   //指向下一个小朋友的指针  
};

 

建立单链表:

那么要从洪水中过去的话,14位小朋友需要建立一个长队。可以想到,建立长队的方法有两种:

首先我们需要空出来一块场地用来建立我们的长队(所说的建立 一个空链表)

code:

    void InitList(LinkList*&L)  
    {  
        L = (LinkList *)malloc(sizeof(LinkList));  
        L->next = NULL;  
    }

 

第一种:乐乐站在第一个,星星站在乐乐 的前面,呆子站在星星的前面……依次排列,这样乐乐会最终站在队尾(这就是头插法建立单链表)。

1. 2 .3.……丰丰,呆子,星星,乐乐。

code:

    void CreateListH(LinkList *&L, int a[], int n)   //头插法建立单链表  
    {  
        LinkList *s;                            //s是要插入的小朋友  
        int i;  
        L = (LinkList *)malloc(sizeof(LinkList)); //申请空间,  
        L->next = NULL;                          //刚开始的时候为空,因为还没有排队。  
        for (i = 0; i < n; i++)                 //我们将后来的小朋友插入前面,并让这个的小朋友的手拉着站在他后面的小朋友的衣服  
        {  
            s->data = a[i];  
            s->next = L->next;   
            L->next = s;  
        }  
    }

 

第二种:乐乐站在第一个,星星 站在乐乐的后面,呆子站在星星的后面,丰丰站在呆子的后面,……其他人依次后排(这就是尾插法建立单链表)。

乐乐,星星,呆子,丰丰……。

    void  CreateListR(LinkList *&L, int a[], int n)  
    {  
        int i;  
        LinkList *s, *r;  
        L = (LinkList *)malloc(sizeof(LinkList));  //申请空间  
        r = L;  
        for (i = 0; i < n; i++)      // s是要插入的小朋友,r只是一个临时标记,为了知道现在谁在最后的位置  
        {  
            s->data = a[i];  
            r->next = s;            //将 s小朋友插入r的后面,  
            r = s;      //插入后,那么s在最后的位置,让其成为标记。因为我们需要知道谁在最后面,方面下次的插入操作  
        }  
        r->next = L->next;             //队伍建立完成后,最后  队尾节点为 NULL;  
    }  


 

那么现在队伍建立完成了,可以过河了,小朋友们都很高兴(其实 一点都不高兴)。

这个时候小韦竟然回来了,小朋友们都很高兴他还 或活着,选举他当了队长 。由于小韦刚回来 ,对队伍的情况 不是 很了解,他想要知道队伍有多少人,于是他从队伍的头到尾进行了查数:

(单链表中数据 节点 的个数)

code:

int ListLength(LinkList *L)
{
    int ans = 0;
    LinkList *p = L;     //小韦学长找到了队伍头部 
    while (p->next != NULL)   //直到尾部,看到一个小朋友 就ans++;
    {
        ans++;
        p = p->next;
    }
    return ans;
}

 

 

但是 悲剧的是,小韦由于智商有限,只能数到10,就不会数了。于是他想了一个方法,让队伍中的小朋友从头到尾 说出自己的名字、信息:

(输出节点存储的信息):

code:

void CoutList(LinkList *L)
{
    LinkList *p = L->next;  //从 有效节点开始
    while (p != NULL)
    {
        printf("%d", p->data);  //小朋友喊出自己的信息
        p = p->next;          //换下一个小朋友
    }
}

 

 

由于小韦只能数到10,造成队伍中的星星的嘲笑,并给他 起了个外号:小白。站在队伍头部的小韦很是气愤,气愤中的小韦突然就知道怎么数10以后的数字了。于是他查了一下嘲笑他的小朋友的位置,给他起外号报复:

修改某个节点的数据信息 :

code:

bool ChangeInfo(LinkList *&L, int i, int &e)    //小韦查到了星星的位置,想好了外号
{
    int j = 0;
    LinkList *p = L;
    while (j < i && p != NULL)                  //如果是不在数据范围内,说明小韦的数学真的很菜
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        p->data = e;                         //如果找到了i位置上的星星,小韦就把他想好的外号赋予星星
        return true;
    }
}

 

 

由于小韦的行为,使得某个位置上的乐乐表现的很气愤。于是小韦查了乐乐的位置,并行使了队长权利将其踢出了队伍(因为 小韦知道乐乐未来会是一位IT大神,要让乐乐挂掉先)。

删除某个节点:

bool ListDelete(LinkList *&L, int i)    //找到乐乐的位置
{
    int j = 0;
    LinkList *p = L, *q;
    while (j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;
    }
    if (p == NULL)                  //如果找错了,不存在i节点,说明小韦的 数学是体育老师教的,
        return false;
    else
    {
        q = p->next;             //如果找到了乐乐,把乐乐一觉踹出队伍,再让乐乐前面的小朋友的手拉着乐乐后面 的小朋友的衣服
        if (q == NULL)
        {
            return false;
        }
        p->next = q->next;
        free(q);
        return true;
    }
}

 

杂七杂八的事情终于弄完了,于是 小韦也归队。(因为他 不想再单独被冲走了)

插入数据元素:

bool ListInsert(LinkList *&L, int i, int e)  //小韦在某个位置上插入队伍
{
    int j = 0;
    LinkList *p = L, *s;
    while (j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }
}

 

那么 现在开始过河了,由于河水  突然猛涨,小韦学长竟然又被冲走了。小伙伴们需要抓的更紧点,于是它们退回来重新 建队。并将抓衣服的方式 更改了一下:让前一个小朋友的手抓住后一个小朋友的衣服,后一个小朋友的手抓住他前面的小朋友的衣服。即(双链表)

相应的此时建双链表的方法也有两种,与建立单链表过程相似,只需要加一个前驱结点即可:

code:

typedef struct Lnode
{
    int data;
    struct Lnode *prior;  //前驱节点
    struct Lnode *next;   //后继节点
}LinkList;

 

第一种建立方式头插法(与单链表头插法相似):

code:

  1. void CreateList_F(LinkList *&L, int a[], int n)
    {
        LinkList *s;
        int i;
        L = (LinkList*)malloc(sizeof(LinkList));
        L->prior = L->next = NULL;
        for (i = 0; i < n; i++)
        {
            s = (LinkList *)malloc(sizeof(LinkList));
            s->data = a[i];
            s->next = L->next;
            if (L->next != NULL)
            {
                L->next->prior = s;
            }
            L->next = s;
            s->prior = L;
        }
    }

     

尾插法建立 双链表:

code:

  1. void CreatList_R(LinkList *&L, int a[], int n)
  2. {
  3.     int i;
  4.     LinkList *s, *r;
  5.     r = L;
  6.     for (i = 0; i < n; i++)
  7.     {
  8.         s = (LinkList*)malloc(sizeof(LinkList));
  9.         s->data = a[i];
  10.         r->next = s;
  11.         s->prior = r;
  12.     }
  13.     r->next = L->next;
  14. }

经过好多坎坷,终于到达的河的对岸,于是小伙伴们 手拉手围成一个圈,兴高采烈的哭了起来。

循环链表:

循环链表 只是将链表 的尾部节点的 next指向了链表 的开头L;

下面我总结下代码:

单链表:

typedef struct Lnode    //数据节点
{
    int data;
    struct Lnode *next;
}LinkList;
void InitList(LinkList *&L)   //创建空的单链表
{
    L = (LinkList *)malloc(sizeof(LinkList));
    L->next = NULL;
}
void CreateListH(LinkList *&L, int a[], int n)    //头插法建立单链表
{
    LinkList *s;
    int i;
    L = (LinkList *)malloc(sizeof(LinkList));   L是 链表的头
    L->next = NULL;
    for (i = 0; i < n; i++)                   //将数据插入链表头(L)的后面
    {
        s->data = a[i];
        s->next = L->next;               //即:s指向 L的 指向,L指向s;
        L->next = s;
    }
}
void  CreateListR(LinkList *&L, int a[], int n)  //尾插法建立单链表
{
    int i;
    LinkList *s, *r;
    L = (LinkList *)malloc(sizeof(LinkList));  //申请空间。开始时L虽然是表头 ,同时也是尾
    r = L;
    for (i = 0; i < n; i++)      //              //将下一个 数据插入队尾的后面,再让该数据成为新的队尾
    {
        s->data = a[i];
        r->next = s;            //r就是队尾部,将 s插入r的后面,
        r = s;                 //插入后,那么s在最后的位置,让其成为标记。现在s就是新的队尾
    }
    r->next = L->next;             //队伍建立完成后,最后  队尾节点为 NULL;
}
</pre><pre code_snippet_id="1630697" snippet_file_name="blog_20160331_15_6131477" name="code" class="cpp">
int ListLength(LinkList *L)                  //返回单链表的长度
{
    int ans = 0;
    LinkList *p = L;                         //(要注意是LinkList * p = L)
    while (p->next != NULL)                 //如果 下一个节点不为空,肯定是有数据存储的,于是ans++;
    {
        ans++;
        p = p->next;
    }
    return ans;
}
void CoutList(LinkList *L)                    //输出每个节点的信息
{
    LinkList *p = L->next;                 //从头开始(要注意是LinkList *p = L->next)
    while (p != NULL)                       //如果当前节点不为空,则 输出信息
    {
        printf("%d", p->data);
        p = p->next;
    }
}
bool GetElem(LinkList *&L, int i, int &e)             //修改某个位置上的数据信息
{
    int j = 0;
    LinkList *p = L;
    while (j < i && p != NULL)                          //如果没有遍历到i-1并且链表没有结束
    {
        j++;                                        //接着找
        p = p->next;
    }
    if (p == NULL)                                         //如果结束时是因为链表结束了,则说明 i超出了范围
        return false;
    else                                                     //否则,修改信息
    {
        p->data = e;
        return true;
    }
}
bool ListDelete(LinkList *&L, int i)                          //删除某个节点
{
    int j = 0;
    LinkList *p = L, *q;
    while (j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else                                                  //如果找到了该节点,
    {
        q = p->next;                                  //那么让当前节点的后记节点指向它后面 的后面,就相当于把 这个节点隔出来了
        if (q == NULL)
        {
            return false;
        }
        p->next = q->next;
        free(q);
        return true;
    }
}
bool ListInsert(LinkList *&L, int i, int e)               //  插入节点
{
    int j = 0;
    LinkList *p = L, *s;
    while (j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else                                              //如果  找到位置,先让要插入的s节点指向当前节点的后继,并让当前节点的后继指向s。
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }
}

 

双链表:

typedef struct Lnode   //双链表节点
{
    int data;
    struct Lnode *prior;
    struct Lnode *next;
}LinkList;
void CreateList_F(LinkList *&L, int a[], int n)   //头插法建立双链表
{
    LinkList *s;
    int i;
    L = (LinkList*)malloc(sizeof(LinkList));
    L->prior = L->next = NULL;                  //首先头部节点的next 和prior为空
    for (i = 0; i < n; i++)
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = a[i];
        s->next = L->next;
        if (L->next != NULL)                     //如果头部节点的next不为空,那么L的下个节点的prior必须要指向s
        {
            L->next->prior = s;
        }
        L->next = s;                              //L的 next指向 s,s的 前驱节点指向L。
        s->prior = L;
    }
}
void CreatList_R(LinkList *&L, int a[], int n)  尾插法建立双链表
{
    int i;
    LinkList *s, *r;
    r = L;
    for (i = 0; i < n; i++)
    {
        s = (LinkList*)malloc(sizeof(LinkList));  //只需要 让新加入的节点  的前驱节点指向当时队尾即可,不用 考虑头部L,因为是 尾插法。
        s->data = a[i];
        r->next = s;
        s->prior = r;
    }
    r->next = L->next;
}

 

 

循环链表  的就不写了,因为只需要 让尾节点和头结点关联上就行了,不过要注意双链表循环和单链表循环是有一定区别的。但是本质不变。

希望  这篇文章 可以 帮助你更好的理解或者复习链表操作 。

如有错,请留言。

温柔正确的人总是难以生存,因为这世界既不温柔,也不正确

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!