Практикум на ЭВМ технология программирования в среде С++




Скачать 409.93 Kb.
НазваниеПрактикум на ЭВМ технология программирования в среде С++
страница12/12
Дата публикации31.05.2014
Размер409.93 Kb.
ТипДокументы
literature-edu.ru > Курсовая работа > Документы
1   ...   4   5   6   7   8   9   10   11   12

6.4Методика решения задач


Рассмотрим пример решения задачи построения и использования связного списка.
Даны натуральное число n, действительные числа x1, …, xn, (n ≥ 2). Получить последовательность x1xn, x2xn-1, …, xnx1.
Идеей решения задачи является создание числового двусвязного списка на основе шаблонного класса 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).

Вершины графа и ребра могут быть нагружены (помечены) дополнительными описаниями – номерами, длинами и т.д.

Деревом называется связный граф без циклов.

Корневое дерево – это связный орграф без циклов, удовлетворяющий следующим условиям:

      1. имеется ровно одна вершина, называемая корнем, к которой не ведет ни одной дуги;

      2. к каждой вершине, отличной от корня ведет ровно одна дуга;

      3. преемники всякой вершины упорядочены.

Вершины корневого дерева, не являющиеся преемниками, называются листьями.

Деревом двоичного поиска для множества чисел S называется размеченное двоичное дерево, в котором каждая вершина v помечена числом l(v)S и которое удовлетворяет следующим условиям:

      1. l(u) < l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого левый преемник v;

      2. l(u) > l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого правый преемник v;

      3. для всякого числа 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Литература


    1. Культин Н.Б. С/С++ в задачах и примерах. – СПб. - Петербург. – 2005. – 288 с.

    2. С/С++ Структурное программирование: Практикум/ Т.А. Павловская, Ю.А. Щупак. СПб.: Питер, 2004. – 239с.: ил.

    3. Каррано Ф.М., Причард Дж.Дж. Абстракция данных и решение задач на С++. Стены и зеркала, 3-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 848 с.

    4. Страустрап Бьярн. Введение в язык С++ ☺

    5. Уроки по С++ для начинающих ☺

    6. Справочное руководство по С++ ☺






1   ...   4   5   6   7   8   9   10   11   12

Похожие:

Практикум на ЭВМ технология программирования в среде С++ iconПрактикум на ЭВМ среда программирования и отладка программ
Рыков В. И. Среда Microsoft Visual C++ и отладка программ. Технология работы с языком С++. /Издание Башкирского ун-та. Уфа 2006....

Практикум на ЭВМ технология программирования в среде С++ iconОсновы информатики и вычислительной техники системы программирования
Рассматриваются основные понятия языков программирования. Излагаются процедурный и объектный подходы в программировании. Более подробно...

Практикум на ЭВМ технология программирования в среде С++ iconРабочая программа по курсу «основы Программирования на языке ассемблер»
Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...

Практикум на ЭВМ технология программирования в среде С++ iconПрограмма учебной дисциплины «Управление данными»
«Математика», «Информатика», «Программирование на языках высокого уровня», «Дискретная математика», «Объектно-ориентированное программирование»,...

Практикум на ЭВМ технология программирования в среде С++ iconПрактикум по спортивной психологии Санкт-Петербург
...

Практикум на ЭВМ технология программирования в среде С++ iconРеферат по теме: "Строение персональных компьютеров ibm pc"
Эвм и мини ЭВМ. Это стало предметом серьезного беспокойства фирмы ibm (International Bussines Machines Corporation) ведущей компании...

Практикум на ЭВМ технология программирования в среде С++ iconКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
Система программирования – комплекс программных инструментов и библиотек, который поддерживает создание и существование программного...

Практикум на ЭВМ технология программирования в среде С++ iconПлан лекции: Задачи, решаемые вычислительными центрами Структура...
Создание вычислительных центров является способом повышения эффективности работы ЭВМ. Вычислительный центр объединяет технику различных...

Практикум на ЭВМ технология программирования в среде С++ iconМентальное моделирование как технология понимания текста на примере книг Карлоса Кастанеды
Ваша собственная ментальная программа. Поэтому вполне может случиться, что некоторые ментальные программы не могут быть отмоделированы...

Практикум на ЭВМ технология программирования в среде С++ iconПрактикум по когнитивной терапии
М15 Практикум по когнитивной терапии: Пер с англ. — Спб.: Речь, 2001. — 560 с. Isbn 5-9268-0036-6

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции