網站首頁 編程語言 正文
前引
我們在數(shù)據(jù)結構中都學到過單鏈表、雙鏈表、棧和隊列，當我們實現(xiàn)的時候時使用結構體指針實現(xiàn)的。定義一個結構體，結構體中存儲指針變量和存放數(shù)值的變量。當然，C++的STL庫中已經有實現(xiàn)好的棧和隊列，我們可以直接用。但是在做算法題時，有時候我們會發(fā)現(xiàn)超出時間限制。原因是我們用STL庫中的棧和隊列容器時，效率相對來說較慢。我們這時就引出用數(shù)組模擬實現(xiàn)棧和隊列。用數(shù)組模擬實現(xiàn)的使用起來效率更高、更方便。當然，我們也會講到用數(shù)組模擬實現(xiàn)單鏈表和雙鏈表。
一、數(shù)組模擬實現(xiàn)單鏈表
1.1 數(shù)組模擬的單鏈表解析
用結構體實現(xiàn)單鏈表時，我們會在結構體中定義一個存放數(shù)據(jù)的變量和一個存放下一個數(shù)據(jù)地址的指針。那我們用數(shù)組模擬實現(xiàn)怎么找到下一個數(shù)據(jù)的呢？用數(shù)組實現(xiàn)單鏈表，我們定義兩個數(shù)組即可。一個數(shù)組存放數(shù)據(jù)，另一個數(shù)組存放下一數(shù)據(jù)的下標（充當結構體中的指針）。我們之直節(jié)看代碼，理解更加容易。
//e[i] 表示點i的值
//ne[i] 表示節(jié)點i的下一個數(shù)據(jù)的下標
//head 表示棧頭下標
//idx 當前已經存儲到第幾個數(shù)據(jù)了
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個節(jié)點后插入一個元素
void Insert(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//刪除第k個節(jié)點
void remove(int k)
{
ne[k]=ne[ne[k]];
}我們再結合著一個例題看一下。
1.2 數(shù)組模擬實現(xiàn)單鏈表例題
實現(xiàn)一個單鏈表，鏈表初始為空，支持三種操作：
- 向鏈表頭插入一個數(shù)；
- 刪除第kk個插入的數(shù)后面的數(shù)；
- 在第kk個插入的數(shù)后插入一個數(shù)。
現(xiàn)在要對該鏈表進行MM次操作，進行完所有操作后，從頭到尾輸出整個鏈表。
注意:題目中第kk個插入的數(shù)并不是指當前鏈表的第kk個數(shù)。例如操作過程中一共插入了nn個數(shù)，則按照插入的時間順序，這nn個數(shù)依次為：第11個插入的數(shù)，第22個插入的數(shù)，…第nn個插入的數(shù)。
輸入格式：
第一行包含整數(shù)MM，表示操作次數(shù)。
接下來MM行，每行包含一個操作命令，操作命令可能為以下幾種：
H x，表示向鏈表頭插入一個數(shù)xx。
D k，表示刪除第kk個插入的數(shù)后面的數(shù)（當kk為00時，表示刪除頭結點）。
I k x，表示在第kk個插入的數(shù)后面再插入一個數(shù)xx（此操作中kk均大于00）。
輸出格式：
共一行，將整個鏈表從頭到尾輸出。
數(shù)據(jù)范圍：
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] 表示節(jié)點i的下一個數(shù)據(jù)的下標
//head 表示棧頭下標
//idx 當前已經存儲到第幾個數(shù)據(jù)了
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個節(jié)點后插入一個元素
void Insert(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//刪除第k個節(jié)點
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]);
}
}二、數(shù)組模擬實現(xiàn)雙鏈表
2.1 數(shù)組模擬實現(xiàn)雙鏈表解析
數(shù)組模擬實現(xiàn)雙鏈表與數(shù)組模擬實現(xiàn)單鏈表大同小異。數(shù)組模擬實現(xiàn)雙鏈表時我們需要定義三個數(shù)組，一個數(shù)組存放數(shù)據(jù)，一個數(shù)組存放該數(shù)據(jù)左邊數(shù)據(jù)的下標（左指針），一個數(shù)組存放該數(shù)據(jù)右邊數(shù)據(jù)的下標（右指針）。我們直接看代碼：
//e[i] 是表示點i的值
//l[i] 表示節(jié)點i的左邊指針是多少
//r[i] 表示節(jié)點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];
}我們發(fā)現(xiàn)，上面代碼并沒有定義在下標為k的左邊插入一個數(shù)據(jù)，我們只定義了在下標為k的右邊插入一個數(shù)據(jù)。為什么呢？因為可以用在下標為k的右邊插入一個數(shù)據(jù)函數(shù)實現(xiàn)在下標為k的左邊插入一個數(shù)據(jù)。我們只需要在下標為k的左邊的數(shù)據(jù)的右邊插入一個數(shù)據(jù)就相當于實現(xiàn)了在下標為k的左邊插入一個數(shù)據(jù)。如下圖，我們想在下標為3的左邊插入一個數(shù)據(jù)，其實就是在下標為2的右邊插入一個數(shù)據(jù)。
我們結合著一個例題理解一下。
2.2 數(shù)組模擬實現(xiàn)雙鏈表例題
實現(xiàn)一個雙鏈表，雙鏈表初始為空，支持55種操作：
- 在最左側插入一個數(shù)；
- 在最右側插入一個數(shù)；
- 將第kk個插入的數(shù)刪除；
- 在第kk個插入的數(shù)左側插入一個數(shù)；
- 在第kk個插入的數(shù)右側插入一個數(shù)
現(xiàn)在要對該鏈表進行MM次操作，進行完所有操作后，從左到右輸出整個鏈表。
注意:題目中第kk個插入的數(shù)并不是指當前鏈表的第kk個數(shù)。例如操作過程中一共插入了nn個數(shù)，則按照插入的時間順序，這nn個數(shù)依次為：第11個插入的數(shù)，第22個插入的數(shù)，…第nn個插入的數(shù)。
輸入格式：
第一行包含整數(shù)MM，表示操作次數(shù)。
接下來MM行，每行包含一個操作命令，操作命令可能為以下幾種：
-
L x，表示在鏈表的最左端插入數(shù)xx。 -
R x，表示在鏈表的最右端插入數(shù)xx。 -
D k，表示將第kk個插入的數(shù)刪除。 -
IL k x，表示在第kk個插入的數(shù)左側插入一個數(shù)。 -
IR k x，表示在第kk個插入的數(shù)右側插入一個數(shù)。
輸出格式：
共一行，將整個鏈表從左到右輸出。
數(shù)據(jù)范圍：
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] 表示節(jié)點i的左邊指針是多少
//r[i] 表示節(jié)點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;
}三、數(shù)組模擬實現(xiàn)棧
3.1 數(shù)組模擬實現(xiàn)棧解析
我們用數(shù)組模擬實現(xiàn)棧是相對簡單的。我們只要滿足棧的先進后出的性質即可。我們直接看代碼，如下：
//********************* 模擬棧
int stack[N],top=0;
//往棧中插入元素
stack[top++];
//拿出棧頂元素
top--;
//棧頂元素
stack[top-1];
//判斷棧是否為空
if(top>0)
{
printf("notempty\n");
}
else
{
printf("empty\n");
}我們這里給出一個用到單調棧的例題。
3.2 數(shù)組模擬實現(xiàn)棧例題
給定一個長度為NN的整數(shù)數(shù)列，輸出每個數(shù)左邊第一個比它小的數(shù)，如果不存在則輸出?1?1。
輸入格式：
第一行包含整數(shù)NN，表示數(shù)列長度。
第二行包含NN個整數(shù)，表示整數(shù)數(shù)列。
輸出格式：
共一行，包含NN個整數(shù)，其中第ii個數(shù)表示第ii個數(shù)的左邊第一個比它小的數(shù)，如果不存在則輸出?1?1。
數(shù)據(jù)范圍：
1≤N≤1051≤N≤105
1≤數(shù)列中元素≤1091≤數(shù)列中元素≤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;
}四、數(shù)組模擬實現(xiàn)隊列
4.1 數(shù)組模擬實現(xiàn)隊列解析
同樣，我們用數(shù)組模擬實現(xiàn)隊列也是很簡單的。我們只要滿足隊列的先進先出的性質即可。我們直接看代碼，如下：
//********************* 模擬對列 int queue[N],head,tail=0; //插入 queue[tail++]=x; //彈出 head++; //判斷隊列是否為空 if(head<tail) not empty; else empty; //取出對頭，隊尾元素 queue[head]; queue[tail-1];
我們這里給出一道用到隊列的例題，相對來說難一點，我們看一下。
4.2 數(shù)組模擬實現(xiàn)隊列例題
給定一個大小為n≤106n≤106的數(shù)組。
有一個大小為kk的滑動窗口，它從數(shù)組的最左邊移動到最右邊。
你只能在窗口中看到kk個數(shù)字。
每次滑動窗口向右移動一個位置。
以下是一個例子：
該數(shù)組為[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 |
你的任務是確定滑動窗口位于每個位置時，窗口中的最大值和最小值。
輸入格式：
輸入包含兩行。
第一行包含兩個整數(shù)nn和kk，分別代表數(shù)組長度和滑動窗口的長度。
第二行有nn個整數(shù)，代表數(shù)組的具體數(shù)值。
同行數(shù)據(jù)之間用空格隔開。
輸出格式：
輸出包含兩個。
第一行輸出，從左至右，每個位置滑動窗口中的最小值。
第二行輸出，從左至右，每個位置滑動窗口中的最大值。
輸入樣例：
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++;
//對頭確定最小數(shù)
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++;
//對頭確定最大數(shù)
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-03-15 pipe-platform-ops SpringCloudAlibaba日志鏈路追蹤和日志查詢系統(tǒng)
- 2022-05-24 Django框架cookie和session方法及參數(shù)設置_python
- 2022-07-21 查看JVM系統(tǒng)參數(shù)的默認值
- 2022-06-07 FreeRTOS實時操作系統(tǒng)結構示例_操作系統(tǒng)
- 2022-05-27 時序數(shù)據(jù)庫TDengine寫入查詢的問題分析_數(shù)據(jù)庫其它
- 2022-03-31 聊聊Python?String型列表求最值的問題_python
- 2022-05-20 Spring-實現(xiàn)AOP的三種方式演示
- 2022-08-12 利用Python判斷文件的幾種方法及其優(yōu)劣對比_python
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學習環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結構-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速