連結リストから入力した数字の位置のノードを削除するプログラムで、2回目からの入力がおかしくなってしまいます。

Question

前提

大学の課題で躓きました。連結リストから入力した数字の位置のノードを削除するプログラムで、2回目からの入力がおかしくなってしまいます。どのようにすれば2回目からも普通に動作するようになるでしょうか。
お願いします。

頭のある連結リストに対し、先頭の節点を削除する関数

void delete(list l);

を定義せよ。この関数は先頭を削除する関数であるが、リスト l の先頭の次を削除したい場合は delete(l->next)、さらにその次を削除したい場合はdelete(l->next->next) のようにすれば、先頭以外の位置のものも削除することができる。なお、メモリリーク)が起こらないように、不要になった節点のメモリは free 関数によって必ず解放する必要がある。作成すべきプログラムは、標準入力の 1 行目に与えられる文字列から char 型のリストを作成し、以降の入力の各行に与えられる「位置」に対し、その位置のアルファベットを削除するプログラムを作成せよ。「位置」は整数値で与えられ、0 番目が先頭を表すものとする。

実行例

>Bingo
Bingo
>2
Bigo
>3
Big

>Linked
Linked
>4
Linkd
>4
Linkd
>4
Linkd
>4
Linkd
>0
ink

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

>Bingo
Bingo
>2
Bigo
>3
Bi
>0
iiiiiiiiiiiiiiiiiiiiiii....

>Linked
Linked
>4
Linkd
>4
Linked
>4
Linked
>0
inkinkinkinkinkinkinkinkinkink........

該当のソースコード

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


typedef char elementtype;
struct node {
  elementtype element;
  struct node* next;
};

typedef struct node* list;

struct node *initlist(elementtype e, struct node *x) {
  struct node *n = (struct node *)malloc(sizeof(struct node));
  n->element = e;
  n->next = x;
  return n;
}

void insert(list *l, elementtype e) {
  *l = initlist(e, *l);
}

void delete (list *l) {
  if((*l)->next!=NULL){
   struct node *n=initlist(NULL,(*l)->next);
    free(*l);
    l=&n;
  }
}

void printlist(list l) {
  for( ; l != NULL; l=l->next) printf("%c", l->element);
  printf("\n");
}

int main() {
  char buf[128];
  struct node head;
  int i;
  list l ;
  fgets(buf, sizeof(buf), stdin);
  int len = strlen(buf);
  if(len>0 && buf[len-1]=='\n') buf[len-1] = '\0';

  head.next = NULL;
  for(i=strlen(buf)-1; i>=0; i--) insert(&head.next, buf[i]);

  printlist(head.next);

  while(fgets(buf,sizeof(buf),stdin) != NULL) {
    sscanf(buf,"%d",&i);
    l = &head;
    for(i; i>0 && l->next!=NULL; i--, l=l->next);
    delete(&l->next);
    printlist(head.next);
  }

  return 0;
}

補足情報（FW/ツールのバージョンなど）

unix gcc 4.8.5

Comments

[jimbe]

何が起きているとお考えでしょうか。
また、それをどうすれば調べられる/確認できると思われますか。

…実行例の Linked のほう、 4 を指定しても d が消えてないですね。

Answer 1

頭のある連結リストに対し、先頭の節点を削除する関数
void delete(list l);
を定義せよ。

質問者の方は、こちらの文言を誤解しているように思います。(誤解を招く表現になっているのは確かなのですが)

出題者はおそらく、引数lの「次の」要素を削除する関数を書いて欲しいのだと思われます。
(頭のある連結リストの場合、先頭の接点は「頭」の次の接点となる)

それを誤解してlの指す要素そのものを削除する関数を書こうとした結果、引数の型をlist lからlist* lに変えざるを得なくなって、混乱を招いているように思います。
(こちらの方針でも書けないことはありませんが、難易度は上がります)

まずは素直に、lの「次の」要素を削除する関数void delete(list l);を書いてみてはいかがでしょうか。

---

なお、現状のコードで、初回だけうまくいっているように見えるのは、偶然にすぎません。

l=&n;とすることで、引数として渡したポインタを書き換えようとしたのだと思いますが、これでは元のポインタは書き換わりません。
(void f(int x) { x = 2; }としても、引数として渡した変数が書き換わらないのと同じ)

その結果、free(*l);で解放された node がそのまま使われ続けることになります。
解放済みメモリの使用は未定義動作なので、何が起こってもおかしくはありません。

Comments

[sawaawa]

delete(l)にすることで治りました。ありがとうございました。

Answer 2

i番目の要素を削除すると、i-1番目とi+1番目が連結になる。

Comments

[KEMONO.PANTSU]

無言低評価禁止

[KEMONO.PANTSU]

低評価禁止

[jimbe]

↑無意味な大量の改行によりコメント欄が圧迫されている為、通報しました。

[KEMONO.PANTSU]

😢

[KEMONO.PANTSU]

死にたい。
😢😢😢

[KEMONO.PANTSU]

時間を戻す方法を知りたい。