当前位置：首页 > 编程日记 > 正文

1025 反转链表

编程日记 2024-09-07 10:30:00

1. 第一次做链表题，但是这题其实也就是套了个链表的壳子，虽然在结点的结构体里面有下一节点地址next这个属性，但是也只在最初给结点标序号时用到，由于没有真正对链表实施倒序，所以后面输出的下一结点的地址实际上只是算好了位置的结点的地址address属性。

struct Node{int data,address,no,next;//自身数据，自身地址，序号，下一个结点的地址 
}node[maxn];

2. 需要考虑到题目中给的结点有的并不在链表当中，所以结点的序号no属性可以开始全部初始化为maxn，表示是无效结点，也便于排序后让无效结点沉到数组后面，此外记得更新有效结点的个数。

for(int i=0;i<maxn;i++){node[i].no = maxn;//初始化所有结点为无效结点 
}int cnt = 0;//有效节点的个数，也是序号的源
while(head!=-1){//开始逐个给有效结点标序号 node[head].no = cnt;cnt ++;head = node[head].next; 
}sort(node,node+maxn,cmp);n = cnt;//n从元素个数蜕变为有效元素个数

3. 地址是作为整型输出，需要采用%05d的格式，但是对-1不能这么做，因此需要额外判断。对于步长为step的每一整组来说，前step-1个元素不必担心下一元素的地址是-1，可以统一输出。但是对于一整组的最后一个元素，首先要判断，这是不是最后一组，如果不是，那也不必担心-1，直接让最后一个元素的下一元素地址等于下一整组首元素的地址。如果是，就要考虑后面是不是有没排序的剩余元素，如果有，最后一个元素的下一元素地址等于没排序的第一个元素的地址，后面的元素正序输出，如果是最后一个输出-1，如果没有，最后一个元素的下一元素地址等于-1。

//开始输出了 for(int i=0;i<n/step;i++){//对于每一组//前step-1个元素的输出,不用考虑-1输出格式不同的问题 for(int j = (i+1)*step-1;j>i*step;j--){printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);}//最后一个元素的输出，需要考虑当前组是不是最后的完整一组 //先输出address和data printf("%05d %d ",node[i*step].address,node[i*step].data);if(i==n/step-1){//已经是最后的完整一组 if(n%step == 0)printf("-1\n");//后面没有元素了else{//后面还有元素，但是不能组成完整的组，当前组最后结点的next是下一个结点的地址 printf("%05d\n",node[n/step*step].address);//最后的元素没有被翻转处理，正序输出，但是要考虑next==-1的问题 for(int j=n/step*step;j<n;j++){if(j==n-1)printf("%05d %d -1\n",node[j].address,node[j].data);else printf("%05d %d %05d\n",node[j].address,node[j].data,node[j+1].address); }} }else{//后面还有完整的组,当前组最后结点的next应该是下一组首个结点的地址 printf("%05d\n",node[(i+2)*step-1].address); }}

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>using namespace std;const int maxn = 100010;struct Node{int data,address,no,next;//自身数据，自身地址，序号，下一个结点的地址 
}node[maxn];bool cmp(Node a,Node b){return a.no<b.no;
} int main(){int head,n,step;//首结点地址，结点总数，步长scanf("%d%d%d",&head,&n,&step);int address;while(n--){scanf("%d",&address);scanf("%d%d",&node[address].data,&node[address].next);node[address].address = address;}for(int i=0;i<maxn;i++){node[i].no = maxn;//初始化所有结点为无效结点 }int cnt = 0;//有效节点的个数，也是序号的源while(head!=-1){//开始逐个给有效结点标序号 node[head].no = cnt;cnt ++;head = node[head].next; }sort(node,node+maxn,cmp);n = cnt;//n从元素个数蜕变为有效元素个数//测试点：看有无正确排序 
//	for(int i=0;i<cnt;i++){
//		printf("%d %d %d\n",node[i].address,node[i].data,node[i].next);
//	}//开始输出了 for(int i=0;i<n/step;i++){//对于每一组//前step-1个元素的输出,不用考虑-1输出格式不同的问题 for(int j = (i+1)*step-1;j>i*step;j--){printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);}//最后一个元素的输出，需要考虑当前组是不是最后的完整一组 //先输出address和data printf("%05d %d ",node[i*step].address,node[i*step].data);if(i==n/step-1){//已经是最后的完整一组 if(n%step == 0)printf("-1\n");//后面没有元素了else{//后面还有元素，但是不能组成完整的组，当前组最后结点的next是下一个结点的地址 printf("%05d\n",node[n/step*step].address);//最后的元素没有被翻转处理，正序输出，但是要考虑next==-1的问题 for(int j=n/step*step;j<n;j++){if(j==n-1)printf("%05d %d -1\n",node[j].address,node[j].data);else printf("%05d %d %05d\n",node[j].address,node[j].data,node[j+1].address); }} }else{//后面还有完整的组,当前组最后结点的next应该是下一组首个结点的地址 printf("%05d\n",node[(i+2)*step-1].address); }}return 0;
}

https://www.dkcj.cn/info/17668.html

1025 反转链表

相关文章：

关于margin

DNS迭代式和递归式域名查询对比

UIActionSheet在iOS8中被弃用造成的错误

SQL分页语句(转)

一个考查作用域以及闭包的题目

弄懂“进程”(上)：3个组成部分、4个基本特征、4个基本状态

解决Failed to execute goal org.apache.maven.plugins

P4722 【模板】最大流

与我们的书合影——在2009北京国际图书展（BIBF）

弄懂“进程”(下)：进程的控制、同步和通信

（转自Timon's wang blogs）C#实现web信息自动抓取

数据结构-栈与队列

雷观(七):靠谱的程序员,不是随便一个码农就可以做到的

1032 Sharing

Magento开发的特点有哪些？

Linux多任务编程之五：exit()和_exit()函数（转）

LogMiner日志分析工具的使用

1052 Linked List Sorting

C#尝试读取或写入受保护的内存。这通常指示其他内存已损坏。

TFS2008 + Windows2003 + Sql2005 安装注意事项

发票拍照识别OCR

1097 Deduplication on a Linked List

搞定MyBatis

6-6.用HLSL定义点光源

2018 JVM 生态报告：79％的 Java 开发者使用 Java 8

广度优先搜索(BFS)模板

static关键字和内存使用

转载：用 Tomcat 和 Eclipse 开发 Web 应用程序

【学习——字符串】字符串之一网打尽quq

分别用BFS和DFS求给定的矩阵中“块”的个数