Lista com descritor (continuação)
Rotina para remover o primeiro elemento de uma LLSECD:
char removeInicioLLSECD(TDescritor *l, TInfo val) {
PNo p;
if (l->qtd==0)
return 0;
else {
p = l->prim;
l->prim=p->prox;
if (l->qtd==1)
l->ult = NULL;
l->qtd--;
strcpy(val, p->info);
free(p);
return 1;
}
}
Rotina para remover o último nó da lista:
char removeUltimoLLSECD(TDescritor *l, TInfo val) {
PNo p, q;
if (l->qtd==0)
return 0;
else {
p = l->prim;
while (p->prox) {
q = p;
p = p->prox;
}
l->qtd--;
val = p->info;
if (l->qtd==0) {
l->prim = NULL;
l->ult = NULL;
} else {
l->ult = q;
q->prox = NULL;
}
free(p);
return 1;
}
}
1
Listas Lineares Duplamente Encadeada (LLDE)
Lista
Maria
José
Pedro
Nas listas com descritores vistas anteriormente a operação de remoção do último nó apresenta a
necessidade de percorrer os nós seqüencialmente, a partir do primeiro elemento, até chegarmos ao
penúltimo nó.
Para se evitar esse percurso, é possível estruturar uma lista de forma que possa ser percorrida em
ambos os sentidos (do início até o fim e do fim até o início). Uma organização implementando esse
tipo de percurso é denominada lista duplamente encadeada.
Esquematicamente podemos representar uma Lista Linear Duplamente Encadeada (LLDE) como:
prim
qtd
ult
3
Maria
José
Pedro
Cada nó de uma lista desse tipo possui pelo menos três campos. Um campo ponteiro indicando o
próximo nó, outro ponteiro indicando o nó anterior e o terceiro campo contendo os dados.
Os tipos em C para manter uma LLDECD podem ser definidos como:
typedef
struct TNo *PNo;
struct TNo {
TInfo info;
PNo esq, dir;
};
typedef
struct {
PNo prim, ult;
int qtd;
} TDescritor;
TDescritor lista;
Iniciação de uma LLDECD:
void iniciaLLDECD(TDescritor *l) {
l->prim=l->ult=NULL;
l->qtd=0;
};
Inserção de um nó no início da lista:
void insereInicioLLDECD(TDescritor *l, TInfo val) {
PNo p;
p = (PNo)malloc(sizeof(TNo));
strcpy(p->info, val);
p->esq = NULL;
p->dir = l->prim;
if (l->qtd==0)
l->ult=p;
else
l->prim->esq = p;
l->prim = p;
l->qtd++;
}
2
Exercícios:
Responda: numa representação de uma LLDE sempre é possível se dizer que: p é igual a
p->dir->esq e é igual a p->esq->dir.?
Faça uma rotina para inserir um nó no fim da lista usando LLDECD.
Rotina para remover o primeiro nó da lista:
char removeInicioLLDECD(TDescritor *l, TInfo val) {
PNo p;
if (l->qtd==0)
return 0;
else {
p = l->prim;
l->prim = p->dir;
l->qtd--;
if (l->qtd==0)
l->ult = NULL;
else
l->prim->esq = NULL;
strcpy(val, p->info);
free(p);
return 1;
}
}
Trecho da inclusão de um nó entre dois nós (o nó antes do ponto de inclusão é indicado pelo
ponteiro q):
p=(PNo)malloc(sizeof(TNo));
p->esq = q;
p->info = val;
// atribuição genérica, qualquer tipo
p->dir = q->dir;
q->dir = p;
p->dir->esq = p;
Trecho para excluir um nó entre dois outros (o nó a ser excluído é indicado pelo ponteiro p):
p->esq->dir = p->dir;
p->dir->esq = p->esq;
val = p->info;
free(p);
Remoção do último nó da lista:
char removeUltimoLLDECD(TDescritor *l, TInfo val) {
PNo p;
if (l->qtd==0)
return 0;
else {
p = l->ult;
l->ult = p->esq;
l->qtd--;
if (l->qtd==0)
l->prim = NULL;
else
l->ult->dir = NULL;
strcpy(val, p->info);
free(p);
return 1;
}
}
Obs.: note que na rotina acima não há mais a necessidade de se percorrer a lista desde o início para
se encontrar o penúltimo nó.
3
Listas Circulares Duplamente Encadeadas com Descritor (LCDECD)
Neste tipo de lista o campo dir do último nó indica o endereço do primeiro nó e o campo da esq do
primeiro nó contém o endereço do último nó.
O descritor para este tipo de lista tem o seguinte formato:
typedef
char TInfo[30];
typedef
struct TNo *PNo;
struct TNo {
TInfo info;
PNo esq, dir;
};
typedef
struct {
PNo prim;
int qtd;
} TDescritor;
TDescritor lista;
Note acima que não há necessidade do campo ult.
Inicia uma LCDECD vazia:
void iniciaLLDECD(TDescritor *l) {
l->prim=NULL;
l->qtd=0;
}
prim
qtd
0
Representação de LCDECD com apenas um nó:
prim
qtd
1
Representação de LCDECD com três nós:
prim
qtd
3
Maria
José
Pedro
4
Exercícios:
1. Crie as rotinas para manipular LCDECD.
2. Polinômios podem ser representados por listas, cujos nós são registros com 3 campos:
coeficiente, expoente e referência ao nó seguinte. Por exemplo, o polinômio 3x5+2x+1 pode
ser representado por:
Poli1
3
5
2
1
1
0
Crie uma rotina para ler um polinômio em uma lista a partir do teclado.
Crie uma rotina que some dois polinômios.
Crie uma rotina para multiplicar dois polinômios.
3. Faça um programa que leia um arquivo texto e carregue cada linha em um nó de uma lista
linear duplamente encadeada com descritor. Após o arquivo estar completamente lido, as
teclas “s” (sobe) e “d” (desce) do teclado podem ser usadas para mostrar uma linha do texto
armazenado na lista. A tecla “s” serve para mostrar a linha acima da linha atualmente sendo
apresentada, a tecla “d” mostra a abaixo da linha atual.
Veja abaixo a representação de uma lista desse tipo criada a partir de um arquivo com três
linhas de texto. Considere que o tamanho máximo de cada linha de texto é de 250 caracteres.
Para ler as setas
Linha 1 do arquivo
Linha 2
Última linha
5