My C homework

[mel_zoom]

Ok I changed the title. Better?

[mel_zoom]

Noooo! I just wrote a really long post and got logged out!

Luckily I was writing most of it in a text editor - phew!

...

Its been a few days now and I read up on malloc(). I realised that malloc doesnt actually care what you are allocating memory for so I changed the structure a little bit so that the text becomes a part of it.

Anyway, this is what I am working towards now:

Code: [Select]



int addword(const char* wordtext); /* main prototype */

struct uniqueword {
    struct uniqueword* last;
    struct uniqueord* next;
    int count;
    char wordtext[1]; /* copy of the text */
};

static struct uniqueword* firstword;

static struct uniqueword* createuniqueword(const char* wordtext)
{
    /* create a new uniqueword structure */
    int wordlength;
    struct uniqueword* unique;

    wordlength = strlen(wordtext);
    unique = (struct uniqueword*)malloc(sizeof(struct uniqueword)+wordlength);

    /* fill in data if malloc() ok */
    if (unique != NULL) {
       unique->last = 0;
       unique->prev = 0;
       unique->count = 1;
       strcpy(unique->wordtext, wordtext);
    }
    return unique;
}

int addword(const char* wordtext)
{
   /* returns 1 if the word was added or zero if it existed or -1 on failure */

   struct uniqueword* newword;
   struct uniqueword* last;
   struct uniqueword* uw;
   int worddiff;

   if (!firstword) {
      newword = createuniqueword(wordtext);
      if (newword) {
         firstword = newword;
         return 1;
      }
      else {
         return -1;
      }
   }

   for (uw = firstword; uw != NULL; uw = uw->next) {
      worddiff = stricmp(wordtext, uw->wordtext);

      /* found it! */
      if (worddiff == 0) {
         uw->count++;
         return 0;
      }

      /* as soon as word > uw->word we insert it immediately before uw */
      if (worddiff > 0) {
         newword = createuniqueword(wordtext);
         if (newword != NULL) {
             newword->prev = uw->prev;
             newword->next = uw;
             uw->prev = newword;
             newword->prev->next = newword;
             return 1;
         } else {
             return -1;
         }
      }

      /* remember the last uniqueword */
      last = uw;
   }

   /* we reached the end of the list without finding it */
   newword = createuniqueword(wordtext);
   if (newword) {
      last->next = newword;
      return 1;
   }
   return -1;
}



Im not really happy with the loop though. Im trying to keep the words sorted based on the greater than / less than return of stricmp() so that the entire list isnt always searched before deciding to add the word.

I think its quite ugly though (having to have a "last" pointer just because the normal loop finishes when uw is null) and probably broken too.

Would "(uw != NULL) && (uw->next != NULL)" in the loop be better? It looks like it would always skip the last one on the list regardless which would only mean having to check if that one matches the wordtext outside the loop which also seems a bit stupid.

[mel_zoom]

falemagn:

Thanks for the hints. The code there was put together but not yet compiled so I expect there to be those sorts of bugs.

I thought about having a search that ran from both ends towards the middle that could terminate once the pointers "cross over". Thats why I thought about having prev/next.

As you can tell I am still some time from making it work :-)

[mel_zoom]

falemagn:

I see. One direction it is then! Is the stricmp() based 'sorting' still useful or not in your opinion?

I ask because a "hash code" was suggested earlier - perhaps I could replace the "prev" with a hash of the string and compare that but I expect any greater than / less than information would be lost.

I got given the following example hash function by Karlos:

Code: [Select]


unsigned long hash32(const char* text)
{
    unsigned long result = 0;
    unsigned long mask = 0x80000000;
    char *pc = (char*)text;
    while (*pc) {
       result = (result<<1) | ((result&mask) ? 1 : 0);
       result ^= (unsigned long)(*pc++);
    }
    return result;
}


Im not entirely sure yet how that works but it generates a "relatively unique" value from the string given. His suggestion was that I should use the hash value of the word being searched for and compare it to the hash value of the existing uniquewords in the list. Only when the hash values match call strcmp() to ensure they are the really same. Im told this should be faster than calling strcmp() each word in turn especially as the list grows.

Unlike my origial idea though it has to check the whole list before deciding the word is not present.

He did also point out that Id need to handle the case insensitivity issue for the above idea to work too.