DTS 05-23-07-2552

สรุป โครงสร้างข้อมูล เรื่อง Linked list และ Stack


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


กระบวนงาน Search list
หน้าที่ :ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์
ผลลัพธ์ :ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล


กระบวนงาน Traverse
หน้าที่:ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูล นำเข้าลิสต ผลลัพธ์ ขึ้นกับการประมวลผล
เช่นเปลี่ยนแปลงค่าใน nodeรวมฟิลด์ในลิสต์ ,คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น


กระบวนงาน Retrieve Node
หน้าที่ :หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์


ฟังก์ชั่น EmptyList
หน้าที่ :ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าเป็นเท็จ ถ้าลิสต์ไม่ว่าง


ฟังก์ชั่น FullList
หน้าที่:ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูล นำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม
เป็นเท็จ ถ้าสามารถมีโหนดอื่น


ฟังก์ชั่น list count
หน้าที่ :นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์


กระบวนงาน destroy list
หน้าที่:ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ผลลัพธ์ ไม่มีลิสต์



stack
คือ โครงสร้างข้อมูลที่สำคัญและมีลักษณะเรียบง่ายซึ่งใช้แถวลำดับเป็นโครงสร้างสำหรับเก็บข้อมูลพื้นฐานได้แก่สแตก เพราะภาษาคอมพิวเตอร์ส่วนมากกำหนดชนิดแถวลำดับไว้ล่วงหน้าและการทำงานของแถวลำดับสะดวกและเรียบง่าย สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก


Popping Stack
หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วยท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่


Stack Top
เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก



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

การบ้าน การใช้ IOSTREAM.H และ STDIO.H

DTS 04-15-07-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Linked List

Linked List

ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ

ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้

ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node)

ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ

เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link)

หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป

ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือสัญลักษณ์ ^

โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน

ได้แก่ จำนวนโหนดในลิสต์ (Count)

พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง (Pos)

และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูล แรกของลิสต์ (Head)

2. Data Node Structure จะประกอบไปด้วยข้อมูล
(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การสร้าง Linked list
วิธีสร้าง Linked list คือการนำข้อมูลที่จะจัดเก็บเข้า Linked list

เพิ่มตรงโหนดตำแหน่งสุดท้ายของลิสต์ ฉะนั้นจึงต้องมี External พอยน์เตอร์

ที่คอยชี้โหนดสุดท้ายของลิสต์ ในที่นี้ใช้ L (Last)

ตัวอย่างการสร้าง Linked list จากลิสต์ L = 21 , 5 , 14

เริ่มจากการให้ H ชี้ทิ่โหนดตำแหน่งแรก และ L ชี้ทิ่โหนดตำแหน่งสุดท้าย

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

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

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

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

tmp.element = 12;

tmp.next = current.next;

DTS 03-01-07-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Pointer , set and string

Pointer คือตัวแปรที่ทำหน้าที่เก็บตำแหน่งที่อยู่ของตัวแปรที่อยู่ในหน่วยความจำ

การประกาศชนิดของตัวเเปรพอยน์เตอร์
รูปแบบจะเป็น
type *variable-name

ต้องมีระบุตัวดำเนินการ เพื่อบอกว่าตัวแปรดังกล่าวเป็นตัวแปรแบบตัวชี้
โดยตัวดำเนินการที่ใช้คือ
1. เครื่องหมาย &
เป็นเครื่องหมายที่ใช้เมื่อต้องการให้เอาค่าตำแหน่งที่อยู่ของตัวแปร
ที่เก็บไว้ในหน่วยความจำออกมาใช้

เช่น m = &count;

เป็นการนำตำแหน่งในหน่วยความจำของตัวแปร count ใส่ลงไปในตัวแปร (แบบพอยท์เตอร์)
m ซึ่งตำแหน่งที่ว่านี้เป็นตำแหน่งของตัวแปรนั้น ๆ ภายในของคอมพิวเตอร์

2. เครื่องหมาย *
ซึ่งจะมีการใช้งานอยู่ 2 ลักษณะ

- ใช้ในการประกาศ parameter
เช่น void swap(int*p,int*q)
{
............................
}




- ใช้เป็น dereferencing operator จะใช้เมื่อต้องการนำค่าที่อยู่ในตำแหน่ง
ที่ตัวแปรพอยน์เตอร์นั้นชี้อยู่ออกมาแสดง


set and string

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

เช่น การตรวจสอบข้อความ การจัดแนวข้อความ ในแต่ละย่อหน้า และการค้นหาคำ เป็นต้น
เช่น "UNIVERSITY!" จะเป็นข้อมูลแบบสตริงยาว 10 อักขระสตริงกับอะแรย์สตริง
คือ อะเรย์ของอักขระ เช่น char a[5]อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ
หรือ เป็นสตริงขนาด 5 อักขระก้อได้

โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character
เช่นchar a[]={'H','E','L','L','O','\0'};char a[]="hello";