Файл: Динамические структуры данных. Списки ( Структуры данных: понятие, типы и форматы).pdf

Рисунок 8 – Схема 2-связного списка

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

Указанное применение 2-х указателей для узлов значительно усложняет архитектуру списка, приводит также к разным дополнительным объемам памяти, обеспечивает выполнение всех команд, операций с обрабатываемой списочной структурой^[15].

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

При непосредственной работе с списочной структурой односвязного типа указатели последнего элемента часто указывают на первый элемент списка (рисунок 9)^[16].

Рисунок 9 – Описание циклических списков

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

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

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

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

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

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

Рисунок 11 – Пример графа

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

Рисунок 12 – Примеры графов

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

---

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

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

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

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

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

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

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

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

Рисунок 13 – Дерево

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

а) б)

Рисунок 14 – Примеры матриц смежности

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

ГЛАВА 2. РЕАЛИЗАЦИЯ ДИНАМИЧЕСКИХ СПИСКОВ
В С++

2.1 Односвязные списки в С++

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

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

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

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

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

---

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

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

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

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

Рисунок 15 – Размещение узлов списка

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

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

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

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

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

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

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

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

Рисунок 16 – Пример списка

2.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):

Рисунок 17 – Результат

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

ГЛАВА 3. ПЕРСПЕКТИВЫ РАЗВИТИЯ ОБЪЕКТНО-
ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ

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

1. Стремление к совершенству;

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

1. Нацеленность на эффективность;

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

---

1. Повышение сложности задач;

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

1. Продление жизненного цикла ПО;

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

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

Одним из первых ЯП является Фортран (FormulaTranslation). Созданный в 50-х годах прошлого века, он по-прежнему остается актуальным. Столь завидное долголетие языку во многом обеспечили простота и накопление значительного объема данных.

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

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

К появлению, без преувеличения, наиболее используемого и востребованного ЯП современности, привело стремление разработчиков создавать программы, которые не зависели бы от типа компьютера и операционной системы. Java не только отвечает за выполнение программ, которые распространяются посредством Web-страниц, но и поддерживает все средства новых ИТ. 

Сочетая в себе языки С и С++, Java объективно является наиболее мощным инструментом для создания кроссплатформенных приложений. Можно сказать, что принцип его работы заключен в выражении: «Write Once, Run Anywhere».Согласно данным TIOBE ЯП Java стал самым популярным в 2015 году.

Несмотря на все отличия и субъективные особенности языков Fortran и Java, оба они являются результатом эволюционных процессов, сотрясающих мир программирования. Эти языки продолжают решать сложнейшие задачи, остаются востребованными и продолжают развиваться. Что будет дальше посмотрим, ведь эволюция – естественный процесс, предотвратить который невозможно.

---