บทที่ 1 อัลกอริทึม Algorithm

ผังงาน อัลกอริทึม

ชนิดของข้อมูล

1.ข้อมูลชนิดตัวอักษร  (Character) คือ ข้อมูลที่เป็นรหัสแทนตัวอักษรหรือค่าจำนวนเต็ม ได้แก่ ตัวอักษร ตัวเลขและกลุ่ม

ตัวอักขระพิเศษใช้พื้นที่ในการเก็บข้อมูล 1 ไบต์

2.ข้อมูลชนิดจำนวนเต็ม (Integer) คือ ข้อมูลที่เป็นเลขจำนวนเต็ม ได้แก่ จำนวนเต็มบวก จำนวนเต็มลบ และศูนย์ 

ข้อมูลชนิดจำนวนเต็มใช้พื้นที่ในการเก็บข้อมูล ขนาด 2 ไบต์

3.ข้อมูลชนิดจำนวนเต็มที่มีขนาด 2 เท่า (Long Integer)  คือ ข้อมูลที่เป็นเลขจำนวนเต็ม ใช้พื้นที่ในการเก็บเป็น 2 เท่าของ Integer 

คือมีขนาด 4 ไบต ์

4.ข้อมูลชนิดเลขทศนิยม (Float) คือ ข้อมูลที่เป็นเลขทศนิยม ขนาด 4 ไบต์

5.ข้อมูลชนิดเลขทศนิยมอย่างละเอียด (Double)  คือ ข้อมูลที่เป็นเลขทศนิยม ใช้พื้นที่ในการเก็บข้อมูลเป็น 2 เท่าของfloat คือมีขนาด 8 ไบต์ 

ผังงาน (Flowchart)

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

ประโยชน์ของผังงาน

-ช่วยลำดับขั้นตอนการทำงานของโปรแกรม และสามารถนำไปเขียนโปรแกรมได้โดยไม่สับสน

-ช่วยใดข้อผิดพลาด

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

-ช่วยให้ผู้อื่นสามารถศึกษาการทำงานของโปรแกรมได้อย่างง่าย และรวดเร็วมากขึ้น

วิธีการเขียนผังงานที่ดี

-ใช้สัญลักษณ์ตามที่กำหนดไว้

-ใช้ลูกศรแสดงทิศทางการไหลของข้อมูลจากบนลงล่าง หรือจากซ้ายไปขวา

-คำอธิบายในภาพควรสั้นกระทัดรัด และเข้าใจง่าย

-ทุกแผนภาพต้องมีลูกศรแสดงทิศทางเข้า - ออก

-ไม่ควรโยงเส้นเชื่อมผังงานที่อยู่ไกลมาก ๆ ควรใช้สัญลักษณ์จุดเชื่อมต่อแทน

-ผังงานควรมีการทดสอบความถูกต้องของการทำงานก่อนนำไปเขียนโปรแกรม

ผังงานโปรแกรม

-จุดเริ่มต้น / สิ้นสุดของโปรแกรม

-ลูกศรแสดงทิศทางการทำงานของโปรแกรมและการไหลของข้อมูล

-ใช้แสดงคำสั่งในการประมวลผล หรือการกำหนดค่าข้อมูลให้กับตัวแปร

-แสดงการอ่านข้อมูลจากหน่วยเก็บข้อมูลสำรองเข้าสู่หน่วยความจำหลักภายในเครื่องหรือการแสดงผลลัพธ์จากการประมวลผลออกมา

-การตรวจสอบเงื่อนไขเพื่อตัดสินใจ โดยจะมีเส้นออกจากรูปเพื่อแสดงทิศทางการทำงานต่อไป เงื่อนไขเป็นจริงหรือเป็นเท็จ

-แสดงผลหรือรายงานที่ถูกสร้างออกมา

-แสดงจุดเชื่อมต่อของผังงานภายใน หรือเป็นที่บรรจบของเส้นหลายเส้นที่มาจากหลายทิศทางเพื่อจะไปสู่การทำงานอย่างใดอย่างหนึ่งที่เหมือนกัน

-การขึ้นหน้าใหม่ ในกรณีที่ผังงานมีความยาวเกินกว่าที่จะแสดงพอในหนึ่งหน้า 

สัญลักษณ์ในการเขียนผังงาน

การเขียนผังงาน (Flowchart) มี 3 แบบ 

1. ผังงานแบบเรียงลำดับ  (Sequemce Flowchart) เป็นการเขียนผังงานแบบง่ายที่สุด ทำงานจากบนลงล่าง ตามลูกศร

2. ผังงานแบบมีทางเลือกหรือแบบมีเงื่อนไข  (Selectiom or Condition Flowchart) คือตรวจสอบเงื่อนไขถ้าเป็นจริง ก็ทำงานตามเงื่อนไขที่เป็นจริง ถ้าเป็นเท็จก็ทำตามเงื่อนไขที่เป็นเท็จ

กรณี 1 ทางเลือก

3.รหัสจำลองที่เรียกว่า การเขียนซูโดโค้ด (Pseudo Code) คือการเขียนคำอธิบายขั้นตอนการทำงานของโปรแกรม  โดยใช้ถ้อยคำผสมระหว่างภาษาอังกฤษและภาษาการเขียนโปรแกรมแบบโครงสร้าง  ซึ่งจะช่วยให้ผู้เขียนโปรแกรมสามารถพัฒนาขั้นตอนต่าง ๆ  ให้เป็นโปรแกรมได้ง่ายขึ้น  ส่วนใหญ่มักใช้คำเฉพาะ  (Reserve Word)  ที่มีในภาษาการเขียนโปรแกรมและมักเขียนด้วยตัวอักษรตัวใหญ่  ซูโดโค้ดที่ดี  จะต้องมีความชัดเจน  สั้น  และได้ใจความ  ข้อมูลต่าง ๆ  ที่ใช้จะถูกเขียนอยู่ในรูปของตัวแปร

รูปแบบ Algorithm  <ชื่อของอัลกอริทึม>

START

1……………………………….

2……………………………….

3…………………………………

END

บทที่ 8 การเรียงลำดับข้อมูล Sorting

การเรียงลำดับข้อมูล

การจัดเรียงลำดับ (Sorting) 

การจัดเรียงข้อมูล ให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ (มากไปน้อย หรือ น้อยไปมาก)

ในกรณีที่ข้อมูลในแต่ละ Record มีหลาย Field เราต้องพิจารณาเลือก Field ที่สนใจเพื่อใช้ในการเรียงลำดับ เช่น การจัดเรียงลำดับประวัตินักศึกษา อาจใช้หมายเลขประจำตัวของนักศึกษาเป็น Field โดยเรียงจากน้อยไปมาก

ประเภทของการเรียงลำดับข้อมูล

การจัดเรียงภายใน (Internal Sorting)

การจัดเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ การจัดเรียงแบบนี้จะต้องอาศัยเทคนิคและวิธีการของโครงสร้างข้อมูลมาช่วย เช่น การใช้ Array หรือ Linked-List เข้ามาช่วย

การจัดเรียงภายนอก (External Sorting)

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

วิธีการจัดเรียงข้อมูล

การจัดเรียงแบบแลกเปลี่ยน (Exchange Sort)

การจัดเรียงแบบแทรก (Insertion Sort)

การจัดเรียงแบบเลือก (Selection Sort)

การจัดเรียงแบบแลกเปลี่ยน (BUBBLE SORT)

เป็นการจัดเรียงโดยการเปรียบเทียบค่า 2 ค่าที่ติดกัน

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

- ข้อมูลที่มีค่าน้อย ต้องอยู่ในตำแหน่งหน้า

- ข้อมูลที่มีค่ามาก จะอยู่ตำแหน่งหลัง

- ข้อมูล 2 ตัวที่อยู่ติดกัน ถ้า

- ถ้าข้อมูลตัวแรกมากกว่าตัวหลัง ก็จะต้องสลับตำแหน่งกัน

- แต่ถ้าข้อมูลตัวแรกน้อยกว่าข้อมูลตัวหลัง ก็ไม่ต้องสลับตำแหน่ง

- ทำเช่นนี้ซ้ำกันไปเรื่อย ๆ จนกว่าการเปรียบเทียบของข้อมูลตลอดทั้งชุดจะไม่ต้องมีการสลับตำแหน่งเลย

Bubble Sort

แนวคิด คือค่าที่มากๆ จะต้องถูกนำไป (ลอยไป) ไว้ด้านท้าย

เหมือนลูกโป่งที่ขนาดใหญ่จะลอยได้เร็วและสูง

แนวคิด

- เริ่มนำข้อมูลตัวแรกเทียบกับตัวที่ 2 ตัวไหนมากก็จะถูกสลับกัน ทำอย่างนี้ไปจนถึงตัวสุดท้าย เราจะได้

- ค่าที่มากที่สุด 1 ตัวไว้ด้านท้าย

- แต่ละครั้งจะได้ค่ามากที่สุดไปไว้ท้ายสุด

- จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-1

- จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-2

- จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-x

ทำจน x = N-1

ตัวอย่าง: Bubble Sort

ข้อมูล 8  ตัวทำ 7  รอบ = 44,55,12,42,94,18,06,67

รอบที่    ข้อมูล

1 06 44 55 12 42 94 18 67

2 06 12 44 55 18 42 94 67

3 06 12 18 44 55 42 67 94

4 06 12 18 42 44 55 67 94

5 06 12 18 42 44 55 67 94

6 06 12 18 42 44 55 67 94

7 06 12 18 42 44 55 67 94

การจัดเรียงแบบแทรก (Insertion Sort)

เป็นการจัดเรียงโดยการนำข้อมูลที่จะทำการเรียงนั้น ๆ ไปจัดเรียงทีละตัว

โดยการแทรกตัวที่จะเรียงไว้ในตำแหน่งที่เหมาะสมของข้อมูลที่มีการจัดเรียงเรียบร้อยแล้ว ณ ตำแหน่งที่ถูกต้อง

⧭ วิธีการลักษณะนี้จะคล้ายกับการหยิบไพ่ขึ้นมาเรียงทีละใบ ซึ่ง

ไพ่ใบแรกจะไม่ต้องสนใจอะไร

แต่เมื่อหยิบไพ่ใบที่ 2 ก็จะต้องพิจารณาว่าจะไว้ก่อนหรือไว้หลังใบแรก

และเช่นเดียวกัน เมื่อหยิบไพ่ใบถัด ๆ มา ก็จะต้องพิจารณาว่าจะวางใบตำแหน่งใดเพื่อให้เกิดการเรียงลำดับ จนกระทั่งหมด

การจัดเรียงแบบเลือก (Selection Sort)

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

HEAP SORT

- ในการจัดเรียงด้วยเวลา O(N log N)  อัลกอริทึมที่ใช้พื้นฐานแนวคิดนี้ เรียกว่า heapsort และมี Big-Oh running time ดีกว่าอัลกอริทึมอื่น ๆ ที่กล่าวมาแล้ว

-วิธีการ คือ สร้าง binary heap (มีสมาชิก N ตัว) ซึ่งใช้เวลา O(N) จากนั้นทำ deleteMin N ครั้ง สมาชิกที่ถูกย้ายออกไปจาก heap ตัวแรก คือตัวที่มีค่าน้อยที่สุด และเรียงลำดับตามค่าไป แล้วนำไปเก็บใน Arrray อีกตัวหนึ่งจากนั้นก็คัดลอกกลับไปยัง Array เดิมซึ่งก็จะเป็นคำตอบในการจัดเรียง เนื่องจากการทำ deleteMin แต่ละตัวใช้ O(log N) ดังนั้น running time รวมทั้งหมด คือ O(N log N)

- หลังการทำงานจนเสร็จ Array ที่ได้ก็จะเป็น Arrayของสมาชิกที่จัดเรียงจากมากไปน้อย

- ถ้าต้องการจัดเรียงจากน้อยไปมาก เราก็จะใช้ heap ที่ parent มีค่ามากกว่า child ของมัน นั่นคือ (max)heap

- เราจะใช้ (max)heap ในการ implement ของเราและยังคงใช้ Array เช่นเดิม

- ขั้นแรกสร้าง heap ด้วย linear time จากนั้นทำ deleteMaxes จำนวน N - 1 ครั้ง ด้วยการสลับสมาชิกตัวสุดท้ายใน heap กับสมาชิกตัวแรก แล้วลดขนาดของ heap ลงแล้วทำการ percolating down 

- หลังจบอัลกอริทึมจะได้ Arrayที่มีสมาชิกเรียงตามลำดับค่า

QUICK SORT

หลักการดำเนินงาน

- หาตำแหน่งในการแยกลิสต์

- แบ่งแยกข้อมูลออกเป็นสองส่วน และหาตำแหน่งในการแยกลิสต์

- ทำจนกว่าข้อมูลจะเรียงลำดับเรียบร้อย

การดำเนินการ

- เริ่มต้นใช้ข้อมูลตัวแรกเป็นตัวเปรียบเทียบ (pivot)

- ทำการเปรียบเทียบค่าของข้อมูลที่ชี้โดย first กับPivot ถ้าน้อยกว่า pivot ให้ทำการเลื่อน firstไปยังข้อมูลต่อไปและเปรียบเทียบไปจนกว่าจะพบแล้วจึงหยุดการเปรียบเทียบ

- เมื่อพบตำแหน่งแล้ว จะหันมาพิจารณาที่ last ชี้อยู่หากค่าที่ last ชี้อยู่มีค่าน้อยกว่าที่ first ชี้อยู่ให้สลับตำแหน่ง

- ทำการเปรียบเทียบค่าของข้อมูลที่ชี้โดย first กับPivot ถ้าน้อยกว่า pivot ให้ทำการเลื่อน firstไปยังข้อมูลต่อไปและเปรียบเทียบไปจนกว่าจะพบแล้วจึงหยุดการเปรียบเทียบ

- เมื่อพบตำแหน่งแล้ว จะหันมาพิจารณาที่ last ชี้อยู่หากค่าที่ last ชี้อยู่มีค่าน้อยกว่าที่ first ชี้อยู่ให้สลับตำแหน่ง

- พบตำแหน่งที่จะใช้แบ่งชุดข้อมูลแล้ว จึงทำการแบ่งข้อมูลออกเป็นสองชุด

-ดำเนินการแบบเดียวกับกับข้อมูลชุดขวามือดำเนินการกับข้อมูลที่เหลือเหมือนเดิมจนกว่าจะได้ข้อมูลในตำแหน่งต่างๆ จนครบ

MERGE SORT

