การวิเคราะห์และการใช้งานทางเลือกการกลับรายการที่เชื่อมโยงทั้งสองแบบเชื่อมโยง

รายการที่เชื่อมโยงทั้งสองรายการกลับด้านนั่นคือตัวชี้หางของตารางโซ่ที่เชื่อมโยงอื่น ๆ จะถูกย้อนกลับจากการควบรวมกิจการจากตัวชี้หางของรายการที่เชื่อมโยงหนึ่งรายการไปยังรายการที่เชื่อมโยงอื่น ๆ ด้านล่างแนวคิดและรหัสการใช้งานของการสลับการกลับรายการของรายการที่เชื่อมโยงทั้งสองรายการจะถูกนำเสนอในรายละเอียด

1. คำอธิบายปัญหา

ลิงก์ A และ B
A: 1-> 2-> 3-> 4
B: a-> b-> c-> d
โปรดย้อนกลับรายการที่เชื่อมโยงสองรายการสลับกัน
4-> d-> 3-> c-> 2-> b-> 1-> a
คำจำกัดความประเภทโหนดมีดังนี้:

 classnode {โหนดสาธารณะถัดไป;

2. ซอร์สโค้ด:

รายการที่เชื่อมโยง A และ B สองรายการจะถูกส่งกลับไปยังรายการที่เชื่อมโยงหลังจากการประมวลผล:

 Node Reverse_merge (Node A, Node B) {// a, b ทั้งหมดมีเพียงหนึ่งโหนดถ้า (a.next == null) {a.next = b; . NEXT; ;

สามการวิเคราะห์:

โปรแกรมแบ่งออกเป็นสามส่วน -ก่อนที่จะรอบในขณะที่วงจรในขณะที่และวงจรในขณะที่
1) การประมวลผลรายการที่เชื่อมโยงก่อนหน้า A และ B

2) ในขณะที่วงจร -ส่วนการประมวลผลหลักของกระบวนการประมวลผลสามารถทำซ้ำได้ที่นี่

อย่างไรก็ตามโหนดที่ A ตั้งอยู่ใน A. ที่ผ่านการประมวลผลเป็นพิเศษเฉพาะสำหรับโหนดที่ A ตั้งอยู่จำเป็นต้องมีการดำเนินการถัดไป = null ซึ่งหมายความว่าอะตอมแรกใน 1 ควรดำเนินการนอกวงจร

หากคุณใช้วิธี 2 คุณจะต้องวาง 1 นิ้วให้ออกจากวงจร ดังนั้นโครงสร้างอะตอมที่อธิบายไว้ใน 2 จึงใช้ที่นี่

ข้อมูลที่ต้องการโดยโครงสร้างอะตอม

เมื่อเราเข้าสู่รอบหนึ่งสมมติว่าการดำเนินการของวงกลมสีน้ำเงินในเวลานี้สถานะของรายการที่เชื่อมโยงของเราคือ:

วิธีการวาดภาพที่ใช้งานง่ายคือ:

มันเกี่ยวข้องกับ 3 โหนด -2,3 และ C ส่วนสีแดงคือวิธีการเชื่อมโยงที่เราต้องการทำ ในการเชื่อมโยง c-> 2,3-> c เราต้องรู้ว่ามีตัวชี้ที่สอดคล้องกันเพื่อบันทึกตำแหน่งของพวกเขา ดังนั้นก่อนรอบวัฏจักรเราจำเป็นต้องควบคุมที่อยู่ขององค์ประกอบทั้งสามนี้และหลังจากการประมวลผลในลักษณะเดียวกันโครงสร้างอะตอมที่ต้องประมวลผลในลักษณะเดียวกัน

ตัวอย่างเช่นวิธีการต่อไปนี้บันทึกที่อยู่ของสามโหนดที่ออกแบบในรอบนี้:

A, Na และ B แสดงตัวชี้หรืออ้างอิงไปยังโหนดที่เกี่ยวข้อง

หลังจากการประมวลผลเสร็จสิ้นคุณต้องบันทึกโหนดที่เกี่ยวข้องในโครงสร้างอะตอมถัดไปในลักษณะเดียวกันเพื่อให้แน่ใจว่าวัฏจักรสามารถดำเนินการได้ตามตรรกะแบบครบวงจร

การทำงานที่ได้รับมอบหมายเหล่านี้เป็นสิ่งที่รหัสกลางของวงจรทำ นอกจากนี้ NextB ถูกกำหนดให้เป็นตัวแปรระดับกลางในรหัสเพื่อบันทึกที่อยู่ของโหนด D ก่อนหน้าก่อนที่จะยกเลิกการเชื่อมต่อ C-> D เนื่องจาก C ถึง 2 จะสูญเสียการติดต่อ D. ตัวแปรระดับกลางนี้เป็นสิ่งจำเป็น

3) ก่อนการวนซ้ำทั้งหมด -แก้ไขปัญหาที่เกิดจากการเตรียมการ

เราไม่ได้จัดการโหนด A เพราะมันพิเศษเกินไปและไม่มีโครงสร้างอะตอมที่เหมาะสมที่สามารถรวมไว้ด้วย ดังนั้นเราจึงวางมันไว้นอกวงจรและเตรียมพร้อมสำหรับการไหลเวียน

หลังจากนั้นเราสามารถใส่ 1, 2 และ b ในรอบ ที่นี่มีเพียงหนึ่งโหนด A และ B ซึ่งจำเป็นต้องดำเนินการแยกต่างหาก

4) หลังจากวนรอบทั้งหมด -การประมวลผลขั้นสุดท้าย

เมื่อเราพบว่ารายการที่เชื่อมโยง B ถึงจุดสิ้นสุดวงจรจะสิ้นสุดลง แต่ในเวลานี้มีโหนดการจัดการ วัฏจักรของเราจะหยุดในโครงสร้างอะตอมนี้:

ในการดำเนินการขั้นสุดท้ายเราต้องประมวลผลขั้นตอนการเชื่อมโยงของ D-> 3,4-> D-this ด้วยตนเองเช่นกันเพราะการรักษาโครงสร้างอะตอมจะต้องพบ

นี่ไม่ใช่วิธีที่สมบูรณ์และมีหลายสิ่งที่ไม่ได้ดำเนินการ นอกจากนี้โครงสร้างข้อมูลโหนดยังไม่ได้กำหนดไว้อย่างสมบูรณ์ แต่นี่ไม่ใช่จุดสนใจของบทความนี้

จากการวิเคราะห์โดยละเอียดข้างต้นฉันหวังว่าจะช่วยให้ทุกคนเข้าใจวิธีการและการใช้งานการควบรวมกิจการทางเลือกที่เชื่อมโยงทั้งสองรายการ