Упорядочение структур данных

Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка), двумя числами(для двумерной таблицы) или несколькими числами для многомерной таблицы. Они также легко упорядочиваются. Основным методом упорядочения является сортировка. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра.

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

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

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

Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т. п. Ранее рассмотренный принцип дихотомии на самом деле является одним из методов индексации данных в иерархических структурах. После такой индексации данные легко разыскиваются по двоичному коду связанного с ними индекса.

Адресные данные. Если данные хранятся не как попало, а в организованной структуре (причем любой), то каждый элемент данных приобретает новое свойство (параметр), который можно назвать адресом. Конечно, работать с упорядоченными данными удобнее, но за это приходится платить их размножением, поскольку адреса элементов данных — это тоже данные, и их тоже надо хранить и обрабатывать.

 

6. Единицы измерения данных

Единицы измерения данных

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

Память носителей в свою очередь имеет ограниченную ёмкость, т.е. способность вместить в себе определенный объем.

· Бит — базовая единица измерения количества информации, равная количеству информации, содержащемуся в опыте, имеющем два равновероятных исхода. Это тождественно количеству информации в ответе на вопрос, допускающий ответы «да» либо «нет» и никакого другого (то есть такое количество информации, которое позволяет однозначно ответить на поставленный вопрос). Один разряд двоичного кода (двоичная цифра). Может принимать только два взаимоисключающих значения: да/нет, 1/0, включено/выключено, и т. п. В электронике 1 двоичному разряду соответствует 1 двоичный триггер, который имеет два устойчивых состояния.

· Байт (англ. byte) — единица хранения и обработки цифровой информации. В настольных вычислительных системах байт считается равным восьми битам, в этом случае он может принимать одно из 256 (2⁸) различных значений. Следует понимать, что количество бит в байте не является однозначной величиной и может варьироваться в широком диапазоне. Так, в первых компьютерах размер байта был равен 6 битам. В суперкомпьютерах, вследствие используемой адресации, один байт содержит 32 бита. Для того, чтобы подчеркнуть, что имеется в виду восьмибитный байт, а также во избежание широко распростанённого заблуждения, что в одном байте исключительно восемь бит, в описании сетевых протоколов используется термин «октет» (лат. octet). Байт в современных x86-совместимых компьютерах — это минимально адресуемый набор фиксированного числа битов.

· Килоба́йт (кБ, Кбайт, КБ) м., скл. — единица измерения количества информации, равная в зависимости от контекста 1000 или 1024 (2¹⁰) стандартным (8-битным) байтам. Применяется для указания объёма памяти в различных электронных устройствах.

1 килобайт (КБ) = 8 килобит (Кб)

Название «килобайт» часто применяется для 1024 байт, но формально неверно, так как приставка кило-, традиционно означает умножение на 1000, а не 1024. Согласно предложению МЭК, формально правильной (хотя и относительно редко используемой) для 2¹⁰ является двоичная приставка киби-.

Исторически сложилось, что со словом «байт» несколько некорректно (вместо 1000 = 10³ принято 1024 = 2¹⁰) использовали и продолжают использовать приставки СИ: 1 Кбайт = 1024 байт, 1 Мбайт = 1024 Кбайт, 1 Гбайт = 1024 Мбайт и т. д. При этом обозначение Кбайт начинают с прописной буквы в отличие от строчной буквы «к» для обозначения множителя 10³.

· Мегаба́йт (Мбайт, М, МБ) м., скл. — единица измерения количества информации, равная, в зависимости от контекста, 1 000 000 (10⁶) или 1 048 576 (2²⁰) стандартным (8-битным) байтам. Сокращенное название МБ отличается от Мегабита (Мб) строчной буквой (но на самом деле иногда происходит некоторая путаница в сокращениях). Применяется для указания объёма памяти в различных электронных устройствах.

· Гигабайт (Гбайт, Г, ГБ) — кратная единица измерения количества информации, равная 10⁹ стандартным (8-битным) байтам или 1 000 000 000 байтам. Применяется для указания объёма памяти в различных электронных устройствах. От сложившегося положения нередко страдают потребители продукции крупных корпораций, производящих жёсткие диски и карты флэш-памяти. Приобретая изделие, в маркировке которого указана его реальная емкость, например, 1 гигабайт или 1 000 000 000 байт они полагают, что приобретают изделие емкостью 1 гибибайт или 1 073 741 824 байт, что нередко приводит к непониманию и недовольству.

Байт- мельчайшая адресуемая единица информации

Килобайт – базовая единица

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

· разрядность данных, обрабатываемых процессором;

· разрядность адресуемых данных (разрядность шины данных);

