pat-1052 Linked List Sorting (64bit) (25分)

pat-1052 Linked List Sorting (64bit) (25分)
在这里插入图片描述

参加晴神的《算法笔记》
大概说几点我遇到的问题以及总结：
1.pat链表内容的题目还是挺常规的，除非是工程应用或者leetcode的题目，它会使用指针实现数组。但是我做到现在，pat的题目都是：思量是链表，但是实现的是静态的方式。（xxx这里我会给一些链表的模板，还是很简单的。这里留一个空）

2.关于代码的一个小细节，因为输入的问题，导入卡了一会

//处理输入 
    for(int i=0;i<n;i++){
        //这里注意：底下两行需要去隔开写，不然cin流一次读入。那么其实第二行并没有更新到。
		cin>>address;
        cin>>Node[address].data>>Node[address].next;
		//地址的点对用的地址 
		Node[address].address=address;
	}

当时是我直接一次性的进行读入，那么结果就会出错。因为第二行的address并没有拿到值。只有在一行结束时，address才确定存在一个数值型数据。

完整的代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
struct node{
	int address;
	int data;
	int next;
	bool flag;
}Node[N];
bool cmp(node a,node b){
	//先去判断无效节点，然后对数值进行排序 
	if(a.flag==false||b.flag==false) return a.flag>b.flag;
	else return a.data<b.data;//从小到大进行排序
} 
int main(){
	for(int i=0;i<N;i++){
		Node[i].flag=false;//设置对所有点进行排序
	}
	int n,begin,address;
	cin>>n>>begin;	
	//处理输入 
    for(int i=0;i<n;i++){
        //这里注意：底下两行需要去隔开写，不然cin流一次读入。那么其实第二行并没有更新到。
		cin>>address;
        cin>>Node[address].data>>Node[address].next;
		//地址的点对用的地址 
		Node[address].address=address;
	}
	//起始地址进行遍历 
    int cnt=0,p=begin;
	//对链表开始遍历，然后选取出适合的节点 
	while(p!=-1){
		Node[p].flag=true;//如果没有访问到-1，
		//那么表示的当前的点是有效节点 
		cnt++;
		p=Node[p].next;//更新当前节点的位置 
	}	
	if(cnt==0) cout<<"0 -1";//表示根本没有有效节点 
	else{
		//对所有节点进行排序 
		sort(Node,Node+N,cmp);//对链表的节点进行遍历
		//数组的格式具有要求,现输出一个节点的值 
		printf("%d %05d\n",cnt,Node[0].address);
		for(int i=0;i<cnt;i++){
            //注意下标的位置 
			if(i!=cnt-1){
				printf("%05d %d %05d\n",Node[i].address,Node[i].data,Node[i+1].address);
			}
			else{
				printf("%05d %d -1\n",Node[i].address,Node[i].data);
			}
		} 
	}
	return 0;
}

本文链接：https://blog.csdn.net/weixin_44110100/article/details/108597723

智能推荐

PAT.A1052 Linked List Sorting

返回目录样例（可复制）注意点本题节点数为0时(即开始地址为start=-1)需要特判输出，本题不会出现开始地址不为-1，但给出的所有节点都没出现开始地址的节点的情况...

PAT-A-1052 Linked List Sorting

//着实被姥姥的测试用例惊叹到。 A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next po...

10. 查询小米Note2共有几次订单，显示产品名称，订单数量

...

新发的日常小实验——使用IETester测试不同IE版本的浏览器，测试网页JS的兼容性（console未定义兼容测试）

文章目录一、痛点：IE兼容测试二、关于IETester 三、IETester下载四、写个html测试js的console接口五、测试结果六、js兼容处理一、痛点：IE兼容测试之前使用.Net的Winform桌面应用框架做了一个PC版的迷你浏览器（使用IE内核），方便拉起网页支付。有用户反馈打开支付页面报了如下的错：“console”未定义到底是多么老旧的I...

linux下搭建nginx及配置

文章目录下载nginx 解压nginx资源包准备编译环境安装编译查找安装路径并启动nginx 浏览器访问下载nginx 下载地址：https://nginx.org/en/download.html 这里用的是nginx-1.16.1版本解压nginx资源包准备编译环境安装编译查找安装路径并启动nginx 浏览器访问 http://IP...

pat-1052 Linked List Sorting (64bit) (25分)

智能推荐

猜你喜欢