Лабораторна работа #4 Работа с линеен едносвързан списък, Платформа за съдържание
Лаборатория #4
Както вече беше отбелязано, опашката и стекът са специални случаи на общата концепция за "линеен списък".
Линеен едносвързан списък може да бъде два вида:
1) директен линеен едносвързан списък;
2) обратен линеен едносвързан списък.
Опашкатае специален случай на директен линеен единично свързан списък. В обратния списък връзката се установява от i-тия елемент към (i-l)-ия елемент.
Стекае специален случай на обратен линеен единично свързан списък. Лесно се вижда, че разделянето на списъци напред и назад е условно и зависи от това коя страна на списъка се счита за начало и коя страна е край.
За да работите с линеен едносвързан списък, са необходими следните указатели:
1) указател към началото на списъка (вземете идентификатора BegL);
2) указател към края на списъка (вземаме идентификатора EndL);
3) указател към k-тия елемент от списъка, където ще се извършват действията: след кой (или пред кой) елементът ще бъде вмъкнат или кой трябва да бъде изтрит (взимаме идентификатор Рk);
4) временен указател за разпределяне на памет за добавени елементи и за освобождаване на памет за изтрити елементи (взимаме идентификатора P).
Разгледайте основните операции върху линейни едносвързани списъци.
1. Създайтелинейниединично свързанисписъци
Създаването (т.е. вмъкването на първия елемент) на линеен единично свързан списък се извършва точно по същия начин като създаването на опашка. Освен това, това се отнася както за директния, w, така и за обратния линеен единично свързан списък, въпреки факта, че обратният линеен единично свързан списък е обобщен случай на стек, иняма опашка. Това се случва точно защото обратният линеен единично свързан списък еобобщенвид стек, който има начало и край, като опашка, а не само връх, като стек.
Добавянето на елемент в края на списък напред е подобно на добавяне на елемент в края на опашка, а добавянето на елемент в края на обратен списък е подобно на добавяне на елемент в горната част на стека.
Схемата за добавяне на прав линеен единично свързан списък би била следната:
Добавянето на елемент в началото на предния списък е същото като добавянето на елемент в горната част на стека, а добавянето на елемент в началото на обратния списък е същото като добавянето на елемент в края на опашката.
Схемата за добавяне на елемент за директен линеен единично свързан списък ще бъде както следва:
4. Размяна на стойностите на информационните полета на k-тия и нови елементи и пренареждане на указателя Pk към новия елемент.
Променливата Tmp трябва да има същия тип,като информационното поле на елемента от списъка Inf.
Премахването на елемент от началото на преден списък е подобно на премахването на елемент от опашка и от стек (имайте предвид, че премахването на елемент от опашка и стек е по същество едно и също).
Премахването на елемент от началото на обърнат списък (или от края на препратен списък) няма аналог в операциите на опашка и стек (това ще бъде обсъдено в следващото подзаглавие).
Схемата за премахване на елемент от началото на преден списък би била следната:
3. Пермутация на указателя на началото на списъка BegL към следващия елемент, използвайкистойността на полето Link, която се съхранява в първия елемент. След това паметта на началния елемент на списъка се освобождава с помощта на допълнителен указател P:
Премахването на елемент от края на списък напред е уникално за действията на опашка и стек, а премахването на елемент от края на обратен списък е подобно на изваждане от опашката или подреждане, както е показано по-горе.
Схемата за премахване на елемент от края на преден списък би била следната:
Съответната схема изглежда така:
Следователно, за да се извърши необходимото действие, е необходимо да се преброят k елемента от началото на списъка, като последователно се премества спомагателният указател от елемент към елемент.
В резултат на това получаваме:
Така че в най-простия случай цикълът за задаване на указател към даден k-ти елемент ще изглежда така:
Този цикъл обаче не взема предвид случая, ако в списъка има по-малко елементи от даденото k. Тоест, може да се използва тогава и само ако е гарантирано, че списъкът има поне k елемента. Ако вземем общия случай, тогава е необходимо допълнително да проверим дали сме стигнали до края на списъка в рамките на цикъла.
11. Задайтеуказателкъмпредпоследенелементна директен едносвързансписък
Спомнете си, че извършването на такова действие е необходимо за премахване на последния елемент от директен едносвързан списък.
Въпреки че предпоследният елемент на директен единично свързан списък се намира близо до опашката на списъка, обаче, за да зададете указател към него, трябва да отидете не от края, а от началото на списъка, тъй катовръзките между елементите са насочени в една посока.
Придвижването през списъка се извършва по същия начин, както е описано по-горе. Единствената разлика е в условието за прекратяване на търсенето. Има два варианта за това състояние.
Можете да сравните или с указателя EndL, или с нула, което също маркира края на списъка.
Въпреки че използването на указателя P^.Link^.Link е малко по-трудно за разбиране, то е и по-универсално, тъй като работи дори и да нямаме EndL указател.
12. Отпечатайтеелементиединично свързанисписъкотначалодокрай
Тази опция за отпечатване на елементи от списък се изпълнява подобно на настройката на показалеца към предпоследния елемент, описан по-горе, с две разлики:
1) движението на работния показалец се извършва до последния елемент;
13. Отпечатайтеелементиединично свързанисписъкоткрайдоначало
Очевидно е, че отпечатването на елементите на списъка от края към началото не може да се извърши толкова просто, колкото в предишния случай, тъй като връзките са насочени само в една посока и е невъзможно да се движите по тях в обратна посока. В този случай трябва да използвате или друг допълнителен списък (но с обратна връзка!), за да съхраните временно елементите на оригиналния списък, или да използвате рекурсия.
Помислете за решение, използващо рекурсия. Тъй като използваме рекурсия, действията трябва да са под формата на процедура.
1. От който текстът се чете на свой ред всички думи и се изчислява честотата на тяхното появяване, т.е. съставя се честотен речник. За да направите това, трябва да направите списък с думи,намерени в текста. Всяка следваща дума се търси в списъка. Ако бъде намерена дума, нейният честотен брояч се увеличава, в противен случай думата се добавя към списъка. За простота ще приемем, че думите са извлечени от текста, кодирани като положителни цели числа и са във входния файл.
3. Даден е линеен еднопосочен списък, в информационните полета на който има цели числа. Премахнете от този списък всички елементи, които имат равномерни стойности на такива полета, като ги съберете в отделен линеен еднонасочен списък.