题目描述

测试

输入样例

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

输出样例

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

代码

一开始看这个形式，地址+值+下一个……模拟内存？？？
就尝试写了一下然后……
有个段错误查不出来了，问老师也没过去……
附上代码请大神指教！

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int data;
    string nextAddr;
    Node() : data(0),nextAddr(nullptr){};
};

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    string firstNodeAddr;
    int N;

/*
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
*/
    cin >> firstNodeAddr >> N; //输入首地址和结点个数

    //地址和结点组成键值对
    map<string, Node> memory;
    for (int i = 0; i < N; i++)
    {
        string addr;
        Node *ptr = new Node;
        cin >> addr >> ptr->data >> ptr->nextAddr;
        memory[addr] = *ptr;
    }

    int nodeNum = 0;                    //计数，用于最后遍历输出
    vector<string> nodeAddrBeenDeleted; //存放被删除的结点的“地址”字符串（在map里能找）
    int nodeBeenDeletedNum = 0;         //被删除节点的个数

    set<int> bucket;                                //用集合存放已有的结点的数据
    bucket.insert(abs(memory[firstNodeAddr].data)); //先将第一个节点的数据放进去
    string addr = firstNodeAddr;
    Node *ptrPrev, *ptrCurrent;
    while (memory[addr].nextAddr != "-1")
    {                                                  //是否遍历到最后
        Node *ptrPrev = &memory[addr];                 //指向前一个结点的指针
        Node *ptrCurrent = &memory[ptrPrev->nextAddr]; //当前判断结点
        if (bucket.count(abs(ptrCurrent->data)) == 0)
        {                                         //若没有这个数据
            bucket.insert(abs(ptrCurrent->data)); //放到数据集合里
            addr = memory[addr].nextAddr;         //继续向下遍历
            nodeNum++;                            //保留结点数+1
        }
        else
        {                                                     //当前数据以有
            nodeAddrBeenDeleted.push_back(ptrPrev->nextAddr); //将当前地址放入被删除容器中
            ptrPrev->nextAddr = ptrCurrent->nextAddr;         //原链表中删除操作
            nodeBeenDeletedNum++;                             //被删除的结点个数+1
        }
        if (nodeNum + nodeBeenDeletedNum >= N)
            break;
    }

    addr = firstNodeAddr; //从第一个节点开始遍历
    //输出存留的链表
    for (int i = 0; i < nodeNum; i++)
    {
        Node *ptr = &memory[addr];
        cout << addr << " " << ptr->data << " " << ptr->nextAddr << endl;
        addr = memory[addr].nextAddr;
    }
    //最后一个单独处理
    cout << addr << " " << memory[addr].data << " -1" << endl;

    //“被删除结点”的链表更改next数据
    for (int i = 0; i < nodeAddrBeenDeleted.size() - 1; i++)
    {
        string addr = nodeAddrBeenDeleted[i];
        Node *ptr = &memory[addr];
        ptr->nextAddr = nodeAddrBeenDeleted[i + 1];
    }
    int n = 0;
    //输出被删除的链表
    for (string addr : nodeAddrBeenDeleted)
    {
        n++;
        Node *ptr = &memory[addr];
        if (n < nodeBeenDeletedNum)
        {
            cout << addr << " " << ptr->data << " " << ptr->nextAddr << endl;
        }
        else
        {
            cout << addr << " " << ptr->data << " -1" << endl;
        }
    }
    return 0;
}

算了我放弃了百度吧……
所以最后还是决定用数组写

如下代码，几个注意点：

1. 结构体中一开始初始化num=2*Maxn，是先将其在排序时放到最后（因为可能会有数据不在链表上），在用链表遍历（一个个next时）遇到的才是在链表上的数据，更改其num即可
2. num相当于记录的是其输出位置（用sort排序就将去重后的链表值放到了前面）

#include<bits/stdc++.h>
using namespace std;
#define Maxn 100000
struct Node{
    int pos,key,next,num=2*Maxn;  //没出现在链表中的直接放到最后
}node[Maxn];
int exist[Maxn];
bool cmp(Node a,Node b){
    return a.num < b.num;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int begin,N,a,cnt1=0,cnt2=0;
    cin >> begin >> N;
    for(int i=0;i<N;i++)
    {
        cin >> a;
        node[a].pos=a;
        cin >> node[a].key >> node[a].next;
    }
    for(int i=begin;i!=-1;i=node[i].next)
    {
        if(!exist[abs(node[i].key)])
        {
            exist[abs(node[i].key)] = 1;
            node[i].num = cnt1; 
            cnt1++;   //计数，相当于在所有数据中找前几个是要输出的
        }else{
            node[i].num = Maxn+cnt2; 
            //最后按num排序后则将不需要的结点放到后面，不输出
            cnt2++;   //标记的是不输出的数量
        }
    }
    sort(node,node+Maxn,cmp);
    int cnt = cnt1+cnt2;
    for(int i=0;i<cnt;i++)
    {
        cout<<setfill('0')<<setw(5)<<node[i].pos<<" "<<node[i].key<<" ";
        if(i!=cnt1-1 && i!=cnt-1)
            cout << setfill('0')<< setw(5) << node[i+1].pos << endl;
        else
            cout << -1 << endl;
    }
}

这里也是新学到两个函数