網站首頁 編程語言 正文
前引
我們在數據結構中都學到過單鏈表、雙鏈表、棧和隊列，當我們實現的時候時使用結構體指針實現的。定義一個結構體，結構體中存儲指針變量和存放數值的變量。當然，C++的STL庫中已經有實現好的棧和隊列，我們可以直接用。但是在做算法題時，有時候我們會發現超出時間限制。原因是我們用STL庫中的棧和隊列容器時，效率相對來說較慢。我們這時就引出用數組模擬實現棧和隊列。用數組模擬實現的使用起來效率更高、更方便。當然，我們也會講到用數組模擬實現單鏈表和雙鏈表。
一、數組模擬實現單鏈表
1.1 數組模擬的單鏈表解析
用結構體實現單鏈表時，我們會在結構體中定義一個存放數據的變量和一個存放下一個數據地址的指針。那我們用數組模擬實現怎么找到下一個數據的呢？用數組實現單鏈表，我們定義兩個數組即可。一個數組存放數據，另一個數組存放下一數據的下標（充當結構體中的指針）。我們之直節看代碼，理解更加容易。
//e[i] 表示點i的值
//ne[i] 表示節點i的下一個數據的下標
//head 表示棧頭下標
//idx 當前已經存儲到第幾個數據了
int head,e[N],ne[N],idx;
//初始化
void Init()
{
head=-1;
idx=0;
}
//頭插
void InsertHead(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
//在地k個節點后插入一個元素
void Insert(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//刪除第k個節點
void remove(int k)
{
ne[k]=ne[ne[k]];
}我們再結合著一個例題看一下。
1.2 數組模擬實現單鏈表例題
實現一個單鏈表，鏈表初始為空，支持三種操作：
- 向鏈表頭插入一個數；
- 刪除第kk個插入的數后面的數；
- 在第kk個插入的數后插入一個數。
現在要對該鏈表進行MM次操作，進行完所有操作后，從頭到尾輸出整個鏈表。
注意:題目中第kk個插入的數并不是指當前鏈表的第kk個數。例如操作過程中一共插入了nn個數，則按照插入的時間順序，這nn個數依次為：第11個插入的數，第22個插入的數，…第nn個插入的數。
輸入格式：
第一行包含整數MM，表示操作次數。
接下來MM行，每行包含一個操作命令，操作命令可能為以下幾種：
H x，表示向鏈表頭插入一個數xx。
D k，表示刪除第kk個插入的數后面的數（當kk為00時，表示刪除頭結點）。
I k x，表示在第kk個插入的數后面再插入一個數xx（此操作中kk均大于00）。
輸出格式：
共一行，將整個鏈表從頭到尾輸出。
數據范圍：
1≤M≤1000001≤M≤100000
所有操作保證合法。
輸入樣例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
輸出樣例：
6 4 6 5
我們看一下這道題的答案,代碼如下:
#include<iostream>
using namespace std;
const int N=100010;
//e[i] 表示點i的值
//ne[i] 表示節點i的下一個數據的下標
//head 表示棧頭下標
//idx 當前已經存儲到第幾個數據了
int head,e[N],ne[N],idx;
//初始化
void Init()
{
head=-1;
idx=0;
}
//頭插
void InsertHead(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
//在地k個節點后插入一個元素
void Insert(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//刪除第k個節點
void remove(int k)
{
ne[k]=ne[ne[k]];
}
int main()
{
int m;
cin>>m;
Init();
while(m--)
{
char op;
cin>>op;
if(op=='H')
{
int x;
cin>>x;
InsertHead(x);
}
else if(op=='D')
{
int k;
cin>>k;
if(!k)
head=ne[head];
else
remove(k-1);
}
else
{
int k,x;
cin>>k>>x;
Insert(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
{
printf("%d ",e[i]);
}
}二、數組模擬實現雙鏈表
2.1 數組模擬實現雙鏈表解析
數組模擬實現雙鏈表與數組模擬實現單鏈表大同小異。數組模擬實現雙鏈表時我們需要定義三個數組，一個數組存放數據，一個數組存放該數據左邊數據的下標（左指針），一個數組存放該數據右邊數據的下標（右指針）。我們直接看代碼：
//e[i] 是表示點i的值
//l[i] 表示節點i的左邊指針是多少
//r[i] 表示節點i的右邊指針是多少
//idx 存儲當前已經用到那個點了
int e[N],l[N],r[N],idx;
//初始化
void Init()
{
r[0]=1;
l[1]=0;
idx=2;
}
//在下標為k的右邊插入一個元素
void Insert(int k,int x)
{
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
//刪除下標為k的元素
void remove(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}我們發現，上面代碼并沒有定義在下標為k的左邊插入一個數據，我們只定義了在下標為k的右邊插入一個數據。為什么呢？因為可以用在下標為k的右邊插入一個數據函數實現在下標為k的左邊插入一個數據。我們只需要在下標為k的左邊的數據的右邊插入一個數據就相當于實現了在下標為k的左邊插入一個數據。如下圖，我們想在下標為3的左邊插入一個數據，其實就是在下標為2的右邊插入一個數據。
我們結合著一個例題理解一下。
2.2 數組模擬實現雙鏈表例題
實現一個雙鏈表，雙鏈表初始為空，支持55種操作：
- 在最左側插入一個數；
- 在最右側插入一個數；
- 將第kk個插入的數刪除；
- 在第kk個插入的數左側插入一個數；
- 在第kk個插入的數右側插入一個數
現在要對該鏈表進行MM次操作，進行完所有操作后，從左到右輸出整個鏈表。
注意:題目中第kk個插入的數并不是指當前鏈表的第kk個數。例如操作過程中一共插入了nn個數，則按照插入的時間順序，這nn個數依次為：第11個插入的數，第22個插入的數，…第nn個插入的數。
輸入格式：
第一行包含整數MM，表示操作次數。
接下來MM行，每行包含一個操作命令，操作命令可能為以下幾種：
-
L x，表示在鏈表的最左端插入數xx。 -
R x，表示在鏈表的最右端插入數xx。 -
D k，表示將第kk個插入的數刪除。 -
IL k x，表示在第kk個插入的數左側插入一個數。 -
IR k x，表示在第kk個插入的數右側插入一個數。
輸出格式：
共一行，將整個鏈表從左到右輸出。
數據范圍：
1≤M≤1000001≤M≤100000
所有操作保證合法。
輸入樣例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
輸出樣例：
8 7 7 3 2 9
我們看一下答案，代碼如下：
#include<iostream>
using namespace std;
const int N=100010;
//e[i] 是表示點i的值
//l[i] 表示節點i的左邊指針是多少
//r[i] 表示節點i的右邊指針是多少
//idx 存儲當前已經用到那個點了
int e[N],l[N],r[N],idx;
//初始化
void Init()
{
r[0]=1;
l[1]=0;
idx=2;
}
//在下標為k的右邊插入一個元素
void Insert(int k,int x)
{
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
//刪除下標為k的元素
void remove(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
int m;
cin>>m;
Init();
while(m--)
{
string op;
int x,k;
cin>>op;
if(op=="L")
{
cin>>x;
Insert(0,x);
}
else if(op=="R")
{
cin>>x;
Insert(l[1],x);
}
else if(op=="D")
{
cin>>k;
remove(k+1);
}
else if(op=="IL")
{
cin>>k>>x;
Insert(l[k+1],x);
}
else
{
cin>>k>>x;
Insert(k+1,x);
}
}
for (int i = r[0]; i != 1; i = r[i])
cout << e[i] << ' ';
return 0;
}三、數組模擬實現棧
3.1 數組模擬實現棧解析
我們用數組模擬實現棧是相對簡單的。我們只要滿足棧的先進后出的性質即可。我們直接看代碼，如下：
//********************* 模擬棧
int stack[N],top=0;
//往棧中插入元素
stack[top++];
//拿出棧頂元素
top--;
//棧頂元素
stack[top-1];
//判斷棧是否為空
if(top>0)
{
printf("notempty\n");
}
else
{
printf("empty\n");
}我們這里給出一個用到單調棧的例題。
3.2 數組模擬實現棧例題
給定一個長度為NN的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出?1?1。
輸入格式：
第一行包含整數NN，表示數列長度。
第二行包含NN個整數，表示整數數列。
輸出格式：
共一行，包含NN個整數，其中第ii個數表示第ii個數的左邊第一個比它小的數，如果不存在則輸出?1?1。
數據范圍：
1≤N≤1051≤N≤105
1≤數列中元素≤1091≤數列中元素≤109
輸入樣例：
5
3 4 2 7 5
輸出樣例：
-1 3 -1 2 2
我們看一下答案，代碼如下：
#include<iostream>
using namespace std;
const int N=100010;
int stack[N],top=0;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int x=0;
scanf("%d",&x);
while(top&&stack[top-1]>=x)
{
top--;
}
if(!top)
printf("-1 ");
else
{
printf("%d ",stack[top-1]);
}
stack[top++]=x;
}
return 0;
}四、數組模擬實現隊列
4.1 數組模擬實現隊列解析
同樣，我們用數組模擬實現隊列也是很簡單的。我們只要滿足隊列的先進先出的性質即可。我們直接看代碼，如下：
//********************* 模擬對列 int queue[N],head,tail=0; //插入 queue[tail++]=x; //彈出 head++; //判斷隊列是否為空 if(head<tail) not empty; else empty; //取出對頭，隊尾元素 queue[head]; queue[tail-1];
我們這里給出一道用到隊列的例題，相對來說難一點，我們看一下。
4.2 數組模擬實現隊列例題
給定一個大小為n≤106n≤106的數組。
有一個大小為kk的滑動窗口，它從數組的最左邊移動到最右邊。
你只能在窗口中看到kk個數字。
每次滑動窗口向右移動一個位置。
以下是一個例子：
該數組為[1 3 -1 -3 5 3 6 7]，kk為33。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [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 |
你的任務是確定滑動窗口位于每個位置時，窗口中的最大值和最小值。
輸入格式：
輸入包含兩行。
第一行包含兩個整數nn和kk，分別代表數組長度和滑動窗口的長度。
第二行有nn個整數，代表數組的具體數值。
同行數據之間用空格隔開。
輸出格式：
輸出包含兩個。
第一行輸出，從左至右，每個位置滑動窗口中的最小值。
第二行輸出，從左至右，每個位置滑動窗口中的最大值。
輸入樣例：
8 3
1 3 -1 -3 5 3 6 7
輸出樣例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
我們看一下答案，代碼如下：
#include<iostream>
using namespace std;
const int N=1000010;
int a[N],q[N];
int head,tail;
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
head=0;
tail=0;
for(int i=0;i<n;i++)
{
//判斷對頭是否已經劃出窗口
if(head<tail&&i-k+1>q[head])
head++;
//對頭確定最小數
while(head<tail&&a[q[tail-1]]>=a[i])
tail--;
q[tail++]=i;
if(i>=k-1)
printf("%d ",a[q[head]]);
}
printf("\n");
head=0;
tail=0;
for(int i=0;i<n;i++)
{
//判斷對頭是否已經劃出窗口
if(head<tail&&i-k+1>q[head])
head++;
//對頭確定最大數
while(head<tail&&a[q[tail-1]]<=a[i])
tail--;
q[tail++]=i;
if(i>=k-1)
printf("%d ",a[q[head]]);
}
return 0;
}原文鏈接：https://blog.csdn.net/weixin_67596609/article/details/128596985
相關推薦
- 2022-05-21 一次線上mongo慢查詢問題排查處理記錄_MongoDB
- 2022-09-05 卷積層計算量（FLOPS）和參數量的計算
- 2022-07-20 python密碼學列置換密碼學習_python
- 2022-08-29 Python如何利用pandas讀取csv數據并繪圖_python
- 2022-11-10 關于docker?cgroups資源限制的問題_docker
- 2021-12-16 Warning: Can‘t perform a React state update on an
- 2022-06-13 Python判斷dict中key是否存在的3種方法實例_python
- 2022-02-12 Cognos Sample for Oracle數據源
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速