数据结构之双链表

前言

上一节,博主讲解了单链表,并且具体的实现了单链表的增删改查,而这次博主要讲解的是双向循环链表,简称双链表.

为何要双链表?

既然有了单链表,为何还搞一个双链表呢? 答案就是解决了单链表的一些缺点. 这个和上一节博主讲解的为何需要单链表,而答案是单链表可以解决顺序表空间浪费严重的问题一样. 所以他们三者构成了一个简单关系,如下图:

补充:,大家如果对单链表的增删查改比较熟悉,就知道单链表有一个致命的缺陷:

• 如果要动尾结点,就必须挨个遍历,找到倒数第二个结点.
• 如果要动中间结点,往往也是需要先找到中间结点的前一个结点.

也就是说,如果想要修改一些东西,就必须得遍历一下链表,这就导致很憋屈,特别是尾插和尾删,明明只需要修改最后一个,却必须全部遍历,而这也就是双链表的诞生原因.他完美的解决了单链表的问题.

双链表的结构图示

既然知道了双链表解决的是单链表的哪些问题,我们不妨猜猜双链表到底什么结构呢?

• 解决了想要动尾结点不需要遍历的问题— — — — 那尾结点一定有被指向,被谁指向呢?两种可能:
  • 被尾结点前一个指向
  • 被头结点指向
• 解决了修改中间结点不需要遍历的问题— — — — 那说明该结点的前一个结点一定有被指向,被谁指向呢?两种可能:
  • 被所需要动结点的前两个结点指向
  • 被所需要动结点指向

所以,他的结构大致应该是下面这样,注意哦~~~,博主说的是大致,因为有一些小细节需要单独拎出来说的:

嗯~~~,这样完全符合我们的要求,但实际上 双向循环链表的真正结构,也是这样,只是比起这个结构多了一个无效数据头结点,这是为了方便头插头删.

真正的双向链表结构:

项目的建造

还是老规矩,博主用的vs2019,就仍然用它进行演示.

我们的目的是要实现双链表,那我们现在就需要3个文件,分别是List.h ,List.c, test.c

作用分别是: 结构体的定义,头文件的引用,函数声明, 函数定义,函数测试

如图:

双链表结点的定义

上图中,双链表的结构图示我们已经非常清楚了,现在我们就需要按照图示用代码进行实现了.

图示中,一个结点的内容有哪些?

• 一个指向前面结点的指针
• 一个存储数据的空间
• 一个指向后面结点的指针

在List.h文件中定义双链表结构

typedef int LTDataType; //我们并不知道要存储什么数据,便以int为例. 之所以用typedef改名是为了以后不用int,修改更方便

typedef struct ListNode
{ 
          
    struct ListNode* prev;
    LTDataType data;
    struct ListNode* next;
}LTNode; //修改个更短的名字

双链表的各种方法实现

顺序表有顺序表的各种操作函数,单链表有单链表的各种操作,而我们的双链表同理,也是有自己的各种操作.

那有什么样子的操作呢? 博主全部列举在下面,后面将会一一进行实现.

在List.h文件中声明各种方法

LTNode* BuyListNode(LTDataType elem);                     //创建一个新链表结点
void ListInit(LTNode** pphead);   						  //初始化
bool ListEmpty(LTNode* phead);    						  //判断链表是否为空
size_t ListSize(LTNode* phead);   						  //返回链表元素数量
void ListPrint(LTNode* phead);    						  //打印链表内容

void ListPushBack(LTNode* phead, LTDataType* elem);       //尾插
void ListPushFront(LTNode* phead, LTDataType* elem);      //头插
void ListPopBack(LTNode* phead);                          //尾删
void ListPopFront(LTNode* phead);                         //头删

LTNode* ListFind(LTNode* phead,LTDataType elem);          //查找元素elem,并返回elem所在结点
void ListInsert(LTNode* pos,LTDataType elem);             //在结点pos之前插入elem,一般配合ListFind使用
void ListErease(LTNode* pos);                             //删除pos结点,一般配合ListFind使用
void ListDestroy(LTNode* phead);  						  //销毁双链表

