แนะนำตารางเชิงเส้นสั้น ๆ และวิธีการบรรลุตารางโซ่คู่

Linear Meter เป็นโครงสร้างเชิงเส้นซึ่งเป็นลำดับที่ จำกัด ซึ่งมีองค์ประกอบข้อมูลประเภท N (N ≥ 0) เดียวกัน

1. อาร์เรย์
อาร์เรย์มีขอบเขตบนและล่างและองค์ประกอบของอาร์เรย์จะต่อเนื่องในขอบเขตบนและล่าง

แผนผังแผนภาพของอาร์เรย์ 10,20,30, 40, 50 50 มีดังนี้:

คุณสมบัติของอาร์เรย์ : ข้อมูลอย่างต่อเนื่อง
อาร์เรย์ที่ซับซ้อนกว่าเล็กน้อยคืออาร์เรย์หลายมิติและอาร์เรย์แบบไดนามิก สำหรับภาษา C อาร์เรย์หลายมิติจะรับรู้ผ่านอาร์เรย์หนึ่งมิติ สำหรับอาร์เรย์แบบไดนามิกมันเป็นอาร์เรย์ของความสามารถของกลุ่มดัชนีที่สามารถเติบโตได้ เวกเตอร์; สำหรับ Java คอลเลกชันนั้นเกี่ยวข้อง

ประการที่สองรายการที่เชื่อมโยงหนึ่งรายการ <br /> รายการที่เชื่อมโยงหนึ่งทาง (รายการที่เชื่อมโยงเดียว) เป็นประเภทของรายการที่เชื่อมโยง

แผนผังไดอะแกรมของรายการที่เชื่อมโยงเดียวมีดังนี้:

หัวหัวว่างเปล่าโหนดผู้สืบทอดของหัวคือ "โหนด 10" (โหนดของข้อมูล 10) และโหนดผู้สืบทอดของ "โหนด 10" คือ "โหนด 20" (ข้อมูลที่มีข้อมูล 10) ..

โหนดลบโซ่เดี่ยว

ลบ "โหนด 30"
ก่อนลบ: โหนดผู้สืบทอดของ "Node 20" คือ "Node 30" และโหนดผู้สืบทอดของ "Node 30" คือ "Node 40"
หลังจากลบ: โหนดผู้สืบทอดของ "โหนด 20" คือ "โหนด 40"

รายการที่เชื่อมโยงเดียวเพิ่มโหนด

เพิ่ม "Node 15" ระหว่าง "Node 10" และ "Node 20"
ก่อนที่จะเพิ่ม: โหนดผู้สืบทอดของ "Node 10" คือ "Node 20"
หลังจากเพิ่ม: โหนดผู้สืบทอดของ "Node 10" คือ "Node 15" และโหนดผู้สืบทอดของ "Node 15" คือ "Node 20"

คุณลักษณะของรายการที่เชื่อมโยงเดียวคือทิศทางการเชื่อมโยงของโหนดคือหนึ่งทาง;

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

แผนผังไดอะแกรมของรายการคู่ที่เชื่อมโยงมีดังนี้:

ส่วนหัวว่างเปล่าโหนดผู้สืบทอดของหัวคือ "โหนด 10" (โหนดของข้อมูล 10); โหนดผู้สืบทอดของ "โหนด 10" คือ "โหนด 20" (ข้อมูล 10 โหนด), "โหนด 20" ผู้สืบทอดโหนดคือ "Node 10"; .

นาฬิกาโซ่คู่ลบโหนด

ลบ "โหนด 30"
ก่อนลบ: โหนดผู้สืบทอดของ "Node 20" คือ "Node 30" และ pre -node ของ "Node 30" คือ "Node 20" โหนดผู้สืบทอดของ "Node 30" คือ "Node 40" และ pre -node ของ "Node 40" คือ "Node 30"
หลังจากการลบ: โหนดผู้สืบทอดของ "Node 20" คือ "Node 40" และ pre -node ของ "Node 40" คือ "Node 20"

รายการลิงค์คู่เพิ่มโหนด

