โครงสร้างข้อมูลใน C คืออะไรและใช้งานอย่างไร

บทนำ

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

ประเภท

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

แอปพลิเคชั่น

ในการออกแบบคอมไพเลอร์ ระบบปฏิบัติการ การสร้างฐานข้อมูล แอพพลิเคชั่นปัญญาประดิษฐ์ และอื่นๆ อีกมากมาย

การจำแนกประเภท

โครงสร้างข้อมูลแบ่งออกเป็นสองประเภท: โครงสร้างข้อมูลดั้งเดิมและโครงสร้างข้อมูลที่ไม่ใช่พื้นฐาน

1. Primitive: เป็นประเภทข้อมูลพื้นฐานที่รองรับโดยภาษาโปรแกรม ตัวอย่างทั่วไปของการจัดหมวดหมู่นี้คือจำนวนเต็ม อักขระ และบูลีน

2. Non-Primitive: โครงสร้างข้อมูลประเภทเหล่านี้สร้างขึ้นโดยใช้โครงสร้างข้อมูลดั้งเดิม ตัวอย่าง ได้แก่ สแต็คที่เชื่อมโยง รายการที่เชื่อมโยง กราฟ และต้นไม้

อาร์เรย์

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

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

ประกาศอาร์เรย์

ใน C สามารถประกาศอาร์เรย์เป็น:

ชื่อ data_type[ความยาว];

ตัวอย่างเช่น,

คำสั่งภายใน[10];

บรรทัดของโค้ดด้านบนสร้างอาร์เรย์ของบล็อกหน่วยความจำ 10 บล็อก ซึ่งสามารถเก็บค่าจำนวนเต็มได้ ใน C ค่าดัชนีอาร์เรย์เริ่มต้นจาก 0 ดังนั้นค่าดัชนีจะอยู่ในช่วงตั้งแต่ 0 ถึง 9 หากเราต้องการเข้าถึงค่าใด ๆ ในอาร์เรย์นั้น เราเพียงแค่พิมพ์:

printf(คำสั่งซื้อ[index_number]);

อีกวิธีในการประกาศอาร์เรย์มีดังนี้:

data_type array_name[ขนาด]={รายการค่า};

ตัวอย่างเช่น,

เครื่องหมาย int[5]={9, 8, 7, 9, 8};

บรรทัดคำสั่งด้านบนสร้างอาร์เรย์ที่มีบล็อกหน่วยความจำ 5 บล็อกพร้อมค่าคงที่ในแต่ละบล็อก บนคอมไพเลอร์ 32 บิต หน่วยความจำ 32 บิตที่ใช้โดยประเภทข้อมูล int คือ 4 ไบต์ ดังนั้นหน่วยความจำ 5 บล็อกจะใช้หน่วยความจำ 20 ไบต์

อีกวิธีที่ถูกต้องในการเริ่มต้นอาร์เรย์คือ:

เครื่องหมาย int [5] = {9 , 45};

คำสั่งนี้จะสร้างอาร์เรย์ 5 บล็อก โดย 3 บล็อกสุดท้ายจะมีค่าเป็น 0

อีกวิธีที่ถูกต้องตามกฎหมายคือ:

เครื่องหมาย int [] = {9 , 5, 2, 1, 3,4};

คอมไพเลอร์ C เข้าใจดีว่าจำเป็นต้องมีเพียง 5 บล็อกเพื่อให้พอดีกับข้อมูลเหล่านี้ในอาร์เรย์ ดังนั้นจะเริ่มต้นอาร์เรย์ของเครื่องหมายชื่อขนาด 5

ในทำนองเดียวกัน อาร์เรย์ 2 มิติสามารถเริ่มต้นได้ด้วยวิธีต่อไปนี้

เครื่องหมาย int[2][3]={{9,7,7},{6, 2, 1}};

คำสั่งดังกล่าวจะสร้างอาร์เรย์ 2 มิติที่มี 2 แถว 3 คอลัมน์

อ่าน: แนวคิดและหัวข้อโครงการโครงสร้างข้อมูล

ปฏิบัติการ

มีการดำเนินการบางอย่างที่สามารถทำได้บนอาร์เรย์ ตัวอย่างเช่น:

1. ข้ามอาร์เรย์
2. การแทรกองค์ประกอบในอาร์เรย์
3. ค้นหาองค์ประกอบเฉพาะในอาร์เรย์
4. การลบองค์ประกอบเฉพาะออกจากอาร์เรย์
5. รวมสองอาร์เรย์และ
6. การเรียงลำดับอาร์เรย์ — เรียงลำดับจากน้อยไปมากหรือมากไปหาน้อย

