Дисциплина: Объектно-ориентированное программирование
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
| «Московский государственный технический университет имени Н.Э. Баумана» (МГТУ им. Н.Э. Баумана) |
ФАКУЛЬТЕТ Информатика и системы управления
КАФЕДРА Компьютерные системы и сети
Отчет
по домашней работе 2.1
Дисциплина: Объектно-ориентированное программирование
Название домашней работы: Функции
Студент гр. ИУ6-22 __________________ М.Ю. Чуриков
(Подпись, дата) (И.О. Фамилия)
Преподаватель __________________ __________________
(Подпись, дата) (И.О. Фамилия)
Москва, 2016
Часть 2.1. Функции.
Дан упорядоченный по неубыванию значений элементов массив целых чисел a, натуральное k и некоторое целое число b. Написать программу, осуществляющую удаление из массива a элемента с номером k и вставляющую элемент, равный b, в массив a так, чтобы упорядоченность его не нарушилась. Для поиска места воспользоваться алгоритмом дихотомического поиска. При программировании использовать функцию. Вывести на печать исходный и сформированный массив.
Текст программы:
#include "stdafx.h"
#include <iostream>
#include <locale.h>
#include <cstring>
#include <conio.h>
using namespace std;
struct el
{
int value;
el *next = NULL;
el *prev = NULL;
};
el* GetAtIndex(el* first, int index)
{
int idx = 0;
for (el* it = first; it != NULL; it = it->next)
{
if (idx == index)
{
return it;
}
idx++;
}
return NULL;
}
el* GetLast(el* first)
{
el* last = first;
for (el* it = first; it != NULL; it = it->next)
{
last = it;
}
return last;
}
void AddAfterElem(el* addAfter, int value)
{
el* next = addAfter->next;
el* p = new el();
p->prev = addAfter;
p->next = addAfter->next;
p->value = value;
if (addAfter->next != NULL)
addAfter->next->prev = p;
addAfter->next = p;
}
el* RemElem(el* first, int index)
{
int idx = 0;
el* prev = NULL;
for (el* it = first; it != NULL; it = it->next)
{
if (idx == index)
{
if (it == first)
{
el* del = first;
first = it->next;
if (first != NULL)
first->prev = NULL;
delete del;
}
else
{
prev->next = it->next;
if (it->next != NULL)
it->next->prev = prev;
}
break;
}
idx++;
prev = it;
}
return first;
}
el* AddElem(el* first, int value)
{
el* p = NULL;
el* last = GetLast(first);
p = new el;
p->value = value;
if (first == NULL)
first = p;
else
{
last->next = p;
p->prev = last;
}
return first;
}
el* listFirst = NULL;
int CountElems(el* first, el* last)
{
int count = 0;
for (el* it = first; it != last; it = it->next)
count++;
if (last != first && last && last != first->next)
count++;
return count;
}
el* AddToSorted(el* first, int count, int value)
{
// insert to start
if (first->value >= value)
{
el* p = new el();
p->next = first;
first->prev = p;
if (first == listFirst)
{
listFirst = p;
}
p->value = value;
return p;
}
el* last = GetAtIndex(first, count-1);
int len = CountElems(first, last);
if (value >= first->value && value <= last->value && count >= 2)
{
el* e1 = NULL;
// get mid, check for left & right parts
el* mid = GetAtIndex(first, count / 2);
if (value >= first->value && value <= mid->value)
e1 = AddToSorted(first, CountElems(first, mid), value);
else
e1 = AddToSorted(mid, CountElems(mid, last), value);
return e1;
}
// insert to end
if (value >= last->value)
{
AddAfterElem(last, value);
return listFirst;
}
return NULL;
}
void PrintArr(el* first)
{
for (el* it = first; it != NULL; it = it->next)
{
printf(" %d", it->value);
}
printf("\n");
}
int main(int argc, const char * argv[])
{
el* first = NULL;
first = AddElem(first, 1);
first = AddElem(first, 2);
first = AddElem(first, 3);
first = AddElem(first, 4);
first = AddElem(first, 5);
first = AddElem(first, 6);
first = AddElem(first, 7);
first = AddElem(first, 8);
first = AddElem(first, 9);
first = AddElem(first, 10);
first = AddElem(first, 11);
PrintArr(first);
int k = 0;
printf("\nEnter k: ");
scanf("%d", &k);
int count = CountElems(first, GetLast(first));
if (k < 0 || k > count)
printf("\nNo such element!");
else
{
first = RemElem(first, k-1);
PrintArr(first);
}
int b = 0;
printf("\nEnter b: ");
scanf("%d", &b);
el* last = GetLast(first);
count = CountElems(first, GetLast(first));
listFirst = first;
AddToSorted(first, count, b);
first = listFirst;
PrintArr(first);
_getch();
return 0;
}
Скриншоты:
Вывод: Научился использовать дихотомический поиск при работе с функциями в Microsoft Visual Studio 2008 на языке C++.
Блок-схема: