[solved] sortowanie bąbelkowe - lista dwukierunkowa

Witam, napisałem kawałek kodu, m.in jest tam opcja sortowania i niestety mi nie działa, tj nie sortuje, Program się kompiluje uruchamia ale gdy wybiorę sortowanie to klapa…

struct lista_zoo

{ 

	lista_zoo *next; //wskaźnik do następnego elementu

	lista_zoo *prev; //wskaźnik do poprzedniego elementu

	string gromada;

	string rodzina;

	string gatunek;

	string waga;

	string data_sprowadzenia;

};

void sortowanie() //bąbelkowe

{


	int i, j, zamiana;

	lista_zoo *tmp=new lista_zoo[sizeof(lista_zoo)];//wskaźnik pomocniczy

	for(i=1; i
	{

		biezacy=tail;

		poprzedni=biezacy->prev;

		for(j=ilosc-1; j>=1; j--) //pętla porównująca sąsiednie elementy

		{

			zamiana=0; //w przypadku zamiany zmiana wartosci	

			if((biezacy->gromada)<(poprzedni->gromada))

			{

				zamiana=1;

				if(j==ilosc-1)

				{

					tmp=poprzedni;

					tail=poprzedni;

					tail->next=NULL;

					tail->prev=biezacy;

					biezacy->next=tail;

					biezacy->prev=tmp->prev;

				}

				if(j==1)

				{

					tmp=poprzedni;

					poprzedni->next=biezacy->next;

					poprzedni->prev=biezacy;

					head=biezacy;

					biezacy->prev=NULL;

					biezacy->next=poprzedni;

				}

				else

				{

					tmp=poprzedni;

					poprzedni->prev=biezacy;

					poprzedni->next=biezacy->next;

					biezacy->prev=tmp->prev;

					biezacy->next=poprzedni;

				}

			}

			if(zamiana==1)

			{

				poprzedni=biezacy->prev;

			}

			else

			{

				tmp=poprzedni;

				biezacy=poprzedni;

				poprzedni=tmp->prev;

			}

		}

	}

}

gdzie “ilosc” to liczba elementów na liście.

Przy zamianie miejscami sąsiednich elementów musisz osobno obsłużyć następujące warunki graniczne:

AB*…

…*AB*…

…*AB

AB

gdzie A i B zamieniane miejscami elementy, * - inny istniejący element, … - brak lub kilka elementów.

Zamiana w każdym z tych 4-ch przypadków jest zupełnie inna.

Skoro to C++, to jest sens odkrywać koło na nowo, jeśli mamy STL?

Teraz mam tak:

void sortowanie() //bąbelkowe

{


	int i, j, zamiana;

	lista_zoo *tmp=new lista_zoo[sizeof(lista_zoo)];//wskaźnik pomocniczy

	for(i=1; i
	{

		biezacy=tail;

		poprzedni=biezacy->prev;

		for(j=ilosc-1; j>=1; j--) //pętla porównująca sąsiednie elementy

		{

			zamiana=0; //w przypadku zamiany zmiana wartosci	

			if((biezacy->gromada)<(poprzedni->gromada))

			{

				zamiana=1;

				if((j==ilosc-1)&&(&poprzedni!=&head))

				{

					tmp=poprzedni;

					tail=poprzedni;

					tail->next=NULL;

					tail->prev=biezacy;

					biezacy->next=tail;

					biezacy->prev=tmp->prev;

				}

				if((j==1)&&(&biezacy!=&tail))

				{

					tmp=poprzedni;

					poprzedni->next=biezacy->next;

					poprzedni->prev=biezacy;

					head=biezacy;

					biezacy->prev=NULL;

					biezacy->next=poprzedni;

				}

				if((&biezacy==&tail)&&(&poprzedni==&head))

				{

					poprzedni->next=NULL;

					poprzedni->prev=biezacy;

					biezacy->next=poprzedni;

					biezacy->prev=NULL;

				}

				else

				{

					tmp->prev=poprzedni->prev;

					poprzedni->prev=biezacy;

					poprzedni->next=biezacy->next;

					biezacy->prev=tmp->prev;

					biezacy->next=poprzedni;


				}

			}

			if(zamiana==1)

			{

				poprzedni=biezacy->prev;

			}

			else

			{

				tmp=poprzedni;

				biezacy=poprzedni;

				poprzedni=tmp->prev;

			}

		}

	}

}

gdzie: AB*…

if((j==1)&&(&biezacy!=&tail))

				{

					tmp=poprzedni;

					poprzedni->next=biezacy->next;

					poprzedni->prev=biezacy;

					head=biezacy;

					biezacy->prev=NULL;

					biezacy->next=poprzedni;

				}

…*AB

if((j==ilosc-1)&&(&poprzedni!=&head))

				{

					tmp=poprzedni;

					tail=poprzedni;

					tail->next=NULL;

					tail->prev=biezacy;

					biezacy->next=tail;

					biezacy->prev=tmp->prev;

				}

…*AB*…

else

				{

					tmp->prev=poprzedni->prev;

					poprzedni->prev=biezacy;

					poprzedni->next=biezacy->next;

					biezacy->prev=tmp->prev;

					biezacy->next=poprzedni;


				}

AB

if((&biezacy==&tail)&&(&poprzedni==&head))

				{

					poprzedni->next=NULL;

					poprzedni->prev=biezacy;

					biezacy->next=poprzedni;

					biezacy->prev=NULL;

				}

LIsta dalej nie jest posortowana i mam posortowany pierwszy element poprawnie a reszta elementów to “stary” pierwszy element tablicy… Proszę o jakąś wskazówkę czy wszystkie mam źle czy tylko któreś konkretnie, czy też warunki w if są do bani.

To do czego sam doszedłem to fakt, że nie zamieniają się elementy i przy próbie wyświetlenia mam naruszenie ochrony pamięci ale nie wiem jak poprawić aby było dobrze bo ja nie widze błedu w zamianie

Co do STL to owszem, ale gdybym konstruował liste po raz n-ty a to jest moja pierwsza i chciałbym wiedzieć co się dzieje a nie korzystać z gotowców za pierwszym razem.

Tak nakręcono że trudno dociec gdzie masz błąd.

Dla mnie o wiele prościej napisać działający kod niż znaleźć taką minimalną poprawkę która by naprawiła tak cudaczne rozwiązanie.

#include 

using namespace std;


struct element

  {

   element *next,*prev;

   int v;

  };


struct List

  {

   element *head,*tail;

  };


void show(const List &L)

  {

   for(element *i=L.head;i;i=i->next) cout<v<
   cout<
  }


void back(const List &L)

  {

   for(element *i=L.tail;i;i=i->prev) cout<v<
   cout<
  }


void swap(List &L,element *a,element *b)

  {

   element *ap=a->prev,*an=a->next,*bp=b->prev,*bn=b->next;

   a->next=bn;

   (bn?bn->prev:L.tail)=a;   

   b->next=a;

   a->prev=b;   

   b->prev=ap;

   (ap?ap->next:L.head)=b;

  }


void sort(List &L)

  {

   for(element *m=L.tail,*mn;m;m=mn)

     {

      mn=0;

      for(element *i=L.head,*n=i->next;(n)&&(i!=m);i=n,n=i->next)

        {

         if((i->v)>(n->v))

           {

            swap(L,i,n);

            mn=n=i;

           }

        }

     }

  }


void app(List &L,int v)

  {

   element *tmp=new element;

   tmp->v=v;

   tmp->next=0;

   tmp->prev=L.tail;

   L.tail=(L.tail?L.tail->next:L.head)=tmp;

  }


void clear(List &L)

  {

   while(L.head)

     {

      element *tmp=L.head;

      L.head=tmp->next;

      delete tmp;

     }

   L.tail=0;

  }


int main()

  {

   List L={0,0};

   int tb[]={9,8,7,6,5,4,3,2,1};

   int tbsize=sizeof(tb)/sizeof(*tb);


   for(int i=0;i
   show(L);

   back(L);


   sort(L);


   show(L);

   back(L);

   clear(L);

   cin.get();

   return 0;

  }

UWAGA, swap przystosowany tylko do sytuacji *AB*, czyli B zawsze idzie po A.

Poradziłem sobie już, dziękuję za pomoc oto gotowy kod gdyby ktoś potrzebował:

void zamiana1(lista_zoo *a,lista_zoo *b)

{

   lista_zoo *ap=a->prev,*an=a->next,*bp=b->prev,*bn=b->next;

   a->next=NULL;

   (bn?bn->prev:tail)=a;   

   b->next=a;

   a->prev=b;   

   b->prev=ap;

   (ap?ap->next:head)=b;

   tail=a;

}


void zamiana2(lista_zoo *a,lista_zoo *b)

{

   lista_zoo *ap=a->prev,*an=a->next,*bp=b->prev,*bn=b->next;

   a->next=bn;

   (bn?bn->prev:tail)=a;   

   b->next=a;

   a->prev=b;   

   b->prev=NULL;

   (ap?ap->next:head)=b;

   head=b;

}


void zamiana3(lista_zoo *a,lista_zoo *b)

{

   lista_zoo *ap=a->prev,*an=a->next,*bp=b->prev,*bn=b->next;

   a->next=NULL;

   (bn?bn->prev:tail)=a;   

   b->next=a;

   a->prev=b;   

   b->prev=NULL;

   (ap?ap->next:head)=b;

   head=b;

   tail=a;

}


void zamiana4(lista_zoo *a,lista_zoo *b)

{

   lista_zoo *ap=a->prev,*an=a->next,*bp=b->prev,*bn=b->next;

   a->next=bn;

   (bn?bn->prev:tail)=a;   

   b->next=a;

   a->prev=b;   

   b->prev=ap;

   (ap?ap->next:head)=b;

}	


void sortowanie() //bąbelkowe

{


	int i, j, zamiana;

	lista_zoo *tmp=new lista_zoo[sizeof(lista_zoo)];//wskaźnik pomocniczy

	for(i=1; i
	{

		biezacy=tail;

		poprzedni=biezacy->prev;

		for(j=ilosc-1; j>=1; j--) //pętla porównująca sąsiednie elementy

		{

			zamiana=0; //w przypadku zamiany zmiana wartosci	

			if((biezacy->gromada)<(poprzedni->gromada))

			{;

				if((biezacy==tail)&&(poprzedni!=head))

				{

					zamiana=1;

					zamiana1(poprzedni, biezacy);

				}

				if((j==1)&&(poprzedni==head))

				{

					zamiana=1;

					zamiana2(poprzedni, biezacy);

				}

				if((biezacy==tail)&&(poprzedni==head))

				{

					zamiana=1;

					zamiana3(poprzedni, biezacy);

				}

				if(zamiana==0)

				{

					zamiana=1;

					zamiana4(poprzedni, biezacy);

				}

			}

			if(zamiana==1)

			{

				poprzedni=biezacy->prev;

			}

			else

			{

				tmp->prev=poprzedni->prev;

				biezacy=poprzedni;

				poprzedni=tmp->prev;

			}

		}

	}

}

Powiedz mi tylko po kiego tyle wersji zamian? U mnie na jednej działa.