【アルゴリズム基礎課】単一チェーンテーブル(静的チェーンテーブル)

文書ディレクトリ

1.思想

2.例題

3.コードテンプレート

4.文法知識補足

1.思想

静的チェーンテーブル、すなわち配列を用いて従来のポインタを用いた単一チェーンテーブルをシミュレートし、利点は速度が速いことである.単一チェーンテーブルに何千もの要素がある場合、「new」という操作だけでタイムアウトする可能性があります.

配列を使用してチェーンテーブルをシミュレートします.4要素があります.具体的な説明はコードと組み合わせて注釈を見ることができます.

e[i]

ne[i]

head

idx

2.例題
1つの単一チェーンテーブルを実現し、チェーンテーブルの初期が空で、3つの操作をサポートする:(1)チェーンテーブルのヘッダに1つの数を挿入する;(2)k番目に挿入された数の後の数を削除する.(3)k番目の挿入数の後に1つの数を挿入する
このチェーンテーブルをM回操作し、すべての操作を行った後、チェーンテーブル全体を最初から最後まで出力します.
注意:タイトルのk番目の挿入数は、現在のチェーンテーブルのk番目の数ではありません.例えば、操作中に合計n個の数が挿入されると、挿入された時間順に、このn個の数は、1番目の挿入数、2番目の挿入数、…n番目の挿入数の順になる.
入力フォーマットの最初の行には、操作回数を示す整数Mが含まれます.次にM行、各行に1つの操作コマンドが含まれ、操作コマンドは以下のいくつかである:(1)「H x」であり、チェーンヘッダーに1つの数xを挿入することを示す.(2)「D k」は、k番目に入力された数を削除した後の数を示す(kが0の場合、削除ヘッダノードを示す).(3)「Ik x」は、k番目に入力された数の後に1つの数xが挿入されていることを示す(この動作ではkはいずれも0より大きい).
出力フォーマットは1行で、チェーンテーブル全体を最初から最後まで出力します.
データ範囲1≦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
3.コードテンプレート

#include
using namespace std;

const int N=1e6+10;
int m;
int e[N],//    i  
    ne[N],//    i next     
    head,//          
    idx;//            

void init(){
    idx=0;
    head=-1;
}

void addToHead(int x){
    e[idx]=x;
    ne[idx]=head;//          
    head=idx;//            
    idx++;
}
void remove(int k){
    //     
    if(k==0){
        head=ne[head];
    }else{
    //    k      k-1   
        ne[k-1]=ne[ne[k-1]];
    }
}
void add(int k,int x){
    //    k      k-1   
    e[idx]=x;
    ne[idx]=ne[k-1];
    ne[k-1]=idx;
    idx++;
}

void print(){
    if(head!=-1){
        for(int i=head;i!=-1;i=ne[i]){
            printf("%d ",e[i]);
        }
    }else printf("    ");
    puts("");
}
int main(){
    scanf("%d",&m);
    init();

    while(m--){
        char c;
        cin>>c;
        if(c=='H'){
            int x;scanf("%d",&x);
            addToHead(x);
        }else if(c=='D'){
            int k;scanf("%d",&k);
            remove(k);
        }else if(c=='I'){
            int k,x;scanf("%d%d",&k,&x);
            add(k,x);
        }
    }

    //    ？
    print();
    return 0;
}

4.文法知識の補足
最初に読み込んだ文字を書くときはscanf("%c",&c);を使いますが、これで読み込んだ文字にはスペース、改行、数字が含まれます.文字を読み込むときにcinを使うか、スペースや改行を考慮してください.例えば、scanf("%d
",&m);