implementacja listy cyklicznej w c++

[birdman]

walcze juz troche czas uz przerobieniem listy jednokierunkowej na cykliczna... i juz mnie cos trafia... nie ma ktos moze jakiejs elegnackiej implementacji listy cyklicznej??

[dzi]

tail nie wskazuje w NULL tylko na head

przy dodawaniu w pozycje tail ustawiasz tez next na head

jak dwukierunkowa to analogicznie z head

generalnie wywalasz (w sposob sensowny) wszystkie NULLe jakie masz

[ayem]

w zasadzie sama implementacja sie nierozni - struktura pozostaje taka sama, metody sie roznia. Dodatkowo w liscie cykliczenej wystepuje wartownik (jakos musisz oznaczyc pierwsza komorke, zeby przy przeszukiwaniu wiedziec skad zaczac i na czymskonczyc)

[bartolomeo_1]

w zasadzie sama implementacja sie nierozni - struktura pozostaje taka sama, metody sie roznia. Dodatkowo w liscie cykliczenej wystepuje wartownik (jakos musisz oznaczyc pierwsza komorke, zeby przy przeszukiwaniu wiedziec skad zaczac i na czymskonczyc)

No nie do końca. W liście cyklicznej możemy wyróżnić tylko element bieżący na który ustawiony jest wskaźnik start. po co Ci początek takiej listy czy jej koniec, jeżeli jest CYKLICZNA ;) a jeżeli chodzi o przeszukiwanie to po co szukać [OD DO] na zasadzie "wyróżniam początek i koniec". to domena listy niecyklicznej. W liście cyklicznej szukasz aż dotrzesz do punktu z którego wyruszyłeś.

element_listy *start, *temp;//ustaw start i temp na bieżacy element;//sprawdz czy start spełnia kryteria;for(temp = temp->next; temp != start; temp = temp->next) /*tu sobie sprawdz czy temp spełnia kryteria*/;

[ayem]

heh to chyba zalezy od implementacji bo wlasnie sprawdzilem w notatkach i mam podany opis z wartownikiem, czasem lepiej ustawic pole startu bo jak nie znajdzie niczego to zapobiegniesz niekontrolowanemu zapetleniu (wartownik to moze byc dodatkowa komorka z jakims znanym kluczem)

[bartolomeo_1]

czasem lepiej ustawic pole startu bo jak nie znajdzie niczego to zapobiegniesz niekontrolowanemu zapetleniu

ustaiwć pole startu dla AKTUALNEGO poszukiwania czegoś w liście = tak (czyli wskaźnik start). ustawić GENERALNE pole startu = nie (czyli specjalny obiekt). spojżałeś na mój przykład? mając listę cykliczną nie zapętlisz się w nim. Oczywiście można wstawiać tak zwanego wartownika, ale wtedy ta lista traci charakter cykliczności. no bo jak to: cykliczna = nie ma początku i końca, prawda? Ale wszystko zależy od zastosowań tak naprawdę... chodzi o to żeby działało sprawnie i wszystko jedno czy jest tam wartownik czy nie ma, jeżeli tak Ci sie lepiej programuje :) Pozdrawiam!

[birdman]

panowie... jawiem jak to dziala i jak powinno byc napisane... ja poprosru szukam gotowej implementacji...

[dzi]

panowie... jawiem jak to dziala i jak powinno byc napisane... ja poprosru szukam gotowej implementacji...

a to nie tutaj o ile mi wiadomo... ;)

moze google? albo servisy o programowaniu?

[bartolomeo_1]

panowie... jawiem jak to dziala i jak powinno byc napisane... ja poprosru szukam gotowej implementacji...

a to nie tutaj o ile mi wiadomo... ;)

moze google? albo servisy o programowaniu?

słusznie. odechcewa sie pomagać jak ktoś tak niewybrednie stawia pytanie. To nie jest bardzo trudne zagadnienie, szczególnie jeżeli już sam napisałeś listę jednokierunkową. Nawet nie napisałeś co ta lista ma robić, co ma sobą reprezentować. Ale trudno. Prosze oto lista cykliczna:

class node{public:  node *next;};int main() {  node aaa, bbb;  aaa.next = &bbb;  bbb.next = &aaa;}

i masz elegancką liste cykliczna. pozdrawiam

[dzi]

panowie... jawiem jak to dziala i jak powinno byc napisane... ja poprosru szukam gotowej implementacji...

a to nie tutaj o ile mi wiadomo... ;)

moze google? albo servisy o programowaniu?

słusznie. odechcewa sie pomagać jak ktoś tak niewybrednie stawia pytanie. To nie jest bardzo trudne zagadnienie, szczególnie jeżeli już sam napisałeś listę jednokierunkową. Nawet nie napisałeś co ta lista ma robić, co ma sobą reprezentować. Ale trudno. Prosze oto lista cykliczna:

class node{public:  node *next;};int main() {  node aaa, bbb;  aaa.next = &bbb;  bbb.next = &aaa;}

i masz elegancką liste cykliczna. pozdrawiam

Hehe, no, schludna odpowiedz ;)

[birdman]

/**** definicja klasy lista jednokierunkowa ****/

// od paranoika - wstawiłem w tagi 'code' bo się rozjeżdżało.

#include <iostream>using namespace std;class lista {public:struct node{	node * next;	double obj;	node(): next(NULL) {};	~node()	{  while(next) 	 {  node * wsk_next = next->next;	// 1    next->next = NULL;    // 2    delete (next);      // 3    next = wsk_next;   	 // 4 	 }	}};private:  node * first;public:lista() : first(NULL) {}~lista() {}lista(const lista & wzor){	node * spointer;	node * pointer;	pointer = first = NULL;	spointer = wzor.first;		while(spointer)	{  node * temp = new node;	  temp -> obj = spointer ->obj;	    if(first == NULL)  {    first = temp;    pointer = temp;  } else   {    pointer ->next = temp;    pointer = temp;  }  spointer = spointer -> next;    	}	}lista & operator= (const lista& wzor){	delete (first);	node * spointer;	node * pointer;	pointer = first = NULL;	spointer = wzor.first;	while(spointer)	{  node * temp = new node;	  temp -> obj = spointer ->obj;  if(first == NULL)  {    first = temp;    pointer = temp;  }  else   {    pointer ->next = temp;    pointer = temp;  }  spointer = spointer -> next;    	}	return *this;}bool findelem(double value , node ** prev , node ** curr){	*prev = NULL;	*curr = first;	while( *curr != NULL)	{ 	 if( (*curr) -> obj == value) return true; 	 *prev = *curr; 	 *curr = (*curr) ->next;	}	return false;}void insert(double wstawka){	node * prev;	node * curr;	if(!findelem(wstawka , &prev , &curr))	{  node * temp = new node;  temp -> next = first;  first = temp;  temp -> obj = wstawka;	}}bool erase(double wartosc){	node * prev;	node * curr;	bool jest = findelem(wartosc,&prev , &curr);	if(jest)	{	  node * temp;  temp = curr -> next;  curr -> next = NULL;  delete curr;  if (prev) 	 prev ->next = temp;  else 	 first = temp;	}	return jest;}void dump(){	node * pokazywacz = first;	while(pokazywacz)	{  cout << pokazywacz ->obj << endl;  pokazywacz = pokazywacz ->next;	}}}; /**** koniec definicji klasy lista jednokierunkowa ****/ int main(){	lista ld;		ld.insert(1.001);	ld.insert(2.002);	ld.insert(3.003);	ld.insert(4.004);	ld.insert(5.005);	lista ld2 = ld;	ld.erase(3.003);	ld.erase(2.002);	ld.erase(1.001);		ld.dump();		ld2.dump();		ld = ld2;	ld.dump();	return 0;}

to jest lista jednokieunkowa i takie same funkcje ma posiadac cykliczna;

[spicum]

Problem rozrosl sie do takiej rangi ze zaraz padne ze smiechu :lol:

 

Postaw sobie wartownika jako 1 element i zapomnijmy o sprawie.

 

Nie mam zielonego pojecia gdzie w tym problem widzisz.

Wiec zlituj sie nad innymi uzytkownikami i pomysl nad tym pomyslem 10 min - poimplementuj z 1h a nie czekaj az Ci ktos napisze.

 

Nie wiem jak inni sie czuja ale osobiescie juz mnie trafia od postow typu napiszcie mi to bo :

:arrow: pomyslec mi sie nie chce

:arrow: od wpisywania google.pl bola mnie palce

:arrow: bo mi sie nie chce*

*niepotrzebne skreslic.

 

Ludzie litosci

[birdman]

problem polegal na tym ze nie mialem czasu sie z tym bawic, a nie wychodzilo mi; jutro usiade i to napisze;

[ayem]

heh niestety programowanie to nie jest cos na co mozna "nie miec czasu" chcesz to robic to potrzebujesz duzo czasu

[birdman]

        	 #include <iostream>#include <string.h>using namespace std;class Tekst{	char *tekst;	int dl;public:	Tekst( char * );	~Tekst();	char * getTekst();	int getDl();	Tekst();	Tekst &operator=(const Tekst &wzor);};Tekst::Tekst(char* co)	{  tekst=new char[strlen(co)+1];  strcpy(tekst,co);  dl=strlen(co);	}Tekst::~Tekst()	{  if(tekst)  delete [] tekst;	}char* Tekst::getTekst()	{  if(tekst)   return tekst;  return "";	}int Tekst::getDl()	{  return dl;	}Tekst::Tekst()	{  tekst=NULL;  dl=0;	}Tekst& Tekst::operator=(const Tekst &wzor)	{  if(this->tekst) delete [] this->tekst;  if(wzor.dl) 	 {    this->tekst=new char[wzor.dl+1];    strcpy(this->tekst,wzor.tekst);    this->dl=wzor.dl; 	 }  else 	 {    this->tekst=NULL;    this->dl=0; 	 }  return *this;	}/*---------------------*/struct node  { 	 node* next; 	 Tekst obj; 	 node(): next(NULL), obj() {};  };/*----------------------*/class lista {node* first;public:	lista & operator= (const lista& wzor);	lista(const lista & wzor); 	 lista() : first(NULL) {}	~lista();	insert(char* wstawka);	bool findelem(char* do_znal , node ** prev , node ** curr);	bool erase(char* co);	dump();};lista::~lista(){	node *temp, *temp2;	temp=first;	temp2=first;			if(first)	{ 	 while (temp->next!=first)    {   	 temp=temp->next;   	 delete temp2;   	 temp2=temp;    }		delete temp2;	first=NULL;	}}lista::lista(const lista & wzor){		node *wskaz;	node *temp;	if(wzor.first)	{    first=new node;  first->obj=wzor.first->obj; //kopiowanie Tekstu	}	wskaz=wzor.first->next;		temp=first;		while(wskaz!=wzor.first)	{  temp->next=new node;  temp->next->obj=wskaz->obj; //kopiowanie tekstu  temp=temp->next;  wskaz=wskaz->next;	}	temp->next=first;}lista & lista::operator= (const lista& wzor){		node *temp, *temp2, *wskaz;	temp=first;	temp2=first;			if(first)	{ 	 while (temp->next!=first)    {   	 temp=temp->next;   	 delete temp2;   	 temp2=temp;    }		delete temp2;	first=NULL;	}	//stara lista jest skasowana wyzej	if(wzor.first)	{  first=new node;  first->obj=wzor.first->obj; //kopiowanie Tekstu  			wskaz=wzor.first->next;	temp=first;		while(wskaz!=wzor.first)	{  temp->next=new node;  temp->next->obj=wskaz->obj; //kopiowanie tekstu  temp=temp->next;  wskaz=wskaz->next;	}	temp->next=first;		}	return *this;	}lista::insert(char* wstawka){node* temp;	if (first)	{    temp=first;  while(temp->next!=first) 	 temp=temp->next;  temp->next=new node;  temp=temp->next;	}	else	{  first=new node;  temp=first;	}	temp->obj=Tekst(wstawka);	temp->next=first;	}bool lista::findelem(char* do_znal , node ** prev , node ** curr){	if(first)	{  (*prev) = first;  while((*prev)->next!=first) 	 (*prev)=(*prev)->next;  // dodane po to zeby poprzedni pokazywal na element wczesiejszy w przypadku gdy       	 // poszukiwany element znajduje sie na poczatku listy	  (*curr) = first;  while(1) 	 {      if( !strcmp( (*curr) -> obj.getTekst(),do_znal))   	 return true;    *prev = *curr; 	     if ((*curr)->next ==first)   	 return false;    *curr = (*curr) ->next; 	 }	}	return false;}bool lista::erase(char* co){	node * prev;	node * curr;	bool jest = this->findelem(co ,&prev ,&curr);	if(jest)	{	    if(first==first->next) first=NULL;  if (curr==first) first=first->next;  prev->next=curr->next;  delete curr; 	 	}	else  cout<<endl<<"Nie skasowano elementu: "<<co<<endl;	return jest;}lista::dump(){    		if(first)	{node *probka;	probka=first;	cout<<endl;	while(probka->next!=first)  {  cout<<probka->obj.getTekst()<<" ";  probka=probka->next;  }	cout<<probka->obj.getTekst()<<" ";		}}  int main(){	node  *pop=NULL;	node *ten=NULL;  		lista ld3;	lista ld;	ld3=ld;	ld.insert("raz");	ld.erase("raz");	ld.dump();	ld.insert("raz");	ld.insert("dwa");	ld.insert("trzy");	ld.insert("cztery");	ld.insert("piec");	ld.dump();if(ld.findelem("raz",&pop,&ten))  { 	 cout<<endl<<"Znaleziono element "<<endl; 	 cout<<"Element ktorego ostatnio poszukiwano to: "<<(ten)->obj.getTekst()<<endl; 	 cout<<"Element ktorego ostatnio poszukiwano to: "<<(pop)->next->obj.getTekst()<<endl;  }  ld.erase("raz");  ld.dump();	lista ld2 = ld;	cout<<"Po skopiowaniu lista ld2 wyglada : ";	ld2.dump();		if(ld.findelem("piec",&pop,&ten))  { 	 cout<<endl<<"Znaleziono element "<<endl; 	 cout<<"Element ktorego ostatnio poszukiwano to: "<<(ten)->obj.getTekst()<<endl; 	 cout<<"Element ktorego ostatnio poszukiwano to: "<<(pop)->next->obj.getTekst()<<endl;  }	ld.erase("cztery");	ld.erase("trzy");	ld.erase("trzy");	ld.erase("cztery");	ld.dump();	ld.erase("piec");ld.dump();		if(ld.findelem("piec",&pop,&ten))  { 	 cout<<"Znaleziono element "<<endl; 	 cout<<"Element ktorego ostatnio poszukiwano to: "<<(ten)->obj.getTekst()<<endl;  }	cout<<endl<<"LD2"<<endl;ld2.dump();	ld2.erase("dwa");ld2.dump();		if(ld2.findelem("cztery",&pop,&ten)) cout<<endl<<"Znaleziono element "<<endl;	cout<<"Element ktorego ostatnio poszukiwano to: "<<(ten)->obj.getTekst()<<endl;		cout<<"LD3"<<endl;	ld3=ld;ld3.dump();ld.dump();cout<<endl;	if(ld3.findelem("cztery",&pop,&ten)) cout<<"Znaleziono element "<<endl;	else cout<<"Nie znaleziono elementu";	ld3.erase("piec");	if(ld3.findelem("piec",&pop,&ten)) cout<<"Znaleziono element "<<endl;ld3.dump();cout<<"nLD4"<<endl;lista l4(ld3);l4.insert("taddaam!!!");l4.dump();	return 0;}