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

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

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

Добрый вечер! Есть список и функции работы с ним(переходы к элементам, их удаление, поиск элементов по каким либо параметрам). Сама структура списка ->
struct list
{
    int data;
    list *next;
}; list *first=0, *nval=0;
Нужна помощь в написании функции сортировки : все нечетные элементы слева , четные справа (т.е - Дано: 27432195, после вызова должно получиться 13579224) В массивах знаю как это делать, а здесь блуждаю в указателях. Помогите разобраться.

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

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;
}

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

  1. В функции AddToList новый узел списка добавляется в конец списка. Если список пуст, то новый узел становится началом списка.
  2. Функция PrintList печатает значения узлов списка в формате Значение: адрес. Если список пуст, то выводится сообщение List is empty.
  3. Функция ClearList проходит по списку и освобождает память, занимаемую каждым узлом, перед чем сохраняя адрес следующего узла.
  4. Функция SortList сортирует список по возрастанию. Для этого список копируется в массив указателей на узлы, затем проводится сортировка массива пузырьком. После сортировки массива восстанавливается векторность списка и обновленный список возвращается.
  5. В функции ProcessList списки с четными и нечетными данными разделяются. Затем каждый из этих списков сортируется с помощью функции SortList. После сортировки списки с четными и нечетными данными объединяются в один список.
  6. В функции main создается пустой список a. Затем в цикле с помощью функции AddToList в список добавляются 10 узлов с различными значениями. После этого список печатается с помощью функции PrintList. Затем список обрабатывается с помощью функции ProcessList, сортируется и снова печатается с помощью функции PrintList. После этого список очищается с помощью функции ClearList.

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


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

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

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