💥【每天學習億點點系列】——重溫雙向帶頭回圈鏈表

頭檔案以及測驗檔案的實作
各個介面的實作
- 1.初始化
- 2.創建節點
- 3.尾插
- 4.頭插
- 5.尾刪
- 6.頭刪
- 7.列印
- 8.查找
- 9在任意位置之后插入
- 10.在任意位置之前插入
- 11.記錄節點個數
- 12.在任意位置之后洗掉
- 13.在任意位置之前洗掉
- 14.洗掉當前位置
- 15.判空
- 16.銷毀
注意點
- 1.雙向鏈表要初始化這個介面的，不同與單鏈表
- 2.帶個哨兵位，解決插入的問題
- 3.注意賦值時的先后順序
- 4.洗掉時要把節點free掉，同時要注意寫法
- 5.判空與以往不同，因為有哨兵位
- 6.不要像釋放順序表一樣釋放，因為空間物理上不連續

頭檔案以及測驗檔案的實作

List.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>

typedef int ListDataType;
typedef struct List
{
	struct List* pre;
	struct List* next;
	ListDataType x;
}List;

void Listinit(List** pphead);//為了讓雙向鏈表自己指向自己
void ListBackPush(List** pphead, ListDataType x);
void ListFrontPush(List** pphead, ListDataType x);
void ListPrint(List* pphead);
void ListBackPop(List** pphead);
void ListFrontPop(List** pphead);
List* ListFind(List* pphead,ListDataType x);
void ListPushAfter(List** pphead, ListDataType x, List* pos);
void ListPushBefore(List** pphead, ListDataType x, List* pos);
void ListPopAfter(List** pphead, List* pos);
void ListPopBefore(List** pphead, List* pos);
void ListPop(List** pphead, List* pos);
int ListSize(List* pphead);
bool ListEmpty(List* pphead);
void ListDestory(List** pphead);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test()
{
	List* phead;
	Listinit(&phead);
	ListBackPush(&phead, 1);
	ListBackPush(&phead, 2);
	ListFrontPush(&phead, 3);
	ListBackPop(&phead);
	ListFrontPop(&phead);
	List* pos=ListFind(phead,1);
	ListPushAfter(&phead, 2, pos); //復用，相當于尾插
	ListPushBefore(&phead, 3, pos);//復用，相當于頭插
	ListPopAfter(&phead, pos);//復用，相當于尾刪
	//ListPopBefore(&phead, pos);//復用，相當于頭刪
	/*ListBackPop(&phead);*/
	/*printf("%d\n", ListEmpty(phead));*/
	/*ListPopBefore(&phead, pos);*/ //檢驗156行的斷言
	ListPop(&phead, pos);
	ListPrint(phead);
}
int main()
{
	test();
	return 0;
}

各個介面的實作

1.初始化

void Listinit(List** pphead)
{
	assert(pphead);
	assert(*pphead);
	List* head = (List*)malloc(sizeof(List));
	if (head == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		*pphead = head;
	}
	(*pphead)->next = *pphead;
	(*pphead)->pre = *pphead;
}

2.創建節點

//創建節點
List* BuyNode(ListDataType x)
{
	List* newnode = (List*)malloc(sizeof(List));
	newnode->x = x;
	return newnode;
}

3.尾插

//尾插
void ListBackPush(List** pphead, ListDataType x)    //這邊不能用二級指標，因為你else里面那種情況會改變頭節點，而你不希望它改變，但是你if里面的情況希望改變，故用這種寫法寫不出來
{
	assert(pphead); 
	//由于初始化的原因，此時雙向鏈表里面已經有一個節點了, 迫于沒有辦法，用帶哨兵位的寫法,用哨兵位可以解決上面的問題，因為這時我不需要分情況來說
	List* newnode = BuyNode(x);   
	newnode->pre = (*pphead)->pre;
	(*pphead)->pre->next = newnode;
	newnode->next = (*pphead);
	(*pphead)->pre = newnode;
}

4.頭插

//頭插
void ListFrontPush(List** pphead, ListDataType x)
{
	assert(pphead);
	List* newnode = BuyNode(x);
	newnode->next = (*pphead)->next;
	(*pphead)->next->pre = newnode;
	(*pphead)->next = newnode;
	newnode->pre = (*pphead);
}

5.尾刪

