Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Линейные и нелинейные структуры




 

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

 

Различают линейные и нелинейные структуры.

К линейным структурам относятся:

§ массив;

§ таблица,

§ стек.

 

Массив - упорядоченная структура однотипных данных. Упорядоченность определяется тем, что отдельные элементы массива обозначаются упорядоченной совокупностью натуральных чисел n, называемых индексами. Число n называется размерностью массива.

 

Одномерный массив (линейная таблица) - массив, элементами которого являются атомарные переменные, например, одномерный массив вещественных чисел (рис.4.2.1). Элементы массива записаны в ячейках таблицы. Над ячейками проставлены индексы.

 

 

                   
  -3     -2   -6      

 

 

Рис. 4.2.1. Одномерный массив

 

Список допустимых действий над массивом:

o создать массив;

o присвоить значение элементу массива;

o запросить значение элемента массива.

 

Массив, элементами которого являются одномерные массивы, называется двумерным массивом. В данном случае размерностью массива будет количество строк - например, n, количество столбцов - количество элементов в строке - например, m.

 

 

           
          -2
           
           
           
           

 

Рис. 4.2.2. Двумерный массив

 

Изображенный на рис. 4.2.2 двумерный массив имеет n=3 строк и m=5 столбцов.

 

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

 

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

 

В программировании применяется сравнительно большое количество таблиц различного назначения. Особой разновидностью таблиц являются так называемые хеш-таблицы.

 

Хеш-таблица — это структура данных, обеспечивающая хранение пар (ключ, значение), что позволяет выполнять операции:

§ добавления новой пары;

§ поиска;

§ удаления пары по ключу.

 

Простейшим примером хеш-функций может служить контрольная сумма.

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

 

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

 

Хеш –таблицы используются для ускорения поиска данных в сложных структурах.

 

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

 

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»).

 

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

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

 

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

 

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

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

 

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

 

 

Вход Выход

 

           
   
 
 
   
 

 

 


Рис. 4.2.3. Стек

 

О́чередь — структура данных с порядком доступа к элементам FIFO (First In — First Out) - «первый пришёл — первый вышел»).

Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди.

 

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

 

 

 


Рис. 4.2.4. Очередь.

 

 

К нелинейным структурам относятся:

§ связные списки;

§ графы;

§ деревья.

 

 

С вя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле.

 

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

 

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

 

 

 


Рис. 4.2.5. Связный список

 

 




Поделиться с друзьями:


Дата добавления: 2014-12-10; Просмотров: 1927; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.