// Main.cpp
#include <cstdlib>
#include <ctime>
#include <iostream>
#include "DoublyLinkedList.hpp"
using namespace std;
int Compare(int a,int b)
{
return a - b;
}
int main(int argc, char *argv[])
{
int k,n,m;
DoublyLinkedList<int> L;
srand(time(NULL));
cin>>n>>m;
for(k = 1;k <= n;k++)
L.insertLast(rand()%m);
L.displayForward();
L.displayBackward();
L.MergeSort(Compare);
L.displayForward();
L.displayBackward();
while(!L.isEmpty())
L.deleteFirst();
system("PAUSE");
return EXIT_SUCCESS;
}
// Link.hpp
template<class T>
class Link
{
private:
T data;
Link<T> *next;
Link<T> *previous;
public:
Link(T data);
void displayLink();
T getData();
void setData(T data);
Link<T> *getNext();
void setNext(Link<T> *next);
Link<T> *getPrevious();
void setPrevious(Link<T> *previous);
template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);
};
template<class T>
Link<T>::Link(T data)
{
setData(data);
setNext(NULL);
setPrevious(NULL);
}
template<class T>
void Link<T>::displayLink()
{
std::cout<<getData()<<" ";
}
template<class T>
T Link<T>::getData()
{
return data;
}
template<class T>
void Link<T>::setData(T data)
{
this->data = data;
}
template<class T>
Link<T> *Link<T>::getNext()
{
return next;
}
template<class T>
void Link<T>::setNext(Link<T> *next)
{
this->next = next;
}
template<class T>
Link<T> *Link<T>::getPrevious()
{
return previous;
}
template<class T>
void Link<T>::setPrevious(Link<T> *previous)
{
this->previous = previous;
}
template <class U>
std::ostream& operator<<(std::ostream& print, Link<U> & L)
{
print << L.getData();
return print;
}
//DoublyLinkedList.hpp
#include "Link.hpp"
template<class T>
class DoublyLinkedList
{
private:
Link<T> *first;
Link<T> *last;
Link<T> *headdel();
void tailins(Link<T> *p);
public:
DoublyLinkedList();
~DoublyLinkedList();
Link<T> *getFirst();
void setFirst(Link<T> *first);
Link<T> *getLast();
void setLast(Link<T> *first);
bool isEmpty();
Link<T> *find(T key);
void insertFirst(T dd);
void insertLast(T dd);
void deleteFirst();
void deleteLast();
bool insertAfter(T key,T dd);
void deleteKey(T key);
void displayForward();
void displayBackward();
bool Split(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T));
void Merge(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T));
void MergeSort(int (*Compare)(T,T));
};
template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
setFirst(NULL);
setLast(NULL);
}
template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
while(!isEmpty())
{
deleteFirst();
}
}
template<class T>
Link<T> *DoublyLinkedList<T>::getFirst()
{
return first;
}
template<class T>
void DoublyLinkedList<T>::setFirst(Link<T> *first)
{
this->first = first;
}
template<class T>
Link<T> *DoublyLinkedList<T>::getLast()
{
return last;
}
template<class T>
void DoublyLinkedList<T>::setLast(Link<T> *last)
{
this->last = last;
}
template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
return getFirst()==NULL;
}
template<class T>
Link<T> *DoublyLinkedList<T>::find(T key)
{
Link<T> *current = getFirst();
while(current != NULL && !(current->getData == key))
current = current->getNext();
return current;
}
template<class T>
void DoublyLinkedList<T>::insertFirst(T dd)
{
Link<T> *newLink = new Link<T>(dd);
if(isEmpty())
setLast(newLink);
else
getFirst()->setPrevious(newLink);
newLink->setNext(getFirst());
setFirst(newLink);
}
template<class T>
void DoublyLinkedList<T>::insertLast(T dd)
{
Link<T> *newLink = new Link<T>(dd);
if(isEmpty())
{
setFirst(newLink);
}
else
{
getLast()->setNext(newLink);
newLink->setPrevious(getLast());
}
setLast(newLink);
}
template<class T>
void DoublyLinkedList<T>::deleteFirst()
{
if(isEmpty())
return;
Link<T> *temp = getFirst();
if(getFirst()->getNext() == NULL)
setLast(NULL);
else
getFirst()->getNext()->setPrevious(NULL);
setFirst(getFirst()->getNext());
delete temp;
}
template<class T>
void DoublyLinkedList<T>::deleteLast()
{
if(isEmpty())
return;
Link<T> *temp = getLast();
if(getFirst()->getNext() == NULL)
setFirst(NULL);
else
getLast()->getPrevious()->setNext(NULL);
setLast(getLast()->getPrevious());
delete temp;
}
template<class T>
bool DoublyLinkedList<T>::insertAfter(T key,T dd)
{
Link<T> *current = find(key);
if(current == NULL)
return false;
Link<T> *newLink = new Link<T>(dd);
if(current->getNext() == NULL)
{
newLink->setNext(NULL);
setLast(newLink);
}
else
{
newLink->setNext(current->getNext());
current->getNext()->setPrevious(newLink);
}
newLink->setPrevious(current);
current->setNext(newLink);
return true;
}
template<class T>
void DoublyLinkedList<T>::deleteKey(T key)
{
Link<T> *current = find(key);
if(current==NULL)
return;
if(current->getPrevious() == NULL)
setFirst(current->getNext());
else
current->getPrevious()->setNext(current->getNext());
if(current->getNext() == NULL)
setLast(current->getPrevious());
else
current->getNext()->setPrevious(current->getPrevious());
delete current;
}
template<class T>
void DoublyLinkedList<T>::displayForward()
{
std::cout<<"List (first-->last): ";
Link<T> *current = getFirst();
while(current != NULL)
{
current->displayLink();
current = current->getNext();
}
std::cout<<"\n";
}
template<class T>
void DoublyLinkedList<T>::displayBackward()
{
std::cout<<"List (last-->first): ";
Link<T> *current = getLast();
while(current != NULL)
{
current->displayLink();
current = current->getPrevious();
}
std::cout<<"\n";
}
template <class T>
Link<T> *DoublyLinkedList<T>::headdel()
{
Link<T> *temp = getFirst();
if(!isEmpty())
{
if(getFirst()->getNext() == NULL)
setLast(NULL);
else
getFirst()->getNext()->setPrevious(NULL);
setFirst(getFirst()->getNext());
}
return temp;
}
template <class T>
void DoublyLinkedList<T>::tailins(Link<T> *p)
{
p->setNext(NULL);
if(isEmpty())
{
p->setPrevious(NULL);
setFirst(p);
}
else
{
getLast()->setNext(p);
p->setPrevious(getLast());
}
setLast(p);
}
template <class T>
bool DoublyLinkedList<T>::Split(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T))
{
bool isEmptyB,swapLists;
Link<T> *currNode = NULL;
Link<T> *prevNode = NULL;
isEmptyB = true;
swapLists = true;
if(!isEmpty())
{
currNode = headdel();
A.tailins(currNode);
prevNode = currNode;
}
while(!isEmpty())
{
currNode = headdel();
if(Compare(prevNode->getData(),currNode->getData()) > 0)
swapLists = !swapLists;
if(swapLists)
A.tailins(currNode);
else
{
B.tailins(currNode);
isEmptyB = false;
}
prevNode = currNode;
}
return isEmptyB;
}
template <class T>
void DoublyLinkedList<T>::Merge(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T))
{
Link<T> *tmpA = NULL;
Link<T> *tmpB = NULL;
Link<T> *poprzedniZtmpA = NULL;
Link<T> *poprzedniZtmpB = NULL;
bool koniecSeriiWtmpA, koniecSeriiWtmpB;
if(!A.isEmpty())
{
tmpA = A.headdel();
}
if(!B.isEmpty())
{
tmpB = B.headdel();
}
koniecSeriiWtmpA = (tmpA == NULL);
koniecSeriiWtmpB = (tmpB == NULL);
while(tmpA != NULL || tmpB != NULL)
{
while(!koniecSeriiWtmpA && !koniecSeriiWtmpB)
if(Compare(tmpA->getData(),tmpB->getData()) <= 0)
{
tailins(tmpA);
poprzedniZtmpA = tmpA;
tmpA = A.headdel();
if(tmpA == NULL || Compare(poprzedniZtmpA->getData(),tmpA->getData()) > 0)
koniecSeriiWtmpA = true;
}
else
{
tailins(tmpB);
poprzedniZtmpB = tmpB;
tmpB = B.headdel();
if(tmpB == NULL || Compare(poprzedniZtmpB->getData(),tmpB->getData()) > 0)
koniecSeriiWtmpB = true;
}
while(!koniecSeriiWtmpA)
{
tailins(tmpA);
poprzedniZtmpA = tmpA;
tmpA = A.headdel();
if(tmpA == NULL || Compare(poprzedniZtmpA->getData(),tmpA->getData()) > 0)
koniecSeriiWtmpA = true;
}
while(!koniecSeriiWtmpB)
{
tailins(tmpB);
poprzedniZtmpB = tmpB;
tmpB = B.headdel();
if(tmpB == NULL || Compare(poprzedniZtmpB->getData(),tmpB->getData()) > 0)
koniecSeriiWtmpB = true;
}
koniecSeriiWtmpA = (tmpA == NULL);
koniecSeriiWtmpB = (tmpB == NULL);
poprzedniZtmpA = NULL;
poprzedniZtmpB = NULL;
}
}
template <class T>
void DoublyLinkedList<T>::MergeSort(int (*Compare)(T,T))
{
bool isEmptyB = false;
DoublyLinkedList<T> L1,L2;
while(!isEmptyB)
{
isEmptyB = Split(L1,L2,Compare);
Merge(L1,L2,Compare);
}
}
Tutaj serie są scalane do jednej listy przez co po każdym scaleniu lista musi być rozdzielana
przy czym jedno dodatkowe rozdzielanie wykonywane jest aby sprawdzić czy można zakończyć algorytm
a jedno dodatkowe scalanie jest wykonywane po to aby listę mieć znowu w (*this)
Pomysł na usprawnienie znalazłem w książce Banachowski Diks Rytter Algorytmy i struktury danych
jednak nie wiem jak go zapisać w kodzie
