Park-Kachen

28 กรกฎาคม 2552

DTS05-22-07-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง Linked list (ต่อ)
Circular Linked list
ในปกติ Linked list เมื่อถึงโหนดสุดท้าย ค่าในฟิลด์ LINK หรือ โหนดถัดไปจะมีค่าเป็น NULL ซึ่งเราสามารถใช้ประโยชน์ได้โดยการเปลี่ยนให้ ค่า NULL ในฟิลด์ LINK เป็นตำแหน่งของโหนดแรกในลิสต์ หรือชี้ไปที่ต้นลิสต์ใหม่นั่นเอง ซึ่งเราจะเรียก Linked list แบบนี้ว่า Circular Linked list ใช้ประโยชน์เมื่อต้องการให้ข้อมูลมีลักษณะเป็นวนรอบหรือลูป โดยแต่ละขั้นตอนการทำงานภายในลูป จะมีการย้ายตำแหน่งของพอยน์เตอร์ไปยังโหนดถัดไปใน Linked list ในลักษณะแบบวงกลม
Doubly Linked list


Doubly linked list ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง





การเพิ่มข้อมูลใน doubly linked list

การเพิ่มข้อมูลใน doubly linked list จะแตกต่างจาก Singly Linked list คือ สามารถเพิ่มโหนดให้อยู่หน้าโหนดที่ระบุได

ตัวอย่างการเพิ่มข้อมูล node (Q) ให้อยู่หน้า node (P)

