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

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

В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как "char", "int", "double". На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с "машиной данных", которая управляет способом доступа к информации в вашей программе. Имеется четыре такие "машины":

• очередь;

• стек;

• связанный список;

• двоичное дерево.

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

Очереди

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

В повседневной жизни очереди встречаются часто. Например, очередь в банке или очередь в кафетериях с быстрым обслуживанием являются очередью в указанном выше смысле /исключая те случае, когда человек пытается добиться обслуживания вне очереди!/. Для того, чтобы лучше понять работу очереди, рассмотрим две процедуры: постановка в очередь и выборка из очереди. При выполнении процедуры постановки в очередь элемент помещается в конец очереди. При выполнении процедуры выборки из очереди из нее удаляется первый элемент, который является результатом выполнения данной процедуры. Работа очереди проиллюстрирована на рис.1. Следует помнить, что при выборке из очереди из нее действительно удаляется один элемент. Если этот элемент нигде не будет сохранен, то в последствии к нему нельзя будет осуществить доступ.

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

#define n 100

int querry[n];

int first;

int dl;

void add(int a){

if(dl<n){

querry[(first+dl)%n]=a;

dl++;

}

}

int del(void){

int x;

if(dl>0)

x=querry[first];

first = (first+1) % n;

dl--;

return(x);

}

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

Пример использования очереди.

Напечатать в порядке возрастания первые n натуральных чисел, в разложении которых на простые множители встречаются только числа 2, 3 и 5.

Заведем три очереди x2,x3,x5.

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

void printAdd(int t ){

printf(“%d”,t);

add(x2,2*t);

add(x3,3*t);

add(x5,5*t);

}

Тогда главная программа должна выглядеть так:

printfAdd(1);

for(k=1; k<n; k++){

x=min(очередной элемент x2, очередной элемент x3, очередной элемент x5);

printAdd(x);

Удалить x из очередей, где он был очередным.

}

Упр. Дописать данную программу.

СТЕКИ

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

Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "push" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" /вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или динамически выделять память под вновь прибывающие элементы.

Реализуем стек на базе массива.

#define n 100

int st[n];

int top=0;

void push(int x){

st[top]=x;

top++;

}

int pop(void){

top--;

return(st[top]);

}

Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые калькуляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.

Ниже показан фрагмент программы для такого калькулятора. Для простоты считаем, что все числа лежат от 0 до 9.

char *st = “53+42-*”;

for(int i=0; st[i]; i++){

if( isdigit(st[i]))

push(st[i]-‘0’);

else{

x=pop();

y=pop();

switch(st[i]){

case ‘+’: push(x+y);break;

case ‘-’: push(y-x);break;

case ‘*’: push(x*y);break;

case ‘/’: push(x/y);break;

}

}

}