//尾刪
void ListBackPop(List** pphead)
{
	assert(pphead);
	assert(*pphead);
	(*pphead)->pre->pre->next = (*pphead);  //這兒要注意寫的時候的先后順序
	(*pphead)->pre = (*pphead)->pre->pre;
}

6.頭刪

//頭刪
void ListFrontPop(List** pphead)
{
	assert(pphead);
	assert(*pphead);
	(*pphead)->next->next->pre = (*pphead);   //同樣也要注意順序
	(*pphead)->next = (*pphead)->next->next;
}

7.列印

//列印
void ListPrint(List* pphead)
{
	assert(pphead);
	List* cur = pphead->next;
	while (cur != pphead)
	{
		printf("%d ", cur->x);
		cur = cur->next;
	}
}

8.查找

List* ListFind(List* pphead,ListDataType x)
{
	assert(pphead);
	List* cur = pphead->next;
	while (cur != pphead)
	{
		if (cur->x == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
}

9在任意位置之后插入

//在任意位置之后插入
void ListPushAfter(List** pphead, ListDataType x, List* pos)
{
	assert(pphead);
	assert(*pphead);
	List* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next->pre = newnode;
	pos->next = newnode;
	newnode->pre = pos;
}

10.在任意位置之前插入

//在任意位置之前插入
void ListPushBefore(List** pphead, ListDataType x, List* pos)
{
	assert(pphead);
	assert(*pphead);
	List* newnode = BuyNode(x);
	pos->pre->next = newnode;
	newnode->pre = pos->pre;
	newnode->next = pos;
	pos->pre = newnode;
}

11.記錄節點個數


//記錄節點個數
int ListSize(List* pphead)
{
	List* cur = pphead->next;
	int n = 0;
	while (cur != pphead)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

12.在任意位置之后洗掉

//在任意位置之后洗掉
void ListPopAfter(List** pphead, List* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(ListSize(*pphead) != 1);
	pos->next->next->pre = pos;         //同上注意順序
	/*pos->next = pos->next->next;*/
	List*temp = pos->next->next;      //注意洗掉時這兒的寫法，要先創建一個臨時變數保存一下，因為你free掉了pos->next,如果你下面再將pos->next->next賦值給pos->next的話
	                                  //肯定時會出問題的，
	free(pos->next);
	pos->next = temp;
}

13.在任意位置之前洗掉

//在任意位置之前洗掉
void ListPopBefore(List** pphead, List* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(ListSize(*pphead) != 1);
	pos->pre->pre->next = pos;          //同上注意順序
	/*pos->pre = pos->pre->pre;*/
	List*temp = pos->pre->pre;          //同上面注意點一樣
	free(pos->pre);
	pos->pre = temp;
}

14.洗掉當前位置

//洗掉當前位置
void ListPop(List** pphead, List* pos)
{
	assert(pphead);
	assert(*pphead);
	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
	free(pos);
	pos = NULL;
}

15.判空

//判空
bool ListEmpty(List* pphead)
{
	/*return pphead == NULL;*/  //因為是有哨兵位的，所以不能這么判斷
	return pphead->next == pphead;
}

16.銷毀

//銷毀
void ListDestory(List** pphead)
{
	assert(pphead);
	//free(*pphead);  //鏈表不想順序表那樣，在物理上是連續的，所以不能這樣釋放，那是順序表的釋放方法
	//*pphead = NULL;
	List* cur = (*pphead)->next;
	while (cur != *pphead)
	{
		List* next = cur->next;
		free(cur);
		cur = next;
	}
	free(*pphead);
}

注意點

1.雙向鏈表要初始化這個介面的，不同與單鏈表

初始化為了讓雙向鏈表自己指向自己，形成環形

2.帶個哨兵位，解決插入的問題

//尾插
void ListBackPush(List** pphead, ListDataType x)    //這邊不能用二級指標，因為你else里面那種情況會改變頭節點，而你不希望它改變，但是你if里面的情況希望改變，故用這種寫法寫不出來
{
	assert(pphead); 
	//由于初始化的原因，此時雙向鏈表里面已經有一個節點了, 迫于沒有辦法，用帶哨兵位的寫法,用哨兵位可以解決上面的問題，因為這時我不需要分情況來說
	List* newnode = BuyNode(x);   
	newnode->pre = (*pphead)->pre;
	(*pphead)->pre->next = newnode;
	newnode->next = (*pphead);
	(*pphead)->pre = newnode;
}