线性表

栈&队列

串

二叉树

持续更新中，尽请期待！！！

双向链表

#include <bits/stdc++.h>
using namespace std;
#define ElemType int
#define Status int

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

void Init_DuL(DuLinkList &L){
   
    L = (DuLinkList)malloc(sizeof(DuLNode));
    L->data = NULL;
    L->next = L;
    L->prior = L;
}

//链表长度
Status Length_DuL(DuLinkList &L){
   
    DuLinkList p;
    p = L->next;
    int i = 0;
    while (p->data != NULL)
    {
   
        p = p->next;
        i++;
    }
    return i;
}

DuLinkList GetElemP_DuL(DuLinkList &L, int i){
   
    DuLinkList p = L->next;
    int j = 1;
    while (p && j < i){
   
        //p不为空或者计数器j还没有等于i时，循环继续
        p = p->next;
        ++j;
    }
    if (!p || j > i || i > (Length_DuL(L) + 1)){
   
        //第i个元素不存在或i大于表长加1时，p指向空
        p = NULL;
    }
    if (i == Length_DuL(L) + 1){
   
        //i等于表长加1时，p指向头结点
        p = L;
    }
    return p;
}

//算法2.18
//带头结点的双链循环线性表L中第i个位置之前插入元素e
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{
   
    //在带条结点的双链循环线性表L中第i个位置之前插入元素e
    //i的合法值为1<=i<=表长+1
    DuLinkList p, s;
    if (!(p = GetElemP_DuL(L, i))) //在L中确定插入位置指针p
        return 0;
    if (!(s = (DuLinkList)malloc(sizeof(DuLNode))))
    {
   
        return 0;
    }
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return 1;
}
//算法2.19
//删除带头结点的双链循环线性表L的第i个元素
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)
{
   
    DuLinkList p;
    if (!(p = GetElemP_DuL(L, i)))
    {
                    //在L中确定第i个元素的位置指针
        return 0; //p=NULL，即第i个元素不存在
    }
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return 1;
}

//释放销毁
void Destory_DuL(DuLinkList &L)
{
   
    DuLinkList p, q;
    p = L->next;
    while (p->data != NULL)
    {
   
        q = p->next;
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);
        p = q;
    }
    free(L);
}