【2月3日PAT刷题笔记】——数据结构专题（1）队列，栈，链表

【2月3日PAT刷题笔记】——数据结构专题（1）队列，栈，链表

  1032 Sharing (25分)（链表的遍历）

  1052 Linked List Sorting (25分) （链表的排序与遍历）

  1097 Deduplication on a Linked List (25分)(链表的遍历，map的使用)

  1074 Reversing Linked List (25分)（链表的遍历）

  1051 Pop Sequence (25分)（栈的应用）

   1056 Mice and Rice (25分)（队列的应用）

专题题目整理

1. 链表操作

                                               1032 Sharing (25分)（链表的遍历）

题意：给出两条链表，他们有可能在从中间的某处开始至末尾是重合起来的，求开始重合的这一点的地址

用表头1开始遍历这个链表一遍，把遍历到的节点都标为true，再从表头2开始遍历这个链表，遍历到true的话，证明这个点就是两个链表的重复点的开端

#include<bits/stdc++.h>
using namespace std;
struct node {int address;char w;int nx;bool flag;
} nodes[100005];
int n;
int main() {int a1,a2;int A,C;char B[2];cin>>a1>>a2>>n;for(int i=0; i<n; i++) {cin>>A>>B>>C;nodes[A].address=A;nodes[A].w=B[0];nodes[A].nx=C;nodes[A].flag=0;}for(;a1!=-1;a1=nodes[a1].nx){nodes[a1].flag=1;}int ans=-1;for(;a2!=-1;a2=nodes[a2].nx){if(nodes[a2].flag==1){ans=nodes[a2].address;break;}}if(ans==-1) printf("-1n");else printf("%05dn",ans);return 0;
}

                               1052 Linked List Sorting (25分) （链表的排序与遍历）

题意：给出一条链表，将他排序后输出

！！！先遍历一遍链表，因为给的节点有可能不在链表上

#include<bits/stdc++.h>
using namespace std;
struct node {int data;int address;int nx;bool flag;
} nodes[100005];
bool cmp(node a,node b) {if(!a.flag||!b.flag) return a.flag>b.flag;else return a.data<b.data;
}
int main() {int n,ad,a,b,c;cin>>n>>ad;for(int i=0; i<n; i++) {cin>>a>>b>>c;nodes[a].address=a;nodes[a].data=b;nodes[a].nx=c;nodes[a].flag=false;}int cnt=0;vector<node>res;for(; ad!=-1; ad=nodes[ad].nx) {nodes[ad].flag=true;cnt++;}sort(nodes,nodes+100005,cmp);if(!cnt){printf("0 -1n");return 0;}printf("%d %05dn",cnt,nodes[0].address);for(int i=0; i<cnt; i++) {if(i==cnt-1) printf("%05d %d -1n",nodes[i].address,nodes[i].data);else printf("%05d %d %05dn",nodes[i].address,nodes[i].data,nodes[i+1].address);}return 0;
}

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

对存在不合理的元素的数组排序的方法

bool cmp(node a,node b){if(!a.flag||!b.flag) return a.flag>b.flag;else return a.data<b.data;
}

                      1097 Deduplication on a Linked List (25分)(链表的遍历，map的使用)

题意：给出一个链表，去除其中存在的重复绝对值的节点后输出

用map记是否绝对值重复就好

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
struct node {int data;int address;int next;
};
node a[maxn];
map<int,int>mp;
int main() {vector<node>ans1,ans2;int n,add,ad,da,nx;cin>>add>>n;for(int i=0; i<n; i++) {cin>>ad>>da>>nx;a[ad].address=ad;a[ad].data=da;a[ad].next=nx;}for(; add!=-1; add=a[add].next) {if(mp[abs(a[add].data)]) {ans2.push_back(a[add]);} else {mp[abs(a[add].data)]=1;ans1.push_back(a[add]);}}for(int i=0; i<ans1.size(); i++) {if(i==ans1.size()-1) printf("%05d %d -1n",ans1[i].address,ans1[i].data);else printf("%05d %d %05dn",ans1[i].address,ans1[i].data,ans1[i+1].address);}for(int i=0; i<ans2.size(); i++) {if(i==ans2.size()-1) printf("%05d %d -1n",ans2[i].address,ans2[i].data);else printf("%05d %d %05dn",ans2[i].address,ans2[i].data,ans2[i+1].address);}return 0;
}

                             1074 Reversing Linked List (25分)（链表的遍历）

题意：给出一个链表，将其中的元素每反转k个后输出

题意：每反转k个，不是只反转前k个

#include<bits/stdc++.h>
using namespace std;
struct node {int data;int address;int nx;
} nodes[100005];
int main() {int ad,n,k;int a,b,c;cin>>ad>>n>>k;for(int i=0; i<n; i++) {cin>>a>>b>>c;nodes[a].address=a;nodes[a].data=b;nodes[a].nx=c;}
//	cout<<"OK"<<endl;vector<node>ans,res;int cnt=0;for(; ad!=-1; ad=nodes[ad].nx) {ans.push_back(nodes[ad]);cnt++;if(cnt%k==0) reverse(ans.begin()+d());}for(int i=0;i<ans.size();i++){if(i==ans.size()-1) printf("%05d %d -1n",ans[i].address,ans[i].data);else printf("%05d %d %05dn",ans[i].address,ans[i].data,ans[i+1].address);}return 0;
}

总结：

PAT关于链表的题都考得大多是关于链表的遍历再加一点点其他简单的内容，然后可能题目的描述会让你感到摸不着头脑。只要搞懂了遍历，链表的题就没问题了。

2.栈及其操作

                                       1051 Pop Sequence (25分)（栈的应用）

题意：列车按1~n的顺序进站，给出一个序列，问能否按照这个序列出站

栈的经典入门题目

#include<bits/stdc++.h>
using namespace std;
int nums[1005];
int main() {int n,m,k;cin>>m>>n>>k;while(k--) {bool flag=true;stack<int>stk;for(int i=0; i<n; i++) {cin>>nums[i];}int pointers=0;for(int i=1;i<=n;i++){stk.push(i);if(stk.size()>m){flag=false;break;}while(!pty()&&p()==nums[pointers]) {stk.pop();pointers++;}}pty()&&flag) printf("YESn");else printf("NOn");}return 0;
}

总结

栈的题目还是考的比较少，注意它FILO的性质

3.队列的应用

                                      1056 Mice and Rice (25分)（队列的应用）

题意：给n只老鼠，每m只分一组，每组最大的晋级，最后输出每只老鼠的排名

！！！设当前老鼠可以分为group组，则这一轮没有晋级的老鼠排名就为group+1

#include<bits/stdc++.h>
using namespace std;
struct node {int weight;int ID;
} mouse[1005];
int n,m;
int number[1005],ran[1005];
int main() {int group;cin>>n>>m;for(int i=0; i<n; i++) {cin>>mouse[i].weight;}for(int i=0; i<n; i++) cin>>number[i],mouse[i].ID=number[i];queue<node>que;for(int i=0; i<n; i++) {que.push(mouse[number[i]]);}while(!pty()) {if(que.size()==1) {ran[que.front().ID]=1;break;}int size=que.size();group=size/m;if(size%m!=0) group++;int cnt=0;node maxn;maxn.weight=-1;for(int i=0; i<size; i++) {int qweight=que.front().weight;if(qweight>maxn.weight) {maxn=que.front();}ran[que.front().ID]=group+1;que.pop();cnt++;if(cnt==m||i==size-1) cnt=0,que.push(maxn),maxn.weight=-1;}}for(int i=0; i<n; i++) {printf("%d%c",ran[number[i]],i==n-1?'n':' ');}return 0;
}