Основные структуры данных - раздел Информатика, ИНФОРМАТИКА Автоматизированная Обработка Больших Объемов Данных Происходит Проще, Когда Д...
Автоматизированная обработка больших объемов данных происходит проще, когда данные упорядочены, т.е. образуют заданную структуру. Среди существующих типов структур данных можно выделить три основных [13]: линейная, иерархическая и табличная.
Линейные структуры данных могут быть представлены списками, в которых каждый элемент данных однозначно определяется своим номером в массиве. Обычный журнал посещаемости занятий, например, имеет структуру списка, т.к. все студенты группы зарегистрированы в нем под уникальными номерами.
При создании любой структуры данных надо решить два вопроса: как разделить элементы данных между собой и как находить нужные элементы. В журнале посещаемости, например, вопросы решаются так: каждый новый элемент списка заносится с новой строки, т.е. разделителем является конец строки, а каждый элемент можно найти по номеру строки.
В случае, когда все элементы списка имеют равную длину A, разделители не нужны. Для нахождения элемента с номером n надо просмотреть список с начала и отсчитать А(n-1) символов. Также упрощенные списки, состоящие из элементов равной длины, называют векторами данных. Итак, линейные структуры данных (списки) – это упорядоченные структуры, в которых адрес элемента однозначно определяется его номером.
В табличных структурах элементы данных определяются адресом ячейки, который состоит не из одного параметра, как в списках, а из нескольких. Для таблицы умножения, например, адрес ячейки определяется номерами строки и столбца. Нужные ячейки находятся на их пересечении, а элемент выбирается из ячейки.
При хранении табличных данных количество разделителей должно быть больше, чем для данных, имеющих структуру списка (строки и столбцы разделяют не одним разделителем, а двумя). Если все элементы таблицы имеют равную длину, они называются матрицами. Для хранения матриц разделители не нужны. Для нахождения элемента с адресом (m, n) в матрице, имеющей M строк и N столбцов, надо просмотреть ее с начала и отсчитать a[N(m-1)+(n-1)] символов, где a – длина одного элемента.
В практике могут быть использованы таблицы (матрицы), у которых размерность (число координат) не два ( строка и столбец), а более. Например, учет учащихся может быть организован в виде таблицы размерностью 5:
-Номер института в университете
-Номер курса (в институте)
-Номер специальности (на курсе)
-Номер группы в потоке одной специальности
-Номер учащегося в группе
Для нахождения данных об учащихся в такой структуре надо знать все пять параметров (координат).
Данные, которые трудно представить в виде списка или таблицы, часто представляют в виде иерархических структур. В иерархической структуре адрес каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу. Например, пусть доступа к программе «Калькулятор» в системе Windows имеет вид: Путь -> Программы -> Стандартные -> Калькулятор.
Линейные и табличные структуры являются простыми. Ими легко пользоваться, т.к. адрес каждого элемента задается одним числом (для списка), двумя числами (для двумерной таблицы) или несколькими числами для многомерной таблицы. Они также легко упорядочиваются. Основным методом упорядочивания является сортировка. Данные можно сортировать по любому избранному критерию: по алфавиту, по возрастанию какого – либо параметра и т.п.
Несмотря на ряд достоинств простых структур данных, у них есть недостаток – их трудно обновлять. Например, при добавлении произвольного элемента в упорядоченную структуру списка может происходить изменение адресных данных у других элементов.
Иерархические структуры данных по форме сложнее, чем линейные и табличные, но они не создают проблем с обновлением данных. Их легко развивать путем создания новых уровней. Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочивания. Часто методы упорядочивания в таких структурах основываются на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который может использоваться при поиске, сортировке и т.д.
Особо следует сказать об адресных данных. В любой организованной структуре каждый элемент данных имеет адрес. Адреса элементов данных – это тоже данные и их тоже надо хранить и обрабатывать. Таким образом, за упорядоченность данных приходится платить их размножением – появлением адресных данных.
Как уже отмечалось ранее, наименьшей единицей измерения данных является байт. В качестве единицы хранения данных принят объект переменной длины, называемый файлом. Файл – это последовательность произвольного числа байтов, обладающая уникальным собственным именем [16]. Обычно в отдельном файле хранят данные, относящиеся к одному типу. В этом случае тип данных определяет тип файла. Имя файла несет в себе адресные данные, а также сведения о типе данных, заключенных в нем. Эти сведения важны для автоматических средств работы с данными при выборе адекватного метода извлечения информации из файла.
Хранение файлов организуется в иерархической структуре, называемой файловой структурой. Вершиной структуры является имя носителя, на котором хранятся файлы. Далее файлы группируются в папки (каталоги), внутри которых могут быть созданы вложенные папки (подкаталоги). Путь доступа к файлу начинается с имени устройства и включает все имена папок (каталогов), через которые проходит. В качестве разделителя используется символ «\». Уникальность имени файла обеспечивается тем, что полным именем файла считается собственное имя файла с путем доступа к нему. Пример записи полного имени файла. C:\информатика\задания\работа с электронными таблицами
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ... ПУТЕЙ СООБЩЕНИЯ МИИТ... Кафедра Вычислительные системы и сети...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Основные структуры данных
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Предшественники электронных вычислительных машин
Первое автоматическое устройство для выполнения операции сложения было создано в 1623 году в Германии Вильгельмом Шикардом на базе механических часов.
Поколения электронных вычислительных машин
На протяжении пяти десятилетий электронная вычислительная техника очень быстро развивается, за это время сменилось несколько поколений ЭВМ.
Поколение ЭВМ определяется совокупностью взаимоо
Упрощенная структура компьютера и принцип его работы.
Современные ЭВМ (компьютеры) имеют разнообразную конфигурацию (состав, физическую и логическую организацию). Однако во многих случаях их упрощенная структура может быть отображена рисунком 1.
Программное обеспечение компьютера
Для того, чтобы ЭВМ была ЭВМ, т.е. могла выполнять любые действия по обработке информации, необходимо составить на понятном ей языке последовательность команд, т.е. программу
История языков программирования
Программы для первых компьютеров писали на «машинном» языке, т.е. в кодах, непосредственно воспринимаемых компьютером.
В начале 50-х годов появился язык ассемблер*
Основные характеристики компьютеров
Важнейшими эксплуатационными характеристиками ЭВМ являются ее производительность Р и общий коэффициент эффективности машины Э:
Э = Р/ (Сэвм + Сэк),
Сэвм – стоимос
МикроЭВМ
С появлением в 70х годах прошлого века сверхбольших интегральных схем стало возможным создавать на одной микросхеме упрощенный вариант процессора – микропроцессор с числом разрядов в слове 8-16 и б
Персональные компьютеры
Первые персональные компьютеры появились в середине 70-х годов. Их разработали независимо друг от друга фирмы IBM и Apple. Однако стоимость компьютеров была слишком высока, и поэтом
Большие ЭВМ и СуперЭВМ
Большие ЭВМ (мэйнфреймы) – это мощные компьютеры общего назначения. Их применяют для обслуживания очень крупных организаций и даже целых отраслей народного хозяйства. На базе таких компьютеров созд
Представление чисел в позиционной системе счисления
Под системой счисления понимается способ представления любого числа с помощью некоторого алфавита символов, называемых цифрами. Существуют различные системы счисления. От их особенностей зав
Случай, когда система счисления является целой степенью числа 2
Рассмотрим правила преобразования восьмеричных и шестнадцатеричных чисел в двоичные и наоборот. Эти правила исключительно просты, т.к. основания восьмеричной и шестнадцатеричной систем есть целые с
Общий случай перевода
Общие правила перевода чисел из десятичной системы счисления в другую приведены ниже
1) Для целых чисел.
Делим число на основание той системы счисления, в которую переводим данное
Двоичная арифметика
Правила выполнения арифметических действий над двоичными числами задаются таблицами двоичных сложения, вычитания и умножения.
Таблица Таблица Таблица
двоичного двоичного двоичного
Представление чисел в форме с фиксированной и плавающей точкой
В ЭВМ применяют две формы представления чисел: с фиксированной точкой (естественная форма) и плавающей точкой.
При представлении чисел с фиксированной точкой положение точки фиксируется в
Коды для представления чисел в компьютере
Взаимно однозначное преобразование слов называется кодированием. В ЭВМ в целях упрощения выполнения арифметических операций применяют специальные коды для представления чисел. При п
Прямой код
Прямой код двоичного числа G, представляемого в n - разрядной сетке, определяется как
G , при G>=0;
G
Обратный код
Обратный код двоичного числа G, представляемого в n - разрядной сетке, определяется как
G , при G>=0;
Дополнительный код
Дополнительный код двоичного числа G, представляемого в n - разрядной сетке, определяется как
G ,
Смещенный код.
Помимо рассмотренных кодов для представления чисел со знаком применяется еще смещенный код. Этот код обычно используется для представления целых чисел, задающих порядки чисел с плавающей точкой. Оп
Сложение чисел в форме с плавающей точкой
Сложение двух чисел, представленных в форме с плавающей точкой осуществляется по следующему алгоритму:
Определение разности R (с помощью алгебраического сложения) порядков заданных чисел с
Кодирование текстовой информации
Современные ЭВМ обрабатывают не только числовую, но и текстовую, другими словами – алфавитно-цифровую информацию, содержащую цифры, буквы, знаки препинания, математические и другие символы. Такой х
Кодирование графической информации
Если рассмотреть с помощью увеличительного стекла черно-белое графическое изображение, напечатанное в газете или книге, то можно увидеть, что оно состоит из мельчайших точек, образу
Кодирование звуковой информации
В отличие от текстовых, числовых и графических данных, у звукозаписей не было столь длительной истории кодирования. Методы кодирования звуковой информации двоичным кодом далеки от с
Представление команд
В общем случае команда состоит из операционной части и адресной части.
Каждая ЭВМ имеет свой набор команд. Полный набор к
Режимы и технологии работы с базами данных
Система управления базами данных имеет два режима работы: проектировочный и пользовательский. Первый режим предназначен для создания или изменения структуры базы данных и создания инструментов для
Получение информации из Интернета
Интернет – всемирная компьютерная сеть. Если два компьютера, находящиеся на разных континентах, обмениваются данными в Интернете, это совсем не значит, что между ними действует одно
Структура документа на языке HTML
1) Документ HTML всегда должен начинаться с тега <HTML> и заканчиваться соответствующим закрывающимся тегом </HTML>.
2) Внутри документа выделяются два основных раздела: раздел
Функциональные блочные элементы
Основными функциональными элементами являются заголовки и абзацы. Язык HTML поддерживает шесть уровней заголовков. Они задаются при помощи парных тегов <H1> до <H6>. Эти элементы отобра
Web-графика
Графические элементы Web-страниц используют два основных формата – GIF и JPEG (допустим формат PNG).
Файлы формата GIF (Graphic Interchange Format) – файл упакован и занимает меньше места,
Средства антивирусной защиты
Основным средством защиты информации является резервное копирование наиболее ценных данных. В случае утраты информации по какой-либо причине жёсткие диски переформатируют и подготавливают к новой э
Понятие несимметричного шифрования информации
Обычный подход состоит в том, что к документу применяется некий метод шифрования (назовём его ключом), после чего документ становится недоступен для чтения обычными средствами. Его может про
Принцип достаточности защиты
Защита публичным ключом (впрочем, как и большинство других видов защиты информации) не является абсолютно надёжной. Поскольку каждый желающий может получить и использовать чей-то публичный ключ, то
Понятие электронной подписи
Итак, клиент может переслать организации свои конфиденциальные данные (например, номер электронного счёта). Точно так же он может общаться и с банком, отдавая ему распоряжения о пер
Понятие электронных сертификатов
Системой несимметричного шифрования обеспечивается делопроизводство в Интернете. Благодаря ей каждый из участников обмена может быть уверен, что полученное сообщение отправлено именно тем, кем оно
Математические основы синтеза схем
Физическим аналогом букв двоичного алфавита (0 и 1) в схемах ЭВМ являются низкий и высокий потенциал, отсутствие и наличие импульса и т.п. Работу любой схемы ЭВМ можно представить следующим образом
Основы булевой алгебры. Булевы функции
Переменные, принимающие два значения: 0 и 1 (ложь и истина), называются булевыми (двоичными, логическими).
Основными операциями булевой алгебры является инверсия, конъюнкция и дизъюнкция.
Законы булевой алгебры.
Законы булевой алгебры можно выразить в виде формул:
Удобно выделить законы, облегчающие преобразования формул к более пр
Основы автоматных преобразований
Цифровой (конечный) автомат – это образ элемента с конечной памятью, который реализуется через механизм «смены состояний», каждое из которых отражает некоторую предысторию поступления входных сигна
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов