[C言語]２つの双方向循環リストをつなげたいです。

Question

前提・実現したいこと

頭（ダミー）がある2つの双方向循環リスト d1, d2においてd1の末尾をd2の先頭につなげ、d２の末尾をd１の先頭つなげたいのですが出力して見たところうまくいっていませんでした。
原因が分からないのでご教示願います。

例

d1　(2)(4)
d2  (1)(3)
結合後
d1 (2)(4)(1)(3)

該当のソースコード(必要ならばすべてのソースコードを添付します)

typedef int elementtype;

struct dlnode {
  elementtype element;
  struct dlnode *prev, *next;
};

typedef struct dlnode* dllist;

void append_dllist(dllist d1, dllist d2) {
  dllist n;
  n = d1;
  while(n->next != d1) {
    n = n->next;
  }
  n->next = d2;
  n = n->next;
  while(n->next != d2) {
    n = n->next;
  }
  n->next = d1;
  delete(d2);
   //free(d2);修正
}

void delete(dllist p) {
  p->prev->next = p->next;
  p->next->prev = p->prev;
  free(p);
}

//nextで一巡するまで要素を[]で囲って出力し、prevで一巡するまで{}で囲って出力する
void print_dllist(dllist d) { 
  dllist n;
  n = d->next;
  while(n != d) {
    printf("[%d]", n->element);
    n = n->next; 
  }
  n = n->prev;  
  while(n != d) {
    printf("{%d}", n->element);
    n = n->prev;
  }
  printf("\n");
  
}

Comments

[退会済みユーザー]

うまくいかなかったというのを具体的に。ソース全体を読みたくないので。。。また、デバッグを試されてみてどうでしたか？

Answer 1

append_dllist 内に delete は不要です。
循環しているので、末尾を探すのに一周する必要もありません。

#include <stdio.h>
#include <stdlib.h>

typedef int elementtype;

struct dlnode {
	elementtype element;
	struct dlnode *prev, *next;
};

typedef struct dlnode* dllist;

dllist new_dllist(int element)
{
	dllist result = malloc(sizeof(struct dlnode));
	result->element = element;
	result->prev = result;
	result->next = result;
	return result;
}

void print_dllist(dllist list)
{
	dllist ptr = list;
	if (list == NULL) return;
	printf("%s\n", "正順に表示します");
	do {
		printf("%d ", ptr->element);
		ptr = ptr->next;
	} while (ptr != list);
	printf("\n");
	printf("%s\n", "逆順に表示します");
	do {
		printf("%d ", ptr->element);
		ptr = ptr->prev;
	} while (ptr != list);
	printf("\n\n");
}

void free_dllist(dllist list)
{
	dllist ptr = list;
	if (list == NULL) return;
	do {
		free(ptr);
		ptr = ptr->next;
	} while (ptr != list);
}

void append_dllist(dllist a, dllist b)
{
	if (a == NULL || b == NULL) return;
	a->prev->next = b;
	b->prev->next = a;
	dllist t = a->prev;
	a->prev = b->prev;
	b->prev = t;
}

void main()
{
	dllist list = new_dllist(2);
	append_dllist(list, new_dllist(4));

	dllist list2 = new_dllist(1);
	append_dllist(list2, new_dllist(3));

	append_dllist(list, list2);
	print_dllist(list);
	free_dllist(list);
}

Comments

[apeirogon0813]

Zuishinさんのコードには先頭のダミーは存在しませんのでappendないのdelete()はいらないと思います。
私のソースコードは以下のようで初めにダミーとなるノードを作りそこから繋げているのでdelete()は必要になってくるという次第です。情報が足りてなくて申し訳ございません。
また、循環しているので、末尾を探すのに一周する必要もありません。
これにはとても納得です！
do-whille文の方がより淡麗で参考になります。
#include<stdio.h>
#include<stdlib.h>

typedef int elementtype;

struct dlnode {
elementtype element;
struct dlnode *prev, *next;
};

typedef struct dlnode* dllist;

void print_dllist(dllist d) {
dllist n;
n = d->next;
while(n != d) {
printf("[%d]", n->element);
n = n->next;
}
n = n->prev;
while(n != d) {
printf("{%d}", n->element);
n = n->prev;
}
printf("\n");

}

