повезана листа: Ово је повезана листа коју желимо да преокренемо.
Након обрнуте повезане листе: Доле ће бити резултат након преокретања горе повезане листе.
У горњем дијаграму примера, можемо видети да главни чвор и репни чвор мењају своје позиције када обрнемо повезану листу. Главни чвор, који је сада репни чвор, указује на нулти чвор јер је сада репни чвор.
Кораци алгоритма
- Креирамо главни метод и декларишемо неке потребне променљиве.
- Затим, наш следећи корак је да креирамо метод који може да креира повезану листу. Овај метод нам помаже да направимо повезану листу.
- Следећи корак је креирање методе за преокретање повезане листе. У овој методи прослеђујемо целу повезану листу, а овај метод ће обрнути повезану листу.
- Сада нам је потребан још један метод да прикажемо наш резултат након што га поништимо.
- Комбиноваћемо све ове горе наведене методе у наш главни метод.
Објаснићемо обрнуту повезану листу користећи неку сликовну форму да бисмо је лакше разумели. Дакле, почнимо са примером.
У наставку је повезана листа коју желимо да вратимо.
Корак 1 . Зелено обојени чвор је главни чвор, који указује на први чвор у покретању.
Корак 2. У следећем кораку ћемо обићи целу повезану листу све док не добијемо нулл показивач поред чвора заглавља. За то ћемо следећем чвору доделити привремено име, као што је приказано на дијаграму испод.
Корак 3. Пошто имамо нови референтни чвор под називом „привремени“, који нам може помоћи да пређемо целу листу повезаних док не добијемо нулл показивач, тако да можемо поставити следећу везу чвора заглавља као нулл, што неће утицати на повезану листу као што је приказано испод на дијаграму. Нулти показивач поред тренутног чвора назива се претходни чвор.
Корак 4. Сада померамо привремени чвор на следећи чвор, а тренутни чвор на претходни привремени чвор. Дакле, сада смо прешли на следећи чвор. Такође мењамо претходни чвор из нулте у само претходни чвор тренутног чвора. Дакле, сада ће се привремени чвор побринути за све прелазе до нулте показивача тако да можемо поставити везу тренутног чвора са претходним чвором, а сада он показује на претходни чвор, као што је приказано на дијаграму испод.
Дакле, следимо исте кораке и, коначно, добићемо обрнуту повезану листу.
Корак 5 .
Корак 6.
Корак 7.
Корак 8.
Корак 9.
Корак 10.
Корак 11.
Корак 12.
Корак 13.
Корак 14. У овом кораку, наша повезана листа се преокренула.
Ц++ Програм за преокретање повезане листе
#инцлуде <иостреам>Користећи именског простора стд ;
// Метод за креирање чвора
струцт чвор {
инт вредност ;
чвор * нектНодеПтр ;
} * нодеОбјецт ;
празнина цреатеЛинкедЛист ( инт н ) ;
празнина реверсеЛинкедЛист ( чвор ** нодеОбјецт ) ;
празнина приказ ( ) ;
инт главни ( ) {
инт н, вредност, ставка ;
цоут << 'Колико чворова желите да креирате =>: ' ;
једење >> н ;
цреатеЛинкедЛист ( н ) ;
цоут << ' \н Информације на повезаној листи: \н ' ;
приказ ( ) ;
цоут << ' \н Повезана листа након обрнуте \н ' ;
реверсеЛинкедЛист ( & нодеОбјецт ) ;
приказ ( ) ;
повратак 0 ;
}
// Овај метод ће креирати повезану листу
празнина цреатеЛинкедЛист ( инт н ) {
струцт чвор * фронтНоде, * темпНоде ;
инт вредност, тј ;
нодеОбјецт = ( струцт чвор * ) маллоц ( величина ( струцт чвор ) ) ;
ако ( нодеОбјецт == НУЛА )
цоут << 'Недовољно за процену памћења' ;
друго {
цоут << 'Молимо унесите информације о чвору 1 (само број): ' ;
једење >> вредност ;
нодеОбјецт - > вредност = вредност ;
нодеОбјецт - > нектНодеПтр = НУЛА ;
темпНоде = нодеОбјецт ;
за ( и = два ; и <= н ; и ++ ) {
фронтНоде = ( струцт чвор * ) маллоц ( величина ( струцт чвор ) ) ;
// Када нема чвора у повезаној листи
ако ( фронтНоде == НУЛА ) {
цоут << „Меморија се не може доделити“ ;
пауза ;
}
друго {
цоут << 'Молимо унесите информације о чвору' << и << ':' ;
једење >> вредност ;
фронтНоде - > вредност = вредност ;
фронтНоде - > нектНодеПтр = НУЛА ;
темпНоде - > нектНодеПтр = фронтНоде ;
темпНоде = темпНоде - > нектНодеПтр ;
}
}
}
}
празнина реверсеЛинкедЛист ( чвор ** нодеОбјецт ) {
струцт чвор * темпНоде = НУЛА ;
струцт чвор * претходниЧвор = НУЛА ;
струцт чвор * цуррентНоде = ( * нодеОбјецт ) ;
док ( цуррентНоде ! = НУЛА ) {
темпНоде = цуррентНоде - > нектНодеПтр ;
цуррентНоде - > нектНодеПтр = претходниЧвор ;
претходниЧвор = цуррентНоде ;
цуррентНоде = темпНоде ;
}
( * нодеОбјецт ) = претходниЧвор ;
}
празнина приказ ( ) {
струцт чвор * темпНоде ;
ако ( нодеОбјецт == НУЛА ) {
цоут << „Листа линкова је празна“ ;
}
друго {
темпНоде = нодеОбјецт ;
док ( темпНоде ! = НУЛА )
{
цоут << темпНоде - > вредност << ' \т ' ;
темпНоде = темпНоде - > нектНодеПтр ;
}
}
цоут << ендл ;
}
Излаз
Колико чворова желите да направите =>: 6Унесите информације о чвору 1 (само број): 101
Унесите информације о чвору 2: 95
Унесите информације о чвору 3: 61
Унесите информације о чвору 4: 19
Унесите информације о чвору 5: 12
Унесите информације о чвору 6: 11
Информације на повезаној листи:
101 95 61 19 12 11
Повезана листа након обрнуте
11 12 19 61 95 101
Закључак
Овај чланак о ЛинукХинт-у је прегледао како да обрнете повезану листу у Ц++. Постоје неки други методи за преокретање повезане листе, али ово је врло чест метод за преокретање повезане листе. На вама је да одлучите како желите да решите своје проблеме, али генерално функција обрнуте повезане листе треба да буде једноставна петља са заменама показивача.