Пирамидальная сортировка битовых строк на Си(C++)


Добавил:DMT
Дата создания:30 апреля 2008, 21:32
Дата обновления:30 апреля 2008, 21:32
Просмотров:8678 последний вчера, 4:47
Комментариев: 0
Исходник программы - пирамидальная сортировка битовых строк
Параметризованная подпрограмма сортировки пирамидальным методом. Отлажена на целых числах и числах с плавающей точкой.
Класс объектов массива, предназначенного для сортировки.
Перегрузка для него операций присваивания и операции сравнения <, <=, ==, >=, >.
Программа, сортирует массив объектов построенного класса - битовых строк с помощью написанной параметризованной подпрограммы.
Код на 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.  
  304. template <class Type>
  305. void swap(Type *a, Type *b)
  306. {
  307. Type temp=*a;
  308. *a=*b;
  309. *b=temp;
  310. }
  311.  
  312. template <class Type>
  313. void SiftUp(Type *x,int n1)
  314. {
  315. int i=n1,p;
  316. while(i>0)
  317. {
  318. p=i/2;
  319. if(x[p]>=x[i]) break;
  320. swap(&x[p],&x[i]);
  321. i=p;
  322. }
  323. }
  324.  
  325. template <class Type>
  326. void SiftDown(Type *x,int n1)
  327. {
  328. int i=0,c;
  329. while((c=2*i)<=n1)
  330. {
  331. if(((c+1)<=n1)&&(x[c+1]>x[c])) c+=1;
  332. if(x[i]>=x[c]) break;
  333. swap(&x[c],&x[i]);
  334. i=c;
  335. }
  336. }
  337.  
  338. template <class Type>
  339. void phyramid(Type *mas1,int n1)
  340. {
  341.  
  342. for(int i=1; i<n1;) SiftUp(mas1,i++);
  343. for(i=(n1-1); i>=1; i--)
  344. {
  345. swap(&mas1[0], &mas1[i]);
  346. SiftDown(mas1,i-1);
  347. }
  348.  
  349. }
  350.  
  351. void main()
  352. {
  353. int i;
  354. int mas1[n];
  355. float mas2[n];
  356. randomize();
  357. for (i=0;i<n;i++)
  358. {
  359. mas1[i]=random(n);
  360. mas2[i]=random(n)*0.01;
  361. }
  362.  
  363. clrscr();
  364. cout<<" Пирамидальная сортировка \n"<<endl;
  365. //сортировка целых чисел
  366. phyramid(mas1,n);
  367.  
  368. cout<<"Отсортированный массив целых чисел:\n"<<endl;
  369. for (i=0;i<n;i++)
  370. cout<<mas1[i]<<" ";
  371. //сортировка чисел с плавающей точкой
  372. phyramid(mas2,n);
  373. cout<<endl<<"\nОтсортированный массив чисел с плавающей точ-кой:\n"<<endl;
  374. for (i=0;i<n;i++)
  375. cout<<mas2[i]<<" ";
  376. BinStr mas3[n]={"1001","1000","1100","1010","1100","1011","0011","1111",
  377. "000000000001","0110","1110","011001","1111","0011","0110",
  378. "1011","0101","0011","0010","1111"};
  379. //сортировка битовых строк
  380. phyramid(mas3,20);
  381. cout<<endl<<endl<<"Отсортированный массив битовых строк:"<<endl;
  382. for (i=0;i<n;i++)
  383. cout<<mas3[i]<<" ";
  384. }
При использовании обязательна ссылка на http://DMTSoft.ru
up