count number of comparisons

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
Reply

•
•
Join Date: Oct 2009
Posts: 10
Reputation: timaquerra is an unknown quantity at this point 
Solved Threads: 0
timaquerra timaquerra is offline Offline
Newbie Poster

count number of comparisons

 
0
  #1
Oct 31st, 2009
Hello guys!

I'm new to C language and I need help to write a program which searches specific word in text file using Binary Search and count the number of comparisons!!!

My text file consist of following data:
apple
book
clock
dog
elephant
fat
hello
key
lucky
moon
olive
paper

So far, i made program which searches word and gives the location (index) of this word in file. However, that's not what I need, I need to count the number of comparisons!

I'm currently here:
C Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #define MAXSIZE 20
  5. #define MAXLEN  20
  6.  
  7.  
  8. int seq_Search(char array[][MAXSIZE], int count, char *key);	
  9.  
  10. int main(void)
  11. {
  12. 	char target[MAXLEN];
  13. 	char words[MAXLEN][MAXSIZE];
  14. 	FILE *file;						
  15.  
  16.  
  17. 	if((file = fopen("a3.txt", "r")) == NULL){
  18. 		printf("Cannot open file\n");
  19. 	} 
  20.  
  21. 	else{
  22.  
  23. 		int i = 0;
  24.  
  25. 		while(!feof(file)){  
  26. 			fscanf(file, "%s", words[i]);
  27. 			}
  28. 			i++;
  29. 		}
  30.  
  31.  
  32. 	printf("\n\nInput: ");
  33. 	scanf("%s", target); 
  34.  
  35.  
  36.  
  37. 			int location = seq_Search(words, 15, target);
  38.  
  39. 			if((strcasecmp(words[location], target)) == 0){
  40. 				printf("\nWord %s found", target);
  41. 				printf("Location: %d\n", location);
  42. 				}
  43. 			else{
  44. 				printf("\nWord %s cannot be found   ", target);
  45. 				printf("Location: %d\n", location);
  46. 				}
  47.  
  48.  
  49. 	}
  50. 	return 0;
  51. }
  52.  
  53. int seq_Search(char array[][MAXSIZE], int end, char *key)
  54.  
  55. {	
  56. 	int mid;
  57. 	int first = 0;
  58. 	int last = end;
  59.  
  60. 	while(first <= last){
  61. 		mid = (first + last) / 2;
  62.  
  63. 		if(strcasecmp(array[mid], key) < 0)
  64. 			{
  65. 				first = mid + 1;
  66. 			}
  67.  
  68. 		else if(strcasecmp(array[mid], key) > 0)
  69. 			{
  70. 				last = mid - 1;
  71. 			}
  72.  
  73. 		else 
  74. 			break;
  75.  
  76. 	}
  77. 	return mid; 
  78. }

Thank you in advance!

PS: sorry for my poor english!
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2008
Posts: 33
Reputation: SVR is an unknown quantity at this point 
Solved Threads: 4
SVR SVR is offline Offline
Light Poster
 
0
  #2
Oct 31st, 2009
Save the result of the string compare so you wont do it twice. Then just increment a counter.

C Syntax (Toggle Plain Text) 
  1.  
  2. int seq_Search(char array[][MAXSIZE], int end, char *key)
  3.  
  4. {	
  5. 	int mid;
  6. 	int first = 0;
  7. 	int last = end;
  8.         int cmp;
  9.  
  10. 	while(first <= last){
  11. 		mid = (first + last) / 2;
  12.                 cmp = strcasecmp(array[mid], key);
  13.                 g_Count++; 
  14.  
  15. 		if(cmp < 0)
  16. 			{
  17. 				first = mid + 1;
  18. 			}
  19.  
  20. 		else if(cmp) > 0)
  21. 			{
  22. 				last = mid - 1;
  23. 			}
  24.  
  25. 		else 
  26. 			break;
  27.  
  28. 	}
  29. 	return mid; 
  30. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2009
Posts: 10
Reputation: timaquerra is an unknown quantity at this point 
Solved Threads: 0
timaquerra timaquerra is offline Offline
Newbie Poster
 
0
  #3
Nov 1st, 2009
•
•
•
•
Originally Posted by SVR View Post
Save the result of the string compare so you wont do it twice. Then just increment a counter.

C Syntax (Toggle Plain Text) 
  1.  
  2. int seq_Search(char array[][MAXSIZE], int end, char *key)
  3.  
  4. {	
  5. 	int mid;
  6. 	int first = 0;
  7. 	int last = end;
  8.         int cmp;
  9.  
  10. 	while(first <= last){
  11. 		mid = (first + last) / 2;
  12.                 cmp = strcasecmp(array[mid], key);
  13.                 g_Count++; 
  14.  
  15. 		if(cmp < 0)
  16. 			{
  17. 				first = mid + 1;
  18. 			}
  19.  
  20. 		else if(cmp) > 0)
  21. 			{
  22. 				last = mid - 1;
  23. 			}
  24.  
  25. 		else 
  26. 			break;
  27.  
  28. 	}
  29. 	return mid; 
  30. }


Thank you very much for your reply, but it seems the code that you showed me didn't work for me! ((((
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C Forum
Thread Tools Search this Thread



Tag cloud for C
adobe ansi api array arrays asterisks bash binarysearch calculate centimeter char convert copyanyfile copyimagefile copypdffile cprogramme createcopyoffile csyntax directory dynamic fflush file fork frequency getlasterror givemetehcodez global graphics gtkgcurlcompiling hacking hardware highest homework i/o inches incrementoperators infiniteloop initialization interest km lazy linked linkedlist linux linuxsegmentationfault list locate logical_drives match matrix meter microsoft motherboard multi mysql number open opendocumentformat opensource owf pattern pdf performance pointer pointers posix power problem probleminc program programming pyramidusingturboccodes read recursion recv repetition scanf scheduling scripting segmentationfault send shape socketprograming spoonfeeding stack standard string strings structures suggestions systemcall test testautomation unix user variable voidmain() wab win32api windows.h
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC