??? ??????? 歡迎來到小林的博客?。?br> ?????????博客主頁：??小林愛敲代碼
?????????博客專欄：?? 數(shù)據(jù)結(jié)構(gòu)與算法
?????????社區(qū) :?? 進(jìn)步學(xué)堂
?????????歡迎關(guān)注：??點(diǎn)贊??收藏??留言
前言
今天給大家?guī)硭膫€(gè)內(nèi)容，一個(gè)是單鏈表非帶頭的實(shí)現(xiàn)，一個(gè)是雙鏈表帶頭循環(huán)的實(shí)現(xiàn)。剩下的就是數(shù)組模擬單鏈表和雙鏈表。
單鏈表
鏈表，在內(nèi)存中并不是連續(xù)存儲(chǔ)的。而鏈表通常會(huì)有next指針指向它的下一個(gè)節(jié)點(diǎn)。鏈表的最后一個(gè)節(jié)點(diǎn)一定指向空。
頭插
頭插我們需要讓新節(jié)點(diǎn)指向頭節(jié)點(diǎn)，然后更換頭節(jié)點(diǎn)為新節(jié)點(diǎn)即可。
尾插
我們只需要找到最后一個(gè)節(jié)點(diǎn)，讓它的next指向新節(jié)點(diǎn)，再把新節(jié)點(diǎn)指向NULL即可。
頭刪
先保存頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后刪除頭節(jié)點(diǎn)。并把保存下來的下一個(gè)節(jié)點(diǎn)設(shè)置為新的頭節(jié)點(diǎn)。
尾刪
尾刪需要記錄一下最后一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。然后刪除最后一個(gè)節(jié)點(diǎn)，把前一個(gè)節(jié)點(diǎn)指向NULL。否則會(huì)出現(xiàn)指向野指針的情況。
指定位置后插入
我們這里只講解在指定位置的后一個(gè)元素插入，因?yàn)閱捂湵碓谥付ü?jié)點(diǎn)的前一個(gè)插入，需要前一個(gè)節(jié)點(diǎn)。但是單鏈表只指后不指前。所以想拿到前一個(gè)節(jié)點(diǎn)必須再遍歷一次，所以不建議單鏈表用前插。在指定位置后插，我們只需要保存一下這個(gè)位置的下一個(gè)節(jié)點(diǎn)，然后讓新節(jié)點(diǎn)指向這個(gè)位置的下一個(gè)節(jié)點(diǎn)。這個(gè)位置指向新節(jié)點(diǎn)。
假設(shè)我們?cè)趐os位置后面插入：
指定位置后刪除
我們還是刪除指定位置后的元素，因?yàn)槿绻麆h除指定元素，我們也需要它的前一個(gè)節(jié)點(diǎn)。單鏈表無法直接獲取前一個(gè)節(jié)點(diǎn)。指定位置后刪除，我們只需要保存下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后刪除下一個(gè)節(jié)點(diǎn)，然后讓這個(gè)位置指向保存下來的的節(jié)點(diǎn)。
單鏈表的代碼實(shí)現(xiàn)：
#include<stdlib.h>
#include<assert.h>
#include<stdio.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)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); //開辟空間
newNode->data = x; //空間值為x
return newNode;
}
// 單鏈表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur) //遍歷一遍鏈表
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
if (*pplist == NULL)//如果鏈表為空調(diào)用頭插
{
SListPushFront(pplist, x);
return;
}
//找到尾部節(jié)點(diǎn)
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
//復(fù)用SListInsertAfter函數(shù)插入
SListInsertAfter(tail, x);
}
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
assert(pplist);
SListNode* newNode = BuySListNode(x);
if (*pplist == NULL) //鏈表為空需要更新頭節(jié)點(diǎn)
{
*pplist = newNode;
newNode->next = NULL;
return;
}
newNode->next = *pplist;
*pplist = newNode;
}
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist)
{
assert(pplist && *pplist);
if ((*pplist)->next == NULL) //鏈表就一個(gè)元素，調(diào)用頭刪
{
SListPopFront(pplist);
return;
}
SListNode* tail = *pplist;
SListNode* prev = NULL;
//遍歷鏈表并刪除
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
// 單鏈表頭刪
void SListPopFront(SListNode** pplist)
{
assert(pplist && *pplist);
//頭刪
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur)
{
if (x == cur->data)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* next = pos->next;
SListNode* newNode = BuySListNode(x);
pos->next = newNode;
newNode->next = next;
}
// 單鏈表刪除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* nextnext = pos->next->next;
free(pos->next);
pos->next = nextnext;
}
// 單鏈表的銷毀
void SListDestroy(SListNode* plist)
{
SListNode* cur = plist;
SListNode* next = plist->next;
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
}
雙鏈表
這里我們實(shí)現(xiàn)一個(gè)帶頭循環(huán)的雙鏈表，因?yàn)檠h(huán)鏈表可以從頭節(jié)點(diǎn)直接找到最后一個(gè)節(jié)點(diǎn)。帶頭是因?yàn)楦玫拇_定鏈表的尾部，帶頭節(jié)點(diǎn)在這里就沖當(dāng)了尾節(jié)點(diǎn)的作用。
指定位置前插入
雙鏈表我們只需要寫指定插入和指定刪除，就可以復(fù)用這兩個(gè)接口實(shí)現(xiàn)頭插，頭刪，尾插，尾刪了。指定位置前插入和單鏈表類似。先保存前一個(gè)節(jié)點(diǎn)坐標(biāo)，然后讓前一個(gè)節(jié)點(diǎn)和新節(jié)點(diǎn)連接，再把自己的prev指針指向新節(jié)點(diǎn)。
為了方便觀看，我把首尾節(jié)點(diǎn)指向的線省略了，實(shí)際上指針是指向首尾的。我們?cè)趐os前插入一個(gè)節(jié)點(diǎn)。
動(dòng)圖演示可能線連接的不怎么好看，但最后都是這樣的
指定位置刪除
指定位置刪除，我們只需要存下前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)。然后把兩個(gè)節(jié)點(diǎn)連接起來，再釋放當(dāng)前節(jié)點(diǎn)即可。
雙鏈表代碼實(shí)現(xiàn)：
#include <assert.h>
#include<stdio.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實(shí)現(xiàn)
typedef int LTDataType;
typedef struct _ListNode
{
LTDataType _data;
struct _ListNode* _next; //指向后一個(gè)節(jié)點(diǎn)
struct _ListNode* _prev; //指向前一個(gè)節(jié)點(diǎn)
}ListNode;
//創(chuàng)建節(jié)點(diǎn)
ListNode* CreateListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->_data = x;
return newNode;
}
// 創(chuàng)建鏈表，返回鏈表的頭結(jié)點(diǎn).
ListNode* ListCreate()
{
ListNode* head = CreateListNode(0);
head->_next = head; //自己指向自己
head->_prev = head; //自己指向自己
return head;
}
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
ListNode* cur = pHead->_next;
while (cur != pHead)
{
ListNode* next = cur->_next;
free(cur);
cur = next;
}
free(pHead);
}
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
ListNode* cur = pHead->_next;
while(cur != pHead)
{
printf("%d->", cur->_data);
cur = cur->_next;
}
printf("NULL\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
ListInsert(pHead, x); //復(fù)用指定插入
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
ListErase(pHead->_prev); //復(fù)用指定刪除
}
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
ListInsert(pHead->_next, x); //復(fù)用指定插入
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
ListErase(pHead->_next); //復(fù)用指定刪除
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
while (pHead)
{
if (pHead->_data == x)
return pHead;
pHead = pHead->_next;
}
return NULL;
}
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* prev = pos->_prev;
ListNode* newNode = CreateListNode(x);
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = pos;
pos->_prev = newNode;
}
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->_prev;
ListNode* next = pos->_next;
free(pos);
prev->_next = next;
next->_prev = prev;
}
數(shù)組模擬單鏈表
數(shù)組模擬鏈表我們需要開一個(gè)數(shù)組來存鏈表的值，還要開一個(gè)數(shù)組連存儲(chǔ)鏈表的指向，還需要一個(gè)變量來代表鏈表的編號(hào)。
e[] 數(shù)組用來存儲(chǔ)鏈表的值 ， ne[] 數(shù)組用來存儲(chǔ)節(jié)點(diǎn)指向節(jié)點(diǎn)的下標(biāo)，數(shù)組的下標(biāo)代表節(jié)點(diǎn)。 head代表頭節(jié)點(diǎn)，值-1則為空節(jié)點(diǎn)。 idx 是給鏈表的節(jié)點(diǎn)的一個(gè)編號(hào)，代表下標(biāo)。
代碼：
#include<iostream>
using namespace std;
const int N = 100010; //鏈表總大小
int e[N];//存儲(chǔ)值
int ne[N];//存儲(chǔ)下一個(gè)節(jié)點(diǎn)
int head,idx;
//鏈表初始化
void init()
{
head = -1 ; //-1為空
idx = 0; //當(dāng)前節(jié)點(diǎn)的編號(hào)
}
void add_to_head(int x) //頭插
{
e[idx] = x; //給新節(jié)點(diǎn)賦值
ne[idx] = head; //指向head指向的節(jié)點(diǎn)
head = idx++; //頭節(jié)點(diǎn)指向新節(jié)點(diǎn)
}
//插入到k節(jié)點(diǎn)后面
void add(int k ,int x)
{
e[idx] = x; //idx編號(hào)的元素的值賦值為x
ne[idx] = ne[k]; //指向k節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
ne[k] = idx++; //指向新插入節(jié)點(diǎn)
}
void remove(int k )
{
ne[k] = ne[ne[k]]; //指向下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
}
數(shù)組模擬雙鏈表
單鏈表需要一個(gè)數(shù)組來存儲(chǔ)指向的節(jié)點(diǎn)，那么雙鏈表就需要兩個(gè)數(shù)組來存儲(chǔ)，一個(gè)指向前節(jié)點(diǎn)，一個(gè)指向后節(jié)點(diǎn)。
r[] 存儲(chǔ)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)下標(biāo)
l[] 存儲(chǔ)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)下標(biāo)
e[] 存儲(chǔ)節(jié)點(diǎn)的值
hh 頭的下標(biāo)
tt 尾的下標(biāo)
idx 節(jié)點(diǎn)的編號(hào)，對(duì)應(yīng)數(shù)組下標(biāo)，每一個(gè)新的編號(hào)被使用說明創(chuàng)建了一個(gè)節(jié)點(diǎn)文章來源：http://www.zghlxwxcb.cn/news/detail-790247.html
#include<iostream>
#include<string>
using namespace std;
const int N = 1e6 + 10;
int r[N],l[N],e[N];
int hh,tt,idx;
void init()
{
hh = 0,tt = 1,idx = 2;//hh代表頭，tt代表尾，idx是其他節(jié)點(diǎn)的編號(hào)
r[hh] = tt; //頭指向尾
l[tt] = hh; //尾指向頭
}
//指定位置的右邊插入
void add_right(int k,int x)
{
e[idx] = x; //idx編號(hào)的節(jié)點(diǎn)的值為x
r[idx] = r[k],l[idx] = k; //idx右邊指向k的右邊，坐標(biāo)指向k
l[r[k]] = idx,r[k] = idx++; //k右節(jié)點(diǎn)的坐標(biāo)指向idx，k的右邊指向idx。idx編號(hào)+1
}
//刪除
void remove(int k)
{
r[l[k]] = r[k]; //k前一個(gè)節(jié)點(diǎn)的右一個(gè)節(jié)點(diǎn)指向k的右節(jié)點(diǎn)
l[r[k]] = l[k]; //k后一個(gè)節(jié)點(diǎn)的左節(jié)點(diǎn)指向k的左節(jié)點(diǎn)
}
總結(jié)：
鏈?zhǔn)綄?shí)現(xiàn)的鏈表的動(dòng)態(tài)的，每次增加節(jié)點(diǎn)需要開辟空間。開辟空間是有消耗的。而數(shù)組模擬的鏈表是靜態(tài)的，這就意味著數(shù)組模擬的鏈表比鏈?zhǔn)綄?shí)現(xiàn)的鏈表更快。但因?yàn)槭庆o態(tài)的，會(huì)占用固定的空間。所以個(gè)人推薦，做題的時(shí)候用靜態(tài)鏈表，其他的時(shí)候用動(dòng)態(tài)鏈表。文章來源地址http://www.zghlxwxcb.cn/news/detail-790247.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】單鏈表 && 雙鏈表(鏈?zhǔn)胶蛿?shù)組實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
