Re: arrays vs linked lists [LONG]

From: George (
Date: 01/06/99

On Wed, 6 Jan 1999, Invincibill wrote the >

>>         Both of the types above can be put into any sorting algorithm
>> rather easily.  BST's are simple with arrays.. Incredibly easy as a matter
>> of fact.  Once you've written your control functions, they're just as

>I hope you arent confusing doing a binary search on an array with
>implementing a BST with an array. they are quite different. at least if
>i remember correctly. its been awhile. yes, the routine to search an
>array by a binary search is quite simple (about 30 lines or so). So is
>the function so search a BST array(recursive, about 6 lines). but the
>BST array is nasty nasty to setup(not to be confused with hard, just
>ugly)in an array.

/* returns the real number of the room with given virtual number */
int real_room(int vnum)
  int bot, top, mid;

  bot = 0;
  top = top_of_world;

  /* perform binary search on world-table */
  for (;;) {
    mid = (bot + top) / 2;

    if ((world + mid)->number == vnum)
      return mid;
    if (bot >= top)
      return NOWHERE;
    if ((world + mid)->number > vnum)
      top = mid - 1;
      bot = mid + 1;

22 lines, counting the comments and without hyper-compacting.  Not too hard
to follow either...  Of course, you have to ensure sorting.

>if you have an array of strings, you cant just say goto array[string] and
>get the element so the example of saying mob=mob_list[700] only applyies a
>small portion of the time. that is one good thing about an ordered array
>of integers tho.

Not unless you use Perl. :)

If you had an array of strings (char *[]), you'd basically have
constants.c.  It's just arrays of strings indexed by integer values.

>i suppose it would be beneficial to implement the linked list scheme and
>make a file called search.c or sort.c which implements all your basic
>functions. then it would be just like a library.(unless you wanted to
>use existing libraries which are out there). But, combined with
>abstraction, i would think BST's would significantly increase the
>efficiency. but no more ram or cp than Circle takes up, compared to
>today's machines, its probably not worth it to mess with it other than
>if you are a typical obsessive coder who has to have the fastest and
>most efficient code there is :)

It's still in development (get v1.0.x for stable) but has many useful
functions and portability aids. Including single and doubly linked list
implementations and hash tables.   There's more, but it's best to just go
read it.

George Greer

     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     |  |

This archive was generated by hypermail 2b30 : 12/15/00 PST