Thread: Finding the Mode

You know what, since I wrote the code, I will explain it. So here goes...

There is nothing special here other than your header that defines inD() and outD() and all of those functions that you use for IO.

Code:

#include <FPT.h>

This is my linked list type. It basically contains a numeric value (of the double type), value. It also keeps track of the frequency of the value through the member frequency which is an integer type. The next member simply points to the next node in the chain. This is how a linked list works.

Code:

struct node
{
  double value;
  int frequency;
  struct node *next;
};

The insert function just adds a new node by inserting the nodes in logical order.

Code:

struct node *insert(struct node *p, double value)
{
  struct node *tmp = p, *head = p;

If the input is 0 that means the list is empty. This if statement simply creates the initial node in all of its glory.

Code:

  if(!p)
  {
    p = malloc(sizeof(*p));

    if(p)
    {
      p->value = value;
      p->frequency = 1;
      p->next = 0;
    }

    return p;
  }

So what if the first node exists? Ok well then instead of making a new list, we are going to go down the list and search for the appropriate position to insert the new data. This is a basic insertion sort technique. The only reason it is efficient for this code is because things are never going to be out of order.

Code:

  /* From here on out, p represents the previous node in the tree */
  for(p = 0; tmp; tmp = tmp->next)
  {

If the value of the node you are viewing matches the value you are inputting instead of adding anything new, we are just going to up the frequency count, and return the beginning of the list.

Code:

    if(tmp->value == value)
    {
      ++tmp->frequency;
      return head;
    }

If the value of the node we are looking at is less than the value of the input than that means the previous node was the last node with a value greater than the input value. In other words you know that this node should go between the previous node and the node that you are looking at. Which is why I have been storing the previous node in p.

Code:

    else if(tmp->value < value)
    {
      tmp->next = p;

      p = malloc(sizeof(*p));
      if(p)
      {
        p->value = value;
        p->frequency = 1;
        p->next = tmp;
        return head;
      }
    }
    p = tmp; // This stores the previous node into p.
  }

  return 0;
}

The clean function recursively destroys the linked list. That is an important step since if we don't clean up the entire list there is a memory leak in the program.

Code:

void clean(struct node *p)
{
  if(p)
  {
    clean(p->next); // This is where the function recurses.
    free(p);
  }
}

This output function is also recursive.

Code:

void outN(struct node *p)
{
  if(p)
  {
    printf("%g\t%d", p->value, p->frequency);

If you wanted to reverse the print order, its a simple matter of switching the last line of the above code block with the first line of the bellow code block.

Code:

    outN(p->next);
  }
}

Last but not least, run this stuff. Its just a simple modification of your code, so I don't think you will have much trouble understanding what is going on here.

Code:

int main()
{
  double i;
  struct node *p = 0;

  outS("Please input a postive integer...");

  while((i=inD())>=0){
    p = insert(p, i);
  }

  outN(p);
  clean(p);
}

Ok thank you so much! That would be greatly appreciated, my friend and i are stumped on this problem..

Any luck?