C和数据结构——双向链表和双向循环链表

#include <bits/stdc++.h>
using namespace std;
/*前驱和后继都能进行遍历的线性链表
1，使用两个指针表示结点的逻辑关系
2，前驱结点指针域prior
3,后继结点指针域next
4,不作特别指出，这里的双向链表都是带头结点的双向循环链表
*/
typedef int Elemtype;
typedef struct DuLNode
{
    Elemtype data;
    struct DULNode *prior, *next;

} DuLNode, *DuLNode;

//双向循环链表求长度
int ListLength(DuLNode L)
{
    int i = 0;
    DuLNode p = L->next;
    while (p) //只用检测p的尾节点是否为空就可以
    {
        i++;
        p = p->next;
    }
    return i;
}

//插入操作
//这里的插入顺序真的很重要哦
/*p--s--q
1,将s的next指向p->next;
2,若p不是最后的结点，将q的prior指向s
3，将s的Prior指针域指向p;
4,将p的next指针域指向s；
    */
int ListInsert(DuLNode L, int i, Elemtype e)
{
    DuLNode p, s;
    if (i < 1 || i > ListLength(L) + 1) //判断数据是否合法
        return 0;
    p = GetElemP(L, i - 1); //找到第i个元素的前驱指针p,
    if (p)                  //判断找到的位置是否正确
        return 0;
    s = (DuLNode)malloc(sizeof(DuLNode)); //申请的新节点，存放e
    if (!s)
    {
        exit(OVERFLOW);
    }
    //进行链接操作
    s->data = e;
    s->prior = p->next; //这一步要放在前面，避免p为尾节点
    p->next->prior = s;
    p->next = s;
    return 1;
}

//删除结点
int ListDelete(DuLNode L, int i, Elemtype &e)
{
    DuLNode p;
    if (i < 1) //判断数据是否合法
        return 0;
    p = GetElemP(L, i); //找到i结点的位置
    if (!p)             //判断找到的位置是否正确
        return 0;
    e = p->data;               //先将数据保存下来，可以省略这一步
    p->prior->next = p->next;  //链接后继
    p->next->prior = p->prior; //链接前驱
    free(p);                   //释放
    return 1;
}