C Inverter nós em uma lista encadeada simples.

NhemonF · 12 de dezembro de 2020

Boa tarde pessoal

Estou com uma dúvida em um exercício de lista encadeada simples. Queria inserir o nó do início como fim, e o nó do fim como o início.

É basicamente nessa maneira:

**ANTES**

L -> (800, 99.99, Polystation 5) -> (981, 199.99, XCaixa Series Y) -> NULL

**DEPOIS**

L -> (981, 199.99, XCaixa Series Y) -> (800, 99.99, Polystation 5) -> NULL

Mas estou com um certo problema com o código, que quando executo o comando, ele não inverte.

A) Função que inverte o nó da lista

// (d) Retorna a Lista invertida. Se a lista está vazia, retorne uma lista vazia.
    Lista *inverter(const Lista *L) {
        // IMPLEMENTE ESTA FUNÇÃO
        Lista* q;   /* variável auxiliar para nova lista */
        No *p;
        int aux;
    
        for (p = L; p != NULL; p = p->prox)
    
            if (p-> == NULL)
            {
                aux = p->prox;
                p->prox = NULL;
                return p;
            }
    }

B) Structs de `_produto`, `_no` e `_lista`

// struct que define um produto
    typedef struct _produto {
        int num_serie; // numero de série do produto
        char nome[64];
        double preco;
    } Produto;

 // struct que define um nó curcular duplamente encadeado
    typedef struct _no {
        Produto *prod;
        struct _no *prox;
    } No;

 // struct que define uma Lista Ligada Simples
    typedef struct _lista {
        No *inicio;
        No *fim;
        int tamanho; // numero de nós da lista
    } Lista;

C) Código acionado na `main()`:

 else if (strcmp(comando, "inverte") == 0) {
           Lista *L_aux = inverter(L);
           destroiLista(&L);
           L = L_aux;
         }

arfneto · 12 de dezembro de 2020

Talvez você não tenha explicado bem o que quer fazer. Inverter a lista é uma coisa. Inverter o primeiro e o último é outra.

Só que se a lista só tem dois elementos vai dar na mesma. E adivinhe quantos elementos tem no seu exemplo... Sim, dois.

Então não dá pra saber.

Poste um programa inteiro, que alguém possa compilar, e mais uma descrição de como reproduzir seu problema.

Se quer inverter o primeiro e o último

Apenas entenda que o último vai passar a ser o primeiro e o sucessor dele vai ser o sucessor do primeiro antes da inversão então você precisa salvar o endereço antes da inversão. E claro que o último sendo o que é não tem sucessor.

Só isso. E trate a condição especial (trivial) de uma lista com um único nó.

Se quer inverter a lista toda

Apenas declare outra lista e vá inserindo os elementos conforme extrai da primeira. Copie da função que mostra os elementos. É simples.

NhemonF · 13 de dezembro de 2020

@arfneto Então, tenho o programa inteiro para algum de vocês compilar. Se não se importar, posso publicar neste comentário.

E sobre as frases em negrito, eu queria inverter a lista pelo nó. Por exemplo, se eu haver uma lista simples com 5 elementos, preciso fazer com que inverta os nós da lista começando pelo último elemento. Certo?

L -> (800, 99.99, Polystation 5) -> (785, 299.99, Mouse Gamer) -> (584, 899.99, Intel Core i9 8700U) -> (123, 34.99, Mousepad Razer) -> (981, 199.99, XCaixa Series Y) -> NULL

L -> (981, 199.99, XCaixa Series Y) -> (123, 34.99, Mousepad Razer) -> (584, 899.99, Intel Core i9 8700U)-> (785, 299.99, Mouse Gamer) -> (800, 99.99, Polystation 5) -> NULL

@arfneto mas fica basicamente assim?

Lista *inverter(const Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    Lista *aux = L;
    No *p;
    No *ant = NULL;
    if (listaEstaVazia(L)){
        return;
    }

    else {
        aux = L->fim;
        while(aux != NULL){
            aux = L->fim;
            p = p->ant;
            L->fim = aux;
        }
    }
    return aux;
}

arfneto · 13 de dezembro de 2020

@NhemonF Use suas próprias funções para criar outra lista. Por isso elas são funções: para poder usar em varias listas. A inversão ocorre naturalmente se você tem uma função que insere no início. E se não tem apenas escreva uma.

Sugiro postar assim ou de modo similar a lista:

L ->
(800, 99.99, Polystation 5) ->
(785, 299.99, Mouse Gamer) ->
(584, 899.99, Intel Core i9 8700U) ->
(123, 34.99, Mousepad Razer) -> 
(981, 199.99, XCaixa Series Y) ->
NULL

E não em uma linha. Acho que dá pra ver porque

Inserir no início inverte a ordem naturalmente. É como uma pilha. Você não precisa fazer nada. Não tem lógica nenhuma: apenas copie a função que mostra a lista e ao invés de mostra o elemento insira no início de outra lista. É trivial.

poste um programa que alguém possa compilar, completo...

NhemonF · 13 de dezembro de 2020

@arfneto Entendi mais ou menos o que você disse.

Vou traduzir do português para C se entendi.

1) Caso a lista não esteja vazia:

if (!listaEstaVazia(L)){

  //comando da função

}

2) Crio um ponteiro de uma lista chamado "aux":

Lista *aux;

3) Crio um ponteiro de "No" chamado "p" que é equivalente ao nó do fim da lista:

No *p = L->fim

4) Crio um ponteiro de "No" chamado "ant", ou seja, quero que percorra para o anterior de "p":

No *ant = NULL

5) Enquanto o ponteiro "p" não for nulo, imprime a lista invertida:

while (p != NULL) {
  printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
  ant->prox = p->prox;
}

É mais ou menos desta maneira?

arfneto · 13 de dezembro de 2020

@NhemonF pode ser. mas parece muito complicado. Repito: poste o programa e eu ajudo você.

No entanto em português ou C apenas crie uma nova lista, adaptando a função que espero que você tenha escrito para mostrar os elementos da lista, e crie outra lista que naturalmente vai estar invertida. Você não precisa fazer nada: apenas insira no início.

NhemonF · 13 de dezembro de 2020

@arfneto Ok. Vou postar o código.

OBS: Tem algumas linhas do código que não posso alterá-las.

/***************************
* LAB 04 - 02/12/2020
* SEU NOME - SEU PRONTUÁRIO
***************************/

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

// struct que define um produto
typedef struct _produto {
    int num_serie; // numero de série do produto
    char nome[64];
    double preco;
} Produto;

// struct que define um nó curcular duplamente encadeado
typedef struct _no {
    Produto *prod;
    struct _no *prox;
} No;

// struct que define uma Lista Ligada Simples
typedef struct _lista {
    No *inicio;
    No *fim;
    int tamanho; // numero de nós da lista
} Lista;

/*********** HEADERS ***********/
Produto *criaProduto(int num_serie, double preco, char nome[64]);
void destroiProduto(Produto **prod_ref);
No *criaNo(int num_serie, double preco, char nome[64]);
Lista *criaLista();
void destroiLista(Lista **L_ref);
int listaEstaVazia(const Lista *L);
void imprime(const Lista *L);
void imprime_ultimo(const Lista *L);


// A SEREM IMPLEMENTADAS POR VOCÊ
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]);
void removeProduto(Lista *L, int num_serie);
void removePrimeiraMetade(Lista *L);
Lista *inverter(const Lista *L);
Lista *ordenar(const Lista *L, int ordem);
/*******************************/

int main() {
    Lista *L = criaLista();

    char comando[64];
    int ordem;

    int num_serie;
    char nome[64];
    double preco;

    scanf("%s", comando);

    while (strcmp(comando, "para") != 0) {
        if (strcmp(comando, "insere_inicio") == 0) {
            scanf("%d", &num_serie);
            scanf("%lf", &preco);
            scanf(" %[^\t\n]s", nome);

            insereNoInicio(L, num_serie, preco, nome);
        }
        else if (strcmp(comando, "remove_produto") == 0) {
            scanf("%d", &num_serie);
            removeProduto(L, num_serie);
        }
        else if (strcmp(comando, "remove_primeira_metade") == 0) {
            removePrimeiraMetade(L);
        }
        else if (strcmp(comando, "inverte") == 0) {
            Lista *L_aux = inverter(L);
            destroiLista(&L);
            L = L_aux;
        }
        else if (strcmp(comando, "ordena") == 0) {
            scanf("%d", &ordem);

            Lista *L_aux = ordenar(L, ordem);
            destroiLista(&L);
            L = L_aux;
        }
        else if (strcmp(comando, "imprime") == 0) {
            imprime(L);
        }

        scanf("%s", comando);
    }

    return 0;
}
////////////////////////////////////

/*************** BODIES *****************/
// (a) Insere um nó no início da Lista com um novo produto, que possui os valores passados por parâmetro.
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]) {
    // IMPLEMENTE ESTA FUNÇÃO
    No *p = criaNo(num_serie, preco, nome); //Cria um nó de um produto para inserir os dados
    p->prox = L->inicio; //Aponta a partir do início da lista encadeada
    L->inicio = p; //Coloca os dados do produto pro início
    L->tamanho++; //Aumenta o tamanho da lista para cada produto adicionado no encadeamento.
}

// (b) Remove o nó da lista cujo produto possua o número de série num_serie.
// Assuma que o número de série é único na lista.
// Se a lista estiver vazia ou não existir nenhum produto com o número de série, nada acontece.
void removeProduto(Lista *L, int num_serie) {
    // IMPLEMENTE ESTA FUNÇÃO
    //caso a lista esteja vazia
    if (listaEstaVazia(L)) {
        return;
    }

    //variável que indica se o número de serie foi encontrado ou não
    // 0 para não
    // 1 para sim
    int encontrou = 0;

    //verifica se o número encontrado está no início
    if(L->inicio->prod->num_serie == num_serie) {
        L->inicio = L->inicio->prox;
        encontrou = 1;
        L->tamanho--;
    }

    //verifica se o número encontrado está em qualquer posição
    else {
        No *no = L->inicio;
        No *anterior = NULL;

        //percorre todo o nó da lista para encontrar o valor inserido
        while(no != NULL && encontrou == 0) {
            if(no->prod->num_serie == num_serie) {
                anterior->prox = no->prox;
                encontrou == 1;
                L->tamanho--;
            }

            anterior = no;
            no = no->prox;
        }
    }
}

