#import "../title_page_template.typ": title_page
#import "../layouts.typ": *

#set text(font: "New Computer Modern", size: 14pt)
#set page(margin: 2cm, paper: "a4")
#set heading(numbering: "1.")
#set figure(supplement: [Рисунок])
#set figure.caption(separator: [ -- ])

#title_page(7, [Линейные динамические списки])

#un_heading([Оглавление])

#outline(
  title: none
)

#pagebreak()

#set page(numbering: "1")
#set par(justify: true, first-line-indent: 1.25cm)

#head1([= Условие задачи])

#par(
  [#indent Задания моего персонального варианта (№22):]
  )

#par(
  [*Задание 1.* Разработать и реализовать программу управлению линейным однонаправленным списком в соответствии с условием задачи, определенной вариантом.]
)

#par(
  [*Задание 2.* Разработать и реализовать программу управлению линейным двунаправленным списком в соответствии с условием задачи, определенной вариантом.]
)

#head1([= Постановка задачи])

#par(
  [*Задание 1.* Дан список, узел которого хранит значение и количество вхождений этого значения (в исходном списке это значение равно 1).
1. Вставить символ в список, если этот символ уже есть в списке, то увеличить количество вхождений символа, если такого значения еще нет в списке, то добавить его в конец списка.
2. Удалить из списка узел с символом, который чаще всего встретился в списке.
3. Модифицировать список, переместив первые m узлов в конец списка.]
)

#par(
  [*Задание 2.* Системный каталог библиотечной автоматизированной системы хранит сведения о книгах фонда в двунаправленном списке. Сведения о принадлежности книги области знания хранит отдельный список, ссылка на который храниться в узле исходного списка соответствующей книги. Часть списка, начиная с узла с заданным номером (номер больше 1) и до конца списка, перенести в начало списка.]
)

#pagebreak()

#let tab(theme) = {
  set par(first-line-indent: 1.25cm, hanging-indent: 1.25cm)
  text([#theme #linebreak()])
}

#let method(num, head, pre, post, header) = {
  par(hanging-indent: 1.25cm, first-line-indent: 1.25cm, [
    #num #head #linebreak()
    Предусловие: #pre #linebreak()
    Постусловие: #post #linebreak()
    Заголовок: #header #linebreak()
  ])
}

#head1([= АТД задачи])

#head2([== АТД задания 1])

#head2([=== #raw("sList")])

#par(
  [
    АТД sList \ { \ 
    #tab([_Данные_ (описание свойств структуры данных задачи)])
    #tab([head -- указатель на головной элемент списка])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание списка],
      [values -- массив символов],
      [линейный однонаправленный список],
      [#raw("sList(std::vector<char> values)")]
    )

    #method(
      [2.],
      [Метод, осуществляющий вывод однонаправленного списка],
      [линейный однонаправленный список],
      [выведенные в консоль значения узлов списка],
      [#raw("print()")]
    )

    #method(
      [3.],
      [Метод, осуществляющие вставку узла в начало списка],
      [sym -- символ],
      [обновленный линейный однонаправленный список],
      [#raw("pushFront(char sym)")]
    )

    #method(
      [4.],
      [Метод, осуществляющий вставку узла в конец списка, если символ не встречается в списке, в противном случае увеличивающий число вхождений символа в данный список],
      [sym -- символ],
      [обновленный линейный однонаправленный список],
      [#raw("insert(char sym)")]
    )

    #method(
      [5.],
      [Метод, осуществляющий перемещение первых $m$ узлов в конец списка],
      [m -- число перемещаемых узлов],
      [обновленный линейный однонаправленный список],
      [#raw("replaceFirst(int m)")]
    )

    #pagebreak()

    #indent #method(
      [6.],
      [Метод, удаляющий узел с наибольшим числом вхождения определенного символа],
      [линейный однонаправленный список],
      [обновленный линейный однонаправленный список],
      [#raw("deleteFrequent()")]
    ) 

    #method(
      [7.],
      [Метод, осуществляющий поиск узла, содержащего заданный символ],
      [sym -- искомый символ],
      [указатель на узел (в случае, если узла с искомым символом в списке нет, возвращается нулевой указатель)],
      [#raw("inList(char sym)")]
    )

    #method(
      [8.],
      [Метод, возвращающий указатель на последний узел списка],
      [линейный однонаправленный список],
      [указатель на последний узел списка],
      [#raw("getTail()")]
    )

    #method(
      [9.],
      [Метод, возвращающий длину списка],
      [линейный однонаправленный список],
      [длина линейного однонаправленного списка],
      [#raw("size()")]
    ) \
    }
    
  ]
)

#head2([=== #raw("sNode")])

#par(
  [
    АТД sNode \ { \
    #tab([_Данные_ (описание свойств структуры данных задачи)])
    #tab([sym -- символ])
    #tab([occurrence -- число вхождений символа в список])
    #tab([next -- указатель на следующий узел списка])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание узла],
      [sym -- символ],
      [узел линейного однонаправленного списка],
      [#raw("sNode(char value)")]
    ) \
    }
  ]
)

#pagebreak()

#head2([== АТД задания 2])

#head2([=== #raw("dList")])

#par(
  [
    АТД dList \ { \
    #tab([_Данные_ (описание свойств структуры данных задачи)])
    #tab([head -- указатель на головной элемент списка])
    #tab([tail -- указатель на последний элемент списка])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание списка],
      [books -- массив, содержащий данные о книгах],
      [линейный двунаправленный список],
      [#raw("dList(std::vector<Book> books)")]
    )

    #method(
      [2.],
      [Метод, осуществляющие вставку узла в начало списка],
      [book -- структура, хранящая данные о книге],
      [обновленный список],
      [#raw("pushFront(Book book)")]
    )

    #method(
      [3.],
      [Метод, осуществляющий вывод данных о книге],
      [линейный двунаправленный список],
      [данные о книге: инвентарный номер, название, автор, год издания, области знаний],
      [#raw("printBook(dNode* node)")]
    )

    #method(
      [4.],
      [Метод, осуществляющий вывод данных о всех книгах каталога],
      [backwards -- булевый параметр, отвечающий за порядок вывода каталога (false -- список выводится слева направа, true -- список выводится справа налево)],
      [выведенная в консоль информация о всех книгах],
      [#raw("printCatalog(bool backwards = false)")]
    )

    #method(
      [5.],
      [Метод, осуществляющий перенос всех узлов списка, начиная с заданного номера, в начало списка], 
      [num -- номер, с которого начинается перенос],
      [обновленный список],
      [#raw("replaceAfter(int num)")]
    )

    #pagebreak()

    #indent #method(
      [6.],
      [Метод, осуществляющий поиск узла списка по ключу],
      [key -- ключ (в моем персональном варианте ключом считается инвентарный номер книги)],
      [указатель на узел спика],
      [#raw("find(int key)")]
    )

    #method(
      [7.],
      [Метод, возвращающий длину списка],
      [линейный двунаправленный список],
      [длина линейного двунаправленного списка],
      [#raw("size()")]
    ) \
    }
  ]
)

#head2([=== #raw("dNode")])

#par(
  [
    АТД dNode \ { \
    #tab([_Данные_ (описание свойств структуры данных задачи)])
    #tab([book -- структура, содержащая данные о книге])
    #tab([next -- указатель на следующий узел списка])
    #tab([prev -- указатель на предыдущий узел списка])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание узла],
      [book -- структура, содержащая данные о книге],
      [узел линейного двунаправленного списка],
      [#raw("dNode(Book book)")]
    ) \
    }
  ]
)

#pagebreak()

#head2([=== #raw("Book")])

#par(
  [
    АТД Book \ { \
    #tab([_Данные_ (описание свойств структуры данных задачи)])
    #tab([key -- $quote.angle.l.double$ключ$quote.angle.r.double$, инвентарный номер книги])
    #tab([year -- год издания книги])
    #tab([author -- автор книги])
    #tab([title -- название книги])
    #tab([fields -- список наименований областей знаний книги])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание структуры],
      [key -- инвентарный номер, year -- год издания, author -- автор, title -- название, fields -- наименования области знаний],
      [структура, содержащая информацию о книге],
      [#raw("Book(int key, int year std::string author, std::string title, std::vector<std::string> fields)")]
    ) \
    }
  ]
)