กระบวนการแยกชุดข้อมูล

กระบวนการรวมชุดข้อมูล

ได้ชุดข้อมูลที่เรียงลำดับเรียบร้อยแล้ว

Merge Sort Algorithm Analysis

จำนวนครั้งของการเปรียบเทียบทั้งหมด

=ผลบวกทุกระดับของ(จำนวนลิสต์ในแต่ละระดับ * จำนวนครั้งของการเปรียบเทียบแต่ละลิสต์ )

= (N-1) *1 + (N/2 -1)*2 + (N/4 – 1)*4 +..+(2-1)*N/2

= ( N-1) + (N-2)+(N-4)+..+(N-N/2) 

=  Nlog2N    จะได้ bigO(Nlog2N)

บทที่ 7 กราฟ Graph

โครงสร้างกราฟ

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

อินดีกรีและเอาท์ดีกรี

· แต่ละโหนดจะมีจำนวนเส้นเซื่อมระหว่างโหนดไม่เท่ากัน

· In-Degree แสดงจำนวนเส้นเซื่อมที่เข้ามายังโหนดนั้นๆ

· Out-Degree แสดงจำนวนเส้นที่ออกจากโหนดนั้นไป

· ใน Undirected Graph จำนวน in-Degree จะเท่ากัน

ประโยชน์ของกราฟ (Routing เป็นการแสดงหาเส้นทาง)

· NetWorek (การเซื่อมต่อของอุประกรณ์ Router)

· เพื่อใช้ในการรับส่งข้อมูลในเครื่องข่าย

ประโยชน์ของกราฟ (Algorithm Design)

· Map Coloring คือวิธีการระบายสีในแผนที่โดยใช้สีน้อยที่สุด

· พื้นที่เดียวกันห้ามใช้สีหมือนกัน

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

ชนิดของกราฟ

- การแบบไม่มีทิศทาง (Undirected  Grehp) คือ กราฟที่เส้นเซื่อมไม่ลูกศรกำกับทิศทางทีมีความสัมพันธ์ของ 2 โหนดแบบไปและกลับ

- กราฟแบบมีทิศทาง (Deriected Grehp หรือ Digraph) คือ กราฟที่เส้นเซื่อมลูกศรกำกับทิศทาง เช่น อาจมีสายการบินจาก กรุงเทพ-เชียมเลียบ กำพูชา แต่ไม่มีสายการบินจากเชียบเลียบ-กรุงเทพ หรือ Edge แสดงค่าโดยสารที่มีราคา ไป-กลับำม่เท่ากันและค่าโทรศัพท์ไทยไปสิงคโปร์ แพงกว่าสิงคโปร์โทรหาไทย

การแทนที่กราฟในหน่วยความจำจะสามารถทำได้ใน 2 แบบคือ

1. Adjacency Matrix: ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List: ใช้ลิ่งค์ลิสต์เก็บข้อมูล

วิธีการท่องไปในกราฟ (Graph Traversal)

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

1.Depth-First Traversal  การท่องแบบลึก

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

2.Breadth-First Traversal  การท่องแบบกว้าง

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

บทที่ 6 ทรี Tree

โครงสร้างทรี

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

องค์ประกอบของทรี

    โหนด ( Node ) ที่ใช้สำหรับบรรจุข้อมูลโดยจะมีกิ่งซึ่งเป็นเส้นที่โยงโหนดเข้าด้วยกันที่เรียกปลาจำนวนของ บรานช์ (Branch) ที่สัมพันธ์กับโหนดเรียกว่า ดีกรี (Degree) และถ้าหากที่เป็นที่ที่ไม่ใช่ที่ว่างหนวดแรกจะเรียกรูท (root) โดยโหนดทุก ๆ โหนดยกเว้นรูทโหนดจะมีเพียง 1 predecessor ในขณะที่ successor อาจเป็น 0 หรือ 1 หรือมากกว่า 1 ก็ได้ สำหรับ Leaf ก็คือโหนดใบที่ไม่มีบรานช์เชือมโยงไปยังโหนดถัดไปหรือโหนดที่ไม่มีตัวตามหลังหรือ Successor นั่นเองในขณะที่ โหนดพ่อ (Parent) จะมี่โหนดตามหลังหรือโหนดลูก (Child) ต่อท้าย โหนดลูกตั้งแต่สองโหนดหรือมากกว่าที่มาจากพ่อเดียวกันจะเรียกว่า โหนดพี่น้อง (Siblings)

    โหนดต่าง ๆ ภายในทรีจะอยู่ในระดับที่ต่างกันโดยเริ่มต้นจากรูทโหนดซึ่งถือเป็นระดับแรกสุด(Level) ส่วนลูกๆ ของรูทโหนดก็คือระดับที่ 1 (Lelvel) และลูกๆ ของโหนดในระดับที่ 1 ก็จะอยู่ในระดับที่ 2 (Level 2) ซึ่งจะเพิ่มระดับไปเรื่อยๆเมื่อลูกหลานเพิ่มขึ้น

ซับทรี (Subtrees)

หมายถึง โครงสร้างที่เชื่อมต่อกันภายใต้ Root โดย

- Node แรกของ Subtrees จะเป็น  Root ของ Subtree นั้น และใช้เป็นชื่อเรียก Subtree

- Subtree สามารถแบ่งย่อยเป็น Subtree ได้อีกจนกว่าจะ  Empty

ต้นไม้แบบไบนารี (Binary Tree)

        ไบนารีทรี หมายถึงทรีที่มีโหนดลูกไม่เกิน สองโหนด ประกอบด้วยโหนดลูกทางซ้าย(Left child)และโหนดลูกทางขวา(Right child) โหนดลูก อาจเป็นทรีย่อยก็ได้ซึ่งแบ่งออกเป็น ทรี ย่อยทางซ้ายและทรีย่อยทางขวาและโหนดลูกแต่ละโหนดอาจมีหนดลูกเพียงด้านซ้ายหรือด้านขวาด้านเดียวก็ได้สำหรับโหนดของทรีมีจำนวนเป็น 0 เรียกว่าทรีว่าง (Empty Tree)

การท่องผ่าน Binary tree

        การท่องผ่านโหนดหมายถึงการเข้าไปในโครงสร้างต้นไม้เพื่อนำข้อมูลในโหนดมาแสดงหรือเพื่อการค้นหาเพื่อประมวลผลการเดินเยี่ยมโหนดมี 3 วิธี

1. imorder trabersal หรือ symmetric order จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบอินออเดอร์ก่อนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบอินออเดอร์(Left/ Root/ Right)

2. preorder traversal จะทำการเยี่ยมโหนดรากก่อน เยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ พรีออเดอร์ และเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบพรีออเดอร์ (Root/Left/Right)

3. postorder traversal หรือ Endorder จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ โพสออเดอร์ก่อนเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบโพสออเดอร์และเยี่ยมโหนดราก (Left/Right/Root

บทที่ 5 คิว Queue

Queue structure

     

       โครงสร้างการทำงานแบบคิวคือการมีการจัดลำดับการเข้าและออกข้อมูลอย่างเป็นลำดับ ข้อมูลใดเข้ามาก่อนก็จะดำเนินการก่อน  หากข้อมูลใดเข้ามาทีหลังก็จะดำเนินการทีหลัง เรียกลักษณะของการดำเนินการแบบนี้ว่า FirstIn First Out (FIFO) หรือเข้าก่อนออกก่อน

ลักษณะของคิว

-  โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นและไม่เชิงเส้น

-  มีทางเข้าและออก 2  ทาง

-  มีการทำงานแบบลำดับ

-  สามารถนำข้อมูลเข้าและนำข้อมูลออกสลับกันได้

-  มีลำดับการทำงานแบบเข้าก่อนออกก่อน (FIFO)

ประเภทของคิว มี 3 ประเภท

-  คิวธรรมดา (Queue)

-  คิววงกลม (Circular Queue)

-  คิวที่เรียงลำดับตามความสำคัญ (Priority Queue)

การดำเนินการของคิว

เมื่อนำเข้าข้อมูลจะต้องจัดเรียงในลักษณะการต่อท้ายกัน

-  ข้อมูลที่อยู่ส่วนท้ายของการเก็บข้อมูล เรียกว่า  Rear

-  ข้อมูลที่อยู่ส่วนหัวของการเก็บข้อมูล ซึ่งจะเรียกว่า  Front

-  การนำข้อมูลเข้าไปในคิว  เรียกว่า Insert (Enqueue)

-  การนำข้อมูลออกจากคิว เรียกว่า Remove (Dequeue)

คิวธรรมดา (Queue)

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

การนำข้อมูลเข้า Enqueue

   ก่อนนำสมาชิกเข้าคิว ต้องตรวจสอบว่าคิวเต็มหรือไม่ โดยที่ ถ้า rear = maxQ แสดงว่าคิวเต็ม (เมื่อ maxQ คือขนาดของคิว)การนำข้อมูลใหม่เข้ามาแถวคอย จะเพิ่มเข้ามาด้านหลังและจะนำเข้ามาเรื่อย ๆ จนเต็ม หรือเรียกว่า แถวคอยเต็ม (Queue Overflow)ดังนั้นการนำสมาชิกเข้าคิว จึง เป็นการเพิ่มค่าพอยน์เตอร์ rear หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน

ลักษณะของคิวแบบวงกลม

- เหมือนคิวธรรมดาคือมีตัวชี้ 2 ตัวคือ front และ rear สำหรับแสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ

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

- เหมือนคิวธรรมดาคือมีตัวชี้ 2 ตัวคือ front และ rear สำหรับแสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ

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

o คิววงกลมจัดการปัญหานี้โดย กรณี rear ชี้อยู่ที่ตำแหน่งสุดท้ายของคิว ถ้าหากมีการเพิ่มข้อมูล ค่าของ rear จะสามารถวนกลับมาชี้ยังตำแหน่งแรกสุดของคิวได้

ดังนั้นคิววงกลมจะสามารถเพิ่มข้อมูลเข้าไปในคิวได้ จนกว่าคิวจะเต็มจริง ๆ

การประยุกต์ใช้ Queue

การประยุกต์คิวมาใช้งานบนคอมพิวเตอร์

-  การเข้าคิวของโปรเซสหรืองานต่าง ๆ เพื่อรอการประมวลผลจากซีพียูตามลำดับ

-  การแบ่งเวลา (Time Sharing) ด้วยการจำกัดตารางเวลาการประมวลผลของแต่ละโปรเซส ส่งผลให้สามารถหมุนเวียนการประมวลผลในแต่ละโปรเซสสลับไปมาได้ ทำให้ดูเหมือนกับการประมวลผลงานหลาย ๆ อย่างได้ในเวลาเดียวกัน (Multitasking)

-  การเข้าคิวเพื่อรอผลลัพธ์จากเครื่องพิมพ์

บทที่ 4 สแตก Stack

Stack (กองซ้อน)

ลักษณะของสแตก

- สแตก เป็นโครงสร้างข้อมูลแบบเชิงเส้น

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

- การเพิ่มหรือนำข้อมูลออกจากสแตกทำได้ที่จุดปลายของสแตกทางเดียว

- มาทีหลังแต่ออกก่อน (Last In – First Out : LIFO)

ส่วนประกอบสำคัญของสแตก

1. ตัวชี้สแตก หรือ Stack Pointer เป็นตัวควบคุมการนำสมาชิกเข้า หรือออกจากสแตก

2. สมาชิกของสแตก หรือ Stack Element คือ สมาชิกของสแตก 

3. ค่าสูงสุดของสแตก หรือ Max Stack เป็นค่าที่บอกว่าสแตกนี้สามารถเก็บข้อมูลได้มากที่สุดเท่าไหร่

การสร้างสแตก Stack implement

สามารถสร้างสแตกด้วยการแทนที่ข้อมูลสแตกได้ 2 วิธี คือ

1. การสร้างสแตกด้วยอาร์เรย์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Static 

2. การสร้างสแตกด้วยลิงค์ลิสต์ เป็นการจัดสรรเนื้อที่หน่วยความจำแบบ Dynamic

การจัดการกับสแตก

       ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (Push Stack) และการดึงข้อมูลออกจากสแตก (Pop Stack)

ฟังก์ชัน Clear stack                                                                                                                                        ClearStack : เป็นการดำเนินการเพื่อลบข้อมูลออกจากสแตกให้หมดกรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ช่องบนสุดของสแตกเป็น 0                                                                                                                                                                   Stack.Top := 0;

ฟังก์ชัน Clear stack                                                                                                                                         ClearStack : กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ต้องสั่งให้ตัวชี้สแตกไม่ชี้ไปที่ไหนเลย

                                               กำหนดค่าตัวชี้สแตก = Null

ฟังก์ชัน empty stack                                                                                                                                          EmptyStack : เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นมีข้อมูลหรือไม่  กรณีใช้โครงสร้างข้อมูลอาร์เรย์ ต้องสั่งให้ตรวจสอบว่าที่ Top ของสแตกนั้นมีค่า = 0 หรือไม่    

                                                EmptyStack := Stack.top := 0;

{ถ้าเป็นจริงจะส่งค่า True ออกมาให้โปรแกรมหลัก}

กรณีใช้โครงสร้างข้อมูลลิงค์ลิสต์ ให้ตรวจสอบว่าตัวชี้สแตกไม่ชี้ไปที่ไหน    

                                                EmptyStack := Stack.Nil;

{ถ้าเป็นจริงคืนค่า True ถ้าไม่จริง คืนค่า False}

ฟังก์ชัน Full stack                                                                                                                                              FullStack : เป็นการดำเนินการเพื่อตรวจสอบว่าสแตกนั้นเต็มหรือไม่  ดำเนินการตรวจสอบเฉพาะข้อมูลอาร์เรย์ ต้องตรวจสอบว่า Top ของสแตกนั้นเป็นค่าสูงสุดที่ขอไว้หรือไม่

                                                  FullStack := Stack.top := MaxStack;

ฟังก์ชัน push stack                                                                                                                                            เป็นการทำงานของสแตกในการนำข้อมูลเข้าสู่สแตกโดยก่อนที่จะนำข้อมูลเข้านั้นต้องจัดการให้ตัวชี้สแตกให้ไปชี้ในตำแหน่งต่อไปของสแตกก่อน

ฟังก์ชัน push stack                                                                                                                                           ในกรณีที่ Push ข้อมูลลงสู่สแตกจนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ Push ข้อมูลได้อีก จะเกิด Error ที่เรียกว่า Stack Overflow

อัลกอริทึมในการ push stack

1. ตรวจสอบว่าสแตกเต็มหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดของตัวแปรอาร์เรย์ที่ใช้เก็บ ถ้าไม่เต็ม ทำข้อ 2. ถ้าเต็ม ทำข้อ 4.

2. ขยับตำแหน่ง Top ไปยังตำแหน่งถัดไป (Top = Top +1)

3. ทำการนำค่าที่ได้มาเก็บไว้ยังตำแหน่งของ Top {push(value,stack);}

4. แจ้งผู้ใช้งานว่า สแตกเต็มไม่สามารถเก็บข้อมูลได้

5.จบการทำงาน

ฟังก์ชัน pop stack                                                                                                                                           เป็นการทำงานของสแตกที่นำข้อมูลที่เก็บอยู่ในสแตกออกจากสแตกมาใช้งาน เมื่อทำการ Pop ข้อมูลออกจากสแตกแล้วต้องมีการจัดการตัวชี้สแตกให้ชี้ไปยังช่องหรือตำแหน่งก่อนหน้าข้อมูลที่ได้ทำการ

Pop ออกไป   

     การ Pop ข้อมูล จะนำข้อมูลส่วนบนสุดของสแตกออกไปทำงานตามความต้องการ แต่ไม่สามารถ Pop ข้อมูลออกจากสแตกที่ว่างเปล่าได้ เพราะจะเกิด Error ที่เรียกว่า Stack Underflow

อัลกอริทึม pop stack

1. ตรวจสอบว่าสแตกว่างหรือไม่โดยเปรียบเทียบค่าTopว่ามีค่าเท่ากับ-1หรือไม่ถ้าไม่ว่างทำข้อ2.ถ้าว่างทำข้อ 4.isEmpty(stack)

2. ทำการดึงค่าในตำแหน่งของ Top ออกมาใช้งาน pop(stack)

3. ขยับตำแหน่ง Top ให้ถอยหลังลงมา (Top = Top-1) ไปทำข้อ 5.

4. ผู้ใช้งานว่า สแตกว่างไม่สามารถดึงข้อมูลไปใช้งานได้

5. จบการทำงาน

การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix                                                                                                                             Infix คือ นิพจน์ที่มีตัวดำเนินการ (Operator) อยู่ระหว่างตัวถูกกระทำ (Operand) เช่น A + B เครื่องหมาย  +  เป็นโอเปอเรเตอร์ระหว่างโอเปอร์แรนด์  A และ  B  ซึ่งเห็น ว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่าง ๆ เรียงตามลำดับการดำเนินการก่อนหลัง (precedence) ได้แก่

ยกกำลัง ^

คูณ หาร * , /

บวก ลบ + , -

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

การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix                                                                                                                                     ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยาก คือ ลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^) มีความสำคัญมากกว่า เครื่องหมายคูณ (*) และหาร (/) และเครื่องหมายคูณและหารมี ความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-)  เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ)   เช่น  A +  B * C เครื่องจะคำนวณ  B * C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า A ซึ่งจะทำงานเหมือน กับ  A + (B * C)  ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับ ความสำคัญเท่ากัน การคำนวณจะกระทำจากซ้ายไปขวา เช่น  A – B + C จะทำ  A – B ก่อน  แล้วจึงนำผลลัพธ์นั้นไปบวกกับ ค่า  C

