双向动态链表

基本要素声明

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int ElemType;

typedef struct DuLNode
{
    ElemType data;
    struct DuLNode * prior;
    struct DuLNode * next;
}DuLNode,*DuLinkList;

双向动态链表逆序创建

图示：当链表为空，插入第一个元素的情况

图示：当链表非空，插入其他元素的情况

void CreateDuList(DuLinkList *L, int n)
{
    *L = (DuLinkList)malloc(sizeof(DuLNode)); /* 创建头结点 */
    (*L)->next = NULL;
    (*L)->prior = NULL;

    DuLinkList p;
    if(n>0) {  /* 如果是第一个结点 */
        p = (DuLinkList)malloc(sizeof(DuLNode));
        scanf("%d",&p->data);
        p->next = (*L)->next;
        p->prior = (*L);
        (*L)->next = p;
        n--;
    }
    for( ; n>0; n--) {
        p = (DuLinkList)malloc(sizeof(DuLNode));
        scanf("%d",&p->data);
        p->next = (*L)->next;
        p->prior = (*L);        /* 新结点p先指向两边两个 */
        (*L)->next->prior = p;  /* 后一个prior指针指向p */
        (*L)->next = p;         /* 前一个next指针指向p */
       
    }
}

获取第i个元素，如果存在，则返回p，否则返回NULL

DuLinkList GetElemP_DuL(DuLinkList L,int i)
{
    DuLinkList p = L->next;
    int k = 1;

    while(p && k<i) {
        p = p->next;
        k++;
    }
    /* 第i个元素不存在 */
    if(!p || k>i)
        return NULL;
    return p;
}

插入元素

图示：当链表为空时，插入第一个

图示：当链表非空时，插入到末尾

图示：当链表非空时，插入中间位置

Status ListInsertDuL(DuLinkList L, int i, ElemType e)
{
    DuLinkList p,s;
    p = L;
    int k=0;
    while(p && k<i-1) {
        p = p->next;
        k++;
    }
    if(!p || k>i-1)
        return ERROR;
    /* 索引到第i-1个 */
    s = (DuLinkList)malloc(sizeof(DuLNode));
    s->data = e;
    if(!(p->next)) {    /* 插入的是末尾位置 */
        s->next = p->next;
        s->prior = p;   /* 插入点先指向两边 */
        p->next = s;    /* 右边元素指向插入点 */
        /* 左边没有元素 */
    }
    else {
        s->next = p->next; /* 插入点先指向两边 */
        s->prior = p;
        p->next->prior = s; /* 两边的元素指向新插入点 */
        p->next = s;
    }
}

删除第i个元素

图示：空链表没有可删除的元素，直接退出

图示：删除最后一个结点的情况

图示：删除中间结点的情况

Status ListDelete_DuL(DuLinkList L, int i, ElemType *e)
{
    DuLinkList p;
    p = L->next;
    int k = 1;

    while(p && k<i) {
        p = p->next;
        k++;
    }
    if(!p || k>i)
        return ERROR;
    /* 找到合法的第i个 */
    if(!(p->next)) { /* 如果是最后一个结点 */
        p->prior->next = p->next;
    }
    else {          
        p->prior->next = p->next;
        p->next->prior = p->prior;
    }
    *e = p->data;
    free(p);
    return OK;
}

打印双向链表

void printDuList(DuLinkList L)
{
    DuLinkList p = L->next; /* 从第一个元素开始 */
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("
");
}

或者逆序打印

void printDuList2(DuLinkList L)
{
    DuLinkList p = L;

    /* 找到最后一个结点 */
    while (p->next) 
        p = p->next;
    
    /* 逆序打印 */
    while (p->prior) { /* 当p到达头结点则退出 */
        printf("%d ",p->data);
        p = p->prior;
    }
    printf("
");
}

测试函数

int main()
{
    DuLinkList L;
    ElemType e;
    // 创建测试 
    CreateDuList(&L,5);
    //插入测试
    ListInsertDuL(L,1,250);
    ListInsertDuL(L,2,750);
    printDuList(L);
    // 删除测试
    ListDelete_DuL(L,7,&e);
    printDuList(L);
    // 获取测试
    DuLinkList p;
    if(p = GetElemP_DuL(L,7))
        printf("p %d
",p->data);
    // 逆序打印
    printDuList2(L);
}