void insert(dllist p, elementtype e) {
dllist n;
n = (struct dlnode *) malloc (sizeof (struct dlnode));
n->element = e;
if(p->next == NULL && p->prev == NULL) {
p->prev = n;
n->next = p;
n->prev = p;
p->next = n;
} else {
n->next = p;
n->prev = p->prev;
p->prev->next = n;
p->prev = n;
}
}

void delete(dllist p) {
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
}

void append_dllist(dllist d1, dllist d2) {
dllist n;
n = d1;
while(n->next != d1) {
n = n->next;
}
n->next = d2;
d2->prev = n;
n = n->next;

while(n->next != d2) {
n = n->next;
}
n->next = d1;
d1->prev = n;
delete(d2);
}
int main(void) {
int i;
char buf[128];
dllist d1, d2, p;
d1 = (struct dlnode *)malloc(sizeof(struct dlnode));
d1->prev = NULL;
d1->next = NULL;

d2 = (struct dlnode *)malloc(sizeof(struct dlnode));
d2->prev = NULL;
d2->next = NULL;

while(fgets(buf,sizeof(buf),stdin) != NULL) {
sscanf(buf,"%d", &i);
insert(d1, i);
insert(d2, i);
}
print_dllist(d1);
print_dllist(d2);

p = d1->next;
while(p != d1) {
if(p->element % 2) {
p = p->next;
delete(p->prev);
continue;
}
p = p->next;
}

p = d2->next;
while(p != d2) {
if(!(p->element % 2)) {
p = p->next;
delete(p->prev);
continue;
}
p = p->next;
}

print_dllist(d1);
print_dllist(d2);
append_dllist(d1, d2);
print_dllist(d1);
return 0;
}

[Zuishin]

ダミーは何のために必要なんですか？

[apeirogon0813]

課題においての指定なのですが、確かになぜ必要なのかわかりかねます。

[Zuishin]

了解しました。
が、多分ダミーの使い方が間違っていると思います。
もう一度よく課題を確認することをお勧めします。

Answer 2

このあたりの子が悪さしているように思えます。

delete(d2);
free(d2);

void delete(dllist p) {
  p->prev->next = p->next; // (4のノード).next = (3のノード)
                           // つまり、 (2)(4)(1)(3) が、(2)←→(4)←→(3) となります。
                           //                                ↑    ↑
                           //                               (1)---┘
  p->next->prev = p->prev; // ここもおかしくなります。
  free(p); // (1のノード)のメモリを解放する
}

• dlistってdlnode*ですよね。ノードだと思うんですが、それを解放しちゃっていいのか？というのがfree(d2)の悪そうな点です。
• delete()は、その前に接続しなおしの処理があるのに、あらためてやることあるのかな？というのが悪そうな点です。

###変数やメンバ変数と、その中身のイメージ
きったない絵であれですが。

Comments

[apeirogon0813]

おっしゃるとおり、二度もfreeする意味はないのでfree(d2)は消しましたが出力結果が
[1][3][1][3][1][3][1][3][1][3]...
と永遠に繰り返し出力されてしまいます、、

[退会済みユーザー]

freeは一度もやらなくていいと思います。ノードを削除するのはまずいですよね。deleteもいらなくないですか？

[apeirogon0813]

delete()の際そのノードはどこからもたどることができないメモリになり、残ってしまう（メモリリーク）が起こらないようにしているのですがまちがてますでしょうか？

[apeirogon0813]

ちなみに、delete内のfree()を消してみましたが出力は変わらず上記のようになってしまいました

[退会済みユーザー]

いえ、deleteそのものが不要かと。deleteの各行が何をしたいか書き出してみてください。
たぶん、誤解の根本は、d2とその中身を誤解されていることにあります。d2はポインタで、その中身は(1)のアドレスです。なので、free(d2)やfree(p)とすると、その中身のアドレス指すノード、つまり(1)のノードを格納しているメモリが解放されます。ということは、せっかくつなげた(1)が消えてしまいます。

[apeirogon0813]

free()はリスト内のある１つのノード（節点）のメモリを開放することではないのでしょうか？

