上文我們通過結(jié)構(gòu)體的結(jié)構(gòu)實現(xiàn)了隊列、以及循環(huán)隊列的實現(xiàn)，我們或許在其他老師的教學(xué)中，只學(xué)到了用結(jié)構(gòu)體的形式來實現(xiàn)鏈表、隊列、棧等數(shù)據(jù)結(jié)構(gòu)，本文我想告訴你的是，我們可以使用數(shù)組的結(jié)構(gòu)實現(xiàn)鏈表、單調(diào)棧、單調(diào)隊列

目錄

前言

一、用數(shù)組結(jié)構(gòu)的好處

1.數(shù)組的優(yōu)缺點

2.鏈表的優(yōu)缺點

3.總結(jié)

二、用數(shù)組實現(xiàn)鏈表

1.認(rèn)識構(gòu)造、初始化

2.將x插入到頭結(jié)點

3.將x插入到第k次插入數(shù)值之后的位置

4.刪除第k次插入的結(jié)點

三、完整代碼演示

四、數(shù)組實現(xiàn)雙向鏈表

1.初始化

2.在第k次插入的點的右邊插入x

3.刪除第k個點

五、完整代碼

前言

你之前實現(xiàn)鏈表的形式，是不是這一種結(jié)構(gòu)來實現(xiàn)

typedef struct ListNode {
	int data;
	struct ListNode* next;
}List;

但是我如果告訴你只需要這樣兩個數(shù)組就能模擬實現(xiàn)鏈表，你相信嗎?。?！

head	表示頭節(jié)點
e[N]	表示存儲結(jié)點數(shù)值的數(shù)組
ne[N]	表示結(jié)點的下一個結(jié)點的位置
idx   表示當(dāng)前存儲元素的位置   當(dāng)前存儲到哪里了就是

?接下來我們來實現(xiàn)單鏈表，以及雙向鏈表

一、用數(shù)組結(jié)構(gòu)的好處

我們在日常學(xué)習(xí)的過程中，老師教授給我們的都是以結(jié)構(gòu)體的形式實現(xiàn)的鏈表，但是呢，比如我們要創(chuàng)建100000個結(jié)點，這樣的話， 用結(jié)構(gòu)體的話，時間太長，空間太大，反觀數(shù)組，就顯得很有優(yōu)勢了。

1.在搞算法的時候，使用數(shù)組的形式去模擬鏈表，會使得運算速度變快，更加適合寫算法，打比賽的小朋友。

2.在筆試的適合，會更快的創(chuàng)建實現(xiàn)鏈表的基礎(chǔ)功能，進(jìn)行插入刪除元素，并根據(jù)下標(biāo)直接找到所需元素等

我們在來了解一下數(shù)組和鏈表的優(yōu)缺點吧

1.數(shù)組的優(yōu)缺點

認(rèn)識數(shù)組：

數(shù)組是一種線性結(jié)構(gòu)，存儲的空間是內(nèi)存連續(xù)的（物理連續(xù)），每當(dāng)創(chuàng)建一個數(shù)組的時候，就必須先申請好一段指定大小的空間。（一次申請即可指定大小的空間）

優(yōu)點：

由于內(nèi)存連續(xù)這一特征，數(shù)組的訪問速度很快，直到索引下標(biāo)之后，可以實現(xiàn)O(1)的時間復(fù)雜度的訪問。

缺點：

1.在任意位置刪除和插入操作的時候，就會涉及到部分元素的移動，這樣的話我們對于數(shù)組的任意位置的刪除和插入的操作的時間復(fù)雜度為O(n)。

比如：

1>在i點后面插入數(shù)據(jù)，那么就需要i+1位置以及之后的元素，整體后移一位（for循環(huán)操作），然后再將插入的數(shù)據(jù)放在i+1的位置上

2>在i點之后刪除元素，那么就需要，將i+1以及之后的元素，整體前移一位，總元素個數(shù)減一

以上是數(shù)組的優(yōu)缺點，可以快速訪問，達(dá)到O(1)，但是在任意刪除和插入元素的時候，會耗時間，達(dá)到O(n)。

2.鏈表的優(yōu)缺點

認(rèn)識鏈表

1.鏈表也是一種線性結(jié)構(gòu)，但是他存儲空間是不連續(xù)的（物理不連續(xù)，邏輯連續(xù)），鏈表的長度是不確定且支持動態(tài)擴展的。每次插入元素的時候，都需要進(jìn)行申請新節(jié)點，然后賦值，插入鏈表中。

優(yōu)點：
在插入數(shù)據(jù)或者刪除數(shù)據(jù)的時候，只需要改變指針的指向即可，不需要類似于數(shù)組那樣部分整體移動，整個過程不涉及元素的遷移，因此鏈表的插入和刪除操作，時間復(fù)雜度為O(1)

缺點：

在查找任意位置的結(jié)點的數(shù)值域的時候，需要遍歷，時間復(fù)雜度為O(n)

但是我們在任意位置插入或者刪除元素的時候，需要查找這個指定的元素的結(jié)點位置，所以綜合起來，鏈表的插入和刪除仍為O(n)。

3.總結(jié)

無論數(shù)組還是鏈表，查找的時間復(fù)雜度都是O(n)，查找都要挨個遍歷，直到找到滿足的條件的數(shù)據(jù)為止，所以對于鏈表，如果沒有給定，指針的地址，只是要插入刪除第N位元素的時候，加上查找，綜合起來時間復(fù)雜度為O(n)。

但是我們?nèi)绻詳?shù)組的形式來實現(xiàn)鏈表，那么插入刪除指定元素位置的時候，是不是就更加簡便了呢，在第N位插入刪除元素的時候，直接以O(shè)(1)的時間復(fù)雜度找到該位置結(jié)點，然后再由于鏈表的刪除插入都是O(1)的，所以整個刪除或插入操作，綜合時間復(fù)雜度為O(1),比普通鏈表快很多。

二、用數(shù)組實現(xiàn)鏈表

1.認(rèn)識構(gòu)造、初始化

我們先由圖示了解初始化的時候的準(zhǔn)備工作

我們使用c++會更加方便理解，因為c++支持用變量來定義數(shù)組

初始化代碼：

//使用c++更簡單，先用c++的形式實現(xiàn)
const int N = 100010;
int head, e[N], ne[N], idx; //全局變量
void init() {
	head = -1;
	idx = 0;//進(jìn)行初始化的操作，idx為當(dāng)前鏈表中（數(shù)組）最后一個元素（末尾），下標(biāo)位置
}

2.將x插入到頭結(jié)點

就是所謂的鏈表中的頭部插入

圖示：

實際上和普通鏈表的頭插一樣，只是流程next指針換成了ne[N]數(shù)組的形式，記錄的是下一結(jié)點的數(shù)值。

代碼如下：

void add_to_head(int x) {
	e[idx] = x;//將x數(shù)值存入到e[]數(shù)組中
	ne[idx] = ne[head];//將idx新插入的結(jié)點的下一個位置存儲到ne[idx]中  ，全局變量 ne以及n數(shù)組初始化為0
	head = idx;
	idx++;
}

3.將x插入到第k次插入數(shù)值之后的位置

圖示：

我們要說明一個問題，ne[N]這個數(shù)組存放的數(shù)值，是不需要管的，因為不管是add還是remove，插入還是刪除結(jié)點，都不會重復(fù)，實際上，e[ne[head]]是得到head結(jié)點下一個結(jié)點的數(shù)值，ne[]數(shù)組只作為，下標(biāo)使用。?

我們是在第k次插入的之后的位置插入x，但是與此同時 ，此時的idx成為新的第k次插入數(shù)據(jù)下標(biāo)，也就是說，再次對第k次插入數(shù)值之后的位置插入的x，實際上是在上一次的新插入的結(jié)點之后進(jìn)行插入

圖示：

代碼如下：

//在第k個插入的數(shù)字之后插入數(shù)據(jù)
void add(int k, int x) {
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}

4.刪除第k次插入的結(jié)點

//將下標(biāo)為k的點后面的點刪掉
void remove(int k, int ne[]) {
	ne[k] = ne[ne[k]];//表示k的下一個位置（ne）為下一個位置的下一個位置，這樣跳過了原來的ne[k]結(jié)點
}//使用的時候應(yīng)該是  刪除的是k之后的點

直接跳過即可，和鏈表類似

三、完整代碼演示

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>


const int N = 100010;
int n, e[N], ne[N], idx, head;


//初始化
void init() {
	head = -1;
	idx = 0;
}

//頭插
void add_to_head(int x) {
	e[idx] = x;
	ne[idx] = head;
	head = idx;
	idx++;
}

//在第k個插入的數(shù)字之后插入數(shù)據(jù)
void add(int k, int x) {
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}
//刪除第k的插入的數(shù)據(jù)
void remove(int k) {
	ne[k] = ne[ne[k]];
}

