Listas Ordenadas e Listas Classificadas. 2 Sumário Fundamentos Listas Ordenadas Listas Classificadas

Listas Ordenadas e Listas Classificadas

2

Sumário

FundamentosListas OrdenadasListas Classificadas

3

Conceito de Listas

Listas são os containers mais simples que existem e também os mais versáteis.Consideradas como tipos abstratos de dados listas são séries de itens e permitem inclusão e exclusão de elementos e a visitação a itens na ordem em que aparecem.

4

Tipos especiais de Listas

Podem ser definidos dois tipos especiais de listas: Listas ordenadas – são aquelas nas quais a

ordem ou posição dos itens é relevante, independentemente de seu conteúdo e, portanto, pode ser modificada.

Listas classificadas – são listas ordenadas nas quais a ordem é inerente ao conteúdo dos itens e não pode ser modificada.

As abstrações destes tipos de listas são encontradas nas interfaces OrderedList e SortedList.

5

Interfaces OrderedList e SortedList

6

Fundamentos

Considerar-se-ão como fundamentos os padrões de Projeto e as Hierarquias de classe, ou Framework, de Bruno Preiis.Em particular as interfaces Comparable Container SearchableContainer

Implementação Java

8

Interface Comparable

public interface Comparable{ boolean isLT (Comparable object); boolean isLE (Comparable object); boolean isGT (Comparable object); boolean isGE (Comparable object); boolean isEQ (Comparable object); boolean isNE (Comparable object); int compare (Comparable object);}

9

Interface Container

public interface Container extends Comparable{ int getCount(); boolean isEmpty(); boolean isFull(); void purge(); void accept(Visitor visitor); Enumeration getEnumeration();}

10

Classe Abstrata AbstractContainer

