רשימה מקושרת: זוהי רשימה מקושרת שאנו רוצים להפוך אותה.
אחרי רשימה מקושרת הפוכה: התוצאה שלמטה תהיה לאחר הפיכת הרשימה המקושרת למעלה.
בתרשים הדוגמה לעיל, אנו יכולים לראות שצומת הראש וצומת הזנב משנים את מיקומם כאשר אנו הופכים את הרשימה המקושרת. צומת הראש, שהוא כעת צומת זנב, מצביע על הצומת האפס מכיוון שהוא כעת צומת זנב.
שלבי אלגוריתם
- אנו יוצרים שיטה ראשית ומצהירים על כמה משתנים נדרשים.
- לאחר מכן, השלב הבא שלנו הוא ליצור שיטה שיכולה ליצור רשימה מקושרת. שיטה זו עוזרת לנו ליצור רשימה מקושרת.
- השלב הבא הוא יצירת שיטה להפוך את הרשימה המקושרת. בשיטה זו, אנו מעבירים את כל הרשימה המקושרת, ושיטה זו תהפוך את הרשימה המקושרת.
- כעת, אנו זקוקים לשיטה נוספת כדי להציג את התוצאה שלנו לאחר הפיכתה.
- נשלב את כל השיטות הנ'ל לשיטה העיקרית שלנו.
אנו הולכים להסביר רשימה מקושרת הפוכה באמצעות צורה ציורית כלשהי כדי להקל על ההבנה. אז בואו נתחיל עם הדוגמה.
להלן רשימה מקושרת שאנו רוצים להפוך.
שלב 1 . הצומת בצבע ירוק הוא צומת ראש, המצביע על הצומת הראשון בהפעלה.
שלב 2. בשלב הבא, נעבור את כל הרשימה המקושרת עד שלא נקבל את מצביע ה-null ליד צומת הכותרת. לשם כך, אנו הולכים להקצות לצומת הבא שם זמני, כפי שמוצג בתרשים שלהלן.
שלב 3. מכיוון שיש לנו צומת התייחסות חדש בשם 'זמני', שיכול לעזור לנו לעבור את כל הרשימה המקושרת עד שלא נקבל את מצביע ה-null, אז נוכל להגדיר את הקישור הבא של צומת הכותרת כ-null, מה שלא ישפיע על המקושר. רשימה כפי שמוצג להלן בתרשים. מצביע האפס שליד הצומת הנוכחי נקרא הצומת הקודם.
שלב 4. כעת, נעביר את הצומת הזמני לצומת הבא ואת הצומת הנוכחי לצומת הזמני הקודם. אז עכשיו עברנו לצומת הבא. אנו גם משנים את הצומת הקודם מ-null רק לצומת הקודם של הצומת הנוכחי. אז עכשיו הצומת הזמני ידאג לכל המעברים עד למצביע האפס כדי שנוכל להגדיר את הקישור של הצומת הנוכחי לצומת הקודם, ועכשיו הוא מצביע על הצומת הקודם, כפי שמוצג בתרשים למטה.
אז נבצע את אותם השלבים, ולבסוף, נקבל רשימה מקושרת הפוכה.
שלב 5 .
שלב 6.
שלב 7.
שלב 8.
שלב 9.
שלב 10.
שלב 11.
שלב 12.
שלב 13.
שלב 14. בשלב זה, הרשימה המקושרת שלנו התהפכה.
תוכנית C++ להיפוך רשימה מקושרת
#includeבאמצעות מרחב שמות סטד ;
// שיטה ליצירת הצומת
struct צוֹמֶת {
int ערך ;
צוֹמֶת * nextNodePtr ;
} * nodeObject ;
בָּטֵל createLinkedList ( int נ ) ;
בָּטֵל reverseLinkedList ( צוֹמֶת ** nodeObject ) ;
בָּטֵל לְהַצִיג ( ) ;
int רָאשִׁי ( ) {
int n,ערך,פריט ;
cout << 'כמה צמתים אתה רוצה ליצור =>: ' ;
אֲכִילָה >> נ ;
createLinkedList ( נ ) ;
cout << ' \n מידע ברשימה המקושרת: \n ' ;
לְהַצִיג ( ) ;
cout << ' \n רשימה מקושרת לאחר הפוך \n ' ;
reverseLinkedList ( & nodeObject ) ;
לְהַצִיג ( ) ;
לַחֲזוֹר 0 ;
}
// שיטה זו תיצור את הרשימה המקושרת
בָּטֵל createLinkedList ( int נ ) {
struct צוֹמֶת * frontNode, * tempNode ;
int ערך, אני ;
nodeObject = ( struct צוֹמֶת * ) malloc ( מידה של ( struct צוֹמֶת ) ) ;
אם ( nodeObject == ריק )
cout << 'לא מספיק כדי לקבוע זיכרון' ;
אַחֵר {
cout << 'אנא הזן את המידע של צומת 1 (מספר בלבד): ' ;
אֲכִילָה >> ערך ;
nodeObject - > ערך = ערך ;
nodeObject - > nextNodePtr = ריק ;
tempNode = nodeObject ;
ל ( אני = שתיים ; אני <= נ ; אני ++ ) {
frontNode = ( struct צוֹמֶת * ) malloc ( מידה של ( struct צוֹמֶת ) ) ;
// כאשר אין שום צומת ברשימה המקושרת
אם ( frontNode == ריק ) {
cout << 'לא ניתן להקצות זיכרון' ;
לשבור ;
}
אַחֵר {
cout << 'אנא הזן את המידע של הצומת' << אני << ':' ;
אֲכִילָה >> ערך ;
frontNode - > ערך = ערך ;
frontNode - > nextNodePtr = ריק ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
בָּטֵל reverseLinkedList ( צוֹמֶת ** nodeObject ) {
struct צוֹמֶת * tempNode = ריק ;
struct צוֹמֶת * הקודם צומת = ריק ;
struct צוֹמֶת * currentNode = ( * nodeObject ) ;
בזמן ( currentNode ! = ריק ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = הקודם צומת ;
הקודם צומת = currentNode ;
currentNode = tempNode ;
}
( * nodeObject ) = הקודם צומת ;
}
בָּטֵל לְהַצִיג ( ) {
struct צוֹמֶת * 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++. ישנן כמה שיטות אחרות להפוך רשימה מקושרת, אך זוהי שיטה נפוצה מאוד להפוך רשימה מקושרת. זה תלוי בך להחליט איך אתה רוצה לפתור את הבעיות שלך, אבל בדרך כלל פונקציית הרשימה המקושרת ההפוכה צריכה להיות לולאה פשוטה עם החלפות מצביעים.