String Insertion Сортировка программы

Question

Я только начинаю наклонять C, поэтому я не очень хорошо ее знаю. Предоставленная нам программа говорит нам написать программу сортировки вставки, которая занимает 20 строк, разделенных пробелом, и сортирует их по алфавиту и распечатывает их по порядку. Это меня сбивает с толку, так как C не имеет типа данных String (по крайней мере, насколько мне известно). Разве строки не просто массивы символов? Вот что я получил:

#include <stdio.h> 
#include <string.h> 
#define MAX_STRINGS 20 

void InsertionSort(char list[]); 

void main() 
{ 
    int index; 
    char strings[MAX_STRINGS]; 

    /* Get input */ 
    printf("Enter %s strings.\n", MAX_STRINGS); 
    for (index = 0; index < MAX_STRINGS; index++) 
    { 
     char tempString[100]; 
     printf("Input string %d : ", index); 
     scanf("%s", &tempString[0]); 
     strings[index] = tempString; 
    } 

    InsertionSort(strings); 

    printf("\nThe input set, in alphabetical order:\n"); 
    for (index = 0; index < MAX_STRINGS; index++) 
    { 
     printf("%s\n", strings[index]); 
    } 
} 

void InsertionSort(char list[]) 
{ 
    int unsorted; 
    int sorted; 
    char unsortedItem; 

    for(unsorted = 1; unsorted < MAX_STRINGS; unsorted++) 
    { 
     unsortedItem = list[unsorted]; 

     for (sorted = unsorted - 1; (sorted >= 0) && (list[sorted] > unsortedItem); sorted--) 
     { 
      list[sorted + 1] = list[sorted]; 
     } 
     list[sorted + 1] = unsortedItem; 
    } 
} 

Я совершенно не знаком с синтаксисом C и C, и я нахожу его очень запутанным. Эта программа работает некорректно. То, что он делает, это позволяет мне вводить 20 строк, но потом ничего не сортируется и ничего не выводит. Любая идея о том, как это исправить? Кроме того, есть ли какая-либо идея, как я могу получить ее туда, где я набираю одно предложение, и каждая строка разделяется пробелом? Например, если я печатаю «Я изучаю, как программировать на C, и сейчас мне это не нравится». это даст мне 16 строк. «Я», «Я», «Обучение» и т. Д. Спасибо.

Answer 1

Используй эту функцию для сортировки строк по алфавиту:

int s_bubblesortA(int argc,char **argv) 
{ 
    int i , j = 0; 
    char *p_1 , *p_2 , *tmp; 
    while(j < argc) 
    { 
     for(i = 0 ; i < argc - j - 1 ; i++) 
     { 
      p_1 = argv[i] , p_2 = argv[i+1]; 
      while(*p_1 && *p_2) 
      { 
       if(*p_1 < *p_2) 
        break; 
       else if(*p_1 > *p_2 || (! *(p_2 + 1) && (*p_1 == *p_2) && *(p_1+1))) 
       { 
        tmp = argv[i]; 
        argv[i] = argv[i+1]; 
        argv[i+1] = tmp; 
        break; 
       } 
       p_1++; 
       p_2++; 
      } 
     } 
     j++; 
    } 
    return 0; 
} 

Примечания: проверить эту ссылку, чтобы таким образом мой полный ответ на аналогичную должность. sort words alphabeticaly in C

Answer 2

Несколько проблем с оригинальным кодом:

1) Вы не можете копировать строки, используя =; используйте strncpy для этого (используя = присваивает указатели).

2) Строка представляет собой массив символов; поэтому массив строк - это массив массивов символов (поэтому ваша подпись InsertionSort неверна). Обратите внимание, что строки C имеют нулевое завершение, что просто означает, что байт со значением 0 означает конец строки (это очень важно, если вы забудете все остальное, запомните это).

3) %s ожидает char*; эта линия производит UB: printf("Enter %s strings.\n", MAX_STRINGS);. Вместо этого вы хотите указать %d (ознакомьтесь с спецификаторами формата printf).

4) Вы не можете сравнивать строки с помощью обычных арифметических операторов; те сравнивают указатели. Вы должны использовать strcmp.

5) Ваша реализация алгоритма сортировки вставки была неправильной.

6) Существует несколько версий разрешений main, разрешенных стандартом, и char main не является одним из них. В этом случае просто используйте int main.

Вот исправленная версия кода:

#include <stdio.h> 
#include <string.h> 
#define MAX_STRINGS 20 
#define MAX_STRING_LEN 200 

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN]); 

int main() 
{ 
    int index; 
    char strings[MAX_STRINGS][MAX_STRING_LEN]; 

    /* Get input */ 
    printf("Enter %d strings.\n", MAX_STRINGS); 
    for (index = 0; index < MAX_STRINGS; index++) 
    { 
     printf("Input string %d : ", index); 
     scanf("%199s", strings[index]);  // limit the width so we don't go past the buffer 
     strings[index][sizeof(strings[index]) - 1] = '\0'; 
    } 

    InsertionSort(strings); 

    printf("\nThe input set, in alphabetical order:\n"); 
    for (index = 0; index < MAX_STRINGS; index++) 
    { 
     printf("%s\n", strings[index]); 
    } 
} 

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN]) 
{ 
    for (int i = 1; i < MAX_STRINGS; i++) 
    { 
     int j = i; 

     while (j > 0 && strcmp(list[j - 1], list[j]) > 0) 
     { 
      char tmp[MAX_STRING_LEN]; 
      strncpy(tmp, list[j - 1], sizeof(tmp) - 1); 
      tmp[sizeof(tmp) - 1] = '\0'; 

      strncpy(list[j - 1], list[j], sizeof(list[j - 1]) - 1); 
      list[j - 1][sizeof(list[j - 1]) - 1] = '\0'; 

      strncpy(list[j], tmp, sizeof(list[j])); 
      list[j][sizeof(list[j]) - 1] = '\0'; 

      --j; 
     } 
    } 
} 

Это может быть немного подавляющим сначала, но читать его медленно и внимательно, и вы не должны иметь никаких проблем.

= '\0' В s после strncpy или scanf - эти функции не неявно нуль-прекратить строки, так что мы должны сделать это вручную - вы можете уйти, не делая это несколько раз, но в конечном счете это будет вернитесь к вам в конце концов. Будьте в безопасности и делайте это привычкой.

Все остальные: если вы заметили какие-либо ошибки, сообщите мне, что уже поздно, и я устал.

Что касается ваших вопросов в комментариях:

1) Почему я, начиная с 1 в цикле for?
Поскольку я позже ссылаюсь на list[j - 1], а с j установлен на значение i (изначально), он не может быть меньше 1 или мы будем использовать отрицательные индексы. См. here для описания алгоритма.

2) Как читать целую строку строки, включая пробелы?
Лучшим решением было бы использовать fgets. Обратите внимание, что у него есть одна причуда: он сохраняет символ \n в массиве. Если вы этого не хотите, вам придется удалить его вручную.

3) Что такое tmp?
Это всего лишь временный буфер char, поэтому я могу обменять две строки, как требует алгоритм. Это не относится к строкам, в общем случае для замены двух переменных вам нужен третий, временный (если вы не выберете некоторые грязные XOR-хаки).