PAT 1025反转链表问题求大神解答

Question

#include <iostream>
#include <string.h>
#include <string>
using namespace std;
struct Node{
    string Address;        //结点地址
    int Data;               //改结点存储的整数数据
    string Next;           //下一个结点的地址
};
int main()
{
    std::ios::sync_with_stdio(false);
    string head;
    int N,K;
    cin >> head >> N >> K;
    struct Node node[N];
    string tempstore;
    int flag = 0;
    for(int i = 0;i < N;i++)
        cin >> node[i].Address >> node[i].Data >> node[i].Next;
    struct Node storeNode[N];
    for(int i = 0;i < N;i++)                //找出首结点存入storeNode
    {
        if(head == node[i].Address)
        {
            storeNode[0] = node[i];
            flag = 1;
            break;
        }
    }
    if(flag == 0)
        return 0;

    for(int i = 0;i < N;i++)                //找出接下来的结点按顺序存入
    {
        flag = 0;
        if(storeNode[i].Next != "-1")
        {

            for(int j = 0;j < N;j++)
            {
                if(storeNode[i].Next == node[j].Address)
                {
                    flag = 1;
                    storeNode[i+1] = node[j];
                    break;
                }
            }
            if(flag == 0)       //如果没有找到下一个结点地址则退出查找
            {
                N = i+1;
                break;
            }
        }
        else{
            N= i+1;
            break;

        }

    }
    if(N >= K)
    {

        struct Node temp;
        int t = N;
        int i = 0,j;
        while(t >= K)
        {
            j = i;
            while(j < (i+K)/2 )
            {
                temp = storeNode[j];
                storeNode[j] = storeNode[i+K-j-1];
                storeNode[i+K-j-1] = temp;
                j++;
            }
            t-=K;
            i+=K;
        }
        int k;
        for(k = 0;k < N-1;k++)
        {
            storeNode[k].Next = storeNode[k+1].Address;
        }
        storeNode[k].Next = "-1";
    }
    for(int i = 0;i < N;++i)
        cout << storeNode[i].Address << ' ' << storeNode[i].Data << ' ' << storeNode[i].Next << endl;
    return 0;
}

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

这是一个使用C语言实现的PAT(反转链表)问题。这个程序首先读取输入的数据，然后构建一个指向第一个节点的指针。然后它遍历整个列表，每次只移动到下一个节点，并将其存储在新的指针中。最后，它将最后一个节点（即最后一个节点）的地址设为"-1"以表示它已经处理完毕。

以下是完整的C代码：

#include <iostream>

// 结构体定义
struct Node {
    std::string address;      // 结点地址
    int data;                  // 改结点存储的整数数据
    std::string next;          // 下一个结点的地址
};

int main() {
    std::ios::sync_with_stdio(false);

    // 读取输入
    std::string head;
    int n, k;
    std::cin >> head >> n >> k;
    struct Node node[n];

    // 构建第一个节点
    std::string tempstore;
    for (int i = 0; i < n; ++i) {
        std::cin >> node[i].address >> node[i].data >> node[i].next;
        if (node[i].address == head) {
            node[i].next = "";
            break;
        } else {
            tempstore = node[i].address;
        }
    }

    // 遍历并反转链表
    for (int i = 0; i < n - 1; ++i) {
        node[i + 1].next = node[i].address;
        node[i].address = "";
    }
    node[n - 1].next = "";

    // 输出结果
    for (int i = 0; i < n; ++i) {
        std::cout << node[i].address << " " << node[i].data << " " << node[i].next << std::endl;
    }

    return 0;
}

注意：这段代码没有包含任何测试用例或注释，所以你可能需要自己添加一些逻辑来确保它能够正常工作。此外，由于这是一道关于反转链表的问题，你可以考虑优化算法，例如使用迭代而不是递归。