片方向リスト実装編《連結リスト》

連結リストメニュー【片方向リスト実装編 step 1 〜 全9問】

問題【連結リストメニュー問題一覧】
Task
 値を保存する配列とポインタを格納する配列を用意してポインタの指し示す値を表示してね。

【片方向リスト実装編 全9問のまとめ】

reader.on('close', () => {
   const Max_Size = 1024;  // 配列の要素数
   let start_ptr = 0;
   const end_ptr = Max_Size - 1;  // 1023
   const Value = new Array(Max_Size);  // 値を保持
   const Next_Ptr = new Array(Max_Size);  // 次のノード(節)のindexを保持
   Value[start_ptr] = -1;  // Value の最初の値を初期化
   Value[end_ptr] = -1;  // Value の最後の値を初期化
   Next_Ptr[start_ptr] = end_ptr;  // Next_Ptr の最初の値を初期化
   Next_Ptr[end_ptr] = -1;  // Next_Ptr の最後の値を初期化
   let empty_min_idx = 1;  // Value に要素が入っていない最も小さいindex(1で初期化)
   let back_ptr = 0;  // empty_min_idx の左隣のindex 
   function push_back(val) {  // 要素を末尾に追加
      const new_ptr = empty_min_idx;  // val を追加する場所
      Value[new_ptr] = val;  // Value に val を追加
      Next_Ptr[new_ptr] = end_ptr;  // new_ptr → end_ptr
      Next_Ptr[back_ptr] = new_ptr;  // back_ptr → new_ptr
      empty_min_idx++;  // empty_min_idx を更新
      back_ptr = new_ptr;  // back_ptr を更新
   }
   function push_front(val) {  // 要素を先頭へ追加
      const new_ptr = empty_min_idx;  // val を追加する場所
      Value[new_ptr] = val;  // Value に val を追加
      Next_Ptr[new_ptr] = Next_Ptr[start_ptr];  // new_ptr → start_ptr の次
      Next_Ptr[start_ptr] = new_ptr;  // start_ptr → new_ptr
      empty_min_idx++;  // empty_min_idx を更新
   }

   function Remove_from_end() {  // 末尾の要素を表示しない
      back_ptr--;  // 最後の要素 → 最後の要素の一つ前の要素 ↓
      Next_Ptr[back_ptr] = end_ptr;  // → end_ptr
   }

   function iRemove_from_front() {  // 先頭の要素を表示しない
      start_ptr++;
   }

   function insert(pos, val) {  // pos に val を 割り込ませる
      const new_ptr = empty_min_idx;  // Value に val を保存する場所
      Value[new_ptr] = val;  // Value に val を追加
      let current_ptr = start_ptr;  // 現在のノード
      for (let i = 0; i < pos; i++) {  // i は表示済みの値の数
         if (current_ptr === end_ptr) {  // 割り込ませる場所が末尾の場合
            break;  // 変更なし
         }         
         if (i === pos - 1) {  // 表示済みの値の数が pos の直前になれば
            [Next_Ptr[current_ptr],Next_Ptr[new_ptr]]= [new_ptr, Next_Ptr[current_ptr]];
          // 今のノード → 新しく追加したノード → 今のノードの次の場所
            break; 
         }
        current_ptr = Next_Ptr[current_ptr];  // 次のノードへ
      }
      empty_min_idx++;
   }

   function iRemove_from_pos(pos) {  // pos にある要素を除いて表示
      current_ptr = pos - 1;
      Next_Ptr[current_ptr] = Next_Ptr[Next_Ptr[current_ptr]];  // 移動先は 元移動先の次の移動先
   }

   function iRemove_from_pos_to_pos(left, right) {  // left 〜 right 間の 要素を削除
      left--;
      right--;
      let current_ptr = start_ptr;
      for (let i = 0; i < left; i++) {  // 削除したい区間の直前まで移動する
         if (current_ptr === end_ptr) {  // current_ptr がリストのサイズより大きい場合
            break;
         }
         current_ptr = Next_Ptr[current_ptr];
      }
      if (current_ptr !== end_ptr) {
         let next_ptr = current_ptr;  // 区間の削除直後のインデックス
         for (let i = 0; i <= right - left; i++) {  // 削除したい区間の直後まで移動する
            if (next_ptr === end_ptr) {
               break;
            }
            next_ptr = Next_Ptr[next_ptr];
         }
         Next_Ptr[current_ptr] = next_ptr;
      }
   }

   function erase(pos) {  // 9
      let current_ptr = start_ptr;
      for (let i = 0; i <= pos; i++) {  // pos がリストのサイズより大きい場合
         if (current_ptr === end_ptr) {
            break;
         }      
         if (i === pos) {  // 削除したい箇所の直前までたどり着いた場合
            if (Next_Ptr[Next_Ptr[current_ptr]] === -1) {  // posが要素数以上だった場合
               break;
            }
            Next_Ptr[current_ptr] = Next_Ptr[Next_Ptr[current_ptr]];
            break;
         }
         current_ptr = Next_Ptr[current_ptr];
      }
   }

   function display() {  // 表示
      let cur_ptr = start_ptr;
      while (cur_ptr !== end_ptr) {
         if (cur_ptr !== start_ptr) {
            console.log(Value[cur_ptr]);
         }
         cur_ptr = Next_Ptr[cur_ptr];
      }
   }
   /* step 1 ここから
      const N = Number(lines[0]);
      for (let i = 1; i <= N; i++) {
         const n = Number(lines[i]);
         Value[i] = n;
      }
      for (let i = 1; i <= N; i++) {
         console.log(Value[i]);
      }
   */
   /* step 2 ここから
       const N = Number(lines[0]);   
       for (let i = 1; i <= N; i++) {
          const n = Number(lines[i]);
          push_back(n);
       }
   */
   /* step 3 ここから
       const N = lines[0].split(' ').map(Number);
       for (let i = 1; i <= N; i++) {
          const n = Number(lines[i]);
          push_front(n);
       }
   */
   /* step 4 ここから
       const [N, K] = lines[0].split(' ').map(Number);
       for (let i = 1; i <= N; i++) {
          const n = Number(lines[i]);
          push_back(n);
       }
       for (let i = 0; i < K; i++) {
          Remove_from_end();
       }
   */
   /* step 5 ここから
       const [N, K] = lines[0].split(' ').map(Number);
       for (let i = 1; i <= N; i++) {
          const n = Number(lines[i]);
          push_back(n);
       }
       for (let i = 0; i < K; i++) {
          iRemove_from_front();
       }
   */
   /* step 6 ここから
   const [N, P, X] = lines[0].split(' ').map(Number);
   for (let i = 1; i <= N; i++) {
      const n = Number(lines[i]);
      push_back(n);
   }
   insert(P, X);
   */
   /* step 7 ここから
       const [N, P] = lines[0].split(' ').map(Number);
       for (let i = 1; i <= N; i++) {
          const n = Number(lines[i]);
          push_back(n);
       }
       iRemove_from_pos(P);
   */
   /* step 8 ここから
    const [N, L, R] = lines[0].split(' ').map(Number);
    for (let i = 1; i <= N; i++) {
       const n = Number(lines[i]);
       push_back(n);
    }
    iRemove_from_pos_to_pos(L, R);
  */
   /* 完成 ここから
   const [N, Q] = lines[0].split(' ').map(Number);
   for (let i = 1; i <= N; i++) {
      const n = Number(lines[i]);
      push_back(n);
   }
   for (let i = N + 1; i <= N + Q; i++) {
      const q = lines[i].split(' ').map(Number);
      // console.log(q);
      switch (q[0]) {
      case 1:
         insert(q[1], q[2]);
         break;
      case 2:
         erase(q[1] - 1);
         break;
      }
   }
   */
   display();
});
hogeちゃんの画像

ポインタと値を 区別して 出力値を制御…!!?? 解説の動画も公開されています。

top

【step 1 〜 完成 の function 】

reader.on('close', () => {
   const Max_Size = 1024;  // 配列の要素数
   let start_ptr = 0;
   const end_ptr = Max_Size - 1;  // 1023
   const Value = new Array(Max_Size);  // 値を保持
   const Next_Ptr = new Array(Max_Size);  // 次のノード(節)のindexを保持
   Value[start_ptr] = -1;  // Value の最初の値を初期化
   Value[end_ptr] = -1;  // Value の最後の値を初期化
   Next_Ptr[start_ptr] = end_ptr;  // Next_Ptr の最初の値を初期化
   Next_Ptr[end_ptr] = -1;  // Next_Ptr の最後の値を初期化   
   let empty_min_idx = 1;  // Value に要素が入っていない最も小さいindex(1で初期化)
   let back_ptr = 0;  // empty_min_idx の左隣のindex 
   function push_back(val) {  // 要素を後尾に追加
      const new_ptr = empty_min_idx;  // val を追加する場所
      Value[new_ptr] = val;  // Value に val を追加
      Next_Ptr[new_ptr] = end_ptr;  // new_ptr → end_ptr
      Next_Ptr[back_ptr] = new_ptr;  // back_ptr → new_ptr
empty_min_idx++;  // empty_min_idx を更新
      back_ptr = new_ptr;  // back_ptr を更新
   }
   function push_front(val) {  // 要素を先頭へ追加
      const new_ptr = empty_min_idx;  // val を追加する場所
      Value[new_ptr] = val;  // Value に val を追加
      Next_Ptr[new_ptr] = Next_Ptr[start_ptr];  // new_ptr → start_ptr の次
      Next_Ptr[start_ptr] = new_ptr;  // start_ptr → new_ptr
      empty_min_idx++;  // empty_min_idx を更新
   }

   function Remove_from_end() {  // 末尾の要素を表示しない
      back_ptr--;  // 最後の要素 → 最後の要素の一つ前の要素 ↓
      Next_Ptr[back_ptr] = end_ptr;  // → end_ptr
   }

   function iRemove_from_front() {  // 先頭の要素を表示しない
      start_ptr++;
   }

   function insert(pos, val) {  // pos に val を 割り込ませる
      const new_ptr = empty_min_idx;  // Value に val を保存する場所
      Value[new_ptr] = val;  // Value に val を追加
      let current_ptr = start_ptr;  // 現在のノード
      for (let i = 0; i < pos; i++) {  // i は表示済みの値の数
         if (current_ptr === end_ptr) {  // 割り込ませる場所が末尾の場合
            break;  // 変更なし
         }         
         if (i === pos - 1) {  // 表示済みの値の数が pos の直前になれば
            [Next_Ptr[current_ptr],Next_Ptr[new_ptr]]= [new_ptr, Next_Ptr[current_ptr]];
          // 今のノード → 新しく追加したノード → 今のノードの次の場所
            break; 
         }
        current_ptr = Next_Ptr[current_ptr];  // 次のノードへ
      }
      empty_min_idx++;
   }

   function iRemove_from_pos(pos) {  // pos にある要素を除いて表示
      current_ptr = pos - 1;
      Next_Ptr[current_ptr] = Next_Ptr[Next_Ptr[current_ptr]];  // 移動先は元移動先の次の移動先
   }

   function iRemove_from_pos_to_pos(left, right) {
      left--;
      right--;
      let current_ptr = start_ptr;  // 区間の削除直前のインデックス
      for (let i = 0; i < left; i++) {  // 削除したい区間の直前まで移動する
         if (current_ptr === end_ptr) {  // current_ptr がリストのサイズより大きい場合
            break;
         }
         current_ptr = Next_Ptr[current_ptr];
      }
      if (current_ptr !== end_ptr) {
         let next_ptr = current_ptr;  // 区間の削除直後のインデックス
         for (let i = 0; i <= right - left; i++) {  // 削除したい区間の直後まで移動する
            if (next_ptr === end_ptr) {
               break;
            }
            next_ptr = Next_Ptr[next_ptr];
         }
         Next_Ptr[current_ptr] = next_ptr;
      }
   }

   function erase(pos) {  // pos にある要素を削除
      let current_ptr = start_ptr;
      for (let i = 0; i <= pos; i++) {  // pos がリストのサイズより大きい場合
         if (current_ptr === end_ptr) {
            break;  // 何もしない
         }      
         if (i === pos) {  // 削除したい箇所の直前までたどり着いた場合
            if (Next_Ptr[Next_Ptr[current_ptr]] === -1) {  // posが要素数以上だった場合
               break;
            }
            Next_Ptr[current_ptr] = Next_Ptr[Next_Ptr[current_ptr]];
            break;
         }
         current_ptr = Next_Ptr[current_ptr];
      }
   }

   function display() {  // 表示
      let cur_ptr = start_ptr;
      while (cur_ptr !== end_ptr) {
         if (cur_ptr !== start_ptr) {
            console.log(Value[cur_ptr]);
         }
         cur_ptr = Next_Ptr[cur_ptr];
      }
   }
});
hogeちゃんの画像

各問 の function のみ抜き出しました。アルゴリズムの問題なので 使いまわせるかも…。

 

top

コメント