C++數(shù)據(jù)結(jié)構(gòu)之單鏈表
更新時間：2022年01月26日 10:45:46 作者：sasorit?
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之單鏈表,鏈表是由一個個結(jié)點鏈結(jié)成的。結(jié)點包括數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域用來存儲數(shù)據(jù)元素的信息，指針域用來存儲下一個結(jié)點的地址,更詳細(xì)內(nèi)容請需要的小伙伴參考下面文章內(nèi)容
簡介：
線性表的順序存儲結(jié)構(gòu)有一個缺點就是插入和刪除時需要移動大量元素，這會耗費許多時間。能不能想辦法解決呢？
干脆所有的元素都不要考慮相鄰位置了，哪有空位就到哪里，讓每一個元素都知道它下一個元素的位置在哪里。
線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)： 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)。
鏈表是由一個個結(jié)點鏈結(jié)成的。
結(jié)點包括數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域用來存儲數(shù)據(jù)元素的信息，指針域用來存儲下一個結(jié)點的地址。
接下來實現(xiàn)一個無頭單向非循環(huán)鏈表。
單鏈表結(jié)構(gòu)的定義
typedef int SLTDataType;
typedef struct SListNode
{
?? ?SLTDataType data;?? ??? ?//數(shù)據(jù)
?? ?struct SListNode* next;?? ??? ?//指向下一個結(jié)點的指針
}SLTNode;單鏈表打印
void SListPrint(SLTNode* phead)
{
?? ?SLTNode* cur = phead;
?? ?while (cur)
?? ?{
?? ??? ?printf("%d -> ", cur->data);
?? ??? ?cur = cur->next;
?? ?}
?? ?printf("NULL\n");
}
將指向鏈表的指針plist做參數(shù)傳給函數(shù)，遍歷一遍鏈表并輸出每個結(jié)點數(shù)據(jù)域的內(nèi)容。
動態(tài)申請一個結(jié)點
SLTNode* BuySListNode(SLTDataType x)
{
?? ?SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
?? ?if (node == NULL)
?? ?{
?? ??? ?printf("malloc fail");
?? ??? ?exit(-1);
?? ?}
?? ?node->data = x;
?? ?node->next = NULL;
?? ?return node;
}用malloc動態(tài)開辟一個結(jié)點，如果node為NULL說明開辟失敗，退出程序。否則將結(jié)點node的數(shù)據(jù)域賦值為x，指針域賦值為NULL。
單鏈表尾插
如果單鏈表為空，開辟一個新結(jié)點用指針指向它即可；如果鏈表不為空，需要開辟一個新結(jié)點，然后找到鏈表的最后一個結(jié)點，讓最后一個結(jié)點的指針域存放新結(jié)點的地址。
有一個鏈表，為鏈表尾插一個新結(jié)點：
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
?? ?assert(pphead);?? ??? ?//plist地址一定不為NULL，進(jìn)行斷言
?? ?if (*pphead == NULL)?? ?//鏈表為空
?? ?{
?? ??? ?SLTNode* newnode = BuySListNode(x);
?? ??? ?*pphead = newnode;
?? ?}
?? ?else ? ? ? ? ? //鏈表不為空
?? ?{?? ??? ?
?? ??? ?SLTNode* tail = *pphead;
?? ??? ?while (tail->next)?? ??? ?//找到最后一個結(jié)點
?? ??? ??? ?tail = tail->next;
?? ??? ?SLTNode* newnode = BuySListNode(x);
?? ??? ?tail->next = newnode;
?? ?}
}
單鏈表尾刪
如果鏈表只有一個結(jié)點，把這個結(jié)點free掉即可。如果鏈表有多個結(jié)點，找到鏈表的尾結(jié)點和尾結(jié)點的前一個結(jié)點，讓尾結(jié)點的前一個結(jié)點的指針域指向NULL，free掉尾結(jié)點。
void SListPopBack(SLTNode** pphead)
{
?? ?assert(pphead);?? ??? ?//斷言pphead
?? ?assert(*pphead);?? ?//當(dāng)鏈表為空時說明沒有結(jié)點，沒法進(jìn)行刪除操作，所以*pphead不能為NULL
?? ?if ((*pphead)->next == NULL)?? ?//只有一個結(jié)點
?? ?{
?? ??? ?free(*pphead);
?? ??? ?*pphead = NULL;
?? ?}
?? ?else ? ? ? ? ? ? ? ?//多個結(jié)點
?? ?{
?? ??? ?SLTNode* tail = *pphead;?? ?//tail表示為節(jié)點
?? ??? ?SLTNode* prev = NULL;?? ??? ?//prev表示尾結(jié)點的前一個結(jié)點
?? ??? ?while (tail->next)?? ??? ?//找到尾結(jié)點和尾結(jié)點的前一個結(jié)點
?? ??? ?{
?? ??? ??? ?prev = tail;
?? ??? ??? ?tail = tail->next;
?? ??? ?}
?? ??? ?prev->next = NULL;
?? ??? ?free(tail);
?? ??? ?tail = NULL;
?? ?}
}單鏈表頭插
申請一個新結(jié)點，讓新結(jié)點的指針域存放頭結(jié)點的地址，原來指向頭結(jié)點的指針plist指向新結(jié)點，新結(jié)點就變成了新的頭結(jié)點。
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
?? ?assert(pphead);
?? ?SLTNode* newnode = BuySListNode(x);
?? ?newnode->next = *pphead;
?? ?*pphead = newnode;
}單鏈表頭刪
用一個指針指向頭結(jié)點的下一個結(jié)點，把頭結(jié)點的空間釋放掉，指向頭結(jié)點的指針指向頭結(jié)點的下一個結(jié)點。頭結(jié)點的下一個結(jié)點就變成了新的頭結(jié)點。同時要考慮鏈表為空時不能刪除，進(jìn)行相應(yīng)的斷言。
void SListPopFront(SLTNode** pphead)
{
?? ?assert(pphead);
?? ?assert(*pphead);
?? ?SLTNode* next = (*pphead)->next;?? ?//指針next記錄頭結(jié)點的下一個結(jié)點
?? ?free(*pphead);
?? ?*pphead = next;
}求單鏈表長度
int SListSize(SLTNode* phead)
{
?? ?int size = 0;
?? ?SLTNode* cur = phead;
?? ?while (cur)
?? ?{
?? ??? ?++size;
?? ??? ?cur = cur->next;
?? ?}
?? ?return size;
}單鏈表查找
遍歷一遍單鏈表，如果某一結(jié)點數(shù)據(jù)域內(nèi)容與要查找內(nèi)容相同，返回該結(jié)點。遍歷完沒有找到，返回NULL。
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
?? ?SLTNode* cur = phead;
?? ?while (cur)
?? ?{
?? ??? ?if (x == cur->data)
?? ??? ??? ?return cur;
?? ??? ?cur = cur->next;
?? ?}
?? ?return NULL;
}單鏈表在pos位置插入
在pos位置插入，如果pos這個位置是頭結(jié)點，和頭插的邏輯是一樣的，可以調(diào)用之前寫過的頭插函數(shù)。
如果這個位置是除頭結(jié)點外的任意一個結(jié)點，我們需要申請一個新結(jié)點，并且記錄pos結(jié)點的前一個結(jié)點，讓新結(jié)點的指針域存放pos的地址，讓pos前一個結(jié)點的指針域存放新結(jié)點的地址，把它們鏈結(jié)起來。
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
?? ?assert(pphead);?? ??? ?//指向頭結(jié)點指針的地址不能為NULL，進(jìn)行斷言
?? ?assert(pos);?? ??? ?//插入位置pos不能為NULL進(jìn)行斷言
?? ?if (pos == *pphead)?? ??? ?//要插入的位置pos和頭結(jié)點是一個位置
?? ?{
?? ??? ?SListPushFront(pphead, x);
?? ?}
?? ?else ? ? ? ? ? ? ? ?//pos不是頭結(jié)點
?? ?{
?? ??? ?SLTNode* prev = *pphead; ? ?//prev用來找到pos位置的前一個結(jié)點
?? ??? ?while (prev->next != pos)
?? ??? ??? ?prev = prev->next;
?? ??? ?SLTNode* newnode = BuySListNode(x);?? ??? ?//申請一個新結(jié)點
?? ??? ?newnode->next = pos;?? ??? ?//把新結(jié)點鏈結(jié)
?? ??? ?prev->next = newnode;
?? ?}
}單鏈表在pos后面位置插入
申請一個新結(jié)點，讓新結(jié)點的指針域存放pos結(jié)點下一個結(jié)點的地址，pos結(jié)點的指針域存放新結(jié)點的地址。
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
?? ?assert(pos);
?? ?SLTNode* newnode = BuySListNode(x);
?? ?newnode->next = pos->next;
?? ?pos->next = newnode;
}單鏈表刪除pos位置
如果pos位置是頭結(jié)點，刪除邏輯和頭刪相同，調(diào)用頭刪函數(shù)即可。
如果是除頭結(jié)點外的其它結(jié)點，找到pos的前一個結(jié)點，讓這個結(jié)點的指針域指向pos的下一個結(jié)點。把pos結(jié)點空間釋放。
void SListErase(SLTNode** pphead, SLTNode* pos)
{
?? ?assert(pphead && *pphead);?? ?//pphead不能為空，鏈表不能為空進(jìn)行斷言
?? ?assert(pos);?? ??? ??? ?//pos不能為空
?? ?if (pos == *pphead)?? ??? ?//要刪除的位置pos是頭結(jié)點
?? ?{
?? ??? ?SListPopFront(pphead);
?? ?}
?? ?else ? ? ? ? ? ? ? ? ? ?//不是頭結(jié)點
?? ?{
?? ??? ?SLTNode* prev = *pphead;?? ?//prev指針用來找到pos結(jié)點的前一個結(jié)點
?? ??? ?while (prev->next != pos)
?? ??? ??? ?prev = prev->next;
?? ??? ?prev->next = pos->next;
?? ??? ?free(pos);
?? ??? ?pos = NULL;
?? ?}
}單鏈表刪除pos的下一個結(jié)點
記錄下pos的下一個結(jié)點，pos結(jié)點指針域指向pos下一個結(jié)點指針域指向的結(jié)點，釋放掉pos的下一個結(jié)點。
void SListEraseAfter(SLTNode* pos)
{
?? ?//pos不能為空，不能為尾結(jié)點，因為尾結(jié)點的下一個是NULL，什么也刪除不了
?? ?assert(pos && pos->next);?? ?
?? ?SLTNode* next = pos->next;?? ??? ?//next指針指向pos下一個結(jié)點
?? ?pos->next = next->next;
?? ?free(next);
?? ?next = NULL;
}判斷單鏈表是否為空
bool SListEmpty(SLTNode* phead)
{
?? ?return phead == NULL;
}頭文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int SLTDataType;
typedef struct SListNode
{
?? ?SLTDataType data;?? ??? ?//數(shù)據(jù)
?? ?struct SListNode* next;?? ??? ?//指向下一個結(jié)點的指針
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//新節(jié)點
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾刪
void SListPopBack(SLTNode** pphead);
//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//頭刪
void SListPopFront(SLTNode** pphead);
//長度
int SListSize(SLTNode* phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//pos位置后面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
//刪除pos后面位置
void SListEraseAfter(SLTNode* pos);
//判空
bool SListEmpty(SLTNode* phead);源文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SListPrint(SLTNode* phead)
{
?? ?SLTNode* cur = phead;
?? ?while (cur)
?? ?{
?? ??? ?printf("%d -> ", cur->data);
?? ??? ?cur = cur->next;
?? ?}
?? ?printf("NULL\n");
}
SLTNode* BuySListNode(SLTDataType x)
{
?? ?SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
?? ?if (node == NULL)
?? ?{
?? ??? ?printf("malloc fail");
?? ??? ?exit(-1);
?? ?}
?? ?node->data = x;
?? ?node->next = NULL;
?? ?return node;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
?? ?assert(pphead);?? ??? ?//plist地址一定不為NULL，進(jìn)行斷言
?? ?if (*pphead == NULL)?? ?//鏈表為空
?? ?{
?? ??? ?SLTNode* newnode = BuySListNode(x);
?? ??? ?*pphead = newnode;
?? ?}
?? ?else ? ? ? ? ? //鏈表不為空
?? ?{?? ??? ?
?? ??? ?SLTNode* tail = *pphead;
?? ??? ?while (tail->next)
?? ??? ??? ?tail = tail->next;
?? ??? ?SLTNode* newnode = BuySListNode(x);
?? ??? ?tail->next = newnode;
?? ?}
}
void SListPopBack(SLTNode** pphead)
{
?? ?assert(pphead);?? ??? ?//斷言pphead
?? ?assert(*pphead);?? ?//當(dāng)鏈表為空時說明沒有結(jié)點，沒法進(jìn)行刪除操作，所以*pphead不能為NULL
?? ?if ((*pphead)->next == NULL)?? ?//只有一個結(jié)點
?? ?{
?? ??? ?free(*pphead);
?? ??? ?*pphead = NULL;
?? ?}
?? ?else ? ? ? ? ? ? ? ?//多個結(jié)點
?? ?{
?? ??? ?SLTNode* tail = *pphead;?? ?//tail表示為節(jié)點
?? ??? ?SLTNode* prev = NULL;?? ??? ?//prev表示尾結(jié)點的前一個結(jié)點
?? ??? ?while (tail->next)?? ??? ?//找到尾結(jié)點和尾結(jié)點的前一個結(jié)點
?? ??? ?{
?? ??? ??? ?prev = tail;
?? ??? ??? ?tail = tail->next;
?? ??? ?}
?? ??? ?prev->next = NULL;
?? ??? ?free(tail);
?? ??? ?tail = NULL;
?? ?}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
?? ?assert(pphead);
?? ?SLTNode* newnode = BuySListNode(x);
?? ?newnode->next = *pphead;
?? ?*pphead = newnode;
}
void SListPopFront(SLTNode** pphead)
{
?? ?assert(pphead);
?? ?assert(*pphead);
?? ?SLTNode* next = (*pphead)->next;
?? ?free(*pphead);
?? ?*pphead = next;
}
int SListSize(SLTNode* phead)
{
?? ?int size = 0;
?? ?SLTNode* cur = phead;
?? ?while (cur)
?? ?{
?? ??? ?++size;
?? ??? ?cur = cur->next;
?? ?}
?? ?return size;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
?? ?SLTNode* cur = phead;
?? ?while (cur)
?? ?{
?? ??? ?if (x == cur->data)
?? ??? ??? ?return cur;
?? ??? ?cur = cur->next;
?? ?}
?? ?return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
?? ?assert(pphead);?? ??? ?//指向頭結(jié)點指針的地址不能為NULL，進(jìn)行斷言
?? ?assert(pos);?? ??? ?//插入位置pos不能為NULL進(jìn)行斷言
?? ?if (pos == *pphead)?? ??? ?//要插入的位置pos和頭結(jié)點是一個位置
?? ?{
?? ??? ?SListPushFront(pphead, x);
?? ?}
?? ?else ? ? ? ? ? ? ? ?//pos不是頭結(jié)點
?? ?{
?? ??? ?SLTNode* prev = *pphead; ? ?//prev用來找到pos位置的前一個結(jié)點
?? ??? ?while (prev->next != pos)
?? ??? ??? ?prev = prev->next;
?? ??? ?SLTNode* newnode = BuySListNode(x);?? ??? ?//申請一個新結(jié)點
?? ??? ?newnode->next = pos;?? ??? ?//把新結(jié)點鏈結(jié)
?? ??? ?prev->next = newnode;
?? ?}
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
?? ?assert(pos);
?? ?SLTNode* newnode = BuySListNode(x);
?? ?newnode->next = pos->next;
?? ?pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
?? ?assert(pphead && *pphead);?? ?//pphead不能為空，鏈表不能為空進(jìn)行斷言
?? ?assert(pos);?? ??? ??? ?//pos不能為空
?? ?if (pos == *pphead)?? ??? ?//要刪除的位置pos是頭結(jié)點
?? ?{
?? ??? ?SListPopFront(pphead);
?? ?}
?? ?else ? ? ? ? ? ? ? ? ? ?//不是頭結(jié)點
?? ?{
?? ??? ?SLTNode* prev = *pphead;?? ?//prev指針用來找到pos結(jié)點的前一個結(jié)點
?? ??? ?while (prev->next != pos)
?? ??? ??? ?prev = prev->next;
?? ??? ?prev->next = pos->next;
?? ??? ?free(pos);
?? ??? ?pos = NULL;
?? ?}
}
void SListEraseAfter(SLTNode* pos)
{
?? ?//pos不能為空，不能為尾結(jié)點，因為尾結(jié)點的下一個是NULL，什么也刪除不了
?? ?assert(pos && pos->next);?? ?
?? ?SLTNode* next = pos->next;?? ??? ?//next指針指向pos下一個結(jié)點
?? ?pos->next = next->next;
?? ?free(next);
?? ?next = NULL;
}
bool SListEmpty(SLTNode* phead)
{
?? ?return phead == NULL;
}
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的文章就介紹到這了,更多相關(guān)C++ 單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹C 語言環(huán)境設(shè)置,在不同的系統(tǒng)平臺上,C語言的環(huán)境設(shè)置不同，這里幫大家整理了Liunx, UNIX,Windows 上安裝C語言環(huán)境，有開始學(xué)習(xí)C語言的朋友可以參考下2016-08-08
這篇文章主要介紹了C++實現(xiàn)棧的操作(push和pop)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)對象化的矩陣相乘小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)掃雷、排雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要給大家介紹了關(guān)于在C程序中處理UTF-8文本的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。2017-11-11
C語言?深入理解動態(tài)規(guī)劃之計數(shù)類DP
動態(tài)規(guī)劃可謂是大名鼎鼎，筆試面試中的高頻考點，也是重點難點，動態(tài)規(guī)劃類型題目靈活多變，難度系數(shù)也相對較高，往往我們做不好動態(tài)規(guī)劃的題目就會與心儀的offer失之交臂，本篇文章我們就一起來研究一下動態(tài)規(guī)劃的計數(shù)類DP2022-04-04
數(shù)據(jù)結(jié)構(gòu) 中數(shù)制轉(zhuǎn)換(棧的應(yīng)用)
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 中數(shù)制轉(zhuǎn)換(棧的應(yīng)用)的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C++設(shè)計模式之簡單工廠模式實例,工廠模式有一種非常形象的描述,建立對象的類就如一個工廠,而需要被建立的對象就是一個個產(chǎn)品,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了在vs2017上配置AppGameKit庫的教程，本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
今天講解的內(nèi)容，則是自己對于這三種語句一些細(xì)節(jié)的簡單介紹，分支語句：if，switch、循環(huán)語句：while，for，do while、goto語句，感興趣的小伙伴可以參考下面具體的文章內(nèi)容2021-09-09