Файл: Лабораторная работа 7 по дисциплине Программирование Указатель на функцию Группа авт242 Студенты Юркевич М. Н.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 22.11.2023

Просмотров: 50

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТЛабораторная работа №7по дисциплине «Программирование» Указатель на функциюГруппа: АВТ-242Студенты: Юркевич М.Н.Преподаватель: Романенко Т. А.НОВОСИБИРСК 2023ЗаданиеШейкер-сортировка двусвязного списка

  1. Преобразовать функцию сортировки в итератор.

  2. Проверить работу итератора на двух структурах данных содержащих указатели на различные типы (например, целые и строки).

  3. Составить отчёт.

  4. Сдать преподавателю файл.doc с отчётом и файл.cpp с исходным текстом программы.
Теоретические сведения Если операцию над элементом структуры данных вынести за пределы алгоритма и реализовать отдельной функцией, а указатель на функцию передавать алгоритму в качестве параметра, то получим универсальную функцию – итератор. Структура данных, обрабатываемая итератором, содержит в своих элементах указатели на переменные произвольного (неизвестного для итератора) типа void*, Итератор получает в качестве параметров указатель на структуру данных и указатель на функцию обработки.Проектирование программы«Составные части» программы:Node* newNode(int data, char name[10]) – функция создания нового узла спискаvoid append(Node** headRef, int data, char name[10]) – функция добавления нового элемента в конец спискаvoid swap(Node* a, Node* b) – функция, меняющая данные двух узловint CompareByName(const Node* a, const Node* b) – функция сравнения двух узлов по имениint CompareByData(const Node* a, const Node* b) – функция сравнения двух узлов по числуvoid cocktailSort(Node* start, int (*compare)(const Node*, const Node*)) – шейкер сортировка двусвязного спискаvoid printList(Node* node) – функция вывода спискаvoid freeList(Node* node) – функция освобождения памятиПеременные:Node* head – голова списка, с которым мы будем работатьint n – количество элементов списка (задается пользователем)
int data, char name[10] – переменные для данных узловint sw – переменная для switchТекст программы с комментариями#define _CRT_SECURE_NO_WARNINGS#include

#include

#include

#include
// Структура для представления узла списка

typedef struct Node {

int data;

char name[10];

struct Node* prev;

struct Node* next;

};
// Функция для создания нового узла списка

Node* newNode(int data, char name[10])

{

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

node->data = data;

strcpy(node->name, name);

node->prev = NULL;

node->next = NULL;

return node;

}
// Функция для добавления нового узла в конец списка

void append(Node** headRef, int data, char name[10])

{

Node* newNode = (Node*)malloc(sizeof(Node));

Node* last = *headRef;

newNode->data = data;

strcpy(newNode->name, name);
newNode->next = NULL;

if (*headRef == NULL) {

newNode->prev = NULL;

*headRef = newNode;

return;

}

while (last->next != NULL) {

last = last->next;

}

last->next = newNode;

newNode->prev = last;

return;

}
// Функция для обмена данных между двумя узлами списка

void swap(Node* a, Node* b)

{

int temp_data = a->data;

char temp_name[10];

strcpy(temp_name, a->name);

a->data = b->data;

b->data = temp_data;

strcpy(a->name, b->name);

strcpy(b->name,temp_name);
}
int CompareByName(const Node* a, const Node* b)

{

return strcmp(a->name, b->name);

}
int CompareByData(const Node* a, const Node* b)

{

return a->data - b->data;

}
// Функция для выполнения шейкерной сортировки двусвязного списка

void cocktailSort(Node* start, int (*compare)(const Node*, const Node*))

{

int swapped;

Node* ptr1;

Node* lptr = NULL;

if (start == NULL)

return;

do {

swapped = 0;

ptr1 = start;

while (ptr1->next != lptr)//пока не достигнем конца - проверяем условие и меняем местами

{

if (compare(ptr1, ptr1->next) > 0)

{

swap(ptr1, ptr1->next);

swapped = 1;

}

ptr1 = ptr1->next;

}

if (swapped == 0)

break;

lptr = ptr1;

ptr1 = ptr1->prev;

while (ptr1->prev != NULL)//пока не достигнем конца - проверяем условие и меняем местами

{

if (compare(ptr1, ptr1->next) > 0)

{

swap(ptr1, ptr1->next);

swapped = 1;

}

ptr1 = ptr1->prev;

}

} while (swapped);

}

// Функция для вывода списка на экран

void printList(Node* node)

{

while (node != NULL) {

printf("%d %s ", node->data, node->name);

node = node->next;

}

printf("\n");

}
// Функция для освобождения памяти, занятой списком

void freeList(Node* node)

{

Node* temp;

while (node != NULL) {

temp = node;

node = node->next;

free(temp);

}

}
// Тестирование работы шейкерной сортировки двусвязного списка

int main() {

setlocale(LC_ALL, "Russian");

Node* head = NULL;

int n, data,sw;

char name[10];
printf("Введите количество элементов списка: ");

scanf("%d", &n);
printf("Введите элементы списка:\n");

for (int i = 0; i < n; i++) {

scanf("%d", &data);

scanf("%s", &name);

append(&head, data, name);

}

printf("Исходный список: ");

printList(head);

printf("По чему сортируем?\n 1 - По числам\n 2 - По словам\n");

scanf("%d", &sw);

switch (sw)

{

case 1:

cocktailSort(head, CompareByData);

case 2:

cocktailSort(head, CompareByName);

}


printf("Отсортированный список: ");

printList(head);
freeList(head); // Освобождение памяти, занятой списком
return 0;

}

Пример работы программы
Пример 1



Пример 2




Выводы:
Благодаря этой работе я научился преобразовывать функцию сортировки в итератор для двусвязного списка. Такой подход позволяет удобно итерироваться по элементам списка и выполнять операции с каждым элементом в процессе сортировки. Я также проверил работу итератора на двух структурах данных, содержащих указатели на различные типы данных, такие как целые числа и строки. Это помогло убедиться в универсальности и эффективности итератора при сортировке различных типов данных в двусвязном списке.

Смотрите также файлы