数据结构基础：双链表结构、实现

继续和颦颦学C语言呀.......>

双链表的结构

 这里的head 为头节点，是‘哨兵位’，实际不存储任何有效的数据

它的存在是为了遍历环链表避免死循环

双链表的实现

typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next; //指针保存下⼀个节点的地址
struct ListNode* prev; //指针保存前⼀个节点的地址
LTDataType data;
}LTNode;

头插

DLinkList HeadInsert(DLinkList &L)
{
    InitList(L); 
    int x;
    cin>>x;
    while(x!=9999)
    {
        LTNode *s = (LTNode *)malloc(sizeof(LTNode));
        s->data = x;
        if(L->next == NULL)
        {
            s->next = NULL;
            s->pre = L;
            L->next = s;
        }
        else
        {
            s->next = L->next;
            L->next->pre = s;
            s->pe = L;
            L->next = s;
        }
        cin>>x;
    }
    return L;
}

尾插 

DLinkList TailInsert(DLinkList &L)
{
    InitList(L);
    LTNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999)
    {
        s = (LTNode *)malloc(sizeof(LTNode));
        s->data = x;
        s->next = NULL;
        s->pre = r;
        r->next = s;
        r = s;
        cin>>x;
    }
    return L;
}

遍历双链表

void PrintList(DLinkList L)
{
    DNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

 查找

void Delete(DLinkList &L, int i)
{
    if(i<1 || i>Length(L))
    {
        cout<<"delete failed: index is wrong."<<endl;
        return;
    }
    LDNode *p = GetElem(L,i-1);
    LDNode *q = p->next;
    p->next = q->next; 
    q->next->pre = p; 
    free(q);
}

 代码需要大家自己多打打才会印象深刻哦加油