9. Listas Ligadas

Uma lista ligada armazena elementos de forma que vizinhos possam estar localizados em posições não adjacentes na memória:

Em uma lista ligada:

A ordem dos elementos na lista é dada através de apontadores. O primeiro elemento da lista é apontado pelo início. Cada célula da lista tem o seguinte aspecto:

struct celula {
    TipoDaLista info;
    struct celula *prox;
}
typedef struct celula *apontador;

9.1. Implementação

Faça uma função que recebe uma lista ligada com números inteiros apontada por início e imprime os números.

Anexo: listaligada.c

9.2. Aplicação

Representação de polinômios usando listas ligadas.

Considere um polinômio de coeficientes reais:

\[p(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n\]

Exemplo:

\[p(x) = 3.5 - 7x^{14} + 3.14x^{123} - 0.3x^{1279}\]

Como representar um polinômio no computador?

Ideia 1: usando um vetor colocando no índice \(i\) o coeficiente do termo de grau \(i\).

Essa representação como desvantagem o desperdício de espaço caso o polinômio seja esparso, ou seja, ele tenha poucos coeficientes não nulos.

Ideia 2: lista ligada com os elementos não nulos do polinômio. Cada célula da lista ligada guarda o grau e o coeficiente não nulo do termo. Vamos considerar que os termos estão ordenados em ordem crescente de grau:

typedef struct cel {
    float coef;
    int expo;
    struct cel *prox;
} celula;
typedef celula *polinomio;

float avalia(polinomio p, float x) {
   /* devolve p(x) */
   float resultado = 0.0;
   polinomio ap = p;

   while (ap != NULL) {
      resultado += ap->coef * pow(x, ap->expo);
      ap = ap->prox;
   }

   return resultado;
}

Se eu tenho um polinômio de grau máximo \(k\), \(m\) termos não nulos, o número de somas é \(n\) e o tempo para todos as operações de exponenciação é \(k\).

Na representação por vetor é proporcional ao grau máximo.

Exercício: soma de polinômios.

polinomio criacelula(float c, int e) {
    polinomio novo = malloc(sizeof(celula));
    novo->coef = c;
    novo->expo = e;
    novo->prox = NULL;
    return novo;
}

polinomio soma(polinomio p, polinomio q) {
    polinomio soma = NULL, ult = NULL, ap = p, aq = q, novo;
    while (ap != NULL && aq != NULL) {
        if (ap->expo < aq->expo) {
            novo = malloc(sizeof(celula));
            novo->coef = ap->coef;
            novo->expo = ap->expo;
            ap = ap->prox;
        }
        else if (ap->expo < ap->expo) {
            novo = criacelula(aq->coef, aq->expo);
            aq = aq->prox;
        }
        else {
            if (ap->coef + aq->coef != 0.0) {
                // nunca vai dar zero devido a problemas de representacao.
                // precisa estar em modulo epsilon.
                novo = criacelula(ap->coef + aq->coef, ap->expo);
                ap = ap->prox;
                aq = aq->prox;
            }
        }

        if (novo != NULL)
            if (soma == NULL)
                soma = ult = novo;
            else {
                ult->prox = novo;
                ult = novo;
            }
    }

    while (ap != NULL) {
        novo = criacelula(ap->coef, ap->expo);
        ap = ap->prox;
        if (soma == NULL)
            soma = ult = novo;
        else {
            ult->prox = novo;
            ult = novo;
        }
    }

    while (aq != NULL) {
        novo = criacelula(aq->coef, aq->expo);
        aq = aq->prox;
        if (soma == NULL)
            soma = ult = novo;
        else {
            ult->prox = novo;
            ult = novo;
        }
    }
}