C++如何用數(shù)組模擬鏈表
前言
鏈表是指由一系列儲存在非連續(xù)儲存空間 結(jié)點組成的儲存結(jié)構(gòu)。每個結(jié)點由兩部分組成:一是儲存元素的數(shù)據(jù)域,一是儲存下一個節(jié)點地址的指針域。用數(shù)組模擬鏈表可以十分清晰明了地理解這一定義。
在這里,我們簡單地介紹一下單鏈表和雙鏈表兩種鏈表以及用數(shù)組模擬實現(xiàn)它們的方式。
1.單鏈表
單鏈表是指針方向單向的鏈表,即a結(jié)點的指針域儲存著b結(jié)點的地址,而b結(jié)點的指針域內(nèi)沒有儲存a結(jié)點的地址。在訪問時,可以由a到b訪問,而不能由b到a訪問。
如圖可以清晰地看到,各個結(jié)點的指向都是單向的。
Q: 那么,如何用數(shù)組來實現(xiàn)它呢?
A: 方法如下
在k結(jié)點右側(cè)插入元素x。先將x賦值給該節(jié)點的數(shù)據(jù)域(e[idx]),然后將k結(jié)點的指針域賦值給該結(jié)點的指針域,最后將k結(jié)點的指針域儲存的地址改為該節(jié)點的地址。
void add(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; }
刪除k結(jié)點指向的結(jié)點。這里所指的刪除,是將k的指向改為該結(jié)點的指向。原本為a -> b -> c,改為a -> c,b結(jié)點依然存在,只是沒有其他結(jié)點指向它,也就無法通過鏈表訪問它,我們認(rèn)為它就再鏈表上被刪除了。
void remove(int k) { ne[k] = ne[ne[k]]; }
讀取鏈表。讀取鏈表只用注意一點,在用單指針掃描時不是將指針位置右移,而是將指針移動到該結(jié)點指向的位置。
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' '; cout << endl;
主要的操作就是如此,下邊看看完整代碼:
這是較為經(jīng)典的寫法,我個人認(rèn)為有些麻煩,head不必單獨拿出來寫一個函數(shù)。但是有助于理解。
#include<iostream> using namespace std; const int M = 1e5 + 10; int m, k, x, idx, head; int e[M], ne[M]; void init() { head = -1, idx = 0; } void add_head(int x) { e[idx] = x; ne[idx] = head; head = idx++; } void remove(int k) { ne[k] = ne[ne[k]]; } void add(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } int main() { init(); cin >> m; while (m--) { char op; cin >> op; if (op == 'H') { cin >> x; add_head(x); } else if (op == 'D') { cin >> k; if (!k) head = ne[head]; remove(k - 1); } else { cin >> k >> x; add(k - 1, x); } } for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' '; cout << endl; return 0; }
這種寫法稍微簡便一些,用a[0]替代head。
#include<iostream> using namespace std; const int M = 1e5 + 10; int m, k, x, idx, head; int e[M], ne[M]; void init() { ne[0] = -1, idx = 1; } void remove(int k) { ne[k] = ne[ne[k]]; } void add(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } int main() { init(); cin >> m; while (m--) { char op; cin >> op; if (op == 'H') { cin >> x; add(0, x); } else if (op == 'D') { cin >> k; if (!k) head = ne[head]; remove(k); } else { cin >> k >> x; add(k, x); } } for (int i = ne[0]; i != -1; i = ne[i]) cout << e[i] << ' '; cout << endl; return 0; }
2.雙鏈表
雙鏈表顧名思義就是指針方向雙向的鏈表。
可以看到除了頭尾他們的指針都是雙向的。
它的實現(xiàn)方法如下:
創(chuàng)建開始和結(jié)束結(jié)點。0表示開始,1表示結(jié)束,互相指向,在插入時直接往中間插入即可。
void init() { r[0] = 1, l[1] = 0; idx = 2; }
插入結(jié)點。雙鏈表插入結(jié)點的方法與單鏈表相同,但是操作要稍微復(fù)雜一些,這是在k結(jié)點右邊插入一結(jié)點的代碼。它要顧及結(jié)點左右的結(jié)點指向,對于兩邊都要操作。面臨在k結(jié)點左邊插入一結(jié)點時,不必單獨在寫一個函數(shù),而改成在l[k]結(jié)點的右邊插入一個結(jié)點。
void add(int k, int x) { a[idx] = x; r[idx] = r[k], l[idx] = l[r[k]]; l[r[k]] = idx, r[k] = idx; idx++; }
刪除節(jié)點。刪除結(jié)點與插入結(jié)點同理,我就不多贅述了。
void remove(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; }
輸出鏈表。可以選擇輸出方向,這里是從左往右輸出。
for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' '; cout << endl;
以下是完整代碼:
#include<iostream> using namespace std; const int N = 1e5 + 10; int a[N], l[N], r[N]; int idx; int m; void init() { r[0] = 1, l[1] = 0; idx = 2; } void add(int k, int x) { a[idx] = x; r[idx] = r[k], l[idx] = l[r[k]]; l[r[k]] = idx, r[k] = idx; idx++; } void remove(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; } int main() { init(); cin >> m; while (m--) { int k, x; string op; cin >> op; if (op == "L") { cin >> x; add(0, x); } else if (op == "R") { cin >> x; add(l[1], x); } else if (op == "D") { cin >> k; remove(k + 1); } else if (op == "IL") { cin >> k >> x; add(l[k + 1], x); } else if (op == "IR") { cin >> k >> x; add(k + 1, x); } } for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' '; cout << endl; return 0; }
總結(jié)
到此這篇關(guān)于C++如何用數(shù)組模擬鏈表的文章就介紹到這了,更多相關(guān)C++數(shù)組模擬鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++11 call_once 和 once_flag的使用與區(qū)別
本文主要介紹了C++11 call_once 和 once_flag的使用與區(qū)別,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06C++結(jié)構(gòu)體與類指針知識點總結(jié)
在本篇文章里小編給大家整理了關(guān)于C++結(jié)構(gòu)體與類指針知識點以及相關(guān)內(nèi)容,有興趣的朋友們參考學(xué)習(xí)下。2019-09-09