サイタプログラミングスクールC言語プログラミング入門講座 神奈川 楽しめる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]
新着レッスンノート

9/12のレッスン内容は、以下の通りです。 ・ポリモーフィズムについて ・Javaでの例外処理(try〜catch) 詳細は、お渡ししたノートを参照してください。 ポリモーフィズムは、オブジェクト指向の三大機能のひとつ(他にはカプセル化と継承があります)ですが、その中で...

9/5のレッスン内容は、以下の通りです。 ・ オブジェクト指向の考え方 □ オブジェクト指向の考え方 今取り組んでいるJavaは、純粋なオブジェクト指向のプログラミング言語に分類されます。そして、これはこれまで取り組んできたC言語とは、アプローチ的にも違うことをお話しし...

3/20のレッスン内容は、以下の通りです。 ・ 関数の再帰呼び出し 再帰呼び出しは自己呼び出しとも呼ばれ、関数が自分自身を「再帰的に」呼び出せるしくみのことです。 レッスンでは「1〜nまでの合計を求める」というお題で説明しましたが、他にも階乗、数列の漸化式などで用いられる仕...

3/15のレッスン内容は、以下の通りです。 ・ ポインタの基礎 ・ 変数の有効範囲 今回の詳細も、別途お渡ししたノートを参照してください。

3/15のレッスン内容は、以下の通りです。  ・ 配列の引数の取り扱い  ・ ポインタと配列・文字列の関係 今回の詳細は、別途お渡ししたノートを参照してください。

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