C Questão interessante com lista encadeada

William Dias · 23 de outubro de 2019

Tenho uma estrutura com N campos e uma tabela com N linhas e N campos. Preciso usar a técnica de lista encadeada para armazenar cada linha da tabela em um nó da estrutura. Porém não consigo fazer isso, uso um loop para ler linha por linha e armazenar em cada nó, porém quando o loop termina, a função retorna apenas o último nó. Acredito que seja essa a questão, porém não tenho nenhuma ideia de como proceder. Grato!

Lista *insereTxt (Lista *l){
    FILE *voo;
    char line[50];
    Lista *novo = NULL;
    voo = fopen("voo.txt","r");
    while(fgets(line, 50, voo) != NULL){
        int iRG;
        char itemp_nome[20];
        char itemp_sobrenome[20];
        sscanf(line, "%s %s %d", itemp_nome, itemp_sobrenome, &iRG);
        novo = (Lista*) malloc(sizeof(Lista));
        novo->prox = l;
        novo->RG = iRG;
        strcpy(novo->nome, itemp_nome);
        strcpy(novo->sobrenome, itemp_sobrenome);
        //printf("Nome: %s %s \t| RG: %d\n", novo->nome, novo->sobrenome, iRG);
    }
    fclose(voo);
    if (novo != NULL){
        printf("\n --> LISTA IMPORTADA COM SUCESSO!\n\n");
        system("pause");
        return novo;
    }
    else{
        printf("\nERRO: Falha ao importar a lista\n");
        system("pause");
        return NULL;
    }
}

Flávio Pedroza · 23 de outubro de 2019

Lista *novo = NULL;
Lista *antigo = NULL;
voo = fopen("voo.txt","r");
    while(fgets(line, 50, voo) != NULL){
        int iRG;
        char itemp_nome[20];
        char itemp_sobrenome[20];
        sscanf(line, "%s %s %d", itemp_nome, itemp_sobrenome, &iRG);
		novo = (Lista*) malloc(sizeof(Lista));
        if (antigo != NULL) antigo->prox = novo;
        //novo->prox = l;
        novo->RG = iRG;
        strcpy(novo->nome, itemp_nome);
        strcpy(novo->sobrenome, itemp_sobrenome);
		antigo = novo;
        //printf("Nome: %s %s \t| RG: %d\n", novo->nome, novo->sobrenome, iRG);
    }

Veja se assim funciona.

Lembre-se que ao final, seu programa deve liberar a memória alocada por malloc chamando free, pois c não tem garbage collector.

arfneto · 24 de outubro de 2019

@William Dias

Não rodei seu código ainda, mas entendo que está tentando inserir sempre no início e sua lista só tem ponteiros pra frente.

Em geral não é isso que você quer.

Porque? A razão é simples: você só tem ponteiros para frente mas você quer ser capaz de reproduzir a estrutura de entrada depois de ter montado a lista, por exemplo para reproduzir a tal tabela NxN igualzinho estava no arquivo. Inserindo no início eles vão ser lidos ao contrário...

Os N campos de que fala são esses 3 apenas, nome sobrenome e RG? e sua lista vai ter MxN estruturas dessas com os 3 campos? Talvez fosse melhor postar as estruturas em questão.

Mais um palpite:

Eu sempre recomendo isso: não misture as coisas. Você tem uma função

Lista* InsereTxt( Lista* l);

E essa função abre arquivos e lê arquivos e tal. Pense numa função assim

Lista* insereRegistro( Lista* lista, Registro* registro);

E pense se ela não faria sua vida mais simples. E antes de tudo escreva uma função

int        mostra_lista( Lista* inicio );

Que mostra um registro da lista por linha e retorna o total de itens lidos para você comparar com o que imagina ter inserido...

Assim na hora de testar não perde tempo lendo arquivos e formatando dados e eventualmente tratando erros que nada tem a ver com a estrutura de dados em si. Do modo como escreveu não está errado, mas é pouco produtivo: até o nome do arquivo é constante. E para mudar o teste você tem que editar o arquivo e salvar os dados e rodar de novo... Acho que entendeu

