ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ

КАФЕДРА ПРИКЛАДНОЙ ИНФОРМАТИКИ 
 

КУРСОВАЯ  РАБОТА

по дисциплине «Информатика»

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

Исполнитель:

Матушкина Дарья Владимировна

курс                                         ФНО

группа                                   УК – 4

    № зачётной книжки   09УБД43898

    Руководитель:

    Тимшина Диана Владимировна 
 
 
 
 
 
 
 
 
 

Новороссийск - 2010

СОДЕРЖАНИЕ 

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

Теоретическая часть «Основные структуры данных»……………………...4

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

    1. Общая характеристика данных……………………………………………4

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

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

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

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

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

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

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

ВВЕДЕНИЕ 

    Информатизация  – это организованный социально-экономический и научно-технический процесс создания оптимальных условий для удовлетворения информационных потребностей и реализации прав граждан, органов государственной власти, органов местного самоуправления, организаций, общественных объединений на основе формирования и использования информационных ресурсов [1, ФЗ-149, 2006].

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

    - дать  общую характеристику данным;

    - изучить  различные структуры данных;

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

    - рассмотреть  режимы обработки данных;

    - решить  практическую задачу  с использованием средств MS Exsel [2 с. 5].

    Основной задачей практической части является расчёт отчислений в Пенсионный фонд и Фонд социального страхования по каждому сотруднику предприятия. Расчёты выполнены с использованием табличного процессора (MS Excel), который позволяют обрабатывать большие объемы числовой информации, формируя из данных таблицы, - калькуляторы, хранящие в своей памяти огромные числовые массивы, и позволяющие выполнять над ними различные арифметические и логические операции, формировать диаграммы и делать множество других операций, полезных для решения различных задач пользователя. Текстовой процессор (MS Word) позволяет готовить текстовые документы, который может включать и таблицы, и рисунки, и диаграммы [3]. 
 

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ «ОСНОВНЫЕ СТРУКТУРЫ ДАННЫХ»

    ВВЕДЕНИЕ

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

1.1 ОБЩАЯ ХАРАКТЕРИСТИКА ДАННЫХ

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

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

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

    Хорошо  спроектированное хранилище данных оптимизирует использование ресурсов (таких как время выполнения операций, используемый объём оперативной памяти, число обращений к дисковым накопителям), требуемых для выполнения наиболее критичных операций.

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

    Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.

    При разработке программного обеспечения  сложность реализации и качество работы программ существенно зависит  от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

    Многие  классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно  встроены в языки программирования. Например, структура данных хэш-таблица  встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++ [4, с. 32-33]. 
 

1.2 КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ 

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

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

• по способам размещения в памяти и связанными с ними способами организации служебной информации;
• по реализуемым при хранении логическим отношениям на множестве данных;
• по способам организации служебной информации о структуре данных (т.е. по структуре информации о структуре), и т.п.

    Однако, единой красивой классификации всей совокупности различных структур не получается. Поэтому более плодотворно  рассматривать некоторые базовые  типовые структуры, которые могут  компоноваться и сочетаться в  различных гибридных комбинациях. Состав таких типовых структур иллюстрируется схемой 1[5]:

Рис. 1. Основные структуры данных

1.3 ХАРАКТЕРИСТИКА ОСНОВНЫХ ТИПОВЫХ СТРУКТУР ДАННЫХ

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

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

    № п/п Фамилия, Имя, Отчество

    1 Аистов Александр Алексеевич

    2 Бобров Борис Борисович

    3 Воробьева Валентина Владиславовна

    27 Сорокин Сергей Семенович

    Разделителем  может быть и какой-нибудь специальный  символ. Наиболее известные разделители между словами - это пробелы. В русском и во многих европейских языках общепринятым разделителем предложений является точка. В рассмотренном учётном журнале в качестве разделителя можно использовать любой символ, который не встречается в самих данных, например символ «*». Тогда список выглядел бы так:

    Аистов  Александр Алексеевич * Бобров Борис  Борисович * Воробьева Валентина  Владиславовна * … * Сорокин Сергей Семенович.

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

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

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

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

    Частным случаем линейного списка является стек.

    Стек - это упорядоченный набор элементов, в котором размещение новых элементов и удаление осуществляется только с одного конца. Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришёл — первым вышел»).

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

    Рис.2 Простое представление стека 

    Стеки широко применяются в вычислительной технике — в частности, для отслеживания точек возврата из подпрограмм используется стек вызовов, который является неотъемлемой частью архитектуры большинства современных процессоров. Языки программирования высокого уровня также используют стек вызовов для передачи параметров при вызове процедур. Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений [6].

    О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется (рис. 3).

    Рис. 3 Реализация очереди на базе массива 

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

    Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

