Изменение порядка слов в строке на месте

Question

Я пытаюсь изменить порядок слов в предложении на месте, например:

В этом предложении слова поменялись местами.

становится

в обратном порядке.Это предложения слов. Это

Это то, что у меня пока есть, и это почти работает: я использую функцию strrev, чтобы перевернуть строку, а затем функцию inprev, чтобы отправить каждое слово в функцию strrev по отдельности,повернуть их обратно к исходной ориентации, но в обратном порядке.Отправка указателя на начало и конец функции strrev может показаться немного глупой, но она позволяет использовать ту же функцию в inprev (), отправляя указатель на начало и конец отдельных слов.

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

void strrev(char * start, char * end);
void inprev(char * start);

int main(void)
{
   char str[] = "Foobar my friends, foobar";
   char * end = (str + strlen(str) -1);
   puts(str);
   strrev(str, end);
   puts(str);
   inprev(str);

   puts(str);

   return 0;
}

void strrev(char * start, char * end)
{
   char temp;

while (end > start)
   {
     temp = *start;
     *start = *end;
     *end = temp;
      start++;
      end--;
   }
}

void inprev(char * start)
{
     char * first = start;
     char * spcpnt = start;
     while (*spcpnt)
     {
        while (*spcpnt != ' ' && *spcpnt)
           spcpnt++;
        strrev(start, spcpnt-1);         // removing the -1 sends the space on the 
        start = spcpnt++;                // other side to be reversed, doesn't stop 
                                         // the problem.  

     }

}

Вот вывод:

Foobar мои друзья, foobar

raboof, sdneirf ym rabooF

foobarfriends, мой Foobar

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

Answer 1

Вам просто нужно переместить указатель start в функции inprev, чтобы пропустить пробел между словами.Поскольку это, кажется, домашнее задание (поправьте меня, если я ошибаюсь), я просто скажу, что все, что вам нужно сделать, это переместить местоположение одного оператора.

Но это создает проблему, а именно,inprev выполняет переполнение буфера, потому что поиск не завершен должным образом.Лучший способ сделать это:

while not end of string
  search for start of word
  start = start of word
  search for end of word
  strrev (start, end)

, и это также позаботится о нескольких пробелах.Кроме того, U + 0020 (ASCII 32, пробел) - не единственный символ пробела.Существуют стандартные библиотечные функции, которые проверяют символы.Они ви начните с is..., например isspace.

Answer 2

Иногда все становится проще, если вы используете не указатели, а смещения. Функции библиотеки strspn () и strcspn () более или менее заставляют вас использовать смещения, и очень хорошо справляется с условием конца строки.

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

size_t revword(char *str);
void revmem(void *ptr, size_t len);

size_t revword(char *str) {
size_t pos,len;

for (pos=len=0; str[pos]; pos += len) {
        len = strspn( str+pos, " \t\n\r");
        if (len) continue;
        len = strcspn( str+pos, " \t\n\r");
        if (!len) continue;
        revmem( str+pos, len );
        }
revmem( str, pos );
return len;
}

void revmem(void *ptr, size_t len)
{
size_t idx;
char *str = (char*) ptr;

if (len-- < 2) return;

for (idx = 0; idx < len; idx++,len--) {
        char tmp = str[idx];
        str[idx] = str[len];
        str[len] = tmp;
        }
}

int main (int argc, char **argv)
{

if (!argv[1]) return 0;
revword(argv[1] );
printf("'%s'\n", argv[1] );

return 0;
}                                                                                           

Answer 3

void reverse_str(char* const p, int i, int j) // helper to reverse string p from index i to j
{
    char t;
    for(; i < j ; i++, j--)
        t=p[i], p[i]=p[j], p[j]=t;
}

void reverse_word_order(char* const p) // reverse order of words in string p
{
    int i, j, len = strlen(p);  // use i, j for start, end indices of each word

    reverse_str(p, 0, len-1);      // first reverse the whole string p
    for(i = j = 0; i < len; i = j) // now reverse chars in each word of string p
    {
        for(; p[i] && isspace(p[i]);) // advance i to word begin
            i++;
        for(j = i; p[j] && !isspace(p[j]);) // advance j to past word end
            j++;
        reverse_str(p, i, j-1);  // reverse chars in word between i, j-1
    }
}

Answer 4

Следующий алгоритм работает и выполняется в 2 этапа.Сначала он переворачивает всю строку.Затем оно переворачивает каждое слово.

#include <stdio.h>

void reverse(char *str, int len)
{
    char *p = str;
    char *e = str + len - 1;

    while (p != e) {
        *p ^= *e ^= *p ^= *e;
        p++;
        e--;
    }
}

void reverse_words(char *str)
{
    char *p;

    // First, reverse the entire string
    reverse(str, strlen(str));

    // Then, reverse each word
    p = str;
    while (*p) {
        char *e = p;
        while (*e != ' ' && *e != '\0') {
            e++;
        }

        reverse(p, e - p);
        printf("%.*s%c", e - p, p, *e);

        if (*e == '\0')
            break;
        else
            p = e + 1;
    }
}

int main(void) {
    char buf[] = "Bob likes Alice";
    reverse_words(buf);
    return 0;
}

Answer 5

разобрался с решением; вот моя исправленная функция, которая работает должным образом.

void inprev(char * str)
{
    _Bool inword = 0;
    char * wordend;
    char * wordstart;

     while(*str)
     {
         if(!isspace(*str) && (inword == 0))
         {
             wordstart = str;
             inword = 1;
         }
         else if (isspace(*str) && (inword == 1))
         {
             wordend = str-1;
             inword = 0;
             strrev(wordstart, wordend);
         }

         str++;
     }

     if (*str == '\0')
        strrev(wordstart, str-1);

}

char * wordend не нужен, так как вы можете просто передать str-1 в функцию strrev, но это делает его немного более понятным.