นิพจน์ Infix, Postfix                                                                                                                                                                          เมื่อการประมวลผลนิพจน์ infix เป็นไปด้วยความยากที่ การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น นิพจน์ postfix เสียก่อน ซึ่งนิพจน์ postfix  คือนิพจน์ที่มีโอเปอร์เรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น

 AB+    หมายถึง           A + B              AB/      หมายถึง           A / B

AB-                             A – B               AB^                             A ^ B

AB*                             A * B  

นิพจน์ Infix, Postfix                                                                                                                                                                          ข้อดีของนิพจน์ postfix คือเป็นนิพจน์ที่มีการคำนวณตาม โอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์ ABC*+  หมายถึง ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ A ต่อไป

กฎการแปลงนิพจน์ Infix, Postfix ด้วยมือ

1. ให้ใส่เครื่องหมายวงเล็บให้กับทุก ๆ นิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ

2. ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix

3. ถอดเครื่องหมายวงเล็บทิ้งให้หมด

กฎการแปลงนิพจน์ Infix, Postfix ด้วยมือ

จงแปลงนิพจน์ A + B * C มาเป็นนิพจน์ Postfix ด้วยมือ

1. ใส่วงเล็บให้หมดตามลำดับความสำคัญ    (A + (B*C) )

2. พิจารณานิพจน์ที่อยู่วงเล็บในสุด โดยย้ายเครื่องหมาย * ไปข้างหลัง C                                                                                                                                  (A + (BC*))                                                                                                                                   จากนั้นย้ายโอเปอเรเตอร์ + ซึ่งอยู่ที่ตำแหน่งวงเล็บเปิดภายนอกไปยังตำแหน่งวงเล็บปิดภายนอกของคู่ตัวเอง                                                                              (A(BC*)+)

