双链表的存储结构

typedef int ElemType;
struct DLinkList {
    ElemType data;
    struct DLinkList *prior;
    struct DLinkList *next;
};

头插法

void CreateDLinkListF(DLinkList *&L,ElemType a[],int n) {
    DLinkList *s;
    int i;
    L=(DLinkList *)malloc(sizeof(DLinkList));
    L->next=L->prior=NULL;
    for(i=0; i<n; i++) {
        s=(DLinkList *)malloc(sizeof(DLinkList));
        s->data=a[i];
        s->next=L->next;
        s->prior=L;
        if(L->next!=NULL)
            L->next->prior=s;
        L->next=s;
    }
}

尾插法

void CreateDLinkListR(DLinkList *&L,ElemType a[],int n) {
    DLinkList *s,*r;
    int i;
    L=(DLinkList *)malloc(sizeof(DLinkList));
    r=L;
    for(i=0; i<n; i++) {
        s=(DLinkList *)malloc(sizeof(DLinkList));
        s->data=a[i];
        s->prior=r;
        r->next=s;
        r=s;
    }
    r->next=NULL;
}

找指定元素值的节点

int FindNode(DLinkList *L,ElemType x) {
    DLinkList *p;int i;
    p=L->next;
    i=1;
    while(p!=NULL && p->data!=x) {
        p=p->next;
        i++;
    }
    if(p==NULL) return 0;
    else return i;
}

在第i个位置上插入节点

int ListInsert(DLinkList *&L,int i,ElemType e) {
    int j=0;
    DLinkList *p=L,*s;
    while(j<i-1 && p!=NULL) {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else {
        s=(DLinkList *)malloc(sizeof(DLinkList));
        s->data=e;
        s->next=p->next;
        if(p->next!=NULL)
            p->next->prior=s;
        s->prior=p;
        p->next=s;
        return 1;
    }
}

删除节点的操作

int ListDelete(DLinkList *&L,int i,ElemType &e) {
    DLinkList *p=L,*q;
    int j=0;
    while(j<i-1 && p!=NULL) {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else {
        q=p->next;
        if(q==NULL) return 0;
        p->next=q->next;
        if(p->next!=NULL) p->next->prior=p;
        e=q->data;
        free(q);
        return 1;
    }
}