欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++?數據結構超詳細講解單鏈表

 更新時間：2022年03月25日 10:09:52   作者：瑯時壹  
這篇文章主要介紹了C++數據結構之單鏈表,鏈表是由一個個結點鏈結成的。結點包括數據域和指針域兩部分，數據域用來存儲數據元素的信息，指針域用來存儲下一個結點的地址,更詳細內容請需要的小伙伴參考下面文章內容

(?´?`?) 單鏈表

前言

上篇順序表結尾了解了順序表的諸多缺點，鏈表的特性很好的解決了這些問題，本期我們來認識單鏈表。

一、鏈表是什么

鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接依次實現的。

  • 由圖，鏈式結構在邏輯上是連續(xù)的，但是物理上不一定連續(xù)
  • 顯示中結點一般是從堆上申請出來的
  • 從堆上申請的空間，是按照一定的策略劃分的，兩次申請的空間，可能連續(xù)，可能不連續(xù)，見順序表

鏈表的分類

鏈表也可以分為很多種

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

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

二、鏈表的實現

基本結點結構

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;

// 動態(tài)申請一個節(jié)點
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);

動態(tài)申請一個節(jié)點

// 動態(tài)申請一個節(jié)點
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;
}

單鏈表打印

鏈表單個結點中，data存儲數據，next存儲下一個結點的地址，可以通過next訪問下一個結點

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

單鏈表尾插

這里傳入了頭結點的地址的指針，是因為有可能要改變頭結點的情況，傳址調用幻術，如果只傳入*plist，相當于只改變形參，實參不會有實際改變，通過pplist可以解決這個問題

// 單鏈表尾插
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;
		}
	}
}

單鏈表的頭插

有點繞，要多想想

// 單鏈表的頭插
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之前的地址，對所傳參數不友好，所以我們一般在后插入

//單鏈表在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ù)刪頭就可以，由于鏈表是一個一個分散的結點，需要逐一刪除

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

總結

鏈表相比但鏈表難度提升不少，對c的掌握也變大，不清晰的地方要多想多畫圖。還請斧正

到此這篇關于C++ 數據結構超詳細講解單鏈表的文章就介紹到這了,更多相關C++ 單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

  • 基于C語言實現高級通訊錄的示例代碼

    基于C語言實現高級通訊錄的示例代碼

    這篇文章主要為大家詳細介紹了如何利用C語言實現一個高級通訊錄的功能，文中的示例代碼講解詳細，具有一定的借鑒價值，需要的小伙伴可以參考一下
    2023-01-01
  • C語言數據輸入與輸出實例詳解

    C語言數據輸入與輸出實例詳解

    這篇文章主要介紹了C語言數據輸入與輸出實例詳解的相關資料,需要的朋友可以參考下
    2017-06-06
  • 共用體的定義與應用詳細解析

    共用體的定義與應用詳細解析

    共同體的定義類似結構體，不過共同體的所有成員都在同一段內存中存放，起始地址一樣，并且同一時刻只能使用其中的一個成員變量
    2013-08-08
  • 簡單談談關于C++中大隨機數的問題

    簡單談談關于C++中大隨機數的問題

    這篇文章主要介紹了關于C++中大隨機數的問題,文中給出了詳細的示例代碼，相信對大家的學習或者工作具有一定的參考借鑒價值，有需要的朋友可以一起來學習學習。
    2017-01-01
  • C語言中函數聲明與調用問題

    C語言中函數聲明與調用問題

    以下是對C語言中的函數聲明與調用進行了詳細的分析介紹，需要的朋友可以過來參考下
    2013-08-08
  • Qt實現棋盤游戲

    Qt實現棋盤游戲

    這篇文章主要為大家詳細介紹了Qt實現棋盤游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-01-01
  • C語言實現順序表的全操作詳解

    C語言實現順序表的全操作詳解

    順序表，全名順序存儲結構，是線性表的一種，線性表用于存儲邏輯關系為“一對一”的數據，順序表自然也不例外，不僅如此，順序表對數據的物理存儲結構也有要求，跟隨下文來具體了解吧
    2022-04-04
  • C語言typedef與復雜函數聲明問題的深入解析

    C語言typedef與復雜函數聲明問題的深入解析

    以下是對C語言中的typedef與復雜函數聲明問題進行了詳細的分析介紹，需要的朋友可以過來參考下
    2013-07-07
  • VS及Unity安裝和使用Nuget包

    VS及Unity安裝和使用Nuget包

    本文主要介紹了VS及Unity安裝和使用Nuget包，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2023-01-01
  • C++ Boost Serialization庫超詳細獎金額

    C++ Boost Serialization庫超詳細獎金額

    Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱
    2022-12-12

最新評論