ถอดเครื่องหมายวงเล็บทิ้งออกให้หมด     ABC*+

การนำสแตกมาใช้ในการแปลงนิพจน์ Infix, Postfix

1. ถ้าค่า input เป็น operand ให้นำค่าไปเป็น Output

2. ถ้าค่า input เป็น operator (เครื่องหมายคณิตศาสตร์) ให้พิจารณาดังนี้

 3. ถ้า สแตกว่าง ให้นำ operator ใส่สแตก

4. ถ้า สแตกไม่ว่าง ให้นำ operator ไปเปรียบกับค่า operator ตัวบนในสแตก ถ้าค่า operator ที่เป็น input มีค่า precedence น้อยกว่าหรือเท่ากับค่า operator ตัวบนของสแตก ให้ดึง operator ตัวบนในสแตกไปเป็น output แล้วเปรียบเทียบกับ operator ในสแตกตัวถัดไป แล้วเปรียบเทียบ

5. ถ้า input เป็น (  ให้ใส่ลงสแตก

6. ถ้าinput เป็น ) ให้ดึงข้อมูลออกจากสแตกทีละตัวไปเป็น output จนกระทั่งพบ (ในสแตกให้ดึงออกมาทิ้งไปไม่ต้องไปใส่เป็นoutput

7. ถ้า input หมด และสแตกยังมีข้อมูลอยู่ ให้ดึงข้อมูลออกจาก stack ที่ตัวไปเป็น output จนกระทั่งสแตกว่าง

บทที่ 3 ลิงค์ลิสต์ Linklist

โครงสร้างข้อมูล Linklist

       จากการทำงานของโครงสร้างข้อมูลอาร์เรย์ (Array Structure) , โครงสร้างข้อมูลสแตก (Stack Structure) และโครงสร้างข้อมูลคิว (Queue Structure) มีลักษณะการจัดเก็บข้อมูลและการเข้าถึงข้อมูลในโครงสร้างแบบลำดับเป็นพื้นที่ต่อเนื่องกัน  การใช้งานของโครงสร้างถูกจำกัดไว้ไม่สามารถทำการปรับเปลี่ยนหรือแก้ไขขนาดของโครงสร้างได้หรือหากต้องการปรับเปลี่ยนโครงสร้างใหม่ จะทำให้เสียเวลาในการประมวลผล ซึ่งในการใช้งานโปรแกรมพื้นที่หน่วยความจำ (Memory) เป็นสิ่งจำเป็นมาก การแก้ไขปัญหาดังกล่าว โดยใช้โครงสร้างข้อมูลแบบอื่น ๆ เป็นสิ่งจำเป็นที่ต้องพิจารณาและยากมาก

   โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่า สมาชิก ( Node) ส่วน เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป (Link)

                            

คุณสมบัติของลิงค์ลิสต์

       ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์ แทน

• โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link โดย

   - Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์

   - Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป

• ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด

• ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน

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

• ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อาร์เรย์

• กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง

ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด

โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วยโหนดต่างๆต่อกันโดยแต่ละโหนดมีส่วนที่สำคัญ 2 ส่วนคือ ส่วนที่เก็บข้อมูล (Data) และ ส่วนที่เก็บตัวชี้ (Pointer)

ข้อดีของลิงค์ลิสต์

1. เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล

2. ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์

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

การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์

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

การเข้าถึงในโครงสร้างเรียกว่า การทำ Traversing มีขั้นตอนดังต่อไปนี้

กำหนดให้ DATA เป็นโครงสร้างข้อมูลลิงค์ลิสต์   และพอยน์เตอร์  PTR ทำหน้าที่ชี้โหนดที่กำลังดำเนินการ  Process  อยู่ในขณะนั้น  (Current Node)

1. กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์  PTR.

2. การวนรอบดำเนินการ   Process  ข้อมูล

3. Apply Process to DATA [PTR]

4. เปลี่ยนค่าพอยน์เตอร์  PTR ให้ชี้โหนดถัดไป

5. เสร็จสิ้นขั้นตอน

การเพิ่มข้อมูลในโครงสร้าง

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

การเพิ่มข้อมูลในโครงสร้างข้อมูลลิงค์ลิสต์ อาจเกิดในลักษณะที่ต่างกัน ซึ่งสรุปได้เป็น 3 ลักษณะ  คือ

1. การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง

2. การเพิ่มข้อมูลต่อจากโหนดที่กำหนด

3. การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง

การลบข้อมูลจากโครงสร้าง

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

การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์ เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้

1. การลบโหนดแรก

 2. การลบโหนดที่อยู่หลังโหนดที่กำหนด

3. การลบโหนดสุดท้าย

ขั้นตอนการลบโหนดมีดังนี้

1. เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการล

2. กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น

3. กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool