Programar em C
185 pág.

Programar em C


DisciplinaLinguagem de Programação Estruturada128 materiais1.055 seguidores
Pré-visualização40 páginas
da pilha (pop)
int desempilhar (Pilha *monte){
 Elemento *p_elemento;
 if (monte->tamanho == 0)
 return -1;
 p_elemento = monte->inicio;
 monte->inicio = monte->inicio->proximo;
 free (p_elemento->dados);
 free (p_elemento);
 monte->tamanho--;
 return 0;
}
Imprimir os elementos da pilha
void mostrar(Pilha * monte){
 Elemento *atual;
 int i;
 atual = monte->inicio;
Pilha 163
 for(i=0;i<monte->tamanho;++i){
 printf(&quot;\t\t%s\n&quot;, atual->dados);
 atual = atual->proximo;
 }
}
Fila ou Queue
Fila
Uma fila ou queue em inglês é uma estrutura de dados que usa o método FIFO(acrônimo para First In, First Out, que
em português significa primeiro a entrar, primeiro a sair).
A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o
elemento do início.
Exemplo de fila em C:
 
 #include <stdio.h> 
 #include <string.h> 
 #include <stdlib.h> 
 void q_enter(void);
 void q_list(void);
 int q_store(char *ptr);
 int q_delete(void);
 int count = 0; //contador
 int store = 0; // proxima posição na fila
 int retrieve = 0; // recupera a posição da fila
 char *queue[100]; // vetor da fila
 int main()
 {
 int i = 0;
 for ( i = 0; i < 100; i++ )
 {
 queue[i] = NULL;
 }
 q_enter(); // entra os dados na fila
 printf(&quot;\n\nTodos os dados da fila (FIFO):\n&quot;);
 q_list();
 q_delete(); // Apaga a primeira entrada da fila
Fila ou Queue 164
 printf(&quot;\n\nA fila depois delete(FIFO):\n&quot;);
 q_list();
 printf(&quot;\n\nNumero de elementos restantes na fila: %i \n&quot;, count);
 getchar(); // espera
 return 0;
 }
 
 void q_enter(void)
 {
 static char str[100], *ptr;
 puts(&quot;Pressione a tecla ENTER sem nome pra sair\n&quot;);
 do {
 printf(&quot;Entre o nome:&quot;);
 gets(str);
 ptr = (char *) malloc(strlen(str)); //alocar um espaço na memória
 strcpy(ptr,str);
 if (*str)
 {
 count++;
 q_store(ptr); // Guarda o endereço da seqüência de caracteres
 }
 } while (*str); //Sair se não houver uma entrada
 }
 
 
 // listar a fila
 void q_list(void)
 {
 int k;
 
 for (k = retrieve; k < store; k++)
 {
 printf(&quot;Elemento %d : %s \n&quot;,k+1,queue[k]);
 }
}
 
 // Guarda os itens na fila
 int q_store(char *ptr)
 {
 if (store == 100) {
 printf(&quot;\nA lista esta cheia!\n&quot;);
 return 0 ;
 }
Fila ou Queue 165
 queue[store] = ptr;
 store++; // próximo índice da fila
 }
 
 // Apaga um item da fila
 int q_delete(void)
 {
 if (store == retrieve) {
 printf(&quot;\nA fila esta vazia!&quot;);
 return 0 ;
 }
 count--;
 retrieve++; 
 }
