数据结构系列学习（五） - 双向链表（Double_Linked_List）

typedef int Elem_type;
typedef struct DNode
{
    Elem_type data;
    struct DNode* next;
    struct DNode* prior;
}DNode, *PDnode;

void Init_dlist(PDnode dlist);
void Clear(PDnode dlist);
void Destroy(PDnode dlist);
void Destroy1(PDnode dlist);
void Show(PDnode dlist);
struct DNode* Search(PDnode dlist,Elem_type val);
int Get_Length(PDnode dlist);
bool IsEmpty(PDnode dlist);
bool Insert_head(PDnode dlist,Elem_type val);
bool Insert_tail(PDnode dlist,Elem_type val);
bool Insert_pos(PDnode dlist,int pos,Elem_type val);
bool Delete_head(PDnode dlist);
bool Delete_tail(PDnode dlist);
bool Delete_pos(PDnode dlist,int pos);
bool Delete_val(PDnode dlist,Elem_type val);

void Init_dlist(PDnode dlist)
//如果没有有效节点，则双向链表的头节点，应该：头节点的数据域浪费掉，不使用，头节点的next域
{
    assert(dlist != nullptr);
    dlist->next = nullptr;
    dlist->prior = nullptr;
}

void Clear(PDnode dlist)
{
    Destroy(dlist);
}

void Destroy(PDnode dlist)//无线头删
{
    while(!IsEmpty(dlist)){
        Delete_head(dlist);
    }
}

void Destroy1(PDnode dlist)//两个指针辅助
{
    assert(dlist != nullptr);
    PDnode p = dlist->next;
    PDnode q = nullptr;
    dlist->next = nullptr;
    while(p != nullptr){
        q = q->next;
        free(p);
        p = q;
    }
}

void Show(PDnode dlist)
{
    assert(dlist != nullptr);
    PDnode p = dlist->next;
    for(;p != nullptr;p = p->next){
        printf("%5d",p->data);
    }
    printf("\n");
}

struct DNode* Search(PDnode dlist,Elem_type val)
{
    assert(dlist != nullptr);
    PDnode p = dlist->next;
    for(;p->next != nullptr;p = p->next){
        if(p->data == val){
            return p;
        }
    }
    return nullptr;
}

int Get_Length(PDnode dlist)
{
    assert(dlist != nullptr);
    int count = 0;
    PDnode p = dlist->next;
    for(;p != nullptr;p = p->next){
        count++;
    }
    return count;
}

bool IsEmpty(PDnode dlist)
{
    return dlist->next == nullptr;
}

bool Insert_head(PDnode dlist,Elem_type val)
{
    assert(dlist != nullptr);
    PDnode pnewnode = (PDnode) malloc(1 * sizeof(DNode));
    //先修改pnewnode自身的两个域，再处理下一个节点的prior域，最后处理上一个节点的next域
    assert(pnewnode != nullptr);
    pnewnode->data = val;
    pnewnode->next = dlist->next;//1
    pnewnode->prior = dlist;
    if(dlist->next != nullptr) {
        dlist->next->prior = pnewnode;
    }
    dlist->next = pnewnode;
    return true;
}

bool Insert_tail(PDnode dlist,Elem_type val)//不存在特殊情况 每一种情况都是修改三个指针域
{
    assert(dlist != nullptr);
    PDnode pnewnode = (PDnode) malloc(1 * sizeof(DNode));
    assert(pnewnode != nullptr);
    pnewnode->data = val;
    PDnode p = dlist;
    for(;p->next != nullptr;p = p->next);
    pnewnode->next = p->next;
    pnewnode->prior = p;
    p->next = pnewnode;
    return true;
}

bool Insert_pos(PDnode dlist,int pos,Elem_type val)//当pos==0的时候是头插 当pos等于length的时候是尾插，其他位置pos >0 && pos < length 的时候是中间插入
{
    assert(dlist != nullptr);
    assert(pos >= 0 && pos <= Get_Length(dlist));
    PDnode pnewnode = (PDnode) malloc(1 * sizeof(DNode));
    assert(pnewnode != nullptr);
    pnewnode->data = val;
    if(pos == 0){
        return Insert_head(dlist,val);
    }
    else if(pos == Get_Length(dlist) - 1){
        return Insert_tail(dlist,val);
    }
    PDnode p = dlist;
    for(int i = 0;i < pos;i++){//当pos等于几
        p = p->next;
    }
    pnewnode->next = p->next;//1
    pnewnode->prior = p;//2
    p->next->prior = pnewnode;//4
    p->next = pnewnode;//3
    return true;
}

bool Delete_head(PDnode dlist)
{
    assert(dlist != nullptr);
    if(IsEmpty(dlist)){
        return false;
    }
    if(dlist->next->next == nullptr){
        dlist->next = nullptr;
    }
    PDnode p = dlist->next;
    dlist->next = p->next;
    p->next->prior = dlist;
    free(p);
    return true;
}

bool Delete_tail(PDnode dlist)
{
    //尾删不存在特殊情况，因为待删除节点就是尾节点，且待删除节点的后一个节点永远永远不存在
    assert(dlist != nullptr);
    if(IsEmpty(dlist)){
        return false;
    }
    PDnode p = dlist;
    for(;p->next != nullptr;p = p->next);
    PDnode q = dlist;
    for(;q->next != p;q = q->next);
    q->next = p->next;
    free(p);
    return true;
}

bool Delete_pos(PDnode dlist,int pos)
{
    assert(dlist != nullptr);
    assert(pos >= 0 && pos < Get_Length(dlist));
    if(IsEmpty(dlist)){
        return false;
    }
    //头删的情况
    if(pos == 0){
        return Delete_head(dlist);
    }
    //尾删的情况
    if(pos == Get_Length(dlist) - 1){
        return Delete_tail(dlist);
    }
    //既不是头删也不是尾删的情况——中间位置的删除，需要统一修改两个指针域
    PDnode q = dlist;
    for(int i = 0;i < pos;i++){
        q = q->next;
    }
    PDnode p = q->next;
    q->next = p->next;
    p->next->prior = q;
    free(p);
    return true;
}

bool Delete_val(PDnode dlist,Elem_type val)
{
    assert(dlist != nullptr);
    if(IsEmpty(dlist)){
        return false;
    }
    PDnode p = Search(dlist,val);
    if(p == nullptr){
        return false;
    }
    PDnode q = dlist;
    for(;q->next != p;q = q->next);
    if(p->next == nullptr){
        q->next = nullptr;
    }
    else{
        q->next = p->next;
        p->next->prior = q;
    }
    free(p);
    return true;
}

#include
#include
#include
#include "Double_Linked_List.h"
int main()
{
    DNode head;
    Init_dlist(&head);
    for(int i = 0;i < 10;i++){
        Insert_pos(&head,i,i + 1);
    }
    printf("原始数据为：\n");
    Show(&head);
/*
    其他函数的测试代码在此添加...
*/
 
}

    printf("经过头插后的数据为：\n");
    Insert_head(&head,100);
    Show(&head);

    printf("经过尾插后的数据为：\n");
    Insert_tail(&head,100);
    Show(&head);

    printf("经过按位置插后的数据为：\n");
    Insert_pos(&head,2,100);
    Show(&head);

    printf("经过头删后的数据为：\n");
    Delete_head(&head);
    Show(&head);

    printf("经过尾删后的数据为：\n");
    Delete_tail(&head);
    Show(&head);

    printf("经过按位置删后的数据为：\n");
    Delete_pos(&head,4);
    Show(&head);

    printf("经过按值删后的数据为：\n");
    Delete_val(&head,2);
    Show(&head);

    PDnode p = Search(&head,4);
    printf("地址为：%p",p);

    PDnode p = Search(&head,100);
    printf("地址为：%p",p);

    Clear(&head);
    Show(&head);

    Destroy(&head);
    Show(&head);

    Destroy1(&head);
    Show(&head);