数据结构系列学习(五) - 双向链表(Double_Linked_List)

发布于:2022-11-09 ⋅ 阅读:(5) ⋅ 点赞:(0) ⋅ 评论:(0)

目录

引言:

学习:

代码实现:

头文件(Double_Linked_List):

结构体的设计:

函数的声明:

源文件(Double_Linked_List)对函数功能的具体实现:

初始化函数(Init_dlist):

清空函数(Clear):

销毁函数(无线头删)(Destroy1):

销毁函数(双指针协作释放节点)(Destroy2):

打印函数(Show):

查找函数(Search):

获取有效长度函数(Get_Length):

判空函数(IsEmpty):

头插函数(Insert_head):

尾插函数(Insert_tail):

按位置插函数(Insert_pos):

头删函数(Delete_head):

尾删函数(Delete_tail):

按位置删函数(Delete_pos):

按值删函数(Delete_val):

测试:

测试初始化函数、打印函数:

测试头插函数: 

测试尾插函数: 

测试按位置插函数:

测试头删函数:

 测试尾删函数:

测试按位置删函数:

测试按值删函数: 

测试查找函数: 

测试清空函数: 

测试销毁函数1: 

测试销毁函数2: 


引言:

数据结构学习目录:

数据结构系列学习(一) - An Introduction to Data Structure

 数据结构系列学习(二) - 顺序表(Contiguous_List)

数据结构系列学习(三) - 单链表(Linked_List) 

数据结构系列学习(四) - 单向循环链表(Circular Linked List)

在上一篇文章中,我们学习了单项循环链表的理论知识并使用代码对它进行了实现,在链式存储结构中还有另外一种表现形式——双向链表。在我们之前学习的单链表或者单向循环链表中,链表中的每一个节点保存的都是它的后继节点的地址,而我们今天将要介绍和学习的双向链表却不一样,双向链表中的节点既能保存它的后继节点的地址,也能保存它的前驱节点的地址。这也是他为什么叫做双向链表的原因。

学习:

双向链表和单链表不同,双向链表每一个节点既保存后继节点的地址,又保存前驱节点的地址。

为什么会有双向链表?

在严蔚敏的《数据结构(C语言版)》中是这样说的,链式存储结构中只有一个指示直接后继的指针域,由此,从某个节点出发只能顺指针往后寻查其他节点。为克服单链表这种单向性的缺点,就产生了双向链表。

双向链表存在的意义:每个节点既可以找到直接后继,也可以找到直接前驱。且每一个节点既可以向后走,也可以向前走,相当于是对单链表的改进,如图:

代码实现:

双向链表中我们要实现的功能(15个):

初始化函数(Init_dlist);

清空函数(Clear);

销毁函数(无线头删)(Destroy1);

销毁函数(双指针协作释放节点)(Destroy2);

打印函数(Show);

查找函数(Search);

获取有效长度函数(Get_Length);

判空函数(IsEmpty);

头插函数(Insert_head);

尾插函数(Insert_tail);

按位置插函数(Insert_pos);

头删函数(Delete_head);

尾删函数(Delete_tail);

按位置删函数(Delete_pos);

按值删函数(Delete_val);

头文件(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);

源文件(Double_Linked_List)对函数功能的具体实现:

初始化函数(Init_dlist):

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

清空函数(Clear):

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

销毁函数(无线头删)(Destroy1):

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

销毁函数(双指针协作释放节点)(Destroy2):

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;
    }
}

打印函数(Show):

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

查找函数(Search):

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;
}

获取有效长度函数(Get_Length):

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

判空函数(IsEmpty):

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

头插函数(Insert_head):

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;
}

尾插函数(Insert_tail):

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;
}

按位置插函数(Insert_pos):

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)){
        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;
}

头删函数(Delete_head):

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;
}

尾删函数(Delete_tail):

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;
}

按位置删函数(Delete_pos):

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;
}

按值删函数(Delete_val):

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<cstdio>
#include<cassert>
#include<cstdlib>
#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);

 运行结果:

测试销毁函数1: 

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

运行结果:

 

测试销毁函数2: 

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

运行结果: