Кружно повезана листа: Предности на примеру програма Ц

Преглед садржаја:

Anonim

Шта је кружно повезана листа?

Кружно повезана листа је низ чворова распоређених на такав начин да се сваки чвор може увући у себе. Овде је „чвор“ аутореференцијални елемент са показивачима на један или два чвора у непосредној близини ИИ.

Испод је приказ кружно повезане листе са 3 чвора.

Овде можете видети да је сваки чвор могуће повући за себе. Горњи пример је кружна појединачно повезана листа.

Напомена: Најједноставнија кружно повезана листа је чвор који прати само себе како је приказано

У овом водичу са кружном повезаном листом научићете:

  • Шта је кружно повезана листа?
  • Основне операције
  • Операција уметања
  • Операција брисања
  • Преокрет кружно повезане листе
  • Предности кружно повезане листе
  • Појединачно повезана листа као кружно повезана листа
  • Примене кружно повезане листе

Основне операције

Основне операције на кружно повезаној листи су:

  1. Уметање
  2. Брисање и
  3. Преокрет
  • Уметање је поступак постављања чвора на одређено место у кружно повезаној листи.
  • Брисање је поступак уклањања постојећег чвора са повезане листе. Чвор се може препознати по појави његове вредности или по положају.
  • Прелазак кружне повезане листе је поступак приказивања целокупног садржаја повезане листе и враћање назад до изворног чвора.

У следећем одељку разумећете уметање чвора и врсте уметања које су могуће у кружној појединачно повезаној листи.

Операција уметања

У почетку морате створити један чвор који показује сам на себе како је приказано на овој слици. Без овог чвора, уметање ствара први чвор.

Даље, постоје две могућности:

  • Уметање на тренутни положај кружно повезане листе. То одговара уметању на почетак краја редовне сингуларно повезане листе. У кружно повезаној листи почетак и крај су исти.
  • Уметање након индексираног чвора. Чвор треба идентификовати бројем индекса који одговара вредности његовог елемента.

За уметање на почетак / крај кружно повезане листе, то јест на место где је додат први чвор,

  • Морате прекинути постојећу само-везу са постојећим чвором
  • Следећи показивач новог чвора повезиваће се са постојећим чвором.
  • Следећи показивач последњег чвора указаће на уметнути чвор.

НАПОМЕНА: Показивач који је главни токен или почетак / крај круга може се променити. И даље ће се вратити на исти чвор током преласка, о чему смо разговарали унапред.

Кораци у (а) и-иии су приказани у наставку:

(Постојећи чвор)

КОРАК 1) Прекините постојећу везу

КОРАК 2) Креирајте везу за прослеђивање (од новог чвора до постојећег чвора)

КОРАК 3) Направите везу петље до првог чвора

Даље, покушаћете да убаците чвор.

На пример, уметнимо „ВАЛУЕ2“ после чвора са „ВАЛУЕ0“. Претпоставимо да је почетна тачка чвор са „ВАЛУЕ0“.

  • Морат ћете прекинути линију између првог и другог чвора и поставити чвор са „ВАЛУЕ2“ између.
  • Следећи показивач првог чвора мора се повезати са овим чвором, а следећи показивач овог чвора мора се повезати са ранијим другим чвором.
  • Остатак аранжмана остаје непромењен. Сви чворови су повратни према себи.

НАПОМЕНА: Будући да постоји циклични распоред, уметање чвора укључује исти поступак за било који чвор. Показивач који довршава циклус довршава циклус као и било који други чвор.

Ово је приказано испод:

(Рецимо да постоје само два чвора. Ово је тривијалан случај)

КОРАК 1) Уклоните унутрашњу везу између повезаних чворова

КОРАК 2) Повежите леви бочни чвор са новим чвором

КОРАК 3) Повежите нови чвор са чвором са десне стране.

Операција брисања

Претпоставимо да је кружно повезана листа са 3 чвора. Случајеви за брисање дати су у наставку:

  • Брисање тренутног елемента
  • Брисање након елемента.

Брисање на почетку / крају:

  1. Прелазак на први чвор са последњег чвора.
  2. Да бисте га избрисали са краја, требало би да постоји само један корак преласка, од последњег до првог чвора.
  3. Избришите везу између последњег и следећег чвора.
  4. Повежите последњи чвор са следећим елементом првог чвора.
  5. Ослободите први чвор.

(Постојеће подешавање)

КОРАК 1 ) Уклоните кружну везу

КОРАЦИ 2) Уклоните везу између првог и следећег, повежите последњи чвор са чвором који прати први

КОРАК 3) Ослободите / ослободите први чвор

Брисање након чвора:

  1. Прелазак до следећег чвора је чвор који треба избрисати.
  2. Пређите на следећи чвор, постављајући показивач на претходни чвор.
  3. Повежите претходни чвор са чвором након садашњег чвора, користећи следећи показивач.
  4. Ослободите тренутни (делинкед) чвор.

КОРАК 1) Рецимо да морамо да избришемо чвор са „ВАЛУЕ1“.

КОРАК 2) Уклоните везу између претходног и тренутног чвора. Повежите његов претходни чвор са следећим чвором на који упућује тренутни чвор (са ВАЛУЕ1).

КОРАК 3) Ослободите или ослободите тренутни чвор.

Преокрет кружно повезане листе

Да бисте прешли кружно повезану листу, почевши од последњег показивача, проверите да ли је последњи показивач НУЛЛ. Ако је овај услов нетачан, проверите да ли постоји само један елемент. У супротном, пређите помоћу привременог показивача док се поново не постигне последњи показивач или онолико пута колико је потребно, као што је приказано у ГИФ-у испод.

Предности кружно повезане листе

Неке од предности кружно повезаних спискова су:

  1. Нема захтева за НУЛЛ додељивање у коду. Кружна листа никада не упућује на НУЛЛ показивач ако није у потпуности ослобођена.
  2. Кружно повезане листе су корисне за завршне операције јер се почетак и крај поклапају. Алгоритми као што је заказивање Роунд Робин-а могу уредно елиминисати процесе који су кружно постављени у редове без наилажења на висеће или НУЛЛ-референцијалне показиваче.
  3. Кружно повезана листа такође обавља све редовне функције појединачно повезане листе. Заправо, доле разматрани кружни двоструко повезани спискови могу чак елиминисати потребу за целовитим преласком за проналажење елемента. Тај би елемент био само тачно супротан почетку, употпуњавајући само половину повезане листе.

Појединачно повезана листа као кружно повезана листа

Препоручујемо вам да покушате да прочитате и примените доњи код. Представља аритметику показивача повезану са кружно повезаним листама.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Објашњење кода:

  1. Прва два ретка кода су неопходне датотеке заглавља.
  2. Следећи одељак описује структуру сваког аутореференцијалног чвора. Садржи вредност и показивач истог типа као и структура.
  3. Свака структура се више пута повезује са објектима исте врсте.
  4. Постоје различити прототипови функција за:
    1. Додавање елемента на празну повезану листу
    2. Уметање на тренутно истакнутом положају кружно повезане листе.
    3. Уметање након одређене индексиране вредности на повезану листу.
    4. Уклањање / брисање након одређене индексиране вредности на повезаној листи.
    5. Уклањање на тренутно истакнутом положају кружно повезане листе
  5. Последња функција штампа сваки елемент кроз кружно заокретање у било ком стању повезане листе.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Објашњење кода:

  1. За аддЕмпти код доделите празан чвор помоћу функције маллоц.
  2. За овај чвор поставите податке у привремену променљиву.
  3. Доделите и повежите једину променљиву са привременом променљивом
  4. Вратите последњи елемент у главни () / контекст апликације.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Објашњење кода

  1. Ако нема елемента за уметање, додајте га на празну листу и вратите контролу.
  2. Направите привремени елемент који ћете поставити након тренутног елемента.
  3. Повежите показиваче као што је приказано.
  4. Врати последњи показивач као у претходној функцији.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Објашњење кода:

  1. Ако на листи нема елемента, занемарите податке, додајте тренутну ставку као последњу ставку на листи и вратите контролу
  2. За сваку итерацију у петљи до-вхиле осигурајте да постоји претходни показивач који садржи резултат задњег преласка.
  3. Тек тада се може догодити следећи преокрет.
  4. Ако су подаци пронађени или се темп врати назад до последњег показивача, време рада се завршава. Следећи одељак кода одлучује шта треба урадити са ставком.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Објашњење кода:

  1. Ако је пређена цела листа, али ставка није пронађена, прикажите поруку „ставка није пронађена“, а затим вратите контролу позиваоцу.
  2. Ако је чвор пронађен и / или чвор још увек није последњи, створите нови чвор.
  3. Повежите претходни чвор са новим чвором. Повежите тренутни чвор са темп (променљива обилажења).
  4. Ово осигурава да се елемент постави иза одређеног чвора на кружно повезаној листи. Вратите се позиваоцу.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Објашњење кода

  1. Да бисте уклонили само последњи (тренутни) чвор, проверите да ли је ова листа празна. Ако јесте, онда ниједан елемент не може бити уклоњен.
  2. Временска променљива само прелази једну везу напред.
  3. Повежите последњи показивач са показивачем после првог.
  4. Ослободите привремени показивач. Ослобађа неповезани последњи показивач.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Објашњење кода

  1. Као и код претходне функције уклањања, проверите да ли постоји елемент. Ако је ово тачно, ниједан елемент не може бити уклоњен.
  2. Показивачима се додељују одређене позиције за лоцирање елемента који се брише.
  3. Показивачи су напредни, један иза другог. (прев иза темп)
  4. Процес се наставља све док се елемент не пронађе или се следећи елемент повуче до последњег показивача.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Објашњење програма

  1. Ако је елемент пронађен након преласка преко целе повезане листе, приказује се порука о грешци која каже да ставка није пронађена.
  2. У супротном, елемент се раздваја и ослобађа у корацима 3 и 4.
  3. Претходни показивач повезан је са адресом на коју је елемент који треба избрисати означен као „следећи“ (темп).
  4. Показивач привремености је зато ослобођен и ослобођен.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Објашњење кода

  1. Завиривање или прелазак није могућ ако је потребно нула. Корисник треба да додели или убаци чвор.
  2. Ако постоји само један чвор, нема потребе за прелазом, садржај чвора се може одштампати, а вхиле петља се не извршава.
  3. Ако постоји више од једног чвора, тада темп исписује све ставке до последњег елемента.
  4. У тренутку када се достигне последњи елемент, петља се прекида и функција враћа позив главној функцији.

Примене кружно повезане листе

  • Имплементација кружног распореда у системске процесе и кружно заказивање у графикама великих брзина.
  • Заказивање прстенова токена у рачунарским мрежама.
  • Користи се у јединицама за приказ као што су продајне табле које захтевају непрекидно обилажење података.