Метод сортировки - метод Шелла, класс - битовая строка


Добавил:DMT
Дата создания:23 апреля 2008, 23:28
Дата обновления:23 апреля 2008, 23:30
Просмотров:5772 последний позавчера, 8:15
Комментариев: 1
Метод сортировки - метод вставок, класс - строка символов
Код на C++
  1. #include <iostream.h>
  2. #include <string.h>
  3. #include <conio.h>
  4. #include <stdlib.h>
  5. #define n 100
  6.  
  7. //класс: Битовая строка
  8. class BinStr
  9. {
  10. private:
  11. char *s; //сама строка
  12. int length; //указатель на длину
  13. public:
  14. BinStr();
  15. BinStr(char *);
  16. BinStr(const BinStr &);
  17. ~BinStr();
  18. int operator> (BinStr &);
  19. int operator>=(BinStr &);
  20. int operator< (BinStr &);
  21. int operator<=(BinStr &);
  22. int operator==(BinStr &);
  23. BinStr &operator=(BinStr &Object);//перегрузка оператора присваивания
  24. friend ostream &operator<<(ostream &, BinStr &);
  25. };
  26.  
  27. BinStr::BinStr()
  28. {
  29. s=new char[1];
  30. *s='\0';
  31. length=0;
  32. }
  33. BinStr::BinStr(char *st)
  34. {
  35. length=strlen(st);
  36. s=new char[(length)+1];
  37. strcpy (s,st);
  38. }
  39. BinStr::BinStr(const BinStr &s1)
  40. {
  41. length=strlen(s1.s);
  42. s=new char[(length)+1];
  43. strcpy (s,s1.s);
  44. }
  45. BinStr::~BinStr()
  46. {
  47. delete s;
  48. }
  49.  
  50. int BinStr::operator> (BinStr &Object)
  51. {
  52. int i;
  53. //если длина левой строки больше правой
  54. if(length>Object.length)
  55. {
  56. //проверяем, есть ли в старших битах левой
  57. //строки, которых нет в правой, единицы
  58. //если есть, то возвращаем 1
  59. for(i=0;i<length-Object.length;i++)
  60. if((s[i]-48)==1)
  61. return 1;
  62. //если единиц не оказалось, то побитово сравниваем
  63. //обе строки: оставшуюся часть правой строки со всей левой,
  64. //до нарушения равновесия
  65. for(i=0;i<Object.length;i++)
  66. if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
  67. return 0;
  68. else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
  69. return 1;
  70. //если строки равны, возвращаем 0
  71. return 0;
  72. }
  73. //далее следует все аналогично для оставшихся двух случаев,
  74. //когда правая строка длиннее левой и когда длины строк равны
  75. else if(length<Object.length)
  76. {
  77. for(i=0;i<Object.length-length;i++)
  78. if((Object.s[i]-48)==1)
  79. return 0;
  80. for(i=0;i<length;i++)
  81. if((s[i]-48)<(Object.s[i+Object.length-length]-48))
  82. return 0;
  83. else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
  84. return 1;
  85. //если строки равны, возвращаем 0
  86. return 0;
  87. }
  88. //когда длины строк равны, просто побитово сравниваем обе строки
  89. //до нарушения равновесия
  90. for(i=0;i<length;i++)
  91. if((s[i]-48)<(Object.s[i]-48))
  92. return 0;
  93. else if((s[i]-48)>(Object.s[i]-48))
  94. return 1;
  95. //если строки равны, возвращаем 0
  96. return 0;
  97. }
  98. int BinStr::operator>=(BinStr &Object)
  99. {
  100. int i;
  101. //если длина левой строки больше правой
  102. if(length>Object.length)
  103. {
  104. //проверяем, есть ли в старших битах левой
  105. //строки, которых нет в правой, единицы
  106. //если есть, то возвращаем 1
  107. for(i=0;i<length-Object.length;i++)
  108. if((s[i]-48)==1)
  109. return 1;
  110. //если единиц не оказалось, то побитово сравниваем
  111. //обе строки: оставшуюся часть правой строки со всей левой,
  112. //до нарушения равновесия
  113. for(i=0;i<Object.length;i++)
  114. if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
  115. return 0;
  116. else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
  117. return 1;
  118. //если строки равны, возвращаем 1
  119. return 1;
  120. }
  121. //далее следует все аналогично для оставшихся двух случаев,
  122. //когда правая строка длиннее левой и когда длины строк равны
  123. else if(length<Object.length)
  124. {
  125. for(i=0;i<Object.length-length;i++)
  126. if((Object.s[i]-48)==1)
  127. return 0;
  128. for(i=0;i<length;i++)
  129. if((s[i]-48)<(Object.s[i+Object.length-length]-48))
  130. return 0;
  131. else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
  132. return 1;
  133. //если строки равны, возвращаем 1
  134. return 1;
  135. }
  136. //когда длины строк равны, просто побитово сравниваем обе строки
  137. //до нарушения равновесия
  138. for(i=0;i<length;i++)
  139. if((s[i]-48)<(Object.s[i]-48))
  140. return 0;
  141. else if((s[i]-48)>(Object.s[i]-48))
  142. return 1;
  143. //если строки равны, возвращаем 1
  144. return 1;
  145. }
  146.  
  147. int BinStr::operator< (BinStr &Object)
  148. {
  149. int i;
  150. //если длина левой строки больше правой
  151. if(length>Object.length)
  152. {
  153. //проверяем, есть ли в старших битах левой
  154. //строки, которых нет в правой, единицы
  155. //если есть, то возвращаем 0
  156. for(i=0;i<length-Object.length;i++)
  157. if((s[i]-48)==1)
  158. return 0;
  159. //если единиц не оказалось, то побитово сравниваем
  160. //обе строки: оставшуюся часть правой строки со всей левой,
  161. //до нарушения равновесия
  162. for(i=0;i<Object.length;i++)
  163. if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
  164. return 1;
  165. else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
  166. return 0;
  167. //если строки равны, возвращаем 0
  168. return 0;
  169. }
  170. //далее следует все аналогично для оставшихся двух случаев,
  171. //когда правая строка длиннее левой и когда длины строк равны
  172. else if(length<Object.length)
  173. {
  174. for(i=0;i<Object.length-length;i++)
  175. if((Object.s[i]-48)==1)
  176. return 1;
  177. for(i=0;i<length;i++)
  178. if((s[i]-48)<(Object.s[i+Object.length-length]-48))
  179. return 1;
  180. else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
  181. return 0;
  182. //если строки равны, возвращаем 0
  183. return 0;
  184. }
  185. //когда длины строк равны, просто побитово сравниваем обе строки
  186. //до нарушения равновесия
  187. for(i=0;i<length;i++)
  188. if((s[i]-48)<(Object.s[i]-48))
  189. return 1;
  190. else if((s[i]-48)>(Object.s[i]-48))
  191. return 0;
  192. //если строки равны, возвращаем 0
  193. return 0;
  194. }
  195.  
  196. int BinStr::operator<=(BinStr &Object)
  197. {
  198. int i;
  199. //если длина левой строки больше правой
  200. if(length>Object.length)
  201. {
  202. //проверяем, есть ли в старших битах левой
  203. //строки, которых нет в правой, единицы
  204. //если есть, то возвращаем 0
  205. for(i=0;i<length-Object.length;i++)
  206. if((s[i]-48)==1)
  207. return 0;
  208. //если единиц не оказалось, то побитово сравниваем
  209. //обе строки: оставшуюся часть правой строки со всей левой,
  210. //до нарушения равновесия
  211. for(i=0;i<Object.length;i++)
  212. if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
  213. return 1;
  214. else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
  215. return 0;
  216. //если строки равны, возвращаем 1
  217. return 1;
  218. }
  219. //далее следует все аналогично для оставшихся двух случаев,
  220. //когда правая строка длиннее левой и когда длины строк равны
  221. else if(length<Object.length)
  222. {
  223. for(i=0;i<Object.length-length;i++)
  224. if((Object.s[i]-48)==1)
  225. return 1;
  226. for(i=0;i<length;i++)
  227. if((s[i]-48)<(Object.s[i+Object.length-length]-48))
  228. return 1;
  229. else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
  230. return 0;
  231. //если строки равны, возвращаем 1
  232. return 1;
  233. }
  234. //когда длины строк равны, просто побитово сравниваем обе строки
  235. //до нарушения равновесия
  236. for(i=0;i<length;i++)
  237. if((s[i]-48)<(Object.s[i]-48))
  238. return 1;
  239. else if((s[i]-48)>(Object.s[i]-48))
  240. return 0;
  241. //если строки равны, возвращаем 1
  242. return 1;
  243. }
  244.  
  245. int BinStr::operator==(BinStr &Object)
  246. {
  247. int i;
  248. //если длина левой строки больше правой
  249. if(length>Object.length)
  250. {
  251. //проверяем, есть ли в старших битах левой
  252. //строки, которых нет в правой, единицы
  253. //если есть, то возвращаем 0
  254. for(i=0;i<length-Object.length;i++)
  255. if((s[i]-48)==1)
  256. return 0;
  257. //если единиц не оказалось, то побитово сравниваем
  258. //обе строки: оставшуюся часть правой строки со всей левой,
  259. //до нарушения равновесия
  260. for(i=0;i<Object.length;i++)
  261. if((s[i+(length-Object.length)]-48)!=(Object.s[i]-48))
  262. return 0;
  263. //если строки равны, возвращаем 1
  264. return 1;
  265. }
  266. //далее следует все аналогично для оставшихся двух случаев,
  267. //когда правая строка длиннее левой и когда длины строк равны
  268. else if(length<Object.length)
  269. {
  270. for(i=0;i<Object.length-length;i++)
  271. if((Object.s[i]-48)==1)
  272. return 0;
  273. for(i=0;i<length;i++)
  274. if((s[i]-48)!=(Object.s[i+Object.length-length]-48))
  275. return 0;
  276. //если строки равны, возвращаем 1
  277. return 1;
  278. }
  279. //когда длины строк равны, просто побитово сравниваем обе строки
  280. //до нарушения равновесия
  281. for(i=0;i<length;i++)
  282. if((s[i]-48)!=(Object.s[i]-48))
  283. return 0;
  284. //если строки равны, возвращаем 1
  285. return 1;
  286. }
  287.  
  288. BinStr& BinStr::operator=(BinStr &Object)
  289. {
  290. length=strlen(Object.s);
  291. s=new char[(length)+1];
  292. strcpy (s,Object.s);
  293. return *this;
  294. }
  295.  
  296.  
  297. ostream &operator<<(ostream &fo, BinStr &fp)
  298. {
  299. fo<<fp.s;
  300. return fo;
  301. }
  302.  
  303. template <class Type>
  304. void shell(Type *x, int n1)
  305. { int i,j,k,gap;
  306. Type t;
  307. int a[5]={9,5,3,2,1};
  308. for(k=0; k<5; k++)
  309. { gap=a[k];
  310. for(i=gap; i<n1; i++)
  311. { t=x[i];
  312. for(j=i-gap; t<x[j]&&j>=0; j=j-gap)
  313. x[j+gap]=x[j];
  314. x[j+gap]=t;
  315. }
  316. }
  317. }
  318.  
  319. void main()
  320. {
  321. int i;
  322. int mas1[n];
  323. float mas2[n];
  324. randomize();
  325. for (i=0;i<n;i++)
  326. {
  327. mas1[i]=random(n);
  328. mas2[i]=random(n)*0.01;
  329. }
  330.  
  331. clrscr();
  332. cout<<" Сортировка методом Шелла\n"<<endl;
  333. //сортировка целых чисел
  334. shell(mas1, n);
  335. cout<<"Отсортированный массив целых чисел:\n"<<endl;
  336. for (i=0;i<n;i++)
  337. cout<<mas1[i]<<" ";
  338. //сортировка чисел с плавающей точкой
  339. shell(mas2, n);
  340. cout<<endl<<"\nОтсортированный массив чисел с плавающей точкой:\n"<<endl;
  341. for (i=0;i<n;i++)
  342. cout<<mas2[i]<<" ";
  343.  
  344. BinStr mas3[n]={"1001","1000","1100","1010","1100","1011","0011","1111",
  345. "000000000001","0110","1110","011001","1111","0011","0110",
  346. "1011","0101","0011","0010","1111"};
  347. //сортировка битовых строк
  348. shell(mas3, n);
  349. cout<<endl<<endl<<"Отсортированный массив битовых строк:"<<endl;
  350. for (i=0;i<n;i++)
  351. cout<<mas3[i]<<" ";
  352. }
