Файл: Отчет по лабораторной работе 9 по дисциплине Программирование.docx

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра Вычислительной техники

отчет

по лабораторной работе № 9

по дисциплине «Программирование»

по теме: «Линейные двусвязные списки»

Студент гр. 2308		Мелихов М. А.
Преподаватель		Аббас С. А. М.

Санкт-Петербург

2023

Цель работы.

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

Задание (вариант 14).

Перепроектировать структуру, созданную при выполнении лабораторной работы №7 (по выбранной предметной области), так, чтобы одно из информационных полей, содержащих характеристику группы объектов (издательство, модель, тип и т. п.), стало ссылкой на элемент двусвязного линейного списка и разработать подалгоритм вывода значений заданного информационного поля элементов двусвязного списка в прямом или обратном направлении по желанию пользователя с одновременным удалением последнего выводимого на экран элемента. Постановка задачи и описание решения.

Постановка задачи и описание решения.

Для выполнения поставленной задачи мы заведем текстовый файл формата .csv, который предварительно наполним строками. В каждой строке файла через «;» будут находиться значения для соответствующих полей нашей структуры.

Создадим структуру и тип данных на основе этой структуры через «typedef». Надо отметить, что помимо поля-указателя на следующий элемент списка, добавится еще одно поле-указатель на предыдущий элемент списка для формирования линейного двусвязного списка.

Построчно читая файл, делим его по разделителю и добавляем соответствующие значения в поля структур. Кроме того, создавая каждый «элемент списка», то есть новую структуру, мы будем связывать ее с предыдущим элементом списка через поля-указатели «next» и «prev».

Для вывода элементов списка в прямом и обратном порядке разработаем две функции, которые будут в цикле выводить значение элемента списка и получать следующий элемент через указатель «prev» или «next» в зависимости от порядка вывода. Кроме того, эти функции будут возвращать указатель на последний выведенный элемент списка.

Далее необходимо реализовать функцию, которая будет удалять элемент списка. Причем, надо заметить, что всегда удаляться будут только первый или последний элементы списка, поэтому достаточно реализовать только две проверки. Функция переопределяет значения head->first или head->last в зависимости от того, первый или последний элемент удаляется, и очищать динамическую память удаляемого элемента. Таким образом элемент удаляется из списка.

Описание функций.

№	Имя	Возвращаемый тип	Назначение
1	main()	int	Главная функция
2	init_head()	head*	Инициализация «головы» списка
3	create_node(char** parts)	node*	Инициализация и создание элемента списка
4	remove_node(node* node)	void	Очистка памяти при удалении элемента списка
5	add_first(head* head, node* new_node)	void	Привязка первого элемента списка к «голове»
6	add_last(head* head, node new_node, node* prev_node)	void	Добавление элемента в конец списка
7	init_parts()	char**	Создание parts и аллоцирование памяти
8	clear_parts(char** parts)	void	Освобождение памяти parts
9	split(char** parts, char* str, char* sep)	void	Деление строки на двумерный массив строк parts
10	get_string(file* file)	char**	Считывание строки из файла и деление на части
11	straight_output(head* head)	Node*	Вывод таблицы в прямом порядке
12	reverse_output(head* head)	Node*	Вывод в обратном порядке
13	remove_elem(head* head, Node* elem)	void	Удаление первого элемента с начала или конца

Описание переменных

Функция main()

№	Имя	Тип	Назначение
1	file	FILE*	Указатель на файл
2	parts	char**	Двумерный список строк после деления строки из файла
3	i, j, num	int	Служебные переменные-счётчики
4	mode	char	Значение для выбора режима работы программы из меню
5	ph	Head*	Указатель на структуру Head
6	p1	Node*	Указатель на структуру - элемент списка - Node
7	p	Node*	Указатель на структуру – элемент списка для добавления элементов в конец списка в цикле
8	prev_p	Node*	Указатель на структуру – элемент списка для предыдущего заданному
9	del_elem	Node*	Указатель на структуру – элемент списка, который нужно удалить из списка

Функция init_head()

№	Имя	Тип	Назначение
1	head_pointer	Head*	Указатель на «голову»

Функция create_node()

№	Имя	Тип	Назначение
1	new_node	Node*	Указатель на структуру – элемент списка

Функция init_parts()

№	Имя	Тип	Назначение
1	parts	char**	Массив строк после деления строки из файла
2	j	int	Служебная переменная-счетчик

Функция split()

№	Имя	Тип	Назначение
1	part	char*	Строка для хранения одного поля после деления строки из файла
2	i	int	Служебная переменная-счетчик

Функция get_string()

№	Имя	Тип	Назначение
1	entry	char*	Строка для хранения строки из файла
2	parts	char**	Массив строк после деления строки из файла
3	sep	char*	Строка-разделитель

Функция straight_output()

№	Имя	Тип	Назначение
1	elem	Node*	Указатель на элемент массива для вывода в цикле
2	i, num	int	Служебные переменные-счетчики

Функция reverse_output()

№	Имя	Тип	Назначение
1	elem	Node*	Указатель на элемент массива для вывода в цикле
2	i, num	int	Служебные переменные-счетчики