Count distinct elements in an list in C

Quote:

---

I want to count all the distinct numbers of a list.For example if my list consist of {1,2,1,1,3,4} i need to return 4.Here is the code i have written.Something is missing but i don't know what.

---

Code:

---


struct Node
{
  int data;
  struct Node *next;
};
typedef struct Node Node_t;



int count_distinct(Node_t * start)
{
    Node_t  *ptr1, *ptr2;
    ptr1 = start;
    int counter=0;
    /* pick one element*/
    while (ptr1 != NULL && ptr1->next != NULL)
    {
        ptr2 = ptr1;

        /* compare picked element with the rest */
        while (ptr2->next != NULL)
        {
            /* If duplicate */
            if (ptr1->data == ptr2->next->data)
            {
                break;
            }
            else /*if unique element must counter++*/
                //do what???
                ptr2 = ptr2->next;
                counter++;
        }
        ptr1 = ptr1->next;
    }
return counter;
}

---

Are you allowed to do things like
- copy found entries into a list that only contains unique instances
- clone the list you have so you're free to remove all duplicates

> 1,2,1,1,3,4
The tricky part is going to be not counting the 1 again, as you already counted it on the first pass.

Sort the list.

Since it's a linked list, you can't use qsort. Mergesort is a good linked list sort algorithm.

Now it's trivial to pick out the unique instances. A unique instance is either the first in the list, or an instance with a non-equal prior.

Does this work?

Code:

---

#include <stdio.h>
#include <stdbool.h>
struct Node
{
  int data;
  struct Node *next;
};
typedef struct Node Node_t;

int count_distinct(Node_t * start)
{
  int counter = 0;
  for ( Node_t *ptr1 = start ; ptr1 != NULL ; ptr1 = ptr1->next ) {
    printf("Outer loop ptr=%p, looking for %d\n", ptr1, ptr1->data );
    Node_t *seen_before = start;
    for ( seen_before = start ; seen_before != ptr1 ; seen_before = seen_before->next ) {
      if ( seen_before->data == ptr1->data ) {
        printf("  Found previous at %p\n", seen_before );
        break;
      }
    }
    if ( seen_before == ptr1 ) {
      printf("  First time seeing %d\n", ptr1->data );
      counter++;
    }
  }
  return counter;
}

int main ( ) {
  Node_t list[] = {
    {1,&list[1]},
    {2,&list[2]},
    {1,&list[3]},
    {1,&list[4]},
    {3,&list[5]},
    {4,NULL},
  };
  printf("%d\n",count_distinct(list));
  return 0;
}

---