Linear Search in a Char Array -- C++ (Visual Studio 2005)

Question

I am very new to C++ programming and you will see why.

I want to make a character array consisting of a few words that I want to search with a linear search function. Does this array have to be a two-dimensional array? For example:

char Colors[3][6] = {"red", "green", "blue"};

I tried it like this:

char Colors[] = {"red", "green", "blue"};

This gave me a "too many initializers" error.

I assume the 1st method is correct because it states the amount of elements in the array and the maximum length of an element, correct?

Now how would I implement a linear search function to find a word inside that array? Can I do something like the following:

(Assuming the linearSearch function has already been declared)

char searchKey;  
char element;

char Colors[3][6] = {"red", "green", "blue"};

printf("Enter the color to look for: \n");

scanf("%s", searchKey);

element = linearSearch(Colors, searchKey, ??); //?? is where I don't know what to enter

if (element != -1)  
{  
    printf("Found the word.\n");  
}  
else  
{  
    printf("Didn't find the word.\n");  
}

Is this possible? If so, what would the declaration look for the linearSearch function? I hope I provided enough information for this to be somewhat usable.

edit: Thanks all for the help, got the program working as intended.

Answer 1

This article contains a string search function. It should also give you insight into how to properly structure your character arrays.

Answer 2

I would recommend to learn about the C++ standard library, which would help you very much. For example,

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

vector<string> words;
words.push_back("red");
words.push_back("blue");
words.push_back("green");

if (find(words.begin(), words.end(), "green") != words.end())
    cout << "found green!"
else
    cout << "didn't find it";

Why implement linearSearch yourself? c++ already has std::find which does it for you! Moreover, if you use a set instead of a vector, you can now use std::binary_search which is O(log n) instead of O(n), since a set is sorted.

Answer 3

You could make your linearSearch function to return the index of the search term in the array. Here is a sample program:

#include <stdio.h>
#include <string.h>

int linearSearch (const char **Array, const char *searchKey, int arraySize) {
    for (int i = 0; i < arraySize; ++i) {
        if (strcmp(Array[i], searchKey) == 0)
            return i;
    }

    // We didn't find the searchKey in the Array
    return -1;
}

int main () {
    char *colors[] = { "red", "green", "blue" };

    int index = linearSearch (colors, "green", 3);

    if (index < 0) { // search string was not found
        printf("Search string not found!\n");
    }
    else {
        printf("String %s found at index %d\n", colors[index], index);
    }

    return 0;
}

We use the strcmp() function to compare the strings. It returns zero if strings match and nonzero if they don't. To use it, you need to include the string.h header.

But, as others have suggested, you should use STL if you can.

Answer 4

If you dont want to use strings, and stay with char arrays you can use strcmp to compare 2 words. The thing to remember with strcmp is that it returns the index of where the word was found, so you if you want only to find words in the begining you do it like this:

for(int i=0;i<SizeOfColorArray;i++)
{
    if(strcmp (MySearchTerm,colors[i]) == 0)
    {
        // it was  a match
        return i;
    }
}

Depending on what you are doing and how big your array is going to get, you should consider looking into having hashes of the strings to increase preformance.

Answer 5

To declare an array of strings, use this syntax

 char *Colors[] = {"red", "green", "blue"};

This is an array of pointers to characters ("Hi" evaluates to a const char* pointing at the 'H'). The compiler will figure out how many elements are needed to store your array (hence the []) in this case it will always be of size 3.

Overall, I agree with rlbond's answer - you should use the STL.

Answer 6

No, you don't need a two-dimensional array.

Here is a way to declare string arrays:

char* Colors[3] = {"red", "green", "blue"};

or

char* Colors[] = {"red", "green", "blue"}; // the compiler will figure out the size

int colors = sizeof(Colors)/sizeof(Colors[0]);

Right after experimenting with C++ you should learn to use STL.