84669 Lernen von Personen
152542 Lernen von Personen
20005 Lernen von Personen
5487 Lernen von Personen
7821 Lernen von Personen
359900 Lernen von Personen
3350 Lernen von Personen
180660 Lernen von Personen
48569 Lernen von Personen
18603 Lernen von Personen
40936 Lernen von Personen
1549 Lernen von Personen
1183 Lernen von Personen
32909 Lernen von Personen
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<
ringa_lee
题主你本地编译居然没有问题,,,,我编译就错。1.题主你在main函数里面声明了一个Node数组,大小为1e5+2,栈的空间较小,而你声明的数组过大,导致了栈溢出,应该放在main函数外面才行,全局空间。2.发现题主你代码有问题啊,QAQ,还一直在找是不是指针访问了未申请的内存的原因导致的段错误,发现你代码好像样例都没过和标准输出不一样
1e5+2
你的算法好像有点问题。。。。。
我终于找到坑点了!!!N不一定是链表的结点总数, 所以你用N/K,得不到正确的次数,可能有几条链表一个数据里面,要针对那条链表获得节点数AC代码,在你的上面改的
N不一定是链表的结点总数
节点数
#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; }
你原来的代码,交换节点部分也有点问题,你只是交换了next指针,而没有修改每个Node里面的nextAddr。
大概看了一下,假设只有一个节点时,下面这段代码可能出现错误:
// 链表翻转 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; }
题主你本地编译居然没有问题,,,,我编译就错。
![](http://img.php.cn/upload/image/000/000/000/6f2ae6fe7601a99063e4e321223e24cc-0.png)
1.题主你在main函数里面声明了一个Node数组,大小为
1e5+2
,栈的空间较小,而你声明的数组过大,导致了栈溢出,应该放在main函数外面才行,全局空间。2.发现题主你代码有问题啊,QAQ,还一直在找是不是指针访问了未申请的内存的原因导致的段错误,发现你代码好像样例都没过
和标准输出不一样
你的算法好像有点问题。。。。。
我终于找到坑点了!!!
N不一定是链表的结点总数
, 所以你用N/K,得不到正确的次数,可能有几条链表一个数据里面,要针对那条链表获得节点数
AC代码,在你的上面改的
你原来的代码,交换节点部分也有点问题,你只是交换了next指针,而没有修改每个Node里面的nextAddr。
大概看了一下,假设只有一个节点时,下面这段代码可能出现错误:
具体错误建议单步跟踪,看执行到哪一行报错。
另外下面这段要干嘛没看懂……判断条件难道不是永远为假么……