Что такое список в программировании

• Модуль csv - чтение и запись CSV файлов
• Создаём сайт на Django, используя хорошие практики. Часть 1: создаём проект
• Онлайн-обучение Python: сравнение популярных программ

• Книги о Python
• GUI (графический интерфейс пользователя)
• Курсы Python
• Модули
• Новости мира Python
• NumPy
• Обработка данных
• Основы программирования
• Примеры программ
• Типы данных в Python
• Видео
• Python для Web
• Работа для Python-программистов

• Сделай свой вклад в развитие сайта!
• Самоучитель Python
• Карта сайта
• Отзывы на книги по Python
• Реклама на сайте

Программирование в "Эврике"

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

A=[1,2,3,4,5] B=["У лукоморья","дуб зеленый"] C=["one",1,1.0,"1"]

В этом примере переменная A — это список из 5 элементов, являющихся целыми числами, B — это список из двух элементов, являющихся строками, а C — это список из 4 элементов: строки "one" , целого числа 1 , действительного числа 1.0 и строки "1" (и все это — различные объекты).

Во многом списки похожи на множества в математике, их главное отличие в том, что списки могут содержать повторяющиеся элементы и элементы списка упорядочены. Можно задать и пустой список, не содержащий элементов: A=[] .

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

Воспользуемся списком для решения задачи нахождения суммы большого количества чисел:

A=input("Введите список чисел: ") S=0 for f in A: S=S+f print "Сумма элементов списка", A, "равна", S

Эта программа сначала просит пользователя ввести список чисел, затем переменной S присваивается значение 0 . В эту переменную мы будем осуществлять суммирование всех элементов списка, организовав цикл по переменной f , принимающей все значение из введенного списка и увеличивая внутри списка значение переменной S на f .

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

Во многих языках программирования структуры данных, наиболее близкие спискам в Питоне, называются .

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

Выше рассказывалось, что список можно задать перечислив его элементы в квадратных скобках через запятую, либо при помощи функции input , если пользователь введет список в таком же виде, либо можно создать список при помощи функции range . Например, если необходимо, чтобы переменная A была списком из n элементов, это можно сделать при помощи присваивания A=range(n) . Распечатать элементы массива можно при помощи инструкции print .

Внимание! Если при вводе списка не заключить его в квадратные скобки, а просто перечислить его элементы через запятую, то будет создан объект, называемый кортежем. Его главное отличие от списков заключается в том, что элементы кортежа нельзя изменять. При попытке присвоить элементу кортежа новое значение будет выдана ошибка "TypeError: object doesn't support item assignment" (Ошибка типа: объект не поддерживает возможность изменения элемента). В случае возникновения таких ошибок будет говориться "смотри листочек".

Обратиться (узнать значение или изменить) элемент с номером i списка A можно используя оператор [] : A[i] . Элементы списка нумеруются, начиная с 0, то есть если в списке есть n элементов, то начальный элемент списка имеет номер 0, а конечный номер n-1. Как правило, номера элементов списка называются (произносится "элемент с индексом 0"). Узнать количество элементов в списке A можно при помощи функции len(A) . Таким образом, распечатать список поэлементно можно при помощи следующей программы:

A=input("Введите список: ") for i in range(0,len(A)): print "Элемент с номером", i, "равен", A[i]

В данном примере если список A состоит из n элементов, то переменная i принимает значения от 0 до n-1, то есть всевозможные значения индексов списка. В следующем примере используется аналогичный цикл для того, чтобы удвоить все элементы списка:

A=input("Введите список: ") for i in range(0,len(A)): A[i]=2*A[i]

Также можно использовать отрицательные значения индекса для нумерации элементов с конца списка: A[-1] обозначает последний элемент списка A , A[-2] — второй с конца и т.д. до первого элемента A[-len(A)] . При попытке обратиться к списку из n элементов по индексу, большему, чем n-1 или меньшему, чем -n, будет выдана ошибка IndexError: list index out of range (значение индекса списка выходит за допустимый диапазон). Такая ошибка является весьма типичной.

Что такое список в программировании

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

Каждый элемент должен хранить ссылки на последующий и предыдущий элемент. Для того, чтобы отделить хранимые объекты от способа хранения вводится вспомогательный объект УЗЕЛ (Node).

Возможны различные реализации списков:

Узел - объекты, который содержит ссылки на последующий и предыдущий элементы, а также значение данного элемента списка.

Списки в стандартной библиотеке C++ являются двусвязными. Поэтому список поддерживает вставку в начало (push_front) и в конец (push_back). Кроме того новые элементы можно вставить в любое место списка (insert). При этом не потребуется переразмещение всей структуры данных. Полный список функций вектора см. Приложение 5.

3.4.2. Итераторы

Для обобщения работы с элементами различных контейнеров вводят понятие, общее для всех контейнеров - итератор. Итераторы являются общей концепцией обработки последовательности элементов, хранимых в любых контейнерах. Реализация итератора отличается для разных типов контейнеров, но работа с итератором, набор функций и операторов унифицирован.

Итератор - это объект, который представляет собой обобщение понятия указатель. Это обобщённый "указатель" на элемент, хранящийся в контейнере. Применение оператора * приведет к разыменованию и получению доступа к значению элемента. А использование операторов ++ и -- позволит получить указатель на следующий и предыдущий элемент, хранимый в контейнере. Все контейнеры должны предоставлять несколько ключевых функций-членов, которые позволяют программисту получить итераторы на первый и последний элемент контейнера, то есть найти "концы" последовательности элемента контейнера.

