Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка Статус: Академик Рейтинг: 8648 ∙ повысить рейтинг »

Коцюрбенко Алексей aka Жерар Статус: Профессор Рейтинг: 2842 ∙ повысить рейтинг »

Boriss Статус: Академик Рейтинг: 2594 ∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:	1691
Дата выхода:	24.10.2011, 14:30
Администратор рассылки:	Киселёва Алёна aka Verena (Профессор)
Подписчиков / экспертов:	286 / 165
Вопросов / ответов:	1 / 2

Консультация # 184233: Здравствуйте! Требуется написать программу из области объектно-ориентированного программирования на С++. Код прокомментировать. Был бы очень благодарен за помощь. Задание: 1. Разработать класс "перемешанная таблица" в соответствии со следующим заданием: Состояние класса - Таблица представляется в виде вектора (массива), сос...

Консультация # 184233:

Здравствуйте!
Требуется написать программу из области объектно-ориентированного программирования на С++. Код прокомментировать. Был бы очень благодарен за помощь.
Задание:
1. Разработать класс "перемешанная таблица" в соответствии со следующим заданием:
Состояние класса -
Таблица представляется в виде вектора (массива), состоящего из элементов. Элемент таблицы состоит из ключа (тип int), поля занятости (тип int) и информации (тип char[ ] фиксированной длины). Для описания элемента таблицы целесообразно использовать структуру. Память под массив выделяется статически, во время компиляции, и задается массивом фиксированного размера. Преобразование ключа в индекс выполняется функцией хеширования. Элементы перемешиваются методом сложения с константой.
Протокол класса -
Определяет возможности создания и инициализации экземпляров класса и правила их использования (методы класса).
Предусмотреть следующие возможности:
∙ создание экземпляров структуры (элемента таблицы) с инициализацией начальным состоянием по умолчанию;
∙ пустой конструктор для инициализации экземпляров и массивов экземпляров класса (таблицы) по умолчанию;
∙ создание экземпляров класса (таблицы) с инициализацией заданным количеством элементов из массива ключей и информации;
∙ ввод значения экземпляра структуры (элемента таблицы) из входного потока (с помощью перегруженного оператора >> );
∙ вывод таблицы в выходной поток (с помощью перегруженного оператора << );
∙ поиск элемента таблицы по ключу (с помощью перегруженного оператора ( ) );
∙ добавление элемента в таблицу (с помощью перегруженного оператора += );
∙ выборка информации из таблицы по заданному ключу (с помощью перегруженного оператора [ ] );
∙ удаление элемента из таблицы (с отметкой в поле занятости) по ключу (с помощью перегруженного оператора -= );
∙ чистка таблицы от “удаленных элементов” – реорганизация таблицы.
2. Проектирование класса рекомендуется начать с представления состояния класса, учитывающего заданные операции, а затем реализации конструкторов и перегруженного оператора вывода. Для отладки и исчерпывающего тестирования других методов разработанного класса реализовать диалоговую программу, которая позволяет вводить параметры, отлаживаемых методов.
3. Повторить разработку класса при условии, что память под строку символов в элементе таблицы и массив структур необходимой длины выделяется динамически, во время выполнения программы (с помощью оператора new; память задается указателем на char в структуре и указателем на структуру в состоянии класса).
Дополнить интерфейс класса следующими возможностями:
∙ память под данные поля информации выделять динамически с помощью оператора new;
∙ создание экземпляра класса (таблицы) с его инициализацией другим экземпляром класса (копирующий конструктор) для элемента таблицы и таблицы;
∙ переопределение экземпляра класса (с помощью перегруженного оп ератора присваивания) для элемента таблицы и таблицы.
4. Написать прикладную программу, использующую разработанный класс.

Дата отправки: 17.10.2011, 13:49
Вопрос задал: Посетитель - 383089 (Посетитель)
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Киселёва Алёна aka Verena (Профессор):

Здравствуйте, Посетитель - 383089!
Вот один из вариантов реализации. Если что-то не так поняла, пишите, исправлю.
Единственное, программа не учитывает вариант, при котором в таблицу передадут разные элементы с одним ключом. Тогда в поиске будет выдаваться только первый из них. Относительно данной ситуации в ТЗ ничего не сказано.
Код класса в приложении и в архиве. Вот пример его использования:

#include <conio.h>
#include <stdlib.h>
#include "HashedTable.h"


