算法 - c++ OJ出现段错误-Questions et réponses sur le réseau chinois PHP

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

// // main.cpp // 反转链表 // // Created by Jzzhou on 16/8/12. // Copyright © 2016年 Jzzhou. All rights reserved. // #include  #include  #include  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<

#include #include #include 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; }

// 链表翻转 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; }

répondre à tous (2)

伊谢尔伦2017-04-17 14:27:40 2 plancher

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

和标准输出不一样

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

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

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

Comme+0

Ajouter une réponse