C語言資料結構超詳細講解單向連結串列

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

typedef struct SListNode
{
	int data;//資料
	struct SListNode* next;//下一個節點的地址
}SListNode;

void SListPrint(SListNode* phead);//列印

SListNode* BuySListNode(SLTDataType x);//搞出一個新節點

void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//頭插

void SListPopBack(SListNode** pphead);//尾刪
void SListPopFront(SListNode** pphead);//頭刪

SListNode* SListFind(SListNode* phead, SLTDataType x);//查詢

void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之後插入

void SListErase(SListNode** pphead, SListNode* pos);//刪除pos位置
void SListEraseAfter(SListNode* pos);//刪除pos之後位置

void SListDestroy(SListNode** pphead);//銷燬

//列印
void SListPrint(SListNode* phead)
{
	//assert(phead);//沒必要斷言，空連結串列也能列印
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

//test.c
void TestSList1()
{
	SListNode* slist;//結構體指標，用於存節點的地址
	SListNode* n1 = (SListNode *)malloc(sizeof(SListNode));
	SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	slist = n1;

	SListPrint(slist);
}

//搞出一個新節點
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	return newnode;
}

//尾插
void SListPushBack(SListNode** pphead,SLTDataType x)//會改變實參slist，要傳二級指標
{
	assert(pphead);//就算連結串列是空，它的二級指標也不為空
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//遍歷找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void TestSList2()
{
	SListNode* slist = NULL;
	for (int i = 0; i < 6; i++)
	{
		SListPushBack(&slist,i);
	}
	SListPrint(slist);
}

//頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//就算連結串列是空，它的二級指標也不為空

	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void TestSList2()
{
	SListNode* slist = NULL;
	for (int i = 0; i < 6; i++)
	{
		SListPushFront(&slist,i);
	}
	SListPrint(slist);
}

//尾刪
void SListPopBack(SListNode** pphead)//如果只有一個節點但還要尾刪，就會改變實參slist，建議傳二級指標
{
	assert(pphead);//就算連結串列是空，它的二級指標也不為空
	//三種情況：
	//1.空
	//2.一個節點
	//3.多個節點
	if (*pphead == NULL)
	{
		return;
	}

	else if ((*pphead)->next == NULL)//優先順序，記得加括號
	{
		free(*pphead);
		*pphead = NULL;
	}

	//第一種寫法（用兩個指標，分別找最後一個和倒數第二個）
	else
	{
		SListNode* prev = NULL;//找倒數第二個元素，用於將它指向NULL
		SListNode* tail = *pphead;//找尾
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;//習慣性free掉就將其置空

		prev->next = NULL;
	}

	//方法二（直接找倒數第二個）
	//else
	//{
		//SListNode* tail = *pphead;//找尾
		//while (tail->next->next != NULL)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	//}
}

//頭刪
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	//1.空
	//2.非空
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

//查詢
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (phead != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//在pos位置之前插入（一般跟find配合使用）
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);//間接檢測連結串列是否為空，因為空連結串列找不到pos
	//1.pos是第一個節點（頭插）
	//2.pos不是第一個節點
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//在pos位置之後插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	newnode->next = next;//順序無所謂
	pos->next = newnode;
	//或者不定義next
	//newnode->next = pos->next;
	//pos->next = newnode;//順序要定好，否則會找不到
}

//刪除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;//好習慣
	}
}

//刪除pos之後位置
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next)//防止pos是最後一個元素
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

//銷燬
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}