Структура и алгоритм обработки данных

Московский государственный  открытый университет

Чебоксарский политехнический  институт

Кафедра информационных технологий и программирования

 

 

 

 

Курсовая работа

по дисциплине: Структура и алгоритм обработки данных

 

 

 

 

 

 Выполнил :

Студент 2-го курса 

очного отделения 

факультета Кит

специальность 230100

Федотов Г.В.

                      Проверила:  Замкова Т.В.

 

 

 

 

 

 

г. Чебоксары, 2013

 

 

Содержание

 

Введение3

Двусвязный список4

Пример  программы на языке C++7

Сеанс работы9

Деревья и их приминения10

Введение10

Основные  понятия10

Применение  и особенности деревьев 12

Пример  программы на языке C++15

Сеанс работы16

Обход графа в ширину. Применение.17

Основные  понятия 17

Описание  графов 18

Процедура поиска в ширину 18

Пример  программы на языке C++20

Сеанс работы23

Заключение.24

Список использованной литературы.25

 

 

 

 

Введение

      В языках программирования существуют способы выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).                               

      Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.

 

 

 

 

 

 

 

 

 

 

 

 

 

Двусвязный список.

         Если главный интерес представляет последовательный перебор набора элементов, их можно организовать в виде связного списка – базовой структуры данных, в которой каждый элемент содержит информацию, необходимую для получения следующего элемента. Основное преимущество связных списков перед массивами заключается в возможности эффективного изменения расположения элементов. За эту гибкость приходится жертвовать скоростью доступа к произвольному элементу списка, поскольку единственный способ получения элемента состоит в отслеживании связей от начала или конца списка.

          Определение. Связный список – это набор элементов, причем каждый из  них является частью узла, который также содержит ссылку на узел.                           Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы. 

          Узлы определяются ссылками на  узлы, поэтому связные списки  иногда называют самоссылочными структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические структуры. Последствия этих двух фактов станут ясны при рассмотрении конкретных представлений и применений связных списков.

           Обычно под связным списком  подразумевается реализация последовательного  расположения набора элементов. Начиная с некоторого узла, мы считаем его первым элементом последовательности. Затем прослеживается его ссылка на другой узел, который дает нам второй элемент последовательности и т.д. Поскольку список может быть циклическим, последовательность иногда представляется бесконечной. Чаще всего приходится иметь дело со списками, соответствующими простому последовательному расположению элементов, принимая одно из следующих соглашений для ссылки последнего узла:

• Это пустая ссылка, не указывающая на какой либо узел.
• Ссылка указывает на фиктивный узел, который не содержит элементов.
• Ссылка указывает на первый узел, что делает список циклическим.

В каждом случае отслеживание ссылок от первого узла до последнего формирует последовательное расположение элементов. Массивы также задают последовательное расположение элементов, но оно реализуется косвенно, за счет позиции в массиве. (Массивы также поддерживают произвольный доступ по индексу, что невозможно для списков.)

 

          Распределение памяти имеет ключевое значение для эффективного использования двусвязных списков. Как только возникает необходимость использовать новый узел, для него следует зарезервировать память. При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовать вычисления, связанные с резервированием памяти во время выполнения, посредством вызовов системных операторов управления памятью. Например в строке кода

       link x = new node;

содержится оператор new, который резервирует достаточный для узла объема памяти и возвращает указатель на него в переменной x.

         В язык С++ широко принято инициализировать область хранения, а не только выделять для нее память. В связи с этим обычно каждую описываемую структуру включается конструктор. Конструктор представляет собой функцию, которая описывается внутри структуры и имеет такое же имя. Для этого конструкторы автоматически вызываются при создании экземпляра структуры.

        Каждая ячейка  двусвязного списка содержит  в поле связей два указателя  адреса. Первый указывает на следующую  ячейку, а второй на предыдущую. 
В качестве примера на рисунке ниже представлен двусвязный список, составленный из четырёх ячеек, которые содержат элементы A, B, C и D.

 
Данные, необходимые для создания и обработки двусвязного списка , определяются с помощью описаний вида:

type AdresaCelula=^Celula;  Celula=record Info : string;  Urm, Prec : AdresaCelula; end;  var P, V : AdresaCelula;

 
Переменные ссылочного типа P и V запоминают соответственно адрес первой ячейки (базовый адрес) и адрес последней  ячейки (адрес вершины). 
Двусвязный список можно создать путём добавления в вершину списка по одному элементу. Сперва двусвязный список является пустым. 
 
К двусвязным спискам можно применять следующие операции: 
- проход по списку от базового элемента к вершине; 
- проход по списку от вершины к базовому элементу; 
- поиск элемента, заданного своим значением; 
- вставка элемента в список; 
- удаление элемента из списка; 
- упорядочивание элементов списка согласно заданному критерию; 
- склеивание списков; 
- разделение списка на несколько отдельных списков и т.д. 
Как и в случае односвязных списков, вставка и удаление элементов, склеивание и разделение списков заключаются в создании и удалении ячеек или соответствующих связей. 
      

 

 

 

 

 

 

 

 

 

 

 

Пример  программы на языке С++

#include"stdafx.h"

#include<iostream>

#include<stdlib.h>

using namespace std;

struct Node

{

int count;

Node *next, *prev;

};

typedef Node *PNode;

/*void Print(PNode &Head)

{

PNode p = Head;        //     

while ( p != NULL ) {  //      

//  -   p

   p = p->next;        //    

   cout<<p->count<<" ";

   }

}*/

PNode CreateNode ( int count )

{

   PNode NewNode = new Node; //    

   NewNode->count = count;             //   = 1

   NewNode->next = NULL;           //   

return NewNode;  //   –  

}

 

