By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,435 Members | 2,891 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,435 IT Pros & Developers. It's quick & easy.

Counting duplicate number in an array- implimented BST

P: 6
This code is created to find all duplicates in a list of number by using a binary search tree implemented as an array. I want to add a function to count how many numbers in the list are duplicated but i dont know where to put it. It's really confusing. One more, i want to increase my array size to 5,000,000 but the program doesnt work.I dont know how to fix it. Plz help me.Thanks 4 advance.

Expand|Select|Wrap|Line Numbers
  1. #include <stdlib.h> 
  2. #include <stdio.h> 
  3. #include <conio.h>
  4.  
  5. #define TRUE 1 
  6. #define FALSE 0 
  7. #define TOTAL_SLOTS 500000     
  8.  
  9. struct nodetype 
  10. long int info; 
  11. long int used; 
  12. }node[TOTAL_SLOTS] ; 
  13.  
  14. //initialize a tree
  15. void initialize (); 
  16. void initialize() 
  17.      long int i; 
  18.      for (i = 0; i<TOTAL_SLOTS; i++) 
  19.          node[i].used = FALSE;                 //mark every node as unused
  20.  
  21. //add node to the tree  
  22. void addnode (long int node_id,long int value) ;  
  23. void addnode (long int node_id,long int value ) 
  24.  
  25.  
  26.        node[node_id].info = value;            //assign the value of the number to the appropriate node_id in the tree
  27.        node[node_id].used = TRUE ;            //mark node as used one
  28.  
  29.  
  30.  
  31.  
  32. int main(void) 
  33.  
  34. {
  35.  
  36. //function ask user for the list of numbers      
  37.      printf("To start, please enter the number of elements in the list: ");
  38.      scanf("%d",&n);
  39.  
  40.      for (i=0;i<n;i++)
  41.      {
  42.           printf("Please enter number #%d: ",i+1);
  43.           scanf("%d",&a[i]);
  44.      }
  45. //initialize the tree
  46.      initialize(); 
  47.  
  48. //examine the numbers in the list
  49.      for(i=0;i<n;i++) 
  50.      { 
  51.        node_id=0; 
  52.        while ((node_id < TOTAL_SLOTS)) 
  53.        {
  54.               if (node[node_id].used == FALSE)   //while node_id has not been used
  55.               {
  56.                      addnode(node_id,a[i]);      //add node_id to the binary search tree
  57.                      break;
  58.               } 
  59.               if (a[i] == node[ node_id ].info)   //while current value has already been in the BST
  60.               {
  61.                      printf("\n%d is a duplicate", a[i]); 
  62.                      break; 
  63.               } 
  64.               if (a[i] < node[node_id].info)       //while value is smaller than the root
  65.                      node_id = 2* node_id +1;      //go to the left subtree
  66.  
  67.               else   
  68.                      node_id = 2* node_id +2;      //go to the right subtree
  69.        } 
  70.  
  71.        if (node_id >=TOTAL_SLOTS) 
  72.        {
  73.               printf("overflow error\n"); 
  74.               exit(1); 
  75.        } 
  76.  
  77. getch ();
  78.  
  79.  
Dec 10 '07 #1
Share this Question
Share on Google+
3 Replies


Expert 100+
P: 849
If a long int is 4 bytes, then an array of 5,000,000 of nodes would use up about 8*5000000=40,000,000 bytes. Thus, simply allocating memory for this program would require at least 40MB. Your compiler probably doesn't want to do that.

You can add the function in the same general area as your other functions, after the struct is defined and before main().

Or, you can simply count up how many times <value> "is a duplicate" prints during your main and print that, no function required.
Dec 10 '07 #2

P: 6
Thank u very much!
About the function count, I mean that I dont know where to put it in the main function.
Dec 11 '07 #3

Expert 100+
P: 849
From the looks of it, a function is really not what you want here, unless you want unnecessary overhead associated with calling it. Simply initialize and use an integer to count the number of times you have to print "duplicate value" when you try to insert.
Dec 11 '07 #4

Post your reply

Sign in to post your reply or Sign up for a free account.