#include <stdio.h> #include <string.h> #define Maxsize 100005 struct node{ int data; int next_add; }list[Maxsize]; int cnt_1[Maxsize]; int cnt_2[Maxsize]; int cnt[Maxsize]; void Merge(struct node list[Maxsize], int l1, int l2, int cnt_1[Maxsize], int cnt_2[Maxsize]){ //对l2进行逆转 for(int i= 0; i<l2/2; i++){ int tmp = cnt_2[i]; cnt_2[i] = cnt_2[l2-i-1]; cnt_2[l2-i-1] = tmp; } int j=0; //计数l2 for(int i=0; i<l1; i++){ if(i % 2 == 1){ list[cnt_1[i]].next_add = cnt_2[j]; if(i == l1-1) list[cnt_2[j]].next_add = -1; else list[cnt_2[j]].next_add = cnt_1[i+1]; j++; } if(j == l2) break; } } void PrintN(struct node list[Maxsize], int first_add){ int sum = 0; int now_add =first_add; while (now_add != -1){ cnt[sum++] = now_add; now_add = list[now_add].next_add; } for(int i=0; i<sum; i++){ if(i == sum-1) printf("%05d %d -1\n", cnt[i], list[cnt[i]].data); else printf("%05d %d %05d\n", cnt[i], list[cnt[i]].data, cnt[i+1]); } } int main(){ int first_add1, first_add2, n; scanf("%d %d %d", &first_add1, &first_add2, &n); int now_add; for(int i=0; i<n; i++){ scanf("%d", &now_add); scanf("%d %d", &list[now_add].data, &list[now_add].next_add); } int l1 = 0; now_add = first_add1; while (now_add != -1){ cnt_1[l1++] = now_add; now_add = list[now_add].next_add; } int l2 = 0; now_add = first_add2; while (now_add != -1){ cnt_2[l2++] = now_add; now_add = list[now_add].next_add; } if(l1 > l2){ Merge(list, l1, l2, cnt_1, cnt_2); PrintN(list, first_add1); } else { Merge(list, l2, l1, cnt_2, cnt_1); PrintN(list, first_add2); } return 0; }为我讲解这个代码
时间: 2024-04-05 09:32:08 浏览: 82
StudentInformation
这是一段使用链表实现合并两个有序链表的代码。具体来说,该程序首先读入两个链表的头指针和节点个数,然后读入链表的节点信息,包括节点值和下一个节点的地址。接着,程序将两个链表分别转换成数组,并将其中一个数组进行逆转。最后,程序使用类似归并排序的方式,将两个有序链表进行合并,并输出合并后的链表。
具体实现方式为,使用两个变量`l1`和`l2`记录两个链表的长度,分别将两个链表转换成数组`cnt_1`和`cnt_2`。然后,如果第一个链表长度大于第二个链表长度,则将第二个链表逆转,并将两个数组以及各自的长度传入`Merge`函数中进行合并。否则,将第一个链表逆转,并将两个数组以及各自的长度传入`Merge`函数中进行合并。合并时,程序使用两个变量`i`和`j`分别遍历两个数组,将两个链表中较小的节点依次加入合并后的链表中。
最后,程序使用`PrintN`函数输出合并后的链表。具体来说,该函数使用一个数组`cnt`记录合并后链表中节点的顺序,然后遍历该数组,输出每个节点的信息,包括节点地址、节点值以及下一个节点的地址。
阅读全文