【数据结构 | PTA】表

7-1 重排链表

输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct Node{int data;//存储数据int pre;//存储前一个节点的地址int next;//存储下一个节点的地址
}node;
int main()
{node str[100005];int i , n , ID , temp;scanf("%d%d",&ID , &n);for(i = 0 ; i < n ; i ++){int ID1 , num , next;scanf("%d%d%d",&ID1 , &num , &next);str[ID1].data = num;str[ID1].next = next;//保存下一个节点的地址if(next != -1)str[next].pre = ID1;//储存前一个节点的地址if(next == -1){temp = ID1;//记录最后一个节点的地址}}for(;;){printf("%05d %d ",temp , str[temp].data);if(temp == ID){printf("-1\n");break;}elseprintf("%05d\n",ID);temp = str[temp].pre;printf("%05d %d ",ID , str[ID].data);if(ID == temp){printf("-1\n");break;}elseprintf("%05d\n",temp);ID = str[ID].next;}return 0;
}

7-2 链表去重

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。

输出格式：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

输出样例：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

#include<stdio.h>
#include<math.h>typedef struct Node
{int date;int next;
}Node;int first[100005]; // 存放第一条链表的地址 
int f = 0;;
int isVisited[100005]; // 判断是否有重复，0代表未重复，1代表已存在 
int is = 0;
int last[100005]; // 存放第二条链表的地址 
int l = 0;void print(Node arr[],int g[],int n);int main()
{Node arr[100005];int head; // 首地址 int n;int ads;scanf("%d %d",&head,&n);for(int i=0;i<n;i++){scanf("%d",&ads);scanf("%d %d",&arr[ads].date,&arr[ads].next);}int p = head;while(p != -1){is = abs(arr[p].date); // 取出键值的绝对值 // 判断该键值是否存在 if(!isVisited[is]){// 该键值不存在 first[f++] = p; // 将该键值的地址放入第一条链表中 isVisited[is] = 1; // 将该键值位置置为1，表示已存在 }else{// 该键值存在 last[l++] = p; // 将该键值地址放入第二条链表中 }p = arr[p].next; // 移向下一位置 }print(arr,first,f);print(arr,last,l);return 0;
}
void print(Node arr[],int g[],int n)
{for(int i=0;i<n;i++){if(i == n-1){printf("%05d %d -1\n",g[i],arr[g[i]].date);}else{printf("%05d %d %05d\n",g[i],arr[g[i]].date,g[i+1]);}}
}

7-3 两个有序链表序列的合并

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式：
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式：
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例：

1 3 5 -1
2 4 6 8 10 -1

输出样例：

1 2 3 4 5 6 8 10

#include<stdio.h>
#include<stdlib.h>
struct Node
{int dat;struct Node *next;
};
typedef struct Node node;
node *headp;
node *make_new_node(node *head)
{node *p;p=(node*)malloc(sizeof(node));head=p;p->next=NULL;return head;
}
int get_merge(node *head1,node *head2)
{node *pos1,*pos2,*headl;if(head1->next==NULL&&head2->next==NULL){return 0;//输出null;}if(head1->next==NULL||head2->next==NULL){return 1;//只需输出一个链表的值}pos1=(node*)malloc(sizeof(node));headl=pos1;headp=headl;head1=head1->next;head2=head2->next;while(head1&&head2){if(head1->dat<head2->dat){headl->next=head1;head1=head1->next;}else{headl->next=head2;head2=head2->next;}headl=headl->next;}if(!head1&&!head2) return 2;if(head1!=NULL){headl->next=head1;}if(head2!=NULL){headl->next=head2;}return 2;
}
void dis_link(node *head)
{node *p=head->next,*pr;while(p->next!=NULL){printf("%d ",p->dat);p=p->next;}printf("%d\n",p->dat);
}
void free_node(node *head)
{node *p;node *pr=head;while(pr->next!=NULL){p=pr->next;free(pr);pr=p;}free(pr);
}
int main(void)
{node *head1=NULL,*head2=NULL;head1=make_new_node(head1);head2=make_new_node(head2);int data;node *ll=head1;while(scanf("%d",&data),data!=-1){node *tep;tep=(node*)malloc(sizeof(node));ll->next=tep;tep->next=NULL;tep->dat=data;ll=tep;}ll=head2;while(scanf("%d",&data),data!=-1){node *tep;tep=(node*)malloc(sizeof(node));ll->next=tep;tep->next=NULL;tep->dat=data;ll=tep;}int flag=get_merge(head1,head2);if(flag==1){if(head1==NULL){dis_link(head2);free_node(head2);}else{dis_link(head1);free_node(head1);}}else if(flag==0){printf("NULL\n");free_node(head1);free_node(head2);}else{dis_link(headp);free_node(headp);}return 0;
}

7-4 两个有序链表序列的交集

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式：
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式：
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 2 5 -1
2 4 5 8 10 -1

输出样例:

2 5

#include <stdio.h>
#include <stdlib.h>
typedef struct list{int num;struct list *next;
}List;
List *creative();
List *together(List *head1,List *head2);
int main() {int flag=1;List *head1,*head2,*head,*p;head1=creative();head2=creative();head=together(head1,head2);p=head;if(p==NULL){printf("NULL");return 0;}while(p){List *q=p;if(flag){printf("%d",p->num);flag=0;} else{printf(" %d",p->num);}p=p->next;free(q);}return 0;
}
List *creative(){int num;List *p=NULL,*last,*head=NULL;head=NULL;while (1){scanf("%d",&num);if(num>0){p=(List*)malloc(sizeof (List));p->num=num;p->next=NULL;if(head!=NULL){last->next=p;} else{head=p;}last=p;} else{return head;}}
}
List *together(List *head1,List *head2){List *head=(List*) malloc(sizeof (List)),*p,*last=NULL;head->next=NULL;while (head1&&head2){if(head1->num==head2->num){p=(List*) malloc(sizeof (List));p->num=head2->num;p->next=NULL;if(head->next){last->next=p;} else{head->next=p;}last=p;head1=head1->next;head2=head2->next;} else if(head1->num<head2->num){head1=head1->next;} else if(head1->num>head2->num){head2=head2->next;}}return head->next;
}