> Well, I wonder if someone could tell me how I might sort a linked list in a
 > similar way to sorting an array with QSORT()?

There's an example of this in the C_ECHO snippets file, latest issue (as
far as I know) is April 1993, filename SNIP0493.ZIP.  I mention it here,
rather than posting the algorithm itself, because you'll probably find a
lot more useful code and tips in there, so it's worth getting in any case.

However, I'm a big fan of dynamic arrays and while I occasionally use
linked lists I usually use dynamic arrays regardless. Apart from having to
use realloc() now and then and putting up with the fact that it is
sometimes slow - which is not the case with adding items to linked lists -
there's very little reason not to use dynamically allocated arrays. While
it is often said that realloc() can cause memory fragmentation, it can be
easily demonstrated that using linked lists can do so as well. The
advantage of dynamic arrays vs. linked lists in this regard is
implementation dependant.


 > I cannot find any built-in functions (eg QSORT()) that allow
 > you to do this.
 > Also, I cannot figure out how to dynamically create/resize an array of say
 > INTs or whatever.  Is this possible?  Can you allocate memory for an array
 > dynamically?

Certainly.  A pointer to a type may also be useful as a pointer to an array
of a type, eg:

    int sizeOfArray = XXX;  /* Where XXX is any number you like */
    int * intArray = malloc(sizeOfArray * sizeof(int));
        /* Points to a block of XXX ints */
    int i;

    for (i = 0 ; i < sizeOfArray ; ++i)     /* Initialise the array */
        intArray[ i ] = i;


 >  If not, it appears that a linked list is the only way to
 > allocate space as required and to delete (shrink) space when
 > no longer needed.

If you need to change the size of the array, you can add some smarts, such
as a variable to contain the list of 'active' entries. You'd then expand or
contract the list using realloc() when adding or removing entries but to
avoid lots of overhead you'd be adding entries in 'lumps' rather than
individually.

# include 
# include 

# define GROW_DELTA    16  /* May require some tuning */
# define INIT_SIZE     16  /* ... */

 typedef struct _myarray myArray;
 struct _myarray
 {
    int sizeOfArray;    /* Array size */
    int activeCells;    /* Number of active entries */
    int * intArray;     /* Pointer to array itself */
 };

 myArray *
 initArray (void)
 {
    myArray * m = malloc(sizeof(myArray));
    if (m == NULL ||
        (m->intArray = (int *) malloc(INIT_SIZE * sizeof(int))) == NULL)
        abort();    /* Not graceful, but demonstrates the point */
    m->sizeOfArray = INIT_SIZE;
    m->activeCells = 0;
    return m;
 }

 void
 addToAray (myArray * m, int * newInt)
 {
    int atCell = m->activeCells;
    if (++m->activeCells >= m->sizeOfArray) /* Gone out of bounds? */
    {
        m->sizeOfArray += GROW_DELTA;       /* Increase size */
        m->intArray = realloc (m->intArray, m->sizeOfArray);
        if (m->intArray == NULL)
            abort();
    }
    m->intArray[atCell] = *newInt;      /* Add item to array */
 }

 int
 compareInts (const void * a, const void * b)
 {
    const int * x = (const int *)a;
    const int * y = (const int *)b;
    return (*x == *y) ? 0 : (*x < *y) ? -1 : 1;
    /*
       could also be "return (*x - *y);", but this works if x and y are
       unsigned values as well as it doesn't cause nonportable sign overflow
     */
 }

 void
 sortArray (myArray * m)
 {
    qsort (m->intArray, m->activeCells, sizeof(int), compareInts);
 }


I haven't run this through a compiler so there are probably some typos here
or there, but you get the idea.

Good luck,

  david

---