#head2([=== #raw("Fields")])

#par(
  [
    АТД Fields \ { \
    #tab([_Данные_ (описание свойств структуры данных задачи)])
    #tab([head -- указатель на головной элемент списка])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание списка],
      [fields -- массив, содержащий наименования областей знаний книги],
      [список областей знаний книги],
      [#raw("Fields(std::vector<std::string> fields)")]
    ) \
    }
  ]
)

#pagebreak()

#head2([=== #raw("Field")])

#par(
  [
    АТД Field \ { \
    #tab([field -- наименование области знаний книги])
    #tab([next -- указатель на следующий узел списка])
    #tab([_Операции_ (объявления операций)])

    #method(
      [1.],
      [Метод, осуществляющий создание узла],
      [field -- структура, содержащая наименование области знаний книги],
      [узел линейного однонаправленного списка],
      [#raw("Field(std::string field)")]
    ) \
    }
  ]
)

#pagebreak()

#head1([= Разработка и реализация задачи])

#head2([== Задание 1])

#head2([=== Структура узла])

#par(
  [
    #indent В соответствии с моим вариантом, структура данных, соответствующая узла однонаправленного списка, должна содержать:
    #enum(
      [Поле, хранящее символ (#raw("sym")).],
      [Поле, хранящее число вхождений символа в список (#raw("occurrence")). Подразумевается, что список не должен содержать узлов, значения полей #raw("sym") у которых равны.],
      [Поле, содержащее указатель на следующий узел списка (#raw("next")).]
    ) 
  ]
)

#head2([=== Изображение структуры списка для 5 элементов])

#par(
  [#indent Ниже приведено изображение списка, состоящего из 5 элементов (см. рис. 2).]
)

#figure(
  image(
    "images/s_node.png"
  ),

  caption: [Структура списка из 5 элементов]
)

#pagebreak()

#head2([=== Изображение операции добавления узла в начало списка])

#par(
  [#indent Ниже приведено изображение, показывающее операцию вставки узла в начало списка в случае, если поле #raw("sym") ни одного из узлов исходного списка не совпадает с полем #raw("sym") нового узла (см. рис. 3).]
)

#figure(
  image(
    "images/s_node_push_front.png"
  ),

  caption: [Операция добавления узла в начало списка]
)

#head2([=== Последовательность операторов, требующихся для добавления узла в начало списка])

#par(
  [
    #enum(
      [Проверка нового символа на вхождение в существующий список путем вызова метода #raw("inList"). Если символ уже встречается в списке, поле #raw("occurrence") узла, в котором встречается этот символ, увеличивается на 1. Иначе создается указатель на новый узел списка #raw("node").],
      [Полю #raw("next") узла по указателю #raw("node") присваивается значение указателя на головной элемент #raw("head").],
      [Указателю #raw("head") присваивается значение #raw("node").]
    )
  ]
)

#head2([=== Код программы])

#par(
  [1. Код файла #raw("s_list.h")]
)

#let base_path = "../../src/work_7/"

#let s_list_h = read(base_path + "singly_linked_list/headers/s_list.h")
#raw(s_list_h, lang: "cpp")

#par(
  [2. Код файла #raw("s_list.cpp")]
)

#let s_list_cpp = read(base_path + "singly_linked_list/source/s_list.cpp")
#raw(s_list_cpp, lang: "cpp")

#par(
  [3. Код файла #raw("s_node.h")]
)

#let s_list_h = read(base_path + "singly_linked_list/headers/s_node.h")
#raw(s_list_h, lang: "cpp")

#par(
  [4. Код файла #raw("s_node.cpp")]
)

#let s_list_cpp = read(base_path + "singly_linked_list/source/s_node.cpp")
#raw(s_list_cpp, lang: "cpp")

#par(
  [5. Код файла #raw("main.cpp")]
)

#let s_list = read(base_path + "singly_linked_list/main.cpp")
#raw(s_list, lang: "cpp")

#head2([=== Тестирование])

#head2([==== #raw("insert")])

#par(
  [#indent 1. Исходный список: 'c' $->$ 'o' $->$ 'r' $->$ 'n'.
  Вставляемое значение: 'y'. 
  Результат выполнения метода приведен ниже(см. рис. 3, здесь и далее в первой строке вывода содержится состояние списка до выполнения метода, во второй строке -- после выполнения метода)]
)

#figure(
  image(
    "images/insert_test_1.png",
    width: 60%,
  ),

  caption: [Тест №1]
)

#pagebreak()

#par(
  [#indent 2. Исходный список тот же. 
  Вставляемое значение: 'o'. 
  Результат выполнения метода приведен ниже (см. рис. 4)]
)

#figure(
  image(
    "images/insert_test_2.png",
    width: 60%,
  ),

  caption: [Тест №2]
)

#head2([==== #raw("deleteFrequent")])

#par(
  [#indent 3. Исходный список: 'w' $->$ 'o' $->$ 'w'. 
  Результат выполнения метода приведен ниже (см. рис. 5)]
)

#figure(
  image(
    "images/delete_frequent_test.png",
    width: 60%,
  ),

  caption: [Тест №3]
)

#head2([==== #raw("replaceFirst")])

#par(
  [#indent 4. Исходный список: 'v' $->$ 'i' $->$ 's' $->$ 't' $->$ 'r' $->$ 'a'. Количество перемещаемых символов: 3. Результат выполнения метода приведен ниже (см. рис. 6).]
)

#figure(
  image(
    "images/replace_first_test_1.png",
    width: 60%,
  ),

  caption: [Тест №4]
)

#par(
  [#indent 5. Исходный список: 'r' $->$ 'i' $->$ 'z' $->$ 'z'. Количество перемещаемых символов: 3. Результат выполнения метода приведен ниже (см. рис. 7).]
)

#figure(
  image(
    "images/replace_first_test_2.png",
    width: 60%,
  ),

  caption: [Тест №5]
)

#pagebreak()

#head2([== Задание 2])

#head2([=== Структура узла])

