Пусть у нас есть очередь из трех элементов а, в и с, в которую первым был помещен элемент а, а последним элемент с. АВС Esimene Viimane Esimene начало. - презентация

1

2

3

4

5 Пусть у нас есть очередь из трех элементов а, в и с, в которую первым был помещен элемент а, а последним элемент с. АВС Esimene Viimane Esimene начало очереди) определяет место в массиве, откуда очередной элемент будет удаляться, Viimane (конец очереди) определяет место в массиве, куда очередной элемент будет добавляться.

6 Сначала обрабатывается элемент, который первый вошел в очередь, в нашем случае это элемент а. Он будет удален из очереди путем смещения указателя Esimene на один элемент вправо А EsimeneViimane Теперь добавим элемент b в очередь. Для этого необходимо записать b в позицию Viimane, а затем передвинуть указатель Viimane на один элемент вправо АВ EsimeneViimane

7 Добавим элемент c в очередь. Для этого необходимо записать c в позицию Viimane, а затем передвинуть указатель Viimane на один элемент вправо АBC EsimeneViimane Теперь добавим элемент d. Для этого необходимо записать d в позицию Viimane, а затем передвинуть указатель Viimane на один элемент вправо АВCD Esimene Viimane

8 Для реализации операций над очередями будем использовать следующие функции: //добавление элемента в очередь void LISA(int Viimane, int Number) //Проверка пустоты очереди void KAS_TYHI(int Esimene, int Viimane) //удаление элемента из очереди void KUSTUTA(int Esimene, int Viimane) //Для моделирования очереди будем //использовать массив Jarjekord (очередь).

9 Пусть размер очереди равен MaxKogus. Тогда функция добавления элемента в очередь будет выглядеть так: void LISA(int Viimane, int number) { //Если очередь полна -> выход if (Viimane==MaxKogus) exit(l); // иначе, добавить элемент number в очередь Jarjekord[Viimane]=number; // Сдвинуть указатель Last на один элемент //вправо Last++; }

10 //Данная функция возвращает р=1, если очередь //пуста, и р=2, если в очереди есть элементы. void KAS_TYHI(int Esimene, int Viimane) { if (Esimene==Viimane) p=l;// Очередь пуста else p=2;//Очередь не пуста }

11 void KUSTUTA (int Esimene, int Viimane) { if (Esimene==Viimane)exit(l);//Очередь пуста //Сдвинуть указатель Esimene на один элемент //вправо Start++; }

12

13 Если стек содержит только один элемент, и этот элемент удаляется, то в результате выполнения операции в данный стек больше не сможет быть занесен ни один элемент. Такой стек называется пустым. Допустим, имеется стек из элементов A, B и C. Если элемент A был первым занесен в стек, а элемент C последним, то стек будет выглядеть. A B C Top

14 Если удалить из стека элемент C, доступный для операций, переместив указатель тор на один элемент вниз, то стек будет таким Теперь добавим в стек некоторый элемент D. Для этого запишем его в вершину стека, сместив указатель тор на один элемент вверх A B Top A B D

15 Для реализации операций над стеками будем использовать следующие функции: //добавление элемента в стек void LISA(int Top, int Number) //проверка пустоты стека void KAS_TYHI(Тор) //удаление элемента из стека void Kustuta(Тор)

16 Пусть размер стека равен MaxStack. Чтобы поместить элемент в стек, необходимо указать сам элемент и индекс (адрес) вершины стека. void LISA(int Top, int Number) { if (Top==MaxStack) exit(l);//Стек заполнен //иначе, добавить элемент Number в стек Stack[Top]=Number; Top++;//Сдвигает указатель Тор на один //элемент вверх } A B Top

17 //Данная функция возвращает р=1,если стек пуст, //и р=2, если в стеке есть элементы. void KAS_TYHI(int Top) { if (Top==0) р=1; // Стек пуст else р=2;// Стек не пуст } A B Top != 0 Top = 0 p = 2 p = 1

18 Функция удаления элементов из стека: void KUSTUTA(int Top) { if (Top==0) exit(l); // Стек пуст // иначе, сдвинуть указатель Тор //на один элемент вниз Тор; } A B Top

19

20 пример списка с элементами а, в, с, d a2 > b3->c4 d0 -> связь элементов списка Указатель элемента а определяет номер следующего элемента списка Указатель элемента в показывает, что за ним следует элемент с Отсутствие или нулевое значение указателя означает, что данный элемент является последним в списке.

21 Элементы в списке могут быть связаны посредством разных указателей: списки, в которых для каждого элемента указатель задает местоположение следующего или предыдущего называются однонаправленными. списки, в которых задаются два указателя, которые определяют местоположение как предыдущего элемента, так и последующего, называются двунаправленными При работе со списками используется, как правило, еще один указатель, который определяет первый элемент списка. Для представления однонаправленного списка в памяти компьютера можно использовать двумерный массив Nimistu [2] [MaxNimistu], где MaxNimistu это количество элементов в списке. В данном двумерном массиве любой элемент Nimistu[0][i] содержит значение элемента списка, а в Nimistu[1][i] находится указатель на следующий элемент.

22 Двунаправленный список так же представляется в виде двумерного массива Nimistu[3][MaxNimistu]. в Nimistu[0][i] расположен элемент списка, а в Nimistu[1][i] и Nimistu[2][i] находятся указатели, которые указывают соответственно на предыдущий и последующий элементы списка. элементпредыдущийпоследующий элементпредыдущийпоследующий элементпредыдущийпоследующий элементпредыдущийпоследующий

23 Основными операциями над списками являются: переход к очередному элементу списка; добавление в список нового элемента; поиск заданного элемента; удаление элемента из списка. Выполнение этих операций основывается на использовании и изменении указателей.

24 Определим значение указателей для пустого списка. Пусть переменная un адрес первого элемента списка. us будет задавать адрес первого элемента списка свободных мест, Для пустого списка us=1, un=o. ХарактеристикаЗначения Индекс массива Элемент списка Указатели

25 Пример Cозданиe пустого списка при помощи функции UusNimistu. void UusNimistu() { for (i=1; i

26 Для добавления элемента х в список необходимо в переменную Pos запомнить адрес первого элемента списка свободных мест. Затем нужно поместить по этому адресу элемент х и в качестве указателя на следующий элемент списка записать номер первого элемента списка. Теперь указателем первого элемента списка будет указатель us, т. к. по его адресу записан новый элемент. Он из разряда свободных элементов переходит в разряд занятых. Указателем списка свободных мест будет Pos, т. е. элемент, который следует в списке свободных мест за только что исключенным из него элементом.

27 Пример кода функции LISA (int, int, int), которая добавляет элемент х в список. void LISA(int US, int UN, int X) { if (Sp==0) exit(1); //Список не содержит элементов Pos=List[1][US]; //Находит адрес первого элемента //списка свободных мест List[0][US]=X; //Помещает по этому адресу значение X List[1][US]=UN; //В качестве указателя на следующий //элемент помещает номер первого //элемента списка UN=US; US=Pos; }

28 добавим в таблицу элементы с и d US = 5, a UN = D ХарактеристикаЗначения Индекс массива Элемент спискаABCD Указатели

29 Рассмотрим подробно операцию добавления элемента х в список. Сначала указатель списка свободных мест us=1, а первый элемент списка un= о. Первоначальный вид списка После добавления в список элемента A, используя функцию LISA(int,int,int). US=2, UN=A. ХарактеристикаЗначения Индекс массива Элемент списка Указатели ХарактеристикаЗначения Индекс массива Элемент спискаA Указатели

30 Добавим в список элемент в, используя функцию LISA (int, int, int). US=3, UN=B Характеристика Значения Индекс массива Элемент, списка А В Указатели Аналогичным образом добавим в таблицу элементы с и d US=5, UN=D Характеристи ка Значения Индекс массива Элемент списка АВCD Указатели

31 Поиск элемента х в списке осуществляется следующим образом: –1. Переменной Lop присваиваем значение указателя первого элемента списка. –2. Далее просматриваем список до тех пор, пока не найдем нужный элемент, либо не достигнем конца списка. Если по окончанию процедуры Lop=o, значит, в списке нет элемента со значением х. void Find(int X, int UN) { Lop=UN; while (List[0][Lop]!=X && Lop!=0) Lop=List[1][Lop];//Присваивает переменной //Lop ссылку на следующий //элемент }

32 Чтобы удалить элемент х из списка, необходимо сначала найти его в списке, например, при помощи функции Find(int, int, int). Если элемент в списке найден, то происходит его удаление. При удалении изменяется указатель записи элемента, идущего в списке перед элементом х таким образом, чтобы он указывал на элемент, идущий в списке после элемента х. Пусть Pos индекс элемента массива, который необходимо удалить, а к индекс элемента массива, который следует за элементом List[1][Pos]. Функция Delete (int, int, int) удаляет элемент x из списка. void Delete(int К, int Pos, int US) { List[1][K]=List[1][Pos]; List[1][Pos]=US; US=Pos; }

33 Проследим удаление элемента x на примере списка Удалим элемент «с» из списка при помощи функции Delete (int,int,int). После проделанных операций указатель списка свободных мест us=з (т.к. Удалялся третий элемент), а первым элементом списка un=о. ХарактеристикаЗначения Индекс массива Элемент спискаАВCD Указатели ХарактеристикаЗначения Индекс массива Элемент спискаАВD Указатели

34 Необходимо сначала найти заданный элемент х, а затем вставить после него новый элемент е. При добавлении нового элемента в список после элемента х по адресу первого элемента списка свободных мест записывается значение нового элемента. Указатель нового элемента принимает значение, равное адресу следующего за ним элемента Эти операции реализует функция void Insert_after(int Pos, int US, int E) { List[0][US]=E; List[l][US]=List[l][Pos]; Listfl][Pos]=US; } Здесь Pos это индекс элемента x.

35 ХарактеристикаЗначения Индекс массива Элемент спискаАВЕD Указатели После добавления элемента е после элемента в в предыдущей таблице получим список

36 Сортировка списков При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка, и для ее решения существуют различные методы. Если в задаче требуется отсортировать все элементы списка, то он сортируется как обычный массив любым методом. ХарактеристикаЗначения Индекс массива12345 Элемент списка31639 Указатели23450 ХарактеристикаЗначения Индекс массива12345 Элемент списка13369 Указатели23450

37 В некоторых задачах возникает необходимость сортировки списка таким образом, чтобы по указателям можно было восстановить исходный список. При сортировке необходимо менять местами не только элементы списка, но и их указатели. void Swap(int х, int у) { int Temp; Temp=List[0][x]; List[0][x]=LiSt[0][y]; List[0][y]=Temp; Temp=List[l][x]; Listjl][x]=List[l][y]; List[l][y]=Temp; } ХарактеристикаЗначения Индекс массива Элемент списка Указатели ХарактеристикаЗначения Индекс массива Элемент списка Указатели 32540

38 Упорядоченные списки List_1 и List_2 длиной m и n сливаются в один упорядоченный список List_res длины m + n, если каждый элемент из List_l и List_2 входит в List_res ровно один раз. Индекс массива Элемент списка Указатели Индекс массива Элемент списка Указатели Индекс массива Элемент списка Указатели Алгоритм слияния двух списков прост. Его основная идея выглядит следующим образом. Для слияния списков List_1 и List_2 список List_res сначала полагается пустым, а затем к нему последовательно приписывается первый узел из List_1 или List_2, оказавшийся меньшим и отсутствующий в List_res.

39 Пример использования рассмотренных структур данных

40 Пример 1.Дана матрица размером М х N, заполненная 0 и 1. Рассмотрим программу, которая определяет количество нулевых островов в матрице. Островом назовем совокупность смежных клеток матрицы, содержащих нули. #include

41 void Find()// Объявление функции { р=0; // Пусть есть нулевые элементы в //матрице for (i=1; i

42 main() { Start=0; Last=0; Label=0; P=1; do { Find();// Вызывает функцию, которая проверяет, есть ли // нулевой элемент в матрице if (р==1) Test(); // Если такой элемент найден, то вызывает функцию, которая // проверяет смежные клетки с данным элементом и заносит их // координаты в очередь, если в них значение равно нулю } while (р==1); cout

43 void Test() // Объявление функции { Label++; // Увеличивает метку, т. е. говорит о начале // поиска нового острова while (Start!=Last) // Пока очередь не пуста... { a=Queue[0] [Start] ;// Запоминает координату X текущей клетки b=Queue[l] [Start]; // Запоминает координату Y текущей клетки // Проверяет все клетки, смежные с текущей if (array[а+1][b]==0) Add(a+1,b); if (array[a-1][b]==0) Add(a-l,b); if (array [a][b+1]==0) Add(a,b+1); if (array[a][b-1]==0) Add(a,b-1); Start++;// Удаляет первый элемент из очереди // Объявление функции // Начальная позиция указателя Start // Начальная позиция указателя Last }