Ассоциативный массив с возможностью хранения данных произвольных типов (хэш-массив)

1. Анализ задания

2. Разработка библиотеки классов

1.1 Диаграмма классов

1.2 Выбор языка программирования

1.3 Реализация классов

3. Разработка тестового приложения

3.1 Методика тестирования

3.2 Структура тестового приложения

4. Результаты тестирования Список литературы Приложение

1. Анализ задания Ассоциативный массив — абстрактный тип данных, позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу.

Ассоциативные массивы, называемые также хеш-массивами или просто хешами — позволяют легко создавать динамические структуры данных — списки и деревья разных видов, с помощью которых можно реализовать функциональность простой системы управления базой данных. Подобной конструкции не найти ни в одном современном языке программирования.

Ассоциативные массивы отличаются от массивов скаляров тем, что в них для ссылки на элементы используются строки, а не числовые индексы, т. е. концептуально они представляют собой список не просто значений элементов массива, а последовательность ассоциированных пар ключ/значение. Ключ является строковым литералом, и именно он и используется для доступа к ассоциированному с ним значению массива.

2 Разработка библиотеки классов

2.1 Диаграмма класса

Таблица

На данной диаграмме показан класс Element и Hashmas

2.2 Выбор языка программирования Сравнение C++ с Delphi:

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:

1. Синтаксис С++ немного мощнее, чем Java, так как С++ поддерживает перегрузку операторов и безопасные по типу перечисления. В случае необходимости можно использовать в коде С++ указатели и другие «незаконные» идиомы, размещая код внутри «небезопасных» блоков.

2. С++ совместим с кодом, написанным на других языках .NET. Это означает, что ИТ-отдел не обязан использовать только лишь С++ для своих разработок. По этой причине С++ может рассматриваться как более дешевая альтернатива Java.

3. Базовые классы .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

{

private:

int elem_id; //0-пусто 1-int 2-float 3-double 4-char 5-char*

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;

}

//перегруженные операторы = для каждого типа данных

const element& operator = (int& value)

{

this->elem_id=1;

this->data.eint=value;

return *this;

}

const element& operator = (float& value)

{

this->elem_id=2;

this->data.efloat=value;

return *this;

}

const element& operator = (double& value)

{

this->elem_id=3;

this->data.edouble=value;

return *this;

}

const element& operator = (char& value)

{

this->elem_id=4;

this->data.echar=value;

return *this;

}

const element& operator = (char*& value)

{

this->elem_id=5;

this->data.estring=value;

return *this;

}

//оператор вывода на экран

friend ostream& operator <<(ostream& os, element& e)

{

switch (e.elem_id)

{

case 1:

os<

break;

case 2:

os<

break;

case 3:

os<

break;

case 4:

os<

break;

case 5:

os<

break;

}

return os;

}

//перегруженные операторы приведения типов

operator int () throw (char*)

{

if (elem_id==1) return data. eint;

else throw («error»);

}

operator float () throw (char*)

{

if (elem_id==2) return data. efloat;

else throw («error»);

}

operator double () throw (char*)

{

if (elem_id==3) return data. edouble;

else throw («error»);

}

operator char () throw (char*)

{

if (elem_id==4) return data. echar;

else throw («error»);

}

operator char* () throw (char*)

{

if (elem_id==5) return data. estring;

else throw («error»);

}

//перегруженные операторы ввода данных

friend istream& operator >>(istream& is, element& e)

{

e.elem_id=0;

char s1[255], *s2;

cin>>s1;

if (strlen (s1)==1)

{

e.elem_id=4;

e.data.echar=s1[0];

}

if (strcmp (TypeToStr (StrToType (s1)), s1)==0)

{

e.elem_id=3;

e.data.edouble=StrToType (s1);

}

if (strcmp (TypeToStr (StrToType (s1)), s1)==0)

{

e.elem_id=2;

e.data.efloat=StrToType (s1);

}

if (strcmp (TypeToStr (StrToType (s1)), s1)==0)

{

e.elem_id=1;

e.data.eint=StrToType (s1);

}

if (e.elem_id==0)

{

e.elem_id=5;

e.data.estring=new char[strlen (s1)+1];

strcpy (e.data.estring, s1);

}

return is;

}

};

Класс Hashmas

class hashmas

{

private:

elem1 **mas; //массив

bool *deleted; //массив статуса элемента (удален или нет)

int count; //длина массива

int kol; //количество элементов в массиве

int hash2(char* s, int n) //хэш функции для вычисления индекса

{

if (n==0) return 0;

else

return (127*hash2(s, n-1)+s[n-1])%count;

}

int hash1(char* s, int i=0)

{

return (hash2(s, strlen (s))+3*i+5*i*i)%count;

}

void resize (); //увеличение размера массива в два раза при заполнении 50%

int seek (char *key); //поиск элемента по ключу

public:

hashmas (int k=8)

{

mas=new elem1*[k];

deleted=new bool[k];

count=k;

kol=0;

for (int i=0;i

{

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

{

return mas[this->seek (key)]->data;

}

friend ostream& operator <<(ostream& os, hashmas& h) //оператор вывода массива на экран

{

for (int i=0;i

{

if ((h.mas[i]->key≠NULL)&(h.deleted[i]==false))

os<<" key: «<key<<» data: «<<*(h.mas[i]->data)<<» n" ;

}

return os;

}

friend istream& operator >>(istream& is, hashmas& h) //ввод элемента массива для добавления

{

elem1 e;

char *s=new char[256];

element* k=new element;

bool b=false;

do

{

cout<<" Input key: «;

cin>>s;

e.key=new char[strlen (s)];

strcpy (e.key, s);

cout<<" Input data: «;

cin>>*k;

e.data=k;

b=h.add (e);

if (b==false) cout<<" This key already usedn" ;

while (b==false);

return is;

Все имена идентификаторов приведены и описаны в строгом соответствии с диаграммой класса пункта 2.1.

3. Разработка тестового приложения ассоциативный массив тестовый программирование

3.1 Методика тестирования

Методика тестирования заключается в разработке тестового C# приложения.

Необходимо на уровне кода:

1) Создать экземпляр класса.

2) Наполнить набор студентов элементами с помощью конструктора

3) Протестировать процедуру вывода набора на экран.

4) Протестировать процедуру поиска информации в наборе по дате.

3.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, Издательство: Питер

2. Технологии программирования С++, Давыдов В. Г., 2005., Издательство: «БХВ-Петербург»

3. Язык программирования С++. Леции и упражнения. Стивен Прата, 2003, Издательство: ДиаСофт, Sams

4. Отладка с С++. Руководство для разработчиков. К. Х. Паппас. У. Х. Мюррей, 2009, Издательство: Бином, McGraw-Hill Companies

5. С++. Структурное программирование. Практикум. Павловская Т. А., ЩупакЮ.А., 2003, Издательство:Питер

Приложение. Система классов

1. // hash-mas.cpp: определяет точку входа для консольного приложения.

2. #include «stdafx.h»

3. #include «conio.h»

4. #include «string.h»

5. #include

6. #include «generalized.cpp»

7. using namespace std;

8. struct elem1 //структура хранит ключ и сопутствующие данные

9. {

10. char *key; //ключ

11. element *data; //данные

12. };

13. class hashmas

14. {

15. private:

16. elem1 **mas; //массив

17. bool *deleted; //массив статуса элемента (удален или нет)

18. int count; //длина массива

19. int kol; //количество элементов в массиве

20. int hash2(char* s, int n) //хэш функции для вычисления индекса

21. {

22. if (n==0) return 0;

23. 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. }

30. void resize (); //увеличение размера массива в два раза при заполнении 50%

31. int seek (char *key); //поиск элемента по ключу

32. public:

33. hashmas (int k=8)

34. {

35. mas=new elem1*[k];

36. deleted=new bool[k];

37. count=k;

38. kol=0;

39. for (int i=0;i

40. {

41. mas[i]=new elem1;

42. mas[i]->key=NULL;

43. deleted[i]=false;

44. }

45. } //конструктор

46. bool add (elem1 e); //добавление элемента

47. bool del (char *key); //удаление элемента по ключу

48. element* operator [](char *key) //перегруженный оператор [] в скобках указывается key возвращается data

49. {

50. return mas[this->seek (key)]->data;

51. }

52. friend ostream& operator <<(ostream& os, hashmas& h) //оператор вывода массива на экран

53. {

54. for (int i=0;i

55. {

56. if ((h.mas[i]->key≠NULL)&(h.deleted[i]==false))

57. os<<" key: «<key<<» data: «<<*(h.mas[i]->data)<<» n" ;

58. }

59. return os;

60. }

61. friend istream& operator >>(istream& is, hashmas& h) //ввод элемента массива для добавления

62. {

63. elem1 e;

64. char *s=new char[256];

65. element* k=new element;

66. bool b=false;

67. do

68. {

69. cout<<" Input key: «;

70. cin>>s;

71. e. key=new char[strlen (s)];

72. strcpy (e.key, s);

73. cout<<" Input data: «;

74. cin>>*k;

75. e. data=k;

76. b=h.add (e);

77. if (b==false) cout<<" This key already usedn" ;

78. }

79. while (b==false);

80. return is;

81. }

82. };

83. bool hashmas: add (elem1 e)

84. {

85. int k=0,i=0;

86. do

87. {

88. k=hash1(e.key, i);

89. i++;

90. }

91. while ((mas[k]->key≠NULL)&(deleted[k]==false)&&(strcmp (mas[k]->key, e. key)≠0));

92. if (mas[k]->key==NULL)

93. {

94. mas[k]->key=e.key;

95. mas[k]->data=e.data;

96. deleted[k]=false;

97. kol++;

98. if (kol*2==count) this->resize ();

99. return true;

100. }

101. else

102. if ((strcmp (mas[k]->key, e. key)==0)&(deleted[k]==false)) return false;

103. else

104. {

105. mas[k]->key=e.key;

106. mas[k]->data=e.data;

107. deleted[k]=false;

108. kol++;

109. if (kol*2==count) this->resize ();

110. return true;

111. }

112. }

113. int hashmas: seek (char *key)

114. {

115. int k=0,i=0;

116. do

117. {

118. k=hash1(key, i);

119. i++;

120. }

121. while ((mas[k]->key≠NULL)&(deleted[k]==false)&&(strcmp (mas[k]->key, key)≠0));

122. if ((mas[k]->key≠NULL)&(deleted[k]==false)&&(strcmp (mas[k]->key, key)==0)) return k; else return -1;

123. }

124. void hashmas: resize ()

125. {

126. hashmas a (count*2);

127. for (int i=0;i

128. if ((mas[i]->key≠NULL)&(deleted[i]==false))

129. a. add (*mas[i]);

130. mas=a.mas;

131. count=a.count;

132. kol=a.kol;

133. deleted=a.deleted;

134. }

135. bool hashmas: del (char *key)

136. {

137. int k=this->seek (key);

138. if (k>-1)

139. {

140. deleted[k]=true;

141. return true;

142. kol—;

143. }

144. else return false;

145. }

146. int _tmain (int argc, _TCHAR* argv[])

147. {

148. hashmas a;

149. for (int i=0; i<3; i++)

150. cin>>a;

151. elem1 e;

152. e. key="key" ;

153. e. data=new element («datan»);

154. a. add (e);

155. cout<

156. cout<

157. a. del («key»);

158. cout<<" after delete element with key=keyn" ;

159. cout<

160. cout<<" after add element with key=keyn" ;

161. a. add (e);

162. cout<

163. _getch ();

164. return 0;

165. }

166. // generalized. cpp: определяет точку входа для консольного приложения.

167. #include «stdafx.h»

168. #include «conio.h»

169. #include «stdio.h»

170. #include

171. #include

172. using namespace std;

173. //функция преобразования строки в любой тип Т

174. template

175. T StrToType (const U &rhs)

176. {

177. T res;

178. std: stringstream ss (rhs);

179. ss>>res;

180. return res;

181. }

182. //функция преобразования любого типа Т в строку

183. template

184. char* TypeToStr (const T &rhs)

185. {

186. std: stringstream ss;

187. ss<

188. std: string s=ss.str ();

189. char *s1=new char[s.size ()+1];

190. strcpy (s1,s.c_str ());

191. return s1;

192. }

193. //объединение

194. union elem

195. {

196. int eint;

197. float efloat;

198. double edouble;

199. char echar;

200. char* estring;

201. };

202. class element

203. {

204. private:

205. int elem_id; //0-пусто 1-int 2-float 3-double 4-char 5-char*

206. elem data;

207. public:

208. //различные конструкторы

209. element (void) {elem_id=0;}

210. element (int value)

211. {

212. elem_id=1;

213. data. eint=value;

214. }

215. element (float value)

216. {

217. elem_id=2;

218. data. efloat=value;

219. }

220. element (double value)

221. {

222. elem_id=3;

223. data. edouble=value;

224. }

225. element (char value)

226. {

227. elem_id=4;

228. data. echar=value;

229. }

230. element (char* value)

231. {

232. elem_id=5;

233. data. estring=value;

234. }

235. //перегруженные операторы = для каждого типа данных

236. const element& operator = (int& value)

237. {

238. this->elem_id=1;

239. this->data.eint=value;

240. return *this;

241. }

242. const element& operator = (float& value)

243. {

244. this->elem_id=2;

245. this->data.efloat=value;

246. return *this;

247. }

248. const element& operator = (double& value)

249. {

250. this->elem_id=3;

251. this->data.edouble=value;

252. return *this;

253. }

254. const element& operator = (char& value)

255. {

256. this->elem_id=4;

257. this->data.echar=value;

258. return *this;

259. }

260. const element& operator = (char*& value)

261. {

262. this->elem_id=5;

263. this->data.estring=value;

264. return *this;

265. }

266. //оператор вывода на экран

267. friend ostream& operator <<(ostream& os, element& e)

268. {

269. switch (e.elem_id)

270. {

271. case 1:

272. os<

273. break;

274. case 2:

275. os<

276. break;

277. case 3:

278. os<

279. break;

280. case 4:

281. os<

282. break;

283. case 5:

284. os<

285. break;

286. }

287. return os;

288. }

289. //перегруженные операторы приведения типов

290. operator int () throw (char*)

291. {

292. if (elem_id==1) return data. eint;

293. else throw («error»);

294. }

295. operator float () throw (char*)

296. {

297. if (elem_id==2) return data. efloat;

298. else throw («error»);

299. }

300. operator double () throw (char*)

301. {

302. if (elem_id==3) return data. edouble;

303. else throw («error»);

304. }

305. operator char () throw (char*)

306. {

307. if (elem_id==4) return data. echar;

308. else throw («error»);

309. }

310. operator char* () throw (char*)

311. {

312. if (elem_id==5) return data. estring;

313. else throw («error»);

314. }

315. //перегруженные операторы ввода данных

316. friend istream& operator >>(istream& is, element& e)

317. {

318. e. elem_id=0;

319. char s1[255], *s2;

320. cin>>s1;

321. if (strlen (s1)==1)

322. {

323. e. elem_id=4;

324. e.data.echar=s1[0];

325. }

326. if (strcmp (TypeToStr (StrToType (s1)), s1)==0)

327. {

328. e. elem_id=3;

329. e.data.edouble=StrToType (s1);

330. }

331. if (strcmp (TypeToStr (StrToType (s1)), s1)==0)

332. {

333. e. elem_id=2;

334. e.data.efloat=StrToType (s1);

335. }

336. if (strcmp (TypeToStr (StrToType (s1)), s1)==0)

337. {

338. e. elem_id=1;

339. e.data.eint=StrToType (s1);

340. }

341. if (e.elem_id==0)

342. {

343. e. elem_id=5;

344. e.data.estring=new char[strlen (s1)+1];

345. strcpy (e.data.estring, s1);

346. }

347. return is;

348. }