Lista Simplesmente Encadeada Introdução

Prévia do material em texto

Estrutura de dadosEstrutura de dados
LSE LSE 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
Lista Simplesmente Encadeada
• Estrutura de dados que armazenam 
valores homogêneos.
• A definição de sua estrutura é definida no 
momento da codificação do programa.
• Tem seu tamanho modificado durante a 
execução do programa.
• O número de elementos na lista 
dependerá da memória disponível, não 
tem limite máximo determinado.
LSE
• Exemplos de declaração de uma LSE em C
Typedef struct registro{ 
char nome[60];
int idade;
float salario; 
}registro;
Typedef struct celula{
struct registro dado;
struct celula *prox;
}célula;
Typedef struct TLista{
struct celula *inicio;
struct celula *fim;
}
Manipulação de LSE
• Operações
– Vazia
– Criar
– Inserir
– Listar
– Consultar
– Excluir
– Destruir
• Vamos supor que tenhamos uma LSE e temos que realizar 
as operações citadas acima. Esta LSE será chamada de “L”
• Como devemos proceder?
Verificando Lista Vazia
• /*--------------------------------------------------------}
• { Rotina : Vazia }
• { Objetivo: Funcao para verificar se a lista esta Vazia. 
}
• { Obs.....: Retorna TRUE se estiver vazia. }
• {--------------------------------------------------------*/
• BOOL Vazia (TLista l) {
• return ((l.inicio == NULL) && (l.fim == NULL));
• }
Criar a Lista
• /*--------------------------------------------------------}
• { Rotina : Criar }
• { Objetivo: Criar a lista - Inicializar os ponteiros. 
}
• {--------------------------------------------------------*/
• void Criar (TLista *l) {
• (*l).inicio = NULL;
• (*l).fim = NULL;
• }
Inserir – LSE - Passos
• Verificar se a lista está vazia
– Sim – vazia
• Alocar memória para o primeiro elemento(início)
• O fim e o início da lista deverão apontar para o mesmo endereço 
de memória
– Não 
• Fazer a inclusão do elemento no final da lista
• Este elemento recém criado deverá ser o fim da lista
• O próximo do final deverá apontar para NULL
Como Ficaria o algorítimo...
• BOOL Inserir (TLista *l, TRegistro d) {
• BOOL ret = FALSE;
• if (Vazia (*l)) {
• (*l).inicio = (TCelula *)malloc (sizeof(TCelula));
• (*l).fim = (*l).inicio;
• } else {
• (*l).fim.prox = (TCelula *)malloc (sizeof(TCelula));
• (*l).fim = (*l).fim->prox;
• }
• (*l).fim.dado = d;
• (*l).fim.prox = NULL;
• ret = TRUE;
• return ret;
• }
Listagem - LSE
• Criar uma estrutura de repetição que 
comece a ler os valores contidos na LSE.
• Lembre-se que o início da LSE é indicado 
por L.inicio e o final é indicado por L.fim. 
• Então iremos fazer uma estrutura de 
repetição que leia os valores do início até o 
fim.
Listagem - LSE
• void Imprimir (TLista l) {
• TCelula *aux;
• if (Vazia(l)) {
• printf ("Lista Vazia !!!");
• } else {
• (*aux) = (*l).inicio;
• while ((*aux) != NULL) {
• printf ("NOME: %s\n", (*aux).dado.nome);
• printf ("IDADE: %d\n", (*aux).dado.idade);
• printf ("SALARIO: %5.2f\n\n", (*aux).dado.salario);
• (*aux) = (*aux).prox;
• }
• }
• }
Consulta - LSE
• Utilizaremos o mesmo raciocínio da listagem
– Criar uma estrutura de repetição que comece a ler os valores 
contidos na LSE.
– Lembre-se que o início da LSE é indicado por L.inicio e o final é
indicado por L.fim. 
– Então iremos fazer uma estrutura de repetição que leia os valores 
do início até o fim.
• A cada interação da estrutura de repetição, devemos 
comparar o conteúdo de cada posição da LSE com o que 
queremos encontrar.
• Obs: Caso achemos o que estávamos procurando, 
interromper a estrutura de repetição, se for o caso. 
Consulta - LSE
• BOOL Consultar (TLista *l, TRegistro *d) {
• TCelula *aux;
• BOOL achou;
• BOOL ret = FALSE;
• if (!Vazia(*l)) {
• achou = FALSE;
• (*aux) = (*l).inicio;
• while ((*aux != NULL) && (!achou)) {
• if (!strcmp ((*aux).dado.nome, d.nome)) {
• achou = TRUE;
• (*d) = (*aux).dado;
• ret = TRUE;
• return ret;
• }
• (*aux) = (*aux).prox;
• }
• }
• return ret;
• }
Exclusão - LSE
• Utilizaremos o mesmo raciocínio da consulta para podermos 
achar o elemento a ser removido.
• Quando acharmos o referido elemento devemos fazer as 
seguintes verificações com o elemento:
– Se ele for o primeiro e único.
– Se ele for o primeiro e não for o único.
– Se for o último.
– Se estiver no meio.
• Para remoções deveremos ter duas variáveis capaz de armazenar 
em os endereços de armazenar o endereço de memória do 
elemento a ser removido e o elemento anterior a ele.
Exclusão - LSE
• Se ele for o primeiro e único, isto é, um 
único elemento na LSE
–Variáveis que armazenam os endereços de 
memória do início e fim da LSE, deverão 
receber o valor nulo (null).
–Devolver ao sistema operacional o antigo 
endereço de memória do início.
Exclusão - LSE
• Se ele for o primeiro e não for o único, isto 
é, tem mais de um elemento na LSE.
–Fazer com que a variável que armazena o 
endereço de memória do início da LSE, receba o 
valor do próximo elemento ao início.
–Devolver o antigo endereço de memória do 
início ao sistema operacional.
Exclusão - LSE
• Se for o último.
–A variável que armazena o endereço de 
memória do fim da LSE, deverá receber o 
endereço de memória do elemento de memória 
anterior ao fim da LSE.
–Devolver ao sistema operacional o antigo 
endereço de memória do último elemento da 
LSE.
Exclusão - LSE
• Se estiver no meio.
– Para o elemento que está posicionado antes do 
elemento que será removido.
• Deveremos atualizar a parte interna que armazena a posição do 
próximo elemento, recebendo o endereço de memória do 
próximo elemento que será removido.
• O próximo do anterior deverá apontar para o próximo do 
auxiliar.
– Devolver ao sistema operacional o endereço de 
memória do auxiliar.
– O auxiliar deverá ser o próximo elemento do anterior.
• BOOL Excluir (TLista *l, TRegistro d) {
• TCelula *aux; // aux vai apontar pra o elemento que quero deletar
• TCelula *ant; // ant vai apontar pra o elemento anterior do que eu quero deletar
• BOOL achou;
• BOOL ret = FALSE;
• if (!Vazia (*l)) {
• achou = FALSE;
• *ant = (*l).inicio;
• *aux = (*l).inicio;
• while ((*aux != NULL) && (!achou)) {
• if (!strcmp ((*aux).dado.nome, d.nome)) {
• achou = TRUE;
• //ver próximo slide
• }
• else { // Mover o aux e o ant - TCelula
• *ant = *aux;
• *aux = (*aux).prox;
• }
• }
• if (achou) {// Eliminar o elemento da memoria
• free (*aux);
• ret = TRUE;
• }
• }
• return ret;
• }
if ((*l).inicio->prox == NULL) { // Se for no inicio com um elemento
(*l).inicio = NULL;
(*l).fim = NULL;
}
else if (*aux ==(*l).inicio) { // Se for no inicio com vários elementos
(*l).inicio = (*l).inicio.prox;
}
else if (*aux ==(*l).fim) { // Se for no fim da lista
(*l).fim = ant;
(*ant).prox = NULL;
}
else { // Se for no meio da lista
(*ant).prox = (*aux).prox;
}
Destruir - LSE
• Ao terminar o programa deveremos 
devolver todos os espaçosde memória 
requisitados, para isso criaremos um 
procedimento para destruir a LSE
Destruir - LSE
• void Destruir (TLista *l) {
• TCelula *aux = (*l).inicio;
• while (*aux != NULL) {
• (*l).inicio = (*aux).prox;
• free (*aux);
• *aux = (*l).inicio;
• }
• (*l).inicio = NULL;
• (*l).fim = NULL;
• }
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de 
Classificação de Dados e Análise de suas 
Complexidades. Rio de Janeiro: Campus, 
1995.
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm 
analysis in C++. California: Benjamin/Cummings, 
1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, 
data structures, sorting, searching. New York: 
Addison-Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & 
AUGENSTEIN, M. Estruturas de Dados usando C. 
São Paulo: Makron Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de 
dados e algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e 
Algoritmos. São Paulo: Berkeley Brasil, 2001.