自学内容网 自学内容网

数据结构-2.9.双链表

一.双链表与单链表的对比:


二.双链表的初始化(带头结点):

1.图解:

2.代码演示:

#include<stdio.h>
#include<stdlib.h>
​
//定义双链表结构体
typedef struct DNode
{
    int data;
    struct DNode *prior;//前驱指针即指向前面数据的指针 
    struct DNode *next;//后继指针即指向后面数据的指针 
}DNode,*DLinklist; //DLinklist与DNode *等价,DLinklist强调链表,DNode *强调结点 
​
//初始化双链表
bool InitDLinkList(DLinklist &L)
{
    L = (DNode *)malloc( sizeof(DNode) );//分配一个头结点
    if( L==NULL ) //内存不足,分配失败 
    {
        return false;
    } 
    L->prior = NULL;//头结点的prior(前驱)永远指向NULL
    L->next = NULL;//头结点之后(后继)暂时还没有结点 
    return true;
} 
​
//判断双链表是否为空(带头结点)->只需要看第一个结点是否为空即可 
bool Empty(DLinklist L)
{
    if( L->next == NULL )//代表双链表第一个结点为空,是空双链表
    {
        return true;
    }
    else
    {
        return false;//代表双链表第一个结点不为空,不是空双链表 
    }
} 
​
int main()
{
    //初始化双链表 
    DLinklist L;
    InitDLinkList(L);
    //后续代码。。。 
    return 0;
}

三.双链表的插入:

图解:

此时要p结点之后插入s结点,起初p->next指向y,先把p的下一个结点即y和要插入的结点即s的指向下一个结点的指针对接即s->next = p->next:

之后还需要把p结点的后继结点即p->next的前向指针p->next->prior指向s即p->next->prior = s:

再把要插入的结点即s结点的前驱指针指向p结点即 s->prior = p:

最后把p结点的后继结点指向s即p->next = s:

但对于上述代码,有一个bug,当p结点是最后一个结点时,p->next->prior = s就会报空指针的错,因为

p结点是最后一个结点时p->next指向NULL,因此,严谨的代码如下:对p->next进行空指针判断

  • 按位序插入:找到要插入的位序的前驱结点,在该结点实现后插操作即可

  • 前插操作:由于双链表的特性,可以很方便的找到给定结点的前驱结点,再对前驱结点进行后插操作即可


四.双链表的删除:

图解:

此时要删除p结点的后继结点q,因此要把q结点的下一个结点和p结点连接,即p->next = q->next:

再把要删除的q结点的后继结点即q->next的前驱结点即q->next->prior指向p即q->next->prior = p:

最后再释放要删除的q结点即free(q):free函数要用到头文件#include<stdlib.h>

但上述代码也有bug,如果此时要删除的q结点为双链表最后一个结点,那么q->next就指向NULL,q->next->prior就会报空指针错误,因此对q->next进行空指针判断以增加严谨性:

销毁双链表:每一次删除头结点的后继结点即可

因为比如第一次删除头结点的后继结点即第一个结点,第二次删除时第二个结点就来了第一个位置,相当于头结点的后继结点,删除即可,以此类推,可销毁双链表:


五.双链表的遍历:

1.对于前向遍历(跳过头结点)的循环条件当p->prior == NULL时,说明此时p结点指向的就已经是头结点了,此时跳出循

环,不操作头结点了;

2.对于按位查找,只需要添加一个计数器,用于记录此时指向的哪个位置的元素,当位置和要找的位置匹配时打印即可;

3.对于按值查找,只需要对当前指向的结点和要找的值对比即可,找到了就打印即可;

4.双链表没有随机存取的特性,所以按位查找,按值查找的时间复杂度为O(n),因为只能用循环的方式一个一个对比依次

往后找。


六.总结:



原文地址:https://blog.csdn.net/ADCvbV/article/details/142320309

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!