データ構造とアルゴリズム:線形テーブル詳細解の順序テーブル記憶原理とモデル


(一)線形テーブルの2つの基本モデル
  • シーケンステーブル:要素の順序は連続する記憶領域に配置され、要素間のシーケンス関係は記憶順序によって
  • を自然に表すことができる.
  • チェーンテーブル:要素がリンク構造のブロックに格納順序テーブルとチェーンテーブルの違い:順序テーブルでは要素間の論理アドレスが隣接し、物理順序も隣接するが、チェーンテーブルでは論理アドレスが隣接し、物理アドレスが必ずしも隣接するとは限らない
  • .
    (二)シーケンステーブルの実現
    (1)基本実現方式
          : , , 
         
          : , 
    

    (2)順序表の作成
          , , tuple()
         
    	  , , , 
    

    (2.1)python動的テーブル作成メカニズム
    (3)手順表の変更操作
    (3.1)末尾に要素を追加
        , O(1) , 
    

    (3.2)指定位置挿入要素
     : , , O(n)
    
      : , , O(1) 
    

    (3.4)末尾削除要素
      , , O(1)
    

    (3.5)指定位置削除要素
      :   , O(n)
    
     : , , O(1)
    

    (4)シーケンステーブルの構成
    (4.1)両実現方式
    1.一体構造:表の記憶領域に記録用記憶領域の容量及び記憶された数量を開拓し、静的順序表に使用する
    2.分離構造:記録記憶領域の容量及び記憶された数量の情報を独立した記憶ブロックに入れ、リンクを通して