51
INE5408 Estruturas de Dados Estruturas de Dados básicas utilizando Vetores - Listas

INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

  • Upload
    dinhque

  • View
    223

  • Download
    1

Embed Size (px)

Citation preview

Page 1: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

INE5408Estruturas de Dados

Estruturas de Dados básicas utilizando Vetores

- Listas

Page 2: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Lista - DefiniçãoUma Lista é um conjunto de dados dispostos e / ou acessáveis em uma seqüência determinada.– Este conjunto de dados pode possuir uma

ordem intrínseca (Lista Ordenada) ou não;– este conjunto de dados pode ocupar

espaços de memória fisicamente consecutivos, espelhando a sua ordem, ou não;

– se os dados estiverem dispersos fisicamente, para que este conjunto seja uma lista, ele deve possuir operações e informações adicionais que permitam que seja tratado como tal (Lista Encadeada).

Page 3: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Vimos dois aspectosEm um projeto de software, dois aspectos devem ser considerados:

• de que forma estão organizados os dados, qual a sua estrutura;

• quais procedimentos atuam sobre estes dados, que operações podem ser realizadas sobre eles.

• Vamos ver agora estes aspectos para as listas.

Page 4: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Listas • A Lista é uma estrutura de dados cujo funcionamento é inspirado no de uma lista “natural”.

20554128924

89552420124 • Uma lista pode ser ordenada ou

não:• quando for ordenada, pode o ser por

alguma característica intrínseca dos dados (ex: ordem alfabética);

• pode também refletir a ordem cronológica (ordem de inserção) dos dados;

• em Smalltalk, a OrderedCollection éuma lista cronológica (add:), a SortedCollection é uma lista ordenada por um critério interno.

Page 5: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Listas usando Vetores

-1012345

Listacheia

Listavazia

20554128924

• Vetores possuem um espaço limitado para o armazenamento de dados;

• necessitamos definir um espaço grande o suficiente para a lista;

• necessitamos de um indicador de qual elemento do vetor é o atual último elemento da lista.

Page 6: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem de Listas utilizando Programação Estruturada

• Modelaremos a Estrutura de Dados Lista utilizando a técnica da Programação Estruturada, armazenando os dados em um Vetor (Array).– Veremos somente algoritmos;– veremos algoritmos tanto para uma lista

cronológica quanto para uma lista ordenada.

• Procedimento Didático:– modelagem da Lista e de seus algoritmos usando

a técnica estruturada;– exercícios.

Page 7: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem da Lista• Aspecto Estrutural:

– necessitamos de um vetor para armazenar as informações;– necessitamos de um indicador da posição atual do último

elemento da lista;– necessitamos de uma constante que nos diga quando a lista

está cheia e duas outras para codificar erros.

• Pseudo-código:constantes MAXLISTA = 100;

tipo Lista {inteiro dados[MAXLISTA];inteiro último;

};

Page 8: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem da Lista• Aspecto Funcional:

– colocar e retirar dados da lista;– testar se a lista está vazia ou cheia (dentre

outros testes);– inicializar a lista e garantir a ordem de seus

elementos.

Page 9: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem da Lista• Operações: adicionar e retirar dados da lista

– Adiciona(dado)– AdicionaNoInício(dado)– AdicionaNaPosição(dado, posição)– AdicionaEmOrdem(dado)– Retira()– RetiraDoInício()– RetiraDaPosição(posição)– RetiraEspecífico(dado)

Page 10: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem da Lista• Operações: testar a lista

– ListaCheia– ListaVazia– Posição(dado)– Contém(dado)– Igual(dado1, dado2)– Maior(dado1, dado2)– Menor(dado1, dado2)

Page 11: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem da Lista• Operações: inicializar ou limpar a lista

– InicializaLista– DestróiLista

Page 12: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo InicializaLista

FUNÇÃO inicializaLista()início

aLista.último <- -1;fim;

Observação: este e os próximos algoritmospressupõem que foi definida uma variávelglobal tipo Lista denominada aLista.

Page 13: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo DestróiLista

FUNÇÃO destróiLista()início

aLista.último <- -1;fim;

Observação: este algoritmo parece redundante. Colocar a sua semântica em separado dainicialização, porém, é importante. Mais tardeveremos que, utilizando alocação dinâmica de memória, possuir um destrutor para aLista é muitoimportante.

Page 14: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo ListaCheia

Booleano FUNÇÃO listaCheia()início

SE (aLista.último = MAXLISTA - 1) ENTÃORETORNE(Verdadeiro)

SENÃORETORNE(Falso);

fim;

Page 15: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo ListaVazia

Booleano FUNÇÃO listaVazia()início

SE (aLista.último = -1) ENTÃORETORNE(Verdadeiro)

SENÃORETORNE(Falso);

fim;

Page 16: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo Adiciona• Procedimento:

– testamos se há espaço;– incrementamos o último;– adicionamos o novo dado.

• Parâmetros:– o dado a ser inserido;– Lista (global).

45

20554128924

Page 17: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaConstantes

ERROLISTACHEIA = -1;ERROLISTAVAZIA = -2;ERROPOSIÇÃO = -3;

Inteiro FUNÇÃO adiciona(inteiro dado)início

SE (listaCheia) ENTÃORETORNE(ERROLISTACHEIA)

SENÃOaLista.último <- aLista.último + 1;aLista.dados[aLista.último] <- dado;RETORNE(aLista.último);

FIM SEfim;

Page 18: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo Retira

• Procedimento:– testamos se há elementos;– decrementamos o último;– devolvemos o último elemento.

• Parâmetros:– Lista (global).

Page 19: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraInteiro FUNÇÃO retira()

inícioSE (listaVazia) ENTÃO

RETORNE(ERROLISTAVAZIA)SENÃO

aLista.último <- aLista.último – 1;RETORNE(aLista.dados[aLista.último +

1]);FIM SE

fim;

Observação: note que aqui se aplicam as mesmas restriçõesdas diversas variantes do algoritmo desempilha.

Page 20: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNoInício• Procedimento:

– testamos se há espaço;– incrementamos o último;– empurramos tudo para

trás;– adicionamos o novo dado

na primeira posição.• Parâmetros:

– o dado a ser inserido;– Lista (global).

4

554128924 5

55412892420

Page 21: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNoInícioInteiro FUNÇÃO adicionaNoInício(inteiro dado)

variáveisinteiro posição; //Variável auxiliar para “caminhar”

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

aLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > 0) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[0] <- dado;RETORNE(0);

FIM SEfim;

Page 22: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNoInícioInteiro FUNÇÃO adicionaNoInício(inteiro dado)

variáveisinteiro posição; //Variável auxiliar para “caminhar”

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

aLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > 0) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[0] <- dado;RETORNE(0);

FIM SEfim;

Page 23: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNoInícioInteiro FUNÇÃO adicionaNoInício(inteiro dado)

variáveisinteiro posição; //Variável auxiliar para “caminhar”

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

aLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > 0) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[0] <- dado;RETORNE(0);

FIM SEfim;

Page 24: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNoInícioInteiro FUNÇÃO adicionaNoInício(inteiro dado)

variáveisinteiro posição; //Variável auxiliar para “caminhar”

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

aLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > 0) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[0] <- dado;RETORNE(0);

FIM SEfim;

Page 25: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDoInício• Procedimento:

– testamos se há elementos;– decrementamos o último;– salvamos o primeiro

elemento;– empurramos tudo para a

frente.• Parâmetros:

– Lista (global).

5420

554128924

554128924 20

Page 26: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDoInícioInteiro FUNÇÃO retiraDoInício()

variáveisinteiro posição, valor;

inícioSE (listaVazia) ENTÃO

RETORNE(ERROLISTAVAZIA)SENÃO

aLista.último <- aLista.último - 1;valor <- aLista.dados[0];posição <- 0;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para a frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEfim;

Page 27: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDoInícioInteiro FUNÇÃO retiraDoInício()

variáveisinteiro posição, valor;

inícioSE (listaVazia) ENTÃO

RETORNE(ERROLISTAVAZIA)SENÃO

aLista.último <- aLista.último - 1;valor <- aLista.dados[0];posição <- 0;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para a frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEfim;

Page 28: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDoInícioInteiro FUNÇÃO retiraDoInício()

variáveisinteiro posição, valor;

inícioSE (listaVazia) ENTÃO

RETORNE(ERROLISTAVAZIA)SENÃO

aLista.último <- aLista.último - 1;valor <- aLista.dados[0];posição <- 0;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para a frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEfim;

Page 29: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDoInícioInteiro FUNÇÃO retiraDoInício()

variáveisinteiro posição, valor;

inícioSE (listaVazia) ENTÃO

RETORNE(ERROLISTAVAZIA)SENÃO

aLista.último <- aLista.último - 1;valor <- aLista.dados[0];posição <- 0;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para a frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEfim;

Page 30: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNaPosição

• Procedimento:– testamos se há espaço e se a posição existe;– incrementamos o último;– empurramos tudo para trás a partir da posição;– adicionamos o novo dado na posição informada.

• Parâmetros:– o dado a ser inserido;– a posição onde inserir;– Lista (global).

Page 31: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNaPosiçãoInteiro FUNÇÃO adicionaNaPosição(inteiro dado, inteiro destino)

variáveisinteiro posição;

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

SE (destino > aLista.último + 1 OU destino < 0) ENTÃORETORNE(ERROPOSIÇÃO);

FIM SEaLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > destino) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[destino] <- dado;RETORNE(aonde);

FIM SEfim;

Page 32: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNaPosiçãoInteiro FUNÇÃO adicionaNaPosição(inteiro dado, inteiro destino)

variáveisinteiro posição;

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

SE (destino > aLista.último + 1 OU destino < 0) ENTÃORETORNE(ERROPOSIÇÃO);

FIM SEaLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > destino) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[destino] <- dado;RETORNE(aonde);

FIM SEfim;

Page 33: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNaPosiçãoInteiro FUNÇÃO adicionaNaPosição(inteiro dado, inteiro destino)

variáveisinteiro posição;

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

SE (destino > aLista.último + 1 OU destino < 0) ENTÃORETORNE(ERROPOSIÇÃO);

FIM SEaLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > destino) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[destino] <- dado;RETORNE(aonde);

FIM SEfim;

Page 34: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaNaPosiçãoInteiro FUNÇÃO adicionaNaPosição(inteiro dado, inteiro destino)

variáveisinteiro posição;

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

SE (destino > aLista.último + 1 OU destino < 0) ENTÃORETORNE(ERROPOSIÇÃO);

FIM SEaLista.último <- aLista.último + 1;posição <- aLista.último;ENQUANTO (posição > destino) FAÇA

//Empurrar tudo para trásaLista.dados[posição] <-

aLista.dados[posição - 1];posição <- posição - 1;

FIM ENQUANTOaLista.dados[destino] <- dado;RETORNE(aonde);

FIM SEfim;

Page 35: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDaPosição• Procedimento:

– testamos se há elementos e se a posição existe;

– decrementamos o último;– salvamos elemento na posição;– empurramos tudo para frente até posição.

• Parâmetros:– o dado a ser inserido;– a posição onde inserir;– Lista (global).

Page 36: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDaPosiçãoInteiro FUNÇÃO retiraDaPosição(inteiro fonte)

variáveisinteiro posição, valor;

inícioSE (fonte > aLista.último OU fonte < 0) ENTÃO

RETORNE(ERROPOSIÇÃO)SENÃO

SE (listaVazia) ENTÃORETORNE(ERROLISTAVAZIA)

SENÃOaLista.último <- aLista.último - 1;valor <- aLista.dados[fonte];posição <- fonte;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEFIM SE

fim;

Page 37: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDaPosiçãoInteiro FUNÇÃO retiraDaPosição(inteiro fonte)

variáveisinteiro posição, valor;

inícioSE (fonte > aLista.último OU fonte < 0) ENTÃO

RETORNE(ERROPOSIÇÃO)SENÃO

SE (listaVazia) ENTÃORETORNE(ERROLISTAVAZIA)

SENÃOaLista.último <- aLista.último - 1;valor <- aLista.dados[fonte];posição <- fonte;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEFIM SE

fim;

Page 38: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDaPosiçãoInteiro FUNÇÃO retiraDaPosição(inteiro fonte)

variáveisinteiro posição, valor;

inícioSE (fonte > aLista.último OU fonte < 0) ENTÃO

RETORNE(ERROPOSIÇÃO)SENÃO

SE (listaVazia) ENTÃORETORNE(ERROLISTAVAZIA)

SENÃOaLista.último <- aLista.último - 1;valor <- aLista.dados[fonte];posição <- fonte;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEFIM SE

fim;

Page 39: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDaPosiçãoInteiro FUNÇÃO retiraDaPosição(inteiro fonte)

variáveisinteiro posição, valor;

inícioSE (fonte > aLista.último OU fonte < 0) ENTÃO

RETORNE(ERROPOSIÇÃO)SENÃO

SE (listaVazia) ENTÃORETORNE(ERROLISTAVAZIA)

SENÃOaLista.último <- aLista.último - 1;valor <- aLista.dados[fonte];posição <- fonte;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEFIM SE

fim;

Page 40: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraDaPosiçãoInteiro FUNÇÃO retiraDaPosição(inteiro fonte)

variáveisinteiro posição, valor;

inícioSE (fonte > aLista.último OU fonte < 0) ENTÃO

RETORNE(ERROPOSIÇÃO)SENÃO

SE (listaVazia) ENTÃORETORNE(ERROLISTAVAZIA)

SENÃOaLista.último <- aLista.último - 1;valor <- aLista.dados[fonte];posição <- fonte;ENQUANTO (posição <= aLista.último) FAÇA

//Empurrar tudo para frenteaLista.dados[posição] <-

aLista.dados[posição + 1];posição <- posição + 1;

FIM ENQUANTORETORNE(valor);

FIM SEFIM SE

fim;

Page 41: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaEmOrdem• Procedimento:

– necessitamos de uma função para comparar os dados (maior);

– testamos se há espaço;– procuramos pela posição onde inserir

comparando dados;– chamamos adicionaNaPosição.

• Parâmetros:– o dado a ser inserido;– Lista (global).

Page 42: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo MaiorBooleano FUNÇÃO maior(inteiro dado1, inteiro dado2)

inícioSE (dado1 > dado2) ENTÃO

RETORNE(Verdadeiro)SENÃO

RETORNE(Falso);FIM SE

fim;

Observação: quando o dado a ser armazenado em uma lista for algo mais complexo do que um inteiro, a comparação de precedência não será mais tão simples (ex.: Empregado1 > Empregado2) e será resultado de um conjunto mais complexo de operações.Para deixar os algoritmos de operações sobre lista independentes do tipo de dado específico armazenado na lista, usamos uma função deste tipo.

Page 43: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo AdicionaEmOrdemInteiro FUNÇÃO adicionaEmOrdem(inteiro dado)

variáveisinteiro posição; //Variável auxiliar para “caminhar”

inícioSE (listaCheia) ENTÃO

RETORNE(ERROLISTACHEIA)SENÃO

posição <- 0;ENQUANTO (posição <= aLista.último E

maior(dado, aLista.dados[posição])) FAÇA//Encontrar posição para inserirposição <- posição + 1;

FIM ENQUANTORETORNE(adicionaNaPosição(dado, posição));

FIM SEfim;

Page 44: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraEspecífico• Retira um dado específico da lista.• Procedimento:

– testamos se há elementos;– testamos se o dado existe e qual sua

posição;– necessitamos de uma função Posição(dado);

– chamamos RetiraDaPosição.• Parâmetros:

– o dado a ser retirado;– Lista (global).

Page 45: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo PosiçãoInteiro FUNÇÃO posição(inteiro dado)

variáveisinteiro posição;

inícioposição <- 0;ENQUANTO (posição <= aLista.último E

NÃO(IGUAL(dado,aLista.dados[posição]))) FAÇA posição <- posição + 1;

FIM ENQUANTOSE (posição > aLista.último) ENTÃORETORNE(ERROPOSIÇÃO)

SENÃORETORNE(posição);

FIM SEfim;

Page 46: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmo RetiraEspecíficoInteiro FUNÇÃO retiraEspecífico(inteiro dado)

variáveisinteiro posição;

inícioSE (listaVazia) ENTÃO

RETORNE(ERROLISTAVAZIA)SENÃO

posição <- posição(dado);SE (posição < 0) ENTÃO

RETORNE(ERROPOSIÇÃO)SENÃO

RETORNE(retiraDaPosição(posição));FIM SE

FIM SEfim;

Page 47: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Algoritmos Restantes• As seguintes funções ficam por conta do

aluno :

– booleano Contém(dado)– booleano Igual(dado1, dado2)– booleano Menor(dado1, dado2)

Page 48: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Exercício de Implementação 3Implemente uma lista em um vetor utilizando a

linguagem de programação “C” e a técnica estruturada de programação.– Crie o seu tipo de dados tLista em um headerfile;– esta deverá ser uma lista de elementos do tipo tAgenda;– o tipo tAgenda é um tipo que representa um nome de 30

posições e um número de telefone;– crie uma função maior(a,b) que compare os nomes de duas

entradas;– programe todas as funções documentando cada função,

inclusive com dicionário de dados;– crie um programa principal que execute todas as funções de

lista a partir de um menu. A função procurar específicodeverá basear-se no nome em uma Agenda;

– além destas funções, o programa deverá ser capaz de listar a lista em ordem alfabética.

Page 49: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem dos Tiposconstantes MAXLISTA = 100;

tipo tAgenda {caracter nome[31];caracter fone[11];

};

tipo tLista {tAgenda dados[MAXLISTA];inteiro último;

};

Page 50: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Modelagem em “C”#define MAXLISTA 100

typedef struct {char nome[31];char fone[11];

} tAgenda;

typedef struct {tAgenda dados[MAXLISTA];int ultimo;

} tLista;

Acessando:x = aLista.dados[10].fone;

Page 51: INE5408 Estruturas de Dados - moodle.ufsc.br · Estruturas de Dados Estruturas de Dados básicas utilizando Vetores-Listas. Lista - Definição Uma Lista é um conjunto de dados dispostos

Para comparar Strings em “C”• Utilize a função de comparação de strings strcmp();

• esta função utiliza ponteiros para strings como parâmetros. Isto não é importante agora; você pode utilizar diretamente o nome de um string;

• observe que a linguagem “C” não permite a atribuição de strings de uma variável para a outra usando-se o comando de atribuição. Isto ocorre porque em “C” um string não é um tipo primitivo, mas sim um tipo composto;

• utilize a função strcpy() para isto;• para as duas funções acima você deve incluir

<string.h>.