数据结构和算法 - 反转链表的算法题，c++实现，有疑问求教？

首先题目的描述是：（这是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;
}

巴扎黑2803 days ago488

数据结构和算法 - 反转链表的算法题，c++实现，有疑问求教？

reply all(1)I'll reply