Основные структуры данных

Оглавление

Введение………………………………………………………………………..3                                                                                                   

1. Теоретическая часть…………………………………..………………..…4     

Введение………………………………………………………………………..4          

1.1. Классификация структур данных ……………………………….....……5               

1.2. Характеристики основных типовых структур ……………………….…6

Заключение ………………………….………………………………………..13

2. Практическая часть……………………………….……………………..15

2.1. Общая характеристика задачи……………………………..……………15

2.2. Описание алгоритма решения задачи ……………………………….....17

Список  использованной литературы……………………………………….22 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

    Для  выполнения курсовой работы по  предмету «Информатика» - для  теоретической части была выбрана  тема «Основные структуры данных»  и раскрыта следующими вопросами:

-введение (по  данной теме);

-классификация  структур данных;

-характеристики  основных типовых структур;

-заключение.

    Для  практической части задача вариант  - №6 «ООО Снежок». Которая решена  при помощи программы MS Excel.

    Характеристика  ПК использованного для выполнения  работы:

монитор 19”Samsung 971P (XXFV),LCD, 1280 x 1024

клавиатура Genius

мышь Genius

принтер Hewlett Packard LaserJet

системный блок IS Mechanics (материнская плата asus,процессор intel).

    Системное обеспечение Windows XP. 
 
 
 
 
 
 
 
 
 
 
 
 

1. Теоретическая часть

Введение

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

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

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

• списковые;

• древовидные  или иерархические;

• сетевые;

• табличные. 
 
 
 
 
 
 
 
 
 

1.1. Классификация структур данных

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

        Структуры можно классифицировать:                                                                - по способам размещения в памяти и связанными с ними способами организации служебной информации;                                                                                       по реализуемым при хранении логическим отношениям на множестве данных;                                                                                                                          - по способам организации служебной информации о структуре данных (т.е. по структуре информации о структуре), и т.п. Однако, единой красивой классификации всей совокупности различных структур не получается. Поэтому более продуктивно рассматривать некоторые базовые типовые структуры, которые могут компоноваться и сочетаться в различных гибридных комбинациях. Состав таких типовых структур иллюстрируется схемой[2,С. 71](рис.1):

      
 
 
 
 
 
 
 

    Рис.1. Структуры данных 

1.2. Характеристики основных типовых структур

Линейные  и нелинейные

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

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

физически последовательные структуры, или просто последовательные структуры данных (ПДС);

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

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

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

       В зависимости от разнообразия  длин данных и способа указания  длины записи ПДС подразделяются  на следующие разновидности: 

- ПДС с фиксированной длиной элементов;

- ПДС с элементами переменной длины;

- ПДС с элементами неопределённой длины.

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

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

- магазин или стек – соответствует принципу «первый вошёл, последний вышел»;

- очередь (т.е. очередь в узком смысле в отличие от всей совокупности этого подкласса ПДС), соответствует принципу «первый вошёл, первый вышел»;

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

Списковые структуры данных

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

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

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

Возможно  совместное и раздельное размещение в памяти собственной и ассоциативной информации (Рис. 2 и Рис. 3):

      

Рис.2. Совместное размещение. 

    Рис.3. Раздельное размещение. 

По виду взаимосвязи элементов различают  однонаправленные, двунаправленные  и кольцевые списковые структуры:

    В однонаправленных списках реализуется  взаимосвязь между элементами типа «следующий». Каждый элемент такого списка содержит указатель с адресом  следующего элемента. Последний элемент  имеет в указателе вместо адреса связи специальный знак – признак  конца списка. Указатель списка содержит адрес его первого элемента. Для  задания однонаправленной списковой  структуры требуется следующая  ассоциативная информация:

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

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

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

- указатель  списка, содержащий адрес первого  и последнего элементов;

- звенья  связи элементов, для простого  элемента это звено содержит  адреса

предыдущего и последующего элементов, а также  адрес значения элемента, для сложного элемента в звене связи содержится адрес последующего и предыдущего  элементов списка и адреса первого  и последнего элемента подсписка[1,С. 89].

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

- указатель  строки, который содержит адрес  указателя начала кольца;

- указатель  начала кольца, который хранит  константу N – число просмотров строки, и адрес первого элемента строки;

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

    При каждом просмотре кольца значение N уменьшается на единицу и проверяется условие N=0. Если N≠0,просмотр продолжается; при N=0 просмотр заканчивается. Двунаправленная кольцевая строка отличается от однонаправленной тем, что вместо указателя начала кольца вводятся два указателя со своими константами – это указатель начала прямого направления и указатель начала обратного направления со своими константами чисел просмотра N1 и N2. Кроме того, звенья связи содержат адреса предыдущего и последующего элементов[4, С.53].