devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

两个链表的合并_双向链表合并

作者：小桥流水78 | 2024-07-30 20:14:02

赞

踩

双向链表合并
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct student {
  5.     int num;   // 学号
  6.     int score;   // 成绩
  7.     struct student* next;
  8. } Student;
  9.  
  10. // 创建新结点
  11. Student* createNode(int num, int score) {
  12.     Student* node = (Student*)malloc(sizeof(Student));
  13.     node->num = num;
  14.     node->score = score;
  15.     node->next = NULL;
  16.     return node;
  17. }
  18.  
  19. // 合并并按学号升序排序两个链表
  20. Student* mergeLinkedList( Student* a, Student* b ) {
  21.     Student *p = a, *q = b, *prev = NULL, *head = NULL;
  22.  
  23.     while( p != NULL && q != NULL ) {
  24.         if( p->num <= q->num ) {
  25.             if( prev == NULL ) head = p;
  26.             else prev->next = p;
  27.  
  28.             prev = p;
  29.             p = p->next;
  30.         }
  31.         else {
  32.             if( prev == NULL ) head = q;
  33.             else prev->next = q;
  34.  
  35.             prev = q;
  36.             q = q->next;
  37.         }
  38.     }
  39.  
  40.     if( p == NULL ) prev->next = q;
  41.     else prev->next = p;
  42.  
  43.     return head;
  44. }
  45.  
  46. // 输出链表中的所有结点
  47. void printLinkedList(Student* L) {
  48.     printf("num\t score\n");
  49.     while (L != NULL) {
  50.         printf("%d\t %d\n", L->num, L->score);
  51.         L = L->next;
  52.     }
  53. }
  54.  
  55. int main() {
  56.     Student *headA = NULL, *headB = NULL, *headC = NULL;   // 三个单向链表
  57.  
  58.     // 分别读入两个链表 a 和 b
  59.     int n, i, x, y;
  60.     printf("Input the number of students in list a: ");
  61.     scanf("%d", &n);
  62.     for (i = 0; i < n; ++i) {
  63.         printf("Input the num and score of the %dth student: ", i + 1);
  64.         scanf("%d%d", &x, &y);
  65.         Student* node = createNode(x, y);
  66.         node->next = headA;
  67.         headA = node;
  68.     }
  69.  
  70.     printf("Input the number of students in list b: ");
  71.     scanf("%d", &n);
  72.     for (i = 0; i < n; ++i) {
  73.         printf("Input the num and score of the %dth student: ", i + 1);
  74.         scanf("%d%d", &x, &y);
  75.         Student* node = createNode(x, y);
  76.         node->next = headB;
  77.         headB = node;
  78.     }
  79.  
  80.     // 将两个链表合并
  81.     headC = mergeLinkedList(headA, headB);
  82.  
  83.     // 输出新链表
  84.     printf("The merged list:\n");
  85.     printLinkedList(headC);
  86.  
  87.     return 0;
  88. }
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct student {
  5.     int num;   // 学号
  6.     int score;   // 成绩
  7.     struct student* next;
  8. } Student;
  9.  
  10. typedef struct {
  11.     Student* head;
  12. } LinkedList;
  13.  
  14. // 初始化单向链表
  15. void initLinkedList(LinkedList* L) {
  16.     L->head = NULL;
  17. }
  18.  
  19. // 创建新结点
  20. Student* createNode(int num, int score) {
  21.     Student* node = (Student*)malloc(sizeof(Student));
  22.     node->num = num;
  23.     node->score = score;
  24.     node->next = NULL;
  25.     return node;
  26. }
  27.  
  28. // 按学号升序插入结点
  29. void insertNode(LinkedList* L, Student* node) {
  30.     if (L->head == NULL || node->num < L->head->num) {
  31.         node->next = L->head;
  32.         L->head = node;
  33.     } else {
  34.         Student* p = L->head;
  35.         while (p->next != NULL && p->next->num <= node->num) {
  36.             p = p->next;
  37.         }
  38.         node->next = p->next;
  39.         p->next = node;
  40.     }
  41. }
  42.  
  43. // 输出链表中的所有结点
  44. void printLinkedList(LinkedList* L) {
  45.     Student* p = L->head;
  46.     printf("num\t score\n");
  47.     while (p != NULL) {
  48.         printf("%d\t %d\n", p->num, p->score);
  49.         p = p->next;
  50.     }
  51. }
  52.  
  53. int main() {
  54.     LinkedList a, b, c;   // 三个单向链表
  55.     initLinkedList(&a);
  56.     initLinkedList(&b);
  57.     initLinkedList(&c);
  58.  
  59.     // 分别读入两个链表 a 和 b
  60.     int n, i, x, y;
  61.     printf("Input the number of students in list a: ");
  62.     scanf("%d", &n);
  63.     for (i = 0; i < n; ++i) {
  64.         printf("Input the num and score of the %dth student: ", i + 1);
  65.         scanf("%d%d", &x, &y);
  66.         Student* node = createNode(x, y);
  67.         insertNode(&a, node);
  68.     }
  69.  
  70.     printf("Input the number of students in list b: ");
  71.     scanf("%d", &n);
  72.     for (i = 0; i < n; ++i) {
  73.         printf("Input the num and score of the %dth student: ", i + 1);
  74.         scanf("%d%d", &x, &y);
  75.         Student* node = createNode(x, y);
  76.         insertNode(&b, node);
  77.     }
  78.  
  79.     // 将两个链表合并
  80.     Student *pa = a.head, *pb = b.head;
  81.     while (pa != NULL && pb != NULL) {
  82.         if (pa->num <= pb->num) {
  83.             Student* node = createNode(pa->num, pa->score);
  84.             insertNode(&c, node);
  85.             pa = pa->next;
  86.         } else {
  87.             Student* node = createNode(pb->num, pb->score);
  88.             insertNode(&c, node);
  89.             pb = pb->next;
  90.         }
  91.     }
  92.     while (pa != NULL) {
  93.         Student* node = createNode(pa->num, pa->score);
  94.         insertNode(&c, node);
  95.         pa = pa->next;
  96.     }
  97.     while (pb != NULL) {
  98.         Student* node = createNode(pb->num, pb->score);
  99.         insertNode(&c, node);
  100.         pb = pb->next;
  101.     }
  102.  
  103.     // 输出新链表
  104.     printf("The merged list:\n");
  105.     printLinkedList(&c);
  106.  
  107.     return 0;
  108. }