int _tmain(int argc, _TCHAR* argv[])
{ //пример
 try {
  Elem e [2];
  e[0].key = 102; strcpy (e[0].info, "ura");
  e[1].key = 113; strcpy (e[1].info, "rok");
  CHashedTable a, b (e, 2);
  cout << "a=" << a << endl;
  cout << "b=" << b << endl;
  a+=e[0];
  cout << "a+=e[0]" << a << endl;
  b+=e[1];
  cout << "b+=e[1]" << b << endl;
  b-=e[1];
  cout << "b-=e[1]" << b << endl;
  b.Clear();
  cout << "b.Clear=" << b << endl;
  cout << "b[102] = " << b[102].info << endl;
  cout << "b(102) = " << b(102) << endl;
  cout << "Enter: " << endl;
  cin >> a;
  cout << "a=" << a << endl;
 } catch (char* ex) {
  cout << ex;
 }
 getch(); //ожидаем пользователя
 return 0;
}

Приложение:
//HashedTable.h #pragma once #include <iostream> using namespace std; struct Elem { //элемент таблицы int key; //ключ int occupied; //признак занятости char info [21]; //информация Elem () : key(0),occupied(0) {info[0] = \'\0\';}; //конструктор по умолчанию }; class CHashedTable { static const unsigned int size = 10; //максимальный размер таблицы unsigned int count; //количество элементов в таблице Elem data [size]; //массив данных public: CHashedTable(); //конструктор по умолчанию CHashedTable (Elem* elem, int n); //конструктор из массива CHashedTable (const CHashedTable &t); //конструктор копирования ~CHashedTable(); //деструктор CHashedTable& operator= (const CHashedTable t); //оператор присваивания CHashedTable& operator+= (const Elem& t); CHashedTable& operator-= (const Elem& t); Elem operator[] (int key); //получение элемента по ключу bool operator() (int key); //проверка существования элемента по ключу void Clear (); //сжатие таблицы (условное, поскольку память статическая) friend ostream& operator << (ostream& str, CHashedTable& t); //вывод friend istream& operator >> (istream& str, CHashedTable& t); //ввод private: unsigned int Hash (int key); //функция хеширования }; //HashedTable.cpp #include "StdAfx.h" #include "HashedTable.h" #include <string.h> CHashedTable::CHashedTable() : count(0) //обнуляем число элементов { } CHashedTable::~CHashedTable() { } CHashedTable::CHashedTable (Elem* elem, int n) { if (n>size) throw "Too big array"; //если размер массива больше максимального count = n; //сохраняем количество for (int i = 0; i<n; i++) { //идём по элементам int j = Hash(elem[i].key); //получаем адрес if (data[j].occupied!=0) { //если уже занят for (int k = 1; k<size; k++) { //ищем новый адрес j = Hash(elem[i].key+k); if (data[j].occupied==0) break; } } if (data[j].occupied!=0) throw "Too many keys with one hash"; //все места заняты - ошибка data[j].occupied = 1; //записываем элемент, помечаем место занятым data[j].key = elem[i].key; strcpy (data[j].info, elem[i].info); } } CHashedTable::CHashedTable (const CHashedTable &t) //конструктор копирования { count = t.count; //копируем всё из другого экземпляра for (int i = 0; i<size; i++) { data[i].key = t.data[i].key; data[i].occupied = t.data[i].occupied; strcpy (data[i].info, t.data[i].info); } } CHashedTable& CHashedTable::operator= (const CHashedTable t) //оператор присваивания { count = t.count; //копируем всё из другого экземпляра for (int i = 0; i<size; i++) { data[i].key = t.data[i].key; data[i].occupied = t.data[i].occupied; strcpy (data[i].info, t.data[i].info); } return *this; } CHashedTable& CHashedTable::operator+= (const Elem& t) { if (count == size) return *this; //если таблица уже заполнена, ничего не делаем int j = Hash (t.key); //получаем адрес if (data[j].occupied!=0) { //если место занято, ищём новое for (int k = 1; k<size; k++) { j = Hash(t.key+k); if (data[j].occupied==0) break; } } if (data[j].occupied!=0) return *this; //если все места заняты, ничего не делаем data[j].occupied = 1; //записываем новый элемент data[j].key = t.key; strcpy (data[j].info, t.info); count++; //увеличиваем количество return *this; } CHashedTable& CHashedTable::operator-= (const Elem& t) { if (count == 0) return *this; //если таблица пуста, ничего не делаем int j = Hash (t.key); //получаем адрес if (data[j].occupied==0 || data[j].key!=t.key) { //если место свободно или на нём другой элемент for (int k = 1; k<size; k++) { //перебираем другие адреса j = Hash(t.key+k); if (data[j].occupied!=0 && data[j].key==t.key) break; } } if (data[j].occupied==0 || data[j].key!=t.key) return *this; //не нашли - ничего не делаем data[j].occupied = 0; //условно удаляем count--; //уменьшаем количество return *this; } Elem CHashedTable::operator[] (int key) { Elem null; //пустой элемент для возврата strcpy (null.info, "Not exist"); if (count == 0) return null; //если таблица пуста, возвращаем пустой int j = Hash (key); //ищем элемент аналогично прочим функциям if (data[j].occupied==0) { for (int k = 1; k<size; k++) { j = Hash(key+k); if (data[j].occupied!=0 && data[j].key==key) break; } } if (data[j].occupied == 0 || data[j].key!=key) return null; //если не нашли, возвращаем пустой else return data[j]; //иначе возвращаем найденный } bool CHashedTable::operator() (int key) { if (count == 0) return false; //аналогично [], только вместо элемента возвращаем true/false int j = Hash (key); if (data[j].occupied==0) { for (int k = 1; k<size; k++) { j = Hash(key+k); if (data[j].occupied!=0 && data[j].key==key) break; } } if (data[j].occupied == 0 || data[j].key!=key) return false; else return true; } void CHashedTable::Clear () { if (count==0) return; //если таблица пуста, нечего сжимать for (int i = 0; i<size; i++) { //идём по массиву if (data[i].occupied==0) continue; //если место свободно, пропускаем int j = Hash(data[i].key); //определяем "идеальный" адрес if (i==j) continue; //если элемент на нём и стоит, пропускаем for (int k = 0; k<size && j<i; k++) { //перебираем другие подходящие адреса, расположенные раньше текущего j = Hash(data[i].key+k); if (data[j].occupied==0) break; //если нашли свободный, прерываем } if (data[j].occupied==0 && j<i) { //если нашли свободный и он раньше текущего data[j] = data[i]; //кладём элемент на лучшую позицию data[i].occupied = 0; //старое место освобождаем } } } unsigned int CHashedTable::Hash (int key) { return key%size; //вычисляем адрес элемента как остаток от деления на максимальный размер таблицы } ostream& operator << (ostream& str, CHashedTable& t) //вывод { str << endl; for (int i=0; i<t.size; i++) { //выводим все элементы, кроме условно удалённых if (t.data[i].occupied == 0) continue; str << i << ": key = " << t.data[i].key << ", " << t.data[i].info << endl; } return str; } istream& operator >> (istream& str, CHashedTable& t) //ввод { Elem tmp; //временная переменная для элемента str >> tmp.key; //ввод ключа str >> tmp.info; //ввод информации t+=tmp; //добавление элемента return str; }

Консультировал: Киселёва Алёна aka Verena (Профессор) Дата отправки: 23.10.2011, 20:31 Прикреплённый файл: посмотреть » [2.3 кб]

Рейтинг ответа: 0 поблагодарить эксперта

Консультирует Jiraff (10-й класс):

Здравствуйте, Посетитель - 383089!
Реализация Вашего ТЗ может быть выполнена еще и так. VS2010.
А вообще для хэшированных таблиц неплохо было бы использовать STL в полной его функциональной возможности, включая алгоритмы, чтобы не изобретать велосипед)))

Приложение:
// DiffTable.cpp : Defines the entry point for the console application. // #include "stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { mixTable T(5); T-=T.getHash(2); tuple t={0,0,"Demo\0","Demo test text\0"}; T+=t; T+=T(T.getHash(5)); T.pack(); T+=T[T.getHash(1)]; std::cout<<"Initializated table content:"<<std::endl<<T<<"Enter new element text:"; std::cin>>T; std::cout<<"With entered text element:"<<std::endl<<T; return 0; } ////////////////////////////////////////////////////////////// // mixTable.h #pragma once #include <vector> #include <iostream> #define INF_LENGTH 255 #define HASH_CONST 12345//Элементы перемешиваются методом сложения с константой struct tuple//Элемент таблицы состоит из { int pKey;//ключа int busy;//поля занятости char information[INF_LENGTH];//и информации char* fullInformation;//память под строку символов в элементе таблицы и массив структур необходимой длины выделяется динамически, //во время выполнения программы (с помощью оператора new; память задается указателем на char в структуре и указателем на //структуру в состоянии класса) bool operator==(tuple& r) { return (pKey==r.pKey); }; tuple& operator=(tuple& t)//переопределение экземпляра класса (с помощью перегруженного оператора присваивания) для элемента таблицы { pKey=t.pKey; memcpy(information,t.information,INF_LENGTH); int sz=strlen(t.fullInformation); fullInformation=new char[sz+1]; memcpy(fullInformation,t.fullInformation,sz); fullInformation[sz]=\'\0\'; busy=1; return (*this); }; }; class mixTable { private: std::vector<tuple> value;//массив элементов int cnt;//количество всех элементов массива public: mixTable(void);//создание экземпляров структуры (элемента таблицы) с инициализацией начальным состоянием по умолчанию mixTable(int);//пустой конструктор для инициализации экземпляров и массивов экземпляров класса (таблицы) по умолчанию mixTable(tuple[], int);//создание экземпляров класса (таблицы) с инициализацией заданным количеством элементов из массива ключей и информации ~mixTable(void); int length(void);//узнать количество неудаленных элементов таблицы int getHash(int);//Преобразование ключа в индекс выполняется функцией хеширования friend std::ostream& operator<<(std::ostream&, mixTable&);//вывод таблицы в выходной поток friend std::istream& operator>>(std::istream&, mixTable&);//ввод значения экземпляра структуры (элемента таблицы) из входного потока tuple& operator()(int);//поиск элемента таблицы по ключу mixTable& operator+=(tuple&);//добавление элемента в таблицу tuple& operator[](int);//выборка информации из таблицы по заданному ключу mixTable& operator-=(int);//удаление элемента из таблицы (с отметкой в поле занятости) по ключу void zap(void); void pack(void);//чистка таблицы от "удаленных элементов" - реорганизация таблицы mixTable& operator=(mixTable&);//переопределение экземпляра класса (с помощью перегруженного оператора присваивания) для таблицы mixTable(mixTable&);//создание экземпляра класса (таблицы) с его инициализацией другим экземпляром класса (копирующий конструктор) //для элемента таблицы и таблицы }; ////////////////////////////////////////////////////////////// // mixTable.cpp #include "StdAfx.h" #include "mixTable.h" //создание экземпляров структуры (элемента таблицы) с инициализацией начальным состоянием по умолчанию mixTable::mixTable(void) :cnt(0) { } //пустой конструктор для инициализации экземпляров и массивов экземпляров класса (таблицы) по умолчанию mixTable::mixTable(int count) :cnt(0) { while(cnt<count) { tuple t={0,0,"Test information\0","Full test information string\0"}; (*this)+=t; } } //создание экземпляров класса (таблицы) с инициализацией заданным количеством элементов из массива ключей и информации mixTable::mixTable(tuple t[], int count) :cnt(0) { while(cnt<count) (*this)+=t[cnt]; } //создание экземпляра класса (таблицы) с его инициализацией другим экземпляром класса (копирующий конструктор) //для элемента таблицы и таблицы mixTable::mixTable(mixTable& T) :cnt(0) { while(++cnt<T.length()) (*this)+=T[T.getHash(cnt)]; } mixTable::~mixTable(void) { zap(); } //Преобразование ключа в индекс выполняется функцией хеширования int mixTable::getHash(int k) { int hash=k+HASH_CONST;//Элементы перемешиваются методом сложения с константой return hash; } //добавление элемента в таблицу mixTable& mixTable::operator+=(tuple& t) { tuple* pt=new tuple(t); pt->pKey=getHash(++cnt); pt->busy=1; value.insert(value.end(),*pt); return *this; } //удаление элемента из таблицы (с отметкой в поле занятости) по ключу mixTable& mixTable::operator-=(int k) { (*this)[k].busy=0; return *this; } //узнать количество неудаленных элементов таблицы int mixTable::length(void) { int j=cnt, i=cnt; while(j>0) if(value[--j].busy==0) i--; return i; } //вывод таблицы в выходной поток std::ostream& operator<<(std::ostream& os, mixTable& table) { int i=0; while(i<table.length()) { int k=table.getHash(++i); os<<table[k].information<<std::endl; if(table[k].fullInformation!=NULL) os<<table[k].fullInformation<<std::endl; } return os; } //ввод значения экземпляра структуры (элемента таблицы) из входного потока std::istream& operator>>(std::istream& is, mixTable& table) { tuple t; is>>t.information; int sz=strlen(t.information); t.fullInformation=new char[sz+1]; memcpy(t.fullInformation,&t.information,sz); t.fullInformation[sz]=\'\0\'; table+=t; return is; } //поиск элемента таблицы по ключу tuple& mixTable::operator()(int k) { tuple t={k,0,{\'\0\'},NULL}; tuple* pt=new tuple(t); int i=0; int l=length(); while(i<l) { pt->pKey=getHash(++i); if(*pt==t) { delete pt; pt=&(value[--i]); i=l; } } return *pt; } //выборка информации из таблицы по заданному ключу tuple& mixTable::operator[](int k) { return (*this)(k); } void mixTable::zap(void) { value.clear(); cnt=0; } //чистка таблицы от "удаленных элементов" - реорганизация таблицы void mixTable::pack(void) { int j=cnt; while(j>0) if(value[--j].busy==0) { value.erase(value.begin()+j); cnt--; } } //переопределение экземпляра класса (с помощью перегруженного оператора присваивания) для таблицы mixTable& mixTable::operator=(mixTable& T) { while(++cnt<T.length()) (*this)+=T[T.getHash(cnt)]; return *this; }

Консультировал: Jiraff (10-й класс) Дата отправки: 24.10.2011, 03:37

Рейтинг ответа: 0 поблагодарить эксперта

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль