5

I've been reading through Introduction To Algorithms 3rd Ed, and I am having difficulty in implementing some practical situations. It's not the theory, or implementing the internals of the data structures themselves, but rather how to design a good interface that makes the data structures useful for storing real data (as opposed to just the keys).

Specifically, I'm told that C has a very "trust the programmer" type philosophy. I just don't know how much trust is too much trust:

As an example, many data structures can be implemented as linked structures with similar nodes having a key, satellite data, and pointers to other nodes in the ds, ex:

typedef struct {
    int key;
    void *data;
    node_t *prev;
    node_t *next;
} node_t;
  1. To what extent should I be encapsulating my implementations? For most structures, you have both: (a) a data structure type, and (b) a type that can be inserted/deleted from the data structure. Should they both be hidden? Clearly if I expose a some node_t with the intention someone only alters key and *data.. theres the possibility prev or next is altered, thus destroying the data structure. A similar risk exists if I expose the data structure type and someone messes around with the root..

  2. How should the keys be stored/accessed/compared? Presumably, the keys depend on the satellite data, but if you go the approach as above, you've decoupled the key from the data itself. What would happen if a user updates the data but forgets to update the key (or worse, they update the key, but don't remove/reinsert it into the ds)? For something like a binary tree which uses only comparisons, I could design the interface to accept comparators that accept pointers to the satellite data? This makes the structure more generalized, but all the defreferencing has to have an impact on speed. Alternatively, (and would be needed for structures like hashes which need a concrete key), I could accept a pointer to a int toKey(void *data)function..

I'm unclear on how good software should be designed for use in the real world.

  • The question in general is pretty good but I find Q2 is a little senseless: either the key is a function of the data (or viceversa) and if you have one you can get the other, or they are decoupled and what your structure is representing is that relationship. Of course, depending of the case you will use one data structure or another (a list or set for the first case, a map for the other). – SJuan76 Aug 12 '14 at 17:32
  • @SJuan76 The problem I'm trying to get at is: suppose the keys are functions of the data. If I change the data, the key will change too .. but the node's position in the data structure wont change. This will result in corrupting the integrity of the structure (for example, a binary tree may loose it's binary-tree property). On the other hand, I have to worry about both a separate keys and data. Altering the data won't have an affect on the key .. but now a user of the altered data may compute a key externally from the data, and never find it in the datastrucuture – Joney Aug 12 '14 at 17:43
  • No, if you change the data of a node in a binary tree it will still be a binary tree. A sorted tree, though, might be get "unsorted". It is a different issue. For sorted structures, what you need is not a key, but an ordering function that signals how to data items are related (see java.lang.Comparable for an example). A key number and comparing by that key number is just an special, very limited implementation of such a version. – SJuan76 Aug 12 '14 at 17:56
  • 1
    As for "altering the data may invalidate the inner structure", the usual answer is "Don't do that"; just add some documentation saying "do not alter the data". For example, in Java you should make hashCode and equals should be based in attributes that are inmutable and so should not change through the live of an object, if in yours implementation it changes... well, have fun with anything Hash*. – SJuan76 Aug 12 '14 at 18:00
  • 1
    Maybe going here a little of topic, but I think it's worth to mention, that AD 2015 you might consider using C++ instead of C. I don't want to got too deep into specifics, but your linked list is actually a great example, that once you start dealing with more complex data structures you end up creating your own quasi-C++ object oriented stuff and reinventing the wheel. Sure, it may be good for for learning how these higher level collections / sets etc really work on the inside, but for actual real life projects it's just too much a risk. I hardly can think of any applications (except maybe rea – Łukasz Zwierko Jul 6 '15 at 18:59
4

Provide methods for manipulating your data structure such as Add() and Remove(), so that your consumers don't have to touch the nodes directly.

  • Yes, but what should these methods accept? A void pointer to data and a pointer to a comparison function (or in a hash, a to_key function)? Should I pass the key separately? Having a user retain a reference to the data and externally altering it while it's in the datastructure (thus potentially destroying the ds) seems about equally likely as them externally altering a pointer in a node type – Joney Aug 12 '14 at 17:50
  • I just don't know how to make an objective judgment on which design choice to go with .. they all seem like they have pros & cons. None appear to be "the best" – Joney Aug 12 '14 at 17:54
  • Have a look at a sample implementation, like this one, especially the insert and remove methods. Your user should be able to hand a pointer to the data structure (or an insertion point to the data structure) and a partially filled out struct instance. The method should fix up the pointers. – Robert Harvey Aug 12 '14 at 17:55
  • Thanks for that. Three follow-up questions: (1) doesn't this result in the element's data being copied into the list ? (2) Is it good practice to have the datastrucutre itself take ownership of managing the memory? (3) For something like a btree, I'm still forced to consider either passing a function that either compares elements, or extracts a key from them vs passing a separate key – Joney Aug 12 '14 at 18:09
  • 1. It depends on how you implement your insert method. You might only manipulate pointers. 2. The data structure should manage memory. 3. Yes, you've got the right idea. Passing a function is one way to keep the tree generalized so that it will work for any struct. – Robert Harvey Aug 12 '14 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.