这个使用了结构体，时间会超限

  1. #include <stdio.h>
  2.  
  3. typedef struct {
  4.     int num;   // 学号
  5.     int score;   // 成绩
  6. } Student;
  7.  
  8. // 归并排序算法
  9. void mergeSort(Student* a, int lo, int hi) {
  10.     if (lo >= hi) return;
  11.     int mid = (lo + hi) / 2;
  12.     mergeSort(a, lo, mid);
  13.     mergeSort(a, mid + 1, hi);
  14.  
  15.     int i = lo, j = mid + 1, k = 0;
  16.     Student temp[hi - lo + 1];
  17.     while (i <= mid && j <= hi) {
  18.         if (a[i].num <= a[j].num) {
  19.             temp[k++] = a[i++];
  20.         } else {
  21.             temp[k++] = a[j++];
  22.         }
  23.     }
  24.     while (i <= mid) {
  25.         temp[k++] = a[i++];
  26.     }
  27.     while (j <= hi) {
  28.         temp[k++] = a[j++];
  29.     }
  30.     for (i = 0; i < k; ++i) {
  31.         a[lo + i] = temp[i];
  32.     }
  33. }
  34.  
  35. int main() {
  36.     int n, m, i, j, k;
  37.     Student a[100], b[100], c[200];
  38.  
  39.     // 分别读入两个数组 a 和 b
  40.     printf("Input the number of students in list a: ");
  41.     scanf("%d", &n);
  42.     for (i = 0; i < n; ++i) {
  43.         printf("Input the num and score of the %dth student: ", i + 1);
  44.         scanf("%d%d", &a[i].num, &a[i].score);
  45.     }
  46.  
  47.     printf("Input the number of students in list b: ");
  48.     scanf("%d", &m);
  49.     for (i = 0; i < m; ++i) {
  50.         printf("Input the num and score of the %dth student: ", i + 1);
  51.         scanf("%d%d", &b[i].num, &b[i].score);
  52.     }
  53.  
  54.     // 按照学号升序合并数组 a 和 b 到 c 中
  55.     i = j = k = 0;
  56.     while (i < n && j < m) {
  57.         if (a[i].num <= b[j].num) {
  58.             c[k++] = a[i++];
  59.         } else {
  60.             c[k++] = b[j++];
  61.         }
  62.     }
  63.     while (i < n) {
  64.         c[k++] = a[i++];
  65.     }
  66.     while (j < m) {
  67.         c[k++] = b[j++];
  68.     }
  69.  
  70.     // 对新数组 c 按照学号升序排序
  71.     mergeSort(c, 0, k - 1);
  72.  
  73.     // 输出新数组
  74.     printf("The merged and sorted list:\n");
  75.     for (i = 0; i < k; ++i) {
  76.         printf("%d %d\n", c[i].num, c[i].score);
  77.     }
  78.  
  79.     return 0;
  80. }

