C++算法（數據結構）版

有些題目不是完整的題目，如需查看完整的題目請移步到acwing的算法基礎課中

單鏈表

鏈表：

（單向）鏈表是由節點和指針構成的數據結構，每個節點存有一個值，和下一個指向下一個節點的指針，因此很多的鏈表問題可以用遞歸來處理。鏈表不能直接獲取任意節點的值，必須要通過指針找到該節點后才能獲取其值

基本操作：

在鏈表頭部插入 / 刪除一個數

在鏈表尾部插入 / 刪除一個數

在鏈表中間插入 / 刪除 一個數

• 單鏈表（鄰接表）常用于存儲圖和樹

題目：

實現一個單鏈表，鏈表初始為空，支持三種操作：

1. 向鏈表頭插入一個數；
2. 刪除第 k 個插入的數后面的一個數；
3. 在第 k 個插入的數后插入一個數。

現在要對該鏈表進行 M 次操作，進行完所有操作后，從頭到尾輸出整個鏈表。

完整題目：（https://www.acwing.com/problem/content/description/828/）acwing算法基礎課

思路：

插入操作：

• 當鏈表為空時，idx = 0
• 當插入第一個元素后(設第一個插入的元素為 a ) 則，e[0] = a , idx = 1
• 當插入第二個元素后(設第二個插入的元素為 b ) 則，e[1] = b , idx = 2
• 當插入第三個元素后(設第三個插入的元素為 c ) 則，e[2] = c , idx = 3
• 當插入第四個元素后(設第四個插入的元素為 d ) 則，e[3] = d , idx = 4

所以；第 K 個插入的數的索引值為 k - 1

刪除加插入操作：

