ตารางเชิงเส้น
ตารางเชิงเส้นเป็นโครงสร้างข้อมูลที่ง่ายที่สุดและใช้กันมากที่สุด พวกเขาเป็นลำดับที่ จำกัด ประกอบด้วยองค์ประกอบข้อมูลส่วนบุคคล (โหนด) ในหมู่พวกเขาจำนวน N ขององค์ประกอบข้อมูลคือความยาวของตาราง เมื่อ n เป็นศูนย์มันจะกลายเป็นตารางที่ว่างเปล่า ตารางเชิงเส้นที่ไม่ว่างเปล่ามักจะถูกบันทึกเป็น:
(a1, a2, …, ai-1, ai, ai+1, …, an)
1. การจัดเก็บตามลำดับและอัลกอริทึมของตารางเชิงเส้น
การจัดเก็บตามลำดับของตารางเชิงเส้นหมายถึงการจัดเก็บองค์ประกอบข้อมูลของตารางเชิงเส้นลงในชุดหน่วยเก็บข้อมูลต่อเนื่องที่มีที่อยู่ในลำดับตรรกะของพวกเขา ตารางเชิงเส้นที่เก็บไว้ในวิธีนี้เรียกว่าตารางลำดับ
1. คำจำกัดความโครงสร้างของตารางการสั่งซื้อ
คลาสสาธารณะ seqlist { / * พื้นที่เริ่มต้นคือ 10 * / ส่วนตัวคงที่ int สุดท้าย list_size = 10; /* ข้อมูลอาร์เรย์ใช้เพื่อจัดเก็บองค์ประกอบ*/ ข้อมูลส่วนตัว int []; /* ตารางปัจจุบันมีความยาวจำนวนองค์ประกอบจริงที่เก็บไว้*/ ความยาว int ส่วนตัว; - 2. แทรกการทำงาน
การดำเนินการแทรกของตารางต่อเนื่องหมายถึงการแทรกองค์ประกอบใหม่ระหว่างองค์ประกอบ I-1 และองค์ประกอบ I-TH ของตารางเชิงเส้น เนื่องจากองค์ประกอบที่อยู่ติดกันของตารางลำดับยังอยู่ติดกันในโครงสร้างทางกายภาพความสัมพันธ์การจัดเก็บข้อมูลทางกายภาพของพวกเขาจะต้องได้รับการเปลี่ยนแปลงที่สอดคล้องกัน เว้นแต่ i = n+1 องค์ประกอบทั้งหมดเริ่มต้นจากองค์ประกอบ i-th ของตารางคำสั่งซื้อดั้งเดิมจะต้องถูกเลื่อนไปข้างหลังโดย 1 ตำแหน่งตามลำดับ
/** * แทรกองค์ประกอบใหม่ก่อนตำแหน่ง i-th ในรายการตารางลำดับโหนด * @param รายการคำสั่งซื้อ * @param ฉันแทรกตำแหน่ง * @param โหนดองค์ประกอบใหม่ */โมฆะสาธารณะแทรกรายการ (รายการ seqlist, int i, int node) {ถ้า (i <1 || i> list.length + 1) กลับ; } if (list.length> = list_size) {system.out.println ("overflow"); กลับ; } สำหรับ (int j = list.length - 1; j> = i - 1; j -) { / * เริ่มจากองค์ประกอบสุดท้ายและย้ายกลับทีละหนึ่ง * / list.data [j+1] = list.data [j]; } /* แทรกองค์ประกอบใหม่* / list.data [i-1] = โหนด; / * เพิ่ม 1 ไปที่ความยาวตาราง */ list.length ++; - 3. ลบการดำเนินการ
การดำเนินการลบของตารางต่อเนื่องหมายถึงการลบองค์ประกอบ I-th ในตาราง ตรงกันข้ามกับการดำเนินการแทรกการแทรกกำลังเคลื่อนย้ายองค์ประกอบไปข้างหลังและการดำเนินการลบกำลังเลื่อนองค์ประกอบไปข้างหน้า
/*** ลบองค์ประกอบ i-th ในรายการตารางคำสั่งซื้อและส่งคืนองค์ประกอบที่ถูกลบ* @param รายการลำดับตาราง* @param i ตำแหน่งองค์ประกอบ* @return Node*/public int deletelist (รายการ seqlist, int i) {int node = 0; if (i <0 || i> list.length) {system.out.println ("ข้อผิดพลาดตำแหน่ง"); ส่งคืนโหนด; } node = list.data [I-1]; สำหรับ (int j = i; j <list.length; j ++) { /* องค์ประกอบส่งต่อ* / list.data [j-1] = list.data [j]; } list.length -; ส่งคืนโหนด;} 4. ตารางคำสั่งซื้อผกผัน
ขั้นแรกให้ใช้ครึ่งหนึ่งของความยาวของตารางเป็นจำนวนการควบคุมวนซ้ำเวลาแลกเปลี่ยนองค์ประกอบสุดท้ายในตารางตามลำดับขององค์ประกอบแรกแลกเปลี่ยนองค์ประกอบสุดท้ายที่สองในลำดับขององค์ประกอบที่สองและอื่น ๆ จนกว่าการแลกเปลี่ยนจะเสร็จสิ้น
/*** ตารางลำดับผกผัน* @param รายการคำสั่งซื้อดั้งเดิม* @return ตารางลำดับหลังจากผกผัน*/public seqlist แปลง (รายการ seqlist) {int node; ความยาว int = list.length/2; สำหรับ (int i = 0; i <length; i ++) { /* องค์ประกอบการแลกเปลี่ยนสมมาตร* / int j = list.length - 1 - i; node = list.data [i]; list.data [i] = list.data [j]; list.data [j] = โหนด; } return list; - 2. การจัดเก็บโซ่และอัลกอริทึมของตารางเชิงเส้น
พื้นที่จัดเก็บข้อมูลขององค์ประกอบข้อมูลของโครงสร้างการจัดเก็บโซ่ที่เก็บตารางเชิงเส้นอาจต่อเนื่องหรือไม่ต่อเนื่องดังนั้นโหนดของรายการที่เชื่อมโยงไม่สามารถเข้าถึงได้แบบสุ่ม การจัดเก็บโซ่เป็นหนึ่งในวิธีการจัดเก็บที่พบบ่อยที่สุด
เมื่อใช้โครงสร้างการจัดเก็บโซ่เพื่อแสดงองค์ประกอบข้อมูลแต่ละรายการนอกเหนือจากการจัดเก็บข้อมูลขององค์ประกอบเองแล้วยังจำเป็นต้องมีที่อยู่ที่อยู่ในการจัดเก็บขององค์ประกอบที่ตามมา ตารางเชิงเส้นที่แสดงโดยวิธีการจัดเก็บนี้เรียกว่ารายการที่เชื่อมโยง
5. คำจำกัดความโครงสร้างของรายการที่เชื่อมโยงเดียว
LinkList คลาสสาธารณะ { /* ฟิลด์ข้อมูล* / ข้อมูลถ่านส่วนตัว; /* องค์ประกอบต่อเนื่อง*/ private linklist ถัดไป;} 6. อัลกอริทึมการสร้างตาราง
วิธีการแทรกส่วนหัวเริ่มต้นด้วยตารางที่ว่างเปล่าอ่านข้อมูลซ้ำ ๆ สร้างโหนดใหม่จัดเก็บข้อมูลการอ่านในฟิลด์ข้อมูลของโหนดใหม่จากนั้นแทรกโหนดใหม่บนส่วนหัวของรายการที่เชื่อมโยงปัจจุบันจนกว่าจะสิ้นสุด
/*** สร้างตารางโดยการแทรกส่วนหัว* @param chars array array* @return รายการที่เชื่อมโยงเดียว*/public linklist createListf (char [] chars) {linklist node; linklist head = null; สำหรับ (char ch: chars) { /* สมัครสำหรับโหนดใหม่* / node = new LinkList (); node.data = ch; /* ชี้ไปที่โหนดผู้สืบทอด*/ node.next = head; head = node; } /* กลับไปที่หัวโหนด* / return head;} 7. วิธีการแทรกหางอัลกอริทึมการสร้างตาราง
ลำดับของโหนดในตารางการแทรกส่วนหัวนั้นตรงกันข้ามกับคำสั่งซื้อเมื่ออินพุต หากลำดับของอินพุตสอดคล้องกันสามารถใช้วิธีการแทรกหาง
/*** วิธีการแทรกหางเพื่อสร้างตาราง* @param chars array array* @return รายการที่เชื่อมโยงเดียว*/public linklist createListrent (char [] chars) {linklist node; linklist head = null; linklist ด้านหลัง = null; สำหรับ (char ch: chars) {node = new LinkList (); node.data = ch; if (head == null) { /* โหนดใหม่คือโหนดหัว* / head = node; } else { /* โหนดก่อนหน้าชี้ไปที่โหนดใหม่* / hear.next = node; } /* หางของตารางชี้ไปที่โหนดใหม่* / hear = node; } /* กลับไปที่หัวโหนด* / return head;}ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น