Estrutura de Dados Heap

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

fila.cpp
#include "fila.h"
//jaimerson_correia@hotmail.com
struct lista{
	void* info;	
	lista *anterior, *proximo;
};
struct fila{
	Lista *inicio, *fim;
	int tamanho;
};
/************funçoes da fila*************/
/*função auxiliar insere*/
static Lista* lista_insere(Lista* fim, void* info){
	Lista* p = (Lista*)malloc(sizeof(Lista));
	p->info = info;
	p->proximo = NULL;
	p->anterior = fim;
	if(fim !=NULL) fim->proximo = p;
	return p;
}
/*funcão auxiliar remocão*/
static Lista* lista_retira(Lista* inicio){
	Lista* p = inicio->proximo;
	if(p) p->anterior = NULL;
	
	free(inicio);
	return p;
}
Fila* fila_cria(){
	Fila* fi = (Fila*)malloc(sizeof(Fila)) ;
	if(fi){
		fi->fim = fi->inicio = NULL;
		fi->tamanho = 0;		
	}
	return fi;
}
void fila_insere(Fila* fi, void* info){
	fi->fim = lista_insere(fi->fim,info);
	if(!fi->inicio){
		fi->inicio = fi->fim;
	}
	fi->tamanho++;
}
void* fila_retira(Fila* fi){
	void* info;
	if(fila_vazia(fi))return NULL;
	fi->tamanho--;//tamanho da fila
	info = fi->inicio->info;
	fi->inicio = lista_retira(fi->inicio);
	if(!fi->inicio){
		fi->fim = NULL;
	}
	return info;
}
int fila_vazia(Fila* fi){	
	return !fi->inicio;
}
void fila_destroi(Fila* fi){
	Lista* aux = fi->inicio;	
	while(aux){
		Lista* li = aux->proximo;
		free(aux);
		aux = li;
	}
	free(aux);
}
void fila_imprime(Fila* fi){
	for(Lista* aux = fi->inicio; aux; aux=aux->proximo){
		printf("%X ",aux->info);
	}
}
void fila_esvazia(Fila* fi){
	while(fi->inicio) fila_retira(fi);
}
static Lista* lista_retira_fim(Lista* fim){
	Lista* p = fim->anterior;
	if(p) p->proximo = NULL;
	free(fim);
	return p;
}
void* fila_retira_fim(Fila* f){
	void* info;
	if(fila_vazia(f)){
		printf("\n\tFila vazia");
		return NULL;
	}
	f->tamanho--;
	info = f->fim->info;
	f->fim = lista_retira_fim(f->fim);
	if(!f->fim) f->inicio = NULL;
	return info;
}
void* get_anterior(Fila* fi){
	printf("\n\tget_anterior()");	
	return fi->inicio->proximo->info;	
}
Lista* get_inicio(Fila* fi){
	return fi->inicio;	
}
Lista* get_proximo(Lista* li){
	return li->proximo;
}
void* get_info(Lista* li){
	return li->info;
}
int fila_tamanho(Fila* fi){
	return fi->tamanho;
}
fila.h
#include <stdio.h>
#include <stdlib.h>
typedef struct fila Fila;
typedef struct lista Lista;
Fila* fila_cria();
void fila_insere(Fila* fi, void* info);
void* fila_retira(Fila* fi);
int fila_vazia(Fila* fi);
void fila_destroi(Fila* fi);
void fila_imprime(Fila* fi);
void fila_esvazia(Fila* fi);
void* fila_retira_fim(Fila* f);
int fila_tamanho(Fila* fi);
Lista* get_inicio(Fila* fi);
Lista* get_proximo(Lista* li);
void* get_info(Lista* li);
void* get_anterior(Fila* fi);
main.cpp
#include <iostream>
#include"fila.h"
#include"projeto_heap.h"
#include"menus.h"
int main(int argc, char** argv) {
	Heap* raiz = heap_cria();
	for(;;){
		switch(menu()){
			case 1:{				
				heap_insere_largura(raiz,menu_form());
				break;
			}
			case 2:{
				heap_remove(raiz)?
					printf("\n\tRemovido com sucesso!"):
					printf("\n\tArvore vazia!");
				break;
			}
			case 3:{
				printf("\n\tPre-ordem: ");
				heap_pre_ordem(raiz);
				printf("\n\n\tPor Nivel: ");
				heap_imprime(raiz);
				break;
			}
			case 4:{
				int x = menu_sair();
				if(x){
					heap_distroi(raiz);
					campeao();
					system("pause");
					exit(1);
				}				
				break;
			}
			case 5:{
				printf("\n\tVoce acessou o campo de teste");
				Fila* fi = fila_cria();
				int a = 1;
				fila_insere(fi,&a);
				
				int b = 2;
				fila_insere(fi,&b);
				
				int c = 3;
				fila_insere(fi,&c);
				fila_retira(fi);
				fila_retira_fim(fi);
				printf("\n\tTamanho -> %i",fila_tamanho(fi));
				vencedor();
				break;
			}
			default:
				printf("\n\tOpcao Invalida!");				
				break;			
		}
		printf("\n\n\t");
		system("pause");
	}
	return 0;
}
menus.cpp
#include"menus.h"
int menu(){
	int op;
	system("cls");
	printf("\n\t******MENU******");
	printf("\n\t[1] - Inserir");
	printf("\n\t[2] - Excluir");
	printf("\n\t[3] - Mostrar");
	printf("\n\t[4] - Sair");
	printf("\n\tDigite a opcao: ");
	scanf("%i",&op);	
	return op;
}
int menu_form(){
	int valor;
	printf("\n\tDigite um valor: ");
	scanf("%i",&valor);
	return valor;
}
int menu_sair(){
	int sim,verdade = 0;
	do{
		printf("\n\tVoce deseja realmente sair? [1]Sim ou [2]Nao: ");
		scanf("%i",&sim);
		verdade = (sim >= 1 && sim <= 2)?1:0;
		if(!verdade)printf("\n\tOpcao Invalida!");
	}while(!verdade);
	return sim == 1?1:0;
	
}
void campeao(){
 
printf("\n ");
printf("\n rM@B@8XEv uEB@B@B@i ");
printf("\n O@@q7uJ:MB. O@Mr5i7@B@E ");
printf("\n MBG :M@ .,:r7LJ1USkqq8OO8BOJv7J, UB11r ,@@r ");
printf("\n :@@ rX@B@. .1EOO8E0XXSk11Uuu2UkkOBEUPB@M@B@B7 LB@B@L iB@ ");
printf("\n i@u rM@. B0v7:. . ..,:::7LYrrLZ @ O@qGB5 LB@ @@ ");
printf("\n ,BU X8: Y, .:...,,::::i7S7L7uJSG LB @Z7rZ, F@S B@ ");
printf("\n @B 7M@G..7 .:,.,.,,:iLUN7:r:NPqk OS LBuL2rvM@BO. .@E ");
printf("\n :@, 778B:..,,.,.::ii:,iuYiq5GL @: O@iG@@BF, MB. ");
printf("\n k@ ,Jri :...,.:rXUk7rr:5k8r B @XYBY: :B2 ");
printf("\n B8 u......,.,iL0irr:q5E: .B 7BJB@ BM ");
printf("\n B1 j:......,.,:j:Lr:P55XZ@@5XBv@J B@ ");
printf("\n B2 ri.,.....,,:LiL7:SFG. iF rBuB, B@ ");
printf("\n Bq ii......,.,:YiY;:5SO ;k u@U@ BM ");
printf("\n EB ii.....,.,,:vi7i.X2Ni.LS 7BSB r@u ");
printf("\n v@: ii,.....,,::iU02u1YXLJMB1POP@ OB: ");
printf("\n .@E :i,. ....::::i;777LM 7L SOMB :@B ");
printf("\n 2@7 ::.....,,::ii;i771M 87 8O@@ B@i ");
printf("\n .OM .:......::iirr77JSN M @P@v.BX ");
printf("\n iB:,.....,::iii777L1U,:P 7MSBkX ");
printf("\n E.....,,::iirrv7JLU0MZqX5GMj ");
printf("\n 1B,vr,,:ii;r7LuJ221uUjuuk@@J@N ");
printf("\n Ui 7B@FL7vL5255XkqF2j50@B@ Yr ");
printf("\n u@B@B@BL;j15Z@O@B@Mi ");
printf("\n rj ::ri .@@. ");
printf("\n ru7rivu1LGB1 ");
printf("\n rBXriuX@@ ");
printf("\n .Mv7B@Z ");
printf("\n 7OB ");
printf("\n . i@L ");
printf("\n . ,B7 ");
printf("\n 12JFuv77rrv@BkU2 ");
printf("\n @B@B@B@B@B@B@B@B ");
printf("\n .20B@@MOOBMBM@MOO@B@O0L ");
printf("\n 7@B@BBO8ZOZ8GOOMBBM@B@@@B:
");
printf("\n @BBF5FNEO8MMBMBM@8u0Gj@@@B ");
printf("\n ZB@08@@B@B@B@B@B@@@B@BM0@B@j ");
printf("\n O@MPB@,:irrrr7r77L2i::BO@@BF ");
printf("\n BB@G@B ....,,::i7q @B@B@J ");
printf("\n O@MEBB . ....,,iu B@B@Bu ");
printf("\n 7@B@O@BG0ZqPSXkXSqPMN0Z@O@B@B: ");
printf("\n 5B@B@B@B@B@@@B@B@B@B@B@B@B@B@; ");
printf("\n .,:;r7vLvjjuLLvLr7i:.. ");
printf("\n ");
}
void vencedor(){
	printf("\n____________oo$$$$$$$$$$$$$$$$$$$$$$$$o");
	printf("\n_________oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o");
	printf("\n_______o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o");
	printf("\n_____o$$$$$$$$$____$$$$$$$$$$$$$____$$$$$$$$$o");
	printf("\n____o$$$$$$$$$______$$$$$$$$$$$______$$$$$$$$$$o");
	printf("\n___$$$$$$$$$$$______$$$$$$$$$$$______$$$$$$$$$$$$");
	printf("\n__$$$$$$$$$$$$$____$$$$$$$$$$$$$____$$$$$$$$$$$$$$");
	printf("\n_$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$");
	printf("\no$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$");
	printf("\n$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$");
	printf("\n$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$___$$$");
	printf("\n$$$$$__$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$___o$$$");
	printf("\n_$$$$___$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$_____$$$$");
	printf("\n__$$$$_____$$$$$$$$$$$$$$$$$$$$$$$$$$$$______o$$$");
	printf("\n___$$$o________$$$$$$$$$$$$$$$$$$$$$_________$$$");
	printf("\n____$$$o__________ $$ $$$$$$$_____________o$$$");
	printf("\n_____$$$$o_________________oo_____________o$$$");
	printf("\n_______$$$$o______o$$$$$$o $$$$o________o$$$$");
	printf("\n_________$$$$$oo_______$$$$o$$$$$o___o$$$$");
	printf("\n_____________$$$$$oooo___$$$o$$$$$$$$$$");
	printf("\n________________$$$$$$$oo $$$$$$$$$$");
	printf("\n__________________________$$$$$$$$$$$");
	printf("\n__________________________$$$$$$$$$$$$");
	printf("\n___________________________$$$$$$$$$$");
	printf("\n_____________________________$$$$$");
}
menus.h
#include <stdio.h>
#include <stdlib.h>
int menu();
int menu_form();
int menu_sair();
void campeao();
void vencedor();
projeto_heap.cpp
#include <stdio.h>
#include <stdlib.h>
#include"projeto_heap.h"
struct heap{
	int chave;
	heap *pai;//Só vai ser usado quando aplicar o upheap
	heap *esquerda;
	heap *direita;
};
Heap* heap_cria(){
	Heap* heap = (Heap*) malloc(sizeof(Heap));
	if(heap){
		*heap = NULL;
	}
	return heap;
}
void libera_no(Nodo* no){
	if(no == NULL)return;
	libera_no(no->esquerda);
	libera_no(no->direita);
	free(no);
	no = NULL;
}
void heap_distroi(Heap* raiz){
	if(raiz == NULL)return;
	libera_no(*raiz);
	free(raiz);
}
int teste_retira(Fila* fi){
	Nodo* h = (Nodo*)fila_retira(fi);
	return h->chave;
}
int arvore_teste(Fila* fi,int chave){
	Nodo* h = (Nodo*) malloc(sizeof(Nodo));
	h->chave = chave;
	fila_insere(fi,h);
	return(h->chave);
}
void imprime(Fila* fi){
	for(Lista* aux = get_inicio(fi); aux; aux=get_proximo(aux)){
		Nodo* info =(Nodo*) get_info(aux);
		printf("%i ",info->chave);
	}
}
void heap_insere_largura(Heap* raiz,int chave ){
 Fila *fi = fila_cria();//cria uma fila vazia
 Nodo *novo;
 
	novo = (Nodo*)malloc(sizeof(Nodo));//cria um novo nodo ( chave )
 if(!novo) printf("\n\tMemoria nao alocada %i",novo);
 novo->chave = chave;
 novo->esquerda = NULL;
 novo->direita = NULL;
 novo->pai = NULL;
 if(!(*raiz)){//Se raiz vazia Então 	
 *raiz = novo;
 (*raiz)->esquerda = NULL;
 (*raiz)->direita = NULL;
 (*raiz)->pai = NULL;
 }else{			
 fila_insere(fi,*raiz);//enfilera( raiz, fila )		
 while(!fila_vazia(fi)){//enquanto fila não vazia 			 
 Nodo *node;
 node = (Nodo*)fila_retira(fi); 
			novo->pai = node; 
			//fila_retira(fi); //nodo = desenfilera( fila )						
			if(!node->esquerda){//Se nodo.esq é vazio Então
 node->esquerda = novo;
 upheap(novo);
 fila_esvazia(fi);//esvazia fila				
 }else if(!node->direita){//Senão Se nodo.dir é vazio Então
 node->direita = novo;
 upheap(novo);
 fila_esvazia(fi);//esvazia fila				
 }else{//Senão 	
 fila_insere(fi,node->esquerda);//enfilera( nodo.esq, fila )
				fila_insere(fi,node->direita);//enfilera( nodo.dir, fila )
 }// Fim-se 
 }//fim-enquanto 
		fila_destroi(fi); 
 }//Fim-Senão
}
void heap_pre_ordem(Heap* raiz){
	if(!(*raiz))return;
	Nodo* no = (*raiz);		
	if(no){
		printf("%d ",no->chave);
		heap_pre_ordem(&(no->esquerda));
		heap_pre_ordem(&(no->direita));
	}
}
void heap_imprime(Heap* raiz){
	if(!(*raiz))return;
	Fila* fi = fila_cria();	
	fila_insere(fi,*raiz);//fila_ins(arvore);
	int x = 0;
	while(!fila_vazia(fi)){
		Nodo* p = (Nodo*)fila_retira(fi);
		printf("%d ",p->chave);
		if(p->esquerda) fila_insere(fi,p->esquerda);
		if(p->direita) fila_insere(fi,p->direita);
	}
	fila_destroi(fi);
}
static void troca(Nodo* filho,Nodo* pai){
	if(!filho || !pai)return;
	int chave = filho->chave;
	filho->chave = pai->chave;
	pai->chave = chave;
}
void upheap(Nodo* no){
	Nodo* filho = no;
	Nodo* pai =no->pai;
	if(pai){
		if(filho->chave > pai->chave){
			troca(filho,pai);
			upheap(pai);
		}
	}
}
Nodo* busca_ultimo(Heap* raiz){
	Nodo* p = *raiz;
	if(!p)return NULL;
	Fila* fi = fila_cria();	
	fila_insere(fi,p);	
	while(!fila_vazia(fi)){
		p = (Nodo*)fila_retira(fi);
		if(p->esquerda) fila_insere(fi,p->esquerda);
		if(p->direita) fila_insere(fi,p->direita);
	}
	fila_destroi(fi);
	return p;
}
int heap_conte_nos(Heap* raiz){
	if(!*raiz)return 0;
	Fila* fi = fila_cria();
	Nodo* p = *raiz;
	fila_insere(fi,p);
	int i = 0;	
	while(!fila_vazia(fi)){
		p = (Nodo*)fila_retira(fi);
		i++;
		if(p->esquerda) fila_insere(fi,p->esquerda);
		if(p->direita) fila_insere(fi,p->direita);
	}
	fila_destroi(fi);
	return i;
}
/*
int heap_excluir_no(Heap* raiz){
	if(!raiz)return 0;
	Nodo* aux = *raiz;
	if(!aux->esquerda){
		aux = NULL;
		free(aux);
	}else if(aux->pai){
		if(!aux->pai->direita){
			aux->pai->esquerda = NULL;
			free(aux->pai->esquerda);
		}else{
			aux->pai->direita =NULL;
			free(aux->pai->direita);
		}
	}
	return 1;
}
*/
int heap_excluir_no(Heap* raiz){
	if(!raiz)return 0;
	Nodo* no = *raiz;
	Fila* fi = fila_cria();	
	Fila* aux = fila_cria();	
	fila_insere(fi,no);
	while(!fila_vazia(fi)){		
		Nodo *p = (Nodo*)fila_retira(fi);
		fila_insere(aux,p);
		if(p->esquerda) fila_insere(fi,p->esquerda);
		if(p->direita) fila_insere(fi,p->direita);
	}
	Lista* li;
	Nodo* teste;
	while(!fila_vazia(aux)){		
		teste = (Nodo*) fila_retira_fim(aux);
		if(!teste->direita && teste->esquerda)
			break;
		else if(teste->direita && teste->esquerda)
			break;
	}
	if(teste){
		if(!teste->direita && !teste->esquerda){
			teste = NULL;
			*raiz = NULL;
			free(teste);
		}else if(!teste->direita){
			teste->esquerda = NULL;
			free(teste->esquerda);
		}else{
			teste->direita = NULL;
			free(teste->direita);
		}
	}
	fila_destroi(aux);
	fila_destroi(fi);
	return 1;
}
static int eh_folha(Nodo* no){	
	return !no->esquerda && !no->direita;
}
static int maior(int x,int y){
	return (x>y)?x:y;
}
static int tem_um_filho(Nodo* no){
	return no->esquerda && !no->direita;
}
void downheap(Nodo* no){	
	if(!no)return;
	if(!eh_folha(no)){	
		if(tem_um_filho(no)){
			if(no->chave < no->esquerda->chave){			
				troca(no,no->esquerda);
}
		}else if(maior(no->esquerda->chave,no->direita->chave)>no->chave){			
			if(no->esquerda->chave > no->direita->chave){
				troca(no,no->esquerda);
				downheap(no->esquerda);
			}else{
				troca(no,no->direita);
				downheap(no->direita);
			}
		}
	}else
		return;
}
int heap_remove(Heap* raiz){
	if(!*raiz)return 0;
	Nodo* no = busca_ultimo(raiz);
	(*raiz)->chave = no->chave;
	heap_excluir_no(raiz);
	downheap(*raiz);
	return 1;
}
projeto_heap.dev
[Project]
FileName=projeto_heap.dev
Name=projeto_heap
Type=1
Ver=2
ObjFiles=
Includes=
Libs=
PrivateResource=
ResourceIncludes=
MakeIncludes=
Compiler=
CppCompiler=
Linker=
IsCpp=1
Icon=
ExeOutput=
ObjectOutput=
LogOutput=
LogOutputEnabled=0
OverrideOutput=0
OverrideOutputName=
HostApplication=
UseCustomMakefile=0
CustomMakefile=
CommandLine=
Folders=
IncludeVersionInfo=0
SupportXPThemes=0
CompilerSet=0
CompilerSettings=0000000000000000000000000
UnitCount=7
[VersionInfo]
Major=1
Minor=0
Release=0
Build=0
LanguageID=1033
CharsetID=1252
CompanyName=
FileVersion=
FileDescription=Developed using the Dev-C++ IDE
InternalName=
LegalCopyright=
LegalTrademarks=
OriginalFilename=
ProductName=
ProductVersion=
AutoIncBuildNr=0
SyncProduct=1
[Unit2]
FileName=fila.h
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
[Unit1]
FileName=main.cpp
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
[Unit3]
FileName=fila.cpp
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
[Unit4]
FileName=projeto_heap.h
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
[Unit5]
FileName=projeto_heap.cpp
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
[Unit6]
FileName=menus.cpp
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
[Unit7]
FileName=menus.h
CompileCpp=1
Folder=
Compile=1
Link=1
Priority=1000
OverrideBuildCmd=0
BuildCmd=
projeto_heap.h
//projeto_heap.h
//typedef struct heap Heap;
#include"fila.h"
typedef struct heap* Heap;
typedef struct heap Nodo;
Heap* heap_cria();
void heap_distroi(Heap* raiz);
void heap_insere_largura(Heap* raiz,int chave );
void upheap(Nodo* no);
int heap_excluir_no(Heap* raiz);
int arvore_teste(Fila* fi,int chave);
int teste_retira(Fila* fi);
Nodo* busca_ultimo(Heap* raiz);
int heap_remove(Heap* raiz);
void downheap(Nodo* no);
void heap_pre_ordem(Heap* raiz);
void imprime(Fila* fi);
void heap_imprime(Heap* raiz);
//int eh_folha(Nodo* no)