データ構造——単鎖表(C++版)

アナログチェーンテーブルは2つの配列でダイナミックチェーンテーブルをシミュレートし、C++のダイナミックメモリ申請が遅すぎるため、静的配列でダイナミックチェーンテーブルをシミュレートし、アルゴリズム効率を向上させる.

の基本構想は動的チェーンテーブルの動作原理と手順とほぼ同じであるが,ノードの代わりに配列を用い,ポインタ

の代わりに変数を用いるにすぎない.

テンプレート

// head     ，e[]      （    ），ne[]     next  （    ），idx           
int head, e[N], ne[N], idx;

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

//          a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

//       ，         
void remove()
{
    head = ne[head];
}

例題は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 1≦M≦100000すべての操作が合法であることを保証する.入力サンプル:10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 I 3 4 D 6出力サンプル:6 4 6 6 6 5

#include

using namespace std;

const int N = 100010;

int m;
int n[N], ne[N], idx, head;

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

//     
void add_to_head(int x)
{
	n[idx] = x; ne[idx] = head; head = idx ++;
}

//  k          
void add(int k, int x)
{
	n[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx ++;
}

//   k         
void remove_1(int k)
{
	ne[k] = ne[ne[k]];
}

int main()
{
	cin >> m;

	init();
	
	int k, x;
	char op;
	
	while(m--)
	{
		cin >> op;

		if(op == 'H')
		{
			cin >> x;
			add_to_head(x);
		}
		else if(op == 'D')
		{
			cin >> k ;
			if(!k) head = ne[head];
			remove_1(k - 1);	//    ， k         k-1
		}
		else 
		{
			cin >> k >> x;
			add(k - 1, x);
		}
	}
					
 	for(int i = head; i != -1; i = ne[i]) cout << n[i] << ' ';

	return 0;
}	 	
		

[^1]注:この文書のコードとテンプレートはwww.acwing.から来ています.com