Рубрики

Программа C для пузырьковой сортировки в связанном списке

Получив односвязный список, отсортируйте его с помощью пузырьковой сортировки .

Input : 10->30->20->5
Output : 5->10->20->30

Input : 20->4->3
Output : 3->4->20

// C программа для реализации Bubble Sort в односвязном списке
#include<stdio.h>
#include<stdlib.h>

  
/ * структура для узла * /

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Функция для вставки узла в начало связанного списка * /

void insertAtTheBegin(struct Node **start_ref, int data);

  
/ * Функция пузырьковой сортировки заданного связанного списка * /

void bubbleSort(struct Node *start);

  
/ * Функция для обмена данными двух узлов a и b * /

void swap(struct Node *a, struct Node *b);

  
/ * Функция для печати узлов в заданном связанном списке * /

void printList(struct Node *start);

  

int main()

{

    int arr[] = {12, 56, 2, 11, 1, 90};

    int list_size, i;

  

    / * начать с пустого связанного списка * /

    struct Node *start = NULL;

  

    / * Создать связанный список из массива arr [].

      Созданный связанный список будет 1-> 11-> 2-> 56-> 12 * /

    for (i = 0; i< 6; i++)

        insertAtTheBegin(&start, arr[i]);

  

    / * распечатать список перед сортировкой * /

    printf("\n Linked list before sorting ");

    printList(start);

  

    / * сортировать связанный список * /

    bubbleSort(start);

  

    / * распечатать список после сортировки * /

    printf("\n Linked list after sorting ");

    printList(start);

  

    getchar();

    return 0;

}

  

  
/ * Функция для вставки узла в начало связанного списка * /

void insertAtTheBegin(struct Node **start_ref, int data)

{

    struct Node *ptr1 = (struct Node*)malloc(sizeof(struct Node));

    ptr1->data = data;

    ptr1->next = *start_ref;

    *start_ref = ptr1;

}

  
/ * Функция для печати узлов в заданном связанном списке * /

void printList(struct Node *start)

{

    struct Node *temp = start;

    printf("\n");

    while (temp!=NULL)

    {

        printf("%d ", temp->data);

        temp = temp->next;

    }

}

  
/ * Пузырьковая сортировка по указанному связанному списку * /

void bubbleSort(struct Node *start)

{

    int swapped, i;

    struct Node *ptr1;

    struct Node *lptr = NULL;

  

    / * Проверка на пустой список * /

    if (start == NULL)

        return;

  

    do

    {

        swapped = 0;

        ptr1 = start;

  

        while (ptr1->next != lptr)

        {

            if (ptr1->data > ptr1->next->data)

            

                swap(ptr1, ptr1->next);

                swapped = 1;

            }

            ptr1 = ptr1->next;

        }

        lptr = ptr1;

    }

    while (swapped);

}

  
/ * функция для обмена данными двух узлов a и b * /

void swap(struct Node *a, struct Node *b)

{

    int temp = a->data;

    a->data = b->data;

    b->data = temp;

}

Выход:

 Linked list before sorting
90 1 11 2 56 12
 Linked list after sorting
1 2 11 12 56 90

Рекомендуемые посты:

Программа C для пузырьковой сортировки в связанном списке

0.00 (0%) 0 votes