構造体のリスト削除

質問

かれこれ１時間くらい悩んでいて
問題として

関数delete()を作成し、プログラムを完成させよ(~yabuki/p7.c)。
関数delete()は、与えられたデータをリストから削除するものである。
ただし、データが先頭であっても動作しなければならない。
次のように出力されるはずである。

NEXT gyuri[23] -> sunyon[23] -> nicole[20] -> hara[20] -> jiyon[17] -> END
PREV jiyon[17] -> hara[20] -> nicole[20] -> sunyon[23] -> gyuri[23] -> END

NEXT gyuri[23] -> sunyon[23] -> nicole[20] -> hara[20] -> END
PREV hara[20] -> nicole[20] -> sunyon[23] -> gyuri[23] -> END

NEXT sunyon[23] -> END
PREV sunyon[23] -> END

list ha nakunarimasita

/*******/の間に５行のプログラムを入れる。それ以外にmain()関数を
変更してはならない。

.........;の部分に構造体のメンバーを定義せよ。

というもので、Deleteしていくプログラムをつくりたいのですが
NEXT gyuri[23] -> sunyon[23] -> nicole[20] -> hara[20] -> jiyon[17] -> END
PREV jiyon[17] -> hara[20] -> nicole[20] -> sunyon[23] -> gyuri[23] -> END

セグメントエラー

