Lista encadeada em C

maio 3, 2007 às 2:55 | Publicado em artigos, C, linux, programacao | 34 Comentários

Fazia alguns meses que estava parado com a programação em linguagem C e só “dedicado” (nunca consigo ficar full time em algo) a linguagem Python. Mas depois de ler o livro A Prática da Programação (obrigado Ruda Moura :)) me fez ter aquele pique novamente de praticar já que sempre fiz algumas coisas profissionais e por diversão com a linguagem.

Resolvi falar sobre lista encadeada em C poque alguns contatos no meu MSN sempre me perguntam sobre e também porque é muito utlizado em diversos algoritmos. Apesar de já ter alguns códigos prontos resolvi refazer dando ênfase nas sugestões do livro, que realmente recomendo já que fala sobre listas, árvores, hash, entre outros mais.

Chega de papo, Show me the Code!, o código abaixo implementa um exemplo de uma lista simples encadeada onde os dados não são ordenados e a forma que são armazenados é igual uma pilha, onde o último dado a entrar é o primeiro a sair, conhecido também como LIFO (Last In, First Out).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define BUFFER 64

/* Estrutura da lista declarada para armazenar nossos dados. */
typedef struct lista {
        char *nome;
        int idade;
        struct lista *proximo;
} Dados;

/* Prototipo das funcoes de manuseio dos dados. */
Dados *inicia_dados(char *nome, int idade);
Dados *insere_dados(Dados *dados, char *nome, int idade);
void exibe_dados(Dados *dados);
void busca_dados(Dados *dados, char *chave);
Dados *deleta_dados(Dados *dados);
int checa_vazio(Dados *dados);

/* Prototipo das funcoes do menu.*/
void insere(void);
void exibe(void);
void busca(void);
void deleta(void);

/* Inicializa a estrutura de dados principal. */
Dados *principal = NULL;

/* Cria a nova lista apontando o proximo no para NULL. */
Dados *inicia_dados(char *nome, int idade) {

        Dados *novo;

        novo = (Dados *)malloc(sizeof(Dados));
        novo->nome = (char *)malloc(strlen(nome)+1);
        strncpy(novo->nome, nome, strlen(nome)+1);
        novo->idade = idade;
        novo->proximo = NULL;

        return novo;
}

/* Como a lista nao esta mais vazia, apontamos o proximo no para lista anterior. */
Dados *insere_dados(Dados *dados, char *nome, int idade) {

        Dados *novo;

        novo = (Dados *)malloc(sizeof(Dados));
        novo->nome = (char *)malloc(strlen(nome)+1);
        strncpy(novo->nome, nome, strlen(nome)+1);
        novo->idade = idade;
        novo->proximo = dados;

        return novo;
}

/* Percorre todos os campos da lista e imprime ate o ponteiro proximo chegar em NULL. */
void exibe_dados(Dados *dados) {

        fprintf(stdout, "Cadastro:\\n\\n");

        fprintf(stdout, "------------------------\\n");

        for (; dados != NULL; dados = dados->proximo) {
                fprintf(stdout, "Nome: %s\\n", dados->nome);
                fprintf(stdout, "Idade: %d\\n", dados->idade);
                fprintf(stdout, "------------------------\\n");
        }

        getchar();
}

/* Percorre cada ponta comparando o nome com a chave. */
void busca_dados(Dados *dados, char *chave) {

        int achou = 0;

        fprintf(stdout, "Cadastro:\\n\\n");
        for (; dados != NULL; dados = dados->proximo) {
                if (strcmp(chave, dados->nome) == 0) {

                        fprintf(stdout, "------------------------\\n");
                        fprintf(stdout, "Nome: %s\\n", dados->nome);
                        fprintf(stdout, "Idade: %d\\n", dados->idade);
                        fprintf(stdout, "------------------------\\n");
                        achou++;
                }
        }

        if (achou == 0)
                fprintf(stdout, "Nenhum resultado encontrado.\\n");
        else
                fprintf(stdout, "Foram encontrados %d registros.\\n", achou);

        sleep(1);
}

