Resumo de Estrutura de Dados 1

Prévia do material em texto

Resumo de Estrutura de Dados 1 
 
 
 
 
O operador Seta (->) existe para acessar os membros da estrutura ou sindicatos por 
meio de ponteiros. 
 
Struct 
Struct diferença de Typedef Struct: Quando usa um nome com struct o padrão de nome 
é menos importante porque ele certamente é um tipo, ele não pode ser usado, e, 
portanto, confundido, com outros identificadores do código. Quando usa um typedef a 
struct não precisa ter nome. Pode ter uma struct anônima sem typedef, mas aí ela não 
poderá ser usada em lugar algum mais na aplicação. 
A função printf possibilita a saída de valores (sejam eles constantes, variáveis ou 
resultado de expressões) segundo um determinado formato. Informalmente, podemos 
dizer 
que a forma da função é: 
printf (formato, lista de constantes/variáveis/expressões...); 
O primeiro parâmetro é uma cadeia de caracteres, em geral delimitada com aspas, que 
especifica o formato de saída das constantes, variáveis e expressões listadas em seguida. 
Para cada valor que se deseja imprimir, deve existir um especificador de formato 
correspondente na cadeia de caracteres formato. Os especificadores de formato variam 
com o tipo do valor e a precisão em que queremos que eles sejam impressos. Estes 
especificadores são precedidos pelo caractere % e podem ser, entre outros: 
 
//%d especifica um int 
//%u especifica um unsigned int 
//%f especifica um double (ou float) 
//%e especifica um double (ou float) no formato científico 
//%g especifica um double (ou float) no formato mais apropriado (%f ou %e) 
//%s especifica uma cadeia de caracteres 
/* 
 
 
/* 
&& operador binário E (AND) 
|| operador binário OU (OR) 
! operador unário de NEGAÇÃO (NOT) 
*/ 
 
/* Scanf 
 
A função scanf permite capturarmos valores fornecidos via teclado pelo usuário do 
programa. Informalmente, podemos dizer que sua forma geral é: 
scanf (formato, lista de endereços das variáveis...); 
O formato deve possuir especificadores de tipos similares aos mostrados para a função 
printf. Para a função scanf, no entanto, existem especificadores diferentes para o tipo 
float e o tipo double: 
 
A principal diferença é que o formato deve ser seguido por uma lista de endereços de 
variáveis (na função printf passamos os valores de constantes, variáveis e expressões). 
Na seção sobre ponteiros, este assunto será tratado em detalhes. Por ora, basta saber 
que, 
para ler um valor e atribuí-lo a uma variável, devemos passar o endereço da variável 
para a 
função scanf. O operador & retorna o endereço de uma variável. Assim, para ler um 
inteiro, devemos ter: 
int n; 
scanf ("%d", &n); 
 
%c especifica um char 
%d especifica um int 
%u especifica um unsigned int 
%f,%e,%g especificam um float 
%lf, %le, %lg especificam um double 
%s especifica uma cadeia de caracteres 
Structs, também conhecidas como Registros, definem tipos de dados que 
agrupam variáveis sob um mesmo tipo de dado. 
A ideia de usar uma struct é permitir que, ao armazenar os dados de uma 
mesma entidade, isto possa ser feito com uma única variável. Por exemplo, 
se for preciso armazenar a altura, o peso e a idade de uma pessoa, pode-se 
criar uma struct chamada Pessoa e agrupar os dados em um único tipo de 
dado, conforme o exemplo a seguir. 
Aos dados agruados em uma struct dá-se o nome de campos(fields). 
typedef struct // Cria uma STRUCT para armazenar os 
dados de uma pessoa 
{ 
 float Peso; // define o campo Peso 
 int Idade; // define o campo Idade 
 float Altura; // define o campo Altura 
} Pessoa; // Define o nome do novo tipo criado 
Após a criação do tipo, é possível declarar variáveis do tipo Pessoa, desta 
forma: 
Pessoa Joao, P1, P2; 
Pessoa Povo[10]; // cria um vetor de 10 pessoas. 
Para acessar os campos de uma struct, usa-se a sintaxe 
NomeDaVariavel.NomeDoCampo, conforme o exemplo a seguir. 
Joao.Idade = 15; 
Joao.Peso = 60.5; 
Joao.Altura = 1.75; 
 
Povo[4].Idade = 23; 
Povo[4].Peso = 75.3; 
Povo[4].Altura = 1.89; 
 
Outra vantagem de utilizar struct é a possibilidade de atribuir os dados de 
uma struct para outra, com apenas um comando de atribuição, como 
neste exemplo: 
 
P2 = Povo [4]; 
 
Passagem de Structs por Parâmetro 
 
Para passar uma struct por valor basta declará-la como um dos 
parâmetros, como no exemplo a seguir 
 
#include <stdio.h> 
 
typedef struct // Cria uma STRUCT para armazenar os 
dados de uma pessoa 
{ 
 float Peso; // define o campo Peso 
 int Idade; // define o campo Idade 
 float Altura; // define o campo Altura 
} Pessoa; // Define o nome do novo tipo criado 
 
void ImprimePessoa(Pessoa P) // declara o parâmetro como 
uma struct 
{ 
 printf("Idade: %d Peso: %f Altura: %f\n", P.Idade, 
P.Peso, P.Altura); 
} 
 
int main() 
{ 
 Pessoa Joao, P2; 
 Pessoa Povo[10]; 
 
 Joao.Idade = 15; 
 Joao.Peso = 60.5; 
 Joao.Altura = 1.75; 
 
 Povo[4].Idade = 23; 
 Povo[4].Peso = 75.3; 
 Povo[4].Altura = 1.89; 
 
 P2 = Povo[4]; 
 P2.Idade++; 
 
 // chama a função que recebe a struct como parâmetro 
 ImprimePessoa(Joao); 
 ImprimePessoa(Povo[4]); 
 ImprimePessoa(P2); 
 return 0; 
} 
 
Alocação Estática 
Na alocação estática de memória, os tipos de dados têm tamanho predefinido. Neste 
caso, o compilador vai alocar de forma automática o espaço de memória necessário. 
Sendo assim, dizemos que a alocação estática é feita em tempo de compilação. Este 
tipo de alocação tende a desperdiçar recursos, já que nem sempre é possível 
determinar previamente qual é o espaço necessário para armazenar as informações. 
Quando não se conhece o espaço total necessário, a tendência é o programador 
exagerar pois é melhor superdimensionar do que faltar espaço. 
Alocação Dinâmica 
Na alocação dinâmica podemos alocar espaços durante a execução de um programa, 
ou seja, a alocação dinâmica é feita em tempo de execução. Isto é bem interessante do 
ponto de vista do programador, pois permite que o espaço em memória seja alocado 
apenas quando necessário. Além disso, a alocação dinâmica permite aumentar ou até 
diminuir a quantidade de memória alocada. 
sizeof 
A função sizeof determina o número de bytes para um determinado tipo de dados. 
É interessante notar que o número de bytes reservados pode variar de acordo com o 
compilador utilizado. 
Exemplo: 
x = sizeof(int); //retorna 4 no gcc 
malloc 
A função malloc aloca um espaço de memória e retorna um ponteiro do tipo void para 
o início do espaço de memória alocado. 
free 
A função free libera o espaço de memória alocado. 
Exemplo: Vetor Dinâmico 
Quando um programador define tipo e o número de elementos um vetor ele está 
utilizando alocação estática. 
Uma alternativa interessante é declarar um vetor como ponteiro, a fim de utilizar 
alocação dinâmica. Para tanto devemos usar a função malloc. Porém, esta função 
necessita saber a quantidade de bytes que devem ser reservados. Para fazer esse cálculo 
usamos o comando sizeof. 
 
#include <stdio.h> 
#include <stdlib.h> //necessário para usar as funções malloc() e free() 
#include <conio.h> 
 
int main(void) 
{ 
 float *v; //definindo o ponteiro v 
 int i, num_componentes; 
 
 printf("Informe o numero de componentes do vetor\n"); 
 scanf("%d", &num_componentes); 
 
 /* ------------- Alocando dinamicamente o espaço necessário ------------- 
 
 1 - Calcular o número de bytes necessários 
 primeiramente multiplicamos o número de componentes do vetor pela 
 quantidade de bytes que é dada pelo comando sizeof, 
 portanto temos: 
 num_componentes * sizeof(float) 
 
 2 - Reservar a quantidade de memória 
 usamos malloc para reservar essa quantidade de memória, 
 então temos: 
 malloc(num_componentes * sizeof(float)) 
 
 3 - Converter o ponteiro para o tipo de dados desejado 
 como a função malloc retorna um ponteiro do tipo void, 
 precisamos converter esse ponteiro para o tipo da nossavariável, no caso f
loat, 
 por isso usamos o comando de conversão explicita: 
 (float *) 
 
 4 - juntando tudo e atribuindo em v temos o comando abaixo: */ 
 
 v = (float *) malloc(num_componentes * sizeof(float)); 
 
 //Armazenando os dados em um vetor 
 for (i = 0; i < num_componentes; i++) 
 { 
 printf("\nDigite o valor para a posicao %d do vetor: ", i+1); 
 scanf("%f",&v[i]); 
 } 
 
 // ------ Percorrendo o vetor e imprimindo os valores ---------- 
 printf("\n*********** Valores do vetor dinamico ************\n\n"); 
 
 for (i = 0;i < num_componentes; i++) 
 { 
 printf("%.2f\n",v[i]); 
 } 
 
 //liberando o espaço de memória alocado 
 free(v); 
 
 getch(); 
 return 0; 
} 
 
