Embed Size (px)
Citation preview
Estruturas Fundamentais
2
Sumário
Objetivo do CursoEstruturas de Dados FundamentaisImplementação Java A classe Array A classe LinkedList
Implementação C++ A classe Array A classe LinkedList
3
Objetivo do Curso
Estudo de tipos abstratos de dados tais como Pilhas Filas Deques Listas Árvores Filas de Prioridades etc
4
Estruturas de Dados Fundamentais
As Estruturas de Dados Fundamentais para a criação dos tipos abstratos de dados são: Arrays Listas Encadeadas
5
Características das Linguagens
Nenhuma linguagem de programação possui nativa a classe Lista Encadeada. Assim será necessário implementar esta classe.A classe array é nativa de toda linguagem de programaçãoEm C++ não existe expressões sobre arrays. Não se pode passar um array como parâmentro de função nem retornar um array de uma função. Não se pode atribuir o valor de um array a a outro array Na linguagem Java é usual criar uma extensão para a classe Array
Implementação Java
Classe Array
8
Arrays primitivos em Java
Os arrays em Java possuem três limitações que seria interessante contornar: Índices sempre vão de 0 até n-1 Não existe atribuição para todo um array O tamanho de um array não pode ser alterado
Para contornar estas limitações pode-se definir uma extensão : a classe Array
9
Classe Array (extensão a Java)
public class Array{ protected Object[] data; protected int base;
// ...}
10
Construtores da classe Array
public class Array{ protected Object[] data; protected int base;
public Array (int n, int m) {
data = new Object[n];base = m;
}
public Array (){ this (0, 0); }
public Array (int n){ this (n, 0); }
// ...}
11
Método assign
public class Array{ // cria uma cópia da lista corrente protected Object[] data; protected int base;
public void assign (Array array) {
if (array != this){ if (data.length != array.data.length)
data = new Object [array.data.length]; for (int i = 0; i < data.length; ++i)
data [i] = array.data [i]; base = array.base;}
} // ...}
12
Métodos getData, getBase e getLength
public class Array{ protected Object[] data; protected int base;
public Object[] getData (){ return data; }
public int getBase (){ return base; }
public int getLength (){ return data.length; }
// ...}
13
Métodos de indexação get e put
public class Array{ protected Object[] data; protected int base;
public Object get (int position) {
return data [position - base]; }
public void put (int position, Object object) {
data [position - base] = object; }
// ...}
14
Emprego de get e put
Caso se desejasse fazer a[2] = b[3] usando a classe Array escrever-se-ia
a.getData()[2] = b.getData()[3];Isto é feio e como não existe sobrecarga de operadores em Java definem-se métodos de indexação get e put obtendo
a.put (2, b.get (3));
15
Redimensionamento – Métodos setBase e setLength
public class Array { protected Object[] data; protected int base; public void setBase (int base) {
this.base = base; }
public void setLength (int newLength) {if(data.length != newLength) {
Object[] newData = new Object[newLength]; int min = data.length < newLength ? data.length :
newLength; for(int i = 0; i < min; ++i)
newData [i] = data [i]; data = newData;
} } // ...}
Classe LinkedList
17
Classe LinkedList
public class LinkedList { protected Element head; // cabeça protected Element tail; // cauda public final class Element { // elemento do lista
Object datum; // dado do elemento ou item
Element next; // ponteiro para sucessorElement(Object datum, Element next) { // construtor
this.datum = datum; this.next = next;
}public Object getDatum() // obter dado
{ return datum; }public Element getNext() // obter sucessor
{ return next; }// ...
} // ...}
18
Métodos Construtor e purge
public class LinkedList{ protected Element head; protected Element tail; public LinkedList () // construir uma lista
{}
public void purge () // esvaziar uma lista {
head = null;tail = null;
} // ...}
19
Métodos getHead, getTail e isEmpty
public class LinkedList{ protected Element head; protected Element tail; public Element getHead () // cabeça da lista
{ return head; } public Element getTail () // cauda da lista
{ return tail; } public boolean isEmpty () //teste de lista vazia
{ return head == null; }
// ...}
20
Métods getFirst e getLast
public class LinkedList { protected Element head; protected Element tail; public Object getFirst() { // obter o primeiro elemento
//da lista if(head == null)
throw new ContainerEmptyException();return head.datum;
}
public Object getLast() {// obter o último elemento //da lista
if(tail == null) throw new ContainerEmptyException();
return tail.datum; } // ...}
21
Método prepend
public class LinkedList{
protected Element head; protected Element tail;
// inluir o objeto item no início da lista corrente public void prepend(Object item) {
Element tmp = new Element(item, head); if(head == null)
tail = tmp; head = tmp;
}
// ...}
22
Método append
public class LinkedList{ protected Element head; protected Element tail;
// incluir o objeto item no final da lista corrente public void append (Object item) {
Element tmp = new Element (item, null); if(head == null) head = tmp; else
tail.next = tmp; tail = tmp;
}
// ...}
23
Método assign
public class LinkedList { protected Element head; protected Element tail;// a lista list será uma cópia da lista corrente public void assign(LinkedList list) {
if(list != this){
purge (); for(Element ptr = list.head;
ptr != null; ptr = ptr.next) {
append (ptr.datum); }
} } // ...}
24
Método extract (1)
public class LinkedList{ protected Element head; protected Element tail;
// Exclui objeto item public void extract(Object item)
{Element ptr = head;Element prevPtr = null;while(ptr != null && ptr.datum != item){
prevPtr = ptr; ptr = ptr.next;
}
25
Método extract (2)
if(ptr == null) throw new IllegalArgumentException("item
not found");if(ptr == head)
head = ptr.next;else
prevPtr.next = ptr.next;if(ptr == tail)
tail = prevPtr; }
// ...}
26
Métodos insertAfter e insertBefore (1)
public class LinkedList { protected Element head; protected Element tail; public final class Element
{Object datum;Element next;
// Inclui item depois do objeto correntepublic void insertAfter(Object item){ next = new Element (item, next);
if(tail == this) tail = next;
}
27
Métodos insertAfter e insertBefore (2)
// Inclui item antes do objeto correntepublic void insertBefore(Object item) { Element tmp = new Element(item, this);
if(this == head) head = tmp;
else { Element prevPtr = head; while(prevPtr != null && prevPtr.next != this)
prevPtr = prevPtr.next; prevPtr.next = tmp;
}}
// ... }
// ...}
Implementação C++
Classe Array
30
31
Definição da Classe Array<T> (1)
// pgm04_01.cpp
template <class T>class Array{protected: T* data; unsigned int base; unsigned int length;public: Array(); Array(unsigned int, unsigned int = 0); ~Array();
Array(Array const&); Array& operator = (Array const&);
32
Definição da Classe Array<T> (2)
// pgm04_01.cpp (Continuação)
T const& operator [] (unsigned int) const;
T& operator [] (unsigned int);
T const* Data () const; unsigned int Base () const; unsigned int Length () const;
void SetBase (unsigned int); void SetLength (unsigned int);
};
33
O Construtor Default da Classe Array<T>
// pgm04_02.cpp
template <class T>
Array<T>::Array () :
data (new T [0]),
base (0),
length (0)
{}
34
Definição do Construtor com tamanho da Classe Array<T>
// pgm04_03.cpp
template <class T>Array<T>::Array (unsigned int n, unsigned int m) : data (new T [n]), base (m), length (n) {}
35
Construtor Copy da Classe Array<T>
// pgm04_04.cpp
template <class T>Array<T>::Array (Array<T> const& array) : data (new T [array.length]), base (array.base), length (array.length)
{ for(unsigned int i = 0; i < length; ++i)
data [i] = array.data [i]; }
36
Destrutor da Classe Array<T>
// pgm04_05.cpp
template <class T>Array<T>::~Array (){
delete [] data;}
37
Definição de Funções Accessor da Classe Array <T>
// pgm04_06.cpp
template <class T>T const* Array<T>::Data () const { return data; }
template <class T>unsigned int Array<T>::Base () const { return base; }
template <class T>unsigned int Array<T>::Length () const { return length; }
38
Definição de Função Operador subscrito da Classe Array <T>
// pgm04_07.cpp
template <class T>T const& Array<T>::operator [] (unsigned int position) const { unsigned int const offset = position - base; if(offset >= length)
throw out_of_range ("invalid position"); return data [offset];}template <class T>T& Array<T>::operator [] (unsigned int position) { unsigned int const offset = position - base; if (offset >= length)
throw out_of_range ("invalid position"); return data [offset];}
39
Redimensionamento de “arrays”
// pgm04_08.cpp
template <class T>void Array<T>::SetBase (unsigned int newBase) { base = newBase; }
template <class T>void Array<T>::SetLength (unsigned int newLength) { T* const newData = new T [newLength]; unsigned int const min = length < newLength ? length :
newLength;
for(unsigned int i = 0; i < min; ++i) newData [i] = data [i];
delete [] data; data = newData; length = newLength;}
Classe LinkedList
41
Implementação
42
Definição das Classes LinkedList<T> e ListElement<T> (1)
// pgm04_09.cpp
template <class T>class LinkedList;
template <class T>class ListElement { T datum; ListElement* next; ListElement (T const&, ListElement*);public: T const& Datum () const; ListElement const* Next () const;
friend LinkedList<T>;};
43
Definição das Classes LinkedList<T> e ListElement<T> (2)
// pgm04_09.cpp (Continuação)
template <class T>class LinkedList{ ListElement<T>* head; ListElement<T>* tail;public: LinkedList (); ~LinkedList ();
LinkedList (LinkedList const&); LinkedList& operator = (LinkedList const&);
44
Definição das Classes LinkedList<T> e ListElement<T> (3)
// pgm04_09.cpp (Continuação)
ListElement<T> const* Head () const; ListElement<T> const* Tail () const; bool IsEmpty () const; T const& First () const; T const& Last () const;
void Prepend (T const&); void Append (T const&); void Extract (T const&); void Purge (); void InsertAfter (ListElement<T> const*, T const&); void InsertBefore (ListElement<T> const*, T const&);};
45
Definição de Funções Membro da Classe ListElement<T>
// pgm04_10.cpp
template <class T>ListElement<T>::ListElement ( T const& _datum, ListElement<T>* _next) : datum (_datum), next (_next) {}
template <class T>T const& ListElement<T>::Datum () const { return datum; }
template <class T>ListElement<T> const* ListElement<T>::Next () const { return next; }
46
Construtor Default da Classe ListElement<T>
// pgm04_11.cpp
template <class T>
LinkedList<T>::LinkedList () :
head (0),
tail (0)
{}
47
Definição de Funções Membro Destrutor e Purge da Classe ListElement<T>
// pgm04_12.cpp
template <class T>void LinkedList<T>::Purge (){ while (head != 0) {
ListElement<T>* const tmp = head; head = head->next; delete tmp;
} tail = 0;}template <class T>LinkedList<T>::~LinkedList () { Purge (); }
48
Definição de Funções Accessor da Classe ListElement<T>
// pgm04_13.cpp
template <class T>ListElement<T> const* LinkedList<T>::Head () const { return head; }
template <class T>ListElement<T> const* LinkedList<T>::Tail () const { return tail; }
template <class T>bool LinkedList<T>::IsEmpty () const { return head == 0; }
49
Definição de Funções First e Last da Classe ListElement<T>
// pgm04_14.cpp
template <class T>T const& LinkedList<T>::First () const{ if(head == 0)
throw domain_error ("list is empty"); return head->datum;}
template <class T>T const& LinkedList<T>::Last () const{ if(tail == 0)
throw domain_error ("list is empty"); return tail->datum;}
50
Definição de Função Prepend da Classe ListElement<T>
// pgm04_15.cpp
template <class T>void LinkedList<T>::Prepend (T const& item){ ListElement<T>* const tmp = new ListElement<T>(item,
head);
if(head == 0)tail = tmp;
head = tmp;}
51
Definição de Função Append da Classe ListElement<T>
// pgm04_16.cpp
template <class T>void LinkedList<T>::Append (T const& item){ ListElement<T>* const tmp = new ListElement<T> (item, 0); if(head == 0)
head = tmp; else
tail->next = tmp; tail = tmp;}
52
Definição de Função Construtor Copy da Classe ListElement<T> (1)
// pgm04_17.cpp
template <class T>LinkedList<T>::LinkedList (LinkedList<T> const& linkedList) : head (0), tail (0){ ListElement<T> const* ptr; for(ptr = linkedList.head; ptr != 0; ptr = ptr->next)
Append (ptr->datum);}
53
Definição de Função Construtor Copy da Classe ListElement<T> (2)
template <class T>LinkedList<T>& LinkedList<T>::operator = (LinkedList<T> const&
linkedList){ if(&linkedList != this) {
Purge (); ListElement<T> const* ptr; for(ptr = linkedList.head; ptr != 0; ptr = ptr-
>next) Append (ptr->datum);
} return *this;}
54
Definição de Função Extract da Classe ListElement<T> (1)
// pgm04_18.cpp
template <class T>void LinkedList<T>::Extract (T const& item){ ListElement<T>* ptr = head; ListElement<T>* prevPtr = 0; while(ptr != 0 && ptr->datum != item) {
prevPtr = ptr; ptr = ptr->next;
}
55
Definição de Função Extract da Classe ListElement<T> (2)
// pgm04_18.cpp (Continuação)
if(ptr == 0) throw invalid_argument ("item not found");
if(ptr == head) head = ptr->next;
else prevPtr->next = ptr->next;
if(ptr == tail) tail = prevPtr;
delete ptr;}
56
Definição de Funções InsertAfter e InsertBefore da Classe ListElement<T> (1)
// pgm04_19.cpp
template <class T>
void LinkedList<T>::InsertAfter (ListElement<T> const* arg,
T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if(ptr == 0)
throw invalid_argument ("invalid position");
ListElement<T>* const tmp = new ListElement<T>(item,
ptr->next);
ptr->next = tmp;
if(tail == ptr)
tail = tmp;
}
57
Definição de Funções InsertAfter e InsertBefore da Classe ListElement<T> (2)
template <class T>void LinkedList<T>::InsertBefore (ListElement<T> const* arg,
T const& item){ ListElement<T>* ptr = const_cast<ListElement<T>*> (arg); if(ptr == 0)
throw invalid_argument ("invalid position"); ListElement<T>* const tmp = new ListElement<T>(item, ptr);
58
Definição de Funções InsertAfter e InsertBefore da Classe ListElement<T> (3)
if(head == ptr)head = tmp;
else {
ListElement<T>* prevPtr = head;while(prevPtr != 0 && prevPtr->next != ptr)
prevPtr = prevPtr->next;if(prevPtr == 0)
throw invalid_argument ("invalid position");prevPtr->next = tmp;
}}
Arrays Multi dimensionais
60
Cálculo de índice
61
Definição das Classes Array2D<T> e Array2D<T>::Row (1)
// pgm04_20.cpp
template <class T>class Array2D{protected: unsigned int numberOfRows; unsigned int numberOfColumns; Array<T> array;
62
Definição das Classes Array2D<T> e Array2D<T>::Row (2)
public: class Row {
Array2D& array2D; unsigned int const row;
public: Row(Array2D& _array2D, unsigned int _row) :
array2D (array2D), row(row) {} T& operator [] (unsigned int column) const { return array2D.Select (row, column); }
};
Array2D (unsigned int, unsigned int); T& Select (unsigned int, unsigned int); Row operator [] (unsigned int);};
63
Funções Membro da Classe Classes Array2D<T> (1)
// pgm04_21.cpp
template <class T>Array2D<T>::Array2D (unsigned int m, unsigned int n) : numberOfRows (m), numberOfColumns (n), array (m * n) {}
64
Funções Membro da Classe Classes Array2D<T> (2)
// pgm04_21.cpp (Continuação)
template <class T>T& Array2D<T>::Select (unsigned int i, unsigned int j){ if (i >= numberOfRows)
throw out_of_range ("invalid row"); if (j >= numberOfColumns)
throw out_of_range ("invalid column"); return array [i * numberOfColumns + j];}
template <class T>Array2D<T>::Row Array2D<T>::operator [] (unsigned int
row) { return Row (*this, row); }
65
Índices Multi dimensionais em C++
A função membro operator[] de Array2D<T> serve para indexar e constrói uma instância da classe Array2D<T>::RowComo exemplo pode-se declarar um array de inteiros e inicializar com o valor zero todos os seus membros da maneira que se segue.
Array2D<int> a (4, 5);for (int i = 0; i < 4; ++i) for (int j = 0; j < 5; ++j) a[i][j] = 0;
66
Multiplicação canônica de matrizes
Dadas as Matrizes A(m x n) e B(n x p) seu produto C =AB tem dimensões m x p
67
Definição da Classe Matrix<T>
// pgm04_22.cpp
template <class T>class Matrix : public Array2D<T>{public: Matrix (unsigned int, unsigned int); Matrix operator * (Matrix const&) const; Matrix operator + (Matrix const&) const;};
68
Classe Matrix<T> - Operador de Multiplicação
// pgm04_23.cpp
template <class T>Matrix<T> Matrix<T>::operator * (Matrix<T> const& arg) const { if(numberOfColumns != arg.numberOfRows)
throw invalid_argument ("incompatible matrices"); Matrix<T> result (numberOfRows, arg.numberOfColumns); for(unsigned int i = 0; i < numberOfRows; ++i) {
for(unsigned int j = 0; j < arg.numberOfColumns; ++j){ T sum = 0; for(unsigned int k = 0; k < numberOfColumns; ++k)
sum += (*this) [i][k] * arg [k][j]; result [i][j] = sum;
} } return result;}
Interfaces das estruturas já vistas
70
Pilhas
public interface Stackextends Container
{ Object getTop (); void push (Object object); Object pop ();}
71
Filas
public interface Queue extends Container
{ Object getHead (); void enqueue (Object object); Object dequeue ();}
72
Deques
public interface Deque extends Container{ Object getHead (); Object getTail (); void enqueueHead (Object object); void enqueueTail (Object object); Object dequeueHead (); Object dequeueTail ();}
