前引

我們在數(shù)據(jù)結(jié)構(gòu)中都學(xué)到過單鏈表、雙鏈表、棧和隊(duì)列，當(dāng)我們實(shí)現(xiàn)的時(shí)候時(shí)使用結(jié)構(gòu)體指針實(shí)現(xiàn)的。定義一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體中存儲(chǔ)指針變量和存放數(shù)值的變量。當(dāng)然，C++的STL庫中已經(jīng)有實(shí)現(xiàn)好的棧和隊(duì)列，我們可以直接用。但是在做算法題時(shí)，有時(shí)候我們會(huì)發(fā)現(xiàn)超出時(shí)間限制。原因是我們用STL庫中的棧和隊(duì)列容器時(shí)，效率相對(duì)來說較慢。我們這時(shí)就引出用數(shù)組模擬實(shí)現(xiàn)棧和隊(duì)列。用數(shù)組模擬實(shí)現(xiàn)的使用起來效率更高、更方便。當(dāng)然，我們也會(huì)講到用數(shù)組模擬實(shí)現(xiàn)單鏈表和雙鏈表。

一、數(shù)組模擬實(shí)現(xiàn)單鏈表

1.1 數(shù)組模擬的單鏈表解析

用結(jié)構(gòu)體實(shí)現(xiàn)單鏈表時(shí)，我們會(huì)在結(jié)構(gòu)體中定義一個(gè)存放數(shù)據(jù)的變量和一個(gè)存放下一個(gè)數(shù)據(jù)地址的指針。那我們用數(shù)組模擬實(shí)現(xiàn)怎么找到下一個(gè)數(shù)據(jù)的呢？用數(shù)組實(shí)現(xiàn)單鏈表，我們定義兩個(gè)數(shù)組即可。一個(gè)數(shù)組存放數(shù)據(jù)，另一個(gè)數(shù)組存放下一數(shù)據(jù)的下標(biāo)（充當(dāng)結(jié)構(gòu)體中的指針）。我們之直節(jié)看代碼，理解更加容易。

//e[i] 表示點(diǎn)i的值
//ne[i] 表示節(jié)點(diǎn)i的下一個(gè)數(shù)據(jù)的下標(biāo)
//head 表示棧頭下標(biāo)
//idx 當(dāng)前已經(jīng)存儲(chǔ)到第幾個(gè)數(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個(gè)節(jié)點(diǎn)后插入一個(gè)元素
 
void Insert(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
//刪除第k個(gè)節(jié)點(diǎn)
void remove(int k)
{
    ne[k]=ne[ne[k]];
}

我們再結(jié)合著一個(gè)例題看一下。

1.2 數(shù)組模擬實(shí)現(xiàn)單鏈表例題

實(shí)現(xiàn)一個(gè)單鏈表，鏈表初始為空，支持三種操作：

• 向鏈表頭插入一個(gè)數(shù)；
• 刪除第kk個(gè)插入的數(shù)后面的數(shù)；
• 在第kk個(gè)插入的數(shù)后插入一個(gè)數(shù)。

現(xiàn)在要對(duì)該鏈表進(jìn)行MM次操作，進(jìn)行完所有操作后，從頭到尾輸出整個(gè)鏈表。

注意:題目中第kk個(gè)插入的數(shù)并不是指當(dāng)前鏈表的第kk個(gè)數(shù)。例如操作過程中一共插入了nn個(gè)數(shù)，則按照插入的時(shí)間順序，這nn個(gè)數(shù)依次為：第11個(gè)插入的數(shù)，第22個(gè)插入的數(shù)，…第nn個(gè)插入的數(shù)。

輸入格式：

第一行包含整數(shù)MM，表示操作次數(shù)。

接下來MM行，每行包含一個(gè)操作命令，操作命令可能為以下幾種：

H x，表示向鏈表頭插入一個(gè)數(shù)xx。

D k，表示刪除第kk個(gè)插入的數(shù)后面的數(shù)（當(dāng)kk為00時(shí)，表示刪除頭結(jié)點(diǎn)）。

I k x，表示在第kk個(gè)插入的數(shù)后面再插入一個(gè)數(shù)xx（此操作中kk均大于00）。

輸出格式：

共一行，將整個(gè)鏈表從頭到尾輸出。

數(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] 表示點(diǎn)i的值
//ne[i] 表示節(jié)點(diǎn)i的下一個(gè)數(shù)據(jù)的下標(biāo)
//head 表示棧頭下標(biāo)
//idx 當(dāng)前已經(jīng)存儲(chǔ)到第幾個(gè)數(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個(gè)節(jié)點(diǎn)后插入一個(gè)元素
void Insert(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
//刪除第k個(gè)節(jié)點(diǎn)
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ù)組模擬實(shí)現(xiàn)雙鏈表

2.1 數(shù)組模擬實(shí)現(xiàn)雙鏈表解析

數(shù)組模擬實(shí)現(xiàn)雙鏈表與數(shù)組模擬實(shí)現(xiàn)單鏈表大同小異。數(shù)組模擬實(shí)現(xiàn)雙鏈表時(shí)我們需要定義三個(gè)數(shù)組，一個(gè)數(shù)組存放數(shù)據(jù)，一個(gè)數(shù)組存放該數(shù)據(jù)左邊數(shù)據(jù)的下標(biāo)（左指針），一個(gè)數(shù)組存放該數(shù)據(jù)右邊數(shù)據(jù)的下標(biāo)（右指針）。我們直接看代碼：

//e[i] 是表示點(diǎn)i的值
//l[i] 表示節(jié)點(diǎn)i的左邊指針是多少
//r[i] 表示節(jié)點(diǎn)i的右邊指針是多少
//idx 存儲(chǔ)當(dāng)前已經(jīng)用到那個(gè)點(diǎn)了
int e[N],l[N],r[N],idx;
//初始化
void Init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}
//在下標(biāo)為k的右邊插入一個(gè)元素
void Insert(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}
//刪除下標(biāo)為k的元素
void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