เพิ่ม "Node 15" ระหว่าง "Node 10" และ "Node 20"
ก่อนที่จะเพิ่ม: โหนดผู้สืบทอดของ "Node 10" คือ "Node 20" และโหนดก่อนหน้าของ "Node 20" คือ "Node 10"
หลังจากเพิ่ม: โหนดผู้สืบทอดของ "Node 10" คือ "Node 15" และ pre -node ของ "Node 15" คือ "Node 10" โหนดผู้สืบทอดของ "Node 15" คือ "Node 20" และโหนดก่อนหน้าของ "Node 20" คือ "Node 15"

การใช้งานรายการโซ่คู่มีการแนะนำด้านล่างและมีการใช้งานสามอย่างของ C/C ++/Java ตามลำดับ

1. C ใช้รายการที่เชื่อมโยงคู่

ใช้ไฟล์รายการสองรายการที่เชื่อมโยงสองทาง (double_link.h)

 #ifndef_double_link_h#define_double_link_h // สร้าง "สองรายการที่เชื่อมโยงกัน" ความสำเร็จกลับไปที่หัว; ความสำเร็จกลับมา 0; กลับไปที่ 1 สำหรับความว่างเปล่า; extern int dlink_is_empty (); ความสำเร็จกลับไปที่ตัวชี้โหนด; ช่องว่างภายนอก* dlink_get (ดัชนี int); // รับ "องค์ประกอบแรกในรายการที่เชื่อมโยงสองทาง" ความสำเร็จกลับไปที่ตัวชี้โหนด; ช่องว่างภายนอก* dlink_get_first (); ความสำเร็จกลับไปที่ตัวชี้โหนด; โมฆะภายนอก* dlink_get_last (); // แทรก "ค่า" ลงในตำแหน่งดัชนี ความสำเร็จกลับมา 0; extern int dlink_insert (ดัชนี int, void *pval); // แทรก "ค่า" ลงในตำแหน่งหัว ความสำเร็จกลับมา 0; extern int dlink_insert_first (void *pval); ความสำเร็จกลับมา 0; extern int dlink_append_last (เป็นโมฆะ *pval); // ลบ "โหนดในตำแหน่งดัชนีในสองรายการที่เชื่อมโยงกัน" ความสำเร็จกลับมา 0; ความสำเร็จกลับมา 0; ความสำเร็จกลับ 0;

double_link.c ในรายการที่เชื่อมโยงสองทาง

 #include <stdio.h> #include <malloc.h>/*** รายการสองรายการที่เชื่อมโยงสองทางของ Lingle สามารถจัดเก็บข้อมูลโดยพลการ ** @author Skywang* @วันที่ 2013/11/07*/// สองรายการที่เชื่อมโยงกับโหนด typedef struct tag_node {stroct tag_node*prev; โปรดทราบว่าค่าของหัวไม่เก็บค่าองค์ประกอบ! จุดตัด จุดตัด โหนดคงที่ *phead = null; จำนวน int คงที่ = 0; // สร้าง "โหนด" ใหม่ ความสำเร็จกลับไปที่ตัวชี้โหนด; โหนดคงที่ *create_node (เป็นโมฆะ *pval) {node *pnode = null; "); return null;} // ค่าเริ่มต้นโหนดแรกและโหนดหลังของจุด pnode ไปยัง pnode-> prev = pnode-> next = pnode; // ค่าของโหนดคือ pvalpnode-> p = p = pval; / สร้าง "สองรายการที่เชื่อมโยงกัน" ความสำเร็จกลับมา 0; int create_dlink () {// สร้างส่วนหัว phead = create_node (null); กลับมานับ == 0;} // กลับไปที่ "รายการสองรายการที่เชื่อมโยงสองรายการ" int dlink_size () {นับคืน;} // รับ "โหนดในตำแหน่งดัชนีในสองรายการที่เชื่อมโยง" โหนดคงที่* get_ get_ Node (Node (INT ดัชนี) {IFX <0 || index> = count) {printf ("%s ล้มเหลว! ดัชนีออกจากขอบเขต!/n", __func __); ถ้า (ดัชนี <= (นับ/2)) {int i = 0; ค้นหา int j = 0; โหนด "โหนดคงที่ * g et_first_node () () ส่งคืน get_node (0);} // รับโหนด" โหนดสุดท้าย "คงที่ * get_last_node () {return get_node (count-); ในรายการที่เชื่อมโยงสองทาง " ความสำเร็จ, ส่งคืนค่าโหนด; เป็นโมฆะ * dlink_get (INT ดัชนี) {Node * Pindex = get_node (ดัชนี); 1 个元素的值” โมฆะ* dlink_get_first () {return dlink_get (0);} // 获取“ 双向链表中最后 1 个元素的值” โมฆะ* dlink_get_last () {return dlink_get (นับ- 1);} // แทรก "pval" ลงในตำแหน่งดัชนี ความสำเร็จกลับมา 0; int dlink_insert (ดัชนี int, void * pval) {// แทรกส่วนหัวถ้า (index == 0) ส่งคืน dlink_insert_first (pvalt (pval); // รับโหนดโหนดที่สอดคล้องกับตำแหน่งที่จะแทรก; if! pindex) return -1; // 创建“ 节点” โหนด *pnode = create_node (pval); if (! pnode) return -1; pnode-> prev = pindex-> ​​prev; pnode-> next = pindex; pindex; -> prev-> next = pnode; {Node *Pnod e = create_node (pval); ++; pnode-> prev = phead-> prev; รายการที่เชื่อมโยง " ความสำเร็จกลับมา 0; int dlink_delete (int index) {node *pindex = get_node (ดัชนี); > next-> prev = pindex-> ​​prev; pindex-> ​​prev-> next = pindex-> ​​next; ฟรี (pindex); count-; return 0;} // 删除第一个节点 int dlink_delete_first () {return dlink_delete (0);} // ลบโหนด int int dlink_delete_last () {return dlink_delete (count-);} // revisit "รายการที่เชื่อมโยงสองทาง" ความสำเร็จกลับมา 0; int destion_dlink () {ถ้า (! phead) {printf ("%s ล้มเหลว! dlink เป็น null!/n", __func __); ในขณะที่ (pnode! = phead) {ptmp = pnode;

โปรแกรมทดสอบรายการที่เชื่อมโยงสองทาง (dlink_test.c)

 #include <stdio.h> #include "double_link.h"/*** C ภาษาเพื่อใช้โปรแกรมทดสอบรายการที่เชื่อมโยงสองทาง ** (01) int_test ()* สาธิต "int data" ในรายการที่เชื่อมโยงสองทาง * (02) string_teest ()* สาธิต "ข้อมูล strine" ในรายการที่เชื่อมโยงสองทาง * (03) Object_teest ()* แสดง "วัตถุ" ในรายการที่เชื่อมโยงสองทาง ** @author Skywang* @date 2013/11/07* /// การดำเนินการรายการที่เชื่อมโยงสองทาง int ข้อมูลเป็นโมฆะ int_teest () {int iarr [4] = {10, 20, 30, 40}; n ------%s ------ ", __func __); create_dlink (); // สร้างรายการสองทางที่เชื่อมโยง dlink_insert (0, & iarr [0]); // แทรก data dlink_insert (0, & & ig & ig & & ig & & & & 1]); data printf ("dlink_is_empty () =%d/n", dlink_is_empty ()); ขนาดของรายการที่เชื่อมโยงสองทางของรายการที่เชื่อมโยงสองทาง int i; ) dlink_get (i); ยี่สิบ "," สามสิบ "," fringf ("/n ----%s ----%s--/n", __func __); 0, Sarr [0]); สองรายการที่เชื่อมโยงกัน; n ", dlink_size ()); // ขนาดของรายการที่เชื่อมโยงสองทาง // พิมพ์ข้อมูลทั้งหมด int i ในรายการที่เชื่อมโยงสองทาง; char *p; int sz = dlink_size (); สำหรับ (i = 0; i <sz; tag_stu {int id; {40, {40, {40, {40, "Dan"},};#define arr_stu_size ", __func __); create_dlink (); // สร้างรายการสองรายการที่เชื่อมโยง DLINK_INSERT (0, & arr_stu [0] ); "dlink_is_empty () =%d/n", dlink_is_empl ()); สองรายการที่เชื่อมโยงกัน // ข้อมูลทั้งหมดในสองรายการที่เชื่อมโยงกัน int i; ) dlink_get (i); ); // แสดงให้เห็นว่า "ข้อมูล int" ในรายการที่เชื่อมโยงสองทาง String_test (); Object_test (); กลับ 0;}

ผลการทำงาน

 ---- int_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = thirtydlink_get -Object_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = [30, vic] dlink_get (1) = [20, jody] dlink_get (2) = [10, Sky]

2. C ++ ตระหนักถึงรายการโซ่คู่

ใช้รหัสสองไฟล์ที่เชื่อมโยงทางเวย์ (doublelink.h)

 #ifndef double_link_hxx#define double_link_hxx#รวมถึง <iostream> การใช้ namespace std; ก่อนหน้านี้ dnode *ถัดไป) {this-> value = t; ขนาด (); int delete_last (); ) {// สร้าง "ความเร็ว" หมายเหตุ: ไม่มีข้อมูลการจัดเก็บบนหัว! phead = new dnode <t> (); >: ~ DoughLink () {// ลบโหนดทั้งหมด dnode <t>* ptmp; ; ลบ ptmp;} // ลบ "หัว" ลบ phead; รายการโซ่为空เทมเพลต <คลาส T> int doublelink <t> :: is_empty () {count return == 0;} // 获取第ดัชนี位置的节点เทมเพลต <คลาส T> dnode <t>* doublelink <t>: : get_node (INT ดัชนี) {// ความถูกต้องของพารามิเตอร์การตัดสินถ้า (ดัชนี <0 || ดัชนี> = นับ) {cout << "รับโหนดล้มเหลว! ดัชนีอยู่ในขอบเขต!" / การค้นหาถ้า (ดัชนี <= count/ 2) {int i = 0; ;} / / ย้อนกลับการค้นหา int j = 0; ; Temple <class t> trivelink <t> :: get_first () {return get_node (0)-> value;} // รับค่าของโหนดสุดท้าย ตำแหน่งดัชนีก่อนเทมเพลต <คลาส T> int doublelink <t> :: แทรก (int index, t t) {ifx == 0) return insert_first (t) ;; > ก่อนหน้านี้); เทมเพลต <class t> int doublelink <t> :: insert_fring (t) {dnode <t>* pnode = ใหม่ dnode <t> (t, phead-> ถัดไป); > next = pnode; > prev = pnode; > next-> prev = pindex-> ​​prev; t> int doublelink <t> :: delete_first () {return del (0);} // 删除最后一个节点เทมเพลต <class t> int doublelink <t> :: delete_last () {return del (count-);}; #endif

