双链表和循环链表

双链表是在单链表节点上添加一个指针字段，指向当前节点的前体. 这样，其后继者可以很容易地找到其前任者，并实现从输出终端节点到起始节点的数据序列.

类似地，双链表也分为带有前导节点的双链表和没有前导节点的双链表. 这种情况类似于单链列表. 当链表为空时，头节点为head-> next的双链表为null. 当没有头的双向链表的头为空时，链表为空.

void CreateDlistR (DLNode *&L, int a[], int n){ 
    DLNode*s,*r;
    inti;
    L = (DLNode*)malloc(sizeof(DLNode));
    L->next = NULL;
    //和单链表一样r始终指向终端结点，开始头结点也是尾结点
    r = L;
    for(i = 1; i< = n; i++){ 
        //创建新结点s->data = a[i];
        s = (DLNode*)malloc(sizeof(DLNode));
        /*下边3句将s插入在L的尾部并且r指向s，s->prior = r;这一句是和建立单链表不同的地方。 */
        r->next = s;
        s->prior = r;
        r = s;
    }
    r->next = NULL;
}

在双链表中找到第一个值为x的节点. 从第一个节点开始，在扫描时进行比较. 如果找到这样的节点带头结点的双循环链表，则返回节点指针，否则返回NULL. 算法代码如下:

DLNode* Finfnode(DLNode *C, int x){ 
    DLNode *p = C->next;
    while(p != NULL){ 
        if(p->data == x) {
            break;
        }
        p = p->next;
    } 
    return p;
    //如果找到则p中内容是结点地址（循环因break结束），
    //没找到 p中内容是NULL（循环因p等于NULL而结束）
    //因此这一句可以将题干中要求的两种返回值的种情况统一。 
}

假设在双向链表中p所指向的节点之后插入了节点s，其操作语句描述为:

s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;

指针更改的过程如下:

如果按照上述顺序插入，则可以视为通用插入方法. 首先链接要插入的节点的两侧，以确保链断开后找不到该节点.

假设您要删除双向链表中p节点的后继节点，则操作语句为:

q= p->next;
p->next= q->next;
q->next->prior= p;
free(q);

指针更改的过程如图所示:

只要单链表的最后一个指针字段（空指针）指向链表中的第一个节点（之所以说这里是第一个节点而不是头节点，是因为如果单链表如果是前导节点，则该循环是循环的，最后一个节点的指针字段应指向头节点；如果循环单链表没有前导节点，则最后一个指针字段应指向起始节点.

当head等于head-> next时，带有head节点的循环单链列表为空；

当head等于null时带头结点的双循环链表，没有头节点的循环单链列表为空.

循环双链表的结构是从双链表派生的，即终端节点的nnext指针指向链表中的第一个节点，而链结中的第一个节点的优先级指针链接列表指向终端节点.

带有头节点的循环双向链表. 当head-> next和heaad-> prior都等于head时，链接列表为空.

当head等于null时，没有头节点的圆形双向链表为空.

循环单链表和循环双链表是从相应的单链表和双链表转换而来的，只需要在终端节点和头节点之间建立连接即可.

圆形单链列表的终端节点的下一个节点指针指向头节点；循环双向链接列表的终端节点的下一个指针指向表的头节点，头节点的前一个指针指向表的尾节点.

如果p指针沿着循环链表移动，则判断p到达表末尾的条件是p-> next == head. 循环链表的各种操作类似于非循环链表.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-279067-1.html