• push_front  - добавить (положить) в начало дека новый элемент;
• push_back  - добавить (положить) в конец дека новый элемент;
• pop_front - извлечь из дека первый элемент;
• pop_back  - извлечь из дека последний элемент;
• front  - узнать значение первого элемента (не удаляя его);
• back  - узнать значение последнего элемента (не удаляя его);
• size  - узнать количество элементов в деке;
• clear - очистить дек (удалить из него все элементы).

    Примером  дека может быть некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это тоже FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек [8].

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

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

    Табличная структура данных                           Таблица 1

    Если  нужно сохранить таблицу в  виде длинной символьной строки, используют один символ-разделитель между элементами, принадлежащими одной строке, и другой разделитель для отделения строк:

    Меркурий0,39*0,056*0#Венера*0,67*0,88*0#Земля*1,0*1,0*1#Марс*1,51*0,1*2#...

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

    Еще проще можно действовать, если все элементы таблицы имеют равную длину. Такие таблицы называют матрицами. В данном случае разделители не нужны, поскольку все элементы имеют равную длину и количество их известно. Для розыска элемента с адресом (m, n) в матрице, имеющей M строк и N столбцов, надо просмотреть ее с самого начала и отсчитать а [N (m-1)+(n-1)] символ, где а - длина одного элемента. Со следующего символа начнется нужный элемент. Его длина равна а, поэтому его конец определить нетрудно.

    Матрицы - это упорядоченные структуры, в которых адрес элемента определяется номером строки и номером столбца, на пересечении которых находится ячейка, содержащая искомый элемент.

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

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

    Пуск > Программы > Стандартные > Калькулятор.

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

    В иерархической структуре, построенной  методом дихотомии, путь доступа  к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи [9, c.46-54].

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

    Каждый  узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, left, right) есть два ребёнка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.

    Двоичное  дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

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

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

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

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

    Двоичное  дерево поиска применяется для построения более абстрактных структур, таких  как множества, мультимножества, ассоциативные массивы (рис. 4). 

    Рис. 4 Двоичное дерево поиска

    Базовый интерфейс двоичного дерева поиска состоит из трех операций:

• FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
• INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).
• REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K [10].

    ЗАКЛЮЧЕНИЕ

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

    В MS Office средством для создания электронных  таблиц является табличный процессор Excel, также популярными являются электронные таблицы Quattro Pro фирмы Novell и Lotus 1-2-3 фирмы Lotus Development. Все они работают в среде Windows и выполняют принципиально одни и те же функции с некоторыми различиями в их реализации [4].

    Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка), двумя числами (для двумерной таблицы) или несколькими числами для многомерной таблицы. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра. Наиболее популярными являются стеки протоколов: TCP/IP, IPX/SPX, NetBEUI/NetBIOS, и другие. Эти стеки протоколов на физическом и канальном уровнях используют стандартизованные протоколы Ethernet, Token Ring, FDDI и некоторые другие, которые позволяют использовать во всех сетях одну и ту же аппаратуру. На верхних уровнях все стеки работают со своими собственными протоколами. Стеки, очереди, деки используются  в программах для повышения эффективности и снижения затрат на управление предприятием или многоквартирным домом, за счет автоматизации расчетно-информационных задач: контроль за расчетами с покупателями/абонентами и поставщиками, бухгалтерский или подомовой учет доходов и расходов, оперативное получение необходимой аналитической информации, для автоматизации занесения показаний приборов учета и отметок об их состоянии.