 |
В журнале каждый новый элемент списка заносится с новой строки, т. е. разделитель конец строки. Нужный элемент разыскивается по номеру строки.
|
|
|
|
Разделителем может быть специальный символ. Так разделители между словами — пробелы. Разделитель предложений — точка.
В журнале разделителем может быть любой символ, не встречающийся в данных, например, «*». Тогда список имеет вид:
Аистов Александр Алексеевич * Бобров Борис Борисович * Воробьева Валентина
Владиславовна *... * Сорокин Сергей Семенович
Для розыска элемента с номером n надо просмотреть список начиная с начала и пересчитать встретившиеся разделители. Когда будет отсчитано n -1 разделителей, начнется нужный элемент. Он закончится, когда встретится следующий разделитель.
Если элементы списка имеют равную длину, разделители не нужны. Для розыска элемента с номером n надо просмотреть список с начала и отсчитать а(п-1) символ, где a — длина одного элемента. Со следующего символа начнется нужный элемент.
Его длина тоже равна a, поэтому его конец определить нетрудно. Списки, состоящие из элементов равной длины, называют векторами данных.
Линейные структуры данных (списки) — это упорядоченные структуры, в которых адрес элемента однозначно определяется его номером.
ТАБЛИЧНЫЕ СТРУКТУРЫ
(ТАБЛИЦЫ ДАННЫХ, МАТРИЦЫ ДАННЫХ)
В таблицах элементы данных определяются адресом ячейки, состоящим из нескольких параметров. В таблице умножения адрес ячейки определяется номерами строки и столбца. Нужная ячейка находится на их пересечении, а элемент выбирается из ячейки.
При хранении табличных данных количество разделителей больше, чем для списка. Например, при печати таблицы в книгах, строки и столбцы разделяют графическими элементами — линиями вертикальной и горизонтальной разметки.
Если нужно сохранить таблицу в виде длинной символьной строки, используют один символ-разделитель между элементами, принадлежащими одной строке, и другой разделитель для отделения строк, например, так:
|
|
|
Меркурий*0>39*0,056*0#Венера*0167*0,88*0#Земля*1,0*1,0*1 #Марс*1,51*0,1*2*...
Для розыска элемента, имеющего адрес ячейки (m, n), надо просмотреть набор данных с начала и пересчитать внешние разделители. Когда будет отсчитан m-\ разделитель, надо пересчитывать внутренние разделители. После того как будет найден n-1 разделитель, начнется нужный элемент. Он закончится, когда будет встречен любой очередной разделитель.
Если все элементы таблицы имеют равную длину, такие таблицы называют матрицами.
Разделители не нужны, все элементы имеют равную длину и количество их известно. Для розыска элемента с адресом (т, п) в матрице, имеющей М строк и N столбцов, надо просмотреть ее с начала и отсчитать a [N(m - 1) + (п - 1)] символ, где а — длина одного элемента. Со следующего символа начнется нужный элемент. Его длина тоже равна а, поэтому его конец определить нетрудно.
Табличные структуры данных (матрицы) — это упорядоченные структуры, в которых адрес элемента определяется номером строки и номером столбца, на пересечении которых находится ячейка, содержащая искомый элемент.
Многомерные таблицы.
ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Нерегулярные данные, которые трудно представить в виде списка или таблицы, часто представляют в виде иерархических структур. Иерархическую структуру имеет система почтовых адресов. Подобные структуры также широко применяют в научных систематизациях и всевозможных классификациях.
В иерархической структуре адрес каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу.
Например, путь доступа к команде, запускающей программу Калькулятор:
Пуск • Программы • Стандартные • Калькулятор.
|
|
|
Дихотомия данных. Основным недостатком иерархических структур данных является увеличенный размер пути доступа. Часто длина маршрута оказывается больше, чем длина данных, к которым он ведет. Поэтому в информатике применяют методы для регуляризации иерархических структур с тем, чтобы сделать путь доступа компактным. Один из методов получил название дихотомии.
В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору Word 2000 выразится следующим двоичным числом: 1010.
УПОРЯДОЧЕНИЕ СТРУКТУР ДАННЫХ
Списочные и табличные структуры - простые. Адрес каждого элемента задается числом (для списка), двумя числами (для двумерной таблицы) или несколькими числами для многомерной таблицы. Они легко упорядочиваются.
Основной метод упорядочения - сортировка. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра.
У простых структур данных есть и недостаток — их трудно обновлять. Если, например, перевести студента из одной группы в другую, изменятся два журнала; в обоих нарушится списочная структура. Если переведенного студента вписать в конец списка, нарушится упорядочение по алфавиту, если вписать по алфавит, то изменятся порядковые номера всех студентов, которые следуют за ним.
При добавлении произвольного элемента в упорядоченную структуру списка может происходить изменение адресных данных у других элементов. В системах, выполняющих автоматическую обработку данных, нужны специальные методы для решения этой проблемы.
Иерархические структуры данных по форме сложнее, но они не создают проблем с обновлением данных. Их легко развивать путем создания новых уровней. Даже если в учебном заведении будет создан новый факультет, это никак не отразится на пути доступа к сведениям об учащихся прочих факультетов.
Недостаток иерархических структур -- относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т. п. Ранее рассмотренный принцип дихотомии на самом деле является одним из методов индексации данных в иерархических структурах. После такой индексации данные легко разыскиваются по двоичному коду связанного с ними индекса.
|
|
|
Адресные данные. Если данные хранятся не как попало, а в организованной структуре (причем любой), то каждый элемент данных приобретает новое свойство (параметр), который можно назвать адресом. Конечно, работать с упорядоченными данными удобнее, но за это приходится платить их размножением, поскольку адреса элементов данных — это тоже данные и их тоже надо хранить и обрабатывать.
КОМПЬЮТЕРНЫЕ СЕТИ
|
|
|