• 當鏈表為空時，idx = 0
• 插入第一個元素 a 后：e[0] = a, idx = 1，
• 插入第二個元素 b 后：e[1] = b, idx = 2,
• 刪除第一個插入的元素 a：head 變為 1， idx 不變，= 2。
• 刪除第二個插入的元素 b：head 變為 2， idx 不變，=2。
• 插入第三個元素 c 后：e[2] = c, idx = 3。

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N  = 100010;int head,idx;
int ne[N],e[N];void init()
{head = -1;idx = 0;
}void add_to_head(int x)
{e[idx] = x;ne[idx] = head;head = idx++;
}void add(int k,int x)
{e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}void remove(int k)
{ne[k] = ne[ne[k]];
}int main()
{int m;cin>>m;init();while(m--){int k,x;char op;cin>>op;if(op == 'H'){cin>>x;add_to_head(x);}else if(op == 'D'){cin>>k;if(!k) head = ne[head];remove(k - 1);  //第k個元素對應的索引為k - 1}else{cin>>k>>x;add(k - 1,x);  //第k個元素對應的索引為k - 1}}for(int i = head;i != -1;i = ne[i])cout<<e[i]<<" ";cout<<endl;return 0;}

總結模板：（acwing——Y總的）

// head存儲鏈表頭，e[]存儲節點的值，ne[]存儲節點的next指針，idx表示當前用到了哪個節點
int head, e[N], ne[N], idx;// 初始化
void init()
{head = -1;idx = 0;
}// 在鏈表頭插入一個數a
void insert(int a)
{e[idx] = a, ne[idx] = head, head = idx ++ ;
}// 將頭結點刪除，需要保證頭結點存在
void remove()
{head = ne[head];
}

雙鏈表

題目：

實現一個雙鏈表，雙鏈表初始為空，支持 5 種操作：

1. 在最左側插入一個數；
2. 在最右側插入一個數；
3. 將第 k 個插入的數刪除；
4. 在第 k 個插入的數左側插入一個數；
5. 在第 k 個插入的數右側插入一個數

現在要對該鏈表進行 M 次操作，進行完所有操作后，從左到右輸出整個鏈表。

注意:題目中第 k 個插入的數并不是指當前鏈表的第 k 個數。例如操作過程中一共插入了 n 個數，則按照插入的時間順序，這 n 個數依次為：第 1 個插入的數，第 2 個插入的數，…第 n 個插入的數。

輸入格式

第一行包含整數 M，表示操作次數。

接下來 M 行，每行包含一個操作命令，操作命令可能為以下幾種：

1. L x，表示在鏈表的最左端插入數 x。
2. R x，表示在鏈表的最右端插入數 x。
3. D k，表示將第 k 個插入的數刪除。
4. IL k x，表示在第 k 個插入的數左側插入一個數。
5. IR k x，表示在第 k 個插入的數右側插入一個數。

輸出格式

共一行，將整個鏈表從左到右輸出。

思路：

和上面的單鏈表差不多

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;int idx;
int l[N],r[N],e[N];void init()
{//0表示左端點，1表示右端點l[1] = 0;r[0] = 1;idx = 2;
}//在下標是k的點的右邊，插入xl[idx] = 
void add(int k,int x)
{e[idx] = x;l[idx] = k;r[idx] = 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()
{int m;cin>>m;init();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{cin>>k>>x;add(k + 1,x);}}for(int i = r[0]; i != 1;i = r[i])cout<<e[i]<<" ";return 0;
}

總結模板：（acwing——Y總的）

// e[]表示節點的值，l[]表示節點的左指針，r[]表示節點的右指針，idx表示當前用到了哪個節點
int e[N], l[N], r[N], idx;// 初始化
void init()
{//0是左端點，1是右端點r[0] = 1, l[1] = 0;idx = 2;
}// 在節點a的右邊插入一個數x
void insert(int a, int x)
{e[idx] = x;l[idx] = a, r[idx] = r[a];l[r[a]] = idx, r[a] = idx ++ ;
}// 刪除節點a
void remove(int a)
{l[r[a]] = l[a];r[l[a]] = r[a];
}

棧

棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。

問題：

實現一個棧，棧初始為空，支持四種操作：

1. push x – 向棧頂插入一個數 x；
2. pop – 從棧頂彈出一個數；
3. empty – 判斷棧是否為空；
4. query – 查詢棧頂元素。

現在要對棧進行 M 個操作，其中的每個操作 3 和操作 4 都要輸出相應的結果

完整題目：（https://www.acwing.com/problem/content/description/830/） acwing算法基礎課

思路：

有數組來模擬棧：

• 用top表示棧頂所在的索引。初始時，top = -1。表示沒有元素。

• push x ：入棧 ，st[++top] = x。

• pop : 出棧， top–。

• empty ：top 大于等于 0 棧非空，小于 0 棧空。top == -1 ? “YES” : “NO”

• query ： 返回棧頂元素。st[top]

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;
int st[N];
int top = -1;int main()
{int m;cin>>m;while(m--){string op;cin>>op;if(op == "push"){int x;cin>>x;st[++top] = x;}if(op == "pop"){top--;}if(op == "empty"){cout<<(top == -1 ? "YES": "NO")<<endl;}if(op == "query"){cout<<st[top]<<endl;}}return 0;
}

總結模板：（acwing——Y總的）

// tt表示棧頂
int stk[N], tt = 0;// 向棧頂插入一個數
stk[ ++ tt] = x;// 從棧頂彈出一個數
tt -- ;// 棧頂的值
stk[tt];// 判斷棧是否為空，如果 tt > 0，則表示不為空
if (tt > 0)
{}

隊列

隊列：是一個特殊的數組。最前面叫隊頭，最后面叫隊尾。只允許在最后面添加元素，只允許在最前面刪除元素。

題目;

實現一個隊列，隊列初始為空，支持四種操作：

1. push x – 向隊尾插入一個數 x；
2. pop – 從隊頭彈出一個數；
3. empty – 判斷隊列是否為空；
4. query – 查詢隊頭元素。

現在要對隊列進行 M 個操作，其中的每個操作 3 和操作 4 都要輸出相應的結果。

完整題目：（https://www.acwing.com/problem/content/description/831/）

思路：

• 用一個數組 q 保存數據。

• 用 hh 代表隊頭，q[hh] 就是隊頭元素， 用 tt 代表隊尾， q[tt] 就是隊尾元素

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;
int hh =0;
int tt = -1;
int q[N];int m;
string s;void push(int x)
{q[++tt] = x;
}void pop()
{hh++;
}void empty()
{if(tt >= hh)cout<<"NO"<<endl;else cout<<"YES"<<endl;
}void query()
{cout<<q[hh]<<endl;
}int main()
{cin>>m;while(m--){cin>>s;if(s == "push"){int x;cin>>x;push(x);}if(s == "pop"){pop();}if(s == "empty"){empty();}if(s == "query"){query();}}return 0;
}

總結模板：（acwing——Y總的）

// hh 表示隊頭，tt表示隊尾
int q[N], hh = 0, tt = -1;// 向隊尾插入一個數
q[ ++ tt] = x;// 從隊頭彈出一個數
hh ++ ;// 隊頭的值
q[hh];// 判斷隊列是否為空，如果 hh <= tt，則表示不為空
if (hh <= tt)
{}

這適用于普通隊列，若是循環隊列還需要加上

if (tt == N) tt = 0; 的判斷條件

單調棧

單調棧是通過維持棧內值的單調遞增（遞減）性，在整體$o(n)$的時間內處理需要大小比較的問題。

題目：

給定一個長度為 N 的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出 ?1。

輸入格式

第一行包含整數 N，表示數列長度。

第二行包含 N 個整數，表示整數數列。

輸出格式

共一行，包含 N 個整數，其中第 i 個數表示第 i 個數的左邊第一個比它小的數，如果不存在則輸出 ?1。

思路：

• 用單調遞增棧，當該元素可以入棧的時候，棧頂元素就是它左側第一個比它小的元素
• 我們只需要維護一個從棧頂到棧底單調遞減的棧，每次不符合單調性就彈棧，最后輸出棧頂即可，最后輸出答案

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;int stk[N],tt;
int n;int main()
{cin>>n;for(int i = 0;i < n;i++){int x;cin>>x;while(tt && stk[tt] >= x) tt--;if(tt) cout<<stk[tt]<<' ';else cout<<-1<<' ';stk[++tt] = x;}return 0;
}

核心部分：

while(tt && stk[tt] >= x) tt--;
if(tt) cout<<stk[tt]<<' ';
else cout<<-1<<' ';stk[++tt] = x;

總結模板：（acwing——Y總的）

//常見模型：找出每個數左邊離它最近的比它大/小的數
int tt = 0;
for (int i = 1; i <= n; i ++ )
{while (tt && check(stk[tt], i)) tt -- ;stk[ ++ tt] = i;
}

單調隊列

題目：

給定一個大小為 n≤106 的數組。

有一個大小為 k 的滑動窗口，它從數組的最左邊移動到最右邊。

你只能在窗口中看到 k 個數字。

每次滑動窗口向右移動一個位置。

以下是一個例子：

該數組為 [1 3 -1 -3 5 3 6 7]，k 為 3。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任務是確定滑動窗口位于每個位置時，窗口中的最大值和最小值。

輸入格式

輸入包含兩行。

第一行包含兩個整數 n 和 k，分別代表數組長度和滑動窗口的長度。

第二行有 n 個整數，代表數組的具體數值。

同行數據之間用空格隔開。

輸出格式

輸出包含兩個。

第一行輸出，從左至右，每個位置滑動窗口中的最小值。

第二行輸出，從左至右，每個位置滑動窗口中的最大值。

思路：

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N = 1000010;int n,k;
int hh = 0,tt = -1;
int q[N],a[N];int main()
{scanf("%d%d",&n,&k);for(int i = 0;i < n;i++){scanf("%d",&a[i]);//移除窗口外的元素（隊首出隊）if( i - k +1 > q[hh])  ++hh;  // 若隊首出窗口，hh加1//維護隊列單調性（保證隊列遞增）while(hh <= tt && a[i] <= a[q[tt]]) --tt;   // 若隊尾不單調，tt減1q[++tt] = i;    // 當前元素入隊，下標加到隊尾if(i + 1 >= k)printf("%d ",a[q[hh]]);   // 輸出結果}printf("\n");hh = 0,tt = -1;for (int i = 0; i < n; ++ i){if (i - k + 1 > q[hh]) ++ hh;//維護隊列單調性（保證隊列遞減）while (hh <= tt && a[i] >= a[q[tt]]) -- tt;q[++ tt] = i;if (i + 1 >= k) printf("%d ", a[q[hh]]);}printf("\n");return 0;
}

總結模板：（acwing——Y總的）

//常見模型：找出滑動窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判斷隊頭是否滑出窗口while (hh <= tt && check(q[tt], i)) tt -- ;q[ ++ tt] = i;
}

KMP

• KMP 算法常用于解決「模式串在文本串中是否存在匹配」的問題

題目：

給定一個字符串 S，以及一個模式串 P，所有字符串中只包含大小寫英文字母以及阿拉伯數字。

模式串 P 在字符串 S 中多次作為子串出現。

求出模式串 P 在字符串 S 中所有出現的位置的起始下標。

輸入格式

第一行輸入整數 N，表示字符串 P 的長度。

第二行輸入字符串 P。

第三行輸入整數 M，表示字符串 S 的長度。

第四行輸入字符串 S。

輸出格式

共一行，輸出所有出現位置的起始下標（下標從 0 開始計數），整數之間用空格隔開。

思路：

求next數組 , 利用Next數組避免回溯 , 匹配字符串

實現代碼：

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010, M = 1000010;int n, m;
char p[N], s[M];
int Next[N];int main() 
{cin >> n >> p + 1 >> m >> s + 1;for (int i = 2, j = 0; i <= n; i++) {// 若當前字符不匹配，通過Next數組回溯j到上一個可能匹配的位置while (j && p[i] != p[j + 1]) j = Next[j];// 若匹配，j后移（延長前綴后綴的匹配長度）if (p[i] == p[j + 1]) j++;// 記錄當前位置的最長匹配長度Next[i] = j;}for (int i = 1, j = 0; i <= m; i++){// 若不匹配，根據Next數組將j跳轉到合適位置（避免i回溯）while (j && s[i] != p[j + 1]) j = Next[j];if (s[i] == p[j + 1]) j++;if (j == n) {printf("%d ", i - n); j = Next[j];}}return 0;
}

總結模板：（acwing——Y總的）

// s[]是長文本，p[]是模式串，n是s的長度，m是p的長度
求模式串的next數組：
for (int i = 2, j = 0; i <= m; i ++ )
{while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;
}// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m){j = ne[j];// 匹配成功后的邏輯}
}

Trie

• Trie樹又稱字典樹、單詞查找樹。是一種能夠高效存儲和查找字符串集合的數據結構

題目：

維護一個字符串集合，支持兩種操作：

1. I x 向集合中插入一個字符串 x；
2. Q x 詢問一個字符串在集合中出現了多少次。

共有 N 個操作，所有輸入的字符串總長度不超過 105，字符串僅包含小寫英文字母。

完整題目：（https://www.acwing.com/problem/content/837/）acwing 算法基礎課

思路：

Trie 樹中每個節點存儲一個字符，從根節點到葉節點的一條路徑存儲一個字符串。

實現代碼：

#include<iostream>using namespace std;const int N = 100010;char str[N];
int cnt[N],idx,son[N][26];void insert(char str[])
{int p = 0;for(int i = 0;str[i];i++){int u = str[i] - 'a';  //將字母轉化為數字if(!son[p][u]) son[p][u] = ++idx;//該節點不存在，創建節點,其值為下一個節點位置p = son[p][u];   //使“p指針”指向下一個節點位置}cnt[p]++;  //結束時的標記，也是記錄以此節點結束的字符串個數
}int query(char str[])
{int p = 0;for(int i = 0;str[i];i++){int u = str[i] - 'a';if(!son[p][u]) return 0;  //該節點不存在，即該字符串不存在p = son[p][u];}return cnt[p];  //返回字符串出現的次數
}int main()
{int n;cin>>n;while(n--){char op[2];scanf("%s%s",op,str);if(op[0] == 'I')insert(str);elseprintf("%d\n",query(str));}return 0;
}

總結模板：（acwing——Y總的）

int son[N][26], cnt[N], idx;
// 0號點既是根節點，又是空節點
// son[][]存儲樹中每個節點的子節點
// cnt[]存儲以每個節點結尾的單詞數量// 插入一個字符串
void insert(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++ ;
}// 查詢字符串出現的次數
int query(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}

并查集

并查集可以動態的連通兩個點，并且可以非常快速的判斷兩個點是否連通

題目：

一共有 n 個數，編號是 1～n，最開始每個數各自在一個集合中。

現在要進行 m 個操作，操作共有兩種：

1. M a b，將編號為 a 和 b 的兩個數所在的集合合并，如果兩個數已經在同一個集合中，則忽略這個操作；
2. Q a b，詢問編號為 a 和 b 的兩個數是否在同一個集合中；

輸入格式

第一行輸入整數 n 和 m。

接下來 m 行，每行包含一個操作指令，指令為 M a b 或 Q a b 中的一種。

輸出格式

對于每個詢問指令 Q a b，都要輸出一個結果，如果 a 和 b 在同一集合內，則輸出 Yes，否則輸出 No。

每個結果占一行。

數據范圍

1 ≤ n,m ≤ $10^5$

思路：

基本原理：

每個集合用一棵樹來表示，樹根的編號就是整個集合的編號，每個節點存儲它的父節點，p[x]表示它的父節點

實現代碼：

#include<iostream>using namespace std;const int N = 100010;int n,m;
int p[N];int find(int x)
{if(x != p[x])p[x] =  find(p[x]);return p[x];
}void merge(int a,int b)
{int pa = find(a);int pb = find(b);if(pa != pb)p[pa] = pb;}void query(int a,int b)
{int pa = find(a);int pb = find(b);if(pa == pb) cout<<"Yes"<<endl;else cout<<"No"<<endl;return ;
}int main()
{cin>>n>>m;for(int i = 1;i <= n;i++)p[i] = i;while(m--){char op;cin>>op;int a,b;cin>>a>>b;if(op == 'M'){merge(a,b);}else{query(a,b);}}return 0 ;
}

樸素并查集–總結模板：（acwing——Y總的）

int p[N]; //存儲每個點的祖宗節點// 返回x的祖宗節點
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}
// 初始化，假定節點編號是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的兩個集合：
p[find(a)] = find(b);

堆

• 堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序， 它的最壞、最好、平均時間復雜度均為 $O(nlogn)$， 它也是不穩定排序。
• 堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值， 這種情況稱為大頂堆。
• 每個結點的值都小于或等于其左右孩子結點的值， 這種情況稱為小頂堆。

題目：

輸入一個長度為 n 的整數數列，從小到大輸出前 m 小的數。

輸入格式

第一行包含整數 n 和 m。

第二行包含 n 個整數，表示整數數列。

輸出格式

共一行，包含 m 個整數，表示整數數列中前 m 小的數。

數據范圍

1 ≤ m ≤ n ≤ $10^5$

思路：

1. 將序列構造成一個大頂堆，再將其與末尾元素進行交換， 此時末尾就為最大值。
2. 然后將剩余元素重新構造成一個堆， 這樣會得到 n 個元素的次小值。 如此反復執行， 便能得到一個有序序列了。

實現代碼：

#include<iostream>using namespace std;const int N = 100010;int n,m;
int cnt;
int a[N];void down(int u)
{//t記錄最小點的編號int t = u;//有左兒子，并且左兒子比t節點的值小，更新tif(2 * u <= cnt && a[2 * u] < a[t]) t = 2 * u;//有右兒子，并且右兒子比t節點的值小，更新tif(2 * u + 1 <= cnt && a[2 * u + 1] < a[t]) t = 2 * u + 1;if(u != t){swap(a[u],a[t]);down(t);}}int main()
{cin>>n>>m;cnt = n;for(int i = 1;i <= n;i++)cin>>a[i];//從第一個非葉節點開始，從右到左，從下到上處理每個節點for(int i = n / 2;i >= 1;i--)down(i);while(m--){cout<<a[1]<<" ";swap(a[1],a[cnt]);//右邊界左移cnt--;down(1);}return 0;
}

總結模板：（acwing——Y總的）

// h[N]存儲堆中的值, h[1]是堆頂，x的左兒子是2x, 右兒子是2x + 1
// ph[k]存儲第k個插入的點在堆中的位置
// hp[k]存儲堆中下標是k的點是第幾個插入的
int h[N], ph[N], hp[N], size;// 交換兩個點，及其映射關系
void heap_swap(int a, int b)
{swap(ph[hp[a]],ph[hp[b]]);swap(hp[a], hp[b]);swap(h[a], h[b]);
}void down(int u)
{int t = u;if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){heap_swap(u, t);down(t);}
}void up(int u)
{while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希表

• 哈希表（hash table,hash map）,又稱散列列表，使用O(n)空間復雜度存儲數據，通過哈希函數映射位置，從而實現近似O(1)時間復雜度的插入，查找，刪除等操作。哈希表可以用來統計頻率，記錄內容等等
• 如果元素有窮，并且范圍不大，那么可以用一個固定大小的數組來存儲或統計元素。

Hash表的主要基本操作：

1. 計算Hash函數的值
2. 定位到對應鏈表中依次遍歷，比較

常用方法：

拉鏈法

開放尋址法

拉鏈法代碼模板–總結模板：（acwing——Y總的）

int h[N], e[N], ne[N], idx;// 向哈希表中插入一個數
void insert(int x)
{int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx ++ ;
}// 在哈希表中查詢某個數是否存在
bool find(int x)
{int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false;
}

開放尋址法代碼模板–總結模板：（acwing——Y總的）

int h[N];// 如果x在哈希表中，返回x的下標；如果x不在哈希表中，返回x應該插入的位置
int find(int x)
{int t = (x % N + N) % N;while (h[t] != null && h[t] != x){t ++ ;if (t == N) t = 0;}return t;
}