我們發(fā)現(xiàn)，上面代碼并沒有定義在下標(biāo)為k的左邊插入一個(gè)數(shù)據(jù)，我們只定義了在下標(biāo)為k的右邊插入一個(gè)數(shù)據(jù)。為什么呢？因?yàn)榭梢杂迷谙聵?biāo)為k的右邊插入一個(gè)數(shù)據(jù)函數(shù)實(shí)現(xiàn)在下標(biāo)為k的左邊插入一個(gè)數(shù)據(jù)。我們只需要在下標(biāo)為k的左邊的數(shù)據(jù)的右邊插入一個(gè)數(shù)據(jù)就相當(dāng)于實(shí)現(xiàn)了在下標(biāo)為k的左邊插入一個(gè)數(shù)據(jù)。如下圖，我們想在下標(biāo)為3的左邊插入一個(gè)數(shù)據(jù)，其實(shí)就是在下標(biāo)為2的右邊插入一個(gè)數(shù)據(jù)。

我們結(jié)合著一個(gè)例題理解一下。

2.2 數(shù)組模擬實(shí)現(xiàn)雙鏈表例題

實(shí)現(xiàn)一個(gè)雙鏈表，雙鏈表初始為空，支持55種操作：

• 在最左側(cè)插入一個(gè)數(shù)；
• 在最右側(cè)插入一個(gè)數(shù)；
• 將第kk個(gè)插入的數(shù)刪除；
• 在第kk個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)；
• 在第kk個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)

現(xiàn)在要對(duì)該鏈表進(jìn)行MM次操作，進(jìn)行完所有操作后，從左到右輸出整個(gè)鏈表。

注意:題目中第kk個(gè)插入的數(shù)并不是指當(dāng)前鏈表的第kk個(gè)數(shù)。例如操作過程中一共插入了nn個(gè)數(shù)，則按照插入的時(shí)間順序，這nn個(gè)數(shù)依次為：第11個(gè)插入的數(shù)，第22個(gè)插入的數(shù)，…第nn個(gè)插入的數(shù)。

輸入格式：

第一行包含整數(shù)MM，表示操作次數(shù)。

接下來MM行，每行包含一個(gè)操作命令，操作命令可能為以下幾種：

• L x，表示在鏈表的最左端插入數(shù)xx。
• R x，表示在鏈表的最右端插入數(shù)xx。
• D k，表示將第kk個(gè)插入的數(shù)刪除。
• IL k x，表示在第kk個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)。
• IR k x，表示在第kk個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)。

輸出格式：

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