Exemplo de execução de alocação dinâmica de memória em C 
Alocação Dinâmica de Matriz em C 
Para o exemplo a seguir vamos fazer a leitura dos valores da matriz usando um arquivo 
texto, portanto será necessário criar o arquivo denominado ArqMatrizes.txt com os 
valores conforme a figura a seguir: 
 
Esse arquivo é composto pelas dimensões das matrizes: 3 6, ou seja, 3 linhas e 6 colunas, 
e também pelos valores das duas matrizes com dimensão 3 x 6. 
No código a seguir vamos alocar dinamicamente duas matrizes 3 X 6 e fazer a leitura dos 
valores do arquivo texto. 
Em seguida vamos alocar dinamicamente uma terceira matriz que vai conter a soma dos 
valores das outras duas matrizes. 
#include <stdio.h> 
#include <stdlib.h> //necessário para usar as funções malloc() e free() 
#include <stdlib.h> 
 
http://linguagemc.com.br/wp-content/uploads/2012/09/ArqMatrizes.png
int main(void) 
{ 
 int i,j,n_linhas,n_colunas; 
 
 //matrizes dinâmicas de duas dimensões portanto vamos necessitar um ponteir
o para a linha 
 //e outro ponteiro apontando para coluna 
 
 int **matriz1,**matriz2,**matriz_soma; 
 FILE *ptrArq; 
 
 //Abrindo o arquivo 
 ptrArq = fopen("ArqMatrizes.txt", "r"); 
 
 //Verificando se a abertura do arquivo foi bem sucedida 
 if (ptrArq == NULL) 
 { 
 printf("Erro ao abrir o arquivo!\n"); 
 printf("Saindo do programa...\n"); 
 system("pause"); 
 exit(1);//abortando o programa 
 } 
 
 // Leitura das dimensões da matriz a partir dos valores do arquivo 
 fscanf(ptrArq,"%d %d",&n_linhas,&n_colunas); 
 
 // Alocar a memória necessária para as matrizes 
 //----------------- Alocando a matriz1 --------------- 
 
 // alocar a quantidade de linhas 
 matriz1 = (int **)calloc(n_linhas,sizeof(int *)); 
 for (i = 0; i < n_linhas; i++) 
 { 
 // alocar a quantidade de colunas de cada linha 
 matriz1[i] = (int *)calloc(n_colunas,sizeof(int)); 
 } 
 
 //----------------- Alocando a matriz2 --------------- 
 matriz2 = (int **)calloc(n_linhas,sizeof(int *)); 
 
 for (i = 0; i < n_linhas; i++) 
 { 
 matriz2[i] = (int *)calloc(n_colunas,sizeof(int)); 
 } 
 
 
 // ------- Ler os valores para as matrizes a partir do arquivo texto ------ 
 for (i = 0; i < n_linhas; i++) 
 { 
 for (j = 0; j < n_colunas; j++) 
 { 
 fscanf(ptrArq,"%d",&matriz1[i][j]);//ler um inteiro do arquivo e armaze
nar na matriz1 
 } 
 } 
 
 
 for (i = 0; i < n_linhas; i++) 
 { 
 for (j = 0; j < n_colunas; j++) 
 { 
 fscanf(ptrArq,"%d",&matriz2[i][j]);//ler um inteiro do arquivo e armaze
nar na matriz2 
 } 
 } 
 
 fclose(ptrArq);//Fechar o arquivo 
 
 // --------------- Mostrar as matrizes lidas --------------------- 
 printf("Matrizes lidas do arquivo:\n"); 
 for (i = 0; i < n_linhas; i++) 
 { 
 for (j = 0; j < n_colunas; j++) 
 { 
 printf("%2d ",matriz1[i][j]); 
 } 
 
 printf(" "); //Espaçamento entre as duas matrizes 
 
 for (j = 0; j < n_colunas; j++) 
 { 
 printf("%2d ",matriz2[i][j]); 
 } 
 printf("\n"); 
 } 
 
 // Alocar memoria para matriz soma 
 matriz_soma = (int **)calloc(n_linhas,sizeof(int *)); 
 
 for (i = 0; i < n_linhas; i++) 
 { 
 matriz_soma[i] = (int *)calloc(n_colunas,sizeof(int)); 
 } 
 
 
 // Calcular matriz soma 
 for (i = 0; i < n_linhas; i++) 
 { 
 for (j = 0; j < n_colunas; j++) 
 { 
 matriz_soma[i][j] = matriz1[i][j] + matriz2[i][j]; 
 } 
 } 
 
 // Mostrar matriz soma 
 printf("\nMatriz soma:\n"); 
 for (i = 0; i < n_linhas; i++) 
 { 
 for (j = 0; j < n_colunas; j++) 
 { 
 printf("%3d ",matriz_soma[i][j]); 
 } 
 printf("\n"); 
 } 
 
 //liberando a memória da matriz1 
 //para matrizes a liberação da memória ocorre na ordem inversa da alocação 
 for (i=0; i < n_linhas; i++) 
 { 
 free (matriz1[i]) ; 
 } 
 free (matriz1) ; 
 
 //liberando a memória da matriz2 
 for (i=0; i < n_linhas; i++) 
 free (matriz2[i]) ; 
 free (matriz2) ; 
 
 //liberando a memória da matriz_soma 
 for (i=0; i < n_linhas; i++) 
 free (matriz_soma[i]) ; 
 free (matriz_soma); 
 
 printf("\n"); 
 system("pause"); 
 return 0; 
} 
Uma aplicação de Struct: as listas simplesmente encadeadas 
Várias estruturas de dados complexas podem ser criadas utilizando simultaneamente 
Struct e ponteiros. Uma destas estruturas é a lista encadeada. Uma lista encadeada é 
uma sequência de Struct, que são os nós da lista, ligados entre si através de ponteiros. 
Esta sequência pode ser acessada através de um ponteiro para o primeiro nó, que é a 
cabeça da lista. Cada nó contém um ponteiro que aponta para a Struct que é a sua 
sucessora na lista. O ponteiro da última Struct da lista aponta para NULL, indicando que 
se chegou ao final da lista. Esta estrutura de dados é criada dinamicamente na memória 
(utiliza-se malloc () e free ()), de modo que se torna simples introduzir nós nela, retirar 
nós, ordenar os nós, etc. Não vamos entrar em detalhes sobre todos os algoritmos que 
poder amos criar em uma lista encadeada, pois isto geralmente e feito em cursos de 
algoritmos e estruturas de dados, não se incluindo no escopo deste curso. Aqui, veremos 
somente formas de se criar uma lista encadeada em C e também maneiras simples de 
percorrer esta lista. 
Supondo que queiramos criar uma lista encadeada para armazenar os produtos 
disponíveis em uma loja. Poder amos criar um n desta lista usando a seguinte Struct: 
struct Produto { 
 int codigo; /* Codigo do produto */ 
 double preco; /* Preco do produto */ 
 struct Produto *proximo; /* Proximo elemento 
da lista encadeada de Produtos */ 
}; 
Note que esta Struct possui, além dos campos de dados código e preço, um campo 
adicional que é um ponteiro para uma Struct do tipo Produto. É este campo que ser 
utilizado para apontar para o próximo nó da lista encadeada. O programa a seguir faz 
uso desta Struct, através de um novo tipo criado por um Typedef, para criar uma lista 
de produtos de uma loja: 
#include <stdio.h> 
#include <stdlib.h> 
 