となり、続きができていません。
delete関数のif(p->next != NULL){　のところだけやると
最後まで出るみたいですが、うまくいってません
よろしくおねがいします。

↓ソースです・・・
#include <stdio.h>
#include <string.h>

struct kara {
char name[16];
int age;
struct kara *next;
struct kara *prev;
};

struct kara * delete(struct kara *,struct kara *);
struct kara * findend(struct kara *);
void* printforw(struct kara *);
void* printback(struct kara *);

int
main()
{
struct kara a, x, f, m, c, *start, *end, *p;
char name[128];

strcpy(a.name, "gyuri");
a.age = 23;
strcpy(x.name, "sunyon");
x.age = 23;
strcpy(f.name, "nicole");
f.age = 20;
strcpy(m.name, "hara");
m.age = 20;
strcpy(c.name, "jiyon");
c.age = 17;
a.next = &x;
x.next = &f;
f.next = &m;
m.next = &c;
c.next = NULL;
/********************* 5 lines */
a.prev = NULL;
x.prev = &a;
f.prev = &x;
m.prev = &f;
c.prev = &m;
/*********************/

start = &a;
end = findend(start);
printforw(start);
printback(end);
printf("\n");

p = &c;
start = delete(start, p);
if (start == NULL) {
printf("list ha nakunarimasita\n");
return 0;
} else {
end = findend(start);
printforw(start);
printback(end);
}
printf("\n");

x.next = NULL;
p = &a;
start = delete(start, p);
if (start == NULL) {
printf("list ha nakunarimasita\n");
return 0;
} else {
end = findend(start);
printforw(start);
printback(end);
}
printf("\n");

p = start;
start = delete(start, p);
//de senntou wo kaesu
if (start == NULL) {
printf("list ha nakunarimasita\n");
return 0;
} else {
end = findend(start);
printforw(start);
printback(end);
}

return 0;
}
struct kara *
delete (struct kara *start,struct kara *p)
{
/*if(p->next->next->next->next)
{
start = p->next->next->next->next;
}
*/
for(p = start;p != NULL;p = p->next)
{
start = p->next->next->next;
p = start;
}
/*
if(p->next)
{
start = p->next;
}
if(p->prev)
{
start = p->prev;
}

if(p->next != NULL){
p->next->prev = p->prev;
}
}
*/
return p;
}

struct kara *
findend(struct kara *start)
{
struct kara *pl;
for(pl = start;pl != NULL; pl = pl->next){
start = pl;
}
return start;
}

void*
printforw(struct kara *aa)
{
struct kara *pl;
printf("NEXT ");
for ( pl = aa; pl != NULL; pl = pl->next) {
printf("%s[%d] -> ", pl->name, pl->age);
}
printf("END\n");
}

void*
printback(struct kara *cc)
{
struct kara *pl;
printf("PREV ");
//for( ; cc != NULL;cc = cc->prev){
for (pl = cc; pl != NULL; pl = pl->prev) {
printf("%s[%d] ->", pl->name,pl->age);
}
printf("END\n");
}

回答No.2

hanabutako · ベストアンサー

これを前提知識なしで出されたら、出題者が悪いと思いますが、そうでなかったらちゃんと授業を聞いていたかと問いただしたくなります。リストの削除の方法って授業で説明しませんでしたか？
他の人が書いたプログラムというのも勉強になると思いますので一応説明します。

deleteという操作は、リストから該当する要素を発見し、その要素を取り除くという操作で行います。
言い換えると、発見するというプログラムと取り除くというプログラムの組み合わせです。

まず、リストから所定の要素を探しだすというプログラムを書きましょう。
それは、こういうコードになるはずです。
struct kara *
find(struct kara *start, struct kara *to_find)
{
struct kara* cur;
for(cur = start;cur != NULL;cur = cur->next)
{
if (cur == to_find) {
printf("found %s %d\n", cur->name, cur->age);
return cur;
}
}
return NULL;
}
このプログラムはto_findに探したい要素のポインターを入れると、それを探しだして、printfで内容を表示した上でそれを返します。

次に、リストからの要素の削除です。
リストから要素を削除するという操作は、自分がいなかったかのようにポインターを付け替えるという操作です。
例えば、次のよなリストでbを消すことを考えます。
a -> b -> c

この場合、bが消えたあとの状態はこうなります。
a -> c

これは、bの指している先であるcをaの指し先に変更するということです。
言い換えると、bのprevのnextをbのnextにするということです。
よって、プログラムでやると b->prev->next = b->nextとなります。
また、prevについても同じ事をするのでb->next->prev = b->prevとなります。
ただし、リストの一番最後の要素に対して削除をする場合、b->nextは存在しないのでb->next->prev = b->prevの動作をする必要はありません。

まとめると、
if (b->prev != NULL) {
b->prev->next = b->next;
}
if (b->next != NULL) {
b->next->prev = b->prev;
}
となります。ただ、削除対象がstartだったとき b->prev == NULLのだけちょっとしたトリックが必要です。
この部分を実際のプログラムに起こすと書くとこんなかんじです。
struct kara *
delete (struct kara *start,struct kara *p)
{
struct kara* to_delete = find(start, p);
if (to_delete != NULL) {
if (to_delete->prev != NULL)
to_delete->prev->next = to_delete->next;
else /* head of the list. */
start = to_delete->next;

if (to_delete->next != NULL)
to_delete->next->prev = to_delete->prev;
}
return start;
}

以上でdelete関数が出来上がりました。

余談ですが、最後の要素を毎回手繰るというのは無駄な操作なので、こういうことをしたい場合は普通はtailqというtailを指すポインタを持つ両方向リンクリストを使うのが普通だと思います。

ついでに余談ですが、リスト操作はコンピュータサイエンスの基礎知識ではありますが、基本的にやることは決まっているので、queue.hなどを使って書くのが普通だと思います。
ちょろっと調べたら、そのtailqの内部構造を解説したページを見つけたので参考までに。
http://d.hatena.ne.jp/koseki2/20120105/tailq

もう一つ余談を言うと、セグメントエラーが出るようなプログラムで動きを確かめるにはgdbを使うと良いです。gdbを使うと、どこでセグメントエラーが出ているか一瞬でわかるので、とりあえず治すのは格段に早くなります。
今回の場合、gdbを使うとstart = p->next->next->next;で出ていると一発でわかります。まぁ、わかったところで上記のようなコードを書かないと動かないのですが。

では、頑張って。

補足

説明はまったくもってないです。簡単な構造体の作り方のみしか教わりません。

こういった応用問題は独学で学ぶしかないので、こういった頼りが必要になってしまいます。先生に聞いても答えてくれはくれないので。
少し参考にして自分なのにdelete関数を作ってみます。

回答No.1

Wr5

リンク構造、ちゃんと理解していない…ってコトでしょうな。

start = delete(start, p);
struct kara *delete (struct kara *start,struct kara *p)
ということは…startからpを探して、リンクのつなぎ替えを実施しさらにその先頭を返却する。
ということになります。
で、
>ただし、データが先頭であっても動作しなければならない。
ということなので条件分岐が必要…ですな。

まず…

startとpが同じか？で分岐。
同じだったら先頭を取り除くので、
startの次へ進めます。
NULL(つまりリストにはstartしかない)であれば戻り値はNULLで、非NULLならstart(またはp)をリンクから外すためにprevをNULLにします。
# リスト構造としてはstartのnextもNULLにすべき…でしょうが……。
startとpが異なる場合はstartからリストを辿ってpを検索、
pの次の要素のprevにpが持っているprevをコピー、pの前の要素のnextにpが持っているnextをコピーしてリンクのつなぎ替えを行います。
# それぞれ、絵に描いてどういうつながりになるのか確認してみるといいでしょう。
pをリンクから外した後で先頭の要素のアドレスを返す。
と……。

まぁ、もう少し効率のいい方法もありますが。
# pは判っているのだからstartから検索する必要はない…よね。と…。

ちなみに…
>struct kara *
>delete (struct kara *start,struct kara *p)
>{
>　for(p = start;p != NULL;p = p->next)
こんなコトしたら、削除対象のpのアドレスがいきなり不明になります。

補足

こういった問題を説明なしに出されるので、なんともいえません。
教えてくれるのはほんの一部で
構造体の簡単な作り方ー！みたいな感じで教えてくれるだけで
本質は課題として出されて、まったく構造体のポインタなどの説明がないんですよね。

最後のはよくわからないのでやってしまいました。
そもそもこのプログラムの前半自体は先生が書いたもので
自分で書いたものではないので、３回表示するんだろうな、くらいで
後は問題通りに何か色々やってみた結果です。