PR03 - Algumas dúvidas

PR03 - Algumas dúvidas

por Nathalia Orlandi Borin -
Número de respostas: 10

Olá!

Meu grupo está com algumas dúvidas em relação à implementação da symbol table:

 

1) A função stable_insert não deveria receber um valor? Já que o equivalente nas STs do Java seria a função put(Key key, Value value), que associa a Key key ao Value value, porém no arquivo stable.h temos apenas:

InsertionResult stable_insert(SymbolTable table, const char *key);

 

2) Sobre os tipos esperados para Key e Value, no enunciado temos:

"A chaves da ST são alguns tipos de dados e o valores strings."

Porém nas funções declaradas em stable.h, a chave é sempre uma string (const char *key) e o valor (EntryData?) que pode assumir outros tipos de dado.

 

3) Sobre a EntryData: não deveria ser uma struct, em vez de uma union? Nesse caso o inteiro i seria a chave (depois de passar pela função de hash), a string str seria o valor associado a essa chave, e o ponteiro p apontaria para a próxima EntryData da tabela, associada a mesma chave (no caso de colisão).


typedef union {
  int i;
  char *str;
  void *p;
} EntryData;

 

4) Apenas para confirmar se entendemos o que a função stable_visit faz:

> A função percorre cada entry de uma symbol table e retorna 0 quando chega ao final dela

> Se não retorna 0, existe alguma convenção de que número retornar? (como o número de elementos visitados, por exemplo)?

 

5) Existe alguma especificação sobre a função de hash que deve ser usada? (modular ou multiplicativo)

 

Acho que por enquanto é isso, obrigada!

Em resposta à Nathalia Orlandi Borin

Re: PR03 - Algumas dúvidas

por Leonardo Lana Violin Oliveira -

Olá Nathalia,

 

1) A função stable_insert não deveria receber um valor? Já que o equivalente nas STs do Java seria a função put(Key key, Value value), que associa a Key key ao Value value, porém no arquivo stable.h temos apenas:

Vocês devem inserir o valor na tabela de símbolos através do InsertionResult retornado pelo função, mais especificamente, através do ponteiro do tipo EntryData que está presente na estrutura do InsertionResult.

2) Sobre os tipos esperados para Key e Value, no enunciado temos:

Acredito que isso tenha sido um erro de digitação. As chaves sempre serão strings e o valor sempre será um EntryData.

3) Sobre a EntryData: não deveria ser uma struct, em vez de uma union? Nesse caso o inteiro i seria a chave (depois de passar pela função de hash), a string str seria o valor associado a essa chave, e o ponteiro p apontaria para a próxima EntryData da tabela, associada a mesma chave (no caso de colisão).

Não, a chave sempre será uma string. Enquanto o value será um EntryData,  que signifca que ele assumirá um dos três tipos listados na union: inteiro, ou string ou void *, dependendo do que for atribuído a ele.

A struct do stable_s vocês terão que criar um header diferente.

4) Apenas para confirmar se entendemos o que a função stable_visit faz:

> A função percorre cada entry de uma symbol table e retorna 0 quando chega ao final dela

> Se não retorna 0, existe alguma convenção de que número retornar? (como o número de elementos visitados, por exemplo)?

A função stable_visit, recebe um ponteiro de função (a função visit), essa função será chamada em cada elemento da tabela. A função stable_visit deve retornar 0 somente quando a iteração for parada pelo função visit, se a stable_visit iterou em todos os elementos deve retornar não 0.

5) Existe alguma especificação sobre a função de hash que deve ser usada? (modular ou multiplicativo)

Não há especificação sobre isso.

Em resposta à Leonardo Lana Violin Oliveira

Re: PR03 - Algumas dúvidas

por Nathalia Orlandi Borin -

A função stable_visit, recebe um ponteiro de função (a função visit), essa função será chamada em cada elemento da tabela. A função stable_visit deve retornar 0 somente quando a iteração for parada pelo função visit, se a stable_visit iterou em todos os elementos deve retornar não 0.

Hmm ainda estou um pouco confusa...

A função visit é chamada em cada elemento da tabela (ou seja, cada stable_s) para iterar sobre esses elementos e retorna um int.

Minhas perguntas são:

1) A função visit recebe como argumentos uma chave e um valor... mas por que? Se ela vai apenas iterar por todos os elementos da lista, não entendo como esses parâmetros seriam usados.

2) Devemos usar a stable_visit para imprimir os pares de chave e valor no nosso programa freq. Se no fim ela só retorna um int, deveríamos estar imprimindo essas coisas dentro da função mesmo? (acho que nesse caso o nome stable_print seria mais adequado, heh)

