2 Replies - 2155 Views - Last Post: 12 April 2012 - 04:14 AM Rate Topic: -----

#1 menace12  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-April 12

Create Function for an Array Binary Search

Posted 11 April 2012 - 05:47 PM

Hi

My task is to input a dictionary text file and store it within an array. I have successfully created this piece of code below:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define Dsize 80368
 
typedef char* string;
 
int dict2array(){
int i;
string Dictionary[Dsize]; // dictionary array
string word="xxxxxxxxxx"; // individual word

FILE *fptr; 
fptr=fopen("dictionary.txt","r");
	if(fptr==NULL)
	{
	printf("cant open dictionary.txt\n");
	}
		for(i=0;i<Dsize;i++) 
    { 
	fscanf(fptr,"%s", word);
Dictionary[i]=malloc((strlen(word)+1)); // make space for word
Dictionary[i]=word; // add word to dictionary array element
printf("Dictionary [%d] = %s\n", i,Dictionary[i]);
	}
fclose(fptr);
return 0;
}


This code however needs to be a function to a main program. My next step is to create a binary search function which searches the already sorted array created above for a specific word typed in by the user. This is where i'm struggling....below is my binary function code:

 {
 int position;
 int begin = 0; 
 int end = max - 1;
 int cond = 0;

 while(begin <= end) {
  position = (begin + end) / 2;
  if((cond = strcmp(Dictionary[position], value)) == 0)
   return position;
  else if(cond < 0)
   begin = position + 1;
  else
   end = position - 1;
 }

 return 0;
}




So my questions are:
1. How do I separate these two pieces of code into two different functions, and then integrate them together in one main program?
2. How can I use the binary search function on the array created in my first function? (In other words how can I access it to allow the binary search function use it?)

After I have successfully got past this stage, i'm required to input another textfile within the main program with spelling mistakes etc, and eventually use the binary search function to compare the two lists.

In other words the end program is required to be a fully working spell checker.

Any help/tips would be much appreciated.

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Create Function for an Array Binary Search

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4278
  • View blog
  • Posts: 13,439
  • Joined: 25-December 09

Re: Create Function for an Array Binary Search

Posted 11 April 2012 - 07:43 PM

You may want to study the links provided in my signature. They should help you better understand how to create and use functions.

Jim
Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5932
  • View blog
  • Posts: 12,855
  • Joined: 16-October 07

Re: Create Function for an Array Binary Search

Posted 12 April 2012 - 04:14 AM

View Postmenace12, on 11 April 2012 - 07:47 PM, said:

I have successfully created this piece of code below:


Have you successfully run it?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define Dsize 80368

// OMG! No! 
// typedef char* string;
 
 
int dict2array(){
	int i;
	char *Dictionary[Dsize];
	char *word="xxxxxxxxxx"; // ok...

	FILE *fptr; 
	fptr=fopen("dictionary.txt","r");
	if(fptr==NULL) {
		printf("cant open dictionary.txt\n");
		// strangely, you don't actually leave here
	}
	
	for(i=0;i<Dsize;i++) {
		// does this even work?
		// it really shouldn't.
		// word, as you've defined it
		// is a pointer to a constant
		// not storage
		fscanf(fptr,"%s", word);
		
		// fine, if word wasn't questionable
		Dictionary[i] = malloc((strlen(word)+1));

		// MEMORY LEAK!!
		// You just lost your malloc and are pointing to an invalid value
		Dictionary[i]=word;
		// you're fooling yourself here
		printf("Dictionary [%d] = %s\n", i,Dictionary[i]);
	}
	fclose(fptr);
	return 0; // is there a point to this return
}



Assuming Dictionary is loaded properly, how do you read it? Your function doesn't pass anything out.

That Dsize is pretty big, btw. Wouldn't you like a nice linked list? Is your dictionary always going to have exactly Dsize values? If not, how many did you read? Where do you check for end of file? Use struct.

I would go with something like:
#define DICT_CAPACITY 80368
#define MAX_WORD 20

typedef struct {
	char *items[DICT_CAPACITY];
	int size;
} Dictionary;

void loadDict(const char *filename, Dictionary *);

void showDict(Dictionary *dict) {
	int i;
	for(i=0;i<dict->size;i++) {
		printf("Dictionary[%d] = %s\n", i, dict->items[i]);
	}
}



If you cannot loop through the values in your array after you've loaded it, then you haven't really loaded it.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1