Здравейте! Мина малко време от последния път, когато Ви питах нещо

Наскоро във форума на data.bg видах тема, в която се искаше помощ за курсова работа. Задачата ми се стори интересна и реших да се опитам да я направя за тренировка. http://forums.data.bg/index.php?showtopic=2126098

Пише всичко да се запазва в двоичен файл, но понеже още не съм наясно с работата с файлове, реших да прескоча това. Проблемът ми е друг. Иска се да има опция за изтриване на посочена връзка от списъка.

Ето какво правя аз:

1. Питам потребителя за номера на връзката. След като я посочи, знам че връзката е напремер temp2.

2. После го питам дали иска да промени данните(1) или да изтрие връзката(2).

3. Ако посочи, че иска да изтрие връзката правя това:

List *temp3;temp3 = temp2;temp2 = temp2->next;delete temp3;

Но не се получава. Не мога да разбера къде бъркам. Целият код е може би малко объркан. Надявам се да схванете идеята ми. Опитвам се да го направя във функцията modify().

        #include<iostream>    using namespace std;    class List	  {		 public:		 int code;		 char address[100];		 double plosht;		 int rooms;		 double naem;		 List *next;  		  void add_node();		 void print_all();	  };    List *start_ptr = NULL;   	 void print_this(List *temp1);   	 void List::add_node()	  {	    List *temp1, *temp2;	    temp1 = new List;	    bool yes = false;	    while(!yes)	    {		    yes = true;		    cout << "Code   : ";		    cin >> temp1->code;  			 temp2 = start_ptr;		    while(temp2 != NULL)			  {			    if(temp1->code == temp2->code) yes = false;			    temp2 = temp2->next; 			   }	    }	    char p[100];	    cin.getline(p, 100);	    cout << "Address: ";	    cin.getline(temp1->address, 100);	    cout << "Plosht : ";	    cin >> temp1->plosht;	    cout << "Stai   : ";	    cin >> temp1->rooms;	    cout << "Naem   : ";	    cin >> temp1->naem; 		 cout << endl;	 		 temp1->next = NULL;	    if(start_ptr == NULL)		  start_ptr = temp1;	    else		  {		    temp2 = start_ptr;		    while(temp2->next != NULL)			  temp2 = temp2->next;		    temp2->next = temp1;		 		   }				  	   }	 	 void modify()	  {	    List *temp1, *temp2;	    bool find = false;	    int kod;	    while(!find)		  {		    cout << "Enter code: ";		    cin >> kod;		    temp1 = start_ptr;		    if(start_ptr == NULL) cout << "Empty List!" << endl;		    else			  {			    while(temp1 != NULL)				  {				    if(kod == temp1->code)				    {					  print_this(temp1);					  find = true;					  temp2 = temp1;				    }				    temp1 = temp1->next;	    				   } 				  if(!find)				   {					 cout << "Can't find such load!" << endl;				   }	   			   }		  }	    cout << endl;	    char quest;	    cout << "=====================================" << endl;	    cout << "| Press 1 and Enter to change data. |"<< endl;	    cout << "| Press 2 and Enter to delete node. |" << endl;	    cout << "=====================================" << endl;	    cin >> quest;	    if(quest == '1')		  {			 cout << "Do you want to use the old code? (Y/N): ";			 cin >> quest;			 if(quest == 'Y' || quest == 'y')			   {				 cout << "Code   : ";				 cout << temp2->code << endl;				 char p[100];				 cin.getline(p, 100);				 cout << "Address: ";				 cin.getline(temp2->address, 100);				 cout << "Plosht : ";				 cin >> temp2->plosht;				 cout << "Stai   : ";				 cin >> temp2->rooms;				 cout << "Naem   : ";				 cin >> temp2->naem; 				  cout << endl;	  			    }			 else			   {				 List *temp3;				 temp3 = start_ptr;				 bool yes = false;				 while(!yes)				   {					 yes = true;					 cout << "Code   : ";					 cin >> kod;					 while(temp3 != NULL)					   {						 if(kod == temp3->code)  yes = false;						 temp3 = temp3->next;	  					    }	    				    }   				   temp2->code = kod;				  char p[100];				  cin.getline(p, 100);				  cout << "Address: ";				  cin.getline(temp2->address, 100);				  cout << "Plosht : ";				  cin >> temp2->plosht;				  cout << "Stai   : ";				  cin >> temp2->rooms;				  cout << "Naem   : ";				  cin >> temp2->naem; 				   cout << endl;	   			    }		  }		  if(quest == '2')		    {			  List *temp3;			  temp3 = temp2;			  delete temp2;			  temp2 = temp3->next;		    }			   	   }	 	 void print_this(List *temp1)	  {	    cout << "Code   : ";	    cout << temp1->code << endl;	    cout << "Address: ";	    cout << temp1->address << endl;	    cout << "Plosht : ";	    cout << temp1->plosht << endl;	    cout << "Stai   : ";	    cout << temp1->rooms << endl;	    cout << "Naem   : ";	    cout << temp1->naem << endl; 		 cout << endl;					    	   }   	 void List::print_all()	  {	    List *temp1;	    temp1 = start_ptr;	    if(start_ptr == NULL)		  cout << "Empty List!" << endl;	    else		  {		    while(temp1 != NULL)			  {			    cout << "Code   : ";			    cout << temp1->code << endl;			    cout << "Address: ";			    cout << temp1->address << endl;			    cout << "Plosht : ";			    cout << temp1->plosht << endl;			    cout << "Stai   : ";			    cout << temp1->rooms << endl;			    cout << "Naem   : ";			    cout << temp1->naem << endl; 				 cout << endl; 				 temp1 = temp1->next;		 			   }    		   }			    	   }    int main()	  {	    int n;	    List A;	    cin >> n;	    for(int i = 0; i <= n-1; i++)		  A.add_node();	    cout << "--------------------------------" << endl;	    modify();	    A.print_all();	    system("pause");	    return 0;	   	   }

Ако имате съвети за подобряване на кода няма да се сърдя, ако ги споделите

 

П.П. Оправих се Самият принцип, който съм използвал е тотално грешен. Ето какво направих сега:

List *temp3 = start_ptr;              while(temp3->next != NULL)                {                  if(temp3->next->code == temp2->code)                    {                      temp3->next = temp2->next;                                      }                            temp3 = temp3->next;                  delete temp2;                }

Редактирано 1 май 201313 г. от snaksa (преглед на промените)

Ако имате съвети за подобряване на кода няма да се сърдя, ако ги споделите

По кода има доста неща които могат да се оправят. Можеш да почнеш от там да направиш данните private. Още по-добре, да си ги отделиш в отделен клас от контейнера. Тогава даже може да използваш някой стандартен контейнер. Всеки от методите също има къде да се пооправи.

П.П. Оправих се Самият принцип, който съм използвал е тотално грешен. Ето какво направих сега:

List *temp3 = start_ptr;              while(temp3->next != NULL)                {                  if(temp3->next->code == temp2->code)                    {                      temp3->next = temp2->next;                                      }                            temp3 = temp3->next;                  delete temp2;                }

Тука май си сбъркал нещо. Както си го написал този цикъл е издъно погрешен. Указателят temp2 не се променя никъде в тялото на цикъла, но се трие безусловно в края му. Това означава, че ако има повече от едно повторение, ще опиташ да изтриеш temp2 няколко пъти, което е невалидна операция, и ще изгърми, без да броим че на второто повторение ще го използваш след като е вече изтрит.

Ммм да. Много сте прав. Къде съм гледал... Така по-добре ли би било?

List *temp3 = start_ptr;              while(temp3 != NULL)                {                  if(temp3->next->code == temp2->code)                    {                      temp3->next = temp2->next;                                     delete temp2;                    }                            temp3 = temp3->next;                }

А какво имате предвид под стандартен контейнер? Просто обикновенна структура ли?

П.С. И ако може с две думи да ми кажете кое би било добре да се пооправи в методите ще е супер

Редактирано 3 май 201313 г. от snaksa (преглед на промените)

Ммм да. Много сте прав. Къде съм гледал... Така по-добре ли би било?

List *temp3 = start_ptr;              while(temp3 != NULL)                {                  if(temp3->next->code == temp2->code)                    {                      temp3->next = temp2->next;                                     delete temp2;                    }                            temp3 = temp3->next;                }

А какво имате предвид под стандартен контейнер? Просто обикновенна структура ли?

П.С. И ако може с две думи да ми кажете кое би било добре да се пооправи в методите ще е супер

 

 

 

Здравейте, 

 

За съжаление и вторият вариант на алгоритъма Ви за премахване на елемент не е твърде добър - отново ми се струва, че указателят temp2 не се мени, а и съществуват още няколко гранични случая

 

За съжаление със C/C++ открай време не се занимавам много, но алгоритмично би трябвало метода за премахване на елемент да е нещо подобно:

void removeElementByValue(List* &start_ptr, int codeToRemove) {	//Case 0: Списъкът е празен - нищо не правим	if (start_ptr == NULL) {		return;	}	List *currentElem = start_ptr;	//Case 1: Трябва да премахнем първият елемент:	if (currentElem != null && currentElem->code == codeToRemove){		start_ptr = currentElem->next;		delete currentElem;                return;	}	//Case2: Премахваме не-първи елемент от списъка. 	while (currentElem->next != NULL) { 		if (currentElem->next->code == codeToRemove) {			List *linkToDelete = currentElem->next			currentElem->next = currentElem->next->next;			delete linkToDelete;			return;		}		currentElem = currentElem->next;	}}

Кода не успях да го тествам дали работи - писах го с оглед на самият алгоритъм. Също така, това не е най-оптимизираният му вариант - съществуват доста по - добри реализации. Този вариант е по-скоро с покриването на различни сценарии, които бихме имали за свързаният списък.

 

P.S. Параметъра "codeToRemove" в метода може успешно да бъде заместен с прочетената стойност за  "kod" от конзолата, както е направено в метода modify();

 

Поздрави !

Редактирано 3 май 201313 г. от dpk (преглед на промените)

...

Забележката ти относно новия код на snaksa е вярна.

За съжаление обаче, метода за триене на елемент не е. Първо, при триене на първият елемент, непременно трябва да се модифицира "оригиналният" указател към него, иначе всяка следваща операция със списъка ще започне с достъпване на невалидна стойност. Второ, точно същото ще се случи и във вашия код - един ред след изтриването на currentElem във втория if, вие достъпвате currentElem->next като условие на while. И последно, както казахте алгоритъмът - точно както всички преди това, не е оптимален - непременно ще обиколи целия списък, което не е необходимо, ако елементът, който търсим е преди края - по един return в края на всяко триене би помогнал много.

Забележката ти относно новия код на snaksa е вярна.

За съжаление обаче, метода за триене на елемент не е. Първо, при триене на първият елемент, непременно трябва да се модифицира "оригиналният" указател към него, иначе всяка следваща операция със списъка ще започне с достъпване на невалидна стойност. Второ, точно същото ще се случи и във вашия код - един ред след изтриването на currentElem във втория if, вие достъпвате currentElem->next като условие на while. И последно, както казахте алгоритъмът - точно както всички преди това, не е оптимален - непременно ще обиколи целия списък, което не е необходимо, ако елементът, който търсим е преди края - по един return в края на всяко триене би помогнал много.

Малко не успявам да схвана как temp2 трябва да се измени. Може ли да ми подскажете малко?

@flare - Напълно съм съгласен със забележките Ви. Наистина кода не беше оптимизиран и оптимален. Мисля, че успях да поправя и проблема относно изтриването на първият елемент. Поставих return клаузи на подходящите места. В този случай, метода ще изтрива първият срещнат елемент от списъка с подаден от потребителя kod. Ако е валиден случаят за наличие на повече от 1 елементи с една и съща стойност на полето code, то метода трябва да се модифицира малко. Мисля, че номера с указател към адрес спестяваше няколко "звездички" в тялото на метода 

 

@snaksa - Визирайки кода, който публикувах по-рано, то променливата temp2 е аналог на променливата linkToDelete - т.е. временен указател към елемента, който ще бъде изтрит.

Малко като странична информация, тук има малко размишления върху проблема, като авторите дават 2 подхода - итеративен и рекурсивен. 

 

След промяната, която отразих след коментарите на flare (надявам се правилни ), то извикването на метода ще стане директно:

 

removeElementByValue(start_ptr, kod);

 

където start_ptr е от тип " List* " както колегата snacks го е дефинирал , а kod е от тип "int" и е стойността, въведена от потребителя.

 

Значи със всички проверки кода така ли трябва да изглежда?:

    void delete_node(List *start_ptr, int kod)      {        List *temp2;        if(start_ptr == NULL)          {            cout << "Empty List!" << endl;            return;          }                         else                {                  List *temp3 = start_ptr;                  if(temp3->code == kod)                    {                      start_ptr = temp3->next;                      delete temp3;                         return;                              }                    else                     {                       while(temp3->next != NULL)                          {                           if(temp3->next->code == kod)                             {                               temp2 = temp3->next;                               temp3->next = temp3->next->next;                               delete temp2;                               return;                                         }                                    temp3 = temp3->next;                           }                         }                      }                          }

 

Значи със всички проверки кода така ли трябва да изглежда?:

    void delete_node(List* &start_ptr, int kod)      {        List *temp2;        if(start_ptr == NULL)          {            cout << "Empty List!" << endl;            return;          }                         else                {                  List *temp3 = start_ptr;                  if(temp3->code == kod)                    {                      start_ptr = temp3->next;                      delete temp3;                         return;                              }                    else                     {                       while(temp3->next != NULL)                          {                           if(temp3->next->code == kod)                             {                               temp2 = temp3->next;                               temp3->next = temp3->next->next;                               delete temp2;                               return;                                         }                                    temp3 = temp3->next;                           }                         }                      }                          }

 

Мисля, че да. Само една корекция съм добавил във прототипа на метода, за да можем да си гарантираме, че работим с адреса на началния елемент. 

Ще е добре и колегата flair да хвърли едно око, за всеки случай, но мисля, че това е метода, който ще Ви свърши работа.

 

Поздрави !

Редактирано 4 май 201313 г. от dpk (преглед на промените)

Мисля, че да. Само една корекция съм добавил във прототипа на метода, за да можем да си гарантираме, че работим с адреса на началния елемент.

Да наистина корекцията Ви се отрази доста положително. Чак сега забелязах, че без нея имам проблеми с изтриването на първата връзка в списъка.

Мерси много