Estruturas de Dados: TAD Lista e Operações

TAD Lista Professor Alexandre Magno de Sousa Departamento de Computação e Sistemas Sumário TAD Lista Definição e operações Estrutura linear encadeada Aplicações Operações básicas Definição Uma lista é uma sequência de um ou mais itens na qual cada elemento xi é de um tipo estruturado de dado específico e n representa o tamanho da lista linear O elemento xi é dito estar na iésima posição da lista x1 x2 x3 xn1 xn Listas Uma das formas mais simples de interligar os elementos de um conjunto Podem crescer ou diminuir de tamanho durante a execução de um programa de acordo com a demanda Itens ou elementos 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 Aplicações Adequadas quando não é possível prever a demanda por memória permite a manipulação de quantidades imprevisíveis de dados de formato também imprevisível São úteis em aplicações tais como Sistemas comerciaisindustriais cadastro e gerenciamento de itens em um sistema específico Computadores gerência de memória e compiladores Simulação sistemas computacionais de linhas de produção etc 1 2 3 Lista encadeada dinamicamente 1 2 3 4 Lista encadeada dinamicamente 1 2 3 4 5 Lista encadeada dinamicamente Operações Conjunto de operações na maioria das aplicações Criar uma lista vazia Inserir um novo item Retirar um item da lista Localizar um item na lista e alterálo se necessário Combinar duas ou mais listas em uma lista Dividir uma lista em duas ou mais listas Fazer uma cópia da lista Ordenar os itens da lista em ordem crescente ou decrescente prox item Célula Lista primeiro ultimo Célula Cabeça tamanho 2 Operação de Inicialização FLVazia Lista primeiro ultimo tamanho Lista primeiro ultimo tamanho Alocação Dinâmica Lista primeiro ultimo tamanho Lista primeiro ultimo tamanho Lista primeiro ultimo NULL tamanho Lista primeiro ultimo NULL tamanho 0 Operação para verificar se a Lista está vazia Vazia Lista primeiro ultimo NULL tamanho 0 Verifica se a lista está vazia Lista primeiro ultimo NULL tamanho 0 Lista primeiro ultimo NULL tamanho 0 Alocação Dinâmica Lista primeiro ultimo NULL tamanho 0 prox Lista primeiro ultimo tamanho 0 prox Lista primeiro ultimo tamanho 0 prox Lista primeiro ultimo tamanho 0 prox Lista primeiro ultimo tamanho 0 prox Lista primeiro ultimo tamanho 0 Lista primeiro ultimo tamanho 0 item Lista primeiro ultimo tamanho 0 x item Lista primeiro ultimo tamanho 0 x prox Lista primeiro ultimo tamanho 0 x NULL Lista primeiro ultimo tamanho 0 x NULL Lista primeiro ultimo tamanho 1 x NULL Lista primeiro ultimo tamanho 1 x NULL Lista primeiro ultimo tamanho 1 x NULL Alocação Dinâmica Lista primeiro ultimo tamanho 1 x Lista primeiro ultimo tamanho 1 x Lista primeiro ultimo tamanho 1 x x Lista primeiro ultimo tamanho 1 x x NULL Lista primeiro ultimo tamanho 2 x x NULL Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Varredura na lista encadeada Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Varredura na lista encadeada Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Varredura na lista encadeada Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Varredura na lista encadeada Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Varredura na lista encadeada Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux prox Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux prox Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux item Exibe o valor do código Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux prox Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux item Exibe o valor do código Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux prox Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux item Exibe o valor do código Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux prox Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux item Exibe o valor do código Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Condição falsa Término do laço Lista primeiro ultimo tamanho 4 x1 x2 x4 NULL x3 Aux Término da função Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux prox itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux prox itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux prox itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 prox Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 prox Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 prox Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 Encontrado Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 um ponteiro para a célula anterior é retornado Lista primeiro ultimo tamanho 4 x1 x2 x4 x3 Aux itemcodigo 3 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 4 itemcodigo 3 Aux2 x1 x2 x4 x3 Aux1 Lista primeiro ultimo tamanho 3 itemcodigo 3 Aux2