Карта абстрактного типа данных

Опубликовано: 30 Сентября, 2022

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

Карта абстрактного типа данных

Карта — это абстрактный тип данных, содержащий набор записей. Это интерфейс, в котором указано, какие операции можно выполнять, но не их реализация. Каждая запись карты содержит ключ и значение. Свойство карты таково, что к каждому значению можно получить доступ или получить его с помощью ключа. Это означает, что каждый ключ связан со значением. Очень важно отметить, что каждый ключ на карте должен быть уникальным. Значения могут дублироваться, но ключи каждый раз должны быть уникальными. В разных языках программирования карты имеют разные названия для их реализации. Посмотрите на пример ниже:

  1. C++: unordered_map, multimap, hash_map и т. д. являются реализациями.
  2. Питон: словари.
  3. Java: HashMaps, HashTables.

Операции карты

Давайте теперь познакомимся с некоторыми полезными операциями, которые можно выполнять с помощью карты:

  • put(key, value): на карту добавляется новая пара ключ-значение. В случае, если ключ уже существует в карте, то старое значение заменяется новым.
  • get(key): Здесь передается ключ, и с помощью ключа мы можем получить значение, связанное с данным ключом.
  • len(): эта операция возвращает длину карты, т. е. количество пар ключ-значение.
  • del: эта операция используется для удаления определенной пары ключ-значение с карты. Вот как это делается: del map[key]. Конкретный ключ и связанное с ним значение удаляются с карты.
  • in: Эта операция возвращает логическое значение. Он возвращает true, если данный ключ существует на карте, иначе возвращает false.

Использование карты

В следующих ситуациях идеально подходит абстрактный тип данных карты:

  • Отметки студента по его студенческому билету.
  • Налоговые данные по номеру социального страхования.
  • Зарплата работника по его табельному номеру.
  • Владелец мотоцикла по номерному знаку владельца.

Карты также широко используются для подсчета частоты. Например: подсчитайте повторяющиеся числа в массиве. Здесь можно использовать карту, где ключом будет индекс числа, а значением будет его частота. В следующей таблице показан пример пары ключ-значение:

Рулон № Имя
101 Шон
102 Джон
103 Дэйвид
104 Джон

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

Реализация карты

Карта также известна как ассоциативный массив. Таким образом, для реализации карты нам нужны два значения данных. Начальный — это ключ, с помощью которого можно получить доступ, удалить, заменить связанное с ним значение. Значение — это второй параметр, который берется при создании карты. Мы можем реализовать карту двумя способами:

  • Список
  • Словарь

Давайте обсудим их один за другим.

Список:

Существуют различные способы реализации карты, но на данный момент список кажется лучшим. Список используется для представления коллекции или набора значений, порядок которых очень важен. Таким образом, чтобы реализовать карту с использованием списка, мы должны создать два списка параллельно. Где первый список используется для хранения ключей, а второй список используется для хранения значений. Посмотрите на следующий пример, где создаются 2 списка.

Список 1:

Индекс Пин-код
0 400099
1 500078
2 340005

Список 2:

Индекс Название дороги
0 Косой переулок
1 Хагрид Роуд.
2 Альбус Уорн

Приведенные выше два списка являются примером реализации карты с использованием двойных списков. Первый список содержит ключ в виде пин-кода, а второй список содержит название дороги в качестве значения, связанного с конкретным ключом.

Пример:

Словарь

Другой способ реализации карты — использование встроенного типа данных словаря. Словарь помогает нам создать список с ключами и значениями, похожий на карту. В Python словарь можно создать, вставив набор элементов в фигурные скобки {}, разделенные запятой. Важно отметить, что значения могут меняться, но ключи неизменны. Важной особенностью словаря является то, что он не допускает дублирования. Еще одним свойством словаря является то, что он упорядочен по своей природе при вставке, что означает, что элементы имеют определенный порядок, который нельзя изменить. Хотя словари изменяемы, это означает, что мы можем добавлять, удалять или заменять элементы даже после создания словаря. Прежде чем понять, как словарь можно использовать для реализации карты, давайте познакомимся с некоторыми важными методами словаря.

Метод Описание
получить() Этот метод используется для возврата значения указанного ключа.
Чисто() Этот метод используется для удаления всех элементов из словаря.
поп() Этот метод используется для удаления элемента, связанного с указанным ключом.
Обновить() Этот метод используется для обновления словаря с указанными парами ключ-значение.
ценности() Этот метод используется для возврата списка всех значений, присутствующих в словаре.
ключи Этот метод используется для возврата списка всех ключей, присутствующих в словаре.

Пример:

Примеры вопросов

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

Решение:

Вопрос 2: Создайте список автомобилей и их цветов. Узнать цвет конкретного автомобиля.

Решение:

Вопрос 3: Удалить конкретное предложение с определенного номера строки из книги.

Решение:

Выход

Before deleting : 
{"line1": "Hello World!", "line2": "I am the best", 
 "line3": "The Giant is here!!", "line4": "Yes!", 
 "line5": "Big Show"}
After deleting line1 : 
{"line2": "I am the best", "line3": "The Giant is here!!", 
 "line4": "Yes!", "line5": "Big Show"}