Estruturas De Dados Listas

TRABALHO ACADÊMICO EFETIVO

SISTEMAS DE INFORMAÇÃO

Estrutura de Dados

Listas

Lucas Jose da Rocha

Unaí-MG, 25 de setembro de 2014

Sumário

1. ....................................................................................................................Introdução

2. .......................................................................................................................Conceito

3. ...............................................................................................................Apresentação

4. ....................................................................................................................Conclusão

5. .............................................................................................. Referência Bibliográfica

1. Introdução:

Uma Lista é uma estrutura de dados linear que e ligadas, chamada de Encadeada também duplamente e simplesmente encadeada, é circular e dinâmica e também Lista de prioridades, são listas compostas por nós que apontam para o próximo elemento da lista, o último elemento apontará para nulo. Para compor uma lista encadeada, basta guardar seu primeiro elemento.

As operações mais frequentes em listas são a busca, a inclusão e a remoção de um determinado elemento, o que, aliás, ocorre na maioria das estruturas de dados.

Lista também é uma sequência ordenada de elementos do mesmo tipo. Por exemplo, um conjunto de fichas de clientes de uma loja, organizadas pela ordem alfabética dos nomes dos clientes. Neste fichário é possível introduzir uma nova ficha ou retirar uma velha, alterar os dados de um cliente etc. Do ponto de vista matemático, uma lista é uma sequência de zero ou mais elementos de um determinado tipo, Geralmente se representa uma lista de elementos, separando-os por vírgulas, que implementa uma coleção ordenada de valores, onde o mesmo valor pode ocorrer mais de uma vez.

2. Conceito

Listas e uma estrutura de dados amplamente utilizada e que implementa a ideia de elementos:

• FIFO (first-in-first-out ou primeiro a entrar, primeiro a sair)

• Permite a adição e remoção de elementos

• O elemento a ser removido e sempre o primeiro a entrar

• As operações de entrada e saída sempre ocorrem nas extremidades

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.

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.

struct cel {

int conteudo;

struct cel *prox;

};

Listas com cabeça e sem cabeça:

celula c, *ini;

c.prox = NULL;

ini = &c;

ou celula *ini;

ini = malloc( sizeof (celula));

ini->prox = NULL;

Inserção em uma lista:

Quero inserir (= insert) uma nova célula com conteúdo x entre a posição apontada pela posição seguinte [por que seguinte e não anterior?] em uma lista encadeada. É claro que isso só faz sentido se p é diferente de NULL

void insere( int x, celula *p)

{

...