/*
* EXPLICAÇÃO DETALHADA DO PROGRAMA
* Este programa implementa um Gerenciador de Lista de Compras utilizando uma
* **Lista Duplamente Encadeada** (Doubly Linked List).
*
* DIFERENÇAS PARA A LISTA ESTÁTICA:
* - Memória Dinâmica: Os itens são alocados em tempo de execução (malloc),
* permitindo um número teoricamente ilimitado de itens (até a memória acabar).
* - Eficiência: A inserção e remoção são eficientes pois não exigem deslocar
* todos os outros elementos (como em arrays), apenas ajustar os ponteiros.
* - Dupla Ligação: Cada nó possui ponteiros para o próximo (`next`) e para o
* anterior (`previous`), permitindo navegação em ambas as direções.
*
* FUNCIONALIDADES:
* 1. Inserção (I): Insere produtos mantendo a ordem alfabética. Ajusta os
* ponteiros `next` e `previous` dos vizinhos para manter a integridade da lista.
* 2. Impressão (P):
* - 'F': Imprime do início (head) até o fim (tail).
* - 'R': Imprime do fim (tail) até o início (head), facilitando visualizar
* os últimos itens adicionados sem percorrer toda a lista.
* 3. Atualização (A): Marca um item como comprado.
* 4. Exclusão (X): Remove um item e libera a memória corretamente, ajustando
* os ponteiros dos nós vizinhos e os ponteiros `head` ou `tail` da lista se necessário.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MEMORY_ERROR 2
#define EXEC_SUCCESS 0
// Estrutura do Nó da Lista Duplamente Encadeada
struct ListNode
{
char *productName; // Ponteiro para string dinâmica (nome do produto)
float quantity; // Quantidade do item
int isBought; // Flag (0=não, 1=sim) indicando se foi comprado
struct ListNode *next; // Ponteiro para o próximo nó
struct ListNode *previous; // Ponteiro para o nó anterior
};
typedef struct ListNode TItem;
// Descritor da Lista Duplamente Encadeada
typedef struct {
TItem *head; // Ponteiro para o início da lista
TItem *tail; // Ponteiro para o final da lista
int count; // Contador total de itens
int boughtCount; // Contador de itens comprados
} TList;
// Protótipos das funções
int UpdateItem(TList *, char []);
int DeleteItem(TList *, char []);
int InsertItem(TList *, char [], float );
void PrintListForward(TList *);
void PrintListReverse(TList *);
void InitializeList(TList *);
int main(void)
{
TList list;
char operation = '.';
char productName[25];
float productQuantity;
TItem *aux;
// Inicializa a lista vazia
InitializeList(&list);
// Loop principal de comandos até o operador '*'
while(operation != '*') {
scanf(" %c", &operation);
if(operation != '*') {
scanf("%24s", productName);
// Se for inclusão, lê a quantidade também
if(operation == 'I')
scanf("%f", &productQuantity);
}
switch(operation) {
case 'I':
// Insere o novo item e imprime confirmação
InsertItem(&list, productName, productQuantity);
printf("Incluiu %s \n", productName);
productQuantity = 0;
break;
case 'P':
// Verifica o argumento para definir o sentido da impressão
if(strcmp("R", productName) == 0)
PrintListReverse(&list);
else if(strcmp("F", productName) == 0)
PrintListForward(&list);
break;
case 'A':
// Marca o item como comprado se existir
if(UpdateItem(&list, productName))
printf("Comprou %s \n", productName);
break;
case 'X':
// Remove o item da lista
if (DeleteItem(&list, productName))
printf("Excluiu %s\n", productName);
break;
case '*':
// Exibe resumo final e encerra
printf("Fim do programa ( %d itens sem comprar)\n", list.count - list.boughtCount);
break;
default:
printf("Operacao invalida.\n");
}
}
return EXEC_SUCCESS;
}
// Inicializa os ponteiros e contadores da lista
void InitializeList(TList *list)
{
list->head = NULL;
list->tail = NULL;
list->count = 0;
list->boughtCount = 0;
}
// Função para inserir um novo item mantendo a ordem alfabética (Inserção Ordenada)
int InsertItem(TList *list, char productName[], float quantity)
{
TItem *newNode, *previousNode, *currentNode;
// Aloca memória para o novo nó
newNode = (TItem *) malloc(sizeof(TItem));
if (newNode == NULL){
puts("Erro fatal: Memoria insuficiente para esta operacao");
return MEMORY_ERROR;
}
// Aloca e copia a string do nome (strdup faz malloc + strcpy)
newNode->productName = strdup(productName);
newNode->quantity = quantity;
newNode->isBought = 0;
list->count++;
// Caso 1: Lista Vazia -> O novo nó é o head e o tail
if (list->head == NULL) {
list->head = newNode;
list->tail = newNode;
newNode->previous = NULL;
newNode->next = NULL;
}
else {
// Percorre a lista para encontrar a posição alfabética correta
previousNode = NULL;
currentNode = list->head;
while (currentNode != NULL && strcmp(currentNode->productName, productName) < 0)
{
previousNode = currentNode;
currentNode = currentNode->next;
}
// Caso 2: Inserção no Meio ou Início
if (currentNode != NULL)
{
// Subcaso 2a: Inserção no Início (antes do head atual)
if (previousNode == NULL) {
list->head = newNode;
currentNode->previous = newNode;
newNode->next = currentNode;
newNode->previous = NULL;
}
// Subcaso 2b: Inserção no Meio (entre previousNode e currentNode)
else {
currentNode->previous = newNode;
previousNode->next = newNode;
newNode->next = currentNode;
newNode->previous = previousNode;
}
}
// Caso 3: Inserção no Final (currentNode chegou ao fim/NULL)
else
{
list->tail->next = newNode;
newNode->previous = list->tail;
list->tail = newNode;
newNode->next = NULL;
}
}
return TRUE;
}
// Marca um item como comprado
int UpdateItem(TList *list, char productName[])
{
TItem *currentNode, *previousNode;
previousNode = NULL;
currentNode = list->head;
// Busca linear pelo produto
while (currentNode != NULL && strcmp(currentNode->productName, productName) != 0)
{
previousNode = currentNode;
currentNode = currentNode->next;
}
// Se não encontrou
if (currentNode == NULL) {
printf("Produto '%s' nao encontrado\n", productName);
return FALSE;
}
// Se já foi comprado
if (currentNode->isBought == 1) {
printf(" %s ja foi comprado \n ", productName);
return FALSE;
}
else
{
// Marca e atualiza o contador
list->boughtCount = list->boughtCount + 1;
currentNode->isBought = 1;
}
return TRUE;
}
// Imprime a lista do início (head) para o fim (tail) - Ordem Alfabética
void PrintListForward(TList *list)
{
TItem *currentNode;
if (list->head == NULL)
puts("Lista vazia");
else
{
printf("\n Lista de compras (do inicio) \n");
currentNode = list->head;
while (currentNode != NULL)
{
printf("%s %.2f %d \n", currentNode->productName, currentNode->quantity, currentNode->isBought);
currentNode = currentNode->next;
}
printf("Total itens: %d Itens comprados: %d\n\n", list->count, list->boughtCount);
}
}
// Imprime a lista do fim (tail) para o início (head) - Ordem Reversa
void PrintListReverse(TList *list)
{
TItem *currentNode;
if (list->head == NULL)
puts("Lista vazia");
else
{
printf("\n Lista de compras (do final) \n");
currentNode = list->tail; // Começa pelo final
while (currentNode != NULL)
{
printf("%s %.2f %d \n", currentNode->productName, currentNode->quantity, currentNode->isBought);
currentNode = currentNode->previous; // Anda para trás usando o ponteiro previous
}
printf("Total itens: %d | Itens comprados: %d\n\n", list->count, list->boughtCount);
}
}
// Remove um item da lista e ajusta os ponteiros da lista duplamente encadeada
int DeleteItem(TList *list, char productName[])
{
TItem *currentNode, *previousNode;
previousNode = NULL;
currentNode = list->head;
// Busca o item a ser removido
while (currentNode != NULL && strcmp(currentNode->productName, productName) != 0)
{
previousNode = currentNode;
currentNode = currentNode->next;
}
// Se não encontrou
if (currentNode == NULL){
printf("Valor informado nao existe na lista\n");
return FALSE;
}
else
{
// Ajuste dos ponteiros vizinhos para remover o nó
// Caso 1: Remoção do Início
if (previousNode == NULL) {
list->head = currentNode->next;
if(list->head != NULL)
currentNode->next->previous = NULL;
}
// Caso 2: Remoção do Meio ou Fim
else {
previousNode->next = currentNode->next;
// Se não é o último item, ajusta o ponteiro 'previous' do próximo
if(currentNode->next != NULL) {
currentNode->next->previous = previousNode;
}
}
// Atualiza contadores
list->count = list->count - 1;
if (currentNode->isBought == 1)
list->boughtCount--;
// Se o item removido era o último, atualiza o ponteiro tail
if (currentNode == list->tail)
list->tail = previousNode;
// Libera a memória do nó e da string do nome
free(currentNode->productName);
free(currentNode);
}
return TRUE;
}