// (c) Remove a primeira metade da Lista. Caso a lista possua um número ímpar de elementos,
// considere que a primeira metade possui mais elementos
// (Ex: se a lista possuir 5 elementos, a primeira metade possui os 3 primeiros elementos).
// Se a lista tiver vazia, nada acontece.
void removePrimeiraMetade(Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    //verifica se a lista está vazia

}

// (d) Retorna a Lista invertida. Se a lista está vazia, retorne uma lista vazia.
Lista *inverter(const Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");
    if (!listaEstaVazia(L)) {
        No *p = L->fim;
        No *ant = NULL;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            ant->prox = p->prox;
        }
    }
    printf("NULL\n\n");
}

// (e) Retorna a lista ordenada pelo número de série de seus produtos, de acordo com uma ordem passada pelo programa:
// ordem=0 significa ordem crescente;
// ordem=1 significa ordem decrescente.
Lista *ordenar(const Lista *L, int ordem) {
    // IMPLEMENTE ESTA FUNÇÃO
    if (ordem == 0){
        if (listaEstaVazia(L)){
            return;
        } else {
            
        }

    } else {
        if (listaEstaVazia(L)){
            return;
        } else {
            
        }
    }
}

/************ FUNÇÕES JÁ IMPLEMENTADAS *************/
Produto *criaProduto(int num_serie, double preco, char nome[64]) {
    Produto *prod = (Produto *)calloc(1, sizeof(Produto));
    prod->num_serie = num_serie;
    prod->preco = preco;
    strcpy(prod->nome, nome);

    return prod;
}

void destroiProduto(Produto **prod_ref) {
    Produto *prod = *prod_ref;

    if (prod != NULL) {
        free(prod);
        *prod_ref = NULL;
    }
}

No *criaNo(int num_serie, double preco, char nome[64]) {
    No *no = (No*) calloc(1, sizeof(No));
    no->prod = criaProduto(num_serie, preco, nome);
    no->prox = NULL;

    return no;
}

Lista *criaLista() {
    return ((Lista*) calloc(1, sizeof(Lista)));
}

void destroiLista(Lista **L) {
    Lista *L_aux = *L;

    // remove todos os nós da lista
    No *p = L_aux->inicio;
    while (p != NULL) {
        No *no = p;
        p = p->prox;
        destroiProduto(&no->prod);
        free(no);
    }
    free(L_aux);
    *L = NULL;
}

int listaEstaVazia(const Lista *L) {
    return (L->inicio == NULL);
}

void imprime(const Lista *L) {
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}

arfneto · 13 de dezembro de 2020

2 horas atrás, NhemonF disse:

Tem algumas linhas do código que não posso alterá-las.

Mas pode apenas não usar

Não está assim muito bom. main() por outro lado está bem ruim, com todos os erros que parecem obrigatórios.

teste o retorno de scanf(). Já leu o manual? Qual o propósito de seguir se pode não ter lido nada?
qual a razão de ler sem um único prompt?
qual a razão de ler do teclado? Mesmo que o enunciado exija é MUITO mais simples e seguro testar com constantes ou ler de um arquivo.
ler valores sem um único prompt? Não seria gentil dizer o que e como espera ler?
não seria razoável mostrar o que leu ao menos enquanto está testando?
quando declara algo está declarando o nome. Não use o asterisco junto à variável. Não reflete o que est;a fazendo.
Esse tipo de função
```
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]);
```
É de certa ingenuidade. Escreva
```
void insereNoInicio(_produto*,Lista *L);
```
Que é muito mais esperto. E mesmo que precise escrever com o protótipo fornecido escreva

void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64])
{
  _produto um;
  um.num_serie = num_serie;
  um.preco = preco;
  strcpy(um.nome, nome);
  insere( &um, L);
  return;
}

E mostre ao seu professor que você pensou melhor que ele.

Entenda que uma lista tem nós. As chamadas das funções de lista não podem usar dados que estão nos nós. É ingenuidade.

E os nós tem dados e uma chave. E a chave pode ou não fazer parte dos dados. Assim é

Se você em essa função aí e esta funcionando, e você tem essa

void imprime(const Lista *L) {
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}

O que acha que vai acontecer se você escrever

int imprime_e_faz_aquilo(const Lista *L, const Lista* Outra )
{
    if ( L == NULL ) return -1;
    if ( Outra == NULL ) return -1;
   
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            insereNoInicio(Outra,  p->prod->num_serie, p->prod->preco, p->prod->nome); // ====<
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}

Pois é.

Não entendeu mesmo o que eu disse?

E essa função?

int faz_aquilo(const Lista *L, const Lista* Outra )
{
    if ( L == NULL ) return -1;
    if ( Outra == NULL ) return -1;
 
    if (!listaEstaVazia(L)) {
        No *p = L->inicio;
        while (p != NULL) {
            insereNoInicio(Outra,  p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
}

Faria o que?

NhemonF · 13 de dezembro de 2020

53 minutos atrás, arfneto disse:
Mas pode apenas não usar

Não está assim muito bom. main() por outro lado está bem ruim, com todos os erros que parecem obrigatórios.
teste o retorno de scanf(). Já leu o manual? Qual o propósito de seguir se pode não ter lido nada?

qual a razão de ler sem um único prompt?

qual a razão de ler do teclado? Mesmo que o enunciado exija é MUITO mais simples e seguro testar com constantes ou ler de um arquivo.

ler valores sem um único prompt? Não seria gentil dizer o que e como espera ler?

não seria razoável mostrar o que leu ao menos enquanto está testando?

quando declara algo está declarando o nome. Não use o asterisco junto à variável. Não reflete o que est;a fazendo.
Esse tipo de função
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]);
É de certa ingenuidade. Escreva
void insereNoInicio(_produto*,Lista *L);
Que é muito mais esperto. E mesmo que precise escrever com o protótipo fornecido escreva
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64])
{
  _produto um;
  um.num_serie = num_serie;
  um.preco = preco;
  strcpy(um.nome, nome);
  insere( &um, L);
  return;
}
E mostre ao seu professor que você pensou melhor que ele.

Entenda que uma lista tem nós. As chamadas das funções de lista não podem usar dados que estão nos nós. É ingenuidade.

E os nós tem dados e uma chave. E a chave pode ou não fazer parte dos dados. Assim é

Se você em essa função aí e esta funcionando, e você tem essa
void imprime(const Lista *L) {
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}
O que acha que vai acontecer se você escrever
int imprime_e_faz_aquilo(const Lista *L, const Lista* Outra )
{
    if ( L == NULL ) return -1;
    if ( Outra == NULL ) return -1;
   
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            insereNoInicio(Outra,  p->prod->num_serie, p->prod->preco, p->prod->nome); // ====<
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}
Pois é.

Não entendeu mesmo o que eu disse?

