Сортировка слов в алфавитном порядке C

Question

Итак, мое упражнение состоит в сортировке слов в массиве 1D. Мой код почти работает, но он всегда пропускает последний символ последнего слова. Вот мой код. Я добавил несколько комментариев, чтобы сделать его читабельным. Я знаю, что это не блестящий код, но я только начал программировать.

int main(void) {
    char input[] = "If you are working on something that you really care about you dont have to be pushed The vision pulls you Steve Jobs";
    sort_alphabetically(input);
    printf("%s", input);
}

int sort_alphabetically(char tab[]) {
    int j = 0, k = 0, i = 0, g = 0, f = 0, l = 0;
    char tmp[1001];
    char tmp2[501][1001];

    while (tab[i] == ' ')  // skipping leading whitespaces
        i++;

    for (j = i; tab[j] != '\0'; j++) {
        if (tab[j] != ' ' && tab[j + 1] != '\0')
            k++;             // counting word length
        else if (tab[j] == ' ' || tab[j + 1] == '\0' || tab[j + 1] == '\0') {
            // copying word t0 2d array
            for (g = k; g > 0; g--) {
                tmp[l] = tab[j - g];
                l++;
            }
            tmp[l] = 0;
            strcpy(tmp2[f], tmp);  // copying
            f++;  //words ++ in  tmp2
            k = 0;  
            l = 0;  
            tmp[0] = 0;  
        }
    }
    tab[0] = 0;
    tmp[0] = 0;

    for (j = 0; j < f; j++) {    
       for (i = 0; i < f - 1; i++) {
           if (strcmp(tmp2[i], tmp2[i + 1]) > 0) {  //sorting words in alphabeticall order
               strcpy(tmp, tmp2[i]);   
               strcpy(tmp2[i], tmp2[i + 1]);   
               strcpy(tmp2[i + 1], tmp);
           }
       }
    }   

    for (i = 0; i < f; i++) {
        strcat(tab, tmp2[i]);    // copying to tab 
        strcat(tab, " ");   //adding spaces after each word
    }
    // removing whitespaces
    for (i = 0; tab[i] == ' ' || tab[i] == '\t'; i++);

    for (j = 0; tab[i]; i++) {
        tab[j++] = tab[i];
    }
    tab[j] = '\0';
}
;

После запуска этого кода он сокращает s в последнем слове (Jobs). Если бы кто-то мог помочь мне с этими спагетти, я был бы так счастлив.

Answer 1

Проблема была в том, как вы обрабатывали нулевой байт в сравнении с пробелом. В случае с пробелом вы фактически были на пробелом, когда копировали строку. Но в случае нулевого байта вы были один перед нулевым байтом. Это приводит к ошибке «один за другим». Вам нужно изменить код, чтобы избежать его обработки по-разному для пробелов и нулевых байтов:

for (j = i; tab[j] != '\0'; j++) {
    //In the space case, you are on the space, but in the \0 case
    //you were one before it.
    //Changed this if statement so that you always copy the string
    //when you're at the last character.
    if (tab[j + 1] == ' ' || tab[j + 1] == '\0') {

        //k is a length, but we're using it as an index
        //so we will need to adjust by one
        for (g = k; g > 0; g--) {
            tmp[l] = tab[j - g + 1];
            l++;
        }
    }
    else
    {
       k++;
    }
}

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

Answer 2

Предостережение: Большинство других респондентов указали на основные ошибки в вашем коде, но здесь есть некоторые более мелкие и некоторые упрощения.

Перед выполнением strcat назад к tab, мы должны сделать tab[0] = 0, чтобы начальная 1009 * strcat работала правильно.

Выполнение strcat(tab," ") после того, что копирует слово, выходит за пределы конец tab и, следовательно, неопределенное поведение. Также требуется ненужная очистка l oop для удаления лишнего пробела, которого не должно было быть в первую очередь.

Первоначальный «разбитый на слова» l oop можно [значительно] упростить.

Существуют некоторые стандартные ускорения для сортировки пузырьков

