数据结构之带头结点的双向循环链表（含全部代码）

电玩女神 2023-09-29 09:53 28阅读 0赞

## 带头结点的双向循环链表的实现 ##

**带头结点的双向循环链表和单链表相比具有许多的优点，增删查改更加的便捷，时间复杂度均为O（1）**  
头文件创建

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<assert.h>

定义数据类型以及创建链表结点

typedef int DataType;
    typedef struct ListNode
    {
        
    	struct ListNode* prev;
    	struct ListNode* next;
    	DataType data;
    }LN;

所需要实现的函数

//初始化
    LN* ListInit();
    //创建结点
    LN* BuyListNode(DataType x);
    //销毁链表
    void ListDestory(LN* phead);
    //打印链表
    void ListPrint(LN* phead);
    //头插
    void ListPushFront(LN* phead, DataType x);
    //尾插
    void ListPushBack(LN* phead, DataType x);
    //头删
    void ListPopFront(LN* phead);
    //尾删
    void ListPopBack(LN* phead);
    //查找x并返回x结点位置
    LN* ListFind(LN* phead, DataType x);
    //在pos前插入x
    void ListInsert(LN* pos, DataType x);
    //删除pos处的元素
    void ListErase(LN* pos);
    //判断链表是否为空
    bool ListEmpty(LN* phead);
    //计算元素个数
    int ListSize(LN* phead);

函数的实现

#include"DList.h"
    
    //初始化
    LN* ListInit()
    {
        
    	LN* phead = BuyListNode(0);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }
    //创建结点
    LN* BuyListNode(DataType x)
    {
        
    	LN* newnode = (LN*)malloc(sizeof(LN));
    	if (newnode == NULL)
    	{
        
    		printf("malloc fail");
    		exit(-1);
    	}
    	else
    	{
        
    		newnode->data = x;
    		newnode->prev = NULL;
    		newnode->next = NULL;
    		return newnode;
    	}
    }
    //销毁链表
    void ListDestory(LN* phead)
    {
        
    	assert(phead);
    	LN* cur = phead->next;
    	while (cur != phead)
    	{
        
    		LN* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	free(phead);
    	phead = NULL;
    }
    //打印链表
    void ListPrint(LN* phead)
    {
        
    	assert(phead);
    	LN* cur = phead->next;
    	while (cur != phead)
    	{
        
    		printf("%d ", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    //头插
    void ListPushFront(LN* phead, DataType x)
    {
        
    	assert(phead);
    	LN* newnode = BuyListNode(x);
    	LN* first = phead->next;
    	phead->next = newnode;
    	newnode->prev = phead;
    	newnode->next = first;
    	first->prev = newnode;
    }
    //尾插
    void ListPushBack(LN* phead, DataType x)
    {
        
    	assert(phead);
    	LN* tail = phead->prev;
    	LN* newnode = BuyListNode(x);
    
    	tail->next = newnode;
    	newnode->prev = tail;
    	phead->prev = newnode;
    	newnode->next = phead;
    }
    //头删
    void ListPopFront(LN* phead)
    {
        
    	assert(phead);
    	assert(phead->next != phead);
    	LN* first = phead->next;
    
    	phead->next = first->next;
    	first->next->prev = phead;
    	free(first);
    	first = NULL;
    }
    //尾删
    void ListPopBack(LN* phead)
    {
        
    	assert(phead);
    	assert(phead->next != phead);
    	LN* tail = phead->prev;
    
    	//phead->prev = tail->prev;
    	tail->prev->next = phead;
    	phead->prev = tail->prev;
    	free(tail);
    	tail = NULL;
    }
    //查找x并返回x结点位置
    LN* ListFind(LN* phead, DataType x)
    {
        
    	assert(phead);
    	LN* cur = phead->next;
    	while (cur != phead)
    	{
        
    		if (cur->data == x)
    		{
        
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    //在pos前插入x
    void ListInsert(LN* pos, DataType x)
    {
        
    	assert(pos);
    	LN* newnode = BuyListNode(x);
    
    	LN* prev = pos->prev;
    	prev->next = newnode;
    	newnode->prev = prev;
    	newnode->next = pos;
    	pos->prev = newnode;
    }
    //删除pos处的元素
    void ListErase(LN* pos)
    {
        
    	assert(pos);
    	LN* prev = pos->prev;
    	LN* next = pos->next;
    
    	prev->next = next;
    	next->prev = prev;
    
    	free(pos);
    	pos = NULL;
    }
    //判断链表是否为空
    bool ListEmpty(LN* phead)
    {
        
    	if (phead == NULL)
    	{
        
    		return true;
    	}
    	else
    	{
        
    		return false;
    	}
    }
    //计算元素个数
    int ListSize(LN* phead)
    {
        
    	int size = 0;
    	assert(phead);
    	LN* cur = phead->next;
    	while (cur != phead)
    	{
        
    		size++;
    		cur = cur->next;
    	}
    	return size;
    }