Представление линейных списков

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждения высшего образования
«Южный федеральный университет»

Инженерно-технологическая академия

Институт компьютерных технологий и информационной безопасности

Кафедра математического обеспечения и применения ЭВМ

[pic 1]

Лабораторная работа №1

по дисциплине

"Структуры и алгоритмы обработки данных"

на тему

"Представление линейных списков"

Выполнил:

студент группы КТбо1-7

Паревская К.В.

Проверил:

Преподаватель

Данилова А.А.

Таганрог 2020

Вариант № 7

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Для всех вариантов нужно реализовать меню со следующим минимальным набором

операций со списком:

1. инициализация пустого списка;
2. уничтожение списка с освобождением памяти;
3. добавление узла в голову списка;
4. добавление узла в хвост списка;
5. удаление узла из головы списка;
6. удаление узла из хвоста списка;
7. выдача текущего списка на экран.

Тип данных, хранящихся в узлах, выбирается по желанию студента. Метод

размещения списка (в динамической памяти или в массиве) также может быть выбран

произвольно.

Кроме того, в каждом варианте следует реализовать две дополнительные операции.

Вариант представления списка и дополнительные операции выбираются согласно номеру

варианта.

1) Циклический односвязный список с указателем на последний узел. Дополнительные

операции: a) инвертировать список (изменить порядок узлов на обратный); б)

перенести (не копируя) один список в хвост второго.

2) Циклический односвязный список с зацикливанием «через указатель».

Дополнительные операции: a) перенести (не копируя) все нечетные по порядку узлы в

отдельный список; б) добавить новый узел после узла с заданным значением данных.

3) Двусвязный линейный список. Дополнительные операции: a) добавить новый узел в

указанную позицию; б) поменять местами первый и последний узлы (требуется

поменять именно узлы, а не их значения).

4) Двусвязный циклический список. Дополнительные операции: a) добавить

(скопировать) один список в хвост второго; б) перенести (не копируя) все четные по

порядку узлы в отдельный список.

5) Циклический односвязный список с указателем на последний узел. Дополнительные

операции: a) поменять местами первый и второй (если он есть) узлы (требуется

поменять именно узлы, а не их значения); б) удалить узел с указанным порядковым

номером.

6) Циклический односвязный список с зацикливанием «через голову». Дополнительные

операции: a) добавить новый узел в указанную позицию; б) удалить узлы с заданным

значением данных.

7) Двусвязный линейный список. Дополнительные операции: a) удалить узлы с заданным

значением данных; б) инвертировать список (изменить порядок узлов на обратный).

8) Двусвязный циклический список. Дополнительные операции: a) добавить новый узел

перед узлом с заданным значением данных; б) удалить узел с указанным порядковым

номером.

ВЫПОЛНЕНИЕ ЗАДАНИЯ

#include <iostream>

using namespace std;

struct List

{

        List* next;

        List* prev;

        int data;

}*head = NULL;

//Инициализация

void Init(List** head)

{

        (*head) = NULL;

}

//Удаление списка с освобождением памяти

void Delete_And_Free_Memory(List** head)

{

        if (*head == NULL)

        {

                return;

        }

        List* p = *head;

        List* t;

        while (p)

        {

                t = p;

                p = p->next;

                delete t;

        }

        *head = NULL;

}

//Вывод списка на экран

void Print(List** head)