int main()
{
	init();
	add_to_head(1);
	add_to_head(2);
	add_to_head(3);
	add_to_head(4);
	add_to_head(5);
	add(2-1, 10);
	add(2-1, 2);
	add(2-1, 3);
	add(2-1, 4);
	add(2-1, 5);
	add_to_head(50);
	for (int i = head; i != -1; i=ne[i]) {
		printf("%d ", e[i]);
	}
	printf("\n");
	for (int i = head; i != -1; i = ne[i]) {
		printf("%d ", ne[i]);
	}
	return 0;
}

四、數(shù)組實現(xiàn)雙向鏈表

1.初始化

//初始化
// e[]表示節(jié)點的值，l[]表示節(jié)點的左指針，r[]表示節(jié)點的右指針，idx表示當(dāng)前用到了哪個節(jié)點
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
	//0表示為左端點，1表示為右端點
	r[0] = 1;
	l[1] = 0;
	idx = 2;//從2開始
}

我們設(shè)定，用e[N]數(shù)組來記錄數(shù)據(jù)，在用 l[N] 、 r[N]數(shù)組表示結(jié)點的左右指針，一開始，0表示為左端點，1表示右端點，然后r、l兩個數(shù)組記錄，數(shù)值下標(biāo)從2開始

e[]表示節(jié)點的值，l[]表示節(jié)點的左指針，r[]表示節(jié)點的右指針，idx表示當(dāng)前用到了哪個節(jié)點文章來源地址http://www.zghlxwxcb.cn/news/detail-807123.html

2.在第k次插入的點的右邊插入x

//在第k次插入的點的右邊插入x；

void add(int k, int x) {
	e[idx] = x;//數(shù)值x給當(dāng)前idx位置的e數(shù)組存儲
	r[idx] = r[k];//將新節(jié)點的左右兩端分別連接k的后一個結(jié)點r[k]和k本身
	l[idx] = k;
	l[r[k]] = idx;//然后將k的右端點的左端點連接idx
	r[k] = idx++;//最后將k的右端點連接idx
}

3.刪除第k個點

//刪除第k個點
void remove(int k) {
	//就是將k的左端點和右端點相互連接
	l[r[k]] = l[k];
	r[l[k]] = r[k];
}

五、完整代碼

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
//使用數(shù)組的形式實現(xiàn)雙向鏈表


//e[N]	表示存儲結(jié)點的數(shù)值
//l[N]	表示當(dāng)前結(jié)點的左結(jié)點位置
//r[N]	表示當(dāng)前結(jié)點的右節(jié)點位置
//idx	表示當(dāng)前結(jié)點存儲的位置

//初始化
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
	//0表示為左端點，1表示為右端點
	r[0] = 1;
	l[1] = 0;
	idx = 2;//從2開始
}

//在第k次插入的點的右邊插入x；

void add(int k, int x) {
	e[idx] = x;//數(shù)值x給當(dāng)前idx位置的e數(shù)組存儲
	r[idx] = r[k];//將新節(jié)點的左右兩端分別連接k的后一個結(jié)點r[k]和k本身
	l[idx] = k;
	l[r[k]] = idx;//然后將k的右端點的左端點連接idx
	r[k] = idx++;//最后將k的右端點連接idx
}

//刪除第k個點
void remove(int k) {
	//就是將k的左端點和右端點相互連接
	l[r[k]] = l[k];
	r[l[k]] = r[k];
}

int main()
{
	init();//初始化
	//添加元素
	for (int i = 0; i < 10; i++)
	{
		add(i, i);//在第i次插入的元素的后面，插入節(jié)點x
	}
	//實現(xiàn)遍歷

	//因為e存儲的是實際元素，但是由于要實現(xiàn)雙向鏈表，即創(chuàng)建左右數(shù)組，表示當(dāng)前idx的左右下標(biāo)
	//如果我們需要進(jìn)行正向，即向右，只需要以r[i]為下標(biāo)，不斷輸出e的元素即可
	//反之以l[i]
	for (int i = 0; i < 10; i++)
	{
		//num表示當(dāng)前此時下標(biāo)位置
		cout << e[r[i]] << " ";//每一次循環(huán)不斷更新當(dāng)前節(jié)點的下一個節(jié)點的下標(biāo)位置
	}

	cout << endl;
	for (int i = 0; i <10 ; i++)
	{
		//idx表示當(dāng)前此時下標(biāo)位置
		cout << e[--idx] << " ";//每一次循環(huán)不斷更新當(dāng)前節(jié)點的下一個節(jié)點的下標(biāo)位置
	}
	//以上是正序和逆序的遍歷
	cout << endl;

	return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)和算法】使用數(shù)組的結(jié)構(gòu)實現(xiàn)鏈表（單向或雙向）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！