ああ、私たちは C++ の「リンクされたリストのチュートリアル」に夢中になっていますが、前回あなたが尋ねたときは非現実的だと言いました。
でも多分私はそれを書く時間があります。
私は最初に自分でお茶を作り、これを少しずつ、一度に 1 つずつ投稿します。
基本的な単方向リスト。
基本的な単一リンク リストはノードで構成され、各ノードにはリスト内の次のノードへのポインタが含まれます。たとえば、 と呼ばれnextます。慣例によりnext、 ==0 はリストの終わりを示します。それでは、このような単純なリストを作成し、それをトラバースして (ここではコンテンツを表示するだけです)、ノードの割り当てを解除してクリーンアップしましょう。
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* first = 0;
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
node->next = first; // After this `node` points to the new first node.
first = node; // Now `first` also points to the new first node.
}
// Display it
for( node_t* p = first; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
最後のクリーンアップでは、削除されたノードにアクセスしないように、正しい順序で作業を行うことが重要です。削除されたノードへのアクセスが機能する場合があります。しかし、その後、マーフィーの法則により、物事が機能することが絶対的に最も重要な時点で失敗します。
出力：
0 114 101 119 111 108 102 110 111 111 109
これらは、文字列の末尾のゼロを含む ASCII 文字コードです。
数字の順番に注意！:-)
単方向リストへの挿入。
配列を直接使用する場合と比較して、連結リストの主な利点は、新しいノードの挿入に一定の時間がかかることです。配列を直接使用する場合、新しい項目を挿入すると、その項目の後 (または前) にすべての項目を移動する必要があり、これには配列のサイズに比例した時間がかかります。ただし、(1) 挿入ポイントを見つける時間は、通常、リスト サイズの線形に強制されますが、配列の場合は対数になる可能性があること、および (2) 「挿入ギャップ」または「カーソル ギャップ」と呼ばれる手法を使用することに注意してください。 」 アイテムの挿入は、配列に対しても一定の時間にすることができます (若干のコストがかかります)。
昇順でソートされた位置に数値を挿入するには、基本リストを使用して、挿入ポイントの前にノードへのポインターが必要です。これにより、そのノードをnext更新して新しいノードを指すことができます。
基本リストでは、最初のノードの前にそのようなノードがないため、以下に示すように、リストの先頭への挿入は醜い特殊なケースになります。
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* first = 0;
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
// Find the insertion point.
node_t* p = first;
node_t* p_node_before = 0;
while( p != 0 && p->value < ch )
{
p_node_before = p;
p = p->next;
}
if( p_node_before == 0 )
{
// Insert at start of list, just like in the first program.
node->next = first; // After this `node` points to the new first node.
first = node; // Now `first` also points to the new first node.
}
else
{
// Insert within the list or at the end of the list.
node->next = p_node_before->next;
p_node_before->next = node;
}
}
// Display it
for( node_t* p = first; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
出力：
0 101 102 108 109 110 111 111 111 114 119
挿入場所の検索により、各挿入には平均してリストの最終的な長さに比例する時間がかかるため、合計でこれは二次時間 O(n 2 ) になることに注意してください。単純な挿入ソートです。バグが発生していないことを願っています。:-)
独創的なポインター ツー ポインター。
next基本的なリストの先頭に挿入する際の混乱を減らす 1 つの方法は、挿入ポイントの前にあるノードのフィールドへのアクセスのみが必要であることに注意することです。
挿入ポイントの前の完全なノードにアクセスする必要はありません。
したがって、ポインターへのnextポインターだけで間に合わせることができます。つまり、ポインタへのポインタ。そして、リストの先頭では、ポインター変数は、その前のノードのフィールドであるかfirstのようにうまく機能するため、最初はポインターへのポインターがポインターを指すだけで(エヘム)、移動できます。次のように、ポインタで：nextfirstnext
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* first = 0;
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
// Find the insertion point.
node_t** p_next_before = &first;
while( *p_next_before != 0 )
{
node_t* const next_node = *p_next_before;
if( next_node->value >= ch )
{
break;
}
p_next_before = &next_node->next;
}
// Insert at start of list, just like in the first program.
node->next = *p_next_before; // After this `node` points to the new first node.
*p_next_before = node; // Now ... also points to the new first node.
}
// Display it
for( node_t* p = first; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
出力はまだ
0 101 102 108 109 110 111 111 111 114 119
あるべきように。
while最初は、かなり長い継続条件をループ ヘッドに直接記述して、そのコードを書きました。しかし、目に見えるものすべてに名前を付ける必要があるという規則に従って、その一部をループ内に移動し、次にbreakステートメントを付けました。breakそれが声明の理由です：名前をサポートするためnext_node。
C++ では、ポインターからポインターへのポインターは、ポインターへの参照として表されることがあります。たとえば、基本リストからノードのリンクを解除する関数は、C スタイルのポインタからポインタへの引数ではなく、参照からポインタへの引数を取る場合があります。該当する場合は、少しきれいだと思います。
ヘッダー ノードの使用。
ポインタ ツー ポインタに代わる方法は、最初の実ノードの前にダミー ノードを導入することです。その場合、空のリストでも 1 つの物理ノード、つまりダミー ノードがあります。ダミー ノードは通常、ヘッダー ノードと呼ばれます。
コンパイラが機械語コードへの変換と最適化を完了すると、ヘッダー ノードを使用するコードは、ポインターからポインターへの手法を使用するコードと同じになる場合があります。単一のポインター変数よりも余裕があります。しかし違いは、コードについてどう考えるか、コードをどのように理解するかです。概念的には、ヘッダー ノードを持つことは、ポインター ツー ポインター手法を使用することとは大きく異なります。たとえば、リスト構造を描画すると、ヘッダー ノードのあるリストは、そのようなノードのないリストとは明らかに異なります。
とにかく、コード：
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* header_node = new node_t();
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
// Find the insertion point.
node_t* p_before = header_node;
while( p_before->next != 0 && p_before->next->value < ch )
{
p_before = p_before->next;
}
// Insert at start of list, just like in the first program.
node->next = p_before->next; // After this `node` points to the new first node.
p_before->next = node; // Now ... also points to the new first node.
}
// Display it
for( node_t* p = header_node->next; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
auto& first = header_node; // Just a renaming for clarity.
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
そして、以前と同様に、出力はまだです
0 101 102 108 109 110 111 111 111 114 119
あるべきように。
