C語言 單向鏈表的增刪查改快速掌握

Posted on by

前言

鏈表是線性表的鏈式存儲結構，它可以以O(1)的時間復雜度進行插入或者刪除，同時由於是鏈式結構相比順序表而言，不會存在空間浪費的情況。而鏈表又分為帶頭單向鏈表，不帶頭單向鏈表，帶頭循環鏈表，不帶頭循環鏈表，帶頭雙向循環鏈表，不帶頭雙向循環鏈表，帶頭雙向鏈表，不帶頭雙向鏈表，總共有八種，其中結構最簡單的是不帶頭單向鏈表，也是實現起來最容易出錯的。並且我們在網上進行鏈表的oj時，題目基本也是不帶頭的單向鏈表，而且也是互聯網大廠面試中最容易考的。

一、創建

typedef int SLTDadaType;//存放的數據類型
struct SListNode
{
	SLTDadaType _data;//存放的數據
	struct SListNode* _next;//指向下一個節點的指針
};
typedef struct SListNode  SListNode;

二、單向鏈表的函數聲明

SListNode* BuyListNode(SLTDadaType x);//創建一個節點
SListNode* SListPushBack(SListNode* head, SLTDadaType x);//尾插
SListNode* SListPopBack(SListNode* head);//頭插
SListNode* SListPushFornt(SListNode* head, SLTDadaType x);//尾刪
SListNode* SListPopFornt(SListNode* head);//頭刪
SListNode* SListFind(SListNode* head, SLTDadaType x);//查找一個節點
void SListModify(SListNode* head, SLTDadaType x,SLTDadaType y);//x修改

三、函數實現

1.創建節點

SListNode* BuyListNode(SLTDadaType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	newnode->_data = x;
	newnode->_next = NULL;
	return newnode;
}

2.尾插節點

SListNode* SListPushBack(SListNode* head, SLTDadaType x)
{
	SListNode* newnode = BuyListNode(x);//無論節點是否為空，都先進行創建一個節點
 
	if (head == NULL)  //頭節點為空
	{
		head = newnode;
		return head;
	}
	else //頭節點不為空，直接遍歷到鏈表結尾進行尾插
	{
		SListNode* tail = head; 
		while (tail->_next != NULL)
		{
			tail = tail->_next;
		}
		tail->_next = newnode;
		return head;
	}
}

3.頭插

SListNode* SListPushFornt(SListNode* head, SLTDadaType x)
{
	SListNode* newnode = BuyListNode(x);
	newnode->_next = head;
	head = newnode;
	return head;
}

4.尾刪

SListNode* SListPopBack(SListNode* head)
{
	//1.空
    //2.隻有一個節點
	//3.有多個節點
	if (head == NULL)
	{
		return head;
	}
	else if (head->_next== NULL)
	{
		free(head);
		head = NULL;
		return head;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = head;
		while (tail->_next != NULL)  //利用前指針來保存要刪除的節點的前一個節點
		{
			prev = tail;
			tail = tail->_next;
		}
		free(tail);
		if (prev != NULL)
		prev->_next = NULL;
		return head;
	}
}

5.頭刪

SListNode* SListPopFornt(SListNode* head)
{
 
	if (head == NULL)
	{
		return head;
	}
	else
	{
		SListNode* cur = head->_next;
		free(head);
		head = cur;
		return head;
	}
}

6.查找節點

SListNode* SListFind(SListNode* head, SLTDadaType x)
{
	SListNode* cur = head;
	while (cur)
	{
		if (cur->_data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->_next;
		}
	}
	return NULL;
}

7.修改

void SListModify(SListNode* head, SLTDadaType x, SLTDadaType y)//x修改
{
	SListNode* find = SListFind(head, x);
	if (find)
	{
		find->_data = y;
	}
	else
	{
		printf("對不起，您要修改的值不存在\n");
	}
}

總結

本篇文章主要是針對單向鏈表一些基本操作的代碼實現，若有寫的錯誤或值得改進的地方，請大傢多多留言指出。

最後，也請大傢多多支持，求關註！！！

到此這篇關於C語言 單向鏈表的增刪查改快速掌握的文章就介紹到這瞭,更多相關C語言 單向鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：