listdouble> ls; listdouble>::iterator it; it=ls.begin(); // итератор на первый элемент контейнера it=ls.end(); // итератор на следующий после последнего элемент контейнера it--; // операторы «++» и «– –» получение указателя на следующий и предыдущий элемент it++; (*it)=5; // оператор * – разыменование и получение доступа к значению элемента // последовательный перебор всех элементов списка через цикл for for(it=x.begin(); it!=x.end(); it++) < sum+=(*it); //доступ к элементам по итератору > // последовательный перебор всех элементов списка через цикл while it=x.begin(); while(it!=x.end())

3.4.3. Пример работы со списком с использованием итераторов (пример 3.4)

Рассмотрим пример работы со списком с использванием итераторов.

///////////////////////////////////////////////////////////////////////////// // Прикладное программирование // Пример 3.4. Пример работы с контейнером list // // Кафедра Прикладной и компьютерной оптики, http://aco.ifmo.ru // Университет ИТМО ///////////////////////////////////////////////////////////////////////////// #include // подключение библиотеки ввода-вывода #include // подключение описания списка #include // для работы с файлами using namespace std; // подключение стандартного пространства имен для использования библиотек // прототипы функций void read_from_file(listint>& data, const string& filename); ///////////////////////////////////////////////////////////////////////////// // Функция чтения конейнера list из файла // data - контейнер для заполнения // filename - имя файла void read_from_file(listint>& data, const string& filename) < ifstream ifile(filename); // создание потока ввода из файла по его имени data.clear(); // очистить контейнер int value; // цикл будет выполняться до тех пор, пока не встретиться конец файла while(!ifile.eof()) < ifile>>value; // читаем число из файла data.push_back(value); // записываем прочитанное число в конец контейнера > > /////////////////////////////////////////////////////////////////////////////// void main() < listint> x; // объявление контейнера listint>::iterator it; // объявление итератора // пример работы с контейнером x.push_back(0); // вставка в конец x.push_back(1); // вставка в конец x.push_back(2); // вставка в конец // x = 0 1 2 x.push_front(5); // вставка в начало // x = 5 0 1 2 it=x.begin(); it++; x.insert(it, 3); // вставка перед итератором it // x = 5 3 0 1 2 // вывод всех элементов контейнера for(it=x.begin(); it!=x.end(); it++) < cout" "; //доступ к элементам по итератору > cout// чтение элементов списка из файла read_from_file(x, "list_data.txt"); // вывод всех элементов контейнера for(it=x.begin(); it!=x.end(); it++) < cout" "; //доступ к элементам по итератору > cout// вычисление суммы всех значений контейнера int sum=0; it=x.begin(); while(it!=x.end()) < sum+=*it; it++; >cout"sum=" /////////////////////////////////////////////////////////////////////////////// 

Список (информатика)

В информатике, спи́сок (англ. list ) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element ); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.

Структура односвязного списка из трёх элементов

Термином список также называется несколько конкретных структур данных, применяющихся при реализации абстрактных списков, особенно связных списков.

Определение

При помощи нотации метода синтаксически-ориентированного конструирования Ч. Хоара определение списка можно записать следующим образом:

Первая строка данного определения обозначает, что список элементов типа (говорят: «список над ») представляет собой размеченное объединение пустого списка и декартова произведения атома типа со списком над . Для создания списков используются два конструктора (вторая строка определения), первый из которых создаёт пустой список, а второй — непустой соответственно. Вполне понятно, что второй конструктор получает на вход в качестве параметров некоторый атом и список, а возвращает список, первым элементом которого является исходный атом, а остальными — элементы исходного списка. То есть получается префиксация атома к списку, с чем и связано такое наименование конструктора. Здесь необходимо отметить, что пустой список не является атомом, а потому не может префиксироваться. С другой стороны, пустой список является как бы нулевым элементом для конструирования списков, поэтому любой список содержит в самом своём конце именно пустой список — с него начинается конструирование.

Третья строка определяет селекторы для списка, то есть операции для доступа к элементам внутри списка. Селектор получает на вход список и возвращает первый элемент этого списка, то есть типом результата является тип . Этот селектор не может получить на вход пустой список — в этом случае результат операции неопределён. Селектор возвращает список, полученный из входного в результате отсечения его головы (первого элемента). Этот селектор также не может принимать на вход пустой список, так как в этом случае результат операции неопределён. При помощи этих двух операций можно достать из списка любой элемент. Например, чтобы получить третий элемент списка (если он имеется), необходимо последовательно два раза применить селектор , после чего применить селектор . Другими словами, для получения элемента списка, который находится на позиции (начиная с для первого элемента, как это принято в программировании), необходимо раз применить селектор , после чего применить селектор .

Четвёртая строка определения описывает предикаты для списка, то есть функции, возвращающие булевское значение в зависимости от некоторых условий. Первый предикат возвращает значение в случае, если заданный список пуст. Второй предикат действует наоборот. Наконец, пятая строка описывает части списка, которые, как уже сказано, представляют собой пустой и непустой списки.

Свойства

У определённой таким образом структуры данных имеются некоторые свойства:

• Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.
• Тип элементов — тот самый тип , над которым строится список; все элементы в списке должны быть этого типа.
• Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).
• Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.
• Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

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

Списки в языках программирования

Функциональные языки

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