C++怎么實現3個鏈表排序整合到一起

本篇內容介紹了“C++怎么實現3個鏈表排序整合到一起”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

當兩個 遞增鏈表時 可以采用 歸并排序 或者 二叉樹建立時候的遞歸。

#include <iostream>
#include <cstring>
using namespace std;
typedef struct node
{
    int data;
    struct node* next;
}NODE;

NODE* CreateList(int a[], int n)
{
    NODE* p;
    NODE* q;
    NODE* head;
    p = new NODE;
    p->data = a[0];
    head = p;
    for(int i=1;i<n;i++)
    {
        q = new NODE;
        q->data = a[i];
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return head;
}

//整體思路跟 排序算法中的 歸并排序類似
NODE* MerageList(NODE* head_1, NODE* head_2)
{
    NODE* head_3 = NULL;
    if(head_1 == NULL)
    {
        head_3 = head_2;
    }
    else if(head_2 == NULL)
    {
        head_3 = head_1;
    }
    else
    {
        NODE* top1 =head_1;
        NODE* top2 =head_2;
        NODE* mid = NULL;
        if(top1->data < top2->data)
        {
            head_3 = top1;
             mid =head_3  ;
            top1 = top1->next;
        }
        else
        {
            head_3 = top2;
             mid = head_3  ;
            top2 = top2->next;
        } // 找到合并后頭節點

        while(top1 && top2)
        {

            if(top1->data < top2->data)
            {
                mid->next = top1;
                mid = top1;
                top1 = top1->next;
            }
            else
            {
                mid->next = top2;
                mid = top2;
                top2 = top2->next;
            }
        }
        if(top1)
        {
            mid->next = top1;
        }
       else  if(top2)
        {
            mid->next = top2;
        }
    }
    return head_3;
}

//我們可以采用二叉樹插入時的 遞歸法
NODE* MerageByDG(NODE* head_1, NODE* head_2)
{
    if(NULL == head_1)
    {
        return head_2;
    }
    else if(NULL == head_2)
    {
        return head_1;
    }
    NODE* head_3;
    if(head_1->data < head_2->data)
    {
        head_3 = head_1;
        head_3->next = MerageByDG(head_1->next, head_2);
    }
    else
    {
        head_3 = head_2;
        head_3->next = MerageByDG(head_1, head_2->next);
    }
    return head_3;
}

int main()
{
    int a[]={1,3,5,7};
    int c[]={2,4,6,8,10};
    NODE* list1 = CreateList(a,4);
    NODE* list3 = CreateList(c,5);
    list1=MerageByDG(list1, list3);
    for(NODE* temp =list1;temp; temp = temp->next)
    {
        cout<< temp->data<<" ";
    }
    cout<<endl;
    return 0;
}

普通數據時可用如下方法 用冒泡排序法

#include <iostream>
#include <cstring>
using namespace std;
typedef struct node
{
    int data;
    struct node* next;
}NODE;
NODE* CreateList(int a[], int n)
{
    NODE* p;
    NODE* q;
    NODE* head;
    p = new NODE;
    p->data = a[0];
    head =p;
    for(int i=1;i<n;i++)
    {
        q = new NODE;
        q->data = a[i];
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return head;
}
void BubbleSort(NODE* list)
{
    for(NODE* temp1= list;temp1; temp1=temp1->next)
    {
        for(NODE* temp2 =temp1->next; temp2; temp2=temp2->next)
        {
            if(temp1->data >temp2->data)
            {
                int temp = temp1->data;
                temp1->data = temp2->data;
                temp2->data = temp;
            }
        }
    }
}
NODE* Merge (NODE* list1, NODE* list2)
{

    NODE* temp2=list2;
    NODE* temp1=list1;
    NODE* front=NULL;
    for(;temp2; temp2 = temp2->next)
    {
        for(;  temp1;  front = temp1,temp1=temp1->next)
        {
            if(  ((temp2->data)  < (temp1->data)) && (front==NULL))
            {
                NODE* temp = new NODE;
                temp->data = temp2->data;
                temp->next = list1;
                list1 = temp;
                break;
            }
            else if( (front != NULL) && (front->data < temp2->data) &&  (temp1->data >= temp2->data) )
            {
                NODE* temp = new NODE;
                temp->data = temp2->data;
                temp->next = temp1;
                front->next = temp;
                break;
            }
            else if ( ( (temp2->data)>(temp1->data) ) && (NULL==temp1->next)  )
            {
                NODE* temp = new NODE;
                temp->data = temp2->data;
                temp1->next = temp;
                temp->next =NULL;
                break;
            }
        }
        temp1 = list1;
        front = NULL;
    }
    return list1;
}
int main()
{
    int a[]={5,6,6,7};
    int b[]={8,6,4,1};
     int c[]={3,5,6,7,8};
    NODE* list1 = CreateList(a,4);
    NODE* list2 = CreateList(b,4);
    NODE* list3 = CreateList(c,5);
    list1=Merge(list1, list2);
    list1=Merge(list1,list3);
    for(NODE* temp =list1;temp; temp = temp->next)
    {
        cout<< temp->data<<" ";
    }
    cout<<endl;
    BubbleSort(list2);
    for(NODE* temp = list2; temp;  temp=temp->next)
    {
        cout<< temp->data<<" ";
    }
    cout<<endl;
    return 0;
}

“C++怎么實現3個鏈表排序整合到一起”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！