Árvores binárias
Arvore binária
Uma arvore binária é uma estrutura de dados que pode ser representada como uma hierarquia onde cada elemento é
chamado de nó . O nó inicial ou o primeiro elemento é chamado de raiz. Em uma arvore binária um elemento pode
ter um máximo de dois filhos no nível inferior denominados como sub-árvore esquerda e sub-árvore direita.Um nó
sem filhos é chamado de folha . A profundidade de um nó é a distância deste nó até a raiz e a distancia entre a folha
mais distante e a raiz é a altura da arvore.Um conjunto de nós com a mesma profundidade é denominado, nível da
árvore.
Struct
 typedef struct No{
 int numero;
 struct No *esquerda;
 struct No *direita;
}No;
Iniciar
void criarArvore(No **pRaiz){
 *pRaiz = NULL;
}
Inserção
void inserir(No **pRaiz, int numero){
 if(*pRaiz == NULL){
 *pRaiz = (No *) malloc(sizeof(No));
 (*pRaiz)->esquerda = NULL;
 (*pRaiz)->direita = NULL;
Árvores binárias 166
 (*pRaiz)->numero = numero;
 }else{
 if(numero < (*pRaiz)->numero)
 inserir(&(*pRaiz)->esquerda, numero);
 if(numero > (*pRaiz)->numero)
 inserir(&(*pRaiz)->direita, numero);
 }
}
Remoção
No *MaiorDireita(No **no){
 if((*no)->direita != NULL) 
 return MaiorDireita(&(*no)->direita);
 else{
 No *aux = *no;
 if((*no)->esquerda != NULL) // se nao houver essa verificacao, 
esse nó vai perder todos os seus filhos da esquerda!
 *no = (*no)->esquerda;
 else
 *no = NULL;
 return aux;
 }
}
No *MenorEsquerda(No **no){
 if((*no)->esquerda != NULL) 
 return MenorEsquerda(&(*no)->esquerda);
 else{
 No *aux = *no; 
 if((*no)->direita != NULL) // se nao houver essa verificacao, 
esse nó vai perder todos os seus filhos da direita!
 *no = (*no)->direita;
 else
 *no = NULL;
 return aux;
 }
}
void remover(No **pRaiz, int numero){
 if(*pRaiz == NULL){ // esta verificacao serve para caso o numero 
nao exista na arvore.
 printf(&quot;Numero nao existe na arvore!&quot;);
 getch();
 return;
 }
 if(numero < (*pRaiz)->numero)
 remover(&(*pRaiz)->esquerda, numero);
Árvores binárias 167
 else 
 if(numero > (*pRaiz)->numero)
 remover(&(*pRaiz)->direita, numero);
 else{ // se nao eh menor nem maior, logo, eh o numero que 
estou procurando! :)
 No *pAux = *pRaiz; // quem programar no Embarcadero vai 
ter que declarar o pAux no inicio do void! :[
 if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == 
NULL)){ // se nao houver filhos...
 free(pAux);
 (*pRaiz) = NULL; 
 }
 else{ // so tem o filho da direita
 if ((*pRaiz)->esquerda == NULL){
 (*pRaiz) = (*pRaiz)->direita;
 pAux->direita = NULL;
 free(pAux); pAux = NULL;
 }
 else{ //so tem filho da esquerda
 if ((*pRaiz)->direita == NULL){
 (*pRaiz) = (*pRaiz)->esquerda;
 pAux->esquerda = NULL
 free(pAux); pAux = NULL;
 }
 else{ //Escolhi fazer o maior filho direito da 
subarvore esquerda.
 pAux = MaiorDireita(&(*pRaiz)->esquerda); //se vc 
quiser usar o Menor da esquerda, so o que mudaria seria isso:
 pAux->esquerda = (*pRaiz)->esquerda; //
 pAux = MenorEsquerda(&(*pRaiz)->direita);
 pAux->direita = (*pRaiz)->direita;
 (*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
 free((*pRaiz)); *pRaiz = pAux; pAux = NULL; 
 }
 }
 }
 }
}
Em ordem
void exibirEmOrdem(No *pRaiz){
 if(pRaiz != NULL){
 exibirEmOrdem(pRaiz->esquerda);
 printf(&quot;\n%i&quot;, pRaiz->numero);
 exibirEmOrdem(pRaiz->direita);
 }
}
Árvores binárias 168
Pré-ordem
void exibirPreOrdem(No *pRaiz){
 if(pRaiz != NULL){
 printf(&quot;\n%i&quot;, pRaiz->numero);
 exibirPreOrdem(pRaiz->esquerda);
 exibirPreOrdem(pRaiz->direita);
 }
}
Pós-ordem
void exibirPosOrdem(No *pRaiz){
 if(pRaiz != NULL){
 exibirPosOrdem(pRaiz->esquerda);
 exibirPosOrdem(pRaiz->direita);
 printf(&quot;\n%i&quot;, pRaiz->numero);
 }
}
Contar nós
int contarNos(No *pRaiz){
 if(pRaiz == NULL)
 return 0;
 else
 return 1 + contarNos(pRaiz->esquerda) + 
contarNos(pRaiz->direita);
} 
Contar folhas
int contarFolhas(No *pRaiz){
 if(pRaiz == NULL)
 return 0;
 if(pRaiz->esquerda == NULL && pRaiz->direita == NULL)
 return 1;
 return contarFolhas(pRaiz->esquerda)