Принципы построения простейших структур данных

МИНЕСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Лабораторная работа №2 по дисциплине «Технологии и методы программирования»

Группа: АБс-023

Студент: Гиске Е.В.

Преподаватель: Медведев М.А.

НОВОСИБИРСК 2022

Цель работы: Рассмотреть принципы построения простейших структур данных. Реализовать алгоритмы в рамках решения различных типовых задач.

Задача: Первая часть: реализовать на языке СИ (инъекции плюсового синтаксиса не допускаются) структуры данных и их основные операции согласно варианту. Описать основную идею использования структур, которые ссылаются сами на себя.

Вторая часть: реализовать в коде заданные алгоритмы, используя стратегии построения алгоритмов.

Часть 1. Вариант №1: Linked list двунаправленный

Двунаправленный linked list – это структура данных, которая состоит из узлов, которые хранят указатели на предыдущий узел и следующий узел.

Основные операции:

create – создание (выделение памяти) структуры

delete – удаление (освобождение памяти) структуры

push_front – добавление элемента в начало списка

push_back – добавление элемента в конец списка

top_front – получить значение первого элемента списка

top_back – получить значение последнего элемента списка

pop_front – удаление первого элемента списка

pop_back – удаление последнего элемента списка

empty – проверка на пустоту списка

size – возвращает размер списка (количество элементов)

print_front – печать списка с первого элемента

print_back – печать списка с последнего элемента

Листинг программы

#include <stdlib.h>

#include <stdio.h>

#include <locale.h>

#include <stdbool.h>

// структура для хранения узлов

typedef struct node {

    int data;

    struct node* next;

    struct node* prev;

} Node;

// структура двунаправленного списка

typedef struct linkedList {

    Node* head;

    Node* tail;

    int size;

} LinkedList;

// создание пустого двунаправленного списка

LinkedList* create() {

    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList)); // выделение памяти для списка

    list->size = 0; // изначальный размер - 0

    list->head = NULL; // начальный элемент пуст

    list->tail = NULL; // конечный элемент пуст

    return list;

}

// удаление двунаправленного списка

void delete(LinkedList** list) {

    Node* temp = (*list)->head; // запоминаем первый узел списка

    Node* next = NULL; // создаем переменную для хранения следующего узла списка

    while (temp != NULL) { // пока есть узлы

        next = temp->next; // обращаемся к узлу

        free(temp); // освобождаем память первого узла списка

        temp = next; // переходим к следующему узлу

    }

    free(*list); // освобождаем память всего списка

    (*list) = NULL; // инициализируем "пустым" значением

}

// добавление нового элемента в начало списка

void push_front(LinkedList* L_list, int value) {

    Node* temp = (Node*)malloc(sizeof(Node)); // выделяем память под новый узел

    if (temp == NULL) { // если память по каким-то причинам не выделилась, сообщаем об ошибке

        printf("ERROR! Во время выделения памяти произошла ошибка\n");

        return;

    }

    temp->data = value; // инициализируем значение узла добавленным значением