您好,登錄后才能下訂單哦!
小編給大家分享一下C++ 數(shù)據(jù)結(jié)構(gòu)中單鏈表的示例分析,希望大家閱讀完這篇文章之后都有所收獲,下面讓我們一起去探討吧!
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接依次實(shí)現(xiàn)的。
由圖,鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的,但是物理上不一定連續(xù)
顯示中結(jié)點(diǎn)一般是從堆上申請(qǐng)出來的
從堆上申請(qǐng)的空間,是按照一定的策略劃分的,兩次申請(qǐng)的空間,可能連續(xù),可能不連續(xù),見順序表
鏈表也可以分為很多種
1. 單向或者雙向
2. 帶頭或者不帶頭
3. 循環(huán)或非循環(huán)
我們最常用的還是無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表 本篇我們實(shí)現(xiàn)無頭單向非循環(huá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)申請(qǐng)一個(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)申請(qǐng)一個(gè)節(jié)點(diǎn)
// 動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn) SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL)//申請(qǐng)失敗 { printf("malloc fail\n"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } return newnode; }
單鏈表打印
鏈表單個(gè)結(jié)點(diǎn)中,data存儲(chǔ)數(shù)據(jù),next存儲(chǔ)下一個(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í)參不會(huì)有實(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; }
單鏈表頭刪
比較簡(jiǎn)單
// 單鏈表頭刪 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之前的地址,對(duì)所傳參數(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; }
看完了這篇文章,相信你對(duì)“C++ 數(shù)據(jù)結(jié)構(gòu)中單鏈表的示例分析”有了一定的了解,如果想了解更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。