要逻辑的《笔记21》

༺ཌༀ⚡☢WA君☢⚡ༀད༻

2025-12-13 11:25:41

发布于：广东

12阅读

0回复

0点赞

链表(数组)

一：输入

1.

$\begin{cases} 0号节点\\ 1号节点\\ 2号节点\\ 3号节点\\ \end{cases}$

2.两个数存储链表的信息

1.date[i]:第i号的值(=3);

2.next[i]:第i号的下一项；

3.head->头节点

二：例子

int date[5]={0,10,20,30,40};
int next[5]={-1,2,4,0,3}；
int head=1;

节点编号	data[i]	next[i]	含义
0	0	-1	值是0，下一个是空
1	10	2	值是10，下一个是2
2	20	4	值是20，下一个是4
3	30	0	值是30，下一个是0
4	40	3	值是40，下一个是3

head:

$1--->2--->4--->3--->0--->NULL;$

$10----20 ----40 ---- 30 ----0---NULL;$

三：题目

#include<bits/stdc++.h>
using namespace std;
int L[10005],R[10005];
bool vis[10086]={0};
void i1(int u, int x) {
    int v=R[u];       
    R[u]=x;           
    L[x]=u;         
    L[v]=x;          
    R[x]=v;          
}
void i2(int u, int x) {
    int v=L[u];
    i1(v,x); 
}
int main() {
    int n,m;
    cin>>n;
    R[0]=n+1;
    L[n+1]=0;
    i1(0,1);
    for (int i=2;i<=n;i++) {
        int k,p;
        cin>>k>>p; 
        if(p==1)i1(k,i); 
        else i2(k,i);
    }
    cin>>m;
    for (int i=0;i<m;i++){
        int x;
        cin>>x;
        vis[x]=1;
    }
    int first=1;
    for (int i=R[0];i!=n+1;i=R[i]) {
        if (vis[i]) continue;
        if (!first) cout<<" ";
        first=0;
        cout<<i;
    }
    return 0;
}