改进算法

  1. #include <stdio.h>
  2.  
  3. typedef struct {
  4.     int num;   // 学号
  5.     int score;   // 成绩
  6. } Student;
  7.  
  8. // 归并排序算法
  9. void mergeSort(Student* a, int lo, int hi) {
  10.     if (lo >= hi) return;
  11.     int mid = (lo + hi) / 2;
  12.     mergeSort(a, lo, mid);
  13.     mergeSort(a, mid + 1, hi);
  14.  
  15.     int i = lo, j = mid + 1, k = 0;
  16.     Student temp[hi - lo + 1];
  17.     while (i <= mid && j <= hi) {
  18.         if (a[i].num <= a[j].num) {
  19.             temp[k++] = a[i++];
  20.         } else {
  21.             temp[k++] = a[j++];
  22.         }
  23.     }
  24.     while (i <= mid) {
  25.         temp[k++] = a[i++];
  26.     }
  27.     while (j <= hi) {
  28.         temp[k++] = a[j++];
  29.     }
  30.     for (i = 0; i < k; ++i) {
  31.         a[lo + i] = temp[i];
  32.     }
  33. }
  34.  
  35. int main() {
  36.     int n, m, i, j, k;
  37.     Student a[100], b[100], c[200];
  38.  
  39.     // 分别读入两个数组 a 和 b
  40.     scanf("%d", &n);
  41.     for (i = 0; i < n; ++i) {
  42.         scanf("%d %d", &a[i].num, &a[i].score);
  43.     }
  44.  
  45.     scanf("%d", &m);
  46.     for (i = 0; i < m; ++i) {
  47.         scanf("%d%d", &b[i].num, &b[i].score);
  48.     }
  49.  
  50.     // 按照学号升序合并数组 a 和 b 到 c 中
  51.     i = j = k = 0;
  52.     while (i < n && j < m) {
  53.         if (a[i].num <= b[j].num) {
  54.             c[k++] = a[i++];
  55.         } else {
  56.             c[k++] = b[j++];
  57.         }
  58.     }
  59.     while (i < n) {
  60.         c[k++] = a[i++];
  61.     }
  62.     while (j < m) {
  63.         c[k++] = b[j++];
  64.     }
  65.  
  66.     // 对新数组 c 按照学号升序排序
  67.     mergeSort(c, 0, k - 1);
  68.  
  69.     // 输出新数组
  70.     for (i = 0; i < k; ++i) {
  71.         printf("%d %d\n", c[i].num, c[i].score);
  72.     }
  73.  
  74.     return 0;
  75. }

此代码产生了，数组越界问题

  1. #include <stdio.h>
  2.  
  3. typedef struct {
  4.     int num;   // 学号
  5.     int score;   // 成绩
  6. } Student;
  7.  
  8. // 归并排序算法
  9. void mergeSort(Student* a, int lo, int hi) {
  10.     if (lo >= hi) return;
  11.     int mid = (lo + hi) / 2;
  12.     mergeSort(a, lo, mid);
  13.     mergeSort(a, mid + 1, hi);
  14.  
  15.     int i = lo, j = mid + 1, k = 0;
  16.     Student temp[hi - lo + 1];
  17.     while (i <= mid && j <= hi) {
  18.         if (a[i].num <= a[j].num) {
  19.             temp[k++] = a[i++];
  20.         } else {
  21.             temp[k++] = a[j++];
  22.         }
  23.     }
  24.     while (i <= mid) {
  25.         temp[k++] = a[i++];
  26.     }
  27.     while (j <= hi) {
  28.         temp[k++] = a[j++];
  29.     }
  30.     for (i = 0; i < k; ++i) {
  31.         a[lo + i] = temp[i];
  32.     }
  33. }
  34.  
  35. int main() {
  36.     int n, m, i, j, k;
  37.     Student a[110], b[110], c[220];   // 扩大数组定义范围
  38.  
  39.     // 分别读入两个数组 a 和 b
  40.     scanf("%d", &n);
  41.     for (i = 0; i < n && i < 100; ++i) {   // 判断输入的大小是否超出了数组定义范围
  42.         scanf("%d %d", &a[i].num, &a[i].score);
  43.     }
  44.  
  45.     scanf("%d", &m);
  46.     for (i = 0; i < m && i < 100 ; ++i) {   // 判断输入的大小是否超出了数组定义范围
  47.         scanf("%d%d", &b[i].num, &b[i].score);
  48.     }
  49.  
  50.     // 按照学号升序合并数组 a 和 b 到 c 中
  51.     i = j = k = 0;
  52.     while (i < n && j < m) {
  53.         if (a[i].num <= b[j].num) {
  54.             c[k++] = a[i++];
  55.         } else {
  56.             c[k++] = b[j++];
  57.         }
  58.     }
  59.     while (i < n) {
  60.         c[k++] = a[i++];
  61.     }
  62.     while (j < m) {
  63.         c[k++] = b[j++];
  64.     }
  65.  
  66.     // 对新数组 c 按照学号升序排序
  67.     mergeSort(c, 0, k - 1);
  68.  
  69.     // 输出新数组
  70.     for (i = 0; i < k && i < 200; ++i) {   // 判断输出的大小是否超出了数组定义范围
  71.         printf("%d %d\n", c[i].num, c[i].score);
  72.     }
  73.  
  74.     return 0;
  75. }

