双方向リストを作ったが、deleteした後にリストの中身を表示させると実行時間超過で中断されてしまう

Question

概要

２つの頭（ダミー）がある双方向循環リストにおいて
（１）入力順と同じ順番にリストを作成する
（２）１つ目のリストは要素が奇数、２つ目のリストは要素が偶数のものを消去する
（３）１つめのリストの末尾に２つ目のリストを繋げ、２つ目のリストの末尾に１つ目のリストの先頭ダミーにつなぐ。尚、２つ目の先頭のダミーは消去する。

というものをプログラムをしたいのですが、２つ目のリスト内の要素が偶数のものを消去を行なった後にリストを出力するときに時間超過で中断されてしまいます。複雑なことは行っていないはずなのに、何がいけないにでしょうか？

実行例

＞1
＞2
＞3
[1][2][3]{3}{2}{1}
[1][2][3]{3}{2}{1}
[2]{2}
[1][3]{3}{1}
[2][1][3]{3}{1}{2}

発生している問題・エラーメッセージ

＞1
＞2
＞3
[1][2][3]{3}{2}{1}
[1][2][3]{3}{2}{1}
この先が行われない

該当のソースコード

#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) {/*d の指しているダミーの節点から、next を順にたどって自分自身に戻るまで element を [と] で挟ん
で標準出力に出力し続けたのち、prev を順にたどって自分自身に戻るまで element を{と}で挟んで標
準出力に出力し続ける関数 (最後に改行)。 */
  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) { /*p の指している節点の prev に、element として 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 の指している節点のみを削除する関数 (p の前後のポインタを繋ぎ変えて、free 関数により削除した
節点のメモリを解放する)。*/
struct  dlnode *next, *prev;
  prev = p->prev;
  next= p->next;
  if (prev != NULL)
    prev->next = next;
  if (next != NULL)
    next ->prev = prev;
  free(p);
}
void append_dllist(dllist d1, dllist d2) {/*d1、d2 の指している節点をダミーの節点とする 2 つの双方向リストを連結する関数 (d1 から next をた
どっていくと、1 つめの双方向リストの要素に続いて 2 つめの双方向リストの要素が現れ、d1 に戻っ
てくるように定義し、2 つめのダミーの節点 d2 のメモリは free 関数によって解放する)*/
  dllist n;
  n = d1;
  while(n->next != d1) {
    n = n->next;
  }
  n->next = d2;

  while(n->next != d2) {
    n = n->next;
  }
  n->next = d1;
  free(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;
  do {
    if(p->element % 2) {
      p = p->next;
      delete(p->prev);
 
    }
    p = p->next;
  }while(p!=d1||p->next!=d1);

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

    print_dllist(d1);
  print_dllist(d2);

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

Comments

[jimbe]

時間超過ということはどこかで無限ループしているのでしょう。
コードの一行毎に printf で何かマークを出すようにし、どこでループしているかを調べては如何でしょうか。

また、コードをコピペしてもコンパイルエラーになっています。
teratail への貼り付けはソースファイルの中身そのままにするようにしてください。

[sawaawa]

申し訳ありません。
訂正前のものを添付していました。

[kazuma-s]

「頭（ダミー）がある双方向循環リスト」の頭の prev と next は NULL ではなく、
最初は 頭のアドレスを入れます。

[dodox86]

タグの「リストボックス」は、GUIの要素の種類のひとつであって、今回は関係無いと思います。

Answer 1

https://pythontutor.com/c.html を利用し、コードの流れを可視化する。

Answer 2

質問のコードは全角スペースが入っていたり、do文の最後にセミコロンがないなど
コンパイル不可能なものです。
また、append_dllist も間違っています。

リストのヘッドの初期化を insert の中で行っているようですが、
ヘッドを作った時に初期化するほうが良いと思います。

#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)
{							
	for (dllist n = d->next; n != d; n = n->next)
		printf("[%d]", n->element);
	for (dllist n = d->prev; n != d; n = n->prev)
		printf("{%d}", n->element);
	printf("\n");
}

void insert(dllist p, elementtype e)
{
	dllist n = malloc(sizeof(struct dlnode));
	n->element = e;
	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)
{
	d1->prev->next = d2->next;
	d2->next->prev = d1->prev;
	d1->prev = d2->prev;
	d2->prev->next = d1;
	free(d2);
}

int main(void)
{
	dllist d1, d2, p, q;
	d1 = malloc(sizeof(struct dlnode));
	d1->prev = d1->next = d1;
	d2 = malloc(sizeof(struct dlnode));
	d2->prev = d2->next = d2;

	char buf[128];
	while (fgets(buf, sizeof buf, stdin)) {
		int i;
		sscanf(buf, "%d", &i);
		insert(d1, i);
		insert(d2, i);
	}
	print_dllist(d1);
	print_dllist(d2);

	for (p = d1->next; p != d1; p = q) {
		q = p->next;
		if (p->element % 2 == 1) delete(p);
	}
	for (p = d2->next; p != d2; p = q) {
		q = p->next;
		if (p->element % 2 == 0) delete(p);
	}
	print_dllist(d1);
	print_dllist(d2);

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

append_dllist の中で free(d2); の代わりに d2->prev = d2->next = d2; としておいて
main で d2 のリストの free を行ったほうがいいとは思うのですが。

このコードが理解できたかどうかコメントをお願いします。

Comments

[sawaawa]

初期化の部分が参考になります。
訂正前のコードを添付してすみませんでした。
ありがとうございました。

Answer 3

コードをよく読んだ訳では無いので処理は確認していませんが、 do while() のセミコロンを付け忘れているのでは無いでしょうか

Answer 4

まずはデバッグできる環境を整えてはどうでしょうか。
Windowsなら、VisualStudioやEclipseなどがあります

ブレークポイントを設定して実行を止め、変数の中身を見ることができます。
また、１行づつ実行して、どう動作するかを見れます。

これで、どこがおかしいのかわからない、ってことはなくなりますよ