アルゴリズム - 連続リストと連鎖リスト

なぜリストなのか?

リストは日常生活でよく見かけます:
  • 待合室にいる人。
  • 専門分野に在籍する学生.
  • 車は赤信号を待っています。
  • etc.
目標は、これらの実例を表現し、コンピュータサイエンスで処理することです。

リストの特徴は何ですか?

  • これらは順番に処理されます。
  • 両端で区切られた<ヘッド>とです。
  • 要素の追加や削除が可能です。
  • 動的構造(サイズは異なります).
表現

1 - 連続した表現

リストを配列 T[1..max] で表現できるが、その構造は静的である (そのサイズは宣言で を定義する時点で固定されている) .



リストタイプ: Article
         {
           T:element
            length: 0..lmax
         }

最も重要な操作


      利点

      • Direct access.
      • リストの末尾での削除と挿入.
      • 簡単な実装.

      短所

      • 長さの変更方法を知っておく必要があります。
      • 削除と挿入にはオフセットが含まれます。

      2- 表現 連鎖 

      一連のリンク(ブロック)で構成され、各リンクは2つのフィールドで構成されています:
        <>要素フィールド.
      • 以下を指すアドレス フィールド。

      L: 最初のリンクへのポインタ.
      空のリンクリストは L=null.

      ptr type: link pointer
      リンクタイプ: article
                 {
                    谷;element
                    リンク: ptr
                  }
      chainlisted< type: link/span>
      var L: chainlisted

      最も重要な操作

      <>
      • コース.
        • プロシージャパス(L:list)
          Top
            pp := L.link // ヘッド de L
            pp != null
            faire
              treat(L.T[i])
              pp := *pp.link
            finfaire
           Fin


        利点

        • シーケンシャルパス.
        • リンクを削除しました。
        • リンクの挿入.

        短所

        • 要素への間接的なアクセスでは、i-1リンクを経由する必要があります。ith maillon.
        • リンクのメモリ空間の損失。