Функция Empty: Булева;

Ако I = 0 тогава Empty: = True Else Empty: = False;

Когато операцията на купчина проба първо трябва да се извършва на купчината от вакуум. Ако е празно, а празното връща True. Ако Празните връща към False, което означава, че на комина не е празна и навън все още можете да изберете елементи.

Процедура StackTop (VAR I: Integer; S: Stack);

2.4.2 Queue

Идеята на опашка всички знаем от всекидневния живот. Елементите на опашката обикновено са поръчки за определена услуга.

В програмирането, има структура от данни, която се нарича опашка. Тази структура на данни се използва, например, за моделиране на реални опашки за определяне на техните характеристики за даден закон Входящите поръчки и да дисциплинираме тяхното поддържане. По същество, тя е полу-статична структура на всички - с течение на времето и дължината на опашката, и съставът може да варира.

На свой ред ris.privedena съдържащ четири елемента - А, В, С и D. елемент е разположен в началото на опашката, и елемент D - в края. Само елементи на опашката могат да бъдат отстранени, което е, на първо място се поставя в първия елемент се отстранява. Поради тази причина, всички често се нарича списък, организирани в съответствие с принципа "първо беше домакин на първия отстранен", за разлика от принципа на организацията на стека - ". Последното място, първият е отстранен"

Дисциплина на обслужване, в който получени поръчки, на първо място, първият избран за услугата (и отстранен от опашката), наречена FIFO (First In First Out - първият, първа изходяща). Опашката е отворен от двете страни.

Така, отстраняването на компонент, получен от опашката, и записа - в края. В този случай, се въвеждат и два указатели - едната отпред на опашката, а вторият - на неговия край.

Действителното място се създава в паметта на компютъра под формата на едномерна масив с краен брой елементи, в този случай трябва да определите типа на договорени покупки, и имате нужда от променлива в работната опашката.

Физически своя страна заема непрекъсната площ от елементи на паметта и да следват един друг, както в последователен списък.

Операции, извършвани на опашката:

три примитивни операции са определени за опашката. Операция вложка (Q, X) поставя елемент х в опашката Q. Операция премахване (р) премахва елемент от опашката Q и присвоява на променливата х. Третата операция, празен (р), връща стойността вярно или невярно зависимост от това дали на опашката е празна или не. В допълнение. Предвид факта, че полу-статичен всички осъществява на едномерен масив, трябва да следвате възможността за преливане. С тази цел opnratsiya пълен (Q).

вложка Операция винаги може да бъде изпълнена, защото броят на елементите, които могат да съдържат част, се налагат никакви ограничения. Операцията за премахване обаче е приложима само за не-празна опашка, тъй като не е възможно да премахнете елемент от опашката не съдържа елементи. В резултат на опит за премахване на елемент от празен опашка е появата на извънредна ситуация, която незареден. Операция празен, разбира се, винаги е възможно.

Един пример за прилагането на опашката във формата на едномерен масив в Паскал:

Опашката = Array [1..MaxQ] на Е;

Извадете елементи А и Б от опашката.

За съжаление, с такова представяне на опашката може да изпита абсурдна ситуация, когато опашката е празна, но новата клетка не може да побере в него (помисли за последователността на операциите за премахване и поставяне, в резултат на такава ситуация). Ясно е, че изпълнението на нея чрез масив е неприемливо.

Едно решение на проблема може да се отстрани операция модификация, така че отстраняване на следващия елемент цялата линия е изместен в началото на масива. Операция премахване (р) може да се реализира по следния начин.

Променливата F, вече не е необходимо, тъй като на първия елемент на масива е винаги в началото на опашката. Празна опашка, представено с опашката за които R стойност е равна на нула.

Въпреки това, този метод е много непродуктивен. Всеки уд-Lenie изисква преместване на всички останали елементи в опашката. Ако опашката съдържа 500 или 1000 къса, очевидно е, че това е много неефективно. Освен това, отстраняване на елемент от логическа операция на опашката включва манипулиране на само един елемент, т.е.. Е. същото време, който се намира в началото на опашката. Изпълнението на тази операция трябва да отразява този факт, без да произвежда голямо разнообразие от допълнителни дейности.

