Estrutura de Dados

Alocação Estática de Memória – Listas

Conceito:

São estruturas que permitem representar um conjunto de dados de forma a

preservar a relação de ordem linear entre eles. Uma lista linear é composta de nós

que podem conter tanto tipos de dados primitivos quanto construídos.

Operações:

As operações mais comuns efetuadas sobre os dados contidos em uma lista linear

são:

acessar determinado nó da lista;

inserir um nó em determinada posição da lista;

remover determinado nó da lista;

determinar o número de nós de uma lista;

localizar determinado dado dentro da lista;

Classificações:

Resumidamente, as seguintes variações de listas lineares podem ser consideradas:

lista linear seqüencial (ou contígua)

lista linear simplesmente ligada (ou encadeada)

lista linear duplamente ligada (ou encadeada)

lista linear seqüencial ou ligada com disciplina de acesso LIFO (pilha)

lista linear seqüencial ou ligada com disciplina de acesso FIFO (fila)

Lista Linear Seqüencial (ou contíguas)

Representação:

1 2 3 4 5 6 7 8 ... n-1 n

Características:

são implementadas através de variáveis estáticas;

o acesso aos seus componentes é feito de maneira direta (através de um índice,

por exemplo);

as estruturas de representação que melhor permitem a implementação de listas

lineares seqüênciais (ou contíguas) são os vetores (arrays).

Vantagens:

Além de todas as vantagens inerentes a manipulação de variáveis estáticas,

também têm como característica marcante o fato de poderem ser implementadas

em praticamente todas as linguagens de programação mais utilizadas (C, Pascal,

COBOL, Fortran, Clipper etc).

Estrutura de Dados

Desvantagens:

Todas as desvantagens inerentes a manipulação de variáveis estáticas, como por

exemplo, a necessidade de se prefixar seu tamanho inicial, a impossibilidade de se

redimensionar este tamanho pré-fixado em tempo de execução, a dificuldade em se

realizar sobre ela certas operações (inserção e remoção, por exemplo) etc..

Ex.: para a lista lineares seqüencial abaixo, que contém uma lista de nomes

arranjados em ordem alfabética, a inclusão de um novo nome (Benedito, por

exemplo), acarretaria a necessidade de se rearranjar todos os nomes a partir de

Carlos, para poder abrir espaço para a inclusão do novo nome.

1

2

3

4

5

6

7

8

9

10

11

12

13

....

n-1

n

Aarão

Carlos

Célia

Dalva

Elídio

Fábio

Francisco

Gustavo

Hélio

Iria

José

Joaquim

Kátia

Zulmira

Zaqueu

Após a inclusão do novo nome, novas inclusões seriam impossíveis, visto que não

mais haveria espaço disponível para tanto.

Principais Operações em Listas:

As principais operações são:

Inserção: no início ou final da Lista;

Remoção: no início ou final da Lista;

Impressão

Pesquisa

Implementação de Listas em Vetor

Como as listas lineares podem ser representadas em C? Como uma lista é apenas

um conjunto de nós, um vetor de nós é uma idéia imediata.

Inserção no Final da Lista

Dado o vetor de nome valor abaixo com capacidade para 10 posições para

inteiros, a inserção pelo final, será realizada a seguinte forma:

i = 0 1 2 3 4 5 6 7 8 9

valor

Estrutura de Dados

Ao inserir um elemento inteiro 10 pelo final do vetor valor, como o mesmo se

encontra vazio, o elemento irá ocupar a posição referente ao índice 0 do vetor.

Essa posição passa a ser a primeira e a última posição do vetor. Um próximo

elemento inteiro 20 a ser inserido irá ocupar a posição 1 do vetor. O elemento

seguinte irá ocupar a posição 2 do vetor e assim por diante até o vetor ter todas as

suas posições preenchidas.

Suponha a inserção dos elementos: 10, 20, 30, 40, 50 e 60 nesta ordem. A lista

ficará representada conforme a figura abaixo:

Conforme o vetor acima, a próxima posição livre é a posição 6 do vetor valor,

sendo assim o próximo elemento deverá ser inserido nessa posição e a última

