Файл: Роман Вячеславович Шамин shamin ru, lector ru, calcs ru.pptx

хранящих как данные, так и ссылку на следующий элемент.

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

Современные языки имеют встроенные списки, когда добавление нового элемента делается автоматически: List.append(X) – добавление X к списку List в Python.

Очередь

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Часто нам нужно организовать очередь, когда мы сохраняем и имеем доступ к элементам не по индексу, а по принципу «первый вошел, первый вышел» FIFO – «first in, first out».

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

Размер очереди может быть фиксированным или динамическим как в случае списков.

Стек

Лекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ru

Стек представляет собой структуру данных, в которой принцип: «последний вошел, первый вышел» LIFO – «last in, first out».

Стек – это очень эффективное средство организации данных, которая применяется в рекурсивных обходах дерева, организации вызовов подпрограмм и др.

Обычно стек поддерживает три операции:

• push(X) – поместить в стек элемент X
• pop() – получить верхний элемент, удалив его из стека
• peek() – получить верхний элемент, без удаления из стека

Стек можно сравнить со стопкой книг или магазином с патронамиХеш-таблица или словарьЛекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ruКлассический массив представляет собой набор элементов, доступ к которым осуществляется с помощью индекса – целого числа 0, 1, …А почему бы не сделать массив, доступ к элементам которого будет не с помощью чисел, а произвольного ключа-имени?Такой массив называется хеш-таблицей или словарем.Хеш-таблица позволяет эффективно организовать доступ по принципу «ключ – значение».Например, для описания студентов можно использовать следующую структуру Students:[key=“фамилия имя отчество”, data = “адрес”]Например: адрес Лобанова Андрея Николаевича можно найти по запросу:Students[“Лобанов Андрей Николаевич”]ЗаключениеЛекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ruВ этой лекции Вы познакомились со следующими понятиями:

---

• Что такое информатика и информация
• Единицы измерения информации
• Энтропия информации по Шеннону
• Системы счисления и перевод из одной системы счисления в другую
• Представление чисел в компьютере
• Что такое данные
• Переменные и типы данных
• Массивы
• Списки
• Очередь
• Стек
• Хеш-таблица или словарь

Подготовка к тестуЛекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ruВопрос № 1:«Что такое информация и какими она может обладать свойствами?»Вопрос № 2:«Сколько бит в 5 гигабайтах?»Вопрос № 3:«Какой смысл имеет энтропия информации?»Вопрос № 4:«Чему равно F516?» «Записать в двоичной системе счисления число 21»Вопрос № 5:«Записать в нормализованной форме число 120,34. Указать мантиссу и порядок»Подготовка к тестуЛекции по информатике, Р.В. Шамин: shamin.ru, lector.ru, calcs.ruВопрос № 6:«Что такое данные и чем они отличаются от информации?»Вопрос № 7:«Какого типа данных могут быть переменные?»Вопрос № 8:«Что такое массив?»Вопрос № 9:«Чем список отличается от массива? от хеш-таблицы?»Вопрос № 10:«В чем разница между стеком и очередью?»Удачи на экзамене!

---