свързан списък: Това е свързан списък, който искаме да обърнем.
След обърнат свързан списък: По-долу ще бъде резултатът след обръщане на списъка с връзки по-горе.
В горната примерна диаграма можем да видим, че главният възел и опашният възел променят своите позиции, когато обърнем свързания списък. Главният възел, който сега е опашен възел, сочи към нулевия възел, защото сега е опашен възел.
Стъпки на алгоритъма
- Създаваме основен метод и декларираме някои задължителни променливи.
- След това следващата ни стъпка е да създадем метод, който може да създаде свързан списък. Този метод ни помага да създадем свързан списък.
- Следващата стъпка е да създадете метод за обръщане на свързания списък. В този метод ние предаваме целия свързан списък и този метод ще обърне свързания списък.
- Сега се нуждаем от друг метод за показване на нашия резултат след обръщането му.
- Ще комбинираме всички тези методи по-горе в нашия основен метод.
Ще обясним обратния свързан списък, използвайки някаква илюстративна форма, за да го направим по-лесен за разбиране. Така че нека започнем с примера.
По-долу е свързан списък, който искаме да обърнем.
Етап 1 . Оцветеният в зелено възел е начален възел, който сочи към първия възел в стартирането.
Стъпка 2. В следващата стъпка ще преминем през целия свързан списък, докато не получим нулевия указател до заглавния възел. За целта ще присвоим на следващия възел временно име, както е показано на диаграмата по-долу.
Стъпка 3. Тъй като имаме нов референтен възел, наречен „временен“, който може да ни помогне да обходим целия свързан списък, докато не получим нулевия указател, така че можем да зададем следващата връзка на заглавния възел като нулев, което няма да повлияе на свързания списък, както е показано на диаграмата по-долу. Нулевият указател до текущия възел се нарича предишен възел.
Стъпка 4. Сега преместваме временния възел към следващия възел и текущия възел към предишния временен възел. Така че сега се преместихме към следващия възел. Също така променяме предишния възел от null само на предишния възел на текущия възел. Така че сега временният възел ще се погрижи за всички пресичания до нулевия указател, така че да можем да настроим връзката на текущия възел към предишния възел и сега той сочи към предишния възел, както е показано на диаграмата по-долу.
Така че следваме същите стъпки и най-накрая ще получим обърнат свързан списък.
Стъпка 5 .
Стъпка 6.
Стъпка 7.
Стъпка 8.
Стъпка 9.
Стъпка 10.
Стъпка 11.
Стъпка 12.
Стъпка 13.
Стъпка 14. На тази стъпка нашият свързан списък се обърна.
C++ програма за обръщане на свързан списък
#includeизползвайки пространство от имена std ;
// Метод за създаване на възела
структура възел {
вътр стойност ;
възел * nextNodePtr ;
} * nodeObject ;
невалиден createLinkedList ( вътр н ) ;
невалиден reverseLinkedList ( възел ** nodeObject ) ;
невалиден дисплей ( ) ;
вътр основен ( ) {
вътр n,стойност,елемент ;
cout << „Колко възли искате да създадете =>:“ ;
храня се >> н ;
createLinkedList ( н ) ;
cout << ' \н Информация в свързания списък: \н ' ;
дисплей ( ) ;
cout << ' \н Свързан списък след обръщане \н ' ;
reverseLinkedList ( и nodeObject ) ;
дисплей ( ) ;
връщане 0 ;
}
// Този метод ще създаде свързания списък
невалиден createLinkedList ( вътр н ) {
структура възел * frontNode, * tempNode ;
вътр стойност, т.е ;
nodeObject = ( структура възел * ) malloc ( размер на ( структура възел ) ) ;
ако ( nodeObject == НУЛА )
cout << 'Недостатъчно за задиране на паметта' ;
друго {
cout << 'Моля, въведете информацията за възел 1 (само номер): ' ;
храня се >> стойност ;
nodeObject - > стойност = стойност ;
nodeObject - > nextNodePtr = НУЛА ;
tempNode = nodeObject ;
за ( аз = две ; аз <= н ; аз ++ ) {
frontNode = ( структура възел * ) malloc ( размер на ( структура възел ) ) ;
// Когато няма нито един възел в свързания списък
ако ( frontNode == НУЛА ) {
cout << „Паметта не може да бъде разпределена“ ;
прекъсвам ;
}
друго {
cout << „Моля, въведете информацията за възела“ << аз << ':' ;
храня се >> стойност ;
frontNode - > стойност = стойност ;
frontNode - > nextNodePtr = НУЛА ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
невалиден reverseLinkedList ( възел ** nodeObject ) {
структура възел * tempNode = НУЛА ;
структура възел * предишен възел = НУЛА ;
структура възел * currentNode = ( * nodeObject ) ;
докато ( currentNode ! = НУЛА ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = предишен възел ;
предишен възел = currentNode ;
currentNode = tempNode ;
}
( * nodeObject ) = предишен възел ;
}
невалиден дисплей ( ) {
структура възел * tempNode ;
ако ( nodeObject == НУЛА ) {
cout << „Списъкът с връзки е празен“ ;
}
друго {
tempNode = nodeObject ;
докато ( tempNode ! = НУЛА )
{
cout << tempNode - > стойност << ' \T ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << endl ;
}
Изход
Колко възли искате да създадете =>: 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
Заключение
Тази статия на LinuxHint прегледа как да обърнете свързан списък в C++. Има някои други методи за обръщане на свързан списък, но това е много често срещан метод за обръщане на свързан списък. От вас зависи да решите как искате да решите проблемите си, но като цяло функцията за обратно свързан списък трябва да бъде обикновен цикъл с размяна на указатели.