Линейные структуры данных

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

КАФЕДРА МАТЕМАТИКИ И ИНФОРМАТИКИ

 

 

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

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

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

 

 

Барнаул - 2007

ОГЛАВЛЕНИЕ

 

ВВЕДЕНИЕ

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

1.2 ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ

1.3 ТАБЛИЧНЫЕ СТРУКТУРЫ ДАННЫХ

1.5 УПОРЯДОЧЕНИЕ СТРУКТУР ДАННЫХ

1.6 РЕЖИМЫ ОБРАБОТКИ ДАННЫХ

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 ОБЩАЯ ХАРАКТЕРИСТИКА ЗАДАЧИ

2.2 ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

ВВЕДЕНИЕ

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

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

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

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

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

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

 ─ решить практическую задачу с использованием средств MS Exsel.

Объектом исследования являются данные. Предметом исследования служат структуры данных.

Информационной базой исследования являются публикации в сети Интернет и учебная литература по изучаемому вопросу.

Структурно работа состоит из введения, теоретической и практической частей, заключения, списка использованной литературы из 6 источников. Во введении обоснована актуальность работы, определены цель, задачи и предмет исследования. В теоретической части рассмотрены основные структуры данных. В практической части решена задача с применением средств MS Exsel.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Данные – это материальные объекты произвольной формы, выступающие в качестве средства представления информации. Преобразование и обработка данных позволяют извлечь информацию, т.е. знание о том или ином предмете, процессе, явлении [2, С.21]. Другими словами данные – диалектическая составная часть информации. Они представляют собой зарегистрированные сигналы. В соответствии с методом регистрации данные могут храниться и транспортироваться на носителях различных видов. Например, на бумаге данные регистрируются путем изменения оптических характеристик ее поверхности. Изменение оптических свойств используется также в устройствах, осуществляющих запись лазерным лучом на пластмассовых носителях с отражающим покрытием (CD-ROM).

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

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

• сбор данных — накопление информации с целью обеспечения достаточной полноты для принятия решений;

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

• фильтрация данных — отсеивание «лишних» данных, в которых нет необходимости для принятия решений;

• сортировка данных — упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации;

• архивация данных — организация хранения данных в удобной и легкодоступной форме;

• защита данных — комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

• транспортировка данных — прием и передача (доставка и поставка) данных между удаленными участниками информационного процесса;

• преобразование данных — перевод данных из одной формы в другую или из одной структуры в другую.

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

ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ

 

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

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

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

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

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

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

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

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

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

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

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

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

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