Пример решения задачи базового уровня. Задача: Пользователь вводит в программу последовательность целых чисел, завершая ввод нажатием <Ctrl+Z>

Задача: Пользователь вводит в программу последовательность целых чисел, завершая ввод нажатием <Ctrl+Z>. Числа могут повторяться. Программа собирает вводимые данные в память, а в конце ввода в произвольном порядке выдает набор из пар чисел на отдельных строках - первое из которых является одним из введенных чисел без повторений, а второе - количество его появлений во вводе. Например, пользователь вводит такую последовательность :

1 2 3 4 5 1 3 5 6 1 <Ctrl+Z>

На что программа выдает следующий результат обработки (строки могут быть в любом порядке):

1 3

2 1

3 2

4 1

5 2

6 1

Реализация на основе хэш-таблиц:

Для реализации задачи требуется реализовать функцию обхода хранящихся ячеек в хэш-таблице. В заголовочный файл с хэш-таблицей (hash_table.hpp) следует добавить такое объявление для функции обхода, которая будет отправлять пару ключ-значение функции обратного вызова:

typedef void( * HashTableWalkFunction ) ( int_key, int_value );

voidHashTableWalk ( constHashTable & _ht, HashTableWalkFunction _f );

Можно реализовать такую функцию для таблицы с закрытым хэшированием. Для этого нужно в файл реализации hash_table_closed_impl.cpp добавить тело функции обхода:

voidHashTableWalk ( constHashTable & _ht, HashTableWalkFunction _f )

{

// Находим ячейки, имеющие статус OCCUPIED, и вызываем функцию пользователя

for( inti = 0; i < _ht.m_tableSize; i++ )

if( _ht.m_pData[ i ].m_status == HashTable::Element::OCCUPIED )

( * _f )( _ht.m_pData[ i ].m_key, _ht.m_pData[ i ].m_value );

}

В качестве альтернативы, такую же функции можно добавить в таблицу с открытым хэшированием. Для этого файл реализации hash_table_open_impl.cpp следует расширить:

voidHashTableWalk ( constHashTable & _ht, HashTableWalkFunction _f )

{

// Находим ячейки, имеющие списки

for( inti = 0; i < _ht.m_tableSize; i++ )

if( _ht.m_pData[ i ] )

{

// Обходим все элементы списка

constHashTable::Element * element = _ht.m_pData[ i ];

while( element )

{

( * _f )( element->m_key, element->m_value );

element = element->m_pNext;

}

}

}

Наконец, составим основную часть программы в соответствии с условием:

#include "hash_table.hpp"

#include <iostream>

// Функция реакции на обход таблицы - печатает пару ключ-значение

voidprintKeyValue ( int_key, int_value )

{

std::cout << _key << ' ' << _value << std::endl;

}

// Основная программа

intmain ()

{

// Создаем хэш-таблицу

HashTable * pHT = HashTableCreate( 10 );

// Цикл ввода данных

while( true)

{

// Вводим очередное число

intvalue;

std::cin >> value;

// Прекращаем ввод при нажатии Ctrl+Z или в случае ошибки

if( std::cin )

{

// Был ли данный ключ уже размещен в таблице ранее?

intcount = HashTableGet( * pHT, value );

if( count == -1 )

// Первое вхождение ключа

HashTableInsert( * pHT, value, 1 );

Else

// Очередное вхождение ранее наблюдавшегося ключа

HashTableInsert( * pHT, value, count + 1 );

}

Else

break;

}

// Инициируем обход таблицы с распечаткой пар ключ-значение

HashTableWalk( * pHT, & printKeyValue );

// Уничтожаем таблицу

HashTableDestroy( pHT );

}

Результат выполнения программы: