帶頭雙向回圈鏈表

我們以及學習了無頭單鏈表，可以發現它有點麻煩

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