Обработка списков. Линейный поиск. Добавление и удаление элементов. Копирование списков

Вопросы:

·     Линейный поиск элемента в списке.

·     Добавление и удаление элементов списка.

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

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

Опишем функцию  в специально созданном модуле, в котором будут содержаться функции обработки списков. Назовём его ListProcessing. Назовём нашу функцию serach, что в переводе на русский язык означает «поиск». Аргументами функции будут: значение искомого элемента – x, а также список, в котором его необходимо найти, – a. Начнём описание тела функции. Объявим переменную i, в которой будем перебирать индексы элементов списка. Присвоим ей значение первого индекса списка, то есть ноль. Дальше запишем цикл while, который будет работать до тех пор, пока элемент списка a[i] не будет равен искомому элементу x. В цикле мы будем переходить к проверке следующего элемента списка. Для этого будем увеличивать переменную-индекс i на 1. После цикла нам остаётся лишь завершить выполнение функции, вернув значение i.

def search (x, a):

    while a[i] != x:

        i  = i + 1

    return i

Написанная функция уже будет работать, но только если элемент с заданным значением будет в списке. Если же такого элемента не окажется, то индекс i выйдет за границы списка, и при попытке обратится к элементу с индексом, которого нет в списке, выполнение функции завершится ошибкой. Чтобы этого не случилось, изменим условие цикла. Теперь цикл будет работать до тех пор, пока не найден элемент с заданным значением или же пока переменная i не достигла значения максимального индекса с писке a, который будет равен длине списка, уменьшенной на единицу. Однако теперь после завершения работы цикла нужно проверить, почему он был завершён. Для этого запишем ветвление, условием которого будет то, что i-тый элемент списка a равен искомому x. Если это условие выполняется, функция вернёт значение i, в противном случае элемент x не будет найден в списке a и функция вернёт значение -1.

def search (x, a):

    while a[i] != x and i < len (a) – 1:

        i  = i + 1

    if a[i] == x:

        return i

    else:

        return -1

Протестируем написанную функцию. Для этого сохраним модуль и запустим его на выполнение. Вызовем написанную функцию для того, чтобы найти элемент со значением 3 в списке из чисел: 20, 7, 3, 4 и 20. Видно, что по порядку этот элемент третий, но так как нумерация элементов списка начинается с нуля, его индекс равен 2. Функция вернула именно это значение. Снова запустим функцию и попробуем найти число 20 в списке, заданном ранее. Такое значение имеют элементы с индексами 0 и 4, но мы условились, что функция будет возвращать индекс первого вхождения элемента, поэтому функция вернула значение 0. Снова запустим функцию и попробуем найти число 5 в списке, заданном ранее. Такого числа там нет, и функция вернула -1, как мы и условились.  Функция работает правильно.

Возможен другой вариант поиска элемента с заданным значением. Для этого существует уже описанная функция index, которая возвращает индекс первого вхождения элемента с заданным значением в список, однако она не работает, если элемента с заданным значением в списке нет. Поэтому, прежде чем использовать эту функцию, нужно сначала проверить, есть ли в списке элемент с заданным значением. Для этого можно записать ветвление с условием x in a. Это условие будет выполняться только тогда, когда в списке a есть элемент со значением x, в противном случае функция должна вернуть -1.

def search (x, a):

    if x in a:

        return a.index (x)

    else:

        return -1

Сохраним изменённый модуль и запустим его на выполнение. Создадим список a из чисел 1, 2 и 3. Вызовем описанную функцию для поиска числа 2 в списке a. Число 2 действительно имеет в списке индекс 1. Снова вызовем функцию для поиска числа 4 в списке a. Такого числа в списке действительно нет. Функция работает правильно.

Иногда поиск данных в списке сводится не к тому, чтобы найти элемент с заданным значением, а к тому, чтобы найти самый-самый элемент, например, элемент с самым большим или с самым малым значением.

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

Начнём написание функции. Опишем её в том же модуле ListProcessing. Назовём её IndOfMax. Её аргументом будет список, в котором нужно найти максимальный элемент – a. В теле функции объявим переменную m, в которой будем хранить индекс элемента, предположительно имеющего максимальное значение. Присвоим ей значение 0. Теперь напишем цикл с параметром i, изменяющимся в диапазоне от 1 до последнего индекса списка a. Здесь функция вычисления длины списка сработает всего один раз, поэтому можно использовать её саму. В цикле запишем ветвление с условием, что элемент списка a с индексом i больше элемента с индексом m. Если это условие выполняется, то предположим, что i-тый элемент списка наибольший и присвоим переменной m значение i. По завершении работы цикла функция вернёт значение m.

