C++數(shù)組模擬之單鏈表與雙鏈表和棧和隊列的實現(xiàn)過程
前引
我們在數(shù)據(jù)結(jié)構(gòu)中都學到過單鏈表、雙鏈表、棧和隊列，當我們實現(xiàn)的時候時使用結(jié)構(gòu)體指針實現(xiàn)的。定義一個結(jié)構(gòu)體，結(jié)構(gòu)體中存儲指針變量和存放數(shù)值的變量。當然，C++的STL庫中已經(jīng)有實現(xiàn)好的棧和隊列，我們可以直接用。但是在做算法題時，有時候我們會發(fā)現(xiàn)超出時間限制。原因是我們用STL庫中的棧和隊列容器時，效率相對來說較慢。我們這時就引出用數(shù)組模擬實現(xiàn)棧和隊列。用數(shù)組模擬實現(xiàn)的使用起來效率更高、更方便。當然，我們也會講到用數(shù)組模擬實現(xiàn)單鏈表和雙鏈表。
一、數(shù)組模擬實現(xiàn)單鏈表
1.1 數(shù)組模擬的單鏈表解析
用結(jié)構(gòu)體實現(xiàn)單鏈表時，我們會在結(jié)構(gòu)體中定義一個存放數(shù)據(jù)的變量和一個存放下一個數(shù)據(jù)地址的指針。那我們用數(shù)組模擬實現(xiàn)怎么找到下一個數(shù)據(jù)的呢？用數(shù)組實現(xiàn)單鏈表，我們定義兩個數(shù)組即可。一個數(shù)組存放數(shù)據(jù)，另一個數(shù)組存放下一數(shù)據(jù)的下標（充當結(jié)構(gòu)體中的指針）。我們之直節(jié)看代碼，理解更加容易。
//e[i] 表示點i的值
//ne[i] 表示節(jié)點i的下一個數(shù)據(jù)的下標
//head 表示棧頭下標
//idx 當前已經(jīng)存儲到第幾個數(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]];
}我們再結(jié)合著一個例題看一下。
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時，表示刪除頭結(jié)點）。
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 當前已經(jīng)存儲到第幾個數(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 存儲當前已經(jīng)用到那個點了
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ù)。
我們結(jié)合著一個例題理解一下。
2.2 數(shù)組模擬實現(xiàn)雙鏈表例題
實現(xiàn)一個雙鏈表，雙鏈表初始為空，支持55種操作：
- 在最左側(cè)插入一個數(shù)；
- 在最右側(cè)插入一個數(shù)；
- 將第kk個插入的數(shù)刪除；
- 在第kk個插入的數(shù)左側(cè)插入一個數(shù)；
- 在第kk個插入的數(shù)右側(cè)插入一個數(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ù)左側(cè)插入一個數(shù)。IR k x，表示在第kk個插入的數(shù)右側(cè)插入一個數(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 存儲當前已經(jīng)用到那個點了
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)棧是相對簡單的。我們只要滿足棧的先進后出的性質(zhì)即可。我們直接看代碼，如下：
//********************* 模擬棧
int stack[N],top=0;
//往棧中插入元素
stack[top++];
//拿出棧頂元素
top--;
//棧頂元素
stack[top-1];
//判斷棧是否為空
if(top>0)
{
printf("notempty\n");
}
else
{
printf("empty\n");
}我們這里給出一個用到單調(diào)棧的例題。
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)隊列也是很簡單的。我們只要滿足隊列的先進先出的性質(zhì)即可。我們直接看代碼，如下：
//********************* 模擬對列 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++)
{
//判斷對頭是否已經(jīng)劃出窗口
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++)
{
//判斷對頭是否已經(jīng)劃出窗口
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;
}到此這篇關(guān)于C++數(shù)組模擬之單鏈表與雙鏈表和棧和隊列的實現(xiàn)過程的文章就介紹到這了,更多相關(guān)C++數(shù)組模擬內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Visual?C++?6.0添加一個對話框的實現(xiàn)步驟
VC6.0是微軟公司推出的一款集成開發(fā)環(huán)境,本文主要介紹了Visual?C++?6.0添加一個對話框的實現(xiàn)步驟,具有一定的參考價值,感興趣的可以了解一下2024-06-06
這篇文章主要介紹了C++與C的差異分析,非常實用,需要的朋友可以參考下2014-08-08
本篇文章是對C++中的Data Member內(nèi)存布局進行了詳細的分析介紹，需要的朋友參考下2013-07-07
這篇文章主要介紹了Clion下vcpkg的使用詳解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
單元測試（unit testing），是指對軟件中的最小可測試單元進行檢查和驗證。這篇文章主要為大家介紹了C語言實現(xiàn)單元測試的方法，需要的可以參考一下2022-09-09
這篇文章主要介紹了深入解析C++編程中類的封裝特性,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
C/C++?Qt?StringListModel?字符串列表映射組件詳解
StringListModel?字符串列表映射組件，該組件用于處理字符串與列表框組件中數(shù)據(jù)的轉(zhuǎn)換，通常該組件會配合ListView組件一起使用，本文給大家介紹了C/C++?Qt?StringListModel?字符串列表映射組件的相關(guān)知識，感興趣的朋友跟隨小編一起看看吧2021-12-12
這篇文章主要介紹了C++類型兼容規(guī)則詳情，共有繼承時，任何需要父類對象的地方，都能使用子類對象“替代”，這就是類型兼容規(guī)則，下面一起來了解文章相關(guān)內(nèi)容吧2022-03-03
這篇文章主要為大家詳細介紹了C語言的快排函數(shù)用法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-08-08
C語言宏定義結(jié)合全局變量的方法實現(xiàn)單片機串口透傳模式
今天小編就為大家分享一篇關(guān)于C語言宏定義結(jié)合全局變量的方法實現(xiàn)單片機串口透傳模式，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12