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++ Boost Serialization庫超詳細獎金額
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫,作為標準庫的后備,是C++標準化進程的開發(fā)引擎之一,是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-12-12