双向循环链表的简单实现C语言

一、  前几天学习了单向链表，这两天学双向循环链表感觉容易了许多，双向循环链表比单向链表的优势是能够知道后一个节点，向前访问，不需要像单向链表一样再从头开始访问。
    下面说一下我对头结点head的理解，前几天学单向链表的时候其实是没有真正理解的，其实头节点中保存的就是一个入口地址，也就是你链表第一个元素的地址，当你想要访问某个链表时，传递的也就是这个地址，比如说*p，他的入口地址也就是head就是p，通常我们得调用p = p->next;之后才能访问到链表的第一个节点。
   
二、 双向链表的学习还非常得益于这篇文章，将的特别好，值得收藏：http://blog.sina.com.cn/s/blog_7d44748b01013fsf.html
下面直接上代码，实现了双向循环链表的创建、查找、插入、删除等操作，插入主要是需要4步，删除需要3步
（1）插入：在p节点前插入s节点
                s->prior=p->prior
                s->next=p
                p->prior->next=s
                p->prior=s

（2）删除：删除p节点                 
                p->prior->next=p->next
                p->next->prior=p->prior
                free(p)


三、代码如下

/*
========================================
            双向循环链表
        输入4个元素，按要求输出
========================================
*/
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct DList
{
    int data;
    struct Dlist *prior;
    struct Dlist *next;

}Dlist;

Dlist *head; //将head定义成全局变量

Dlist *DlistCreat(int n) //有n个节点
{ //创建双向循环链表
    int i;
    Dlist *p, *q;

    head = (Dlist *)malloc(sizeof(Dlist));
    head->data = 0;
    p = head;

    for(i = 0; i < n; i++)
    {
        q = (Dlist *)malloc(sizeof(Dlist));
        printf("Input n num:");
        scanf("%d", &(q->data));

        p->next = q; // 顺向连接新结点
        q->next = head; // 始终保持环形连接
        q->prior = p; // 新结点的反向链接
        p = q; // 为连接新节点做准备
    }
    head->prior = p; // 头结点的prior指向最后的结点，是实现双向环形链表的最后一步

    return head;
}


void Sprint(Dlist *p)
{ // 顺向输出链表数据
    p = p->next;
    while(p != head)
    {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
}

void Nprint(Dlist *p)
{ // 反向输出链表数据
    p = p->prior;
    while(p != head)
    {
        printf("%3d", p->data);
        p = p->prior;
    }
    printf("\n");
}

Dlist *DlistFind(Dlist *p, int n)
{ // 找到链表第n个位置的元素
    int i;
    //Dlist *p;
    p = head->next;
    for(i = 0; i < n; i++)
    {
        p = p->next;
    }

    return p->prior;
}

int DlistInsert(Dlist *q, int n, int num)
{ //在链表q的第n个位置上插入num
    Dlist *p, *s, *m; /*其中m是个临时节点*/
    p = DlistFind(q, n);

    s = (Dlist *)malloc(sizeof(Dlist));
    s->data = num;

    s->prior = p->prior; /*在p节点前插入需要以下4步*/
    s->next = p;

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

    p->prior =s;

    return 0;
}

int DlistDelete(Dlist *q, int n)
{
    //删除链表q中的第n个元素
    Dlist *p, *m1, *m2; /*其中m1、m2都是临时节点*/
    p = DlistFind(q, n);

    m1 = p->prior; /*删除p需要以下两步*/
    m1->next = p->next;

    m2 = p->next;
    m2->prior = p->prior;

    free(p);
    return 0;
}

int DlistCount(Dlist *p)
{ //输出链表p总的节点个数
    int i = 0;
    p = p->next;
    while(p != head)
    {
        i++;
        p = p->next;
    }
    return i;
}

int main()
{
    Dlist *p, *q;
    int n = 4; /*有4个节点的链表*/
    p = DlistCreat(n);
    Sprint(p);
    Nprint(p);

    q = DlistFind(p, 2); /*找到在链表第二个位置的元素*/
    printf("%3d\n", q->data);

    DlistInsert(p, 2, 99); /*链表p第2个位置上插入99*/
    Sprint(p);

    DlistDelete(p, 3); /*删除链表p第3个位置上的元素*/
    Sprint(p);

    printf("%3d\n", DlistCount(p)); /*输出链表p总的节点个数*/
    return 0;
}