#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#define n 100
//класс: Битовая строка
class BinStr
{
private:
char *s; //сама строка
int length; //указатель на длину
public:
BinStr();
BinStr(char *);
BinStr(const BinStr &);
~BinStr();
int operator> (BinStr &);
int operator>=(BinStr &);
int operator< (BinStr &);
int operator<=(BinStr &);
int operator==(BinStr &);
BinStr &operator=(BinStr &Object);//перегрузка оператора присваивания
friend ostream &operator<<(ostream &, BinStr &);
};
BinStr::BinStr()
{
s=new char[1];
*s='\0';
length=0;
}
BinStr::BinStr(char *st)
{
length=strlen(st);
s=new char[(length)+1];
strcpy (s,st);
}
BinStr::BinStr(const BinStr &s1)
{
length=strlen(s1.s);
s=new char[(length)+1];
strcpy (s,s1.s);
}
BinStr::~BinStr()
{
delete s;
}
int BinStr::operator> (BinStr &Object)
{
int i;
//если длина левой строки больше правой
if(length>Object.length)
{
//проверяем, есть ли в старших битах левой
//строки, которых нет в правой, единицы
//если есть, то возвращаем 1
for(i=0;i<length-Object.length;i++)
if((s[i]-48)==1)
return 1;
//если единиц не оказалось, то побитово сравниваем
//обе строки: оставшуюся часть правой строки со всей левой,
//до нарушения равновесия
for(i=0;i<Object.length;i++)
if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
return 0;
else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
return 1;
//если строки равны, возвращаем 0
return 0;
}
//далее следует все аналогично для оставшихся двух случаев,
//когда правая строка длиннее левой и когда длины строк равны
else if(length<Object.length)
{
for(i=0;i<Object.length-length;i++)
if((Object.s[i]-48)==1)
return 0;
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i+Object.length-length]-48))
return 0;
else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
return 1;
//если строки равны, возвращаем 0
return 0;
}
//когда длины строк равны, просто побитово сравниваем обе строки
//до нарушения равновесия
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i]-48))
return 0;
else if((s[i]-48)>(Object.s[i]-48))
return 1;
//если строки равны, возвращаем 0
return 0;
}
int BinStr::operator>=(BinStr &Object)
{
int i;
//если длина левой строки больше правой
if(length>Object.length)
{
//проверяем, есть ли в старших битах левой
//строки, которых нет в правой, единицы
//если есть, то возвращаем 1
for(i=0;i<length-Object.length;i++)
if((s[i]-48)==1)
return 1;
//если единиц не оказалось, то побитово сравниваем
//обе строки: оставшуюся часть правой строки со всей левой,
//до нарушения равновесия
for(i=0;i<Object.length;i++)
if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
return 0;
else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
return 1;
//если строки равны, возвращаем 1
return 1;
}
//далее следует все аналогично для оставшихся двух случаев,
//когда правая строка длиннее левой и когда длины строк равны
else if(length<Object.length)
{
for(i=0;i<Object.length-length;i++)
if((Object.s[i]-48)==1)
return 0;
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i+Object.length-length]-48))
return 0;
else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
return 1;
//если строки равны, возвращаем 1
return 1;
}
//когда длины строк равны, просто побитово сравниваем обе строки
//до нарушения равновесия
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i]-48))
return 0;
else if((s[i]-48)>(Object.s[i]-48))
return 1;
//если строки равны, возвращаем 1
return 1;
}
int BinStr::operator< (BinStr &Object)
{
int i;
//если длина левой строки больше правой
if(length>Object.length)
{
//проверяем, есть ли в старших битах левой
//строки, которых нет в правой, единицы
//если есть, то возвращаем 0
for(i=0;i<length-Object.length;i++)
if((s[i]-48)==1)
return 0;
//если единиц не оказалось, то побитово сравниваем
//обе строки: оставшуюся часть правой строки со всей левой,
//до нарушения равновесия
for(i=0;i<Object.length;i++)
if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
return 1;
else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
return 0;
//если строки равны, возвращаем 0
return 0;
}
//далее следует все аналогично для оставшихся двух случаев,
//когда правая строка длиннее левой и когда длины строк равны
else if(length<Object.length)
{
for(i=0;i<Object.length-length;i++)
if((Object.s[i]-48)==1)
return 1;
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i+Object.length-length]-48))
return 1;
else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
return 0;
//если строки равны, возвращаем 0
return 0;
}
//когда длины строк равны, просто побитово сравниваем обе строки
//до нарушения равновесия
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i]-48))
return 1;
else if((s[i]-48)>(Object.s[i]-48))
return 0;
//если строки равны, возвращаем 0
return 0;
}
int BinStr::operator<=(BinStr &Object)
{
int i;
//если длина левой строки больше правой
if(length>Object.length)
{
//проверяем, есть ли в старших битах левой
//строки, которых нет в правой, единицы
//если есть, то возвращаем 0
for(i=0;i<length-Object.length;i++)
if((s[i]-48)==1)
return 0;
//если единиц не оказалось, то побитово сравниваем
//обе строки: оставшуюся часть правой строки со всей левой,
//до нарушения равновесия
for(i=0;i<Object.length;i++)
if((s[i+(length-Object.length)]-48)<(Object.s[i]-48))
return 1;
else if((s[i+(length-Object.length)]-48)>(Object.s[i]-48))
return 0;
//если строки равны, возвращаем 1
return 1;
}
//далее следует все аналогично для оставшихся двух случаев,
//когда правая строка длиннее левой и когда длины строк равны
else if(length<Object.length)
{
for(i=0;i<Object.length-length;i++)
if((Object.s[i]-48)==1)
return 1;
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i+Object.length-length]-48))
return 1;
else if((s[i]-48)>(Object.s[i+Object.length-length]-48))
return 0;
//если строки равны, возвращаем 1
return 1;
}
//когда длины строк равны, просто побитово сравниваем обе строки
//до нарушения равновесия
for(i=0;i<length;i++)
if((s[i]-48)<(Object.s[i]-48))
return 1;
else if((s[i]-48)>(Object.s[i]-48))
return 0;
//если строки равны, возвращаем 1
return 1;
}
int BinStr::operator==(BinStr &Object)
{
int i;
//если длина левой строки больше правой
if(length>Object.length)
{
//проверяем, есть ли в старших битах левой
//строки, которых нет в правой, единицы
//если есть, то возвращаем 0
for(i=0;i<length-Object.length;i++)
if((s[i]-48)==1)
return 0;
//если единиц не оказалось, то побитово сравниваем
//обе строки: оставшуюся часть правой строки со всей левой,
//до нарушения равновесия
for(i=0;i<Object.length;i++)
if((s[i+(length-Object.length)]-48)!=(Object.s[i]-48))
return 0;
//если строки равны, возвращаем 1
return 1;
}
//далее следует все аналогично для оставшихся двух случаев,
//когда правая строка длиннее левой и когда длины строк равны
else if(length<Object.length)
{
for(i=0;i<Object.length-length;i++)
if((Object.s[i]-48)==1)
return 0;
for(i=0;i<length;i++)
if((s[i]-48)!=(Object.s[i+Object.length-length]-48))
return 0;
//если строки равны, возвращаем 1
return 1;
}
//когда длины строк равны, просто побитово сравниваем обе строки
//до нарушения равновесия
for(i=0;i<length;i++)
if((s[i]-48)!=(Object.s[i]-48))
return 0;
//если строки равны, возвращаем 1
return 1;
}
BinStr& BinStr::operator=(BinStr &Object)
{
length=strlen(Object.s);
s=new char[(length)+1];
strcpy (s,Object.s);
return *this;
}
ostream &operator<<(ostream &fo, BinStr &fp)
{
fo<<fp.s;
return fo;
}
template <class Type>
void shell(Type *x, int n1)
{ int i,j,k,gap;
Type t;
int a[5]={9,5,3,2,1};
for(k=0; k<5; k++)
{ gap=a[k];
for(i=gap; i<n1; i++)
{ t=x[i];
for(j=i-gap; t<x[j]&&j>=0; j=j-gap)
x[j+gap]=x[j];
x[j+gap]=t;
}
}
}
void main()
{
int i;
int mas1[n];
float mas2[n];
randomize();
for (i=0;i<n;i++)
{
mas1[i]=random(n);
mas2[i]=random(n)*0.01;
}
clrscr();
cout<<" Сортировка методом Шелла\n"<<endl;
//сортировка целых чисел
shell(mas1, n);
cout<<"Отсортированный массив целых чисел:\n"<<endl;
for (i=0;i<n;i++)
cout<<mas1[i]<<" ";
//сортировка чисел с плавающей точкой
shell(mas2, n);
cout<<endl<<"\nОтсортированный массив чисел с плавающей точкой:\n"<<endl;
for (i=0;i<n;i++)
cout<<mas2[i]<<" ";
BinStr mas3[n]={"1001","1000","1100","1010","1100","1011","0011","1111",
"000000000001","0110","1110","011001","1111","0011","0110",
"1011","0101","0011","0010","1111"};
//сортировка битовых строк
shell(mas3, n);
cout<<endl<<endl<<"Отсортированный массив битовых строк:"<<endl;
for (i=0;i<n;i++)
cout<<mas3[i]<<" ";
}
Выход