· максимальное значение беззнакового целого типа, напрямую поддерживаемого процессором: если результат арифметической операции превосходит это значение, то происходит переполнение;

· максимальный объём оперативной памяти, напрямую адресуемой процессором.

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

Се́ктор диска — минимальная адресуемая единица хранения информации на дисковых запоминающих устройствах. Является частью дорожки диска. У большинства устройств размер сектора составляет 512 байт, либо 2048 байт (например, у оптических дисков).

Для более эффективного использования места на диске файловая система может объединять секторы в кластеры, размером от 512 байт (один сектор) до 64 кбайт (128 секторов). Переход к кластерам произошел потому, что размер таблицы FAT был ограничен, а размер диска увеличивался. Количество секторов на цилиндрах ранее было одинаковым, на современных дисках количество секторов на цилиндр разное, но контроллер жёсткого диска сообщает о некоем условном количестве дорожек, секторов и сторон, хотя позднее была создана система обращения к дискам, в которой все секторы пронумерованы. Первый сектор диска обычно является загрузочным.

7. Файловая структура

Файловая система (ФС)- функциональная часть ОС, т.е. это порядок хранения и - организации файлов на диске

Виды файловой структуры: 1) Одноуровневая ФС - линейная последовательность имен файлов, используется для дисков с небольшим количеством файлов; 2) Многоуровневая иерархическая ФС - представляет собой древовидную структуру, служит для хранения сотни и тысячи файлов. Каталог (Папка) верхнего уровня содержит вложенные папки 1уровня, которые могут содержать папки 2 уровня и тд

Для хранения информации каждый диск разбивается на 2 области: 1) каталог (directory) или папка - содержит названия файлов и указание на начало их размещения на диске; 2) область хранения файлов, содержит текст.

Чтобы найти файл надо знать: 1)имя файла; 2) где храниться файл

например:

C:\GAMES\CHESS\zena.exe

Имя диска – С

папка 1уровня –GAMES

папка 2уровня –CHESS; имя файла - zena.exe

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

 

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

Файл – это последовательность произвольного числа байтов, обладающая уникальным собственным именем.

Хранение файлов организуется в иерархической структуре, которая в данном случае называется файловой структурой. В качестве вершины структуры служит имя носителя, на котором сохраняются файлы. Далее файлы группируются в папки, внутри которых могут быть созданы вложенные папки. Путь доступа к файлу начинается с имени устройства и включает все имена папок, через которые проходит. В качестве разделителя используется символ "\" (обратная косая черта).

Полным именем файла считается собственное имя файла вместе с путем доступа к нему

<имя носителя>\<имя папки 1>\…<имя папки n> \имя файла.

По способам именования файлов различают "короткое" и "длинное" имя. До появления Windows95 существовало соглашение, согласно которому имя файла состоит из 2-х частей: собственно имени и расширения имени. На имя файла отводится 8 символов, а на его расширение – 3 символа. Имя от расширения отделяется точкой. Как имя, так и расширение могли включать только символы латинского алфавита. Такие имена файлов назывались "короткими". Их недостаток – низкая содержательность. С появлением Windows95 было введено понятие "длинного" имени. Такое имя может содержать до 256 символов. "Длинное" имя может содержать любые символы, кроме 9 специальных: \, /,:, *,?, ", <, >, |. В имени разрешается использовать пробелы и несколько точек. Расширением имени считаются все символы, идущие после последней точки.

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

Атрибуты – это дополнительные параметры, определяющие свойства файлов.

Атрибут Только чтение ограничивает возможности работы с файлом. Его установка означает, что файл не предназначен для внесения изменений.

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

Атрибутом Системный помечаются файлы, обладающие важными функциями в работе самой операционной системы.

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

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

К основным операциям с файловой структурой относятся:

· навигация по файловой структуре;

· запуск программ и открытие документов;

· создание папок;

· копирование файлов и папок;

· перемещение файлов и папок;

· удаление файлов и папок;

· переименование файлов и папок;

· создание ярлыков.

Навигация по файловой структуре

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

Операционная система Windows предоставляет несколько методов навигации по файловой структуре. Основными средствами навигации являются программа Проводник и система окон Мойкомпьютер.

При работе с файловой структурой следует иметь в виду:

· при перетаскивании значков объектов между папками, принадлежащими одному диску, автоматически выполняется перемещение объектов. Если нужно выполнить копирование, используют специальное перетаскивание;

· при перетаскивании значков объектов между папками, принадлежащими разным дискам, автоматически выполняется копирование объектов. Если нужно выполнить перемещение, используют специальное перетаскивание.

8. Предмет и задачи информатики