Veja esse header por exemplo

#define _CRT_SECURE_NO_WARNINGS
#include    "memory.h"
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>

struct registro
{
    int     RG;
    char    nome[20];
    char    sobrenome[20];
};

typedef struct registro Registro;

struct lista
{
    Registro    r;
    struct      lista* proximo;
};    // Lista

typedef struct lista Lista;

int            insere_3_campos(char[], char[], int, Lista*);

int            insere_registro(Registro*, Lista*);

int            mostra_lista(Lista*);

Pode ser algo parecido com o seu caso. Veja as duas funções insere_: com elas você pode inserir campos na sua lista e APENAS testar sua lista inserindo a partir dos campos ou a partir da estrutura já montada.

E veja esse programa

int main(int argc, char** argv)
{
    Registro    modelo;                    // "template" de registro: modelo
    Registro*   pModelo = &modelo;         // ponteiro para o modelo

    Lista        a_lista;                  // nossa lista de teste
    Lista*       pLista = &a_lista;        // um ponteiro para a lista    

    int n;
    n = mostra_lista(pLista);            // vazia
    printf("mostra_lista() retornou %d\n", n);

    // monta um registro padrão, "Jhonny Cash", RG = 0
    strcpy(modelo.nome, "Jhonny");
    strcpy(modelo.sobrenome, "Cash");
    int        rg = 1;
    for (int i = 0; i < 3; i+=1, rg+=1)
    {
        modelo.RG = rg;
        insere_3_campos(modelo.nome, modelo.sobrenome, modelo.RG, pLista);
    }
    n = mostra_lista(pLista);            // vazia
    printf("mostra_lista() retornou %d\n", n);

    for (int i = 0; i < 3; i+=1, rg+=1)
    {
        modelo.RG = rg;
        insere_registro(&modelo, pLista);
    }
    n = mostra_lista(pLista);            // vazia
    printf("mostra_lista() retornou %d\n", n);

    return 0;
}    // end main()

Ele pega um modelo de estrutura e testa a inserção com as duas rotinas, usando o modelo e numerando o RG de um em um pra poder testar se a função que mostra está preservando a ordem e não duplicando nada. Talvez a descrição correta seria que ao numerar os registros inseridos no teste você verifica se a rotina de inserção é estável. Estável quer dizer que ela preserva a ordem de entrada para itens idênticos.

Eis o que esse programa mostra

mostra_lista() retornou -2
insere_via_3_campos('Jhonny' 'Cash' [1])
insere_via_3_campos('Jhonny' 'Cash' [2])
insere_via_3_campos('Jhonny' 'Cash' [3])
mostra_lista() retornou -2
insere_registro('Jhonny' 'Cash' [4])
insere_registro('Jhonny' 'Cash' [5])
insere_registro('Jhonny' 'Cash' [6])
mostra_lista() retornou -2

Ainda sem código nenhum! Mas já implementa vários conceitos. Espero que tenha compreendido.

Repito: acho que deve inserir no FINAL da lista os novos elementos

Não se esqueça de salvar o endereço de início da lista.

Eis o programa inteiro caso queira inserir seu código nesse mecanismo

#define _CRT_SECURE_NO_WARNINGS
#include    "memory.h"
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>

struct registro
{
    int     RG;
    char    nome[20];
    char    sobrenome[20];
};

typedef struct registro Registro;

struct lista
{
    Registro      r;
    struct lista* proximo;
};    // Lista

typedef struct lista Lista;

int            insere_3_campos(char[], char[], int, Lista*);

int            insere_registro(Registro*, Lista*);

int            mostra_lista(Lista*);


