Содержание:
Информация для всех студентов, а особенно для студентов САФУ
Здравствуйте! Мы - команда из $3$-х программистов, которые оказывают квалифицированную помощь студентам со всех уголков России, Украины, Белоруссии, Казахстана, в написании лабораторных, курсовых и дипломных работ по программированию.
Также к нам постоянно обращаются студенты за помощью, когда требуется выполнить задание, связанное с программированием высшей математики или проектированием баз данных.
Вам знакома обложка этого учебно-методического пособия? Если, да, то вы обратились точно по адресу! В данном материале вы найдете образцы выполнения заданий из всех лабораторных работ.
Т к я являюсь репетитором по информатике и программированию, то на постоянной основе готовлю студентов технических вузов к сдаче экзаменов, помогаю в реализации лабораторных практикумов.
Кстати, если хотите научиться безошибочно выполнять вузовские лабораторные работы по программированию, а также на достойном уровне выучить язык "чистый" Си или C++, то записывайтесь ко мне на индивидуальную подготовку. Мой контактный №тел.: $8\ (926)\ 610 - 61 - 95$.
Не спеша ознакомьтесь с информацией, представленной на данной веб-странице. Найдете очень много полезного для себя, а также параллельно решите все проблемы с программированием, которые у вас возникли в вузе.
Для навигации по лабораторным работам используйте ссылочное меню в верхней части данной веб-страницы.
Также стоит учитывать тот факт, что издание могло переиздаваться. Следовательно, своего варианта, возможно, вы не сможете обнаружить в перечне заданий. В этом случае обязательно пишите нам на почту: administrator@videoege.ru. Поддержка оказывается круглосуточно!
Мы поможем вам решить любые проблемы, связанные с программированием и программированием высшей математики. Поэтому смело обращайтесь к нам за оперативной помощью.
Нужна ли регистрация на сайте для заказа лабораторной работы?
Нет, для заказа требуемой вам лабораторной работы не нужна никакая регистрация на сайте! Все, что вам необходимо - написать на наш электронный адрес: administrator@videoege.ru.
Мы готовы оказать вам любую информационную поддержку круглосуточно.
Лабораторная работа №1
Работа со списком
Краткая постановка задачи:
|
Необходимо написать модуль, содержащий решения $16$ задач для работы со списком, и программу, демонстрирующую работу этого модуля. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя. При необходимости следует использовать вспомогательные функции. В разработанном модуле не должны применяться интерфейсные функции (исключение возможно только для функций ввода элементов и вывода списка). |
Я (Александр Георгиевич) полностью разработал решение данной задачи для всех студентов, изучающих данную тему. Программа реализована в среде MS Visual Studio на языке программирования C++ (консольный проект). За $1\ 000$ рублей могу перевести данную программу с консольного варианта на визуальный формат(формы с различными визуальными элементами управления).
В коде я учел все пожелания и требования к данной задаче, выдвигаемые составителями. Соблюдены названия переменных, порядок выполнения операторов и пр.нюансы.
Хочется отметить лишь одну весомую неточность, допущенную составителем: в пункте $№17$ требуется отсортировать линейный список устойчивым алгоритмом сортировки, и предлагается воспользоваться сортировкой выбором. Дело в том, что данная сортировка является как раз-таки неустойчивой! Поэтому я выбрал для сортировки списка оптимальную сортировку пузырьком (сортировку обменом), которая является устойчивой.
| Напомню, что под устойчивой сортировкой понимают такую сортировку, которая не меняет взаимного расположения элементов с одинаковыми ключами. |
В итоге получилась программа, состоящая из $500+$ строк кода. Для студенческой лабораторной работы данный объем является немалым. Программа снабжена колоссальным количеством подсказок, различных информативных сообщений, помогающих пользователю ориенитроваться в ходе выполнения программы.
Список пользовательских функций, закодированных в программе:
| № | Название функции | Назначение функции |
| 1. | int Menu(void) | Главное меню программы. |
| 2. | int InputIntValue(void) | Ввод значения информационного поля элемента вводом с клавиатуры. |
| 3. | list* CreateElement(int pinf) | Создание нового элемента с заданным значением информационного поля. |
| 4. | void AddElementBeginList(list** pfirst, const int pinf) | Добавление элемента в начало линейного списка. |
| 5. | void AddElementEndList(list** pfirst, const int pinf) | Добавление элемента в конец линейного списка. |
| 6. | void AddElementBeforeTarget(list* pfirst, const int pinf, const int pnumber) | Добавление элемента перед заданным по номеру элементом списка. |
| 7. | void AddElementAfterTarget(list* pfirst, const int pinf, const int pnumber) | Добавление элемента после заданного по номеру элемента списка. |
| 8. | void DeleteElementBeginList(list** pfirst) | Удаление элемента из начала односвязного списка. |
| 9. | void DeleteElementEndList(list* pfirst) | Удаление элемента из конца односвязного списка. |
| 10. | void DeleteTargerElementByNumber(list* pfirst, const int pnumber) | Удаление заданного по номеру элемента списка. |
| 11. | void ClearList(list** pfirst) | Удаление всех элементов списка (очистка списка). |
| 12. | void PrintList(const list* pfirst) | Вывод элементов линейного списка на экран пользователя. |
| 13. | list* GetElement(list* pfirst, const int pnumber) | Получение заданного по номеру элемента списка для анализа. |
| 14. | int GetCountElementsList(const list* pfirst) | Получение количества элементов односвязного списка. |
| 15. | bool IsExistElement(list* pfirst, const int pinf) | Поиск образца (заданного элемента) по значению в списке. |
| 16. | list* CopyList(list* pfirst) | Формирование полной/глубокой копии линейного списка. |
| 17. | void SplitList(list* pfirst) | Расщепление линейного списка на $2$ подсписка по критерию четность/нечетность значений элементов. |
| 18. | void BubbleSortList(list* pfirst) | Сортировка списка методом пузырька (обменом). |
| 19. | int main(void) | Главная функция всей программы (точка входа). |
Реализация задачи на языке C++:
[start lines=10]
#include <locale.h> // для руссификации диалогов (setlocale)
#include <iomanip> // для форматированного вывода (setw)
using namespace std; // быстрое обращение к функция из стандартного пространства имен
//--------------------------------------------------------------------------
// структура "Элемент списка"
//--------------------------------------------------------------------------
struct list
{
int inf; // информационное поле элемента
list* next; // ссылочное поле на следующий элемент списка
};
//--------------------------------------------------------------------------
// главное меню программы
//--------------------------------------------------------------------------
int Menu(void)
{
int select;
do
{
system("CLS");
cout << "1 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА В НАЧАЛО СПИСКА" << endl;
cout << "2 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА В КОНЕЦ СПИСКА" << endl;
cout << "3 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА ПЕРЕД ЗАДАННЫМ ЭЛЕМЕНТОМ" << endl;
cout << "4 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА ПОСЛЕ ЗАДАННОГО ЭЛЕМЕНТА" << endl;
cout << "5 - УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ НАЧАЛА СПИСКА" << endl;
cout << "6 - УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ КОНЦА СПИСКА" << endl;
cout << "7 - УДАЛЕНИЕ ЗАДАННОГО ЭЛЕМЕНТА (ПО НОМЕРУ)" << endl;
cout << "8 - УДАЛЕНИЕ ВСЕГО СПИСКА" << endl;
cout << "9 - ВЫВОД ЭЛЕМЕНТОВ СПИСКА НА ЭКРАН" << endl;
cout << "10 - ПОДСЧЕТ КОЛИЧЕСТВА ЭЛЕМЕНТОВ СПИСКА" << endl;
cout << "11 - ПОЛУЧЕНИЕ ЗАДАННОГО УЗЛА СПИСКА ДЛЯ АНАЛИЗА" << endl;
cout << "12 - ПОИСК ОБРАЗЦА" << endl;
cout << "13 - СОЗДАНИЕ КОПИИ СПИСКА" << endl;
cout << "14 - РАЗДЕЛЕНИЕ СПИСКА НА ДВА ПОДСПИСКА (ЧЕТ/НЕЧЕТ)" << endl;
cout << "15 - СОРТИРОВКА СПИСКА МЕТОДОМ ОБМЕНА (ПУЗЫРЬКОВАЯ)" << endl;
cout << "16 - ВЫХОД" << endl;
cout << "Выбор: ";
cin >> select;
}
while((select < 1) || (select > 16));
return select;
}
//--------------------------------------------------------------------------
// ввод значения информационного поля элемента вводом с клавиатуры
//--------------------------------------------------------------------------
int InputIntValue(void)
{
int value;
cout << endl << "Введите значение элемента (целое число): ";
cin >> value;
return value;
}
//--------------------------------------------------------------------------
// создание элемента с заданным значением
//--------------------------------------------------------------------------
list* CreateElement(int pinf)
{
list* add = new list;
add->inf = pinf;
add->next = NULL;
return add;
}
//--------------------------------------------------------------------------
// добавление элемента в начало списка
//--------------------------------------------------------------------------
void AddElementBeginList(list** pfirst, const int pinf)
{
list* add = CreateElement(pinf);
add->next = *pfirst;
*pfirst = add;
}
//--------------------------------------------------------------------------
// добавление элемента в конец списка
//--------------------------------------------------------------------------
void AddElementEndList(list** pfirst, const int pinf)
{
list* add = CreateElement(pinf);
if(*pfirst == NULL)
*pfirst = add;
else
{
list* p = *pfirst;
while(p->next != NULL)
p = p->next;
p->next = add;
}
}
//--------------------------------------------------------------------------
// добавление элемента перед заданным элементом
//--------------------------------------------------------------------------
void AddElementBeforeTarget(list* pfirst, const int pinf, const int pnumber)
{
list* p = pfirst;
for(int i = 1; i < (pnumber - 1); i++)
p = p->next;
list* add = CreateElement(pinf);
add->next = p->next;
p->next = add;
}
//--------------------------------------------------------------------------
// добавление элемента после заданного элемента
//--------------------------------------------------------------------------
void AddElementAfterTarget(list* pfirst, const int pinf, const int pnumber)
{
list* p = pfirst;
for(int i = 1; i < pnumber; i++)
p = p->next;
list* add = CreateElement(pinf);
add->next = p->next;
p->next = add;
}
//--------------------------------------------------------------------------
// удаление элемента из начала списка
//--------------------------------------------------------------------------
void DeleteElementBeginList(list** pfirst)
{
list* p = *pfirst;
*pfirst = p->next;
delete p;
p = NULL;
}
//--------------------------------------------------------------------------
// удаление элемента из конца списка
//--------------------------------------------------------------------------
void DeleteElementEndList(list* pfirst)
{
list* p = pfirst;
while(p->next->next != NULL)
p = p->next;
delete p->next;
p->next = NULL;
}
//--------------------------------------------------------------------------
// удаление заданного элемента по номеру
//--------------------------------------------------------------------------
void DeleteTargerElementByNumber(list* pfirst, const int pnumber)
{
list* p = pfirst;
for(int i = 1; i < (pnumber - 1); i++)
p = p->next;
list* del = p->next;
p->next = del->next;
delete del;
del = NULL;
}
//--------------------------------------------------------------------------
// удаление всего списка
//--------------------------------------------------------------------------
void ClearList(list** pfirst)
{
list* p = *pfirst;
while(*pfirst != NULL)
{
*pfirst = p->next;
delete p;
p = *pfirst;
}
*pfirst = NULL;
}
//--------------------------------------------------------------------------
// вывод элементов списка на экран
//--------------------------------------------------------------------------
void PrintList(const list* pfirst)
{
cout << endl << "Элементы списка имеют вид: ";
while(pfirst)
{
cout << setw(8) << pfirst->inf;
pfirst = pfirst->next;
}
}
//--------------------------------------------------------------------------
// получение заданного узла списка для анализа
//--------------------------------------------------------------------------
list* GetElement(list* pfirst, const int pnumber)
{
list* p = pfirst;
for(int i = 1; i < pnumber; i++)
p = p->next;
return p;
}
//--------------------------------------------------------------------------
// подсчет количества элементов списка
//--------------------------------------------------------------------------
int GetCountElementsList(const list* pfirst)
{
int count = 0;
while(pfirst)
{
count++;
pfirst = pfirst->next;
}
return count;
}
//--------------------------------------------------------------------------
// поиск образца (по значению)
//--------------------------------------------------------------------------
bool IsExistElement(list* pfirst, const int pinf)
{
list*p = pfirst;
while(p != NULL)
{
if(p->inf == pinf)
return true;
p = p->next;
}
return false;
}
//--------------------------------------------------------------------------
// получение копии списка
//--------------------------------------------------------------------------
list* CopyList(list* pfirst)
{
list* newlist = NULL;
while(pfirst != NULL)
{
AddElementEndList(&newlist, pfirst->inf);
pfirst = pfirst->next;
}
return newlist;
}
//--------------------------------------------------------------------------
// разделение списка на 2 подсписка по четности/нечетности
//--------------------------------------------------------------------------
void SplitList(list* pfirst)
{
list* chet = NULL;
list* nechet = NULL;
while(pfirst != NULL)
{
if(pfirst->inf % 2 == 0)
AddElementEndList(&chet, pfirst->inf);
else
AddElementEndList(&nechet, pfirst->inf);
pfirst = pfirst->next;
}
cout << endl << "Список расщеплен на два подсписка по критерию четности/нечетности" << endl;
PrintList(chet);
PrintList(nechet);
ClearList(&chet);
ClearList(&nechet);
cout << endl << "Память из-под полученных временных подсписков успешно удалена.";
}
//--------------------------------------------------------------------------
// сортировка списка по возрастанию ключей (методом обмена)
//--------------------------------------------------------------------------
void BubbleSortList(list* pfirst)
{
list* p = pfirst;
while(pfirst->next != NULL)
{
list* sort = p;
bool isSort = true;
while(sort->next != NULL)
{
if(sort->inf > sort->next->inf)
{
int swap = sort->inf;
sort->inf = sort->next->inf;
sort->next->inf = swap;
isSort = false; // сортировка еще не закончена
}
sort = sort->next;
}
if(isSort == true) // элементы УЖЕ упорядочены, поэтому дальше сортировать смысла нет
break;
pfirst = pfirst->next;
}
}
//--------------------------------------------------------------------------
// главная функция программы (точка входа)
//--------------------------------------------------------------------------
int main(void)
{
setlocale(LC_ALL, "rus");
list* first = NULL; // указатель на начало списка (на 1-ый элемент списка)
int select;
do
{
select = Menu();
switch (select)
{
case 1: // добавление элемента в начало списка
{
AddElementBeginList(&first, InputIntValue());
cout << "Элемент успешно добавлен в начало списка.";
break;
}
case 2: // добавление элемента в конец списка
{
AddElementEndList(&first, InputIntValue());
cout << "Элемент успешно добавлен в конец списка.";
break;
}
case 3: // добавление элемента перед заданным элементов
{
int count = GetCountElementsList(first);
if(count == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Вставка перед заданным элементом невозможна.";
else
{
PrintList(first);
int number;
cout << endl << "Введите номер элемента, перед которым требуется вставить новый элемент (нумерация с 1): ";
cin >> number;
if((number < 1) || (number > count))
cout << "Элемента с введенным номером не существует! Вставка невозможна.";
else
{
if(number == 1) // равносильно вставке в начало списка
AddElementBeginList(&first, InputIntValue());
else
AddElementBeforeTarget(first, InputIntValue(), number);
cout << "Элемент успешно добавлен перед заданным элементом.";
}
}
break;
}
case 4: // добавление элемента после заданного элемента
{
int count = GetCountElementsList(first);
if(count == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Вставка после заданного элемента невозможна.";
else
{
PrintList(first);
int number;
cout << endl << "Введите номер элемента, после которого требуется вставить новый элемент (нумерация с 1): ";
cin >> number;
if((number < 1) || (number > count))
cout << "Элемента с введенным номером не существует! Вставка невозможна.";
else
{
if(number == count) // равносильно вставке в конец списка
AddElementEndList(&first, InputIntValue());
else
AddElementAfterTarget(first, InputIntValue(), number);
cout << "Элемент успешно добавлен после заданного элемента.";
}
}
break;
}
case 5: // удаление элемента из начала списка
{
if(GetCountElementsList(first) == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Удаление элемента из начала списка невозможно.";
else
{
PrintList(first);
DeleteElementBeginList(&first);
PrintList(first);
cout << endl << "Элемент успешно удален из начала списка.";
}
break;
}
case 6: // удаление элемента из конца списка
{
int count = GetCountElementsList(first);
if(count == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Удаление элемента из конца списка невозможно.";
else
{
PrintList(first);
if(count == 1) // удаляется единственный элемент
DeleteElementBeginList(&first);
else
DeleteElementEndList(first);
PrintList(first);
cout << endl << "Элемент успешно удален из конца списка.";
}
break;
}
case 7: // удаление заданного элемента (по номеру)
{
int count = GetCountElementsList(first);
if(count == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Удаление заданного элемента невозможно.";
else
{
PrintList(first);
int number;
cout << endl << "Введите номер элемента, который требуется удалить (нумерация с 1): ";
cin >> number;
if((number < 1) || (number > count))
cout << "Элемента с введенным номером не существует! Удаление невозможно.";
else
{
if(number == 1) // равносильно удалению из начала списка
DeleteElementBeginList(&first);
else
if(number == count) // равносильно удалению из конца списка
DeleteElementEndList(first);
else
DeleteTargerElementByNumber(first, number); // удаляется срединный элемент
PrintList(first);
cout << endl << "Заданный элемент успешно удален из списка.";
}
}
break;
}
case 8: // удаление всего списка
{
ClearList(&first);
cout << endl << "Список успешно очищен от элементов (список стал пустым).";
break;
}
case 9: // вывод на экран элементов списка
{
if(GetCountElementsList(first) == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Печать невозможна.";
else
PrintList(first);
break;
}
case 10: // подсчет кол-ва элементов в списке
{
cout << endl << "На данный момент в списке находится элементов: " << GetCountElementsList(first) << " шт.";
break;
}
case 11: // получение заданного узла списка
{
int count = GetCountElementsList(first);
if(count == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Получение заданного элемента для анализа невозможно.";
else
{
PrintList(first);
int number;
cout << endl << "Введите номер элемента, к которому требуется получить доступ (нумерация с 1): ";
cin >> number;
if((number < 1) || (number > count))
cout << "Элемента с введенным номером не существует! Доступ получить невозможно.";
else
{
list* p = GetElement(first, number);
cout << endl << "Значение заданного элемента: " << p->inf << endl;
cout << "Значение следующего элемента: ";
if(p->next == NULL)
cout << "NULL" << endl;
else
cout << p->next->inf << endl;
cout << "Адрес заданного элемента: " << hex << p << endl;
cout << endl << "Анализ успешно завершен.";
}
}
break;
}
case 12: // поиск образца
{
if(GetCountElementsList(first) == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Поиск образца невозможен.";
else
{
PrintList(first);
int inf;
cout << endl << "Введите значение элемента для поиска: ";
cin >> inf;
if(IsExistElement(first, inf) == true)
cout << "Элемент с заданным ключом присутствует в списке.";
else
cout << "Элемент с заданным ключом отсутствует в списке.";
}
break;
}
case 13: // получение копии списка
{
if(GetCountElementsList(first) == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Получение копии списка невозможно.";
else
{
list* newlist = CopyList(first);
cout << endl << "Копия списка успешно проведена!";
PrintList(newlist);
ClearList(&newlist);
cout << endl << "Элементы копии списка удалены из памяти.";
}
break;
}
case 14: // разделение списка по критерию четности/нечетности ключей
{
if(GetCountElementsList(first) == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Расщепление списка на 2 подсписка невозможно.";
else
{
PrintList(first);
SplitList(first);
}
break;
}
case 15: // сортировка списка методом обмена
{
if(GetCountElementsList(first) == 0)
cout << endl << "В списке нет ни одного элемента (список пуст)! Сортировка списка невозможна.";
else
{
PrintList(first);
BubbleSortList(first);
cout << endl << "Сортировка списка по возрастанию ключей методом оптимальной сортировки обменом произведена успешно!" << endl;
PrintList(first);
}
break;
}
}
if(select != 16)
{
fflush(stdin);
cin.get();
}
}
while(select != 16);
// незабываем удалить память из-под списка при закрытии программы
ClearList(&first);
return 0; // завершение работы программы и передача управления в ОС
}
//--------------------------------------------------------------------------
Результаты работы программы:
| № | Смысл операции | Результат |
| 1. | Попытка поиска элемента (на данный момент список пуст). |  |
| 2. | Добавление элемента со значением $15$ в начало списка. |  |
| 3. | Добавление элемента со значением $-17$ в конец списка. |  |
| 4. | Добавим элементы со значеним $5$, $120$ в начало списка, а затем $13$, $-6$, $23$ в конец списка и распечатаем элементы списка на экран. |  |
| 5. | Удалим элемент, стоящий на $3$-й позиции (нумерация элементов с $1$). |  |
| 6. | Попробуем удалить элемент, задав некорректный номер элемента. |  |
| 7. | Удалим последний элемент списка. |  |
| 8. | Удалим первый элемент списка. |  |
| 9. | Добавим элемент перед заданным по номеру элементом. |  |
| 10. | Распечатаем элементы списка на экран. |  |
| 11. | Расщепим данный список на $2$ подсписка. |  |
| 12. | Попробуем найти элемент в списке со значением $13$. |  |
| 13. | Добавим элемент после заданного элемента по номеру. |  |
| 14. | Попробуем найти элемент по его номеру для проведения анализа. |  |
| 15. | Получим копию данного списка. |  |
| 16. | Запросим количество элементов списка. |  |
| 17. | Отсортируем список пузырьковой сортировкой по возрастанию ключей элементов списка. |  |
| 18. | Удалим все элементы из списка. |  |
| 19. | Попробуем распечатать пустой список на экран. |  |
Повторю, стоимость заказа решения данной задачи в визуальном формате (с формами и визуальными элементами управления) составляет $1\ 000$ рублей.
Варианты индивидуальных заданий
Задание для всех вариантов звучит так (или, возможно, немного изменено, т к могут быть разные издания учебного пособия).
|
Для всех вариантов необходимо написать программу для решения задачи. Для хранения данных применять линейный список; для хранения даты и времени использовать тип данных time_t; исходные данные брать из текстового файла с именем "test.txt". Файл сдается вместе с работой и должен содержать не менее $10$ записей. В начале работы программы данные загружаются в список, а пользователю предлагается меню в случае командно-текстового интерфейса или же графический интерфейс. Обязательно должно быть реализовано выполнение следующих функций:
Для решения задач обязательно использовать функции. Все необходимые данные для функций должны передаваться им в качестве параметров. Использование глобальных переменных в функциях не допускается. |
ВАЖНО!
Стоимость программы (командно-текстовый интерфейс) из любого варианта составляет $500$ рублей.
Стоимость программы (визуальный интерфейс) из любого варианта составляет $1\ 000$ рублей.
Варианты заданий:
| № вар. | Формулировка |
| 1. | Счет в банке представляет собой структуру с полями: номер счета, код счета, фамилия владельца, сумма на счете, дата открытия счета, годовой процент начисления. Реализовать поиск и сортировку по номеру счета, дате его открытия и фамилии владельца. |
| 2. | Запись о товаре на складе представляет собой структуру с полями: номер склада, код товара, наименование товара, дата поступления на склад, срок хранения в днях, количество единиц товара, цена за единицу товара. Поиск и сортировка - по номеру склада, наименованию товара. Вывести список просроченных товаров (поиск всех товаров, у которых на текущую дату истек срок хранения). |
| 3. | Запись о преподаваемой дисциплине представляется структурой: код дисциплины в учебном плане, наименование дисциплины, фамилия преподавателя, код группы, количество студентов в группе, количество часов лекций, количество часов практических занятий, вид итогового контроля (зачет или экзамен), дата начала занятий. Поиск и сортирвока - по фамилии преподавателя, количеству часов, дате начала занятий. |
| 4. | Информационная запись о книге, выданной на руки абоненту, представляет собой структуру следующего вида: номер читательского билета, фамилия абонента, дата выдачи, количество дней, автор, название, год издания, цена. Поиск и сортировка - по номеру читательского билета, автору книги. Вывести список все просроченных книг (поиск всех книг, которые на текущую дату должны быть сданы). |
| 5. | Информационная запись о файле содержит следующие поля: каталог, имя файла, расширение, дата и время создания, атрибуты "только для чтения", "скрытый", "системный", количество выделенных секторов (размер секотора принять равным $512$ байтам). Поиск и сортировка - по каталогу, дате создания файла. Выяснить, поместится ли файл на носитель с некоторым количеством секторов. |
| 6. | Разовый платеж за телефонный разговор является структурой с полями: фамилия плательщика, номер телефона, дата разговора, тариф за минуту разговора, время начала разговора, время окончания разговора. Поиск и сортировка - по фамилии плательщика, дате разговора. Найти все разговоры со временем разговора больше заданного. |
| 7. | Модель компьютера характеризуются кодом и маркой компьютера, типом процессора (может содержать цифры и буквы), частотой работы процессора, объемом оперативной памяти, объемом жесткого диска, датой выпуска на рынок, стоимостью компьютера в рублях и количеством экзмепляров, имеющихся в наличии. Поиск и сортировка - по типу процессора, объему ОЗУ, дате выпуска компьютера на рынок. |
| 8. | Список абонентов сети кабельного телевидения состоит из элементов следующей структуры: фамилия, район, адрес, телефон, номер договора, дата заключения договора, оплата установки, дата последнего платежа. Поиск и сортировка - по району, номеру договора, дате последнего платежа. |
| 9. | Сотрудник представлен структурой Person с полями: табельный номер, номер отдела, фамилия, оклад, дата поступления на работу, процент надбавки, процент налоговых сборов, количество отработанных дней в месяце, количество рабочих дней в месяце, начислено, удержано. Поиск и сортировка - по номеру отдела, дате поступления на работу, фамилии. |
| 10. | Запись о багаже пассажира авиарейса содержит следующие поля: номер рейса, дата и время вылета, пункт назначения, фамилия пассажира, количество мест багажа, суммарный вес багажа. Поиск и сортировка - по дате вылета, пункту назначения. Найти всех пассажиров, у которых масса багажа выше максимально допустимой. |
| 11. | Учетная запись посещения спорткомплекса имеет структуру: фамилия клиента, код и вид спортивного занятия, фамилия тренера, дата и время начала тренировки, количество минут, тариф. Поиск и сортировка - по фамилии клиента, дате начала и количеству минут тренировки (больше или меньше введенного). |
| 12. | Одна запись о медикаменте содержит следующие поля: номер аптеки, название лекарства, количество упаковок, имеющиеся в наличии в данной аптеке, стоимость одной упаковки, дата поступления в аптеку, срок хранения (в днях). Поиск и сортировка - по номеру аптеки, наименованию препарата, дате поступления. |
| 13. | Одна запись журнала учета содержит поля: код игрушки, название игрушки, тип игрушки, возрастные ограничения (например, от 6 лет), цена за единицу, количество в наличии, дата поступления в магазин, поставщик. Поиск и сортировка - по дате поступления, поставщику, возрастным ограничениям. |
| 14. | Один элемент (автомобиль) представляет собой структуру с полями: фамилия владельца, марка автомобиля, требуемая марка бензина, мощность двигателя, объем бака, остаток бензина, объем масла, дата техосмотра. Дана фиксированная цена литра бензина и заливки масла. Поиск и сортировка - по марке автомобиля, мощности двигателя, дате техосмотра. |
| 15. | Запись в журнале зимней экзаменационной сессии представляет собой структуру с полями: курс, код группы, фамилия студента, дата поступления, номер зачетной книжки, дисциплина, оценка за экзамен по дисциплине. Поиск и сортировка - по номеру курса, номеру зачетной книжки, дате поступления. |
| 16. | Структура одной записи оплаты за коммунальные услуги содержит поля: номер дома, номер квартиры, фамилия владельца, вид платежа (квартплата, газ, вода, электричество), дата платежа, сумма платежа, процент пени, на сколько дней просрочен платеж. Поиск и сортировка - по номеру дома, виду платежа, дате платежа. |
| 17. | Одна запись счета за ремонтные работы содержит поля: название фирмы, вид работ, единица измерения, стоимость единицы выполненных работ, дата исполнения, количество выполненных работ. Поиск и сортировка - по названию фирмы, виду работ, дате исполнения. |
| 18. | Одна учетная запись журнала стоянки автомобилей имеет структуру: номер автомобиля, фамилия владельца, дата и время начала, дата и время окончания, тариф за час. Поиск и сортировка - по номеру автомобиля, дате начала стоянки, фамилии владельца. |
| 19. | Структура записи о сельскохозяйственном продукте содержит поля: наименование района (где выращивают), наименование продукта, площадь (га), урожайность (кг/га), цена за $1$ кг, потери при транспортировке (%), стоимость продукта, предполагаемая дата сбора. Поиск и сортировка - по наименованию района, урожайности, предполагаемой дате сбора. |
| 20. | В туристической фирме учетная запись о проданном туре содержит следующие поля: наименование тура, фамилия клиента, цена одного дня (в рублях), дата заезда, количество дней, стоимость проезда, курс валюты, количество валюты, стоимость проезда. Поиск и сортировка - по наименованию тура, стоимости проезда, дате заезда. |
| 21. | Сотовый телефон характеризуется названием производителя, номером модели (может содержать цифры и буквы), временем работы аккумулятора, наличием и максимальной емкостью карты памяти, датой выпуска на рынок, стоимостью в рублях и количеством экземпляров, имеющихся в наличии. Поиск и сортировка - по номеру модели, объему памяти на карте, дате выпуска на рынок. |
| 22. | Одна запись о предемете мебели содержит следующие поля: артикул (может содержать цифры и буквы), наименование, цвет, стоимость, дата изготовления, количество имеющихся в наличии экземпляров. Поиск и сортировка - по артикулу, количеству экземпляров, дате изготовления. |
Лабораторная работа $№1$ предполагает написание программы на языке C++. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Лабораторная работа №2
Задание для всех вариантов звучит так (или, возможно, немного изменено, т к могут быть разные издания учебного пособия).
|
Необходимо написать три модуля, в совокупности содержащие решения десяти задач для работы со стеками, очередями, деками, и программу, демонстрирующую работу этих модулей. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя. Все задачи выполнять через функции, при необходимости можно использовать вспомогательные функции. В разработанных модулях не должны применяться интерфейсные функции, весь интерфейс реализуется демонстрационной программой. В качестве данных, если не сказано иначе, брать последовательность случайных целых чисел (положительных и отрицательных). Желательно также предусмотреть ввод элементов списка с клавиатуры. |
Для студентов мы бесплатно закодировали модуль работы со стеком и программу, демонстрирующую работу этого модуля. Разработка велась в среде MS Visual Studio в виде консольного приложения с помощью языка программирования C++.
ВАЖНО!
Стоимость заказа программ:
| № | Структура данных | Консольный формат | Визуальный формат |
| 1. | Стек | Бесплатно (см.реализацию ниже) | $750$ рублей |
| 2. | Очередь | $500$ рублей | $750$ рублей |
| 3. | Дек | $500$ рублей | $750$ рублей |
|
Стек (stack) - динамическая структура данных, в которой все включения, исключения и доступ производятся только с одного конца по принципу LIFO (от англ. "Last In - First Out" - последним пришел, первым ушел). Стеки широко применяются в программировании для: передачи параметров в функции, трансляции, реализации рекурсии, реализации управления динамической памятью и др. Принцип работы стека легко понять на примере стопки тарелок: чтобы взять вторую тарелку сверху, нужно снять самую верхнюю. Список задач по моделированию стека:
|
В результате кодирования данной задачи получился проект, состоящий из $3$ файлов:
stack.h - пользовательские описания (типы данных и прототипы функций).
stack.cpp - модуль для работы со стеком.
source.cpp - программа, демонстрирующая работу модуля stack.cpp.
Содержимое файла stack.h:
// структура "Элемент стека"
//--------------------------------------------------------------------------
struct TElem
{
int inf; // информационное поле
TElem* next; // связующее поле
};
//--------------------------------------------------------------------------
TElem* CreateElement(const int pinf); // создание элемента с заданным значением
TElem* Push(TElem* ptop, const int pinf); // добавление элемента в вершину стека
int Pop(TElem** ptop); // удаление элемента из вершины стека
void Reverse(TElem** ptop); // реверсирование (переворачивание) стека
void Print(TElem** ptop); // вывод элементов стека на экран (двойное переворачивание)
void Clear(TElem** ptop); // очистка стека (удаление всех элементов)
Содержимое файла stack.cpp:
[start lines=10]
#include "stack.h"
using namespace std;
//--------------------------------------------------------------------------
// создание элемента с заданным значением
//--------------------------------------------------------------------------
TElem* CreateElement(const int pinf)
{
TElem* add = new TElem;
add->inf = pinf;
add->next = NULL;
return add;
}
//--------------------------------------------------------------------------
// добавление элемента в вершину стека
TElem* Push(TElem* ptop, const int pinf)
{
TElem* add = CreateElement(pinf);
add->next = ptop;
ptop = add;
return ptop;
}
//--------------------------------------------------------------------------
// удаление элемента из вершины стека
//--------------------------------------------------------------------------
int Pop(TElem** ptop)
{
TElem* del = *ptop;
*ptop = del->next;
int deleteInf = del->inf;
delete del;
del = NULL;
// в качестве ответа возвращаем значение удаленного элемента
return deleteInf;
}
//--------------------------------------------------------------------------
// реверсирование (переворачивание) стека
//--------------------------------------------------------------------------
void Reverse(TElem** ptop)
{
TElem* newStack = NULL;
while(*ptop != NULL)
newStack = Push(newStack, Pop(ptop));
*ptop = newStack;
}
//--------------------------------------------------------------------------
// вывод элементов стека на экран (двойное переворачивание)
//--------------------------------------------------------------------------
void Print(TElem** ptop)
{
cout << "Элементы стека имеют вид: ";
TElem* newStack = NULL;
while(*ptop != NULL)
{
int value = Pop(ptop);
cout << "\t" << value;
newStack = Push(newStack, value);
}
*ptop = newStack;
Reverse(ptop);
cout << endl;
}
//--------------------------------------------------------------------------
// очистка стека (удаление всех элементов)
//--------------------------------------------------------------------------
void Clear(TElem** ptop)
{
TElem* del = *ptop;
// пока в стеке остались элементы
while(*ptop != NULL)
{
*ptop = del->next;
delete del;
del = *ptop;
}
*ptop = NULL;
}
//--------------------------------------------------------------------------
Содержимое файла source.cpp:
[start lines=10]
#include "stack.h" // подключаем пользовательские описания
// использование функций напрямую из стандартного пространства имен
using namespace std;
//--------------------------------------------------------------------------
// главное меню программы
//--------------------------------------------------------------------------
int Menu(void)
{
int select;
do
{
system("CLS");
cout << "1 - ДОБАВЛЕНИЕ ЭЛЕМЕНТА В ВЕРШИНУ СТЕКА" << endl;
cout << "2 - УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ ВЕРШИНЫ СТЕКА" << endl;
cout << "3 - РЕВЕРСИРОВАНИЕ (ПЕРЕВОРАЧИВАНИЕ) СТЕКА" << endl;
cout << "4 - ПЕЧАТЬ ЭЛЕМЕНТОВ СТЕКА НА ЭКРАН" << endl;
cout << "5 - ОЧИСТКА СТЕКА (УДАЛЕНИЕ ВСЕХ ЭЛЕМЕНТОВ)" << endl;
cout << "6 - ВЫХОД" << endl;
cout << "Выбор: ";
cin >> select;
}
while((select < 1) || (select > 6));
cout << endl;
return select;
}
//--------------------------------------------------------------------------
// ввод значения информационного поля элемента вводом с клавиатуры
//--------------------------------------------------------------------------
int InputIntValue(void)
{
int value;
cout << "Введите значение элемента стека (целое число): ";
cin >> value;
return value;
}
//--------------------------------------------------------------------------
// главная функция программы (точка входа)
//--------------------------------------------------------------------------
int main(void)
{
TElem* top = NULL; // указатель на вершину стека
int select; // хранит №пункта меню, выбранного пользователем
setlocale(LC_ALL, "rus"); // настройка руссификации диалогов
do
{
select = Menu(); // отображение главного меню пользователю
switch(select)
{
case 1: // добавление элемента в вершину стека
{
if(top != NULL)
Print(&top);
top = Push(top, InputIntValue());
Print(&top);
cout << "Элемент успешно добавлен в вершину стека.";
break;
}
case 2: // удаление элемента из вершины стека
{
if(top == NULL)
cout << endl << "Стек пуст (не содержит ни одного элемента)! Удаление элемента невозможно.";
else
{
Print(&top);
Pop(&top);
Print(&top);
cout << "Элемент успешно удален из вершины стека.";
}
break;
}
case 3: // реверсирование (переворот) стека
{
if(top == NULL)
cout << endl << "Стек пуст (не содержит ни одного элемента)! Переворот стека невозможен.";
else
{
Print(&top);
Reverse(&top);
Print(&top);
cout << "Стек успешно реверсирован." << endl;
}
break;
}
case 4: // печать элементов стека на экран
{
if(top == NULL)
cout << endl << "Стек пуст (не содержит ни одного элемента)! Печать элементов невозможна.";
else
Print(&top);
break;
}
case 5: // очистка стека (удаление всех элементов)
{
Clear(&top);
cout << endl << "Из стека успешно удалены все элементы (стек пуст).";
break;
}
}
// если не выход, то делаем задержку программы, чтобы просмотреть результаты
if(select != 6)
{
fflush(stdin);
cin.get();
}
}
while(select != 6);
Clear(&top); // перед выходом из программы нужно подчистить память из-под стека
return 0; // завершение работы программы и передача управления в ОС
}
Результаты работы программы:
| № | Смысл операции | Результат |
| 1. | Попытка печати всех элементов стека (на начальный момент стек пуст). |  |
| 2. | Добавление в вершину стека элемента со значением $5$. |  |
| 3. | Добавляем в вершину стека последовательно элементы со значениями $4$, $3$, $2$ и $1$. |  |
| 4. | Попробуем удалить из стека верхний элемент. |  |
| 5. | Добавим в начало стека элемент со значением $-55$. |  |
| 6. | Произведем реверсировку стека, т е перевернем элементы стека. |  |
| 7. | Попробуем удалить из стека верхний элемент. |  |
| 8. | Произведем реверсировку стека, т е перевернем элементы стека. |  |
| 9. | Произведем очистку стека, т е удалим из стека все элементы. |  |
| 10. | Попытка печати всех элементов стека (на данный момент стек пуст). |  |
| 11. | Завершим работу с программой. |  |
Лабораторная работа №3
Работа с бинарным деревом поиска
Краткая постановка задачи:
|
Необходимо написать модуль, содержащий решения $16$ задач для работы с бинарными деревьями, и программу, демонстрирующую работу этого модуля. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя. При необходимости можно использовать вспомогательные функции. В разработанном модуле не должны применяться интерфейсные функции (исключение возможно только для функций вывода дерева). |
Мы частично разработали решение данной задачи для всех студентов, изучающих данную тему. Программа реализована в среде MS Visual Studio на языке программирования C++ (консольный проект).
В коде учтены все пожелания и требования к данной задаче, выдвигаемые составителями. Соблюдены названия переменных, порядок выполнения операторов и пр.нюансы.
Закодированы следующие операции над бинарным деревом поиска:
| № | Смысл операции | Название функции в коде |
| 1. | Создание бинарного дерева поиска. Формируется бинарное дерево поиска, состоящее из $n$ элементов ($n$ вводится с клавиатуры). |
void MakeBinaryTree(bintree** proot, const int pn) |
| 2. | Добавление узла в бинарное дерево поиска. Пользователь вводит число, необходимо добавить его в дерево, руководствуясь принципами построения бинарного дерева поиска. | void Insert(bintree** proot, const int pinf) |
| 3. | Вывод бинарного дерева. Элементы дерева необходимо вывести в порядке возрастания ключей узлов. Реализован симметричный обход дерева (ЛКП). Способ вывода простой, а не "красивый". | void LKP(bintree* proot) |
| 4. | Поиск образца в бинарном дереве. | bool SearchNodeByKey(bintree* proot, const int pkey) |
| 5. | Подсчет количества узлов дерева. Использовать для решения подзадачи рекурсивный алгоритм. | int GetCountNodes(bintree* proot) |
| 6. | Подсчет числа листьев дерева. Использовать для решения подзадачи рекурсивный алгоритм. | int GetCountLeaves(bintree* proot) |
| 7. | Генерация случайного целого числа на заданном отрезке. | int irand(const int pa, const int pb) |
| 8. | Ввод с клавиатуры значения ключа добавляемого узла. | int InputIntValue(void) |
| 9. | Создание узла бинарного дерева поиска с заданным ключом. | bintree* CreateNode(const int pinf) |
| 10. | Проверка добавляемого узла на дубликатность. | bool IsUniqueValueInsert(bintree* proot, const int pinf) |
| 11. | Вывод бинарного дерева. Реализован прямой обход дерева (КЛП). | void KLP(bintree* proot) |
| 12. | Вывод бинарного дерева. Реализован обратный обход дерева (ЛПК). | void LPK(bintree* proot) |
| 13. | Удаление всех узлов из бинарного дерева (полная очистка дерева). | void RemoveBinaryTree(bintree** proot) |
| 14. | Главная функция программы (точка входа). | int main(void) |
Операции, имеющие желтоватый фон, - вспомогательные операции, которые так или иначе были использованы при кодировании основных операций обработки бинарного дерева поиска.
ВАЖНО!
Ниже приведена стоимость доработки программы:
| № | Операция | Консольный формат | Визуальный формат |
| 1. | Создание бинарного дерева поиска из $n$ элементов. | Бесплатно (см.реализацию ниже) | $250$ рублей |
| 2. | Добавление узла в бинарное дерево поиска. | Бесплатно (см.реализацию ниже) | $250$ рублей |
| 3. | Вывод бинарного дерева в порядке возрастания ключей его элементов ("красивый" формат). | $400$ рублей | $700$ рублей |
| 4. | Поиск образца в бинарном дереве поиска. | Бесплатно (см.реализацию ниже) | $250$ рублей |
| 5. | Подсчет количества узлов дерева. | Бесплатно (см.реализацию ниже) | $150$ рублей |
| 6. | Подсчет числа листьев дерева. | Бесплатно (см.реализацию ниже) | $150$ рублей |
| 7. | Расчет степени вершины, используя рекурсивный обход. | $100$ рублей | $250$ рублей |
| 8. | Расчет уровня вершины. | $100$ рублей | $250$ рублей |
| 9. | Расчет высоты дерева. | $100$ рублей | $250$ рублей |
| 10. | Поиск образца в бинарном дереве (любом дереве). | $100$ рублей | $250$ рублей |
| 11. | Удаление узла дерева с поддеревом. | $100$ рублей | $250$ рублей |
| 12. | Удаление всего дерева (с использованием п.11). | $100$ рублей | $250$ рублей |
| 13. | Удаление узла с перестройкой дерева. | $250$ рублей | $600$ рублей |
| 14. | Обход дерева в глубину (не рекурсивный). Требуется использовать стек, реализованный в предыдущей лабораторной работе. |
$200$ рублей, если стек уже закодирован. $700$ рублей, если стек не закодирован и его нужно кодировать. |
$500$ рублей, если стек уже закодирован. $1\ 200$ рублей, если стек не закодирован и его нужно кодировать. |
| 15. | Обход дерева в ширину (не рекурсивный). Требуется использовать очередь, реализованную в предыдущей лабораторной работе. |
$200$ рублей, если очередь уже закодирована. $700$ рублей, если очередь не закодирована и ее нужно кодировать. |
$500$ рублей, если очередь уже закодирована. $1\ 200$ рублей, если очередь не закодирована и ее нужно кодировать. |
| 16. | Балансировка дерева. | $500$ рублей | $900$ рублей |
Данная работа предполагает написание программы на языке C++. При заказе нужных вам операций над бинарным деревом поиска вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
В результате частичного кодирования данной задачи получился проект, состоящий из $3$ файлов:
tree.h - пользовательские описания (типы данных и прототипы функций).
tree.cpp - модуль для работы с бинарным деревом поиска.
source.cpp - программа, демонстрирующая работу модуля tree.cpp.
Содержимое файла tree.h:
#define _TREE_H_
//--------------------------------------------------------------------------
// структура "Узел бинарного дерева поиска"
//--------------------------------------------------------------------------
struct bintree
{
int inf; // ключевое значение узла дерева
bintree* left; // указатель на левое поддерево
bintree* right; // указатель на правое поддерево
};
//--------------------------------------------------------------------------
void RemoveBinaryTree(bintree** proot);
// создание узла бинарного дерева поиска с заданным ключом
bintree* CreateNode(const int pinf);
// проверка на дубликатность узла при добавлении
bool IsUniqueValueInsert(bintree* proot, const int pinf);
void Insert(bintree** proot, const int pinf); // добавление узла в бинарное дерево поиска
// генерация случайного числа на заданном отрезке
int irand(const int pa, const int pb);
// построение бинарного дерева поиска, состоящего из n узлов
void MakeBinaryTree(bintree** proot, const int pn);
void LKP(bintree* proot); // симметричных обход дерева
void KLP(bintree* proot); // прямой обход дерева
void LPK(bintree* proot); // обратный обход дерева
// поиска образца в дереве (поиск по ключу узла)
bool SearchNodeByKey(bintree* proot, const int pkey);
int GetCountNodes(bintree* proot); // подсчет узлов дерева
int GetCountLeaves(bintree* proot); // подсчет узлов-листьев дерева
void RemoveBinaryTree(bintree** proot); // удаление всех узлов из дерева
#endif
Содержимое файла tree.cpp:
[start lines=10]
#include <iomanip>
#include "tree.h"
using namespace std;
//--------------------------------------------------------------------------
// удаление всех узлов дерева (очистка дерева)
//--------------------------------------------------------------------------
void RemoveBinaryTree(bintree** proot)
{
if(*proot != NULL)
{
RemoveBinaryTree(&((*proot)->left));
RemoveBinaryTree(&((*proot)->right));
// текущий удаляемый узел гарантировано является листом
delete *proot;
*proot = NULL;
}
}
//--------------------------------------------------------------------------
// создание узла бинарного дерева поиска с заданным ключом
//--------------------------------------------------------------------------
bintree* CreateNode(const int pinf)
{
bintree* node = new bintree;
node->inf = pinf;
node->left = node->right = NULL;
return node;
}
//--------------------------------------------------------------------------
// проверка на дубликат ключа узла дерева
// false - добавляемый узел уже присутствует в дереве
// true - добавляемый узел отсутствует в дереве
//--------------------------------------------------------------------------
bool IsUniqueValueInsert(bintree* proot, const int pinf)
{
// "прошли" все дерево, не встретив дубликатного значения
if(proot == NULL)
return true;
// встали на узел, имеющий такой же ключ (встретили дубликат)
if(pinf == proot->inf)
return false;
// продвигаемся по дереву
if(pinf < proot->inf)
return IsUniqueValueInsert(proot->left, pinf);
else
return IsUniqueValueInsert(proot->right, pinf);
}
//--------------------------------------------------------------------------
// добавление узла в бинарное дерево поиска
//--------------------------------------------------------------------------
void Insert(bintree** proot, const int pinf)
{
if(*proot == NULL)
*proot = CreateNode(pinf);
else
if(pinf < (*proot)->inf)
Insert(&((*proot)->left), pinf);
else
Insert(&((*proot)->right), pinf);
}
//--------------------------------------------------------------------------
// генерация случайного целого числа на заданном отрезке
//--------------------------------------------------------------------------
int irand(const int pa, const int pb)
{
return (rand() % (pb - pa + 1) + pa);
}
//--------------------------------------------------------------------------
// создание бинарного дерева поиска, состоящего из n узлов
//--------------------------------------------------------------------------
void MakeBinaryTree(bintree** proot, const int pn)
{
// если дерево было сформировано раньше, то сначала нужно
// удалить все узлы "старого" дерева, а потом создавать новое
if(*proot != NULL)
RemoveBinaryTree(proot);
for(int i = 1; i <= pn; i++)
{
int key = irand(-100, 100);
// пытаемся добавлять узел до тех пор, пока не будет сгенерирован уникальный ключ
while(IsUniqueValueInsert(*proot, key) == false)
key = irand(-100, 100);
// гарантировано добавляем в дерево узел с уникальным ключом
Insert(proot, key);
}
}
//--------------------------------------------------------------------------
// вывод ключей узлов дерева по возрастанию (симметричный обход)
//--------------------------------------------------------------------------
void LKP(bintree* proot)
{
if(proot != NULL)
{
LKP(proot->left);
cout << setw(8) << proot->inf;
LKP(proot->right);
}
}
//--------------------------------------------------------------------------
// прямой порядок обхода (корень-влево-вправо)
//--------------------------------------------------------------------------
void KLP(bintree* proot)
{
if(proot != NULL)
{
cout << setw(8) << proot->inf;
KLP(proot->left);
KLP(proot->right);
}
}
//--------------------------------------------------------------------------
// обратный порядок обхода (влево-вправо-корень)
//--------------------------------------------------------------------------
void LPK(bintree* proot)
{
if(proot != NULL)
{
LPK(proot->left);
LPK(proot->right);
cout << setw(8) << proot->inf;
}
}
//--------------------------------------------------------------------------
// поиска образца в дереве по заданному ключу узла
//--------------------------------------------------------------------------
bool SearchNodeByKey(bintree* proot, const int pkey)
{
if(proot == NULL)
return false;
if(proot->inf == pkey)
return true;
if(pkey < proot->inf)
return (SearchNodeByKey(proot->left, pkey));
else
return (SearchNodeByKey(proot->right, pkey));
}
//--------------------------------------------------------------------------
// подсчет количество узлов дерева (рекурсивный обход)
//--------------------------------------------------------------------------
int GetCountNodes(bintree* proot)
{
if(proot == NULL)
return 0;
else
return GetCountNodes(proot->left) + GetCountNodes(proot->right) + 1;
}
//--------------------------------------------------------------------------
// подсчет количество узлов-листьев дерева (рекурсивный обход)
//--------------------------------------------------------------------------
int GetCountLeaves(bintree* proot)
{
if(proot == NULL)
return 0;
if((proot->left == NULL) && (proot->right == NULL))
return 1;
else
return (GetCountLeaves(proot->left) + GetCountLeaves(proot->right));
}
//--------------------------------------------------------------------------
Содержимое файла source.cpp:
[start lines=10]
#include <time.h> // для использования функции (time)
#include <iomanip> // для форматированного вывода (setw)
#include "tree.h"
using namespace std;
//--------------------------------------------------------------------------
// главное меню программы
//--------------------------------------------------------------------------
int Menu(void)
{
int select;
do
{
system("CLS");
cout << "Аббревиатура \'ДДП\' расшифровывается как \'Двоичное Дерево Поиска\'." << endl << endl;
cout << "1 - СОЗДАНИЕ ДДП из n элементов" << endl;
cout << "2 - ДОБАВЛЕНИЕ УЗЛА В ДДП" << endl;
cout << "3 - СИММЕТРИЧНЫЙ ОБХОД ДДП (влево-корень-вправо)" << endl;
cout << "4 - ПОИСК ОБРАЗЦА В ДДП" << endl;
cout << "5 - ПОДЧСЕТ КОЛИЧЕСТВА УЗЛОВ ДДП" << endl;
cout << "6 - ПОДСЧЕТ КОЛИЧЕСТВА УЗЛОВ-ЛИСТЬЕВ ДДП" << endl;
cout << "7 - ВЫХОД" << endl;
cout << "Выбор: ";
cin >> select;
}
while((select < 1) || (select > 7));
return select;
}
//--------------------------------------------------------------------------
// ввод с клавиатуры значения ключа добавляемого узла
//--------------------------------------------------------------------------
int InputIntValue(void)
{
int value;
cout << endl << "Введите значение ключа добавляемого узла (целое число): ";
cin >> value;
return value;
}
//--------------------------------------------------------------------------
// главная функция программы (точка входа)
//--------------------------------------------------------------------------
int main(void)
{
bintree* root = NULL; // указатель на корень дерева
setlocale(LC_ALL, "rus"); // руссификация диалогов программы
// чтобы генератор каждый раз возвращал различные числа
srand((unsigned)time(0));
int select;
do
{
select = Menu();
switch(select)
{
case 1: // создание ДДП, состоящего из n узлов
{
int n;
cout << endl << "Введите количество узлов, добавляемых в дерево (> 0): ";
cin >> n;
MakeBinaryTree(&root, n);
cout << "Бинарное дерево поиска, состоящее из " << n << " узлов, успешно сформировано.";
break;
}
case 2: // добавление нового узла в ДДП
{
int key = InputIntValue();
if(IsUniqueValueInsert(root, key) == false)
cout << "Узел с ключом \'" << key << "\' уже присутствует в дереве. Добавление дубликата невозможно!";
else
{
Insert(&root, key);
cout << "Новый узел с ключевым значением \'" << key << "\' успешно добавлен в бинарное дерево поиска.";
}
break;
}
case 3: // симметричный обход дерева (влево-корень-вправо)
{
if(root == NULL)
cout << endl << "Бинарное дерево поиска не содержит ни одного узла. Печать невозожна.";
else
{
cout << endl << "Узлы дерева имеют значения: ";
LKP(root);
}
break;
}
case 4: // поиск образца в бинарном дереве поиска
{
if(root == NULL)
cout << endl << "Бинарное дерево поиска не содержит ни одного узла. Поиск образца невозможен.";
else
{
int sample;
cout << endl << "Введите значение образца для поиска (целое число): ";
cin >> sample;
if(SearchNodeByKey(root, sample) == true)
cout << "Узел с заданным ключом присутствует в дереве.";
else
cout << "Узел с заданным ключом отсутсвует в дереве.";
}
break;
}
case 5:
{
cout << endl << "Двоичное дерево поиска содержит узлов: " << GetCountNodes(root) << " шт.";
break;
}
case 6:
{
cout << endl << "Двоичное дерево поиска содержит узлов-листьев: " << GetCountLeaves(root) << " шт.";
break;
}
}
if(select != 7)
{
fflush(stdin);
cin.get();
}
}
while(select != 7);
// перед выходом из программы следует подчистить память из-под узлов бинарного дерева поиска
if(root != NULL)
RemoveBinaryTree(&root);
return 0; // завершение работы программы и передача управления в ОС
}
//--------------------------------------------------------------------------
Результаты работы программы:
| № | Смысл операции | Результат |
| 1. | Попытка получить общее количество узлов в дереве (изначально дерево пустое). |  |
| 2. | Добавление узла в дерево с ключом, равным $27$. |  |
| 3. | Добавляем последовательно узлы со значениями: $11$, $45$, $33$, $-5$, $21$. После этого печатаем узлы дерева на экран. |  |
| 4. | Попытка получить общее количество листьев в дереве. |  |
| 5. | Создаем дерево, состоящее из $8$ узлов. |  |
| 6. | Печатаем узлы дерева на экран. |  |
| 7. | Завершаем работу с программой. |  |
Варианты индивидуальных заданий
Задание для всех вариантов звучит так (или, возможно, немного изменено, т к могут быть разные издания учебного пособия).
| За индивидуальную задачу при работе по БРС можно получить до 5 баллов. Для ее решения рекомендуется использовать подготовленный ранее программный модуль. |
ВАЖНО!
Задания обладают не одинаковой сложностью. Есть достаточно нетривиальные операции, требующие кодирования дополнительных функций.
Стоимость каждой операции обозначена в таблице ниже в самой правкой колонке "Стоимость".
Варианты заданий:
| № вар. | Формулировка | Стоимость |
| 1. | Определите, есть ли в данном бинарном дереве два одинаковых элемента (дерево не является бинарным деревом поиска). | $250$ рублей |
| 2. | Выведите номера уровней данного бинарного дерева, на которых имеются листья. | $200$ рублей |
| 3. | Выведите номера вершин, у которых количество потомков в леввом поддереве не равно количеству потомков в правом поддереве. | $200$ рублей |
| 4. | Выведите номера вершин, для которых высота левого поддерева не равна высоте правого поддерева. | $150$ рублей |
| 5. | Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на $1$. |
Бесплатно |
| 6. | Найдите высоту дерева $H$ и удалите из него (с перейстройкой) все вершины на уровне $\frac{H}{2}$. | $400$ рублей |
| 7. | Найдите минимальный путь между двумя произвольными листьями. | $150$ рублей |
| 8. | Найдите минимальный путь между двумя произвольными вершинами дерева. | $150$ рублей |
| 9. | Найдите высоту дерева $H$ и удалите в нем все вершины (с перейстройкой) на глубине $\frac{H}{2}$, у которых высота левого поддерева равна высоте правого поддерева. | $400$ рублей |
| 10. | Найдите путь максимальной длины и отразите дерево зеркально относительно этого пути. | $300$ рублей |
| 11. | Найдите путь максимальной длины между двумя произвольными вершинами с разным числом потомков. | $250$ рублей |
| 12. | Найдите путь максимальной длины между двумя произвольными вершинами разной высоты. | $200$ рублей |
| 13. | Найдите пути минимальной длины между корнем и листьями. | $200$ рублей |
| 14. | Определите, являются ли два дерева зеркальным отражением друг друга. | $350$ рублей |
| 15. | Найдите среднюю по значению вершину в дереве (вершину, у которой значение ближе всего по модулю к среднему арифметическому значений всех вершин). | $200$ рублей |
| 16. | Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны. | $150$ рублей |
| 17. | Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны. | $150$ рублей |
| 18. | Удалите все вершины, для которых количество потомков в левом поддереве отличается от количества вершин в правом поддереве на $2$ и более. | $150$ рублей |
| 19. | Удалите все вершины, у которых высота левого поддерева отличается от высоты правого поддерева на $2$. | $150$ рублей |
| 20. | Выясните, является ли дерево симметричным. | $200$ рублей |
| 21. | Вычислите количество вершин, для которых высота левого поддерева равна высоте правого поддерева. | $150$ рублей |
| 22. | Вычислите количество вершин, у которых равны или высоты поддеревьев, или количество потомков в правом и левом поддеревьях. | $150$ рублей |
Лабораторная работа $№3$ предполагает написание программы на языке C++. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Образец выполнения (вариант №5)
Напомним условие задания к варианту $№5$:
| Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на $1$. |
Прежде чем переходить непосредственно к кодированию данного задания, нужно провести его алгоритмизацию. Данный этап является обязательным и ни один профессиональный программист не опускает его в своей работе.
Предположим, что мы получили бинарное дерево поиска следующей конфигурации:
Данное дерево состоит из $12$ узлов, образующих $4$ уровня, кстати, является почти сбалансированным (для решения данной задачи это не важно).
Очевидно, что придется просмотреть все узлы данного дерева. Для этого можно воспользоваться любым из вариантов обхода дерева (прямой, обратный, симметричный). Выбираем симметричный порядок обхода, чтобы при печати номеров вершин они шли по возрастанию.
Далее нужно вспомнить, что в нашем распоряжении (в разработанном ранее модуле для работы с двоичным деревом поиска) есть замечательная функция, подсчитывающая количество узлов в заданном дереве/поддереве:
// подсчет количество узлов дерева (рекурсивный обход)
//--------------------------------------------------------------------------
int GetCountNodes(bintree* proot)
{
if(proot == NULL)
return 0;
else
return GetCountNodes(proot->left) + GetCountNodes(proot->right) + 1;
}
//--------------------------------------------------------------------------
Благодаря данной функции мы достаточно просто решим поставленную задачу! Начинаем последовательно сканировать в симметричном порядке все вершины дерева и для каждого узла подсчитывать количество потомков из левого и правого поддерева. Затем сравниваем модуль разности этих количеств на $1$, т к нам не важно, в каком из поддеревьев будет больше потомков на одного, главное, чтобы отличие было строго на один потомок.
Для приведенного дерева желтые узлы удовлетворяют этому условию:
| № | Значение вершины | Количество потомков в левом поддереве | Количество потомков в правом поддереве | Разность | Условие |
| 1. | -7 | 0 | 1 | 1 |  |
| 2. | 14 | 0 | 0 | 0 | |
| 3. | 25 | 2 | 2 | 0 | |
| 4. | 36 | 0 | 1 | 1 | |
| 5. | 39 | 0 | 0 | 0 | |
| 6. | 50 | 5 | 6 | 1 | |
| 7. | 61 | 0 | 1 | 1 | |
| 8. | 62 | 0 | 0 | 0 | |
| 9. | 77 | 2 | 3 | 1 | |
| 10. | 94 | 0 | 0 | 0 | |
| 11. | 100 | 1 | 0 | 1 | |
| 12. | 123 | 2 | 0 | 2 |
Реализация задачи на языке C++:
#include "tree.h" // подключаем заголовочный файл с описаниями модуля работы с ДДП
using namespace std; // стандартное пространство имен
//-------------------------------------------------------------------------------
// получаем все вершины дерева, у которых количество потомков в левом поддереве
// отличается от количества потомков в правом поддереве на 1
//-------------------------------------------------------------------------------
void PrintNodesDifferent_one(bintree* proot)
{
static const int DIFFERENT = 1; // отличие кол-ва потомков должно быть на 1
if(proot != NULL)
{
PrintNodesDifferent_one(proot->left); // продвигаемся в левое поддерево
// вычисляем количество потомков из левого поддерева
int countNodesInLeftSubtree = GetCountNodes(proot->left);
// вычисляем количество потомков из правого поддерева
int countNodesInRightSubtree = GetCountNodes(proot->right);
// выводим на экран значение вершины, удовлетворяющее условию
if(abs(countNodesInLeftSubtree - countNodesInRightSubtree) == DIFFERENT)
cout << "\t" << proot->inf;
PrintNodesDifferent_one(proot->right); // продвигаемся в правое поддерево
}
}
//-------------------------------------------------------------------------------
// главная функция программы (точка входа)
//-------------------------------------------------------------------------------
int main(void)
{
setlocale(LC_ALL, "rus");
bintree* root = NULL;
int count;
cout << "Введите количество узлов создаваемого бинарного дерева поиска (> 0): ";
cin >> count;
for(int i = 1; i <= count; i++)
{
int key;
cout << "\t- введите значение ключа добавляемого узла: ";
cin >> key;
Insert(&root, key);
}
cout << endl << "Значения вершин, у которых количество потомков в левом поддереве отличается от " << endl;
cout << "\tколичества потомков в правом поддереве на 1: ";
// получаем все вершины, удовлетворяющие заданному условию
PrintNodesDifferent_one(root);
RemoveBinaryTree(&root); // удаляем все узлы из бинарного дерева поиска
// задержка программы, чтобы можно было просмотреть результат работы программы
cout << endl << endl << "Для завершения работы программы нажмите клавишу ENTER...";
fflush(stdin);
cin.get();
return 0; // завершение работы программы и передача управления в ОС
}
//-------------------------------------------------------------------------------
Результаты работы программы:
Для реализации индивидуального задания $№5$ мы воспользовались лишь одной готовой функцией (GetCountNodes - подсчет количества потомков), обход дерева пришлось кодировать с нуля, т к в модуле нет на $100\%$ подходящей функции обхода бинарного дерева поиска. Также программа, приведенная в задании $№5$, предназначена только для нахождения нужных вершин двоичного дерева поиска.
Лабораторная работа №4
Работа с графом
Краткая постановка задачи:
|
Необходимо написать модуль, содержащий решения $11$ задач для работы с графами, и программу, демонстрирующую работу этого модуля. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя. Разобранные алгоритмы можно применять непосредственно, однако чаще всего они нуждаются в некоторых изменениях. При необходимости следует использовать вспомогательные функции. В качестве данных, если не сказано иначе, рекомендуется брать заранее заготовленные текстовые файлы, содержащие описание подобранных графов. Случайная генерация графов неудобна, так как для многих алгоритмов нужны графы, обладающие заранее известными свойствами. Граф хранится в текстовом файле (предпочтительнее) или вводится с клавиатуры, может быть задан любым из описанных выше способов. Необходимо иметь возможность прочитать его не только в соответствующую структуру, но и во все остальные. Желательно предусмотреть варианты хранения неориентированных и ориентированных графов. |
ВАЖНО!
Ниже приведена стоимость доработки программы:
| № | Операция | Консольный формат | Визуальный формат |
| 1. | Построение матрицы смежности. | $100$ рублей | $200$ рублей |
| 2. | Построение матрицы инциденций. | $120$ рублей | $240$ рублей |
| 3. | Построение перечней ребер. | $120$ рублей | $240$ рублей |
| 4. | Построение списков связи. | $150$ рублей | $300$ рублей |
| 5. | Построение остовного дерева путем обхода в глубину. | $200$ рублей | $400$ рублей |
| 6. | Построение остовного дерева путем обхода в ширину. | $200$ рублей | $400$ рублей |
| 7. | Построение каркаса минимальной стоимости (алгоритм Краскала). | $400$ рублей | $800$ рублей |
| 8. | Построение каркаса минимальной стоимости (алгоритм Прима). | $400$ рублей | $800$ рублей |
| 9. | Поиск и построение Эйлеров цикла в графе. | $500$ рублей | $1\ 000$ рублей |
| 10. | Построение массива кратчайших путей алгоритмом Дейкстры. | $350$ рублей | $700$ рублей |
| 11. | Построение матрицы кратчайших путей алгоритмом Флойда. | $400$ рублей | $800$ рублей |
Данная работа предполагает написание программы на языке C++. При заказе нужных вам операций с графом вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Варианты индивидуальных заданий
Задание для всех вариантов звучит так (или, возможно, немного изменено, т к могут быть разные издания учебного пособия).
| Для решения задач использовать графы. Для хранения графа в памяти ЭВМ необходимо организовать наиболее удобное его представление с точки зрения решаемой задачи. Исходные данные читать из текстового файла. |
ВАЖНО!
Задания обладают не одинаковой сложностью. Есть достаточно нетривиальные операции, требующие кодирования дополнительных функций.
Стоимость каждой операции обозначена в таблице ниже в самой правкой колонке "Стоимость".
Варианты заданий:
| № | Формулировка задания | Стоимость |
| 1. | Найти самый длинный простой путь в графе (путь, все ребра которого попарно различны) | $400$ рублей |
| 2. | Найти медиану взвешенного графа, т е такую вершину, сумма расстояний от которой до всех других вершин минимальна. | $400$ рублей |
| 3. | Задана система односторонних дорог. Найти путь, соединяющий города $A$ и $B$ и не проходящий через заданное множество городов. | $300$ рублей |
| 4. | Определить, изоморфен ли заданный граф своему дополнению. | $600$ рублей |
| 5. | Мостом графа назовем такое ребро, удаление которого увеличивает число компонент связности графа. Найти все мосты для заданного графа. | $250$ рублей |
| 6. | Найти длину самого длинного простого пути от города $A$ до города $B$ в заданной системе односторонних дорог. | $300$ рублей |
| 7. | В заданном графе найти максимальный по количеству вершин полный подграф. | $600$ рублей |
| 8. | Задан ориентированный граф с $N$ ($1 \leq N \leq 10$) вершинами, пронумерованными целыми числами от $1$ до $N$. Напишите программу, которая подсчитывает количество различных путей между всеми парами вершин графа. | $400$ рублей |
| 9. | Необходимо добраться на самолете из города $A$ в город $B$ при условии, что между ними нет прямого авиационного сообщения, затратив при этом минимальные средства. Заданы возможные промежуточные аэропорты. Для каждой пары аэропортов известно, существует ли между ними прямой маршрут, и если да, то известна минимальная стоимость перелета по этому маршруту. | $400$ рублей |
| 10. | Даны два числа: $N$ и $M$. Построить граф из $N$ вершин и $M$ ребер. Каждой вершине ставится в соответствие число ребер, входящих в нее. Граф должен быть таким, чтобы сумма квадратов этих чисел была минимальна. | $500$ рублей |
| 11. | По заданной системе односторонних дорог определить, есть ли в ней город, куда можно попасть из любого другого города, проезжая не более $100$ км. | $350$ рублей |
| 12. | В графе найти максимальное (по количеству ребер) подмножество попарно несмежных ребер. | $500$ рублей |
| 13. | Определить, является ли заданный граф двудольным. | $600$ рублей |
| 14. | По системе двусторонних дорог определить, можно ли, построив какие-нибудь три новые дороги, из заданного города добраться до каждого из остальных городов, проезжая не более $100$ км. | $400$ рублей |
| 15. | Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ-получателей, которым она рассылает программное обеспечение всякий раз, получив новое бесплатное программное обеспечение (извне сети или из другой школы). При этом, если школа $B$ есть в списке получателей школы $A$, то школа $A$ может не быть в списке получателей школы $B$. Требуется написать написать программу, определяющую минимальное количество школ, которым надо передать по экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети в соответствии с соглашениями. | $600$ рублей |
| 16. | Известно, что заданный граф - не дерево. Проверить, можно ли из него получить дерево путем удаления $n$ вершин (каждая вершина удаляется вместе с инцидентными ей ребрами, $n$ вводится с клавиатуры). | $500$ рублей |
| 17. | Задан неориентированный граф. При прохождении по некоторым ребрам некоторые (определенные заранее) ребра могут исчезать или появляться. Найти кратчайший путь из вершины с номером $q$ в вершину с номером $w$. | $600$ рублей |
| 18. |
Дан ориентированный граф с $N$ вершинами ($N \le 50$). Вершины и дуги окрашены в цвета с номерами от $1$ до $M$ ($M \leq 6$). Указаны две вершины, в которых находятся фишки игрока, и конечная вершина. Правила перемещения фишек:
Игра заканчивается, если одна из фишек достигает конечной вершины. Написать программу поиска кратчайшего пути до конечной вершины, если он существует. |
$600$ рублей |
| 19. | Заданы два числа: $N$ и $M$ ($20 \leq M \leq N \leq 150$), где $N$ - количество точек на плоскости. Требуется построить дерево из $M$ точек так, чтобы оно было оптимальным. Дерево называется оптимальным, если сумма всех его ребер минимальна. Все ребра - расстояния между вершинами, заданными координатами точек на плоскости. | $500$ рублей |
| 20. | Треугольником в неориентированном графе называется тройка вершин, попарно соединенных дугами. Склеиванием треугольника называется операция замены вершин треугольника новой вершиной с сохранением всех связей с остальными вершинами графа. Дан неориентированный граф. Склейте все треугольники графа. | $500$ рублей |
| 21. | Проверить, является ли заданный ориентированный граф связным. | Бесплатно (см.пример ниже) |
Лабораторная работа $№4$ предполагает написание программы на языке C++. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Образец выполнения (вариант №21)
Напомним условие задания к варианту $№21$:
| Проверить, является ли заданный ориентированный граф связным. |
Прежде чем переходить непосредственно к кодированию данного задания, нужно провести его алгоритмизацию. Данный этап является обязательным и ни один профессиональный программист не опускает его в своей работе.
Если граф является ориентированным, то можно говорить о нескольких вариантах его связности:
Ориентированный граф называется сильно-связным, если в нем существует путь из произвольной вершины в любую другую произвольную вершину.
Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных ребер неориентированными.
Составители заданий ни слова не упомянули про данную тонкость, поэтому нам придется самим определиться, с каким типом связности работать. Очевидно, что будем анализировать ориентированный граф, который является сильно-связным.
Также будем считать, что анализируемый на связность граф является невзвешенным, то есть его дуги не обладают каким-либо весом. На вход программе будет подаваться текстовый файл (в формате $*.txt$), в котором хранится матрица смежности, описывающая структуру анализируемого ориентированного графа. В первой строке файла будет записано натуральное число, выражающее количество вершин рассматриваемого графа.
Пример входного текстового файла с данными и визуализация графа, построенного на основании этих данных:
Является ли представленный выше ориентированный граф связным? Чтобы ответить на этот вопрос, нам нужно проверить необходимое и достаточное условие связности графа: "ориентированный граф будет связным, если существует путь из произвольной вершины в любую другую произвольную вершину".
Так как граф является ориентированным, то придется последовательно перебирать все его вершины! Потому что, если, например, мы смогли посетить вершину $№6$ из вершины $№5$, то это не гарантирует обратного.
Для обхода графа в основном применяются два классический алгоритма:
Обход графа в ширину (в теории англ. BFS, Breadth-First-Searh).
Обход графа в глубину (в теории англ. DFS, Depth-First-Search).
Студентам, которым предстоит сдача данной лабораторной работы, нужно в совершенстве понимать данные алгоритмы обхода. 
Если у вас есть какие-то сложности с понимаем того, как устроены данные алгоритмы обхода графа, то можете записаться на частные занятия по программированию к репетитору Александру Георгиевичу (№тел.: $8 - 926 - 610 - 61 - 95$). Кстати, именно он является автором данной статьи, поэтому сможет ответить на любые вопросы, связанные с теорией графов.
Алгоритм обхода графа в ширину задействует такую структуру данных, как очередь, а алгоритм обхода графа в глубину - стек. Возьмем за базу алгоритм DFS, использующий стек. Кстати, в лабораторной работе $№2$ были закодированы, как стек, так и очередь. Частично тем кодом можно воспользоваться при программировании данного задания. Но лишь частично!
Заданный граф состоит из $6$ вершин. Чтобы проверить ориентированный граф на связность, запустим последовательно алгоритм DFS (обход в глубину) из каждой его вершины.
Ниже приведены способы посещения всех вершин графа при первоначальной различной вершины графа. Посещения производятся в соответствии c алгоритмом DFS. Над каждой дугой графа проставлено число, которое показывает порядок перемещения между вершинами графа.
| № стартовой вершины | Схема посещения вершин графа | Связность? |
| 1 |  |
|
| 2 |  |
|
| 3 |  |
|
| 4 |  |
|
| 5 |  |
|
| 6 |  |
|
Из какой бы вершины мы не начинали обход графа, всегда удается посетить абсолютно все вершины, то есть существует путь от произвольной вершины в любую другую произвольную, следовательно, заданный ориентированный граф является связным.
А теперь давайте из представленного графа удалим буквально одну связь/дугу между вершинами $№3$ и $№2$. И запустим алгоритм обхода DFS из вершины $№5$.
Как видите, результаты неутешительны, связность графа стала нарушена - он стал несвязным ориентированным графом! Теперь граф обладает больше одной компонентой связности. А достаточно было убрать всего лишь одну дугу...
В итоге, чтобы студент мог безболезненно правильно закодировать подобную задачу, он должен хорошо понимать:
Принцип работы одномерных и двухмерных динамических массивов.
Принцип работы динамической структуры данных стек.
Принцип правильного конструирования программного обеспечения (разделение подзадач на отдельные функции).
Принцип работы обхода графа в глубину (DFS).
Как взаимодействовать с текстовыми файлами, используя файловые потоки.
Для решения поставленной задачи пришлось разработать следующие программные функции ($12$ штук):
| № | Смысл операции | Название функции в коде |
| 1. | Создание элемента стека. | TElem* CreateElem(const int pinf) |
| 2. | Добавление элемента в стек (в вершину стека). | void Push(const int pinf) |
| 3. | Получение значения элемента на вершине стека (не удаляя сам элемент). | int Peek(void) |
| 4. | Удаление элемента из вершины стека. | void Pop(void) |
| 5. | Выделение памяти под динамическую матрицу смежности графа. | int** CreateMatrix(const int psize) |
| 6. | Вывод матрицы смежности графа на экран. | void PrintMatrix(int** pmatrix, const int psize) |
| 7. | Заполнение матрицы смежности графа данными из заданного текстового файла. | int** ReadMatrixFromTextFile(const string pnameFile, int& psize) |
| 8. | Освобождение памяти из-под динамической матрицы смежности графа. | void DestroyMatrix(int** pmatrix, const int psize) |
| 9. | Обход неориентированного графа в глубину (с использованием структуры данных стек, нерекурсивный алгоритм). | bool DFS(int** pmatrix, const int psize, const int pstartVertex, bool pvisited[]) |
| 10. | Установка всем вершинам графа статуса "посещена / не посещена". | void SetStatusVertex(bool pvisited[], const int psize, const bool pstatus) |
| 11. | Проверка ориентированного графа на связность. | void IsConnectedGraph(int** pmatrix, const int psize) |
| 12. | Главная функция программы (точка входа). | int main(void) |
Реализация задачи на языке C++:
[start lines=10]
#include <iomanip> // для форматного вывода информации
#include <string> // для работы со строками
#include <fstream> // для работы с файлами
using namespace std; // подключаем стандартное пространство имен
//---------------------------------------------------------------------------
// структура "Элемент стека"
//---------------------------------------------------------------------------
struct TElem
{
int inf; // значение информационного поля элемента
TElem* next; // ссылка на следующий элемент стека
} *top = NULL; // глобальный указатель на вершину стека
//---------------------------------------------------------------------------
// создание элемента стека
//---------------------------------------------------------------------------
TElem* CreateElem(const int pinf)
{
TElem* add = new TElem;
add->inf = pinf;
add->next = NULL;
return add;
}
//---------------------------------------------------------------------------
// добавление элемента в вершиу стека
//---------------------------------------------------------------------------
void Push(const int pinf)
{
TElem* add = CreateElem(pinf);
if(top != NULL)
add->next = top;
top = add;
}
//---------------------------------------------------------------------------
// получение значения элемента на вершине стека
//---------------------------------------------------------------------------
int Peek(void)
{
return (top->inf);
}
//---------------------------------------------------------------------------
// удаление элемента из вершины стека
//---------------------------------------------------------------------------
void Pop(void)
{
TElem* del = top;
top = top->next;
delete del;
del = NULL;
}
//---------------------------------------------------------------------------
// выделение памяти под матрицу смежности графа
//---------------------------------------------------------------------------
int** CreateMatrix(const int psize)
{
int** matrix = new int*[psize];
for(int i = 0; i < psize; i++)
matrix[i] = new int[psize];
return matrix;
}
//---------------------------------------------------------------------------
// вывод матрицы смежности графа на экран
//---------------------------------------------------------------------------
void PrintMatrix(int** pmatrix, const int psize)
{
cout << endl << "Матрица смежности заданного графа имеет вид: " << endl;
for(int i = 0; i < psize; i++)
{
for(int j = 0; j < psize; j++)
cout << setw(8) << pmatrix[i][j];
cout << endl << endl;
}
}
//---------------------------------------------------------------------------
// заполнение матрицы смежности графа данными из текстового файла
//---------------------------------------------------------------------------
int** ReadMatrixFromTextFile(const string pnameFile, int& psize)
{
ifstream file(pnameFile);
file >> psize;
int** matrix = CreateMatrix(psize);
for(int i = 0; i < psize; i++)
for(int j = 0; j < psize; j++)
file >> matrix[i][j];
file.close();
return matrix;
}
//---------------------------------------------------------------------------
// освобождение памяти из-под матрицы смежности графа
//---------------------------------------------------------------------------
void DestroyMatrix(int** pmatrix, const int psize)
{
for(int i = 0; i < psize; i++)
delete []pmatrix[i];
delete []pmatrix;
}
//---------------------------------------------------------------------------
// обход графа в глубину (с использованием стека, нерекурсивный вариант)
// false - не все вершины были посещены
// true - все вершины были посещены
//---------------------------------------------------------------------------
bool DFS(int** pmatrix, const int psize, const int pstartVertex, bool pvisited[])
{
// стек вершин изначально пуст
top = NULL;
// помещаем в стек стартовую вершину (нумерация вершин с 0)
Push(pstartVertex - 1);
// помечаем стартовую вершину, как посещенную
pvisited[pstartVertex - 1] = true;
// пока стек не станет пустым
while(top != NULL)
{
// берем вершину, находящуюся на вершине стека
int numberCurrentVertex = Peek();
// удаляем вершину из стека
Pop();
// последовательно добавляем в стек все вершины, которые смежны
// только что взятой вершины из стека + только те вершины, которые не посещены
for(int j = 0; j < psize; j++)
if((pmatrix[numberCurrentVertex][j] == 1) && (pvisited[j] == false))
{
Push(j); // добавляем еще непосещенную вершину в стек
pvisited[j] = true; // устанавливаем статус этой вершины, как "посещена"
}
}
// проверка статуса вершины графа на посещенность
for(int i = 0; i < psize; i++)
if(pvisited[i] == false)
return false;
return true;
}
//---------------------------------------------------------------------------
// установка всем вершинам графа статуса "посещена/не посещена"
// false - не посещена
// true - посещена
//---------------------------------------------------------------------------
void SetStatusVertex(bool pvisited[], const int psize, const bool pstatus)
{
for(int i = 0; i < psize; i++)
pvisited[i] = pstatus;
}
//---------------------------------------------------------------------------
// проверка ориентированного графа на связность (ключевая функция программы)
//---------------------------------------------------------------------------
void IsConnectedGraph(int** pmatrix, const int psize)
{
// отвечает за статус вершины "посещена/не посещена"
bool* visited = new bool[psize];
// запускаем обход графа в глубину ИЗ КАЖДОЙ вершины
for(int i = 1; i <= psize; i++)
{
SetStatusVertex(visited, psize, false);
bool isVisitedAllVertexes = DFS(pmatrix, psize, i, visited); // обход графа в глубину с вершины №i
// если при обходе графа в глубину не все вершины были посещены, значит он несвязный
if(isVisitedAllVertexes == false)
{
cout << endl << "Заданный ориентированный граф является НЕСВЯЗНЫМ!" << endl;
cout << "Из вершины №" << i << " нельзя добраться до любой вершины графа." << endl;
return;
}
}
cout << endl << "Заданный ориентированный граф является СВЯЗНЫМ!" << endl;
}
//---------------------------------------------------------------------------
// главная функция программы (точка входа)
//---------------------------------------------------------------------------
int main(void)
{
setlocale(LC_ALL, "rus"); // настройка руссификации диалогов программы
int size; // размер матрицы смежности графа (количество вершин графа)
int** matrix = NULL; // динамическая матрица смежности графа
string nameInputTextFile; // имя входного текстового файла с данными (матрица смежности)
// запрашиваем с клавиатуры имя входного текствого файла
cout << "Введите имя текстового файла с данными: ";
getline(cin, nameInputTextFile);
ifstream textFile(nameInputTextFile);
textFile.close();
if(!textFile) // если файла с введенным именем НЕ существует, то выдаем сообщение и завершаем работу программы
cout << endl << "Файла с именем \'" << nameInputTextFile << "\' не существует! Чтение матрицы смежности графа невозможно!";
else
{
// читаем матрицу смежности графа из текстового файла
matrix = ReadMatrixFromTextFile(nameInputTextFile, size);
// выводим считанную матрицу смежности графа на экран
PrintMatrix(matrix, size);
// проверка графа на связность
IsConnectedGraph(matrix, size);
// удаляем память из-под динамической матрицы смежности графа
DestroyMatrix(matrix, size);
matrix = NULL; // чтобы не было висячей ссылки
}
cout << endl << "Для завершения работы программы нажмите клавишу ENTER...";
fflush(stdin);
cin.get(); // задержка работы программы, чтобы можно было просмотреть результаты
return 0; // завершение работы программы и передача управления в ОС
}
//---------------------------------------------------------------------------
Результаты работы программы:
| № | Визуальное представление графа | Результат |
| 1. |  |
 |
| 2. |  |
 |
| 3. |  |
 |
О качестве программного кода
Абсолютно любую программу можно закодировать "тысячей" способами. У каждого профессионального программиста собственная философия кодирования, начиная от названия переменных, и, заканчивая подсветкой редактора программного кода.
У каждого из нас за плечами колоссальное количество успешно реализованных студенческих проектов. И мы прекрасно понимаем, что вузовские программы, а особенно лабораторные работы, должны соответствовать требованиям, описанным в методическом пособии.
Поэтому, прежде чем приступать к кодированию, мы очень тщательно и скрупулезно изучаем все студенческие материалы, по которым студентам предстоит выполнять лабораторные проекты. Все лабораторные работы из данного практикума не являются исключением.
Соблюдены названия переменных и функций, порядок и способ заполнения массивов и т.п. Преподаватель, принимающий у вас работу, не заподозрит, что вы программировали не самостоятельно.
Закодируем студенческие работы на любом из следующих языков программирования: C, C++, C#, Pascal, Delphi
Зачастую разные вузы используют одни и те же методические обучающие пособия. Поэтому, если вы не студент САФУ, но вам требуется выполнить такие же или похожие задания, но не на языке C/C++, а, например, на языке Pascal, то мы абсолютно без каких-либо проблем напишем соответствующий код с нуля.
В нашем штате есть СИ-ориентированный программист Валентин Смирнов. Владеет на профессиональном уровне $3$-мя Си-подобными языками: C, C++, C#. Поэтому сообщите нам, под какой язык программирования следует провести адаптацию нужных вам лабораторных работ.
Стоимость реализации будет такой же, как под язык C++. Т е мы не делаем перевод С-ориентированных программ на другой язык программирования бесплатно. Но перевод будет сделан в кратчайшие сроки, как правило, в день вашего обращения.
Скидка 50% при заказе всех вариантов лабораторных/курсовых работ
Своим потенциальным клиентам мы предлагаем сумасшедший бонус! При одновременном заказе всех вариантов какой-либо лабораторной работы предоставляется ценовая скидка в размере $50\%$ от первоначальной стоимости.
| Пример. Студенты, учащиеся в одном вузе, испытывают колоссальные проблемы с практическим заданием на языке C++. Поэтому они принимают коллегиальное решение заказать сразу все варианты этой работы. В этом случае им предоставляется скидка в размере $50\%$. Значит, стоимость каждой программы уже составляет, например, не $200$ рублей, а всего $100$ рублей. |
Для получения подобной скидки вам нужно оформить заказ на приобретение всех программ выбранной работы. Если по каким-либо причинам вы закажите не все варианты конкретной работы, то бонус не предоставляется.
Для оформления подобного заказа мы предлагаем вам, студентам, объединяться в группу.
Также хочется отметить особый случай, с которым мы периодически сталкиваемся. Иногда студенты определенной группы решают заказать все варианты всех лабораторных работ! В такой ситуации стоимость обговаривается в индивидуальном порядке, но скидка может достигать $70\%$.
А какими способами можно оплатить заказанные работы?
Своим потенциальным клиентам мы предлагаем следующие варианты оплаты:
На карточку Сбербанка России (рекомендуемый способ).
WebMoney.
Яндекс.Деньги.
На номер мобильного телефона (нерекомендуемый способ).
Окажем вам полную информационную поддержку, по заказанным у нас работам
Заказав у нас работы, вы получаете полную информационную поддержку. Что включает подобная поддержка?
Ответим на любые тематические вопросы, связанные с программой/отчетом-алгоритмом/блок-схемой, которую вы заказали.
Поможем запустить программу на вашем ПК. Или диагностируем проблему, с которой вы столкнулись, предложив рациональные пути решения.
Исправим код программы под новые требования. Как правило, стоимость этой доработки составляет $10\%$ от первоначальной стоимости купленной программы, т е доработка производится не бесплатно.
Данный материал (программы, текст, оформление) подготовлен при участии:
| Александр Георгиевич | Валентин Иванович |
|
► Основатель данного сайта. |
► Профессиональный программист на языках: C, C++, C#, Java. |