Друг метод включва помисли масив, който съдържа опашка във формата на затворен пръстен, а не линейна последователност с начало и край. Това означава, че първият елемент на опашката веднага следва последен. Това означава, че дори ако последният елемент не е на разположение, нова стойност може да се постави точно зад него на мястото на първия елемент, когато първият елемент е празен.

Организация на линията на пръстен.

Помислете за пример. Да приемем, че опашката съдържа три елемента - в позиции 3, 4 и 5, пет елемент масив. Този случай е показан на фиг. 2.17. Въпреки, че масивът е празен и последния ред не е налична.

Сега, ако се прави опит да се въведе елемент на G, а след това тя ще бъде записана в първата позиция на масива, както е показано на фиг. 2.17. Първият елемент на опашката е Q (3), последвано от елементите на Q (4) Q (5) и Q (L).

За съжаление, това е трудно да се определи, когато опашката е празна, когато с това представяне. В състояние R

Един от начините за решаване на този проблем е въвеждането на споразумение, по силата на което индексът на стойност Fest масив, непосредствено предхождащ първия елемент на опашката. не на индекса на първия елемент. В този случай, тъй като R съдържа последния етап на индекса, състоянието F = R означава, че опашката е празна.

Имайте предвид, че преди работа опашка, F и R в комплекта на последния индекс масив стойност вместо 0 и 1, тъй като в този представителство на последната опашка елемент масив от бърз, но предхожда първия елемент. Тъй като R = F, след това опашката първоначално е празен.

Принцип на работа на кръглата опашката:

1. въвеждане елемент р х на място.

2. Отстраняване на елемент на х завои.

3. Проверете за празна опашка.

19. Що се организират пръстен от всички?

20. Какви са характеристиките близнак на палубата?

Досега са се разглеждат само статичните софтуерни обекти. Въпреки това, използването на програмни само статични обекти могат да причинят проблеми, специално по отношение на получаване на ефективна компютърна програма. Факт е, че понякога ние не знаем предварително не само от размера на стойността на дадена програма обект, но и за това дали обектът съществува или не. Този вид софтуерни обекти, които се случват още по време на изпълнение на програмата или на стойностите на размерите на която се определя по време на изпълнението на програмата, известна като динамични обекти.

Динамични структури от данни имат две функции:

1) Предварително неопределен брой елементи в структурата.

2) Елементи на динамични структури имат твърд линеен поръчка. Те могат да бъдат разпръснати от паметта.

За да се свържат елементи между динамични структури на елементите в допълнение към областта за информация включва поле указатели (фиг. 3.1) (сухожилие структура с други елементи).

3.1 Свързани списъци

Най-често срещаните динамични структури са свързани списъци. От гледна точка на логическо представяне отличава линейни и нелинейни списъци.

За линейни списъци са просто свързани и двойно-свързани списъци. За нелинейна - размножават.

елемент от списъка, като цяло, е запис поле и един или повече указатели.

3.1.1 поединично-свързани списъци

списък свързан елемент съдържа две области (фигура 3.2.): поле информационна област (информация), и указател (PTR).

Достъпът до елемент в списъка е само от самото начало, което означава, че обратната връзка не е в списъка.

3.1.2 Ring поединично свързан списък

Пръстен списък единично свързан е получен от конвенционален свързан списък от последната списъка елемент указател задача започне списък указател (фигура 3.3).

Основни операции, извършвани в списъка на свързани

1) Поставете в началото на списъка със свързани.

Се добавя в началото на свързан списък елемент информация поле D. За това е необходимо да се генерира празен елемент (Р = GetNode). Информация поле на клетката за определяне на стойността D (INFO (P) = D) на стойност указател за този елемент за присвояване указател към началото на списъка (PTR (P) = Lst), стойността на списъка началната указател към определя стойността на стрелката Р (Lst = P).

Изпълнение на Паскал:

Поставете горната част на

2) Премахване на началния елемент свързан списък.

