โครงสร้างข้อมูลแบบลิงค์ลิสต์ (linklist)
Download as ppt, pdf4 likes6,972 views
วิชาโครงสร้างྺ้อมูล
โครงสร้างข้อมูลแบบลิงค์ลิสต์ (linklist)
- 1. โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked List) โครงสร้างข้อมูล (Data Structure)
- 2. โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked List) ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกัน ไปตามลำาดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้ ซึ่ง ในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็น พอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยัง โหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วน
- 3. โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked List) Linke d list คล้ายๆ กับขบวนรถไฟ ตรงที่ว่าการที่จะเกิด เป็นขบวนรถไฟได้จะต้องมีการนำาโบกี้รถไฟหลายๆ โบกี้มาต่อกัน ขบวนจะสั้นหรือยาวก็ขึ้นอยู่กับโบกี้ เหล่านี้ หากผู้โดยสารโบกี้แรกๆ ต้องการที่จะไปยัง โบกี้สุดท้ายก็ต้องเดินผ่านโบกี้อื่นๆ ระหว่างทางด้วย
- 4. โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked List) โหนด (Node) โครงสร้างแบบ Linked list แบ่งได้หลายแบบตามวิธีการชี้ ไปยังโหนดต่างๆ เช่น Singly Linked list , Doubly Linked list , Multi-Linked list Singly Linked list Singly Linked list จะประกอบด้วยโหนดที่มีพอยน์เตอร์ชี้ ไปในทิศทางเดียว คือชี้ไปยังโหนดถัดไป
- 5. โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked List) Doubly Linked list Doubly linked list ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนด ถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึง สามารถทำาการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไป ข้างหน้า และอ่านไปทางข้างหลัง
- 6. การทำางานของลิสต์ การสร้างลิสต์ว่าง การทดสอบว่าลิสต์ว่างหรือไม่ การเพิ่มสมาชิกใหม่ลงในลิสต์ การลบสมาชิกออกจากลิสต์ การท่องไปในลิสต์หรือส่วนของลิสต์ โดยการเข้าถึง สมาชิก และประมวลผลสมาชิกแบบลำาดับ
- 7. การสร้างรายการว่าง typedef struct listnode{ // create list node type int value; struct listnode *next; } LISTNODE; LISTNODE *numlist=NULL; numlist =(LISTNODE *)malloc(sizeof(LISTNODE)); numlist
- 8. ทดสอบว่ารายการว่างหรือไม่ // return 1 if list is empty, else return 0. int islempty(LISTNODE *head) { return (head == NULL); } numlist = NULL
- 9. การเพิ่มสมาชิกใหม่ลงในรายการ Insert first element Insert element on head of list Insert element between list Insert element on end of list
- 10. Insert first element numlist = getnode(); // head of list numlist->value = 23; numlist->next = NULL; numlist 23 NULL
- 11. Insert element on head of list NEW = getnode(); // head of list NEW->value = 20; NEW->next = numlist; NEW 20 numlist 23 NULL numlist = NEW;
- 12. Insert element between list NEW = getnode(); NEW->value = 24; NEW->next = numlist->next ; numlist 23 numlist->next = NEW; 25 NULL NEW 24
- 13. Insert element on end of list NEW = getnode(); NEW->value = 25; NEW->next = NULL; NEW 25 numlist 23 NULL numlist->next = NEW; NULL
- 14. การลบสมาชิกออกจากรายการ delete element on head of list delete element between list delete element on end of list
- 15. delete element on head of list if( numlist->value == 23 ){ // test value of head node backup = numlist; // backup head node numlist = numlist->next; // move head to next node 23 free(backup); // free backup node } 25 NULL 24backup
- 16. delete element between list ptr = ptr->next; // move ptr to next node if( (ptr->next)->value == 24 ){ // test value of next node backup = ptr->next; // backup next node ptr->next = (ptr->next)->next; // point next node to skip 1 node 23 free(backup); // free backup node } 25 NULL 24 backup
- 17. delete element on end of list while(ptr->next!=NULL){ ptr = ptr->next; // move ptr to next node if( (ptr->next)->value == 25 ){ // test value of next node backup = ptr->next; // backup next node ptr->next = (ptr->next)->next; // point next node to skip 1 node 23 free(backup); // free backup node break; } } 25 NULL 24 ptr backup
- 18. การเข้าถึงสมาชิกของรายการ void printlst(LISTNODE *numlist) { LISTNODE *ptr=numlist; while(ptr!=NULL){ printf("%3d",ptr->value); ptr = ptr->next; // next node } } 23 25 NULL 24 ptr numlist