void delete(dllist p) {
//pの指すノードの前のノードのnextにpの指すノードの次のノードをポインタする
p->prev->next = p->next;
//pの指すノードの次のノードのprevにpの指すノードの前のノードをポインタする
p->next->prev = p->prev;
リストから外されたノードpを開放する
free(p);

}

[退会済みユーザー]

> free()はリスト内のある１つのノード（節点）のメモリを開放することではないのでしょうか？
はい、あっています。なので、ノードが消えてしまいます。今回やりたいことはリストをつなげることであって、なにかノードを消したいわけではないですよね？なので、freeが出てくるのはおかしいです。ちなみに、nextやprevへの代入ですが、これはノードが代入されているのではなく、ノードへの住所であるアドレスが代入(コピー)されいているだけです。住所をコピーしても、家がコピーされないのとおなじです。

ごめんなさい、deleteメソッドの各行で何がしたいかではなく、各行でそれをなぜしたいかを書いて下さい の間違いでした。

[apeirogon0813]

d1, d2の先頭にはそれぞれ頭であるダミーが入っているのでd1とd2をつなげた際、真ん中にd2のダミーが入っていては要素の出力の時に邪魔ですのでfree()でダミーのノードを開放しました。

はい、住所をコピーすることによって二つのリストをつなげているのですが、だめなのでしょうか

[退会済みユーザー]

d2に入っているのはダミーでなく、ノード(1)へのアドレスです。なので、free(d2)とすると、ノード(1)が消えます。コード上で代入しているものはノードでなく全てアドレスである点に注意してください。なので、なにかしらfree()すると、ノード(家)が消えます。

> はい、住所をコピーすることによって二つのリストをつなげているのですが、だめなのでしょうか
リストをつなげるのは、append_dllistメソッドの最初からdeleteメソッドの前までできているのでは？deleteであらためてリストをつなげなおすのでおかしくなっているのではないかな？と（ほかにも原因はあるかもしれませんが）

[apeirogon0813]

動かしているのはポインタnであってd2は動かしていないのでd2はd2リストの頭であるダミーへのアドレスを指していると思うので開放すると結果的にd2のダミーのみが開放されると思うのですが。
ちなみにfreeあってもなくてもdelete()しないと以下のように出力されダミーの要素が入ってきてしまいます。
[2][0][1][3]{3}{1}{0}{2}

ちなみにappend_dllist()においてprevの方を接続し忘れていたのでそこをつなげるとなぜかうまく出力されました。

[退会済みユーザー]

絵を見ていただければわかるのですが、ダミーとなるノードは存在しません。d2というポインタ変数そのものをダミーというのであれば理解できます。しかし、d2というポインタ変数という箱の中身であるアドレスはダミーではなく、値1のノードを指します。

[退会済みユーザー]

void append_dllist(dllist d1, dllist d2)
{
dlnode* d1Head = d1;
dlnode* d1Tail = d1->prev;
dlnode* d2Head = d2;
dlnode* d2Tail = d2->prev;

// d1の尾とd2の頭をつなぎます
d1Tail->next = d2Head;
d2Head->prev = d1Tail;
// d2の尾とd1の頭をつなぎます
d2Tail->next = d1Head;
d1Head->prev = d2Tail;
}

[apeirogon0813]

すみません私が提示したソースコードだけではダミーのノードが作られているのかわかりませんよね。
ppnさんの絵の場合はたしかにダミーとなるノードは存在せずそのまま繋げるだけなのは賛成です。

[退会済みユーザー]

なるほど、そういうことでしたか。であれば、上のコードを少し変えて、最後にfree(d2)すればいいと思います。

[apeirogon0813]

情報が不足していたため誤解させて申し訳ございませんでした。

[退会済みユーザー]

こんな感じですね。ただ、解放するときはZuishinさんのようにチェックいれたほうがいいです。
void append_dllist(dllist d1, dllist d2)
{
dlnode* d1Head = d1->next;
dlnode* d1Tail = d1->next->prev;
dlnode* d2Head = d2->next;
dlnode* d2Tail = d2->next->prev;

// d1の尾とd2の頭をつなぎます
d1Tail->next = d2Head;
d2Head->prev = d1Tail;
// d2の尾とd1の頭をつなぎます
d2Tail->next = d1Head;
d1Head->prev = d2Tail;

free(d2);
}

[apeirogon0813]

ありがとうございます。
参考にします。