數(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] 是表示點(diǎn)i的值
//l[i] 表示節(jié)點(diǎn)i的左邊指針是多少
//r[i] 表示節(jié)點(diǎn)i的右邊指針是多少
//idx 存儲(chǔ)當(dāng)前已經(jīng)用到那個(gè)點(diǎn)了
int e[N],l[N],r[N],idx;
//初始化
void Init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}
//在下標(biāo)為k的右邊插入一個(gè)元素
void Insert(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}
//刪除下標(biāo)為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ù)組模擬實(shí)現(xiàn)棧

3.1 數(shù)組模擬實(shí)現(xiàn)棧解析

我們用數(shù)組模擬實(shí)現(xiàn)棧是相對(duì)簡單的。我們只要滿足棧的先進(jìn)后出的性質(zhì)即可。我們直接看代碼，如下：

//********************* 模擬棧
int stack[N],top=0;
//往棧中插入元素
stack[top++];
//拿出棧頂元素
top--;
//棧頂元素
stack[top-1];
//判斷棧是否為空
if(top>0)
{
    printf("notempty\n");
}
else
{
    printf("empty\n");
}

我們這里給出一個(gè)用到單調(diào)棧的例題。

3.2 數(shù)組模擬實(shí)現(xiàn)棧例題

給定一個(gè)長度為NN的整數(shù)數(shù)列，輸出每個(gè)數(shù)左邊第一個(gè)比它小的數(shù)，如果不存在則輸出−1−1。

輸入格式：

第一行包含整數(shù)NN，表示數(shù)列長度。

第二行包含NN個(gè)整數(shù)，表示整數(shù)數(shù)列。

輸出格式：

共一行，包含NN個(gè)整數(shù)，其中第ii個(gè)數(shù)表示第ii個(gè)數(shù)的左邊第一個(gè)比它小的數(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ù)組模擬實(shí)現(xiàn)隊(duì)列

4.1 數(shù)組模擬實(shí)現(xiàn)隊(duì)列解析

同樣，我們用數(shù)組模擬實(shí)現(xiàn)隊(duì)列也是很簡單的。我們只要滿足隊(duì)列的先進(jìn)先出的性質(zhì)即可。我們直接看代碼，如下：

//********************* 模擬對(duì)列
int queue[N],head,tail=0;
//插入
queue[tail++]=x;
//彈出
head++;
//判斷隊(duì)列是否為空
if(head<tail) not empty;
else empty;
//取出對(duì)頭，隊(duì)尾元素
queue[head];
queue[tail-1];

我們這里給出一道用到隊(duì)列的例題，相對(duì)來說難一點(diǎn)，我們看一下。

4.2 數(shù)組模擬實(shí)現(xiàn)隊(duì)列例題

給定一個(gè)大小為n≤106n≤106的數(shù)組。

有一個(gè)大小為kk的滑動(dòng)窗口，它從數(shù)組的最左邊移動(dòng)到最右邊。

你只能在窗口中看到kk個(gè)數(shù)字。

每次滑動(dòng)窗口向右移動(dòng)一個(gè)位置。

以下是一個(gè)例子：

該數(shù)組為[1 3 -1 -3 5 3 6 7]，kk為33。

你的任務(wù)是確定滑動(dòng)窗口位于每個(gè)位置時(shí)，窗口中的最大值和最小值。

輸入格式：

輸入包含兩行。

第一行包含兩個(gè)整數(shù)nn和kk，分別代表數(shù)組長度和滑動(dòng)窗口的長度。

第二行有nn個(gè)整數(shù)，代表數(shù)組的具體數(shù)值。

同行數(shù)據(jù)之間用空格隔開。

輸出格式：

輸出包含兩個(gè)。

第一行輸出，從左至右，每個(gè)位置滑動(dòng)窗口中的最小值。

第二行輸出，從左至右，每個(gè)位置滑動(dòng)窗口中的最大值。

輸入樣例：

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++)
    {
        //判斷對(duì)頭是否已經(jīng)劃出窗口
        if(head<tail&&i-k+1>q[head])
            head++;
        //對(duì)頭確定最小數(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++)
    {
        //判斷對(duì)頭是否已經(jīng)劃出窗口
        if(head<tail&&i-k+1>q[head])
            head++;
        //對(duì)頭確定最大數(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ù)組模擬之單鏈表與雙鏈表和棧和隊(duì)列的實(shí)現(xiàn)過程的文章就介紹到這了,更多相關(guān)C++數(shù)組模擬內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論