My C homework

[A4000_Mad]

Thanks Mel, I'm really getting to like this C stuff :-)

I must not mention the beautiful new avatar......
I must not mention the beautiful new avatar......
I must not mention the beautiful new avatar......
I must not mention the beautiful new avatar......
I must not mention the beautiful new avatar......

But wow!!


A4000 Mad

[mel_zoom]

How strange - I was really annoyed at the time that picture was taken as I wrestling with a particularly annoying earpiece prior to a product release event!

I thought the look of perplexed frustration would be apt for when I start getting into more realistic C code :-)

[falemagn]

mel_zoom wrote:

I thought the look of perplexed frustration would be apt for when I start getting into more realistic C code :-)

Except that you don't look either perplexed nor frustrated, in that picture. ;-)

[madsjm]

I read "Mel C's homework", and I thought one of the Spice Girls was among us.

My face is red.  :roll:

[mel_zoom]

Ok I changed the title. Better?

[madsjm]

BTW: Seeing the number of replies Mel get in these forums.. She could work very well as the new marketing campaign for Amiga!  :lol:

[Jupp3]

I just wonder why you choose C, as that a language is old and on it's way out.

You know it's been going out since it was first published, still going (out) strong :-)

Also html is going out, and will be totally replaced with flash. Or is it still flash? At least it was >5 years ago...

I perfer object oriented stuff.

Me too. That's why I code C in object oriented way. imho, "being object oriented" is mostly the attitude of a programmer, more than a feature of a programming language.

yes, english is very old, and a huge part of the world still uses it. However it is evolving all the time, so learning old english first does not help you talk with people.

Luckily C is evolving aswell. There have been few newer standard revisions, but most notably there's steady development for various libraries, that you can use to do, well, just about anything.

[Cymric]

Piru wrote:
I guess what I am trying to say is: Don't be too hard on yourself and don't demand perfection from the beginning. Allow yourself to use simple(r) solutions, it is enough to recognize that better solutions exist. You can always improve the code after the basics work. (And in case you can't get the advanced solution working, at least you have the simpler one that DOES ;-))

In addition, it always makes a big impression on people when you're able to brag you've rewritten the code to make it 1000% faster. (Everyone goes 'Wow!' and 'That's HUMONGOUS!' and 'There's a coder who knows where his towel is!'.) What you don't say is how terrible your first solution was  :-P

[Karlos]

falemagn wrote:

mel_zoom wrote:

I thought the look of perplexed frustration would be apt for when I start getting into more realistic C code :-)

Except that you don't look either perplexed nor frustrated, in that picture. ;-)

It is a lot better than the look of sullen boredom I was wearing at that presentation :lol:

[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.

[falemagn]

@ Mel

Since you're never traversing the list backwards, you don't really need the "prev" pointer. Besides, you mispelled "prev" with "last" in the uniqueword structure definition. ;-)

About the loop issue: the "trick" is to not add the new word while within the loop, but do it always outside, trying to unify the cases in which it's the last word in the chain or one in between. You can state the loop's invariant property that when it finishes looping, the "last" pointer always points to the word after which you need to insert yours, then factor the loop in such a way as to make that the case.

In other words, consider the loop as the implementation of a "find" function that returns the pointer to the element in the list which is the upper bound of all elements that are less than the one you want to add.

If you need code hints, I can give them to you, but I'm sure you'll prefer to work that out by yourself. ;-)

[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 :-)

[falemagn]

mel_zoom wrote:
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 guessed as much, but still apart from that mistake the code as it is will work just fine. It's kind of amazing how you are so good at such stuff... the dream girl of any geek, I'd say. ;-)

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.

That may sound a clever idea, but you'd not get better performances than the one-way search unless you were thinking of parallelizing the algorithm... which would be quite an overengineering. :-) In both cases, the average compexity would be O(n/2).

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

There's still another improvement you could make, namely structure the code in such a way as to allocate the new uniqueword only in one place rather than in three like you do now. But we'll keep this for later... ;-)

[mgerics]

All right, I've figured it out - Mel Zoom is NOT a woman! HE is a lazy young brat who wants the 'cool' aspect of being able to program a computer, but is too lazy to do it HIMSELF. HE is taking code found on the web and plagiarizing it and taking advantage of the people on Amiga.org by asking for help with HIS 'pet' project!

Admit it, Mel! You found that avatar, who must be a local model from your home town, and decided 'those nerdy geeks at a.org will fall in love with this person and give me all sorts of free advice..'



Um, you know I'm just kidding, right? Best of luck in your endeavors. Makes me want to get back to C coding and delete Visual Basic from my computer.

[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.

[CannonFodder]

madsjm wrote:
I read "Mel C's homework", and I thought one of the Spice Girls was among us.

My face is red.  :roll:

Dirty boy! ;-)