Geum.ru

«Программное обеспечение вычислительной техники и автоматизированных систем»

Вид материалаУчебное пособие

Содержание


Результаты работы программы
Расчетно-графическое задание 3
Подобный материал:
1   2   3   4   5   6   7   8   9


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


Пример 1

Задание

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


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


Программа


#include

#include

#include

#include

#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
if((s[i]-48)==1)

return 1;

//если единиц не оказалось, то побитово сравниваем

//обе строки: оставшуюся часть правой строки со всей левой,

//до нарушения равновесия

for(i=0;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
{

for(i=0;i
if((Object.s[i]-48)==1)

return 0;

for(i=0;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
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
if((s[i]-48)==1)

return 1;

//если единиц не оказалось, то побитово сравниваем

//обе строки: оставшуюся часть правой строки со всей левой,

//до нарушения равновесия

for(i=0;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
{

for(i=0;i
if((Object.s[i]-48)==1)

return 0;

for(i=0;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
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
if((s[i]-48)==1)

return 0;

//если единиц не оказалось, то побитово сравниваем

//обе строки: оставшуюся часть правой строки со всей левой,

//до нарушения равновесия

for(i=0;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
{

for(i=0;i
if((Object.s[i]-48)==1)

return 1;

for(i=0;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
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
if((s[i]-48)==1)

return 0;

//если единиц не оказалось, то побитово сравниваем

//обе строки: оставшуюся часть правой строки со всей левой,

//до нарушения равновесия

for(i=0;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
{

for(i=0;i
if((Object.s[i]-48)==1)

return 1;

for(i=0;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
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
if((s[i]-48)==1)

return 0;

//если единиц не оказалось, то побитово сравниваем

//обе строки: оставшуюся часть правой строки со всей левой,

//до нарушения равновесия

for(i=0;i
if((s[i+(length-Object.length)]-48)!=(Object.s[i]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

//далее следует все аналогично для оставшихся двух случаев,

//когда правая строка длиннее левой и когда длины строк равны

else if(length
{

for(i=0;i
if((Object.s[i]-48)==1)

return 0;

for(i=0;i
if((s[i]-48)!=(Object.s[i+Object.length-length]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

//когда длины строк равны, просто побитово сравниваем обе строки

//до нарушения равновесия

for(i=0;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<
return fo;

}


template

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
{ t=x[i];

for(j=i-gap; t=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
{

mas1[i]=random(n);

mas2[i]=random(n)*0.01;

}


clrscr();

cout<<" Сортировка методом Шелла\n"<
//сортировка целых чисел

shell(mas1, n);

cout<<"Отсортированный массив целых чисел:\n"<
for (i=0;i
cout<
//сортировка чисел с плавающей точкой

shell(mas2, n);

cout<
for (i=0;i
cout<

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<
for (i=0;i
cout<
}

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


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


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


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

#include

#include

#include


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

class SymStr

{

private:

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

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

public:

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

SymStr()

{

s=new char[1];

*s='\0';

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; }


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

int operator> (SymStr &);

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

int operator>=(SymStr &);

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

int operator< (SymStr &);

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

int operator<=(SymStr &);

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

int operator==(SymStr &);

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

SymStr &operator=(SymStr &Object);


// Перегрузка оператора << для вывода строки

friend ostream &operator<<(ostream &, SymStr &);

};


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

int SymStr::operator> (SymStr &Object)

{

if(strcmp(s, Object.s) > 0) return 1;

return 0;

}


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

int SymStr::operator>=(SymStr &Object)

{

if(strcmp(s, Object.s) >= 0) return 1;

return 0;

}

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

int SymStr::operator< (SymStr &Object)

{

if(strcmp(s, Object.s) < 0) return 1;

return 0;

}


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

int SymStr::operator<=(SymStr &Object)

{

if(strcmp(s, Object.s) <= 0) return 1;

return 0;

}


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

int SymStr::operator==(SymStr &Object)

{

if(strcmp(s, Object.s) == 0) return 1;

return 0;

}


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

SymStr& SymStr::operator=(SymStr &Object)

{

length = strlen(Object.s);

s = new char[length + 1];

strcpy(s, Object.s);

return *this;

}


// Перегрузка оператора << для вывода строки

ostream &operator<<(ostream &fo, SymStr &fp)

{

fo << fp.s;

return fo;

}


// Cортировка вставками

template

void insert (Type *x, int n)

{

int i, j;

Type t;

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

{

t = x[i];

for (j = i - 1; j >= 0 && t < x[j]; j--)

x[j + 1] = x[j]; // Сдвиг на одну позицию

x[j + 1] = t;

}

}


void main()

{

int i;

int mas1[30]; // Определяем целочисленный массив

float mas2[30]; // Определяем массив чисел с плавающей точкой

randomize(); // Инициализация генератора случайных чисел


// Заполняем массивы случайными числами

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

{

mas1[i] = random(30);

mas2[i] = random(30) * 0.01;

}


clrscr(); // Очищаем экран

cout << "\t\t\tСортировка методом вставок\n\n";

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

insert(mas1, 30);

cout << "Результат сортировки целых чисел:\n";

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

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

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

insert(mas2, 30);

cout << "\n\nРезультат сортировки чисел с плавающей точкой:\n";

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

cout << mas2[i] << " ";


SymStr mas3[5] = {"diman", "max", "vasyan", "sanya", "leha"};

// Cортировка символьных строк

insert(mas3, 5);

cout << "\n\nРезультат сортировки битовых строк:\n";

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

cout << mas3[i] << " ";

getch();

}


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


Сортировка методом вставок


Результат сортировки целых чисел:

0 0 1 2 3 4 6 7 8 8 8 9 10 11 12 12 13 13 14 15 16 19 20 21 22 26 27 28 28 29


Результат сортировки чисел с плавающей точкой:

0 0.01 0.03 0.03 0.05 0.06 0.06 0.07 0.08 0.09 0.09 0.1 0.12 0.13 0.14 0.14 0.15 0.15 0.16 0.16 0.18 0.19 0.19 0.2 0.2 0.22 0.26 0.27 0.27 0.29


Результат сортировки битовых строк:

diman leha max sanya vasyan


^ РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 3


Производные классы


Задание. Используя производные классы, определить класс параметризованного списка одного из следующих типов. Применить его для построения списка объектов указанного типа данных.


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

S1. Упорядоченный список.

S2. Циклический односвязный список.

S3. Циклический двухсвязный список.

S4. Дек.

S5. Очередь.

S6. Дерево поиска.


Определим следующие типы данных:

T1. Число по модулю n.

T2. Текстовая строка.

T3. Рациональное число.

T4. Битовая строка.

T5. Комплексное число.


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

S2
S3
S4
S5
S6

T1
1
6
11
16
21
26

T2
2
7
12
17
22
27

T3
3
8
13
18
23
28

T4
4
9
14
19
24
29

T5
5
10
15
20
25
30