«

»

Ассоциативный массив

Для доступа к элементам индексного массива используются обычные целые числа, называемые индексами. У ассоциативного массива (словаря) эту функцию выполняют ключи. Они, в отличие от индексов, могут быть заданы не только числовым типом данных, но и, например строковым или булевым. Каждому элементу ассоциативного массива соответствует пара «ключ-значение» (key, value), и на нем определены четыре базовые операции:

  • INSERT – операция добавления пары в массив;
  • REASSIGN – операция изменения существующей пары;
  • DELETE – операция удаления пары из массива;
  • SEARCH – операция поиска пары в массиве.

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

  • словарь (Objective-C, .NET, Python, …);
  • карта (C++, Java, Haskell, …);
  • хеш (Perl, Ruby, …).

В одних ЯП высокого уровня реализована встроенная поддержка ассоциативных массивов (Perl, PHP, Python, Ruby, JavaScript), в других они поставляются со специальными библиотеками (C++). Если же язык не имеет необходимых средств, то работу ассоциативного массива, как правило, можно имитировать при помощи других языковых компонентов.

В качестве примера объекта, организованного по принципу ассоциативного массива, можно привести тетрадь или базу данных, служащую для записи студентов, выписавших книги в университетской библиотеке, и пока не вернувших их. Ключами здесь будут названия книг, значениями – имена студентов. Так одно значение может соответствовать нескольким ключам (при этом ключи не повторяются), т. е. одну книгу может выписать только один студент, но этот же студент вправе выписать и другие книги.

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
setlocale(LC_ALL, "Rus");
string name, book, number;
map <string, string> library;
do
{
cout<<"\n\nВыберите операцию:"<<endl;
cout<<"\n1. Добавить запись\n2. Найти запись\n";
cout<<"3. Удалить запись\n4. Вывести весь список\n5. Выйти\n\n";
cout<<"Номер операции > "; cin>>number;

if (number=="1")
{ cin.sync(); // очистка буфера
cout<<"Название книги > "; getline(cin, book);
cout<<"Имя студента > "; getline(cin, name);
library[book]=name;
cout<<"Добавлено..."<<endl<<endl;
}

else if (number=="2")
{ cin.sync(); // очистка буфера
cout<<"Книга > "; getline(cin, book);
map <string, string>::const_iterator ifind=library.find(book);
if (ifind!=library.end())
{
cout<<"Книга: <"<<ifind->first<<"> | ";
cout<<"Студент: <"<<ifind->second<<">\n";
}
else cout<<"Данные отсутствуют";
}

else if (number=="3")
{ cin.sync(); // очистка буфера
cout<<"Книга > "; getline(cin, book);
library.erase(book);
cout<<"\nДанные удалены..."<<endl;
}

else if (number=="4")
{
map <string, string>::const_iterator i;
for(i=library.begin(); i!=library.end(); ++i)
{
cout<<"Книга: <"<<i->first<<"> | ";
cout<<"Студент: <"<<i->second<<">\n";
}
}

else if (number=="5") return 0;
else cerr<<"\nНеопознанная команда"<<endl;
} while (number!="5");

return 0;
}

 

Здесь за весь функционал ассоциативного массива отвечает контейнер <map> библиотеки STL. Для его работы, вначале необходимо подключить файл map к программе посредством директивы #include:

#include <map>

Затем описать сам массив:

map <тип данных ключей, тип данных значений> название массива;

Для работы с массивом, контейнер <map> предоставляет определенное количество специальных функций, но в программе выше, использовались лишь некоторые из них.

Фактически ассоциативный массив базируется на другой структуре данных. В зависимости от ЯП, он имеет различную реализацию. Например, в языках Ruby и Python ассоциативные массивы используют хеш-таблицу, а контейнер <map> в C++ выполнен на основе красно-чёрного дерева. Другие реализации оперируют сортированными и несортированными связными списками. Также возможен вариант, в котором используется массив фиксированного размера с указателем на последний заполненный элемент этого массива.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *