开发者

C语言带头双向循环链表的示例代码

目录
  • 前言
  • 结构分析
  • 链表的基本操作实现
    • 创建节点
    • 初始化链表
    • 链表销毁
    • 打印链表
    • 链表尾插
    • 链表尾删
    • 链表头插
    • 链表头删
    • 链表查找
    • 链表pos位置前面去插入
    • 删除pos位置
    • 链表判空
    • 代码复用
  • 总代码及头文件

    前言

    对于链表来说,不只有单链表这一个品种;

    链表有很多种形态

    按方向分:单向、双向

    按带不带头:带头、不带头

    按循环:循环、不循环

    1、单向或则双向:

    C语言带头双向循环链表的示例代码

    2、带头或者不带头:

    C语言带头双向循环链表的示例代码

    3、循环或者不循环:

    C语言带头双向循环链表的示例代码

    组合排列一下的话,链表一共有8种形态!!!

    今天我们就来学习一下结构最复杂的带头双向循环链表!!!;

    虽然名字听上去比较复杂,但是实现起来比单链表(全名:不带头、不循环、单向链表)更加简单,也不需要过多考虑特殊情况;

     

    两种链表的比较:(上面是单链表,下面是带头双向循环链表)

    C语言带头双向循环链表的示例代码

    结构分析

    C语言带头双向循环链表的示例代码

    首先链表的头节点是不存储有效数据的(该节点被称为哨兵位),其次我们只需要知道改头节点的指针就能找到整个链表,并且便于对整个链表进行维护;

    当然既然是双向的嘛,那节点一定有个指针域指向前一个节点,另一个指针域指向后一个节点;

    那么我们的单个节点的数据结构就是:

    开发者_Python入门

    C语言带头双向循环链表的示例代码

    现在我们定义了一个plist指针用来维护整个链表,根据上面说的plist就应该用来存储哨兵位的头节点的指针,那么如何表示链表为NULL的情况?

    链表为空:

    C语言带头双向循环链表的示例代码

    就是:

    head->next=head;

    head->prev=head;

    链表的基本操作实现

    创建节点

    ListNode* ListCreate(LTDataType x)
    {
    	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    	if (!NewNode)
    		exit(-1);
    	NewNode->val = x;
    	NewNode->prev = NULL;
    	NewNode->next = NULL;
    	return NewNode;
    }
    

    我们在创建节点的时候就一起将数据域初始化,方标后续操作;

    初始化链表

    void InitDummyHead(ListNode* pHead)
    {
    	assert(pHead);
    	pHead->prev = pHead;
    	pHead->next = pHead;
    }
    

    链表销毁

    // 双向链表销毁
    void ListDestory(ListNode* pHead)
    {
    	assert(pHead);
    	ListNode* cur = pHead->next;
    	ListNode* next = NULL;
    	while (cur!=pHead)
    	{
    		next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	free(cur);
    }
    

    实现思路:

    C语言带头双向循环链表的示例代码

    打印链表

    除了哨兵位的节点存到是无效数据不打印外,其他节点的数据都要打印:

    // 双向链表打印
    void ListPrint(ListNode* pHead)
    {
    	assert(pHead);
    	ListNode* cur = pHead->next;
    	while (cur != pHead)
    	{
    		ListNode* next = cur->next;
    		printf("%d->",cur->val);
    		cur = next;
    	}
    	printf("NULL\n");
    }
    

    链表尾插

    该链表的尾插,比单链表的尾插简单太多了,不用遍历找尾:

    // 双向链表尾插
    void ListPushBack(ListNode* p编程Head, LTDataType x)
    {
    	assert(pHead);
        ListNode* NewNode = ListCreate(x);
    	ListNode* tail = pHead->prev;
    	tail->next = NewNode;
    	NewNode->prev = tail;
    	pHead->prev = NewNode;
    	NewNode->next = pHead;
    }
    

    链表尾删

    由于是循环的,哨兵位的前一个节点就是尾节点,同时尾节点的前一个节点我们也不用遍历,可以很轻松的拿到:

    // 双向链表尾删
    void ListPopBack(ListNode* pHead)
    {
    	编程客栈assert(pHead);
    	assert(!is_Empty(pHead));//判空
    	ListNode* tail = pHead->prev;
    	ListNode* prev = tail->prev;
    	ListNode* next = pHead;
    	free(tail);
    	prev->next = next;
    	next->prev = prev;
    }
    

    链表头插

    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x)
    {
    	assert(pHead);
    	ListNode* prev = pHead;
    	ListNode* cur = pHead->next;
    	ListNode* NewNode = ListCreate(x);
    	prev->next = NewNode;
    	NewNode->prev = prev;
    	NewNode->next = cur;
    	cur->prev = NewNode;
    }
    

    链表头删

    // 双向链表头删
    void ListPopFront(ListNode* pHead)
    {
    	assert(pHead);
    	assert(!is_Empty(pHead));//判空
    	ListNode* prev = pHead;
    	ListNode* cur = pHead->next;
    	ListNode* next = cur->next;
    	free(cur);
    	prev->next = next;
    	next->prev = prev;
    }
    

    链表查找

    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
    	assert(pHead);
    	assert(!is_Empty(pHead));//表都为NULL了,就没办法找了
    	ListNode* cur = pHead->next;
    	while (cur != pHead)
    	{
    		if (cur->val == x)
    			return cur;
    		else
    			cur = cur->next;
    	}
    	return NULL;
    }
    

    链表pos位置前面去插入

    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
    	assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点,因此我们假设pos传的都是合法指针和NULL
    	ListNode* NewNode = ListCreate(x);
    	ListNode* prev = pos->prev;
    	NewNode->next = pos;
    	pos->prev = NewNode;
    	prev->next = NewNode;
    	NewNode->prev = prev;
    }
    

    删除pos位置

    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
    	assert(pos);//由于参数限制,我们无法判断表是否为NULL;
    	ListNode* prev = pos->prev;
    	ListNode* next = pos->next;
    	free(pos);
    	prev->next = next;
    	next->prev = prev;
    }
    

    链表判空

    //判断链表是否为NULL
    bool is_Empty(ListNode* pHead)
    {
    	assert(pHead);
    	return pHead == pHead->prev;
    }
    

    代码复用

    我们上面既然实现了在pos位置之前插入和删除pos位置的数据;

    那么:

    ListInsert(plist,x);//相当于尾插
    ListInsert(plist->next, x);//相当于头插
    ListErase(plist->next);//相当于头删
    ListErase(plist->prev);//相当于尾删;
    

    那么实际上我们只要实现ListInsertListErase这两个接口就能快速实现出带头双向循环链表了;

    总代码及头文件

    头文件的包含:

    #pragma once
    #include<stdjavascriptio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<stdbool.h>
    // 带头+双向+循环链表增删查改实现
    typedef int LTDataType;
    typedef struct ListNode
    {
    	LTDataType val;
    	struct ListNode* next;
    	struct ListNode* prev;
    }ListNode;
    
    // 创建返回链表的头结点.
    ListNode* ListCreate(LTDataType x);
    //初始化哨兵位的头节点;
    void InitDummyHead(ListNode* pHead);
    // 双向链表销毁
    void ListDestory(ListNode* pHead);
    // 双向链表打印
    void ListPrint(ListNode* pHead);
    // 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x);
    // 双向链表尾删
    void ListPopBack(ListNode* pHead);
    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x);
    // 双向链表头删
    void ListPopFront(ListNode* pHead);
    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x);
    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x);
    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos);
    //判断链表是否为NULL
    bool is_Empty(ListNode* pHead);
    

    功能代码实现:

    #include"DList.h"
    ListNode* ListCreate(LTDataType x)
    {
    	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
    	if (!NewNode)
    		exit(-1);
    	NewNode->val = x;
    	NewNode->prev = NULL;
    	NewNode->next = NULL;
    	return NewNode;
    }
    void InitDummyHead(ListNode* pHead)
    {
    	assert(pHead);
    	pHead->prev = pHead;
    	pHead->next = pHead;
    }
    // 双向链表销毁
    void ListDestory(ListNode* pHead)
    {
    	assert(pHead);
    	ListNode* cur = pHead->next;
    	ListNode* next = NULL;
    	while (cur!=pHead)
    	{
    		next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	free(cur);
    }
    // 双向链表打印
    void www.devze.comListPrint(ListNode* pHead)
    {
    	assert(pHead);
    	ListNode* cur = pHead->next;
    	while (cur != pHead)
    	{
    		ListNode* next = cur->next;
    		printf("%d->",cur->val);
    		cur = next;
    	}
    	printf("NULL\n");
    }
    // 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x)
    {
    	assert(pHead);
    	/*ListNode* NewNode = ListCreate(x);
    	Lis编程tNode* tail = pHead->prev;
    	tail->next = NewNode;
    	NewNode->prev = tail;
    	pHead->prev = NewNode;
    	NewNode->next = pHead;*/
    	ListInsert(pHead,x);//函数复用
    }
    // 双向链表尾删
    void ListPopBack(ListNode* pHead)
    {
    	assert(pHead);
    	assert(!is_Empty(pHead));//判空
    	/*ListNode* tail = pHead->prev;
    	ListNode* prev = tail->prev;
    	ListNode* next = pHead;
    	free(tail);
    	prev->next = next;
    	next->prev = prev;*/
    	ListErase(pHead->prev);//函数复用
    }
    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x)
    {
    	assert(pHead);
    	/*ListNode* prev = pHead;
    	ListNode* cur = pHead->next;
    	ListNode* NewNode = ListCreate(x);
    	prev->next = NewNode;
    	NewNode->prev = prev;
    	NewNode->next = cur;
    	cur->prev = NewNode;*/
    	ListInsert(pHead->next,x);//函数复用
    }
    // 双向链表头删
    void ListPopFront(ListNode* pHead)
    {
    	assert(pHead);
    	assert(!is_Empty(pHead));//判空
    	/*ListNode* prev = pHead;
    	ListNode* cur = pHead->next;
    	ListNode* next = cur->next;
    	free(cur);
    	prev->next = next;
    	next->prev = prev;*/
    	ListErase(pHead->next);//函数复用
    }
    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
    	assert(pHead);
    	assert(!is_Empty(pHead));//表都为NULL了,就没办法找了
    	ListNode* cur = pHead->next;
    	while (cur != pHead)
    	{
    		if (cur->val == x)
    			return cur;
    		else
    			cur = cur->next;
    	}
    	return NULL;
    }
    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
    	assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点,因此我们假设pos传的都是合法指针和NULL
    	ListNode* NewNode = ListCreate(x);
    	ListNode* prev = pos->prev;
    	NewNode->next = pos;
    	pos->prev = NewNode;
    	prev->next = NewNode;
    	NewNode->prev = prev;
    }
    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
    	assert(pos);//由于参数限制,我们无法判断表是否为NULL;
    	ListNode* prev = pos->prev;
    	ListNode* next = pos->next;
    	free(pos);
    	prev->next = next;
    	next->prev = prev;
    }
    //判断链表是否为NULL
    bool is_Empty(ListNode* pHead)
    {
    	assert(pHead);
    	return pHead == pHead->prev;
    }
    

    以上就是C语言带头双向循环链表的示例代码的详细内容,更多关于C语言带头双向循环链表的资料请关注我们其它相关文章!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