Застосування алгоритмів до вектора

Для сортування можна застосувати стандартний алгоритм sort. Для його використання необхідно підключити файл заголовків алгоритмів.

# Include "algorithm"

Після чого можна сортувати, як весь вектор, так і окремі його частини:

vector <int> v1 (10);

vector <int> v2 (10);

for (int x = 0; x <v1.capacity (); x + +) v1 [x] = 10-x;

for (x = 0; x <v1.capacity (); x + +) v2 [x] = 10-x;

for (x = 0; x <v1.size (); x + +) cout << v1 [x] << "";

cout << endl;

for (x = 0; x <v2.size (); x + +) cout << v2 [x] << "";

cout << endl;

cout << "___________ SORT _____________" << endl;

sort (v1.begin (), v1.end ());

for (x = 0; x <v1.size (); x + +) cout << v1 [x] << "";

cout << endl;

sort (v2.begin () +1, v2.end () -1);

for (x = 0; x <v2.size (); x + +) cout << v2 [x] << "";

cout << endl;

Приклад 1 виконання Завдання 1

( з використанням ітератора )

Для даних типу char з використанням ітератора виконати таку послідовність дій:

1. Описання об'єкту класу

2. Ініціалізацію VECTORу

3. Виведення VECTORу

4. Сортування VECTORу

5. Виведення VECTORу

6. Визначення на кожному кроці поточного розміру VECTORу

7. Доповнення з заданої позиції у VECTOR

8. Видалення з заданої позиції у VECTOR

9. Сортування VECTORу

10. Виведення VECTORу

vector <char> ch; //об"являємо вектор символьного типу

cout << "\nEnter number of element =";

cin >> N;

// заповнюємо вектор символами з порядковими номерами після 60

for(I=0;I<N;I++)

{

 

ch.push_back(rand()%10+60);

}

cout << "\n\nNew vector\n";

for (I = 0; I<ch.size(); I++)

cout << ch[I] << " ";

cout << "\nCurrent size = "<<ch.size();

// сортуємо вектор

sort(ch.begin(),ch.end());

cout << "\nSorted vactor\n";

for (I = 0; I<ch.size(); I++)

cout << ch[I] << " ";

 

int pos_ins;

char new_elem;

cout << "\nEnter position when insert =";

cin >> pos_ins;

cout << "\nEnter new element value =";

cin >> new_elem;

 

vector <char>::iterator ch_p=ch.begin();

ch_p = ch_p+pos_ins;

// якщо вказано правильне місце вставки, вставляємо масив

if (pos_ins>=0 && pos_ins<=ch.size())

{

ch.insert(ch_p,1,new_elem);

}

 

for (I = 0; I<ch.size(); I++)

cout << ch[I] << " ";

 

cout << "\nEnter position when erase =";

cin >> pos_ins;

 

cout << "\nCurrent size = "<<ch.size();

cout << "\nErase element\n";

// якщо вказано правильне місце вставки, вставляємо масив

if (pos_ins>=0 && pos_ins<=ch.size())

{

ch.erase(ch.begin()+pos_ins,ch.begin()+pos_ins+1);

}

for (I = 0; I<ch.size(); I++)

cout << ch[I] << " ";

 

cout << "\nCurrent size = "<<ch.size();

 

return 0;

}

Приклад 2 виконання Завдання 2

В одномірному масиві, що складається з n елементів, обчислити: суму негативних елементів масиву; добуток елементів масиву, розташованих між максимальним і мінімальним елементами. Упорядкувати елементи масиву по зростанню.

Лістинг програми:

#include "stdafx.h"

#include <iostream.h>

#include <vector>

#include <stdlib.h>

#include <stdio.h>

#include <algorithm>

 

using namespace std;

 

int main(int argc, char* argv[])

{

vector <int> v; //об"являємо вектор цілого типу

int I=0, N=0;

cout << "\nEnter number of element =";

cin >> N;

// заповнюємо вектор довільними числами

for(I=0;I<N;I++)

{

v.push_back(rand()%10-5);

}

// виводими вектор на екран

cout << "\n\nNew vector\n";

for (I = 0; I<v.size(); I++)

cout << v[I] << " ";

// знаходимо суму елементів вектора менше нуля

int sum=0;

for (I = 0; I<v.size(); I++)

if (v[I]<0)

sum +=v[I];

cout << "\nsum elementiv below 0 is "<<sum;

// знаходимо добуток елементів масиву,

// розташованих між максимальним і мінімальним елементами.

// об"являємо вказівник на максимальний елемент

vector<int>::iterator max_it = max_element(v.begin(), v.end());

// об"являємо вказівник на мінімальний елемент

vector<int>::iterator min_it = min_element(v.begin(), v.end());

vector<int>:: iterator p;

long dob=1;

// визначаємо чи максимальний чи мінімальний елемент знаходиться в векторі першим

if (max_it>min_it)

{

for(p=min_it;p<=max_it;p++)

{

dob *=*p;

}

}

else

{

for(p=max_it;p<=min_it;p++)

{

dob *=*p;

}

}

cout << "\nDobutoc of negative elements is "<< dob<<"\n";

// сортуємо вектор

sort(v.begin(),v.end());

// виводимо вектор на екан

cout << "Sorted vector \n";

for (I = 0; I<v.size(); I++)

cout << v[I] << " ";

Приклад 3 виконання завдання №3

Варіант 2. Задача “Студент” (прізвище, вік).

Лістинг програми

#include "stdafx.h"

#include <iostream.h>

#include <vector>

#include <stdlib.h>

#include <stdio.h>

#include <algorithm>

using namespace std;

struct structura{ //ініціалізація структури згідно варіанту

char name[20];

int age;

}str,str1;

template <class T>

class S //клас для роботи з структурою

{

private:

vector<T>st; //динаміний масив для роботи з структурою

public:

S(int n); //конструктор

print(void); //функція для виводу масиву

insert(void); //функція для вставки структури в масив

sort(void); //функція для сортування масиву структур

float sum(void); //функція для знаходження суми по полю структури age

erase(int n); //функція для видалення структури з масиву

};

template <class T> //шаблон класу

S<T>::S(int n) //описання конструктора

{

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

{

cout << "Enter name["<<i<<"]=";

cin >>str.name;

cout << "Enter age["<<i<<"] =";

cin >>str.age;

st.push_back(str);

}

};

template <class T>

S<T>::print() //описання функції для виводу масиву

{

for(int i=0; i<st.size(); i++)

{

cout <<"\nname["<<i<<"]="<<st[i].name;

cout <<"\nage["<<i<<"] ="<<st[i].age;

}

};

template <class T>

S<T>::insert() //описання функції для вставки структури в масив

{

cout<<"\n\nInsert\n";

cout << "Enter name=";

cin >>str.name;

cout << "Enter age=";

cin >>str.age;

st.push_back(str);

};

template <class T>

S<T>::sort() //описання функції для сортування масиву структур

{

for(int i=0;i<st.size()-1;i++)

for(int j=i+1;j<st.size();j++)

{

if(st[i].age<st[j].age)

{

str1=st[i];

st[i]=st[j];

st[j]=str1;

}

}

}

template <class T>

S<T>::erase(int n)//описання функції для видалення структури з масиву

{

if (n>=0 && n<=st.size())

{

st.erase(st.begin()+n,st.begin()+n+1);

}

else cout << "\nIncorrect position\n";

};

template <class T>

float S<T>::sum() // описання функції для знаходження суми по полю структури age

{

float s=0;

for(int i=0; i<st.size(); i++)

s=s+st[i].age;

return s;

};

int main(int argc, char* argv[]) //головна програма

{

int N=0,k;

cout << "\nEnter number of element =";

cin >> N;

S<structura> x(N); //ініціалізація динамічного масиву

x.print(); //виклик функції print()

x.insert(); //виклик функції insert()

x.print(); //виклик функції print()

cout<<"\nSortuvanie\n";

x.sort(); //виклик функції sort()

x.print(); //виклик функції print()

cout<<"\nsum="<<x.sum();

cout<<"\n\nEnter position when erase\n";

cin>>k;

x.erase(k); //виклик функції erase(k)

x.print(); //виклик функції print()

return 0;

}

Тестування:

Enter number of element =5

Enter name[0]=Popov

Enter age[0] =45

Enter name[1]=Sidorov

Enter age[1] =32

Enter name[2]=Bobrov

Enter age[2] =22

Enter name[3]=Novikov

Enter age[3] =51

Enter name[4]=Filatov

Enter age[4] =33

Insert

Enter name=Kotov

Enter age=24

name[0]=Popov

age[0] =45

name[1]=Sidorov

age[1] =32

name[2]=Bobrov

age[2] =22

name[3]=Novikov

age[3] =51

name[4]=Filatov

age[4] =33

name[5]=Kotov

age[5] =24

Sortuvanie

name[0]=Novikov

age[0] =51

name[1]=Popov

age[1] =45

name[2]=Filatov

age[2] =33

name[3]=Sidorov

age[3] =32

name[4]=Kotov

age[4] =24

name[5]=Bobrov

age[5] =22

sum=207

Enter position when erase

name[0]=Novikov

age[0] =51

name[1]=Popov

age[1] =45

name[2]=Filatov

age[2] =33

name[3]=Sidorov

age[3] =32

name[4]=Bobrov

age[4] =22

 

Контрольні запитання

Для чого було створено STL?

Що таке контейнери, алгоритми, ітератори?

Види контейнерів.

Як працюють алгоритми?

Види ітераторів.

Що таке VECTOR?

Назвіть відомі вам функції-члени класу VECTOR.

Основні операції, які можна виконувати з VECTOR.

Що таке LIST?

Назвіть відомі вам функції-члени класу LIST.

Наведіть приклад простого списку.

Лабораторна робота №12

Тема: Особливості створення програм обробки динамічних даних (списків) з використанням контейнерів LIST, MAP, STRING стандартної бібліотеки шаблонів STL.

Мета: Набуття навичок в розробці програм з використанням контейнерів LIST, MAP, STRING стандартної бібліотеки шаблонів STL.

Порядок виконання роботи

1. Ознайомитись з теоретичною частиною даної теми.

2. Розробити структуру класу, який призначений для обробки складних динамічних даних та методів контейнера LIST стандартної бібліотеки шаблонів STL для обробки даних, що задані в Завданні відповідного варіанту.

3. Розробити структуру класу, який призначений для обробки складних динамічних даних та методів контейнера MAP стандартної бібліотеки шаблонів STL для обробки даних, що задані в Завданні відповідного варіанту.

4. Розробити структуру класу, який призначений для обробки складних динамічних даних та методів контейнера STRING стандартної бібліотеки шаблонів STL для обробки даних, що задані в Завданні відповідного варіанту.

5. Розробити функції класу, структура якого розроблена в п.2-4 для виконання Завдання.

6. Розробити програму, яка використовує розроблену в п.2-5 шаблонів класів для виконання Завдання.

7. Розробити 2-3 теста для перевірки правильності роботи даної програми.

8. Оформити звіт до лабораторної роботи.

Завдання 1

Структура розробленого класу повинна містити: 2-3 конструктори, функції заповнення, виведення, доповнення, видалення, вставки, сортування, часткового сортування (по заданному діапазону і критерію), пошуку по заданному критерію.

Варіант 1. Задача “Банківське переведення” (дата, час, № рахунку, розмір рахунку).

Варіант 2. Задача “Студент” (прізвище, вік).

Варіант 3. Задача “Медична картка” (прізвище, вага).

Варіант 4. Задача “Результати хімічного досліду” (float, float).

Варіант 5. Задача “Результати хімічного досліду” (час, кількість

речовини).

Варіант 6. Задача “Розклад” (№ рейсу та час відправлення).

Варіант 7. Задача. “Успішність” (предмет, оцінка).

Варіант 8. Задача “Мобільний телефон” (час розмови, кількість грошей, № телефону).

Варіант 9. Задача “Мешканці” (прізвище, № квартири).

Варіант 10. Задача “Кабельне телебачення” (кількість каналів, вартість, назва пакету).

Клас повинен містити методи обробки списку:

- вставка;

- сортування по полю;

- сумування;

- видалення.

Теоретичні відомості

Приклад розробки програми

// Templates.cpp: Defines the entry point for the console application.

//

#include "stdafx.h"

#include "stdio.h"

#include <stdlib.h>

 

 

template <class T>

class List

{

private:

T *v;

int size;

public:

List(int);

T& operator[](int i) {return v[i];}

T& operator=(T * arr) {return arr;}

print_array(void);

sort_array(void);

};

 

 

template <class T>

List<T>::List(int n)

{

v = new T[n];

size = n;

}

 

template <class T>

List<T>::print_array()

{

int i;

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

{

printf (" %d |", v[i]);

}

}

 

template <class T>

List<T>::sort_array()

{

int i, n=1;

T temp;

 

while (n<size)

{

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

{

if (v[i]>v[i+1])

{

temp = v[i];

v[i]=v[i+1];

v[i+1]=temp;

}

}

n++;

}

}

 

 

void main()

{

const num = 10;

int i;

 

List<int> integer(num);

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

{

integer[i]=(int)(rand()/1000)+60;

}

 

List<int> character(num);

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

{

character[i]=(char)(rand()/1000)+60;

}

 

printf("\nInteger before sorting:\n");

integer.print_array();

printf("\nChar before sorting:\n");

character.print_array();

// sorting

integer.sort_array();

character.sort_array();

printf("\nInteger after sorting:\n");

integer.print_array();

printf("\nChar after sorting:\n");

character.print_array();

printf("\ndone\n");

Контрольні запитання

1. Що таке шаблон?

2. У яких файлах знаходяться шаблони?

3. Типи шаблонів, які використовуються у С++.

4. Основне призначення шаблонів.

5. Правила створення шаблону в С++.

6. Які функції та класи називаються родовими?

7. Основні принципи організації шаблону функції.

8. Основні принципи організації шаблону класу.

9. У файлах з яким розширенням необхідно зберігати шаблони і чому?

10. Наведіть форми об’явлення родових функцій та класів.

11. Наведіть приклад родового класу.

Лабораторна робота №13

Тема: Особливості розробки програм з використанням бібліотеки потокового введення/виведення.

Мета: Набуття навичок в розробці програм з використанням потоків даних.

Порядок виконання

1. Ознайомитись з теоретичною частиною даної теми.

2. Розробити клас або ієрархію класів обробки динамічних масивів даних з використанням стандартних потоків (cin, cout) для базових типів відповідно Завданню 1.

3. Розробити метод класу з використанням стандартних потоків (cin, cout) для базових типів відповідно Завданню 1 з використанням:

а) прапорців (skip ws, left, right, fixed, showpos, scientific);

б) компонентних змінних класу ios (int x - width, int x - precision);

в) маніпуляторів (endl, flush, ws, ends)

для організації форматування даних при обміні з потоками.

4. Розробити метод класу з використанням стандартних класів istrstream, ostrstream, strstream для створення, роботи та виводу зі строкових потоків відповідно Завдання 2.

При розробці програми використовувати режими використання прапорців: ios:: out; ios:: atc; ios:: app.

5. Розробити тест для перевірки вірності даної програми.

6. Оформити звіт до лабораторної роботи.

Завдання 1.

Варіант1. Розробити програму для виводу на екран усіх позитивних елементів одновимірного динамічного масиву і їх суми і кількості.

Варіант 2. Розробити програму для виводу на екран усіх негативних елементів одновимірного динамічного масиву і їх суми і кількості.

Варіант 3. Розробити програму для виводу на екран кількості нульових елементів одновимірного динамічного масиву і їх порядкових номерів.

Варіант 4. Розробити програму для виводу на екран суми першої і другої половини одновимірного динамічного масиву і кількості позитивних елементів у кожній.

Варіант 5. Розробити програму для виводу на екран середнього і дисперсії даного одновимірного динамічного масиву.

Варіант 6. Розробити програму для виводу на екран вихідного одновимірного динамічного масиву й упорядкованого по зростанню методом пухирця.

Варіант 7. Розробити програму для виводу на екран вихідного одномірного динамічного масиву й упорядкованого по убуванню методом пухирця.

Варіант 8. Розробити програму для виводу на екран мінімального і максимального елементів одновимірного динамічного масиву і їх порядкових номерів.

Варіант 9. Розробити програму для виводу на екран вихідного одновимірного динамічного масиву і перетвореного таким чином, що максимальний елемент став першим елементом, а мінімальний – останнім.

Варіант 10. Розробити програму для виводу на екран вихідного одновимірного динамічного масиву і перетвореного таким чином, що максимальний елемент став останнім, а максимальний – першим.

Завдання 2.

Варіант 1. Розробити програму для виводу на екран усіх позитивних елементів кожного рядка двовимірного динамічного масиву і їх порядкових номерів.

Варіант 2. Розробити програму для виводу на екран усіх негативних елементів кожного рядка двовимірного динамічного масиву і їх порядкових номерів.

Варіант 3. Розробити програму для виводу на екран усіх позитивних елементів кожного стовпця даного двовимірного динамічного масиву і їх порядкових номерів.

Варіант 4. Розробити програму для виводу на екран усіх негативних елементів кожного стовпця даного двовимірного динамічного масиву і порядкових номерів.

Варіант 5. Розробити програму для виводу на екран суми і кількості всіх позитивних елементів кожного рядка даного двовимірного динамічного масиву.

Варіант 6. Розробити програму для виводу на екран суми усіх негативних елементів кожного рядка даного двовимірного динамічного масиву і їх кількості в кожнім рядку.

Варіант 7. Розробити програму для виводу на екран середнього арифметичного всіх позитивних елементів кожного стовпця даного двовимірного динамічного масиву.

Варіант 8. Розробити програму для виводу на екран середнього арифметичного всіх негативних елементів кожного стовпця даного двовимірного динамічного масиву.

Варіант 9. Розробити програму для виводу на екран суми усіх позитивних елементів верхньої і нижньої трикутних матриць даного двовимірного динамічного масиву і їхньої кількості в кожній.

Варіант 10. Розробити програму для виводу на екран суми усіх негативних елементів верхньої і нижньої трикутних матриць даного двовимірного динамічного масиву і їх кількості в кожній.

Теоретичні відомості

Потік визначається як послідовність байтів (символів) і з погляду програми не залежить від конкретних пристроїв (файл на диску, принтер), з якими ведеться обмін даних. При обміні даними з потоком часто використається буфер обміну, у якому розташовуються виведені програмою дані перед тим, як вони будуть передані зовнішньому пристрою, При введенні даний вони спочатку поміщаються в буфер, і тільки потім передаються в область пам'яті основної програми. Використання буфера підвищує швидкість передачі даних і т.д.

Відповідно до особливостей «пристрою», до якого приєднаний потік, потоки прийнято ділити на стандартні, консольні, строкові й файлові. Консольні потоки мають зручні засоби для роботи із клавіатурою і з екраном. Консольні потоки не сумісні з Windows програмуванням, тому про них буде вестися мова менше.

Якщо символи потоку в сукупності утворять символьний масив (рядок) в основній пам'яті, то це строковий потік. Якщо при використанні потоку його символи розміщаються на зовнішньому носії (дискеті...), то говорять про файловий потік.