数据结构（复习）关于双向链表

循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗费是O（n）。如果希望从表中快速确定某一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域prior。这样形成的链表中就有两条方向不同的链，我们可称之为双（向）链表（Double Linked List）。双链表的结构定义如下：

typedef struct DNode

{

ElemType data;

struct DNode *prior,*next;

}DNode,*DoubleList;

双链表的结点结构如图2.14所示。

与单链表类似，双链表一般也是有头指针唯一确定的，增加头结点也能使双链表的某些运算变得方便。同时双向链表也可以有循环表，称为双向循环链表，其结构如图2.15所示。

由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：

P->prior->next=p=p->next->prior

在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

1.双向链表的前插操作

算法描述：欲在双向链表第i个结点之前插入一个新的结点，则指针的变化情况如图2.16所示。

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// 关于数据结构的总结与复习  Coding
//3.关于双向循环链表的问题

#include <cstdio>
#include <cstdlib>
#define error 0
#define ok 1
//#define _OJ_

typedef struct Lnode
{
    int data;
    struct Lnode *pre;
    struct Lnode *next;         //定义前驱和后继
} Lnode, *Linklist;

Linklist
Init_List(void)
{
    int i, n;
    Linklist L, head, p;
    L = (Linklist) malloc (sizeof(Lnode));
    head = L;
    
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
    p = (Linklist) malloc (sizeof(Lnode));    scanf("%d", &p->data);
    L->next = p;    p->pre = L;
    L = p;
    }
    L->next = head;    head->pre = L;         //前后相邻元素互指，  最后元素指向head，
    //head指向tail
    return head;
}

int
List_Length(Linklist L)
{
    int cnt = 0;
    Linklist p;
    p = L;

    while (p->next != L) {
          cnt++;
          p = p->next;
    }
    return cnt;
}

int
List_Delete(Linklist L, int i)
{
    int j;
    Linklist p;
    p = L->next;

    if(i < 1 && i > List_Length(L)) {
        printf("删除超限：
");    return error;
    }

    printf("从第%d个元素删除：
", i);
    for (j = 1; j < i; j++) {
        p = p->next;
    }//值得注意的是单链表删除，插入找到前驱即可，，而在这里要找到第i个元素

    p->pre->next = p->next;
    p->next->pre = p->pre;
}


int
List_Insert(Linklist L, int i, int e)
{
    int j;
    Linklist p, s;
    p = L->next;
    s = (Linklist) malloc (sizeof(Lnode));    s->data = e;

    if(i < 1 && i > List_Length(L) + 1) {
        printf("插入超限：
");     return error;
    }

    for (j = 1; j < i; j++) {
        p = p->next;
    }//值得注意的是单链表删除，插入找到前驱即可，，而在这里要找到第i个元素

    s->pre = p->pre;    p->pre->next = s;
    s->next = p;        p->pre = s;
}

void
print(Linklist L)
{
    Linklist p;
    p = L;
    printf("打印循环链表：");
    while (p->next != L) {
        printf("%d ", p->next->data);
        p = p->next;
    }
}

void
print1(Linklist L)
{
    Linklist p;
    p = L;
    printf(" 逆向打印循环链表：");
    while (p->pre != L) {
        printf("%d ", p->pre->data);
        p = p->pre;
    }
}


int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE JUDGE
       freopen("input.txt", "r", stdin);
       //freopen("output.txt", "w", stdout);
#endif
    

    Linklist L;

    L = Init_List();

    print(L);

    printf("
双向循环链表长度:%d
", List_Length(L));

    List_Delete(L, 2);

    // List_Delete(L, 1);

    // List_Delete(L, 3);               //边界值的测试

    print(L);

    // List_Insert(L, 2, 10);

    // List_Insert(L, 1, 11);

    List_Insert(L, 4, 12);             //边界值得测试

    print1(L);
    
    return 0;
}