連結リストを用いて、入力した位置にアルファベットを挿入するプログラムを作ろうとしたが、Segmentation Faultが発生した。

Question

連結リストを用いて、入力した位置にアルファベットを挿入するプログラムを作ろうとしましたが、Segmentation Faultが発生してしまいました。デバッガgdbもうまく作動しません。どのようにすれば直るのか分かりません。問題は以下の通りです。

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

void insert(list l, elementtype e);

を用いて標準入力の 1 行目に与えられる文字列から char 型のリストを作成し、以降の入力の各行に与えられる「位置」と「アルファベット 1 文字」に対し、その位置にアルファベットを挿入するプログラムを作成せよ。「位置」は整数値で与えられ、0 番目が先頭を表すものとする。また、標準出力には、標準入力から 1 行入力されるごとに、その時点でのリストの内容を先頭から順に文字列として並べたものと改行文字を出力する。「位置」がその時点でのリストの長さより大きい場合には、末尾に挿入するものとせよ。

実行例

Big
2 n
4 o 　/入力終わり/
Big
Bing
Bingo

ink
0 L
42 d
4 e /入力終わり/

ink
Link
Linkd
Linked

該当のソースコード

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

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

/* 要素e,次に繋がるノードxを示すノードを作る */

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

/* リストに要素eのノードを挿入*/

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

/* 表示 */

void print_list(list l) {
  while ( l != NULL) {
    printf("%d", l->element);
    l = l->next;
  }
}

int main() {
  int i,　s;
  char c, buf[128];
  list l ;
/* リストlの初期化 */
  l = (struct node *) malloc (sizeof (struct node) );
  l ->next =NULL;

  fgets(buf,sizeof(buf),stdin);　/* ← 1 行目を buf に読み込み */  　
　for(i=0; (c = buf[i])!='\n'; ++i) {/* ← 1 文字ずつ処理する for 文 */    
insert(&l,c);/* ※ここで c をリスト l の末尾に挿入 */
    l=l->next;
  }
  print_list(l);
  while(fgets(buf,sizeof(buf),stdin) != NULL) {/* ← 2 行目以降を順に buf に読み込み */
    sscanf(buf,"%d %c", &i, &c);
    for(s = 0 ;s < i ;s++){
      l=l->next;
}
    insert(&l,c);/* ※ここでリスト l の i 番目に c を挿入 */
      print_list(l);
  }

  return 0;
}

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

unix gcc 4.8.5

Comments

[jimbe]

デバッガに頼る前に、コードを見直して頭の中でシミュレートしてみては如何でしょうか。

> insert(&l,c);/* ※ここで c をリスト l の末尾に挿入 */

insert は

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

ではありませんか？

ですので変数 l は insert を呼んでいる for の中で
> l=l->next;
として書き換えてしまっていますが、それ以降の処理はできますか？

ついでに、 insert が先頭に追加してそのアドレスを設定してくれるのならば、1行目の処理の際は文字列の最後から先頭に向かって処理をして行けば、アドレスの処理などしなくても、最後にはリストの先頭が設定されていることになるはずです。

なお、 fgets は読み込んだ"サイズ-1"バイトの中に改行が無かった場合は改行コード無しで戻りますので、改行コードまで処理をするという条件では終わらない可能性があります。

[jimbe]

過去問見ると課題やってるだけなんですね…。

Answer 1

表示の関数の不具合とか「頭のある連結リスト」の頭が無さそうとかは大丈夫だったんでしょうか。

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

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

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 printlist(list l) {
  for( ; l != NULL; l=l->next) printf("%c", l->element);
  printf("\n");
}

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

  struct node head;
  head.next = NULL; //文字列の先頭ノードのアドレス
  for(int i=strlen(buf)-1; i>=0; i--) insert(&head.next, buf[i]);

  printlist(head.next);

  while(fgets(buf,sizeof(buf),stdin) != NULL) {
    int index;
    char chara;
    sscanf(buf,"%d %c", &index, &chara);

    list np = &head;
    for(int i=0; i<index && np->next!=NULL; i++, np=np->next);
    insert(&np->next, chara);

    printlist(head.next);
  }

  return 0;
}

Answer 2

Segmentation fault (core dumped)

Main.cpp:46:32: warning: treating Unicode character as whitespace [-Wunicode-whitespace]
  fgets(buf,sizeof(buf),stdin);　/* ← 1 行目を buf に読み込み */  　
                               ^~
Main.cpp:46:78: warning: treating Unicode character as whitespace [-Wunicode-whitespace]
  fgets(buf,sizeof(buf),stdin);　/* ← 1 行目を buf に読み込み */  　
                                                                  ^~
Main.cpp:47:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace]
　for(i=0; (c = buf[i])!='\n'; ++i) {/* ← 1 文字ずつ処理する for 文 */    
^~
3 warnings generated.

Answer 3

質問者様のコードに全角スペースが含まれているのでそちらは削除してください。

Segmentation Faultが発生してしまいました。

for(i=0; (c = buf[i])!='\n'; ++i) {/* ← 1 文字ずつ処理する for 文 */    
    insert(&l,c);/* ※ここで c をリスト l の末尾に挿入 */
    l=l->next;
  }

最後の l = l->next のせいで毎回リストの最後に戻ってきています。
その後のwhile文の中でまたl = l->nextをしていますが、リストの最後のl->nextはNULLです。
ここでは l のアドレスにNULLを代入することになりますのでアクセス例外が起きてしまいます。

ですので、一行目の処理は以下のようにしたほうが良いかと思います。

fgets(buf,sizeof(buf),stdin);/* ← 1 行目を buf に読み込み */ 
    for(i=0; (c = buf[i])!='\n'; ++i) {/* ← 1 文字ずつ処理する for 文 */   
        if (i == 0) {
            l->element = buf[0];       /* 先頭リストのelementに不定の値を入れない処理 */
        }
        else {
            insert(&l, c);/* ※ここで c をリスト l の末尾に挿入 */
        }
    }
    last = l;

Comments

[jimbe]

"next" ですので、『リストの頭』と言うよりは『リストの最後』の方がリンクのイメージに合う気がします。

[ALOHAMS]

片方向リストはあるノードの挿入や削除が得意ではありません。
できれば双方向リストなどを採用した方が楽かもしれません。
参考：https://same.blog/2022/01/13/c%E8%A8%80%E8%AA%9E%E5%8F%8C%E6%96%B9%E5%90%91%E3%83%AA%E3%82%B9%E3%83%88%E3%81%A8%E3%81%9D%E3%81%AE%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C%E8%BF%BD%E5%8A%A0%E3%80%81%E5%89%8A%E9%99%A4%E3%80%81/#toc7

[jimbe]

課題でしょうから、リストの構造の変更は出来なさそうですが。

[aoba-purines]

解決しました。
ありがとうございました。

[ALOHAMS]

Jimbe様
>"next" ですので、『リストの頭』と言うよりは『リストの最後』の方がリンクのイメージに合う気がします。
確かにそちらの方がイメージに合いますね。回答本文を修正しました。

>課題でしょうから、リストの構造の変更は出来なさそうですが。
void insert(list l, elementtype e);用いて～と書いてありましたね。失礼しました。