สแตค (Stack
สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้ เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้การนำข้อมูลเข้า-ออก จากสแตค (push , pop) จะมีลักษณะแบบเข้าหลัง ออกก่อน (LIFO : Last In , First Out) คือ ข้อมูลที่เข้าไปในสแตคลำดับหลังสุด จะถูกนำข้อมูลออกจากสแตคเป็นลำดับแรก ยกตัวอย่างการทำงานแบบ LIFO เช่น การวางจานซ้อนกัน

รูปแสดงลักษณะของสแตค ที่ประกอบด้วยข้อมูล A , B , C , D และ E มี TOP ที่ชี้ที่สมาชิกตัวบนสุดของสแตค


Stack ที่พบในชีวิตประจำวัน คือ กล่องที่ใส่ CD
posted by Park-Kachen at 06:17 0 comments

20 กรกฎาคม 2552

DTS04-15-07-2552

สรุปสิ่งที่ได้จากการเรียน Set & String และ Linked lists


การสร้างอะเรย์ของสตริง สามารถทำได้ทั้งแบบที่กำหนดตัวแปรและแบบที่ให้ค่าเริ่มต้น จะสร้างเมื่อสตริงมีจำนวนมาก เพื่อช่วยให้เขียนโปรแกรมได้สะดวกขึ้น




ARAY ของสตริงที่ยาวไม่เท่ากัน ทำได้เฉพาะเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น




ตัวอย่าง code




ผลการรันโปรแกรม
Data structure
English
Programming
Photoshop
Systems Analysis

ARAY ของสตริงที่ยาวเท่ากัน ถือว่าเป็นอะเรย์ที่แท้จริง สามารถกำหนดได้ทั้งเมื่อกำหนดตัวแปรและเมื่อมีการให้ค่าเริ่มต้น โดยดำเนินการแบบกำหนดอะเรย์ 2 มิติ

ตัวอย่าง code ผลการรันโปรแกรม
Olive
Mango
Apple

Linked Lists
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^



โหนด (Node)

การสร้าง Linked list
วิธีสร้าง Linked list คือการนำข้อมูลที่จะจัดเก็บเข้า Linked list เพิ่มตรงโหนดตำแหน่งสุดท้ายของลิสต์ ฉะนั้นจึงต้องมี External พอยน์เตอร์ที่คอยชี้โหนดสุดท้ายของลิสต์ ในที่นี้ใช้ L (Last) ตัวอย่างการสร้าง Linked list จากลิสต์ L = 21 , 5 , 14เริ่มจากการให้ H ชี้ทิ่โหนดตำแหน่งแรก และ L ชี้ทิ่โหนดตำแหน่งสุดท้าย








ข้อมูล 5 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 5






เพิ่มข้อมูล 14 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 14








การเพิ่มและลบข้อมูลใน Linked list

การเพิ่มข้อมูลที่ต้น list














จากรูป จะเพิ่ม NODE(tmp) ลงใน linked list โดยมีขั้นตอนคือ
tmp = new ListNode();
tmp.element = 12;
tmp.next = current.next;

การเพิ่มข้อมูลโดยแทรกลงในลิสต์
การเพิ่มข้อมูลจะทำการแทรกโหนด New หลังโหนด P

ตัวอย่าง ทำการเพิ่มข้อมูลโหนด 16 ระหว่างโหนด 21 และ 5





















จากรูปมีขั้นตอนดังนี้
tmp = new ListNode();
tmp.element = 16;
tmp.next = current.next;
current.next = tmp

การลบข้อมูลใน Linked list
การลบข้อมูลที่ต้น list
เนื่องจากขั้นตอนของการลบข้อมูลที่ header นั้นจะมีปัญหาที่ยุ่งยากกว่าเมื่อ design ด้วย oop(java) เราสามารถที่จะแก้ปัญหานี้ได้โดยการใส่ header node ที่ว่าง ๆ ไว้ข้างหน้าของ linked list เพื่อที่จะทำหน้าที่เป็นชี้ว่าเป็นหัวโหนดโดยที่ไม่ต้องมี pointer คอยชี้ที่ header และเมื่อเราต้องการที่จะเปลี่ยนแปลงข้อมูลใด ๆ บนหัวสามารถที่จะทำได้โดยการแทรก node เข้าไปดังตัวอย่างของการแทรกข้อมูลข้างล่าง







จากรูปมีขั้นตอนดังนี้

tmp.next = tmp.next.next





posted by Park-Kachen at 05:33 0 comments

13 กรกฎาคม 2552

DTS03-01-07-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง Pointer และ Set



Pointer
การกำหนดตัวแปร Pointer จะคล้ายกับการกำหนดตัวแปรชนิดต่างๆ เพียงแต่ต้องมีเครื่องหมาย * หน้าชื่อตัวแปร ดังนี้
int *pt;



char *pt;



ในที่นี้กำหนดให้ pt เป็นตัวแปร Pointer ซึ่งเก็บ Address ของตัวแปรชนิดตัวเลขจำนวนเต็ม
ในเรื่อง Pointer มีเครื่องหมาย 2 ชนิด คือ * และ & เครื่องหมาย * จะให้ค่า ของข้อมูล ซึ่งเก็บอยู่ใน Address โดย Address นี้เก็บ อยู่ในตัวแปร Pointer ซึ่งอยู่หลังเครื่องหมาย * สำหรับเครื่องหมาย & จะให้ค่า Address ของตัวแปรซึ่งอยูหลังเครื่องหมาย & ดังตัวอย่าง


การประกาศตัวแปรPointer
ต้องมีระบุตัวดำเนินการ (Operator) เพื่อบอกว่าตัวแปรดังกล่าวเป็นตัวแปรแบบตัวชี้ โดยตัวดำเนินการที่ใช้คือ * และ & เช่น จะประกาศตัวแปรชนิดPointer คือ int *countPtr; ในที่นี้หมายถึง ตัวแปร countPtr ถูกประกาศให้เป็นตัวแปรชนิด Pointer และทำหน้าที่ชี้ (เก็บ Address) ไปยังตำแหน่งที่เก็บค่าจำนวนเต็ม(เป็นชนิดเดียวกับที่เราประกาศไว้ ในที่นี้คือ Integer)

ตัวอย่าง code

int x = 10;

int *xPtr;

xPtr = &x; //ชี้ไปยังตำแหน่ง x
จะได้ว่า



หมายความว่า : Pointer xPtr ชี้ไปยังตำแหน่งเดียวกับ ตัวแปร x ซึ่งเก็บค่า 10 ไว้


pointer กับ array
pointer และ array มันถูกนำมาอธิบายไว้ด้วยกัน เพราะ pointer กับ array มีหลายอย่างที่คล้ายๆ กัน และอันที่จริงเราสามารถสร้าง array จาก pointer ได้ ซึ่งแม้จะมีข้อเสียที่ใช้งานได้ยากกว่า แต่ก็มีข้อดีที่ทำงานได้เร็วกว่าPointer และ array มักถูกนำมาใช้ร่วมกันอยู่เสมอเนื่องจาก array เป็นข้อมูลในหน่วยความจำที่เรียงติดกันไป เราจึงอาจใช้ pointer เพื่อวนเข้าถึงข้อมูลเหล่านั้น ดังโค้ดต่อไปนี้ จะเห็นได้ว่าการใช้ pointer เข้าถึงข้อมูลใน array (array element) โดยตอนแรกเราสร้าง array ชื่อ myArray จากนั้นสร้าง pointer ที่ชี้ไปยัง array ชื่อ ptArray คำสั่ง fixed ทำหน้าที่ตั้งให้ pointer ชี้ไปยังตัวแปรแบบ managed และตรึงค่าของตัวแปรไว้ไม่ให้เปลี่ยนตำแหน่งระหว่างโปรแกรมทำงาน
ผลลัพธ์เมื่อโปรแกรมทำงานคือ 1234

posted by Park-Kachen at 03:53 0 comments