チェーンテーブルの基本概念と操作及び206.Reverse Linked List

参考書目とリンク:
1、基本概念、双方向チェーンテーブルと循環チェーンテーブル
2、チェーンテーブル、ヘッドポインタ、ヘッド接点
3、チェーンテーブルの作成、ノードの追加、削除、チェーンテーブルの逆順序、並べ替えと破棄など
4、チェーンテーブルの基本操作(全)
5、双方向、循環チェーンテーブル操作
チェーンテーブルコンセプト:(listNode*p={int data;node*next})
チェーンテーブルは物理記憶ユニット上の非連続、非順序の記憶構造であり、データ要素の論理順序はチェーンテーブル内のポインタリンク順序によって実現される.チェーンテーブルは、実行時に動的に生成できる一連のノード(チェーンテーブルの各要素をノードと呼ぶ)から構成されます.各ノードには、データ要素を格納するデータドメインと、次のノードアドレスを格納するポインタドメインの2つのセクションがあります.線形テーブルの順序構造に比べて、操作が複雑です.順番に格納する必要がないため、チェーンテーブルは挿入時にO(1)の複雑さに達し、別の線形テーブルの順序テーブルよりもずっと速いが、1つのノードを検索したり、特定の番号のノードにアクセスしたりするにはO(n)の時間が必要であり、線形テーブルと順序テーブルの対応する時間複雑さはそれぞれO(logn)とO(1)である.
チェーンテーブル構造を使用すると、配列チェーンテーブルが予めデータサイズを知る必要があるという欠点を克服することができ、チェーンテーブル構造はコンピュータのメモリ空間を十分に利用し、柔軟なメモリ動態管理を実現することができる.しかし,チェーンテーブルは配列ランダム読み出しの利点を失い,同時にチェーンテーブルはノードのポインタドメインを増加させるため,空間オーバーヘッドが大きい.チェーンテーブルの最も明らかな利点は、従来の配列が関連項目を配列する方法が、メモリまたはディスク上のこれらのデータ項目とは順序が異なり、データのアクセスが異なる配列順序で変換されることが多いことです.チェーンテーブルでは、テーブル上の任意の場所のノードの挿入と削除は許可されますが、ランダムアクセスは許可されません.チェーンテーブルには、一方向チェーンテーブル、双方向チェーンテーブル、ループチェーンテーブルなど、さまざまなタイプがあります.チェーンテーブルは、複数のプログラミング言語で実現できます.LispやSchemeのような言語の組み込みデータ型には,チェーンテーブルへのアクセスと操作が含まれている.C,C+,Javaなどのプログラム言語またはオブジェクト向け言語は,可変ツールによってチェーンテーブルを生成する.
ヘッドポインタ、ヘッドノード、ヘッドノード、および単一チェーンテーブルにヘッドノードを設定する役割は何ですか?

                      a1   。      ，                  ，     ，                   ，              ，     、                   。              （           ）   。         ，           ，       。               。         、            。       ，                   。
   headàdatalink            ，
              （           ）   ；
                     ；                （     ？          ！）
                       a1   。

チェーンテーブルのメリットとデメリット:

  :1:              ,       .
        2:                 !       
  :1:         ,  :   100   ,        
         next 99        
         2:         ,        

             ,  ，       。

チェーンテーブル問題コード実装キー:
1、戻り値タイプはノードタイプであることが多い
2、画図方法で構想を整理する
3、境界条件についての厳格な要求(空のチェーンテーブル、1つの要素のチェーンテーブルなど)
チェーンテーブルコードテクニックのまとめ:
1.一般的に、ヘッダノード、現在のノード、および新しいノードを表す2つまたは3つのノードを定義します.または前のノード、現在のノード、後のノードなど
2、文の理解:
                     p->next=q;//ノードpにおけるポインタアドレスq、すなわちpはqを指し、pの指向を変更するために定義される.
                     p=q->next;//pに値を割り当てる、すなわちqの次のアドレスであり、チェーンテーブルを拡張するために使用される.
                     p=q;//ノードqをノードpに付与する.すなわち、現在のノード位置pが変化し、新しいノードの位置qとなる.
                     p->next=q->next;//qの次のノードをpの後ろに接続する
例:206.Reverse Linked List(チェーンテーブル反転)

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        ListNode *prev = NULL, *cur=head, *tmp;//    ，   ，   ，     
        while(cur){
            tmp = cur->next;//       
            cur->next = prev;//  cur     
            prev = cur;//cur        prev，       
        cur = tmp;//tmp        cur ，       
        }//  cur  ，  prev           ，            。
       return prev;//        ，         
    }
};