/* Estrutura que ser usada para criar os nós da lista */ 
 
typedef struct tipo_produto { 
 int codigo; /* Codigo do produto */ 
 double preco; /* Preco do produto */ 
 struct tipo_produto *proximo; /* Proximo elemento da lista 
encadeada de Produtos */ 
} TProduto; 
 
/* Prototipos das funcoes para inserir e listar produtos */ 
 
void inserir(TProduto **cabeca); 
void listar (TProduto *cabeca); 
 
int main() 
{ 
 TProduto *cabeca = NULL; /* Ponteiro para a cabeca da 
lista */ 
 TProduto *noatual; /* Ponteiro a ser usado para 
percorrer a lista no momento de desalocar seus elementos*/ 
 char q; /* Caractere para receber a 
opcao do usuario */ 
 do { 
 printf("\n\nOpcoes: \nI -> para inserir novo produto;\nL 
-> para listar os produtos; \nS -> para sair \n:"); 
 scanf("%c", &q); /* Le a opcaodo usuario */ 
 switch(q) { 
 case 'i': case 'I': inserir(&cabeca); break; 
 case 'l': case 'L': listar(cabeca); break; 
 case 's': case 'S': break; 
 default: printf("\n\n Opcao nao válida"); 
 } 
 fflush(stdin); /* Limpa o buffer de entrada */ 
 } while ((q != 's') && (q != 'S') ); 
 
/* Desaloca a memória alocada para os elementos da lista */ 
 
 noatual = cabeca; 
 while (noatual != NULL) 
 { 
 cabeca = noatual->proximo; 
 free(noatual); 
 noatual = cabeca; 
 } 
} 
/* Lista todos os elementos presentes na lista encadeada */ 
 
void listar (TProduto *noatual) 
{ 
 int i=0; 
 while( noatual != NULL) /* Enquanto nao chega no fim da 
lista */ 
 { 
 i++; 
 printf("\n\nProduto número %d\nCodigo: %d 
\nPreco:R$%.2lf", i, noatual->codigo, noatual->preco); 
 noatual = noatual->proximo; /* Faz noatual apontar 
para o proximo no */ 
 } 
} 
/* Funcao para inserir um novo no, ao final da lista */ 
 
void inserir (TProduto **cabeca) 
{ 
 TProduto *noatual, *novono; 
 int cod; 
 double preco; 
 printf("\n Codigo do novo produto: "); 
 scanf("%d", &cod); 
 printf("\n Preco do produto:R$"); 
 scanf("%lf", &preco); 
 if (*cabeca == NULL) /* Se ainda nao existe nenhum produto 
na lista */ 
 { 
/* cria o no cabeca */ 
 *cabeca = (TProduto *) malloc(sizeof(TProduto)); 
 (*cabeca)->codigo = cod; 
 (*cabeca)->preco = preco; 
 (*cabeca)->proximo = NULL; 
 } 
 else 
 { 
/* Se ja existem elementos na lista, deve percorre-la até' o seu 
final e inserir o novo elemento */ 
 noatual = *cabeca; 
 while(noatual->proximo != NULL) 
 noatual = noatual->proximo; /* Ao final do while, 
noatual aponta para o ultimo no */ 
 novono = (TProduto *) malloc(sizeof(TProduto));/* Aloca 
memória para o novo no */ 
 novono->codigo = cod; 
 novono->preco = preco; 
 novono->proximo = NULL; 
 noatual->proximo = novono; /* Faz o ultimo no apontar 
para o novo no */ 
 } 
} 
 
 
É interessante notar que, no programa anterior não existe limite para o número de 
produtos que se vai armazenar na lista. Toda vez que for necessário criar um novo 
produto, memória para ele será alocada e ele será criado no final da lista. Note que a 
função inserir recebe o endereço do ponteiro cabeça da lista. Qual a razão disto? A razão 
é que o endereço para o qual a cabeça da lista aponta poderá ser modificado caso se 
esteja inserindo o primeiro elemento na lista. Tente entender todos os passos deste 
programa, pois ele possui várias das características presentes em programas que 
manipulam listas encadeadas. Também é importante notar que várias outras estruturas 
de dados complexas podem ser criadas com Struct contendo ponteiros que apontam 
para outras Struct. 
Recursividade em C 
Em uma função recursiva, a cada chamada é criada na memória uma nova ocorrência 
da função com comandos e variáveis “isolados” das ocorrências anteriores. 
A função é executada até que todas as ocorrências tenham sido resolvidas. 
Porém um problema que surge ao usar a recursividade é como fazê-la parar. Caso o 
programador não tenha cuidado é fácil cair num loop infinito recursivo o qual pode 
inclusive esgotar a memória… 
Toda recursividade é composta por um caso base e pelas chamadas recursivas,. 
Caso base: é o caso mais simples. É usada uma condição em que se resolve o problema 
com facilidade. 
Chamadas Recursivas: procuram simplificar o problema de tal forma que convergem 
para o caso base. 
Vantagens da recursividade 
• Torna a escrita do código mais simples e elegante, tornando-o fácil de entender 
e de manter. 
Desvantagens da recursividade 
• Quando o loop recursivo é muito grande é consumida muita memória nas 
chamadas a diversos níveis de recursão, pois cada chamada recursiva aloca 
memória para os parâmetros, variáveis locais e de controle. 
• Em muitos casos uma solução iterativa gasta menos memória, e torna-se mais 
eficiente em termos de performance do que usar recursão. 
Exemplo clássico de recursividade: fatorial 
//Cálculo de fatorial com função recursiva 
#include <stdio.h> 
#include <conio.h> 
 
//protótipo da função fatorial 
double fatorial(int n); 
 
int main(void) 
{ 
 int numero; 
 double f; 
 
 printf("Digite o numero que deseja calcular o fatorial: "); 
 scanf("%d",&numero); 
 
 //chamada da função fatorial 
 f = fatorial(numero); 
 
 printf("Fatorial de %d = %.0lf",numero,f); 
 
 getch(); 
 return 0; 
} 
 
//Função recursiva que calcula o fatorial 
//de um numero inteiro n 
double fatorial(int n) 
{ 
 
 double vfat; 
 
 if ( n <= 1 ) 
 //Caso base: fatorial de n <= 1 retorna 1 
 return (1); 
 else 
 { 
 //Chamada recursiva 
 vfat = n * fatorial(n - 1); 
 return (vfat); 
 } 
} 
 
 
 
 
Tela de Execução 
 
Tela de execução clássico de recursividade fatorial 
Explicação do código 
No programa acima, se o número n for menor ou igual a 1 o valor 1 será retornado e a 
função encerrada, sem necessidade de chamadas recursivas. Caso contrário dá-se 
início a chamadas recursivas até cair no caso mais simples que é resolvido e assim, as 
chamadas retornam valores de forma a solucionar o cálculo. 
Veja a figura a seguir que representa as chamadas recursivas para o cálculo de 5! 
 
Cálculo recursivo 5! 
 
http://linguagemc.com.br/wp-content/uploads/2012/06/teladeexecucaoclassicoderecursividade.png
http://linguagemc.com.br/wp-content/uploads/2012/06/calculorecursivo53.png
 Lista Circular 
/* 
 Estrutura nó 
*/ 
typedef struct no{ 
 int valor; 
 struct no *proximo; 
}No; 
 
// estrutura lista 
typedef struct{ 
 No *inicio; 
 No *fim; 
 int tam; 
}Lista; 
 
 
/* 
 procedimento para inserir no início 
*/ 
void inserir_no_inicio(Lista *lista, int num){ 
 No *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 // o próximo aponta para o início da lista 
 novo->proximo = lista->inicio; 
 // novo se torna o início da lista 
 lista->inicio = novo; 
 // se fim for nulo (lista vazia), fim aponta para 
novo nó 
 if(lista->fim == NULL) 
 lista->fim = novo; 
 // fim aponta para início 
 lista->fim->proximo = lista->inicio; 
 lista->tam++; 
 
 
 
 
 
 
 
 
 
 
typedef struct no{ 
 int valor; 
 struct no *proximo; 
}No; 
 
typedef struct{ 
 No *inicio; 
 No *fim; 
 int tam; 
}Lista; 
 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
 
void criar_lista(Lista *lista){ 
 lista->inicio = NULL; 
 lista->fim = NULL; 
 lista->tam = 0; 
} 
 
// procedimento para inserir no início 
void inserir_no_inicio(Lista *lista, int num){ 
 No *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 novo->proximo = lista->inicio; 
 lista->inicio = novo; 
 if(lista->fim == NULL) 
 lista->fim = novo; 
 lista->fim->proximo = lista->inicio; 
 lista->tam++; 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
 
// procedimento para inserir no fim 
void inserir_no_fim(Lista *lista, int num){ 
 No *aux, *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 
 // é o primeiro? 
 if(lista->inicio == NULL){ 
 lista->inicio = novo; 
 lista->fim = novo; 
 lista->fim->proximo = lista->inicio; 
 } 
 else{ 
 lista->fim->proximo = novo; 
 lista->fim = novo; 
 // as duas linhas a seguir são sinônimas. Escolha a que 
achar mais fácil compreender 
 //lista->fim->proximo = lista->inicio;novo->proximo = lista->inicio; 
 } 
 lista->tam++; 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
// procedimento para inserir ordenado 
void inserir_ordenado(Lista *lista, int num){ 
 No *aux, *novo = malloc(sizeof(No)); 
 if(novo){ 
 novo->valor = num; 
 if(lista->inicio == NULL){ 
 inserir_no_inicio(lista, num); 
 } 
 else if(novo->valor < lista->inicio->valor){ 
 inserir_no_inicio(lista, num); 
 } 
 else{ 
 aux = lista->inicio; 
 while(aux->proximo != lista->inicio && novo->valor > aux-
>proximo->valor) 
 aux = aux->proximo; 
 if(aux->proximo == lista->inicio) 
 inserir_no_fim(lista, num); 
 else{ 
 novo->proximo = aux->proximo; 
 aux->proximo = novo; 
 lista->tam++; 
 } 
 } 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
// função para remover um nó 
No* remover(Lista *lista, int num){ 
 No *aux, *remover = NULL; 
 
 if(lista->inicio){ 
 if(lista->inicio == lista->fim && lista->inicio->valor == num){ 
 remover = lista->inicio; 
 lista->inicio = NULL; 
 lista->fim = NULL; 
 lista->tam--; 
 } 
 else if(lista->inicio->valor == num){ 
 remover = lista->inicio; 
 lista->inicio = remover->proximo; 
 lista->fim->proximo = lista->inicio; 
 lista->tam--; 
 } 
 else{ 
 aux = lista->inicio; 
 while(aux->proximo != lista->inicio && aux->proximo->valor 
!= num) 
 aux = aux->proximo; 
 if(aux->proximo->valor == num){ 
 if(lista->fim == aux->proximo){ 
 remover = aux->proximo; 
 aux->proximo = remover->proximo; 
 lista->fim = aux; 
 } 
 else{ 
 remover = aux->proximo; 
 aux->proximo = remover->proximo; 
 } 
 lista->tam--; 
 } 
 } 
 } 
 
 return remover; 
} 
// função para buscar um valor 
No* buscar(Lista *lista, int num){ 
 No *aux = lista->inicio; 
 
 if(aux){ 
 do{ 
 if(aux->valor == num) 
 return aux; 
 aux = aux->proximo; 
 }while(aux != lista->inicio); 
 } 
 return NULL; 
} 
// procedimento para imprimir a lista circular 
void imprimir(Lista lista){ 
 No *no = lista.inicio; 
 printf("\n\tLista tam %d: ", lista.tam); 
 if(no){ 
 do{ 
 printf("%d ", no->valor); 
 no = no->proximo; 
 }while(no != lista.inicio); 
 printf("\nInicio: %d\n", no->valor); 
 } 
 printf("\n\n"); 
} 
 
int main(){ 
 
 int opcao, valor, anterior; 
 //No *lista = NULL; 
 Lista lista; 
 No *removido; 
 
 criar_lista(&lista); 
 
 do{ 
 printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - 
InserirO\n\t4 - Remover\n\t5 - Imprimir\n\t6 - Buscar\n"); 
 scanf("%d", &opcao); 
 
 switch(opcao){ 
 case 1: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 inserir_no_inicio(&lista, valor); 
 break; 
 case 2: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 inserir_no_fim(&lista, valor); 
 break; 
 case 3: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 inserir_ordenado(&lista, valor); 
 break; 
 case 4: 
 printf("Digite um valor a ser removido: "); 
 scanf("%d", &valor); 
 removido = remover(&lista, valor); 
 if(removido){ 
 printf("Elemento removido: %d\n", removido->valor); 
 free(removido); 
 } 
 else 
 printf("elemento inesistente!\n"); 
 break; 
 case 5: 
 imprimir(lista); 
 break; 
 case 6: 
 printf("Digite um valor a ser buscado: "); 
 scanf("%d", &valor); 
 removido = buscar(&lista, valor); 
 if(removido) 
 printf("Valor encontrado: %d\n", removido->valor); 
 else 
 printf("Valor nao encontrado!\n"); 
 break; 
 default: 
 if(opcao != 0) 
 printf("Opcao invalida!\n"); 
 } 
 
 }while(opcao != 0); 
 
 return 0; 
} 
 
 
Lista duplamente encadeada 
 
 
 
 
 
/* 
 Estrutura nó para a lista duplamente encadeada 
*/ 
typedef struct no{ 
 int valor; 
 struct no *proximo; 
 struct no *anterior; 
}No; 
 
 
 
 
 
/* 
 procedimento para inserir um novo nó no início da lista 
*/ 
void inserir_no_inicio(No **lista, int num){ 
 No *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 // próximo do novo nó aponta para o início da lista 
 novo->proximo = *lista; 
 // o anterior é nulo pois é o primeiro nó 
 novo->anterior = NULL; 
 // se a lista não estiver vazia, o anterior do primeiro nó 
aponta para o novo nó 
 if(*lista) 
 (*lista)->anterior = novo; 
 // o novo nó passa a ser o início da lista (o primeiro nó da 
lista) 
 *lista = novo; 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
typedef struct no{ 
 int valor; 
 struct no *proximo; 
 struct no *anterior; 
}No; 
 
// procedimento para inserir no início 
void inserir_no_inicio(No **lista, int num){ 
 No *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 novo->proximo = *lista; 
 novo->anterior = NULL; 
 if(*lista) 
 (*lista)->anterior = novo; 
 *lista = novo; 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
 
// procedimento para inserir no fim 
void inserir_no_fim(No **lista, int num){ 
 No *aux, *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 novo->proximo = NULL; 
 
 // é o primeiro? 
 if(*lista == NULL){ 
 *lista = novo; 
 novo->anterior = NULL; 
 } 
 else{ 
 aux = *lista; 
 while(aux->proximo) 
 aux = aux->proximo; 
 aux->proximo = novo; 
 novo->anterior = aux; 
 } 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
// procedimento para inserir no meio 
void inserir_no_meio(No **lista, int num, int ant){ 
 No *aux, *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 // é o primeiro? 
 if(*lista == NULL){ 
 novo->proximo = NULL; 
 novo->anterior = NULL; 
 *lista = novo; 
 } 
 else{ 
 aux = *lista; 
 while(aux->valor != ant && aux->proximo) 
 aux = aux->proximo; 
 novo->proximo = aux->proximo; 
 if(aux->proximo) 
 aux->proximo->anterior = novo; 
 novo->anterior = aux; 
 aux->proximo = novo; 
 } 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
 
void inserir_ordenado(No **lista, int num){ 
 No *aux, *novo = malloc(sizeof(No)); 
 
 if(novo){ 
 novo->valor = num; 
 // a lista está vazia? 
 if(*lista == NULL){ 
 novo->proximo = NULL; 
 novo->anterior = NULL; 
 *lista = novo; 
 } // é o menor? 
 else if(novo->valor < (*lista)->valor){novo->proximo = *lista; 
 (*lista)->anterior = novo; 
 *lista = novo; 
 } 
 else{ 
 aux = *lista; 
 while(aux->proximo && novo->valor > aux->proximo->valor) 
 aux = aux->proximo; 
 novo->proximo = aux->proximo; 
 if(aux->proximo) 
 aux->proximo->anterior = novo; 
 novo->anterior = aux; 
 aux->proximo = novo; 
 } 
 } 
 else 
 printf("Erro ao alocar memoria!\n"); 
} 
 
No* remover(No **lista, int num){ 
 No *aux, *remover = NULL; 
 
 if(*lista){ 
 if((*lista)->valor == num){ 
 remover = *lista; 
 *lista = remover->proximo; 
 if(*lista) 
 (*lista)->anterior = NULL; 
 } 
 else{ 
 aux = *lista; 
 while(aux->proximo && aux->proximo->valor != num) 
 aux = aux->proximo; 
 if(aux->proximo){ 
 remover = aux->proximo; 
 aux->proximo = remover->proximo; 
 if(aux->proximo) 
 aux->proximo->anterior = aux; 
 } 
 } 
 } 
 return remover; 
} 
 
No* buscar(No **lista, int num){ 
 No *aux, *no = NULL; 
 
 aux = *lista; 
 while(aux && aux->valor != num) 
 aux = aux->proximo; 
 if(aux) 
 no = aux; 
 return no; 
} 
 
void imprimir(No *no){ 
 printf("\n\tLista: "); 
 while(no){ 
 printf("%d ", no->valor); 
 no = no->proximo; 
 } 
 printf("\n\n"); 
} 
// retorna ponteiro para o último nó da lista 
No* ultimo(No **lista){ 
 No *aux = *lista; 
 while(aux->proximo) 
 aux = aux->proximo; 
 return aux; 
} 
 
// imprime a lista do fim para o início 
// recebe um ponteiro para o último nó da lista 
void imprimirContrario(No *no){ 
 printf("\n\tLista: "); 
 while(no){ 
 printf("%d ", no->valor); 
 no = no->anterior; 
 } 
 printf("\n\n"); 
} 
 
int main(){ 
 
 int opcao, valor, anterior; 
 No *removido, *lista = NULL; 
 
 do{ 
 printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - 
InserirM\n\t4 - InserirO\n\t5 - Remover\n\t6 - Imprimir\n\t7 - 
Buscar\n\t8 - ImprimirC\n"); 
 scanf("%d", &opcao); 
 
 switch(opcao){ 
 case 1: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 inserir_no_inicio(&lista, valor); 
 break; 
 case 2: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 inserir_no_fim(&lista, valor); 
 break; 
 case 3: 
 printf("Digite um valor e o valor de referencia: "); 
 scanf("%d%d", &valor, &anterior); 
 inserir_no_meio(&lista, valor, anterior); 
 break; 
 case 4: 
 printf("Digite um valor: "); 
 scanf("%d", &valor); 
 inserir_ordenado(&lista, valor); 
 break; 
 case 5: 
 printf("Digite um valor a ser removido: "); 
 scanf("%d", &valor); 
 removido = remover(&lista, valor); 
 if(removido){ 
 printf("Elemento a ser removido: %d\n", removido-
>valor); 
 free(removido); 
 } 
 else 
 printf("Elemento inexistente!\n"); 
 break; 
 case 6: 
 imprimir(lista); 
 break; 
 case 7: 
 printf("Digite um valor a ser buscado: "); 
 scanf("%d", &valor); 
 removido = buscar(&lista, valor); 
 if(removido) 
 printf("Elemento encontrado: %d\n", removido->valor); 
 else 
 printf("Elemento nao encontrado!\n"); 
 break; 
 case 8: 
 imprimirContrario(ultimo(&lista)); 
 break; 
 default: 
 if(opcao != 0) 
 printf("Opcao invalida!\n"); 
 } 
 
 }while(opcao != 0); 
 
 return 0; 
} 
 
 
Pilha 
#include <iostream> 
#define tamanho 5 
using namespace std; 
 
//define a estrutura que será a pilha 
//a estrutura armazena a indicação do topo da pilha e um vetor 
com os itens (valores) da pilha 
typedef struct{ 
 int topo = 0; 
 int item [tamanho] ; 
} PILHA; 
 
//retorna se a pilha está vazia ou não 
bool pilhaVazia(PILHA p){ 
 if(p.topo == 0) { 
 return true; 
 } else { 
 return false; 
 } 
} 
 
//retorna se a pilha está cheia ou não 
bool pilhaCheia(PILHA p) { 
 int tam = sizeof(p.item)/sizeof(int); //determina o 
tamanho do vetor 
 
 if (p.topo < tam) { 
 return false; 
 } else { 
 return true; 
 } 
} 
 
//adiciona valor na pilha 
void empilha(PILHA &p, int x){ 
 p.item[p.topo++]=x; 
} 
 
//remove valor da pilha 
int desempilha(PILHA &p){ 
 return (p.item[--p.topo]) ; 
} 
 
//mostra os valores armazenados na pilha 
void mostraPilha(PILHA p) { 
 cout << "Valores da pilha: "; 
 for (int i = 0; i < p.topo; i++) { 
 cout << p.item[i] << " "; 
 } 
 cout << "\n"; 
} 
 
//Código para testar a implementação. 
int main(){ 
 PILHA s; //criar a pilha 
 
 //Verificar que a pilha está vazia 
 if(pilhaVazia(s)) { 
 cout<<"A pilha está vazia."<<endl; 
 } else { 
 cout<<"A pilha não está vazia."<<endl; 
 } 
 
 //Empilha valor e verifica se a pilha está vazia 
 empilha(s,10); 
 if(pilhaVazia(s)) { 
 cout<<"A pilha está vazia."<<endl; 
 } else { 
 cout<<"A pilha não está vazia."<<endl; 
 } 
 
 //Empilhar 3 elementos 
 empilha(s,20); 
 empilha(s,30); 
 empilha(s,40); 
 
 //Mostra os valores da pilha 
 mostraPilha(s); 
 
 //Verifica que a pilha está cheia 
 if(pilhaCheia(s)) { 
 cout<<"A pilha está cheia."<<endl; 
 } else { 
 cout<<"A pilha não está cheia."<<endl; 
 } 
 
 //Empilha valor e verifica se a pilha está cheia 
 empilha(s,50); 
 mostraPilha(s); 
 if(pilhaCheia(s)) { 
 cout<<"A pilha está cheia."<<endl; 
 } else { 
 cout<<"A pilha não está cheia."<<endl; 
 } 
 
 //Desempilha e mostrar o valor desempilhado 
 cout<<"Valor desempilhado: "<< desempilha(s) <<endl; 
 
 mostraPilha(s); 
 
 return 0; 
} 
 
Filas: 
Listas, pilhas e filas são estruturas de dados, que nos permitem organizar e interagir com nossos dados 
e organizá-los de diferentes formas. Em C++ existem bibliotecas que nos permitem implementar esses 
tipos de estruturas, o que torna nosso trabalho mais simples do que se tivéssemos de criá-las 
manualmente. 
 Primeiro vamos falar sobre pilhas: 
#include <stack> 
#include <iostream> 
 
using namespace std; 
 
int main(){ 
 stack<int> pilha; 
 for(int i=0;i<10;i++){ 
 pilha.push(i); 
 } 
 cout << pilha.top() << endl; 
 pilha.pop(); 
 cout << pilha.top() << endl; 
 for(int i=0;i<9;i++){ 
 pilha.pop(); 
 if(pilha.empty()){ 
 cout << "Fiquei vazia na iteração: " << i+1 << endl; 
 } 
} 
 
 
 A biblioteca para se usar pilha em c++ é a "stack". Logo após declararmos nossa "stack", indicando 
qual tipo de dado colocaremos nela, com o nome pilha, temos um for e uma função chamada push 
(). A função push é a função que nos permite empilhar os nossos objetos em nossa pilha. Caso não 
saibam, uma pilha funciona seguindo o padrão FILO (First in Last out), que significa que o primeiro 
elemento a entrar é o último a sair, como se os elementos realmente estivessem empilhados um em 
cima do outro. 
 Logo a seguir temos a função top (), que nos retorna o elemento do topo sem removê-lo. Já a função 
pop () remove o elemento no topo da lista, porém não retorna o seu valor. Na primeira vez que 
printamos no console o top (), teremos o valor 9. Depoisde darmos o pop e printarmos o top de novo, 
teremos o valor 8. No último for temos a função empty (), que retornará true caso a pilha esteja vazia. 
Ou seja, só entraremos naquele if na última iteração e o print que aparecerá será "Fiquei vazia na 
iteração 8". 
 Em seguida temos filas. Filas seguem o padrão FIFO (First In First Out), ou seja, o primeiro a chegar 
é o primeiro a sair. 
include <iostream> 
#include <queue> 
 
using namespace std; 
 
int main(){ 
 queue<int> fila; 
 for(int i=0;i<10;i++){ 
 fila.push(i); 
 } 
 cout << fila.front() << endl; 
 cout << fila.pop() << endl; 
 cout << fila.front() << endl; 
 
 for(int i=0;i<9;i++){ 
 fila.pop(); 
 if(fila.empty()){ 
 cout << "Vazio na iteração " << i+1 << endl; 
 } 
 } 
} 
 
 
 Como podemos ver em fila temos funções semelhantes às de pilha. As diferenças são poucas, 
como o include, que deixa de ser "stack" para "queue" e ao invés de top () em fila temos front 
(). A principal diferença é que na pilha ao usarmos top () veríamos o último elemento que foi 
adicionado a pilha (no exemplo acima o 9), já na fila ao usarmos front () vemos o primeiro 
elemento (Nesse caso o 0) e ao usarmos pop () o nosso próximo elemento será o inteiro de 
valor 1. 
 Já a lista é, de certa forma, uma estrutura mais completa, porque podemos utilizá-la de 
diversas formas, incluindo no estilo de pilha e fila. Em uma lista podemos adicionar um 
elemento tanto no início quanto no fim da lista, assim como podemos escolher se vamos retirar 
o elemento do início ou do fim também! Porém em uma lista podemos inserir os elementos 
onde queremos assim como remover o elemento que quisermos. Vamos ver: 
#include <iostream> 
#include <list> 
 
using namespace std; 
 
int main(){ 
 list<int> lista; 
 list<int>::iterator it; 
 for(int i=0;i<5;i++){ 
 lista.push_back(i); 
 } 
 for(int i=5;i<10;i++){ 
 lista.push_front(i); 
 } 
 // Conteudo da lista: 9 8 7 6 5 0 1 2 3 4 
 cout << lista.front() << endl; 
 //printa 9 na tela 
 cout << lista.back() << endl; 
 // printa 4 na tela 
 cout << lista.size() << endl; 
 //printa o tamanho da lista na tela, que é igual a 10 
 
 for(it = lista.begin(); it!=lista.end();it++){ 
 //printa os numeros pares começando do inicio da lista 
 if(*it %2 == 0){ 
 cout << *it << endl; 
 } 
 } 
 it--; 
 // adiciona dois 11 antes do 4 na lista 
 lista.insert(it,2,11); 
 for(it = lista.begin(); it!=lista.end();it++){ 
 //printa os numeros pares 
 cout << *it << " "; 
 } 
 cout << endl; 
 it--;//retira o 4 da lista 
lista.erase(it);// printa o 3 que agora é o novo ultimo elemento da listacout << 
lista.back() << endl; 
 // limpa a lista inteira 
 lista.clear(); 
 // printará 0 pois a lista está vazia 
 cout << lista.size() << endl; 
} 
 
 
Primeiro vamos começar com os comandos pusb_back () e push_front (). Eles respectivamente 
adicionam o elemento passado no final da lista e no início da lista (nos comentários temos os 
resultados dos prints). Em seguida checamos qual o nosso primeiro elemento e qual o nosso último 
respectivamente. Depois temos a função size () (que também existe para filas e pilhas) que nos retorna 
o tamanho da nossa lista. Agora temos a grande diferença de lista para os demais, em listas podemos 
iterar entre todos os elementos, assim como fazemos em um vetor. Porém para isso precisamos de um 
iterador, o nosso iterator it que nada mais é do que um ponteiro que aponta para elementos de listas 
que tenham o tipo int como dado. 
 os comandos begin() e end() retornam respectivamente um ponteiro para o início e para o fim da 
lista, a diferença é que o ponteiro do begin aponta realmente para o primeiro elemento da lista 
enquanto o end aponta para depois do último elemento. Depois que pritamos todos os numeros 
pares, usamos o it-- para voltarmos a apontar para o último elemento e usamos a função insert(). Essa 
função nos permite inserir elementos na posição anterior a que nosso iterador está apontando. O 
segundo parâmetro é opcional e serve para dizermos quantas cópias daquele elemento queremos 
inserir (O default é 1). Em seguida temos o erase(), que apaga o elemento que nosso iterador está 
apontando. Por fim temos a função clear(), que limpa nossa lista inteira!