ไฟล์ทดสอบรายการสองรายการที่เชื่อมโยงกัน (dlinktest.cpp)

 #include <Iostream> #include "doublelink.h" userspace std; --- "<< endl; // สร้างรายการที่เชื่อมโยงสองทาง doublelink <int>* pdlink = ใหม่ doublelink <int> (); pdlink-> แทรก (0, 20); // แทรก 20 ลงในตำแหน่งแรก pdlink-> append_last (10); << "is_empty () =" << pdlink-> is_empty () << endl; << endl; ข้อมูลทั้งหมด int sz = pdlink-> size (); -> get (i) << endl;} void string_test () {string sarr [4] = {"สิบ", "ยี่สิบ", "สามสิบ", "สี่สิบ"}; ---- "" << endl; องค์ประกอบที่สองใน SARR เข้าสู่ PDLink-> append_last (SARR [0]); ); ตำแหน่ง // ไม่ว่ารายการที่เชื่อมโยงสองทางจะว่างเปล่า << "is_empty () =" << pdlink-> is_empty () << endl; () = "<< pdlink-> size () << endl; // ข้อมูลทั้งหมด int sz = pdlink-> size (); สำหรับ (int i = 0; i <sz; i ++)" <") = "<< pdlink-> get (i) << endl;} struct stu {int id; ชื่อถ่าน [20];}; Stu arr_stu แบบคงที่ [] = {10," Sky "}, {20 20," โจดี้ " "}, {30," vic "}, {40," dan "},};#define arr_stu_size cout <<"/n ---- object_test ---- "<< endl; // สร้างสอง- รายการที่เชื่อมโยง doublelink <stu>* pdlink = ใหม่ doublelink <stu> (); > append_last (arr_stu [0]); ไปยังตำแหน่งแรก // ว่ารายการที่เชื่อมโยงสองทางนั้นว่างเปล่า << "is_empty () =" << pdlink-> is_empty () << endl; = "<< pdlink-> size () << endl; // พิมพ์ข้อมูลทั้งหมด int sz = pdlink-> size () ในรายการที่เชื่อมโยงสองทาง; = 0; i <sz; i ++) {p = pdlink-> get (i); Main () {int_teest (); String_test (); Object_test (); กลับ 0;}

ตัวอย่างคำอธิบาย

ในตัวอย่างข้างต้นฉันใส่ "คำสั่ง" และ "การใช้งาน" ของรายการที่เชื่อมโยงทั้งสองทางในไฟล์ส่วนหัว ข้อกำหนดการเขียนโปรแกรมเตือนเรา: แยกการประกาศและการดำเนินการของการเรียกร้องและจำนวนไฟล์ส่วนหัว (ไฟล์. h หรือ. hpp) มีเพียงคำสั่งและรับผิดชอบการใช้งานในไฟล์การใช้งาน (ไฟล์. cpp)!
แล้วทำไมคุณถึงทำเช่นนี้? นี่เป็นเพราะในการใช้งานรายการที่เชื่อมโยงสองทางเทมเพลตจะถูกนำมาใช้ หากต้องการพูดง่ายๆหากมีการประกาศใน doublelink.h และนำไปใช้ใน doublelink.cpp; เมื่อเราสร้างวัตถุของ doublelink ในหมวดหมู่อื่น ๆ ข้อผิดพลาดจะถูกรวบรวม ด้วยเหตุผลเฉพาะคุณสามารถอ้างถึง "ทำไมคอมไพเลอร์ C ++ ไม่สามารถรองรับการรวบรวมเทมเพลตแยกต่างหาก"

ผลการทำงาน

 ---- int_test ---- is_empty () = 0Size () = 3PDLink (0) = 30PDLink (1) = 20PDLink (2) = 10 ---- string_test ----- ว่างเปล่า () = 0Size () = 3PDLink (0) = ThirTypDlink (1) = TwentypDlink (2) = Ten ---- Object_teest ---- is_empty () = 0Size () = 3PDLink (0) = [30, VIC] PDLink (1) = [ 20 20, Jody] PDLink (2) = [10, Sky]

3. Java ตระหนักถึงรายการโซ่คู่

