プログラミングスクールC言語プログラミング入門講座レッスンノート リスト構造の任意場所のノード削除処理

リスト構造の任意場所のノード削除処理

C言語プログラミング入門講座のレッスンノート

レッスンノートって?レッスンノートって?

2/13のレッスン内容は、以下の通りです。

 ○ リスト構造プログラミング
  ・ 任意場所のノード削除(続き)

以下に詳細を記します。

□ 任意場所のノード削除(つづき)

前回は、ノードの削除処理に関する全体像をフローチャートを使って表してみました。

  [START]
    |
  ・ ノードの削除判定(1以外が入力されたら、即ENDに行く)
    |
  ◎ IDの指定
   ・ 範囲内のIDが指定されるまで、再入力
    |
  ◎ IDからのノード特定
   ・ 指定されたIDと一致するものをリストから探す
    |
  ◎ 特定したノードに関する連鎖の張り替え
   ・ 特定したノードとつながる全連鎖を消す
   ・ 特定したノードの前と後ろのノードをつなげる
   ・ 特定したノードの領域を解放する
    |
  ◎ IDの振り直し
   ・ ノード削除後のリストに対して、IDを割り振りなおす
    |
  [END]

今回は、この中の◎の部分(サブルーチンとした箇所)のアルゴリズムを考えていきました。

[IDの指定]

今回は、リストに登録されているID以外が入力されたら、再入力を促す仕様にしました。

この仕様のもとで、以下のアルゴリズムを作成しました。

  [START]
   │
   ├←───────────────┐
  [IDの入力要求(プロンプト付)]    │
   │                │No
  <指定したIDがリストに存在するか?>┘
   │Yes
  [指定したIDを呼び出し元に返す]
   │
  [END]

[IDからのノード特定]

指定されたIDを入力(引数)として、ノードを特定する処理ですね。

アルゴリズムは、以下のような感じになります。

  [START](指定されたIDを引数とする)
   │
  (ループ開始部: リストを先頭から最後まで探索)
   │                
  <ノードのIDが指定したIDと一致したか?>┐
   │No                 │Yes
  (ループ終了部)             │
                      │
   ┌←─────────────────┘
  [特定したノードを呼び出し元に返す]
   │
  [END]

[特定したノードに関する連鎖の張り替え]

次は、連鎖の張り替えのアルゴリズムです。

  [START](特定したノードを引数とする)
   │
  [特定したノードの前、後ろを一時変数に設定(以降、prevとnextと称する)]
   │                
  <nextが存在するか?>─────┐
   │Yes             │No
  [prev->nextをnextにする]  [prevをlastnodeに設定する]
   │              │
   ├←─────────────┘                
  <prevが存在するか?>─────┐
   │Yes             │No
  [next->backをprevにする]  [nextをtopnodeに設定する]
   │              │
   ├←─────────────┘
  [特定したノードのbackとnextをNULLにする]
   │
  [特定したノードの領域を解放する]
   │
  [END]

[IDの振り直し]

最後にIDの振り直しです。

削除したノードから振り直す、というのは改善点として挙げられますが、まずはベタに1から振り直すようにしました。

  [START](指定されたIDを引数とする)
   │
  [変数i に1を設定]
   │
  (ループ開始部: リストを先頭から最後まで探索)
   │                
  [変数i の内容を、ノードのIDおよびlist_numに設定]
   │
  (ループ終了部)
   │
  [END]
このレッスンノートを書いたコーチ

富士通でソフトウェア開発を担当。楽しいプログラミングの醍醐味、教えます

楽しめるC言語セミナー
源田雄一 (C言語)

品川・戸塚・武蔵中原・立川・新横浜・中山・長津田・成瀬・町田・関内・石川町・東小金井...

レッスンノート ページ先頭へ

C言語情報

サイタのC言語講師がブログを通して、C言語情報を発信。更新情報のチェックはこちらから!