Exemplos em linguagem C, lista, pilha, fila, ordenação de vetor, ordenação InsertionSort, ordenação BlubbleSort

Prévia do material em texto

Exemplos em linguagem C 
Fila, pilha e ordenação 
Nenhum exemplo deste é de minha autoria, são apenas para referência. 
Álison Bissoli 
 
1 – Lista encadeada 
2 - Pilha 
3 - Pilha 2 
4 - Inserir na pilha até digitar 999 
5 - Decimal para binário utilizando pilha 
6 - FILA 
7 - Ordenação de vetor 
8 - Ordenação InsertionSort 
9 - Ordenação BubbleSort 
 
1. Lista encadeada 
 
//TAD - lista 
//este exemplo insere dados sempre no final da lista encadeada. Os valores sao informados 
pelo usuario e mostrados no final 
 
include <stdio.h> 
typedef struct 
{ 
 int codigo; 
 float custo; 
 struct peca *prox; 
} peca; 
peca *inicio,*fim; 
void inicialista() 
{ 
 inicio=fim=NULL; 
 printf("\nLista inicializada. tecle algo "); 
 getch(); 
} 
void mostra(int k, peca *aux) 
{ 
 if (aux == NULL) return; 
 else 
 { 
 printf("\n%3d %4d %8.2f",k+1,aux->codigo,aux->custo); 
 aux=(peca *)aux->prox; 
 k++; 
 mostra(k,aux); 
 } 
} 
int main() 
{ 
 int k,t; 
 peca *aux,*p; 
 printf("\nQuantas pecas serao informadas? "); 
 scanf("%d",&t); 
 while (t<1) 
 { 
 printf("Quantidade deve ser maior que zero "); 
 scanf("%d",&t); 
 } 
 inicialista(); //inicia a lista 
 for (k=0; k<t; k++) //preenche a lista com dados informados 
 { 
 //aloca memoria e insere valores na lista encadeada 
 p = (peca*)malloc(sizeof(peca)); 
 if (p == NULL) 
 { 
 printf("\nNao ha memoria suficiente. Tecle algo"); 
 getch(); 
 return 0; 
 } 
 printf("\ndigite numero inteiro para codigo %d: ",k+1); 
 scanf("%d",&p->codigo); 
 printf("digite numero real para custo %d: ",k+1); 
 scanf("%f",&p->custo); 
 //ajusta os controles da lista 
 if (inicio == NULL) 
 { 
 p->prox=NULL; 
 inicio=fim=p; 
 aux=p; 
 } 
 else 
 { 
 p->prox=NULL; 
 fim=p; 
 aux->prox=(struct peca*)p; 
 aux=p; 
 } 
 } 
//mostra os dados da lista 
 system("cls"); 
 printf("*** Listagem da lista de pecas ***\n\n"); 
 printf("Ord codigo custo\n"); 
 aux=inicio; 
 k=0; 
 mostra(k,inicio); 
 /* 
 while (aux != NULL) 
 { 
 printf("\n%3d %4d %8.2f",k+1,aux->codigo,aux->custo); 
 aux=(peca *)aux->prox; 
 k++; 
 } 
 */ 
//libera a memoria alocada 
 free(aux); 
 free(inicio); 
 free(fim); 
 free(p); 
 printf("\n\nTecle algo para encerrar..."); 
 getch(); 
 return 0; 
} 
 
 
2. Pilha 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
//declaraçao da estrurura pilha 
struct pilha 
{ 
 int codigo; 
 float custo; 
 struct pilha *prox; 
} pilha; 
struct pilha *topo; 
void inicialista() 
{ 
 topo=NULL; 
 printf("\nLista inicializada! O que deseja fazer agora?\n"); 
} 
// FUNÇAO PARA SELECIONAR OPCAO DO MENU. 
int menu() 
{ 
 int opc; 
 printf("\nDigite o numero da opcao desejada: \n"); 
 printf("0 - Encerrar.\n"); 
 printf("1 - Inserir Cadastro na Pilha.\n"); 
 printf("2 - Retirar Cadastro da Pilha.\n"); 
 printf("3 - Exibir Cadastros Empilhados.\n"); 
 scanf("%d", &opc); 
 while(opc<0 || opc>3 || opc%1 !=0) 
 { 
 system("cls"); 
 printf("\nOpcao invalida. Escolha novamente.\n"); 
 printf("\nDigite o numero da opcao desejada: \n"); 
 printf("0 - Encerrar.\n"); 
 printf("1 - Inserir Cadastro na Pilha.\n"); 
 printf("2 - Retirar Cadastro da Pilha.\n"); 
 printf("3 - Exibir Cadastros Empilhados.\n"); 
 fflush(stdin); 
 scanf("%d", &opc); 
 } 
 return opc; 
} 
// FUNÇAO PARA MOSTRAR A PILHA GERADA. 
void mostra(int k, struct pilha*aux) 
{ 
 if (aux == NULL) return; 
 else 
 { 
 printf("\n %3d %4d %8.2f",k+1,aux->codigo,aux->custo); 
 aux=(struct pilha*)aux->prox; 
 k++; 
 mostra(k,aux); 
 } 
} 
int main () 
{ 
 //INICIA A PILHA 
 inicialista(); 
 int k,t=0, opcao,tam=0; 
 struct pilha *aux,*novo; 
 do 
 { 
 opcao=menu(); 
 switch(opcao) 
 { 
 case 0: // ENCERRA O PROGRAMA. 
 break; 
 case 1: // INSERE OS CADASTROS NA PILHA. 
 system("cls"); 
 printf("\nOpcao 1 Selecionada - Inserir Cadastro na Pilha.\n"); 
 printf("\nQuantas pecas serao informadas? "); 
 scanf("%d",&t); 
 while (t<1) 
 { 
 printf("Quantidade deve ser maior que zero."); 
 scanf("%d",&t); 
 } 
 tam=tam+t; 
//preenche a pilha com os valores informados 
 for (k=0; k<t; k++) 
 { 
//aloca memoria e insere valores na pilha 
 novo = (struct pilha*) malloc(sizeof(struct pilha)); 
 if (novo == NULL) 
 { 
 printf("\nNao ha memoria suficiente para alocar o cadastro. Tecle algo para 
encerrar."); 
 getch(); 
 return 0; 
 } 
 printf("\nCADASTRO PECA:\n"); 
 printf("\nDigite numero inteiro para codigo:"); 
 scanf("%d",&novo->codigo); 
 printf("Digite numero real para custo:"); 
 scanf("%f",&novo->custo); 
//ajusta os controles da PILHA 
 novo->prox=(struct pilha*)topo; 
 topo=novo; 
 } 
 system("cls"); 
 printf("\nCADASTRO REALIZADO COM SUCESSO!\n"); 
 printf("\nO que deseja fazer agora?\n"); 
 break; 
 case 2: // RETIRA OS CADASTROS DA PILHA SEGUINDO O PADRAO UEPS 
 system("cls"); 
 printf("\nOpcao 2 Selecionada - Retirar Cadastro da Pilha.\n"); 
 int n; 
 printf("Deseja retirar quantos cadastros da pilha?"); 
 scanf("%d", &n); 
 if (n>tam) 
 { 
 system("cls"); 
 printf("Impossivel. Nao ha essa quantidade de elementos na pilha atual."); 
 break; 
 } 
 for (k=0; k<n; k++) 
 { 
 free(topo); 
 topo=topo->prox; 
 novo=novo->prox; 
 } 
 system("cls"); 
 printf("\nCADASTROS RETIRADOS COM SUCESSO!\n"); 
 printf("\nO que deseja fazer agora?\n"); 
 tam=tam-n; 
 break; 
 case 3: // Exibir a pilha atual - o ultimo elemento inserido sempre fica no topo. 
 system("cls"); 
 printf("\nOpcao 3 Selecionada - Exibir Cadastros Empilhados.\n"); 
 printf("Ordem | Codigo | Custo\n"); 
 aux=topo; 
 k=0; 
 mostra(k,topo); // funçao para mostrar os elementos da pilha 
 printf("\nO que deseja fazer agora?\n"); 
 break; 
 default: 
 printf("\nOpcao invalida.\n"); 
 } 
 } 
 while(opcao !=0); 
//libera a memoria alocada 
 free(aux); 
 free(novo); 
 free(topo); 
 printf("\n\nTecle algo para encerrar..."); 
 getch(); 
 return 0; 
} 
 
 
3. Pilha 2 
/******************************************************** 
 
 PILHA 
 -------- 
 
 Rotinas básicas de manipulação de Pilha: 
 - Estruturas de dados com alocação estática 
 - Inserção no final (topo) do vetor 
 - Remoção do final (topo) do vetor 
 
 Aplicação típica: 
 - O ultimo a entrar eh o primeiro a sair 
 
*********************************************************/#include <stdio.h> 
#include <conio.h> 
 
#define MAX_PILHA 100 
 
#define FALSO 0 
#define VERDADEIRO 1 
 
#define OK 1 
#define ERRO 0 
 
typedef int Tipo_Dado; 
 
typedef struct 
 { 
 Tipo_Dado Dado[MAX_PILHA]; 
 int Base,Topo; 
 } Tipo_Pilha; 
 
/* Rotinas de Manipulacao de Pilha - Lista Linear Seqüencial */ 
 
void inicializa_pilha (P) 
Tipo_Pilha *P; 
{ 
 P->Base=0; 
// como foi passado o endereço da estrutura, o acesso é feito através do símbolo -> 
 P->Topo=0; 
} 
 
int insere_pilha (P, Dado) 
Tipo_Pilha *P; 
Tipo_Dado Dado; 
{ 
 if (P->Topo < MAX_PILHA) /* Vetor nao esta cheio ? */ 
 { 
 P->Dado[P->Topo]=Dado; 
 (P->Topo)++; 
 return(OK); 
 } 
 else 
 return(ERRO); 
} 
 
retira_pilha (P, Dado) 
Tipo_Pilha *P; 
Tipo_Dado *Dado; 
{ 
 if (P->Topo == P->Base) 
 return(ERRO); 
 else 
 { 
 (P->Topo)--; 
 *Dado=P->Dado[P->Topo]; 
 return(*Dado); 
 } 
} 
 
void exibe_pilha (P) 
Tipo_Pilha P; 
{ 
 Tipo_Dado dado; 
 int cont; 
 
 printf("\n"); 
 for (cont=(P.Topo)-1; cont >= (P.Base); cont--) 
 printf("Vetor[%d]=%d\n",cont,P.Dado[cont]); 
 printf("\n"); 
} 
 
int quantidade_pilha (P) 
Tipo_Pilha P; 
{ 
 return( P.Topo-P.Base ); 
} 
 
int cheia_pilha (P) 
Tipo_Pilha P; 
{ 
 if (P.Topo == MAX_PILHA) 
 return(OK); 
 else 
 return(!OK); 
} 
 
int vazia_pilha (P) 
Tipo_Pilha P; 
{ 
 if (P.Topo == P.Base) 
 return(OK); 
 else 
 return(!OK); 
} 
 
int esvazia_pilha (P) 
Tipo_Pilha *P; 
 
{ 
 P->Topo=0; 
 P->Base=0; 
} 
 
 
 
4. Inserir na pilha até digitar 999 
 
/************************************************************ 
EXEMPLO DE APLICACAO 1: PROGRAMA PRINCIPAL 
O programa abaixo ilustra a possibilidade para reverter uma certa sequencia de valores 
numéricos inseridos ate que seja digitado o valor 999. 
************************************************************/ 
 
void main() 
{ 
 int num, x; 
 Tipo_Pilha P; 
 clrscr(); 
 inicializa_pilha(&P); 
 printf("\nArmazene um numero: "); 
 scanf("%d",&num); 
 while( (num !=999) && (cheia_pilha(P) != 1)) { 
 insere_pilha(&P,num); 
 printf("\nArmazene um numero: "); 
 scanf("%d",&num); 
 } 
 printf("\nSequencia LIFO\n"); 
 while(vazia_pilha(P) != 1) { 
 x=retira_pilha(&P); 
 printf("%d ",x); 
 } 
 getch(); 
} 
 
 
5. Decimal para binário utilizando pilha 
/************************************************************ 
EXEMPLO DE APLICACAO 2: PROGRAMA PRINCIPAL 
O programa abaixo ilustra Conversão de um número decimal para a base binária, utilizando 
PILHAS 
************************************************************/ 
 
void main() 
{ 
 
 int x,num,den, resto; 
 Tipo_Pilha P; 
 clrscr(); 
 inicializa_pilha(&P); 
 printf("\nEntre com o numero na base decimal: "); 
 scanf("%d",&num); 
 printf("\nO numero %d na base 10 -> ",num); 
 while( (num !=0) && (cheia_pilha(P) != 1) ) { 
 resto = num%2; 
 den = num/2; 
 num = den; 
 insere_pilha(&P,resto); 
 } 
 while(vazia_pilha(P) != 1) { 
 x=retira_pilha(&P); 
 printf("%d",x); 
 } 
 printf(" na base 2\n"); 
 getch(); 
} 
 
 
 
 
 
 
 
 
 
 
6. FILA 
 
/******************************************************** 
 FILA 
 ------ 
 Rotinas básicas de manipulação de FILAS usando vetores: 
 - Estruturas de dados com alocação estática 
 - Insere no final da fila 
 - Remoção do inicio da fila 
 - Fila circular 
 Aplicação típica: 
 - Lista de elementos a espera de um tratamento, 
 em que a ordem de chegada e importante 
*********************************************************/ 
 
#include <stdio.h> 
#include <conio.h> 
#define MAX_FILA 100 
#define FALSO 0 
#define VERDADEIRO 1 
#define OK 1 
#define ERRO 0 
typedef int Tipo_Dado; 
typedef struct 
 { 
 Tipo_Dado Dado[MAX_FILA]; 
 int Inicio,Fim; 
 } Tipo_Fila; 
 
/* Rotinas de Manipulacao de FILAS - First In, First Out (FIFO) Alocacao seqüencial */ 
void inicializa_fila (Tipo_Fila *F) 
{ 
 F->Inicio=0; 
 F->Fim=0; 
} 
int insere_fila (Tipo_Fila *F,Tipo_Dado Dado) 
{ 
 int prox; 
 
 prox=F->Fim+1; 
 
 if (prox == MAX_FILA) 
 prox=0; 
 
 if (prox == F->Inicio) 
 return(ERRO); 
 else 
 { 
 F->Dado[F->Fim]=Dado; 
 F->Fim=prox; 
 return(OK); 
 } 
} 
int retira_fila (Tipo_Fila *F,Tipo_Dado *Dado) 
{ 
 if (F->Fim == F->Inicio) 
 return(ERRO); 
 else 
 { 
 *Dado= F->Dado[F->Inicio]; 
 (F->Inicio)++; 
 if (F->Inicio >= MAX_FILA) 
 F->Inicio=0; 
 return(OK); 
 } 
} 
void lista_fila (Tipo_Fila F) 
{ 
 int cont; 
 printf("\n"); 
 cont=F.Inicio; 
 while (cont != F.Fim) 
 { 
 printf("Fila[%d]=%d\n",cont,F.Dado[cont]); 
 cont++; 
 if (cont >= MAX_FILA) 
 cont=0; 
 } 
 printf("\n"); 
} 
int consulta_fila (Tipo_Fila F,int Indice,Tipo_Dado *Dado) 
{ 
 if (F.Fim > F.Inicio) 
 if ((Indice <= F.Inicio) || (Indice > F.Fim) || 
 (Indice >= MAX_FILA) || (Indice < 0)) 
 return(ERRO); 
 else 
 if (((Indice > F.Fim) && (Indice <= F.Inicio)) || 
 (Indice >= MAX_FILA) || (Indice < 0)) 
 return(ERRO); 
 else 
 { 
 *Dado=F.Dado[Indice]; 
 return(OK); 
 } 
} 
 
int acha_fila (Tipo_Fila F,Tipo_Dado Dado,int *Indice) 
{ 
 int cont; 
 int achou; 
 
 achou=FALSO; 
 cont = F.Inicio; 
 *Indice = NULL; 
 while (cont != F.Fim) 
 { 
 cont++; 
 if (cont == MAX_FILA) 
 cont=0; 
 
 if (F.Dado[cont] == Dado) 
 { 
 achou=VERDADEIRO; 
 *Indice=cont; 
 break; 
 } 
 } 
 
 if (achou) 
 return(OK); 
 else 
 return(ERRO); 
} 
 
int cheia_fila (Tipo_Fila F) 
{ 
 if ((F.Fim+1 == F.Inicio) || (F.Fim+1 > MAX_FILA)) 
 return(OK); 
 else 
 return(ERRO); 
} 
 
int vazia_fila (Tipo_Fila F) 
{ 
 if (F.Fim == F.Inicio) 
 return(OK); 
 else 
 return(ERRO); 
} 
int quantidade_fila (Tipo_Fila F) 
{ 
 if (F.Fim > F.Inicio) 
 return(F.Fim-F.Inicio); 
 else 
 return(F.Fim+(MAX_FILA-1)-F.Inicio); 
} 
/* PROGRAMA PRINCIPAL */ 
main() 
{ 
 Tipo_Fila F; 
 int Valor; 
 
 printf("\n>>> ROTINAS DE MANIPULACAO DE FILAS <<<\n\n"); 
 
 inicializa_fila(&F); 
 
 if (vazia_fila(F)) 
 printf("=> F vazia\n"); 
 
 if (insere_fila(&F,2)) 
 printf("=> Valor 2 inserido na fila\n"); 
 
 if (insere_fila(&F,4)) 
 printf("=> Valor 4 inserido na fila\n"); 
 
 if (insere_fila(&F,6)) 
 printf("=> Valor 6 inserido na fila\n"); 
 printf("\n=> Elementos da fila... [inicio ao fim]\n"); 
 lista_fila(F); 
 if (acha_fila(F,4,&Valor)) 
 printf("=> O valor 4 foi achado na posicao %d\n",Valor); 
 
 if (!acha_fila(F,5,&Valor)) 
 printf("=> O valor 5 nao foi achado na fila\n"); 
 
 if (retira_fila(&F,&Valor)) 
 printf("=> Valor %d retirado da fila\n",Valor); 
 
 if (retira_fila(&F,&Valor)) 
 printf("=> Valor %d retirado da fila\n",Valor); 
 
 if (retira_fila(&F,&Valor)) 
 printf("=>Valor %d retirado da fila\n",Valor); 
 
 printf("Pressione uma tecla para continuar...\n"); 
 getch(); 
 
 printf("\n=> Elementos da fila... [inicio ao fim]\n"); 
 lista_fila(F); 
 
 if (vazia_fila(F)) 
 printf("=> F vazia\n"); 
 
 printf("Pressione uma tecla para terminar o programa...\n"); 
 getch(); 
} 
 
 
7. Ordenação de vetor 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
//função que ordena vetor 
void ordenavet(int *p, int* u) 
{ 
//ordenacao por selecao direta 
 int *k,*j,aux; 
 if (p == NULL) 
 { 
 printf("\nVetor vazio.Tecle algo para retornar"); 
 getch(); 
 } 
 else 
 for (k=p; k<u-1; k++) 
 for (j=k+1; j<u; j++) 
 { 
 if (*k>*j) 
 { 
 aux=*k; 
 *k=*j; 
 *j=aux; 
 } 
 } 
} 
//função que mostra vetor 
void mostravet(int *p, int *u) 
{ 
 int *aux; 
 aux=p; 
 printf("\n"); 
 if (aux == NULL) 
 { 
 printf("\nVetor vazio.Tecle algo para retornar"); 
 getch(); 
 } 
 else 
 while (aux<u) 
 { 
 printf("%d ",*aux); 
 aux++; 
 } 
 free(aux); 
 printf("\n"); 
} 
int main() 
{ 
 int k,tam, *pri, *ult, *p; 
 printf("\nQual o tamanho do vetor? "); 
 scanf("%d",&tam); 
 p = malloc(tam*sizeof(int)); 
 if (p == NULL) 
 { 
 printf("\nNao foi possivel alocar memoria"); 
 printf("\nTecle algo para terminar"); 
 getch(); 
 return 0; 
 } 
 else 
 { 
 Página 1 
 vetordin2 
 pri=p; 
 srand(time(NULL)); 
 /*preenche o vetor com inteiros aleatorios 
 no intervalo [1, 100] 
 */ 
 for (k=0; k<tam; k++) 
 { 
 *p = rand()%100+1; 
 p++; 
 } 
 ult=p; 
 } 
//chama função que mostra vetor antes de ordenar 
 printf("\nVetor de aleatorios nao ordenado:\n"); 
 mostravet(pri,ult); 
//chama funcao para ordenar o vetor 
 ordenavet(pri,ult); 
//mostra vetor apos ordenar 
 printf("\nVetor depois de ordenado:\n"); 
 mostravet(pri,ult); 
 printf("\n"); 
 printf("\nObrigado por usar este programa.\nTecle algo para encerrar..."); 
 getch(); 
 return 0; 
} 
 
 
 
8. Ordenação insertionSort 
 
void insertionSort(int numeros[], int tam) { 
 int i, j, eleito; 
 for (i = 1; i < tam; i++){ 
 eleito = numeros[i]; 
 j = i - 1; 
 while ((j>=0) && (eleito < numeros[j])) { 
 numeros[j+1] = numeros[j]; 
 j--; 
 } 
 numeros[j+1] = eleito; 
 } 
} 
 
// Ordenação SelectionSort 
 
void selection_sort(int num[], int tam) 
{ 
 int i, j, min, aux; 
 for (i = 0; i < (tam-1); i++) 
 { 
 min = i; 
 for (j = (i+1); j < tam; j++) { 
 if(num[j] < num[min]) { 
 min = j; 
 } 
 } 
 if (i != min) { 
 aux = num[i]; 
 num[i] = num[min]; 
 num[min] = aux; 
 } 
 } 
} 
 
 
9. Ordenação Bubble sort 
 
#include <stdio.h> 
 int main(void){ 
 int vetor[10] = {10,9,8,7,6,5,4,3,2,1}; 
 int tamanho = 10; 
 int aux; 
 for(int i=tamanho-1; i >= 1; i--) { 
 for( int j=0; j < i ; j++) { 
 if(vetor[j]>vetor[j+1]) { 
 aux = vetor[j]; 
 vetor[j] = vetor[j+1]; 
 vetor[j+1] = aux; 
 } 
 } 
 } 
 for( int r = 0; r < 10; ++r){ 
 
 printf("%d\n",vetor[r]); 
 } 
}