def IndOfMax (a):

    m = 0

    for i in range (1, len (a)):

        if a[i] > a[m]:

            m = i

    return m

Протестируем функцию. Для этого сохраним модуль и запустим его на выполнение. Создадим список a из чисел 7, 25 и 12. Максимальное значение имеет элемент списка с индексом 1. Проверим это, вызвав функцию IndOfMax (a). Функция действительно вернула 1. Добавим в конец списка a ещё один элемент, равный 25, и вызовем функцию для изменённого списка. Мы условились, что функция вернёт индекс первого из элементов с наибольшим значением. Так и случилось – она вернула 1. Функция работает правильно.

Напишем противоположную ей функцию поиска элемента списка с наименьшим значением. Для этого скопируем написанную функцию и будем изменять её код. Изменим название функции на IndOfMin. В условии ветвления, которое находится в цикле, изменим знак «больше» на знак «меньше».

def IndOfMin (a):

    m = 0

    for i in range (1, len (a)):

        if a[i] < a[m]:

            m = i

    return m

Сохраним модуль и протестируем функцию. Вызовем её для списка из чисел 7, 8, 3 и 5. Минимальный элемент списка действительно имеет индекс 2. Функция работает правильно.

Для решения обеих задач мы последовательно перебирали все элементы списка. Такой поиск называется линейным. Этот метод универсален, то есть он подходит для поиска элементов в любом списке.

Часто нужно добавлять и удалять элементы из списка. Как добавить элемент в конец списка мы знаем.

a = a + [x]

В начало списка элемент можно добавить аналогично.

a = [x] + a

При добавлении элемента в середину списка могут возникнуть сложности. Но это не сложно сделать, зная некоторые особенности. Для того, чтобы добавить в список a некоторый элемент x на позицию с индексом i, нужно сначала проверить, заполнены ли все элементы перед i-тым. Для этого достаточно записать ветвление с условием, что длина списка a не меньше i. Если это условие выполняется, мы можем осуществить вставку элемента. После этого присвоим переменной a список, состоящий из трёх частей, где первая часть будет состоять из элементов списка, расположенных до i-того, не включая i-тый элемент. Чтобы её выделить, необходимо записать a [0:i]. Так обозначаются элементы списка a с индексами от 0 до i, не включая последний. Дальше будет следовать список из одного элемента x, и, наконец, элементы списка a от i-того до последнего. Так как элемент с индексом после двоеточия не включается в промежуток, то после двоеточия нужно указать длину списка a.

if len (a) >= i:

    a = a[0:i] + [x] + a[i:len (a)]

Похожим образом можно и удалить i-тый элемент из списка a. Сначала нужно проверить, есть ли в списке элемент с таким индексом. Для этого записывается ветвление с условием, что i < len (a). Если это условие выполняется, то элемент с индексом i есть в списке и его можно удалить. Для этого переменной a присваивается результат объединения элементов списка a с индексами от 0 до i, не включая последний, а также элементов списка a с индексами от i + 1 до последнего.

if i < len (a):

    a = a[0:i] + a[i + 1:len (a)]

Для того, чтобы получить перевёрнутый список, в котором первый элемент исходного списка станет последним, а второй – предпоследним и так далее, нужно вызвать у этого списка метод reverse без параметров.

Рассмотрим копирование списков в языке Python. Казалось бы, здесь всё просто: для того, чтобы создать копию списка a, достаточно объявить некоторую переменную, назовём её b, и присвоить ей значение a. Однако если так поступить и после этого попытаться изменить один из списков, то вслед за ним будет автоматически изменён и второй. Почему так происходит? Дело в том, что когда мы присваиваем переменной Бэ значение a, то переменная b начинает обозначать ту же область оперативной памяти, что и переменная a, и при обращении к любому из списков будет изменена именно эта область. Чтобы в переменной b именно создать копию списка a, достаточно присвоить ей элементы списка a с нулевого до последнего.

b = a[0:len (a)]

При такой записи слева и справа от двоеточия можно ничего не указывать.

b = a[:]

Мы узнали:

·     Для поиска элементов в списке можно использовать метод линейного поиска, который состоит в последовательной проверке всех элементов списка.

·     Каким образом можно добавить и удалить элемент из списка.

·     Как скопировать список в в языке Python.