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

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ
ТЕХНОЛОГИЙ имени МУХАММАДА АЛЬ-ХОРЕЗМИ

САМОСТОЯТЕЛЬНАЯ РАБОТА НА ТЕМУ:
«Линейные структуры данных»

Студента группы: 065-20
Выполнил: Эргашев Н.
Проверила: Тошпулатова Н.Б.

1. 
   Введение.......................................................................................................2
   
2. 
   Основная часть...........................................................................................3
   
3. 
   Заключение................................................................................................17
   
4. 
   Литературы и сайты................................................................................19
   

ВВЕДЕНИЕ

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

Понятие структуры всегда соответствует сложному объекту, обладающему свойством целостности, и вместе с тем сконструированному из простых компонентов путем использования определенной системы правил. Можно выделить следующие основные виды структур данных:
♦ простые (т.е. встроенные в язык) структуры – это основные конструкции, из которых строятся более сложные структуры-агрегаты. Простые структуры и агрегаты образуют фундаментальные структуры. Данные, представленные в виде фундаментальных структур, во время выполнения программы могут изменять значение, но изменить их строение нельзя;
♦ составные (динамические) структуры в процессе выполнения программы могут изменять как значение, так и строение;
♦ иерархические структуры - это динамические структуры, которые содержат данные, распределенные по уровням;
♦ объектно-ориентированные структуры воплощают концепцию совместной обработки данных и алгоритмов.
Развитие концепции структуризации в программировании. Развитие концепции структуризации прежде всего нашло отражение в топологии языков программирования. Топология – это основные элементы языка программирования и их взаимодействие.
1 ПОКОЛЕНИЕ (FORTRAN –1, ALGOL-58) Программы имеют простую структуру, состоящую из области глобальных данных и подпрограмм (рис.1). Ошибка в какой-либо подпрограмме может повлиять на исполнение других подпрограмм, т.к. область данных является общей. Большое количество перекрестных связей между подпрограммами, запутанные схемы управления,
неясный смысл данных снижают понимаемость и надежность программ. В языках появились простейшие управляющие структуры – операторы условного и безусловного перехода, циклы с различными условиями повторения и выхода и т.п. 2 ПОКОЛЕНИЕ (FORTRAN-II, ALGOL-68, LISP, PL/1) В языках реализованы разнообразные механизмы передачи параметров, а также механизмы управления вложенностью подпрограмм и областями видимости, что послужило основой структурного программирования (рис.2). Возникли методы структурного проектирования, позволяющие создавать большие программные системы, используя подпрограммы как готовые строительные блоки. Были заложены основы структуризации данных, т.е. появились типы данных, конструируемые пользователем, например, записи.
3 ПОКОЛЕНИЕ (PASCAL, MODULА, SIMULA, C, PROLOG) Для языков этого поколения характерно развитие и широкое использование метода структурного программирования, развитие средств абстрагирования типов (появилась даже теория типов). Получила развитие концепция модуля как программной оболочки, внутри которой можно скрыть данные и процедуры, а взаимодействие между различными модулями организовать с помощью интерфейса (рис.3). Скрытие данных поддерживается за счет раздельной компиляции модулей, а также механизмов управления доступом к данным и процедурам внутри модуля. В языке SIMULA появились классы – основа объектно-ориентированного программирования.