С таблицами данных мы тоже хорошо знакомы, достаточно вспомнить всем известную таблицу умножения. Табличные структуры отличаются от списочных тем, что элементы данных определяются адресом ячейки, который состоит не из одного параметра, как в списках, а из нескольких. Для таблицы умножения, например, адрес ячейки определяется номерами строки и столбца. Нужная ячейка находится на их пересечении, а элемент выбирается из ячейки.
При хранении табличных данных количество разделителей должно быть больше, чем для данных, имеющих структуру списка. Например, когда таблицы печатают в книгах, строки и столбцы разделяют графическими элементами — линиями вертикальной и горизонтальной разметки (рис. 1).
Если нужно сохранить таблицу в виде длинной символьной строки, используют один символ-разделитель между элементами, принадлежащими одной строке, и другой разделитель для отделения строк, например так:
Для розыска элемента, имеющего адрес ячейки (т, п), надо просмотреть набор данных с самого начала и пересчитать внешние разделители. Когда будет отсчитан т-1 разделитель, надо пересчитывать внутренние разделители. После того как будет найден n-1 разделитель, начнется нужный элемент. Он закончится, когда будет встречен любой очередной разделитель.
Планета
Расстояние до Солнца, а.е.
Относительная величина
Количество спутников
Меркурий
0,39
0,056
Венера
0,67
0,88
Земля
1,0
1,0
Марс
1,51
0,1
Юпитер
5,2
Рис. 1. В двумерных таблицах, которые печатают в книгах, применяется два типа разделителей - вертикальные и горизонтальные линии
Еще проще можно действовать, если все элементы таблицы имеют равную длину. Такие таблицы называют матрицами. В данном случае разделители не нужны, поскольку все элементы имеют равную длину и количество их известно. Для розыска элемента с адресом (т, п) в матрице, имеющей М строк и N столбцов, надо просмотреть ее с самого начала и отсчитать а [N(т - 1) + (п - 1)] символ, где а — длина одного элемента. Со следующего символа начнется нужный элемент. Его длина тоже равна а, поэтому его конец определить нетрудно.
Таким образом, табличные структуры данных (матрицы} — это упорядоченные структуры, в которых адрес элемента определяется номером строки и номером столбца, на пересечении которых находится ячейка, содержащая искомый элемент.
4. Основные структуры данных.Иерархические структуры данных.Упорядочивание структур данных.Дихотомия данных.
Иерархические структуры данных:Нерегулярные данные, которые трудно представить в виде списка или таблицы, часто представляют в виде иерархических структур. С подобными структурами мы очень хорошо знакомы по обыденной жизни. Иерархическую структуру имеет система почтовых адресов. Подобные структуры также широко применяют в научных систематизациях и всевозможных классификациях (рис. 2).В иерархической структуре адрес каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу. Вот, например, как выглядит путь доступа к команде, запускающей программу Калькулятор (стандартная программа компьютеров, работающих в операционной системе Windows):
Пуск > Программы > Стандартные > Калькулятор.
Рис. 2. Пример иерархической структуры данных
Дихотомия данных.Основным недостатком иерархических структур данных является увеличенный размер пути доступа. Очень часто бывает так, что длина маршрута оказывается больше, чем длина самих данных, к которым он ведет. Поэтому в информатике применяют методы для регуляризации иерархических структур с тем, чтобы сделать путь доступа компактным. Один из методов получил название дихотомии.
Рис. 3.Пример, поясняющий принцип действия метода дихотомии
Его суть понятна из примера, представленного на рис. 3.
В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору Word 2000 выразится следующим двоичным числом: 1010.
Упорядочение структур данных:Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка), двумя числами (для двумерной таблицы) или несколькими числами для многомерной таблицы. Они также легко упорядочиваются. Основным методом упорядочения является сортировка. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра.Несмотря на многочисленные удобства, у простых структур данных есть и недостаток — их трудно обновлять. Если, например, перевести студента из одной группы в другую, изменения надо вносить сразу в два журнала посещаемости; при этом в обоих журналах будет нарушена списочная структура. Если переведенного студента вписать в конец списка группы, нарушится упорядочение по алфавиту, а если его вписать в соответствии с алфавитом, то изменятся порядковые номера всех студентов, которые следуют за ним.
Таким образом, при добавлении произвольного элемента в упорядоченную структуру списка может происходить изменение адресных данных у других элементов. В журналах успеваемости это пережить нетрудно, но в системах, выполняющих автоматическую обработку данных, нужны специальные методы для решения этой проблемы.Иерархические структуры данных по форме сложнее, чем линейные и табличные, но они не создают проблем с обновлением данных. Их легко развивать путем создания новых уровней. Даже если в учебном заведении будет создан новый факультет, это никак не отразится на пути доступа к сведениям об учащихся прочих факультетов.Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т. п. Ранее рассмотренный принцип дихотомии на самом деле является одним из методов индексации данных в иерархических структурах. После такой индексации данные легко разыскиваются по двоичному коду связанного с ними индекса.
5.Системы счисления. Понятие позиционной и непозиционной системы счисления.Перевод чисел из одной системы счисления в другую.Кодирование — представление символов одного алфавита символами другого. Информация для обработки ее компьютером кодируется с помощью двоичной системы счисления. Система счисления — способ представления любого числа с помощью алфавита символов, называемых цифрами. Системы счисления принято делить на позиционные и непозиционные.Непозиционная система счисления — это такая система, в которой вводится ряд символов для представления основных чисел, а остальные числа — результат их сложения и вычитания, (например, римская система счисления).Основные символы для обозначения десятичных разрядов в римской системе счисления: I — один, X — десять, С — сто, М — тысяча и их половины V — пять, L — пятьдесят, D — пятьсот. Натуральные числа записываются при помощи повторения этих цифр (например, II — два, III — три, XXX — тридцать, СС — двести). Если же большая цифра стоит перед меньшей цифрой, то они складываются, если наоборот — вычитаются (например, VII — семь, IX — девять).
Позиционная система счисления — это такая система, в которой любое число представляется в виде последовательности цифр, количественное значение которых зависит от их места (позиции) в числе (например, десятичная система счисления).
Любое число в позиционной системе счисления может быть представлено в следующем виде:
ap=anpn+an-1pn-1+…+a3p3+a2p2+a1p1+a0p0,где an, an-1, …, a2,a1,a0 – цифры в записи числа, p – основание системы счисления
Основание системы счисления — это количество символов в ее алфавите.
Буквенные обозначения систем счисления:
D — десятичная (decimal); В — двоичная (binary); О — восьмеричная (octal); Н — шестнадцатеричная (hex).
Алфавит десятичной системы состоит из десяти символов — 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 — называемых арабским цифрами. По правилам этой системы счисления символы располагаются, начиная с нулевой позиции и далее по возрастающей справа налево. Символ 1 в нулевой позиции — это единица, а в первой позиции — это уже 10 единиц.
Официальное "рождение" двоичной системы счисления связывают с именем Готфрида Вильгельма Лейбница. В 1703 г. он опубликовал статью, в которой были рассмотрены все правила выполнения арифметических действий над двоичными числами.
Примеры двоичного представления 2-х десятичных чисел в двоичной системе счисления
1205 = 100101101012 1197 = 100101011012
На первый взгляд оба двоичных представления почти не отличаются друг от друга, хотя закодированные числа совершенно разные.
Перевод из двоичной системы в десятичную и обратно — работа для компьютера, а не для человека. И все-таки для того, чтобы упростить перевод из двоичной системы в десятичную, ввели систему восьмеричную (в ее алфавите восемь символов: 0, 1, 2, 3, 4, 5, 6, 7). Восьмеричная система — компромисс между двоичной и десятичной системами. Числа в этой системе читаются легко и прост переход от двоичного представления к восьмеричному. В восьмеричной системе после 7 для увеличения числа нужно сместиться на один разряд влево, подобно тому, как в десятичной системе после 9 при увеличении числа на 1 выполняем смещение на один разряд влево.
Таким образом,О 10 = D8,Но 8 = 23, значит, сдвиг на 1 разряд влево в восьмеричной системе соответствует сдвигу на 3 разряда влево в двоичной системе.Переход из двоичной системы счисления в восьмеричную осуществляется заменой справа налево каждой триады двоичных цифр на одну восьмеричную цифру.И, наоборот: Переход из восьмеричной системы в двоичную осуществляется заменой каждой восьмеричной цифры тремя двоичными цифрами.
Например:О 162 = В 001 110010
Для перевода числа из любой системы счисления в десятичнуюнужно умножить содержимое каждого разряда на основание системы в степени, равной порядковому номеру разряда, и все сложить.
Например:0162 = 1 х 82 + 6 х 81 + 2 х8° = D114 В 1 1 10010 = 1х26+1х25 + 1х24 + - О х 2° = D 114
Для перевода числа из десятичной системы счисления в любую другую систему счислениянужно делить "до упора" это число на основание той системы, в которую переводим число, а потом прочесть остатки справа налево.Например: D 114 = О 162
