Посоветуйте алгоритм разбиения строки на записи

ещё раз убеждаюсь, что С провоцирует велосипедизм. А на питоне мы делаем так: "foo bar baz test blablabla".split()

Странный вопрос. Просматриваешь строку с начала, подсчитывая попадающиеся пробелы (или группы подряд идущих пробелов, смотря что тебе надо), возможно пропуская начальные пробелы (опять же смотря что тебе надо). Запоминаешь позицию после n-1-го пробела и перед n-ным. Между ними - твоё поле.

Или я чего-то не понял?

Не просматривать всё подряд не выйдет, если только у тебя нет какой-то дополнительной информации об этой строке.

Да нет проблем и для C найти аналогичную библиотечную функцию, по-моему вопрос хитрее. :)

эт я вчера сильно уставший решал эту задачу а сегодня решил поинтересоватся как её решили другие

есть конечно ещё вариант с regex но кажется что в этой ситуации это неоптимальное решение или я не умею им пользоватся?

да кстати а regex повторяющиеся шаблоны?

в смысле не цепочку символов а именно цепочку шаблонов?

/(\S+\s+){2}(\S+)/ && print "$2\n" на перле

Но в данном случае это оверхед.

ну я так не думаю.

если эт реализуемо на regex то вполне возможно что так и сделаю.

по крайней мере это не велосипед

Ну а regex engine по-твоему что будет делать?

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

наверное я криво выразился. вариант с regex я тоже отношу к "алгоритмам". возможно потому что мало спал ;-)

regex я к либам не отношу. на сколькоя я знаю это часть glibc.

Ты и glibc к либам не относишь? :)

я имел ввиду что за собой ненужно тягать никаких левых либ

Просто когда спрашивают об алгоритме, обычно имеют в виду, как это вообще должно работать, внутри. Безотносительно glibc, языка C, доступных библитек и прочих посторонних обстоятельств. В общем слово "алгоритм" маленько другое означает.

> /(\S+\s+){2}(\S+)/ && print "$2\n" на перле
>
> Но в данном случае это оверхед.

perldoc -f split

чем не устраивают стандартные strsep/strtok ?

Причём тут perldoc, ему регвыр нужен был.

почитай маны на них и условие задачи.

на regex трудоёмкость на порядок меньше

>на regex трудоёмкость на порядок меньше

Это еще не факт. Обертка над strtok займет строчек пять и "никаких левых либ" тянуть не придется для обработки regexp

Да уж, задача-то совсем никудышная для regex.

> почитай маны на них и условие задачи.
>
> на regex трудоёмкость на порядок меньше

Вспомним условие задачи:

> тоесть есть строкак состоящая из безпробелных полей разделённых
> произвольным количеством пробелов.

Единственный regexp в этой задаче - это "произвольное количество пробелов".
IMHO в C использование для такой цели regexp'ов - ненужный геморрой
и раздувание исходного кода. Хотя конечно можно использовать как
POSIX regexp'ы так и perlre - если хочется "стоя и в гамаке". :-)))

Я бы использовал или strtok (strtok_r) или просто цикл вручную -
получится куда короче, чем в regexp'ами.

HTH

>Я бы использовал или strtok (strtok_r) или просто цикл вручную - получится куда короче, чем в regexp'ами.

предлагаю посоревноватся.

ты пытаешся реализовать на strtok или strsep а я не regex. потом сравним ;-)

PS: я тут strspn вспомнил. эт действительно может заметно склонить в сторону от regex

2cvv:
> предлагаю посоревноватся.
> ты пытаешся реализовать на strtok или strsep а я не regex.
> потом сравним ;-)

Ну почему бы и нет...
Тогда поставь задачу более конкретно:

> нада ф-я выдающая поле по его номеру.

Что это значит? Сделать strdup() этого поля? Или вернуть указатель
на начало поля в исходной строке и отдельно его длину? Или сразу
распарсить всю строку и вернуть массив из char* на все поля с их
длинами? Или допускается модификация строки (забивание туда \0
вместо пробелов) и возврат массива из char* на все поля, при этом
длины уже не нужны? Или еще как?
Короче давай прототип функции ;-)

вобщем оставить в строке только указанное поле сдвинутое в начало строки.

char * field(unsigned number, char *str){

return str; }

поля нумеруются с ЕДИНИЦЫ

Млин, ну cvv, ты даешь, может ты лучше на python или perl пересядешь? Туда, где есть стандартная
библиотека, делающая все за тебя. Это же надо развить тему в форуме по такому вопросу. Я с вас ох..ваю.

Какие регекспы? это оверхеад, давай ка использовать их там, где они действительно нужны, там, где
они дают действительно ощутимый выигрыш в скорости разработки.
Функция, нужная тебе пишется за 3 минуты, решает задачу за O(n) (на регекспах ты этого не добьешься).

Вот пример, написанный за пару минут (без проверки на переполнение):

int
get_field (const char * const str, int num, char * ptr)
{
  int len = strlen (str), state = 0, n = 0, i;

  for (i = 0; i < len; ++p, ++i)
    switch (state) {
    case 0:
      if (*p != ' ') state = ++n != num ? 1 : (*ptr++ = *p, 2);
      break;
    case 1:
      if (*p == ' ') state = 0;
    case 2:
      if (*p == ' ') {
        *ptr = 0; return 0;
      } else
        *ptr++ = *p;
    }
  return -1;
}

P.S. И стоило выносить эту тему на форум, показывая, что ты не можешь нормально решить такую задачу? Луговского на тебя нет...

sorry, гощу у родителей, залез в инет с виндовой тачки, а решение набил у себя на лэптопе, поэтому при переносе
пропустил две строки.
Нужно еще в начале
const char * p = str;
и break в конце ветки case 1.

В принципе p можно убрать, тогда получается так:
int
get_field (const char * str, int num, char * ptr)
{
  int len = strlen (str), state = 0, n = 0, i;

  for (i = 0; i < len; ++str, ++i)
    switch (state) {
    case 0:
      if (*str != ' ') state = ++n != num ? 1 : (*ptr++ = *str, 2);
      break;
    case 1:
      if (*str == ' ') state = 0;
      break;
    case 2:
      if (*str == ' ') {
        *ptr = 0; return 0;
      } else
        *ptr++ = *str;
    }
  return -1;
}

мои 5 копеек :) 
писано с руки, не отлаживалось.. 

/** get field from space-sperated string
   @arg str source string
   @arg num field index
   @arg dlen (out,optional) pointer for save field len
   @return pointer to founded field (no \0 terminated - use dlen),
*/
#define SPACES " \t\v"
char *getfield(char *str,int num,int *dlen) {
   int i;
   assert(str!=NULL);
   assert(num>=0);
   num--;
   str+=strspn(str,SPACES);
   if (!*str)
      return NULL;
   for(i=0;i<num;i++) {
      str+=strcspn(str,SPACES);
      str+=strspn(str,SPACES);
      if (!*str) {
         return NULL;
      }
   }
   if (dlen) (*dlen)=strcspn(str,SPACES);
   return str;
}

2cvv:

Ну по твоему условию:

1. Вернуть ту же строку, нужное поле сдвинуто в начало.
2. Нумерация полей с единицы.
3. Если такого поля нет, строка станет нулевой длины.

На скорую руку, без всяких strtok() получается что-то типа:

#include <string.h>
 
char* get_field(unsigned n, char* str)
{
    char *s, *e;
    for (s=e=str; *e && n; n--)
    {
        for (s=e; *s == ' '; s++);
        for (e=s; *e != ' ' && *e; e++);
    }
    
    if (n) s=e;
    memmove(str, s, e-s);
    str[e-s] = '\0';
    return str;
}

вобщем я решил задачу следующим образом:

static char*field(unsigned fld_nbr, char*str){
	if(!str)return str;

	strip_space(str);

	if(!fld_nbr)return str;

	unsigned str_len=strlen(str);
	if(!str_len) return str;

	unsigned j=0, fld_cur=1;
	char prev_char='\0';

	if(fld_cur<fld_nbr)     for(;   j<str_len;   prev_char=str[j], j++){
		if(isblank(prev_char) && !isblank(str[j])) fld_cur++;
		if(fld_cur==fld_nbr) break;
	}

	if(fld_cur<fld_nbr){*str='\0'; return str;} //Po pravilnomy zdes' nado vozvraschat NULL

	if(j){ memmove(str, str+j, str_len-j+1); str_len-=j; }

	str[strcspn(str, " \t")]='\0';

	return str;
}

Все замечания и предложения рассматриваются.

ну во первых насколько я вижу ты программы пишеш только for fun и ни в одном серьёзном проэкте не учавствовал, иначе бы знал где существует масса задач для которых твои предложения на тему перла питона и иже с ними не годятся НИКАКИМ боком.

а выдержать свою ф-ю хоть как-то соответвующей прототипу - слабо?

>чем не устраивают стандартные strsep/strtok ?

В манах их советуют не использовать:

man strsep:
>ОШИБКИ РЕАЛИЗАЦИИ
>       Эта функция подвержена тем же проблемам, что и strtok().  В  частности,
>       она модифицирует исходную строку.  Избегайте этой функции.

man strtok:
>ПРОБЛЕМЫ
>       Никогда не используйте эти функции.

P.S. Я за использование strspn()/strcspn()

>unsigned str_len=strlen(str);

strlen() возвращает тип size_t, так что лучше использовать именно его. Ну и лучше определять переменные не внутри ф-ии, а в самом начале.

> ну во первых насколько я вижу ты программы пишеш только for fun и ни в одном серьёзном проэкте не учавствовал,
> иначе бы знал где существует масса задач для которых твои предложения на тему перла питона и иже
>  с ними не годятся НИКАКИМ боком.

Нет, ну я с вас удивляюсь... И как это ты узнал, что я ни в одном серьезном проЭкте не учавствовал, из
каких моих слов ты сделал вывод, что я не знаю о "массе задач" для которых мои предложения на тему перла
и питона не годятся?

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

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

Просто поднимать вопрос в форуме по такому делу... Делать с помощью
регекспов то, что и так пишется
за пару минут... Я понимаю, что Кнута с Корменом читать не хочется, но ты ведь хочешь быть программистом,
и, наверное, хорошим? Давай-ка ты почитаешь хотя бы Шеня - отличная книга, быстро читается, большое
число примеров - она очень полезна. А то развелось кодеров, которые изучат язык, стандартную
библиотеку и идут программровать, а программировать то они и не умеют... (особенно часто замечаю
это в сообществе Java-программистов (может от того, что их особенно много?).

Не прими мои слова как какое-то назойливое поучение. Это просто дружеский совет. Это действительно
стоит того, чтобы потратить немного своего времени.

P.S. не хотел никого обидеть...

ладно расскажи о специфике решаемых тобою задач чтобы я понял откудова у тебя есть время и возможность перебирать реализациями конкретной ф-и

не совсем понятен вопрос, что такое "возможность перебирать реализациями конкретной ф-и" ???

Ок, другими словами: ты рекомендуеш занятся premature optimization.

есть авторитетное мнение что на текущем этапе написания приложения это зло.

> Давай-ка ты почитаешь хотя бы Шеня - отличная книга, быстро читается, большое

a mozno link, libo polnoe nazvanie knigi?

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

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

И вопрос в твоей манере: какими же серьезными задачами занимаешься ты, что можешь выносить такую маленькую задачу
на обсуждение в форум и ждать сутки, когда она решится, вместо того, чтобы за 10 минут сделать ее самому? По-моему
не похоже на то, что это серьезный проект с сжатыми сроками и т.д.

P.S. может перестанешь пытаться уличить меня в некомпетентности ?
P.P.S. я вполне согласен прекратить дискуссию, не имеющую отношение к первоначальному вопросу во избежание
возникновения неприятных впечатлений у оппонентов друг о друге :)

Шень. Программирование: теоремы и задачи.
http://www.mccme.ru/free-books/

По теме рекомендую 5-ю главу. Там все ну ОЧЕНЬ просто описано на примерах.

>И вопрос в твоей манере: какими же серьезными задачами занимаешься ты, что можешь выносить такую маленькую задачу на обсуждение в форум и ждать сутки, когда она решится, вместо того, чтобы за 10 минут сделать ее самому? По-моему не похоже на то, что это серьезный проект с сжатыми сроками и т.д.

просто я в тот день решил порядка сотни сильно разношерстных/разнотипных задач и когда к вечеру поднялась упомянутая мною задача мои мозги оказались не в состояниии переключится на новую тематику.

Hint: Енштейн за теоремой пифагора лазил в справочник а не выводил за 1 минуту.

Вот теперь все разъяснили. Надеюсь, конфликт исчерпан. Я действительно никого не хотел обидеть.

С уважением ко всем оппонентам,

thanks!

>  в тот день решил порядка сотни сильно разношерстных/разнотипных задач

8 часов по 60 минут на 100 задач это меньше 5 минут на каждую..
cvv : Вы монстр :)

ну я просидел часов 12 а не восемь.

тяжеловатым денёк оказался ;-)