Файл: Способы организации данных: пользовательский тип данных - структура ( Понятие о программировании и структурировании данных).pdf

2.2.Нелинейные динамические структуры

Нелинейным разветвляющимся списком называют такой динамический список, узлами у которого являются уже созданные ранее списки (рисунок 10) [13].

Рис.10. Схема нелинейного разветвленного списка

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

Граф – совокупность узлов (или вершин) и соединяющих их дуг (ребер).

Если дуги являются направленными, то такой граф называют ориентированным или направленным графом (орграфом) (рисунок 11) [2].

Рис.11. Пример графа

На рисунке 12, показаны несколько примеров самых простейших графов:

Рис.12. Примеры графов

При определении структуры ориентированного графа общее количество его ребер, входящих практически в любой с узлов, называют входной полустепенью, выходящих – выходной полустепенью. [17]

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

Граф является связным, если в нем существует цепь между всеми парами вершин.

Если же граф не связный, его можно разбивать на k связных элементов – в таком случае называется k-связным.

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

Такой граф является сетью.

Циклом называют цепь с какой-нибудь вершины в нее саму.

Стоит отметить, что дерево – это граф, характеризующийся такими свойствами:[19]

1. Существует один единственный узел, на который не ссылаются иные элементы – корень (рисунок 13).

Рис.13. Дерево

2.Начиная с корневого элемента, следуя по определенной последовательности, можно качественно осуществлять доступ практически к всем элементам.

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

а) б)

Рис.14. Примеры матриц смежности

Во второй главе исследования рассмотрены понятия и виды динамических структур данных, приведены отличительные их свойства, определения нелинейных структур.

3. ИСПОЛЬЗОВАНИЕ ЯЗЫКА ВЫСОКОГО УРОВНЯ ДЛЯ РЕАЛИЗАЦИИ ДИНАМИЧЕСКИХ СТРУКТУР

3.1. Пример реализации структур в С++ – односвязные списки

Рассмотрим далее списковые динамические структуры и их обработку в С++.

Как было ранее указано, список – динамическая структура данных, где несколько полей являются адресом (ссылкой, указателем) на иные структуры аналогичного типа.[19]

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

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

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

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

Элементы динамических списков часто располагаются в памяти несколько хаотично.

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

Список, который имеет разные числовые значения в памяти можно расположить так (рисунок 14) [17]:

Рис.14. Размещение узлов списка

Стрелки на рисунке 13 указывают последовательность размещения элементов.

Для выполнения работы с узлами списка так, как и в любой связной структуре данных, надо выполнить определение места нахождения требуемого элемента. [1]

В этом случае часто хранят только адреса (указатели) первого элемента (first).

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

Заметим, что к всем элементам можно легко добраться, начиная с самого первого и т.д.

В приведенном выше рисунке 14 элемент, имеющий значение 1 может «направить» нас на место, где размещен узел со значением 8 и т.д.

Чтобы «найти» элемент, который имеет значение 1, надо обратится к первому элементу (4), узнать адрес следующего (-5), потом узнать остальные адреса.

Наглядно списки изображены таким образом (рисунок 15):

Рис.15. Пример списка

3.2. Операции с элементами динамической структуры в С++

Рассмотрим пример с описанием основных операций и функции для обработки линейного односвязного списка.

//заголовочные файлы

#include <conio.h>

#include <iostream>

//объявление пространства имен

using namespace std;

//оглашение структуры ls

struct ls

{

int dat;

ls *next;

};

//описание указателей

ls * last, *first;

//функция, выполняющая просмотр списка

void print_ls()

{

ls *s=first;

cout<<"List: ";

while(s!=0)

{

cout<<s->dat<<"_";

s=s->next;

}

cout<<endl;

}

// добавления узлов в конец динамического списка

void a_end(int y)

{

ls *s=new ls;

s->dat=y;

c->next=NULL;

//проверка наличия первого элемента

if(first==0)

first=s;

else

last->next = s;

last = s;

}

//функция для добавления узлов в начало

void a_beg(int y)

{

ls *s=new ls;

s->dat=x;

s->next=0;

//наличние первого элемента

if(first==0)

{

first=s;

last=s;

}

else

s->next = first;

first = s;

}

// добавление узлов в середину линейного списка

void a_mid(int u, int y)

{

ls *s=new ls;

ls *s1;

s->dat=y;

s->next=0;

if(first==0)

first=s;

else

{

s1=first;

while(s1!=0)

{

if (s1->dat==u)

{

s->next=s1->next;

s1->next=s;

}

s1=s1->next;

}

}

}

// удаление элементов в начале списка

void d_beg()

{

ls *s=first;

first=first->next;

delete s;

}

// удаление элементов с конца

void d_end()

{

ls *s=first;

ls *s1;

while (s->next!=last)

s=s->next;

last=s;

s1=last->next;

delete s1;

s->next=0;

}

//

int main()

{

int y,N;

cout<<"N = ";

cin>>N;

cout<<"List: ";

for(int j=0;j<N;j++)

{

cin>>y;

a_beg(y);

}

//Вызов пользовательских функций

// добавление элементов в середину линейного списка

a_mid(3,11);

//печать

print_list();

// удаление элементов в начале списка

d_beg();

//печать

print_list();

// удаление элементов с конца

d_end();

{

//печать

getch();

print_list();

return 0;

}

}

Получим (рисунок 16):

Рис.16. Результат

При написании последней части курсовой работы на практике было рассмотрено все операции для выполнения обработки структуры –односвязного списка.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

В курсовой работе решены следующие задачи:

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

– выполнен анализ принципов обработки структур;

– дана характеристика нелинейным структурам;

– рассмотрены односвязные динамические списки в С++;

– выполнена реализация основных алгоритмов по работе со структурами на практике.

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