描述:
首先题目的描述是：（这是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 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 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;
}