Файл: Лабораторная работа 7 по дисциплине Программирование Указатель на функцию Группа авт242 Студенты Юркевич М. Н.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 22.11.2023
Просмотров: 12
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Лабораторная работа №7
по дисциплине «Программирование»
Указатель на функцию
Группа: АВТ-242
Студенты: Юркевич М.Н.
Преподаватель: Романенко Т. А.
НОВОСИБИРСК 2023
Задание
Шейкер-сортировка двусвязного списка
-
Преобразовать функцию сортировки в итератор. -
Проверить работу итератора на двух структурах данных содержащих указатели на различные типы (например, целые и строки). -
Составить отчёт. -
Сдать преподавателю файл.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
Выводы:
Благодаря этой работе я научился преобразовывать функцию сортировки в итератор для двусвязного списка. Такой подход позволяет удобно итерироваться по элементам списка и выполнять операции с каждым элементом в процессе сортировки. Я также проверил работу итератора на двух структурах данных, содержащих указатели на различные типы данных, такие как целые числа и строки. Это помогло убедиться в универсальности и эффективности итератора при сортировке различных типов данных в двусвязном списке.