数据结构简单入门/复习(二)-循环链表与双向链表(C语言)

循环链表

循环链表是在线性链表的基础上,将最后一个结点的next设置为头指针。即

|empty – first| -> |data1 – second| -> |data2 – head|

双向链表

定义与结构

双向链表是在线性链表的基础上加入一个指向直接前驱的指针变量prior。

define int ElemType          //元素类型设置为int
typedef struct DuLNode{      //链表结构定义
    ElemType data;           //数据域
    struct DuLNode *prior    //直接前驱
    struct DuLNode *next;    //直接后继
}DuLNode;

插入

目的:只知道A与B,A的直接后继是C,将B插入A后C前。

原理:将B的前驱设置为A,后继设置为C,将C前驱设置为B,A后继设置为B

B->prior = A;
B->next = A->next;
A->next->prior = B;
A->next = B;

结点删除

目的:只知道A,删除ABC中的B。

原理:将A的后继设置为C,将B释放,将C的前驱设置为A。

A->next = A->next->next;
free(A->next->prior);
A->next->prior = A;

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注