Таблица представляет собой одномерный массив (вектор), элементами которого являются записи. Отдельная запись массива называется строкой таблицы. Чаще всего

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

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

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

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

Объектом исследования являются структуры данных. Предметом исследования являются линейные и нелинейные структуры данных.

Цель работы – выявить особенности линейных и нелинейных структур данных.

Для достижения поставленной цели в работе были сформулированы следующие задачи:

- рассмотреть классификацию типов и структур данных;

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

- выявить особенности построения деревьев и графов.

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

1. Классификация типов и структур данных

Необходимо отметить, что дек является более универсальной структурой данных по сравнению с другими описанными в таблице 1, поскольку позволяет накладывать дополнительные ограничения на операции, а также с ним можно выполнять моделирование стека и очереди [8, cтр.106].

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

К нелинейным структурам данных относятся виды, приведенные на рисунке 2.

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

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

2. Линейные и нелинейные структуры данных

2.1 Стеки, очереди, деки и списки

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

Стек – это упорядоченный набор элементов, в котором добавление новых и удаление существующих элементов разрешено только с одного конца, который называется вершиной стека [1, cтр.180].

Стек называют структурой типа LIFO (Last In - First Out) последним пришел - первым ушел. Стек похож на стопку с подносами, уложенными один на другой – чтобы достать какой-то поднос необходимо снять все подносы, которые лежат на нем, а положить новый поднос можно только сверху всей стопки. На рисунке 3 изображен стек из 6 элементов.

Рисунок 3  Схематическое представление стека
В современных компьютерах стек используется: для размещения локальных переменных, параметров процедуры или функции или для сохранения адреса возврата (по какому адресу необходимо вернуться из процедуры), временного хранения данных.

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

Очередь - это упорядоченный набор элементов, в котором добавление новых элементов допустимо с конца очереди, а удаление существующих элементов – только с начала очереди [3, cтр.96].

Очередь называют структурой типа FIFO (First In - First Out) - первым пришел, первым ушел. Очередь проще всего представить себе в виде очереди в магазине. Как и стек, очередь можно реализовать с помощью массива или двусвязного списка.

Рисунок 4  Очередь
Для работы с очередью необходимо определить, как выполняются две операции – добавление элемента в конец очереди (Push Finish) и удаление элемента с начала очереди (Pop). Данные операции приведены в приложении 1.

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

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

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

Над списками можно выполнять следующие операции [7, cтр.180]:

- добавление элемента в конец списка;

- чтение элемента с заданным ключом;

- вставка элемента в заданное место списка;

- удаление элемента с заданным ключом;

- упорядочивание списка по ключу.

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

При добавлении нового узла New Unit в начало списка необходимо выполнить действия, приведенные на рисунке 5.

Рисунок 5  Добавление узла в начало списка
Как видно из рисунка 5, в данном случае необходимо установить ссылку узла New Unit на голову существующего списка, а также создать голову списка на новый узел.

Пример добавления узла после заданного значения приведен на рисунке 6.

Рисунок 6  Добавление узла после заданного
Как видно из рисунка 6, данная операция выполняется посредством установки ссылку нового узла на узел, следующий за данным узлом, а затем установки данного узла p на New Unit.

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

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

Рисунок 7  Удаление узла
Есть и другой способ упростить работу с односвязным списком - хранить в памяти указатель не только на следующий, но и на предыдущий элемент списка.

Рисунок 8  Структура двусвязного списка
Помимо значимых данных каждый узел списка содержит также ссылку на следующий за ним узел (поле next) и предыдущий (поле prev). Поле next у последнего элемента и поле prev у первого содержат NULL.

При добавлении нового узла New Unit в начало списка необходимо использовать последовательность, приведенную на рисунке 9.

Рисунок 9  Добавление элемента двусвязного списка
Как видно из рисунка 9 в данном случае вначале необходимо установить указатель next узла New Unit на голову существующего списка и его указатель prev в NULL. Далее нужно установить указатель prev бывшего первого узла (если он существовал) на New Unit. После этого установить голову списка на новый узел. Если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

Благодаря симметрии добавление нового узла New Unit в конец списка проходит совершенно аналогично, достаточно в указанной выше процедуре необходимо везде поменять местами Start на Finish, а также поменять prev и next.

Добавление элемента двусвязного списка после заданного приведено на рисунке 10.

Рисунок 10  Добавление элемента двусвязного списка после заданного
Как видно из рисунка 10 в данном случае необходимо установить ссылки нового узла на следующий за данным (next) и предшествующий ему (prev), а также установить ссылки соседних узлов так, чтобы включить New Unit в список.

Для удаления узла также требуются указатели на голову и хвост списка, поскольку они могут измениться при удалении крайнего элемента списка. На первом этапе устанавливаются ссылки соседних узлов (если они есть) так, как если бы удаляемого узла не было бы. Затем узел удаляется и память, которую он занимает, освобождается. Эти этапы показаны на рисунке 11.

Рисунок 11  Удаление элемента двусвязного списка
Иногда список (односвязный или двусвязный) замыкают в кольцо, то есть указатель next последнего элемента указывает на первый элемент, и (для двусвязных списков) указатель prev первого элемента указывает на последний.
2.2 Деревья, графы
Дерево – это совокупность узлов (вершин) и соединяющих их направленных ребер (дуг), причем в каждый узел, за исключением корня, ведет ровно одна дуга. Корень – это начальный узел дерева, в который не ведет ни одной дуги.

Например, генеалогическое дерево - в корне дерева находится человек, от него идет две дуги к его родителям, от каждого из родителей - две дуги к их родителям [5, cтр.48].

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

Рисунок 12  Пример дерева и не дерева
Предком для узла x называется узел дерева, из которого существует путь в узел x. Потомком узла x называется узел дерева, в который существует путь (по стрелкам) из узла x. Родителем для узла x называется узел дерева, из которого существует непосредственная дуга в узел x. Сыном узла x называется узел дерева, в который существует непосредственная дуга из узла x. Уровнем узла x называется длина пути (количество дуг) от корня к данному узлу. Считается, что корень находится на уровне 0.

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

Упорядоченным деревом называется дерево, все вершины которого упорядочены (то есть имеет значение последовательность перечисления потомков каждого узла).

Дерево представляет собой типичную рекурсивную структуру, которая определяет саму себя. Как и любое рекурсивное определение, определение дерева состоит из двух частей – первая определяет условие окончания рекурсии, а второе – механизм ее использования [1, cтр.46].

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

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

На рисунке 13 даны деревья, а) и б) являются строго двоичными, а в) и г) – нет.

Рисунок 13  Двоичные деревья
Полным двоичным деревом называется дерево, у которого все листья находятся на одном уровне и каждая внутренняя вершина имеет непустые левое и правое поддеревья. На рисунке выше только дерево а) является полным двоичным деревом.

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

Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами. Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер [5, cтр.67].

Граф, содержащий ребра между всеми парами вершин, является полным. Пример построения графа приведен на рисунке 14.

Рисунок 14 – Пример построения графа

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

Графы бывают связанными и не связанными. Примеры построения связанных и не связанных графов приведены на рисунке 15.

Заключение

В процессе написания работы были выявлены особенности линейных и нелинейных структур данных.

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

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

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

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

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

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

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

Было установлено, что в списке каждый элемент связан со следующим и, возможно, с предыдущим. В первом случае список называется односвязным, во втором - двусвязным. Также применяются термины однонаправленный и двунаправленный. Если последний элемент связать указателем с первым, получается циклический список. Количество элементов в списке может изменяться в процессе работы программы.

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

Дерево представляет собой типичную рекурсивную структуру, которая определяет саму себя. Как и любое рекурсивное определение, определение дерева состоит из двух частей – первая определяет условие окончания рекурсии, а второе – механизм ее использования.

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

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

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

Веками человечество накапливало знания, сведения об окружающем мире, т.е. собирало информацию. Вна­чале информация передавалась из поколения в поколение в виде преданий и устных рассказов. Возникновение и развитие книжного дела позволило передавать и хранить информацию в более надежном письменном виде. Открытия в области электричества привели к появлению телеграфа, теле­фона, радио, телевидения — средств, позволяющих оперативно передавать и накапливать информацию. Развитие прогресса обусловило резкий рост информации, в связи, с чем вопрос о её сохранении и переработке стано­вился год от года острее. С появлением вычислительной техники значи­тельно упростились способы хранения, а главное, обработки информации. Развитие вычислительной техники на базе микропроцессоров приводит к совершенствованию компьютеров и программного обеспечения. Появля­ются программы, способные обработать большие потоки информации. С их помощью создаются информационные системы. Целью любой информационной системы является обработка данных об объектах и явлениях реального мира и предоставление нужной человеку информации о них.

Практическая часть курсовой работы состоит из построения и анализа компьютерной модели решения задачи варианта 4.

Список используемой литературы

3) [endif]-->Модели и структуры данных: учебное пособие/ В. Д. Далека, А. С. Деревянко, О. Г. Кравец, Л. Е. Тимановская. - Харьков: ХГПУ, 2000г. - 241с.

4) [endif]-->Структуры и алгоритмы обработки данных: учебноепособие/Ключарев А. А., Матьяш В. А., Щекин С. В.- СПбГУАП.СПб., 2003г. - 172 с.

5) [endif]-->Алгоритмы и структуры данных: учебное пособие/ Л. Г. Гагарина, В. Д. Колдаев. – М.: Финансы и статистика; ИНФРА-М, 2009г. – 304с.

2.1 [endif]-->Постановка задачи

2.1.1 Цель решения задачи

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

2.1.2 Условие задачи

• 1) [endif]-->годовая процентная ставка;
• 2) [endif]-->срок выдачи кредита;
• 3) [endif]-->сумма кредита;
• 4) [endif]-->номер платежа;
• 5) [endif]-->дата платежа;
• 6) [endif]-->текущий остаток по кредиту; сумма процентов;
• 7) [endif]-->погашение основного долга;
• 8) [endif]-->платеж по кредиту.

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

Ведомость платежей по кредиту клиента К. В. Рыбиной банка "Акцепт +" за 2010г.

Читайте также:

  
• Реферат психологическая помощь в экстремальных ситуациях
  
• Законодательство третьего рейха реферат
  
• Ответственность в этике реферат
  
• Эмоция дегеніміз не реферат
  
• Взаимосвязь общения и деятельности реферат