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

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

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

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

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

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

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

курс                                         ФНО

группа                                   УК – 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, «последним пришёл — первым вышел»).