Сортировка связанного списка - C (СИ)
Формулировка задачи:
Доброго времени! =)
имеется структура, ссылающаяся на саму себя и определения собственных типов данных:
со вставкой, удалением, выводом, сохраниением/загрузкой в/из файла в связанном списке разобрался. и на словах: если находится элемент, у которого номер семестра больше чем у след. эл-та, то необходимо его скопировать в буфер, затем на место этого элемента вставляем след. элемент, и модифицируем указатели у них - у элемента, который находится в буфере *next присваеваем *next того элемента, который был следующим, а *next у элемента который был следующий, присваеваем указатель на буфер.
вот моя идея, но она не работает...=(
помогите с алгоритмом, пожалуйста
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; }
Решение задачи: «Сортировка связанного списка»
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; }
Объяснение кода листинга программы
Объяснение порядка выполнения кода:
- Функция
sort
принимает указатель на голову связанного спискаheadDIS
в качестве аргумента. - Если список пуст, функция возвращает 0.
- В противном случае, инициализируется новый узел
headNode
с пустым значениемnext
. - Начинается цикл, который проходит по всем элементам списка, начиная с
t
. - Для каждого элемента
t
ищется следующий элементu
и сохраняется в переменнойu
. - Затем, для каждого элемента
t
, ищется предыдущий элементp
в отсортированной части списка. - Если
p
равно NULL, это означает, что текущий элементt
является первым элементом в отсортированной части списка, поэтому он добавляется в конец отсортированной части списка. - Если
p
не равно NULL, тоt
сравнивается сp->next
. Еслиt->num_term
больше, чемp->next->num_term
, тоt
становится новымnext
дляp
. - Если
t
больше, чемp->next
, тоt
добавляется передp->next
в отсортированную часть списка. - По завершении цикла,
headDIS
обновляется, чтобы указывать на первый элемент в отсортированной части списка. - Функция возвращает 1, чтобы указать, что список был успешно отсортирован.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д