Estrutura de dados II
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
Listas lineares
Lista Linear
Definição: seqüência de zero ou mais elementos a1,a2, ...,an
sendo
ai elementos de um mesmo tipo
n o tamanho da lista linear
Propriedade fundamental: os elementos têm relações de
ordem na lista
ai precede ai+1 (e ai sucede ai-1);
a1 é o primeiro elemento da lista
an é o último elemento da lista
Lista Linear
São estruturas flexíveis, que podem crescer ou diminuir
durante a execução do programa, de acordo com a demanda
São mais adequadas para aplicações nos quais não é
possível prever a demanda por espaços
Exs.:
1.
Listas de Arquivos de uma pasta
2.
Listas de Programas Instalados
3.
Listas de Fontes Instaladas
4.
Etc...
Implementação do TAD Listas
Tipos de Implementação:
1. Através de arranjos (arrays) – listas estáticas
2. Através de apontadores ou ponteiros – listas dinâmicas
Em qualquer uma das implementações, deve-se:
1. Definir da Estrutura de Dados
2. Definir as Operações
Operações Usuais de uma Lista
Iniciar/Criar uma lista linear vazia
Inserir um novo elemento após o i-ésimo elemento
Retirar i-ésimo elemento
Buscar o i-ésimo elemento
Combinar duas ou mais listas em uma lista única
Dividir uma lista em duas ou mais listas
Fazer uma cópia da lista
Ordenar os itens da lista em ordem crescente ou decrescente
Classificação das listas lineares
Listas lineares
Pilha
Fila
Fila Dupla
(double ended queue – deque)
Fila com entrada restrita
Fila com saída restrita
Pilhas
(stack)
Pilhas
Uma das estruturas de dados mais simples é a pilha. Possivelmente por essa
razão, é a estrutura de dados mais utilizada em programação, sendo inclusive
implementada diretamente pelo hardware da maioria das máquinas modernas.
A idéia fundamental da pilha é que todo o acesso a seus elementos é feito
através do seu topo. Assim, quando um elemento novo é introduzido na pilha,
passa a ser o elemento do topo, e o único elemento que pode ser removido da
pilha é o do topo. Isto faz com que os elementos da pilha sejam retirados na
ordem inversa à ordem em que foram introduzidos: o primeiro que sai é o último
que entrou (a sigla LIFO – last in, first out – é usada para descrever esta
estratégia).
Pilhas
Analogia com uma pilha de pratos.
Se quisermos adicionar um prato na pilha, o colocamos no topo. Para pegar um
prato da pilha, retiramos o do topo. Assim, temos que retirar o prato do topo para
ter acesso ao próximo prato. A estrutura de pilha funciona de maneira análoga.
Cada novo elemento é inserido no topo e só temos acesso ao elemento do topo
da pilha.
Pilhas
Existem duas operações básicas que devem ser
implementadas numa estrutura de pilha: a operação para
empilhar um novo elemento, inserindo-o no topo, e a
operação para desempilhar um elemento, removendo-o do
topo. É comum nos referirmos a essas duas operações pelos
termos em inglês push (empilhar) e pop (desempilhar).
Funcionamento
Exemplo de utilização
O exemplo de utilização de pilha mais próximo é a própria pilha de
execução da linguagem C. As variáveis locais das funções são
dispostas numa pilha e uma função só tem acesso às variáveis que
estão no topo (não é possível acessar as variáveis da função locais às
outras funções).
Há várias implementações possíveis de uma pilha, que se distinguem
pela natureza dos seus elementos, pela maneira como os elementos
são armazenados e pelas operações disponíveis para o tratamento da
pilha.
Estrutura para representação
#define MAXPILHA 100
struct stack {
int topo;
int item [MAXPILHA];
}
Uso
struct stack s;
Estrutura para representação
topo – usado para saber o número de elementos na lista
Se topo = -1 assume-se que pilha vazia
12
top= -1
33
33
55
55
55
top= 0
top=1
top=2
Inicializando uma pilha
Pilha não pode conter elementos
Não precisa preencher vetor com zeros
Basta fazer top = -1
inicPilha(s)
topo(s)  -1;
void inicPilha(struct stack * ps){
ps->topo = -1;
}
Verificando limites
Para desempilhar um elemento é necessário que esse
elemento exista
Não é possível desempilhar se pilha estiver vazia
int pilhaVazia(struct stack * ps){
if(ps-> topo == -1)
return 1;
else
return 0;
Uso da verificação de limite
If(pilhaVazia(&s) )
** tratamento de pilha vazia**
else
** faz alguma coisa pois pilha cheia**
Verificação de pilha cheia
int pilhaCheia(struct stack * ps){
if(ps-> topo == MAXPILHA -1)
return 1;
else
return 0;
Empilhando um elemento
int push(struct stack * ps, x){
if(pilhaCheia(ps))
printf(“Pilha estah cheia”);
else
return (psitem[ ++(pstopo)] = x);
}
Uso
push(&s, 20);
Desempilhando
int pop(struct stack * ps){
if(pilhaVazia(ps))
printf(“Pilha estah vazia”);
else
return (psitem[ pstopo - -] );
}
Uso
var = pop(&s);
Consultando o topo
Não remove o elemento, apenas consulta qual está no topo
int topo(struct stack * ps){
if(pilhaVazia(ps))
printf(“Pilha estah vazia”);
else
return (psitem[ pstopo ] );
}
Uso
var = topo(&s);
Uso
Conversão de decimal para binário
3510  ? 2
35 / 2 = 17 Resto = 1
17 / 2 = 8 Resto = 1
8/2=4
Resto = 0
4/2=2
Resto = 0
2 / 2 = 1 Resto = 0
1 0 0 0 1 1 2  3510