Необходимо е да се премахне първия елемент в списъка, но не забравяйте, информацията, съдържаща се в областта на тази позиция Info. За да направите това ще се въведе показалка P, което би означавало, сменяем елемент (P = Lst). Включено в променливи X стойността на информация поле елемент, за да се отстранят Info (X = Info (P)). Стойност указател в началото на списъка определя стойността на показалеца след сменяемия елемент (Lst = PTR (P)). Премахване на елементи (FreeNode (P)).

Изпълнение на Паскал:

Премахване от началото

3.1.3 Dual-списък

Използването на еднопосочни списъци може да доведе до някои трудности при решаването на редица проблеми. Факт е, че можете да преместите еднопосочно списъка само в една посока, от връзката със заглавието на последната брънка в списъка. В същото време често е необходимо да правите никакви процесорни елементи, предхождащи елемент на предварително определен имот. Въпреки това, след намирането на елемента с този имот на свързан списък, не можем да се наситят на удобен и бърз достъп до предишния елемент - за постигането на тази цел трябва да се усложни алгоритъма, което е неудобно и непрактично.

Двойно свързан списък се характеризира с това, че всеки елемент има две насоки. Един показва предходния елемент (назад), другите точки на следващия елемент (права линия) (фиг. 3.4).

В действителност, двойно свързан списък е свързан списък с два еднакви елементи, записани в обратна последователност.

3.1.4 Ring двойно свързан списък

Операции на двойни свързани списъци:

- списък cozdanie т;

- Търси за даден елемент в списъка;

- вмъкване на елемент на определена позиция в списъка;

- премахвате по предварително определен участник.

3.2 Изпълнението на комина с помощта на свързан списък

Така или поединично свързан списък може да се мисли като комин. Въпреки това, в списъка в сравнение с купа в едномерен масив е предимство, тъй като не е определен предварително резолюция.

Стека операции, приложими за списъци

1). За да добавите елемент към стека, е необходимо да се замени алгоритъм Lst стека указател към показалеца (Операция Push (S, X)).

2) Проверка на стека за невалидни (празно (S))

Ако Stack = Nil след това Печат "Stack е празен"

3) елемент проба от стека (POP (S))

3.3 Организация Getnode операции, Freenode и рециклиране на освободените елементи

За по-добро използване на паметта на компютъра ви (за да се избегне отпадъци. Т.е. неизползваните позиции) със своите списъци, за да създадете безплатен списък, който има същия формат поле като това на списъка на функциите.

Ако функцията изброява различен формат, вие трябва да създадете безплатен списък на всеки списък функция.

Броят на стоките за свободното списъка трябва да бъдат дефинирани решаване на задача от програмата. Обикновено, безплатно списък се създава в паметта на компютъра като комин. По този начин създаване (GetNode) нов елемент еквивалентна проба от свободната стека елемент и експлоатация FreeNode - добавяне на свободен стека освободена елемент.

Да предположим, че трябва да се създаде празен списък от типа на стека (Фигура 3.6). При указател към началото на списъка - напразно. Да се ​​разработят процедури, които ще ни позволят да създадете празен елемент от списъка и да освободи обекта от списъка.

3.3.1 Работа GetNode

Да се ​​разработят процедури, които ще създадат празен елемент от списъка с показалеца П.

За изпълнение на необходимите операции GetNode генерирани показалка елемент присвояване на стойност на безплатно списък показалеца и показалеца старт за да преминете към следващата точка.

Преди това, е необходимо да се провери дали елементите в списъка. Отпада безплатно списък (Наличност = Nil), еквивалентни функционални списък преливане.

Ако Наличност = Nil след това Печат "преливане" Стоп

3.3.2 Работа FreeNode

При Нод освобождаване елемент (P) на функционална списък операция FreeNode (P), тя се съхранява в списъка със свободни.

3.3.3 Изхвърляне на освободените елементи в умножаване на списъци

Стандартни операции връщат списъка освободената елемент в басейна на свободните позиции не винаги произведе ефекта, ако използвате нелинейни списъци с умножение.

