Combinar tipo de listas enlazadas simples

ordenamiento por mezcla class sola lista enlazada mediante el programa C: En este artículo, vamos a ver cómo ordenar dos listas enlazadas utilizando ordenamiento por mezcla ?

Planteamiento del problema: Escribir un programa en C ++ para ordenar dos listas enlazadas individuales utilizando la técnica de combinación de tipo.

Solución: Combinar tipo es una técnica eficaz for clasificación listas enlazadas utilizando la recursividad.

algoritmo de ordenamiento por mezcla for

  1. Dividir la lista en dos mitades.
  2. llamada a la función recursiva mergesort () dos listas especie del individuo.
  3. Combinar dos listas ordenadas.

1. Dividir la lista en dos mitades

Utilizamos la tortuga y la liebre algoritmo de partición for la lista enlazada de Floyd en dos mitades. Declaramos un puntero lento y un puntero rápido. puntero pasa lento un paso por delante, donde los rápidos puntero pasa de dos pasos a la vez. Así, cuando el puntero rápido llega al final de la lista, el puntero es lenta en la mitad del camino.

    slow=head; //head of the list
fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
//split1 && split2 points to the head of the split list
*split1=head;
*split2=slow->next;
//split the list by partitioning
slow->next=NULL; //partitioning

2. Llame a la función recursiva por fusión () dos ordenar las listas individuales

Deje SPLIT1 y SPLIT2 puntos a los dos lista individual después de la partición.

Llamamos por fusión () de forma recursiva dos especie esta lista dos.

    mergeSort(&split1);
mergeSort(&split2);

3. Combinar dos lista ordenada

class fusionar dos lista clasificada en otra lista ordenada.

Podemos hacerlo mediante la comparación de elementos de dos listas.

C ++ Merge aplicación for tipo Finally individuales listas enlazadas

#include<bits/stdc++.h>
using namespace std;
class node{
    public:
int data; // data field
struct node *next;
};
void display(class node* head){
node* current=head; // current node set to head
while(current!=NULL){ //traverse until current node isn't NULL
printf("%d ",current->data);
current=current->next; // go to next node
}
}
node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}
node* mergeList(node* split1,node* split2){
//merging two sorted list
node* newhead=NULL;
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
//recursively merge
if(split1->data<=split2->data){
newhead=split1;
newhead->next=mergeList(split1->next,split2);
}
else{
newhead=split2;
newhead->next=mergeList(split1,split2->next);
}
return newhead;
}
void splitList(node* head,node** split1,node** split2){
//similar to flyod's tortoise algorithm
node* slow=head;
node* fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split1=head;
*split2=slow->next;
//spliting
slow->next=NULL;
}
void mergeSort(node** refToHead){
node* head=*refToHead;
node* split1,*split2;
//base case
if(head==NULL || head->next==NULL){
return;
}
//split the list in two halves
splitList(head,&split1,&split2);
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
//merge two sorted list
*refToHead=mergeList(split1,split2);
return;
}
int main(){
printf("creating the linked list by inserting new nodes at the endn");
printf("enter 0 to stop building the list, else enter any integern");
int k,count=1,x;
node* curr,*temp;
scanf("%d",&k);
node* head=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head;
///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"before merge sort...n";
display(head); // displaying the list
cout<<"nafter merge sort...n";
mergeSort(&head);
display(head);
return 0;
}

salida

creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
6 5 4 7 1 0
before merge sort...
6 5 4 7 1
after merge sort...
1 4 5 6 7

Ejemplo con explicación

Let the linked be
6->5->4->7->1->NULL

Head=6
----------------------------------------------------------------
mergeSort(6)
6 !=NULL
6->next !=NULL
Call to splitList(6,split1,split2)
----------------------------------------------------------------
In splitList(6,split1,split2):
slow=6
fast=6->next=5
iteration 0:
5!=NULL
fast=5->next=4
4!=NULL
slow=6->next=5
fast=4->next=7
iteration 1:
7!=NULL
fast=7->next=1
1!=NULL
slow=5->next=4
fast=1->next=NULL
iteration 2:
fast==NULL
so iteration stops
split1=6(head)
split2=slow->next=4->next=7
slow->next=NULL
thus the partitioned linked lists are
split1=6->5->4->NULL
split2=7->1->NULL
----------------------------------------------------------------
Now we individually sort split1 & split2 recursively
Thus needless to say it again partitions
both the list until base cases is reached.
The ultimate outcome is the two sorted list
Split1 pointing to 4->5->6->NULL
Split2 pointing to 1->7->NULL
----------------------------------------------------------------
Now we merge this two sorted list to produce the ultimate sorted list
mergeList(split1, split2) // mergeList(4, 1)
Split1!=NULL
Split2!=NULL
Split1->data>split2->data (4>1)
Thus newhead =split2 // newhead =1
newhead->next=mergeList(split1, split2->next));
Call mergeList(split1, split2->next) // (4, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(4,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (4<7)
Thus newhead =split1 // newhead =4
newhead->next=mergeList(split1->next, split2));
Call mergeList(split1->next, split2) // (5, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(5,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (5<7)
Thus newhead =split1 // newhead =5
newhead->next=mergeList(split1->next, split2));
Call mergeList(split1->next, split2) // (6, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(6,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (6<7)
Thus newhead =split1 // newhead =6
newhead->next=mergeList(split1->next, split2));
Call mergeList(split1->next, split2) // (NULL, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(5,7)
Split1==NULL
Return split2 (7->NULL)
----------------------------------------------------------------
Thus at mergeList(6,7)
newhead=6
newhead->next=7->NULL
function returns 6->7->NULL
----------------------------------------------------------------
Thus at mergeList(5,7)
newhead=5
newhead->next=6->7->NULL
function returns 5->6->7->NULL
----------------------------------------------------------------
Thus at mergeList(4,7)
newhead=4
newhead->next=5->6->7->NULL
function returns 4->5->6->7->NULL
----------------------------------------------------------------
Thus at mergeList(4,1)
newhead=1
newhead->next=4->5->6->7->NULL
function returns 1->4->5->6->7->NULL
Which is the sorted list


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *