数据结构（初阶）—— C语言实现双向带头循环链表

23次阅读
没有评论

数据结构（初阶）—— C语言实现双向带头循环链表

 

目录

一、链表种类的优劣

二、什么是双向循环链表 

三，双向循环链表各接口函数实现 

1.双链表的初始化

2.双链表的打印 

3.扩容函数 

4.双链表的尾插 

5.双链表的尾删

6.双链表的头插

7.双链表的头删 

8.双链表的查找

9. 双链表在pos位置之前插入结点

10.双链表删除pos位置的结点 

11.双链表的销毁 

四、源代码 

List.h

List.c

test.c

五、顺序表和双向链表的总结

1.顺序表的优点与缺点

2. 双向链表的优点与缺点

一、链表种类的优劣

链表可分为8种：

单向 双向
单向带头循环 双向带头循环
单向带头不循环 双向带头不循环
单向不带头循环 双向不带头循环
单向不带头不循环 双向不带头不循环

在C语言实现链表那篇博客中https://blog.csdn.net/sjsjnsjnn/article/details/123920224?spm=1001.2014.3001.5501

主要实现的是单向不带头非循环的链表结构；

此结构：

        结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
————————————————————————————————————————-
本次主要分析
双向带头循环链表的链表结构；
此结构：
        
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向
循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而
简单了；

二、什么是双向循环链表 

     双向循环链表和单链表都是由结点组成的，单链表包含一个数据域和一个指针域构成，而双向循环链表不同，它是由一个数据域和两个指针域组成，其中指针包含前驱指针（prev）和后继指针（next）；

数据结构（初阶）—— C语言实现双向带头循环链表

数据结构（初阶）—— C语言实现双向带头循环链表

三，双向循环链表各接口函数实现 

1.双链表的初始化

//双向带头循环链表的初始化
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//创建头结点
	phead->next = phead;//后继指针指向头
	phead->prev = phead;//前驱指针指向头
	return phead;
}

2.双链表的打印 

//双向带头循环链表的打印
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->Data);
		cur = cur->next;
	}
	printf("\n");
}

3.扩容函数 

//增容函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->Data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

数据结构（初阶）—— C语言实现双向带头循环链表

4.双链表的尾插 

//双向带头循环链表的尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

数据结构（初阶）—— C语言实现双向带头循环链表

5.双链表的尾删

//双向带头循环链表的尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
	//ListErase(phead->prev);//尾删就相当于复用Erase这个函数
}

 数据结构（初阶）—— C语言实现双向带头循环链表

6.双链表的头插

//双向带头循环链表的头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;//先找到头
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
	//ListInsert(phead->next, x);
}

 数据结构（初阶）—— C语言实现双向带头循环链表

7.双链表的头删 

//双向带头循环链表的头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//如果哨兵位的后继指针指向的是头，就不能去调用头删
	LTNode* next = phead->next;//先找到头结点
	LTNode* nextNext = next->next;//再找到头结点的下一个结点
	phead->next = next->next;
	nextNext->prev = phead;
}

 数据结构（初阶）—— C语言实现双向带头循环链表

8.双链表的查找

//双向带头循环链表的查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;//从头结点出发
	while (cur != phead)
	{
        //找到返回对应的地址
		if (cur->Data == x)
		{
			return cur;
		}
        //找不到继续向后找
		cur = cur->next;
	}
    //彻底找不到
	return NULL;
}

9. 双链表在pos位置之前插入结点

//双向带头循环链表pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;//先找到pos的前一个结点的位置
	LTNode* newnode = BuyListNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

数据结构（初阶）—— C语言实现双向带头循环链表

10.双链表删除pos位置的结点 

//双向带头循环链表pos位置删除
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;//找到pos的前一个位置
	LTNode* posNext = pos->next;//和pos的后一个位置
    //把前一个结点和后一个结点链接起来
	posPrev->next = posNext;
	posNext->prev = posPrev;
    //释放pos结点
	free(pos);
	pos = NULL;
}

数据结构（初阶）—— C语言实现双向带头循环链表

11.双链表的销毁 

//双向带头循环链表的销毁
void ListDestroy(LTNode* phead)
{
    //在销毁链表的时候，逐个销毁，销毁前一个，必须要保存下一个结点的地址
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

四、源代码 

List.h

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType Data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

//双向带头循环链表的初始化
LTNode* ListInit();

//双向带头循环链表的打印
void ListPrint(LTNode* phead);

//增容函数
LTNode* BuyListNode(LTDataType x);

//双向带头循环链表的尾插
void ListPushBack(LTNode* phead, LTDataType x);

//双向带头循环链表的尾删
void ListPopBack(LTNode* phead);

//双向带头循环链表的头插
void ListPushFront(LTNode* phead, LTDataType x);

//双向带头循环链表的头删
void ListPopFront(LTNode* phead);

//双向带头循环链表的查找
LTNode* ListFind(LTNode* phead, LTDataType x);

//双向带头循环链表pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);

//双向带头循环链表pos位置删除
void ListErase(LTNode* pos);

//双向带头循环链表的销毁
void ListDestroy(LTNode* phead);

List.c

#include "List.h"

//双向带头循环链表的初始化
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//创建头结点
	phead->next = phead;//后继指针指向头
	phead->prev = phead;//前驱指针指向头
	return phead;
}

//双向带头循环链表的打印
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->Data);
		cur = cur->next;
	}
	printf("\n");
}

//增容函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->Data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

//双向带头循环链表的尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

//双向带头循环链表的尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
	//ListErase(phead->prev);//尾删就相当于复用Erase这个函数
}

//双向带头循环链表的头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
	//ListInsert(phead->next, x);
}

//双向带头循环链表的头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
	phead->next = next->next;
	nextNext->prev = phead;
}

//双向带头循环链表的查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->Data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//双向带头循环链表pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

//双向带头循环链表pos位置删除
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

//双向带头循环链表的销毁
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

test.c

#include "List.h"


void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPushBack(plist, 7);
	ListPushBack(plist, 8);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);

	ListPushFront(plist, 4);
	ListPushFront(plist, 3);
	ListPushFront(plist, 2);
	ListPushFront(plist, 1);
	ListPrint(plist);
	//ListPopFront(plist);
	//ListPopFront(plist);
	//ListPrint(plist);

	LTNode* ret = ListFind(plist, 4);
	ListInsert(ret, 30);
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;
}

int main()
{
	TestList1();
	return 0;
}

五、顺序表和双向链表的总结

1.顺序表的优点与缺点

优点：（可以使用下标访问 ）     

1.支持随机访问；需要随机访问结构支持算法可以很好的适用；

        2.cpu高速缓存命中率更高 

缺点：

        1.头部、中部插入删除数据时间效率低。O(N)

        2.连续的物理空间，空间不够需要增容；

                ①、增容有一定程度消耗

                ②、为了避免频繁增容，一般我们都按倍数去增，用不完可能存在一定的空间浪费

2. 双向链表的优点与缺点

优点：（不可以使用下标访问 ）

        1.任意位置插入，效率高；o(1)

        2.按需申请释放空间；

缺点：

        1.不支持随机访问；意味着：一些排序，二分查找在这种结构上不适用；

        2.链表存储一个值，同时要存储链接指针，也有一定的消耗；

        3.cpu高速缓存命中率更低；

正文完
发表至： 编程语言
2023-06-21
 0