Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > С/С++
Перезагрузить страницу Как создать два и три дерева
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Sserg+ Sserg+ вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2010
По умолчанию Как создать два и три дерева - 11.12.2010, 02:30

Реализую структуру данных 2-3 дерево,возникла нерешаемая проблема с удалением элементов,программа не проходит тест на удаление элементов,
(не очищается память),требуется помощь в отладке.
Ответить с цитированием
  (#2 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 11.12.2010, 03:08

Ну так код что ли покажи...
Ответить с цитированием
  (#3 (permalink)) Старый
Sserg+ Sserg+ вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2010
По умолчанию 11.12.2010, 19:52

Вот код...
Код:
typedef struct Tree{
	char *key;
	long long unsigned int num;
	struct Tree *left;
	struct Tree *right;
	bool rh;//компонент rh обозначает горизонтальность правой ссылки, если равен true
	bool leaf;//true - если лист и false - если не лист
}Tree;

Tree *root=NULL;
Tree *tempel1=NULL;
Tree *tempel2=NULL;
Tree *tempel3=NULL;

int RETURN;

bool check=true;
bool check2=true;
bool splitting=false;//проверка на разбиение
bool exist=false;
bool del=false;
bool del_elem=false;
bool check3=true;

void GLOB_PEREM_OK();

//-----------------------------------------Delete elements of the tree------------------------------------------------------//
void T_Balans(Tree *T, char *c);

int Delete(char *c){
	RETURN=1;
	T_Balans(root, c);
	GLOB_PEREM_OK();
	return RETURN;
}

void T_Find(Tree *T){//находит самый левый элемент правого поддерева
	if(T->leaf==true){
		tempel1=T;
		check2=true;
		return;
	}
	else{
		if(check2==true){
			check2=false;
			T_Find(T->right);
			return;
		}
		else if(check2==false){
			T_Find(T->left);
			return;
		}
	}
}
void T_Balans2(Tree *T, char *c);
void T_Balans(Tree *T, char *c){
	
	if(strcoll(T->key, c) == 0){
		if(T->leaf==false){
			T_Find(T);
			free(T->key);
			T->key=tempel1->key;
			T->num=tempel1->num;
			T_Balans2(T, tempel1->key);
			free(tempel1);
			tempel1=NULL;
			if(check==true){
				RETURN=0;
				return;
			}
		check=false;
		RETURN=0;
		return;
		}
		if(T->leaf==true){
			if(T->rh==false){
				if(root==T) root=NULL;
				free(T->key);
				T->key=NULL;
				free(T);
				T=NULL;
				check=false;
				del_elem=true;
				RETURN=0;
				return;
			}
			if(T->rh==true){
			check2=false;
			tempel2=T->right;
			if(T==root){
				root=tempel2;
				tempel2=NULL;
				check2=true;
			}
			free(T->key);
			T->key=NULL;
			free(T);
			T=NULL;
			RETURN=0;
			return;
			}
		}
	}
	else if(T->rh==true && strcoll(T->right->key, c) == 0){
		if(T->leaf==false){
			T_Find(T->right);
			free(T->right->key);
			T->right->key=tempel1->key;
			T->right->num=tempel1->num;
			T_Balans2(T, tempel1->key);
			free(tempel1);
			tempel1=NULL;
			if(check==true){
				RETURN=0;
				return;
			}
		RETURN=0;
		return;
		}
		if(T->leaf==true){
			free(T->right->key);
			T->right->key=NULL;
			free(T->right);
			T->right=NULL;
			T->rh=false;
			RETURN=0;
			return;
		}
	}

	 if(T->rh==true && strcoll(T->right->key, c) < 0 && T->leaf==false){
        T_Balans(T->right->right, c);
		if(check2==false){
			 T->right->right=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		if(del_elem==true){
			if(tempel1==NULL) tempel1=T->right->right;
			T->right->right=NULL;
			del_elem=false;
		}
		if(check==false){
			if(T->right->left->rh==false){
				tempel2=T->right->left;
				T->right->left=tempel2->right;
				tempel2->right=T->right;
				T->right=tempel2;
				tempel2->rh=true;
				T->rh=false;
				if(tempel2->leaf==true) T->right->right->leaf=true;
				check=true;
				return;
			}
			if(T->right->left->rh==true){
				tempel2=T->right->left->right;
				T->right->left->rh=false;
				T->right->left->right=tempel2->left;
				tempel2->left=T->right->left;
				T->right->left=tempel2->right;
				tempel2->right=T->right;
				T->right=tempel2;
				if(tempel2->leaf==true){
					tempel2->leaf=false;
					T->right->right->leaf=true;
				}
				check=true;
				return;
			}
		}//if(check==false)
			if(T==root){
				check=true;
			}
		
		return;
	 }
	 
	if(strcoll(T->key, c) > 0 && T->leaf==false){
        T_Balans(T->left, c);
		if(check2==false){
			 T->left=tempel2;
			 tempel2=NULL;
			 check2=true;
		}
		if(del_elem==true){
			if(tempel1==NULL) tempel1=T->left;
			T->left=NULL;
			del_elem=false;
		}
		if(check==false){
			if(T->rh==false){
				if(T->right->rh==false){
					T->rh=true;
					if(T->right->leaf==true) T->leaf=true;
					if(T==root) check=true;
					return;
				}
				if(T->right->rh==true){
					tempel2=T->right;
					T->right=tempel2->left;
					tempel2->left=T;
					tempel2->rh=false;
					if(tempel2->leaf==true){
						T->leaf=true;
						tempel2->leaf=false;
					}
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}//if(T->right->rh==true)
			}//if(T->rh==false)
			if(T->rh==true){
				if(T->right->left->rh==true){
					tempel2=T->right->left;
					T->right->left=tempel2->right;
					tempel2->right=T->right;
					T->right=tempel2->left;
					tempel2->left=T;
					T->rh=false;
					if(tempel2->leaf==true){
						tempel2->leaf=false;
						T->leaf=true;
					}
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}
				if(T->right->right->rh==true){
					tempel2=T->right->left;
					T->right->left=tempel2->right;
					tempel2->right=T->right;
					tempel2->rh=true;
					T->right=tempel2->left;
					tempel2->left=T;
					tempel3=tempel2->right->right;
					tempel2->right->right=tempel3->left;
					tempel3->left=tempel2->right;
					tempel2->right=tempel3;
					tempel3->rh=false;
					tempel2->left->rh=false;
					if(tempel2->leaf==true){
						tempel2->leaf=false;
						tempel2->right->leaf=false;
						tempel2->right->left->leaf=true;
						tempel2->left->leaf=true;
					}
					tempel3=NULL;
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}
				if(T->right->left->rh==false && T->right->right->rh==false){
					tempel2=T->right->left;
					T->right->left=tempel2->right;
					tempel2->right=T->right;
					T->right=tempel2->left;
					tempel2->left=T;
					tempel2->right->rh=true;
					tempel2->rh=false;
					tempel2->left->rh=false;
					if(tempel2->leaf==true){
						tempel2->leaf=false;
						tempel2->left->leaf=true;
						tempel2->right->leaf=true;
					}
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}
			}//if(T->rh==true)
		}//if(check==false)
		if(T==root){
				check=true;
			}
		return;
	}

	 if(T->rh==false && strcoll(T->key, c) < 0 && T->leaf==false){
		 T_Balans(T->right, c);
		 if(check2==false){
			 T->right=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		 if(del_elem==true){
			 if(tempel1==NULL) tempel1=T->right;
			 T->right=NULL;
			 del_elem=false;
		 }
		 if(check==false){
			 if(T->left->rh==false){
				 tempel2=T->left;
				 T->left=tempel2->right;
				 tempel2->right=T;
				 tempel2->rh=true;
				 if(tempel2->leaf==true) T->leaf=true;
				 check2=false;
				 if(T==root){
					 root=tempel2;
					 tempel2=NULL;
					 check=true;
				 }
				 return;
			 }
			 if(T->left->rh==true){
				 tempel2=T->left->right;
				 T->left->rh=false;
				 T->left->right=tempel2->left;
				 tempel2->left=T->left;
				 T->left=tempel2->right;
				 tempel2->right=T;
				 if(tempel2->leaf==true){
					 tempel2->leaf=false;
					 tempel2->right->leaf=true;
				 }
				 check2=false;
				 check=true;
				 if(T==root){
					 root=tempel2;
					 tempel2=NULL;
					 check2=true;
				 }
				 return;
			 }
		 }//if(check==false)
		 if(T==root){
				check=true;
			}
		 return;
	 }

	 if(T->rh==true && strcoll(T->right->key, c) > 0 && T->leaf==false){
		 T_Balans(T->right->left, c);
		 if(check2==false){
			 T->right->left=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		 if(del_elem==true){
			 if(tempel1==NULL) tempel1=T->right->left;
			 T->right->left=NULL;
			 del_elem=false;
		 }
		 if(check==false){
			 if(T->right->right->rh==false){
				 T->rh=false;
				 T->right->rh=true;
				 if(T->right->right->leaf==true) T->right->leaf=true;
				 check=true;
				 return;
			 }
			 if(T->right->right->rh==true){
				 tempel2=T->right->right;
				 T->right->right=tempel2->left;
				 tempel2->left=T->right;
				 T->right=tempel2;
				 tempel2->rh=false;
				 if(tempel2->leaf==true){
					 tempel2->leaf=false;
					 T->right->left->leaf=true;
				 }
				 check=true;
				 tempel2=NULL;
				 return;
			 }
		 }//if(check==false)
		 if(T==root){
				check=true;
			}
		 return;
	 }

}
Ответить с цитированием
  (#4 (permalink)) Старый
Sserg+ Sserg+ вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2010
По умолчанию 11.12.2010, 19:53

Вот ещё не большой кусочек кода...

Код:
void T_Balans2(Tree *T, char *c){
	
	if(strcoll(T->key, c) == 0){
		if(check3==false){
		if(T->rh==false){
		check=false;
		del_elem=true;
		return;
		}
		else if(T->rh==true){
			if(tempel1==NULL) tempel1=T;
			tempel2=T->right;
			check2=false;
			check=true;
			del_elem=false;
			return;
		}
		}
		else if(check3==true){
			check3=false;
			if(T->rh==false){
		T_Balans2(T->right, c);
		 if(check2==false){
			 T->right=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		 if(del_elem==true){
			 if(tempel1==NULL) tempel1=T->right;
			 T->right=NULL;
			 del_elem=false;
		 }
		 if(check==false){
			 if(T->left->rh==false){
				 tempel2=T->left;
				 T->left=tempel2->right;
				 tempel2->right=T;
				 tempel2->rh=true;
				 if(tempel2->leaf==true) T->leaf=true;
				 check2=false;
				 if(T==root){
					 root=tempel2;
					 tempel2=NULL;
					 check=true;
				 }
				 return;
			 }
			 if(T->left->rh==true){
				 tempel2=T->left->right;
				 T->left->rh=false;
				 T->left->right=tempel2->left;
				 tempel2->left=T->left;
				 T->left=tempel2->right;
				 tempel2->right=T;
				 if(tempel2->leaf==true){
					 tempel2->leaf=false;
					 tempel2->right->leaf=true;
				 }
				 check2=false;
				 check=true;
				 if(T==root){
					 root=tempel2;
					 tempel2=NULL;
					 check2=true;
				 }
				 return;
			 }
		 }//if(check==false)
		 if(T==root){
				check=true;
			}
		 return;
		 }//if(T->rh==false)
			if(T->rh==true){
				T_Balans2(T->right->left, c);
		 if(check2==false){
			 T->right->left=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		 if(del_elem==true){
			 if(tempel1==NULL) tempel1=T->right->left;
			 T->right->left=NULL;
			 del_elem=false;
		 }
		 if(check==false){
			 if(T->right->right->rh==false){
				 T->rh=false;
				 T->right->rh=true;
				 if(T->right->right->leaf==true) T->right->leaf=true;
				 check=true;
				 return;
			 }
			 if(T->right->right->rh==true){
				 tempel2=T->right->right;
				 T->right->right=tempel2->left;
				 tempel2->left=T->right;
				 T->right=tempel2;
				 tempel2->rh=false;
				 if(tempel2->leaf==true){
					 tempel2->leaf=false;
					 T->right->left->leaf=true;
				 }
				 check=true;
				 tempel2=NULL;
				 return;
			 }
		 }//if(check==false)
		 if(T==root){
				check=true;
			}
		 return;
			}//if(T->rh==true)
		}//else if(check3==true)
	}//if(strcoll(T->key, c) == 0)
	else if(T->rh==true && strcoll(T->right->key, c) == 0){
			check3=false;
		T_Balans2(T->right->right, c);
		if(check2==false){
			 T->right->right=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		if(del_elem==true){
			if(tempel1==NULL) tempel1=T->right->right;
			T->right->right=NULL;
			del_elem=false;
		}
		if(check==false){
			if(T->right->left->rh==false){
				tempel2=T->right->left;
				T->right->left=tempel2->right;
				tempel2->right=T->right;
				T->right=tempel2;
				tempel2->rh=true;
				T->rh=false;
				if(tempel2->leaf==true) T->right->right->leaf=true;
				check=true;
				return;
			}
			if(T->right->left->rh==true){
				tempel2=T->right->left->right;
				T->right->left->rh=false;
				T->right->left->right=tempel2->left;
				tempel2->left=T->right->left;
				T->right->left=tempel2->right;
				tempel2->right=T->right;
				T->right=tempel2;
				if(tempel2->leaf==true){
					tempel2->leaf=false;
					T->right->right->leaf=true;
				}
				check=true;
				return;
			}
		}//if(check==false)
			if(T==root){
				check=true;
			}
		
		return;
	}//else if(T->rh==true && strcoll(T->right->key, c) == 0)

	 if(T->rh==true && strcoll(T->right->key, c) < 0 && T->leaf==false){
        T_Balans2(T->right->right, c);
		if(check2==false){
			 T->right->right=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		if(del_elem==true){
			if(tempel1==NULL) tempel1=T->right->right;
			T->right->right=NULL;
			del_elem=false;
		}
		if(check==false){
			if(T->right->left->rh==false){
				tempel2=T->right->left;
				T->right->left=tempel2->right;
				tempel2->right=T->right;
				T->right=tempel2;
				tempel2->rh=true;
				T->rh=false;
				if(tempel2->leaf==true) T->right->right->leaf=true;
				check=true;
				return;
			}
			if(T->right->left->rh==true){
				tempel2=T->right->left->right;
				T->right->left->rh=false;
				T->right->left->right=tempel2->left;
				tempel2->left=T->right->left;
				T->right->left=tempel2->right;
				tempel2->right=T->right;
				T->right=tempel2;
				if(tempel2->leaf==true){
					tempel2->leaf=false;
					T->right->right->leaf=true;
				}
				check=true;
				return;
			}
		}//if(check==false)
			if(T==root){
				check=true;
			}
		
		return;
	 }
	 
	if(strcoll(T->key, c) > 0 && T->leaf==false){
        T_Balans2(T->left, c);
		if(check2==false){
			 T->left=tempel2;
			 tempel2=NULL;
			 check2=true;
		}
		if(del_elem==true){
			if(tempel1==NULL) tempel1=T->left;
			T->left=NULL;
			del_elem=false;
		}
		if(check==false){
			if(T->rh==false){
				if(T->right->rh==false){
					T->rh=true;
					if(T->right->leaf==true) T->leaf=true;
					if(T==root) check=true;
					return;
				}
				if(T->right->rh==true){
					tempel2=T->right;
					T->right=tempel2->left;
					tempel2->left=T;
					tempel2->rh=false;
					if(tempel2->leaf==true){
						T->leaf=true;
						tempel2->leaf=false;
					}
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}//if(T->right->rh==true)
			}//if(T->rh==false)
			if(T->rh==true){
				if(T->right->left->rh==true){
					tempel2=T->right->left;
					T->right->left=tempel2->right;
					tempel2->right=T->right;
					T->right=tempel2->left;
					tempel2->left=T;
					T->rh=false;
					if(tempel2->leaf==true){
						tempel2->leaf=false;
						T->leaf=true;
					}
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}
				if(T->right->right->rh==true){
					tempel2=T->right->left;
					T->right->left=tempel2->right;
					tempel2->right=T->right;
					tempel2->rh=true;
					T->right=tempel2->left;
					tempel2->left=T;
					tempel3=tempel2->right->right;
					tempel2->right->right=tempel3->left;
					tempel3->left=tempel2->right;
					tempel2->right=tempel3;
					tempel3->rh=false;
					tempel2->left->rh=false;
					if(tempel2->leaf==true){
						tempel2->leaf=false;
						tempel2->right->leaf=false;
						tempel2->right->left->leaf=true;
						tempel2->left->leaf=true;
					}
					tempel3=NULL;
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}
				if(T->right->left->rh==false && T->right->right->rh==false){
					tempel2=T->right->left;
					T->right->left=tempel2->right;
					tempel2->right=T->right;
					T->right=tempel2->left;
					tempel2->left=T;
					tempel2->right->rh=true;
					tempel2->rh=false;
					tempel2->left->rh=false;
					if(tempel2->leaf==true){
						tempel2->leaf=false;
						tempel2->left->leaf=true;
						tempel2->right->leaf=true;
					}
					check2=false;
					check=true;
					if(T==root){
						root=tempel2;
						tempel2=NULL;
						check2=true;
					}
					return;
				}
			}//if(T->rh==true)
		}//if(check==false)
		if(T==root){
				check=true;
			}
		return;
	}

	 if(T->rh==false && strcoll(T->key, c) < 0 && T->leaf==false){
		 T_Balans2(T->right, c);
		 if(check2==false){
			 T->right=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		 if(del_elem==true){
			 if(tempel1==NULL) tempel1=T->right;
			 T->right=NULL;
			 del_elem=false;
		 }
		 if(check==false){
			 if(T->left->rh==false){
				 tempel2=T->left;
				 T->left=tempel2->right;
				 tempel2->right=T;
				 tempel2->rh=true;
				 if(tempel2->leaf==true) T->leaf=true;
				 check2=false;
				 if(T==root){
					 root=tempel2;
					 tempel2=NULL;
					 check=true;
				 }
				 return;
			 }
			 if(T->left->rh==true){
				 tempel2=T->left->right;
				 T->left->rh=false;
				 T->left->right=tempel2->left;
				 tempel2->left=T->left;
				 T->left=tempel2->right;
				 tempel2->right=T;
				 if(tempel2->leaf==true){
					 tempel2->leaf=false;
					 tempel2->right->leaf=true;
				 }
				 check2=false;
				 check=true;
				 if(T==root){
					 root=tempel2;
					 tempel2=NULL;
					 check2=true;
				 }
				 return;
			 }
		 }//if(check==false)
		 if(T==root){
				check=true;
			}
		 return;
	 }

	 if(T->rh==true && strcoll(T->right->key, c) > 0 && T->leaf==false){
		 T_Balans2(T->right->left, c);
		 if(check2==false){
			 T->right->left=tempel2;
			 tempel2=NULL;
			 check2=true;
		 }
		 if(del_elem==true){
			 if(tempel1==NULL) tempel1=T->right->left;
			 T->right->left=NULL;
			 del_elem=false;
		 }
		 if(check==false){
			 if(T->right->right->rh==false){
				 T->rh=false;
				 T->right->rh=true;
				 if(T->right->right->leaf==true) T->right->leaf=true;
				 check=true;
				 return;
			 }
			 if(T->right->right->rh==true){
				 tempel2=T->right->right;
				 T->right->right=tempel2->left;
				 tempel2->left=T->right;
				 T->right=tempel2;
				 tempel2->rh=false;
				 if(tempel2->leaf==true){
					 tempel2->leaf=false;
					 T->right->left->leaf=true;
				 }
				 check=true;
				 tempel2=NULL;
				 return;
			 }
		 }//if(check==false)
		 if(T==root){
				check=true;
			}
		 return;
	 }

}
Ответить с цитированием
  (#5 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 11.12.2010, 21:39

Ну это хорошо.. В дебаге запускал? При падении, если по стеку прогуляться, куда показывает отладчик? На какую строку кода?
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Sserg+ Sserg+ вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.12.2010
По умолчанию 11.12.2010, 21:54

В дебагере стек не смотрел, но я проганял прогу через dmalloc. Он ругается, вроде идёт утечка памяти, но место в коде он не может показать.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Визуализация дерева в Prolog 5.2 Moonbiter Prolog 2 17.04.2018 20:52
Вывод дерева cska_fun Prolog 21 31.05.2014 15:33
Определить функцию для вывода бинарного дерева на экран в виде дерева imported_Vinni Lisp 22 20.06.2011 22:34
Сортировка АВЛ-дерева Khelleos Visual C++ 3 09.05.2011 14:52
обход дерева mike2007 Prolog 4 30.05.2010 05:30
Класс бинарного дерева yasya Алгоритмы 2 29.04.2009 22:53
удаление из AVL дерева lexamac Prolog 0 20.05.2008 22:50
Копирование дерева Alan2006 Prolog 3 08.05.2007 20:33
Удаление элементов тз дерева UIN С/С++ 3 03.01.2006 11:09
Симметричность дерева ... imported_Zhenka Prolog 2 16.12.2005 09:46
Вывод дерева Tough Prolog 6 06.11.2005 18:13
Построение дерева 2 S.Yu.Gubanov Алгоритмы 3 09.12.2002 15:43



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов