Расчетно-графическое задание 2

Шаблоны функций и классов

Задание

Написать параметризованную подпрограмму сортировки указанным методом. Отладить ее на целых числах и числах с плавающей точкой.

Определить класс объектов массива, предназначенного для сортировки. Перегрузить для него операцию присваивания и операции сравнения <, <=, ==, >=, >.

Написать программу, сортирующую массив объектов построенного класса с помощью написанной параметризованной подпрограммы.

Варианты заданий

Рассмотрим следующие методы сортировки:

   S1. Пирамидальная сортировка.

   S2. Сортировка подсчетом.

   S3. Метод Шелла.

   S4. Быстрая сортировка.

   S5. Метод выбора.

   S6. Метод вставок.

Рассмотрим классы:

   String – строка символов;

   Fraction – рациональная дробь;

   Bits – битовая строка;

   Bcd – строка, состоящая из десятичных цифр, записанных как символы;

   Vector – n-мерный вектор, вектора сортируются в лексикографическом порядке.

Комбинируя методы сортировки и классы, получаем варианты заданий:

Примеры выполнения РГЗ 2

Пример 1

Задание

Написать параметризованную подпрограмму сортировки указанным   методом. Отладить ее на целых числах и числах с плавающей точкой.

Определить класс объектов массива, предназначенного для сортировки. Перегрузить для него операцию присваивания и операции сравнения <, <=, ==, >=, >.

Написать программу, сортирующую массив объектов построенного класса с помощью написанной параметризованной подпрограммы.

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

Программа

#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='';

   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<<"                       Сортировка методом Шелла "<<endl;

   //сортировка целых чисел

   shell(mas1, n);

   cout<<"Отсортированный массив целых чисел: "<<endl;

   for (i=0;i<n;i++)

      cout<<mas1[i]<<" ";

   //сортировка чисел с плавающей точкой

   shell(mas2, n);

   cout<<endl<<" Отсортированный массив чисел с плавающей точкой: "<<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]<<" ";

}

Результаты работы программы

Сортировка методом Шелла

Отсортированный массив целых чисел:

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

Пример 2

Задание

Написать параметризованную подпрограмму сортировки указанным методом. Отладить ее на целых числах и числах с плавающей точкой.   

Определить класс объектов массива, предназначенного для сортировки. Перегрузить для него операцию присваивания и операции сравнения <, <=, ==, >=, >.         

Написать программу, сортирующую массив объектов построенного класса с помощью написанной параметризованной подпрограммы.

Метод сортировки - метод вставок, класс – строка символов.

Программа

#include <iostream.h>

#include <string.h>

#include <conio.h>

#include <stdlib.h>

// Класс - строка символов

class SymStr

   {

   private:

               char *s;                                    // Строка

               int  length;       // Длина строки

   public:

               // Конструкторы

               SymStr()

                           {

                           s=new char[1];

                           *s='';

                           length=0;

                           }

               SymStr(char *str)

                           {

                           length = strlen(str);

                           s = new char[length + 1];

                           strcpy (s, str);

                           }

               SymStr(const SymStr &str)

                           {

                           length = str.length;

                           s = new char[length + 1];

                           strcpy (s, str.s);

                           }

               // Деструктор

               ~SymStr() { delete s; }

               // Перегрузка оператора >

    &