58404724 TI listas em C

Prévia do material em texto

MC202 – Estruturas de Dados
Aulas 4–7: Listas Ligadas
Felipe P.G. Bergo
1 Listas Generalizadas
E´ muitas vezes deseja´vel armazenar uma sequ¨eˆncia de elementos em alguma ordem espec´ıfica, em
algum tipo de lista. Operac¸o˜es naturais sobre listas sa˜o:
• Inserir um novo elemento (no fim, no in´ıcio, em algum ponto espec´ıfico).
• Buscar por um determinado valor.
• Obter o n-e´simo elemento da lista.
• Remover um elemento da lista.
• A partir de um elemento, obter o pro´ximo elemento, ou o elemento anterior.
• Apagar toda a lista.
• Obter o primeiro ou o u´ltimo elemento da lista.
• Obter o nu´mero de elementos da lista.
• Percorrer todos os elementos da lista, do primeiro para o u´ltimo ou vice-versa.
Embora seja poss´ıvel realizar todas estas operac¸o˜es sobre um vetor, algumas delas tornam-se ine-
ficientes devido a` necessidade de manter os elementos em um espac¸o cont´ıguo de memo´ria. Listas
ligadas sa˜o uma soluc¸a˜o em geral mais eficiente para a implementac¸a˜o de listas.
2 Listas Ligadas
Uma lista ligada e´ uma colec¸a˜o de no´s que podem ser alocados em regio˜es na˜o cont´ıguas de memo´ria.
Cada no´ mantem uma ou mais refereˆncias (ponteiros) que indicam onde esta˜o localizados os no´s
relacionados (pro´ximo no´, no´ anterior).
Podemos nos referenciar a uma lista ligada atrave´s de seu primeiro no´. Entretanto, toda vez que
realizarmos uma inserc¸a˜o no in´ıcio da lista teremos que garantir que todas as partes do programa
que referenciam a lista tenha suas refereˆncias atualizadas. Para evitar este problema, e´ comum
usar um no´ especial, chamado no´-cabec¸a, e´ um ponteiro para o primeiro elemento da lista.
1
2.1 Lista Simplesmente Ligada
Nesta sec¸a˜o comentamos a implementac¸a˜o em C de uma lista simplesmente ligada com no´ cabec¸a.
Precisamos de dois tipos de dados: um tipo No´, que representa cada elemento da lista ligada, e um
tipo Lista que contem um ponteiro para o no´ cabec¸a:
typedef struct Noh {
int dado; // o dado poderia ser de qualquer tipo
struct Noh *prox; // ponteiro para proximo elemento
} Noh;
typedef struct Lista {
Noh *cabeca;
} Lista;
As operac¸o˜es ba´sicas sobre a estrutura sa˜o a criac¸a˜o de listas e de no´s. Ambas as operac¸o˜es levam
tempo constante, O(1):
Lista * lista_cria() {
Lista *L;
L = (Lista *) malloc(sizeof(Lista));
L->cabeca = NULL;
return L;
}
Noh * noh_cria(int dado) {
Noh *N;
N = (Noh *) malloc(sizeof(Noh));
N->dado = dado;
N->prox = NULL;
return N;
}
Ao contra´rio dos vetores, onde acessamos qualquer elemento usando um ı´ndice nume´rico, com uma
lista temos apenas acesso sequ¨eˆncial: para chegar no de´cimo elemento temos que passar por todos
os nove elementos anteriores. Para percorrer uma lista, precisamos obter seu primeiro elemento e
enta˜o obtemos os elementos subsequ¨entes seguindo os ponteiros de pro´ximo elemento em cada no´.
Estas duas operac¸o˜es tambe´m levam tempo constante.
Noh *lista_primeiro(Lista *L) {
return(L->cabeca);
}
Noh *lista_proximo(Noh *N) {
return(N->prox);
}
2
Andar para tra´s em uma lista simplesmente ligada na˜o e´ ta˜o simples, requer que a lista seja
percorrida desde o in´ıcio verificando se, para cada elemento x, proximo(x) e´ o elemento do qual
procuramos o elemento anterior. A operac¸a˜o leva tempo O(n) em uma lista com n elementos.
Noh *lista_anterior(Lista *L,Noh *N) {
Noh *p;
if (N == L->cabeca) return NULL;
p = lista_primeiro(L);
while(lista_proximo(p)!=NULL) {
if (lista_proximo(p) == N)
return p;
p = lista_proximo(p);
}
return NULL;
}
Obter o u´ltimo elemento tambe´m requer que toda a lista seja percorrida:
Noh *lista_ultimo(Lista *L) {
Noh *p;
p = lista_primeiro(L);
if (p==NULL) return NULL;
while(lista_proximo(p)!=NULL)
p = lista_proximo(p);
return p;
}
Podemos querer 3 tipos de inserc¸o˜es em uma lista: no in´ıcio, no fim ou em uma posic¸a˜o arbitra´ria
no meio. Na lista simplesmente ligada a inserc¸a˜o no in´ıcio e´ trivial: Fazemos o pro´ximo do novo
elemento apontar para o primeiro elemento da lista e fazemos com que o novo elemento seja o
primeiro elemento (cabec¸a) da lista. A inserc¸a˜o em posic¸a˜o arbitra´ria pode ser feita em tempo
constante se tivermos um ponteiro para o elemento que sera´ o elemento anterior ao novo elemento:
void lista_insere_apos(Noh *novo, Noh *anterior) {
novo->prox = anterior->prox;
anterior->prox = novo;
}
A inserc¸a˜o no final da lista exige que encontremos seu u´ltimo elemento, o que leva tempo O(n). A
remoc¸a˜o de um elemento arbitra´rio requer que encontremos o elemento anterior ao removido, o que
leva tempo O(n). A operac¸a˜o de remoc¸a˜o fica assim:
void lista_remove(Lista *L, Noh *N) {
3
Noh *p;
if (N == L->cabeca) {
L->cabeca = N->prox;
} else {
p = lista_anterior(L,N);
if (p!=NULL)
q->prox = p->prox;
}
noh_destroi(N); // desaloca o no’ removido
}
Para desalocar no´s e listas temos as 3 operac¸o˜es abaixo.
void noh_destroi(Noh *N) {
free(N);
}
void noh_destroi_recursivo(Noh *N) {
if (N->prox != NULL) noh_destroi_recursivo(N->prox);
noh_destroi(N);
}
void lista_destroi(Lista *L) {
if (L->cabeca != NULL) noh_destroi_recursivo(L->cabeca);
free(L);
}
A busca de um dado dentro de uma lista ligada leva tempo O(n) (pode ser necessa´rio percorrer
todos os elementos), e a obtenc¸a˜o do x-e´simo elemento leva tempo Θ(x) (e´ necessa´rio percorrer a
lista desde o in´ıcio ate´ o elemento desejado).
2.2 Listas Circulares Duplamente Ligadas
A lista simplesmente ligada e´ ineficiente quando precisamos acessar o final da lista ou obter o
elemento anterior. Estes dois problemas podem ser resolvidos pela lista duplamente ligada circular.
Nesta lista, cada no´ tem um apontador para o pro´ximo elemento e para o elemento anterior. Ale´m
disso, o primeiro elemento aponta para o u´ltimo como seu “anterior”, e o u´ltimo elemento aponta
para o primeiro como seu “pro´ximo”. Sabemos onde a lista comec¸a atrave´s do apontador cabec¸a,
que indica o primeiro elemento. As definic¸o˜es de tipos para a Lista Duplamente Ligada Circular
(LDLC) ficam assim:
typedef struct LdlNoh {
int dado;
struct LdlNoh *ant, *prox;
4
} LdlNoh;
typedef struct {
LdlNoh *cabeca;
} LDLC;
As operac¸o˜es para obter o elemento anterior e o u´ltimo elemento ficam triviais, O(1), bastando
seguir o ponteiro ant e pegar o elemento anterior ao primeiro, respectivamente. A lista duplamente
ligada circular exige, entretanto, alguns cuidados especiais: como o u´ltimo elemento tem o ponteiro
de pro´ximo elemento apontando para o primeiro, e´ preciso tomar cuidado para na˜o percorrer a lista
em c´ırculos. Abaixo mostramos um exemplo de como percorrer uma LDLC, implementando uma
operac¸a˜o de busca:
LdlNoh * ldlc_busca(LDLC *L, int dado) {
LdlNoh *p;
p = ldlc_primeiro(L); // p = L->cabeca;
if (p==NULL) return NULL;
do {
if (p->dado == dado)
return p;
p = ldlc_proximo(p);
} while(p!=ldlc_primeiro(L));
return NULL;
}
Ao realizar inserc¸o˜es e remoc¸o˜es tambe´m e´ preciso tomar cuidado para “costurar” os ponteiros
afetados de forma adequada. A func¸a˜o C abaixo implementa a inserc¸a˜o apo´s um no´ arbitra´rio:
void ldlc_insere_apos(LDLC *L, LdlNoh *novo, LdlNoh *onde) {
novo->ant = onde;
novo->prox = onde->prox;
novo->ant->prox = novo;
novo->prox->ant = novo;
}
Com a LDLC conseguimos realizar todas as operac¸o˜es, exceto busca e acesso aleato´rio, em tempo
constante. O prec¸o pago por esta performance e´ o gasto de memo´ria com o ponteiro adicional para
o elemento anterior. Em um PC comum, se utilizarmos uma LDLC para armazenar apenas um
inteiro em cada no´ de lista, estamos usando 12 bytes por no´, 4 para o dado e 8 para os ponteiros.
Isto significa que 66% da memo´ria sera´ usada apenas para manter a estrutura, e na˜o para os dados
em si.
5
3 Performance
Na tabela abaixo comparamos a performanceassinto´tica de tempo para operac¸o˜es sobre listas em
treˆs estruturas de dados: vetores, lista simplesmente ligada (LSL) e LDLC.
Operac¸a˜o Vetor LSL LDLC
Criac¸a˜o O(1) O(1) O(1)
Destruic¸a˜o O(1) O(N) O(N)
Obter x-e´simo Elemento O(1) O(N) O(N)
Obter Primeiro Elemento O(1) O(1) O(1)
Obter U´ltimo Elemento O(1) O(N) O(1)
Obter Pro´ximo Elemento O(1) O(1) O(1)
Obter Elemento Anterior O(1) O(N) O(1)
Busca O(N) O(N) O(N)
Inserc¸a˜o (In´ıcio) O(N) O(1) O(1)
Inserc¸a˜o (Meio) O(N) O(N) O(1)
Inserc¸a˜o (Fim) O(1) O(N) O(1)
Remoc¸a˜o O(N) O(N) O(1)
Listas ligadas gastam um pouco mais de memo´ria que vetores, mas permitem inserc¸o˜es e remoc¸o˜es
mais eficientes. Em conjuntos dinaˆmicos de dados, em que sa˜o realizadas muitas inserc¸o˜es e
remoc¸o˜es, listas ligadas sa˜o mais vantajosas que vetores. Em algumas arquiteturas de computadores
a fragmentac¸a˜o de uma grande lista como va´rios no´s na˜o cont´ıguos na memo´ria principal pode ser
uma vantagem. A grande vantagem de vetores sobre listas ligadas e´ o acesso aleato´rio (obter o
x-e´simo elemento) em tempo constante.
Para melhorar a performance da busca e´ necessa´rio manter os dados ordenados dentro da estrutura.
Em um vetor ordenado podemos realizar buscas em tempo O(logN). A busca bina´ria exige acesso
aleato´rio, e na˜o e´ diretamente aplica´vel a listas ligadas. Para realizar buscas ra´pidas em estruturas
ligada utilizaremos a´rvores de busca, que sera˜o apresentadas em aulas futuras.
4 Exemplo: Representac¸a˜o de Polinoˆmios
Listas ligadas sa˜o uma forma comum para a representac¸a˜o de polinoˆmios. Podemos usar uma LDLC
para representar um polinoˆmio mantendo cada termo em um no´ da lista. Neste caso, cada no´ tera´
duas informac¸o˜es: o coeficiente e e o expoente. Uma opc¸a˜o que melhora a performance na soma
de termos e facilita a impressa˜o do polinoˆmio e´ manter os no´s em ordem crescente de expoente.
Temos, enta˜o, as estruturas da lista definidas da seguinte forma:
typedef struct Termo {
float coef, expo;
struct Termo *prox, *ant;
} Termo;
6
typedef struct {
Termo *cabeca;
} Poly;
A operac¸a˜o essencial e´ a adic¸a˜o de um termo a um polinoˆmio existente: procuramos um termo
com o mesmo expoente. Se houver, apenas somamos os coeficientes. Sena˜o, adicionamos um novo
termo na posic¸a˜o adequada da lista.
void poly_soma_termo(Poly *P, float coef, float expo) {
Termo *t,*u,*s;
t = poly_primeiro(P);
if (t==NULL || t->expo > expo) {
u = termo_cria(coef,expo);
poly_insere_inicio(P,u);
} else {
while(t->expo < expo) {
t = poly_proximo(t);
if (t == poly_primeiro(P)) break;
}
if (t->expo == expo) {
t->coef = t->coef + coef;
} else {
u = termo_cria(coef,expo);
s = poly_ultimo(P);
if (expo > s->expo) {
poly_insere_fim(P,u);
} else {
t = poly_anterior(t);
poly_insere_apos(P,u,t); // insere u apos t
}
}
}
}
E podemos usar esta operac¸a˜o para realizar a soma de polinoˆmios. Para realizar P1 = P1 + P2
basta percorrer P2 e somar cada um de seus termos a P1:
void poly_soma(Poly *P1, Poly *P2) {
Termo *t;
t = poly_primeiro(P2);
if (t==NULL) return;
do {
poly_soma_termo(P1,t->coef,t->expo);
t = poly_proximo(t);
} while(t!=poly_primeiro(P2));
}
7
A multiplicac¸a˜o de dois polinoˆmios pode ser realizada com a seguinte func¸a˜o:
Poly *poly_mult(Poly *P1, Poly *P2) {
Termo *t1, *t2;
Poly *P3;
P3 = poly_cria();
if (poly_primeiro(P1)==NULL || poly_primeiro(P2)==NULL) return P3;
t1 = poly_primeiro(P1);
do {
t2 = poly_primeiro(P2);
do {
poly_soma_termo(P3,(t1->coef)*(t2->coef),(t1->expo)+(t2->expo));
t2 = poly_proximo(t2);
} while(t2 != poly_primeiro(P2));
t1 = poly_proximo(t1);
} while(t1 != poly_primeiro(P1));
return P3;
}
8