Skip to main content
gamedev.net
🔒 Locked

Data Structure Implementation

Started by AcePilot 4 replies 1.6k views
Original Post
AcePilot
AcePilot
I have finally created my own implementation of a data structure :) can anyone tell me a way to improve on this? 

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

int loop;

typedef struct str
{
	struct itm* base;  
	int count;

}structure;

typedef struct itm
{
	struct itm* next;
	struct itm* prev;
	void* data;
}item;

struct itm* get_item(int n, structure* stack)
{
    item* cur = NULL;
	item* stp = stack->base;

	if(n == 0)
	{
		return stack->base;
	}
	for(loop = 0; loop < n; loop++)
	{
		stp = stp->next;
	}

	return stp;
}

void add_item(struct itm* itm, structure* stack)
{
	struct itm* last = get_item(stack->count, stack);
	last->next = itm;
	itm->prev = last;
	itm->next = NULL;
	stack->count++;
}

void init_stack(structure* stack)
{
	stack->base = (struct itm *)malloc(sizeof(struct itm));
	stack->count = 0;
}

void remove_item(int n, structure* stack)
{
	struct itm* rem = get_item(n, stack);
	rem->prev->next = rem->next;
	if(rem->next != NULL)
		rem->next->prev = rem->prev;
	free(rem);
	stack->count -= 1;
}

item* New_Item(void* data)
{
	item* itm = (item*)malloc(sizeof(item));
	itm->data = data;
	return itm;
}
xor
xor
Maybe implement FIFO and FILO methods for two types of stack.
Maybe make it OO.
Maybe implement other data structures.
Specialist
Specialist
Quote:
Original post by xor
Maybe implement FIFO and FILO methods for two types of stack.
Maybe make it OO.
Maybe implement other data structures.

Add template.
demonkoryu
demonkoryu
Hi,

your first data structure? Nice... for a coder, thats should feel like the first love oO
Seriously, this PDF gives some good ideas to improve your data structure. There is some irrelevant stuff in it, but you'll need push/pop/deque etc. methods in your structure. And some times after that, you should make that a C++ class (from your design, it could be easily converted to a C++ class). And then... of course.. templates, so you don't need to use thouse filthy, not type-safe void* pointers!

Keep it going!
AcePilot
AcePilot
Hey,

Thanks Konfusius that pdf file really helped. By the way, i did try to make it some OOP using C by creating a struct called structure. If i didnt do that, i would have to create a copy of these functions for each data structure i create!
Zahlman
Zahlman
I assume you're using plain C. This stuff is of course easier to implement in C++ using templates (and you also don't have to pay for the pointer that way... I guess you could hack some macros together in C but... ugh...). Of course, it's even easier to implement in C++ using std::list ;) But I assume your intent is to learn the low-level details, which is fine. So I will suffer your void*s and what-not :)

int loop;

!!! Asking for trouble. Scope it properly.
typedef struct str{	struct itm* base;  	int count;}structure;

Add a pointer to the other end, too (and keep it properly updated) so that you don't have to scan through the list for each append.
struct itm* get_item(int n, structure* stack)

I'd put the parameters the other way around. Conventionally the "this parameter" comes first when you do these things in C. Also, make it return the actual void*. One important OO concept is encapsulation; here, that means not making the outside code have to muck around with the stack's implementations details (i.e. the 'node' structs). Oh, and if you're going to use the typedef struct idiom, then USE it - i.e. "item* get_item".
{    item* cur = NULL;	item* stp = stack->base;

Don't be so skimpy with your variable names; they don't cost you anything :)
	if(n == 0)	{		return stack->base;	}

You don't need this special case, so don't include it. Test it if you don't believe me.

However, you might just want to do some bounds checking on n in case it's negative or in excess of the list length...
void add_item(struct itm* itm, structure* stack)

Again, reverse the arguments, and take in an actual void* rather than an 'itm' struct. Oh, and document that the user is responsible for copying stuff if needed! :)
void init_stack(structure* stack){	stack->base = (struct itm *)malloc(sizeof(struct itm));	stack->count = 0;}

OK, so you're keeping a sentinel node in place. Have you noticed that your indexing for get_item is thus off-by-one (or at least, 1-based)? Or that this might not work because you don't initialize the initial "base" item?

Meanwhile, you really should instead make it so that you have (and expose via the header; see way below after the horizontal rule) a function to *return a new 'stack'* instead. This is even though I'll tell you *not* to expose a function for new item creation (see below). The difference is that stacks are the structure that users will be concerned with, while items are an implementation detail embedded within stacks.
void remove_item(int n, structure* stack)

Design issue: You can only add to the end, but you can remove from anywhere. What kind of data structure is that?
rem->prev->next = rem->next;

What if you try to remove item 0?
item* New_Item(void* data)

Going along with the other suggestions, this would become a "private" method, and would get invoked where needed to create items. Factoring it out like this is a reasonably good idea though. :)

And once you have a solid (and do remember to test it!) implementation, be careful with your header design. Related to encapsulation is the concept of information hiding, i.e. not giving users information they don't need (which they could then use to mess things up). So the header should only refer to things that will be needed in order to link and use the functionality.

With the other suggestions I made, you would want to include the following in the header:

- Declaration of the 'structure' struct (not mentioning its members! Outside code doesn't need to know about that stuff, either logically - users shouldn't muck around with it - or technically - since they only have pointers to 'structures', the contents needn't be known for linking). Note that 'item' won't be mentioned at all outside.
- Prototypes for the other functions, using void* rather than item* of course (see above comments about interface). Except not for "New_Item", which would become for internal use only. This is how you do "private" in C ;)

And that's it, this time. If any of those library headers were required in order to make the actual declarations (and it happens sometimes, though not so often with stdlib et al. as with, say, time.h), then I would put them in the header as well. This is way better than expecting the client code to include those headers before yours, because that's one more thing to worry about that you really don't need when everything's in order.

Oh, and don't forget your include guards :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.