C++超詳細講解單連結串列的實現

// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單連結串列列印
void SListPrint(SListNode* plist);
// 單連結串列尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單連結串列的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單連結串列的尾刪
void SListPopBack(SListNode** pplist);
// 單連結串列頭刪
void SListPopFront(SListNode** pplist);
// 單連結串列查詢
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單連結串列在pos位置之後插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單連結串列刪除pos位置之後的值
void SListEraseAfter(SListNode* pos);

typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next; 
}SListNode;

//連結串列節點開闢
SLTNode* BuySListNode(SLTDateType x)
{
	//動態分配一個節點
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		//分配失敗則列印錯誤資訊並結束程序
		perror("newnode fail:");
		exit(-1);
	}
	//成功則進行賦值
	newnode->data = x;
	newnode->next = NULL;
	//返回節點地址，以便後續操作
	return newnode;
}

//連結串列資料列印
void SListPrint(SLTNode* phead)//一級指標接收一級指標（列印不需改變指標本身內容）
{
	//建立一個定址指標
	SLTNode* cur = phead;
	while (cur!=NULL)//後續還有節點
	{
		//列印資料並指向下一個節點
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//最後列印空指標
	printf("NULLn");
	return;
}

//連結串列尾插資料
void SListPushBack(SLTNode** pphead, SLTDateType x)//二級指標接收一級指標（尾插存在需改變連結串列指標本身內容）
{
	//避免傳入錯誤(直接報錯便於找到錯誤位置)
	assert(pphead);
	//接收新節點的地址
	SLTNode* newnode=BuySListNode(x);
	//頭節點為空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾節點
		SLTNode* tail = *pphead;//建立定址節點
		//兩個及以上節點的情況
		while (tail->next != NULL)
		{
			//指向下一個節點
			tail = tail->next;	
		}
		//找到了
		tail->next = newnode;
	}
	return;
}

//連結串列前刪資料
void SListPopFront(SLTNode** pphead)
{
	//避免傳入錯誤(直接報錯便於找到錯誤位置)
	assert(pphead);
	//連結串列為空的情況
	if (*pphead == NULL)
	{
		return;
	}
	//建立指標儲存第二個節點地址
	SLTNode* next = (*pphead)->next;
	//釋放當前頭結點空間
	free(*pphead);
	//更新頭結點資料
	*pphead = next;
	return;
}

//連結串列資料查詢
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	//建立定址指標
	SLTNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data == x)//找到資料符合節點
		{
			return cur;//返回節點地址（好處：以便後續再尋找或修改）
		}
		else
		{
			//找下一個節點
			cur = cur->next;
		}
	}
	//未找到資料符合節點
	return NULL;
}

//連結串列pos位置往前插入(較難)（還有在pos位置之後插入，簡單點）
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	//避免傳入錯誤(直接報錯便於找到錯誤位置)
	assert(pphead);
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	//首結點符合的情況
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		//建立定址指標
		SLTNode* cur = *pphead;
		while (cur !=NULL)
		{
			if (cur->next!= pos)
			{
				cur = cur->next;//找到下一節點
			}
			else // 找到對應空間
			{
				cur->next = newnode;
				newnode->next = pos;
				return;//結束尋找（否則會一直插入，造成死迴圈）
			}
		}
	}
	//未找到則什麼也不幹
	return;
}

//連結串列pos位置往後插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
	return;
}

//連結串列pos位置刪除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//避免傳入錯誤(直接報錯便於找到錯誤位置)
	assert(pphead);
	assert(pos);
	//頭結點符合的情況
	if (*pphead == pos)
	{
		*pphead = (*pphead)->next;
		free(pos);
	}
	else
	{
		//建立定址指標
		SLTNode* cur = *pphead;
		while (cur != NULL)
		{
			if (cur->next != pos)
			{
				cur = cur->next;//找到下一節點
			}
			else // 找到對應空間
			{
				SLTNode* next = cur->next->next;
				free(cur->next);
				cur->next = next;
				return;//結束尋找
			}
		}
	}
	//未找到則什麼也不幹
	return;
}

//連結串列節點釋放
void SListDestory(SLTNode** pphead)
{
	//避免傳入錯誤(直接報錯便於找到錯誤位置)
	assert(pphead);
	//遍歷釋放
	SLTNode* cur = *pphead;
	while (cur)
	{
		//儲存下一個地址
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//置空
	*pphead = NULL;
	return;
}