массива. Таким образом, в результате каждой проверки вдвое сужается область поиска. Например, если в массиве 100 чисел, то после первой итерации область поиска уменьшается до 50 чисел, после второй – до 25, после третьей до 13, после четвертой до 7 и т.д. Если длина массива равна n, то для поиска в массиве элементов достаточно около log2n сравнений.

int BinarySearch (int lb, int ub, int key, int* pArr)

/* a – исходный массив, lb – левая граница поиска, ub – правая граница поиска, key – значение искомого элемента. Функция возвращает индекс совпадающего элемента в массиве, и -1 – если элемент не найден */

{

int m;

return(-1); // функция возвращает -1 , если элемент не найден do

{ m = (lb + ub)/2; //находим индекс «половинки» массива if (key < pArr[m]) ub = m-1;

else

if (key > pArr[m]) lb = m+1; else

{ // найдено совпадение return(m);

} break;

}

}

while (lb > ub);

Динамические структуры данных

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

Например, если указан массив char S[10];

то под него один раз в начале выполнения программ выделяется 10 байт оперативной памяти.

147

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

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

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

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

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

Достоинства связного представления данных:

∙в возможности обеспечения значительной изменчивости структур;

∙размер структуры ограничивается только доступным объемом машинной памяти;

∙при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;

∙большая гибкость структуры.

Вместе с тем связное представление не лишено и недостатков, основные из которых:

∙ на поля связок расходуется дополнительная память;

148

∙доступ к элементам связной структуры может быть менее эффективным по времени.

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

К динамическим структурам, используемым в программировании, относятся:

∙динамические массивы (были рассмотрены в теме 6);

∙линейные списки;

∙стек;

∙очередь, дек;

∙деревья.

Линейные списки

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

149

Графически связи в списках удобно изображать с помощью стрелок, как было показано в разделе описания указателей. Если элемент списка не связан с любым другим, то в поле указателя записывают значение, не указывающее ни на какой элемент (пустой указатель). Такая ссылка в Паскале обозначается nil, а на схеме обозначается перечеркнутым прямоугольником. Ниже приведена структура односвязного списка (рис.40), т.е. связь идет от одного элемента списка к другому в одном направлении. Здесь поле D – это информационное поле, в котором находятся данные (любой допустимый в языке Паскаль тип), поле N (NEXT) – указатель на следующий элемент списка.

Рис.40. Пример односвязного линейного списка

Каждый список должен иметь следующие указатели: Head – голова списка, Cur – текущий элемент списка, иногда в односвязных списках также используется указатель Tail – хвост списка (в двухсвяхных списках он используется всегда). Поле указателя последнего элемента списка является пустым, в нем находится специальный признак nil, свидетельствующий о конце списка и обозначается перечеркнутым квадратом.

Двухсвязный линейный список отличается от односвязного наличием в каждом узле списка ещё одного указателя B (Back), ссылающегося на предыдущий элемент списка (рис.41).

H N D

N D B C

T D B

Рис.41. Пример двухсвязного линейного списка

150

Структура данных, соответствующая двухсвязному линейному списку описывается на языке Си следующим образом:

struct list

{

int value; // значение элемента

}

struct list *next; // указатель на следующий элемент struct list *back; // указатель на предыдующий элемент

При работе с линейными списками используются следующие основные операции:

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

∙добавление нового элемента в список: в голову списка, в хвост списка, после текущего элемента списка, перед текущим элементом списка;

∙удаление элемента из списка;

∙обход списка с целью его обработки;

∙поиск узла в списке;

∙переход на узел в списке по номеру от начала и другие операции.

Создание списка

При создании списка нужно выполнить следующие действия (рис. 42):

∙выделить память;

∙«обнулить» указатели на предыдущий и последующий элементы;

∙определить указатели на голову, хвост и текущий элемент списка;

∙внести в информационную часть списка данные.

list* ptr = new list; ptr -> next = NULL;

ptr -> back = NULL; tail cur tail = ptr;

head = ptr; cur = ptr;

ptr -> value = val;

Рис.42. Процедура создания списка

Добавление нового узла в список

Для добавления нового узла в голову списка нужно выполнить последоватеьность действий, указанных в табл.15.

151

2.Заполнить информационную часть узла и

4.2.Для головы списка предыдущий указатель

4.3.Установить на новый узел указатель на голову

head

int val; list head;

list* ptr = new list; ptr->value = val; ptr->next = NULL; ptr->back = NULL;

if (head == Nil) head = ptr //список пустой?

152

else

{

Ptr->next = head;

Head->back = ptr;

}

Head = ptr;

Добавление в хвост списка и после текущего узла списка (или перед текущим) делается аналогично:

int s list tail;

list* ptr = new list; ptr->value = val; ptr->next = NULL; ptr->back = NULL;

if (tail == NULL) tail = ptr //список пустой? else

{

}

tail->next = ptr; prt->back = tail; tail = ptr;

Удаление узла из списка

При удалении узла из списка нужно рассмотреть следующие ситуации:

1.Удаляемый узел является головой списка.

2.Удаляемый узел является хвостом списка.

3.Удаляемый узел единственный в списке.

4.Удаляемый узел не является ни головой, ни хвостом, ни единственным в списке.

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

153

5. Освобождаем память, выделенную динамически для удаляемого узла списка:

free(tail); cur

154

//удаление узла в списке list head,tail,cur, temp;

// проверяем является ли узел единственным в списке?

if ((cur->next == NULL) && (cur->back = NULL))

{

head = NULL;

tail = NULL; // делаем список пустым free(cur);

}

cur = NULL; //освобождаем память

elseif (cur->next == NULL) // текущий узел является хвостом?

{tail = tail->back; // Хвостом теперь станет предпоследний узел tail->next = NULL;

free (cur); cur = tail;

}

else

if (cur->back == NULL) // текущий узел является головой?

{head = head->next; // головой становится второй узел списка head->back = NULL;

free (cur); cur = head;

}

else //узел ни голова, ни хвост, ни единственный в списке

{cur->back->next = cur->next; cur->next->back = cur->back; temp = cur;

cur = cur->next; free (temp);

};

}

Обход списка и переход к узлу по номеру от головы списка

Обход списка осуществляется с целью анализа, обработки и поиска данных находящихся в списке. Заметим, что переход к следующему узлу осуществляется присваиванием указателю C на текущий узел значения указателя на следующий узел cur->next. Но по определению списка, последний узел в списке содержит пустой указатель на следующий узел. А значит это и является признаком конца обхода списка. Таким образом, стандартный алгоритм обхода списка прост:

3.Выполнять в цикле:

4.Обработать текущий узел.

5.Перейти к следующему узлу.

6.До тех пор пока указатель на следующий узел станет пустым.

155