/* Deleta o ultimo registro inserido. */
Dados *deleta_dados(Dados *dados) {

        Dados *novo;

        novo = dados->proximo;

        free(dados->nome);
        free(dados);

        fprintf(stdout, "O ultimo registro inserido foi deletado com sucesso.\\n");
        sleep(1);

        return novo;
}

/* Apena checa se a lista e NULL ou nao. */
int checa_vazio(Dados *dados) {

        if (dados == NULL) {
                fprintf(stdout, "Lista vazia!\\n");
                sleep(1);
                return 1;
        } else
                return 0;
}

/* Obtem os dados necessarios para chamar as funcoes de manuseio de dados. */
void insere(void) {

        char *nome;
        int idade;

        nome = (char *)malloc(BUFFER);

        fprintf(stdout, "\\n\\nDigite o Nome: \\n----> ");
        scanf("%s", nome);
        fprintf(stdout, "\\n");

        fprintf(stdout, "Digite a Idade: \\n----> ");
        scanf("%d", &idade);
        fprintf(stdout, "\\n");

        if (principal == NULL) 
                principal = inicia_dados(nome, idade);
        else 
                principal = insere_dados(principal, nome, idade);
}

void exibe(void) {

        if (!checa_vazio(principal))
                exibe_dados(principal);
}

void busca(void) {

        char *chave;

        if (!checa_vazio(principal)) {

                chave = (char *)malloc(BUFFER);

                fprintf(stdout, "Digite o nome para buscar: \\n--> ");
                scanf("%s", chave);

                busca_dados(principal, chave);
        }
}

void deleta(void) {

        if (!checa_vazio(principal))
                principal = deleta_dados(principal);
}

int main(void) {

        char escolha;

        do {
                system("/usr/bin/clear"); /* Nao lembro de nada melhor! 😛 */
                fprintf(stdout, "\\n\\t\\tCadastro de Pessoas\\n\\n");
                fprintf(stdout, "Escolha uma opcao: \\n");
                fprintf(stdout, "1 - Insere Dados\\n");
                fprintf(stdout, "2 - Exibe Dados\\n");
                fprintf(stdout, "3 - Busca Dados\\n");
                fprintf(stdout, "4 - Deleta Dados\\n");
                fprintf(stdout, "5 - Sair\\n\\n");

                scanf("%c", &escolha);

                switch(escolha) {
                        case '1':
                                insere();
                                break;

                        case '2':
                                exibe();
                                break;

                        case '3':
                                busca();
                                break;

                        case '4':
                                deleta();
                                break;

                        case '5':
                                exit(0);
                                break;

                        default:
                                fprintf(stderr,"Digite uma opcao valida!\\n");
                                sleep(1);
                                break;
                }

                getchar(); /* E para impedir sujeira na entrada da escolha. Nao lembro de nada melhor tambem. 😛 */
        }

        while (escolha > 0); /* Loop Principal. */

        return 0;
}

Veja o uso de uma única lista (principal) que no decorrer das chamadas das funções de manuseio de dados, ela vai se alterando com cada ponteiro retornado, tornando mais fácil seu uso.

Não tenho muito que falar porque fiz esse código correndo em umas 2 horas (mas que levou 2 dias por causa de conversas paralelas no MSN, Gmail, entre outros! =P), inclusive nem fiz mais tratamentos devidos mas enfim, a idéia é quem tiver dúvidas, que pergunte nos comentários! Eu AMO responder dúvidas (inteligentes) e acredito que sempre tem alguma visto que a linguagem C em si é um tanto quanto confusa pra maioria (principalmente pra mim!) mas que sempre podem ser sanadas!

Ainda quero postar exemplos melhores na prática, como por exemplo códigos a nível de kernel (LKM – Loadable Kernel Module) onde temos estruturas interessantes para criarmos block devices, mexer com file operations, hookar funções de rede entre outros! Há uma vasta diversidade para treinarmos mais e melhorar nossos códigos! Espero falar mais em breve. Por enquanto até a próxima! 😛

E quem quiser baixar o fonte direto está aqui: lista_simples_encadeada.c

Aguardo as dúvidas! 😀