Файл: Динамические структуры данных. Списки (Основные понятия).pdf

Рисунок 58 – Результат поиска существующего элемента

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

ЗАКЛЮЧЕНИЕ

В рамках данной работы была рассмотрена тема «Динамические структуры данных. Списки».

Первая глава работы носит теоретический характер. В ней описываются общие понятия, приводится классификация структур данных, а также рассматриваются динамические структуры.

Структура данных представляет собой множество элементов данных и связей, установленных между ними.

Понятие «физическая структура данных» характеризует способ физического размещен данных в памяти компьютера.

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

Динамические структуры данных – структуры, обладающие свойством изменчивости.

К динамическим структурам относят:

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

В рамках практической части разработаны класс линейного односвязного и циклического двусвязного списков на языке программирования высокого уровня С++, а также приложения, демонстрирующие работу с этими классами.

Основные функции, реализуемые в приложениях:

• вывод содержимого списка на экран;
• добавление элемента в начало списка;
• добавление элемента в конец списка;
• удаление последнего элемента списка;
• поиск элемента по значению;
• выход из программы.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Алексеев А.Ю. Динамические структуры данных: Учебно-методическое пособие / А.Ю. Алексеев, С.А. Ивановский, Д.В. Куликов – Петропавловск-Камчатский: КамчатГТУ, 2014. – 68 с.
2. Блинов И.Н. Java. Методы программирования: уч.-мет. пособие / И.Н. Блинов, В.С. Романчик. – Минск : издательство «Четыре четверти», 2013. – 896 с.
3. Бузыкова Ю.С. Языки и технологии программирования – Хабаровск : Изд-во Тихоокеан. гос. ун-та, 2014. – 44 с.
4. Давыдова Н.А. Программирование / Н.А. Давыдова, Е.В. Боровская. – М.: БИНОМ, 2015. – 241 с.
5. Далека В.Д. Модели и структуры данных. Учебное пособие. Харьков: ХГПУ, 2013. – 241 с.
6. Кадырова Г.Р. Основы алгоритмизации и программирования – Ульяновск : УлГТУ, 2014. – 95 с.
7. Ключарев А.А. Структуры и алгоритмы обработки данных / А.А. Ключарев, В.А. Матьяш, С.В. Щекин. – СПб.: Изд-во СПбГУАП, 2013. – 172 с.
8. Конова Е.А. Структуры данных. Программирование на языке С и С++ / Е.А. Конова, Г.А. Поллак, А.М. Ткачев. – Челябинск: Изд-во ЮУрГУ, 2014. – 106 с.
9. Кузниченко М.А. Динамические структуры данных: учебное пособие – Орск: Издательство ОГТИ, 2014. – 102 с.
10. Кумагина Е.А. Введение в структуры данных / Е.А. Кумагина, Н.Н. Чернышова. – Нижний Новгород: Изд-во ННГУ, 2016. – 36 с.
11. Латухина Е.А. Структуры данных и алгоритмы. – Архангельск: ИПЦ САФУ, 2013. – 42 с.
12. Мясников Е.В. Списки и деревья / Е.В. Мясников, А.Б. Попов. – Самара: Изд-во СГАУ им. С.П. Королева, 2015. – 24 с.
13. Назаренко П.А. Алгоритмы и структуры данных: учебное пособие. Самара: ПГУТИ, 2015. – 196 с.Третьяков Ю.А. Динамические структуры данных. – М.: Изд-во МГУ, 2012. – 24 с.
14. Обухович Т.М. Программирование. Паскаль: Учебное пособие для студентов направления «Информатика и вычислительная техника» / Рубцовский индустриальный институт. – Рубцовск, 2015. – 73 с.
15. Орлов С.А. Теория и практика языков программирования – СПб.: Питер, 2013. – 668 с
16. Полетаев И.А. Программирования на языке высокого уровня Паскаль – Издательство ППИ, 2015. – 159 с.
17. Прата С. Язык программирования С – М.: Издательский дом «Вильямс», 2013. – 960 с.
18. Серикова Н.В. Практическое руководство к лабораторному практикуму «Динамические структуры данных». Минск, 2012. – 62 с.
19. Фофанов О.Б. Алгоритмы и структуры данных. – Томск: Изд-во Томского политехнического университета, 2014. – 126 с.
20. Чулюков В.А. методы разработки программ (алгоритмы и структуры данных). – Воронеж: Изд-во ВГУ, 2014. – 154 с.

---

