Файл: Роман Вячеславович Шамин 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:

«В чем разница между стеком и очередью?»

Удачи на экзамене!

---