RE: Item e Key

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Um aluno escreveu (on Tuesday, 10 Apr 2001, at 21:50:41 -0300):
 > Professor,
 > 
 > tenho algumas dúvidas e embora tenha lido o livro do Sedgewick repetidas
 > vezes nao consegui chegar a uma conclusao, são elas: 
 > 
 > Item é um campo da minha estrutura (nó de lista ou de árvore) 

Acho que é melhor pensar assim: os objetos que seu programa cliente precisa
manipular são os itens.  Assim, do ponto de vista da aplicação, os itens são
"as personagens principais".

Por exemplo, um item poderia ser o conjunto de informacoes associadas a uma
aluno da USP (_tudo_ sobre ele), poderia ser o conjunto de informacoes sobre
um cliente de uma empresa, poderia ser o conjunto de informacoes sobre um
avião que está voando no espaço aéreo que o seu programa está monitorando,
poderia ser um pacote TCP/IP que você precisa rotear, etc.

Em geral, seu programa precisa manter estes objetos (= itens) em alguma
estrutura que permita fácil acesso a cada um deles individualmente.
Abstratamente falando, as nossas tabelas de simbolos são tais estruturas de
dados.  Por definicao, tais tabelas permitem insercao de novos objetos,
procura de algum objeto determinado, remocao de algum objeto dado, e algumas
outras operações.

Agora, nas implementacoes que temos visto de tais tabelas, temos umas
estruturas (no sentido da linguagem C) que têm um campo que serve para
armazenar o item.  Note que o programa cliente nao deve saber disto: para ele,
a unica coisa que ele sabe é que os itens estão armazenados de alguma forma
(poderia ser em um vetor, por exemplo).  Ademais, se tais estruturas são
organizadas pela tabela de simbolos em uma lista linear, ou em uma árvore, ou
em uma matriz, etc, também não é visível ao programa cliente.

 >                                                               que contem
 > várias Keys 

Supomos sempre que cada objeto (= item) tem o que chamamos de uma chave, que o
identifica de forma única.  Por exemplo, nos exemplos acima, poderia ser o
número USP do aluno, o CPF do cliente, a identificacao do avião (sua "chapa"),
o header do pacote, etc.

 >             (nao consigo distinguir Item de Key) ? 

Em nossas implementações, os itens contêm toda a informacao sobre o objeto;
cada item tem um key, que o identifica univocamente.

 > Porque a função STsearch (progr. 12.1 - livro do Sedgewick)  retorna um
 > Item e nao um link (vetor para o nó)? 

De fato, o prototipo da funcao é 

  Item STsearch(Key);

A explicacao é a seguinte: o programa cliente que usa esta funcao quer o
objeto associado a uma dada chave.  Por exemplo, seu programa quer conjunto de
informacoes associadas a um dado NUSP.  O programa cliente não quer saber como
os objetos estão sendo armazanados.

 >                                       Pois no meu modo de ver (que deve
 > estar errado) nao consiguiria alterar meus dados sendo passado somente o
 > Item para minha chamada. 

Entendi sua duvida: de fato, se queremos alterar as informacoes associadas a
uma chave, precisamos ter acesso ao objeto, e nao apenas saber quais sao estas
informacoes.  Na grande maioria dos casos, temos declarado o tipo Item como
sendo um _ponteiro_ para uma estrutura que contem as informacoes, de forma
que, apos uma chama de STsearch(), temos acesso ao objeto que queremos
alterar.

Até mais, Yoshi