Como armazenar dados de satélite em estruturas de dados C

5

Eu tenho lido através do Introdução aos Algoritmos do 3º Ed , e estou tendo dificuldades em implementar algumas práticas situações. Não é a teoria, ou a implementação das partes internas das estruturas de dados, mas sim como projetar uma boa interface que torne as estruturas de dados úteis para armazenar dados reais (em oposição a apenas as chaves).

Especificamente, me disseram que C tem uma filosofia do tipo "confiar no programador". Eu só não sei quanta confiança é muita confiança:

Como exemplo, muitas estruturas de dados podem ser implementadas como estruturas vinculadas com nós similares tendo uma chave, dados de satélite e ponteiros para outros nós no ds, ex:

typedef struct {
    int key;
    void *data;
    node_t *prev;
    node_t *next;
} node_t;
  1. Até que ponto devo estar encapsulando minhas implementações? Para a maioria das estruturas, você tem os dois: (a) um tipo de estrutura de dados e (b) um tipo que pode ser inserido / excluído da estrutura de dados. Ambos devem estar escondidos? Claramente, se eu expor um pouco de node_t com a intenção de alguém só altera key e *data .. existe a possibilidade de prev ou next ser alterada, destruindo assim a estrutura de dados. Um risco semelhante existe se eu expor o tipo de estrutura de dados e alguém mexer com a raiz ...

  2. Como as chaves devem ser armazenadas / acessadas / comparadas? Presumivelmente, as chaves dependem dos dados do satélite, mas se você seguir a abordagem acima, você dissociou a chave dos dados em si. O que aconteceria se um usuário atualizasse os dados, mas esquecesse de atualizar a chave (ou pior, eles atualizassem a chave, mas não a removessem / reinserisse no ds)? Para algo como uma árvore binária que usa apenas comparações, eu poderia projetar a interface para aceitar comparadores que aceitam ponteiros para os dados de satélite? Isso torna a estrutura mais generalizada, mas toda a defreferência tem que ter impacto na velocidade. Como alternativa, (e seria necessário para estruturas como hashes que precisam de uma chave concreta), eu poderia aceitar um ponteiro para uma função int toKey(void *data) .

Não estou claro como um bom software deve ser projetado para uso no mundo real.

    
por Joney 12.08.2014 / 19:20
fonte

1 resposta

4

Forneça métodos para manipular sua estrutura de dados, como Add() e Remove() , para que seus consumidores não precisem tocar nos nós diretamente.

    
por 12.08.2014 / 19:24
fonte