Технологии Программирования. 8 лекция

Тема 6:

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

очереди и списка.

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

1. Очередь – СД, для которой определены операции добавления и удаления элементов по принципу FIFO («первым пришел – первым обслуживается-выходит»).

Простейший способ реализации очереди – массив и два указателя. Первый указатель Start указывает на начало очереди, второй Last – на конец.

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

Конец очереди - это номер элемента массива, в который будут заноситься данные.

Опр. Очередь, в которой нет ни одного элемента, называется пустой. Изображение очереди (1ый элемент А, последний – С)

ОПЕРАЦИИ над очередями и

их компьютерная реализация

1) Добавление элемента (записать D в позицию Last, а затем передвинуть указатель Last на один элемент в право

// max_queue - Размер очереди void Add(int Last, int Number)

{if (Last = = max_queue) exit(1); // очередь полна

2) Удаление элемента (удаляем элемент, который первым вошел, то есть А. Удаляется он смещением указателя Start вправо на 1)

void Remove(int Start, int Last)

3) Проверка пустоты очереди (на наличие элементов)

int Empty(int Start, int Last)

{if (Start == Last) return 0; // очередь пуста

}

Empty (анлг.) - пустой

ПРИМЕР 1

Дана матрица M*N, заполненная 0 и -1.

Рассмотрим программу, которая определяет количество нулевых островов. Остров – совокупность смежных клеток матрицы, содержащих нули

const int N=4; const int M=4;

int A[N+2][M+2]={ {-1, -1, -1, -1, -1, -1},

{-1, 0, 0, -1, -1, -1}, {-1, 0, -1, 0, 0, -1}, {-1, -1, 0, -1, 0, -1}, {-1, 0, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1}

};

/* Для того чтобы не выйти за пределы матрицы при проверке смежных

клеток добавлены внешние границы */

// определяем переменные на внешнем уровне, видны во

всех функциях

int Queue[2][M*N]; // очередь

int Start,Last; // указатели начало и конец очереди int Label, i,j,p,a,b;

void Add(int x, int y); // функция добавления элемента в очередь

{

Queue[0][Last] =x ; Queue[1][Last] =y ;

// заносим в очередь координаты Last++; //сдвигаем указатель вправо

}

// функция ищет нулевой элемент и заносит координаты элемента в очередь

void Find()

{ p=0; // в матрице есть нулевые элементы for(i=1; i<=N&& p= =0; i++)

for(j=1; j<=M&& p= =0; j++)

// если есть нулевой элемент, то if(A[i][i] = = 0)

{ p=1; Add(i,j);

// заносим координаты в очередь

}

}

// определяем границы острова

void test() { Label++;

// изменили количество островов и начинаем поиск нового острова

while (Start!=Last) // пока очередь не пуста

{a=queue[0][Start]; // запоминаем x координату текущей клетки b=queue[1][Start]; // запоминаем y координату текущей клетки

// проверяем все клетки, смежные с текущей

if(A [a+1][b] = = 0) Add(a+1,b); if(A [a-1 ][b] = = 0) Add(a-1,b); if(A [a][b+1] = = 0) Add(a,b+1);

if(A [a][b-1] = = 0) Add(a,b -1);

Start=++; // удаляем первый элемент из очереди

}

}

main()

{Start=0;

Last=0;

Label=0;

p=1;

do{ Find();

//вызываем функцию, которая проверяет есть ли нулевой элемент

//на выходе p=0 (нет ) или p=1 (да есть)

if(p = = 1) test();

//нулевой элемент есть , проверяем смежные клетки

} while(p = = 1);

cout Label; // количество островов

…

}