算法 - 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;
}