При использовании обязательна ссылка на http://DMTSoft.ru
Результаты работы программы
Сортировка методом Шелла
Отсортированный массив целых чисел:
0 1 1 2 3 4 4 5 6 6 7 9 9 10 10 11 11 11 13 15 16 16 16 17 18 19 19 20 20 21 21
22 22 24 24 24 26 26 26 28 28 33 33 35 37 37 38 38 42 45 45 45 46 46 46 48 53 54
55 55 55 56 57 62 62 62 64 64 65 65 69 69 70 71 71 71 71 73 74 75 75 75 77 79 8
0 80 80 80 83 86 88 88 90 92 93 95 96 96 98 99

Отсортированный массив чисел с плавающей точкой:
0 0 0.01 0.02 0.02 0.04 0.07 0.07 0.1 0.11 0.12 0.12 0.13 0.14 0.17 0.17 0.17 0.
19 0.2 0.2 0.2 0.21 0.22 0.22 0.22 0.23 0.23 0.24 0.24 0.27 0.27 0.27 0.28 0.29
0.3 0.31 0.34 0.35 0.35 0.35 0.37 0.37 0.37 0.4 0.43 0.43 0.44 0.44 0.46 0.48 0.
5 0.51 0.52 0.53 0.54 0.55 0.55 0.55 0.56 0.59 0.6 0.61 0.63 0.63 0.67 0.69 0.7
0.71 0.73 0.73 0.74 0.74 0.74 0.76 0.77 0.77 0.78 0.79 0.8 0.81 0.82 0.83 0.86 0
.87 0.87 0.88 0.9 0.9 0.9 0.9 0.92 0.93 0.93 0.94 0.94 0.94 0.94 0.97 0.97 0.98

Отсортированный массив битовых строк:
000000000001 0010 0011 0011 0011 0101 0110 0110 1000 1001 1010 1011 1011 1100 11 00 1110 1111 1111 1111 011001
up