3) O que exatamente seria "quando a iteração for parada pela função visit"? Esse int tem apenas a finalidade de indicar se houve algum erro na função?

 

Obrigada novamente!

Em resposta à Nathalia Orlandi Borin

Re: PR03 - Algumas dúvidas

por Leonardo Lana Violin Oliveira -

1) Não é a função visit que vai iterar em todas as chaves e valores, quem faz isso é a stable_visit. A função visit é uma função que você vai passar como argumento para a stable_visit, e a stable_visit vai aplicar a visit em cada uma das entradas da tabela

 

2) Não, quem vai imprimir de fato a entrada (par de chave e valor) é a função visit,  e não a stable_visit.

 

3) Exatamente, o int indica se a função terminou com sucesso ou não.

Em resposta à Leonardo Lana Violin Oliveira

Re: PR03 - Algumas dúvidas

por Bruna Thalenberg -

Estou com dúvidas parecidas com as da Nathalia:

1) A função visit recebe como argumentos uma chave e um valor... mas por que? Se ela vai apenas iterar por todos os elementos da lista, não entendo como esses parâmetros seriam usados.

R: Não é a função visit que vai iterar em todas as chaves e valores, quem faz isso é a stable_visit. A função visit é uma função que você vai passar como argumento para a stable_visit, e a stable_visit vai aplicar a visit em cada uma das entradas da tabela

A assinatura de stable_visit é int stable_visit(SymbolTable table, int (*visit)(const char *key, EntryData *data)), então, se entendi direito, a chamada seria algo como
stable_visit(table, visit(key, data)), não? A questão é, se todos vão ser visitados (já que a stable_visit vai iterar em todas as chaves e valores), por que eu preciso passar key e data como argumentos? Ou eu posso chamar stable_visit(table, visit())?

Em resposta à Bruna Thalenberg

Re: PR03 - Algumas dúvidas

por Leonardo Lana Violin Oliveira -

A chamada da stable_visit é stable(table, visit), sem o parêntesis, assim você passa o ponteiro de função e não o valor retornado pela função. Passando dessa forma a stable_visit pode chamar a visit dentro dela.

Em resposta à Leonardo Lana Violin Oliveira

Re: PR03 - Algumas dúvidas

por Gabriel Araujo -

Sobre o header stable_s: o enunciado não diz que nós não podemos mudar stable.h?

Outra coisa: a função stable_create() não deveria retornar um ponteiro? (já que o struct *SymbolTable é ponteiro).

Em resposta à Gabriel Araujo

Re: PR03 - Algumas dúvidas

por José Coelho de Pina -

Oi Gabriel,

Desculpe pela demora...

Sobre o header stable_s: o enunciado não diz que nós não podemos mudar stable.h?

Legal que você perguntou!

Não escrevemos mais isso no enunciado.
Uma API (.h em C) não pode ser mudada, a não ser que haja um acordo.

a função stable_create() não deveria retornar um ponteiro? (já que o struct *SymbolTable é ponteiro).

O protótipo está ok.

Aqui tem o exemplo de implementação de uma pilha (pilha.h, pilha.c e cliente) que usa o mesmo conceito.

Se você quiser brincar com o código, o fonte está aqui.

Em resposta à Nathalia Orlandi Borin

Re: PR03 - Algumas dúvidas

por José Coelho de Pina -

Oi Nathalia,

Muito legal as suas perguntas!

Aproveitando a deixa...

Sobre a EntryData: não deveria ser uma struct, em vez de uma union?

Os interessados podem ler sobre as diferenças de struct e union em https://www.geeksforgeeks.org/difference-structure-union-c/.

Veja o que a seção 6.8 do Kernighan and Ritchie tem a dizer a respeito.

 

Em resposta à Nathalia Orlandi Borin

Re: PR03 - Algumas dúvidas

por José Coelho de Pina -

Ois,

Aqui vai um esclarecimento sobre a função stable_visit().

Digamos que um item da tabela de símbolos é um par chave-valor, no caso. key-data, onde:

  • key é um string (char *) que representa uma chave, e
  • data é um ponteiro para uma union EntryData que representa o valor da chave.

A função stable_visit() deve percorrer toda a tabela de símbolos table e examinar cada um de seus itens.

Por examinar um item key-data queremos dize fazer uma chamada visit(key, data) que examina o item como bem entender. Por exemplo, a função visit() pode ser um mero printf() de key e data. E evidente que a maneira que essa impressão é feita depende do tipo do valor que data representa.

Considerem a declaração

#define EXIT_SUCCESS 1
#define EXIT_FAILURE 0

As funções stable_visit() e visit() retornam EXIT_FAILURE se ocorreu algum problema e EXIT_SUCCESS em caso contrário. Isso é meio padrão.

té +,
lana, victor e coelho