Блог

Главная - Вопросы по программированию - Как найти ошибку в логике моего кода?

Как найти ошибку в логике моего кода?

#c #string #c-strings #bubble-sort

#c #строка #c-строки #пузырьковая сортировка

Вопрос:

 #include<stdio.h>
#include<string.h>
int main()
{
    setbuf(stdout,NULL);
    char str1[50][50],temp[50];
    int lim,i,j,res;
    printf("Enter the number of strings: ");
    scanf("%d",amp;lim);
    for(i=0;i<lim;i  )
    {
        scanf("%s",str1[i]);
    }
    for(i=0;i<lim;i  )
    {
        for(j=1;j<lim-1;j  )
        {
            res=strcmp(str1[i],str1[j]);
            if(res==1)
            {
                strcpy(temp,str1[i]);
                strcpy(str1[i],str1[j]);
                strcpy(str1[j],temp);
            }
        }
    }
    for(i=0;i<lim;i  )
    {
        puts(str1[i]);
    }
    return 0;
}

Я пытаюсь использовать пузырьковую сортировку для сортировки строк, введенных пользователем. Но результат получается неправильным.

Есть ли какая-либо ошибка в моей логике в if инструкции?

Комментарии:

1. @h0r53 Не то чтобы это добавило какой-либо безопасности коду. Проблема начинается с scanf .

2. У @h0r53 strncpy есть свои проблемы. Особенно скопированная строка может оказаться без нулевого разделителя.

3. @Jabberwocky Я видел людей, которым сказали заменить strcpy(str1, str2) на strncpy .. И они это сделали strncpy(str1, str2, strlen(str2)) (ну, иногда заботились о 1) 😀

4. При пузырьковой сортировке вы сравниваете соседние элементы и меняете местами, когда это необходимо. Этот код начинается с i и сравнивается str1 с i каждым другим элементом. После того, как вы поменяли str1[i] местами что-то другое, вы больше не сравниваете это с соседними элементами, потому что i это будет пропущено на следующей итерации цикла. Это логический недостаток.

5. Подсказка: не уверен, что проблема в этом: но if (res==1) это неправильно и должно быть if (res>0) . strcmp Внимательно прочитайте документацию, особенно ту часть, которая касается возвращаемого значения.

Ответ №1:

Как заметил @h0r53 в комментариях, то, что вы реализовали, [вообще] не является пузырьковой сортировкой. Это почти сортировка по выбору, но она имеет неправильные границы итерации внутреннего цикла, которые кажутся несколько напоминающими пузырьковую сортировку. Комбинация нарушена. С точки зрения сортировки выборки это неправильно, потому что вы никогда не рассматриваете последний элемент, и это неэффективно, потому что вы без необходимости пересматриваете ведущие элементы, которые уже были отсортированы.

Ключевая часть алгоритмически правильной версии сортировки выбора может выглядеть следующим образом:

     for (i = 0; i < lim; i  ) {
        for (j = i   1; j < lim; j  ) {  // These bounds are changed vs. the original
            // Compare each subsequent element with element i:
            res = strcmp(str1[i], str1[j]);
            if (res > 0) {
                strcpy(temp, str1[i]);
                strcpy(str1[i], str1[j]);
                strcpy(str1[j], temp);
            }
        }
    }

Альтернативно, это была бы алгоритмически правильная версия пузырьковой сортировки:

     // for (i = 0; i < lim; i  ) {  // particularly inefficient; note: no i in the loop body
    for (; lim > 1; lim--) {  
        for (j = 0; j < lim - 1; j  ) {  // Almost, but not quite, the same as the original
            // Compare each element but the last with the following one:
            res = strcmp(str1[j], str1[j   1]);
            if (res > 0) {
                strcpy(temp, str1[j]);
                strcpy(str1[j], str1[j   1]);
                strcpy(str1[j   1], temp);
            }
        }
    }

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

Ответ №2:

Ваш код может выполняться, если вы измените инструкцию сортировки, как показано ниже: Из:

     for(i=0;i<lim;i  )
    {
        for(j=1;j<lim-1;j  )
        {
            res=strcmp(str1[i],str1[j]);
            if(res==1)
            {
                strcpy(temp,str1[i]);
                strcpy(str1[i],str1[j]);
                strcpy(str1[j],temp);
            }
        }
    }

Для

     while (cont) {
        cont = 0;
        for (int i = 0; i < lim - 1; i  )
        {
            res=strcmp(str1[i],str1[i 1]);
            if (res > 0)
            {
                strcpy(temp,str1[i]);
                strcpy(str1[i],str1[i 1]);
                strcpy(str1[i 1],temp);
                cont = 1;
            }
        }
    }