E essa função?
int faz_aquilo(const Lista *L, const Lista* Outra )
{
    if ( L == NULL ) return -1;
    if ( Outra == NULL ) return -1;
 
    if (!listaEstaVazia(L)) {
        No *p = L->inicio;
        while (p != NULL) {
            insereNoInicio(Outra,  p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
}
Faria o que?

Eu ainda não entendi direito... Eu acho que assim daria um erro ao compilar.

Na verdade, acho que tenho uma pequena ideia. Mas não sei se para você estaria certo:

Criar um nó do qual aponta para o fim da lista.

Eu iria criar um nó que aponta para o fim da lista?

Basicamente assim?

int faz_aquilo(const Lista *L, const Lista* Outra ) {
  if ( L == NULL ) return -1;
  if ( Outra == NULL ) return -1;

  if (!listaEstaVazia(L)) {
    No *p = L->fim;
    No *ant = NULL;
    while (p != NULL) {
      insereNoInicio(Outra, p->prod->num_serie, p->prod->preco, p->prod->nome);
      ant->prox = p->prox;
    }
  }
}

arfneto · 13 de dezembro de 2020

13 minutos atrás, NhemonF disse:

Eu iria criar um nó que aponta para o fim da lista?

Basicamente assim?

Não precisa fazer nada. A natureza de inserir no inicio é inverter a orem então é só usar o código como te mostrei: apenas modifique sua versão de imprime() ecomo eu mostrei.

Não entendo o que quer dizer com

15 minutos atrás, NhemonF disse:

Eu ainda não entendi direito... "Eu acho que assim daria um erro ao compilar" Como assim? Apenas compile e veja se dá erro.

NhemonF · 13 de dezembro de 2020

16 minutos atrás, arfneto disse:

Eu ainda não entendi direito... "Eu acho que assim daria um erro ao compilar" Como assim? Apenas compile e veja se dá erro.

Então, o código deu erro. Não saiu a lista invertida.

arfneto · 13 de dezembro de 2020

27 minutos atrás, NhemonF disse:

Então, o código deu erro. Não saiu a lista invertida.

Então as funções estão erradas. Não há como não inverter: escreva num papel: 1 2 3 4 5 => 5 4 3 2 1 . Não tem outro jeito. É a natureza.

O programa não está muito bom, como te falei. E nem os protótipos nem as estruturas de dados. Poste o programa como está agora se quiser que eu dê uma olhada. E mais gente pode ajudar

NhemonF · 13 de dezembro de 2020

@arfneto Vou postar o código aqui mesmo.

/***************************
* LAB 04 - 02/12/2020
* SEU NOME - SEU PRONTUÁRIO
***************************/

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

// struct que define um produto
typedef struct _produto {
    int num_serie; // numero de série do produto
    char nome[64];
    double preco;
} Produto;

// struct que define um nó curcular duplamente encadeado
typedef struct _no {
    Produto *prod;
    struct _no *prox;
} No;

// struct que define uma Lista Ligada Simples
typedef struct _lista {
    No *inicio;
    No *fim;
    int tamanho; // numero de nós da lista
} Lista;

/*********** HEADERS ***********/
Produto *criaProduto(int num_serie, double preco, char nome[64]);
void destroiProduto(Produto **prod_ref);
No *criaNo(int num_serie, double preco, char nome[64]);
Lista *criaLista();
void destroiLista(Lista **L_ref);
int listaEstaVazia(const Lista *L);
void imprime(const Lista *L);
void imprime_ultimo(const Lista *L);


// A SEREM IMPLEMENTADAS POR VOCÊ
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]);
void removeProduto(Lista *L, int num_serie);
void removePrimeiraMetade(Lista *L);
Lista *inverter(const Lista *L);
Lista *ordenar(const Lista *L, int ordem);
/*******************************/

int main() {
    Lista *L = criaLista();

    char comando[64];
    int ordem;

    int num_serie;
    char nome[64];
    double preco;

    scanf("%s", comando);

    while (strcmp(comando, "para") != 0) {
        if (strcmp(comando, "insere_inicio") == 0) {
            scanf("%d", &num_serie);
            scanf("%lf", &preco);
            scanf(" %[^\t\n]s", nome);

            insereNoInicio(L, num_serie, preco, nome);
        }
        else if (strcmp(comando, "remove_produto") == 0) {
            scanf("%d", &num_serie);
            removeProduto(L, num_serie);
        }
        else if (strcmp(comando, "remove_primeira_metade") == 0) {
            removePrimeiraMetade(L);
        }
        else if (strcmp(comando, "inverte") == 0) {
            Lista *L_aux = inverter(L);
            destroiLista(&L);
            L = L_aux;
        }
        else if (strcmp(comando, "ordena") == 0) {
            scanf("%d", &ordem);

            Lista *L_aux = ordenar(L, ordem);
            destroiLista(&L);
            L = L_aux;
        }
        else if (strcmp(comando, "imprime") == 0) {
            imprime(L);
        }

        scanf("%s", comando);
    }

    return 0;
}
////////////////////////////////////

/*************** BODIES *****************/
// (a) Insere um nó no início da Lista com um novo produto, que possui os valores passados por parâmetro.
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]) {
    // IMPLEMENTE ESTA FUNÇÃO
    No *p = criaNo(num_serie, preco, nome); //Cria um nó de um produto para inserir os dados
    p->prox = L->inicio; //Aponta a partir do início da lista encadeada
    L->inicio = p; //Coloca os dados do produto pro início
    L->tamanho++; //Aumenta o tamanho da lista para cada produto adicionado no encadeamento.
}

// (b) Remove o nó da lista cujo produto possua o número de série num_serie.
// Assuma que o número de série é único na lista.
// Se a lista estiver vazia ou não existir nenhum produto com o número de série, nada acontece.
void removeProduto(Lista *L, int num_serie) {
    // IMPLEMENTE ESTA FUNÇÃO
    //caso a lista esteja vazia
    if (listaEstaVazia(L)) {
        return;
    }

    //variável que indica se o número de serie foi encontrado ou não
    // 0 para não
    // 1 para sim
    int encontrou = 0;

    //verifica se o número encontrado está no início
    if(L->inicio->prod->num_serie == num_serie) {
        L->inicio = L->inicio->prox;
        encontrou = 1;
        L->tamanho--;
    }

    //verifica se o número encontrado está em qualquer posição
    else {
        No *no = L->inicio;
        No *anterior = NULL;

        //percorre todo o nó da lista para encontrar o valor inserido
        while(no != NULL && encontrou == 0) {
            if(no->prod->num_serie == num_serie) {
                anterior->prox = no->prox;
                encontrou == 1;
                L->tamanho--;
            }

            anterior = no;
            no = no->prox;
        }
    }
}

// (c) Remove a primeira metade da Lista. Caso a lista possua um número ímpar de elementos,
// considere que a primeira metade possui mais elementos
// (Ex: se a lista possuir 5 elementos, a primeira metade possui os 3 primeiros elementos).
// Se a lista tiver vazia, nada acontece.
void removePrimeiraMetade(Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando no código
}

// (d) Retorna a Lista invertida. Se a lista está vazia, retorne uma lista vazia.
Lista *inverter(const Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    Lista *Outra;
    if ( L == NULL ) return -1;
    if ( Outra == NULL ) return -1;

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;
        No *ant = NULL;
        while (p != NULL) {
            insereNoInicio(Outra,  p->prod->num_serie, p->prod->preco, p->prod->nome);
            ant->prox = p->prox;
            p->prox = p;
        }
    }
}

