Лабораторная работа1. Лабораторная работа 1. Линейный однонаправленный список
 Скачать 84 Kb.
|
|
Лабораторная работа №1. Линейный однонаправленный список. Цель работы: Ознакомление с организацией линейного однонаправленного списка. Программирование основных операций доступных для линейного однонаправленного списка. Теоретическая часть Линейные списки. Наиболее простой способ организовать структуру данных, состоящую из некоторого множества элементов – это организовать линейный список. Список – это структура данных, представляющая собой логически связанную последовательность элементов списка. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей, и в зависимости от их количества в элементах различают однонаправленные и двунаправленные линейные списки. Линейный однонаправленный список В этом списке любой элемент имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем у последнего элемента.  Линейный однонаправленный список имеет только один указатель в элементах. Это позволяет минимизировать расход памяти на организацию такого списка. Однако это позволяет осуществлять переходы между элементами только в одном направлении, что зачастую увеличивает время, затрачиваемое на обработку списка. Описание класса элемента линейного однонаправленного списка: Для работы с элементов линейного однонаправленного списка будем использовать следующий класс:  Описание класса линейного однонаправленного списка: Для работы с линейным однонаправленным списком будем использовать следующий класс:  Объявление списка в основной программе будет следующим:  Основные операции, осуществляемые с линейным однонаправленным списком: – вставка нового элемента; – просмотр всего списка; – поиск элемента; – удаление элемента; – очистка всего списка. Организация функций списка выполним с помощью методов класса однонаправленный линейный список. Вставка нового элемента Вставка первого и последующих элементов списка отличаются друг от друга. Поэтому приводится два алгоритма вставки первого элемента и последующего. Вставка первого элемента (вставка в начало списка): В качестве параметра передается число для заполнения поля данных. В начале, необходимо создать новый элемент списка, в который записать поле данных. После этого необходимо предусмотреть проверку на пустоту списка. Если список пуст, то новый элемент сделать первым. Иначе первый и созданный элемент поменять местами. Пример функции вставки первого элемента в список:  Пример вызова метода вставки первого элемента в основной программе:  Вставка элемента справа относительно текущего элемента списка В качестве параметров передаются поле-данное для заполнения создаваемого элемента и текущий элемент списка, который передаётся в функцию по ссылке. Если список пуст, то вызвать функцию вставки первого элемента, после чего текущий элемент сделать первым. Иначе создать новый элемент, заполнить его данными и поменять местами с текущим элементом. После всего перезаписать текущий элемент. Пример функции вставки последующего элемента:  Просмотр списка. Функция просмотра списка заключается в последовательном просмотре всех элементов списка с выводом на экран до тех пока не дошли до конца списка: Пример функции просмотра элементов списка:  Поиск элемента списка. Операция поиска элемента в списке заключается в последовательном просмотре всех элементов списка до тех пор, пока текущий элемент не будет содержать заданное значение или пока не будет достигнут конец списка. В последнем случае функция возвращает пустой указатель. Входными параметрами являются значение, которое должен содержать искомый элемент. В качестве выходного параметра передается найденный элемент или присваивается null, если элемента в списке нет. Таким образом, функция возвращает найденный элемент или на пустой элемент. Пример функции поиска элемента:  Основная программа  Удаление элемента списка. Операция удаления элемента линейного однонаправленного списка осуществляет удаление элемента, на который установлен указатель текущего элемента. После удаления указатель текущего элемента устанавливается на предшествующий элемент списка, или на новое начало списка, если удаляется первый. Алгоритмы удаления первого и не первого элементов списка отличаются друг от друга. Поэтому в процедуре, реализующую данную операцию, осуществляется проверка, какой элемент удаляется, и далее реализуется соответствующий алгоритм удаления: Пример функции удаления текущего элемента.  Очистка всего списка. Очистка списка заключается в организации цикла до тех пор пока указатель на первый элемент списка не станет равным null. Переход к следующему элементу делается через специально созданный временный элемент. Пример кода функции.  Контрольные вопросы: Однонаправленный линейный список. Функция вставки первого элемента в список. Функция вставки не первого элемента в список. Функция просмотра всех элементов списка. Функция удаления элемента из списка. Функция очистки списка. Функция поиска элемента в списки по информационному полю. Порядок выполнения лабораторной работы: Ознакомиться и выполнить общую часть лабораторной работы; Выполнить задания в соответствии с вариантом (вариант берётся по номеру журнале); Показать результаты работающей программы преподавателю; На отчёт предоставить: Титульный лист; Листинг программы с комментариями согласно номеру варианта. Ответить на контрольные вопросы. Практическая часть. Индивидуальные задания. Во всех вариантах необходимо: Организовать список, состоящий из 10 элементов вводимых с клавиатуры, через функцию вставки первого элемента в список. Организовать функцию просмотра всего списка элементов. Организовать функцию вставки элемента справа относительно текущего. Организовать функцию поиска элемента в списке. Организовать функцию удаления элемента из списка. Организовать функцию очистки списка. Остальные функции реализовать в соответствии с вариантом. Организовать однонаправленный линейный список с функцией поиска максимального элемента списка. Организовать однонаправленный линейный список с функцией вставки элемента в список с заменой текущего элемента. Организовать однонаправленный линейный список с функцией вставки элемента в список справа от текущего элемента. Организовать однонаправленный линейный список с функцией вставки элемента в список слева от текущего элемента. Организовать однонаправленный линейный список с функцией вставки элемента в конец списка. Организовать однонаправленный линейный список с функцией поиска минимального элемента в списке. Организовать однонаправленный линейный список с функцией вывода отдельного элемента списка на экран по его порядковому номеру в списке. Организовать однонаправленный линейный список с функцией добавления нового элемента в список каждый раз справа от первого элемента. Организовать однонаправленный линейный список с функцией добавления нового элемента в список каждый раз слева от последнего элемента. Организовать однонаправленный линейный список с функцией вывода на экран только четных элементов списка. Организовать однонаправленный линейный список с функцией удаления диапазона значений из списка (дан первый номер и последний номер элементов, которые необходимо удалить из списка). Организовать однонаправленный линейный список с функцией вывода на экран только положительных элементов списка. Организовать однонаправленный линейный список с функцией удаления из списка четных элементов списка. Организовать однонаправленный линейный список с функцией удаления из списка элементов списка стоящих на нечётных местах. Организовать однонаправленный линейный список с функцией удаления из списка элементов списка стоящих на чётных местах. Организовать однонаправленный линейный список с функцией удаления из списка элементов кратных трём. Организовать однонаправленный линейный список с функцией вывода на экран элементов больших первого элемента. Организовать однонаправленный линейный список с функцией вывода на экран элементов больших последнего элемента. Организовать однонаправленный линейный список с функцией вывода на экран элементов меньших последнего элемента. Организовать однонаправленный линейный список с функцией вывода на экран элементов меньших первого элемента. |