Sortowanie listy przez łączenie naturalne Mariusz: Chciałbym wykorzystać pomysł łączenia naturalnego do sortowania listy Sortowanie można by podzielić na trzy procedury Procedura rozdzielająca serie na przemian do dwóch list Procedura scalająca serie występujące w dwóch listach Procedura sortująca (Nie tworzymy nowych węzłów tylko ustawiamy dowiązania istniejących węzłów) Do wykrywania końca serii przeglądać listę dwoma wskaźnikami (porównywanie klucza w poprzednim węźle oraz w bieżącym węźle) czy wystarczy jeden wskaźnik (porównywanie klucza w bieżącym węźle i w następnym węźle) Wygląda na to że procedura scalająca będzie nieco bardziej skomplikowana niż w algorytmie rekurencyjnym bo tutaj musimy uwzględnić także scalanie serii Ciekaw jestem waszych pomysłów na zrealizowanie tych funkcji

Mariusz: template<class T> class Node { T data; Node *next; public: Node(T data) { this−>data = data; this−>next = NULL; } T getData(); void setData(T data); Node *getNext(); void setNext(Node *p); }; template<class T> T Node<T>::getData() { return this−>data; } template<class T> void Node<T>::setData(T data) { this−>data = data; } template<class T> Node<T> *Node<T>::getNext() { return this−>next; } template<class T> void Node<T>::setNext(Node *p) { this−>next=p; } template<class T> class List { Node<T> *head; public: List() { this−>head=NULL; } void push(T data); void pop(); Node<T> *searchNode(T data); void insertNode(T data); void deleteNode(T data); void printList(); }; template<class T> void List<T>:: push(T data) { Node<T> *x=new Node<T>(data); x−>setNext(this−>head); this−>head=x; } template<class T> void List<T>:: pop() { Node<T> *p; if(this−>head!=NULL) { p=this−>head; this−>head=this−>head−>getNext(); delete p; } } template<class T> Node<T> *List<T>::searchNode(T data) { Node<T> *x; x=this−>head; while(x!=NULL && x−>getData()!=data) x=x−>getNext(); return x; } template<class T> void List<T>::insertNode(T data) { Node<T> *x=new Node<T>(data); Node<T> *y; Node<T> *z; if(this−>head==NULL) { this−>head=x; x−>setNext(NULL); } else { y=this−>head; z=NULL; while(y!=NULL && x−>getData()>y−>getData()) { z=y; y=y−>getNext(); } x−>setNext(y); if(z!=NULL) { z−>setNext(x); } else { this−>head=x; } } } template<class T> void List<T>:: deleteNode(T data) { Node<T> *x; Node<T> *y; x=this−>searchNode(data); if(this−>head!=NULL && x!=NULL) { if(this−>head==x) { this−>head=x; this−>head=x−>getNext(); delete x; } else { y=this−>head; while(y−>getNext()!=x) { y=y−>getNext(); } y−>setNext(x−>getNext()); delete x; } } } template<class T> void List<T>:: printList() { Node<T> *p=this−>head; while(p!=NULL) { cout<<p−>getData()<<" −> "; p=p−>getNext(); } cout<<"NULL"<<endl; } Ostatnio bawiłem się Pythonem (na Linuksie z płytki tylko Python i C/C++ są dostępne) i postanowiłem podobną klasę napisać w C++ Jak dopisać łączenie naturalne do tej listy

sata: Idz już stąd nudny jesteś.