算法 - 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.题主你在main函数里面声明了一个Node数组，大小为1e5+2，栈的空间较小，而你声明的数组过大，导致了栈溢出，应该放在main函数外面才行，全局空间。
2.发现题主你代码有问题啊，QAQ，还一直在找是不是指针访问了未申请的内存的原因导致的段错误，发现你代码好像样例都没过

和标准输出不一样

你的算法好像有点问题。。。。。

我终于找到坑点了！！！N不一定是链表的结点总数, 所以你用N/K,得不到正确的次数，可能有几条链表一个数据里面，要针对那条链表获得节点数
AC代码，在你的上面改的

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

struct Node {
    int addr;
    int data;
    int nextAddr;
    Node *ne;
    void printNode() {
        if(nextAddr != -1) {
            printf("%05d %d %05d\n", addr, data, nextAddr);
        } else {
            printf("%05d %d -1\n", addr, data);
        }
    }
    Node(int a = -1, int b = -1, int c = -1, Node* d = NULL) : addr(a), data(b), nextAddr(c), ne(d) {}
};
Node nodes[100005];

int main(int argc, const char * argv[]) {
    int N, K, A;
    //freopen("D:\\in", "r", stdin);
    //freopen("D:\\out", "w", stdout);
    cin >> A >> N >> K;
    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];
    //cout << head << endl;
    Node *temp = &nodes[A];
    head-> ne = temp;
    int cnt_n = 1;
    while (temp->nextAddr != -1 && temp) {
        temp-> ne = &nodes[temp->nextAddr];
        temp = temp->ne;
        ++cnt_n;
    }
    temp -> ne = NULL;
    Node* test = head;
    //cout << "linked list\n";
    //cout << test << endl;
    
    //while (test -> ne != NULL)
    //{
    //    printf("%05d\n",(test -> ne) -> nextAddr);
    //    test = test -> ne;
    //}
    
    int time = cnt_n/K;
    // 链表翻转
    Node *tempHead = head;
    for (int i = 1; i <= time; ++i)
    {
        Node *p1 = tempHead->ne;
        for (int j = 1; j <= K - 1; ++j)
        {
            Node *p2 = p1->ne;
            p1->ne = p2->ne;
            p1 -> nextAddr = p2 -> ne -> addr;
            p2->ne = tempHead->ne;
            p2 -> nextAddr = tempHead -> ne -> addr;
            tempHead->ne = p2;
            tempHead -> nextAddr = p2 -> addr;
        }
        tempHead = p1;
    }
    //cout << "linked list\n";
   // cout << test << endl;
    
    //test = head;
    //while (test -> next != NULL)
    //{
    //    printf("%05d\n",(test -> next) -> nextAddr);
    //    test = test -> next;
    //}
    
    // 输出链表
    // right code
    Node *first = head->ne;
    while (first  != NULL) {
        first->printNode();
        first = first->ne;
    }
    return 0;
}

你原来的代码，交换节点部分也有点问题，你只是交换了next指针，而没有修改每个Node里面的nextAddr。

Answer 2

大概看了一下，假设只有一个节点时，下面这段代码可能出现错误：

// 链表翻转
Node *tempHead = head;
for (int i = 0; i < time; ++i)
{
    Node *p1 = tempHead->next;       // p1 指向链表中惟一一个节点
    for (int j = 0; j < K - 1; ++j)
    {
        Node *p2 = p1->next;         // p2 == NULL
        p1->next = p2->next;         // p2->next 报错
        p2->next = tempHead->next;
        tempHead->next = p2;
    }
    tempHead = p1;
}

具体错误建议单步跟踪，看执行到哪一行报错。

另外下面这段要干嘛没看懂……判断条件难道不是永远为假么……

if(nodes[A].addr != A) {
    return 0;
}