Реферат на тему структуры данных
Обновлено: 04.07.2024
При разработке программ и алгоритмов важным этапом является этап подбора математической абстракции для описания данных, используемых в формулировке задачи. Например, в случае поиска оптимальной стратегии для игры чет-нечет таким объектом была игра, в случае задачи об Ариадне и Тезее - лабиринт, в задаче о ходе коня - шахматная доска, в примере из лекции 16 - учреждение. Будем называть предстваление этих объектов-данных ввиде математических абстракций Абстрактными Структурами Данных (АСД). В случае игры в качестве АСД мы использовали дерево; в случае лабиринта - граф; в случае шахматной доски - матрицу.
Выбрав подходящую по своим математическим свойствам структуру АСД, мы приходим к другой проблеме - как представить выбранную АСД в терминах тех структур данных, с которыми умеет работать исполнитель алгоритмов, которые есть в испоьзуемом языке программирования. Назовем эти струтктуры данных Структурами Данных Хранения (СДХ). Например, в случае задачи об Ариадне и Тезее мы представили граф, представляющий лабиринт, в виде матрицы смежности, которую мы представили в виде соотвествующей СДХ - массива, для шахматной доски мы применили ту же структуру данных для хранения данных задачи, для учреждения - мы использовали запись.
Критерием выбора для АСД подходящей СДХ является эффективность операций над СДХ, являющихся аналогами соотвествующих операций над АСД. Под эффективностью мы понимаем сложность алгоритмов над СДХ.
Итак, мы приходим к следующей проблеме: задано АСД, набор СДХ; требуется построить отображение АСД -> СДХ так, чтобы сложность алгоритмов операций над СДХ, соотвествующих надлежащим оперциям над АСД, была бы минимальной.
Бесплатно скачать реферат "Структуры данных" в полном объеме
Поиск рефератов по алфавиту
2. Реферат: Структура центральной нервной системы и общие принципы её функционирования
Центральная нервная система включает головной и спинной мозг, выполняющие в организме человека и животных сложнейшие функции. Функции центральной нервной системы. 1. Центральна.
3. Реферат: Структура экосистем
Экосистемы состоят из живого и неживого компонентов, называемых соответственно биотическим и абиотическим. Совокупность живых организмов биотического компонента называется сообщест.
4. Реферат: Структурированные компьютерные сети
Сеть всегда объединяет несколько абонентов, каждый из которых имеет право передавать свои пакеты. Но по одному кабелю не может одновременно передаваться два пакета, иначе возможен .
5. Реферат: Структурне програмування
За часів стихійного програмування хорошими програмістами вважали тих, хто створював досить хитромудрі програми, які займали мінімум часу та пам’яті при виконанні. Це було цілком пр.
6. Реферат: Структурно-семантична організація побутової лексики слобожанської говірки
Одним із першочергових завдань сучасної української діалектології є системне вивчення структурно-семантичної організації діалектів на всій етномовній території або на частині цієї .
7. Реферат: Структурное программирование
Традиционная технология программирования формировалась на заре вычислительной техники, когда в распоряжении пользователей были ограниченные ресурсы ЭВМ, а разработчик программ был .
8. Реферат: Структурные компоненты клетки
Термин "ядро" (лат. nucleus) впервые применил Р. Броун в 1833 году, когда описывал шарообразные структуры, наблюдаемые им в клетках растений. Ядерная оболочка. Внутреннее простран.
9. Реферат: Структурные кризисы: сущность и последствия
Проблема цикличности экономики за более чем вековую историю её существования стала средоточием для исследования многих факторов, оказывающих наиболее существенное влияние на развит.
10. Реферат: Структурный функционализм
Теория функционализма Мертона состоит как бы из двух взаимосвязанных аспектов: критического и творчески-новаторского. Мертон считает неверным применение трех .
11. Реферат: Структуры данных
При разработке программ и алгоритмов важным этапом является этап подбора математической абстракции для описания данных, используемых в формулировке задачи. Например, в случае поиск.
13. Реферат: Субкультура как фактор социализации
В культурологии проблема субкультуры рассматривается, как правило, в рамках концепции социализации. Предполагается, что приобщение к культурным стандартам, вхождение в мир господст.
14. Реферат: Субординація та повага: як знайти "золоту середину"
Відповідно до визначення, службовий етикет - система особистісних взаємин керівника з підлеглими, вищими керівниками та колегами, визначальним принципом якої є співробітництво та в.
15. Реферат: Субъекты и объекты социальной работы
Необходима помощь сегодня, сейчас, когда всем так трудно. Трудно по разным причинам. Многие оказались в результате реформ за той социальной чертой, когда вопрос о хлебе.
16. Реферат: Субъекты международных экономических отношений
Для современной мировой экономики характерен стремительно идущий процесс транснационализации. В этом процессе основной движущей силой выступают транснациональные корпорации (ТНК). .
17. Реферат: Субъекты права
Субъектами права являются индивиды или организации, которые на основании юридических норм могут быть участниками правоотношений, т. е. носителями субъективных прав и обязанностей. .
18. Реферат: Суворов А.В. его жизнь и военная деятельность
В ряду русских замечательных людей Александр Васильевич Суворов очень резко выделяется во всех отношениях. Особенно ярко и внушительно проявилось это в возвышении Суворова, заурядн.
19. Реферат: Судетский кризис
Немецкая национальная проблема в Чехословакии была одной из главных проблем, стоявших перед международным социал-демократическим движением в 1920-е гг. Она занимала важное место в .
20. Реферат: Судимость несовершеннолетних
Преступление - это социальное зло, а преступность несовершеннолетних - зло, увеличенное во много раз. И хотя процент осужденных судами несовершеннолетних в сравнении со взрослым.
21. Реферат: Судова влада в Україні
Про принципи судочинства ми можемо говорити на підставі Конституції України. Отже, найважливіші принципи судоустрою: 1. здійснення правосуддя виключно судами 2. поширення юрисд.
Актуальность выбранной темы исследования заключается в том, что типы и структуры данных составляют фундамент, на основе которого строится вся современная технология программирования.
Понятие структуры данных можно определить следующим образом - это некоторая программная единица, дающая возможность хранить и обрабатывать множество однотипных и/или логически связанных данных. При этом реализуется возможность добавления, поиска, изменения и удаления данных в множестве посредством набора функций. Структуры данных формируются с помощью типов данных, ссылок и операций над ними в конкретном языке программирования.
Различные виды структур данных подходят для различных приложений, при этом часть из них имеют узкую специализацию для определённых задач. Фундаментальными блоками для большей части структур данных являются массивы, записи, размеченные объединения и указатели.
Объектом исследования являются структуры данных. Предметом исследования являются линейные и нелинейные структуры данных.
Цель работы – выявить особенности линейных и нелинейных структур данных.
Для достижения поставленной цели в работе были сформулированы следующие задачи:
- рассмотреть классификацию типов и структур данных;
- проанализировать особенности построения стеков, очередей, деков и список данных;
- выявить особенности построения деревьев и графов.
Вопросы исследования линейных и нелинейных структур данных постоянно обсуждаются отечественными и зарубежными специалистами, среди которых следует отметить работы
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.
Заключение
В процессе написания работы были выявлены особенности линейных и нелинейных структур данных.
На первоначальном этапе была рассмотрена классификация типов и структур данных и установлено, что по категориям типов данных выделяют встроенные, перечисляемые, конструируемые, указательные типы данных и типы данных определяемые пользователем.
В структуре данных выделяют простые базовые, статистические, полустатистические, динамические и файловые структуры данных. Также существует классификация с выделением линейных и нелинейных структур данных.
К линейным структурам данных относятся массив, строка, запись, множество, таблица, список, стек, разреженные матрицы, очередь и дек. К нелинейным структурам данных относятся мультисписок, разделенные списки, граф и дерево.
В работе более детально были рассмотрены стеки, очереди, деки и списки. Было установлено, что стек, дек и очередь представляют собой частные случаи односвязных списков, для которых определен только операции добавления/удаления элементов только из начала или конца списка.
Стек выступает упорядоченным набором элементов, в котором добавление новых и удаление существующих элементов разрешено только с одного конца, который называется вершиной стека.
Очередь выступает упорядоченным набором элементов, в котором добавление новых элементов допустимо с конца очереди, а удаление существующих элементов – только с начала очереди.
В свою очередь дек выступает упорядоченным набором элементов, в котором добавление новых и удаление существующих элементов допустимо с любого конца.
Было установлено, что в списке каждый элемент связан со следующим и, возможно, с предыдущим. В первом случае список называется односвязным, во втором - двусвязным. Также применяются термины однонаправленный и двунаправленный. Если последний элемент связать указателем с первым, получается циклический список. Количество элементов в списке может изменяться в процессе работы программы.
Дерево является совокупностью узлов (вершин) и соединяющих их направленных ребер (дуг), причем в каждый узел, за исключением корня, ведет ровно одна дуга. Корень – это начальный узел дерева, в который не ведет ни одной дуги.
Дерево представляет собой типичную рекурсивную структуру, которая определяет саму себя. Как и любое рекурсивное определение, определение дерева состоит из двух частей – первая определяет условие окончания рекурсии, а второе – механизм ее использования.
Анализ показал, что на практике главным образом применяются деревья особого вида, называемые двоичными или бинарными. Двоичным деревом называется дерево, каждый узел которого имеет не более двух сыновей.
Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами. Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.
В ориентированном графе ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами. В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях. Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.
Бинарное дерево, простой пример ветвящейся связной структуры данных.
Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Абстрактный тип данных;
Реализация какого-либо абстрактного типа данных;
Экземпляр типа данных, например, конкретный список;
В контексте функционального программирования — уникальная единица (англ. unique identity), сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.
Структуры данных формируются с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.
Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.
Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов (STL) языка C++.
Основные структуры данных
Работа с большими наборами данных автоматизируется проще, когда данные упорядочены, то есть образуют заданную структуру. Существует три основных типа структур данных: линейная, иерархическая и табличная. Их можно рассмотреть на примере обычной книги.
Если разобрать книгу на отдельные листы и перемешать их, книга потеряет свое назначение. Она по-прежнему будет представлять набор данных, но подобрать адекватный метод для получения из нее информации весьма непросто. (Еще хуже дело будет обстоять, если из книги вырезать каждую букву отдельно — в этом случае вряд ли вообще найдется адекватный метод для ее прочтения.)
Если же собрать все листы книги в правильной последовательности, мы получим простейшую структуру данных — линейную. Такую книгу уже можно читать, хотя для поиска нужных данных ее придется прочитать подряд, начиная с самого начала, что не всегда удобно.
Для быстрого поиска данных существует иерархическая структура. Так, например, книги разбивают на части, разделы, главы, параграфы и т. п. Элементы структуры более низкого уровня входят в элементы структуры более высокого уровня: разделы состоят из глав, главы из параграфов и т. д.
Линейные структуры (списки данных, векторы данных)
При создании любой структуры данных надо решить два вопроса: как разделять элементы данных между собой и как разыскивать нужные элементы. В журнале посещаемости, например, это решается так: каждый новый элемент списка заносится с новой строки, то есть разделителем является конец строки. Тогда нужный элемент можно разыскать по номеру строки.
N п/п Фамилия, Имя, Отчество
1 Аистов Александр Алексеевич
2 Бобров Борис Борисович
3 Воробьева Валентина Владиславовна
27 Сорокин Сергей Семенович
Разделителем может быть и какой-нибудь специальный символ. Нам хорошо известны разделители между словами — это пробелы. В русском и во многих европейских языках общепринятым разделителем предложений является точка.
Аистов Александр Алексеевич * Бобров Борис Борисович * Воробьева Валентина Владиславовна *. * Сорокин Сергей Семенович
В этом случае для розыска элемента с номером n надо просмотреть список, начиная с самого начала и пересчитать встретившиеся разделители. Когда будет отсчитано n - 1 разделителей, начнется нужный элемент. Он закончится, когда будет встречен следующий разделитель.
Таким образом, линейные структуры данных (списки) — это упорядоченные структуры, в которых адрес элемента однозначно определяется его номером.
Табличные структуры (таблицы данных, матрицы данных)
С таблицами данных мы тоже хорошо знакомы, достаточно вспомнить всем известную таблицу умножения. Табличные структуры отличаются от списочных тем, что элементы данных определяются адресом ячейки, который состоит не из одного параметра, как в списках, а из нескольких. Для таблицы умножения, например, адрес ячейки определяется номерами строки и столбца. Нужная ячейка находится на их пересечении, а элемент выбирается из ячейки.
При хранении табличных данных количество разделителей должно быть больше, чем для данных, имеющих структуру списка. Например, когда таблицы печатают в книгах, строки и столбцы разделяют графическими элементами — линиями вертикальной и горизонтальной разметки:
Расстояние до Солнца, а.е.
Рис. 1.4. В двумерных таблицах, которые печатают в книгах, применяется два типа разделителей — вертикальные и горизонтальные
Если нужно сохранить таблицу в виде длинной символьной строки, используют один символ-разделитель между элементами, принадлежащими одной строке, и другой разделитель для отделения строк, например так:
Для розыска элемента, имеющего адрес ячейки (m,n), надо просмотреть набор данных с самого начала и пересчитать внешние разделители. Когда будет отсчитан m-1 разделитель, надо пересчитывать внутренние разделители. После того как будет найден n-1 разделитель, начнется нужный элемент. Он закончится, когда будет встречен любой очередной разделитель.
Таким образом, табличные структуры данных (матрицы) — это упорядоченные структуры, в которых адрес элемента определяется номером строки и номером столбца, на пересечении которых находится ячейка, содержащая искомый элемент.
Иерархические структуры данных
Нерегулярные данные, которые трудно представить в виде списка или таблицы, часто представляют в виде иерархических структур. С подобными структурами мы очень хорошо знакомы по обыденной жизни. Иерархическую структуру имеет система почтовых адресов. Подобные структуры также широко применяют в научных систематизациях и всевозможных классификациях
Упорядочение структур данных
Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка) или двумя числами (для двумерной таблицы). Они также легко упорядочиваются. Основным методом упорядочения является сортировка. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра.
Несмотря на многочисленные удобства, у простых структур данных есть и недостаток — их трудно обновлять. Если, например, перевести студента из одной группы в другую, изменения надо вносить сразу в два журнала посещаемости; при этом в обоих журналах будет нарушена списочная структура. Если переведенного студента вписать в конец списка группы, нарушится упорядочение по алфавиту, а если его вписать в соответствии с алфавитом, то изменятся порядковые номера всех студентов, которые следуют за ним.
Таким образом, при добавлении произвольного элемента в упорядоченную структуру списка может происходить изменение адресных данных у других элементов. В журналах успеваемости это пережить нетрудно, но в системах, выполняющих автоматическую обработку данных, нужны специальные методы для решения этой проблемы.
Иерархические структуры данных по форме сложнее, чем линейные и табличные, но они не создают проблем с обновлением данных. Их легко развивать путем создания новых уровней. Даже если в учебном заведении будет создан новый факультет, это никак не отразится на пути доступа к сведениям об учащихся прочих факультетов.
Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т. п.
Файлы и файловая структура
Единицы представления данных – двоичная система, десятичная система. Единицы измерения данных – байт, Кбайт и т.д.
Единицы хранения данных
В качестве единицы хранения данных принят объект переменной длины, называемый файлом. Файл — это последовательность произвольного числа байтов, обладающая уникальным собственным именем. Обычно в отдельном файле хранят данные, относящиеся к одному типу. В этом случае тип данных определяет тип файла.
Поскольку в определении файла нет ограничений на размер, можно представить себе файл, имеющий 0 байтов (пустой файл), и файл, имеющий любое число байтов.
Понятие о файловой структуре
Требование уникальности имени файла очевидно — без этого невозможно гарантировать однозначность доступа к данным. В средствах вычислительной техники требование уникальности имени обеспечивается автоматически — создать файл с именем, тождественным уже имеющемуся, не может ни пользователь, ни автоматика.
Уникальность имени файла обеспечивается тем, что полным именем файла считается собственное имя файла вместе с путем доступа к нему. Понятно, что в этом случае на одном носителе не может быть двух файлов с тождественными полными именами.
Пример записи полного имени файла:
Вот пример записи двух файлов, имеющих одинаковое собственное имя и размещенных на одном носителе, но отличающихся путем доступа, то есть полным именем. Для наглядности имена каталогов (папок) напечатаны прописными буквами.
Актуальность темы в том, что с появлением вычислительной техники значи¬тельно упростились способы хранения, а главное, обработки информации. Развитие вычислительной техники на базе микропроцессоров приводит к совершенствованию компьютеров и программного обеспечения. Появля¬ются программы, способные обработать большие потоки информации. С помощью таких программ создаются информационные системы. Целью любой информационной системы является обработка данных об объектах и явлениях реального мира и предоставление нужной человеку информа¬ции о них.
Содержание
Введение 3
1. Информация и данные 4
2. Классификация структур данных 5
3. Характеристики основных типовых структур 8
3.1 Линейные и нелинейные. ……………………………………………. 8
3.2 Списковые структуры данных 10
3.3 Древовидные (иерархические) структуры данных…………….…….12
3.4 Сетевые структуры данных. ………………………………..…………13
3.5 Табличные структуры данных……………………………………..…..13
Заключение 15
ПРАКТИЧЕСКАЯ ЧАСТЬ
Работа содержит 1 файл
ИНФОРМАТИКА ГОТОВА.docx
1. Информация и данные 4
2. Классификация структур данных 5
3. Характеристики основных типовых структур 8
3.1 Линейные и нелинейные. ……………… ……………………………. 8
3.2 Списковые структуры данных 10
3.3 Древовидные (иерархические) структуры данных…………….…….12
3.4 Сетевые структуры данных. ………………………………..…………13
3.5 Табличные структуры данных……………………………………..…..13
Список использованной литературы
Введение.
Актуальность темы в том, что с появлением вычислительной техники значительно упростились способы хранения, а главное, обработки информации. Развитие вычислительной техники на базе микропроцессоров приводит к совершенствованию компьютеров и программного обеспечения. Появляются программы, способные обработать большие потоки информации. С помощью таких программ создаются информационные системы. Целью любой информационной системы является обработка данных об объектах и явлениях реального мира и предоставление нужной человеку информации о них.
Цель курсовой работы: рассмотреть основные структуры данных.
Задачи курсовой работы:
1. Информация и данные
Виды форм представления информации:
- По способу отображения: символьная (знаки, цифры, буквы); графическая (изображения); текстовая (набор букв, цифр) и звуковая.
- По месту появления: внутренняя (выходная) и внешняя (входная).
- По стабильности: постоянная и переменная.
- По стадии обработки: первичная и вторичная. 1
Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе понятия "структуры данного". 2
2. Классификация структур данных
Структуры данных служат материалами, из которых строятся программы. Как правило, данные имеют форму чисел, букв, текстов, символов и более сложных структур типа последовательностей, списков и деревьев.
Для точного описания абстрактных структур данных и алгоритмов программ используются такие системы формальных обозначений, называемые языками программирования, в которых смысл всякого предложения определяется точно и однозначно. Среди средств, представляемых почти всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем. Выбор правильного представления данных служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Вряд ли когда-нибудь появится общая теория выбора структур данных. Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, направления которой соответствуют различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам.
Физическая структура данных отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета её представления в машинной памяти называется абстрактной или логической структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и наоборот. Эти процедуры обеспечивают доступ к физическим структурам и выполнение над ними различных операций.
Различаются простые (базовые, примитивные) структуры (типы) данных и интегрированные (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).
Весьма важный признак структуры данных - её изменчивость - изменение числа элементов или связей между элементами структуры. По признаку изменчивости различают структуры статические, полустатические и динамические. Классификация структур данных по признаку изменчивости приведена на рис. 1.
Рис. 1. Классификация структур данных
Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.
Второй важный признак структуры данных - характер упорядоченности её элементов. По этому признаку структуры можно делить на линейные и нелинейные структуры. 3 В зависимости от характера взаимного расположения элементов в памяти, линейные структуры можно разделить на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.
В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет:
1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;
2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
3) множество допустимых операций, которые применимы к объекту описываемого типа. 4
Читайте также: