Upload
internet
View
133
Download
0
Embed Size (px)
Citation preview
Listas Encadeadas
Professor Reverton de PaulaFaculdade Anhanguera de Indaiatuba
Listas Encadeadas
• Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. – Cada elemento da sequência é armazenado em
uma célula da lista: • o primeiro elemento na primeira célula, o segundo na
segunda e assim por diante.
Lista: Operações
• Adicionar um elemento na primeira posição de um Vetor consome muito tempo, – Pois temos de deslocar todos os outros elementos
uma posição para a frente.• A performance dessa operação degrada a
medida que a quantidade de elementos do nosso vetor cresce: – ela consome tempo linear em relação ao número
de elementos.
Lista: Operações
• Analogamente, remover um elemento da primeira posição implica em deslocar todos os outros elementos que estão na sua frente para trás.
• Em alguns casos, queremos uma implementação de Lista na qual a operação de adicionar ou a de remover um aluno na primeira posição seja computacionalmente eficiente. – Conseguiremos isso através de uma Lista Ligada.
Lista: Operações
• Operações que poderemos fazer em uma dada lista– Adicionar um dado elemento no fim da Lista.– Adicionar um dado elemento em um dada posição.– Pegar o elemento de uma dada posição.– Remover o elemento de uma dada posição.– Verificar se um dado elemento está contido na Lista.– Informar a quantidade de elementos da Lista.
Listas encadeadas
• Precisamos de algo que não seja fixo como um array.
• Então a idéia aqui é ter uma forma de, dado um aluno, saber quem é o próximo, sem usar uma estrutura fixa
Listas encadeadas
• Repare que:– apesar do efeito de um aluno estar “ao lado” do outro,
• na memória é mais provável que eles não se encontrem um ao lado do outro, – e sim em regiões bem diferentes da memória, – só que cada um deles sabe dizer em que local se encontra o próximo
aluno (pois temos a referência ao proximo).
Célula e Lista Ligada
Listas Encadeadas
Estrutura de uma lista encadeada
• Uma lista encadeada (= linked list = lista ligada) é uma sequência de células; – cada célula contém:
• um objeto de algum tipo • e o endereço da célula seguinte.
• Vamos supor que os objetos armazenados nas células são do tipo int. – A estrutura de cada célula de uma tal lista pode ser definida assim:struct cel { int conteudo; struct cel *prox; };
Estrutura de uma lista encadeada
• É conveniente tratar as células como um novo tipo-de-dado e atribuir um nome a esse novo tipo:– typedef struct cel celula;
• Uma célula c e um ponteiro p para uma célula podem ser declarados assim:– celula c; – celula *p;
Estrutura de uma lista encadeada
• Se c é uma célula então c.conteudo é o conteúdo da célula e c.prox é o endereço da próxima célula.
• Se p é o endereço de uma célula, então:– p->conteudo é o conteúdo da célula e– p->prox é o endereço da próxima célula. – Se p é o endereço da última célula da lista
então p->prox vale NULL.
Endereço de uma lista encadeada
• O endereço de uma lista encadeada é o endereço de sua primeira célula.
• Se p é o endereço de uma lista, convém, às vezes, dizer simplesmente "p é uma lista".
• Listas são entidades eminentemente recursivos.– Para tornar isso evidente, basta fazer a seguinte
observação: • se p é uma lista então vale uma das seguintes alternativas:
– p == NULL ou– p->prox é uma lista.
Listas com cabeça e sem cabeça
• Uma lista encadeada pode ser organizada de duas maneiras diferentes, um óbvia e outra menos óbvia.
• Lista com cabeça – O conteúdo da primeira célula é irrelevante: ela
serve apenas para marcar o início da lista. • A primeira célula é a cabeça (= head cell = dummy cell)
da lista. • A primeira célula está sempre no mesmo lugar na
memória, mesmo que a lista fique vazia.
Lista com cabeça
• Digamos que ini é o endereço da primeira célula.
• Então ini->prox == NULL se e somente se a lista está vazia. Para criar uma lista vazia, basta dizer
Lista sem cabeça
• Lista sem cabeça– O conteúdo da primeira célula é tão relevante
quanto o das demais. – Nesse caso, a lista está vazia se o endereço de sua
primeira célula é NULL. • Para criar uma lista vazia basta fazer
Alocação estática de memória
• As declarações abaixo alocam memória para diversas variáveis. A alocação é estática, pois acontece antes que o programa comece a ser executado:– char c; – int i; – int v[10];
Alocação dinâmica de memória
• Às vezes, a quantidade de memória a alocar só se torna conhecida durante a execução do programa.
• Para lidar com essa situação é preciso recorrer à alocação dinâmica de memória.
• A alocação dinâmica é gerenciada pelas funções:– malloc – Free
• que estão na biblioteca stdlib. – Para usar esta biblioteca, é preciso dizer
» #include <stdlib.h> no início do programa.
Função malloc
• A função malloc (abreviatura de memory allocation) – aloca um bloco de bytes consecutivos na memória do
computador • e devolve o endereço desse bloco. • O número de bytes é especificado no argumento da função.
• No seguinte fragmento de código, malloc aloca 1 byte: O endereço devolvido por malloc é do tipo
"genérico" void *. O programador armazena esse endereço num ponteiro de tipo apropriado. No exemplo ao lado, o endereço é armazenado num ponteiro-para-char.
Função malloc
• O que fazer para alocar um tipo-de-dado que ocupa vários bytes?– É preciso recorrer ao operador sizeof, que diz
quantos bytes o tipo especificado tem:
Atenção
• Overhead. Cada invocação de malloc aloca um bloco de bytes consecutivos maior que o solicitado: – os bytes adicionais são usados para guardar informações
administrativas sobre o bloco de bytes • essas informações permitem que o bloco seja corretamente
desalocado, mais tarde, pela função free.
– O número de bytes adicionais pode ser grande, mas não depende do número de bytes solicitado no argumento de malloc.
• Não é recomendável, portanto, invocar malloc repetidas vezes com argumento muito pequeno.
• É preferível alocar um grande bloco de bytes e retirar pequenas porções desse bloco na medida do necessário.
A memória é finita
• Se a memória do computador já estiver toda ocupada?– malloc não consegue alocar mais espaço • e devolve NULL.
• Convém verificar essa possibilidade antes de prosseguir:
Função Free
• As variáveis alocadas estaticamente dentro de uma função desaparecem quando a execução da função termina.
• Já as variáveis alocadas dinamicamente continuam a existir mesmo depois que a execução da função termina.
• Se for necessário liberar a memória ocupada por essas variáveis, é preciso recorrer à função free.
Função Free
• A função free libera a porção de memória alocada por malloc.
• O comando free( ptr) avisa o sistema de que o bloco de bytes apontado por ptr está livre.
• A próxima chamada de malloc poderá tomar posse desses bytes.
• A função free não deve ser aplicada a uma parte de um bloco de bytes alocado por malloc; – aplique free apenas ao bloco todo.
Função Free
• Convém não deixar ponteiros "soltos" (= dangling pointers) no seu programa– pois isso pode ser explorado por hackers para
atacar o seu computador. • Portanto, depois de cada free( ptr), atribua NULL a ptr:
Para saber mais
• Ler e entender os algoritmos descrito em:• http://www.inf.ufsc.br/~ine5384-hp/
Capitulo4/EstruturasListaEncadeada.html
Bibliografia
• http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html
• https://www.caelum.com.br%2Fapostila-java-estrutura-dados%2Flistas-ligadas