http://eduinf.waw.pl/inf/alg/001_search/0097.php
Po dodaniu szablonów wartownicy w funkcjach
split oraz merge trochę przeszkadzają (nie wiadomo jak je zainicjalizować)
Jakieś propozycje jak się ich pozbyć
Jakieś propozycje jak usunąć rekursję ?
Podobno może ona powodować przepełnienie stosu
Na wiki proponują pominąć etap dzielenia i zacząć od razu scalanie
Listę przeglądamy za pomocą wskaźników a nie za pomocą indeksów
Wolałbym nie wprowadzać całkowitoliczbowych indeksów
Ad 1. Przeanalizuj jak algorytm działa i zbuduj inną swoją implementacje
Ad 2. Dzielisz za każdym razem przez dwa, czyli jeżeli masz 1 miliard elementów to będziesz mieć jakieś 30 zagnieżdżonych wywołań, więc nie ma co się obawiać przepełnienia stosu.
Ad 3. Na wiki ten algorytm jest dla tablic nie dla list.
Fałszywe elementy ułatwiają konstrukcję algorytmu – dzięki nim listy nie są puste i można ich adresy przypisać bezpośrednio wskaźnikom p1 i p2. W przeciwnym razie musielibyśmy modyfikować algorytm dla pierwszego wstawianego na listę elementu. A tak zawsze dodajemy jedynie następnik elementu, który już na liście się znajduje. Na końcu algorytmu po prostu usuwamy dodane elementy i otrzymujemy właściwe listy.
Oto co Wałaszek , autor tych funkcji napisał o użytych wartownikach
Każdy pisze sobie tylko tyle ile wie (na 100% nie więcej) ...
Znacznie lepszy efekt uzyskuje się poprzez podwójny wskaźnik - nie trzeba żadnych przydzieleń ani usunięć.
Można również oprogramować to inaczej - jako dodawanie na koniec listy, poczynając od największych elementów.
void List::split(List & l1, List & l2)
{
Node* fast;
Node* slow;
if(L==NULL||L->Next()==NULL)
{
l1.L=L;
l2.L=NULL;
}
else
{
slow=L;
fast=L->Next();
}
while(fast!=NULL)
{
fast=fast->Next();
if(fast!=NULL)
{
slow=slow->Next();
fast=fast->Next();
}
}
l1.L=L;
l2.L=slow->Next();
slow->changeNext(NULL);
}
Dodawanie na końcu to raczej dla listy dwukierunkowej
Gdy wkleiłem powyższy kod to nie zatrzymuje się
Jak dopisałem nowy konstruktor tym razem bez parametrów to wartownicy już trochę mniej przeszkadzają
chociaż ich usunięcie zwolniłoby miejsce w pamięci
Krzywy Lew napisał(a):
... Dodawanie na końcu to raczej dla listy dwukierunkowej ...
Kto ci takie bzdury naopowiadał?
Po pierwsze, sama klasa listy może zawieraćheaditailnadal dodanie na koniec oraz na początek ma koszt 0(1): http://4programmers.net/Forum/C_i_C++/262765-listy_dodawanie_pierwszego_el?p=1203991#id1203991
Po drugie, ponieważ dodajesz w jednej metodzie to możesz wskaźnik na koniec trzymać na zewnątrz klasy.
Co do kodu - bez konkretnego kodu który da się skompilować - to tylko do wróżbitów.
Myślałem że wstawianie na koniec to operacja liniowa tzn że musimy przejść wskaźnikami całą listę aby dodać na koniec
co mogłoby zwiększyć złożoność a wskaźnik tail występuje tylko w dwukierunkowych
Ile pamięci możemy zaoszczędzić pozbywając się wartowników
Oto kod który powinien się skompilować
#include <iostream>
#include <cstdlib>
using namespace std;
template <class T>
class Node
{
private:
T data;
Node<T> *next;
public:
Node<T>(){next=NULL;}
Node<T> (T dane) { data = dane; next = NULL; }
T Data () { return data; }
Node<T> * Next () { return next; }
void changeNext (Node<T> *n) { next = n; }
};
template <class T>
class List
{
private:
Node<T> *L;
public:
List () { L = NULL; }
~List () { removeallNode (); }
bool emptyList (); // zwraca 1, jesli lista jest pusta
void addNode (Node<T> *n); //dodaje wierzcho�ek n na pocz�tek listy
void printNode (); //drukuje list�
void removeNode (Node<T> *n); //usuwa wierzcho�ek
void removeallNode (); //usuwa ca�� list�
Node<T> *locateNode (T i); //zwraca wska�nik do wierzcho�ka zawieraj�cego warto�� i
void split(List<T> & , List<T> & );
void merge(List<T> & , List<T> & );
void merge_sort();
};
template<class T>
bool List<T>::emptyList (){ // zwraca 1, jesli lista jest pusta
if (L == NULL) return 1;
else return 0;
}
template<class T>
void List<T>::addNode (Node<T> *n){ //dodaje wierzcho�ek n na pocz�tek listy
n -> changeNext (L);
L = n;
}
template<class T>
void List<T>::printNode (){ //drukuje list�
Node<T> *q;
q = L;
while (q != NULL)
{
cout << q -> Data() << endl;
q = q -> Next();
}
}
template<class T>
void List<T>::removeNode (Node<T> *n){ //usuwa wierzcho�ek
if (L == n)
{
L = L -> Next();
delete n;
}
else {
Node<T> *q;
q = L;
while ((q -> Next() != NULL) && (q -> Next() != n)) q = q -> Next();
if (q -> Next() == n)
{
q -> changeNext (q -> Next() -> Next());
delete n;
}
}
}
template<class T>
void List<T>::removeallNode (){ //usuwa ca�� list�
Node<T> *q;
while (L != NULL)
{
q = L;
L = L -> Next ();
delete q;
}
}
template<class T>
Node<T> *List<T>::locateNode (T i){ //zwraca wska�nik do wierzcho�ka zawieraj�cego warto�� i
Node<T> *q;
q = L;
while ((q != NULL) && (q -> Data() != i)) q = q -> Next ();
return q;
}
template<class T>
void List<T>::split(List<T> & l1, List<T> & l2)
{
Node<T> * p1, * p2;
bool s = false;
l1.addNode(new Node<T>());
l2.addNode(new Node<T>());
p1 = l1.L;
p2 = l2.L;
while(L)
{
if(s)
{
p2->changeNext(L) ;
p2 = p2->Next();
}
else
{
p1->changeNext(L);
p1 = p1->Next();
}
L = L->Next();
s = !s;
}
p1->changeNext(NULL);
p2->changeNext(NULL);
l1.removeNode(l1.L);
l2.removeNode(l2.L);
}
template<class T>
void List<T>::merge(List<T> & l1, List<T> & l2)
{
Node<T> * p;
Node<T> * q=new Node<T>();
addNode(q);
p = L;
while(l1.L && l2.L)
{
if(l1.L->Data() > l2.L->Data())
{
p->changeNext(l2.L);
l2.L = l2.L->Next();
}
else
{
p->changeNext(l1.L);
l1.L = l1.L->Next();
}
p = p->Next();
}
while(l1.L)
{
p->changeNext(l1.L);
l1.L = l1.L->Next();
p = p->Next();
}
while(l2.L)
{
p->changeNext(l2.L);
l2.L = l2.L->Next();
p = p->Next();
}
removeNode(L);
}
template<class T>
void List<T>::merge_sort()
{
List<T> h1,h2;
if(L && L->Next())
{
split(h1,h2);
h1.merge_sort();
h2.merge_sort();
merge(h1,h2);
}
}
/*void List::split(List & l1, List & l2)
{
Node* fast;
Node* slow;
if(L==NULL||L->Next()==NULL)
{
l1.L=L;
l2.L=NULL;
}
else
{
slow=L;
fast=L->Next();
}
while(fast!=NULL)
{
fast=fast->Next();
if(fast!=NULL)
{
slow=slow->Next();
fast=fast->Next();
}
}
l1.L=L;
l2.L=slow->Next();
slow->changeNext(NULL);
}*/
int main ()
{
int wybor, liczba;
List<int> lista;
do
{
cout << "****************************\n";
cout << "* Lista pojedynczo wiazana *\n";
cout << "****************************\n";
cout << "\n\n1 - dodawanie liczby do listy\n";
cout << "2 - drukowanie listy\n";
cout << "3 - usuwanie liczby z listy\n";
cout << "4 - usuwanie wszystkich liczb\n";
cout << "5 - szukanie liczby\n";
cout << "6 - sortowanie listy\n";
cout << "0 - wyjscie z programu\n";
cout << "Twoj wybor?\t";
cin >> wybor;
switch (wybor)
{
case 1: cout << "\n\nPodaj liczbe:\t";
cin >> liczba;
Node<int> *q;
q = new Node<int> (liczba);
lista.addNode(q);
break;
case 2: if (!lista.emptyList())
{
cout << "\n\nNa liscie sa:\n";
lista.printNode();
}
else cout << "\n\nLista pusta\n";
system ("PAUSE");
break;
case 3: cout << "\n\nPodaj liczbe:\t";
cin >> liczba;
Node<int> *r;
r = lista.locateNode(liczba);
if (r) lista.removeNode(r);
else cout << "\n\nNie ma takiej liczby na liscie\n";
system ("PAUSE");
break;
case 4: lista.removeallNode();
break;
case 5: cout << "\n\nPodaj liczbe:\t";
cin >> liczba;
Node<int> *s;
s = lista.locateNode(liczba);
if (s) cout << "Liczba jest na liscie\n";
else cout << "Liczby nie ma na liscie\n";
system ("PAUSE");
break;
case 6: lista.merge_sort();
system("PAUSE");
break;
}
system ("CLS");
}
while (wybor != 0);
return 0;
}
Funkcja w której próbowałem pozbyć się wartowników jest zakomentowana
Przy tak skonstruowanej klasie, niczego oprócz strażników nie pozostaje.
Klasa jest skonstruowana źle, Node powinna być zwykłą strukturą wewnętrzna - może być prywatną.
Pamięci ani czasu dużo nie zaoszczędzisz.
Przy poprawnej konstrukcji można napisać coś takiego:
template<class T> void List<T>::split(List<T> &a,List<T> &b)
{
Node<T> **tb[]={&a.L,&b.L};
for(bool s=false;L;s=!s)
{
Node<T> *tmp=*(tb[s]);
tmp->next=L; // tu można zastosować changeNext(0);
tb[s]=&(tmp->next); // tu potrzebujemy dostęp do składowej next aby mieć jej adres.
L=L->next; // tu można zastosować Next();
}
(*(tb[false]))->next=(*(tb[true]))->next=0; // tu można zastosować changeNext(0);
}