ПРИЛОЖЕНИЯ

Линейный односвязный список

Spisok.h

#pragma once

class Spisok

{

public: struct Node //описание узла - элемента списка

{

int value; //значение

struct Node *next; //ссылка на следующий элемент

} *head;

//конструктор

Spisok(int val);

Spisok();

//деструктор

~Spisok();

//добавление в начало

void AddAtBegin(int val);

//добавление в конец

void AddAtEnd(int val);

//удаление из конца

void Delete();

//очистка списка

void Drop();

//поиск по значению

int Search(int val);

//вывод на экран

void Show();

};

Spisok.cpp

#include <stdlib.h>

#include <stdio.h>

#include "Spisok.h"

Spisok::Spisok()

{

}

Spisok::Spisok(int val)

{

head = (Node*)malloc(sizeof(Node)); //выделяем память под элемент

head->value = val; //сохраняем значение

head->next = NULL; //обнуляем ссылку на следующий элемент

}

Spisok::~Spisok()

{

Node *temp = head;

while (head->next)

{

head = head->next;

free(temp);

temp = head;

}

free(head);

}

void Spisok::AddAtBegin(int val)

{

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

temp->value = val; //сохраняем значение

temp->next = head; //следующий элемент - бывший первый

head = temp; //переносим указатель первого элемента

}

void Spisok::AddAtEnd(int val)

{

Node *temp = head;

while (temp->next) //просматриваем список до конца

temp = temp->next;

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

temp = temp->next;

temp->value = val; //сохраняем значение

temp->next = NULL; //ссылка на следующий элемент = NULL т.к. добавление в конец

}

void Spisok::Delete()

{

Node *temp = head;

if (temp == NULL)

printf("List is empty!\n");

else

{

if (temp->next == NULL)

{

free(temp);

head = NULL;

}

else

{

while (temp->next->next)

temp = temp->next;

Node *buf = temp;

buf->next = NULL;

free(temp->next);

}

printf("Last element has been deleted!\n");

}

}

void Spisok::Drop()

{

Node *temp = head;

if (temp == NULL)

printf("List is empty!\n");

else

{

if (temp->next == NULL)

{

free(temp);

head = NULL;

}

else

{

while (temp->next->next)

{

Node *buf = temp;

temp = temp->next;

free(buf);

}

head = NULL;

}

printf("List was dropped!\n");

}

}

int Spisok::Search(int val)

{

Node *temp;

int pos = -1;

int i = 0;

temp = head;

if (temp == NULL) return pos;

while (temp->next) //просмотр всего списка

{

if (temp->value == val) //если значение найдено

{

pos = i; //сохраняем номер позиции

break;

}

else //если нет

{

temp = temp->next; //переходим к следующему элементу

i++;

}

}

if (temp->value == val) pos = i; //проверка последнего элемента

return pos; //возвращаем номер позиции или -1, если элемент не найден

}

void Spisok::Show() //функция вывода массива на экран

---

{

Node *temp;

system("cls"); //очистка экрана

if (head == NULL) //проверка - если список пуст

printf("List is empty!\n");

else

{

temp = head;

printf("List:\n");

while (temp->next != NULL) //просматриваем весь список

{

printf("%d ", temp->value); //выводим очередной элемент

temp = temp->next;

}

printf("%d\n", temp->value); //выводим последний элемент

}

system("pause"); //задержка экрана

}

main.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#include "Spisok.h"

int Menu() //функция показа меню

{

int choice;

system("cls");

printf("Menu\n");

printf("1. Show list\n");

printf("2. Add element at begin\n");

printf("3. Add element at end\n");

printf("4. Remove last element\n");

printf("5. Search element\n");

printf("6. Drop list\n");

printf("0. Exit\n");

printf("--------------------------------------------\n");

printf("Your choice: ");

scanf("%d", &choice); //осуществление выбора

return choice; //возврат выбранного значения

}

int getVal()

{

int val;

system("cls");

printf("Enter value: ");

scanf("%d", &val);

return val;

}

int main(int argc, char** argv) {

Spisok p;

p.head = NULL;

int n;

int choice = Menu();

while (choice != 0)

{

switch (choice)

{

case 1:

p.Show();

break;

case 2:

p.AddAtBegin(getVal());

system("cls");

printf("Element has been added!\n");

system("pause");

break;

case 3:

p.AddAtEnd(getVal());

system("cls");

printf("Element has been added!\n");

system("pause");

break;

case 4:

system("cls");

p.Delete();

system("pause");

break;

case 5:

n = p.Search(getVal());

system("cls");

if (n == -1) printf("No such element!\n");

else printf("Position = %d\n", n + 1);

system("pause");

break;

case 6:

system("cls");

p.Drop();

system("pause");

break;

default:

printf("Error!\nPress any key to continue...");

break;

}

choice = Menu();

}

return 1;

}

