C語(yǔ)言中單鏈表怎么用

這篇文章將為大家詳細(xì)講解有關(guān)C語(yǔ)言中單鏈表怎么用，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

1、單鏈表

概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。

 （鏈表和我們生活中最接近的就是火車了。）

2、單鏈表的實(shí)現(xiàn)

接下來(lái)我們來(lái)實(shí)現(xiàn)單鏈表的增刪查改

頭文件

#pragma once
 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
typedef int SLDataType;
 
//鏈表的創(chuàng)建
typedef struct SListNode
{
	SLDataType data;//val
	struct SListNode* next;//存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址
}SListNode,SLN;
 
//打印鏈表
void SListPrint(SListNode* phead);
 
//尾插
void SListPushBack(SListNode** pphead, SLDataType x);
 
//頭插
void SListPushFront(SListNode** pphead, SLDataType x);
 
//尾刪
void SListPopBack(SListNode** pphead);
 
//頭刪
void SListPopFront(SListNode** pphead);
 
//查找
SListNode* SListFind(SListNode* phead, SLDataType x);
 
//在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLDataType x);
 
//刪除pos位置
void SListErase(SListNode** pphead, SListNode* pos);
 
//在pos位置之后插入
void SlistInserAfter(SListNode* pos, SLDataType x);
 
//刪除pos后的值
void SlistEraseAfter(SListNode* pos);
 
//用完銷毀
void SListDestroy(SListNode** pphead);

函數(shù)的實(shí)現(xiàn)

（1）打印鏈表

void SListPrint(SListNode* phead)
{
	assert(phead);
 
	SListNode* cur = phead;
 
	if (cur == NULL)
	{
		printf("SList is NULL\n");
	}
 
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

（2）動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)

將一個(gè)data x動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)。

SListNode* BuySList(SLDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

（3）尾插

void SListPushBack(SListNode** pphead, SLDataType x)
{
	assert(pphead);
 
	SListNode* newnode = BuySList(x);
	
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//走完循環(huán)找到尾
		tail->next = newnode;
	}
 
}

（4）頭插

void SListPushFront(SListNode** pphead, SLDataType x)
{
	assert(pphead);
 
	SListNode* newnode = BuySList(x);
 
	newnode->next = *pphead;
	*pphead = newnode;
 
}

（5）尾刪

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
 
	//當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)時(shí)
	if (*pphead == NULL)
	{
		printf("SListNode is NULL\n");
		return;
	}
	//當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)時(shí)
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//當(dāng)鏈表有多個(gè)結(jié)點(diǎn)時(shí)
	else
	{
		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

（6）頭刪

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
 
	if (*pphead == NULL)
	{
		printf("SList is NULL\n");
		return;
	}
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

（7）查找

SListNode* SListFind(SListNode* phead, SLDataType x)
{
	assert(phead);
 
	SListNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		//如果沒找到就往下走
		cur = cur->next;
	}
	//循環(huán)完成后還沒找到就說(shuō)明鏈表中沒有該值
	return NULL;
}

（8）在pos之前插入

void SListInsert(SListNode** pphead, SListNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
 
	//pos是第一個(gè)位置
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
 
	//pos不是第一個(gè)位置
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySList(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

（9）刪除pos

void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
 
	//1、頭結(jié)點(diǎn)為空
	if (*pphead == NULL)
	{
		printf("SList is NULL\n");
		return;
	}
	//2、刪除第一個(gè)結(jié)點(diǎn)
	else if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	//3、其他結(jié)點(diǎn)
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

（10）在pos之后插入

相對(duì)于在pos之前插入，在pos后插入可以不用傳頭結(jié)點(diǎn)，無(wú)論pos在哪個(gè)位置都適用。

void SListInsertAfter(SListNode* pos, SLDataType x)
{
	assert(pos);
 
	SListNode* newnode = BuySList(x);
	SListNode* next = pos->next;
 
	pos->next = newnode;
	newnode->next = next;
 
    //下面這種方式也可以
	/*SListNode* newnode = BuySList(x);
	newnode->next = pos->next;
	pos->next = newnode;*/
}

（11）在pos后刪除

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
 
	SListNode* next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
	
}

（12）最后用完記得銷毀

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

3、各功能的測(cè)試

#include "SList.h"
 
void test1()
{
	SListNode* slist = NULL;
 
	//測(cè)試尾插
	SListPushBack(&slist, 1);
	SListPushBack(&slist, 2);
	SListPushBack(&slist, 3);
	SListPushFront(&slist, 5);
	SListPushFront(&slist, 4);
	SListPrint(slist);
 
	//測(cè)試頭插
	SListPushFront(&slist, 5);
	SListPushFront(&slist, 4);
	SListPrint(slist);
 
	//測(cè)試尾刪
	SListPopBack(&slist);
	SListPopBack(&slist);
	SListPrint(slist);
 
	//測(cè)試頭刪
	SListPopFront(&slist);
	SListPopFront(&slist);
	SListPopFront(&slist);
	SListPrint(slist);
 
	//測(cè)試查找
	SListNode* ret1 = SListFind(slist, 5);
	printf("%d\n", ret1->data);
	/*SListNode* ret2 = SListFind(slist, 2);
	printf("%d\n", ret2->data);*/
 
	//pos前插測(cè)試
	SListNode* pos = SListFind(slist, 1);
	if (pos)
	{
		SListInsert(&slist,pos,3);
	}
	SListPrint(slist);
	pos = SListFind(slist, 1);
	if (pos)
	{
		SListInsert(&slist, pos, 10);
	}
	SListPrint(slist);
 
	//刪除pos測(cè)試
	pos = SListFind(slist, 10);
	if (pos)
	{
		SListErase(&slist, pos);
	}
	SListPrint(slist);
 
	//測(cè)試在pos后插入
	pos = SListFind(slist, 3);
	if (pos)
	{
		SListInsertAfter(pos, 6);
	}
	SListPrint(slist);
	pos = SListFind(slist, 1);
	if (pos)
	{
		SListInsertAfter(pos, 8);
	}
	SListPrint(slist);
 
	//測(cè)試刪除pos后的值
	pos = SListFind(slist, 1);
	if (pos)
	{
		SListEraseAfter(pos);
	}
	SListPrint(slist);
 
}
 
int main()
{
	
	test1();
 
	return 0;
}

運(yùn)行結(jié)果：

單鏈表的實(shí)現(xiàn)到此結(jié)束，如果你還想更進(jìn)一步，請(qǐng)關(guān)注后續(xù)----單鏈表OJ，讓你從此不再迷茫！ 

關(guān)于“C語(yǔ)言中單鏈表怎么用”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。