質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.77%

連結リストのスプライス(splice)を実装したい

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,385

score 157

趣味でC言語の連結リストを作っています。C++のstd::listと同じように使えることが目標です。

lis (singly linked list for C language)
https://github.com/katahiromz/lis/blob/master/lis.h
https://github.com/katahiromz/lis/blob/master/lis.c
https://github.com/katahiromz/lis/blob/master/nod.h
https://github.com/katahiromz/lis/blob/master/nod.c

ファイル「lis.c」の865行目のlis_splice関数と、881行目のlis_splice_range関数を実装したいと考えております。プロトタイプは以下の通りです。

void lis_splice(PLIS pl, PNOD here, PLIS other, PNOD it);
void lis_splice_range(PLIS pl, PNOD here, PLIS other, PNOD begin, PNOD end);

型PLISは、構造体LISへのポインターです。PNODは、構造体NODへのポインターです。

構造体NODは、nod.hで宣言されており、ノードを表しています。

構造体LISは、lis.hで宣言されており、連結リストを表しています。

lis_splice関数は、連結リストotherにノードitを取り除き、連結リストplのノードhereがある場所に移動します。hereがNULLだったら、最後の方に移動します。

lis_splice_range関数は、連結リストotherにあるノード[begin, end)を取り除き、連結リストplのノードhereがある場所に移動します。hereがNULLだったら、最後の方に移動します。endがNULLだったら、begin以降のすべてのノードを移動します。

よろしくお願いします。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

すいません。
本質的な回答ではありませんが、今後のことを考えてという意味で1点。
Listを Lis, Node をNOD と訳す積極的なメリットがないと思いますので、
是非 LIST, NODE をそのまま使うことをおすすめします。

何か意図的なのかも知れませんが、このサイトのような質問の場に出す時にもきっと可読性が向上して、回答する側にとっても回答しやすくなるかも知れません。

本質的な回答はここから。。。

このNOD/LIS は「双方向キュー」を構成していると考えて良いかと思いますが、双方向キューの終端を NULLで定義したことでコードが煩雑になっている気がします。

双方向キューで「何もない」という状態は安易に考えると NULL にしたがるところですが、一般的には自己参照にする方がとてつもなく処理を簡単にします。

lis_initを例に自己参照を導入すると。。。

void lis_init(PLIS pl)
{
    assert(pl != NULL);
    pl->first = pl;
    pl->last = pl;
    pl->count = 0U;
    assert(lis_valid(pl));
} /* lis_init */

となります。
これによってノードの挿入(EnQueue)、抜き取り(DeQueue)は信じられないほど簡単になるはずです。
簡単になるだけでなく、バグになりにくくなって堅牢になります。
これは RTOS等でも実際に使われているキュー構造での処理方法で、RTOSのように速度重視の世界でかつ確実に動作させるシステムで実装される定石のコードです。

是非採用してみてください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

https://github.com/katahiromz/lis/pull/1

pullrequestしました。そっちにも書いたとおり、さらに
DeepDiveIntoSeaさんの指摘通り、endの扱いに致命的な問題があるようです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.77%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る