ข้อเสีย

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

รายการที่เชื่อมโยง

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

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

แหล่งที่มา

การเริ่มต้นรายการที่เชื่อมโยง

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

โหนดโครงสร้าง

{

ข้อมูลภายใน;

โหนดโครงสร้าง *ถัดไป;

};

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

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

รายการเชื่อมโยงข้ามผ่าน

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

การเพิ่มโหนด

อัลกอริทึมในการเพิ่มโหนดก่อนโหนดเฉพาะจะเป็นดังนี้:

1. ตั้งค่าตัวชี้จำลองสองตัว (ptr และ preptr) ที่ชี้ไปที่หัวในตอนแรก
2. ย้าย ptr จนกระทั่ง ptr.data เท่ากับ data ก่อนที่เราจะทำการแทรกโหนด preptr จะเป็น 1 โหนดหลัง ptr
3. สร้างโหนด
4. โหนดที่จำลอง preptr ชี้ โหนดถัดไปของโหนดจะชี้ไปที่โหนดใหม่นี้
5. โหนดใหม่ถัดไปจะชี้ไปที่ ptr

อัลกอริทึมสำหรับการเพิ่มโหนดหลังจากข้อมูลเฉพาะจะทำในลักษณะเดียวกัน

ข้อดีของรายการเชื่อมโยง

1. ขนาดไดนามิกไม่เหมือนกับอาร์เรย์
2. การแทรกและการลบทำได้ง่ายกว่าในรายการที่เชื่อมโยงมากกว่าในอาร์เรย์

คิว

คิวตามระบบประเภทเข้าก่อนออกก่อนหรือแบบ FIFO ในการใช้งานอาร์เรย์ เราจะมีตัวชี้สองตัวเพื่อแสดงกรณีการใช้งานของ Queue

แหล่งที่มา

FIFO โดยทั่วไปหมายความว่าค่าที่เข้าสู่สแต็กก่อนออกจากอาร์เรย์ก่อน ในแผนภาพคิวด้านบน ด้านหน้าของตัวชี้จะชี้ไปที่ค่า 7 หากเราลบบล็อกแรก (dequeue) ส่วนหน้าจะชี้ไปที่ค่า 2 ในทำนองเดียวกัน หากเราป้อนตัวเลข (enqueue) ให้พูดว่า 3 ใน ตำแหน่ง 5 จากนั้นตัวชี้ด้านหลังจะชี้ไปที่ตำแหน่ง 5

สภาวะล้นและอันเดอร์โฟลว์

อย่างไรก็ตาม ก่อนป้อนค่าข้อมูลในคิว เราต้องตรวจสอบเงื่อนไขโอเวอร์โฟลว์ โอเวอร์โฟลว์จะเกิดขึ้นเมื่อมีการพยายามแทรกองค์ประกอบลงในคิวที่เต็มแล้ว คิวจะเต็มเมื่อด้านหลัง = max_size–1

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

ซ้อนกัน

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

หากเราต้องการใส่องค์ประกอบ (พุช) ในอาร์เรย์ ตัวชี้บนจะเลื่อนขึ้นหรือเพิ่มขึ้นทีละ 1 หากเราต้องการลบองค์ประกอบหนึ่ง (ป๊อป) ตัวชี้บนสุดจะลดลง 1 หน่วยหรือลดลง 1 หน่วย สแต็กรองรับการทำงานพื้นฐานสามอย่าง: พุช ป๊อป และมองลอด การดำเนินการ Peep เป็นเพียงการแสดงองค์ประกอบบนสุดในสแต็ก

แหล่งที่มา

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

บทสรุป

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

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับ Javascript, การพัฒนาแบบฟูลสแตก, ลองดูโปรแกรม Executive PG ของ upGrad & IIIT-B ในการพัฒนาซอฟต์แวร์แบบครบวงจร ซึ่งออกแบบมาสำหรับมืออาชีพที่ทำงานและมีการฝึกอบรมที่เข้มงวดมากกว่า 500 ชั่วโมง, โครงการมากกว่า 9 โครงการ และการมอบหมายงาน สถานะศิษย์เก่า IIIT-B โครงการหลักและความช่วยเหลือด้านงานกับบริษัทชั้นนำ