データ構造とアルゴリズム--02チェーンテーブル-チェーンテーブルコードを簡単に書く方法

データ構造とアルゴリズム--02チェーンテーブル-チェーンテーブルコードを簡単に書く方法
チェーンテーブルを書くのは容易なことではありません.特に、チェーンテーブルの反転、順序付きチェーンテーブルのマージなど、複雑なチェーンテーブル操作があります.コードを書くことができても、エラーが発生しやすい.だから一定量の精力を払うのが前提条件で、またいくつかの必要な技巧を身につける必要があります.
1.ポインタまたは参照の意味を理解する.C言語などの言語にはポインタの概念があり、Java、Pythonなどの他の言語ではポインタの代わりに「参照」が使用される.しかし、本質的には同じで、指すオブジェクトのメモリアドレスを格納します.ポインタの使用とは、ある変数のアドレスをポインタに付与することであるか、ポインタにその変数が格納されたメモリアドレスとして理解され、ポインタによってその変数が見つかる.
チェーンテーブル内のポインタの使用:

p->next=qは、p点を示すnextポインタがqノードのメモリアドレスを格納していることを示す.

p->next=p->next->nextは、pノードのnextポインタがpノードの次のノードのメモリアドレスを格納していることを示す.

2.ポインタの紛失やメモリの漏洩、例えばチェーンテーブルのノードを挿入する操作に注意してください.

p->next = x;
x->next = p->next;

  上記のコードが1行目のコードを完了した後、すでにノードを指している.2行目は、x->nextにxを割り当て、自分が自分を指しているため、チェーンテーブル全体が半分に切断され、ポインタの紛失やメモリの漏洩が発生します.上記の1、2行のコードコードを交換すればいいです.

x->next = p->next;
p->next = x;

チェーンテーブルのノードを削除することは、挿入と同じです. C言語では、メモリ管理はプログラマーが担当し、手動でメモリ領域を解放する必要があります.Javaのような仮想マシンがメモリを自動的に管理するプログラミング言語では、これほど考える必要はありません.
3.歩哨の簡略化による難易度の実現チェーンテーブルの挿入、削除操作について、最初のノードの挿入と最後のノードの削除が必要な場合に特殊な処理を行う.しかし、このようにコードを実現すると煩雑で、簡潔ではありません.では、私たちは「哨兵」を使ってこの問題を解決します.私たちがここで言っている哨兵も「境界問題」を解決し、業務論理に直接参加しない.いつでも、チェーン時計が空いているかどうかにかかわらず、headポインタはずっとこの哨兵の結点を指しています.私たちもこのような哨兵の結点のあるチェーン時計をリーダーチェーン時計と呼んでいます.逆に、哨兵の結点のないチェーン時計を先頭に立たないチェーン時計と呼ぶ.
4.境界条件処理チェーンテーブルの境界条件は以下のとおりです.

チェーンテーブルが空の場合

もしチェーン時計が宝だけで1つのノード

を行うならば

チェーン時計が宝行の2つの接点

であれば

コードロジックは、ヘッダノードとテールノードを処理する場合

である.
5.図を例に挙げて、思考を補助する.複雑なニーズを実現する前に、まず図の形式で論理の流れ全体を整理してから、図を見てコードを書くのは簡単だ.またバグに遭遇した場合、解決も便利になります.
6.多写多練いくつかの一般的なチェーンテーブル操作.

単鎖表反転

チェーンテーブルにおけるリングの検出

2 2つの秩序チェーンテーブルのマージ

チェーンテーブルの最後からn番目のノード

を削除する.

チェーンテーブルの中間ノード

を求めます
以上はチェーンテーブル操作のテクニックをまとめただけで、あとは実戦でコードを叩く練習です.