#par(
  [
    #indent В соответствии с моим вариантом, структура данных, соответствующая узла двунаправленного списка, должна содержать:
    #enum(
      [Поле, хранящее данные о книге (#raw("book"), данное поле представляет собой отдельную структуру #raw("Book")).],
      [Поле, содержащее указатель на следующий узел списка (#raw("next")).],
      [Поле, содержащее указатель на предыдущий узел списка (#raw("prev")).]
    )
    #indent Структура #raw("Book") содержит инвентарный номер книги, являющийся ее ключом (#raw("key")), год издания книги (#raw("year")), имя автора книги (#raw("author")), название книги (#raw("title")), а также список областей знаний книги (#raw("fields")), представленный линейным однонаправленным списком, который в свою очередь представлен структурой #raw("Fields")
  ]
)

#par(
  [Структура #raw("Fields") содержит указатель на головной узел списка (#raw("head")), представленный структурой #raw("Field")]
)

#par(
  [Структура #raw("Field") содержит наименование области знаний книги (#raw("field")) и указатель на следующие узел списка (#raw("next")).]
)

#head2([=== Изображение структуры списка для 5 элементов])

#par(
  [#indent Ниже приведено изображение списка, состоящего из 5 элементов (см. рис. 3).]
)

#figure(
  image(
    "images/d_node.png"
  ),

  caption: [Структура списка из 5 элементов]
)

#pagebreak()

#head2([=== Изображение операции добавления узла в начало списка])

#par(
  [#indent Ниже приведено изображение, показывающее операцию вставки узла в начало списка (см. рис. 4).]
)

#figure(
  image(
    "images/d_node_push_front.png"
  ),

  caption: [Операция добавления узла в начало списка]
)

#head2([=== Последовательность операторов, требующихся для добавления узла в начало списка])

#par(
  [
    #enum(
      [Создание указателя на новый узел списка #raw("newNode").],
      [Полю #raw("next") узла по указателю #raw("newNode") присваивается значение указателя на головной узел #raw("head")],
      [Полю #raw("prev") узла по указателю #raw("head") присваивается значение #raw("newNode")],
      [Указателю #raw("head") присваивается значение #raw("newNode").]
    )
  ]
)

#head2([=== Код программы])

#par(
  [1. Код файла #raw("d_list.h")]
)

#let d_list_h = read(base_path + "doubly_linked_list/headers/d_list.h")
#raw(d_list_h, lang: "cpp")

#par(
  [2. Код файла #raw("d_list.cpp")]
)

#let d_list_cpp = read(base_path + "doubly_linked_list/source/d_list.cpp")
#raw(d_list_cpp, lang: "cpp")

#par(
  [3. Код файла #raw("d_node.h")]
)

#let d_node_h = read(base_path + "doubly_linked_list/headers/d_node.h")
#raw(d_node_h, lang: "cpp")

#par(
  [4. Код файла #raw("d_node.cpp")]
)

#let d_node_cpp = read(base_path + "doubly_linked_list/source/d_node.cpp")
#raw(d_node_cpp, lang: "cpp")

#par(
  [5. Код файла #raw("book.h")]
)

#let book_h = read(base_path + "doubly_linked_list/headers/book.h")
#raw(book_h, lang: "cpp")

#par(
  [6. Код файла #raw("book.cpp")]
)

#let book_cpp = read(base_path + "doubly_linked_list/source/book.cpp")
#raw(book_cpp, lang: "cpp")

#par(
  [7. Код файла #raw("fields.h")]
)

#let fields_h = read(base_path + "doubly_linked_list/headers/fields.h")
#raw(fields_h, lang: "cpp")

#par(
  [8. Код файла #raw("fields.cpp")]
)

#let fields_cpp = read(base_path + "doubly_linked_list/source/fields.cpp")
#raw(fields_cpp, lang: "cpp")

#par(
  [9. Код файла #raw("field.h")]
)

#let field_h = read(base_path + "doubly_linked_list/headers/field.h")
#raw(field_h, lang: "cpp")

#par(
  [10. Код файла #raw("d_list.cpp")]
)

#let field_cpp = read(base_path + "doubly_linked_list/source/field.cpp")
#raw(field_cpp, lang: "cpp")

#par(
  [11. Код файла #raw("main.cpp")]
)

#let d_list_h = read(base_path + "doubly_linked_list/main.cpp")
#raw(d_list_h, lang: "cpp")

#pagebreak()

#head2([=== Тестирование])

#par(
  [#indent 1. Исходный список содержит информацию о 4-х произвольных книгах. Переносятся в начало все книги, начиная со 2.]
)

#figure(
  image(
    "images/replace_after_test_1.png",
    width: 60%,
  ),

  caption: [Тест №1]
)

#pagebreak()

#par(
  [#indent 2. Исходный список содержит информацию о тех же самых книгах. Производится попытка перенести в начало книги, начиная с 5.]
)

#figure(
  image(
    "images/replace_after_test_2.png",
    width: 60%,
  ),

  caption: [Тест №1]
)

#pagebreak()

#head1([= Выводы])

#par(
  [#indent В результате выполнения самостоятельной работы были получены умения и навыки по созданию динамически формируемых структур данных средствами языка С++, а также применению линейных списков в реализации алгоритмов.]
)

#pagebreak()

#head1([= Список информационных источников])

#par(
  [
    1. #internet(
    [Структуры данных: связный список / Хабр], 
    [habr.com], 
    [https://habr.com/ru/articles/717572/], 
    [06.05.24]
    ).
  ]
)

#par(
  [
    2. #internet(
      [Linked List Data Structure -- GeeksforGeeks],
      [geeksforgeeks.com],
      [https://www.geeksforgeeks.org/data-structures/linked-list/],
      [06.05.24]
    )
  ]
)
