初識鏈表（無頭單向非回圈鏈表的增刪查改）

目錄

鏈表相對于順序表的優點是 操作資料時不需要大規模地移動原有的資料

1. 中間/頭部的插入洗掉，時間復雜度為O(N)

SListNode.h(頭檔案的參考，結構體的定義）

SListNode.c(各個函式的定義）

test.c(測驗各個函式的功能）

列印函式

插入資料時開辟空間的函式

一、增（頭插 尾插 指定位置前或后插入）

1、頭插

2.頭刪

3、尾插

4、尾刪

二、查找資料

三、洗掉指定資料與洗掉指定資料前或后端的資料

1.洗掉指定資料

2.洗掉指定資料后邊的資料

3.洗掉指定元素前面的那個元素

四、指定資料前或后插入資料

1.指定資料后插入新資料

2.指定資料前插入資料

五、改

先大致看一下整體的代碼 好利于下面的閱讀和理解

SListNode.h(頭檔案的參考，結構體的定義）

SListNode.c(各個函式的定義）

test.c(測驗各個函式的功能）

列印函式

void SListPrint(SLTNode* plist)
{
	while (plist != NULL)//只要結點不是空就列印其對應的值 鏈表尾是空   
	{
		printf("%d->", plist->data);
		plist = plist->next;
	}
	printf("NULL\n");
}

插入資料時開辟空間的函式

SLTNode* BuySList(val)
{
	SLTNode* node= (SLTNode*)malloc(sizeof(SLTNode));
	node->data = val;
	node->next = NULL;
	return node;

}

一、增（頭插 尾插 指定位置前或后插入）

插入資料時要考慮幾種的情況：1.鏈表為空 2.鏈表中只有一個資料

1、頭插

void SListPushFront(SLTNode** plist, SLTDataType val)
{
	SLTNode* node = BuySList(val);//創建一塊空間 把資料存入該空間 再把指向該空間的地址與鏈表相連
	node->next = *plist;
	*plist = node;//這里要改變*plist 的值 傳參時就要傳*plist 的地址 所以形參是二級指標用來接受一級指標的地址（*plist是結構體指標）

}

2.頭刪

void SListPopFront(SLTNode** plist)
{
	if (*plist == NULL)
	{
		printf("SLTNode is NULL\n");
		return;//考慮鏈表是否為空 是空就無資料可刪 回傳
	}
	else
	{
		/*SLTNode* node= *plist;
		node = node->next;*/ 

		//(*plist) = (*plist)->next;
		SLTNode* node = (*plist)->next;//保存下一個結點的地址 
		free(*plist);//既然是頭刪就要釋放第一個結點的地址指向的那塊空間 
		*plist = NULL;//釋放后要置空 防止記憶體泄漏
		*plist = node;//讓保存的下一個結點的地址當新地址即新的頭   把頭刪了要有新的頭

	}

}

3、尾插

void SListPushBack(SLTNode** plist,SLTDataType val)
{
	SLTNode* newnode = BuySList(val);//既然是要插入資料 那開始就為其開辟一塊空間 并且保存其地址 后面直接連在鏈表上即可
	if (*plist == NULL)
	{
	*plist = newnode;//考慮鏈表頭是空的情況  這是就直接把開辟的新空間的地址當作頭即可

	}
	
	else
	{
		SLTNode* tail = *plist;//如果不是頭為空的情況就要去找鏈表的尾了 找到尾巴后在其后面把開始開辟的空空間連在后邊 就是尾插了
		while (tail->next != NULL)
		{
			
			tail = tail ->next;//這里要注意加上括號 因為* 和-> 都是解參考 同級 要用括號括起來 
		}
		//(*plist)->next=newnode;
		tail->next = newnode;//連接


	}

}

4、尾刪

void SListPopBack(SLTNode** plist)
{
	//考慮三種情況 
	//1.鏈表為空
	if (*plist == NULL)
	{
		printf("SLTNode is NULL!\n");
		return;
	}
	//2.鏈表只有一個元素（結點）
	else if ((*plist)->next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	//3.鏈表有多個元素
	else
	{
		SLTNode* node = NULL;
		SLTNode* tail = *plist;
		while (tail->next != NULL)
		{
			node = tail;//尾刪要找尾 同時還要讓尾上一個結點的next為空 這就找到尾的上一個結點的地址了 這里是先保存一份尾 再讓其往后走 形成一前一后的結構
			tail = tail->next;
		}
		free(tail);//釋放尾置空 達到尾刪的效果
		tail = NULL;
		node->next = NULL;//讓尾的上一個元素的next為空 因為鏈表最后得是空的
	}

}

二、查找資料

SLTNode* SListFound(SLTNode* plist, SLTDataType val)
{
	SLTNode* node = plist;//這里因為不要改變實參 所以傳的實參的值 前面涉及到改變實參 所傳的是實參的地址 
	while (node)//讓頭往后走 遍歷鏈表的每個元素
	{
		if (node->data == val)//判斷node指向的資料是不是我們要查找的值 如果是就回傳其地主 不是的話就讓node往后走 直到尾
		{
			return node;
		}
		else
		{
			node = node->next;
		}
	}
	return NULL;//如果上面都沒有回傳地址就會往下執行 那么就是沒有找到就回傳空指標

}

根據回傳值列印要查找的資料

三、洗掉指定資料與洗掉指定資料前或后端的資料

1.洗掉指定資料

void SListErasecur(SLTNode** plist, SLTDataType val)//洗掉指定的資料 
{
	SLTNode* node = *plist;//拷貝一份頭地址 防止改變鏈表頭
	SLTNode* prev = NULL;//定義一個前驅指標 形成一前一后地址的結構  好讓鏈表能洗掉資料后還是連在一起的
	if (*plist == NULL)
	{
		printf("the SLTNode is already NULL!\n");
		return;
	}
	
	else
	{
		SLTNode* node = *plist;
		while (node->data != val)
		{
			prev = node;
			node = node->next;
		}//找到給定的資料的地址和其上一個元素的地址
		if (prev == NULL)//如果prev是空 那么就是第一個就是我們要刪的資料 就是相當于頭刪了 
		{
			
				SLTNode* node1 = (*plist)->next;
				free(*plist);
				*plist = NULL;
				*plist = node1;
			
		}
		else//否則就讓指定資料的前一塊空間的next指向指定資料后面的那一塊空間 釋放給定的資料的空間
		{
			prev->next = prev->next->next;
			free(node);
			node = NULL;

		}
	}
}

2.洗掉指定資料后邊的資料

void SListEraseAfter(SLTNode** plist, SLTDataType val)
{
	SLTNode* node = *plist;//拷貝頭
	if (*plist == NULL)//如果為空鏈表
	{
		printf("NLTNode is NULL\n");
		return;
	}
	else if ((*plist)->next == NULL)//如果只有一個資料 無法實作
	{
		printf("error!\n");
		return;
	}
	else
	{
		node = SListFound(*plist, val);//呼叫上面的查找函式 找我們給定的那個資料的位置 再去對其后面的資料進行洗掉
		node->next = node->next->next;//跳過給定資料后面的元素 調整指向順序
		free(node->next);//釋放要刪資料的空間
		node->next = NULL;
	}
}

3.洗掉指定元素前面的那個元素

思路： 轉變一下思想直接交換給定元素和其前一個元素的值 在釋放給定元素的空間可以達到相同效果

void SListEraseBefore(SLTNode** plist, SLTDataType val)
{
	if (*plist == NULL)
	{
		printf("SLTNode is already NULL!\n");
		return;
	}
	else if ((*plist)->next == NULL)
	{
		*plist = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* node = *plist;

		while (node->data != val)
		{
			prev = node;
			node = node->next;
		}
		if (prev == NULL)
		{
			printf("error! \n");
			return;
		}
		else
		{
			/**plist = prev->next;
			free(prev);
			prev = NULL;*/
			SLTNode* swapnode=(SLTNode*)malloc(sizeof(SLTNode));
			swapnode->data = 0;
			swapnode->data = prev->data;
			prev->data = node->data;
			node->data =swapnode->data;
			prev->next = prev->next -> next;
			free(node);
			node = NULL;
		}


	}

}

四、指定資料前或后插入資料

1.指定資料后插入新資料

void SListInsertAfter(SLTNode** plist,SLTDataType des, SLTDataType val)
{
	SLTNode* newnode = BuySList(val);
	SLTNode* desnode=SListFound(*plist, des);
	if (desnode == NULL)
	{
		printf("not find!\n");
		return;
	}
	else
	{ 
		newnode->next = desnode->next;
		desnode->next = newnode;
	
	}


}

2.指定資料前插入資料

思路：常規的思路是去找指定位置的元素地址 弄個前驅指標 找到指定元素上一個元素的地址將其洗掉 但是刪了后要讓被刪元素的上一個元素的next指向我們給定的資料的地址 但是這個不好找 很麻煩 所以轉變思路 直接在給定資料后插入新資料 再交換兩者的位置即可實作

void SListInsertBefore(SLTNode** plist, SLTDataType des, SLTDataType val)
{
	SLTNode* newnode=BuySList(val);
	SLTNode* desnode = SListFound(*plist, des);
	SLTNode* swapnode = (SLTNode*)malloc(sizeof(SLTNode));
	swapnode->data = 0;
	if (*plist == NULL)
	{
		*plist = newnode;
	}
	else
	{
		newnode->next = desnode->next;
		desnode->next = newnode;
		swapnode->data = desnode->data;
		desnode->data = newnode->data;
		newnode->data = swapnode->data;
		/*swapnode = desnode;
		desnode= newnode;
		newnode= swapnode;*/


	}
}

五、改

這個就比較簡單了 找到給定元素地址 將其指向的資料改變即可

void SListModify(SLTNode** plist, SLTDataType des, SLTDataType val)
{
	SLTNode* node = SListFound(*plist,des);
	if (node == NULL)
	{
		printf("error!\n");
		return;
	}
	else
	{
		node->data = val;
	}
}

最后給上代碼運行圖

創作不易 點贊支持一下吧! 若有不足 多加指點 互相交流呀~