1. คำนำ
เมื่อเร็ว ๆ นี้เมื่อตรวจสอบโครงสร้างข้อมูลและอัลกอริทึมปัญหาอัลกอริทึมบางอย่างใช้ความคิดของสแต็คและเมื่อพูดถึงสแต็กเราต้องพูดคุยเกี่ยวกับรายการที่เชื่อมโยง อาร์เรย์และรายการที่เชื่อมโยงเป็นพื้นฐานของโครงสร้างการจัดเก็บเชิงเส้นและสแต็คและคิวเป็นแอปพลิเคชันของโครงสร้างการจัดเก็บเชิงเส้น ~
บทความนี้ส่วนใหญ่จะอธิบายถึงจุดความรู้พื้นฐานของรายการที่เชื่อมโยงเดียวและทำให้การแนะนำง่าย ๆ หากมีข้อผิดพลาดใด ๆ โปรดแก้ไข
2. ทบทวนและความรู้
เมื่อพูดถึงรายการที่เชื่อมโยงก่อนอื่นมาพูดถึงอาร์เรย์ก่อน การเปรียบเทียบกับอาร์เรย์ทำให้คุณเข้าใจโครงสร้างการจัดเก็บของรายการที่เชื่อมโยงเป็นอย่างดี
2.1 ตรวจสอบอาร์เรย์
เราได้เรียนรู้อาร์เรย์ทั้งใน C และ Java:
ข้อดีของอาร์เรย์:
ข้อเสียของอาร์เรย์:
2.2 ลิงก์รายการคำอธิบาย
หลังจากอ่านอาร์เรย์แล้วกลับไปที่รายการที่เชื่อมโยงของเรา:
โหนด n ได้รับการจัดสรรและเชื่อมต่อซึ่งกันและกันผ่านตัวชี้ แต่ละโหนดมีโหนดก่อนหน้าเดียวโหนดแต่ละโหนดมีโหนดที่ตามมาเพียงหนึ่งโหนดโหนดแรกไม่มีโหนดก่อนหน้าและโหนดหางไม่มีโหนดที่ตามมา
ข้อดีของรายการที่เชื่อมโยง:
ข้อเสียของรายการที่เชื่อมโยง:
ฉันจะอธิบายข้อกำหนดที่เกี่ยวข้องกับรายการที่เชื่อมโยงผ่านภาพด้านบน:
ในการกำหนดรายการที่เชื่อมโยงเราต้องใช้ตัวชี้หัวเท่านั้นและรายการที่เชื่อมโยงทั้งหมดสามารถอนุมานได้ผ่านตัวชี้หัว ~
มีหลายประเภทของรายการที่เชื่อมโยง:
1. ตารางลิงค์ทางเดียว
2. ตารางลิงค์แบบสองทิศทาง
3. รายการลิงค์รีไซเคิล
สิ่งที่คุณต้องจำเมื่อใช้งานรายการที่เชื่อมโยงคือ:
ฟิลด์ตัวชี้ในโหนดชี้ไปที่โหนด!
3. รายการลิงค์การใช้งาน Java
อัลกอริทึม:
ก่อนอื่นเรากำหนดคลาสเป็นโหนด
เพื่อความสะดวกในการดำเนินงานฉันได้กำหนดโดยตรงว่าเป็นสาธารณะ
โหนดระดับสาธารณะ {// ข้อมูลข้อมูลสาธารณะข้อมูลสาธารณะ; // โดเมนตัวชี้ชี้ไปที่โหนดสาธารณะต่อไปถัดไป โหนดสาธารณะ () {} โหนดสาธารณะ (ข้อมูล int) {this.data = data; } โหนดสาธารณะ (ข้อมูล int, โหนดถัดไป) {this.data = ข้อมูล; this.next = ถัดไป; - 3.1 สร้างรายการที่เชื่อมโยง (เพิ่มโหนด)
แทรกข้อมูลลงในรายการที่เชื่อมโยง:
/*** เพิ่มข้อมูลลงในรายการที่เชื่อมโยง** @param ข้อมูลค่าที่จะเพิ่ม*/โมฆะคงที่สาธารณะ adddata (ค่า int) {// เริ่มต้นโหนดที่จะเพิ่ม newNode = new node (ค่า); // โหนดชั่วคราวโหนดอุณหภูมิ = head; // ค้นหาโหนดหางในขณะที่ (temp.next! = null) {temp = temp.next; } // กรณีที่ head node.next เป็น null รวมอยู่ ~ temp.next = newNode; - 3.2 การสำรวจรายการที่เชื่อมโยง
เราได้เขียนวิธีการเพิ่มเติมด้านบนและตอนนี้เราจะผ่านมันเพื่อดูว่ามันถูกต้อง ~~~
เริ่มจากโหนดแรกและค้นหาต่อไปจนกว่าจะไม่มีข้อมูลในโหนดที่ตามมา:
/ *** ข้ามรายการที่เชื่อมโยง** @param หัวหัวหัวโหนด*/ โมฆะคงที่สาธารณะ traverse (หัวโหนด) {// โหนดชั่วคราวเริ่มต้นจากโหนดโหนดแรกอุณหภูมิ = head.next; ในขณะที่ (temp! = null) {system.out.println ("ทำตามบัญชีอย่างเป็นทางการ java3y:" + temp.data); // ดำเนินการต่อด้วยอุณหภูมิถัดไป = temp.next; -ผลลัพธ์:
3.3 แทรกโหนด
/*** ใส่โหนด** @param หัวหัวตัวชี้* @param ตำแหน่งดัชนีที่จะแทรก* ค่า @param ค่าที่จะแทรก*/โมฆะสาธารณะคงที่ insertNode (หัวโหนด, ดัชนี int, ค่า int) {// ก่อนอื่นคุณต้องพิจารณาว่าตำแหน่งที่ระบุไว้ ผิดกฎหมาย."); กลับ; } // โหนดชั่วคราวเริ่มจากโหนดเริ่มต้นโหนดอุณหภูมิ = head; // คลิกตำแหน่งปัจจุบันของ int traversal int currentPos = 0; // เริ่มต้นโหนดที่จะแทรกโหนด insertNode = โหนดใหม่ (ค่า); ในขณะที่ (temp.next! = null) {// ตำแหน่งของโหนดก่อนหน้าถูกพบถ้า (((ดัชนี - 1) == currentpos) {// temp แสดงถึงโหนดก่อนหน้า // ชี้ตัวชี้ดั้งเดิมจากโหนดก่อนหน้าไปยังโหนดที่แทรกไปยัง InsertNode.next = temp.next; // ชี้ฟิลด์ตัวชี้ของโหนดก่อนหน้าไปยังโหนดที่จะแทรก temp.next = insertNode; กลับ; } currentPos ++; temp = temp.next; - 3.4 รับความยาวของรายการที่เชื่อมโยง
มันง่ายมากที่จะได้รับความยาวของรายการที่เชื่อมโยง สามารถทำได้โดยการสำรวจและรับ +1 สำหรับแต่ละโหนด ~
/ *** รับความยาวของรายการที่เชื่อมโยง* @param หัวหัวตัวชี้*/ public static int linklistLength (หัวโหนด) {int length = 0; // โหนดชั่วคราวเริ่มจากโหนดโหนดแรกอุณหภูมิ = head.next; // ค้นหาโหนดหางในขณะที่ (temp! = null) {ความยาว ++; temp = temp.next; } ความยาวคืน; - 3.5 ลบโหนด
การลบโหนดในบางตำแหน่งนั้นคล้ายกับโหนดการแทรกและคุณต้องค้นหาโหนดก่อนหน้าด้วย เปลี่ยนฟิลด์ตัวชี้ของโหนดก่อนหน้าและคุณสามารถลบได้ ~
/** * ลบโหนดตามตำแหน่ง * * @param หัวหัวตัวชี้ * @param ดัชนีตำแหน่งที่จะลบ */โมฆะคงที่สาธารณะ deletenode (หัวโหนด, ดัชนี int) {// ก่อนอื่นคุณต้องตรวจสอบว่าตำแหน่งที่ระบุนั้นถูกกฎหมายหรือไม่ (ดัชนี <1 || ดัชนี กลับ; } // โหนดชั่วคราวเริ่มจากโหนดเริ่มต้นโหนดอุณหภูมิ = head; // ตำแหน่งปัจจุบันของบันทึกการเดินทางเป็น int currentPos = 0; ในขณะที่ (temp.next! = null) {// ที่ตั้งของโหนดก่อนหน้านี้พบได้ถ้า (((ดัชนี - 1) == currentpos) {// temp แสดงถึงโหนดก่อนหน้า // temp.next แสดงถึงโหนดที่คุณต้องการลบ // ที่เก็บ // ที่เก็บของโหนดที่คุณต้องการลบโหนด deletenode = temp.next; // โหนดถัดไปที่คุณต้องการลบโหนดจะถูกส่งไปยังโหนดก่อนหน้าเพื่อควบคุม temp.next = deleTenode.next; // java จะรีไซเคิลและไม่ควรทำให้รู้สึกมากที่จะตั้งค่าให้เป็นโมฆะ (โดยส่วนตัวแล้วฉันคิดว่าถ้ามันไม่ถูกต้องโปรดชี้ให้เห็น ~) deleTenode = null; กลับ; } currentPos ++; temp = temp.next; - 3.6 เรียงลำดับรายการที่เชื่อมโยง
ฉันได้พูดคุยเกี่ยวกับอัลกอริทึมการเรียงลำดับ 8 ครั้งแล้ว [สรุปของแปดอัลกอริทึมการเรียงลำดับ] ฉันจะเลือกการเรียงลำดับฟองง่าย ๆ ในครั้งนี้ (ที่จริงฉันต้องการเขียนเรียงลำดับอย่างรวดเร็ว แต่มันรู้สึกยากที่จะลอง ... )
/ ** * เรียงลำดับรายการที่เชื่อมโยง * * @param head * */ โมฆะสาธารณะคงที่ sortlinklist (หัวโหนด) {โหนด currentNode; โหนด NextNode; สำหรับ (currentNode = head.next; currentNode.next! = null; currentNode = currentNode.next) {สำหรับ (nextNode = head.next; nextNode.next! = null; nextNode = nextNode.next) nextNode.data = nextNode.next.data; nextNode.next.data = temp; - 3.7 ค้นหาโหนด k-last ในรายการที่เชื่อมโยง
อัลกอริทึมนี้ค่อนข้างน่าสนใจ: ตั้งค่าพอยน์เตอร์สองตัว P1 และ P2 เพื่อให้โหนด P2 K เร็วกว่า P1 และข้ามย้อนหลังในเวลาเดียวกัน เมื่อ P2 ว่างเปล่า P1 เป็นโหนดสุดท้ายของ K-th
/ *** ค้นหา k-th จนกระทั่งโหนดสุดท้ายในรายการที่เชื่อมโยง (ตั้งค่าพอยน์เตอร์สองตัว P1 และ P2 ทำให้ P2 K เร็วกว่า P1 และย้อนกลับไปข้างหลังในเวลาเดียวกันเมื่อ P2 ว่างเปล่า P1 คือ K-th จนกระทั่งหัว Node************************************************ LinkListLength (head)) ส่งคืน null; P1.Next;
3.8 ลบข้อมูลซ้ำในรายการที่เชื่อมโยง
มันคล้ายกับการเรียงลำดับฟองตราบใดที่มันเท่ากันมันสามารถลบได้ ~
/ ** * ลบข้อมูลที่ซ้ำกันในรายการที่เชื่อมโยง (คล้ายกับเดือดมันเทียบเท่ากับการลบ) * * @param หัวหัวหัวโหนด */ โมฆะสาธารณะคงที่ deleteduplecate (หัวโหนด) {// โหนดชั่วคราว (เริ่มต้นจากโหนดแรก-> โหนดที่มีข้อมูลจริง // โหนดถัดไปของโหนดปัจจุบัน (โหนดแรก) โหนด nextNode = temp.next; ในขณะที่ (temp.next! = null) {ในขณะที่ (nextNode.next! = null) {ถ้า (nextNode.next.data == nextNode.data) {// ลบโหนดถัดไป } else {// ดำเนินการต่อด้วย nextNode nextNode = nextNode.next; }} // รอบถัดไปของการเปรียบเทียบ temp = temp.next; - 3.9 สอบถามโหนดกลางของรายการที่เชื่อมโยง
อัลกอริทึมนี้ก็น่าสนใจเช่นกัน: ตัวชี้ที่ใช้เวลา 1 ขั้นตอนในแต่ละครั้งตัวชี้ที่ใช้เวลา 2 ขั้นตอนในแต่ละครั้งจากนั้นใช้เวลาหนึ่งขั้นตอนนั่นคือโหนดกลาง
/ *** สอบถามโหนดกลางของรายการที่เชื่อมโยงเดียว*/ โหนดสแตติกสาธารณะ searchMid (หัวโหนด) {โหนด P1 = หัว; โหนด p2 = หัว; // ทำขั้นตอนเดียวและหนึ่งขั้นตอนสองขั้นตอนจนกว่าจะเป็นโมฆะ โหนดกลางที่คุณไปถึง (p2! = null && p2.next! = null && p2.next.next! = null) {p1 = p1.next; p2 = p2.next.next; } return p1; -3.10 เอาต์พุตแบบเรียกซ้ำตารางที่เชื่อมโยงเดี่ยวจากหางหนึ่งไปอีกหัว
/ *** เอาต์พุตรายการเดียวที่เชื่อมโยงจากหางไปยังหัวโดยการเรียกซ้ำ** @param หัวหัวโหนด*/ โมฆะสาธารณะคงที่ printListreversely (หัวโหนด) {ถ้า (หัว! = null) {printListreversely (head.next); System.out.println (head.data); - 3.11 รายการลิงก์ย้อนกลับ
/ *** ใช้การผกผันของรายการที่เชื่อมโยง** @param โหนดโหนดหัวของรายการที่เชื่อมโยง*/ โหนดคงที่สาธารณะ ReverselinkList (โหนดโหนด) {โหนดก่อนหน้า; if (node == null || node.next == null) {prev = node; } else {node tmp = reverselinkList (node.next); node.next.next = node; node.next = null; prev = tmp; } return prev; - อ้างอิงถึงรายการลิงก์ย้อนกลับจาก: //www.vevb.com/article/136185.htm
4. ในที่สุด
ไม่ยากที่จะเข้าใจรายการที่เชื่อมโยงเอง แต่อาจทำให้เกิดอาการปวดหัวเมื่อทำการดำเนินการที่เกี่ยวข้อง head.next ถัดไปถัดไปต่อไป .... (ฉันยังอ่อนแอในอัลกอริทึม ... ฉันไม่มีสมองมากพอ ... ) ฉันเขียนสิ่งเล็ก ๆ น้อย ๆ นี้หลังจากสองวัน ...
คุณสามารถทำอะไรก็ได้เพียงแค่รู้ว่าตัวชี้หัวเมื่อใช้งานรายการที่เชื่อมโยง
1. เพิ่มข้อมูลในรายการที่เชื่อมโยง
2. สำรวจรายการที่เชื่อมโยง
3. แทรกโหนดลงในรายการที่เชื่อมโยงในตำแหน่งที่กำหนด
4. รับความยาวของรายการที่เชื่อมโยง
5. ลบโหนดในตำแหน่งที่กำหนด
6. เรียงลำดับรายการที่เชื่อมโยง
7. ค้นหาโหนด k-last ในรายการที่เชื่อมโยง
8. ลบข้อมูลที่ซ้ำกันในรายการที่เชื่อมโยง
9. สอบถามโหนดกลางของรายการที่เชื่อมโยง
10. เอาต์พุตตารางลิงค์เดียวซ้ำจากหางถึงหัว
11. รายการลิงค์ย้อนกลับ
PS: การใช้งานของทุกคนจะแตกต่างกันดังนั้นรายละเอียดเล็ก ๆ น้อย ๆ บางอย่างจะเปลี่ยนแปลงอย่างหลีกเลี่ยงไม่ได้และไม่มีวิธีที่แน่นอนในการเขียนดังนั้นคุณจึงสามารถตระหนักถึงฟังก์ชั่นที่เกี่ยวข้อง ~
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่าเนื้อหาของบทความนี้จะมีค่าอ้างอิงบางอย่างสำหรับการศึกษาหรือที่ทำงานของทุกคน หากคุณมีคำถามใด ๆ คุณสามารถฝากข้อความไว้เพื่อสื่อสาร ขอบคุณสำหรับการสนับสนุน Wulin.com
ข้อมูลอ้างอิง: