2 พาร์ตที่ไปคู่กันเสมอ — เขียนโค้ด C ให้ได้ กับ วาดภาพให้ได้ว่าแต่ละ statement เกิดอะไรขึ้น · ทุกอย่างในหน้านี้เดินทีละบรรทัดแล้วภาพขยับตาม
สไลด์เปิดมาด้วยคำถามนี้ — ตอบให้ได้ว่า array มีปัญหาอะไร
Base + i×eSize (หน่วยที่ 3) — แต่ Linked List ทำแบบนั้นไม่ได้ ต้องไล่จากหัวทีละ node เพราะแต่ละ node อยู่คนละที่ในหน่วยความจำ · ได้ความยืดหยุ่น แต่เสียการเข้าถึงแบบสุ่ม + เปลืองที่เก็บ pointer เพิ่มทุก nodeถ้าตรงนี้ไม่ชัด พาร์ตวาดภาพจะพังทั้งหมด
// Type DECLARATIONS
struct node{
int data; // ช่องข้อมูล (data section)
struct node *next; // ช่องลูกศร (link section)
};
typedef struct node nodePtr;
nodePtr *ptr;
data = ค่าที่เก็บ · next = ที่อยู่ของ node ถัดไปnext ไม่ได้เก็บ node — เก็บแค่ เลขที่อยู่ ของ node นั้นnext = NULL เสมอ — คือป้ายบอกว่า "จบแล้ว"| เขียน | หมายถึง |
|---|---|
ptr | ที่อยู่ ของ node (ตัวชี้) |
*ptr | ทั้ง node ที่ ptr ชี้อยู่ |
ptr->data(*ptr).data | ช่อง data ในnode นั้น (2 อันนี้เหมือนกันเป๊ะ) |
ptr->next | ช่อง next = ที่อยู่ของ node ถัดไป |
ptr->next->data | ช่อง data ของ node ถัดไป |
-> ว่า "เดินไปที่ node นั้น แล้วเปิดช่อง…"ท่ามาตรฐานจากสไลด์ — malloc → ใส่ data → ตั้ง next = NULL → ค่อยลิงก์
current = (struct node *)malloc(sizeof(struct node)); // 1. ขอที่ในหน่วยความจำ current->data = i; // 2. ใส่ข้อมูล current->next = NULL; // 3. ปิดท้ายด้วย NULL เสมอ
malloc คืนค่าเป็นที่อยู่ของก้อนใหม่ — ถ้าไม่เก็บใส่ตัวแปรไว้ = หาไม่เจออีกเลย (memory leak)ลูปนี้โผล่ในทุกฟังก์ชัน (แสดงผล / ค้นหา / หาท้ายลิสต์) — จำโครงให้ได้
ptr = head; // เริ่มที่หัวเสมอ ห้ามใช้ head เดินเอง!
while (ptr != NULL) {
printf("%d\n", ptr->data);
ptr = ptr->next; // ก้าวไปตัวถัดไป
}
head เดินเอง — เดินเสร็จ head จะกลายเป็น NULL แล้วหาลิสต์ไม่เจออีกเลย ต้องใช้ตัวชี้ชั่วคราวptr != NULL = "ยังไม่หมดลิสต์" · ถ้าเขียน ptr->next != NULL จะหยุดที่ตัวสุดท้าย (ใช้ตอนอยากได้ท้ายลิสต์)จากไฟล์ lab ของ Beer เอง (Lab4-2-1 test 3.c case 2) — ต้องทำได้ทั้ง 3 เคส
current->next = ptr->next; ← ให้ node ใหม่จับตัวถัดไปไว้ก่อนptr->next = current; ← แล้วค่อยให้ตัวหน้าชี้มาที่ node ใหม่ptr->next ถูกทับก่อน = ส่วนหางหลุดหายทั้งก้อน หาไม่เจออีกเลยnext = NULL อยู่แล้ว เลยเขียน ptr->next = current; ตรงๆ ได้เลย ไม่ต้องเก็บปลายทางไว้ก่อน
ptr = NULL;ptr กับ current ไม่มีหน้าที่แล้ว แต่ยังค้างชี้กลางลิสต์อยู่ — เวลาวาดภาพสอบจะรกและสับสนptr = NULL; → ภาพเหลือแค่ head ที่จำเป็นจริง อ่านง่ายขึ้นมากfree() ต้อง = NULL เสมอcurrent->next = ptr->next; ptr->next = current; ptr = NULL; // ปิดตัวที่ใช้เสร็จ — ภาพสะอาด current = NULL; // เหลือแต่ head ที่จำเป็น
หลักการเดียวกัน: ให้ตัวหน้าข้ามตัวที่จะลบ แล้วค่อย free
prev->next = ptr->next; // 1. ให้ตัวหน้าข้ามไปเลย free(ptr); // 2. คืนหน่วยความจำทีหลัง
ptr->next อ่านไม่ได้แล้ว (dangling pointer)head = head->next แล้วค่อย free ตัวเก่าptr->next == NULL พร้อมจำ prev ไว้ptr = NULL; ทุกครั้งหลัง free() — กัน dangling pointer + ทำให้ภาพที่วาดสอบสะอาดให้ statement มาเป็นชุด → ตอบว่าภาพสุดท้ายของลิสต์เป็นยังไง · พิมพ์เองได้ แก้ภาพเริ่มต้นได้
s = r — ย้ายตัวชี้ให้ชี้ที่เดียวกันr = r->next — เดินไปข้างหน้า 1 ก้าวp = p->next->next — ก้าว 2 ทีr->next = p — เปลี่ยนลูกศร ของ nodeq->info = 7 — เปลี่ยนค่าในช่องข้อมูลq = malloc(nodePtr) — สร้าง node ใหม่free(s) — คืนหน่วยความจำt->next = NULL — ปิดท้ายลิสต์data แทน info ก็ได้ · ใส่ ; ท้ายบรรทัดหรือไม่ใส่ก็ได้ · // = คอมเมนต์วาดในกระดาษทด (ปุ่มมุมขวาล่าง) แล้วค่อยกดรันเทียบ