Представление данных в памяти ЭВМ

⇐ ПредыдущаяСтр 4 из 6Следующая ⇒

Данные хранятся в памяти компьютера. При этом различают логическую (в программе) и физическую (в памяти) структуры данных. Эффективность алгоритмов зависит от того, насколько согласованы обе эти структуры.

Память современных ЭВМ имеет линейную организацию. Она представляет собой последовательность ячеек (строк). Наименьшей адресуемой единицей является байт. Данные имеют размер, равный 1 или нескольким байтам. Память для них выделяется компилятором.

Так для простых (скалярных) типов данных в разных компьютерах и языках программирования используются следующие объемы памяти.

a) Булевский тип – 1 байт (причем для задания значений «истина» или «ложь» достаточно 1 бита, оно берется из младшего разряда байта);

b) Символьный – 1 байт ( в java – 2 байта);

c) Целочисленный – 2 или 4 байта;

d) Вещественный – 4 или 8 байт;

e) Строковый – до 256 байт.

Сложные типы могут размещаться в смежных ячейках памяти или произвольно.

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

Имя

Адрес (элемент(index)) = Начало + размер_ячейки * index.

Такой подход облегчает работу с массивом. Его элементы могут обрабатываться последовательно или в любом порядке.

Линейные списки обычно располагаются в памяти последовательно (как массивы). Этот порядок часто нарушается при выполнении операций вставок и удалений.

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

Деревья представляют собой связные списки соответствующей структуры. Они хранятся аналогично.

Графы и таблицы принято представлять таблицами связности, смежности и др., т.е. двумерными массивами.

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

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

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

Базовые алгоритмы обработки данных

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

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

2) Алгоритмы обработки строк, которые включают в себя ряд методов обработки длинных последовательностей символов. Наиболее распространенными являются задачи поиска подстроки в строке.

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

4) Алгоритмы на деревьях, которые используются при решении ряда важных задач. Одной из основных задач является поиск и сортировка на двоичных и В - деревьях. Эти структуры позволяют существенно упростить решение таких задач.

АЛГОРИТМЫ ПОИСКА

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

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

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

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

Общий алгоритм поиска ключа можно представить так.

1. Ввести исходный массив (ключей).

2. Повторять

ввести аргумент поиска и вывести результат

пока не надоест.

3. Закончить.

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

Наиболее распространенными являются три алгоритма поиска:

1) Линейный;

2) Дихотомический:

3) Интерполирующий.

1.1. Алгоритм линейного поиска

В соответствии с этим алгоритмом эталонный массив просматривается последовательно от первого до последнего элемента. Наиболее сложным, как уже отмечалось, является случай, когда ключа нет в таблице (не найден).

Уточненный алгоритм будет таким.

1. Ввести исходный массив (ключей).

2. Выполнять

2. 1. Ввести аргумент поиска (целое число);

2. 2. Если аргумент поиска больше или равен нулю,

2.2.1. Результат (номер в массиве, num) = - 1 (не найден, такого номера нет);

2.2.2. Для индекса массива (i) от 0 до Длина.массива

Если аргумент поиска = ключ[i],

номер в массиве (num) = i;

2.2.3. Если номер num = - 1,

вывести: «Такого ключа в массиве нет»,

Иначе

вывести: «Ключ найден под номером num».

пока будет аргумент поиска больше или равен нулю.

3. Закончить.

Обозначим массив ключей key, а аргумент поиска - arg. Тогда соответствующий фрагмент программы линейного поиска будет иметь вид, приведенный ниже.

public static void main (String[] args) {

Scanner sc=new Scanner(System.in);

int n;

System.out.print(" Введите количество элементов массива => " );

n=sc.nextInt();

System.out.println(" \tВведите элементы массива " );

int key[]=new int[n];

for (int i = 0; i < key.length; i++)

key[i]=sc.nextInt();

System.out.println(" \n Поиск ключа" );

do{

int arg, num;

System.out.println(" \n Введите аргумент поиска – искомый ключ" );

arg=sc.nextInt();

if (arg> =0){

num=-1;

for (int i = 1; i < key.length; i++)

if (arg==key [i])

num=i;

if (num =-1)

System.out.println(" Такого ключа нет" );

else

System.out.println(" Ключ найден под номером “+ num);

} while (arg> =0);

}

Основной недостаток алгоритма линейного поиска – большое время. При использовании оператора For для поиска ВСЕГДА выполняется ровно n операций сравнения, не зависимо от того, найден ключ или нет. Поэтому программа, обнаружив аргумент в начале массива, продолжает его просмотр до конца, т.е. выполняет бесполезную работу. Время поиска может быть существенно сокращено, если обеспечить его прекращение, когда ключ найден. При равномерном распределении элементов в таблице эталонов (ключей) среднее время поиска может стать пропорциональным величине n / 2.

Этого можно достичь, изменив пункт 2 в рассмотренном выше алгоритме следующим образом.

Ускорение линейного поиска

2. Выполнять

2. 1. Ввести аргумент поиска (целое число);

2. 2. Если аргумент поиска больше или равен нулю,

2.2.1. Результат (num) = - 1 (не найден);

2.2.2. Начальный индекс, i=0;

2.2.3. Пока (num=-1) и (i< =n – Длины.массива)

a) Если аргумент поиска = ключ[i],

номер в массиве (num) = i;

b) i=i + 1

2.2.4. Если номер num = - 1,

вывести: «Такого ключа в массиве нет»,

Иначе

вывести: «Ключ num найден».

пока будет аргумент поиска больше или равен нулю.

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

// Ускорение линейного поиска }

do{

int arg, num, i;

System.out.println(" \n Введите аргумент поиска – искомый ключ" );

arg=sc.nextInt();

if (arg> =0){

num=-1;

int i=0;

while ((num=-1) & & (i < key.length)) {

if (arg==key [i])

num=i;

i++;

}

if (num =-1)

System.out.println(" Такого ключа нет" );

else

System.out.println(" Ключ" +num+” найден“);

} while (arg> =0);

}

Трудоемкость (временная сложность) алгоритма линейного поиска определяется числом операций сравнения, выполняемых при просмотре таблицы эталонов. В лучшем случае количество таких операций равно 1, в худшем – n, а в среднем, если возможные значения ключей равновероятны, - n / 2. Таким образом, асимптотическая оценка О(n) = n.

⇐ Предыдущая 1 2 345 6 Следующая ⇒