Listas Lineares: Definição, Aplicabilidade e Operações

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Listas
Profª: Karina Dutra de Carvalho Lemos
*
Definição de Listas
Uma lista linear é uma sequência de zero ou mais itens x1, x2, · · · , xn, na qual xi é de um determinado tipo e n representa o tamanho da lista linear. Sua principal propriedade estrutural envolve as posições relativas dos itens em uma dimensão. Assumindo n ≥ 1, x1 é o primeiro item da lista e xn é o último item da lista. Em geral:
xi precede xi+1 para i = 1, 2, · · · , n – 1
xi sucede xi−1 para i = 2, 3, · · · , n
o elemento xi é dito estar na i-ésima posição da lista.
*
Uma das formas mais simples de interligar os elementos de um conjunto é por meio de uma lista. 
Lista é uma estrutura em que as operações inserir, retirar e localizar são definidas. 
Listas são estruturas muito flexíveis, porque podem crescer ou diminuir de tamanho durante a execução de um programa, de acordo com a demanda. Itens podem ser acessados, inseridos ou retirados de uma lista. Duas listas podem ser concatenadas para formar uma lista única, ou uma pode ser partida em duas ou mais listas. 
*
Aplicabilidade
Listas são adequadas para aplicações nas quais não é possível prever a demanda por memória, permitindo a manipulação de quantidades imprevisíveis de dados, de formato também imprevisível. Listas são úteis em aplicações tais como manipulação simbólica, gerência de memória, simulação e compiladores.
*
Operações com listas
Para criar um tipo abstrato de dados Lista, é necessário definir um conjunto de operações sobre os objetos do tipo Lista. O conjunto de operações a ser definido depende de cada aplicação, não existindo um conjunto de operações que seja adequando a todas as aplicações. 
*
Operações com listas
Um conjunto de operações necessário a uma maioria de aplicações é apresentado a seguir:
Criar uma lista linear vazia.
Inserir um novo item imediatamente após o i-ésimo item.
Retirar o i-ésimo item.
Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de seus componentes.
*
Combinar duas ou mais listas lineares em uma lista única.
Partir uma lista linear em duas ou mais listas.
Fazer uma cópia da lista linear.
Ordenar os itens da lista em ordem ascendente ou descendente, de acordo com alguns de seus componentes.
Pesquisar a ocorrência de um item com um valor particular em algum componente.
Intercalar listas.
*
Funções e Procedimentos
FLVazia(Lista) → Faz a lista ficar vazia.
Insere(x, Lista) → Insere x após o último item da lista.
Retira(p, Lista, x) → Retorna o item x que está na posição p da lista, retirando-o da lista e deslocando os itens a partir da posição p+1 para as posições anteriores.
Vazia(Lista) → Esta função retorna true se lista vazia; senão retorna false.
Imprime(Lista) → Imprime os itens da lista na ordem de ocorrência.
*
Implementação de listas por meio de Arranjos
Os itens da lista são armazenados em posições contíguas de memória. 
A lista pode ser percorrida em qualquer direção.
A inserção de um novo item pode ser realizada após o último item com custo constante.
*
Implementação de listas por meio de Arranjos
A inserção de um novo item no meio da lista requer um deslocamento de todos os itens localizados após o ponto de inserção.
Retirar um item do início da lista requer um deslocamento de itens para preencher o espaço deixado vazio.
*
Vantagem
Economia de memória, pois os apontadores são implícitos nesta estrutura.
A lista pode ser percorrida em qualquer direção.
A inserção de um novo item pode ser realizado após o último item com custo constante.
*
Desvantagens
O custo para inserir ou retirar itens da lista, que pode causar um deslocamento de todos os itens, no pior caso;
Em aplicações em que não existe previsão sobre o crescimento da lista, a utilização de arranjos em linguagens como o Pascal pode ser problemática porque neste caso o tamanho máximo da lista tem de ser definido em tempo de compilação.
*
Estrutura da lista usando arranjo
O campo item é o principal componente do registro tipolista.
Os itens são armazenados em um arranjo de tamanho suficiente para armazenar a lista.
O campo Último do registro tipolista contém um apontador que aponta para a posição seguinte a do último elemento da lista.
O i-ésimo item da lista está armazenado na i-ésima posição do arranjo, 1 ≤ i < Último.
A constante maxtam define o tamanho máximo permitido para a lista.
*
Implementação
const
 inicioarranjo=1;
 maxtam=1000;
type
 apontador = integer;
 tipoitem= record 
 chave:string;
 end;
 tipolista= record 
 item: array [1..maxtam] of tipoitem;
 primeiro:apontador;
 ultimo:apontador;
 end;
*
Operações sobre listas usando Arranjo
1- Procedimento para fazer a lista ficar vazia:
 
procedure flvazia(var lista:tipolista);
begin
 lista.primeiro:=inicioarranjo;
 lista.ultimo:=lista.primeiro;
end;
*
Operações sobre listas usando Arranjo
2- Função para verificar se a lista esta vazia:
 
Function Vazia(Var lista:tipolista): boolean;
Begin
 Vazia:=lista.primeiro=lista.ultimo;
End;
*
Operações sobre listas usando Arranjo
3- Procedimento para inserir um elemento no final da lista:
 
procedure insere(x: tipoitem; var lista:tipolista);
begin
 if lista.ultimo > maxtam
 then writeln('Lista está cheia')
 else begin
 lista.item[lista.ultimo]:=x;
 lista.ultimo:=lista.ultimo+1;
 end;
end;
*
Operações sobre listas usando Arranjo
4- Procedimento para retirar um elemento em qualquer lugar da lista: 
Procedure Retira(p: apontador; var lista:tipolista; var item:tipoitem);
Var
 aux:integer;
Begin
 If (vazia(lista)) or (p>=lista.ultimo)
 Then writeln('Erro: Posição não Existe')
 Else begin
 Item:=lista.item[p];
 Lista.ultimo:=lista.ultimo - 1;
 For aux:=p to lista.ultimo-1 do
 Begin
 Lista.item[aux]:=lista.item[aux+1];
 End;
 End;
End;
*
Operações sobre listas usando Arranjo
5 - Procedimento para imprimir o conteúdo da lista:
 
procedure imprime(var lista:tipolista);
var 
 aux:integer;
begin
 for aux:=lista.primeiro to lista.ultimo-1 do
 begin
 writeln;
 write('O conteúdo da lista na posição ',aux, ' é: ');
 writeln(lista.item[aux].chave);
 end;
 readln;
end;
*
Exemplo1:Programa que implementa as 5 operações básicas para se trabalhar com uma lista usando arranjo.
program listarranjo;
uses crt;
const
 inicioarranjo=1;
 maxtam=100;
type
 apontador=integer;
 tipoitem= record 
 chave:string[15];
 end;
 tipolista= record 
 item: array [1..maxtam] of tipoitem;
 primeiro:apontador;
 ultimo:apontador;
 end;
*
procedure flvazia(var lista:tipolista);
begin
 lista.primeiro:=inicioarranjo;
 lista.ultimo:=lista.primeiro;
end; 
procedure insere(x: tipoitem; var lista:tipolista);
begin
 if lista.ultimo > maxtam
 then writeln('lista cheia')
 else begin
 lista.item[lista.ultimo]:=x;
 lista.ultimo:=lista.ultimo+1;
 end;
end;
*
procedure imprime(var lista:tipolista);
var 
 aux:integer;
begin
 for aux:=lista.primeiro to lista.ultimo-1 do
 begin
 writeln;
 write('O conteúdo da lista na posição ',aux, ' é: ');
 writeln(lista.item[aux].chave);
 end;
 readln;
end;
*
Function Vazia(Var lista:tipolista): boolean;
Begin
 Vazia:=lista.primeiro=lista.ultimo;
End;
 
Procedure Retira(p: apontador; var lista:tipolista; var item:tipoitem);
Var 
 aux:integer;
Begin
 If (vazia(lista)) or (p>=lista.ultimo)
 Then writeln('Erro: Posição não Existe')
 Else begin
 Item:=lista.item[p];
 Lista.ultimo:=lista.ultimo - 1;
 For aux:=p to lista.ultimo-1 do
 Begin
 Lista.item[aux]:=lista.item[aux+1];
 End;
 End;
End;
*
VAR
lista:tipolista;
 x:tipoitem;
 i,n:integer;
 p:apontador;
 
begin
 n:=1;
 flvazia(lista);
 
 while n <> 0 do
 begin
 clrscr;
 writeln(' [0]- Sair');
 writeln;
 writeln(' [1]- Limpar lista');
 writeln;
 
*
writeln(' [2]- Inserir elemento na lista');
 writeln;
 writeln(' [3]- Imprimir conteúdo da lista');
 writeln;
 writeln(' [4]- Retirar um elemento da lista');
 writeln;
 write('Entre com a opcao: ');
 readln(n);
 writeln;
*
 case n of
 1: flvazia(lista);
 2: begin
 write('Entre com um nome: ');
 readln(x.chave);
 insere(x,lista);
 end;
 3: imprime(lista);
 4: begin
 write('Entre com a posição do elemento a ser retirado: ');
 readln(p);
 retira(p,lista,x);
 readln;
 end;
 end;
 end;
 readkey;
end.
*
EXEMPLO 2: Procedimentos para serem utilizados em lista por arranjo
6- Procedimento para fazer a cópia de uma lista:
procedure copia(var lista,listacop:tipolista);
begin
 listacop:=lista;
end;
 
Para chamar o procedimento copia e imprimir a cópia:
 6: begin
 copia(lista,listacop);
 imprime(listacop);
 end;
*
7- Procedimento para juntar duas listas em uma única:
 
procedure junta(var lista,lista2,listaj:tipolista);
var
 i:integer;
begin
 listaj:=lista;
 for i:=lista2.primeiro to lista2.ultimo-1 do
 begin
 listaj.item[listaj.ultimo]:=lista2.item[i];
 listaj.ultimo:=listaj.ultimo+1;
 end;
end;
 
*
Para chamar o procedimento junta; imprimir o conteúdo da listaj e inserir conteúdo na lista2:
 
7: begin
 write('entre com o nome: ');
 readln(x.chave);
 insere(x,lista2);
 end;
8: begin
 junta(lista,lista2,listaj);
 imprime(listaj);
 end;
*
8- Procedimento que parte uma lista em duas outras e limpa seu conteúdo:
 
procedure partir(var lista,listap1,listap2:tipolista);
var 
 i,tam:integer;
begin
 flvazia(listap1);
 flvazia(listap2);
 tam:= (lista.ultimo -1) div 2;
 for i:=lista.primeiro to lista.ultimo -1 do
 begin
*
 if i<=tam
 then begin
 listap1.item[listap1.ultimo]:=lista.item[i];
 listap1.ultimo:=listap1.ultimo+1;
 end
 else begin
 listap2.item[listap2.ultimo]:=lista.item[i];
 listap2.ultimo:=listap2.ultimo+1;
 end;
 end;
 flvazia(lista);
end;
*
Para chamar o procedimento partir e imprimir o conteúdo da listap1 e listap2;
9: begin
 partir(lista,listap1,listap2);
 writeln('Conteúdo da lista parte 1:');
 imprime(listap1);
 writeln('Conteúdo da lista parte 2:');
 imprime(listap2);
 end;
*
9- Procedimento para Intercalar listas:
Procedure alterna(var lista1,lista2:tipolista;var lista3:tipolista2);
var
 i:integer;
begin
 i:=1;
 while (i<=lista1.ultimo-1) or (i<=lista2.ultimo-1) do
 begin
 lista3.item[lista3.ultimo]:=lista1.item[i];
 lista3.ultimo:=lista3.ultimo+1;
 lista3.item[lista3.ultimo]:=lista2.item[i];
 lista3.ultimo:=lista3.ultimo+1;
 i:=i+1;
 end;
end;
*
Para chamar o procedimento alterna e imprimir o conteúdo da lista3;
10: begin
 alterna(lista1,lista2,lista3);
 imprime1(lista3);
 end;
*
10- Procedimento para pesquisar a ocorrência de um item:
procedure procura(var lista1:tipolista;x:tipoitem);
var
 i:integer;
 encontrou:boolean;
begin
 encontrou:=false;
 for i:=lista1.primeiro to lista1.ultimo-1 do
 begin
 if lista1.item[i].cpf=x.cpf
 then begin
 encontrou:=true;
 writeln('CPF encontrado na posicao:',' ',i);
 writeln('O dono deste documento e:',' ',lista1.item[i].nome);
 break;
 end;
 end;
 if encontrou=false
 then writeln('CPF nao encontrado');
 readln;
end;
*
Para chamar o procedimento procura;
11:begin
 Writeln('Entre com o cpf');
 readln(x.cpf);
 procura(lista1,x);
 end;
*
11- Ordenar os itens da lista em ordem ascendente:
procedure ordena(var lista1:tipolista);
var
 i,aux,bolha,superior:integer;
begin
 superior:=lista1.ultimo-1;
 while superior>1 do
 begin
 bolha:=lista1.primeiro; 
 for i:=1 to superior-1 do
 begin
 
*
if lista1.item[i].numero >lista1.item[i+1].numero
 then begin
 aux:=lista1.item[i].numero;
 lista1.item[i].numero:=lista1.item[i+1].numero;
 lista1.item[i+1].numero:=aux;
 bolha:=i;
 end;
 end;
superior:=bolha;
 end;
end;
*
Para chamar o procedimento ordena;
12: begin
 ordena(lista1);
 imprime(lista1);
 end;