posição livre do vetor passará a ser a posição 7.

Remoção no Final da Lista

A Remoção pelo Final da Lista, deve acontecer pela última posição do vetor valor

que possui elemento. De acordo com o vetor valor, a última posição com elemento

é a posição 6, logo, o elemento a ser removido pelo final do vetor, é o elemento

que ocupa esta posição, sendo o elemento 70. Após o elemento 70 ser removido, o

último elemento do vetor passa a ser o elemento da posição 5, isto é, o elemento

60. Dessa forma, as remoções dessa lista representada pelo vetor valor ocorrem

pelo final da lista.

É importante verificar em uma inserção, se a lista está cheia. Dessa forma, não é

possível inserir mais elementos. Da mesma forma, é importante verificar em uma

remoção se a lista não está vazia.

Impressão da Lista

A impressão da lista consiste em apresentar todos os elementos que fazem parte

da lista, mostrando os elementos que ocupam a posição 0 do vetor até a última

posição preenchida do vetor.

i = 0 1 2 3 4 5 6 7 8 9

valor 10 20 30 40 50 60

i = 0 1 2 3 4 5 6 7 8 9

valor 10 20 30 40 50 60 70

i = 0 1 2 3 4 5 6 7 8 9

valor 10 20 30 40 50 60

Estrutura de Dados

Pesquisa na Lista

A pesquisa na lista consiste em procurar elementos no vetor, informando se o

elemento foi encontrado ou não e qual a posição do vetor que este elemento ocupa.

A Impressão e a Pesquisa de elementos da lista se mostram de forma semelhante,

tanto para inserções e remoções do início ou final da lista.

Exemplo: Implementação de Lista Estática em C para números inteiros, com

operações de inserção no final da lista, remoção do final da lista, consulta e

pesquisa de elementos.

#include <stdio.h> #include <conio.h> #include <stdlib.h> #define MAX 5 void insere_final(); void remove_final(); void imprime_lista(); void busca(); struct lista { int valor[MAX]; int tamanho; int inicio; }; struct lista l; main() { l.inicio = l.tamanho = 0; int op; while(op != 5) { system("cls"); printf("Manipulacao de Lista Estatica"); printf("\nDigite 1 para Insercao no Inicio"); printf("\nDigite 2 para Imprimir a Lista"); printf("\nDigite 3 para Remover do Inicio"); printf("\nDigite 4 para Buscar Elemento"); printf("\nDigite 5 para Sair"); printf("\nDigite a opcao desejada: "); scanf("%i",&op); switch(op) { case 1: insere_final(); break; case 2: imprime_lista(); break; case 3: remove_final(); break; case 4: busca(); break; case 5: exit(1); default: printf("\nEntre com uma opcao valida!"); } }

Estrutura de Dados

} void insere_final() { int x; if(l.tamanho == MAX) { printf("\nLista cheia!"); exit(1); } else { printf("\nDigite uma valor: "); scanf("%i",&x); l.valor[l.tamanho] = x; l.tamanho++; printf("Elemento %i inserido com sucesso!",x); } getch(); } void remove_final() { if(l.tamanho == 0) { printf("\nLista Vazia!"); exit(1); } l.tamanho--; printf("Elemento %i removido com sucesso!",l.valor[l.tamanho]); getche(); } void imprime_lista() { int v; int i; i = l.inicio; while(i != l.tamanho) { v = l.valor[i]; printf("\nElemento %i da lista eh: %i",i,v); i++; } getche(); } void busca() { bool encontrou; int valor_procurado; int v; int i; i = l.inicio; printf("Entre com o valor que deseja buscar: "); scanf("%i",&valor_procurado);

Estrutura de Dados

while(i != l.tamanho) { v = l.valor[i]; if(v == valor_procurado) { printf("Elemento %i encontrado na posicao %i",l.valor[i],i); encontrou = 1; } i++; } if(encontrou != 1) printf("Elemento %i nao encontrado",valor_procurado); getche(); }

Remoção do Início da Lista

A Remoção pelo Início da Lista, deve acontecer sempre pela primeira posição do

vetor valor, isto é, a posição de índice 0. De acordo com o vetor valor, a primeira

posição é ocupada pelo elemento 70, logo, ele é o primeiro elemento a ser

removido do vetor. Após o elemento 70 ser removido, o primeiro elemento do

vetor passa a ser o elemento passa a ser o elemento que ocupava a posição 1 do

vetor, isto é, o elemento 60. E todos os elementos “andam” uma posição para

trás.

Da mesma forma que a inserção pelo final da lista, é importante verificar em uma

inserção, se a lista está cheia. Dessa forma, não é possível inserir mais elementos.

Deve-se verificar também em uma remoção se a lista não está vazia.

Exemplo: Implementação de Lista Estática em C para números inteiros, com

operações de inserção no início da lista, remoção do início da lista, consulta e

pesquisa de elementos.

#include <stdio.h> #include <conio.h> #include <stdlib.h> #define MAX 5 void insere_inicio(); void remove_inicio(); void imprime_lista(); void busca(); struct lista { int valor[MAX]; int inicio, final, tamanho;

i = 0 1 2 3 4 5 6 7 8 9

valor 60 50 40 30 20 10

0

Estrutura de Dados

}; struct lista l; main() { l.inicio = l.tamanho = 0; l.final = -1; int op; while(op != 5) { system("cls"); printf("Manipulacao de Lista Estatica"); printf("\nDigite 1 para Insercao no Inicio"); printf("\nDigite 2 para Imprimir a Lista"); printf("\nDigite 3 para Remover do Inicio"); printf("\nDigite 4 para Buscar Elemento"); printf("\nDigite 5 para Sair"); printf("\nDigite a opcao desejada: "); scanf("%i",&op); switch(op) { case 1: insere_inicio(); break; case 2: imprime_lista(); break; case 3: remove_inicio(); break; case 4: busca(); break; case 5: exit(1); default: printf("\nEntre com uma opcao valida!"); } } } void insere_inicio() { int i, vezes = 0; int x; if(l.tamanho == MAX) { printf("\nLista cheia!"); exit(1); } else { printf("\nDigite uma valor: "); scanf("%i",&x); i = l.final; while (vezes < l.tamanho) { l.valor[i+1] = l.valor[i]; i--; vezes++; } l.final++; l.valor[l.inicio] = x; l.tamanho++; }

Estrutura de Dados

getche(); } void remove_inicio() { int i, vezes=0; if(l.tamanho == 0) { printf("\nLista Vazia!"); exit(1); } i = l.inicio; while (vezes < (l.tamanho-1)) { l.valor[i] = l.valor[i+1]; i++; vezes++; } l.final--; l.tamanho--; getche(); } void imprime_lista() { int v; int i; i = l.inicio; while(i != l.tamanho) { v = l.valor[i]; printf("\nElemento %i da lista eh: %i",i,v); i++; } getche(); } void busca() { bool encontrou; int valor_procurado; int v; int i; i = l.inicio; printf("Entre com o valor que deseja buscar: "); scanf("%i",&valor_procurado); while(i != l.tamanho) { v = l.valor[i]; if(v == valor_procurado) { printf("Elemento %i encontrado na posicao %i",l.valor[i],i); encontrou = 1; } i++;

Estrutura de Dados

} if(encontrou != 1) printf("Elemento %i nao encontrado",valor_procurado); getche(); }

Exemplo de Inserção e Remoção do Final da Lista usando Ponteiro

O exemplo a seguir, implementa o mesmo exemplo acima, porém as funções irão o

ponteiro da variável umaLista que pertece a estrutura, isto é, as funções irão

receber o endereço da variável umaLista.

#include <stdio.h> #include <conio.h> #include <stdlib.h> #define MAX 5 struct lista { int valor[MAX]; int tamanho; int inicio; }; void inicia(struct lista *umaLista) { umaLista->inicio = umaLista->tamanho = 0; } void insere_final(struct lista *l, int x) { if(l->tamanho == MAX) { printf("\nLista cheia!"); exit(1); } else { l->valor[l->tamanho] = x; l->tamanho++; printf("Elemento %i inserido com sucesso!",x); } getch(); } int remove_final(struct lista *l) { if(l->tamanho == 0) { printf("\nLista Vazia!"); exit(1); } l->tamanho--; printf("Elemento %i removido com sucesso!",l->valor[l->tamanho]); return l->valor[l->tamanho]; getche();

Estrutura de Dados

} void imprime_lista(struct lista *l) { int v; int i; i = l->inicio; while(i != l->tamanho) { v = l->valor[i]; printf("\nElemento %i da lista eh: %i",i,v); i++; } getche(); } void busca(struct lista *l) { bool encontrou; int valor_procurado; int v; int i; i = l->inicio; printf("Entre com o valor que deseja buscar: "); scanf("%i",&valor_procurado); while(i != l->tamanho) { v = l->valor[i]; if(v == valor_procurado) { printf("Elemento %i encontrado na posicao %i",l->valor[i],i); encontrou = 1; } i++; } if(encontrou != 1) printf("Elemento %i nao encontrado",valor_procurado); getche(); } main() { int op; int valor, retorno; struct lista umaLista; inicia(&umaLista); while(op != 5) { system("cls"); printf("Manipulacao de Lista Estatica"); printf("\nDigite 1 para Insercao no Final"); printf("\nDigite 2 para Imprimir a Lista"); printf("\nDigite 3 para Remover do Final");

Estrutura de Dados

printf("\nDigite 4 para Buscar Elemento"); printf("\nDigite 5 para Sair"); printf("\nDigite a opcao desejada: "); scanf("%i",&op); switch(op) { case 1: printf("Digite um valor para lista: "); scanf("%i",&valor); insere_final(&umaLista,valor); break; case 2: imprime_lista(&umaLista); break; case 3: retorno = remove_final(&umaLista); break; case 4: busca(&umaLista); break; case 5: exit(1); default: printf("\nEntre com uma opcao valida!"); } } }

Outro exemplo de Inserção e Remoção Final da Lista usando Ponteiro para

duas listas distintas

Este exemplo é muito semelhante ao anterior, porém faz uso da criação de duas

listas distintas. As funções são as mesmas apresentadas anteriormente, porém

agora com dois ponteiros distintos.

#include <stdio.h> #include <conio.h> #include <stdlib.h> #define MAX 5 struct lista { int valor[MAX]; int tamanho; int inicio; }; void inicia(struct lista *l) { l->inicio = l->tamanho = 0; } void insere_final(struct lista *l, int x) { if(l->tamanho == MAX) {

Estrutura de Dados

printf("\nLista cheia!"); exit(1); } else { l->valor[l->tamanho] = x; l->tamanho++; printf("Elemento %i inserido com sucesso!",x); } getch(); } int remove_final(struct lista *l) { if(l->tamanho == 0) { printf("\nLista Vazia!"); exit(1); } l->tamanho--; printf("Elemento %i removido com sucesso!",l->valor[l->tamanho]); return l->valor[l->tamanho]; getche(); } void imprime_lista(struct lista *l) { int v; int i; i = l->inicio; while(i != l->tamanho) { v = l->valor[i]; printf("\nElemento %i da lista eh: %i",i,v); i++; } getche(); } void busca(struct lista *l) { bool encontrou; int valor_procurado; int v; int i; i = l->inicio; printf("Entre com o valor que deseja buscar: "); scanf("%i",&valor_procurado); while(i != l->tamanho) { v = l->valor[i]; if(v == valor_procurado) { printf("Elemento %i encontrado na posicao %i",l->valor[i],i); encontrou = 1;

Estrutura de Dados

} i++; } if(encontrou != 1) printf("Elemento %i nao encontrado",valor_procurado); getche(); } main() { int op; int valor, retorno; struct lista l1, l2; inicia(&l1); inicia(&l2); while(op != 9) { system("cls"); printf("Manipulacao de 2 Listas Estaticas"); printf("\nDigite 1 para Insercao no Final da Lista l1"); printf("\nDigite 2 para Insercao no Final da Lista l2"); printf("\nDigite 3 para Imprimir a Lista l1"); printf("\nDigite 4 para Imprimir a Lista l2"); printf("\nDigite 5 para Remover do Final da Lista l1"); printf("\nDigite 6 para Remover do Final da Lista l2"); printf("\nDigite 7 para Buscar Elemento na Lista l1"); printf("\nDigite 8 para Buscar Elemento na Lista l2"); printf("\nDigite 9 para Sair"); printf("\nDigite a opcao desejada: "); scanf("%i",&op); switch(op) { case 1: printf("Digite um valor para a lista l1: "); scanf("%i",&valor); insere_final(&l1,valor); break; case 2: printf("Digite um valor para a lista l2: "); scanf("%i",&valor); insere_final(&l2,valor); break; case 3: printf("\nImpressao da lista l1"); imprime_lista(&l1); break; case 4: printf("\nImpressao da lista l2"); imprime_lista(&l2); break; case 5: printf("\nRemocao da lista l1"); retorno = remove_final(&l1);

Estrutura de Dados

break; case 6: printf("\nRemocao da lista l2"); retorno = remove_final(&l2); break; case 7: busca(&l1); break; case 8: busca(&l2); break; case 9: exit(1); default: printf("\nEntre com uma opcao valida!"); } } }

