Lista encadeada em C

maio 3, 2007 às 2:55 | Publicado em artigos, C, linux, programacao | 30 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! 😀

Anúncios

30 Comentários »

RSS feed for comments on this post. TrackBack URI

  1. Muito interessante, se eu programasse em C me seria bem útil! Vê se faz uma dessa em Python aee pra galera :P!

    • queria q vc comentasse esse codigo ,pra eu entender melhor ,pois , n entendi, obrigada

  2. #include
    #include

    /* Estrutura que será usada para criar os nós da lista */

    typedef struct tipo_produto {
    int codigo;

    double preco;
    struct tipo_produto *proximo; } TProduto;
    void inserir(TProduto **cabeca);
    void listar (TProduto *cabeca);

    int main()
    {
    TProduto *cabeca = NULL; //1

    TProduto *noatual; //2

    char q; //3
    do {
    printf(“\n\nOpcoes: \nI -> para inserir novo produto;\nL -> para listar os produtos; \nS -> para sair \n:”);
    scanf(“%c”, &q); /* Le a opcao do 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 valida”);
    }
    getchar(); /* Limpa o buffer de entrada */
    } while ((q != ‘s’) && (q != ‘S’) );
    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 = malloc(sizeof(TProduto));
    (*cabeca)->codigo = cod;
    (*cabeca)->preco = preco;
    (*cabeca)->proximo = NULL;
    }
    else
    {
    noatual = *cabeca;//2
    while(noatual->proximo != NULL)
    noatual = noatual->proximo; //1
    novono = malloc(sizeof(TProduto));/* Aloca memoria para o novo no */
    novono->codigo = cod;
    novono->preco = preco;
    novono->proximo = NULL;
    noatual->proximo = novono; //3

    }
    }

    esse codigo falta alguma coisa pra funcionar pode ajudar?
    hilner@bol.com.br

  3. esta bem elaborada a função de busca poderia retornar um ponteiro para o no achado assim seria fácil deletar

    bom mais eu resolvi postar mais pela curiosidade q me causou o código
    for (; dados != NULL; dados = dados->proximo) {
    como é o funcionamento dessa sintaxe?
    pois o primeiro parâmetro não existe o segundo é uma comparação e o próximo é uma incrementação passando entre os dados da lista achei muito interessante não conhecia
    onde eu posso ver mais sobre esses laços for com funções diferenciadas dessa forma?

  4. eu to iniciando em c e queria saber o q o meu codigo tem que não imprime a lista:

    #include
    #include

    using namespace std;
    struct no
    {
    int info;
    struct no *prox;
    };
    void insere_inicio(struct no **l,int elem)
    {
    struct no *novono;
    novono=(struct no*)malloc(sizeof(struct no));
    if (*l == NULL)
    {
    novono->info=elem;
    novono->prox=NULL;
    }
    else
    {
    novono->info=elem;
    novono->prox=*l;
    *l=novono;
    }
    }
    int main()
    {
    int num,op;
    struct no*lista,**aux;
    lista=(struct no*)malloc(sizeof(struct no));
    lista=NULL;
    op=1;
    while (op !=0)
    {
    cout <> op;
    cout <> num;
    insere_inicio(&lista,num);
    }
    cout <> op;
    **aux=*lista;
    if (op == 2)
    {
    while ((*aux)->prox != NULL)
    {
    cout <info;
    *aux=(*aux)->prox;
    }

    }

    system(“PAUSE”);

    }

    desde ja obrigadu

  5. gostei muito desse exemplo,e queira pedir uma ajudinha nesse excercicio:

    DESEJAMOS EFETUAR UMA ANÁLISE ESTATÍTICA A RESPEITO DOS LIVROS VENDIDOS POR UMA LIVRARIA EM UM DETERMINADO MÊS. PARA CADA LIVRO, SÃO FONECIDAS AS SEGUINTES INFORMAÇÕES: TITULO DO LIVORA, TIPO(F=FICÇÃO / N=NÃO FICÇÃO/ T=TECNICO-CIENTIFICO),PREÇO UNITARIO DE VENDA E QUANTIDADE DE EXEMPLARES VENDIDOS NO MÊS. ELABORA UMA APLICAÇÃO USANDO UMA LISTA LIGADA QUE LEIA AS INFORMAÇÕES SOBRE OS LIVROS E AO FINAL, MOSTRE O SEGUINTE RELATORIO:
    1.QUANTIDADE DE EXEMPLARES DE CADA TIPO VENDODO NP MÊS;
    2.MEDIA DE PREÇOS DE VENDA DE LIVRO POR TIPO;
    3.NOME DO LIVRO MAIS VENDIDO COM SUE PREÇO DE VENDA(OBS:NÃO É PRECISO CONSIDERAR EMPATES)!

    POF FAVOR ME AJUDE!!!!!

  6. cara senssacional seu blog , pena que voce parou de postar neh… os exercicios … eles sao muito bom mesmo vc acabou de me dar uma ajuda fenomenal espero que tenha muito sucesso teh +

  7. show de bola, tava procurando na net, gostei mto
    vlw

  8. Olá meu nome é naal adorei este artigo com ele consegui me guiar nos estudos de lista encadeada, já fiz varios programas de cadastro com esta tecnica e estou adorando, quando você pega o geito as vezes fica mais interessante que vetor.
    Bom depois de estar bem preparado em lista encadeada resolvar tentar gravar as informações no computador para deipois carregalas novamente, resolvi estudar arquivos mas estou com dificuldades.
    Você poderia mostrar um código fonte básico com função para salvar um lista encadeada em um arquivo e também carregar de um arquivo uma lista encadeada.
    Obrigado.
    Agradeço desde já.

  9. Muito bom esse exemplo, me esclareceu e me orientou a compreender o conceito de lista. Valeu!!!

  10. Olá caro amigo!

    Muito bom o seu código, muito bom mesmo. Com certeza você já deve saber, mas não custa nada eu dizer aqui que muitos livros não detalham tão bem seus códigos quanto você. Um bom exemplo disso é o livro C Completo e Total que é muito sucks para Linux.

  11. Pessoal, estou com um probliminha para resolver este exercicio… Mas ele e bastante interessante…gostaria de ajuda

    Em uma agencia bancaria dos anos 90 existem dois caixas e uma fila de clientes a serem atendidos.
    Implementar um programa para simulação das filas na agencia.Considerar que o tamanho da fila é indeterminado. Nessa agencia esta sendo realizada uma pesquisa, e todas as pessoas, ao serem atendidas em um dos caixas prenchem uma ficha fornecendo as seguintes informações : nome; sexo; e operação realizada (deposito ou retirada). Em cada caixa existe uma pilha de fichas preenchidas com essas informções.
    Implementar um programa para realizar a simulação desse sistema, contendo os seguintes modulos:

    – inclusão de pessoas nas filas
    – atendimento das pessoas (com o preenchimento da ficha)
    – emissão de relatorio. A qualqer momento o gerente do banco podera solicitar as seguintes informações aos caixas:

    1.O Nome de todas as pessoas do sexo feminino atendidos em cada caixa;

    2. O nome de todos os clientes que realizaram um deposito em casa caixa;

    3. O numero do caixa que atendeu o maior numero de pessoas ate o monento da pesquisa;

    Ao ser realizada uma pesquisa por parte do gerente da agencia todas as fichas preenchidas existentes nos caixais são recolhidas.

  12. dá para fazer um trabalho para mim ?

  13. oi cara, eu coloquei seu código para rodar só que tá dando um errinho na linha em que você coloca:

    sleep(1);

    por favor me ajude, preciso mesmo do seu código para mim estudar e entender o funcionamento desta lista encadeada!

  14. duvida com sleep sou novo em linguagem c e estou aprendendo agora a usar listas fila e pilha
    lista encadeada

  15. Mas aí, gostaria de saber como você colocou o fonte editado como se estivesse no terminal. Você poderia dizer?

  16. O source está realmente muito bem desenvolvido. Os comentarios são informativos e as tabulações foram usadas com lógica. Já conhecia este conceito simples e poderoso, mas quis dar uma revisada pra fortalecer mais a base. Mesmo o teu artigo não tendo nada de novo para min, que já tenho formação, para iniciantes é informação mastigada de grande valia. Quem dera eu ter encontrado o source como o teu na minha época de estudante. Parabens, continue postando informações pertinentes a grande subarea da informática, que é a programação, pois isso sacia a alma de muitos curiosos, como eu, quando sobra um tempinho livre.
    Abração!!!

  17. Execute com a pilha de execucao recursiva a busca pelos elementos 1,20 e 36 na sequencia:
    1,3,7,15,21,22,36,78,95,106.

    Ajuda por favor…

  18. olá sou iniciante em linguagem c, e já não mais o que fazer para implementar o enunciado abaixo como em uma lista encadeada. Por favor se possível me ajude:
    Os dados relativos a um grupo de atletas foram organizados em uma lista linear encadeada. O
    campo de informação de cada nodo desta lista apresenta o nome e a altura de um atleta, conforme
    exibido na implementação a seguir:
    struct no{
    char nome[30];
    float altura;
    struct no *prox;
    };
    struct no *atletas;
    Implemente as funções a seguir:
    a) uma função nro_altletas (struct no *atletas) que retorna o número total de
    atletas desta lista;
    b) uma função exibe_maiores_1_90 (struct no *atletas) para imprimir o nome de
    todos os atletas que apresentam altura superior a 1,90m;
    c) uma função dividir_lista (struct no *atletas, struct no
    **maiores_1_70, struct no **menores_1_70) para dividir esta lista em duas
    outras, uma com os dados dos atletas com altura inferior a 1,70m, e a outra com os atletas com
    altura igual ou superior a este valor. Nesta operação não deverão ser alocadas novas áreas de
    memória – deverão ser utilizadas as mesmas da lista original.

    Na expectativa desde já agradeço.

  19. Pessoal, estou com um problema que esta me deixando aos nervos!!!
    tenho que implementar uma lista encadeada com alocacao dinamica em que cargas sao alocadas em um trem, e a que sera alocada primeira for a que tiver uma data mais recente. Caso o tamanho da carga seja maior que a capacidade dos vagoes do trem, ele vai para o proximo trem.
    Nesse msm programa tenho que fazer um TAD para o trem que contem os vagoes, e as carga armazenadas nele (impossivel de fazer!).
    Para piorar tem que armazenar em um arquivo texto os pedidos das cargas ordenadas. Um outro arquivo txt itinerario.txt que armazena os pedidos nos trens que ja foram colocados, e um outro arquivo que contem as cargas nao alocadas nos trens. BOA SORTE PARA QUEM OUSAR A FAZER ESSE PROGRAMA!!! NAO ESQUECA DE DORMIR!!

  20. oie…to precisando fazer um trabalho que tem uma lista de alunos de cada aluno tenho que ter a matricula, nome e notas 1 e 2, porém não sei como fazer uma lista do tipo aluno…
    pode me ajudar?

  21. Meu jovem, preciso fazer um códio em c valendo nota, sobre lista encadeada:
    elaborar um procedimento (código em C) que insira um valor antes do último valor da lista.

    Utilize a seguinte declaração de struct:
    struct nodo
    {
    int valor;
    struct nodo *prox;
    };

    O que deve ser entregue:
    Listagem do programa em C (bem identada e comentada
    , vc pode me dar um help?

  22. Legal os comentarios acima, mas e se eu tiver uma lista encadeada, ja achei como faz p xcluir o nó do inicio e o do fim, agora quero excluir o nó do meio, como faço heim??????Sei q tenho q percorrer vetor intero mas como faço p excluir o nó do meio??????

  23. quem poderia me ajudar a fazer uma lista encadeada..?? $$? É URGENTE!!

  24. Muitissimo obrigado, seu codigo meu ajudou muito, tanto em aprender a lista de adjacencia como desenvolver meu trabalho, Um abraçãoooo

  25. Muito bom o codigo , ,mas poderia complicar e concatenar duas lista encadeadas, por exemplo a l1 e a l2 e checar se nao ha registros repetidos, ai formaria a concatencao.

  26. e como seria se fosse ordenada ??

  27. Alguém saberia dizer o que significa isso :

    system( “/usr/bin/cls” );

    • Isso é para limpar a tela no terminal do Linux.

  28. […] Referência: Lista encadeada em C […]


Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Crie um website ou blog gratuito no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: