Файл: Лабораторная работа 01 Среды разработки программ на языке С Драчева Кристина Проверил Савин Н. И. Тула 2023.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.02.2024
Просмотров: 57
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев
2. Техническое задание
1.Создайте процедуру обхода дерева «в глубину».
2.Создайте процедуру обхода дерева «в ширину».
3.Создайте процедуру поиска значения.
4.Создайте процедуру построения бинарного дерева на основе не бинарного.
5.Создайте процедруру обхода дерева с использованием пустых указателей в исходном дереве для организации перехода от «потомков» к «предкам».
6.Создайте процедуру обхода дерева с использованием изменения внутренней структуры дерева для определения пути обхода?
3.Постановка задачи
Решить заданные задачи и ответить на контрольные вопросы.
Способ решения. Для решения поставленной задачи будет использован объектно-ориентированный язык программирования С++.
4. Ход работы
Задание №1
Листинг программы:
usingnamespace std;
structnode {
int key;
node* left, * right;
};
node* newNode(intkey) {
node* elem = newnode;
elem->key = key;
elem->left = elem->right = NULL;
return elem;
};
void printAsLevelOrder(node* elem) {
queue
q.push(elem);
while (!q.empty()) {
node* elem = q.front();
cout << elem->key <<" ";
q.pop();
if (elem->left != NULL) {
q.push(elem->left);
}
if (elem->right != NULL) {
q.push(elem->right);
}
}
}
int main() {
node* root = newNode(10);
root->left = newNode(11);
root->left->left = newNode(7);
root->right = newNode(9);
root->right->left = newNode(15);
root->right->right = newNode(8);
cout <<"Вывод :\n";
printAsLevelOrder(root);
return 0;
}
Задание№2
Листингпрограммы:
typedefstructnode {
constvoid* ptr;
structnode* next;
} node_t;
typedefstruct {
node_t* head;
node_t* tail;
} queue_t;
void queue_init(queue_t* q);
int queue_push(queue_t* q, constvoid* ptr);
void queue_pop(queue_t* q);
constvoid* queue_front(queue_t* q);
int queue_empty(queue_t* q);
typedefstructtree {
int key;
structtree* left;
structtree* right;
} tree_t;
tree_t* tree_insert(tree_t** tr, intkey);
void tree_clear(tree_t* tr);
void tree_out_width(FILE* _out, consttree_t* tr) {
consttree_t* p;
queue_t q;
queue_init(&q);
queue_push(&q, tr);
while (!queue_empty(&q)) {
p = (consttree_t*)queue_front(&q);
queue_pop(&q);
fprintf(_out, "%d ", p->key);
if (p->left != NULL)
queue_push(&q, p->left);
if (p->right != NULL)
queue_push(&q, p->right);
}
}
int main(void) {
int i;
tree_t* tr = NULL;
for (i = 0; i < 20; ++i)
tree_insert(&tr, rand() % 10);
tree_out_width(stdout, tr);
tree_clear(tr);
return 0;
}
tree_t* tree_insert(tree_t** tr, intkey) {
tree_t* p = *tr;
while (p != NULL) {
if (key == p->key)
return p;
elseif (key< p->key) {
tr = &p->left;
p = p->left;
}
else {
tr = &p->right;
p = p->right;
}
}
p = (tree_t*)malloc(sizeof(tree_t));
if (p != NULL) {
p->key = key;
p->left = p->right = NULL;
*tr = p;
}
return p;
}
void tree_clear(tree_t* tr) {
if (tr != NULL) {
if (tr->left != NULL)
tree_clear(tr->left);
if (tr->right != NULL)
tree_clear(tr->right);
free(tr);
}
}
void queue_init(queue_t* q) { q->head = q->tail = NULL; }
int queue_empty(queue_t* q) { return (q->head == NULL); }
constvoid* queue_front(queue_t* q) { returnq->head->ptr; }
int queue_push(queue_t* q, constvoid* ptr) {
node_t* p = (node_t*)malloc(sizeof(node_t));
if (p != NULL) {
p->ptr = ptr;
p->next = NULL;
if (q->head == NULL)
q->head = q->tail = p;
else {
q->tail->next = p;
q->tail = p;
}
}
return (p != NULL);
}
void queue_pop(queue_t* q) {
node_t* t;
if (q->head != NULL) {
t = q->head;
q->head = q->head->next;
free(t);
if (q->head == NULL)
q->tail = NULL;
}
}
Задание№3
Листинг программы:
structnode {
int key;
node* parent;
node* left;
node* right;
}
void deep_walk(node* root) {
stack = create_stack();
stack_push(stack, root);
while ((node * n = stack_pop(stack)) != NULL) {
do {
printf("%c", n->key);
if (n->left != NULL) {
if (n->right != NULL)
stack_push(stack, n->right);
n = n->left;
}
else
N = n->right;
} while (n != NULL)
}
}
Задание№4
Листингпрограммы:
constint COUNT = 10;
structtree {
int info;
tree** childs;
int count;
};
void error(intn) {
setlocale(LC_ALL, "Russian");
switch (n) {
case 0: printf("\nНормально"); break;
case 1: printf("\nНетпамяти!"); break;
case 2: printf("\nСлишком много дочерних предметов!"); break;
default: printf("\nНеизвестная ошибка!"); break;
}
fflush(stdin); getchar(); exit(n);
}
tree* init(tree* p, intinfo) {
p->info = info; p->childs = nullptr; p->count = 0; returnp;
}
void print1(tree* p) {
setlocale(LC_ALL, "Russian");
printf("Элемент %d (%d childs)\n", p->info, p->count);
}
void print(tree* p, inttab = 0) {
print1(p);
for (int i = 0; i
for (int k = 0; k <= tab; k++) printf("\t");
print(p->childs[i], ++tab);
--tab;
}
}
tree* search(tree* t, intinfo) {
if (t->info == info) returnt;
elseif (t->count > 0) {
for (int i = 0; i
tree* p = search(t->childs[i], info);
if (p != nullptr) return p;
}
returnnullptr;
}
elsereturnnullptr;
}
tree* search_parent(tree* t, tree* p) {
if (t->count > 0) {
for (int i = 0; i
if (t->childs[i]->info == p->info) returnt;
else {
tree* s = search_parent(t->childs[i], p);
if (s != nullptr) return s;
}
}
returnnullptr;
}
elsereturnnullptr;
}
tree* add(tree* ptr, intparentinfo, intinfo) {
tree* p = search(ptr, parentinfo);
if (p) {
if (p->count == 0) {
p->childs = newtree * [COUNT];
if (p->childs == nullptr) error(1);
p->childs[0] = newtree;
if (p->childs[0] == nullptr) error(1);
p->count = 1;
}
elseif (p->count < COUNT - 1) {
p->childs[p->count] = newtree;
if (p->childs[p->count] == nullptr) error(1);
p->count++;
}
else error(2);
return init(p->childs[p->count - 1], info);
}
returnnullptr;
}
void remove(tree* t, tree* p) {
tree* item = search(t, p->info);
if (item) {
tree* parent = search_parent(t, item);
if (parent) {
for (int i = 0; i < parent->count; i++) if (parent->childs[i]->info == item->info) {
for (int k = i; k < parent->count - 1; k++) parent->childs[k] = parent->childs[k + 1];
parent->count--;
}
}
if (item->count > 0) {
for (int i = item->count - 1; i > -1; i--) {
remove(t, item->childs[i]);
}
item->count = 0;
}
delete item;
}
}
int main(void) {
setlocale(LC_ALL, "Russian");
tree head;
init(&head, 1);
tree* ptr = &head;
add(ptr, 1, 2);
add(ptr, 1, 3);
add(ptr, 1, 4);
tree* ptr2 = add(ptr, 2, 5);
add(ptr, 2, 6);
add(ptr, 5, 7);
add(ptr, 7, 8);
add(ptr, 6, 9);
printf("\nПоисктест: ");
tree* s = search(ptr, 5);
if (s) print1(s); else printf("Ненайдено");
printf("\nВсеэлементы:\n");
print(ptr);
remove(ptr, ptr2);
printf("\nВсе элементы после удаления :\n");
print(ptr);
error(0);
}
Задание 5
constint COUNT = 10;
structtree {
int info;
tree** childs;
int count;
};
void error(intn) {
setlocale(LC_ALL, "Russian");
switch (n) {
case 0: printf("\nНормально"); break;
case 1: printf("\nНетпамяти!"); break;
case 2: printf("\nСлишком много дочерних предметов!"); break;
default: printf("\nНеизвестная ошибка!"); break;
}
fflush(stdin); getchar(); exit(n);
}
tree* init(tree* p, intinfo) {
p->info = info; p->childs = nullptr; p->count = 0; returnp;
}
void print1(tree* p) {
setlocale(LC_ALL, "Russian");
printf("Элемент %d (%d childs)\n", p->info, p->count);
}
void print(tree* p, inttab = 0) {
print1(p);
for (int i = 0; i
for (int k = 0; k <= tab; k++) printf("\t");
print(p->childs[i], ++tab);
--tab;
}
}
tree* search(tree* t, intinfo) {
if (t->info == info) returnt;
elseif (t->count > 0) {
for (int i = 0; i
tree* p = search(t->childs[i], info);
if (p != nullptr) return p;
}
returnnullptr;
}
elsereturnnullptr;
}
tree* search_parent(tree* t, tree* p) {
if (t->count > 0) {
for (int i = 0; i
if (t->childs[i]->info == p->info) returnt;
else {
tree* s = search_parent(t->childs[i], p);
if (s != nullptr) return s;
}
}
returnnullptr;
}
elsereturnnullptr;
}
tree* add(tree* ptr, intparentinfo, intinfo) {
tree* p = search(ptr, parentinfo);
if (p) {
if (p->count == 0) {
p->childs = newtree * [COUNT];
if (p->childs == nullptr) error(1);
p->childs[0] = newtree;
if (p->childs[0] == nullptr) error(1);
p->count = 1;
}
elseif (p->count < COUNT - 1) {
p->childs[p->count] = newtree;
if (p->childs[p->count] == nullptr) error(1);
p->count++;
}
else error(2);
return init(p->childs[p->count - 1], info);
}
returnnullptr;
}
void remove(tree* t, tree* p) {
tree* item = search(t, p->info);
if (item) {
tree* parent = search_parent(t, item);
if (parent) {
for (int i = 0; i < parent->count; i++) if (parent->childs[i]->info == item->info) {
for (int k = i; k < parent->count - 1; k++) parent->childs[k] = parent->childs[k + 1];
parent->count--;
}
}
if (item->count > 0) {
for (int i = item->count - 1; i > -1; i--) {
remove(t, item->childs[i]);
}
item->count = 0;
}
delete item;
}
}
int main(void) {
setlocale(LC_ALL, "Russian");
tree head;
init(&head, 1);
tree* ptr = &head;
add(ptr, 1, 2);
add(ptr, 1, 3);
add(ptr, 1, 4);
tree* ptr2 = add(ptr, 2, 5);
add(ptr, 2, 6);
add(ptr, 5, 7);
add(ptr, 7, 8);
add(ptr, 6, 9);
printf("\nПоисктест: ");
tree* s = search(ptr, 5);
if (s) print1(s); else printf("Ненайдено");
printf("\nВсеэлементы:\n");
print(ptr);
remove(ptr, ptr2);
printf("\nВсе элементы после удаления :\n");
print(ptr);
error(0);
}
-
Ответы на контрольные вопросы
-
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов. -
При первом способе каждый узел (кроме корня) содержит указатель на породивший его узел, т. е. на элемент, находящийся на более высоком уровнеиерархии. Второй способ представления применяют, если каждый узел дерева имеет не более двух (в более общем случае ― не более А) поддеревьев. Третий способ представления состоит в том, что в каждом элементе содержатся два указателя, причем один из них служит для представления списка поддеревьев, а второй для связывания элементов в этот список -
При первом способе каждый узел (кроме корня) содержит указатель на породивший его узел, т. е. на элемент, находящийся на более высоком уровнеиерархии. Второй способ представления применяют, если каждый узел дерева имеет не более двух (в более общем случае ― не более А) поддеревьев. Третий способ представления состоит в том, что в каждом элементе содержатся два указателя, причем один из них служит для представления списка поддеревьев, а второй для связывания элементов в этот список -
«в глубину», «в ширину». с использованием пустых указателей в исходном дереве, с использованием изменения внутренней структуры дерева, «сверзу вниз», «снизу вверх» Говорят, что дерево проходится сверху вниз, если каждый узел всегда проходится раньше, чем поддеревья этого узла.
В этом случае также говорят, что дерево обходится в нисходящем порядке. Аналогично, при обходе снизу вверх (восходящий порядок обхода) узел проходится после того, как пройдены его поддеревья. -
Обход является обходом «в глубину», если в любом поддереве исходного дерева узлы обходятся «подряд», т. е. если обход некоторого поддерева начат, то он продолжается до тех пор, пока все поддерево не будет обойдено -
Обход является обходом «в ширину», если узлы, расположенные ближе к корню дерева, обходятся раньше, чем узлы, отстоящие дальше от корня. При этом расстояние от узла до корня измеряется количеством ребер на кратчайшем пути из этого узла до корня.
-
Вывод по проделанной работе
Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Институт Прикладной математики и компьютерных наук
Кафедра Вычислительной техники
Учебная дисциплина
Программирование
Уровень профессионального образования: (высшее образование – бакалавриат)
Направление подготовки: Информатика и вычислительная техника
Профиль подготовки: Электронно-вычислительные машины, комплексы, системы и сети
Лабораторная работа № 09
Алгоритмические основы программирования на языке С++. Задачи на графах.
Выполнила: Драчева Кристина
Проверил Савин Н.И.
Тула 2023
1 2 3 4 5 6
1. Цель работы
Ознакомится с графами и основными алгоритмами на них.
2. Техническое задание
1) Напишите программу, реализующую алгоритм поиска в ширину.
2) Напишите программу, реализующую алгоритм поиска в глубину.
3) Напишите программу, реализующую алгоритм Беллмана-Форда.
4) Напишите программу, реализующую алгоритм Дейкстры.
5) Напишите программу поиска остовного дерева минимального веса методом Прима.
6) Напишите программу поиска остовного дерева минимального веса методом Крускала
7) Напишите программу поиска мостов в неориентированном графе
8) Напишите программу поиска точек сочленения в неориентированном графе
9) Напишите программу топологической сортировки ациклического ориентированного графа
10) Напишите программу поиска циклов внеориентированном графе
11) Напишите программу поиска компонент сильной связности в ориентированном графе.
3.Постановка задачи
Решить заданные задачи и ответить на контрольные вопросы.
Способ решения. Для решения поставленной задачи будет использован объектно-ориентированный язык программирования С++.
4. Ход работы
Задание№1
Листинг программы:
usingnamespace std;
int main()
{
vector
constint n = 4;
int s = 0;
int Adj[n][n] = {
{0,1,0,0},
{1,0,1,0},
{0,1,0,1},
{0,0,1,0} };
for (int i = 0; i < n; i++)
{
g.push_back(vector
for (int j = 0; j < n; j++)
{
g[i].push_back(0);
g[i][j] = Adj[i][j];
}
}
queue
q.push(s);
vector
vector
used[s]=true;
p[s] = -1;
while (!q.empty())
{
int v = q.front();
for (size_t i = 0; i < g[v].size(); ++i)
{
if (!used[i]&& g[v][i])
{
used[i]=true;
q.push(i);
d[i] = d[v] + 1;
p[i] = v;
}
}
q.pop();
}
for (int i = 0; i < n; i++)
cout << d[i]<<" ";
cout << endl;
for (int i = 0; i < n; i++)
cout << p[i]<<" ";
cout << endl;
system("pause");
return 0;
}
Задание№2
Листингпрограммы:
usingnamespace std;
constint n = 5;
int i, j;
bool* visited = newbool[n];
int graph[n][n] =
{
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0}
};
void DFS(intst)
{
int r;
cout <
visited[st] = true;
for (r = 0; r <= n; r++)
if ((graph[st][r] != 0) && (!visited[r]))
DFS(r);
}
void main()
{
setlocale(LC_ALL, "Rus");
intstart;
cout <<"Матрица смежности графа: "<< endl;
for (i = 0; i < n; i++)
{
visited[i] = false;
for (j = 0; j < n; j++)
cout <<" "<< graph[i][j];
cout << endl;
}
cout <<"Стартоваявершина>> "; cin >> start;
bool* vis = newbool[n];
cout <<"Порядок обхода: ";
DFS(start - 1);
delete[]visited;
system("pause>>void");
}
Задание 3
int C[MAX_N][MAX_N];
int F[MAX_N][MAX_N];
int P[MAX_N][MAX_N];
int push[MAX_N];
int mark[MAX_N];
int pred[MAX_N];
int dist[MAX_N];
int N, M, s, t;
int max_flow;
int min_cost;
void file_read()
{
int u, v, c, p;
in >> N >> M >> s >> t; N++;
for (int i = 0; i < M; i++)
{
in >> u >> v >> c >> p;
C[u][v] = c;
P[u][v] = p;
P[v][u] = -p;
}
}
int edge_cost(intu, intv)
{
if (C[u][v] - F[u][v] > 0) return P[u][v];
elsereturn MAX_VAL;
}
int check_cycles()
{
for (int u = 1; u < N; u++)
for (int v = 1; v < N; v++)
if (dist[v] > dist[u] + edge_cost(u, v))
return u;
return MAX_VAL;
}
void init()
{
for (int i = 1; i < N; i++)
{
mark[i] = 0;
push[i] = 0;
pred[i] = 0;
dist[i] = MAX_VAL;
}
}
int bf(ints)
{
init();
queue
pred[s] = s;
dist[s] = 0;
Q.push(s);
Q.push(MAX_N);
int u, series = 0;
while (!Q.empty())
{
while (Q.front() == MAX_N)
{
Q.pop();
if (++series > N) return check_cycles();
else Q.push(MAX_N);
}
u = Q.front(); Q.pop();
for (int v = 1; v < N; v++)
if (dist[v] > dist[u] + edge_cost(u, v))
{
dist[v] = dist[u] + edge_cost(u, v);
pred[v] = u;
Q.push(v);
}
}
}
int bfs(ints, intt)
{
init();
queue
mark[s] = 1;
pred[s] = s;
push[s] = MAX_VAL;
Q.push(s);
while (!mark[t] && !Q.empty())
{
int u = Q.front(); Q.pop();
for (int v = 1; v < N; v++)
if (!mark[v] && (C[u][v] - F[u][v] > 0))
{
push[v] = min(push[u], C[u][v] - F[u][v]);
mark[v] = 1;
pred[v] = u;
Q.push(v);
}
}
return mark[t];
}
void max_flow_ff()
{
int u, v, flow = 0;
while (bfs(s, t))
{
int add = push[t];
v = t; u = pred[v];
while (v != s)
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
}
flow += add;
}
max_flow = flow;
}
void min_cost_flow()
{
max_flow_ff();
int u, v, flow = 0;
int add = MAX_VAL;
int neg_cycle;
neg_cycle = bf(t);
while (neg_cycle != MAX_VAL)
{
v = neg_cycle; u = pred[v];
do
{
add = min(add, C[u][v] - F[u][v]);
v = u; u = pred[v];
} while (v != neg_cycle);
v = neg_cycle; u = pred[v];
do
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
} while (v != neg_cycle);
neg_cycle = bf(t);
}
for (int u = 1; u < N; u++)
for (int v = 1; v < N; v++)
if (F[u][v] > 0)
min_cost += F[u][v] * P[u][v];
}
void file_write()
{
out << max_flow << endl;
out << min_cost << endl;
}
void main()
{
file_read();
min_cost_flow();
file_write();
}
Задание 4
int main()
{
int f, n, s;
cin >> n;
cin >> s;
cin >> f;
vector
vector
vector
vector
used.assign(n, 0);
distance.assign(n, im);
distance[s - 1] = 0;
for (int i = 0; i < n; i++)
g[i].assign(n, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
for (int i = 0; i < n; i++)
{
int v = -1;
for (int j = 0; j < n; j++)
if (used[j] == false&& (v == -1 || distance[j] < distance[v]))
v = j;
used[v] = true;
for (int j = 0; j < n; j++)
if (g[v][j] != -1 && distance[v] + g[v][j] < distance[j])
{
parents[j] = v;
distance[j] = distance[v] + g[v][j];
}
}
if (distance[f - 1] != im)
cout << distance[f - 1] << endl;
else
cout << -1 << endl;
//system("pause");
return 0;
}
Задание 5
Листингпрограммы:
usingnamespace std;
constint INF = 1e9 + 7;
vector
bool used[100000
int main() {
int mst_weight = 0;
priority_queue
q.push({ 0, 0 });
while (!q.empty()) {
pair
q.pop();
int dst = c.first, v = c.second;
if (used[v]) {
continue;
}
used[v] = true;
mst_weight += dst;
for (pair
int u = e.first, len_vu = e.second;
if (!used[u]) {
q.push({ len_vu, u });
}
}
}
cout <<"Minimum spanning tree weight: "<< mst_weight << endl;
}
Задание№6
Листингпрограммы:
usingnamespace std;
typedeflonglongll;
constll maxn = 100, maxm = 200;
vector
vector
ll i, j, k, z = 0, temp, r, n, m;
ll findroot(llv)
{
return d[v] == -1 ? v : d[v] = findroot(d[v]);
}
bool union_set(lla, llb)
{
ll q1, q2;
q1 = findroot(a);
q2 = findroot(b);
if (q1 != q2)
{
r = rand() % 2;
r == 0 ? d[q1] = q2 : d[q2] = q1;
returntrue;
}
returnfalse;
}
void input()
{
scanf("%I64d %I64d", &n, &m);
for (i = 0; i < m; ++i)
{
scanf("%I64d %I64d %I64d", &a[i].second.first, &a[i].second.second, &a[i].first);
}
}
void sol()
{
sort(a.begin(), a.begin() + m);
temp = n - 1;
for (i = 0; i < m && z < temp; ++i)
{
if (union_set(a[i].second.first, a[i].second.second))
{
++z;
p.push_back(a[i]);
}
}
}
void output()
{
for (i = 0; i < p.size(); ++i)
printf("%I64d -> %I64d = %I64d\n", p[i].second.first, p[i].second.second, p[i].first);
}
int main()
{
srand(time(0));
input();
sol();
output();
system("pause");
return 0;
}
Задание 7
Листинг программы:
intconstn = 4;
int timer, tin[n], fup[n];
bool used[n];
int mx[n][n];
void dfs(intv, intp = -1)
{
used[v] = true;
tin[v] = fup[v] = timer++;
for (int i = 0; i < n; ++i)
{
if (mx[v][i] == 1)
{
int to = i;
if (to == p) continue;
if (used[to]) fup[v] = std::min(fup[v], tin[to]);
else
{
dfs(to, v);
fup[v] = std::min(fup[v], fup[to]);
if (fup[to] > tin[v]) std::cout <<"bridge: ("<
}
}
}
}
void find_bridges()
{
timer = 0;
for (int i = 0; i < n; ++i)
{
used[i] = false;
}
for (int i = 0; i < n; ++i)
{
if (!used[i]) dfs(i);
}
}
int main()
{
srand(time(0));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
int tmp = rand() % n;
if (!tmp) mx[i][j] = 1;
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (mx[i][j]) mx[j][i] = 1;
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << mx[i][j] <<" ";
}
std::cout <<"\n";
}
find_bridges();
return 0;
}
Задание 8
Листинг программы:
namespaceTSG
{
classTSG
{
staticint n, ic;
staticint[] P;
staticbool[] mark;
staticint number = 0;
staticint[, ] G;
staticvoid insert_matr()
{
StreamReader R = new StreamReader("in.txt");
string[] lines = File.ReadAllLines("in.txt").ToArray();
n = lines.Length;
G = newint[n, n];
for (int i = 0; i < n; i++)
{
int[] row = lines[i].Split(newchar[] { ',', ' ', '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
for (int j = 0; j < n; j++)
{
G[i, j] = row[j];
}
}
P = newint[n];
mark = newbool[n];
for (int i = 0; i < n; i++)
{
mark[i] = false;
P[i] = -1;
}
ic = 1;
R.Close();
}
publicstaticint func(int[, ] G, intn)
{
int result;
for (int i = 0; i
{
if (mark[i] == false)
{
dfs(G, n, i);
for (int k = 0; k
{
if (P[k] != -1)
Console.Write(P[k] + 1 + " ");
P[k] = -1;
}
number++;
Console.WriteLine();
}
}
Console.WriteLine("Числокомпонентовсвязностей - {0}", number);
result = number;
number = 0;
return result;
}
staticvoid dfs(int[, ] G, intn, intv)
{
int i;
P[ic - 1] = v;
mark[v] = true;
for (i = 0; i
{
if (G[v, i] == 1 && !mark[i])
{
ic++;
dfs(G, n, i);
}
}
}
staticvoid delete_points(intk)
{
if (k< n - 1)
{
int num = k;
int a = -1;
int b = -1;
int[, ] G2 = newint[n - 1, n - 1];
for (int str = 0; str < n; str++)
{
a++;
b = -1;
for (int stolb = 0; stolb < n; stolb++)
{
b++;
if (k == stolb)
{
b--;
}
if (k == str)
{
a--;
break;
}
if (k != str &&k != stolb)
{
G2[a, b] = G[str, stolb];
}
}
}
P = newint[n - 1];
mark = newbool[n - 1];
for (int i = 0; i < n - 1; i++)
{
mark[i] = false;
P[i] = -1;
}
ic = 1;
if (func(G2, n - 1) > 1)
Console.WriteLine("\n\n\nТочкасочленения №{0}", k);
delete_points(k + 1);
}
}
}
}
Задание№9
Листингпрограммы:
usingnamespace std;
vector
int n;
bool used[15];
vector
void dfs(intv) {
used[v] = true;
for (size_t i = 0; i < g[v].size(); ++i) {
int to = g[v][i];
if (!used[to])
dfs(to);
}
ans.push_back(v);
}
void topological_sort() {
for (int i = 0; i < n; ++i)
used[i] = false;
ans.clear();
for (int i = 0; i < n; ++i)
if (!used[i])
dfs(i);
reverse(ans.begin(), ans.end());
}
int main()
{
return 0;
}
Задание 10
int from = 0, n = 0, k = 0, ncycle = 0, to;
void DFS(intv) {
color[v] = 1;
for (int i = 0; i < nreber; i++) {
if (g[i][0] == v) {
to = g[i][1];
if (color[to] == 0) {
p[n][0] = g[i][0];
p[n][1] = g[i][1];
from = v;
n++;
DFS(to);
}
elseif (color[to] = 1) {
p[n][0] = g[i][0];
p[n][1] = g[i][1];
k = n;
cout << ncycle + 1 <<") ";
for (int i = 0; i < k; i++)
cout << p[i][0] <<'-'<< p[i][1] <<' ';
cout << p[k][0] <<'-'<< p[k][1] <<' '<< endl;
ncycle++;
}
color[v] = 2;
}
}
}
Задание№11
Листингпрограммы:
void dfs(intv) {
if (used[v]) {
return;
}
used[v] = true;
for (int i = 0; i < adj[v].size(); ++i) {
adjT = new vector[n];
for (int i = 0; i < m; ++i) {
int v, w; scanf("%d %d", &v, &w); v--; w--; adj[v].push_back(w);
int v = topSort[i];
if (!used[v]) {
ccs(v, componentID);
componentID++;
}
}
componentCount = componentID;
printData();
}
int main()
{
run();
return 0;
}
5.Ответы на контрольные вопросы
-
Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время. алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. -
общая стоимость выполнения строк 4-7 процедуры DFS_Visit равна Θ(Е). Время работы процедуры DFS, таким образом, равно Θ(V + Е). -
Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов. -
Метод поиск в глубину получил такое название за то, что при его реализации можно дальше уйти от исходной вершины, а когда идти уже некуда, возвращаемся в ту вершину, откуда идет хотя бы одно ребро в не пройденные еще вершины -
Алгоритм Дейкстры решает задачу о кратчайшем пути из одной вершины во взвешенном ориентированном графе G = (V, Е) в том случае, когда веса ребер неотрицательны. Поэтому в настоящем разделе предполагается, что для всех ребер (u, v) Є Е выполняется неравенство w (u, v) ≥ 0. Через некоторое время станет понятно, что при хорошей реализации алгоритм Дейкстры производительнее, чем алгоритм БеллманаФорда.
1 2 3 4 5 6
6.Вывод по проделанной работе
Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Институт Прикладной математики и компьютерных наук
Кафедра Вычислительной техники
Учебная дисциплина
Программирование
Уровень профессионального образования: (высшее образование – бакалавриат)
Направление подготовки: Информатика и вычислительная техника
Профиль подготовки: Электронно-вычислительные машины, комплексы, системы и сети
Лабораторная работа № 10
Классы в языке С++
Выполнила: Драчева Кристина
Проверил Савин Н.И.
Тула 2023
1. Цель работы
Ознакомление с основными концепциями объектно-ориентированного программирования; изучение классов языка С++, способов их описания и использования, получение представления о перегрузке операторов и функций; получение навыков применения объектов в прикладных программах.
2. Техническое задание
1. Разработать класс, позволяющий выполнять действия над матрицами произвольных размерностей (сложение, вычитание, умножение, транспонирование, нахождение определителя). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
2. Разработать класс, позволяющий выполнять действия над векторами произвольной длины (сложение, вычитание, скалярное и векторное умножение, нахождение модуля и направляющих косинусов). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
3. Разработать класс, позволяющий оперировать с комплексными числами (сложение, вычитание, умножение, деление, возведение в степень, извлечение корня, перевод из одной формы записи в другую). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
4. Разработать класс, позволяющий оперировать с множествами целых чисел (находить объединение, пересечение, инверсию и мощность множеств). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
5. Разработать класс, позволяющий хранить и обрабатывать информацию о студентах группы (добавление информации, сортировку по различным критериям, поиск по различным критериям, вывод информации об успеваемости, выбор всех отличников, хорошистов, троечников, выбор всех студентов, имеющих средний балл не ниже заданного). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
3.Постановка задачи
Решить заданные задачи и ответить на контрольные вопросы.
Способ решения. Для решения поставленной задачи будет использован объектно-ориентированный язык программирования С++.
4.Ходработы
Задание №1
Листингпрограммы:
usingnamespace std;
classArray
{
protected:
int** _data;
int _cols, _rows;
public:
Array(void) : _data(0), _rows(0), _cols(0) {};
Array(introws, intcols, boolfill = false, intfiller = 0)
: _rows(rows), _cols(cols), _data(0)
{
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
{
_data[i] = newint[_cols];
if (fill)
for (int j = 0; j < _cols; j++)
_data[i][j] = filler;
}
}
Array(constArray&other) :
_cols(other.cols()),
_rows(other.rows())
{
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
{
_data[i] = newint[_cols];
for (int j = 0; j < _cols; j++)
_data[i][j] = other._data[i][j];
}
}
constArray transpon() const
{
Array C(_cols, _rows);
for (int i = 0; i < _cols; i++)
for (int j = 0; j < _rows; j++)
C[i][j] = _data[j][i];
return C;
}
constArrayoperator+(constArray&other) const
{
if ((_cols != other.cols()) || (_rows != other.rows()))
throwout_of_range("матрицынеимеют");
Array C(_rows, _cols);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
C._data[i][j] = _data[i][j] + other._data[i][j];
return C;
}
constArrayoperator-(constArray&other) const
{
if ((_cols != other.cols()) || (_rows != other.rows()))
throwout_of_range("Multiplied matrixes do not have same number of cols and rows.");
Array C(_rows, _cols);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
C._data[i][j] = _data[i][j] - other._data[i][j];
return C;
}
constArrayoperator*(constArray&other) const
{
if (_cols != other.rows())
throwout_of_range("Multiplied matrixes do not have same number of cols and rows.");
Array C(_rows, other.cols(), true);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
for (int k = 0; k < _cols; k++)
C[i][j] += _data[i][k] * other._data[k][j];
return C;
}
constArrayoperator<<(constArray&other) const
{
}
Array&operator= (constArray&other)
{
if (this != &other)
{
if (_data != 0)
{
for (int i = 0; i < _rows; i++)
delete[] _data[i];
delete[] _data;
}
_rows = other.rows();
_cols = other.cols();
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
_data[i] = newint[_cols];
for (int i = 0; i < _rows; i++)
for (int j = 0; j < _cols; j++)
_data[i][j] = other._data[i][j];
}
return *this;
}
friendostream&operator<< (ostream& o, constArray& a)
{
for (int i = 0; i < a._rows; i++)
{
for (int j = 0; j < a._cols; j++)
o << setw(4) << a._data[i][j];
o << endl;
}
return o;
}
void fill_random()
{
for (int i = 0; i < _rows; i++)
for (int j = 0; j < _cols; j++)
_data[i][j] = rand() % 100 + 1;
}
int* operator[](inti) { return _data[i]; }
int& at(inti, intj) { return _data[i][j]; }
constint cols() const { return _cols; }
constint rows() const { return _rows; }
Array()
{
if (_data != 0)
{
for (int i = 0; i < _rows; i++)
delete[] _data[i];
delete[] _data;
}
}
};
int main()
{
srand(static_cast(time(0)));
int N, M, K;
cin >> N >> M >> K;
Array x(N, M, true, 1);
Array y(N, M, true, 1);
Array z(N, K);
z.fill_random();
cout << (x * y) << endl;
cout << (x + y) << endl;
cout << z << endl << z.transpon() << endl;
return 0;
}
Задание № 2
Листингпрограммы:
usingnamespace std;
classVector
{
private:
int x;
int y;
int z;
public:
Vector() : x(0), y(0), z(0)
{}
Vector(intvx, intvy, intvz) : x(vx), y(vy), z(vz)
{}
void showVector()
{
cout << x <<":"<< y <<":"<< z <<"";
}
void showProizVector()
{
cout << x + y + z <<"";
}
Vectoroperator+(Vector)const;
Vectoroperator%(Vector)const;
Vectoroperator*(Vector)const;
};
VectorVector :: operator+ (Vectord2)const
{
int vx = x + d2.x;
int vy = y + d2.y;
int vz = z + d2.z;
returnVector(vx, vy, vz);
}
VectorVector :: operator% (Vectord2)const
{
int vx = x * d2.x;
int vy = y * d2.y;
int vz = z * d2.z;
returnVector((vx + vy + vz), vx * 0, vy * 0);
}
VectorVector :: operator* (Vectord2)const
{
int vx = y * d2.z - z * d2.y;
int vy = z * d2.x - x * d2.z;
int vz = x * d2.y - y * d2.x;
returnVector((vx + vy + vz), vx * 0, vy * 0);
}
int _tmain(intargc, _TCHAR* argv[])
{
setlocale(0, "Rus");
int x, y, z, i, j, k;
Vector a, b, c;
cout <<"Введитекоординатывектора a: "<< endl;
cin >> x >> y >> z;
cout <<"Введите координаты вектора b: "<< endl;
cin >> i >> j >> k;
a =Vector(x, y, z);
b =Vector(i, j, k);
c = a + b;
cout <<"Сложение a("; a.showVector(); cout <<") + b("; b.showVector(); cout <<") = c("; c.showVector(); cout <<")"<< endl;
c = a % b;
cout <<"Скалярноепроизведение a("; a.showVector(); cout <<") % b("; b.showVector(); cout <<") = "; c.showProizVector(); cout << endl;
c = a * b;
cout <<"Векторноепроизведение a("; a.showVector(); cout <<") * b("; b.showVector(); cout <<") = "; c.showProizVector(); cout << endl;
cin.get();
cin.get();
return 0;
}
Задание№3
Листингпрограммы:
usingnamespacestd;
classComplex
{
private:
double real;
double image;
public:
Complex() {};
Complex(doubler) { real = r; image = 0; }
Complex(doubler, doublei) { real = r, image = i; }
Complex() {}
float abs() а
{
return sqrt(real * real - image * image);
}
Complex operator+(Complex&);
Complexoperator-(Complex&);
Complexoperator*(Complex&);
Complexoperator/(Complex&);
friendostream&operator<<(ostream&, Complex&);
friendistream&operator>>(istream&, Complex&);
};
ComplexComplex::operator+(Complex&fp1)
{
fp1.real = real + fp1.real;
fp1.image = image + fp1.image;
returnfp1;
}
ComplexComplex::operator-(Complex&fp1)
{
fp1.real = real - fp1.real;
fp1.image = image - fp1.image;
returnfp1;
}
ComplexComplex::operator*(Complex&fp1)
{
double i, j;
i = real * fp1.real - image * fp1.image;
j = real * fp1.image + fp1.real * image;
fp1.real = i;
fp1.image = j;
returnfp1;
}
ComplexComplex::operator/(Complex&fp1)
{
double k, i, j;
k = fp1.real * fp1.real + fp1.image * fp1.image;
i = (real * fp1.real + image * fp1.image) / k;
j = (fp1.real * image - real * fp1.image) / k;
fp1.real = i;
fp1.image = j;
returnfp1;
}
ostream&operator<< (ostream&fo, Complex&fp)
{
if (fp.image < 0) fo<
elsefo<
}
istream&operator>>(istream&fi, Complex&fp)
{
cout <<"Введите действительную часть: ";
fi>>fp.real;
cout <<"Введите мнимую часть: ";
fi>>fp.image;
returnfi;
}
void main()
{
setlocale(LC_ALL, "Russian");
Complex c1, c2, c3, c4, c5;
cin >> c1;
cin >> c2;
cin >> c3;
cin >> c4;
cin >> c5;
cout <<"\nc1 = "<< c1;
cout <<"c2 = "<< c2;
cout <<"c3 = "<< c3;
cout <<"c4 = "<< c4;
cout <<"c5 = "<< c5 <<'\n';
cout <<"Модуль c1: "<< c1.abs() <<"\n\n";
cout <<"c1 + c2 = "<< (c1 + c2);
cout <<"c1 - c3 = "<< (c1 - c3);
cout <<"c1 * c4 = "<< (c1 * c4);
cout <<"c1 / c5 = "<< (c1 / c5);
system("pause");
}
Задание №4
Листинг программы:
usingnamespace std;
classArray
{
int* mas, k;
void Add(int);
void Sub(int);
public:
Array() :k(0), mas(newint(0)) {};
Array(constArray&);
Array() { delete[]mas; };
voidoperator+=(intn) { Add(n); };
voidoperator+=(Array&);
voidoperator-=(intn) { Sub(n); };
voidoperator-=(constArray&);
Arrayoperator*(constArray&)const;
voidoperator*=(constArray&);
friendbooloperator==(Array&, Array&);
friendbooloperator<=(Array&, Array&);
friendostream&operator<<(ostream&, constArray&);
friendistream&operator>>(istream&s, Array&);
int HowMany() { return k; };
};
Array::Array(constArray&x) :k(x.k)
{
mas = newint[k];
for (int i = 0; i < k; i++)
mas[i] = x.mas[i];
}
voidArray::Add(intn)
{
int* t, pos;
for (pos = 0; pos < k && mas[pos]
if (mas[pos] != n)
{
t = newint[++k];
for (int i = 0; i < k - 1; i++)
t[i < pos ? i : i + 1] = mas[i];
t[pos] = n;
delete[]mas;
mas = t;
}
}
voidArray::operator+=(Array&x)
{
for (int i = 0; i
Add(x.mas[i]);
}
voidArray::Sub(intn)
{
if (k > 0)
{
int* t, pos;
for (pos = 0; pos < k && mas[pos]
if (mas[pos] == n)
{
t = newint[--k];
for (int i = 0; i < k + 1; i++)
if (i != pos) t[i < pos ? i : i - 1] = mas[i];
delete[]mas;
mas = t;
}
}
}
voidArray::operator-=(constArray&x)
{
for (int i = 0; i
return Sub(x.mas[i]);
}
ArrayArray::operator*(constArray&x)const
{
Array t(*this), t2(*this);
t -=x;
for (int i = 0; i < t.k; ++i)
t2.Sub(t.mas[i]);
return t2;
}
voidArray::operator*=(constArray&x)
{
Array t(*this);
t -=x;
for (int i = 0; i < t.k; i++)
Sub(t.mas[i]);
}
booloperator==(Array&x, Array&y)
{
if (x.k != y.k) returnfalse;
for (int i = 0; i
if (x.mas[i] != y.mas[i]) returnfalse;
returntrue;
}
booloperator<=(Array&x, Array&y)
{
int s = 0;
for (int i = 0; i
while (x.mas[i] != y.mas[i + s])
{
if (x.k + s >y.k) returnfalse;
s++;
}
returntrue;
}
ostream&operator<<(ostream&s, constArray&p)
{
if (p.k != 0) {
s<<"(";
for (int i = 0; i
6.Вывод по проделанной работе
Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Институт Прикладной математики и компьютерных наук
Кафедра Вычислительной техники
Учебная дисциплина
Программирование
Уровень профессионального образования: (высшее образование – бакалавриат)
Направление подготовки: Информатика и вычислительная техника
Профиль подготовки: Электронно-вычислительные машины, комплексы, системы и сети
Лабораторная работа № 10
Классы в языке С++
Выполнила: Драчева Кристина
Проверил Савин Н.И.
Тула 2023
1. Цель работы
Ознакомление с основными концепциями объектно-ориентированного программирования; изучение классов языка С++, способов их описания и использования, получение представления о перегрузке операторов и функций; получение навыков применения объектов в прикладных программах.
2. Техническое задание
1. Разработать класс, позволяющий выполнять действия над матрицами произвольных размерностей (сложение, вычитание, умножение, транспонирование, нахождение определителя). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
2. Разработать класс, позволяющий выполнять действия над векторами произвольной длины (сложение, вычитание, скалярное и векторное умножение, нахождение модуля и направляющих косинусов). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
3. Разработать класс, позволяющий оперировать с комплексными числами (сложение, вычитание, умножение, деление, возведение в степень, извлечение корня, перевод из одной формы записи в другую). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
4. Разработать класс, позволяющий оперировать с множествами целых чисел (находить объединение, пересечение, инверсию и мощность множеств). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
5. Разработать класс, позволяющий хранить и обрабатывать информацию о студентах группы (добавление информации, сортировку по различным критериям, поиск по различным критериям, вывод информации об успеваемости, выбор всех отличников, хорошистов, троечников, выбор всех студентов, имеющих средний балл не ниже заданного). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
3.Постановка задачи
Решить заданные задачи и ответить на контрольные вопросы.
Способ решения. Для решения поставленной задачи будет использован объектно-ориентированный язык программирования С++.
4.Ходработы
Задание №1
Листингпрограммы:
usingnamespace std;
classArray
{
protected:
int** _data;
int _cols, _rows;
public:
Array(void) : _data(0), _rows(0), _cols(0) {};
Array(introws, intcols, boolfill = false, intfiller = 0)
: _rows(rows), _cols(cols), _data(0)
{
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
{
_data[i] = newint[_cols];
if (fill)
for (int j = 0; j < _cols; j++)
_data[i][j] = filler;
}
}
Array(constArray&other) :
_cols(other.cols()),
_rows(other.rows())
{
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
{
_data[i] = newint[_cols];
for (int j = 0; j < _cols; j++)
_data[i][j] = other._data[i][j];
}
}
constArray transpon() const
{
Array C(_cols, _rows);
for (int i = 0; i < _cols; i++)
for (int j = 0; j < _rows; j++)
C[i][j] = _data[j][i];
return C;
}
constArrayoperator+(constArray&other) const
{
if ((_cols != other.cols()) || (_rows != other.rows()))
throwout_of_range("матрицынеимеют");
Array C(_rows, _cols);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
C._data[i][j] = _data[i][j] + other._data[i][j];
return C;
}
constArrayoperator-(constArray&other) const
{
if ((_cols != other.cols()) || (_rows != other.rows()))
throwout_of_range("Multiplied matrixes do not have same number of cols and rows.");
Array C(_rows, _cols);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
C._data[i][j] = _data[i][j] - other._data[i][j];
return C;
}
constArrayoperator*(constArray&other) const
{
if (_cols != other.rows())
throwout_of_range("Multiplied matrixes do not have same number of cols and rows.");
Array C(_rows, other.cols(), true);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
for (int k = 0; k < _cols; k++)
C[i][j] += _data[i][k] * other._data[k][j];
return C;
}
constArrayoperator<<(constArray&other) const
{
}
Array&operator= (constArray&other)
{
if (this != &other)
{
if (_data != 0)
{
for (int i = 0; i < _rows; i++)
delete[] _data[i];
delete[] _data;
}
_rows = other.rows();
_cols = other.cols();
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
_data[i] = newint[_cols];
for (int i = 0; i < _rows; i++)
for (int j = 0; j < _cols; j++)
_data[i][j] = other._data[i][j];
}
return *this;
}
friendostream&operator<< (ostream& o, constArray& a)
{
for (int i = 0; i < a._rows; i++)
{
for (int j = 0; j < a._cols; j++)
o << setw(4) << a._data[i][j];
o << endl;
}
return o;
}
void fill_random()
{
for (int i = 0; i < _rows; i++)
for (int j = 0; j < _cols; j++)
_data[i][j] = rand() % 100 + 1;
}
int* operator[](inti) { return _data[i]; }
int& at(inti, intj) { return _data[i][j]; }
constint cols() const { return _cols; }
constint rows() const { return _rows; }
Array()
{
if (_data != 0)
{
for (int i = 0; i < _rows; i++)
delete[] _data[i];
delete[] _data;
}
}
};
int main()
{
srand(static_cast(time(0)));
int N, M, K;
cin >> N >> M >> K;
Array x(N, M, true, 1);
Array y(N, M, true, 1);
Array z(N, K);
z.fill_random();
cout << (x * y) << endl;
cout << (x + y) << endl;
cout << z << endl << z.transpon() << endl;
return 0;
}
Задание № 2
Листингпрограммы:
usingnamespace std;
classVector
{
private:
int x;
int y;
int z;
public:
Vector() : x(0), y(0), z(0)
{}
Vector(intvx, intvy, intvz) : x(vx), y(vy), z(vz)
{}
void showVector()
{
cout << x <<":"<< y <<":"<< z <<"";
}
void showProizVector()
{
cout << x + y + z <<"";
}
Vectoroperator+(Vector)const;
Vectoroperator%(Vector)const;
Vectoroperator*(Vector)const;
};
VectorVector :: operator+ (Vectord2)const
{
int vx = x + d2.x;
int vy = y + d2.y;
int vz = z + d2.z;
returnVector(vx, vy, vz);
}
VectorVector :: operator% (Vectord2)const
{
int vx = x * d2.x;
int vy = y * d2.y;
int vz = z * d2.z;
returnVector((vx + vy + vz), vx * 0, vy * 0);
}
VectorVector :: operator* (Vectord2)const
{
int vx = y * d2.z - z * d2.y;
int vy = z * d2.x - x * d2.z;
int vz = x * d2.y - y * d2.x;
returnVector((vx + vy + vz), vx * 0, vy * 0);
}
int _tmain(intargc, _TCHAR* argv[])
{
setlocale(0, "Rus");
int x, y, z, i, j, k;
Vector a, b, c;
cout <<"Введитекоординатывектора a: "<< endl;
cin >> x >> y >> z;
cout <<"Введите координаты вектора b: "<< endl;
cin >> i >> j >> k;
a =Vector(x, y, z);
b =Vector(i, j, k);
c = a + b;
cout <<"Сложение a("; a.showVector(); cout <<") + b("; b.showVector(); cout <<") = c("; c.showVector(); cout <<")"<< endl;
c = a % b;
cout <<"Скалярноепроизведение a("; a.showVector(); cout <<") % b("; b.showVector(); cout <<") = "; c.showProizVector(); cout << endl;
c = a * b;
cout <<"Векторноепроизведение a("; a.showVector(); cout <<") * b("; b.showVector(); cout <<") = "; c.showProizVector(); cout << endl;
cin.get();
cin.get();
return 0;
}
Задание№3
Листингпрограммы:
usingnamespacestd;
classComplex
{
private:
double real;
double image;
public:
Complex() {};
Complex(doubler) { real = r; image = 0; }
Complex(doubler, doublei) { real = r, image = i; }
Complex() {} 6.Вывод по проделанной работе
Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Институт Прикладной математики и компьютерных наук
Кафедра Вычислительной техники
Учебная дисциплина
Программирование
Уровень профессионального образования: (высшее образование – бакалавриат)
Направление подготовки: Информатика и вычислительная техника
Профиль подготовки: Электронно-вычислительные машины, комплексы, системы и сети
Лабораторная работа № 10
Классы в языке С++
Выполнила: Драчева Кристина
Проверил Савин Н.И.
Тула 2023
1. Цель работы
Ознакомление с основными концепциями объектно-ориентированного программирования; изучение классов языка С++, способов их описания и использования, получение представления о перегрузке операторов и функций; получение навыков применения объектов в прикладных программах.
2. Техническое задание
1. Разработать класс, позволяющий выполнять действия над матрицами произвольных размерностей (сложение, вычитание, умножение, транспонирование, нахождение определителя). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
2. Разработать класс, позволяющий выполнять действия над векторами произвольной длины (сложение, вычитание, скалярное и векторное умножение, нахождение модуля и направляющих косинусов). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
3. Разработать класс, позволяющий оперировать с комплексными числами (сложение, вычитание, умножение, деление, возведение в степень, извлечение корня, перевод из одной формы записи в другую). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
4. Разработать класс, позволяющий оперировать с множествами целых чисел (находить объединение, пересечение, инверсию и мощность множеств). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
5. Разработать класс, позволяющий хранить и обрабатывать информацию о студентах группы (добавление информации, сортировку по различным критериям, поиск по различным критериям, вывод информации об успеваемости, выбор всех отличников, хорошистов, троечников, выбор всех студентов, имеющих средний балл не ниже заданного). Интерфейс класса должен включать перегруженные операторы. Предусмотреть возможность загрузки данных из файла.
3.Постановка задачи
Решить заданные задачи и ответить на контрольные вопросы.
Способ решения. Для решения поставленной задачи будет использован объектно-ориентированный язык программирования С++.
4.Ходработы
Задание №1
Листингпрограммы:
usingnamespace std;
classArray
{
protected:
int** _data;
int _cols, _rows;
public:
Array(void) : _data(0), _rows(0), _cols(0) {};
Array(introws, intcols, boolfill = false, intfiller = 0)
: _rows(rows), _cols(cols), _data(0)
{
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
{
_data[i] = newint[_cols];
if (fill)
for (int j = 0; j < _cols; j++)
_data[i][j] = filler;
}
}
Array(constArray&other) :
_cols(other.cols()),
_rows(other.rows())
{
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
{
_data[i] = newint[_cols];
for (int j = 0; j < _cols; j++)
_data[i][j] = other._data[i][j];
}
}
constArray transpon() const
{
Array C(_cols, _rows);
for (int i = 0; i < _cols; i++)
for (int j = 0; j < _rows; j++)
C[i][j] = _data[j][i];
return C;
}
constArrayoperator+(constArray&other) const
{
if ((_cols != other.cols()) || (_rows != other.rows()))
throwout_of_range("матрицынеимеют");
Array C(_rows, _cols);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
C._data[i][j] = _data[i][j] + other._data[i][j];
return C;
}
constArrayoperator-(constArray&other) const
{
if ((_cols != other.cols()) || (_rows != other.rows()))
throwout_of_range("Multiplied matrixes do not have same number of cols and rows.");
Array C(_rows, _cols);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
C._data[i][j] = _data[i][j] - other._data[i][j];
return C;
}
constArrayoperator*(constArray&other) const
{
if (_cols != other.rows())
throwout_of_range("Multiplied matrixes do not have same number of cols and rows.");
Array C(_rows, other.cols(), true);
for (int i = 0; i < C.rows(); i++)
for (int j = 0; j < C.cols(); j++)
for (int k = 0; k < _cols; k++)
C[i][j] += _data[i][k] * other._data[k][j];
return C;
}
constArrayoperator<<(constArray&other) const
{
}
Array&operator= (constArray&other)
{
if (this != &other)
{
if (_data != 0)
{
for (int i = 0; i < _rows; i++)
delete[] _data[i];
delete[] _data;
}
_rows = other.rows();
_cols = other.cols();
_data = newint* [_rows];
for (int i = 0; i < _rows; i++)
_data[i] = newint[_cols];
for (int i = 0; i < _rows; i++)
for (int j = 0; j < _cols; j++)
_data[i][j] = other._data[i][j];
}
return *this;
}
friendostream&operator<< (ostream& o, constArray& a)
{
for (int i = 0; i < a._rows; i++)
{
for (int j = 0; j < a._cols; j++)
o << setw(4) << a._data[i][j];
o << endl;
}
return o;
}
void fill_random()
{
for (int i = 0; i < _rows; i++)
for (int j = 0; j < _cols; j++)
_data[i][j] = rand() % 100 + 1;
}
int* operator[](inti) { return _data[i]; }
int& at(inti, intj) { return _data[i][j]; }
constint cols() const { return _cols; }
constint rows() const { return _rows; }
int N, M, K;
cin >> N >> M >> K;
Array x(N, M, true, 1);
Array y(N, M, true, 1);
Array z(N, K);
z.fill_random();
cout << (x * y) << endl;
cout << (x + y) << endl;
cout << z << endl << z.transpon() << endl;
return 0;
}
Задание № 2
Листингпрограммы:
usingnamespace std;
classVector
{
private:
int x;
int y;
int z;
public:
Vector() : x(0), y(0), z(0)
{}
Vector(intvx, intvy, intvz) : x(vx), y(vy), z(vz)
{}
void showVector()
{
cout << x <<":"<< y <<":"<< z <<"";
}
void showProizVector()
{
cout << x + y + z <<"";
}
Vectoroperator+(Vector)const;
Vectoroperator%(Vector)const;
Vectoroperator*(Vector)const;
};
VectorVector :: operator+ (Vectord2)const
{
int vx = x + d2.x;
int vy = y + d2.y;
int vz = z + d2.z;
returnVector(vx, vy, vz);
}
VectorVector :: operator% (Vectord2)const
{
int vx = x * d2.x;
int vy = y * d2.y;
int vz = z * d2.z;
returnVector((vx + vy + vz), vx * 0, vy * 0);
}
VectorVector :: operator* (Vectord2)const
{
int vx = y * d2.z - z * d2.y;
int vy = z * d2.x - x * d2.z;
int vz = x * d2.y - y * d2.x;
returnVector((vx + vy + vz), vx * 0, vy * 0);
}
int _tmain(intargc, _TCHAR* argv[])
{
setlocale(0, "Rus");
int x, y, z, i, j, k;
Vector a, b, c;
cout <<"Введитекоординатывектора a: "<< endl;
cin >> x >> y >> z;
cout <<"Введите координаты вектора b: "<< endl;
cin >> i >> j >> k;
a =Vector(x, y, z);
b =Vector(i, j, k);
c = a + b;
cout <<"Сложение a("; a.showVector(); cout <<") + b("; b.showVector(); cout <<") = c("; c.showVector(); cout <<")"<< endl;
c = a % b;
cout <<"Скалярноепроизведение a("; a.showVector(); cout <<") % b("; b.showVector(); cout <<") = "; c.showProizVector(); cout << endl;
c = a * b;
cout <<"Векторноепроизведение a("; a.showVector(); cout <<") * b("; b.showVector(); cout <<") = "; c.showProizVector(); cout << endl;
cin.get();
cin.get();
return 0;
}
Задание№3
Листингпрограммы:
usingnamespacestd;
classComplex
{
private:
double real;
double image;
public:
Complex() {};
Complex(doubler) { real = r; image = 0; }
Complex(doubler, doublei) { real = r, image = i; }
float abs() а
{
return sqrt(real * real - image * image);
}
Complex operator+(Complex&);
Complexoperator-(Complex&);
Complexoperator*(Complex&);
Complexoperator/(Complex&);
friendostream&operator<<(ostream&, Complex&);
friendistream&operator>>(istream&, Complex&);
};
ComplexComplex::operator+(Complex&fp1)
{
fp1.real = real + fp1.real;
fp1.image = image + fp1.image;
returnfp1;
}
ComplexComplex::operator-(Complex&fp1)
{
fp1.real = real - fp1.real;
fp1.image = image - fp1.image;
returnfp1;
}
ComplexComplex::operator*(Complex&fp1)
{
double i, j;
i = real * fp1.real - image * fp1.image;
j = real * fp1.image + fp1.real * image;
fp1.real = i;
fp1.image = j;
returnfp1;
}
ComplexComplex::operator/(Complex&fp1)
{
double k, i, j;
k = fp1.real * fp1.real + fp1.image * fp1.image;
i = (real * fp1.real + image * fp1.image) / k;
j = (fp1.real * image - real * fp1.image) / k;
fp1.real = i;
fp1.image = j;
returnfp1;
}
ostream&operator<< (ostream&fo, Complex&fp)
{
if (fp.image < 0) fo<
elsefo<
}
istream&operator>>(istream&fi, Complex&fp)
{
cout <<"Введите действительную часть: ";
fi>>fp.real;
cout <<"Введите мнимую часть: ";
fi>>fp.image;
returnfi;
}
void main()
{
setlocale(LC_ALL, "Russian");
Complex c1, c2, c3, c4, c5;
cin >> c1;
cin >> c2;
cin >> c3;
cin >> c4;
cin >> c5;
cout <<"\nc1 = "<< c1;
cout <<"c2 = "<< c2;
cout <<"c3 = "<< c3;
cout <<"c4 = "<< c4;
cout <<"c5 = "<< c5 <<'\n';
cout <<"Модуль c1: "<< c1.abs() <<"\n\n";
cout <<"c1 + c2 = "<< (c1 + c2);
cout <<"c1 - c3 = "<< (c1 - c3);
cout <<"c1 * c4 = "<< (c1 * c4);
cout <<"c1 / c5 = "<< (c1 / c5);
system("pause");
}
Задание №4
Листинг программы:
usingnamespace std;
classArray
{
int* mas, k;
void Add(int);
void Sub(int);
public:
Array() :k(0), mas(newint(0)) {};
Array(constArray&);
s<
}
s<
}
returns<<")";
}
istream&operator>>(istream&s, Array&p)
{
int tmp;
char c;
s>> c;
while (c != ')')
{
s>> tmp >> c;
p.Add(tmp);
}
returns;
}
int main()
{
Array a, b, c;
cout <<" Введите множество А: "<<"\n";
cin >> a;
cout << a <<"\n";
a -= 9;
cout <<"После вычитания из множества элемента 9: "<< a <<"\n";
cout <<" Введите множество B: "<<"\n";
cin >> b;
b += 7;
cout <<"После добавления в множествo элементa 7 : "<< b <<"\n";
cout <<" Пересечение множеств A и В: "<<"\n";
cout << a * b <<"\n";
cout <<"Количество элементов в множестве В: "<< b.HowMany() <<"\n";
if (a <= b)
cout <<"А - подмножество В \n";
else {
if (b <= a)
cout <<"B - подмножество A \n";
}
cout <<" Объединение множеств А и B: "<<"\n";
c = a;
a += b;
cout << a <<"\n";
cout <<" Разница множеств А и B: "<<"\n";
c -= b;
cout << c <<"\n";
return 1;
}
Задание№5
Листинг программы:
#defineARR 4
structst
{
char fam[80];
int age;
int gruppa;
int mas[ARR];
};
classStudent
{
vector
public:
Student() {};
Student() {};
void getData()
{
st student;
cout <<"/n Vvedite familiy: ";
cin >> student.fam;
cout <<" Vvedite gruppu: /n";
cin >> student.gruppa;
cout <<" Vvedite vozrast: /n";
cin >> student.age;
for (int i = 0; i
{
cout <<"Vvedite ocenku "<< i << endl;
cin >> student.mas[i];
}
students.push_back(student);
}
};
5.Ответы на контрольные вопросы
-
Главный недостаток структурного подхода заключается в следующем: процессы и данные существуют отдельно друг от друга (как в модели деятельности организации, так и в модели программной системы), причем проектирование ведется от процессов к данным. Таким образом, помимо функциональной декомпозиции, существует также структура данных, находящаяся на втором плане.
В объектно-ориентированном подходе основная категория объектной модели - класс - объединяет в себе на элементарном уровне как данные, так и операции, которые над ними выполняются (методы). Именно с этой точки зрения изменения, связанные с переходом от структурного к объектно-ориентированному подходу, являются наиболее заметными. Разделение процессов и данных преодолено, однако остается проблема преодоления сложности системы, которая решается путем использования механизма компонентов.
Плюсы ООП:
Объектная декомпозиция дает возможность создавать программные системы меньшего размера путем использования общих механизмов, обеспечивающих необходимую экономию выразительных средств.
Объектная декомпозиция уменьшает риск создания сложных систем ПО, так как она предполагает эволюционный путь развития системы на базе относительно небольших подсистем.
Объектная модель вполне естественна, поскольку в первую очередь ориентирована на человеческое восприятие мира, а не на компьютерную реализацию.
Объектная модель позволяет в полной мере использовать выразительные возможности объектных и объектно-ориентированных языков программирования.
К недостаткам объектно-ориентированного подхода относятся некоторое снижение производительности функционирования ПО и высокие начальные затраты. Объектная декомпозиция существенно отличается от функциональной, поэтому переход на новую технологию связан как с преодолением психологических трудностей, так и дополнительными финансовыми затратами. -
Инкапсуляция представляет собой механизм, который связывает вместе код и данные и который хранит их от внешнего воздействия и от неправильного использования. Более того, именно инкапсуляция позволяет создавать объекты. -
В С++ полиморфизм поддерживается как на этапе выполнения программы, так и на этапе ее компиляции. В качестве примера полиморфизма на этапе компиляции можно указать перегрузку операторов и функций. -
С помощью наследования можно создать общий класс, определяющий общие черты совокупности объектов. Этот класс может наследоваться другими более специфическими классами, каждый из которых может добавить свои элементы в описании объекта. -
Класс - это тип. Этот производный тип вводится в программу с помощью специального оператора объявления класса. В объявлении класса используется ранее описанный инструментальный набор средств для построения и преобразования производных типов.
Спецификатор класса представляет то, что называется объявлением класса. Уточнённый спецификатор типа объявляет расположенный за ним идентификатор именем класса. Уточнённый спецификатор обеспечивает неполное предварительное объявление класса и перечисления.
Спецификатор класса представляет то, что называется объявлением класса. Уточнённый спецификатор типа объявляет расположенный за ним идентификатор именем класса. Уточнённый спецификатор обеспечивает неполное предварительное объявление класса и перечисления. -
Конструктор — функция, предназначенная для инициализации объектов класса.
Нигде не утверждается, что объект должен быть инициализирован, и программист может забыть инициализировать его или сделать это дважды.
ООП дает возможность программисту описать функцию, явно предназначенную для инициализации объектов. Поскольку такая функция конструирует значения данного типа, она называется конструктором. -
Объекты могут быть переданы в функции тем же способом, что и переменные любого другого типа. Объекты передаются функциям с использованием стандартного механизма передачи по значению. Это означает, что создается копия объекта, которая и передается функции.
Когда функция возвращает объект, автоматически создается временный объект, содержащий возвращаемое значение. Именно этот объект фактически возвращается функцией. После того, как значение возвращено, этот объект уничтожается. -
Перегрузка процедур и функций — возможность использования одноимённых подпрограмм: процедур или функций в языках программированияВ большинстве ранних языков программирования для упрощения процесса трансляции существовало ограничение, согласно которому одновременно в программе не может быть доступно более одной процедуры с одним и тем же именем. В соответствии с этим ограничением все подпрограммы, видимые в данной точке программы, должны иметь различные имена. -
Перегрузка операторов в программировании — один из способов реализации полиморфизма, заключающийся в возможности одновременного существования в одной области видимости нескольких различных вариантов применения оператора, имеющих одно и то же имя, но различающихся типами параметров, к которым они применяются. Иногда возникает потребность описывать и применять к созданным программистом типам данных операции, по смыслу эквивалентные уже имеющимся в языке. -
Ключевое слово this представляет собой неявно определенный указатель на сам объект. С его помощью метод класса определяет, с данными какого объекта ему предстоит работать -
Функция перегрузки operator= возвращает скрытый указатель *this (т.е. текущий объект) и мы даже можем связать выполнение нескольких операций присваивания вместе
6.Вывод по проделанной работе
Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев