รายการที่เชื่อมโยง: นี่คือรายการเชื่อมโยงที่เราต้องการย้อนกลับ
หลังจากกลับรายการลิงก์: ด้านล่างจะเป็นผลลัพธ์หลังจากย้อนกลับรายการที่เชื่อมโยงด้านบน
ในแผนภาพตัวอย่างข้างต้น เราจะเห็นว่าโหนดส่วนหัวและโหนดท้ายเปลี่ยนตำแหน่งเมื่อเราย้อนกลับรายการที่เชื่อมโยง โหนดหัวซึ่งตอนนี้เป็นโหนดหาง ชี้ไปที่โหนด null เนื่องจากตอนนี้เป็นโหนดท้าย
ขั้นตอนอัลกอริทึม
- เราสร้างเมธอดหลักและประกาศตัวแปรที่ต้องการ
- จากนั้น ขั้นตอนต่อไปของเราคือการสร้างเมธอดที่สามารถสร้างรายการที่เชื่อมโยงได้ วิธีนี้ช่วยให้เราสร้างรายการที่เชื่อมโยง
- ขั้นตอนต่อไปคือการสร้างวิธีการย้อนกลับรายการที่เชื่อมโยง ในวิธีนี้ เราจะส่งรายการที่เชื่อมโยงทั้งหมด และวิธีนี้จะย้อนกลับรายการที่เชื่อมโยง
- ตอนนี้เราต้องการวิธีอื่นในการแสดงผลลัพธ์ของเราหลังจากย้อนกลับ
- เราจะรวมวิธีการทั้งหมดข้างต้นเป็นวิธีหลักของเรา
เราจะอธิบายรายการลิงก์ย้อนกลับโดยใช้รูปแบบรูปภาพเพื่อให้เข้าใจได้ง่ายขึ้น เริ่มจากตัวอย่างกันก่อน
ด้านล่างนี้เป็นรายการเชื่อมโยงที่เราต้องการย้อนกลับ
ขั้นตอนที่ 1 . โหนดสีเขียวคือโหนดหลัก ซึ่งชี้ไปที่โหนดแรกในการเริ่มต้น
ขั้นตอนที่ 2. ในขั้นตอนถัดไป เราจะสำรวจรายการที่เชื่อมโยงทั้งหมดจนกว่าเราจะไม่ได้รับตัวชี้ว่างถัดจากโหนดส่วนหัว สำหรับสิ่งนั้น เราจะกำหนดชื่อชั่วคราวให้กับโหนดถัดไป ดังแสดงในแผนภาพด้านล่าง
ขั้นตอนที่ 3 เนื่องจากเรามีโหนดอ้างอิงใหม่ที่ชื่อว่า 'ชั่วคราว' ซึ่งสามารถช่วยให้เราสำรวจรายการที่เชื่อมโยงทั้งหมดจนกว่าเราจะไม่ได้รับพอยน์เตอร์ null เราจึงสามารถตั้งค่าลิงก์ถัดไปของโหนดส่วนหัวเป็น null ซึ่งจะไม่ส่งผลกระทบต่อการลิงก์ รายการที่แสดงด้านล่างในแผนภาพ ตัวชี้ null ถัดจากโหนดปัจจุบันเรียกว่าโหนดก่อนหน้า
ขั้นตอนที่ 4 ตอนนี้ เราย้ายโหนดชั่วคราวไปยังโหนดถัดไป และโหนดปัจจุบันไปยังโหนดชั่วคราวก่อนหน้า ตอนนี้เราได้ย้ายไปยังโหนดถัดไปแล้ว เรายังเปลี่ยนโหนดก่อนหน้าจาก null เป็นเพียงโหนดก่อนหน้าของโหนดปัจจุบัน ดังนั้น ตอนนี้โหนดชั่วคราวจะดูแลการข้ามผ่านทั้งหมดจนถึงตัวชี้ว่าง เพื่อให้เราสามารถตั้งค่าการเชื่อมโยงของโหนดปัจจุบันไปยังโหนดก่อนหน้า และตอนนี้มันกำลังชี้ไปยังโหนดก่อนหน้า ดังที่แสดงในแผนภาพด้านล่าง
ดังนั้นเราจึงทำตามขั้นตอนเดียวกัน และสุดท้าย เราจะได้รายการลิงก์ที่ย้อนกลับ
ขั้นตอนที่ 5 .
ขั้นตอนที่ 6
ขั้นตอนที่ 7
ขั้นตอนที่ 8
ขั้นตอนที่ 9
ขั้นตอนที่ 10
ขั้นตอนที่ 11
ขั้นตอนที่ 12
ขั้นตอนที่ 13
ขั้นตอนที่ 14 ในขั้นตอนนี้ รายการที่เชื่อมโยงของเราจะย้อนกลับ
โปรแกรม C++ เพื่อย้อนกลับรายการที่เชื่อมโยง
#รวมถึงโดยใช้ เนมสเปซ มาตรฐาน ;
// วิธีการสร้างโหนด
โครงสร้าง โหนด {
นานาชาติ ค่า ;
โหนด * โหนดถัดไปPtr ;
} * โหนดวัตถุ ;
เป็นโมฆะ สร้างรายการที่เชื่อมโยง ( นานาชาติ น ) ;
เป็นโมฆะ ย้อนกลับLinkedList ( โหนด ** โหนดวัตถุ ) ;
เป็นโมฆะ แสดง ( ) ;
นานาชาติ หลัก ( ) {
นานาชาติ น. ค่า, รายการ ;
ศาล << 'จำนวนโหนดที่คุณต้องการสร้าง =>: ' ;
การกิน >> น ;
สร้างรายการที่เชื่อมโยง ( น ) ;
ศาล << ' \n ข้อมูลในรายการที่เชื่อมโยง: \n ' ;
แสดง ( ) ;
ศาล << ' \n รายการที่เชื่อมโยงหลังจากย้อนกลับ \n ' ;
ย้อนกลับLinkedList ( & โหนดวัตถุ ) ;
แสดง ( ) ;
กลับ 0 ;
}
// เมธอดนี้จะสร้างลิงค์ลิสต์
เป็นโมฆะ สร้างรายการที่เชื่อมโยง ( นานาชาติ น ) {
โครงสร้าง โหนด * โหนดหน้า, * โหนดชั่วคราว ;
นานาชาติ ค่า, ผม ;
โหนดวัตถุ = ( โครงสร้าง โหนด * ) มัลลอค ( ขนาดของ ( โครงสร้าง โหนด ) ) ;
ถ้า ( โหนดวัตถุ == โมฆะ )
ศาล << 'ไม่เพียงพอที่จะกำหนดหน่วยความจำ' ;
อื่น {
ศาล << 'กรุณาป้อนข้อมูลโหนด 1 (เฉพาะตัวเลข):' ;
การกิน >> ค่า ;
โหนดวัตถุ - > ค่า = ค่า ;
โหนดวัตถุ - > โหนดถัดไปPtr = โมฆะ ;
โหนดชั่วคราว = โหนดวัตถุ ;
สำหรับ ( ผม = สอง ; ผม <= น ; ผม ++ ) {
โหนดหน้า = ( โครงสร้าง โหนด * ) มัลลอค ( ขนาดของ ( โครงสร้าง โหนด ) ) ;
// เมื่อไม่มีโหนดใด ๆ ในรายการที่เชื่อมโยง
ถ้า ( โหนดหน้า == โมฆะ ) {
ศาล << 'ไม่สามารถจัดสรรหน่วยความจำได้' ;
หยุดพัก ;
}
อื่น {
ศาล << 'กรุณากรอกข้อมูลโหนด' << ผม << ':' ;
การกิน >> ค่า ;
โหนดหน้า - > ค่า = ค่า ;
โหนดหน้า - > โหนดถัดไปPtr = โมฆะ ;
โหนดชั่วคราว - > โหนดถัดไปPtr = โหนดหน้า ;
โหนดชั่วคราว = โหนดชั่วคราว - > โหนดถัดไปPtr ;
}
}
}
}
เป็นโมฆะ ย้อนกลับLinkedList ( โหนด ** โหนดวัตถุ ) {
โครงสร้าง โหนด * โหนดชั่วคราว = โมฆะ ;
โครงสร้าง โหนด * โหนดก่อนหน้า = โมฆะ ;
โครงสร้าง โหนด * โหนดปัจจุบัน = ( * โหนดวัตถุ ) ;
ในขณะที่ ( โหนดปัจจุบัน ! = โมฆะ ) {
โหนดชั่วคราว = โหนดปัจจุบัน - > โหนดถัดไปPtr ;
โหนดปัจจุบัน - > โหนดถัดไปPtr = โหนดก่อนหน้า ;
โหนดก่อนหน้า = โหนดปัจจุบัน ;
โหนดปัจจุบัน = โหนดชั่วคราว ;
}
( * โหนดวัตถุ ) = โหนดก่อนหน้า ;
}
เป็นโมฆะ แสดง ( ) {
โครงสร้าง โหนด * โหนดชั่วคราว ;
ถ้า ( โหนดวัตถุ == โมฆะ ) {
ศาล << 'รายการเชื่อมโยงว่างเปล่า' ;
}
อื่น {
โหนดชั่วคราว = โหนดวัตถุ ;
ในขณะที่ ( โหนดชั่วคราว ! = โมฆะ )
{
ศาล << โหนดชั่วคราว - > ค่า << ' \t ' ;
โหนดชั่วคราว = โหนดชั่วคราว - > โหนดถัดไปPtr ;
}
}
ศาล << จบ ;
}
เอาต์พุต
คุณต้องการสร้างกี่โหนด =>: 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 ++ มีวิธีอื่นในการย้อนกลับรายการที่เชื่อมโยง แต่นี่เป็นวิธีที่ใช้กันทั่วไปในการย้อนกลับรายการที่เชื่อมโยง ขึ้นอยู่กับคุณที่จะตัดสินใจว่าคุณต้องการแก้ปัญหาของคุณอย่างไร แต่โดยทั่วไปแล้ว ฟังก์ชันรายการที่ลิงก์ย้อนกลับควรเป็นแบบวนซ้ำธรรมดาที่มีการสลับพอยน์เตอร์