算法 - c++ OJ出现段错误

Question

RT，我在做PAT的一道链表翻转题，本地调试没问题，但是提交一直出现段错误。十分不解，望各路神仙帮忙看看，先谢过了~

//
//  main.cpp
//  反转链表
//
//  Created by Jzzhou on 16/8/12.
//  Copyright © 2016年 Jzzhou. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

struct Node {
    int addr;
    int data;
    int nextAddr;
    Node *next;
    void printNode() {
        if(nextAddr != -1) {
            printf("%.5d %d %.5d", addr, data, nextAddr);
        } else {
            printf("%.5d %d -1", addr, data);
        }
    }
};

int main(int argc, const char * argv[]) {
    int N, K, A;
    cin>>A>>N>>K;
    if (N == 0) {
        return 0;
    }
    Node nodes[100002];
    for (int i = 0; i < N; ++i) {
        int addr, data, nextAddr;
        cin>>addr>>data>>nextAddr;
        nodes[addr].addr = addr;
        nodes[addr].data = data;
        nodes[addr].nextAddr = nextAddr;
    }
    
    Node *head = &nodes[100001];
    if(nodes[A].addr != A) {
        return 0;
    }
    // 生成链表
    Node *temp = &nodes[A];
    head->next = temp;
    while (temp->nextAddr != -1) {
        temp->next = &nodes[temp->nextAddr];
        temp = temp->next;
    }
    temp->next = NULL;
    
    int time = N/K;
    // 链表翻转
    Node *tempHead = head;
    for (int i = 0; i < time; ++i)
    {
        Node *p1 = tempHead->next;
        for (int j = 0; j < K - 1; ++j)
        {
            Node *p2 = p1->next;
            p1->next = p2->next;
            p2->next = tempHead->next;
            tempHead->next = p2;
        }
        tempHead = p1;
    }
    // 输出链表
    Node *first = head->next;
    while (first != NULL) {
        first->printNode();
        first = first->next;
        if (first != NULL) {
            cout<<endl;
        }
    }
    
    return 0;
}

Answer 1

聞いてください、ローカルのコンパイルには問題はありませんでしたが、私のコンパイルは間違っていました。
1. メイン関数内で 1e5 2 のサイズの Node 配列を宣言しました。スタック領域が小さく、宣言した配列が大きすぎるため、メイン関数の外側に配置する必要があります。はい、グローバル空間です。
2. QAQ さんのコードに問題があることがわかりました。適用されていないメモリにアクセスするポインターによって引き起こされるセグメンテーション違反を探しています。コードがサンプルに失敗していることがわかりました。

は標準出力と同じではありません

アルゴリズムに問題があるようです。 。 。 。 。

ついに落とし穴を発見しました！ ！ ！ N不一定是链表的结点总数 なので、N/K を使用すると正しい回数が得られません。1 つのデータ内に複数のリンクされたリストが存在する可能性があり、そのリンクされた 节点数
AC コードを取得する必要があります。上で変更したリスト

リーリー

元のコードには、ノード交換部分にも問題があります。各ノードの nextAddr を変更せずに、次のポインタを交換しただけです。

Answer 2

簡単に見てみると、ノードが 1 つしかないと仮定すると、次のコードにはエラーがある可能性があります:

リーリー

単一のステップで特定のエラーを追跡し、エラーが報告された実行行を確認することをお勧めします。

あと、次の段落の意味が分かりません…判定条件は常に偽ではないでしょうか…

リーリー