ПРИЛОЖЕНИЕ 2

Циклический двусвязный список

Spisok.h

#pragma once

class Spisok

{

public: struct Node //описание узла - элемента списка

{

int value; //значение

struct Node *next; //ссылка на следующий элемент

struct Node *back; //ссылка на предыдущий элемент

} *head;

//конструктор

Spisok(int val);

Spisok();

//деструктор

~Spisok();

//добавление в начало

void AddAtBegin(int val);

//добавление в конец

void AddAtEnd(int val);

//удаление из конца

void Delete();

//поиск по значению

int Search(int val);

//вывод на экран

void Show();

};

Spisok.cpp

#include <stdlib.h>

#include <stdio.h>

#include "Spisok.h"

Spisok::Spisok()

{

}

Spisok::Spisok(int val)

{

head = (Node*)malloc(sizeof(Node)); //выделяем память под элемент

head->value = val; //сохраняем значение

head->next = head; //зацикливаем список по прямой ссылке

head->back = head; //зацикливаемсписок по обратной ссылке

}

Spisok::~Spisok()

{

Node *temp = head;

while (head->next)

{

head = head->next;

free(temp);

temp = head;

}

free(head);

}

void Spisok::AddAtBegin(int val)

---

{

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

temp->value = val; //сохраняем значение

if (head != NULL)

{

temp->next = head;

head->back = temp;

Node *last = head; //ищем последний элемент

while (last->next != head)

last = last->next;

last->next = temp;

temp->back = last;

head = temp; //переносим указатель первого элемента

}

else

{

temp->next = temp;

temp->back = temp;

head = temp;

}

}

void Spisok::AddAtEnd(int val)

{

Node *temp = head;

if (head != NULL)

{

while (temp->next != head) //просматриваем список до конца

temp = temp->next;

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

temp = temp->next;

temp->value = val; //сохраняем значение

temp->next = head; //ссылка на следующий элемент = голове списка т.к. добавление в конец

head->back = temp;

}

else

{

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

temp->value = val; //сохраняем значение

temp->next = temp;

temp->back = temp;

head = temp;

}

}

void Spisok::Delete()

{

Node *temp = head;

if (temp == NULL)

printf("List is empty!\n");

else

{

while (temp->next->next != head)

temp = temp->next;

Node *buf = temp;

free(temp->next);

buf->next = head;

printf("Last element has been deleted!\n");

}

}

int Spisok::Search(int val)

{

Node *temp;

int pos = -1;

int i = 0;

temp = head;

if (temp == NULL) return pos;

while (temp->next != head) //просмотр всего списка

{

if (temp->value == val) //если значение найдено

{

pos = i; //сохраняем номер позиции

break;

}

else //если нет

{

temp = temp->next; //переходим к следующему элементу

i++;

}

}

if (temp->value == val) pos = i; //проверка последнего элемента

return pos; //возвращаем номер позиции или -1, если элемент не найден

}

void Spisok::Show() //функция вывода массива на экран

{

Node *temp;

system("cls"); //очистка экрана

if (head == NULL) //проверка - если список пуст

printf("List is empty!\n");

else

{

temp = head;

printf("List:\n");

while (temp->next != head) //просматриваем весь список

{

printf("%d ", temp->value); //выводим очередной элемент

temp = temp->next;

}

printf("%d\n", temp->value); //выводим последний элемент

}

system("pause"); //задержка экрана

}

main.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#include "Spisok.h"

int Menu() //функция показа меню

{

int choice;

system("cls");

printf("Menu\n");

printf("1. Show list\n");

printf("2. Add element at begin\n");

printf("3. Add element at end\n");

printf("4. Remove last element\n");

printf("5. Search element\n");

printf("0. Exit\n");

printf("--------------------------------------------\n");

printf("Your choice: ");

scanf("%d", &choice); //осуществление выбора

return choice; //возврат выбранного значения

}

int getVal()

{

int val;

system("cls");

printf("Enter value: ");

scanf("%d", &val);

return val;

}

int main(int argc, char** argv) {

Spisok p;

p.head = NULL;

int n;

---