Първият метод на рециклиране - Метод броячи. Във всеки елемент от списъка на многомерна поле поставен брояч, който отброява броя на връзки към елемента. Когато брояч елемент е в нулево състояние, а елементът поле нула указатели са налице, елементът може да се върне в басейна на наличните елементи.

Вторият метод - GC метод (метод маркер). Ако някой елемент е свързан, елемент на полето един-битов (маркер) е настроен на "1", в противен случай - на "0". Чрез преливни сигнални компоненти се търсят, за които означението е нула, т.е.. Д. Включени програмата за събиране на боклука, който сканира цялата памет и назначен да се върнете към списъка със свободни от елементи, всички от елементите, които не са маркирани маркер.

3.4 поотделно свързан списък, като независима структура на данните

Трябва да бъде включен в съществуващ масив елемент X от между 5 и 6 елемента.

За да се извърши тази операция в масива трябва да "изтрие" всички елементи, като се започне с X6 - увеличаване на индексите им по един. Като резултат, ние се след вкарването на масива (фигура 3.7, 3.8.):

Тази процедура може да отнеме много значително време. За разлика от това, в свързано операция списък вмъкване се състои в промяна на стойността на 2 показалци и генериране на свободен елемент. И времето, прекарано на тази операция е постоянна и не зависи от броя на елементите в списъка.

3.4.1 Поставяне и изваждане на предмети от списъка

Ние определяме елемента, след което искате да вмъкнете елемент в списък. Вмъкването е направена като се използват процедури InsAfter (Q, X) и отстраняване - DelAfter (Q, X).

В тази работа на стрелката Р да сочи към елемент, след което необходимостта от добавяне или заличаване (Фигура 29).

Да предположим, че искате да вмъкнете нов елемент с информация поле X след елемента, посочен от показалеца П. работник

1) Необходимо е да се създаде нов елемент.

2) информационното поле на този елемент за присвояване X. стойност

3) Поставете получената елемент.

Това е процедура InsAfter (Q, X).

Да предположим, че трябва да изтриете списък елемент, който следва след елемента, посочен от показалеца П. работник

1) Задаване на Q стойност на показалеца върху елемента да бъдат изтрити.

2) вариабилен X съхранява стойността на полето за информация на отстранения елемент.

3) промяна на стойността на показалеца върху сменяемия елемент на показалеца на следващия елемент и производство на заличаване.

Това е процедура DelAfter (Р, X).

Pascal горе процедура ще бъде както следва:

процедура InsAfter (Var Q: PNode; X: цяло число);

процедура DelAfter (Var Q: PNode; Var X: цяло число);

3.4.2 Примери за типични операции на списъци

Означаваме P - работа показалка в началото на процедурата, P = Lst. Ние също така въвеждане на показалеца Q, зад която един елемент от P. Когато стрелката Р ще елемент, последният се отстранява относително Q указател като следващ елемент.

Докато P <> нула правя

Ако Информация (P) = 4 тогава

Дан подредени възходящо Info - списък на полета. Трябва да бъде поставена в списъка със стойността на елемент X, без да нарушава подредбата на списъка.

Нека X = 16. Първоначалното състояние: Q = Nil, P = Lst. Въвеждане елемент трябва да възникне между 3 и 4, елемент (ris.3.10).

Докато (P <> Nil) и (X> Информация (P)) правя

3.4.3 Функция елементи в списъците

За създаване на списък с глава допълнителен елемент се въвежда в горната част на списъка, който може да съдържа информация за списъка (фиг. 3.11).

заглавието на списък често се поставя динамична променлива, която съдържа редица елементи в списъка (с изключение на много заглавието).

Ако списъкът е празен, има само един списък с глава (фиг. 3.12).

Също така е удобно да се сложи в областта на информацията в заглавието списък край показалеца на. След това, ако в списъка се използва като опашка, Fr = Lst и Re = Info (Lst).

Поради големия обем на материала се поставя на няколко страници:
1 2 3 4 5 6 7 8

Свързани статии

• Допълнителни данни за обработка на печат в priprinter