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