Ассоциативный массив с возможностью хранения данных произвольных типов (хэш-массив)
Содержание
1. Анализ
задания
. Разработка
библиотеки классов
.1 Диаграмма
классов
.2 Выбор
языка программирования
.3 Реализация
классов
. Разработка
тестового приложения
.1
Методика тестирования
.2
Структура тестового приложения
. Результаты
тестирования
Список
литературы
Приложение
1. Анализ задания
Ассоциативный массив - абстрактный
тип данных
<#"587300.files/image001.gif">
Таблица
|
Объект
класса hashmas
|
Объект
класса element
|
|
-
массив структуры - массив статусов - длина массива - количество элементов в
массиве - хэш функция() - увеличение размера массива() - поиск элемента()
|
-
ид типа данных - данные (объединение)
|
|
+
добавление() + удаление() + оператор <<() + оператор >>() +
оператор []()
|
+
конструкторы() + оператор =() (для разных типов данных) + оператор <<()
+ оператор >>() + операторы преобразования типов
|
На данной диаграмме показан класс Element
и Hashmas
.2 Выбор языка программирования
Сравнение C++
с Delphi:, другой инструмент быстрой разработки от Borland, сочетает формы с
использованием собственного языка, основанного на языке Pascal. Delphi достиг
наивысшей популярности перед появлением VB6, будучи единственным простым языком
для создания компонентов СОМ и элементов управления Active X, который могли бы
использовать программисты, не знающие С++.
Основанный на использовании пар BEGIN … END для
разделения блоков кода, синтаксис Delphi является более громоздким и
прямолинейным, чем синтаксис С++.
Сравнение С++ с Java:
Очевидно, что Java оказал сильное влияние на
С++. Кто-то однажды назвал С++ - как “Cava”. Андерс Хелзберг (Anders
Hejlsberg), лидер группы разработчиков С++, возглавлял также разработку J++,
теперь уже не существующего компилятора Java от Microsoft. Синтаксисы Java и
С++ похожи. Даже структура библиотеки Java и базовых классов .NET практически
одинакова. Разумеется, оба языка используют байт-код.В настоящее время Java имеет
сильное преимущество перед С++ - платформенную независимость. Поскольку
существуют реализации среды исполнения Java для большинства вычислительных
платформ, один и тот же байт-код Java может теоретически выполняться на любой
из них. Это то, чего пока не могут достичь программы .NET.
С++ имеет три небольших преимущества перед Java:
. Синтаксис С++ немного мощнее, чем Java,
так как С++ поддерживает перегрузку операторов и безопасные по типу
перечисления. В случае необходимости можно использовать в коде С++ указатели и
другие “незаконные” идиомы, размещая код внутри “небезопасных” блоков.
. С++ совместим с кодом, написанным на
других языках .NET. Это означает, что ИТ-отдел не обязан использовать только
лишь С++ для своих разработок. По этой причине С++ может рассматриваться как
более дешевая альтернатива Java.
. Базовые классы .NET предоставляют С++
унифицированный, стандартизированный источник повсеместно требуемой
функциональности, такой как XML, работа с сетью и графикой. Для доступа к
аналогичным средствам программисты Java нередко вынуждены использовать
множество различных источников.
Сравнение С++ с JavaScript:
Как известно, JavaScript не имеет ничего общего
с Java. JavaScript - язык сценариев, применяемый на стороне клиента для
оживления web-страниц. Присвоение ему названия JavaScript было бесстыдной
маркетинговой политикой, направленной на получение прибыли от успеха Java. Во
времена, когда Java в основном использовался для создания апплетов, JavaScript
и Java иногда преследовали схожие цели.С++ похож на JavaScript тем. что оба
языка наследуют С-подобный синтаксис. С++, однако, не строго интерпретируется,
а компилируется в байт-код, который кэшируется и не может быть использован в
качестве языка сценариев для web- браузера (по крайней мере, сейчас). В то
время как JavaScript основное свое внимание уделяет откликам на события
web-браузера, С++ сосредотачивается на создании HTML и получении данных,
которые посылает web-браузер.
Как будет показано при обсуждении WebControls,
JavaScript и С++ могут использоваться совместно для достижения большего
эффекта. В Интернет - приложении код на С++ может определять, какой тип
браузера применяется на стороне клиента, и посылать ему фрагмент кода на
JavaScript, предназначенный для этого браузера. Разумеется, можно писать
страницы ASP.NET с использованием JavaScript (JScript) точно так же, как это
делается в ASP-страницах.
2.3 Реализация
классов
Класс Element
class element
{:elem_id; //0-пусто
1-int 2-float 3-double 4-char 5-char*data;:
//различные
конструкторы(void)
{elem_id=0;}(int value)
{_id=1;.eint=value;
}(float value)
{_id=2;.efloat=value;
}(double value)
{_id=3;.edouble=value;
}(char value)
{_id=4;.echar=value;
}(char* value)
{_id=5;
data.estring=value;
}
//перегруженные операторы = для каждого типа
данных
const element& operator =
(int& value)
{>elem_id=1;>data.eint=value;*this;
}element& operator = (float&
value)
{>elem_id=2;>data.efloat=value;*this;
}element& operator =
(double& value)
{>elem_id=3;>data.edouble=value;*this;
}element& operator = (char&
value)
{>elem_id=4;>data.echar=value;*this;
}element& operator = (char*&
value)
{>elem_id=5;>data.estring=value;
return *this;
}
//оператор вывода на экран
friend ostream& operator
<<(ostream& os, element& e)
{(e.elem_id)
{1:<<e.data.eint;;2:<<e.data.efloat;;3:<<e.data.edouble;;4:<<e.data.echar;;5:<<e.data.estring;
break;
}os;
}
//перегруженные операторы приведения типов
operator int () throw (char*)
{(elem_id==1) return data.eint;throw
("error");
}float () throw (char*)
{(elem_id==2) return
data.efloat;throw ("error");
}double () throw (char*)
{(elem_id==3) return
data.edouble;throw ("error");
}char () throw (char*)
{(elem_id==4) return
data.echar;throw ("error");
}char* () throw (char*)
{(elem_id==5) return data.estring;
else throw ("error");
}
//перегруженные операторы ввода данных
friend istream& operator
>>(istream& is, element& e)
{.elem_id=0;s1[255],
*s2;>>s1;(strlen(s1)==1)
{.elem_id=4;.data.echar=s1[0];
}(strcmp(TypeToStr<double>(StrToType<double>(s1)),s1)==0)
{.elem_id=3;.data.edouble=StrToType<double>(s1);
}(strcmp(TypeToStr<float>(StrToType<float>(s1)),s1)==0)
{.elem_id=2;.data.efloat=StrToType<float>(s1);
}(strcmp(TypeToStr<int>(StrToType<int>(s1)),s1)==0)
{.elem_id=1;.data.eint=StrToType<int>(s1);
}(e.elem_id==0)
{.elem_id=5;.data.estring=new char[strlen(s1)+1];(e.data.estring,s1);
}is;
}
};
Класс Hashmas
class hashmas
{:**mas; //массив*deleted; //массив статуса
элемента (удален или нет)count; //длина массиваkol; //количество элементов в
массивеhash2(char* s, int n) //хэш функции для вычисления индекса
{(n==0) return
0;(127*hash2(s,n-1)+s[n-1])%count;
}hash1(char* s,int i=0)
{(hash2(s,strlen(s))+3*i+5*i*i)%count;
}resize(); //увеличение размера массива в два
раза при заполнении 50%seek(char *key); //поиск элемента по ключу
public:(int k=8)
{=new elem1*[k];=new
bool[k];=k;=0;(int i=0;i<count;i++)
{[i]=new
elem1;[i]->key=NULL;[i]=false;
}
} //конструкторadd
(elem1 e); //добавление элемента
bool del(char *key); //удаление элемента по
ключу* operator [](char *key) //перегруженный оператор [] в скобках указывается
key возвращается data
{mas[this->seek(key)]->data;
}ostream& operator
<<(ostream& os, hashmas& h) //оператор
вывода
массива
на
экран
{(int i=0;i<h.count;i++)
{((h.mas[i]->key!=NULL)&(h.deleted[i]==false))<<"key:
"<<h.mas[i]->key<<" data: "<<*(h.mas[i]->data)<<"\n";
}os;
}istream& operator
>>(istream& is, hashmas& h) //ввод
элемента
массива
для
добавления
{e;*s=new char[256];* k=new
element;b=false;
{<<"Input key:
";>>s;.key=new char[strlen(s)];(e.key,s);<<"Input data:
";>>*k;.data=k;=h.add(e);(b==false) cout<<"This key
already used\n";(b==false);is;
Все имена идентификаторов приведены и описаны в
строгом соответствии с диаграммой класса пункта 2.1.
3. Разработка тестового приложения
ассоциативный массив тестовый программирование
3.1 Методика тестирования
Методика тестирования заключается в разработке
тестового C# приложения.
Необходимо на уровне кода:
1) Создать экземпляр класса.
) Наполнить набор студентов элементами с
помощью конструктора
) Протестировать процедуру вывода набора
на экран.
) Протестировать процедуру поиска
информации в наборе по дате.
.2 Структура тестового приложения
Система классов реализована на языке C++ и
состоит из двух классов и структуры.
Интерфейс класса hashmas
Свойство mas
- массив структуры с данными.
Свойство deleted
- массив статусов элементов.
Свойство count
- размер массива.
Свойство kol
- количество элементов в массиве.
Метод hash1
- первая хэш функция.
Метод hash2
- вторая хэш функция.
Метод resize
- увеличение размера массива.
Метод seek
- поиск элемента по ключу.
Метод operator
<< - перегруженный оператор вывода массива на
экран.
Метод operator
>> - перегруженный оператор ввода элемента массива
с клавиатуры и его добавление в массив.
Метод add
- добавление элемента.
Метод del
- удаление элемента.
Метод operator
[]
- перегруженный оператор [], доступ к элементу массива с заданным ключом.
Структура elem
Поле key
- ключ.
Поле data
- сопутствующие данные.
Интерфейс класса element
Свойство elem_id
- ид типа данных.
Свойство data
- данные.
Метод operator
=
- перегруженный оператор =.
Метод operator
<< - перегруженный оператор вывода.
Метод operator
>> - перегруженный оператор ввода.
Метод operator int() float() double() char() char*() - операторы
приведения
типов.
Объединение elem
Поле eint
- данные типа int.
Поле efloat
- данные типа float.
Поле edouble
- данные типа double.
Поле echar
- данные типа char.
Поле estring
- данные типа char*.
4. Результаты тестирования
На рисунке приведен результат работы приложения:
Тестовое приложение разработано на языке C++
консольное приложение.
Программа в цикле запрашивает у пользователя
несколько элементов. Добавляет еще один элемент. Выводит данные с определенным
ключом. Удаляет элемент с заданным ключом. Программа повторно заносит элемент с
удаленным ключом. Выводит массив на экран.
Список литературы
1. Самоучитель
С++, Крупник А.Б., 2005, Издательство: Питер
. Технологии
программирования С++, Давыдов В.Г.,2005. , Издательство:
"БХВ-Петербург"
. Язык
программирования С++. Леции и упражнения. Стивен Прата,2003, Издательство:
ДиаСофт, Sams
. Отладка
с С++. Руководство для разработчиков. К.Х. Паппас. У.Х. Мюррей, 2009,
Издательство: Бином, McGraw-Hill Companies
. С++.
Структурное программирование. Практикум . Павловская Т. А. ,
ЩупакЮ.А.,2003,Издательство:Питер
Приложение. Система классов
1. // hash-mas.cpp: определяет точку входа
для консольного приложения.
. #include "stdafx.h"
. #include "conio.h"
. #include "string.h"
. #include <iostream>
. #include "generalized.cpp"
. using namespace std;
. struct elem1 //структура хранит ключ и
сопутствующие данные
. {
. char *key; //ключ
. element *data; //данные
. };
. class hashmas
. {
. private:
. elem1 **mas; //массив
. bool *deleted; //массив статуса
элемента (удален или нет)
. int count; //длина массива
. int kol; //количество элементов в
массиве
. int hash2(char* s, int n) //хэш функции
для вычисления индекса
. {
. if (n==0) return 0;
. else
24. return
(127*hash2(s,n-1)+s[n-1])%count;
25. }
26. int hash1(char* s,int i=0)
27. {
28. return
(hash2(s,strlen(s))+3*i+5*i*i)%count;
29. }
. void resize(); //увеличение размера
массива в два раза при заполнении 50%
. int seek(char *key); //поиск элемента
по ключу
. public:
. hashmas(int k=8)
. {
. mas=new elem1*[k];
. deleted=new bool[k];
. count=k;
. kol=0;
39. for (int i=0;i<count;i++)
40. {
. mas[i]=new elem1;
. mas[i]->key=NULL;
. deleted[i]=false;
. }
. } //конструктор
. bool add (elem1 e); //добавление
элемента
. bool del(char *key); //удаление
элемента по ключу
. element* operator [](char *key)
//перегруженный оператор [] в скобках указывается key возвращается data
. {
50. return
mas[this->seek(key)]->data;
51. }
. friend ostream& operator
<<(ostream& os, hashmas& h) //оператор вывода массива на экран
. {
54. for (int
i=0;i<h.count;i++)
55. {
56. if
((h.mas[i]->key!=NULL)&(h.deleted[i]==false))
. os<<"key:
"<<h.mas[i]->key<<" data:
"<<*(h.mas[i]->data)<<"\n";
58. }
. return os;
. }
61. friend istream& operator
>>(istream& is, hashmas& h) //ввод
элемента
массива
для
добавления
62. {
. elem1 e;
. char *s=new char[256];
. element* k=new element;
. bool b=false;
. do
. {
. cout<<"Input key: ";
. cin>>s;
71. e.key=new char[strlen(s)];
72. strcpy(e.key,s);
. cout<<"Input data: ";
. cin>>*k;
. e.data=k;
. b=h.add(e);
77. if (b==false)
cout<<"This key already used\n";
78. }
. while (b==false);
. return is;
. }
. };
83. bool hashmas::add(elem1 e)
84. {
. int k=0,i=0;
. do
. {
88. k=hash1(e.key,i);
89. i++;
. }
91. while
((mas[k]->key!=NULL)&(deleted[k]==false)&&(strcmp(mas[k]->key,e.key)!=0));
. if (mas[k]->key==NULL)
93. {
94. mas[k]->key=e.key;
. mas[k]->data=e.data;
96. deleted[k]=false;
. kol++;
98. if (kol*2==count)
this->resize();
99. return true;
. }
. else
102. if
((strcmp(mas[k]->key,e.key)==0)&(deleted[k]==false)) return false;
103. else
. {
105. mas[k]->key=e.key;
. mas[k]->data=e.data;
107. deleted[k]=false;
. kol++;
109. if (kol*2==count)
this->resize();
110. return true;
. }
. }
113. int hashmas::seek(char *key)
114. {
. int k=0,i=0;
. do
. {
. k=hash1(key,i);
. i++;
. }
121. while
((mas[k]->key!=NULL)&(deleted[k]==false)&&(strcmp(mas[k]->key,key)!=0));
. if
((mas[k]->key!=NULL)&(deleted[k]==false)&&(strcmp(mas[k]->key,key)==0))
return k; else return -1;
123. }
. void hashmas::resize()
. {
. hashmas a(count*2);
127. for (int i=0;i<count;i++)
. if
((mas[i]->key!=NULL)&(deleted[i]==false))
129. a.add(*mas[i]);
. mas=a.mas;
. count=a.count;
. kol=a.kol;
. deleted=a.deleted;
. }
135. bool hashmas::del(char *key)
136. {
137. int k=this->seek(key);
138. if (k>-1)
. {
. deleted[k]=true;
. return true;
. kol--;
. }
. else return false;
. }
146. int _tmain(int argc, _TCHAR*
argv[])
147. {
. hashmas a;
. for (int i=0; i<3; i++)
. cin>>a;
. elem1 e;
. e.key="key";
153. e.data=new
element("data\n");
154. a.add(e);
. cout<<a;
. cout<<a["key"];
. a.del("key");
158. cout<<"after
delete element with key=key\n";
159. cout<<a;
160. cout<<"after add
element with key=key\n";
161. a.add(e);
. cout<<a;
. _getch();
. return 0;
. }
. // generalized.cpp: определяет точку
входа для консольного приложения.
. #include "stdafx.h"
. #include "conio.h"
. #include "stdio.h"
. #include <iostream>
. #include <sstream>
. using namespace std;
. //функция преобразования строки в любой
тип Т
174. template <typename T,
typename U>
. T StrToType(const U
&rhs)
176. {
. T res;
. ss>>res;
. return res;
. }
. //функция преобразования любого типа Т
в строку
. template <typename T>
184. char* TypeToStr(const T
&rhs)
185. {
. std::stringstream ss;
. ss<<rhs;
188. std::string s=ss.str();
. char *s1=new
char[s.size()+1];
. strcpy(s1,s.c_str());
191. return s1;
. }
. //объединение
. union elem
. {
. int eint;
. float efloat;
. double edouble;
. char echar;
. char* estring;
. };
. class element
. {
. private:
205. int elem_id; //0-пусто
1-int 2-float 3-double 4-char 5-char*
206. elem data;
. public:
. //различные конструкторы
. element(void) {elem_id=0;}
. element(int value)
. {
. elem_id=1;
. data.eint=value;
. }
. element(float value)
. {
. elem_id=2;
. data.efloat=value;
. }
. element(double value)
. {
. elem_id=3;
. data.edouble=value;
. }
. element(char value)
. {
. elem_id=4;
. data.echar=value;
. }
. element(char* value)
. {
. elem_id=5;
. data.estring=value;
. }
. //перегруженные операторы = для каждого
типа данных
236. const element& operator =
(int& value)
237. {
. this->elem_id=1;
. this->data.eint=value;
. return *this;
. }
242. const element& operator =
(float& value)
243. {
. this->elem_id=2;
. this->data.efloat=value;
. return *this;
. }
248. const element& operator =
(double& value)
249. {
. this->elem_id=3;
. this->data.edouble=value;
. return *this;
. }
254. const element& operator =
(char& value)
255. {
. this->elem_id=4;
. this->data.echar=value;
. return *this;
. }
260. const element& operator =
(char*& value)
261. {
. this->elem_id=5;
. this->data.estring=value;
. return *this;
. }
. //оператор вывода на экран
267. friend ostream& operator
<<(ostream& os, element& e)
268. {
. switch (e.elem_id)
. {
. case 1:
. os<<e.data.eint;
. break;
. case 2:
. os<<e.data.efloat;
. break;
. case 3:
. os<<e.data.edouble;
. break;
. case 4:
. os<<e.data.echar;
. break;
. case 5:
. os<<e.data.estring;
. break;
. }
. return os;
. }
. //перегруженные операторы приведения
типов
. operator int () throw (char*)
. {
292. if (elem_id==1) return
data.eint;
293. else throw ("error");
. }
. operator float () throw (char*)
. {
297. if (elem_id==2) return
data.efloat;
298. else throw ("error");
. }
. operator double () throw (char*)
. {
302. if (elem_id==3) return
data.edouble;
303. else throw ("error");
. }
. operator char () throw (char*)
. {
307. if (elem_id==4) return
data.echar;
308. else throw ("error");
. }
. operator char* () throw (char*)
. {
312. if (elem_id==5) return
data.estring;
313. else throw ("error");
. }
. //перегруженные операторы ввода данных
316. friend istream& operator
>>(istream& is, element& e)
317. {
. e.elem_id=0;
. char s1[255], *s2;
. cin>>s1;
. if (strlen(s1)==1)
. {
. e.elem_id=4;
. e.data.echar=s1[0];
. }
326. if
(strcmp(TypeToStr<double>(StrToType<double>(s1)),s1)==0)
327. {
. e.elem_id=3;
329. e.data.edouble=StrToType<double>(s1);
330. }
331. if
(strcmp(TypeToStr<float>(StrToType<float>(s1)),s1)==0)
332. {
. e.elem_id=2;
334. e.data.efloat=StrToType<float>(s1);
335. }
336. if
(strcmp(TypeToStr<int>(StrToType<int>(s1)),s1)==0)
337. {
. e.elem_id=1;
339. e.data.eint=StrToType<int>(s1);
340. }
. if (e.elem_id==0)
. {
. e.elem_id=5;
344. e.data.estring=new
char[strlen(s1)+1];
. strcpy(e.data.estring,s1);
346. }
. return is;
. }