Динамические структуры данных

Глава 1. Списки, стеки, очереди

Графическая иллюстрация метода наименьших квадратов (мнк).

Оценка погрешности метода наименьших квадратов.

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

Так как , то прямая y = 0.165x+2.184 лучше приближает исходные данные.

На графиках все прекрасно видно. Красная линия – это найденная прямая y = 0.165x+2.184, синяя линия – это , розовые точки – это исходные данные.

Для чего это нужно, к чему все эти аппроксимации?

Я лично использую для решения задач сглаживания данных, задач интерполяции и экстраполяции (в исходном примере могли бы попросить найти занчение наблюдаемой величины y при x=3 или при x=6 по методу МНК). Но подробнее поговорим об этом позже в другом разделе сайта.

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

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

Элементарным, неструктурированным оператором является оператор присваивания. Ему соответствует скалярный тип данных. Оба они являются простейшими строительными блоками для составных операторов и типов данных. Простейшие структуры, получаемые с помощью перечисления, или следования, – это составной оператор и структура. Оба состоят из небольшого количества компонент, которые могут различаться. Если все компоненты одинаковы, их не нужно выписывать отдельно: для того, чтобы описать повторения, число которых известно и конечно, пользуются оператором цикла с параметром for и массивом. Выбор из двух или более вариантов выражается операторами if или swith и соответственно записью с вариантами. И, наконец, повторение неизвестное количество раз выражается оператором цикла с предусловием while или с постусловием do. Соответствующая структура данных – последовательность (файл).

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

Таблица 1.

Аналогии между методами структурирования алгоритмов и методами структурирования данных

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

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

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

Листинг 8.1. Рекурсивный класс узла

class MyNode

{

public int inf;

public MyNode next;

public MyNode(int inf, MyNode next)

// конструктор

{

this.inf = inf;

this.next = next;

}

}

В этом классе определены два поля: поле inf, которое содержит информацию и может быть любого типа; поле next того же самого типа что и сам узел. То есть поле next показывает на такой же элемент, что и сам узел. Конструктор MyNode() принимает значения полей.

На основе этого класса создадим класс динамического списка MyList, который содержит два поля: поле head всегда показывающее на начало списка и поле count, содержащее информацию о количестве элементов списка.

Листинг 8.2. Класс динамического списка

class MyList

{

public MyNode head; // голова списка

public int count; // число элементов

public MyList() // Конструктор

public void Add(int inf) // Add

public void Printer() // Вывод списка

public MyNode FindNode(int val)// Поиск узла

public void Delete(int index)

//Удалить по индексу

public void Insert(int index, int val)

// Вставить по индексу

public void AddSort(int inf)

}

Список элементов показан на рис. 8.1.

Рис. 8.1. Линейный список

Кроме этого классMyList содержит некоторое количество методов.

Конструктор MyList()обнуляет число элементов count и направляет голову head на null:

Листинг 8.3. Конструктор

public MyList() // Конструктор

{

head = null;

count = 0;

}

Метод Add() создает новый элемент p, у которого поле next показывает на head, перемещает head на p и увеличивает count.

Листинг 8.4. Метод Add()

public void Add(int inf) // Add

{

MyNode p = new MyNode(inf, head);

head = p;

count++;

}

Метод Printer()ставит p на начало списка head, выводит на экран p.inf и перемещает p на следующий элемент.

Листинг 8.5. Метод Printer()

public void Printer() // Вывод списка

{

MyNode p = head;

Дата добавления: 2014-03-11; просмотров: 427; Нарушение авторских прав

Мы поможем в написании ваших работ!