陣列實作的單鏈表(c++)
在面對大量資料（特別是競賽時），如果使用結構體實作的鏈表，當你進行大量插入時，new一個節點是非常慢的，并且用結構體實作的鏈表每一次進行操作時，由于節點與節點之間用指標聯系，當你要遍歷到鏈表中某個節點，每次都需要從頭開始，時間復雜度為O(n)，而當使用陣列實作鏈表時，陣列實作的單鏈表可以通過下標來索引節點，可以直接通過下標找到某個節點的值和下一個節點的，因此陣列實作的單鏈表的最大優點就是快(插入和洗掉操作都是O(1)的時間復雜度)，畢竟陣列的特點就是隨機存取嘛，
1 #include <stdio.h>
2 #include <iostream>
3 using namespace std;
4 const int N=100010;
5 //用陣列實作單鏈表是因為 用結構體和指標*next new的速度太慢
6 //head 表示頭結點的下標
7 //e[i]表示結點i的值
8 //ne[i]表示結點i的next2指標是多少
9 //idex表示當前儲存到了那個點
10 int head,e[N],ne[N],idx;
11 void init()
12 {
13 head=-1;
14 idx=0;
15 }
16 void add_to_head(int x) //插入元素到頭結點
17 {
18 e[idx]=x;
19 ne[idx]=head;
20 head=idx;
21 idx++;
22 }
23 void add(int k,int x)//把元素X插入到k后面
24 {
25 e[idx]=x;
26 ne[idx]=ne[k];
27 ne[k]=idx;
28 idx++;
29 }
30 void remove(int k)//洗掉元素x后面的元素
31 {
32 ne[k]=ne[ne[k]];
33 //idx--; 不用管洗掉的元素 ，就讓他放在陣列里面
34 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/247687.html
標籤：其他
上一篇：一萬一千字！結合代碼超詳細講解SQL執行流程（二）！干貨到底！建議收藏！
下一篇：【資訊流推薦論文大賞】Predicting Clicks: Estimating the Click-Through Rate for New Ads