int main(int argc, char** argv)
{
    Registro    modelo;                // "template" de registro: modelo
    Registro*     pModelo = &modelo;    // ponteiro para o modelo

    Lista        a_lista;                // nossa lista de teste
    Lista*        pLista = &a_lista;        // um ponteiro para a lista    

    int n;
    n = mostra_lista(pLista);            // vazia
    printf("mostra_lista() retornou %d\n", n);

    // monta um registro padrão, "Jhonny Cash", RG = 0
    strcpy(modelo.nome, "Jhonny");
    strcpy(modelo.sobrenome, "Cash");
    int        rg = 1;
    for (int i = 0; i < 3; i+=1, rg+=1)
    {
        modelo.RG = rg;
        insere_3_campos(modelo.nome, modelo.sobrenome, modelo.RG, pLista);
    }
    n = mostra_lista(pLista);            // vazia
    printf("mostra_lista() retornou %d\n", n);

    for (int i = 0; i < 3; i+=1, rg+=1)
    {
        modelo.RG = rg;
        insere_registro(&modelo, pLista);
    }
    n = mostra_lista(pLista);            // vazia
    printf("mostra_lista() retornou %d\n", n);

    return 0;
}    // end main()


int insere_3_campos(char nome[], char sobrenome[], int RG, Lista* lista)
{
    printf("insere_via_3_campos('%s' '%s' [%d])\n",
        nome, sobrenome, RG
    );
    return 0;
}    // end insere_3_campos()


int insere_registro(Registro* r, Lista* l)
{
    printf("insere_registro('%s' '%s' [%d])\n",
        r->nome, r->sobrenome, r->RG
    );
    return 0;
}


int            mostra_lista(Lista* lista)
{
    if ( lista == NULL)        return -1;
    return -2;
}

William Dias · 24 de outubro de 2019

7 horas atrás, Flávio Pedroza disse:


Lista *novo = NULL;
Lista *antigo = NULL;
voo = fopen("voo.txt","r");
    while(fgets(line, 50, voo) != NULL){
        int iRG;
        char itemp_nome[20];
        char itemp_sobrenome[20];
        sscanf(line, "%s %s %d", itemp_nome, itemp_sobrenome, &iRG);
		novo = (Lista*) malloc(sizeof(Lista));
        if (antigo != NULL) antigo->prox = novo;
        //novo->prox = l;
        novo->RG = iRG;
        strcpy(novo->nome, itemp_nome);
        strcpy(novo->sobrenome, itemp_sobrenome);
		antigo = novo;
        //printf("Nome: %s %s \t| RG: %d\n", novo->nome, novo->sobrenome, iRG);
    }

Veja se assim funciona.

Lembre-se que ao final, seu programa deve liberar a memória alocada por malloc chamando free, pois c não tem garbage collector.

Olá! Me lembro de ter tentado algo parecido porém não tenho certeza. Irei testar. Mas pelo que entendi, cada "novo" retornado pela função é um nó da lista, que na função main é atribuído a "l", assim, mantendo uma sequência, porém não tenho certeza... Vou postar meu código completo para uma melhor análise.

adicionado 8 minutos depois

@arfneto

Muito grato pela atenção!

Interessante o seu raciocínio, irei estuda-lo com mais calma, programação ainda é um pouco complexo para mim, rs!

Consegui "resolver" chamando a função várias vezes, porém sim, está lendo tudo invertido...

Segue o meu código completo para melhor análise:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <dirent.h>

//--------estrutura--------

typedef struct lista {
    char nome[20];
    char sobrenome[20];
    int RG;
    int n_voo;
    struct lista *prox;
}Lista;

//-------protótipos--------

Lista *inicializa (void);
Lista *insere (Lista *l);
Lista *insereTxt (Lista *l, char line[]);
Lista *busca (Lista *);
Lista *libera(Lista *l);
Lista *retira (Lista *l);
void criaTxt(Lista *l);
void DisplayList (Lista *l);
void vazia (Lista *l);

//----------inicio----------

int main (void){
    Lista *l; /* declara uma lista não inicializada */
    l = inicializa(); /* inicializa lista como vazia */
    int mOpcao;
    do{
        printf("\n----------------------------MENU-----------------------------\n");
        printf("Para ADICIONAR um novo passageiro, pressione \t1:\n");
        printf("Para REMOVER um passageiro, pressione \t\t2:\n");
        printf("Para LISTAR os passageiros, pressione \t\t3:\n");
        printf("Para BUSCAR um passageiro, pressione \t\t4:\n");
        printf("Para IMPORTAR uma lista, pressione \t\t5:\n");
        printf("Para SALVAR alteracoes, pressione \t\t6:\n");
        printf("Para SAIR do programa, pressione \t\t7:\n");
        printf("----------------------------MENU-----------------------------\n");
        printf("\n --> DIGITE UMA DAS opções DO MENU E PRESSIONE ENTER: ");
        scanf("%d", &mOpcao);
        switch (mOpcao){
            case 1:
                l = insere(l);
                system("cls");
                break;
            case 2:
                retira(l);
                system("cls");
                break;
            case 3:
                DisplayList(l);
                system("cls");
                break;
            case 4:
                busca(l);
                system("cls");
                break;
            case 5:
                if(l != NULL)
                    l = libera(l);
                char line[50];
                system("ls");
                FILE *voo;
                voo = fopen("voo.txt","r");
                printf("\n----------------------IMPORTANDO LISTA-----------------------\n");
                while(fgets(line, 50, voo) != NULL)
                    l = insereTxt(l, line);
                fclose(voo);
                printf("\n --> Lista importada com sucesso!\n\n");
                system("pause");
                system("cls");
                break;
            case 6:
                criaTxt(l);
                system("cls");
                break;
        }
    }while(mOpcao != 7);
    //vazia(l);
    system("pause");
    return 0;
}

Lista *inicializa (void){//inicializa lista.
    return NULL;
}

void DisplayList(Lista *l){
    Lista *novo=l;
    printf("\n--------------------LISTA DE PASSAGEIROS---------------------\n");
    if(novo == NULL)
        printf("\n --> ERRO: Nao ha passageiros na memoria, importe uma lista ou adicione novos passageiros.\n");
    for(novo=l; novo!=NULL; novo=novo->prox){
        printf("Nome: %s %s \t| RG: %d\n", novo->nome, novo->sobrenome, novo->RG);
    }
    printf("\n");
    system("pause");
}

Lista *insere (Lista *l){
    printf("\n-------------------ADICIONANDO PASSAGEIROS--------------------\n");
    printf("\nPRESSIONE ENTER PARA COMECAR\n");
    char inome[20];
    char isobrenome[20];
    int iRG;
    printf("\nNOME: ");
    scanf("%s", inome);
    printf("\nSOBRENOME: ");
    scanf("%s", isobrenome);
    printf("\nRG: ");
    scanf("%d", &iRG);
    Lista *novo = (Lista*) malloc(sizeof(Lista));
    novo->prox = l;
    novo->RG = iRG;
    strcpy(novo->nome, inome);
    strcpy(novo->sobrenome, isobrenome);
    printf("\nPASSAGEIRO ADICIONADO COM SUCESSO!\n");
    system("pause");
    return novo;
}

Lista *insereTxt (Lista *l, char line[]){
    Lista *novo = NULL;
    int iRG;
    char itemp_nome[20];
    char itemp_sobrenome[20];
    sscanf(line, "%s %s %d", itemp_nome, itemp_sobrenome, &iRG);
    novo = (Lista*) malloc(sizeof(Lista));
    novo->prox = l;
    novo->RG = iRG;
    strcpy(novo->nome, itemp_nome);
    strcpy(novo->sobrenome, itemp_sobrenome);
    return novo;
}

void criaTxt(Lista *l){
    Lista *p = l;
    printf("\n------------------------SALVANDO VOO-------------------------\n");
    printf("\n --> ANTENCAO: Essa alteracao ira sobrescrever o arquivo anterior.\n");
    printf("\n --> Pressione ENTER para aplicar ou QUALQUER OUTRA TECLA para recusar.\n");
    if(getch()==13){
        if(p != NULL){
            FILE *voo;
            voo= fopen("voo.txt", "w");
            for (p = l; p != NULL; p = p->prox){
                char temp_nome[20];
                char temp_sobrenome[20];
                int temp_RG;
                strcpy(temp_nome, p->nome);
                strcpy(temp_sobrenome, p->sobrenome);
                temp_RG=p->RG;
                fprintf(voo, "%s %s %d\n", temp_nome, temp_sobrenome, temp_RG);
            }
            fclose(voo);
        }
        else
            printf("\n --> ERRO: Nao foi feita nenhuma alteracao, nao foi possivel salvar o arquivo.\n\n");
        }
    system("pause");
}

Lista *busca(Lista *l){
    Lista *p;
    int bRG;
    printf("Digite o RG a ser buscado: ");
    scanf("%d", &bRG);
    for (p=l; p !=NULL; p=p->prox){
        if (bRG == p->RG){
            printf("Passageiro encontrado. %d\n");
            system("pause");
            return p;
        }
        else{
            printf("Passageiro nao encontrado.\n"); // não achou o elemento
            system("pause");
            return NULL;
        }
    }
}

Lista *retira (Lista *l) {
    Lista* ant = NULL; /* ponteiro para elemento anterior */
    Lista* p = l; /* ponteiro para percorrer a lista*/
    int rRG;
    printf("\n --> Digite o RG do passageiro a ser removido: \n");
    scanf("%d", &rRG);
    /* procura elemento na lista, guardando anterior */
    while (p != NULL && p->RG != rRG) {
        ant = p;
        p = p->prox;
    }
    /* verifica se achou elemento */
    if (p == NULL){
      system("pause");
        return l; /* não achou: retorna lista original */
    }
    /* retira elemento */
    if (ant == NULL) {
        /* retira elemento do inicio */
        l = p->prox;
    }
    else {
        /* retira elemento do meio da lista */
        ant->prox = p->prox;
    }
    free(p);
    system("pause");
    return l;
}

Lista *libera(Lista *l){
    Lista *p = l;
    while (p != NULL) {
        Lista *t = p->prox; // guarda referência para o próximo elemento
        free(p); //libera a memória apontada por p
        p = t; // faz p apontar para o próximo 
    }
    return p;
}

/*void vazia (Lista *l){
    printf("\nStatus da lista: ");
    if (l == NULL)
        printf("Vazia\n");
    else
        printf("Cheia\n");
}*/

O que você acha?

Agora estou com mais um problema, preciso listar minhas "tabelas" .txt, escolher uma e abri-la... Não sei como posso fazer isso.

arfneto · 24 de outubro de 2019

9 horas atrás, William Dias disse:

Muito grato pela atenção!

Interessante o seu raciocínio, irei estuda-lo com mais calma, programação ainda é um pouco complexo para mim, rs!

Consegui "resolver" chamando a função várias vezes, porém sim, está lendo tudo invertido...

@William Dias

Deixe ver se eu entendi: eu te disse que você está perdendo tempo escrevendo assim, e você disse que é uma ideia interessante mas vai ver depois. Então se eu estiver errado não vai fazer diferença MAS se eu estiver certo você vai perder muito mais tempo até ter tempo para descobrir que eu estou certo e o seu tempo se foi?

Eu acho programação algo complexo. E alguns problemas então... Bem complexos. E programar problemas complexos é então sempre um desafio.

9 horas atrás, William Dias disse:

mais um problema, preciso listar minhas "tabelas" .txt, escolher uma e abri-la... Não sei como posso fazer isso

Sim. Mais uma prova de que estou certo: tire isso do código que trata a lista. Implemente a lista e teste tudo. Depois você trata de ler e aí resolve isso.

O sistema tem funções que listam o conteúdo de um diretório, basta você ler o conteúdo e mostrar na tela para o usuário escolher o arquivo de entrada. Faça isso depois. As funções estão em dirent.h. Insisto: não faça as duas coisas ao mesmo tempo

E insira no fim da lista. Já expliquei porque: na saída precisa preservar a ordem.

Depois se precisar mostro um exemplo de código

Seu código está bom mas está pouco genérico e vai --- como já está --- ter problemas com isso: tire do código da lista essas coisas de ler e abrir arquivos

arfneto · 26 de outubro de 2019

Um exemplo: imagine seu registro declarado assim em

Citação

meu_registro.h

#include    "memory.h"
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>
#include    "malloc.h"

struct registro
{
    int     RG;
    char    nome[20];
    char    sobrenome[20];
};

typedef struct registro Registro;

// fim de meu_registro.h

Mas você ter um outro assim

#include    "memory.h"
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>
#include    "malloc.h"

struct registro
{
    int     CPF;
    int     RG;
    char    CEP[9];
    char    nome[20];
    char    sobrenome[20];
};

typedef struct registro Registro;

// fim de meu_registro2.h

E imagine suas rotinas da lista declaradas em minha_lista.h

#include    "meu_registro.h"

struct lista
{
    Registro*        r;
    struct lista*    proximo;
};    // Lista

typedef struct lista Lista;

int            apaga_registro( int(*)(Registro*, Registro*), Registro*,  Lista**);
int            da_um_fim_na_lista(    Lista**);
int            insere_ao_final( Registro*, Lista**);
int            insere_na_ordem( int (*)(Registro*, Registro*), Registro*, Lista**);
Registro*      pesquisa_registro( int(*)(Registro*, Registro*), Registro*, Lista**);
int            remove_item( Lista*, Lista**);
int            remove_registro( int(*)(Registro*, Registro*), Registro*, Lista**);

// fim de minha_lista.h

Porque isso?

Imagine agora que essas funções de lista.h trabalham só com a lista em si e os ponteiros para Registro. Então você pode usar essas funções para resolver todos os problemas de listas encadeadas simples que tenha. Sem ter que mudar nada. Apenas altera o header que descreve o Registro.

Por exemplo, da_um_fim_na_lista() percorre a lista e vai apagando todos os registros e os nós da lista em si, até o último ponteiro, e não precisa saber o que tinha dentro.

insere_na_ordem() por exemplo insere os registros na ordem na lista, classificados por qualquer campo. Como por RG no primeiro ou por CPF ou CEP no segundo exemplo. E você não precisa mudar nada nas funções se mudar de Registro

Espero que ajude a entender a razão, mesmo sem ler uma implementação dessas coisas.

Notei que falta uma função genérica para percorrer a lista ., Depois vou acrescentar uma. Já fiz algo assim umas vezes.

Essas funções vem da funcionalidade primária que se procura nessas estruturas, e tem uma abreviatura: CRUD --- na verdade tem outras --- para Create, Read, Update e Delete e no final pense que podia declarar as funções assim

#include    "meu_registro_v.h"

struct lista
{
    void*            r;
    struct lista*    proximo;
};    // Lista
typedef struct lista Lista;

int            apaga_registro(int(*)(void*, void*), void*, Lista**);
int            da_um_fim_na_lista(Lista**);
int            insere_ao_final(void*, Lista**);
int            insere_na_ordem(int (*)(void*, void*), void*, Lista**);
void*        pesquisa_registro(int(*)(void*, void*), void*, Lista**);
int            remove_item(Lista*, Lista**);
int            remove_registro(int(*)(void*, void*), void*, Lista**);
// fim de minha_lista_v.h

E aí sequer precisa chamar a estrutura de Registro e você tem uma implementação abstrata para lista que funciona para qualquer coisa porque todos os ponteiros foram trocados de Registro* para void*. Nada original porque isso que as bibliotecas fazem afinal.

Para um exemplo bem melhor que o meu veja a função qsort() do C em stdlib.h por exemplo.