Linked List Sorting (25)

思路 地址映射把一条有效的链条找到，然后排序这个链条然后输出。
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

#ifndef debug
ifstream ifile("case.txt");
#define cin ifile
#endif


struct link
{
    int data;
    int adr;
    int nAdr;
};

bool Cmp(struct link & a, struct link & b)
{
    return a.data < b.data;
}

int main()
{
    int n, startAdr;
    while (cin >> n >> startAdr)
    {
        vector<struct link> v(n);
        int mark[100000] = { 0 };// 地址映射
        vector<struct link> valid;
        int index = 0;
        for (int i = 0; i < n; i++)
        {
            int tmp;
            cin >> v[i].adr >> v[i].data >> v[i].nAdr;
            mark[v[i].adr] = i;
            if (v[i].adr == startAdr)
            {
                index = i;
            }
        }
        //int validNum = 0;
        for (int i = index; v[i].nAdr!=-1;)
        {
            valid.push_back(v[i]);
            i = mark[v[i].nAdr];
            index = i;
        }
        valid.push_back(v[index]);// 添加 -1这个节点
        sort(valid.begin(), valid.end(), Cmp);
        // 输出
        if (startAdr == -1)
        {
            cout << 0 << " " << -1 << endl;
            continue;
        }
        cout << valid.size() << " " << setfill('0') << setw(5) << valid[0].adr << endl;
        for (int i = 0; i < valid.size(); i++)
        {
            cout << setfill('0') << setw(5) << valid[i].adr;
            if (i != valid.size() - 1)
                cout << " " << valid[i].data << " " << setfill('0') << setw(5) << valid[i + 1].adr << endl;
            else
                cout << " " << valid[i].data << " " << -1 << endl;
        }
    }
    system("pause");
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

#define MAX 100009

//我习惯邓俊辉版数据结构的双链表(有不存数据的头、尾节点),各种操作都很方便
//不过本题只需要把链表更新为双链表,然后进行插入排序即可
int N, key[MAX], nex[MAX], pri[MAX], first;
int len = 1;

void read_list() {
	memset(nex, -1, sizeof(nex));
	memset(pri, -1, sizeof(pri));

	cin >> N >> first; int ad;
	for (int i = 1; i <= N; ++i) {
		cin >> ad; 
		cin >> key[ad] >> nex[ad];
	}
}

void set_prior() {//把单链表变为双链表,顺便统计实际在链表中的节点个数
	int p = first, q = nex[first];
	while (q != -1) {
		++len;
		pri[q] = p;
		p = q; q = nex[q];
	}
}

void insertion_sort() {//插入排序,循环内两个if-else是为了应对链表两端的特殊情况
					   //如果有不存储数据的头尾节点,则这两个if-else都可以简化,不过本题就不讨论这个了
	for (int p = nex[first]; p != -1; p = nex[p])//从第2个节点到最后一个节点
		if (key[pri[p]] > key[p]) {//发现逆序,则
			int q = pri[p]; int pp = q;
			//跳出循环后,q指向<=key[p]的最右者
			for (; q != -1 && key[q] > key[p]; q = pri[q]);

			//摘除p
			if (nex[p] != -1) { nex[pp] = nex[p]; pri[nex[p]] = pp; }//常规
			else nex[pp] = -1;//p指向最后一个节点本身

			//插入q后方
			pri[p] = q; 
			if (q != -1) { nex[p] = nex[q]; pri[nex[q]] = p; nex[q] = p; }//常规
			else { nex[p] = first; pri[first] = p; first = p; }//q指向第一个节点的前端

			p = pp;//重置p,以便进行下一轮遍历
		}
}

void out_res() {
	if (first != -1) {//有一个坑爹的样例把头节点设置成NULL
		printf("%d %05d\n", len, first);
		int p = first, q = nex[first];
		while (q != -1) {
			printf("%05d %d %05d\n", p, key[p], q);
			p = q; q = nex[q];
		}
		printf("%05d %d %d", p, key[p], q);
	}
	else cout << 0 << " " << -1;
}

int main()
{
	read_list();
	set_prior();
	insertion_sort();
	out_res();

	return 0;
}

a = input().split()
if a[1] == '-1':
    print(0,-1)
    import sys
    sys.exit(0)
d,e = {},{}
for i in range(int(a[0])):
    b = input().split()
    d[b[0]] = b[1:]
while a[1] != "-1":
    e[int(d[a[1]][0])],a[1] = [a[1],d[a[1]][1]],d[a[1]][1]
m = sorted(e)
print(len(e),e[m[0]][0])
for i in range(len(e) - 1):
    print(e[m[i]][0],m[i],e[m[i + 1]][0])
print(e[m[-1]][0],m[-1],-1)

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef struct sNode {
	int Add, Key, Next;
	sNode(int add, int key, int next) :
		Add(add), Key(key), Next(next) {}
}Node;

vector<Node> List;
inline bool cmp(int A, int B) { return List[A].Key < List[B].Key; }

int main(int argc, const char* argv[]) {
	ios::sync_with_stdio(false);
	map<int, int> add2index;
	int N, Head;
	cin >> N >> Head;
	for (int i = 0;i < N;i++) {
		int add, val, next;
		cin >> add >> val >> next;
		List.push_back(Node(add, val, next));
		add2index[add] = i;
	}
	int p = Head;
	vector<int> Output;
	while (p + 1) {
		Output.push_back(add2index[p]);
		p = List[add2index[p]].Next;
	}
	sort(Output.begin(), Output.end(), cmp);
	int len = Output.size() - 1;
	if (len + 1) {
		printf("%d %05d", len + 1, List[Output[0]].Add);
		for (int i = 0;i < len;i++)
			printf("\n%05d %d %05d", List[Output[i]].Add, List[Output[i]].Key, List[Output[i + 1]].Add);
		printf("\n%05d %d -1", List[Output[len]].Add, List[Output[len]].Key);
	}
	else cout << "0 -1";

	//system("pause");
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
struct Node{                                                 //定义静态链表
    int next,key;
}node[maxn];
int order[maxn];                                             //开一个数组按顺序存储有效结点
bool cmp(int a,int b){                                       //按要求以key从小到大排序
    return node[a].key<node[b].key;
}
int main(){
    int n,head,num,count=0;
    cin>>n>>head;
    for(int i=0;i<n;i++){
        cin>>num;
        cin>>node[num].key>>node[num].next;
    }
    if(head==-1){                                            //结点全部无效，不在链表中，输出特例并退出程序
        printf("0 -1");
        return 0;
    } 
    for(int i=0,num=head;num!=-1;num=node[num].next,i++){    //以给出首地址遍历链表，将有效结点的地址按顺序存储到数组中
        count++;
        order[i]=num;
    }
    n=count;
    sort(order,order+n,cmp);                                 //给链表结点按key从小到大排序
    printf("%d %05d\n",n,order[0]);                          //输出链表结点个数以及排序后的首地址
    for(int i=0;i<n;i++){
        printf("%05d %d ",order[i],node[order[i]].key);
        if(i!=n-1) printf("%05d\n",order[i+1]);
        else printf("-1\n");                                 //链表最后一个结点的next为null即-1
    }
    return 0;
} 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
	int ad,key,next;
}no[100005];
bool cmp(node a,node b){
	return a.key<b.key;
}
int main(){
	int n,h;
	cin>>n>>h;
	for(int i=0;i<n;i++){
		int t;cin>>t;
		no[t].ad=t;
		cin>>no[t].key>>no[t].next;
	}
	vector<node> r;
	for(int cur=h;cur!=-1;cur=no[cur].next){
		r.push_back(no[cur]);
	}
	if(r.size()==0) {printf("0 -1");return 0;}
	sort(r.begin(),r.end(),cmp);
	printf("%d %05d\n",r.size(),r[0].ad);
	for(int i=0;i<r.size();i++){
		printf("%05d %d ",r[i].ad,r[i].key);
		if(i==r.size()-1) printf("-1\n");
		else printf("%05d\n",r[i+1].ad);		
	}
	return 0;
}

#include<unordered_map>
#include<cstdio>
using namespace std;
class Node{
public:
    int addr;
    int key;
    int nextAddr;
    Node* next;
    Node(int _addr, int _key, int _nextAddr):addr(_addr),key(_key),nextAddr(_nextAddr),next(NULL){}
    Node():next(NULL){}
};
unordered_map<int,Node*> mp;
Node* merge(Node* A, Node* B){
    if(A == NULL) return B;
    if(B == NULL) return A;
    Node* dummy = new Node(-2,0,-1);
    Node* tmp = dummy;
    while(A && B){
        if(A->key < B->key){
            tmp->next = A;
            A = A->next;
        }else{
            tmp->next = B;
            B = B->next;
        }
        tmp = tmp->next;
    }
    tmp->next = (A==NULL? B : A);
    Node* res = dummy->next;
    delete dummy;
    return res;
}
Node* mergeSort(Node* head){
   if(!head || !(head->next)) return head;
   Node *slow=head, *fast = head->next, *partner=head;
   while(fast && fast->next){
       fast = fast->next->next;
       slow = slow->next;
   }
   partner = slow->next;
   slow->next = NULL;
   Node* m1 = mergeSort(head);
   Node* m2 = mergeSort(partner);
   return merge(m1,m2);
}

int main(){
    int N,start,addr,key,nextAddr,count;
    scanf("%d %d",&N,&start);
    Node nodes[N];
    for(int i = 0 ; i < N; i++){
        scanf("%d %d %d",&addr,&key,&nextAddr);
        nodes[i].addr = addr;
        nodes[i].key = key;
        nodes[i].nextAddr = nextAddr;
        mp[addr] = &nodes[i];
    }
    //构建链表
    if(start == -1){//头结点即为NULL的情况
        printf("0 -1");
        return 0;
    }
    Node* head = mp[start];
    count = 1;
    while(head->nextAddr != -1){
        head->next = mp[head->nextAddr];
        head = head->next;
        count++;
    }
    Node* newHead = mergeSort(mp[start]);

    printf("%d %05d\n",count,newHead->addr);
    while(newHead){
        printf("%05d %d",newHead->addr, newHead->key);
        if(newHead->next) printf(" %05d\n",newHead->next->addr);
        else printf(" -1\n");
        newHead = newHead->next;
    }
    return 0;
}

n,start = map(int,input().split())
if start!=-1:
    lst,lst1 = [None,None]*100001,[]
    for i in range(0,n):
        a,b,c = map(int,input().split())
        lst[a]=[b,c]
    while start!=-1:
        lst1.append([start,lst[start][0]])
        start = lst[start][1]      
    lst1.sort(key = lambda x:(x[1]))
    for i in range(0,len(lst1)-1):
        lst1[i].append(lst1[i+1][0])
    print(str(len(lst1))+" "+"%05d"%lst1[0][0])
    for i in range(0,len(lst1)-1):
        print("%05d"%lst1[i][0]+" "+str(lst1[i][1])+" "+"%05d"%lst1[i][2])
    print("%05d"%lst1[len(lst1)-1][0]+" "+str(lst1[len(lst1)-1][1])+" "+"-1")
else:
    print("0 -1")

#要注意本题对算法的复杂度有要求。在提取有效链表的时候需要节省时间的方法。

N,M=map(int,input().split())
inList=[None,None]*100005
for i in range(N):
    a,b,c=map(int,input().split())
    inList[a]=[b,c]
L=[]
while M!=-1:
    L.append([M,inList[M][0]])
    M=inList[M][1]
L.sort(key=lambda x:x[1])
if len(L)==0:
    print(0,-1)
else:
    print('{} {:05d}'.format(len(L),L[0][0]))
    for i in range(len(L)-1):
        print('{:05d} {} {:05d}'.format(L[i][0],L[i][1],L[i+1][0]))
    print('{:05d} {} {}'.format(L[-1][0],L[-1][1],-1))

 // 1052.cpp : 定义控制台应用程序的入口点。
//

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <cmath>

using namespace std;

struct NODE {
	int addr, data, next;
};

vector<NODE> vec;

bool compare(NODE a, NODE b)
{
	return a.data < b.data;
}

const int maxn = 100010;
int s[maxn], dat[maxn];

int main()
{
	int n, start; scanf("%d%d", &n, &start);
	if (start == -1) {
		printf("0 -1");
		return 0;
	}
	for (int i = 0; i < n; i++) {
		int addr, data, next;
		scanf("%d%d%d", &addr, &data, &next);
		if (addr >= 0) {
			s[addr] = next;
			dat[addr] = data;
		}
	}

	while (start != -1) {
		NODE node;
		node.addr = start;
		node.next = s[node.addr];
		node.data = dat[node.addr];
		vec.push_back(node);
		start = s[start];
	}

	sort(vec.begin(), vec.end(), compare);
	for (int i = 0; i < vec.size() - 1; i++)
		vec[i].next = vec[i + 1].addr;
	if(vec.size() > 0)
		vec[vec.size() - 1].next = -1;

	printf("%d %05d\n", vec.size(), vec[0].addr);
	for (int i = 0; i < vec.size(); i++)
		if (i == vec.size() - 1)
			printf("%05d %d %d\n", vec[i].addr, vec[i].data, vec[i].next);
		else
			printf("%05d %d %05d\n", vec[i].addr, vec[i].data, vec[i].next);
	
    return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;
const int maxn=100001;
struct NODE{
	int addr,key,next;
	bool fg;
}node[maxn];
bool cmp(NODE a,NODE b){
	if(a.fg==false || b.fg==false)
		return a.fg>b.fg;
	else
		return a.key<b.key;
}
int main(){
	int n,s;
	for(int i=0;i<maxn;i++){
			node[i].fg=false;;
		}
	//	freopen("G:\\PATdata\\A1052.txt","r",stdin);
	cin>>n>>s;
	int addr;
		for(int i=0;i<n;i++){

			cin>>addr;
			cin>>node[addr].key>>node[addr].next;
			node[addr].addr=addr;
		}
		int cnt=0,p=s;
		while(p!=-1){
			node[p].fg=true;
			cnt++;
			p=node[p].next;
		}


	if(cnt!=0){
			sort(node,node+maxn,cmp);
			s=node[0].addr;
			printf("%d %05d\n",cnt,s);
			for(int i=0;i<cnt;i++){
				if(i<cnt-1)
					printf("%05d %d %05d\n",node[i].addr,node[i].key,node[i+1].addr);
				else
					printf("%05d %d -1\n",node[i].addr,node[i].key);
			}

	}else
		printf("0 -1\n");

	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

struct Node{
    int key, address;
    bool operator<(const Node& that) const {
        return (key<that.key);
    }
};

int data[100000][2];

int main()
{
    // 读入数据
    int N, startAddress, address;
    scanf("%d %d", &N, &startAddress);
    while(N--) {
        scanf("%d", &address);
        scanf("%d %d", &data[address][0], &data[address][1]);
    }
    vector<Node> nodes; address = startAddress; Node tempNode;
    while(address != -1) {
        tempNode.key = data[address][0];
        tempNode.address = address;
        nodes.push_back(tempNode);
        address = data[address][1];
    }

    // 排序输出
    sort(nodes.begin(), nodes.end()); int i;
    if(nodes.size()) {
        printf("%d %05d\n", nodes.size(), nodes[0].address);
        for(i=0; i<nodes.size()-1; i++) {
            printf("%05d %d %05d\n", nodes[i].address,\
                    nodes[i].key, nodes[i+1].address);
        }
        printf("%05d %d -1\n", nodes[i].address, nodes[i].key);
    } else {
        printf("0 -1\n");
    }

    return 0;
}