Creating a function

[Henry Dominik]

Hello guys,

I am new to C/C++ and I have a problem in one of the materials am using to learn C. It has a problem that am trying to solve in C, and am really finding it hard to solve.

But I did not find it hard to do in Java, but when it comes to C, I just got lost.
Below is the question and the solution I have written in Java. So, I was woundering if anyone could show me how to do it in C so that I can progress to other topics.

---

Write a function, arraysearch, that searches through a sorted array of C strings for a specified string, using the following function definition:

int arraysearch(char ** array, int arraySize, char * searchString);
The function should return the 1-based index of the matching element in the array, or the value 0 if the search string cannot be found.

---

The following is the solution I came up with in Java and it works.
------------Java------------------
public int arraySearch(String[] array, String searchValue){
int index = 0;

     if(array.length < 0 | array.length == 0){
         throw new ArrayIndexOutOfBoundsException();
     }
      else{
         Arrays.sort(array);
      }
      index = Arrays.binarySearch(array, searchValue );
      return index; 
  }

---------------End Java------------------
Any helps at all is greatly appreciated :-)

Thanks guys

[Nobody/Anonymous]

/ example bubble sort (of pointers) ... then binary search /

include <stdio.h>

include <stdlib.h>

include <string.h>

define MAX 8

/ ** function prototypes * */

void sortArray( char p, int arraySize );
void printArray( char p, int arraySize );
int searchArray(char **p, int arraySize, char searchStr[]);

int main(void)
{
char names[][MAX] = { "zeta", "gamma", "alpha", "delta", "beta" };
int N=sizeof(names)/sizeof(names[0]);
char ** p = (char) malloc( Nsizeof(char) );
int i;
for( i=0; i<N; ++i )
p[i] = names[i];

printArray(p, N);
puts("");
sortArray(p, N);
printArray(p, N);

puts("");  
for( i=0; i<N; ++i )
     printf("\n%7s now in position %2d", names[i], searchArray(p, N, names[i]) );

puts("");   
for( i=0; i<N; ++i )
     printf("\n%7s now in position %2d", p[i], searchArray(p, N, p[i]) );

puts("");   
printf("\n%7s is in position %2d", "xxxx", searchArray(p, N, "xxxx") );

printf("\n\nPress 'Enter' to exit ... ");
getchar();
return 0;

}

/ ** function definitions * */

void sortArray( char p, int arraySize )
{
int i, j, compare;
char temp;
for(i=0; i<arraySize-1; ++i)
for(j=0; j<arraySize-1-i; ++j )
{
compare = strcmp( p[j], p[j+1] );
if( compare > 0 )
{
temp = (p+j);
(p+j) = (p+j+1);
*(p+j+1) = temp;
}
}
}

int searchArray(char p, int arraySize, char searchStr[])
{
int low = 0,
mid,
high = arraySize-1;
while(low < high)
{
mid = (low + high)/2;
if( strcmp( p[mid], searchStr ) < 0 )
low = mid+1;
else
high = mid; / can't be high = mid-1; here A[mid] >= value,
so high can't be < mid if A[mid] == value /
}
if( (low < arraySize) && (strcmp( p[low], searchStr) == 0) )
return low+1; / +1 to give one_based_index /
else
return 0; / i.e. NOT in array /
}

void printArray( char **p, int arraySize )
{
int i;
for(i=0; i<arraySize; ++i)
printf( "%s ", p[i] );
}

[Henry Dominik]

sorry, I forgot to show you guys what I was trying to do.
The code below is what I was writing.

---

include <stdio.h>

#include <string.h>

main()
{
char names[3] = {"Jam","dough","nut","yummy"};
int answer = arraysearch(names, 3, "nut");
printf(answer);
system("pause");

return 0;

}
int arraySearch(char[] *array, int arraySize, char searchString)
{
//here is where am lost totally :(((
}

[Anonymous]

If you already know Java, C++ would be a more obvious language to learn.

To do the sorting, take a look at the qsort() function from stdlib.h and strcmp() from string.h - but the question does not require you to sort - you seem to have invented that requirement in your Java version. The question implies that the array is already sorted. I suggest that arraysort() should be a separate function that you call before searcharray()

The question gives arraysearch() requires array to have type char but you have declared the it as char[] array - which is not the same thing.

In main() you have declared a 3 byte char array and tried to initialise it with 4 strings! Bothe teh number of elements and their type is incorrect. You then pass 3 instead of 4 to arraysearch(). Which is it; three or four? It should be:

char names[][32] = {"Jam","dough","nut","yummy"};

The second subsript [32] is an arbitrarily large array - no string element may have more than 32 characters. The first subscript[] is implied by teh number of initialisers, but begs the question of what you pass as arraySize - you may wish to use an explicit value (or better a macro); the compiler will then tell you if you provide too many initialisers (bit not too few).

The standard C library does not provide extensive standard algorithms like Java (other than qsort() ). Another reason why C++ would be a more natural language for you (because it does). In C you will need to program this yourself from first principles - which is probably the point of the exercise - to understand pointers and arrays. Presumably because the array is said to be sorted a binary search is intended, but a start-to-end search is not precluded by teh question you posted - not a very interesting exercise though!

array is a pointer to an array of strings containing arraySize elements.

Also...

1) You should get into the habit of explicitly declaring main as returning int - otherwise your code will not be protable to C++ without modification.
2) You will need a prototype declaration of arraysearch() before main() - alternatively define arraysearch() before main(). The first of these is more usual.

Clifford

[Henry Dominik]

wow,

Thanks Clifford for your feedback, it was great.

However,I have never writen any C programs before that's why am having a bit of a hard time understanding pointers and arrays in C.

In the sample code I provided, I added the last object yummy after I finished writing that code, and yes you were right, that should be three elements in the array (char names[3] = {"Jam","dough","nut"}) without the 'yummy'.

Again, am suppose to write the function/method in C and not C++. Either way, am still very lost and I don't want to give in so easily, grrrr :-((
I must crack on, this is the first hurdle so far and it seems like a big mountain.

Dominik

[Anonymous]

OK, to kick start you:

The body of arraysearch() would be something like:

---

int compare ;
int index = arraySize / 2;
int skip = index ;
int one_based_index = 0 ;

do
{
compare = strcmp( array[index], searchString) ;
skip /= 2 ;
if( compare == 0 )
{
one_based_index = index + 1 ;
break ;
}
else if( compare < 0 )
{
index = index + skip ;
}
else
{
index = index - skip ;
}
} while( skip != 0 ) ;

return one_based_index ;

Note that this is intended as a suggestion, I typed it directly into the forum, have not tested it or checked it, it probably contains errors - I leave that as an exercise for the reader! ;-)

Clifford

[Henry Dominik]

Thanks Clifford,

You have done a great deal of job :-))). In fact, I did not change your code and it basically 'ran out of the box'. Thanks once again.

My question is, if the arraySize is not an even number, then we could not divide it by two. Is there any way we could write it so that they arraySize will be flexible no matter what type of integer is supplied as long as its an integer for the size of the array?

Here is the complete code:

#include <stdio.h>
#include <string.h>
#define NUM 3
// int arraysearch(char, int, char);
int main(void)
{
char names[5][32] = {"five","four","one","three","two"};
int answer = arraysearch(names, 5, "five");
printf("%d\n",answer);
system("pause");

 return 0;

}
int arraysearch(char ** array, int arraySize, char* searchString)
{

   int compare ;
   int index = arraySize / 2;
   int skip = index ;
   int one_based_index = 0 ;

   do
   {
      //qsort(array);// I want to sort the elements in array before searching.
      compare = strcmp( array[index], searchString) ;
      skip /= 2 ;
  if( compare == 0 )
   {
     one_based_index = index + 1 ;
     break ;
   }
   else if( compare < 0 )
   {
   index = index + skip ;
   }
  else
  {
  index = index - skip ;
  }
  } while( skip != 0 ) ;

 return one_based_index ;

}

---

The code gives me '0' when I try to search for the location of 'five'. But it gives me '2' when I search for 4.

Is there anyway I can sort it out?
Again, thank alot for your code so far. I couldn't have written it my self, I must confess.

Regards,

Dominik.

[Anonymous]

Yea, it was a poor algorithm. My suggestion is not to reinvent the wheel and use existing expertise: http://en.wikipedia.org/wiki/Binary_search#The_algorithm

Clifford

[Henry Dominik]

Thanks Clifford,

You have been superd. I followed the suggested link and I was able to achieve what I wanted.
However, is there a way of making elements in array unique? What I mean is, I don't want to have duplicate elements: e.g char *names[6][32] = {"five","four","two","one","three","two"};

From the code above, there are 2 twos and that is not good.
Any more helps is highly appreciated.

Thanks,

Dominik

[Anonymous]

What you are looking for is a C++ STL <set> container. As I said before the C standard library provides none of the sophisticated functionality of Java or C++, it is a lower level language, you'll need to grow your own.

If you have previously sorted the array (which arraysearch() requires) finding and removing duplicates is straightforward because the duplicates will be adjacent. Of course the fact that they are adjacent may mean that they don't actually matter in terms of the arraysearch() result.

I can think of three ways to remove the duplicates from a sorted array:

1) Iterate through the array and use memmove() when you find a duplicate to move the remainder of the array to the current location - this can be very inefficient in terms of time, and is non-deterministic (i.e. it may be quick it may be slow, it depends on the number of duplicates and where they are in the array)

2) Iterate through the array, copying each string to a new array, skipping duplicates along the way. This is more deterministic, more duplicates makes it faster rather than slower, the worst case is that there are no duplicates and all the strings are copied.

3) Iterate the array, and add a pointer to each string to an array of pointers, skipping the duplicates. This is fastest since only pointers are set and no data is moved. It is again deterministic, with worst case when there are no duplicates exist. It is also fairly memory efficient if teh strings are generally longer than three bytes.

If you choose to use (2) use memcpy() rather than strcpy() if the strings mostly of similar length, and just copy the whole allocated space rather than just the string data - strcpy() may mean moving less data, but it first has to determine the string length, and this is a real performance killer - C strings are generally poor, see http://www.joelonsoftware.com/articles/fog0000000319.html).

Clifford

[Nobody/Anonymous]

"you'll need to grow your own"

O_o

"However, is there a way of making elements in array unique?"

Nah, I don't think he is nearly skilled enough to implement a balanced tree.

Soma

[Henry Dominik]

Clifford,

Thanks once more for your time and effort you've put into helping to learn and understand what one language provides over another.

Here's my story:
The problem started during my university days where we were never exposed to any language other than Java. Believe me, it has made life really difficult for me both at home and at work. I tend to look at every problem from Java's point of view. Whenever I see a problem that needs solving, the next thing that comes to my mind is to use Java. I must confess, its the only language that I know very well (beside other Java-based frameworks and XML) and I've been using it since 2000.

Now, the reason why am learning C is because I will be starting with a new company in September and they work mainly with C and a few in Java. And for that reason, I went to a bookshop and got myself a book on C and try to work my way through before september.

I have found some of the topics fairly easy to follow as am learning to 'unlearn' everything i knew before. The only major topic that am currently finding hard is the array and pointer topics. They're doing my head in :-).

I've always envied C/C++ programmer and I think you guys are the real developers.

Love you all.

Dominik

[Nobody/Anonymous]

You might want to also work through this free/quick online course by Bruce Eckel:

http://mindview.net/CDs/ThinkingInC/beta3

[Nobody/Anonymous]

Aqui te mando una nueva version.

Espero te sirva.

include <stdio.h>

include <string.h>

int arraySearch(char array[], int arraySize, char searchString);

int main()
{
char *names[4] = {"Jam","dough","nut","yummy"};
int answer = arraySearch(names, 4, "nut");
printf("%i", answer);
printf("press any key");
getchar();
return 0;
}

int arraySearch(char array[], int arraySize, char searchString)
{
int c = 0;
for (c = 0; c<arraySize; c++)
{
if ( strcmp(array, searchString) == 0)
{
printf("%s %i %s\n", array, c, searchString);
return c;
}
array ++;
}
return -1;
}

[Anonymous]

That solution does not make use of the fact that the array is sorted to optimise the search - which is I think the point of the exercise.