问题描述
首先题目的描述是：（这是pat上的一道题）
给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：00100 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218输出样例：00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1
我的想法是，先把输入的每个节点的数据存入一个类数组中，然后从第一个节点开始，每隔k(即要求反转的子链结点的个数)个将节点放入栈中，再从栈中取出时，他们的顺序就是相反的了，所以把他们再放入队列中。由于N不一定被k整除，所以上述过程循环N/k次，余下的rest=N%k个节点直接按顺序放入队列中
最后让队列按顺序输出每个节点的 节点地址和数据，他的下一个节点的地址不输出，而是由下一个节点把自己的节点地址输入两次而已，注意头尾也就是：第一个节点的地址 第一个节点的数据 /第二个节点的地址第二个节点的地址 第二个节点的数据 /第三个节点的地址第三个节点的地址 第三个节点的数据.........
我的问题是：运行的时候出问题会提示：Exception thrown at 0x0FD6DAF3 (msvcp140d.dll) in ConsoleApplication1025quickandquick.exe: 0xC0000005: Access violation reading location 0x000186A3.
我的想法就是数组元素在栈里倒过之后再倒进队列里，为什么会出错呢，到底犯了什么错误呢？谢谢？
代码如下：
#include 'stdafx.h' #include<iostream> #include<iomanip> #include<string> using namespace std;//Student类class Student {public: int add; int data; int next; Student() {}};//栈template<class Type> class Stack {private: Type *urls; int max_size, top_index;public: Stack(int length_input) {urls = new Type[length_input];max_size = length_input;top_index = -1; } ~Stack() {delete[] urls; } bool push(const Type element) {if (top_index >= max_size - 1) { return false;}top_index++;urls[top_index] = element;return true; } bool pop() {if (top_index < 0) { return false;}top_index--;return true; } Type top() {return urls[top_index]; } bool empty() {if (top_index < 0){ return true;}else{ return false;} }};//队列template<class Type> class Queue {private: Type *data; int head, tail, length;public: Queue(int length_input) {data = new Type[length];length = length_input;head = 0;tail = -1; } ~Queue() {delete[] data; } void push(Type element) {if (tail + 1 < length) { tail++; data[tail] = element;} } Type front() {return data[head]; } void pop() {head = head + 1; }};int main(){ int firstadd; int N; int dist; cin >> firstadd >> N >> dist; Student *list = new Student[100000];//将输入的数据放到Student类的数组中 for (int i = 0; i < N; i++) {int add, data, next;cin >> add >> data >> next;list[add].add = add;list[add].data = data;list[add].next = next; } Queue<Student> queue1(N);Stack<Student> stack(dist); int times = N / dist; int rest = N%dist;//每隔k个，将数组中的元素按原来的顺序倒入栈中，因为//每个节点有记录下一个节点的地址，而且存入时下标就是当前地址，所以可以按照原来的顺序取出 for (int i = 0; i < times; i++) {for (int j = 0; j < dist; j++){ stack.push(list[firstadd]); firstadd = list[firstadd].next;}for (int k = 0; k < dist; k++){ queue1.push(stack.top()); stack.pop();} } for (int i = 0; i < rest; i++) {queue1.push(list[firstadd]);firstadd = list[firstadd].next; } //输出结果 for (int i = 0; i < N; i++) {if (i == 0) { cout.width(5); cout.fill(’0’); cout << queue1.front().add;//运行时的错误break指向这行 cout << ' ' << queue1.front().data << ' '; queue1.pop();}else{ cout.width(5); cout.fill(’0’); cout << queue1.front().add; cout << endl; cout.width(5); cout.fill(’0’); cout << queue1.front().add; cout << ' ' << queue1.front().data << ' '; queue1.pop();} } cout << '-1'; return 0;}
问题解答
回答1：题主的代码中，Queue的构造函数,在执行new操作的时候，length的值还没有定义，所以data数组的长度是未知的（或者直接在new的时候Error）。
Queue(int length_input) { data = new Type[length]; length = length_input; head = 0; tail = -1;}
换一下顺序就可以了：
Queue(int length_input) { data = new Type[length_input]; length = length_input; head = 0; tail = -1;}
