Thread: Count distinct elements in an list in C

  1. #1
    Registered User
    Join Date
    Dec 2020
    Posts
    2

    Count distinct elements in an list in C

    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;
    }
    Last edited by Xaris; 12-02-2020 at 09:25 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2012
    Posts
    505
    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.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program to count each distinct word input
    By nvangogh in forum C++ Programming
    Replies: 1
    Last Post: 06-30-2015, 09:50 AM
  2. Help keeping a count of distinct values
    By Kevin Nguyen in forum C Programming
    Replies: 9
    Last Post: 09-13-2013, 12:31 AM
  3. Pointers and printing distinct elements in array
    By dave_the_bear10 in forum C Programming
    Replies: 2
    Last Post: 10-29-2011, 01:31 AM
  4. Replies: 2
    Last Post: 07-28-2010, 02:07 PM
  5. Count distinct array values
    By rkooij in forum C Programming
    Replies: 4
    Last Post: 10-03-2006, 03:03 AM

Tags for this Thread