русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Линейный список

Линейный список в информатике и программировании определяется как экземпляр абстрактного типа данных, что формализует концепцию упорядоченного множества элементов. Например, абстрактный тип данных для бестиповых, переменных списков можно определить с помощью конструктора и четырех операций:

  • конструктор для создания пустого списка;
  • операция определения пустоты списка;
  • операция для добавления элемента в начало списка (cons в Лиспе);
  • операция получения первого элемента списка (или «головы») списка (car в Лиспе);
  • операция для определения списка, состоящего из всех элементов списка кроме первого (или его «хвоста») (cdr в Лиспе).

Характеристики

По определению, список - это последовательность из N ? 0 элементов X [1], X [2], ... X [n], для которой выполняется следующее условие: если n 0 и X [1] - первый элемент в списке, а X [n] - последний, то k -й элемент расположен между X [k-1] и X [k +1] элементами для всех 1 k n.

С такими структурами данных выполняются следующие операции:

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

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

стек - линейный список, в котором операции сложения и удаления выполняются только на одном конце списка (верхушке стека). Принцип построения стека называют LIFO (англ. last in, first out).

очередь (односторонняя очередь) - линейный список, где операции сложения выполняются на одном конце (в голове очереди), а операции изъятия - на другом конце списка (в хвосте очереди). Принцип построения очереди называют FIFO (англ. first in, first out).

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

Просмотров: 3203

Оглавление: Компьютерная графика и информация в компьютерной сфере


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.