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


Добавил:DMT
Дата создания:30 апреля 2008, 21:32
Дата обновления:30 апреля 2008, 21:32
Просмотров:10849 последний сегодня, 15:18
Комментариев: 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.    
  369.    cout<<"Отсортированный массив целых чисел:\n"<<endl;
  370.    for (i=0;i<n;i++)
  371.       cout<<mas1[i]<<" ";
  372.    //сортировка чисел с плавающей точкой
  373.      phyramid(mas2,n);
  374.    cout<<endl<<"\nОтсортированный массив чисел с плавающей точ-кой:\n"<<endl;
  375.    for (i=0;i<n;i++)
  376.       cout<<mas2[i]<<" ";
  377.   
  378. BinStr mas3[n]={"1001","1000","1100","1010","1100","1011","0011","1111",
  379. 		"000000000001","0110","1110","011001","1111","0011","0110",
  380. 		"1011","0101","0011","0010","1111"};
  381. 	//сортировка битовых строк
  382. 	phyramid(mas3,20);
  383.    cout<<endl<<endl<<"Отсортированный массив битовых строк:"<<endl;
  384.    for (i=0;i<n;i++)
  385.       cout<<mas3[i]<<" ";
  386. }
При использовании обязательна ссылка на http://DMTSoft.ru
up