Я понимаю, что вы только начинаете [и некоторые школы действительно выступают за i, j и т. Д.], Но это лучше использовать несколько [более] различительных имен

В любом случае, вот несколько измененная версия:

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

int opt_dbg;

#define dbg(_fmt...) \
    if (opt_dbg) \
        printf(_fmt)

void
sort_alphabetically(char tab[])
{
    char tmp[1001];
    char words[501][1001];
    char *src;
    char *dst;
    char *beg;
    int chr;
    int wordidx;
    int wordcnt;

    wordidx = 0;
    dst = words[wordidx];
    beg = dst;

    // split up string into individual words
    src = tab;
    for (chr = *src++;  chr != 0;  chr = *src++) {
        switch (chr) {
        case ' ':
        case '\t':
            // wait until we've seen a non-white char before we start a new
            // word
            if (dst <= beg)
                break;

            // finish prior word
            *dst = 0;

            // point to start of next word
            dst = words[++wordidx];
            beg = dst;
            break;

        default:
            *dst++ = chr;
            break;
        }
    }

    // finish last word
    *dst = 0;

    // get number of words
    wordcnt = wordidx + 1;

    if (opt_dbg) {
        for (wordidx = 0; wordidx < wordcnt; ++wordidx)
            dbg("SPLIT: '%s'\n",words[wordidx]);
    }

    // in bubble sort, after a given pass, the _last_ element is guaranteed to
    // be the largest, so we don't need to examine it again
    for (int passlim = wordcnt - 1;  passlim >= 1;  --passlim) {
        int swapflg = 0;

        // sorting words in alphabetical order
        for (wordidx = 0;  wordidx < passlim;  ++wordidx) {
            char *lhs = words[wordidx];
            char *rhs = words[wordidx + 1];

            if (strcmp(lhs,rhs) > 0) {
                dbg("SWAP/%d: '%s' '%s'\n",passlim,lhs,rhs);
                strcpy(tmp,lhs);
                strcpy(lhs,rhs);
                strcpy(rhs,tmp);
                swapflg = 1;
            }
        }

        // if nothing got swapped, we can stop early (i.e. everything is in
        // sort)
        if (! swapflg)
            break;
    }

    // clear out destination so [first] strcat will work
    tab[0] = 0;

    // copy back words into original string
    // adding the space as a _prefix_ before a word eliminates the need for a
    // cleanup to remove the last space
    for (wordidx = 0;  wordidx < wordcnt;  ++wordidx) {
        dbg("SORTED: '%s'\n",words[wordidx]);

        // adding spaces before each word
        if (wordidx > 0)
            strcat(tab, " ");

        // copying to tab
        strcat(tab,words[wordidx]);
    }
}

int
main(int argc,char **argv)
{
    char input[] = "If you  are  working on something that you really care"
        " about you dont have to be  pushed The vision pulls you Steve Jobs";

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 'd':
            opt_dbg = ! opt_dbg;
            break;
        }
    }

    sort_alphabetically(input);
    printf("%s\n", input);

    return 0;
}

Answer 3

Проблема в том, что вы копируете символы в буфер tmp при достижении конца строки ввода (tab); то есть когда tab[j + 1] == '\0' верно. В этом случае вы не копируете последние данные в этом for l oop:

    for (g = k; g > 0; g--) {
        tmp[l] = tab[j - g];
        l++;
    }

Чтобы устранить проблему, просто измените условие l oop 's' на включайте, когда g равен нулю, и пропустите эту «итерацию», когда вы встретите пробел:

    for (g = k; g >= 0; g--) { // Make sure to include any 'last' character
        if (tab[j - g] != ' ') { // ... but skip if this is a space
            tmp[l] = tab[j - g];
            l++;
        }
    }

Обратите внимание, что у вас есть избыточный тест в этой строке:

    else if (tab[j] == ' ' || tab[j + 1] == '\0' || tab[j + 1] == '\0') {

который также можно написать без третьего теста (который совпадает со вторым), таким образом:

    else if (tab[j] == ' ' || tab[j + 1] == '\0') {