public abstract class AbstractContainer extends AbstractObject implements Container{ protected int count; public int getCount()

{ return count; } public boolean isEmpty()

{ return getCount() == 0; } public boolean isFull()

{ return false; } // ...}

11

Interface SearchableContainer

public interface SearchableContainer extends Container{ boolean isMember(Comparable object); void insert(Comparable object); void withdraw(Comparable obj); Comparable find(Comparable object);}

Listas Ordenadas

13

Listas Ordenadas - Sumário

IntroduçãoImplementação sobre “Arrays”Implementação sobre Listas Encadeadas

14

Introdução

As listas Ordenadas serão apresentadas por uma interface e duas classes correspondendo a dois tipos de implementação, sobre “arrays” e sobre listas encadeadas: Interface OrderedList Classe OrderedListAsArray Classe OrderedListAsLinkedList

15

Interface OrderedList

public interface OrderedList

extends SearchableContainer

{

Comparable get (int i);

Cursor findPosition (Comparable object);

}

16

Interface OrderedList

Esta interface estende SearchableContainer e apresenta os métodos get e findPosition. Por sua vez SearchableContainer dispõe dos métodos: insert withdraw find isMember

17

Método findPosition de OrderedList

O método findPosition retorna um Cursor, cuja interface será exibida a seguir e que dispõe dos métodos: getDatum insertAfter insertBefore withdraw

18

Interface Cursor

public interface Cursor{ Comparable getDatum(); void insertAfter(Comparable object); void insertBefore(Comparable object); void withdraw();}

19

Interface SortedList

public interface SortedList

extends SearchableContainer

{

Comparable get(int i);

Cursor findPosition(Comparable object);

}

Implementação sobre “Arrays”

21

Classe OrderedListAsArray

public class OrderedListAsArray

extends AbstractSearchableContainer

implements OrderedList

{

protected Comparable[] array;

// ...

}

22

Construtor e método de inserção de item no final da lista

public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList{ protected Comparable[] array; public OrderedListAsArray(int size)

{ array = new Comparable [size]; } public void insert(Comparable object) {

if(count == array.length) throw new ContainerFullException ();

array[count] = object; ++count;

} // ...}

23

Métodos isMember e findpublic class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList{ protected Comparable[] array; public boolean isMember(Comparable object) {

for(int i = 0; i < count; ++i) if(array[i] == object)

return true; return false;

} public Comparable find(Comparable arg) {

for(int i = 0; i < count; ++i) if(array[i].isEQ(arg))

return array[i]; return null;

} // ...}

24

Método withdraw (1)

public class OrderedListAsArray extends AbstractSearchableContainer

implements OrderedList{ protected Comparable[] array; public void withdraw(Comparable object)

{ if(count == 0)

throw new ContainerEmptyException (); int i = 0; while(i < count && array[i] != object)

++i; if(i == count)

throw new IllegalArgumentException("objetonão encontrado");

25


for( ; i < count - 1; ++i) array[i] = array[i + 1];

array[i] = null; --count;

} // ...}

26

Posição de um item em uma lista por meio da Classe Interior OrderedListAsArray.MyCursor (1)

public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList{ protected Comparable[] array; protected class MyCursor

implements Cursor {

int offset; MyCursor (int offset)

{ this.offset = offset; }

27

Posição de um item em uma lista por meio da Classe Interior OrderedListAsArray.MyCursor (2)

public Comparable getDatum() {

if(offset < 0 || offset >= count)throw new IndexOutOfBoundsException();

return array [offset]; } // ...

} // ...}

28

Busca de um item e acesso por posiçãoMétodos findPosition e get de OrderedListAsArray

public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList{ protected Comparable[] array; public Cursor findPosition(Comparable object) {

int i = 0; while(i < count && array[i].isNE(object))

++i; return new MyCursor(i);

} public Comparable get(int offset) {

if(offset < 0 || offset >= count) throw new IndexOutOfBoundsException();

return array[offset]; } // ...}

29

Inserção de itens em posições arbitrárias Métodos insertBefore e insertAfter de OrderedListAsArray

30

Método insertAfter (1)


implements Cursor {

int offset;

31

Método insertAfter (2)

public void insertAfter (Comparable object) {


if(count == array.length) throw new ContainerFullException();

int insertPosition = offset + 1; for(int i = count; i > insertPosition; --i)

array[i] = array[i - 1]; array[insertPosition] = object; ++count;

} // ...

} // ...}

32

Método insertBefore (1)


implements Cursor {

int offset;

33

Método insertBefore (2)

public void insertBefore(Comparable object) {



int insertPosition = offset; for(int i = count; i > insertPosition; --i)

array[i] = array[i - 1]; array[insertPosition] = object; ++count;

} // ...

} // ...}

34

Exclusão de itens em posições arbitrárias Método withdraw de OrderedListAsArray

35



implements Cursor {

int offset;

36

Método withdraw (2) public void withdraw() {


if(count == 0) throw new ContainerEmptyException();

int i = offset; while(i < count - 1) {

array[i] = array[i + 1]; ++i;

} array[i] = null; --count; } // ...

} // ...}

Implementação sobre Listas Encadadeadas

38

Métodos da classe LinkedList

getDatumgetNextConstrutor e purgegetHeadgetTailisEmptygetFirstgetLastprependappendassignextractinsertAfterinsertBefore

39

Classe OrderedListAsLinkedList

public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList{ protected LinkedList linkedList; // ...}

40

Construtor e métodos de inserção de objeto (1)

public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList{ protected LinkedList linkedList; public OrderedListAsLinkedList()

{ linkedList = new LinkedList(); } public void insert(Comparable object) {

linkedList.append(object); ++count;

}

41

Construtor e métodos de inserção de objeto (2)

public Comparable get(int offset) {


LinkedList.Element ptr = linkedList.getHead();

for(int i = 0; i < offset && ptr != null; ++i) ptr = ptr.getNext();

return (Comparable) ptr.getDatum(); } // ...}

42

Métodos isMember e find (1)

public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList{ protected LinkedList linkedList; public boolean isMember (Comparable object) {

for(LinkedList.Element ptr = linkedList.getHead();ptr != null; ptr = ptr.getNext())

{ if((Comparable) ptr.getDatum() == object)

return true; } return false;

}

43

Métodos isMember e find (2)

public Comparable find (Comparable arg) {

for(LinkedList.Element ptr = linkedList.getHead();ptr != null; ptr = ptr.getNext())

{ Comparable object = (Comparable) ptr.getDatum(); if(object.isEQ(arg))

return object; } return null;

} // ...}

44

Método withdraw

public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList{ protected LinkedList linkedList; public void withdraw (Comparable object) {


linkedList.extract(object); --count;

} // ...}

45

Classe Interior OrderedListAsLinkedList.MyCursor

public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList{ protected LinkedList linkedList; protected class MyCursor

implements Cursor {

LinkedList.Element element; MyCursor(LinkedList.Element element)

{ this.element = element; } public Comparable getDatum()

{ return (Comparable) element.getDatum(); } // ...

} // ...}

46

Busca de um item e acesso por posição Método findPositionpublic class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList{ protected LinkedList linkedList; public Cursor findPosition (Comparable arg) {

LinkedList.Element ptr;for(ptr = linkedList.getHead(); ptr != null; ptr = ptr.getNext())

{ Comparable object = (Comparable) ptr.getDatum(); if(object.isEQ(arg))

break; } return new MyCursor (ptr);

} // ...}

47

Método insertAfter


implements Cursor {

LinkedList.Element element; public void insertAfter (Comparable object) {

element.insertAfter(object); ++count;

} // ...

} // ...}

48

Exclusão de item correnteMétodo withdraw


implements Cursor {

LinkedList.Element element; public void withdraw() {

linkedList.extract(element.getDatum()); --count;

} // ...

} // ...}

Listas Classificadas

50

Listas Classificadas - Sumário

IntroduçãoImplementação sobre “Arrays”Implementação sobre Listas Encadeadas

51

Introdução

As listas Classificadas serão apresentadas por uma interface e duas classes correspondendo a dois tipos de implementação, sobre “arrays” e sobre listas encadeadas: Interface SortedList Classe SortedListAsArray Classe SortedListAsLinkedList


53

Classe SortedListAsArray

public class SortedListAsArray

extends OrderedListAsArray

implements SortedList

{

// ...

}

54

Inclusão de itens em uma lista classificada

55

Método insertpublic class SortedListAsArray extends OrderedListAsArray implements SortedList{ public void insert (Comparable object) {


int i = count; while(i > 0 && array[i - 1].isGT(object)) {

array[i] = array[i - 1]; --i;

} array[i] = object; ++count;

} // ...}

56

Busca binária

Quando existe um “array” de itens classificados uma maneira eficiente de localizar um dado item é a chamada busca binária.Este algoritmo utiliza o conceito de intervalo de busca para determinar a posição de um item no “array” classificado.O intervalo inicial vai de 0 até count – 1. O intervalo é estreitado comparando o item de busca com o item no meio do intervalo. Se houver coincidência a busca está encerrada com

sucesso. Se o item de busca for menor a “metade” superior do

intervalo de busca é descartada e a busca prossegue recursivamente.

Se o item de busca for maior a “metade” inferior do intervalo de busca é descartada e a busca prossegue recursivamente.

57

Busca Binária - Método findOffset (1)

public class SortedListAsArray extends OrderedListAsArray implements SortedList{ protected int findOffset (Comparable object) {

int left = 0; int right = count - 1; while(left <= right) {

int middle = (left + right) / 2; if(object.isGT( array[middle] ))

left = middle + 1;

58

Busca Binária - Método findOffset (2)

else if(object.isLT( array[middle] )) right = middle - 1;

else return middle;

}return -1;

} // ...}

59

Busca de itens em Listas Classificadas

O método find retorna uma referência a um objeto buscado na listaO método findPosition retorna um Cursor

60

Métodos find e findPosition (1)

public class SortedListAsArray extends OrderedListAsArray implements SortedList{ public Comparable find (Comparable object) {

int offset = findOffset(object); if(offset >= 0)

return array[offset]; else

return null; }

61

Métodos find e findPosition (2)

public Cursor findPosition (Comparable object) {

return new MyCursor(findOffset(object)) {

public void insertAfter(Comparable object){ throw new InvalidOperationException(); }

public void insertBefore(Comparable object){ throw new InvalidOperationException(); }

}; } // ...}

62

Método withdrawpublic class SortedListAsArray extends OrderedListAsArray implements SortedList{ public void withdraw (Comparable object) {


int offset = findOffset(object); if(offset < 0)

throw new IllegalArgumentException ( "objeto não encontrado"); int i; for(i = offset; i < count - 1; ++i)

array[i] = array[i + 1]; array[i] = null; --count;

} // ...}


64

Classe SortedListAsLinkedList

public class SortedListAsLinkedList extends OrderedListAsLinkedList implements SortedList{ // ...}

65

Método insert (1)

public class SortedListAsLinkedList extends OrderedListAsLinkedList implements SortedList{ public void insert (Comparable arg) {

LinkedList.Element ptr; LinkedList.Element prevPtr = null; for(ptr = linkedList.getHead(); ptr != null;

ptr = ptr.getNext()) {

Comparable object = (Comparable) ptr.getDatum(); if(object.isGE (arg))

break; prevPtr = ptr;

}

66

Método insert (2)

if(prevPtr == null) linkedList.prepend(arg);

else prevPtr.insertAfter(arg);

++count; } // ...}

67

Outras operações

Nenhuma outra operação além das herdadas da classe OrderedListAsLinkedList pode ser implementada. insert get isMember find withdraw findPosition insertAfter – não é o caso insertBefore – não é o caso

Implementação C++

69

Hierarquia de Classe de Listas Ordenadas e Listas Classificadas

70

Searchable Container

Insert • Inclusão de objetos no Container;

Withdraw • Exclusão de objetos no Container;

Find • Localização de objetos no Container;

IsMember • Teste se dada instância de objeto está no Container.

Listas Ordenadas

72

Ordered List

FindPosition • Encontra dada instância de objeto na Lista Ordenada;

operator [] • Dá acesso ao objeto em determinada posição em uma Lista Ordenada;

Withdraw(Position&) • Remove o objeto em determinada posição em uma Lista Ordenada;

InsertAfter • Insere um objeto em uma Lista Ordenada depois do objeto que está em

dada posição;

InsertBefore • Insere um objeto em uma Lista Ordenada antes do objeto que está em

dada posição.

73

Definições das Classes List e OrderedList

// pgm07_01.cppclass Position : public Iterator{};class List : public virtual SearchableContainer{

public: virtual Object& operator [] (unsigned int) const = 0; virtual Object& operator [] (Position const&) const = 0; virtual Position& FindPosition (Object const&) const = 0; virtual void Withdraw (Position const&) = 0;

};class OrderedList : public virtual List{

public: virtual void InsertAfter (Position const&, Object&) = 0; virtual void InsertBefore (Position const&, Object&) = 0;

};

74

Classe OrderedList

A classe OrderedList extende a classe List adicionando mais duas funções membro: InsertAfter InsertBefore

75

Classe Position

A classe Position cria uma abstração da posição de um item em uma lista

Sendo esta abstração quase idêntica a um iterator, a classe Position é derivada da classe abstrata Iterator


77

Definição da Classe ListAsArray

// pgm07_02.cpp

class ListAsArray : public virtual OrderedList

{

protected:

Array<Object*> array;

class Pos;

public:

ListAsArray (unsigned int);

// ...

friend class Pos;

};

78

Definição do Construtor, da Função Membro Insert e do Operador Subscripting, da Classe ListAsArray

// pgm07_03.cpp

ListAsArray::ListAsArray (unsigned int size) :

array (size) {}

void ListAsArray::Insert (Object& object) {

if(count == array.Length ())

throw domain_error (“lista cheia");

array [count] = &object;

++count;

}

Object& ListAsArray::operator [] (unsigned int offset) const {

if(offset >= count)

throw out_of_range (“deslocamento inválido");

return *array [offset];

}

79

Definição das Funções Membro IsMember e Find da Classe ListAsArray

// pgm07_04.cppbool ListAsArray::IsMember (Object const& object) const{

for(unsigned int i = 0; i < count; ++i)if(array [i] == &object)

return true;return false;

}Object& ListAsArray::Find (Object const& object) const{

for(unsigned int i = 0; i < count; ++i)if(*array [i] == object)

return *array [i];return NullObject::Instance ();

}

80

Diferença entre as funções isMember e Find (1)

IsMember busca uma específica instância de objetoFind busca um objeto que se encaixe na descriçãoExemplo: Object& object1 = *new Int (57); Object& object2 = *new Int (57); ListAsArray list (1); list.Insert (object1);

São criadas duas instâncias de objeto da classe Int ambas com o valor 57Apenas object1 é inserido na lista ordenada list

81

Diferença entre as funções isMember e Find (2)

O chamado de função list.IsMember (object1)

retorna trueO chamado de função list.IsMember (object2)

retorna false. Uma busca do tipo: Object& object3 = list.Find (object2)

retorna resultado satisfatório pois object3 refere-se a object1

82

Definição da Função Membro Withdraw da Classe ListAsArray

// pgm07_05.cpp

void ListAsArray::Withdraw (Object& object)

{

if(count == 0)

throw domain_error ("lista vazia");

unsigned int i = 0;

while (i < count && array [i] != &object)

++i;

if(i == count)

throw invalid_argument("objeto não encontrado");

for( ; i < count - 1U; ++i) array [i] = array [i + 1];

--count;

}

83

Exclusão de elementos da Lista Ordenada (1)

Para remover object1 da lista ordenada, pode-se escrever list.Withdraw (object1);A chamada list.Withdraw (object2) falhará pois object2 não está na listaCaso se tenha perdido a pista de object1 pode-se escrever: list.Withdraw (list.Find (object2));

Isto primeiramente encontra o objeto na lista ordenada (object1) que corresponde a object2 e então exclui o objeto

84

Definição da Classe ListAsArray::Pos

// pgm07_06.cpp

class ListAsArray::Pos : public Position

{

protected:

ListAsArray const& list;

unsigned int offset;

public:

// ...

friend class ListAsArray;

friend class SortedListAsArray;

};

85

Definição da Função Membro FindPosition e do Operador Subscripting da Classe ListAsArray

// pgm07_07.cppPosition& ListAsArray::FindPosition (Object const& object)

const{

unsigned int i = 0;while(i < count && *array [i] != object)

++i;return *new Pos (*this, i);

}

Object& ListAsArray::operator [] (Position const& arg) const{

Pos const& position = dynamic_cast<Pos const&> (arg);if(&position.list != this || position.offset >= count)

throw invalid_argument("posição inválida");return *array [position.offset];

}

86

Inserção de itens em posições arbitrárias Métodos insertBefore e insertAfter de OrderedListAsArray

87

Definição da Função Membro InsertAfter da Classe ListAsArray

// pgm07_08.cppvoid ListAsArray::InsertAfter( Position const& arg,

Object& object){

Pos const& position = dynamic_cast<Pos const&> (arg);

if(count == array.Length ())throw domain_error("lista cheia");

if(&position.list != this || position.offset >= count) throw invalid_argument("posição inválida");

unsigned int const insertPosition = position.offset + 1;

for(unsigned int i = count; i > insertPosition; --i) array[i] = array [i - 1U];array [insertPosition] = &object;++count;

}

88

Exclusão de itens em posições arbitrárias Método withdraw de OrderedListAsArray

89

Definição da Função Membro Withdraw da Classe ListAsArray

// pgm07_09.cppvoid ListAsArray::Withdraw (Position const& arg){


if(count == 0)throw domain_error("list is empty");

if(&position.list != this || position.offset >= count)

throw invalid_argument("posição inválida");for(unsigned int i = position.offset; i < count-1U; ++i)

array[i] = array[i + 1]; --count;}


91

Definição da Classe LinkedList

// pgm07_10.cpp

class ListAsLinkedList : public virtual OrderedList

{

protected:

LinkedList<Object*> linkedList;

class Pos;

public:

ListAsLinkedList ();

// ...

friend class Pos;

};

92

Definição do Operador Subscripting, da Função Membro Insert e do Construtor da Classe ListAsLinkedList (1)

// pgm07_11.cpp

ListAsLinkedList::ListAsLinkedList () :

linkedList ()

{}

void ListAsLinkedList::Insert (Object& object)

{

linkedList.Append (&object);

++count;

}

93

Definição do Operador Subscripting, da Função Membro Insert e do Construtor da Classe ListAsLinkedList (2)

Object& ListAsLinkedList::operator [] (unsigned int offset) const

{if(offset >= count)

throw out_of_range(“deslocamento inválido");unsigned int i = 0;ListElement<Object*> const* ptr = linkedList.Head ();while(i < offset && ptr != 0){

ptr = ptr->Next ();++i;

}if(ptr == 0)

throw logic_error(“não deveria ter ocorrido");return *ptr->Datum ();

}

94

Definição das Funções Membros IsMember e Find da Classe ListAsLinkedList

// pgm07_12.cppbool ListAsLinkedList::IsMember (Object const& object) const{

ListElement<Object*> const* ptr;for(ptr = linkedList.Head (); ptr != 0; ptr = ptr->Next())

if(ptr->Datum () == &object)return true;

return false;}Object& ListAsLinkedList::Find(Object const& object) const

{ListElement<Object*> const* ptr;for(ptr = linkedList.Head (); ptr != 0; ptr = ptr->Next())

if(*ptr->Datum() == object)return *ptr->Datum ();

return NullObject::Instance();}

95

Definição da Função Membro Withdraw da Classe ListAsLinkedList

// pgm07_13.cpp

void ListAsLinkedList::Withdraw (Object& object)

{

if(count == 0)

throw domain_error("lista vazia"); linkedList.Extract(&object);

--count;

}

96

Definição da Classe ListAsLinkedList::Pos

// pgm07_14.cpp

class ListAsLinkedList::Pos : public Position

{

ListAsLinkedList const& list;

ListElement<Object*> const* element;

public:

// ...

friend class ListAsLinkedList;

};

97

Definição do Operador Subscripting e da Função Membro FindPosition da Classe ListAsLinkedList

// pgm07_15.cppPosition& ListAsLinkedList::FindPosition ( Object const&

object) const{

ListElement<Object*> const* ptr = linkedList.Head ();while(ptr != 0 && *ptr->Datum () != object)

ptr = ptr->Next ();return *new Pos (*this, ptr);

}Object& ListAsLinkedList::operator [] ( Position const&

arg) const{

Pos const& position = dynamic_cast<Pos const&> (arg);if(&position.list != this || position.element == 0)

throw invalid_argument(“posição invalida");return *position.element->Datum ();

}

98

Definição da Função Membro InsertAfter da Classe ListAsLinkedList

// pgm07_16.cppvoid ListAsLinkedList::InsertAfter ( Position const& arg,

Object& object){


if(&position.list != this || position.element == 0)throw invalid_argument("posição invalida");

linkedList.InsertAfter(position.element, &object); ++count;

}

99

Definição da Função Membro Withdraw da Classe ListAsLinkedList

// pgm07_17.cppvoid ListAsLinkedList::Withdraw (Position const& arg){


if(count == 0)throw domain_error("lista vazia");

if(&position.list != this || position.element == 0)throw invalid_argument("posição invalida");

linkedList.Extract(position.element->Datum ());--count;

}

Listas Classificadas

101

Definição da Classe SortedList

// pgm07_20.cpp

class SortedList : public virtual List

{

};


103

Definição da Classe SortedListAsArray

// pgm07_21.cpp

class SortedListAsArray :

public virtual SortedList, public virtual ListAsArray

{

unsigned int FindOffset (Object const&) const;

public:

SortedListAsArray (unsigned int);

// ...

};

104

Definição da Função Membro Insert da Classe SortedListAsArray

// pgm07_22.cppvoid SortedListAsArray::Insert (Object& object){

if(count == array.Length ())throw domain_error("lista cheia");

unsigned int i = count;while(i > 0 && *array [i - 1U] > object){

array[i] = array[i - 1U]; --i;}array[i] = &object;++count;

}

105

Definição da Função FindOffset da Classe SortedListAsArray// pgm07_23.cppunsigned int SortedListAsArray::FindOffset( Object const&

object) const{

int left = 0;int right = count - 1;while(left <= right){

int const middle = (left + right) / 2;if(object > *array [middle])

left = middle + 1;else

if(object < *array [middle])right = middle - 1;

elsereturn middle;

}return count;

}

106

Definição das Funções Membro Find e FindPosition da Classe SortedListAsArray

// pgm07_24.cppObject& SortedListAsArray::Find (Object const& object) const{

unsigned int const offset = FindOffset (object);if(offset < count)

return *array [offset];else

return NullObject::Instance ();}

Position& SortedListAsArray::FindPosition ( Object const& object) const

{Pos& result = *new Pos (*this);result.offset = FindOffset (object);return result;

}

107

Definição da Função Membro Withdraw da Classe SortedListAsArray

//pgm07_25.cppvoid SortedListAsArray::Withdraw (Object& object){

if(count == 0)throw domain_error("lista vazia");

unsigned int const offset = FindOffset (object);if(offset == count)

throw invalid_argument("objeto não encontrado");for(unsigned int i = offset; i < count - 1U; ++i)

array[i] = array[i + 1];--count;

}


109

Definição da Classe SortedListAsLinkedList

// pgm07_26.cpp

class SortedListAsLinkedList :

public virtual SortedList, public virtual ListAsLinkedList

{

public:

SortedListAsLinkedList ();

// ...

};

110

Definição da Função Membro Insert da Classe SortedListAsLinkedList

// pgm07_27.cppvoid SortedListAsLinkedList::Insert (Object& object){

ListElement<Object*> const* prevPtr = 0;ListElement<Object*> const* ptr = linkedList.Head ();while(ptr != 0 && *ptr->Datum () < object){

prevPtr = ptr;ptr = ptr->Next ();

}if(prevPtr == 0)

linkedList.Prepend (&object);else

linkedList.InsertAfter (prevPtr, &object);++count;

}

Documents

Listas Ordenadas e Listas Classificadas. 2 Sumário Fundamentos Listas Ordenadas Listas Classificadas