- โครงสร้างข้อมลแบบลิงค์ลิสต์
- กระบวนงานและฟังกชันทที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต์
- ลิงค์ลิสต์แบบซับซ้อน
ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่าง ๆ โดยมพอยเตอร์เป็นตัวเชื่อมต่อ
แต่ละอิลลเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คอ Data จะเก็บข้อมูลของอิลิเมนท์
และส่วนที่สอง คอ Link Field จะทำหน้าที่เก็บตฎแหน่งของโนดต่อไปในลิสต์
การดำเนินการเกี่ยวกับสตริง จะใช้คำสั่ง #include ในการเรียกใช้ เช่น
- ฟังก์ชัน strlen(str) ใช้หาความยาว
- ฟังก์ชัน strcpy(str1, str2) ใช้คัดลอกข้อมูล จากตัวที่ 2 ไปให้ตัวที่ 1
- ฟังก์ชัน strcat(str1, str2) ใช้เชื่อมต่อข้อความ เช่น ตัวแปร 1 เก็บ ชื่อ ตัวแปร 2 เก็บ นามสกุล แล้วนำตัวแปรทั้ง2 มาต่อกัน
- ฟังก์ชัน stecmp(str1, str2) ใช้ปรียบเทียบข้อความ 2 ข้อความว่ามีค่าเท่ากันหรือไม่ ยึดตามหลักพจนานุกรม
โครงสร้างข้อมูลแบบลิงค์ลิสต์
จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure ประกอบด้วย Count, Pos และ head แสดงได้ดังภาพ
2. Data Node Structure ประกอบด้วย Data และ Pointer ที่ชี้ไปยังข้อมูลตัวถัดไป แสดงได้ดังภาพ
กระบวนงานและฟังก์ชันที่ใช้ดำเนินงานพื้นฐาน
1. Create List มีหน้าที่สร้างลิสต์ว่าง ผลลัพธ์ที่ได้คือ ลิสต์ว่าง และ count จะมีค่าป็น 0
2. Insert Node มีหน้าที่เพิ่มข้อมูลลงไปในลิสต์ในตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ลิสต์ ข้อมูล และตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะมีค่าเป็น 1 หรือ 2.....n ตามจำนวนของการ insert
3. Delete Node มีหน้าที่ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ข้อมูลและตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะลดจำนวนจากเดิมลงเรื่อย ตามจำนวนลิสต์ที่ลบไป
4. Search list มีหน้าที่ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ ผลลัพธ์ที่ได้ จะเป็นค่าจริงถ้าพบข้อมูล และจะเป็นค่าเท็จถ้าไม่พบข้อมูล
5. Traverse ทำหน้าที่ท่องหรือเยือนไปในลิสต์เพื่อเข้าถึงและประมวลผลนำเข้า ผลลัพธ์ที่ได้จะขึ้นอยู่กับการประมวลผล อย่างเช่น การรวมฟิลด์ในลิสต์ การเปลี่ยนแปลงค่าในโนด การคำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น
6. Retrieve Node ทำหน้าที่หาตำแหน่งของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้ก็คือ ตำแหน่งข้อมูลที่อยู่ในลิสต์ และเมื่อรู้ตำแหน่งก็ดึงค่าที่ได้มาแสดงในโปรแกรม
7. EmptyList ทำหน้าที่ทดสอบดูว่า ลิสต์ว่างหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อลิสต์ว่าง และจะเป็นเท็จก็ต่อเมื่อลิสต์ไม่ว่าง
8. FullList ทำหน้าที่ในการทดสอบว่าลิสต์เต็มหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อหน่วยความจำเต็ม และจะเป็เท็จก็ต่อเมื่อลิสต์นั้นสามารถมีโนดอื่น
9. List Count ทำหน้าที่นับจำนวนของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้คือ จำนวนข้อมูลที่อยู่ในลิสต์นั้นๆ ซึ่งจะใช้ค่า count ที่อยู่ใน Head Node ออกมาแสดง
10. Destroy List ทำหน้าที่ในการลำลายลิสต์ หรือหยุดใช้ลิสต์นี้แล้ว
Linked List แบบซับซ้อน มี 2 แบบ
สแตก stack
สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทําที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สําคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนําออกมา จากสแตกเป็นลําดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การดําเนินงานพื้นฐานของสแตกการทํางานต่าง ๆ ของสแตกจะกระทําที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตําแหน่งข้อมูลบนสุดของสแตกด้วยการทํางานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สําคัญ
คือ1.Push คือ การนําข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก
ในการเพิ่มข้อมูลลงในสแตก จะต้องทําการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตําแหน่งให้ไปชี้ที่ตําแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม้สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
2. Pop คือ การนําข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องการนําข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนําข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนําสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทําการ pop สแตก จะทําให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow เพราะฉะนั้นก่อนนําข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนําข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตําแหน่งให้ไปชี้ตําแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนํา ออกไป
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นําเอาข้อมูลนั้นออกจากสแตก
ตัวอย่างการทำงานแบบโครงสร้างข้อมูลแบบสแตกที่สามารถเห็นได้ในชีวิตประจำวันทั่วไป ได้แก่
- การใส่เสื้อผ้าเราจะต้องเริ่มใส่เสื้อผ้าที่อยู่ด้านในสุดก่อน และเมื่อเราจะถอดเสื้อผ้าเราก้อจะต้องเริ่มถอดจากชิ้นนอกก่อนเสมอถอดไล่จากชิ้นนอกไปจนถึงชิ้นในสุดเพราะเราไม่สามารถที่จะถอดชิ้นที่อยู่ด้านในออกก่อนได้
- การหยิบน้ำดื่มจากตู้แช่ตามร้านสะดวกซื้อต่างๆ ซึ่งผู้ซื้อจะต้องหยิบน้ำดืมขวดที่อยู่ด้านนอกสุด ซึ่งเป็นขวดสุดท้านในการนำเข้าในตู้แซ่
- การหยิบรถเข็นในห้างสรรพสินค้า
ไม่มีความคิดเห็น:
แสดงความคิดเห็น