最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天最资讯丨pat乙级链表问题

来源：博客园


【资料图】

链表题目：一开始以为要按照链表那样一个一个搞，看完这个后思路清晰：1025链表一连a三题链表题。在输入完链表之后，遍历链表使用另一个数组(可以是指针数组也可以是节点数组)记录下该节点的地址或者将节点的顺序调对，并且记录有多少个节点(加个变量记录就行，还可以用来作为变化的数组下标)，读到-1停止。然后就进行对应的操作输出就行了，以下代码来自柳婼和上面那个链接1025:反转链表

#include   #include   using namespace std;  int main() {  int first, k, n, temp;  cin >> first >> n >> k;  int data[100005], next[100005], list[100005];  for (int i = 0; i < n; i++) {  cin >> temp;  cin >> data[temp] >> next[temp];  }  int sum = 0;//不⼀定所有的输⼊的结点都是有⽤的，加个计数器  while (first != -1) {  list[sum++] = first;  first = next[first];  }  for (int i = 0; i < (sum - sum % k); i += k)  reverse(begin(list) + i, begin(list) + i + k);  for (int i = 0; i < sum - 1; i++)printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);  printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);  return 0;  }#include#includeusing namespace std;struct List{int id;int date;int next;};int main(){struct List p[100000+10];//链表结构体 struct List *q[100000+10];//存放链表结构体地址的数组int first,num,ty;cin>>first>>num>>ty;int ID,Date,NEXT;//暂时存放 for (int i = 0; i < num; i++) //读数据 {cin>>ID>>Date>>NEXT;p[ID].date=Date;p[ID].next=NEXT; p[ID].id=ID; }int tk=0; for(int i=first;i!=-1;i=p[i].next)//将数据按顺序存放到指针数组q中 {q[tk++]=&p[i]; } for(int i=tk,j=0;i/ty!=0;i-=ty,j+=ty){reverse(q+j,q+j+ty);//逆序指针数组  原来数组存放的链表地址进行逆序 }for( int i=0;iid,q[i]->date,q[i+1]->id);}printf("%05d %d -1",q[tk-1]->id,q[tk-1]->date);return 0;}

1075:链表元素分类

将结点⽤list[10000]保存， list为node类型， node中保存结点的值value和它的next地址。 list的下标就是结点的地址。将<0、 0～k、 >k三部分的结点地址分别保存在v[0]、 v[1]、 v[2]中，最后将vector中的值依次输出即可  .即只遍历一次，减少遍历次数#include   #include   using namespace std;  struct node {  int data, next;  }list[100000];  vector v[3];  int main() {  int start, n, k, a;  scanf("%d%d%d", &start, &n, &k);  for (int i = 0; i < n; i++) {  scanf("%d", &a);  scanf("%d%d", &list[a].data, &list[a].next);  }  int p = start;  while(p != -1) {  int data = list[p].data;  if (data < 0)  v[0].push_back(p);  else if (data >= 0 && data <= k)  v[1].push_back(p);  else  v[2].push_back(p);  p = list[p].next;  }  int flag = 0;  for (int i = 0; i < 3; i++) {  for (int j = 0; j < v[i].size(); j++) {  if (flag == 0) {  printf("%05d %d ", v[i][j], list[v[i][j]].data);  flag = 1;  } else {  printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);  }  }  }  printf("-1");  return 0;  }

1105：链表合并：⽤vectorL1、 L2存储题⽬中给定的两个链表， vectorans保存合并后的链表。将较⻓的⼀个链表存储在L1中，如果原本L1较短，则将L1与L2⽤swap函数互相置换~在链表合并的过程中， i从0开始，将L1中每个结点添加到ans中，如果当前i是奇数（i & 1不等于0）就把L2的⼀个结点添加到ans中，直到L2中没有剩余元素,反复，我是遍历了两遍，然后如果大小区分就swap首地址。

#include   #include   using namespace std;  struct node {  int data, next;  }A[100000];  vector L1, L2, ans;  int sa, sb, n, a, ta, tb, c;  int main() {  cin >> sa >> sb >> n;  for (int i = 0; i < n; i++) {  cin >> a >> A[a].data >> A[a].next;  }  ta = sa;  while (ta != -1) {  L1.push_back(ta);  ta = A[ta].next;  }  tb = sb;  while (tb != -1) {  L2.push_back(tb);  tb = A[tb].next;  }  if (L1.size() < L2.size()) swap(L1, L2);  for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {  ans.push_back(L1[i]);  if (i & 1 && c >= 0) ans.push_back(L2[c--]);  }  for (int i = 1; i < ans.size(); i++) {  printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);}  printf("%05d %d -1", ans.back(), A[ans.back()].data);  return 0;  }

关键词： 一个一个 上面那个