PNode Head = NULL, Tail = NULL;

void AddFirst(PNode &Head, PNode &Tail, PNode NewNode)

{

NewNode->next = Head;

NewNode->prev = NULL;

if ( Head ) Head->prev = NewNode;

Head = NewNode;

if (!Tail )Tail=Head;

}

void AddLast(PNode &Head, PNode &Tail, PNode NewNode)

{

NewNode->prev =Tail;

NewNode->next =NULL;

if (Tail) Tail->next = NewNode;

Tail= NewNode;

if (!Head )Head=Tail;

}

void AddAfter (PNode &Head, PNode &Tail,PNode p, PNode NewNode)

{

if(!p->next )

AddLast (Head, Tail, NewNode);

else {

NewNode->next = p->next;

NewNode->prev = p;

p->next->prev = NewNode;

p->next = NewNode;

}

}

void Delete(PNode &Head, PNode &Tail, PNode OldNode)

{

if (Head == OldNode)

{

Head = OldNode->next;

if ( Head )

Head->prev = NULL;

else Tail = NULL;

}

else {

OldNode->prev->next = OldNode->next;

if ( OldNode->next )

OldNode->next->prev = OldNode->prev;

else Tail = NULL;

}

delete OldNode;

}

PNode Find (PNode Head,  int a)

{

   PNode q = Head;

   while (q && (a!=q->count))

      q = q->next;

   return q;

}

void Print(PNode Tail)

{

PNode p = Tail;

while ( p ) {  // проход по списку и вывод результатов

     printf ( "%d\n", p->count );

     p = p->prev;

}

}

void main()

{int a,b,c;

PNode NewNode=new Node ;

PNode OldNode=NULL;

FILE *f;

f=fopen("input.txt","r+");

setlocale(LC_ALL,"Russian");

PNode Head = NULL, Tail = NULL,p, where;

while(1){

cout<<"меню:\n"<<"1.добавить первым\n"<<"2.добавить последним\n"<<"3.добавить после заданного\n"<<"4.удалить\n"<<"5.вывести список\n"<<"выберите действие"<<endl;

cin>>a;

switch(a){

case 1:

cout<<"введите данное"<<endl;

cin>>b;

p=CreateNode(b);

AddFirst(Head,Tail,p);

fprintf(f,"%d %d",b,p);

fprintf(f,"\n");

break;

case 2:

cout<<"введите данное"<<endl;

cin>>b;

NewNode=CreateNode(b);

AddLast(Head, Tail,NewNode) ;

fprintf(f,"%d %d",b,NewNode);

    fprintf(f,"\n");

    break;

case 3:

cout<<"введите данное после которого нужно добавить"<<endl;

cin>>b;

p=Find(Head,b);

cout<<"введите данное  которое нужно добавить"<<endl;

cin>>c;

NewNode=CreateNode(c);

AddAfter (Head, Tail, p,  NewNode) ;

//fprintf(f,"%d %d",b,NewNode);

  //  fprintf(f,"\n");

break;

case 4:

cout<<"введите данное которое надо удалить"<<endl;

cin>>b;

OldNode=Find(Head,b);

Delete(Head, Tail, OldNode) ;break;

 

case 5: Print(Tail);break;

default: cout<<"вы выбрали неверное действие!";

}

 

}

fclose(f);

}Сеанс работы

 

 

 

Деревья и их применение.

Введение.

       Деревья  – это математические абстракции, играющие главную роль при  разработке и анализе алгоритмов, поскольку

     - мы используем  деревья для описания динамических  свойств алгоритмов;

     - мы строим  и используем явные структуры  данных, которые являются конкретными  реализациями деревьев.

       Люди часто встречаются с деревьями в повседневной жизни – это основное понятие очень хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева. Еще один пример – организация спортивных турниров. В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа  «разделяй и властвуй». Четвертым примером служит дерево синтаксического разложения предложения английского  (или  любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков.

         Применительно к компьютерам,  одно из наиболее известных  применений структур деревьев  – для организации файловых  систем. Файлы хранятся в каталогах, которые рекурсивно определяются как в последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева.

          Существует множество различных  типов деревьев, и важно понимать  различие между абстракцией и  конкретным представлением, с которым  выполняется работа для данного  приложения.

Основные  понятия.

         Дерево – это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям.

        Вершина – это простой объект (называемый так же узлом), который может имеет имя и содержать другую связанную с ним информацию.

       Ребро – это связь между двумя вершинами.

        Путь в дереве – это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева.

       Лист дерева – это узел, не имеющий потомков или терминальными (оконечными, terminal) узлом.

       Внутренняя вершина – это узел, имеющий потомков.

       Высота дерева – это максимальный уровень листа дерева.

       Дерево с корнем – это дерево, в котором один узел назначен корнем дерева. В области компьютеров термин дерево обычно применяется к деревьям с корнем, а термин свободное дерево – к более общим структурам.Существует только один путь между корнем и каждым из других узлов дерева. Данное определение никак не определяет направление ребер; обычно считается, что все ребра указывают от корня или к корню, в зависимости от приложения.

    Упорядоченное дерево — это дерево с корнем, в котором определен порядок следования дочерних узлов каждого узла.

       М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-арными деревьями.

       Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.

      Определяющее свойство дерева – существование только одного пути, соединяющие любые два узла. Если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором.

Применение и  особенности деревьев

 Очень часто при решении задачи перед программистом возникает проблема выбора наиболее подходящей структуры данных, но чтобы сделать правильный выбор необходимо знать сильные и слабые стороны этих структур.