// (e) Retorna a lista ordenada pelo número de série de seus produtos, de acordo com uma ordem passada pelo programa:
// ordem=0 significa ordem crescente;
// ordem=1 significa ordem decrescente.
Lista *ordenar(const Lista *L, int ordem) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando em como fazer
    if (ordem == 0){
        if (listaEstaVazia(L)){
            return;
        } else {

        }

    } else {
        if (listaEstaVazia(L)){
            return;
        } else {

        }
    }
}

/************ FUNÇÕES JÁ IMPLEMENTADAS *************/
Produto *criaProduto(int num_serie, double preco, char nome[64]) {
    Produto *prod = (Produto *)calloc(1, sizeof(Produto));
    prod->num_serie = num_serie;
    prod->preco = preco;
    strcpy(prod->nome, nome);

    return prod;
}

void destroiProduto(Produto **prod_ref) {
    Produto *prod = *prod_ref;

    if (prod != NULL) {
        free(prod);
        *prod_ref = NULL;
    }
}

No *criaNo(int num_serie, double preco, char nome[64]) {
    No *no = (No*) calloc(1, sizeof(No));
    no->prod = criaProduto(num_serie, preco, nome);
    no->prox = NULL;

    return no;
}

Lista *criaLista() {
    return ((Lista*) calloc(1, sizeof(Lista)));
}

void destroiLista(Lista **L) {
    Lista *L_aux = *L;

    // remove todos os nós da lista
    No *p = L_aux->inicio;
    while (p != NULL) {
        No *no = p;
        p = p->prox;
        destroiProduto(&no->prod);
        free(no);
    }
    free(L_aux);
    *L = NULL;
}

int listaEstaVazia(const Lista *L) {
    return (L->inicio == NULL);
}

void imprime(const Lista *L) {
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}

arfneto · 13 de dezembro de 2020

Ok, o programa não está assim bom. tem os problemas que já expliquei e você nada mudou.

Os protótipos e as estruturas também.

Mas pode funcionar assim mesmo...

Agora:

Lista* inverter(const Lista* L) {
    // IMPLEMENTE ESTA FUNÇÃO
    Lista* Outra;
    if (L == NULL) return -1;
    if (Outra == NULL) return -1;

Como assim? Que acha que vai ter em Outra se acabou de declarar e sequer inicializou? Nem olhei muito o resto. Sequer compila o programa como está...

Compare com o que eu escrevi de cabeça, copiando de seu código:

int faz_aquilo(const Lista *L, const Lista* Outra )
{
    if ( L == NULL ) return -1;
    if ( Outra == NULL ) return -1;

É claro que Outra tem que apontar para uma lista. possivelmente vazia. Não necessariamente porque pode querer concatenar listas usando a mesma função (não do modo como escreveu, claro).

Que tal declarar

    Lista* Outra = criaLista();

e continuar testando? Poste o novo código

Continuei olhando o programa. Não está bom e tem os problemas que eu te disse. Sequer compilava.

No entanto veja essa função

Lista* inverter(const Lista* L)
{
    if (L == NULL) return NULL;
    No* p = L->inicio;

    Lista* Outra = criaLista();
    if (Outra == NULL) return NULL;
    while (p != NULL)
    {
        insereNoInicio(Outra, p->prod->num_serie, p->prod->preco, p->prod->nome);
        p = p->prox;
    };  // while()
    return Outra;
};

que funciona se insereNoInicio() funcionar...

E esse código para main():

#include "outro.h"
int main()
{
    Lista* L = criaLista();
    imprime(L);

    for (int i = 0; i < 10; i += 1) insereNoInicio(L, i, 0., "teste");
    imprime(L);
    Lista* invertida = inverter(L);
    imprime(invertida);

    return 0;
}

Que mostra

Tamanho da lista: 0
L -> NULL

Tamanho da lista: 10
L -> (9, 0.00, teste) -> (8, 0.00, teste) -> (7, 0.00, teste) -> (6, 0.00, teste) ->
     (5, 0.00, teste) -> (4, 0.00, teste) -> (3, 0.00, teste) -> (2, 0.00, teste) ->
     (1, 0.00, teste) -> (0, 0.00, teste) -> NULL

Tamanho da lista: 10
L -> (0, 0.00, teste) -> (1, 0.00, teste) -> (2, 0.00, teste) -> (3, 0.00, teste) ->
     (4, 0.00, teste) -> (5, 0.00, teste) -> (6, 0.00, teste) -> (7, 0.00, teste) ->
     (8, 0.00, teste) -> (9, 0.00, teste) -> NULL

Exceto pelas quebras de linha que eu acrescentei... Mude isso.

E reescreva main(). Recomendo mesmo fazer como eu disse.

Recomendo também escrever o programa como está abaixo. Escreve-se assim em todo o mundo, e o mais provável é que eles estajam todos certos:

Headers com as estruturas e protótipos mas sem alocar NADA. No caso só um:

Spoiler


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

// struct que define um produto
typedef struct _produto {
    int num_serie; // numero de série do produto
    char nome[64];
    double preco;
} Produto;

// struct que define um nó curcular duplamente encadeado
typedef struct _no {
    Produto* prod;
    struct _no* prox;
} No;

// struct que define uma Lista Ligada Simples
typedef struct _lista {
    No* inicio;
    No* fim;
    int tamanho; // numero de nós da lista
} Lista;

/*********** HEADERS ***********/
Produto* criaProduto(int num_serie, double preco, char nome[64]);
void destroiProduto(Produto** prod_ref);
No* criaNo(int num_serie, double preco, char nome[64]);
Lista* criaLista();
void destroiLista(Lista** L_ref);
int listaEstaVazia(const Lista* L);
void imprime(const Lista* L);
void imprime_ultimo(const Lista* L);


// A SEREM IMPLEMENTADAS POR VOCÊ
void insereNoInicio(Lista* L, int num_serie, double preco, char nome[64]);
void removeProduto(Lista* L, int num_serie);
void removePrimeiraMetade(Lista* L);
Lista* inverter(const Lista* L);
Lista* ordenar(const Lista* L, int ordem);

O código da lista separado

Spoiler


/***************************
* LAB 04 - 02/12/2020
* SEU NOME - SEU PRONTUÁRIO
***************************/
#include "outro.h"

////////////////////////////////////

/*************** BODIES *****************/
// (a) Insere um nó no início da Lista com um novo produto, que possui os valores passados por parâmetro.
void insereNoInicio(Lista* L, int num_serie, double preco, char nome[64]) {
    // IMPLEMENTE ESTA FUNÇÃO
    No* p = criaNo(num_serie, preco, nome); //Cria um nó de um produto para inserir os dados
    p->prox = L->inicio; //Aponta a partir do início da lista encadeada
    L->inicio = p; //Coloca os dados do produto pro início
    L->tamanho++; //Aumenta o tamanho da lista para cada produto adicionado no encadeamento.
}

// (b) Remove o nó da lista cujo produto possua o número de série num_serie.
// Assuma que o número de série é único na lista.
// Se a lista estiver vazia ou não existir nenhum produto com o número de série, nada acontece.
void removeProduto(Lista* L, int num_serie) {
    // IMPLEMENTE ESTA FUNÇÃO
    //caso a lista esteja vazia
    if (listaEstaVazia(L)) {
        return;
    }

    //variável que indica se o número de serie foi encontrado ou não
    // 0 para não
    // 1 para sim
    int encontrou = 0;

    //verifica se o número encontrado está no início
    if (L->inicio->prod->num_serie == num_serie) {
        L->inicio = L->inicio->prox;
        encontrou = 1;
        L->tamanho--;
    }

    //verifica se o número encontrado está em qualquer posição
    else {
        No* no = L->inicio;
        No* anterior = NULL;

        //percorre todo o nó da lista para encontrar o valor inserido
        while (no != NULL && encontrou == 0) {
            if (no->prod->num_serie == num_serie) {
                anterior->prox = no->prox;
                encontrou = 1; // == 1 ?
                L->tamanho--;
            }

            anterior = no;
            no = no->prox;
        }
    }
}

// (c) Remove a primeira metade da Lista. Caso a lista possua um número ímpar de elementos,
// considere que a primeira metade possui mais elementos
// (Ex: se a lista possuir 5 elementos, a primeira metade possui os 3 primeiros elementos).
// Se a lista tiver vazia, nada acontece.
void removePrimeiraMetade(Lista* L) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando no código
}

Lista* inverter(const Lista* L)
{
    if (L == NULL) return NULL;
    No* p = L->inicio;

    Lista* Outra = criaLista();
    if (Outra == NULL) return NULL;
    while (p != NULL)
    {
        insereNoInicio(Outra, p->prod->num_serie, p->prod->preco, p->prod->nome);
        p = p->prox;
    };  // while()
    return Outra;
};

// (e) Retorna a lista ordenada pelo número de série de seus produtos, de acordo com uma ordem passada pelo programa:
// ordem=0 significa ordem crescente;
// ordem=1 significa ordem decrescente.
Lista* ordenar(const Lista* L, int ordem) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando em como fazer
    if (ordem == 0) {
        if (listaEstaVazia(L)) {
            return NULL;
        }
        else {

        }

    }
    else {
        if (listaEstaVazia(L)) {
            return NULL;
        }
        else {

        }
    };
    return NULL;
}

/************ FUNÇÕES JÁ IMPLEMENTADAS *************/
Produto* criaProduto(int num_serie, double preco, char nome[64]) {
    Produto* prod = (Produto*)calloc(1, sizeof(Produto));
    prod->num_serie = num_serie;
    prod->preco = preco;
    strcpy(prod->nome, nome);

    return prod;
}

void destroiProduto(Produto** prod_ref) {
    Produto* prod = *prod_ref;

    if (prod != NULL) {
        free(prod);
        *prod_ref = NULL;
    }
}

No* criaNo(int num_serie, double preco, char nome[64]) {
    No* no = (No*)calloc(1, sizeof(No));
    no->prod = criaProduto(num_serie, preco, nome);
    no->prox = NULL;

    return no;
}

Lista* criaLista() {
    return ((Lista*)calloc(1, sizeof(Lista)));
}

void destroiLista(Lista** L) {
    Lista* L_aux = *L;

    // remove todos os nós da lista
    No* p = L_aux->inicio;
    while (p != NULL) {
        No* no = p;
        p = p->prox;
        destroiProduto(&no->prod);
        free(no);
    }
    free(L_aux);
    *L = NULL;
}

int listaEstaVazia(const Lista* L) {
    return (L->inicio == NULL);
}

void imprime(const Lista* L) {
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No* p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}

E main em outro arquivo, assim pode ter muitos programas de teste...

Spoiler


#include "outro.h"
int main()
{
    Produto um = { 0, "teste", 12.34F };
    Lista* L = criaLista();
    imprime(L);

    for (int i = 0; i < 10; i += 1) insereNoInicio(L, i, 0., "teste");
    imprime(L);
    Lista* invertida = inverter(L);
    imprime(invertida);

    return 0;
}

NhemonF · 13 de dezembro de 2020

**mensagem apagada**

arfneto · 13 de dezembro de 2020

Leia o que acrescentei agora e talvez entenda melhor o que está errado...

NhemonF · 13 de dezembro de 2020

@arfneto Ah!! Desculpe. Vou ler aqui

8 minutos atrás, arfneto disse:

Leia o que acrescentei agora e talvez entenda melhor o que está errado...

Agora entendi!!

Pelo que vi no seu código e o que eu escrevi bem no início do post, vi que equivoquei bastante em tentar inverter a ordem, como se fosse uma lista duplamente encadeada.

Tentei fazer esta possibilidade de uma lista simplesmente encadeada se tornar duplamente encadeada pelo método que fiz

Agora esclareceu bastante!!!

NhemonF · 14 de dezembro de 2020

@arfneto Queria agradecer pela ajuda e pelo tempo que você teve para me ajudar neste exercício. Desculpe pela minha lerdeza em pensar (que faz jus à foto do perfil)

arfneto · 14 de dezembro de 2020

3 horas atrás, NhemonF disse:

Pelo que vi no seu código e o que eu escrevi bem no início do post, vi que equivoquei bastante em tentar inverter a ordem, como se fosse uma lista duplamente encadeada

Não faria diferença a lista ter ponteiros para os dois lados nessa questão de inverter. Entenda que inserir no início de outra lista vai inverter a ordem naturalmente. É a natureza das coisas. Se você tira os caras de uma fila e põe no início de outra os últimos serão os primeiros. É só isso.

No geral uma lista duplamente encadeada é muito mais simples de programar e não o contrário. Tendo ponteiros só para um lado navegar é um inferno e qualquer coisa que queria fazer tem que voltar para o início (ou para o fim) e se reposicionar.

No futuro procure usar as coisas como te falei nesses posts, em especial em relação às estruturas de dados e a organização dos arquivos de programa. E scanf(). São erros comuns que tomam muito tempo.

Espero que tenha terminado o programa

NhemonF · 14 de dezembro de 2020

@arfneto Aproveitando esta deixa, poderia me ajudar um pouco mais no programa?

Eu sei que estou tomando muito do seu tempo, mas estou com dúvidas a respeito deste programa

Bom, agora pra ordenar de forma crescente e decrescente, de acordo com o número de série do produto, devo criar um ponteiro chamado "crescente", que seria o ponteiro de Lista e igualar a L. Certo?

E depois criar o nó *p, que vai apontar para o produto, e que por sua vez vai apontar para o número de série?

Como no código abaixo:

Lista *ordenar(const Lista *L, int ordem) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando em como fazer
    if (ordem == 0){
        Lista *Crescente = L;
        No *p = p->prod->num_serie;
      
      	while (p != NULL){
          	insereNoInicio(Crescente, p->prod->num_serie, p->prod->preco, p->prod->nome);
          	p->prod->num_serie = p->prox;
        }
    }
}

arfneto · 14 de dezembro de 2020

@NhemonF abra um tópico sobre inserção ordenada em listas ligadas.

Na prática quando você insere dados numa estrutura dessas você quer inserir mesmo em uma certa ordem de chave e nem sempre como uma simples fila com os elementos em ordem de entrada. E quando vai usar a ordem de entrada em geral insere no fim para manter a abstração de fila FIFO e não como em geral na pilha LIFO

Mas pode querer vários critérios para a mesma lista: um acesso por ordem de número de série ou CPF do comprador ou CEP de entrega por exemplo. Afinal os dados são os mesmos e essa é a vantagem de ter um computador afinal.

Uma função assim é central:

Lista*      _inserir_na_ordem(void*, Lista*, int(*)(void*, void*));

onde você passa a função de comparação. Se os índices existem desde o início da lista, basta adaptar a inserção e criar as listas de ponteiros. Mas é preciso ter uma função que reconstrói os índices, e é essa que você vai usar.

Abra outro tópico. Isso pode interessar a outros e aqui enterrado no tópico #21 vai ficar difícil de achar