Сортировка массива строк в C с использованием указателей без qsort

Question

Итак, я полный новичок в C, и я пытался отсортировать массив строк без использования qsort. Вот код:

#include <stdio.h>
#include <string.h>
void sort(char *ar[],int n)
{
    int i,j;
    char temp[10]; 
    for (i=0;i<n-1;i++)
    {
        for (j=0;j<n-i-1;j++)
        {
            if ((strcmp (*(ar+j),*(ar+j+1)))>0)
            {
                strcpy (temp, *(ar+j));
                strcpy (*(ar+j), *(ar+j+1));
                strcpy (*(ar+j+1), temp);
                printf ("%s\n", temp);
            }
        }
    }
    /*printf ("After sorting: \n");
    for (i=0;i<n;i++)
    printf ("%s\n", *(ar));*/
}
int main()
{
    int i,n;
    char* ar[]={"ghi","def","abc"};
    n = sizeof(ar)/sizeof(*ar);
    printf ("Before sorting: \n");
    for (i=0;i<n;i++)
    printf ("%s\n", *(ar+i));
    sort (ar,n);
    printf ("After sorting: \n");
    for (i=0;i<n;i++)
    printf ("%s\n", *(ar+i));
    return 0;
}

Однако он печатает только строки перед сортировкой. Что я здесь делаю не так?

Answer 1

У вас неопределенное поведение в вашей функции сортировки.

Есть две причины:

1. Вы используете массив указателей, и каждый указатель указывает в буквальную строку;
2. Вы используете strcpy для копирования содержимого между строками.

В C попытка изменить буквальную строку - это неопределенное поведение . Литеральные строки, по сути, являются только для чтения . Обратите внимание, что они не являются постоянными, даже несмотря на то, что всегда рекомендуется использовать const указатели.

У вас есть два возможных способа решения этой проблемы:

1. Используйте массив вместо массивов:

   char ar[][10] = { ... };
   

   Тогда содержимое строк можно изменять, и вы можете использовать strcpy.

2. Или вместо этого поменять местами указатели:

   char *temp = ar[j];
   ar[j] = ar[j + 1];
   ar[j + 1] = temp;
   

Answer 2

Я думаю, вам лучше использовать strdup() для копирования строки вместо использования strcpy, потому что первая строка будет храниться в куче, а вторая строка будет храниться в стеке, который легко теряется после вашего вызова sort() .

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

void sort(char *array[], int start, int end) {
    for (int i = start; i <= end - 1; i++) {
        for (int j = i + 1; j <= end; j++) {
            // swap if array[i] > array[j]
            if (strcmp(array[i], array[j]) > 0) {
                char *tmp = strdup(array[j]);
                array[j] = strdup(array[i]);
                array[i] = strdup(tmp);
            }
        } 
    }
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <string> ...\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    sort(argv, 1, argc - 1);            // sort

    for (int i = 1; i < argc; i++) {
        printf("%s ", argv[i]);
    }
    printf("\n");

    exit(EXIT_SUCCESS);
}

$ ./sort_string_array ghi def abc

abc def ghi

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

Answer 3

Ваша основная проблема в том, что вы используете strcpy() со строковыми литералами, что запрещено. Если вместо этого вы поменяете указатели местами, ваш алгоритм будет работать отлично. Вот обновленная версия sort():

void sort(char *ar[],int n)
{
    int i,j;
    char* temp; 
    for (i=0;i<n-1;i++)
    {
        for (j=0;j<n-i-1;j++)
        {
            if (strcmp (ar[j], ar[j + 1] ) > 0)  // more readable with indexing syntax
            {
                temp = ar[j];
                ar[j] = ar[j+1];
                ar[j+1] = temp;
                printf ("%s\n", temp);
            }
        }
    }
}