поиск символа в строке языка C

Question

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

Примечание: attrPtr - это char *, который содержит ссылку на строку, содержащую символ '"' на большом расстоянии.

int position = 0;

char qolon = '"';//character to search

while (*(attrPtr + position++) != qolon);

char* attrValue = NULL;

attrValue = (char*)malloc(position * sizeof(char));

strncpy(attrValue, attrPtr, position-1);

Answer 1

strchr обычно будет несколько быстрее. Также вам нужно проверить терминатор NUL, который strchr будет обрабатывать для вас.

char *quotPtr = strchr(attrPtr, qolon);
if(quotPtr == NULL)
{
  ... // Handle error
}
int position = quotPtr - attrPtr;
char* attrValue = (char*) malloc((position + 1) * sizeof(char));
memcpy(attrValue, attrPtr, position);
attrValue[position] = '\0';

Я еще не проверял.

РЕДАКТИРОВАТЬ: Fix off-by-one.

Answer 2

C имеет встроенную функцию поиска символа в строке - strchr(). strchr() возвращает указатель на найденный символ, а не позицию массива, поэтому для его получения вы должны вычесть указатель на начало строки из возвращенного указателя. Вы можете переписать вашу функцию как:

char qolon = '"';//character to search
char *found;
char *attrVal = NULL;

found = strchr(attrPtr, qolon);

if (found)
{
    size_t len = found - attrPtr;

    attrVal = malloc(len + 1);
    memcpy(attrVal, attrPtr, len);
    attrVal[len] = '\0';
}

Это может быть быстрее, чем ваш оригинал, с небольшим постоянным коэффициентом; однако вы не получите ускорение на порядок. Поиск символа в неупорядоченной строке в основном равен O (n) по длине строки.

Answer 3

Две важные вещи:

1) Всегда проверяйте NULL-терминатор при поиске строки следующим образом:

while (*(attrPtr + position++) != qolon);

должно быть:

while (attrPtr[position] && attrPtr[position++] != qolon);

(если передать строку без искомого символа, это может занять очень много времени, так как она сканирует всю память). Редактировать: Я только что заметил, что кто-то еще опубликовал это раньше, я, ну да ладно. Я не согласен, кстати, strchr () - это хорошо, но простой цикл, который также проверяет терминатор, тоже подойдет (и часто имеет преимущества).

2) ВНИМАНИЕ от strncpy ()!

strncpy(attrValue, attrPtr, position-1);

strlen (attrPtr)> = (position-1), поэтому NOT завершает строку null в attrValue, что может вызвать всевозможные проблемы (включая невероятное замедление в коде позже). Как примечание, strncpy () является уникальным разработчиком, поэтому если вы делаете что-то вроде:

char buf[512];
strncpy(buf,"",4096);

Вы будете писать 4096 байтов нулей.

Лично я использую lstrcpyn () на Win32, и на других платформах у меня есть простая реализация этого. Это гораздо полезнее для меня.

Answer 4

Алгоритм, который вы опубликовали, неправильно обрабатывает случай, когда символ не существует в строке. Если это произойдет, он будет просто перемещаться по памяти, пока случайно не найдет байт, соответствующий вашему символу, или вы пролетите мимо выделенной памяти и получите ошибку сегмента. Я подозреваю, поэтому иногда кажется, что это «слишком долго».

В C строки обычно заканчиваются на 0 (ascii nul или '\0'). В качестве альтернативы, если вы заранее знаете длину строки, вы можете использовать ее.

Конечно, есть стандартная подпрограмма библиотеки C, которая делает именно это: strchr(). Мудрый программист использует это, а не рискует ошибками, выпуская свои собственные.

Answer 5

Требуется алгоритм O(n) для поиска символа в строке. Таким образом, вы не можете сделать намного лучше, чем то, что вы уже делаете. Также обратите внимание, что вам не хватает memset(attrValue, 0, position);, иначе ваша строка attrValue не будет иметь нулевого завершения.