FRIHOST • FORUMS • FAQ • TOS • BLOGS • DIRECTORY
You are invited to Log in or Register a Frihost Account!

A linked list.

   Frihost Forum Index -> Scripting -> Others
 


qebab
I have been spending some hours now, implementing a linked list and some functions for it in C.
- It is doubly linked (a node has a link to two nodes, one in front and one behind it).
- Whenever a node is added to a list, it should be added in the 'right' place, ie. the list is ordered by the content of the nodes, so it's always sorted.

I've made it work, and it does what it is supposed to. However, my make_node function suffers from a massive brainfart I'm having right now, and I used a goto in it. It's pretty disastrous, and it's hard to keep track on things. If anyone could take a look and see if they would be able to help me fix it (I'm still suffering from my brainfart and can't see the way), I would be very happy.

The comment in the code about the function should show how things are intended to work.
Code.

Thanks in advance.
MrBlueSky
When traversing a recursive datastructure (a datastructure which contains a pointer to itself) a natural thing to do is to use a recursive function (a function which calls itself). So lets create a recursive function "insert_node" which inserts a node into a list:

When the list is empty, the function can simply return the node: there is nothing more to do. Inserting a value in an empty list results in a list containing just that one value:

Code:

node *insert_node(node *alist, node *anode) {

   // inserting a node in empty list: is just the node itself
   if (alist == NULL) {
      return anode;
   }
}


If the list isn't empty, we check its first value. If the value to be inserted is smaller we can append it to the start of the list:

Code:

   if (anode->content < alist->content) {
      // insert anode here
      anode->next = alist;
      alist->last = anode;
      return anode;
       }


If the first value is smaller than the value to be inserted we need to insert the value into the tail of the list (list->next) at the right place and return the altered list. This is the recursive part. We already have a function which inserts a value into a list at the right place: the function itself. We only have to call it with the correct arguments:

Code:

if (anode->content >= alist->content) {
      // insert anode in the tail of the list
      anode->last = alist;
      alist->next = insert_node(alist->next, anode);
      return alist;
}


Here we construct a list by just taking its first element, and letting list->next point to the original list->next with the value anode inserted in it.

The entire program:

Code:


/* A node in a linked list. */
typedef struct link {
     long content;
     struct link *next;
    struct link *last;
} node;
 


node *make_node(long content) {

    node *self = malloc(sizeof(node));
   self->content = content;
   self->next = NULL;
   self->last = NULL;
   return self;

}

node *insert_node(node *alist, node *anode) {

   // inserting a node in empty list: is just the node itself
   if (alist == NULL) {
      return anode;
   }

   // non-empty list
   // check the values
   if (anode->content < alist->content) {
      // insert anode here
      anode->next = alist;
      alist->last = anode;
      return anode;
   } else {
      // insert anode in the tail of the list
      anode->last = alist;
      alist->next = insert_node(alist->next, anode);
      return alist;
   }

}

int main() {
   node *mylist = insert_node(NULL, make_node(5));
   mylist = insert_node(mylist, make_node(7));
   mylist = insert_node(mylist, make_node(6));
   mylist = insert_node(mylist, make_node(8));
   return 0;
}



I have added a function make_node which creates a new node given a value, because the insert-function has to insert nodes in a linked list, not create new nodes. This makes it easy to make it recursive: it only accepts pointers to nodes and returns a pointer to a node.
Indi
i don't see that it's really necessary to completely write an interface to get rid of a single goto. i made a suggested change here, but messed up those old-school comments.

But long story short, all you need to do is step through your list until you find the first node whose content is greater than the value you have. Then just insert the new node before that node.

There are only two special cases: when the new node will become the new first node (its content is smaller than the content in the first node), and when the new node will become the new last node (its content is greater than the content in the last node).

If you're clever, you only need to handle one of those cases explicitly, and the other will take care of itself (in the code i wrote, the latter case gets taken care of automatically).
qebab
Both seem to be clever solutions, but I've had to put off C for a while after uni started again, so I haven't tested them. Thanks for the assistance! Smile

Quick question; How useful would a datastructure like that be? I don't really write any big programs, rarely more than 400-500 lines at the most (Notable exception being a 5 000 line IRC bot written in Python), so I don't have much experience with datastructures.

The motivation for learning C I originally had was to be able to extend and embed the python interpreter and have a very fast (As in computer-time, not my time) alternative for very demanding calculations. However, I really, really like C now, it's interesting and it has my curiosity pinned. But it's sort of... small. The other day I was performing a heavy numerical calculation only to find out that the numbers got too large for long long (Only after the calculation was finished), so it was hopelessly inaccurate.

I guess I should google before I ask, but I might as well post here when I'm on a roll anyway. Do either of you happen to know a big-number library, a string library and some datastructure libraries for C? (Datastructures as in hashtables and sets, possibly some trees)
Indi
This is just opinion, and not very helpful if you're just interested in C - but i've always found C to be a royal pain in the ass when it came to doing any serious math. Fortran or C++ are what i always end up falling back on.

Unless you're married to C - and i can't imagine why anyone would be in the 21st century (as you say, it is "small") - you will find that doing math in C++ can be almost laughably easy. You could write your own big number class without too much effort... and it would automatically work with tons of existing code with no modifications. Observe:
Code:
// To find the differences between the values in two lists of integers
array<int, 4> a = { 4, 3, 8, 7 };
array<int, 4> b = { 6, 5, 3, 6 };

list<int> result;

transform(a.begin(), a.end(), b.begin(),  b.end(), back_inserter(result), minus<int>());

////////////////////////////////////////////////////////////////////////////////////
// To find the differences between the values in two lists of big numbers
array<bignumber, 4> a = { 4, 3, 8, 7 };
array<bignumber, 4> b = { 6, 5, 3, 6 };

list<bignumber> result;

transform(a.begin(), a.end(), b.begin(),  b.end(), back_inserter(result), minus<bignumber>());

////////////////////////////////////////////////////////////////////////////////////
// Pretty much no changes, except the type
// And if you were smart... you wouldn't have to worry about that either


Also, you wouldn't have to worry about writing a linked list - there's one already built in.
qebab
I see. Well, you give sound and honest advice, even though it wasn't the one I wanted to hear. Smile

I'll take a look at C++ again when I find the time, I guess.
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2007 Frihost, forums powered by phpBB.