連結リストを実装したいのですが、segmentation fault: 11と出てしまいます。

Question

前提・実現したいこと

以下の命令を受けつける双方向連結リストを実装したいです。

insert x: 連結リストの先頭にキー x を持つ要素を継ぎ足す。
delete x: キー x を持つ最初の要素を連結リストから削除する。そのような要素が存在しない場合は何もしない。
deleteFirst: リストの先頭の要素を削除する。
deleteLast: リストの末尾の要素を削除する。

以下入力例

7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5

以下出力例

6 1 2

この機能の実装中に以下のエラーメッセージが発生しました。

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

以下の３行の入力後、segmentation fault: 11のメッセージが出てしまいます。何を改善したらこれはなくなるのでしょうか。

2
delete 2
insert 1
Segmentation fault: 11

該当のソースコード

#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node{
    int key;
    Node *next, *prev;
};

Node *nil;

Node* listSearch(int key){
    Node *cur = nil->next;//
 while(cur != nil && cur->key != key ){
     cur = cur->next;
 }  
 return cur;
}

void init() {
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void insert(int key){
    Node *x = (Node *)malloc(sizeof(Node));
    x->next = nil->next;
    x->prev = nil;
    nil->next = x;
    nil->next->prev = x;
}

void deleteNode(Node *t){
    if (t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
} 

void deletefirst(){
    deleteNode(nil->next);
    }

void deletelast(){
    deleteNode(nil->prev);
}

void deletekey(int key){
    deleteNode(listSearch(key));
}

void printlist(){
    Node *cur = nil->next;
    int isf = 0;
    while(1){
        if(cur == nil) break;
        if(isf++ > 0) printf("");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
}

int main(){
    int i, n, key;
    scanf("%d", &n);
    //int size = 0;
    //int np = 0, nd = 0;
    char com[20];
    for(i=0;i<n;i++){
        scanf("%s%d", com, &key);
        if(com[0] == 'i'){ insert(key); 
        //np++; size++;
        }
        else if(com[0] == 'd'){
            if(strlen(com) > 6) deletefirst();
            else if(com[6] == 'F') deletelast();
        }else{
            deletekey(key); //nd++;
        }
        //size--;
        }  

    printlist();
    return 0;

}

補足情報

AOJのアルゴリズムとデータ構造の問題です。
ALDS1_3_C: Doubly Linked List

Answer 1

init を呼んでいないからでは？

Comments

[Zuishin]

とりあえず聞かれたことだけ答えましたが、他にも怪しいところがいくつかあります。よくソースを追ってください。

[goro_gnm]

回答ありがとうございます。
init 抜けていました。
また他に自分が気づいたところを直したところ、insert delete のみの命令であれば実行できるようになりました。
ただ deleteFirst deleteLast が命令に入るとできません。
このscanfの方法だと、命令のあとに int が入らないことに原因があるように思います。だとすると、どのようにしたらいいのでしょうか。
cを触ったことがある程度でc++を始めたばかりです。よろしくお願いします。

#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node{
int key;
Node *next, *prev;
};

Node *nil;

Node* listSearch(int key){
Node *cur = nil->next;//
while(cur != nil && cur->key != key ){
cur = cur->next;
}
return cur;
}

void init() {
nil = (Node *)malloc(sizeof(Node));
nil->next = nil;
nil->prev = nil;
}

void insert(int key){
Node *x = (Node *)malloc(sizeof(Node));
x->key = key;
x->next = nil->next;
nil->next = x;
nil->next->prev = x;
x->prev = nil;
}

void deleteNode(Node *t){
if (t == nil) return;
t->prev->next = t->next;
t->next->prev = t->prev;
free(t);
}

void deletefirst(){
deleteNode(nil->next);
}

void deletelast(){
deleteNode(nil->prev);
}

void deletekey(int key){
deleteNode(listSearch(key));
}

void printlist(){
Node *cur = nil->next;
int isf = 0;
while(1){
if(cur == nil) break;
if(isf++ > 0) printf("");
printf("%d", cur->key);
cur = cur->next;
}
printf("\n");
}

int main(){
int i, n, key;
scanf("%d", &n);
//int size = 0;
//int np = 0, nd = 0;
init();
char com[20];
for(i=0;i<n;i++){
scanf("%s%d", com, &key);
if(com[0] == 'i'){ insert(key);
//np++; size++;
}
else if(com[0] == 'd'){
if(strlen(com) > 6){
if(com[6] == 'F') deletefirst();
else if(com[6] == 'L') deletelast();
}else{
deletekey(key); //nd++;
}
//size--;
}
}

printlist();
return 0;

}

[Zuishin]

この質問は「連結リストを実装したいのですが、segmentation fault: 11と出てしまいます。」で、それは解決したと思います。他にも問題はありますが、それはまた別の問題なので、まず自分でソースを追ってデバッグしてください。それでわからなければまた新たに質問してください。

連結リストが欲しいというだけなら std::list でいいはずです。学習のために組んでいるんですよね？ デバッグを全部人にやらせたのでは学習効果が薄いのでは？

[pepperleaf]

質問文、更新しませんか?
インデントが崩れて見ずらいです。

[goro_gnm]

＞Zuisjin さん
新たな質問にしなかったのは私の怠惰でした。失礼しました。
回答ありがとうございました。

私は自分である程度考えてわからないときはデバックをしてもらった方が効率がいいかなと思っておりますが、まあ人それぞれですね。

＞pepperleaf さん
私も投稿してから気づきました。ご指摘ありがとうございます。

[Zuishin]

自分でしないなら std::list を使うのが一番効率的ですね。既に完成してるので。完成した連結リストのソースも探せばいくらでもあるはずです。