Структуры данных и модели вычислений
Общие сведения о списках
Остановимся на наиболее часто используемых структурах данных, называемых списками. Списки лежат в основе многих более сложных структур данных. В простейшем случае списки используются для представления кортежей.
Кортеж — это конечная последовательность, возможно с повторениями, элементов некоторого множества . Элементами кортежа могут быть числа, символы некоторого алфавита, точки плоскости и т.д. В более сложных случаях элементами кортежа, в свою очередь, могут быть также кортежи. Элементы, не являющиеся кортежами, называются атомами. Количество элементов в кортеже называется его длиной. Удобно рассматривать кортежи, не содержащие ни одного элемента. Такие кортежи называются пустыми. Длина пустого кортежа считается равной .
Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества . Если длина кортежа равна , , то кортеж
удобно рассматривать как отображение множества в множество . Таким образом, — это -й элемент кортежа .
Термин "список" используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа — его позиция в памяти. В некоторых случаях номер элемента в кортеже и его позиция в памяти связаны друг с другом арифметическими соотношениями таким образом, что по номеру легко вычисляется позиция и, наоборот, по позиции вычисляется номер. В других случаях связь между номерами и позициями задается "таблично" или осуществляется с помощью алгоритмических процедур. Множество позиций обозначим через . Иногда удобно считать, что в множестве имеется специальный элемент , указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка мы имеем дело с тремя множествами , , и с отображениями на этих множествах.
Типичными при работе со списками являются следующие операции:
- Нахождение позиции элемента в памяти по его номеру в кортеже.
- Нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции.
- Нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.
- Удаление элемента, находящегося в заданной позиции.
- Вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции.
- Определение длины кортежа.
