【练习】归并和冒泡两种方法c++将两个无序链表合并为一个升序的有序链表

曾经终败给现在 2022-11-19 01:24 44阅读 0赞

定义：

struct node { 
        int data;
        node* next;
    
    };

新建有头指针的链表：

struct node *head;
    head = NULL;//头指针初始为空
    struct node *p;
    //动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
    p=(struct node *)malloc(sizeof(struct node));
    scanf("%d",&a);
    p->data=a;//将数据存储到当前结点的data域中
    p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空

完整版本：

#include <stdio.h>
    #include <stdlib.h>
    //这里创建一个结构体用来表示链表的结点类型
    struct node
    { 
    int data;
    struct node *next;
    };
    int main()
    { 
    struct node *head,*p,*q,*t;
    int i,n,a;
    scanf("%d",&n);
    head = NULL;//头指针初始为空
    for(i=1;i<=n;i++)//循环读入n个数
    { 
    scanf("%d",&a);
    //动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
    p=(struct node *)malloc(sizeof(struct node));
    p->data=a;//将数据存储到当前结点的data域中
    p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
    if(head==NULL)
    head=p;//如果这是第一个创建的结点，则将头指针指向这个结点
    else
    q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
    q=p;//指针q也指向当前结点
    }
    //输出链表中的所有数
    t=head;
    while(t!=NULL)
    { 
    printf("%d ",t->data);
    t=t->next;//继续下一个结点
    }
    getchar();getchar();
    return 0;
    }

合并采用先分别升序后再进行合并两个有序链表，分别升序采用双指针和递归调用。先看用归并排序：

## 用归并排序： ##

node* merge(node* p,node*p2) { //这里是合并的排序
        node* src = new node;
     src->next = nullptr;
        //src->data = 0;
        node* now = src;
        node* a1 = p;
        node* a2 = p2;
        while (a1 != NULL && a2 != NULL) { 
            if (a1->data >= a2->data) { 
                node* tem = a2->next;
                src->next = a2;
                a2 = tem;
            }
            else { 
                node* tem = a1->next;
                src->next = a1;
                a1 = tem;
            }
            src = src->next;//合并两个有序链表 src->next=nullptr
        }
        if (a1 != NULL) src->next = a1;
        if (a2 != NULL)src->next = a2;
        return now->next;
    
    
    }
    node* merge_sort(node* p) { //这是将一个链表进行升序
        if (p == nullptr || p->next == nullptr) return p;
        node* fast = p;
        node* slow = new node;
        slow->data = 0;
        slow->next = p;
    
        while (fast != NULL && fast->next != NULL) { 
            fast = fast->next->next;
            slow = slow->next;
        }
        node* rhead = slow->next;
        slow->next = NULL;
        node* lh = merge_sort(p);
    
        node* rh = merge_sort(rhead);
      
        node* after = merge(lh, rhead);
        return after;
    }
    int main()
    { 
        srand(0);
        node* m = new node;
       
        m->data = rand()%5;
        //cout << m->data;
        node* n = new node;
        n->data = rand()%7;
        m->next = n;
        
        node* nn = new node;
     
        nn->data = rand()%8;
        n->next = nn;
        nn->next = nullptr;
        node* copy_m = m;
        cout << "第一个链表：";
        while (copy_m) { 
            cout << copy_m->data;
            copy_m = copy_m->next;
        }
        cout << endl;
        node* m2 = new node;
        m2->data =rand()%18;
        
        node* n2 = new node; 
        n2->data = rand() % 13;
        m2->next = n2;
    
        node* nn2 = new node;
    
        nn2->data = rand()%15;
        n2->next = nn2;
        nn2->next = nullptr;
        node* copy_n = m2;
        cout << "第二个链表：";
        while (copy_n) { 
            cout << copy_n->data;
            copy_n = copy_n->next;
        }
        cout << endl;
       node*one = merge_sort(m);
    
       node*two= merge_sort(m2);
        node* new_m = merge(one,two);
        node* nice = new_m;
        cout << endl;
        cout << "合并两个有序链表后的结果：";
        while (nice) { 
           
            cout << nice->data << "->";
            nice = nice->next;
        }
    }

结果：  
![在这里插入图片描述][20210414025014462.png]

## 用冒泡排序： ##

node* merge_sort(node* p) { //这是将一个链表进行升序
        if (p == nullptr || p->next == nullptr) return p;
        node* mana = p;
        
        node* pp = mana;
      
        for (int i = 0; i < len(p) - 1; i++) { 
            mana = p;
            for (int j = 0; j < len(p) - i - 1; j++) { 
                node* t1 = mana;
                node* t2 = mana->next;
                if (t1->data > t2->data) { 
                    int tem = t1->data;
                    t1->data = t2->data;
                    t2->data = tem;
                }
                mana = mana->next;
            }
        }
        return pp;
    }

int main()
    { 
        srand(0);
        node* m = new node;
       
        m->data = rand()%12;
        //cout << m->data;
        node* n = new node;
        n->data = rand()%17;
        m->next = n;
        
        node* nn = new node;
     
        nn->data = rand()%18;
        n->next = nn;
       
    
        node* nnn = new node;
    
        nnn->data = rand() % 23;
        nnn->next = NULL;
        nn->next = nnn;
        node* copy_m = m;
        cout << "第一个链表：";
        while (copy_m) { 
            cout << copy_m->data<<"-";
            copy_m = copy_m->next;
        }
        cout << endl;
        node* m2 = new node;
        m2->data =rand()%18;
        
        node* n2 = new node; 
        n2->data = rand() % 13;
        m2->next = n2;
    
        node* nn2 = new node;
    
        nn2->data = rand()%15;
        n2->next = nn2;
        nn2->next = nullptr;
        node* copy_n = m2;
        cout << "第二个链表：";
        while (copy_n) { 
            cout << copy_n->data << "-";
            copy_n = copy_n->next;
        }
        cout << endl;
       node*one = merge_sort(m);
    
       node*two= merge_sort(m2);
        node* new_m = merge(one,two);
        node* nice = new_m;
        cout << endl;
        cout << "合并两个有序链表后的结果：";
        while (nice) { 
           
            cout << nice->data << "->";
            nice = nice->next;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

[20210414025014462.png]: /images/20221022/f8196489b22d4f2ca622a6ba8a827e24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221022/06cc2bc17219451bb6e8be96c09cba88.png