Структуры данных.

Списки.

Списки широко распространены в Питоне и имеют множество методов манипулирования(метод отделяется от имени списка точкой: имя_списка.метод()):



>>> a = [66.6, 333, 333, 1, 1234.5]

>>> print a.count(333), a.count(66.6), a.count('x')

2 1 0

>>> a.insert(2, -1)

>>> a.append(333)

>>> a

[66.6, 333, -1, 333, 1, 1234.5, 333]

>>> a.index(333)

1

>>> a.remove(333)

>>> a

[66.6, -1, 333, 1, 1234.5, 333]

>>> a.reverse()

>>> a

[333, 1234.5, 1, 333, -1, 66.6]

>>> a.sort()

>>> a

[-1, 1, 66.6, 333, 333, 1234.5]

Использование списков, как стеков.

Стек – это структура данных, организованнная по принципу “Последним пришёл, первым ушёл”(LIFO). В Питоне нет встроенного класса стека, но вы можете использовать списки Питона так, как они были бы стеками: для добавления элемента используйте append, а для получения последнего – метод pop() без аргумента(метод pop удаляет элемент). Например:



>>> stack = [3, 4, 5]

>>> stack.append(6)

>>> stack.append(7)

>>> stack

[3, 4, 5, 6, 7]

>>> stack.pop()

7

>>> stack

[3, 4, 5, 6]

>>> stack.pop()

6

>>> stack.pop()

5

>>> stack

[3, 4]

Использование списков, как очередей.

Очередь – это другая структура данных, организованнная по принципу “Первым пришёл, первым ушёл”(FIFO). В Питоне нет встроенного класса очереди, но вы можете также использовать списки Питона: для добавления элемента используйте append, а для получения последнего – метод pop(0)(метод pop удаляет элемент). Например:

>>> queue = [1, 2, 3]

>>> queue.append(4) # Terry arrives

>>> queue.append(5) # Graham arrives

>>> queue.pop(0)

5

>>> queue.pop(0)

4

>>> queue

[1, 2, 3]

Функциональные инструменты программирования.

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

filter()

map()

reduce()

Функция filter() может использоваться для выборки значений из списка, условием служит функция пользователя. Синтаксис функции filter(имя_функции, список). Функция возвращает только те элементы списка, для которых значение функции принимает ненулевое(истинное) значение:

>>> def f(x): return x % 2 != 0 and x % 3 != 0#Выбор некоторых простых чисел

...

>>> filter(f, range(2, 25))

[5, 7, 11, 13, 17, 19, 23]



Функция map() имеет следующий синтаксис: map(имя_функции, список). Map() возвращает список, являющийся результатом работы функции для каждого элемента списка:

>>> def cube(x): return x*x*x#Куб числа

...

>>> map(cube, range(1, 11))

