Сортировка связанного списка - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Доброго времени! =) имеется структура, ссылающаяся на саму себя и определения собственных типов данных:
struct iDiscipline{
    char name[10];//имя
    int num_course;//№ курса
    int num_term;//№ семестра
    int am_lec;//кол-во часов лекций
    int am_pr;//практик
    int am_lab;//лабы
    int am_one;//сам.раб
    int am_ALL;//всего часов
    struct iDiscipline *next; //указатель на следующий элемент списка 
};
 
typedef struct iDiscipline LIST;
typedef LIST *LISTDIS;
со вставкой, удалением, выводом, сохраниением/загрузкой в/из файла в связанном списке разобрался.

НО НИКАК НЕПОЛУЧАЕТСЯ ОСУЩЕСТВИТЬ СОРТИРОВКУ.

вот мой код:
int sort(LISTDIS *headDIS)
{
    if (*headDIS == NULL)
        return 0;//в списке пусто
    else {
        LISTDIS currentDIS, nextDIS, prevDIS, buffer;
 
        currentDIS = *headDIS;
        prevDIS = NULL;
 
        if (currentDIS->next != NULL)//проверяем, не 1 ли в списке элемент
            nextDIS = currentDIS->next;
        else
            return -1;//в списке 1 элемент
 
        for (;currentDIS != NULL;currentDIS=currentDIS->next) {
            for (;nextDIS != NULL;nextDIS=nextDIS->next) {
                //по семестру
                if (currentDIS->num_term > nextDIS->num_term) {
                    buffer = currentDIS;
                    buffer->next = nextDIS->next;
                    currentDIS = nextDIS;
                    currentDIS->next = buffer;
                }
            }
        }
    }
    return 1;
 
}
и на словах: если находится элемент, у которого номер семестра больше чем у след. эл-та, то необходимо его скопировать в буфер, затем на место этого элемента вставляем след. элемент, и модифицируем указатели у них - у элемента, который находится в буфере *next присваеваем *next того элемента, который был следующим, а *next у элемента который был следующий, присваеваем указатель на буфер. вот моя идея, но она не работает...=( помогите с алгоритмом, пожалуйста

Решение задачи: «Сортировка связанного списка»

textual
Листинг программы
int sort(LISTDIS *headDIS)
{
    if (*headDIS == NULL)
        return 0;//в списке пусто
    else {
        LIST headNode;
 
        headNode.next = 0;
        for ( LISTDIS t = *headDIS, u, p; t; t = u )
        {
            u = t->next;
            for ( p = &headNode; p->next && t->num_term > p->next->num_term; p = p->next );
            t->next = p->next;
            p->next = t;
        }
        *headDIS = headNode.next;
    }
    return 1;
}

Объяснение кода листинга программы

Объяснение порядка выполнения кода:

  1. Функция sort принимает указатель на голову связанного списка headDIS в качестве аргумента.
  2. Если список пуст, функция возвращает 0.
  3. В противном случае, инициализируется новый узел headNode с пустым значением next.
  4. Начинается цикл, который проходит по всем элементам списка, начиная с t.
  5. Для каждого элемента t ищется следующий элемент u и сохраняется в переменной u.
  6. Затем, для каждого элемента t, ищется предыдущий элемент p в отсортированной части списка.
  7. Если p равно NULL, это означает, что текущий элемент t является первым элементом в отсортированной части списка, поэтому он добавляется в конец отсортированной части списка.
  8. Если p не равно NULL, то t сравнивается с p->next. Если t->num_term больше, чем p->next->num_term, то t становится новым next для p.
  9. Если t больше, чем p->next, то t добавляется перед p->next в отсортированную часть списка.
  10. По завершении цикла, headDIS обновляется, чтобы указывать на первый элемент в отсортированной части списка.
  11. Функция возвращает 1, чтобы указать, что список был успешно отсортирован.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.429 из 5
Похожие ответы