6.4Методика решения задач
Рассмотрим пример решения задачи построения и использования связного списка.
Даны натуральное число n, действительные числа x1, …, xn, (n ≥ 2). Получить последовательность x1 – xn, x2 – xn-1, …, xn – x1.
Идеей решения задачи является создание числового двусвязного списка на основе шаблонного класса List библиотеки STL и подсчет требуемых разностей за счет согласованного движения по списку с обеих концов навстречу друг другу.
Сформируем Rational Rose MFC - проект с именем LinkList..В проекте, в пакете Use Case View образуем Use Case с именем «Получить разность чисел» и актера с именем “Main”
6.4.1Диаграммы использования
Диаграммы имеют вид:
6.4.2Модуль LinkList.h:
Текст программы имеет вид:
// Copyright (C) 1991 - 1999 Rational Software Corporation
#if defined (_MSC_VER) && (_MSC_VER >= 1000)
#pragma once
#endif
#ifndef _INC_LINKLIST_45B863B50271_INCLUDED
#define _INC_LINKLIST_45B863B50271_INCLUDED
//Даны натуральное число n, действительные числа x1, …, xn,
//(n >= 2). Получить последовательность чисел x1 - xn, x2 -
//x(n-1), …, x(n-1) - xn
//##ModelId=45B863B50271
class LinkList
{
private:
//Функция вывода потенциальных ошибок в программе.
//##ModelId=45BB177200EA
void error(const char* textl, const char* text2);
//##ModelId=45BF65CF0203
int mNum;
//list mList;
public:
//Конструктор по умолчанию (пустой).
//##ModelId=45BB122F037A
LinkList();
//Функция чтения последовательности чисел и формирования
//двусвязного списка
//##ModelId=45B863E900AB
fListCreate();
//Функция расчитывает разность чисел, используя
//одновременное встречное движение по двусвязному списку
//##ModelId=45B865EB009C
diffWork();
};
#endif /* _INC_LINKLIST_45B863B50271_INCLUDED */
#include "LinkList.h"
6.4.3Модуль LinkList.h
// Copyright (C) 1991 - 1999 Rational Software Corporation
#include "LinkList.h"
#include
#include
#include
using namespace std;
//##ModelId=45BF79670119
typedef list ListInt;
ListInt mList; //Создаем пустой список
ListInt::iterator i, j; //Два итератора для движения по списку
//##ModelId=45BB122F037A
LinkList::LinkList() {} //Конструктор по умолчанию
//##ModelId=45B863E900AB
LinkList::fListCreate()
{
ifstream from("From.txt"); //Oткрываем входной файл
if (!from) error("Input file don't found ;", "From.txt");
i = mList.begin(); //Итератор на первый элемент
while (from >> mNum)
mList.insert(i, mNum); //Создание списка
}//Конец процедуры fListCreate
//##ModelId=45B865EB009C
LinkList::diffWork()
{
j = mList.begin();
i = j; //Другая техника не проходит
j = mList.end();
--j;
//cout << *j<< endl; //Отладка
while (i != mList.end())
{ //Встречное движение по списку
cout << *i - *j<< endl;
++i; --j;
}//Конец цикла while
}//Конец процедуры diffWork
//##ModelId=45BB177200EA
void LinkList::error(const char* textl, const char* text2)
{
cerr << textl << ' ' << text2 << endl;
exit(1);
}//Конец процедуры error
6.4.4Модуль Main
int main()
{
LinkList s;
s.fListCreate();//Создание двусвязного списка
s.diffWork(); //Подсчет и вывод на экран разностей чисел
return 1;
}
7Графы, двоичные деревья
Граф – это пара (V, E), где V – конечное непустое множество вершин, а E – множество пар (u, v) вершин из V, называемых ребрами. Говорят, что ребро s = <u, v> соединяет вершины u и v. Ребро s и вершина u называются инцидентными, а вершины u и v смежными. Подграфом графа G называется такая его часть G, которая вместе со всякой парой вершин u, v содержит и ребро (u, v).
Вершины графа и ребра могут быть нагружены (помечены) дополнительными описаниями – номерами, длинами и т.д.
Деревом называется связный граф без циклов.
Корневое дерево – это связный орграф без циклов, удовлетворяющий следующим условиям:
-
имеется ровно одна вершина, называемая корнем, к которой не ведет ни одной дуги;
-
к каждой вершине, отличной от корня ведет ровно одна дуга;
-
преемники всякой вершины упорядочены.
Вершины корневого дерева, не являющиеся преемниками, называются листьями.
Деревом двоичного поиска для множества чисел S называется размеченное двоичное дерево, в котором каждая вершина v помечена числом l(v)S и которое удовлетворяет следующим условиям:
-
l(u) < l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого левый преемник v;
-
l(u) > l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого правый преемник v;
-
для всякого числа aS существует единственная вершина v, для которой l(v)=a.
Обозначим через ρ(T) максимум среди расстояний от корня дерева T до его листьев. (мы полагаем ρ(T) = -1, если Т пусто).
АВЛ-деревом, называется дерево двоичного поиска в котором для каждой вершины v выполнено следующее условие:
где v1 и v2 – преемники, а T1 и T2 – поддеревья с корнями v1 и v2.
7.1Обход корневого дерева
Обход корневого дерева состоит в посещении вершин этого дерева в некотором порядке. Определим три разных обхода дерева T (c корнем v и его преемниками v1, … , vn).
Прямой обход (или П - обход):
-
Посетить корень v;
-
Выполнить П – обход поддеревьев с корнями v1, … , vn в указанной последовательности.
Обратный обход (или О - обход)
-
Выполнить О – обход поддеревьев с корнями v1, … , vn в указанной последовательности;
-
Посетить корень v.
Обход во внутреннем порядке (или В - обход) двоичного дерева
-
Выполнить В – обход левого поддерева корня дерева Т;
-
Посетить корень дерева Т;
-
Выполнить В – обход правого поддерева корня дерева Т.
Термин «посетить корень» означает вывод его значения на экран или указание в списке обходе.
7.2Решение задачи построения дерева поиска
Написать программу построения дерева поиска по последовательности чисел, все элементы которой различны.
Функция insertItem определяет технологию построения дерева.
7.2.1Заголовочные файлы
// TreeNode.h
typedef int TreeltemType; //Тип значения
class TreeNode //Узел дерева
{
friend class BinaryTree1;
private:
TreeltemType item; //Данные
TreeNode *leftChildPtr; //Указатель на левый дочерний узел
TreeNode *rightChildPtr; //Указатель на правый дочерний узел
//public:
TreeNode();
TreeNode(const TreeltemType& nodeltem,
TreeNode *left,
TreeNode *right):
item(nodeltem),leftChildPtr(left),
rightChildPtr(right){};
};//Конец класса TreeNode
// BinaryTree1.h
#include "TreeNode.h"
#include
using namespace std;
class BinaryTree1
{
public:
int tNumbPar ; //Номер узла родителя
string order ; //Направление
int tNumbChild; //Номер узла потомка
//Конструктор о умолчанию
BinaryTree1();
//Дает команду для вставки в бинарное дерево поиска
//нового элемента
void BinaryTreeInsert(const int& newItem);
protected :
//Рекурсивно вставляет в нужное место дерева поиска
//элемент
void insertItem(TreeNode *& treePtr,
const int& newItem);
private:
TreeNode *root; //Указатель на корень дерева
};
7.2.2Файлы реализации
//TreeNode.cpp
#include "TreeNode.h"
//BinaryTree1.cpp
#include "BinaryTree1.h"
#include //Определение NULL
#include
using namespace std;
BinaryTree1::BinaryTree1() : root(NULL)
{
tNumbPar = 0; order = "Main";
}//Конец конструктора по умолчанию
void BinaryTree1::BinaryTreeInsert(const int& newItem)
{
insertItem(root, newItem);
}
void BinaryTree1::insertItem(TreeNode *& treePtr,
const int& newItem)
{
if (treePtr == NULL)
{
//Найдена позиция вставки
//Производится вставка после листа
//Создать новый узел
treePtr = new TreeNode(newItem, NULL, NULL);
cout << "Father = " << tNumbPar << " Order " << order;
cout << " Child " << newItem << endl;
}
//В противном случае ищем место для вставки
else if (newItem < treePtr->item)
{//Поиск в левом поддереве
tNumbPar = treePtr->item; //Для печати
order = "left";//Для печати
insertItem(treePtr->leftChildPtr, newItem);
}
else
{//Поиск в правом поддереве
tNumbPar = treePtr->item; //Для печати
order = "right";//Для печати
insertItem(treePtr->rightChildPtr, newItem);
}
}//Конец функции insertItem
//Main.cpp
#include "BinaryTree1.h"
//#include "TreeNode.h"
#include
#include
using namespace std;
void main()
{
BinaryTree1 q;
ifstream inFile ("Node.txt");
int x;
while (inFile >> x) // Считывание до конца файла
q.BinaryTreeInsert(x);//Формирование дерева
cout << endl;
inFile.close();
}
7.2.3Тестирование
Содержимое тестового файла:
2 4 3 6 5 1
Результат тестирования:
Рисунок дерева:
(построен как Use Case диаграмма системы Rational Rose)
8Графы, системы дорог
9Литература
-
Культин Н.Б. С/С++ в задачах и примерах. – СПб. - Петербург. – 2005. – 288 с.
-
С/С++ Структурное программирование: Практикум/ Т.А. Павловская, Ю.А. Щупак. СПб.: Питер, 2004. – 239с.: ил.
-
Каррано Ф.М., Причард Дж.Дж. Абстракция данных и решение задач на С++. Стены и зеркала, 3-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 848 с.
-
Страустрап Бьярн. Введение в язык С++ ☺
-
Уроки по С++ для начинающих ☺
-
Справочное руководство по С++ ☺
|
