自学内容网 自学内容网
自学内容网 > 正文

【数据结构 | PTA】表

🕗 发布于 2024-10-08 20:55 数据结构  

文章目录

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;
        }
        else
            printf("%05d\n",ID);
        temp = str[temp].pre;
        printf("%05d %d ",ID , str[ID].data);
        if(ID == temp)
        {
            printf("-1\n");
            break;
        }
        else
            printf("%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;
}

原文地址：https://blog.csdn.net/2301_77485708/article/details/142767827

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024