Связанный список и сортировка по алфавиту - PullRequest
Новая
       35

Связанный список и сортировка по алфавиту

0 голосов
/ 18 января 2019

Я использую связанный список для хранения структур. Каждый узел имеет структуру с именем item_t. У item_t есть поле с именем name. Я хочу отсортировать имена по алфавиту, поменяв местами элементы (item_t) в узлах. Алгоритм работает для чисел (целые числа, числа с плавающей точкой и т. Д.), Но дает неверные результаты для строк

Я предполагаю, что проблема кроется в неправильном использовании strcmp, но я прочитал всю документацию и не вижу ее. 

typedef struct item_t
/*
 Definition of the item_t struct
*/
{
    char *name;
    float price;
}item_t;

/* structure for a node */
typedef struct node_t
{
    item_t item;
    struct node_t *next;
} node_t;

/* function to swap item of two nodes a and b*/
void swap(node_t *a, node_t *b)
{
    item_t temp = a->item;
    a->item = b->item;
    b->item = temp;
}

void bubbleSortByNameAscending(node_t *start)
{
    int swapped = 1;
    node_t *ptr1;
    node_t *lptr = NULL;

    /* Checking for empty list */
    if (start == NULL)
            return;
    while (swapped)
    {
        swapped = 0;
        ptr1 = start;

        while (ptr1->next != lptr)
        {
            if (strcmp(ptr1->item.name, ptr1->next-    >item.name) > 0)
            {
                    swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }

}

/* Bubble sort the given linked list */
void bubbleSortByPriceAscending(node_t *start)
/* TESTED */
{
    int swapped;
    node_t *ptr1;
    node_t *lptr = NULL;

    /* Checking for empty list */
    if (start == NULL)
        return;

    do
    {
        swapped = 0;
        ptr1 = start;

        while (ptr1->next != lptr)
        {
            if (ptr1->item.price > ptr1->next->item.price)
            {
                swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }    
        lptr = ptr1;
    }
    while (swapped);
}

Учитывая этот список:

  1. Элемент списка
  2. S7Edge 1500.00
  3. iPhone7 1000,00
  4. iOS10 0
  5. Android 0

Я ожидаю следующих результатов при сортировке по имени:

  1. Android 0
  2. iOS 0
  3. iPhone7 1000,00
  4. iPhone8 2000.00
  5. S7Edge 1500.00

Но я получаю это:

  1. Android 0
  2. S7Edge 1500.00
  3. iOS 0
  4. iPhone7 1000,00

  5. iPhone8 2000.00 Затем я добавил еще один элемент, начинающийся с Z, чтобы понять его:

    • Android 0
    • iOS 0
    • iPhone7 1000,00
    • iPhone8 2000.00
    • S7Edge 1500.00
    • Зойдберг 0

И я получил:

  • Android 0
  • S7Edge 1500.00
  • Зойдберг 0
  • iOS 0
  • iPhone7 1000,00
  • iPhone8 2000.00

РЕДАКТИРОВАТЬ: Я почти уверен, «я»! = «Я», более того, «Z»> «я». Логичным решением было бы все в нижнем или верхнем регистре, а затем strcmp, но как мне отменить изменения обратно, чтобы «IPHONE» стал «iPhone»?

1 Ответ

0 голосов
/ 18 января 2019

Я решил проблему, продублировав строки с именами во временные переменные, strupr () (делает заглавную строку) временными переменными и сравнил их. Затем я поменяю местами в соответствующих узлах, работает как шарм. 

while (swapped)
            {
                swapped = 0;
                ptr1 = start;

                while (ptr1->next != lptr)
                {
                    char *temp1 = strdup(ptr1->item.name);
                    char *temp2 = strdup(ptr1->next->item.name);

                    strupr(temp1);
                    strupr(temp2);
                    if (strcmp(temp1, temp2) > 0)
                    {
                        swap(ptr1, ptr1->next);
                        swapped = 1;
                    }
                    ptr1 = ptr1->next;
                }
                lptr = ptr1;
            }
...