[学习笔记]双向链表

什么是双向链表？实际上，在单个链表的基础上增加了一个小功能，即每个节点不仅具有尾随的指针字段，而且还增加了前驱指针字段双向链表，从而更方便地查找数据，例如假设当前节点是头节点，如果要指向尾节点，我们只需要将头节点的前驱指针字段指向尾节点，这样就可以直接指向尾节点，并且时间复杂度为O（1），但是它也带来了缺点，即增加了空间消耗，但有时不值得用空间交换时间.

同时双向链表，我们仍然可以使用head节点，它与循环单链表不同，因为该节点还有一个额外的前驱指针字段，所以在使用head指针时可以添加和删除head，尾节点是可行的. 出于相同的原因使用

双向链表的数据结构为:

typedef struct Node{
    struct Node *Prior;
    char Data;
    struct Node *Next;
}Node;
typedef struct Node *List;

基本操作与常规链表相同:

1. 创建整个表:

BOOL CreateNewDoubleLinkList(List *L,int Length)
{
    int temp;
    char Chart='a';
    List EndNode,NewEndNode;
    *L=(List)malloc(sizeof(Node));//为头指针分配内存
    if(!(*L))
        return false;
    EndNode=*L;//先让尾结点指向头指针
    for(temp=0;temp<Length;temp++,Chart++)
    {
        NewEndNode=(List)malloc(sizeof(Node));//为新的尾结点分配内存
        if(!NewEndNode)
            return false;
        NewEndNode->Data=Chart;//为新的尾结点赋值
        NewEndNode->Prior=EndNode;//新的尾结点的前驱指针指向原来的尾结点
        EndNode->Next=NewEndNode;//原来的尾结点的后驱指针指向新的尾结点
        EndNode=NewEndNode;//让原来的尾结点指向新的尾结点
    }
    EndNode->Next=(*L)->Next;//尾结点的后驱指针域指向头结点
    (*L)->Next->Prior=EndNode;//头结点的前驱指针域指向尾结点
    (*L)->Prior=EndNode;//头指针的前驱指针域别浪费了,让他指向尾结点吧:)
    (*L)->Data=temp;//头指针的数据域保存链表的长度
    return true;
}

2. 删除整个表格:

BOOL EmptyDoubleLinkList(List *L)
{
    List DeletePreNode,DeleteNode;
    int temp;
    if((int)(*L)->Data==0)//当链表为空时,返回错误
        return false;
    DeletePreNode=(*L)->Prior;//先让与删除的前一个结点指向头指针,为何这样具体参见我关于循环链表的笔记:)
    for(temp=1;temp<(int)(*L)->Data;temp++)//清空链表
    {
        DeleteNode=DeletePreNode->Next;//保存要删除结点的地址
        DeleteNode->Next->Prior=DeletePreNode;//把要删除的结点的下一个结点的前驱指针域指向欲删除结点的前一个结点
        DeletePreNode->Next=DeleteNode->Next;//把欲删除的前一个结点的后驱指针域指向要删除的节点的下一个结点地址
        free(DeleteNode);//释放与删除的结点内存
        DeletePreNode=DeletePreNode->Next;//欲删除的结点地址后移一位
    }
    free(DeletePreNode);//释放尾结点的内存,这里很容易出错,可以当上面的for循环再做左后一个循环时就只剩下两个结点,然后最后释放了第二个结点,即只剩下一个结点,这个结点的前驱和后驱指针域都是指向它自己的,所以当退出循环时只剩下它自己,也就是我们链表中的最后一个数据(其实是最初链表的倒数第二个结点),因此我们在这里释放它的内存
    (*L)->Prior=(*L)->Next=NULL;//头指针的前驱和后驱指针域指向null
    (*L)->Data=0;//链表长度改为0
    return true;
}

3. 整个表遍历:

BOOL BrowseDoubleLinkList(List L)
{
    List CurrentNode;
    int count=1;
    if(0==(int)L->Data)
        return false;
    CurrentNode=L->Next;//当前结点指向头指针;
    while(count<=L->Data)//输出链表数据
    {
        printf("%3c",CurrentNode->Data);//输出当前结点数据
        if(count%6==0)
            printf("\n");
        CurrentNode=CurrentNode->Next;//当前结点后移一位
        count++;
    }
    return true;
}

4. 插入数据:

BOOL InsertDoubleLinkList(List *L,int InsertPostion,char InsertData)
{
    int temp;
    List CurrentNode,InsertNode;
    if(InsertPostion<1)//如果插入位置小于1,则默认新的插入位置在第一个
        InsertPostion=1;
    if(InsertPostion>(int)(*L)->Data+1)//如果插入位置大于链表长度加1,则默认新的插入位置为表尾 
        InsertPostion=(int)(*L)->Data+1;
    CurrentNode=*L;//当前结点指向头指针 
    for(temp=0;temp<InsertPostion;temp++)//把当前结点指向要插入的位置
    {
        CurrentNode=CurrentNode->Next;
    }
    InsertNode=(List)malloc(sizeof(Node));//为要插入的结点分配内存
    if(!InsertNode)
        return false;
    InsertNode->Data=InsertData;//把数据插入要插入的结点处
    InsertNode->Next=CurrentNode;//当要插入的结点的后驱指针域指向要当前结点
    InsertNode->Prior=CurrentNode->Prior;//把当前结点的上一个结点指向要插入结点的前驱指针域
    CurrentNode->Prior->Next=InsertNode;//把要插入的结点指向当前结点的上一个结点的后驱指针域
    CurrentNode->Prior=InsertNode;
    if(1==temp)//如果插入的位置为表头,则更新头指针的后驱指针域        
        (*L)->Next=InsertNode;
    if((temp-1)==(*L)->Data)//如果插入的是表尾,则更新头指针的前驱指针域
        (*L)->Prior=InsertNode;
    (*L)->Data++;
    return true;
}

5. 删除数据:

BOOL DeleteDataDoubleLinkList(List *L,int DeletePosithion,char *DeleteData)
{
    List DeleteNode;
    int temp;
    if(0==(int)(*L)->Data||DeletePosithion>(int)(*L)->Data||DeletePosithion<1)//链表为空时或删除位置不存在时,返回错误
        return false;
    DeleteNode=*L;//首先指向头指针
    for(temp=0;temp<DeletePosithion;temp++)//把当前指针移动到欲删除的结点处
        DeleteNode=DeleteNode->Next;
    DeleteNode->Prior->Next=DeleteNode->Next;//欲删除的前一个结点的后驱指针域指向欲删除结点的后一个结点
    DeleteNode->Next->Prior=DeleteNode->Prior;//欲删除的后一个结点前驱指针域指向欲删除的前一个结点
    if(1==DeletePosithion)//如果删除的是头结点,则更新头指针的后驱指针域
        (*L)->Next=DeleteNode->Next;
    if(DeletePosithion==(int)(*L)->Data)//如果删除的是尾结点,则更新头指针的前驱指针域
        (*L)->Prior=DeleteNode->Prior;
    *DeleteData=DeleteNode->Data;//输出删除的数据
    free(DeleteNode);//释放欲删除结点的内存
    (*L)->Data--;//链表的长度减一
    return true;
}

还要编写一个小程序来运行:

#define true 1
#define false 0
#define BOOL int
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
    List DL;
    char Output;
    if(false==CreateNewDoubleLinkList(&DL,20))
        return false;
    printf("成功建立链表!\n");
    printf("当前链表数据为:\n");
    BrowseDoubleLinkList(DL);
    printf("\n当前链表长度为:%d\n",(int)DL->Data);
    printf("在第12个位置插入数据'~'...\n");
    if(false==InsertDoubleLinkList(&DL,12,'~'))
        return false;
    printf("插入数据成功!\n");
    printf("当前链表数据为:\n");
    BrowseDoubleLinkList(DL);
    printf("\n当前链表长度为:%d\n",(int)DL->Data);
    printf("删除第5个数据...\n");
    if(false==DeleteDataDoubleLinkList(&DL,5,&Output))
        return false;
    printf("成功删除第5个数据,删除的值为%c\n",Output);
    printf("当前链表数据长度为:%d,新的链表如下:\n",(int)DL->Data);
    BrowseDoubleLinkList(DL);
    printf("\n清空数据表...\n");
    if(false==EmptyDoubleLinkList(&DL))
        return false;
    printf("\n已清空链表!\n当前链表长度为:%d\n",(int)DL->Data);
    getchar();
    return 0;
}

渲染效果:

Capture.PNG

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-215263-1.html