修改后的代码

  1. #include <stdio.h>
  2. #include <stdlib.h>   // 用到 malloc 和 free 函数
  3.  
  4. typedef struct Linklist1052{
  5.     int num;
  6.     int score;
  7.     struct Linklist1052 *next;
  8. }Node;
  9.  
  10. Node* create(int n){
  11.     Node *p1,*p2;
  12.     Node *head = NULL;
  13.     p1=p2=(Node *)malloc(sizeof(Node));
  14.  
  15.     for(int i=0;i<n;i++){
  16.         scanf("%d %d",&p1->num,&p1->score);
  17.         if(i==0){
  18.             head=p1;
  19.         }else{
  20.             p2->next=p1;
  21.         }
  22.         p2=p1;
  23.         p1=(Node *)malloc(sizeof(Node));
  24.     }
  25.     p2->next=NULL;
  26.     return head;
  27. }
  28.  
  29. void print1052(Node *head){
  30.     Node *p = head;
  31.     if(head!=NULL){
  32.         while(p!=NULL){
  33.             printf("%d %d\n",p->num,p->score);
  34.             p=p->next;
  35.         }
  36.     }
  37. }
  38.  
  39. // 对链表进行归并和排序操作
  40. Node *pai1052(Node *a, Node *b, int n, int m){
  41.     Node *p,*q,*head,*min,*minq,*newp;
  42.     head=NULL;
  43.     p=a;
  44.     while(p->next!=NULL){
  45.         p=p->next;
  46.     }
  47.     p->next=b;
  48.     q=min=q=p;
  49.  
  50.     for(int i=0; i<n+m; i++){
  51.         p=a;
  52.         q=minq=min=p;
  53.         // 寻找num最小指针
  54.         while(p!=NULL){
  55.             if(min->num>p->num){
  56.                 min=p;
  57.                 minq=q;
  58.             }
  59.             q=p;
  60.             p=p->next;
  61.         }
  62.         if(min==a){  // 首位最小的情况
  63.             a=a->next;
  64.         } 
  65.         // 解绑
  66.         minq->next=min->next; 
  67.         if(i==0){
  68.             head=min;
  69.         }else{
  70.             newp->next=min;
  71.         }
  72.         newp=min;
  73.     }
  74.     newp->next=NULL;
  75.     return head;
  76. }
  77.  
  78. int main(){
  79.     Node *a,*b,*ab;
  80.     int n,m;
  81.     scanf("%d",&n);
  82.     scanf("%d",&m);
  83.     a=create(n);
  84.     b=create(m);
  85.     ab=pai1052(a,b,n,m);
  86.     print1052(ab);
  87.  
  88.     // 释放内存，防止内存泄漏
  89.     Node *temp = NULL;
  90.     while (a != NULL)
  91.     {
  92.         temp = a;
  93.         a = a->next;
  94.         free(temp);
  95.     }
  96.     while (b != NULL)
  97.     {
  98.         temp = b;
  99.         b = b->next;
  100.         free(temp);
  101.     }
  102.     while (ab != NULL)
  103.     {
  104.         temp = ab;
  105.         ab = ab->next;
  106.         free(temp);
  107.     }
  108.  
  109.     return 0;
  110. }

最后解决代码

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号