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

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

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

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

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

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

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

Номер выпуска:	1703
Дата выхода:	03.12.2011, 02:30
Администратор рассылки:	Киселёва Алёна aka Verena (Профессор)
Подписчиков / экспертов:	282 / 164
Вопросов / ответов:	1 / 1

Консультация # 184593: Ещё раз здравствуйте, уважаемые эксперты! Прошу переработать программу в приложение с учётом 3его пункта задания. Сам класс работает, нужно только переработать его в соответствии с 3им пунктом. Также прошу объяснить назначение копирующего конструктора и оператора присваивания. Задание: 1. Разработать класс "перемешанная таблица" ...

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

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

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

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

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

Приложение:
//HashedTable.h #pragma once #include <iostream> using namespace std; struct Elem { //элемент таблицы int key; //ключ int occupied; //признак занятости char* info; //информация Elem () : key(0),occupied(0),info(NULL) {}; //конструктор по умолчанию ~Elem () { if (info!=NULL) delete [] info; } //деструктор для строки Elem (const Elem& el):key(el.key),occupied(el.occupied) { //конструктор копирования info = new char [strlen(el.info)+1]; strcpy (info, el.info);} Elem& operator = (const Elem el) { //оператор присваивания key=el.key; occupied = el.occupied; if (info!=NULL) delete [] info; info = new char [strlen(el.info)+1]; strcpy (info, el.info); return *this; } }; class CHashedTable { static const int step = 1; unsigned int size; //количество элементов в таблице unsigned int count; //количество элементов в таблице Elem* data; //массив данных bool localadding; //флаг для перехеширования 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); //функция хеширования bool HasKey (int key); void Resize (int newsize); }; //HashedTable.cpp #include "StdAfx.h" #include "HashedTable.h" #include <string.h> CHashedTable::CHashedTable() : count(0), size(0), data(NULL) //обнуляем число элементов { localadding = false; } CHashedTable::~CHashedTable() { if (data!=NULL) delete [] data; } CHashedTable::CHashedTable (Elem* elem, int n) //конструктор из массива { localadding = false; data = new Elem [n]; count = size = n; //сохраняем количество for (int i = 0; i<n; i++) { //идём по элементам if (HasKey (elem[i].key)) continue; int j = Hash(elem[i].key); //получаем адрес if (data[j].occupied!=0) { //если уже занят for (int k = 1; k<count; 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; data[j].info = new char [strlen(elem[i].info)+1]; strcpy (data[j].info, elem[i].info); } } CHashedTable::CHashedTable (const CHashedTable &t) //конструктор копирования { localadding = false; data = new Elem [t.size]; count = t.count; //копируем всё из другого экземпляра size = t.size; for (int i = 0; i<size; i++) { data[i].key = t.data[i].key; data[i].occupied = t.data[i].occupied; data[i].info = new char [strlen(t.data[i].info)+1]; strcpy (data[i].info, t.data[i].info); } } CHashedTable& CHashedTable::operator= (const CHashedTable t) //оператор присваивания { localadding = false; data = new Elem [t.size]; count = t.count; //копируем всё из другого экземпляра size = t.size; for (int i = 0; i<size; i++) { data[i].key = t.data[i].key; data[i].occupied = t.data[i].occupied; data[i].info = new char [strlen(t.data[i].info)+1]; strcpy (data[i].info, t.data[i].info); } return *this; } CHashedTable& CHashedTable::operator+= (const Elem& t) { int t1=-1, t2=-1; if (!localadding && size<count+1) Resize (count+1); //если это не перехеширование и памяти не хватает - выделяем int start, j, free = -1; start = j = Hash (t.key); //получаем адрес do { if (data[j].occupied==1 && data[j].key==t.key) return *this; //место занято и ключи совпадают,выходим if (data[j].occupied==-1) if(free == -1) free = j; if (data[j].occupied == 0) { if(free != -1) j = free; data[j].occupied = 1; //записываем новый элемент data[j].key = t.key; data[j].info = new char [strlen(t.info)+1]; strcpy (data[j].info, t.info); if (!localadding) count++; //увеличиваем количество return *this; } j = (j+step)%size; } while(start != j); if(free == -1) return *this; else j = free; data[j].occupied = 1; //записываем новый элемент data[j].key = t.key; data[j].info = new char [strlen(t.info)+1]; strcpy (data[j].info, t.info); if (!localadding) count++; //увеличиваем количество return *this; } CHashedTable& CHashedTable::operator-= (const Elem& t) { if (count == 0) return *this; //если таблица пуста, ничего не делаем int j = Hash (t.key); //получаем адрес if (data[j].occupied==0) return *this; //такого нет и не было if (data[j].occupied==-1 || data[j].key!=t.key) { //если место свободно или на нём другой элемент for (int k = 1; k<size; k++) { //перебираем другие адреса //j = Hash(t.key+k); j = (j+step)%size; if (data[j].occupied==1 && data[j].key==t.key) break; //если место занято и ключи совпадают, прерываем } } if (data[j].occupied==0 || data[j].key!=t.key) return *this; //не нашли - ничего не делаем data[j].occupied = -1; //условно удаляем count--; //уменьшаем количество return *this; } Elem CHashedTable::operator[] (int key) { Elem null; //пустой элемент для возврата if (count == 0) return null; //если таблица пуста, возвращаем пустой int start, j; start = j = Hash (key); //ищем элемент аналогично прочим функциям if (data[j].occupied==0) return null; //такого нет и не было do { if (data[j].occupied == 1 && data[j].key==key) return data[j]; //иначе возвращаем найденный j = (j+step)%size; } while(j != start && data[j].occupied != 0); return null; //если не нашли, возвращаем пустой } bool CHashedTable::operator() (int key) { if (count == 0) return false; //если таблица пуста, возвращаем пустой int start, j; start = j = Hash (key); //ищем элемент аналогично прочим функциям if (data[j].occupied==0) return false; //такого нет и не было do { if (data[j].occupied == 1 && data[j].key==key) return true; //иначе возвращаем найденный j = (j+step)%size; } while(j != start && data[j].occupied != 0); return false; //если не нашли, возвращаем пустой } void CHashedTable::Clear () { if (count==0 || count==size) return; //если таблица пуста, нечего сжимать Elem* tmp = new Elem [count]; int oldsize = size; size = count; for (int i = 0; i<oldsize; i++) { //идём по массиву if (data[i].occupied==0 || data[i].occupied==-1) continue; //если место свободно, пропускаем int j = Hash(data[i].key); //определяем "идеальный" адрес if (i==j) continue; //если элемент на нём и стоит, пропускаем for (int k = 0; k<size && j<i; k++) { //перебираем другие подходящие адреса, расположенные раньше текущего //j = (j+step)%size;j = Hash(data[i].key+k); j = (j+k)%size; if (data[j].occupied==0 || data[j].occupied==-1) break; //если нашли свободный, прерываем } if ((data[j].occupied==0 || data[j].occupied==-1) && j<i) { //если нашли свободный и он раньше текущего data[j] = data[i]; //кладём элемент на лучшую позицию data[i].occupied = -1; //старое место освобождаем } } for (int i=0; i<count; i++) tmp[i] = data[i]; delete [] data; data = tmp; } unsigned int CHashedTable::Hash (int key) { return key%size; //вычисляем адрес элемента как остаток от деления на максимальный размер таблицы } bool CHashedTable::HasKey (int key) { for (int i = 0; i<size; i++) if (data[i].occupied!=0 && data[i].key == key) return true; return false; } void CHashedTable::Resize (int newsize) //перевыделение памяти и перехеширование { localadding = true; //перехеширование Elem* tmp = data; //сохраняем указатель data = new Elem [newsize]; //выделяем новую память int oldsize = size; //сохраняем старый размер size = newsize; //пишем новый размер for (int i=0; i<oldsize; i++) //перехешируем с новым размером *this+=tmp[i]; if (tmp!=NULL) delete [] tmp; //если указатель не пустой, освобождаем старую память localadding = false; //перехеширование закончили } ostream& operator << (ostream& str, CHashedTable& t) //вывод { str << endl; for (int i=0; i<t.size; i++) { //выводим все элементы, кроме пустых и условно удалённых if (t.data[i].occupied == 0 || t.data[i].occupied == -1) continue; str << i << ": key = " << t.data[i].key << ", " << t.data[i].info << endl; } return str; } istream& operator >> (istream& str, CHashedTable& t) //ввод { Elem tmp; //временная переменная для элемента cout << "Key: " << endl; str >> tmp.key; //ввод ключа cout << "Information: " << endl; tmp.info = new char [101]; str >> tmp.info; //ввод информации t+=tmp; //добавление элемента return str; } //11.cpp #include "StdAfx.h" #include <conio.h> #include <stdlib.h> #include "HashedTable.h" CHashedTable c; char menu () { system ("cls"); cout << "1. Default (empty)\n"; cout << "2. From massive\n"; cout << "3. Input\n"; cout << "4. Output\n"; cout << "5. Search element\n"; cout << "6. Search information\n"; cout << "7. Add element\n"; cout << "8. Delete element\n"; cout << "9. Reorganize table\n"; cout << "0. Exit\n"; cout << "\nGo to "; char c; cin >> c; return c; } void p1 () { CHashedTable a; cout << "a=" << a << endl; getch(); } void p2 () { Elem e [4]; e[0].key = 102; e[0].info = new char [10]; strcpy (e[0].info, "first"); e[1].key = 113; e[1].info = new char [10]; strcpy (e[1].info, "second"); e[2].key = 345; e[2].info = new char [10]; strcpy (e[2].info, "third"); e[3].key = 13; e[3].info = new char [10]; strcpy (e[3].info, "fourth"); CHashedTable b (e, 4); cout << "b=" << b << endl; getch(); } void p3 () { cin >> c; //работа потокового ввода >>, с клавиатуры вводятся данные для нового элемента cout << "c=" << c << endl; getch(); } void p4 () { cout << "c=" << c << endl; //выводим на экран, демонстрация работы оператора << getch(); } void p5 () { int k; cout << "Key: " << endl; cin >> k; if (c(k)==true) cout << "Element found" << endl; else cout << "Element not found" << endl; //cout << "c(key) = " << c(k) << endl; //работа оператора () getch(); } void p6 () { int k; cout << "Key: " << endl; cin >> k; cout << "c[key] = " << c[k].info << endl; //работа оператора [] getch(); } void p7 () { Elem e; e.key = 102; e.info = new char [10]; strcpy (e.info, "first"); c+=e; //добавляем в объект а элемент e[0] cout << "c+=e[0]" << c << endl; //выводим результат getch(); } void p8 () { Elem e [1]; cout << "Key: " << endl; cin >> e[0].key; c-=e[0]; //удаляем из объекта b элемент e[1] cout << "b-=e[0]" << c << endl; //выводим результат getch(); } void p9 () { c.Clear(); //сжатие объекта b cout << "c.Clear=" << c << endl; //выводим результат getch(); } int _tmain(int argc, _TCHAR* argv[]) { //пример bool p = true; while (p) { try { char c = menu(); switch (c) { case \'1\': p1(); break; case \'2\': p2(); break; case \'3\': p3(); break; case \'4\': p4(); break; case \'5\': p5(); break; case \'6\': p6(); break; case \'7\': p7(); break; case \'8\': p8(); break; case \'9\': p9(); break; case \'0\': p = false; break; } } catch (char* ex) { cout << ex; } } return 0; }

Консультировал: Киселёва Алёна aka Verena (Профессор) Дата отправки: 02.12.2011, 12:34

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

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

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