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

数据结构(初阶)—— C语言实现双向带头循环链表_第1张图片

目录

一、链表种类的优劣

二、什么是双向循环链表 

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

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语言实现双向带头循环链表_第2张图片

数据结构(初阶)—— C语言实现双向带头循环链表_第3张图片

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

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张图片

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张图片

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张图片

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张图片

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张图片

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语言实现双向带头循环链表_第9张图片

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语言实现双向带头循环链表_第10张图片

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 
#include 
#include 

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高速缓存命中率更低;

你可能感兴趣的