C语言双链表怎么实现

本篇内容介绍了"C语言双链表怎么实现"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

定义

链表是通过一组任意的存储单元来存储线性表中的数据元素，每一个结点包含两个域：存放数据元素信息的域称为数据域，存放其后继元素地址的域称为指针域。因此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;}

"C语言双链表怎么实现"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！