Структуры данных. - раздел Информатика, Информатика Оперативная Память Пк Организована В Виде Отдельных Ячеек С Последовательными...
Оперативная память ПК организована в виде отдельных ячеек с последовательными адресами. Однако часто бывает удобно представлять эти ячейки в виде других структур данных. Например, записи о продажах за неделю удобно представлять в табличной форме, которая является абстрактным представлением данных.
Во время конструирования абстрактных представлений необходимо различать является структура данных статической или динамической, то есть, меняется ли со временем ее форма и размер. В целом статическими структурами проще управлять, чем динамическими. Если структура статическая необходимо только обеспечит способы доступа к различным элементам данных и способы изменения значений элементов, находящихся на определенных местах. В случае динамической структуры необходимо решать проблемы добавления и удаления элементов данных и поиска пространства в памяти для увеличения размера структуры.
Указатели. Указатель – это ячейка (или блок ячеек), содержащий адрес другой ячейки памяти. Применительно к структурам данных указатели используются для записи адресов элементов данных. Таким образом, элемент данных может храниться в какой-либо ячейки памяти, а адрес этой ячейки – в указателе, при помощи которого можно позже получить эти данные. То есть значение указателя сообщит нам, где искать данные («указатель указывает на данные»).
Пример использования указателя. В памяти ПК храниться список рассказов, отсортированный в алфавитном порядке по названию. Такая организация удобна во многих приложениях, но затрудняет поиск рассказов, написанных одним автором, т.к. они разбросаны по всему списку. Для решения этой проблемы можно зарезервировать в каждом блоке ячеек памяти, представляющем один рассказ, отдельную ячейку типа указатель. Тогда в каждом из этих указателей можно хранить адрес другого блока, представляющего произведение того же автора, и все рассказы одного автора будут связаны в замкнутую цепь.
Массивы. Часто удобно представлять данные в виде таблиц, т.е. как двумерный массив. Но память машины организована не как таблица, а как цепочка ячеек с последовательными адресами. Поэтому требуемую прямоугольную структуру массива приходится моделировать. Если массив статичен (то есть его размер не изменяется по мере внесения изменений в данные), то подсчитаем объем памяти необходимый для всего массива, и зарезервируем непрерывный блок ячеек памяти полученного размера. Начиная с первой ячейки этого блока, последовательно в каждую ячейку записываем значения из первой строки массива, после первой строки таким же образом записываем последующие. Такая система записи называется построчной (может быть постолбцовая запись). При обращении к элементам массива транслятор преобразует запросы в фактические адреса памяти. Программист тем временем может представлять данные в табличной форме (абстрактная структура), даже если на самом деле они хранятся в одной строке (фактическая структура).
Списки. Это набор записей, выстроенных в определенной последовательности. Один из способов хранения списка – запись всего списка в один блок ячеек памяти с последовательными адресами (непрерывный список). Если данные динамические, то при добавлении или удалении данных приходится перемещать часть элементов списка в другие ячейки памяти.
Проблем, возникающих при работе с динамическими списками, можно избежать, разрешив хранение отдельных имен в различных областях памяти, а не одном большом непрерывном блоке. Например, можно хранить каждое имя в блоке из девяти смежных ячеек памяти. Первые восемь необходимы для записи самого имени, а последняя ячейка будет использоваться как указатель на следующее имя в списке. Следуя этому принципу, список можно раскидать по небольшим блокам, каждый из 9 ячеек, которые связаны между собой указателями. Подобная организация списков называется связным списком.
Для того чтобы определить начало связного списка, отдельно определяется еще один указатель, в котором хранится адрес первой записи. Так как этот указатель указывает на начало, или голову списка, он называется указателем головы.
Для определения конца связного списка используется пустой указатель (NIL), который является просто определенного вида набором битов и находится в последней записи, указывая, что за ним в списке более нет элементов, пример, если мы условимся никогда не хранить элементы списка по адресу 0; значение 0 никогда не будет являться разрешенным значением указателя, и этому его можно использовать как пустой указатель.
На рис. 3.11 отдельные блоки памяти, в которых хранятся элементы связного списка, представлены в виде прямоугольников. Строение каждого прямоугольника (блока памяти) обозначено надписями над ним. Указатели представлены стрелками, идущими от самого указателя к адресу, на который тот указывает. Для прохождения списка нужно последовать указателю головы — так мы найдем первую запись. Далее необходимо следовать указателям, хранящимся в записях, и по ним переходить от элемента к элементу до достижения пустого (NIL) указателя.
Рис. 3.12. Структура связного списка.
Теперь вернемся к вопросу удаления и добавления элементов в список. Использование указателей устраняет необходимость перемещения имен из одной ячейки памяти в другую, возникающую при хранении списка в одном связном блоке. Удалить имя можно, изменив один указатель. Это означает, что указатель, который ранее указывал на удаленное имя, изменяется и указывает теперь на имя, следующее за удаленным (рис. 3.13). Тогда при обработке списка удаленное имя пропускается.
Рис. 3.13. Удаление записи из связного списка.
При добавлении нового имени находим неиспользуемый блок из девяти ячеек памяти, записываем новое имя в первые восемь ячеек, а в девятую записываем адрес имени, которое должно следовать в списке за новым. Затем изменяем указатель, связанный с именем, которое должно предшествовать новому имени в списке так, чтобы он указывал на этот новый блок (рис. 3.14). После этого новую запись можно будет найти на нужном месте при прохождении списка.
Рис. 3.14. Добавление записи в связный список.
Стек. Если разрешить удаление и добавление данных только в начале или в конце структуры, то можно использовать непрерывную структуру. В стеке последний добавленный элемент всегда будет удален первым (последним прибыл – первым убыл). Тот конец стека, где добавляются или удаляются элементы, называется вершиной стека, другой конец называют основанием стека. Для реализации стека в памяти компьютера обычно резервируют блок смежных ячеек памяти достаточного размера, чтобы вместить стек с учетом его увеличения или уменьшения.
Очередь – это список, в который записи добавляются с одной стороны, а удаляются с другой (первым прибыл – первым обслужен). Тот конец очереди, откуда удаляются записи, называется головой или началом очереди, конец очереди, куда добавляются записи, называется хвостом очереди.
Деревья. Эта структура данных отражает принцип организации типичных компаний. В такой структуру президент находится на вершине, от которой отходят линии к вице-президентам, и т.д. Чтобы дать интуитивное определение дерева накладывает ограничение, состоящее в том, что ни один сотрудник компании не подчиняется двум разным начальникам. То есть разные ветви организации не сливаются на нижнем уровне.
Рис. 3.15. Структура дерева.
Каждый элемент дерева называется узлом (рис. 3.15). Узел, находящийся наверху, называется корневым. Если перевернуть рисунок вверх ногами, этот узел будет находиться на месте основания или корня дерева. Узлы на противоположном конце дерева называются терминальными (или листовыми). Если мы выберем любой нетерминальный узел дерева, то обнаружим, что он вместе с узлами, находящимися ниже, также образует дерево. Эти меньшие структуры называются поддеревьями. Иногда структура деревьев рассматривается так, как если бы каждый узел порождал узлы, находящиеся сразу же под ним. Так определяются предки и потомки. Потомки узла называются дочерними узлами, а его предок - родителем. Узлы, имеющие одного и того же родителя, называются братьями. Глубину дерева определяют как количество узлов в наиболее длинном пути от корня до листа. Другими словами, глубина дерева – это количество горизонтальных уровней в нем.
Бинарное дерево – дерево, где у каждого узла может быть максимум два потомка. Бинарные деревья обычно хранятся в памяти при помощи связной структуры, похожей на связные списки. Каждая запись (или узел) дерева состоит из трех компонентов: 1) данные, 2) указатель на первого потомка узла и 3) указатель на второго потомка узла.
Все темы данного раздела:
Информационная система.
Система – множество элементов, находящихся в отношениях и связях друг с другом, образующих определенную целостность (единство). Системный подход
История развития вычислительных машин.
Развитие вычислительных машин можно разделить на следующие этапы:
1) механический – абак, счеты, логарифмическая линейка, арифмометры, механические вычислительные машины;
2) элект
Механический этап.
Абак – доска, посыпанная тонким слоем песка, не ней можно писать буквы и цифры. Впоследствии на доске появились углубления, по которым перемещали кости и камешки.
Одним из первых вычислите
Электромеханический этап
Исследователем, использовавшим идею Жаккарда (ткацкий станок), был Герман Холлерит (1860-1929), который применил способ кодирования информации в виде отверстий на бумажных картах для ускорения проц
Электронный этап
По-видимому, первой электронной машиной была машина Атанасова-Берри, построенная в период с 1937 по 1941 год в колледже штата Айова Джоном Атанасовым и его ассистентом Клиффордом Бери. Скоро послед
Микроэлектронный этап
Первый шаг к уменьшению размеров ЭВМ стал возможен с изобретением в 1948 году транзисторов. До появления интегральных схем транзисторы изготовлялись по отдельности и в процессе сборки схем соединял
Представление информации в виде двоичного кода в памяти ЭВМ.
В современной компьютерной науке информация представляется как последовательность битов. Бит – двоичный разряд – является одним из двух чисел – 0 или 1, которые рассматриваются просто как символы,
Представление изображений.
В современных компьютерных системах хранится не только текстовая и числовая информация, но и графическая, звуковая и видеоинформация. По сравнению с методами хранения символов и чисел способы предс
Аппаратное обеспечение ЭВМ.
Архитектура ЭВМ включает в себя как структуру, отражающую аппаратный состав ПК, так и программно–математическое обеспечение. Основы учения об архитектуре вычислительных машин и принципы логического
Хранение данных в памяти ЭВМ.
Различают устройства хранения информации, реализованные в виде электронных схем, и накопители информации, при помощи которых данные записываются на какой-либо носитель, например магнитный или оптич
Память.
Виды памяти показаны на рис. 1.2. Внутренняя памятьсостоит из оперативного и постоянного запоминающего устройства.
ПЗУ и внешняя память.
Из-за зависимости от питания (обнуляется при отключении питания) и ограниченного размера оперативной памяти большинство машин снабжены устройствами хранения данных (mass storage sistem), которые вк
Процессор.
Кроме способности хранить данные, компьютер должен обладать способностью обрабатывать их так, как это предписано алгоритмом. Это значит, что машина должна иметь средства выполнения операций над дан
Шины и контроллеры.
Для передачи двоичного кода центральный процессор и оперативная память компьютера соединены набором проводников, который называется шиной. С помощью этой шины процессор может извле
Конструктивное исполнение.
Состав ПК принято называть конфигурацией. Поскольку современные компьютеры имеют блочно-модульную конструкцию, то необходимую аппаратную конфигурацию, можно реализовать из готовых
Периферийные устройства.
Периферийные устройства — это устройства, с помощью которых информация или вводится в компьютер, или выводится из него. Они также называют внешними или устройствами ввода-вывода да
Устройства ввода информации.
Клавиатура- основное устройство ввода информации. Расположение латинских букв на ней соответствует расположению клавиш на латинской печатной машинке (т.н. клавиатура QWERTY- по пер
Устройства вывода информации.
Дисплей (монитор) - основное устройство вывода информации. Дисплеи бывают основанными на электронно-лучевой трубке (обычном кинескопе), жидких кристаллах (lcd, англ. Liquid crystal
Устройства связи.
Модем (модулятор-демодулятор) – устройство, преобразующее информацию к виду, в котором ее можно передавать по линиям связи, в частности - по телефонным линиям. Модемы бывают внутре
Операционная система.
Операционная система – программа, которая управляет общими действиями машины (ЭВМ) или группы машин, объединенных в сеть. Операционная система обеспечивает связь пользователей с ПК
Компоненты операционной системы.
Часть операционной системы, которая определяет интерфейс между операционной системой и пользователем, называется оболочкой. Задача оболочки состоит в том, чтобы взаимодейств
Алгоритм — это упорядоченный набор однозначных выполнимых шагов.
Обратите внимание на то, что это определение утверждает, что набор шагов должен быть упорядочен. Это означает, что шаги в алгоритме должны быть структурированы, то есть должны выпо
Представление алгоритма.
Для представления алгоритма используется язык представления: естественный, картинок, блок-схем и т.д. При естественном представлении алгоритм можно понять неправильно, потому что и
Типовые структуры алгоритмов.
Различают три типовые структуры алгоритмов: линейную; разветвленную; циклическую. Чаще всего алгоритмы решаемых задач состоят из отдельных частей, которые, в свою очередь, относятся к одной или дру
Алгоритмы сортировки.
Для решения многих задач необходимо упорядочить исходные данные по определенному признаку. Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество ср
Алгоритмы поиска.
Алгоритм последовательного поиска последовательно рассматривает элементы списка в том порядке, в котором они расположены в списке. Стоит задача найти
Эффективность и правильность алгоритмов.
Хотя современные машины способны выполнять миллионы команд в секунду, эффективность остается главной проблемой при построении алгоритмов. Один из разделов вычислительной техники называется анализ а
История языков программирования.
Языки программирования разработаны так, чтобы они позволяли записать алгоритм в форме, понятной человеку и легко преобразуемой в команды машинного языка. Языки программирования позволяют избежать л
Парадигмы программирования.
В основе разделения языков программирования на поколения лежит линейная шкала. Позиция языка на этой шкале определяется тем, насколько пользователь свободен от ненужной информации и в какой степени
Структура программы на Паскале.
Программа на языке Паскаль состоит из строк, максимальная длина которой может быть равна 127 символам. Строка может начинаться с любой колонки. Количество операторов в строке произвольно.
Тело функции
END;
3. раздел операторов, т.е. сама программа. Операторы выполняются в том порядке, в котором они записаны в соответствии с синтаксисом и правилами пунктуации языка Паскаль. Слова BEGIN и
Правила пунктуации.
1) точка с запятой не ставиться после зарезервированных слов unit, label, uses, type, const, var и ставиться после завершения каждого описания;
2) точка с запятой не ставиться после begin
Алфавит и словарь языка.
Символы языка – элементарные знаки, используемые для составления текстов. Они составляют алфавит языка. Программа на Паскале формируется с помощью конечного набора знаков, образующих алфавит языка,
Константы и переменные, типы данных.
Как и другие языки программирования, Паскаль интерпретирует данные как константы и переменные. Они определяются идентификаторами (именами), по которым к ним можно обращаться в программе.
Процедуры ввода-вывода.
Для выполнения операций ввода-вывода служат четыре процедуры: READ, READLN, WRITE, WRITELN. Примеры использования этих процедур приведены в этой главе и в ранее рассмотренных примерах 6, 7, 9,11.
Работа с файлами.
Как уже говорилось выше в пособии рассматривается работа только с текстовыми файлами. Для организации текстового файла прежде всего необходимо в разделе описаний объявить соответствующую файловую п
Процедуры и функции.
Подпрограммой называется именованная логически законченная группа операторов языка программирования, которую можно вызвать по имени для выполнения любое количество раз из различных
Типы текстовых редакторов.
Большинство документов, предназначенных для печати на бумаге, а также многие электронные документы являются текстовыми, то есть представляют собой блоки текста, состоящие из обычных слов, набранных
Текстовый процессор Word.
Типы шрифтов. Существуют два типа шрифтов: растровые (Туре 1) и векторные (ТrueТуре). Растровые шрифты имеют фиксированный размер и предназначены в первую очередь для вывода на экр
Табличный процессор Excel.
Интерфейс Excel (рис. 3.7) состоит из шести областей:
- окно рабочей книги (рабочий лист);
- строка меню;
- панелей инструментов (например, панель формат
Копирование и перемещение данных.
Выделение ячеек производится с целью обозначения диапазона или ячейки, к которым должна относиться следующая команда или функция. Наименьшая структурная единица выделенного диапазо
Управление данными. Сортировка и фильтрация.
В Ехсеl можно сортировать ячейки по возрастанию и убыванию. Для сортировки сначала выберите диапазон ячеек, данные в которых надо отсортировать, а затем нажмите на одну из кнопок с
Использование расширенного фильтра.
Над диапазоном, который будет использоваться, как диапазон условий должно быть не менее трех пустых строк. Диапазон условий должен включать заголовки столбцов (которые можно скопировать из основной
Построение диаграмм и графиков.
Графики и диаграммы – наиболее эффективный способ представления данных. Они облегчают восприятие и анализ предлагаемых материалов, выявляют соотношение значений данных и динамику изменения ряда дан
Печать документов.
Экранное представление электронной таблицы обычно значительно отличается от того, которое получилось бы при выводе данных на печать. Это связано с тем, что единый рабочий лист приходится разбивать
Разработка программного обеспечения.
Исследования в области программного обеспечения в настоящее время развиваются в двух плоскостях: некоторые исследователи, которых называют практиками, разрабатывают методы создания приложений, а др
Файловые структуры.
Хранение файла на запоминающем устройстве предписывает, что файл должен быть разделен на блоки, являющиеся физическими записями, совместимыми с используемым устройством хранения. Например, файлы, з
Структуры баз данных.
Современные информационные системы, основанные на концепции интеграции данных, характеризуются огромными объёмами хранимых данных, сложной организацией, необходимостью удовлетворять различные требо
Модели баз данных.
Абстрактное представление базы данных называется моделью базы данных. Модель базы данных определяет структуру данных и операции их обработки. Поиски наилучшей модели базы данных все еще ведутся. Це
Реляционная модель.
В этой модели концептуальное представление базы – набор таблиц, состоящих из строк и столбцов. СУБД в таком случае будет включать процедуры, которые позволят приложению выбирать определенные элемен
Иерархическая модель.
Модель позволяет строить базы данных с древовидной структурой, где каждый узел содержит свой тип данных (рис. 3.18).
Для представления такой модели используется ориентированный граф. Граф
Сетевая модель.
В сетевой структуре при тех же основных понятиях (уровень, узел, связь) каждый элемент может быть связан с любым другим элементом (рис. 3.19).
Системы управления базами данных (СУБД).
Как упомянуто выше, СУБД называют программную систему, предназначенную для создания на компьютерах общей БД, используемой для решения множества задач. Подобные системы служат для поддержания базы д
Microsoft Access - СУБД реляционного типа.
СУБД Access хранит все данные в одном файле, хотя и распределяет их по разным таблицам. Базой данных Access является файл, который имеет расширение mdb. Этот файл может содержать не только таблицы,
Тип данных.
После ввода имени поля необходимо задать тип данных, которые будут находиться в этом поле. Наиболее удобным способом является выбор типа из списка, но можно ввести наименование типа и вручную. Как
Ввод и проверка данных.
Данные можно вводить непосредственно в таблицу (выбрав Таблица - Открыть) или с помощью созданной формы.
При работе в режиме таблицы существуют три операц
Сортировка и фильтрация данных.
Операция сортировки данных используется для удобства нахождения нужной информации. Когда на экране (или на бумаге) отображается таблица, гораздо легче найти нужную строку, если эти
Создание форм.
Форма представляет собой некий электронный бланк, в котором имеются поля для ввода данных. Оператор при работе с базой данных вводит данные в эти поля, и данные автоматически заносятся в таблицы ба
Создание запросов.
Большинство СУБД разрешают использовать запросы следующих типов:
- запрос-выборка, предназначенный для отбора данных, хранящихся в таблицах, и не изменяющий эти данные;
- запрос-и
Автоматизация расчетов с помощью запросов.
Access позволяет автоматизировать различного рода вычисления. Например, процесс пересчета цены товара в рублях на денежные эквиваленты в иностранных валютах. Такие расчеты бывают необходимыми в тор
Понятие макрокоманды и макроса.
Макросом называют набор из одной или более команд, выполняющих определенные, часто используемые операции, например, открытие форм или печать отчетов. Макросы могут быть полезны для
Компьютерные сети.
Создание компьютерных сетей было вызвано потребностью совместного использования информации у людей, работающих на удаленных друг от друга компьютерах.
Компьютерная сеть (а
Интернет.
Интернет - глобальная компьютерная сеть. Интернет был создан довольно давно (в 50гг. 20 века) и развивался как ведомственная сеть, принадлежащая министерству обороны США. В 1983г.
Система адресов Интернета.
Каждому компьютеру в Интернете присваивается уникальный адрес, который называется IP-адресом (Internet Protocol адрес) и используется для идентификации машины в сети. Система IP-ад
Электронная почта.
Для передачи сообщений от одного пользователя к другому (такая система называется электронной почтой — e-mail) каждое локальное руководство назначает машину, которая выполняет все действия по обраб
Гипертекстовые документы.
Кроме того, что Интернет предоставляет возможность коммуникации с помощью электронной почты, он также является средством распространения мультимедийных документов, которые называются гиперт
Защита информации.
В вычислительной технике понятие безопасности является весьма широким. Оно подразумевает и надежность работы компьютера, и сохранность ценных данных, и защиту информации от внесения в нее изменений
Новости и инфо для студентов