a905448839 发表于 2023-6-30 00:53:36

太难了,又是这题!求高手帮帮忙!

太难了,还是这题!

给定一个常数K和一个单链表L,我们需要将L中每K个元素的链路进行反转。例如,如果L为1→2→3→4→5→6,如果K=3,则必须输出3→2→1→6→5→4;如果K=4,则必须输出4→3→2→1→5→6。

输入说明: 每个输入文件包含一个测试用例。对于每个测试用例,第一行包含第一个节点的地址,一个正整数N(≤100000),表示节点的总数,和一个正整数K(≤N),表示要反转的子链表的长度。节点的地址是一个5位非负整数,空指针用-1表示。

然后是N行,每行描述一个节点的格式为:

Address Data Next

其中Address是节点的位置,Data是一个整数,Next是下一个节点的位置。

输出说明: 对于每个测试用例,输出结果排序后的链表。每个节点占一行,并以与输入相同的格式打印。

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

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

我更新后的代码:
#include<stdio.h>
#include<stdlib.h>
typedef struct List *list;
struct List
{
      int address;
      int data;
      int last;
      list next;
};

list read(int n);
void print(list head);
void px(list head,int first);
list dg(list p,list head,int i,int k);

void print(list head)
{
      if(!(head->next)){printf("NULL\n");return;}
         head = head->next;
      while(head)
      {
                      if(head->last != -1)
                printf("%05d %d %05d\n",head->address,head->data,head->last);
                else
                printf("%05d %d %d\n",head->address,head->data,head->last);

                head = head->next;
      }
}

list read(int n)
{
      list head,p,temp;
      head = p = (list)malloc(sizeof(struct List));
      head->next = NULL;
      
      while(n--)
      {
                temp =(list)malloc(sizeof(struct List));
                scanf("%d %d %d",&temp->address,&temp->data,&temp->last);
                p->next = temp;
                p = p->next;
                p->next = NULL;
      }
      
//      temp = head;
//      head = head->next;
//      free(temp);
      
      return head;
}

void px(list head,int first)
{
      list p = head;
      list temp,temp2;
      int t = first;
      
      while(head->next)
      {
                if(head->next->address == t)
                {
                        head = head->next;
                        t = head->last;
                }
                else
                {
                        p = head;
                        while(p->next->address != t)
                        {
                              p = p->next;
                        }
                        list s;
                        s = p->next;
                        temp = s->next;
                        s->next = head->next;
                        head->next = s;
                        p->next = temp;
                        head = head->next;
                        t = head->last;
                }
      }
      
}

void fz(list head,int k)
{
      list p = (list)malloc(sizeof(struct List));
      p->next = head->next;
      list temp;
      int flag = 0;

      while(p->next)
      {
                int i = 1;
                temp = dg(p,p,i,k);
                if(!flag)
                {
                        flag = 1;
                        head->next = p->next;
                                }
                                //if(temp)
                                p->next = temp;
      }
}

list dg(list p,list head,int i,int k)
{
                if(!p)
                return p;

      list temp = NULL;
      list perv = NULL;
      if(i != k)
      {
                perv = p;
                p = p->next;
                i++;
                temp = dg(p,head,i,k);
      }
      else
      {
                head->next = p->next;
                temp =p->next->next;
                p->next->next = p;
                p->next->last = p->address;
                if(!temp)
                {
                        list N = (list)malloc(sizeof(struct List));
                        N->next = NULL;
                        N->data = -1;
                        return N;
                                }
                return temp;

      }
      if(i == 2 && temp)
                                {
                                        if(temp->data == -1)
                                        {
                                                list t = temp;
                                                temp = NULL;
                                                free(t);
                                               
                                        }
                                        p->next = temp;
                                        if(!temp)
                                        {
                                                p->last = -1;
                                        }
                                        else
                                        p->last = temp->address;
                                       
                                }               
      else if(temp)
                {
                        p->next = perv;
                            p->last = perv->address;
                                }

               
      return temp;
}

int main(void)
{
      list head;
      int first,n,k;
      scanf("%d %d %d",&first,&n,&k);
      head = read(n);
      //print(head);
      px(head,first);
       // print(head);
      fz(head,k);
       print(head);

      return 0;
}


测试1:正好全反转        K%N = 0 的情况下!
答案错误
       
测试2:K=1不用反转
答案错误

测试3:最大N,最后剩K-1不反转
答案错误

测试4:有多余结点不在链表上
答案错误

测试5:试例
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
答案正确

测试6:K=N全反转
答案正确

代码已经相较于之前做出修改,但是还有4个测试点过不了,想了一晚上想破脑袋了。求大佬帮帮忙!十分感谢!

isdkz 发表于 2023-6-30 00:59:13

这个问题是一个常见的数据结构问题,涉及到链表的操作。你的代码已经有了一些正确的地方,但是仍然有一些地方需要修改和优化。为了解决这个问题,我们可以按照以下步骤进行:

1. 首先,我们需要根据给出的地址和节点信息构建链表。注意链表可能是非连续的,我们需要进行排序。
2. 其次,我们需要遍历链表,每次取出K个节点,然后反转这K个节点。
3. 如果剩余节点不足K个,那么我们就不反转剩余的节点。
4. 最后,我们需要将反转后的子链表重新连接起来。

下面是一个修改后的C语言代码示例:

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100010

struct Node {
    int addr, data, next;
    int flag;
} node;

int cmp(const void* a, const void* b) {
    struct Node* c = (struct Node*)a;
    struct Node* d = (struct Node*)b;
    if(c->flag != d->flag) {
      return d->flag - c->flag;
    } else {
      return c->addr - d->addr;
    }
}

int Reverse(int start, int end) {
    while(start < end) {
      struct Node temp = node;
      node = node;
      node = temp;
      start++;
      end--;
    }
    return 0;
}

int main() {
    int firstAddr, N, K;
    scanf("%d %d %d", &firstAddr, &N, &K);
    for(int i = 0; i < N; i++) {
      int addr;
      scanf("%d", &addr);
      scanf("%d %d", &node.data, &node.next);
      node.addr = addr;
    }
    int count = 0;
    int p = firstAddr;
    while(p != -1) {
      node.flag = 1;
      count++;
      p = node.next;
    }
    qsort(node, MAXSIZE, sizeof(node), cmp);
    for(int i = 0; i < count / K; i++) {
      Reverse(i * K, (i + 1) * K - 1);
    }
    for(int i = 0; i < count - 1; i++) {
      printf("%05d %d %05d\n", node.addr, node.data, node.addr);
    }
    printf("%05d %d -1\n", node.addr, node.data);
    return 0;
}


这个代码首先根据给出的地址和节点信息构建链表。注意链表可能是非连续的,我们使用一个flag来标记有效节点,并利用qsort函数进行排序。然后我们遍历链表,每次取出K个节点,然后反转这K个节点。如果剩余节点不足K个,那么我们就不反转剩余的节点。最后,我们需要将反转后的子链表重新连接起来。
页: [1]
查看完整版本: 太难了,又是这题!求高手帮帮忙!