[数据结构与算法]带头双向循环链表

我们以及学习了无头单链表，可以发现它有点麻烦

1.单链表不能从后面往前

2.找不到它的前驱（上一个地址）

（尾插，尾删，中插，中删）都要找到它的前一个节点

3.没有带头的节点：要用二级指针进行传参，不用改变传过来指针

那么我们可以介绍一下带头双向循环链表的好处

1.带头节点的好处

：不存储有效数据，带哨兵位的头节点不存入链表的长度，使得尾插更加方便，每次都在头后进行连接

2.双向的好处

：方便找到他的前一个节点

3.循环的好处

：头指向尾，尾指向头，头的前一个节点就是尾，方便找尾节点

??

?list.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int listdata;
typedef struct listnode
{
	struct listnode*prev;
	struct listnode*next;
	listdata data;
}listnode;

//初始化链表的哨兵位的头节点
listnode* listinit();
//实现尾插
void listpushback(listnode*phead, listdata x);

//实现打印，头节点不打印
void listprint(listnode*phead);

//头插
void listpushfront(listnode* phead, listdata x);

//头删
void listpopfront(listnode*phead);

void listpopback(listnode*phead);

listnode* listfind(listnode*phead,listdata x);

//中间加入
void listinsert(listnode*phead, listdata x);
//中间删除
void listerase(listnode*pos);
//销毁
void listdestroy(listnode*phead);

list.c?

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
//首先要先开辟节点
listnode* buynode(listdata x)
{
	listnode*newnode = (listnode*)malloc(sizeof(listnode));
	newnode->next = NULL;
	newnode ->prev = NULL;
	newnode->data = x;
	return newnode;
}


//初始化带哨兵位的头节点
listnode* listinit()
{
	//初始化头节点
	listnode*phead = buynode(0);
	//因为是循环链表，所以且是头节点
	头的前面和后面都是指向自己
    phead->next = phead;
	phead->prev = phead;
	return phead;
}



//实现尾插，和有无节点都无关都可以用这代码
void listpushback(listnode*phead, listdata x)
{
	//因为定义了双向链表
	//所以用头指针的prev就能找到尾节点
	listnode*tail = phead->prev;
	listnode*newnode = buynode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
//利用中间插入的代码也可以实现尾插，传入头的地址，在头的前面插入就是尾插
	/*listinsert(phead,x);*/
}



//打印
void listprint(listnode*phead)
{
	// 头不打印
//加入断言就方便如果有错误就好找一点
	assert(phead);//断言pheaed不可能为空指针，假设传参错误就会报错
	listnode*cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");

}



//头插

void listpushfront(listnode* phead, listdata x)
{
	listnode*newnode = buynode(x);
	listnode*first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
//使用中间插入的也可以实现头插，但应传入的是第一个节点的值，在第一个节点前面实现头插
	/*listinsert(phead->next,x);*/
}




//头删

void listpopfront(listnode*phead)
{
	//这个做法和有几个节点没有关系，如果只有一个节点的话，next就指向头节点，没有节点的话，就指向自己
	listnode*first = phead->next;
	listnode*second = first->next;
	//要先完成节点的链接才可以把头节点给free掉
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
//使用中间删除的代码也可以实现头删，也要找到头后面第一个节点，把这个节点给删除掉
	/*listerase(phead->next);*/
}



//尾删
void listpopback(listnode*phead)
{
	listnode*tail = phead->prev;
	listnode*prev = tail->prev;
	phead->prev = prev;
	prev->next = phead;
	free(tail);
	tail = NULL;
//使用中间删除的代码实现，找到它前一个节点，并把它删除掉
	/*listerase(phead->prev);*/
}



//查找某一个节点
listnode* listfind(listnode*phead,listdata x)
{
	//要找某个节点
	assert(phead);
	listnode*cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}



//在pos的前面插入
void listinsert(listnode*pos, listdata x)
{
	//加个断言
	assert(pos);
	listnode*newnode = buynode(x);
	listnode*prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos -> prev = newnode;
}




//中间删除
void listerase(listnode*pos)
{
	assert(pos);
	listnode*next = pos->next;
	listnode*prev = pos->prev;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}


//销毁
void listdestroy(listnode*phead)
{
	assert(phead);
	listnode*cur = phead->next;
	while (cur != phead)
	{
		//定义一个指针指向下一个，否则就找不到下一个节点了
		listnode*next = cur->next;
		free(cur);
		cur =next;
	}
	phead = NULL;//都得干掉，
}

test.c?

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"


//带头双向循环链表，最有用的链表结构，任意位置插入删除都是O（1），
//查找还是O(N);但是查找的时候有更有的算法
//1.平衡搜索树（AVL树和红黑树）
//2.哈希表
//3.B树 B ＋树系列
//跳表，布隆过滤器，位图




//但是我们其实只需要用insert 和erase就可以完成各种操作
void testlist()
{
	//我们要创建一个带头双向循环链表
	//即尾指向头，头指向尾，一个节点可以找到前后两个节点
	//首先就要初始化一个哨兵位的头节点
	
	listnode*plist = listinit();
	listpushback(plist, 1);
	listpushback(plist, 2);
	listpushback(plist, 3);
	listpushback(plist, 4);
	listpushback(plist, 5);
	listpopfront(plist);
	listprint(plist);
	 listpopback(plist);
	listpushfront(plist,0);
	listnode* pos=listfind(plist,3);
	if (pos)
	{
		//查找附带着修改的作用，找的同时可以对他进行修改
		pos->data = 30;
		printf("find\n");
		listprint(plist);
	}
	//想在3的前面插入一个300
	listinsert(pos, 300);
	//把pos的位置给删掉
	listerase(pos);
	listinsert(pos, 40);
	listprint(plist);
	listdestroy(plist);
}






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

?我以及将代码上传到我的gitee上面去了

wcode: 代码收集 - Gitee.com