1

Как реализовать функцию swap для сортировки односвязного списка?

Моя структура:

struct prog
{
    char name[80];
    unsigned int kol;
    double time1;
    double time2;

    struct prog* next;
};

Мой код сортировки (сортировал относительно переменной kol):

void zad6(struct prog* head)
{
    int swapped, i;
    struct prog* ptr1;
    struct prog* lptr = NULL;
    if (head == NULL)
    {
        return;
    }
    do
    {
        swapped = 0;
        ptr1 = head;
        while (ptr1->next != lptr)
        {
            if (ptr1->kol > ptr1->next->kol)
            {
                swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

Вот моя функция swap:

void swap(struct prog* a, struct prog* b)
{
     // что тут написать?
}
5
  • В вашем (неправильном) варианте сортровки списка можно перемещать данные между элементами списка, сохраняя указатели. void swap(struct prog* a, struct prog* b) { struct prog t; struct prog *a_next, *b_next; a_next = a->next; b_next = b->next; t = *a; *a = *b; *b = t; a->next = a_next; b->next = b_next;}
    – avp
    28 мар 2020 в 16:19
  • ну как, сортировка получилась?
    – avp
    29 мар 2020 в 13:40
  • avp, да спасибо все работает
    – user379722
    29 мар 2020 в 14:56
  • @avp, мне нравится этот пользователь с односвязным списком. Он уже наделал 100500 учёток и после каждого вопроса закрывает их...
    – 0andriy
    30 мар 2020 в 11:08
  • @0andriy, боится чего-то, наверное считает, что так его не отследят
    – avp
    30 мар 2020 в 12:54

1 ответ 1

1

А вот так правильно (в рамках того же алгоритма, делающего перестановки пока переставляется) программировать сортировку списка.
Правильно в смысле эффективности.

По сути, эффективная сортировка списка должна менять порядок его элементов (изменять указатели на следующий в структурах данных), а не копировать содержимое одной области памяти в другую. Это особенно актуально, если в элементах списка хранится много данных (например, несколько килобайт) или на эти данные есть указатели из других структур данных.

struct prog *
sort_list (struct prog *head)
{
  int swp;

  do {
    swp = 0;
    struct prog **prev = &head;

    for (struct prog *p = head; p && p->next; p = p->next) {
      if (p->kol > p->next->kol) {
        // SWAP;
        struct prog *t = p->next,
          *u = p->next->next;

        p->next = u;
        t->next = p;
        *prev = t;
        swp++;
      }
      prev = &(p->next);
    }
  } while (swp);

  return head;
}

использование:

struct prog *list = make_list();
  ...
list = sort_list(list);

Замечу, что длинные списки сортировать таким алгоритмом весьма не эффективно. С хорошей сортировкой списков (сложность N log(N)) можно ознакомиться тут.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.