[学习笔记]双向链表

什么是双向链表呢?其实就是在单链表的基础上添加了小功能,即每个结点不仅有后驱指针域,同时增加了前驱指针域,这样查找数据就更加方便了,比如说当前结点是头结点,如果是要指向尾结点的话就只需要我们把头结点的前驱指针域指向尾结点,这样就可以直接指向尾结点,时间复杂度就为O(1),不过也带来了弊端,即增加了空间的消耗,不过有时候空间换时间还是值得的不是.

同时我们依旧可以使用头结点,跟循环单链表不同,因为结点多了一个前驱指针域,所以使用头指针时增删头,尾结点是可行的,当然,尾指针也一样可以使用,原因相同

双向链表的数据结构为:

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