Sociedade

FACULDADE DE COMPUTAÇÃO E INFORMÁTICA
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO, SISTEMAS DE INFORMAÇÃO E
TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS
Estrutura de Dados – Semana 2 – 1º SEMESTRE/2014

TEORIA: TAD VETOR (PARTE I)

Nossos objetivos nesta semana são:

apresentar o conceito e especificação do TAD Vetor implementar o TAD Vetor através de arranjos simples e arranjos extensíveis iniciar o estudo de avaliação de eficiência temporal das operações sobre o TAD Vetor via análise assintótica O(.) estudar as implementações Vector e ArrayList da Java Collections.

Para esta semana, usamos como referências a seção 6.1 Listas Arranjo (exceto a subseção 6.1.2) no nosso livro-texto:

GOODRICH, M.T.; TAMASSIA, R. Estruturas de Dados & Algoritmos em Java. 5.ed. Bookman: Porto Alegre, 2010.

Não deixem de ler esta seção durante esta semana!

CONCEITO DE VETOR (ou LISTA-ARRANJO)

Um vetor (ou lista-arranjo, num nome mais moderno) de tamanho N é uma coleção V de N elementos, armazenados de forma linear, de tal maneira que se possa acessar seus elementos através de um índice (posição). No exemplo abaixo, temos um vetor de tamanho 4, com indexação feita a partir do índice 0.

Como um TAD, o vetor deve suportar as seguintes operações:

Operação
Significado
Restrição empty (N) cria um vetor vazio com capacidade para N elementos
N ≥ 1 isEmpty() verifica se o vetor está vazio, isto é, não contém elementos

size() devolve o tamanho do vetor, isto é, quantos elementos estão inseridos no vetor

get(i) retorna o elemento de índice i
0 ≤ i ≤ N-1 set(i,E) substitui por E e retorna o elemento de índice i
0 ≤ i ≤ N-1 add (i,E) insere um novo elemento E no índice i
0 ≤ i ≤ N-1 remove (i) remove o elemento de índice i
0 ≤ i ≤ N-1

A seguir, tem-se a especificação do TAD Vetor:

TYPE Vector sorts Vector, Integer, Boolean, Element operations empty: Integer  Vector isEmpty: Vector 