Сортировка односвязного динамического списка - C (СИ)
Формулировка задачи:
Добрый вечер!
Есть список и функции работы с ним(переходы к элементам, их удаление, поиск элементов по каким либо параметрам). Сама структура списка ->
Нужна помощь в написании функции сортировки : все нечетные элементы слева , четные справа
(т.е - Дано: 27432195, после вызова должно получиться 13579224)
В массивах знаю как это делать, а здесь блуждаю в указателях. Помогите разобраться.
struct list { int data; list *next; }; list *first=0, *nval=0;
Решение задачи: «Сортировка односвязного динамического списка»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> typedef struct TList TList; struct TList { int Data; TList *Next; }; /* функция добавления в список */ void AddToList(TList **pBegin,const int a) { TList* p=NULL; if(*pBegin==NULL) /*новый список */ { *pBegin=malloc(sizeof(**pBegin)); (*pBegin)->Data=a; (*pBegin)->Next=NULL; } else { /* добавляем в конец */ p=*pBegin; while(p->Next!=NULL) p=p->Next; p->Next=malloc(sizeof(*p)); p->Next->Data=a; p->Next->Next=NULL; } } /* функция печати списка на экран */ void PrintList(const TList* pBegin) { const TList *p=pBegin; printf("%s\n","===== List values ====="); while(p!=NULL) { printf("%p%s%i\n",p,": ",p->Data); p=p->Next; } if(pBegin==NULL) printf("%s\n","List is empty"); } /* функция очистки списка */ void ClearList(TList** pBegin) { TList *p=NULL; while(*pBegin!=NULL) { p=(*pBegin)->Next; free(*pBegin); *pBegin=p; } } /* функция сортировки списка по возрастанию */ void SortList(TList** pBegin) { int NodesCount=0; /* количество узлов в списке */ TList** Nodes=NULL; /* массив указателей на узлы списка */ int i,j; /* переменные циклов */ TList* temp; /* параметр */ /* считаем число узлов в списке */ temp=*pBegin; while(temp!=NULL) { NodesCount=NodesCount+1; temp=temp->Next; } if(NodesCount!=0) { Nodes=malloc(NodesCount*sizeof(*Nodes)); i=0; /* копируем адреса узлов в массив */ temp=*pBegin; while(temp!=NULL) { Nodes[i]=temp; i=i+1; temp=temp->Next; } /* сортировка массива пузырьком */ for(j=0;j<NodesCount;j++) { for(i=0;i<NodesCount-1;i++) { if((Nodes[i]->Data)>(Nodes[i+1]->Data)) { temp=Nodes[i]; Nodes[i]=Nodes[i+1]; Nodes[i+1]=temp; } } } /* восстанавливаем векторность списка */ for(i=0;i<NodesCount-1;i++) Nodes[i]->Next=Nodes[i+1]; Nodes[NodesCount-1]->Next=NULL; /* возвращаем модифицированный список */ *pBegin=Nodes[0]; free(Nodes); } } /* функция обработки списка */ void ProcessList(TList** pBegin) { TList* EvenStart=NULL; /* указатель на начало списка, содержащего четные данные */ TList* EvenEnd=NULL; /* указатель на последний элемент списка с четными данными */ TList* OddStart=NULL; /* --//-- нечетные */ TList* OddEnd=NULL; /* --//-- последний + нечетные */ TList* p=NULL; /* итератор списка */ TList* next=NULL; /* указатель на последующий элемент в списке */ p=*pBegin; while(p!=NULL) { next=p->Next; /* запоминаем адрес следующего элемента в списке */ if(p->Data%2==0) { if(EvenStart==NULL) /* начинаем список с четными данными */ { EvenStart=p; EvenStart->Next=NULL; EvenEnd=EvenStart; } else { /* перебрасываем адреса */ EvenEnd->Next=p; EvenEnd=EvenEnd->Next; EvenEnd->Next=NULL; } } else { if(OddStart==NULL) /* начинаем список с нечетными данными */ { OddStart=p; OddStart->Next=NULL; OddEnd=OddStart; } else { OddEnd->Next=p; OddEnd=OddEnd->Next; OddEnd->Next=NULL; } } p=next; /* идем к следующему элементу */ } SortList(&EvenStart); /* сортируем список с четными данными */ SortList(&OddStart); /* сортируем список с нечетными данными */ if(OddStart!=NULL) /* если есть вообще нечетные данные */ { /* сшиваем конец списка с нечетными данными со списком с четными и возвращаем */ p=OddStart; while(p->Next!=NULL) p=p->Next; p->Next=EvenStart; *pBegin=OddStart; } else *pBegin=EvenStart; } int main(void) { TList* a=NULL; /* указатель на начало списка */ int k=0; int i=0; for(i=0;i<10;i++) { scanf("%d",&k); AddToList(&a,k); } PrintList(a); ProcessList(&a); PrintList(a); ClearList(&a); getchar(); return 0; }
Объяснение кода листинга программы
- В функции
AddToList
новый узел списка добавляется в конец списка. Если список пуст, то новый узел становится началом списка. - Функция
PrintList
печатает значения узлов списка в форматеЗначение: адрес
. Если список пуст, то выводится сообщениеList is empty
. - Функция
ClearList
проходит по списку и освобождает память, занимаемую каждым узлом, перед чем сохраняя адрес следующего узла. - Функция
SortList
сортирует список по возрастанию. Для этого список копируется в массив указателей на узлы, затем проводится сортировка массива пузырьком. После сортировки массива восстанавливается векторность списка и обновленный список возвращается. - В функции
ProcessList
списки с четными и нечетными данными разделяются. Затем каждый из этих списков сортируется с помощью функцииSortList
. После сортировки списки с четными и нечетными данными объединяются в один список. - В функции
main
создается пустой списокa
. Затем в цикле с помощью функцииAddToList
в список добавляются 10 узлов с различными значениями. После этого список печатается с помощью функцииPrintList
. Затем список обрабатывается с помощью функцииProcessList
, сортируется и снова печатается с помощью функцииPrintList
. После этого список очищается с помощью функцииClearList
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д