[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

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



>>> seq = range(8)

>>> def square(x): return x*x#Квадрат числа

...

>>> map(None, seq, map(square, seq))

[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]



Функция reduce() имеет следующий синтаксис: reduce(имя_функции, список). Она возвращает единственное значение, являющееся выполнением пользовательской функции над первыми двумя элементами списка, затем с результатом выполнения функции и следующим элементом списка, например прогармма считает сумму всех чисел от 1 до 10:

>>> def add(x,y): return x+y

...

>>> reduce(add, range(1, 11))

55

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



Выражения в списках.

В Питоне есть альтернативный способ создания списков по определённым правилам, позволяющий избегать использования функций filter(), map(), reduce(): использование выражений внутри списков. Такие выражения имеют следующий формат: заголовок цикла for, задающий ограничения при создании списков, за этим циклом может(необязательно) следовать некоторое количество условий if и циклов for, по которым, собственно, и создаётся результативный список. Приведём пример таких выражений:

>>> freshfruit = [' банан', ' ананас', 'яблоко ']

>>> [weapon.strip() for weapon in freshfruit]

['банан', 'ананас', 'яблоко']

>>> vec = [2, 4, 6]

>>> [3*x for x in vec]

[6, 12, 18]

>>> [3*x for x in vec if x > 3]

[12, 18]

>>> [3*x for x in vec if x < 2]

[]

>>> [{x: x**2} for x in vec]

[{2: 4}, {4: 16}, {6: 36}]

>>> [[x,x**2] for x in vec]

[[2, 4], [4, 16], [6, 36]]

>>> [(x, x**2) for x in vec]

[(2, 4), (4, 16), (6, 36)]

>>> vec1 = [2, 4, 6]

>>> vec2 = [4, 3, -9]

>>> [x*y for x in vec1 for y in vec2]

[8, 6, -18, 16, 12, -36, 24, 18, -54]

>>> [x+y for x in vec1 for y in vec2]

[6, 5, -7, 8, 7, -5, 10, 9, -3]

>>> [vec1[i]*vec2[i] for i in range(len(vec1))]

[8, 12, -54]

Оператор del.

Данный оператор полезен для удаления объектов из памяти, когда они не нужны(после удаления объекта или переменной, вы не сможете больше к ним обращаться). Кроме того, оператор del может использоваться для удаления элемента из списка по его индексу или по промежутку:

>>> a

[-1, 1, 66.6, 333, 333, 1234.5]

>>> del a[0]

>>> a

[1, 66.6, 333, 333, 1234.5]

>>> del a[2:4]

>>> a

[1, 66.6, 1234.5]



Константные списки.

Мы до сих пор рассматривали списки, т.е. последовательности, элементы которых могут быть доступны для изменения по отдельности. Другим типом последовательности является константный список(tuple). Такой список в теле программы обозначается списком элементов через запятую, может содержать в себе элементы различных типов, но изменить их через индекс не удастся(см. строки). Константные списки могут содержать в себе в качестве элементов другие последовательности. Для списков константного типа определены операции присваивания, склеивания +, индексации(только чтение). Использовать такие списки удобно при доступе к базам данных(одинаковые поля) и системам координат. Рассмотрим примеры константных списков:

>>> t = 12345, 54321, 'привет!'

>>> t[0]

12345

>>> t

(12345, 54321, 'привет!')

>>> #Вложенный список:

... u = t, (1, 2, 3, 4, 5)

>>> u

((12345, 54321, 'привет!'), (1, 2, 3, 4, 5))#Выходные данные тоже в скобках

Внимание: для создания пустого константного списка просто присвойте ему значение (), для создания списка, состоящего из одного элемента сделайте следующее: “имя_списка = единственный_элемент,” - не забудьте запятую в конце(выглядит не слишком приятно):

>>> empty = ()

>>> singleton = 'привет', # <-- не забыть бы про запятую

>>> len(empty)

0

>>> len(singleton)

1

>>> singleton

('привет',)

Создание константного списка из других переменных, вроде “список = 'привет', 'пока', a” является примером упаковки переменных в константный список. Можно провести обратное действие – распаковку, если такой список присваивается нескольким переменным(их число должно быть равно числу элементов в константном списке):

>>> x, y, z = t

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



Словари.

Во всех рассмотренных последовательностях обращаться к отдельным элементам нужно было по индексу. Иную форму организации последовательности представляют словари. В словарях для доступа к отдельным его элементам используются ключевые индексы, подобные индексам в базах данных. Индексом может быть любой неизменяемый объект, такой как строка, число, константный список(такой список может содержать только строки, числа или другие константные списки). В тексте программы словари задаются фигурными скобками {} с элементами словаря. Каждому элементу словаря должен соответствовать определённый индекс, который отделяется от элемента двоеточием(“индекс:значение”). К элементам словаря можно обращаться по соответствующим им индексам. При обращении к несуществующему индексу возникает ошибка. Чтобы узнать список всех индексов словаря, можно воспользоваться методом keys(), которая возвращает все индексы словаря в случайном порядке(но вы можете отсортировать индексы функцией sort()). Чтобы проверить наличие индекса в словаре, можно использовать метод has_key(). Вот простой пример использования словаря:



>>> tel = {'Ваня': 4098, 'Коля': 4139}

>>> tel['Андрей'] = 4127

>>> tel

{'Коля': 4139, 'Андрей': 4127, 'Ваня': 4098}

>>> tel['Ваня']

4098

>>> del tel['Коля']

>>> tel['Дима'] = 4127

>>> tel

{'Андрей': 4127, 'Дима': 4127, 'Ваня': 4098}

>>> tel.keys()

['Андрей', 'Дима', 'Ваня']

>>> tel.has_key('Ваня')

1



Особенности операторов сравнения.

Теперь, когда мы познакомились со списками, пришёл черёд изучить дополнительные сведения об операторах сравнения. Операторы сравнения (>; <; ==; !=; >=; <=)имеют в выражениях приоритет оценки ниже арифметических операторов, то есть в выражении a + b > c + d * e будут оценены вначале арифметические операции, а затем их результаты будут сравниваться. Операторы сравнения могут комбинироваться друг с другом, например, в выражении “a < b == c” операторы сравнения оцениваются слева направо, так как имеют одинаковый приоритет. Выражения с операторами сравнения могут объединяться с помощью логических операций or(или), and(и) и not(не). Значение логических операторов ясно из названия, поэтому комментарии здесь излишни. Приоритет логических операторов ниже, чем к операторов сравнения, самый высокий приоритет у оператора not, самый низкий – у оператора or. Поэтому, при оценке логических выражений, включающих в себя операторы различного приоритета, встретившееся выражение false может вызвать то, что операторы с более низким приоритетом обработаны не будут.

Для списков существуют особые операторы сравнивания:

оператор in(not in) оценивает, входит ли заданный элемент в последовательность;

оператор is(is not) применяется для изменяемых последовательностей и определяет, действительно ли две последовательности указывают на одну и ту же область памяти(то есть являются идентичными).

Результат сравнения может быть присвоен переменной логического типа(принимает значения true и false). В отличие от языка Си, в Питоне не допускаивается присваивание при сравнении, что исключает ошибку, распространённую в языке Си и связанную с употреблением =, вместо ==.

Сравнение списков.

Сравнение списков несколько отличается от сравнения простых числовых значений. Во-первых, списки должны быть одинакового типа. Во-вторых сравнение идёт в лексикографическом порядке, т.е оцениваются вначале первые элементы последовательностей, если они не равны, то далее возвращается результат(>;<;!=), иначе оценивается следующая пара элементов. Последовательности будут равны только в том случае, если все их элементы будут соответственно равны. Кроме этого, более длинная последовательность будет всегда больше более короткой.Строки сравниваются, учитывая порядок символов в строках в таблице ASCII. Приведём примеры сравнения последовательностей:



(1, 2, 3) < (1, 2, 4)

[1, 2, 3] < [1, 2, 4]

'ABC' < 'C' < 'Pascal' < 'Python'

(1, 2, 3, 4) < (1, 2, 4)

(1, 2) < (1, 2, -1)

(1, 2, 3) == (1.0, 2.0, 3.0)

  1. 2, ('aa', 'ab')) < (1, 2, ('abc', 'a'), 4)

При этом, допускается сравнивание элементов различного типа(хотя по-моему это сильно усложняет понимание программы), при этом строка всегда больше списка, константный список больше строки и.т.д. Различные числовые типы сравниваются путём приведения их к типу с точкой.