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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

GitHub

GitHubは、Gitバージョン管理システムを利用したソフトウェア開発向けの共有ウェブサービスです。GitHub商用プランおよびオープンソースプロジェクト向けの無料アカウントを提供しています。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

1881閲覧

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

katahiromz

総合スコア186

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

GitHub

GitHubは、Gitバージョン管理システムを利用したソフトウェア開発向けの共有ウェブサービスです。GitHub商用プランおよびオープンソースプロジェクト向けの無料アカウントを提供しています。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2015/07/27 06:15

趣味で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以降のすべてのノードを移動します。

よろしくお願いします。

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

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のように速度重視の世界でかつ確実に動作させるシステムで実装される定石のコードです。

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

投稿2016/01/28 08:51

DeepDiveIntoSea

総合スコア33

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

投稿2016/01/27 05:23

編集2016/01/28 16:25
yumetodo

総合スコア5850

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問