Структуры данных и модели вычислений

         

Общие сведения о списках


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

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

Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества . Если длина кортежа равна , , то кортеж

удобно рассматривать как отображение множества в множество . Таким образом, — это -й элемент кортежа .

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

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

  • Нахождение позиции элемента в памяти по его номеру в кортеже.
  • Нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции.
  • Нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.
  • Удаление элемента, находящегося в заданной позиции.
  • Вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции.
  • Определение длины кортежа.



Содержание    Вперед