Exemplo: Implementação de Lista Estática Tenenbaum. Este exemplo, implementa

uma lista para 500 nós, utilizando uma estrutura com campos info (que contém o

elemento inserido) e next (próximo elemento da lista) e é criado um vetor

node[NUMNODES] para as 500 posições. A figura abaixo representa a manipulação

dessa lista.

info next

0

1

2

3

499

1

2

3

4

-1

Estrutura de Dados

#include<stdio.h> #include<conio.h> #include<stdlib.h> #define NUMNODES 500 int avail; struct nodetype { int info, next; }; struct nodetype node[NUMNODES]; void inicia() { avail = 0; for(int i = 0; i < NUMNODES-1; i++) node[i].next = i + 1; node[NUMNODES-1].next = -1; } int getnode() { int p; if(avail == -1) { printf("estouro\n"); exit(1); } p = avail; avail = node[avail].next; return(p); } int freenode(int p) { node[p].next = avail; avail = p; return avail; } void insafter(int p, int x) { int q; if(p == -1) { printf("insercao nula\n"); return; } q = getnode(); node[q].info = x; node[q].next = node[p].next; node[p].next = q; printf("\nElemento %i inserido com sucesso!",x); getche();

Estrutura de Dados

} int delafter(int p, int *px) { int q; if((p == -1) || (node[p].next == -1)) { printf("remocao nula\n"); return -1; } q = node[p].next; *px = node[q].info; node[p].next = node[q].next; freenode(q); return *px; } main() { int op; int valor; int retorno; inicia(); while(op != 3) { system("cls"); printf("Manipulacao de Lista"); printf("\nDigite 1 para inserir elemento na lista"); printf("\nDigite 2 para remover elemento da lista"); printf("\nDigite 3 para sair"); printf("\nEntre com a opcao desejada: "); scanf("%i",&op); switch(op) { case 1: printf("Entre com um valor: "); scanf("%i",&valor); insafter(1, valor); break; case 2: retorno = delafter(1,&valor); printf("O valor de retorno eh: %i",retorno); getch(); break; case 3: exit(1); } } }

A função inicia() é responsável por montar a lista ilustrada no desenho acima e

colocar nos campos next o valor dos campos próximos. A última posição, tem -1

na posição next.

Estrutura de Dados

A função void insafter(int p, int x), é responsável pela inserção dos elementos na

lista. É realizado uma chamada para a função getnode() que verifica se a lista está

cheia e caso não esteja, devolve a próxima posição livre em que o elemento pode

ser inserido.

A função int delafter(int p, int *px), é responsável pela exclusão dos elementos. É

realizada uma chamada para a função freenode() libera um nó que não será mais

utilizado.

Este exemplo apresenta de uma forma um pouco mais complexa, o exemplo

apresentado anteriormente para lista com inserção no final e remoção do final da

lista.