博客

①最后一个测试点错误，且只有一分，一般是特值没有处理好，考虑到如果恋上没有结点也应该输出0，-1.

②***







if里注意是两个=，老是错








③应该注意并非所有结点都一定在初始给定的链上，用flag先标志一遍，再排序的同时将有效结点移动左端

④用%05d输出前端补0的五位整数

⑤本题最后输出的next会改变，有必要单独再节点中存储地址。

时隔半年，我又做了一遍！使用静态链表插入排序，好像不能原地进行，因为会断链。由于不带头结点，也不是循环链表，所以头结点尾结点都要单独处理，经过判断后分为三种情况进行插入，难免有些累赘，最后只拿了21分！有几个问题：

1⃣️判断到达最后一个结点的条件一开始写的是londe[p].next!=-1，后来发现这样处理不到最后一个结点，后来又改成lnode[p].adddress!=-1,但是又回取执行lnode[-1]这个结构体，最后的解决办法是：

for(lnode[p].address!=-1)
if(p==-1)
break;

2⃣️插入第一个结点与插入中间结点区别，都是当前要插入的结点小于res的结点，那么怎么区分开来？

第一个办法是设置了标志位，标志已经插入首部，比后边也不用插了，后来发现更好的应该是党插入一个结点时就应该break，结束本次插入；

3⃣️解读：

for(i=0;i<100000;i++){
         lnode[i].address=-1;
         res[i].next=-1;
     }

lnode中没有初始化到的点，默认为0，但是0可能是数组下标，因此应该初始化为-1来判断lnode中的结点已经遍历完成。

在lnode中的最后一个结点，未必是res中的最后一个结点，本应给res最后一个元素赋值-1的，算是暴力法吧

#include<iostream>
#include<iomanip>
using namespace std;
struct node{
    int data,address,next;
}lnode[100000],res[100000];
int main(){
    int i,j,n,root;
    cin>>n>>root;
    if(n==0)
        cout<<"0 -1";
    for(i=0;i<100000;i++){
         lnode[i].address=-1;
         res[i].next=-999;
     }
    for(i=0;i<n;i++){
        cin>>j;
        lnode[j].address=j;
        cin>>lnode[j].data>>lnode[j].next;
    }
    res[root].data=lnode[root].data;
    res[root].address=lnode[root].address;
    int root1=root;
    root=lnode[root].next;
    if(n>1)
    {for(int p=root;lnode[p].address!=-1;p=lnode[p].next){
        int q,pre;
        for(q=root1,pre=root1;q!=-1;q=res[q].next){   //两个链表首结点可能不同
            if(lnode[p].data<res[root1].data){
                res[p].next=root1;        //没有前驱结点，只管后继和值域，不带头结点
                res[p].data=lnode[p].data;
                root1=p;
                res[root1].address=root1;
                break;
            }
            if(lnode[p].data<=res[q].data){              //中间结点的插入操作
                res[pre].next=p;
                res[p].data=lnode[p].data;
                res[p].next=res[q].address;
                res[p].address=p;
                break;
            }
            if(q!=root1)
                pre=res[pre].next;
        }
        if(q==-1){
            res[p].data=lnode[p].data;
            res[p].address=p;
            res[pre].next=p;
        }
        if(lnode[p].next==-1)
            break;
      }
    }
    cout<<n<<" "<<setw(5)<<setfill('0')<<root1<<endl;
    if(n>0)
    {for(int q=root1;res[q].address!=-1;q=res[q].next){
        cout<<setw(5)<<setfill('0')<<res[q].address<<" "<<res[q].data<<" ";
        if(res[q].next!=-1)
            cout<<setw(5)<<setfill('0')<<res[q].next<<endl;
        else{
            cout<<"-1"<<endl;break;
        }
    }
    }
    return 0;
}

#include<algorithm>
using namespace std;
struct node {
    int address, data, next, flag = 0;
}n[100010];
bool cmp(node a, node b)
{
    if (a.flag == b.flag) return a.data < b.data;
    else
        return a.flag > b.flag;
}
int main()
{
    int m, s1, count = 0;
    cin >> m >> s1;
    for (int i = 0; i < m; i++)
    {
        int ad;
        cin >> ad;
        cin >> n[ad].data >> n[ad].next;
        n[ad].address = ad;
    }
    for (int p = s1; p != -1; p = n[p].next)
    {
        n[p].flag = 1;
        count++;
    }
    sort(n, n + 100000, cmp);
    if(count==0)
    {
        printf("0 -1\n");
        return 0;
    }
    printf("%d %05d\n", count, n[0].address);
    for (int i = 0; i < count; i++)
    {
        if (i == count - 1)
            printf("%05d %d -1\n", n[i].address, n[i].data);
        else
        {
            printf("%05d %d %05d\n", n[i].address, n[i].data,n[i+1].address);
        }
    }
    return 0;
} ```