Линейный поиск в массиве символов - C ++ (Visual Studio 2005) - PullRequest
Новая
       12

Линейный поиск в массиве символов - C ++ (Visual Studio 2005)

1 голос
/ 25 мая 2009

Я очень новичок в программировании на C ++, и вы поймете, почему.

Я хочу создать массив символов, состоящий из нескольких слов, которые я хочу найти, с помощью функции линейного поиска. Должен ли этот массив быть двумерным? Например: 

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

Я попробовал это так: 

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

Это дало мне ошибку "слишком много инициализаторов".

Я предполагаю, что 1-й метод является правильным, потому что он устанавливает количество элементов в массиве и максимальную длину элемента, верно?

Теперь, как мне реализовать функцию линейного поиска, чтобы найти слово внутри этого массива? Могу ли я сделать что-то вроде следующего:

(при условии, что функция linearSearch уже была объявлена) 

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");  
}

Возможно ли это? Если так, что объявление будет искать для функции linearSearch? Я надеюсь, что предоставил достаточно информации, чтобы это можно было использовать.

edit: Спасибо всем за помощь, программа заработала как положено.

Ответы [ 6 ]

9 голосов
/ 25 мая 2009

Я бы порекомендовал узнать о стандартной библиотеке C ++, которая очень вам поможет. Например, 

#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";

Зачем реализовывать linearSearch самостоятельно? C ++ уже имеет std::find, который делает это за вас! Более того, если вы используете set вместо vector, теперь вы можете использовать std::binary_search, то есть O (log n) вместо O (n), поскольку набор отсортирован.

3 голосов
/ 25 мая 2009

Чтобы объявить массив строк, используйте этот синтаксис 

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

Это массив указателей на символы («Привет» означает const char *, указывающий на «H»). Компилятор выяснит, сколько элементов необходимо для хранения вашего массива (отсюда и []), в этом случае он всегда будет иметь размер 3.

В целом, я согласен с ответом rlbond - вы должны использовать STL.

2 голосов
/ 25 мая 2009

Нет, вам не нужен двумерный массив.

Вот способ объявить строковые массивы: 

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

или 

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

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

Сразу после экспериментов с C ++ вы должны научиться использовать STL.

2 голосов
/ 25 мая 2009

Вы могли бы сделать вашу функцию linearSearch возвращающей индекс поискового термина в массиве. Вот пример программы: 

#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;
}

Мы используем функцию strcmp () для сравнения строк. Возвращает ноль, если строки совпадают, и ненулевое, если они не совпадают. Чтобы использовать его, вам нужно включить заголовок string.h.

Но, как предлагали другие, вы должны использовать STL, если можете.

0 голосов
/ 25 мая 2009

Если вы не хотите использовать строки и использовать массивы символов, вы можете использовать strcmp для сравнения 2 слов. Что следует помнить с помощью strcmp , так это то, что он возвращает индекс того, где слово было найдено, поэтому, если вы хотите только найти слова в начале, вы делаете это так: 

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

В зависимости от того, что вы делаете, и от того, насколько большим будет ваш массив, вам следует рассмотреть возможность использования хешей строк для увеличения производительности.

0 голосов
/ 25 мая 2009

Эта статья содержит функцию поиска строки. Он также должен дать вам представление о том, как правильно структурировать массивы персонажей.

...