การใช้งาน doublelink.java

 /*** รายการที่เชื่อมโยงสองทางของ Java * หมายเหตุ: มีรายการที่เชื่อมโยงสองทางในแพ็คเกจคอลเลกชันของ Java / top headpate dnode <t> mhead; {this.value = value; หมายเหตุ: ไม่มีข้อมูลการจัดเก็บบนหัว! mhead = new dnode <t> (null, null, null); ส่งคืน mcount;} // ว่ารายการที่เชื่อมโยงนั้นเป็นบูลีนที่ว่างเปล่า isempty () {return mcount == 0;} // โหนดส่วนตัว dnode <t> getNode (INT ดัชนี) {IFX) {ดัชนี <0 || ดัชนี> = Mcount) โยน indexoutofboundsexception ใหม่ (); ;} // 反向查找 dnode <t> rnode = mhead.prev; int rindex = mcount - index -1; สำหรับ (int j = 0; j <rindex; j ++) rnode = rnode / รับค่าของโหนดของตำแหน่งดัชนี <t> (t, mhead, mhead.next); t> (t, inode.prev, inode); โมฆะสาธารณะ INSERTFIRST (T T) {INSERT (0, T);} // เพิ่มโหนดไปที่จุดสิ้นสุดของรายการที่เชื่อมโยงของโมฆะสาธารณะภาคผนวก (t T) {DNODE <T> ใหม่ DNODE <T> (t, Mhead Prev Mhead); mhead.prev.next = node; .next = inode.next; โหนดโมฆะสาธารณะ deletElast () {del (mcount-);}}

โปรแกรมทดสอบ (dlinktest.java)

 /*** รายการที่เชื่อมโยงสองทางของ Java * หมายเหตุ: มีรายการที่เชื่อมโยงสองทางในแพ็คเกจคอลเลกชันที่มาพร้อมกับ Java การทำงานของตารางที่เชื่อมโยงสองครั้งข้อมูลเป็นโมฆะแบบคงที่ INT_TEEST () {int [] {10, 20, 30, 40}; = ใหม่ doublelink <integer> (); ตำแหน่งแรก // ไม่ว่ารายการที่เชื่อมโยงสองทางจะเป็นระบบที่ว่างเปล่า out.printf ("isempty () =%b/n", dlink.isempty ()); d/n ", dlink.size ()); // พิมพ์โหนดทั้งหมดสำหรับ (int i = 0; i <dlink.size (); i ++) system.out .println (" dlink ("+i+") = "+dlink.get (i));} โมฆะคงที่ string_test () {string [] sarr = {" สิบ "," ยี่สิบ "," สามสิบ "," สี่สิบ ""}; /n ---- string_test ---- "); // สร้างรายการสองทางที่เชื่อมโยงสองทาง doublelink <string> dlink = ใหม่ doublelink <string> (); [1]); // แทรกองค์ประกอบที่สองใน sarr ในตำแหน่งแรก dlink.appendlast (sarr [0]); ตำแหน่งแรก // ไม่ว่ารายการที่เชื่อมโยงสองทางนั้นจะเป็น System.out.out.printf ("isempty () =%b/ n", dlink.isempty ());// system.out.printf ("ขนาด () =%d/ n ", dlink.size ()); // พิมพ์โหนดทั้งหมดสำหรับ (int i = 0; i <dlink.size (); i ++) system.out.println (" dlink ("+i+ ") ="+dlink.get (i));} // นักเรียนชั้นเรียนภายในชั้นเรียนภายในชั้นเรียน {นักเรียน id id ส่วนตัว (int id, ชื่อสตริง) {this.id = id; ouverridepublic String toString () {"+id+", "+name+"] ";} tudent [] studers = นักเรียนใหม่ [] {นักเรียนใหม่ (10," Sky "), นักเรียนใหม่ (20," Jody "), ใหม่ นักเรียน (30, "Vic"), นักเรียนใหม่ (40, "Dan"),}; รายการที่เชื่อมโยงสองทาง Doublerink <student> dlink = ใหม่ doublelink <student> (); องค์ประกอบแรกในนักเรียนถึง dlink.insertfirst (นักเรียน [นักเรียน [นักเรียน [นักเรียน [2]); printf ("isempty () =%b/n", dlink.isempty ()); โหนดสำหรับ (int i = 0; i <dlink.size ()); โมฆะคงที่หลัก (String [] ศิลปะ) {int_test (); String_test (); Object_test (); -

ผลการทำงาน

 ---- int_test ---- isempty () = falsesize () = 3dlink (0) = 30dlink (1) = 20dlink (2) = 10 ---- string_test ——-- isempty () = falsesize () = = 3Dlink (0) = ThirtyDlink (1) = TwentyDlink (2) = Ten ---- Object_teest --- isempty () = falsesize () = 3Dlink (0) = [30, vic] dlink (1) = [20 20 20 20 20 , Jody] Dlink (2) = [10, Sky]

ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้