欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言线性表之双链表详解

程序员文章站 2022-06-10 08:05:53
目录定义1.删除2.插入3.建立4.查找总结定义链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域。因此n个元...

定义

链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域。因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表。若此链表的每个结点中包含两个指针域,则被称为双链表

双链表的结点结构定义如下:

typedef struct node
{
    datatype data;
    struct node *llink;
    struct node *rlink;
} dlinklist;

像单链表一样,需要一个类似于“头结点”一样的结点(记为rear),其数据域为空,指针域的llink指针指向表头结点rlink指针指向表尾结点。而表头结点的llink指针指向null,表尾结点的rlink指针指向null。

1.删除

假设结点p是待删除结点,我们只需让p的前一个结点的rlink指针(p->llink->rlink)指向p的后一个结点(p->rlink),并让p的后一个结点的llink指针(p->rlink->llink)指向p的前一个指针(p->llink),然后释放p所占内存空间,即可完成删除操作。因为这是双链表的删除算法,因此待删除结点在表头或表尾会有略微的区别,但只要抓住核心算法:

p->llink->rlink = p->rlink; p->rlink->llink = p->llink; free(p);

再对表头表尾结点进行特殊处理(改变rear指针的指针域)即可。

双链表删除算法示例如下:

int deletedlinklist(dlinklist *rear, dlinklist *p)
/*在双链表删除结点p,成功返回1,否则返回0*/
{
    dlinklist *q = p->rlink, *s = p->llink;/*q指向p的后继,s指向p的前继*/
    if (s!=null && q==null)/*删除的是最后一个结点*/
    {
        rear->rlink = p->llink;
        p->llink->rlink = p->rlink;
        free(p);
        return 1;
    }
    if (s==null && q!=null)/*删除的是第一个结点*/
    {
        rear->llink = p->rlink;
        p->rlink->llink = p->llink;
        free(p);
        return 1;
    }
    if (s==null & q==null)/*双链表只有一个结点*/
    {
        rear->rlink = rear->llink = null;
        free(p);
        return 1;
    }
    if (s!=null && q!=null)
    {
        p->llink->rlink = p->rlink;
        p->rlink->llink = p->llink;
        free(p);
        return 1;
    }
    return 0;
}

2.插入

假设要把结点q插入到结点p与p的后一个结点之间,需要先令q的llink指针(q->llink)和rlink指针(q->rlink)分别指向p和p的后一个结点(p->rlink),再令p的后一个结点的llink指针(p->rlink->llink)指向q,p的rlink指针(p->rlink)指向q。稍加分析可知,若①②③三个步骤顺序错误,则无法完成插入。用代码表示就是:

q->llink = p; q->rlink = p->rlink; p->rlink->llink = q; p->rlink = q;

同样地,若要在表头或表尾插入元素,则紧抓住核心算法稍作改变,并改变rear的指针域即可。

双链表插入算法示例如下:

int insert(dlinklist *rear, dlinklist *p, datatype x)
{
    dlinklist *q = (dlinklist *)malloc(sizeof(dlinklist));
    if (q == null)
        return 0;
    q->data = x;/*数据域赋值*/
    if (p->rlink == null)/*在表尾插入元素*/
    {
        rear->rlink = q;
        q->llink = p;
        q->rlink = p->rlink;
        p->rlink = q;
        return 1;
    }
    if (p == rear)/*若p为rear,认为在表头插入元素*/
    {
        q->llink = rear->llink->llink;
        q->rlink = rear->llink;
        rear->llink->llink = q;
        rear->llink = q;
        return 1;
    }
    q->llink = p;
    q->rlink = p->rlink;
    p->rlink->llink = q;
    p->rlink = q;
    return 1;
}

3.建立

利用前面所讲在表尾插入元素的办法,我们可以每建立一个新结点就将其插入到表尾。当刚开始建立双链表时,让rear的llink指针(rear->llink)指向表头结点,并让表头结点指向null;当建立结束时,让rear的rlink指针(rear->rlink)指向最后一个结点,即可完成双链表的建立。

dlinklist *createdlinklist(){    dlinklist *rear, *p, *q;    rear = (dlinklist *)malloc(sizeof(dlinklist));    p = (dlinklist *)malloc(sizeof(dlinklist));    if (rear==null || p==null)    {        free(rear);        free(p);        return null;    }    datatype x;    scanf(&x);    p->data = x;    rear->llink = p;    p->llink = null;    p->rlink = null;    scanf(&x);    while (x != flag)/*flag为建立结束的标志*/    {        q = (dlinklist *)malloc(sizeof(dlinklist));        if (q == null)        {            dlinklist *pr;            p = rear->llink;            while (p != null)            {                pr = p->rlink;                free(p);                p = pr;            }            free(rear);            return null;        }        q->data = x;        q->llink = p;        q->rlink = null;        p->rlink = q;        scanf(&x);    }    rear->rlink = q;    return rear;}dlinklist *createdlinklist()
{
    dlinklist *rear, *p, *q;
    rear = (dlinklist *)malloc(sizeof(dlinklist));
    p = (dlinklist *)malloc(sizeof(dlinklist));
    if (rear==null || p==null)
    {
        free(rear);
        free(p);
        return null;
    }
    datatype x;
    scanf(&x);
    p->data = x;
    rear->llink = p;
    p->llink = null;
    p->rlink = null;
    scanf(&x);
    while (x != flag)/*flag为建立结束的标志*/
    {
        q = (dlinklist *)malloc(sizeof(dlinklist));
        if (q == null)
        {
            dlinklist *pr;
            p = rear->llink;
            while (p != null)
            {
                pr = p->rlink;
                free(p);
                p = pr;
            }
            free(rear);
            return null;
        }
        q->data = x;
        q->llink = p;
        q->rlink = null;
        p->rlink = q;
        scanf(&x);
    }
    rear->rlink = q;
    return rear;
}

4.查找

相对于单链表,双链表的优势是可以实现双向的查找。假设让指针p和指针q分别从表头和表尾向中间遍历双链表的每一个结点,当p==q或p->llink==q时认为已遍历结束。

dlinklist *searchdlinklist(dlinklist *rear, datatype x)
{
    dlinklist *p = rear->llink, *q = rear->rlink;
    while (p->data!=x && q->data!=x)
    {
        p = p->rlink;
        q = q->llink;
        if (p==q || p->llink==q)
            break;
    }
    if (p->data == x)
        return p;
    else if (q->data == x)
        return q;
    else
        return null;
}

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容