💥【每天學習億點點系列】——重溫單鏈表

頭檔案以及測驗部分的代碼
單鏈表各個介面的實作
- 1.尾插
- 2.尾刪
- 3.列印
- 4.頭插
- 5.頭刪
- 6.查找
- 7.在任意位置之前插入
- 8.在任意位置之后插入
- 9.洗掉當前位置
- 10.洗掉任意位置的前一個節點
- 11.洗掉任意位置的后一個節點
- 12.銷毀
- 13.判空
注意點
- 1.單鏈表的實作方式里面不能用一級指標接收的方式來實作也不可能做的到
- 2.單鏈表不需要初始化這個介面
- 3.尾節點如何解決的問題（懸疑問題）
- 4. free時注意函式之間可能會有影響（懸疑問題）
- 5.很多介面都要注意分類討論

頭檔案以及測驗部分的代碼

SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<stdlib.h>
typedef int SDataType;
typedef struct Node
{
	SDataType data;
	struct Node* next;
}Node;


/*void SListinit(Node** phead);*/  //單鏈表不需要這個介面
void SListPushBack(Node** phead, SDataType x);
void SListPopBack(Node** phead);
void SListPrint(Node* phead);
void SListPushFront(Node** phead, SDataType x);
void SListPopFront(Node** phead);
Node* SListFind(Node* phead, SDataType x);
void SListPushBefore(Node** phead, Node* pos, SDataType x);//在任意位置之前插入
void SListPushAfter(Node** phead, Node* pos, SDataType x);//在任意位置之后插入
void SListPop(Node** phead, Node* pos);//洗掉查找的節點
void SListPopBefore(Node** phead, Node* pos);//洗掉任意位置之后的節點
void SListPopAfter(Node** phead, Node* pos);//洗掉任意位置之前的節點
bool SListEmpty(Node* phead);
void SListDestory(Node** phead);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test()
{
	/*Node a;*///這種方式是寫不出來的，之前在寫stack就深有體會
	Node* a=NULL;
	//SListinit(&a);//單鏈表不要這個介面
	SListPushBack(&a, 1);
	SListPushBack(&a, 2);
	SListPopBack(&a);
	SListPopBack(&a);
	SListPushFront(&a, 1);
	SListPushFront(&a, 0);
	SListPopFront(&a);
	SListPopFront(&a);
	SListPushBack(&a, 1);
	SListPushBack(&a, 2);
	Node* pos = SListFind(a, 2);
	SListPushBefore(&a, pos, 3);
	pos = SListFind(a, 1);
	SListPushBefore(&a, pos, 0);  //復用，相當于頭插
	pos = SListFind(a, 0);
	SListPushAfter(&a, pos, 66);
	SListPop(&a, pos);//復用，相當于頭刪
	pos = SListFind(a, 1);
	SListPopAfter(&a, pos);
	SListPopBefore(&a, pos);//復用，相當于頭刪
	SListPopAfter(&a, pos);//復用，相當于尾刪
	/*printf("%p\n", SListFind(a, 2));*/
	/*SListPopFront(&a);  判斷191行的斷言*/
	/*SListPopBack(&a);*/  //測驗129行的斷言的
	//SListDestory(&a);
	SListPrint(a);
}


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

單鏈表各個介面的實作

1.尾插

void SListPushBack(Node** phead, SDataType x)
{
	assert(phead);
	Node* tail = *phead;
	//沒有節點
	if ((*phead == NULL))
	{
		*phead = BuyNode(phead, x);
		(*phead)->next = NULL;
	}
	//有節點
	else
	{
		while (tail->next)    //采用遍歷的方法找尾節點，同時這兒要注意while（）里面的寫法
		{
			tail = tail->next;
		}
		Node* newnode = BuyNode(phead, x);
		tail->next = newnode;
		newnode->next = NULL;
	}
}

2.尾刪

void SListPopBack(Node** phead)
{
	assert(phead);
	assert(*phead);
	/*assert(!SListEmpty(phead));*/
	//只有一個節點的情況
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	//多個節點的情況
	else
	{
		Node* tail = *phead;
		while (tail->next)
		{
			tail = tail->next;
		}
		Node* tailpre = *phead;
		while (tailpre->next != tail)
		{
			tailpre = tailpre->next;
		}
		tailpre->next = tail->next;
		free(tail);
		tail = NULL;
	}
}

3.列印

