Сега нека да погледнем на етапа на изпълнение на въз основа на масиви. Както и преди, за простота ще използваме масив от TList. Поне в този случай ние не трябва да се притеснявате за заделяне на памет и увеличаване на размера на масива.
Знаейки как да се приложи всичко въз основа на списъка свързани, първо желание може да бъде да се симулира дейността Поставяне в опашката, се добавят точки към крайния инстанция TList масив, използвайки метода Добавете и да се симулира отстраняването от линията - за отстраняване на първия елемент от метод Изтриване метод ( или обратно, поставена в началото на масива, и се отстранява от края). Независимо от това, нека да видим какво ще се случи по едно и също време с масив. Когато методът за добавяне не се случи нищо интересно, освен когато това е необходимо да се увеличи размера на масива. Тази операция клас O (л) - точно това, което се изисква. Що се отнася до изтриване, тук не всичко е толкова розова. За изпълнението на операцията за отстраняване на линията от масива TList трябва да премахнете първия елемент, което ще доведе до факта, че всички елементи на масива ще се движат напред с една позиция. Такава операция зависи от броя на елементите в масива, т.е. Той принадлежи към клас 0 (н). Така че ние чакахме лоши новини. Ние не можем да променим отчета за дейността на места в опашката и де-опашка, т.е. Ние добавяме само в горната част на списъка и я извадете от края. С други думи, ние все още се получи работа клас 0 (н), когато се добавя към горната част на списъка.
Някои източници, описани на принципа все още се използва за изпълнение на опашката. Освен това, TQUEUE клас Contnrs модул, евентуално въз основа на този принцип.
Фигура 3.10. Използването на множество опашки
Как да се прилагат набор от всички на основата, че двете основни операции принадлежат към класа 0 (1)?
Разтворът е да се използва кръгла опашка. Представете си прием при зъболекаря. Като правило, това е една стая със столове покрай стените. За разлика от линията в супермаркета, откъде идваш до върха на опашката, бута количка, на рецепцията, който седеше на един стол. Когато се обадите на следващия пациент всички останали не се изправи и не се движат към следващото стола. Точно пред опашката - някои трудно обяснимо атрибут (да, с впечатлението, че в Америка не е на опашката на зъболекар.) - се прехвърля на друго лице. Когато се обадите на този атрибут на пациента се прехвърля към следващия пациент, и тя се превръща в "началото" на опашката. По този начин, никой не става от стола си, просто по някакъв начин (може би с помощта на стоматологична асистент), първият пациент в опашката се определя. Този вид организация се нарича кръгова опашка.
За изпълнение на кръгла Робин въз основа на масиви, ще се въведе една променлива, която ще съдържа индекса на първия елемент в опашката. В допълнение, ние се въведе друга променлива, която ще се насочи към края на опашката. Ще започнем с някои от масива с определен брой елементи (размер се основава на максималния възможен брой на елементите в опашката) и да се установи началната индекс елемент, равен на индекса на крайния елемент. В действителност, това уравнение означава, че опашката е празна.
Атакуването елемент елемент настройка еквивалентна стойност, което показва в края на индекса на опашка, равна на стойността, записана в опашката елемент. След това, в края на стойността на индекса на опашката трябва да се увеличи с 1. Ако увеличението на индекса ще надхвърли размера на масив, трябва да го настройте на 0 индексът на първата клетъчна единица.
Премахване на елемент от опашката означава връщане стойност на елемента, посочен от индекса на опашката. След това стойността на увеличението на стартовата линия на индекса от 1. Ако ще надхвърли размера на масива, след като увеличението на индекса, то бъде 0. Очевидно е, че преди да отстраните елемент от опашката, трябва да се гарантира, че на опашката не е празна. За да направите това, проверете дали индексите началото и края на опашката, равна на (в случая на капиталов индекс, опашката е празна).
И това остава да се разгледа друг проблем: при определянето на елементите на опашката, уверете се, че новата стойност на края на индекса на опашката не е равна на стойността на индекса на опашка. Ако се наблюдава равенство, това означава, че всички елементи, изцяло запълнени. За съжаление, тази ситуация означава също (поне за експулсиране с опашка), че опашката е празна. По този начин, ако такава е достатъчно абсурдна ситуация възниква - празна опашка попълнено еквивалент - е необходимо да се увеличи размера на масива, чрез преместване на всички елементи в масива и промяна на стойностите на индексите началото и края на опашката.
Клас TtdArrayQueue интерфейс изглежда точно същата като класа интерфейс TtdQueue.
Обявата 3.31. клас TtdArrayQueue
Конструкторът и деструктор не са много по-различни от съответната методи TtdArrayStack клас.
Обявата 3.32. TtdArrayQueue на конструктор и деструктор
Най-интересното нещо се случва в методи Enqueue и Dequeue.
Обявата 3.33. Enqueue и Dequeue методи клас TtdArrayQueue
Както можете да видите, елемент от елемент отстраняване опашка включва връщане, който е в позиция на индекса на опашката, а след това се увеличи в индекса от 1. Queuing включва записване елемент в позиция на индекса в края на опашката и увеличението на индекса от 1. Ако опашката достигне края на своя старт размерът на съоръженията се увеличава с помощта на метод aqGrow:
Обявата 3.34. Разширяване на размера на модел TtdArrayQueue
Горният метод е най-сложната метод в целия клас. Когато той се нарича опашката е пълна, в края на индекса на опашката е равна на индекса на началото (не забравяйте, че това също така означава, че опашката е празна), необходимостта да се увеличи размера на масива TList. Първото нещо, което правим - увеличаване на размера на масива с 50%. След това, всичко, което трябва да се определи на ринга, така че тя правилно отчита наличното пространство. Ако стойността на индекса на опашката е 0, линията на пръстен не е кръгла, и всичко, което трябва да се направи - промените стойността на края на индекса на опашка. Ако стойността на индекса не е равно на 0 старт, опашката е "глава" вътре в масива. , Се до началото на масива и да отидете в края на индекса на опашка (която е равна на индекса на опашката), за да преминете през елементите в правилния ред, започваме с индекса на опашката, стигаме до края на стария масив. Сега имаме допълнителни елементи, които се намират между старата и новата края на масива. Ето защо, ние трябва да поставите елементите намерени между стартовата линия и стария края на масива, така че те се състоя преди новата края на масива. След това ние се правилния ред на елементите в кръгла опашка.
Пълен клас TtdArrayQueue код може да бъде намерена на уеб-сайта на издателството, в материалния секция. След разтоварване на материалите търсят сред тях TDStkQue.pas файл.
Основните алгоритми и структури от данни в Делфи
Свързани статии