双链表之新建结点

结点的作用是干什么呢? 没错, 那就是存储数据,所以新建结点首要目的就是把数据存储

LTNode* BuyListNode(LTDataType elem)
{ 
            
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if(newnode == NULL)
    { 
            
        perror("错误原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

双链表之初始化

既然是初始化,那我们要初始化什么呢? 我们知道双链表是具有一个无效数据头结点的,所以我们初始化要做的事情就是

给无效数据头结点创立一个空间,并随机给个值,然后让其前后指针都指向着自己,这样就符合 双向循环链表的结构

//大家注意哦~,博主这里用的是二级指针,为什么呢?
//因为实参是一个一级指针
//而如果形参是一级指针,这就属于值传递了,函数内pphead的值改变并不会影响外面的实参,而初始化是需要修改实参的.
void ListInit(LTNode** pphead)
{ 
            
    assert(pphead); //pphead一定不能是空指针
    
    (*pphead) = BuyListNode(-1); //随机给一个值用来创建结点
    
    (*pphead)->prev = *pphead;
    (*pphead)->next = *pphead;
}

测试是否成功:

通过调试可以发现,plist存储的数据是-1,前指针指向了plist自己,后指针plist也指向了自己.成功!!!

双链表之判空

双链表判空,判断的是哪一部分呢? 没错,判断的是头结点的后面部分,即排除了无效数据头结点的部分,如图:

所以我们只需要判断就是头结点之后(phead->next)的结点值是不是phead,原因:

• 当链表为空时候,就只剩下一个无效头结点.— — —即phead->next 等于 phead
• 当链表不为空时候,就有有效结点— — —即phead->next 不等于 phead

bool ListEmpty(LTNode* phead)
{ 
              
    assert(phead); //phead不能为空
    
    return phead->next == phead; 
}

测试是否成功:

1代表空,正确,因为这个时候除了头结点自己,就没有任何结点

双链表之求具体元素数量

同样,我们求取元素数量求取的还是头结点之后.

size_t ListSize(LTNode* phead)
{ 
              
    assert(phead);
    size_t sum = 0;
    LTNode* cur = phead->next; //从头结点之后开始遍历
    
    while(cur != phead) //当cur再次为phead时候,说明链表已经遍历完毕.
    { 
              
        sum++;
        cur = cur->next;
    }
    
    return sum;
}

测试是否成功:

成功!!!

双链表之打印链表内容

一样,我们打印的还是有效数据,即头结点之后的数据

void ListPrint(LTNode* phead)
{ 
              
	assert(phead);
	LTNode* cur = phead->next;

	while (cur != phead)
	{ 
              
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("|完毕|\n");
}

双链表之尾插

终于到这里了,这就是我们的重头戏部分了.

还记得我们为什么有双链表吗?那就是尾插时候不需要从头遍历到尾,才能找到尾结点.

我们定义的这个双向链表的尾结点怎么找到呢? 没错 , phead->prev

那么我们尾插的步骤是什么呢? 请看图:

• 第一步,创建新结点存储数据
• 第二步,原尾结点和现在新结点互相链接
• 第三步,新结点和头结点互相链接

void ListPushBack(LTNode* phead, LTDataType* elem)
{ 
                
    assert(phead);
    
    LTNode* tail = phead->prev;  //找到尾结点
    LTNode* newnode  = BuyListNode(elem); //创建新结点
    
    //原来尾结点和现在新结点链接
    tail->next = newnode;
    newnode->prev = tail;
    
    //新结点和头结点链接
    phead->prev = newnode;
    newnode->next = phead;
}

测试是否成功

成功!!!

双链表之尾删

老规矩,到底怎样操作呢?,先上图!

• 第一步,找到尾结点和倒数第二个结点
• 第二步,释放尾结点
• 第三步,头结点和倒数第二个结点连接

void ListPopBack(LTNode* phead)
{ 
                  
    assert(phead);
    assert(ListEmpty(phead)); //如果链表为空就不能删除.
    
    LTNode* tail = phead->prev;//尾结点
    LTNode* tail_prev = tail->prev;//倒数第二个结点
    
    free(tail);//释放尾结点
    tail = NULL;
    
    tail_prev -> next = phead; //头结点和倒数第二个结点连接
    phead->prev = tail_prev;
}

测试是否成功

成功!!

双链表之头插

头插怎样操作?? 还是老规矩,先上图?

• 第一步,创建新结点存储数据
• 第二步,新结点与头结点后的首结点链接
• 第三步,新结点与头结点链接

void ListPushFront(LTNode* phead, LTDataType* elem)
{ 
                    
    assert(phead);
    
    LTNode* newnode  = BuyListNode(elem); //创建新结点存储数据
    LTNode* Second_first = phead->next; //头结点后的首结点.
    
    //新结点 与 头结点后的首结点 链接
    Second_first ->prev = newnode;
    newnode->next = Second_first;
    
    //新结点与头结点链接
    phead->next = newnode;
    newnode->prev = phead;
}

测试是否成功:

成功!!!

双链表之头删

怎样头删? 还是老规矩,先画图看清楚步骤!

• 第一步,头结点与头删结点后的结点连接
• 第二步,释放头删结点

void ListPopFront(LTNode* phead)
{ 
                      
    assert(phead);
    assert(!ListEmpty(phead)); //如果为空就无法删除
    LTNode* Front_second = phead->next->next;//头删结点后的结点
    LTNode* front = phead->next; //头删结点
    
    //连接
    phead->next = Front_second;
    Front_second->prev = phead;
    
    //释放头删结点
    free(front);
    front = NULL;
}

测试是否成功

成功!!

双链表之查找值

这个题比较简单,直接遍历查找就行,然后返回该结点值

LTNode* ListFind(LTNode* phead,LTDataType elem)
{ 
                        
    assert(phead);
    LTNode* cur = phead->next;
    while(cur != phead)
    { 
                        
        if(cur->data == elem)
        { 
                        
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

双链表之任意位置插入值

任意位置插入值的步骤和其实和头插的步骤一模一样,只是头插是在头结点后面的首结点前插入.

而任意位置前插入是在给定的pos结点之前插入,所以这里博主就不画图了,大家可以看着头插的图进行理解.

void ListInsert(LTNode* pos,LTDataType elem) //还记得我们最开始声明时候说的,这个函数需要和ListFind配合吗?请看:
{ 
                          
    assert(pos);
    
    LTNode* pos_prev = pos->prev;  //保存pos结点之前的结点
    
    LTNode* newnode = BuyListNode(elem); //创建新结点
    
    //新结点与pos链接
    newnode->next = pos;
    pos->prev = newnode;
    
    //新结点与原来pos之前的结点连接
    pos_prev->next= newnode;
    newnode->prev = pos_prev;
    
}

测试是否成功

成功!!!

双链表之任意位置删除

任意位置删除和尾删的步骤一模一样,只是尾删删除的是尾结点,连接的是原来尾结点前面结点和头结点

而任意位置删除的是我们给的结点pos,连接的是pos前后的结点,一样,大家可以去看尾删的动图,博主就不再画了

void ListErease(LTNode* pos)
{ 
                            
    assert(pos);
    
    LTNode* prev = pos-> prev; //pos 之前结点
    LTNode* next = pos->next;  //pos 之后结点
    
    free(pos);
    pos = NULL;
    
    prev->next = next;
    next->prev = prev;
}

测试是否成功:

成功!!!

双链表之销毁空间

挨个释放即可

void ListDestroy(LTNode* phead)
{ 
                            
    assert(phead);
    
    LTNode* cur = phead->next;
    while(cur != phead)
    { 
                            
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    
    free(cur);
    cur = NULL;
}

测试:

成功~~~