что такое линейный список
Линейный список
Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой.
В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных.
На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список».
К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и четырёх основных операций:
Характеристики
Реализации
См. также
Полезное
Смотреть что такое «Линейный список» в других словарях:
линейный список — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN linear list … Справочник технического переводчика
Список (значения) — Список письменный перечень, число, состав; документ, содержащий перечень каких либо сведений; в переносном смысле буквальное, точное воспроизведение, копия; рукописная копия древнего памятника письменности. Список в информатике и… … Википедия
Список — О списках в Википедии см. руководство Википедия:Списки Список письменный перечень, число, состав; документ, содержащий перечень каких либо сведений; в переносном смысле буквальное, точное воспроизведение, копия; рукописная копия… … Википедия
Список (информатика) — У этого термина существуют и другие значения, см. Список. В информатике, список (англ. list) это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного… … Википедия
Список улиц Иваново — Содержание 1 0 9 2 А 3 Б 4 В … Википедия
Список улиц Кирова — Список улиц муниципального образования «Город Киров»[1]. Продолжением является Реестр населённых пунктов МО «Город Киров». Легенда … Википедия
Линейный — название населённых пунктов: Россия Линейный посёлок городского типа в составе города Волгоград Волгоградской области. Линейный посёлок в Юргинском районе Кемеровской области … Википедия
Список улиц Минска — Список улиц Минска … Википедия
Список военных кораблей Азовского флота — Корабль «Гото Предестинация» В связи с подготовкой Петра I к военным действиям против Османской империи к концу XVII века возникла необходимость в строительстве регулярного русского военно морского флота (Азовского флота). 20 октября 1696 … Википедия
Список улиц города Можги — Содержание 1 0 9 2 А Ж 3 З К … Википедия
Реализация односвязного списка на c++
Эта картинка демонстрирует, как будет выглядеть односвязный список.
Реализация узла
Значение, которое будет задавать пользователь
Указатель на следующий элемент (по умолчанию nullptr)
Реализация односвязного списка
Указатель на первый узел
Указатель на последний узел
Функция проверки наличия узлов в списке
Функция добавления элемента в конец списка
Функция печати всего списка
Функция поиска узла в списке по заданному значению
Функция удаления первого узла
Функция удаления последнего узла
Функция удаления узла по заданному значению значению
Функция обращения к узлу по индексу (дополнительная функция)
Реализация 1-3 пункта
Функция проверки наличия узлов в списке
Функция добавления элемента в конец списка
Здесь надо рассмотреть два случая:
В обоих случаях надо создать сам узел со значением, которое мы передали в эту функцию.
Первый случай:
Здесь нам как раз пригодиться функция проверки наличия узлов. Если список пустой, тогда мы присваиваем указателю на первый узел и последний узел указатель на новый узел и выходим из функции.
Второй случай:
Нам уже не нужно проверка наличия узлов в списке, так как если первый случай не происходит, то в списке есть узлы. Раз мы добавляем в конец, надо указать, что новый узел стоит после последнего узла. Затем мы меняем значения указателя last.
Теперь в список можно добавлять элементы.
Функция печати всего списка
Тест уже написанных функций
Код который мы написали:
Функция поиска узла в списке по заданному значению
Также делаем проверку is_empty() и создаём указатель p на первый узел
Обходим список, пока указатель p не пустой и пока значение узла p не равно заданному значению. После цикла возвращаем наш узел
Функция удаления первого узла
Функция удаления последнего узла
Конец списка одновременно и начало
Когда размер списка больше одного
Первый случай:
Сравниваем указатель на первый узел и указатель на последний узел, если они равны, то вызываем функцию удаления первого узла.
Второй случай:
Функция удаления узла по заданному значению значению
Делаем проверку is_empty(). И рассматриваем уже три случая:
Узел, который нам нужен, равен первому
Узел, который нам нужен, равен последнему
Когда не первый и не второй случаи
Первый случай:
Сравниваем значение первого узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления первого узла.
Второй случай:
Сравниваем значение последнего узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления последнего узла.
Третий случай:
Функция обращения к узлу по индексу
Для этой функции надо перегрузить оператор []
Тест программы
Заключение
Вот Вы и научились реализовывать односвязный список, и, надеюсь, стали лучше его понимать.
Линейный односвязный список
Вы будете перенаправлены на Автор24
Линейный односвязный список — это динамическая структура данных, в которой каждый элемент связан со следующим элементом с помощью специального указателя.
Введение
Под связным списком понимается основная структура данных, которая имеет динамический характер и состоит из узлов. Любой узел состоит из информации и ссылок («связок») на следующие и/или расположенные ранее узлы списка. У связного списка имеется одно очень существенное достоинство по сравнению с массивами и это гибкая структура. Расположение компонентов связного списка не обязательно соответствует их порядковой нумерацией, хранящейся в компьютере, а система прохождения списка определяется в явной форме связями внутри списка.
Линейный односвязный список
Линейным односвязным списком называется организация данных, которые состоят из однотипных компонентов, имеющих последовательные связи друг с другом при помощи указателей. У каждого компонента из списка имеется указатель на последующий компонент. У конечного элемента списка указатель указывает на нуль. Начальным в списке расположен компонент, на который не ссылаются никакие указатели. А указатель каждого узла ведёт на соседний узел списка. Если список односвязный, то движение внутри списка возможно лишь в направлении окончания списка. Выяснить адрес компонента, расположенного ранее, по данным текущего узла, не представляется возможным. В дисциплине информатика под линейным списком понимается абстрактный вид информационных данных, который формализует термин упорядоченных данных в коллекции. Обычно, линейный список можно организовать в виде массива или связного списка. Бывают моменты, когда понятие списка в произвольной трактовке применяется в виде синонима связного списка. Например, абстрактный тип данных нетипичного, с возможностью изменения, списка определяется в виде набора из конструктора алгебраического типа данных и базовых процедур:
Готовые работы на аналогичную тему
Основные характеристики линейных односвязных списков
К основным характеристикам линейных односвязных списков относятся:
Линейный односвязный список в языке Си
использование односвязного списка:
Одной из модификаций связного списка считается список, который замкнут в кольцо. То есть представляет собой замкнутый цикл. По структуре он бывает односвязный или двусвязный. В конечном компоненте замкнутого списка содержится указание на начальный компонент, в котором, в свою очередь, при двусвязном списке может быть указатель на конечный компонент. Обычно, такое построение основывается на линейном списке, в котором не должно быть ссылок на нуль. Есть ещё списки в виде цикла, где выделяется головной элемент. Это значительно облегчает полное прохождение списка.
Преимущества и недостатки линейного односвязного списка
Можно отметить следующие основные преимущества:
Основные проблемные моменты связного списка определяются их основным свойством, а именно последовательным доступом к информационным данным:
Добавление узла в односвязный линейный список
Операция формирования нового узла в списке имеет два аргумента:
Блок-схема формирования нового узла представлена в следующем виде:
Рисунок 1. Блок-схема формирования нового узла. Автор24 — интернет-биржа студенческих работ
Процесс добавления узла в линейный односвязный список состоит из следующих этапов:
Динамические структуры данных: однонаправленные и двунаправленные списки
Цель лекции: изучить понятия, классификацию и объявление списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.
Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.
В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.
Однонаправленные (односвязные) списки
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа поле ; адресное поле ; >;
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка.
Информационных полей может быть несколько.
Основными операциями, осуществляемыми с однонаправленными списками, являются:
Особое внимание следует обратить на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.
Рассмотрим подробнее каждую из приведенных операций.
Для описания алгоритмов этих основных операций используется следующее объявление:
Создание однонаправленного списка
Печать (просмотр) однонаправленного списка
Что такое линейный список
«Щас по списку и пойдем. »
Реальное многообразие структур данных базируется всего на двух основных способах получения адреса хранимого элемента: вычисление (массив) и хранение (указатель). До сих пор основной компонентой структуры данных являлся массив (обычный массив, массив указателей). Если же попытаться построить структуру данных, исходя только из указателей, то получается цепочка (последовательность) элементов, содержащих указатели друг на друга. В простейшем случае она может быть линейной (список), в более сложных случаях – ветвящейся (деревья, графы). Итак, список – линейная последовательность элементов, каждый из которых содержит указатели (ссылается) на своих соседей.
рис. 63-1. Списковая структура
Сразу же отметим основную особенность: физическое размещение в памяти элементов списка не имеет никакого значения, все определяется наличием ссылок на него в других элементах и извне. У массива всегда есть «начало». У списка по определению отсутствует фиксированная привязка к памяти. Перечислим основные релятивистские свойства списка :
· элемент списка доступен в программе через указатель. «Смысл» этого указателя отражает функциональное назначение элемента списка в программе: первый, последний, текущий, предыдущий, новый и т.п.. Между указателем и элементом списка имеется такая же взаимосвязь, как между индексом в массиве и элементом массива;
· в программе список задается посредством заголовка – указателя на первый элемент списка;
· порядок следования элементов определяется последовательностью связей между элементами. Изменение порядка следования элементов (вставка, удаление) осуществляются изменением переустановкой указателей на соседние элементы.
· список удобен для использования именно как динамическая структура данных: элементы списка обычно создаются как динамические переменные, а связи между ними устанавливаются программно (динамически);
Отсюда следует, что преимущества списков проявляются в таких структурах данных, где операции изменения порядка превалируют над операциями доступа и поиска.
Определение списка и работа с ним
Повторим все то же самое, но уже в терминах языка программирования. Начнем с элемента списка. Он является составной (структурированной) переменной, содержащей собственно хранимые данные и указатели на соседей:
struct elem // определение структурированного типа
elem *next; // единственный указатель или
elem *next,*pre v ; // два указателя или
elem *links[10]; // ограниченное количество указателей (не больше 10) или
elem **plinks; // произвольное количество указателей (внешний МУ)
Переменная такого типа может содержать одну, две, не более 10 и произвольное (динамический массив) количество указателей на аналогичные переменные. Но это еще не список, а описание его составляющих (элементов) как типа данных. Из него следует только, что каждый из них ссылается на аналогичные элементы. Никак нельзя определить ни количества таких переменных в структуре данных, ни характера связей между ними (последовательный, циклический, произвольный). Следовательно, конкретный тип структуры данных (линейный список, дерево, граф) зависит от функций, которые с ней работают. Значит, структура данных «зашита» не столько в этом определении, сколько в алгоритмах, работающих с этим типом.
Списковые структуры данных обычно являются динамическими по двум причинам:
· сами переменные таких структур создаются как динамические переменные, то есть количество их может быть произвольным;
· количество связей между переменными и их характер также определяются динамически в процессе работы программы.
В зависимости от связей списки бывают следующих видов:
Оставим пока за кадром вопрос, а как же создаются списки. Ибо в динамической структуре данных мы попадаем в замкнутый круг: чтобы работать со структурой данных, необходимо ее создать, а при создании нужно знать технологические приемы работы с ней.