void SListPrint(Node* phead)
{
	while (phead)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

4.頭插

void SListPushFront(Node** phead, SDataType x)
{
	assert(phead);
	//鏈表中沒有節點的情況
	if (*phead == NULL)
	{
		Node* newnode = BuyNode(phead, x);
		newnode->next = NULL;
		*phead = newnode;
	}
	//鏈表中有節點的情況
	else
	{
		Node* newnode = BuyNode(phead, x);
		newnode->next = *phead;
		*phead = newnode;
	}
}

5.頭刪

void SListPopFront(Node** phead)
{
	assert(phead);
	assert(*phead);
	//一個節點
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	//多個節點
	else
	{
		Node* newhead = (*phead)->next;
		free(*phead);
		*phead = newhead;
	}
}

6.查找

Node* SListFind(Node* phead, SDataType x)
{
	assert(phead);
	Node* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
}

7.在任意位置之前插入

void SListPushBefore(Node** phead, Node* pos, SDataType x)
{
	assert(phead);
	//在第一個節點之前插入的情況
	if (pos==*phead)
	{
		Node* newnode = BuyNode(phead, x);
		newnode->next = *phead;
		*phead = newnode;
	}
	//在非第一個節點之前插入的情況，這時就要記錄你要插入節點的前一個節點了
	else
	{
		Node* pospre = *phead;
		while (pospre->next != pos)
		{
			pospre = pospre->next;
		}
		Node* newnode = BuyNode(phead, x);
		pospre->next = newnode;
		newnode->next = pos;
	}
}

8.在任意位置之后插入

void SListPushAfter(Node** phead, Node* pos, SDataType x)
{
	assert(phead);
	//由于是在節點之后插入，所以沒必要分類了
	Node* newnode = BuyNode(phead, x);
	newnode->next = pos->next;
	pos->next = newnode;
}

9.洗掉當前位置

void SListPop(Node** phead, Node* pos)
{
	assert(phead);
	assert(*phead);
	//洗掉第一個節點的情況
	if (pos == *phead)
	{	
//		free(*phead);
不能這樣寫，因為如果你這樣寫free掉*phead時，相當于把pos也釋放掉了，因為你的pos
是通過find這個介面找到的，而這個介面也是二級指標接收，所以你在這個介面總釋放
掉了*phead，也會有影響到find的那個介面，應該用一個指標提前記錄好新的頭節點
//		*phead =pos->next;
		Node* newhead = pos->next;
		free(*phead);
		*phead = newhead;
	}
	//洗掉的不是第一個節點時
	else
	{
		Node* pospre = *phead;
		while (pospre->next != pos)
		{
			pospre = pospre->next;
		}
		pospre->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

10.洗掉任意位置的前一個節點

void SListPopBefore(Node** phead, Node* pos)
{
	assert(phead);
	assert(*phead);
	assert((*phead)->next != NULL); //當鏈表中只有一個元素時，此時它之后也不能洗掉了，因為之后沒有元素了，
    //當pos為第二個節點，也就是要洗掉的是第一個節點時,也就是頭刪，這兒也可以選擇復用
	if (pos == (*phead)->next)
	{
		Node* newhead = (*phead)->next;
		free(*phead);
		*phead = newhead;
	}
	//其他情況
	else
	{
		Node* posprepre = *phead;
		while (posprepre->next->next != pos)
		{
			posprepre = posprepre->next;
		}
		posprepre->next = pos;
		free(posprepre->next);
		posprepre->next = NULL;
	}
}

11.洗掉任意位置的后一個節點

void SListPopAfter(Node** phead, Node* pos)
{
	assert(phead);
	assert(*phead);
	assert((*phead)->next != NULL);//當鏈表中只有一個元素時，此時它之后也不能洗掉了，因為之后沒有元素了，
	Node* posnextnext = pos->next->next;
	free(pos->next);
	pos->next = posnextnext;
}

12.銷毀

void SListDestory(Node** phead)
{
	assert(phead);
	assert(*phead);
	Node* cur = *phead;
	Node* next = NULL;
	while (cur)
	{
		next= cur->next;
		free(cur);
		cur = next;
	}
	printf("銷毀成功\n");
}

13.判空

bool SListEmpty(Node* phead)
{
	return phead == NULL;
}

注意點

1.單鏈表的實作方式里面不能用一級指標接收的方式來實作也不可能做的到

因為像這些地方你必須要解參考傳過來的指標才能改變外面，而你型別又不同，所以這種方式不可能實作

這一點在堆疊的實作當中就深有體會，具體可以去看鏈接

2.單鏈表不需要初始化這個介面

單鏈表不需要初始化這個介面，而且你單鏈表本來就是由一個個插入的節點構成，為什么要初始化了，又初始化什么東西了也沒東西給你初始化呀，

3.尾節點如何解決的問題（懸疑問題）

尾節點一般大家寫單鏈表的時候都是通過便利去找的，這樣效率會比較低，但是不是只能這么實作了？我有一個想法，我們可以用結構體包裹的方法，定義一個單鏈表型別的結構體，這個結構體里面包含了一個頭指標和尾指標，因為整個結構體其實就可以看成由這兩個指標構成的，然后這兩個指標又是節點型別的結構體，具體我還沒實作，只是想法而已，如果實作了效率將大大提高

4. free時注意函式之間可能會有影響（懸疑問題）

在這里插入圖片描述

如果這段代碼你用我注釋中的那種寫法來寫的話，你會發現當釋放掉phead時，pos居然也釋放掉了，我猜測具體原因可能是與Find那個函式之間存在一些影響，暫且把它做為懸疑問題，日后回過頭來再看看，

5.很多介面都要注意分類討論

這兒就不具體再說了，在上面的各個函式的實作里面，注釋都寫的很清楚，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/293960.html

標籤：其他

上一篇：【每天學習億點點系列】——OJ203題：移除鏈表元素

下一篇：順序表基本功能函式的實作