Файл: Алгоритмы сортировки данных (Структура и типы данных).pdf

ВУЗ: Не указан

Категория: Курсовая работа

Дисциплина: Не указана

Добавлен: 26.05.2023

Просмотров: 92

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Введение

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

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

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


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

Методы хранения информации, называемые «простыми», т. е. неделимыми на составные части, предпочтительнее изучать вместе с конкретным языком программирования, либо же глубоко углубляться в суть их работы. Поэтому здесь будут рассмотрены лишь «интегрированные» структуры, те которые состоят из простых, а именно: массивы, списки, деревья и графы.

Сформулируем цели и задачи курсовой работы.

Цель: Изучение принципов организации данных

Задачи:

  1. Изучить и проанализировать научно-методическую литературу по теме «Организация данных: структуры, списки, стеки, очереди. Методы работы».
  2. Написать программы, демонстрирующие работу стеков, списков, очередей.
  3. Изучить структуры данных
  4. Изучить типы данных

Глава 1. Сортировка данных.

1.1 Данные. Структура.

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

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


Виды форм представления информации:

  1. ^ По способу отображения: 

а) символьная (знаки, цифры, буквы); 

б) графическая (изображения); 

в) текстовая (набор букв, цифр); 

г) звуковая.

  1. По месту появления: 

а) внутренняя (выходная); 

б) внешняя (входная)

  1. По стабильности: 

а) постоянная; 

б) переменная 

  1. По стадии обработки: 

а) первичная;

б) вторичная. ^

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

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

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

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

Различаются простые (базовые, примитивные) типы данных и интегрированные  Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. 

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

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

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


2. Второй важный признак структуры данных - характер упорядоченности её элементов. По этому признаку структуры можно делить налинейные и нелинейные структуры. В зависимости от характера взаимного расположения элементов в памяти, линейные структуры можно разделить на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные списки). 

В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Информация по каждому типу однозначно определяет: 

1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, и интерпретирование двоичного представления; 

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа; 

3) множество допустимых операций, которые применимы к объекту описываемого типа. 

1.2 Типы данных

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

По способу представления и обработки типы данных бывают:

  • простые
  • структурированные
  • указатели
  • объекты
  • процедуры

Целые типы. С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов).

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

Таблица 1. Целостный тип данных

Тип

Диапазон

Размер в байтах

Shortint

-128…127

1

Integer

-32 768…32 767

2

Longint

-2 147 483 648…2 147 483 647

4

Byte

0…255

1

Word

0…65 535

2

Объявить целочисленную переменную можно в разделе Var, например:

Var book: word;

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


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

В Паскале бывают следующие вещественные типы данных:

Таблица 2. Вещественный тип данных

Тип

Диапазон

Память, байт

Количество цифр

Real

2.9e-39 … 1.7e38

6

11-12

Single

1.5e-45 … 3.4e38

4

7-8

Double

5.0e-324 …1.7e308

8

15-16

Extended

3.4e-4932 … 1.1e493

10

19-20

Comp

-9.2e63 … (9.2e63)-1

8

19-20

Над ними может быть выполнено большее количество операций и функций, чем над целыми. Например, эти функции возвращают вещественный результат:

sin(x) – синус;

cos(x) – косинус;

arctan(x) – арктангенс;

ln(x) – натуральный логарифм;

sqrt(x) – квадратный корень;

exp(x) – экспонента;

Логический тип

Значениями логического типа BOOLEAN может быть одна из заранее объявленных констант false (ложь) или true (истина). Данные логического типа занимают один байт памяти. При этом значении false соответствует нулевое значение байта, а значению true соответствует любое ненулевое значение байта. Над логическими типами возможны операции нулевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor). В этих операциях операнды логического типа рассматриваются как единое целое. Результаты логического типа получаются при сравнении данных любых типов. 

Переменная, имеющая логический тип данных может принимать всего два значения: true (истина) и false (ложь). Здесь истине соответствует значение 1, а ложь тождественная нулю.  Объявить булеву переменную можно так:

Var A: Boolean;

Над данными этого типа могут выполняться операции сравнения и логические операции:  not , and, or, xor.

Символьный тип

Значением символьного типа char являются символы из некоторого предопределенного множества. В большинстве современных персональных ЭВМ этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена информацией). Это множество состоит из 256 разных символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие символы. Допускается некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита. Значение символьного типа char занимает в памяти 1 байт.