Question

数据结构之单链表基本运算的实现[12]

Answer 1

　　双向链表结点的定义如下

　　typedef struct node{

　　DataType data;

　　struct node *prior *next;

　　}DuNode *DLinkList;

　　和单链表类似 双向链表也有几种变形形式 图 给出了带头结点的双向链表示意图 链表中存在从头到尾和从尾到头的两条链;图 给出了带头结点的双向循环链表示意图 链表中存在两个环

　　显然通过某结点的指针p可以直接得到它的后继结点的指针p >next 也可以直接得到它的前驱结点的指针p >prior 这样在有些需要查找前驱的操作中时间效率大大提高

　　设p指向双向循环链表中的某一结点 即p是该结点的指针 则p >prior >next表示的是*p结点之前驱结点的后继结点的指针 即与p相等;类似 p >next >prior表示的是*p结点之后继结点的前驱结点的指针 也与p相等 所以有以下等式

　　p=p >prior >next = p >next >prior

　　双向链表中结点的插入 设p指向双向链表中某结点 s指向待插入的值为x的新结点 将*s插入到*p的前面 插入示意图如图 所示

　　

　　图 双向链表中的结点插入

lishixinzhi/Article/program/sjjg/201311/23077