快捷導(dǎo)航

C++?數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解單鏈表

更新時(shí)間：2022年03月25日 10:09:52 作者：瑯時(shí)壹

這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之單鏈表,鏈表是由一個(gè)個(gè)結(jié)點(diǎn)鏈結(jié)成的。結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域用來存儲數(shù)據(jù)元素的信息，指針域用來存儲下一個(gè)結(jié)點(diǎn)的地址,更詳細(xì)內(nèi)容請需要的小伙伴參考下面文章內(nèi)容

前言

上篇順序表結(jié)尾了解了順序表的諸多缺點(diǎn)，鏈表的特性很好的解決了這些問題，本期我們來認(rèn)識單鏈表。

一、鏈表是什么

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接依次實(shí)現(xiàn)的。

由圖，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是物理上不一定連續(xù)
顯示中結(jié)點(diǎn)一般是從堆上申請出來的
從堆上申請的空間，是按照一定的策略劃分的，兩次申請的空間，可能連續(xù)，可能不連續(xù)，見順序表

鏈表的分類

鏈表也可以分為很多種

1. 單向或者雙向
2. 帶頭或者不帶頭
3. 循環(huán)或非循環(huán)

我們最常用的還是無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表本篇我們實(shí)現(xiàn)無頭單向非循環(huán)鏈表增刪查改

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

基本結(jié)點(diǎn)結(jié)構(gòu)

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

頭文件

//llist.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 動(dòng)態(tài)申請一個(gè)節(jié)點(diǎn)
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
// 分析思考為什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
// 分析思考為什么不刪除pos位置？
void SListEraseAfter(SListNode* pos);
// 單鏈表的銷毀
void SListDestory(SListNode* plist);

動(dòng)態(tài)申請一個(gè)節(jié)點(diǎn)

// 動(dòng)態(tài)申請一個(gè)節(jié)點(diǎn)
SListNode* BuySListNode(SLTDateType 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;
}

單鏈表打印

鏈表單個(gè)結(jié)點(diǎn)中，data存儲數(shù)據(jù)，next存儲下一個(gè)結(jié)點(diǎn)的地址，可以通過next訪問下一個(gè)結(jié)點(diǎn)

// 單鏈表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;//訪問下一個(gè)結(jié)點(diǎn)
	}
	printf("NULL\n");
}

單鏈表尾插

這里傳入了頭結(jié)點(diǎn)的地址的指針，是因?yàn)橛锌赡芤淖冾^結(jié)點(diǎn)的情況，傳址調(diào)用幻術(shù)，如果只傳入*plist，相當(dāng)于只改變形參，實(shí)參不會有實(shí)際改變，通過pplist可以解決這個(gè)問題

// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)//空鏈表
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;//遍歷至最后插入
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

單鏈表的尾刪

一前一后遍歷，找到空后直接free（tail），將prev->next置空即可

// 單鏈表的尾刪
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)//空鏈表，無需刪除
	{
		return;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		{
			while (tail->next != NULL)
			{
				prev = tail;
				tail = tail->next;
			}

			free(tail);
			tail = NULL;
			prev->next = NULL;
		}
	}
}

單鏈表的頭插

有點(diǎn)繞，要多想想

// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

單鏈表頭刪

比較簡單

// 單鏈表頭刪
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)//鏈表為空
	{
		return;
	}
	else
	{
		SListNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}

// 單鏈表查找
遍歷即可
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data = x)
		{
			return cur;
		}
		cur = cur->next;
	}

	retuen NULL;
}

*單鏈表在pos位置之后插入x

為什么不在pos之前插入，由于我們是單向鏈表，需要從頭遍歷查找pos，如果在pos之前插入，找到pos還需找到pos之前的地址，對所傳參數(shù)不友好，所以我們一般在后插入

//單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

單鏈表刪除pos位置之后的值為什么不刪除pos位置，同上，在邏輯上和傳參不友好.

// 單鏈表刪除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

單鏈表的銷毀鏈表不像順序表連續(xù)刪頭就可以，由于鏈表是一個(gè)一個(gè)分散的結(jié)點(diǎn)，需要逐一刪除

// 單鏈表的銷毀
void SListDestory(SListNode** pplist)
{
	assert(*pplist);
	SListNode* cur = *pplist;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;
}