โครงสร้างข้อมูลและอัลกอริทึม - คู่มือฉบับย่อ

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

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

ลักษณะของโครงสร้างข้อมูล

Correctness - การใช้โครงสร้างข้อมูลควรใช้อินเทอร์เฟซอย่างถูกต้อง
Time Complexity - เวลาในการทำงานหรือเวลาดำเนินการของการดำเนินการของโครงสร้างข้อมูลต้องน้อยที่สุด
Space Complexity - การใช้หน่วยความจำของการดำเนินการโครงสร้างข้อมูลควรน้อยที่สุด

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

เนื่องจากแอปพลิเคชันมีความซับซ้อนและมีข้อมูลมากมายจึงมีปัญหาทั่วไปสามประการที่แอปพลิเคชันต้องเผชิญอยู่ในขณะนี้

Data Search- พิจารณาสินค้าคงคลัง 1 ล้านรายการ (10 ⁶ ) รายการของร้านค้า หากแอปพลิเคชันต้องการค้นหารายการจะต้องค้นหารายการใน 1 ล้านรายการ (10 ⁶ ) รายการทุกครั้งที่ทำให้การค้นหาช้าลง เมื่อข้อมูลเติบโตขึ้นการค้นหาจะช้าลง
Processor speed - ความเร็วของโปรเซสเซอร์แม้ว่าจะสูงมาก แต่ก็มีข้อ จำกัด หากข้อมูลเพิ่มขึ้นเป็นพันล้านบันทึก
Multiple requests - เนื่องจากผู้ใช้หลายพันคนสามารถค้นหาข้อมูลพร้อมกันบนเว็บเซิร์ฟเวอร์แม้เซิร์ฟเวอร์ที่รวดเร็วจะล้มเหลวในขณะค้นหาข้อมูล

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

กรณีเวลาดำเนินการ

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

Worst Case- นี่คือสถานการณ์จำลองที่การดำเนินการโครงสร้างข้อมูลโดยเฉพาะต้องใช้เวลาสูงสุด หากเวลาที่เลวร้ายที่สุดของการดำเนินการคือƒ (n) การดำเนินการนี้จะใช้เวลาไม่เกินƒ (n) โดยที่ƒ (n) แสดงถึงฟังก์ชันของ n
Average Case- นี่คือสถานการณ์จำลองที่แสดงเวลาดำเนินการโดยเฉลี่ยของการดำเนินการของโครงสร้างข้อมูล หากการดำเนินการใช้เวลาในการดำเนินการƒ (n) การดำเนินการ m จะใช้เวลาmƒ (n)
Best Case- นี่คือสถานการณ์จำลองที่แสดงเวลาการดำเนินการที่น้อยที่สุดที่เป็นไปได้ของการดำเนินการของโครงสร้างข้อมูล หากการดำเนินการใช้เวลาในการดำเนินการƒ (n) การดำเนินการจริงอาจใช้เวลาเป็นจำนวนสุ่มซึ่งจะมีค่าสูงสุดเป็นƒ (n)

คำศัพท์พื้นฐาน

Data - ข้อมูลคือค่าหรือชุดของค่า
Data Item - รายการข้อมูลหมายถึงหน่วยค่าเดียว
Group Items - รายการข้อมูลที่แบ่งออกเป็นรายการย่อยเรียกว่ารายการกลุ่ม
Elementary Items - รายการข้อมูลที่ไม่สามารถแบ่งได้จะถูกเรียกว่าเป็นรายการพื้นฐาน
Attribute and Entity - เอนทิตีคือสิ่งที่มีคุณลักษณะหรือคุณสมบัติบางอย่างซึ่งอาจถูกกำหนดค่า
Entity Set - เอนทิตีของแอตทริบิวต์ที่คล้ายกันสร้างชุดเอนทิตี
Field - ฟิลด์เป็นหน่วยข้อมูลพื้นฐานหน่วยเดียวที่แสดงถึงคุณลักษณะของเอนทิตี
Record - บันทึกคือชุดของค่าฟิลด์ของเอนทิตีที่กำหนด
File - ไฟล์คือชุดของบันทึกของเอนทิตีในชุดเอนทิตีที่กำหนด

ลองใช้ตัวเลือกออนไลน์

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

ลองใช้ตัวอย่างต่อไปนี้โดยใช้ไฟล์ Try it ตัวเลือกที่มุมขวาบนของกล่องโค้ดตัวอย่าง -

#include <stdio.h>
int main(){
   /* My first program in C */
   printf("Hello, World! \n");
   return 0;
}

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

การตั้งค่าสภาพแวดล้อมท้องถิ่น

หากคุณยังเต็มใจที่จะตั้งค่าสภาพแวดล้อมของคุณสำหรับการเขียนโปรแกรมภาษา C คุณต้องมีเครื่องมือสองตัวต่อไปนี้ที่มีอยู่ในคอมพิวเตอร์ของคุณ (a) Text Editor และ (b) The C Compiler

แก้ไขข้อความ

สิ่งนี้จะใช้ในการพิมพ์โปรแกรมของคุณ ตัวอย่างของตัวแก้ไขบางตัว ได้แก่ Windows Notepad, OS Edit command, Brief, Epsilon, EMACS และ vim หรือ vi

ชื่อและเวอร์ชันของโปรแกรมแก้ไขข้อความอาจแตกต่างกันไปตามระบบปฏิบัติการต่างๆ ตัวอย่างเช่น Notepad จะใช้กับ Windows และสามารถใช้ vim หรือ vi บน Windows ได้เช่นเดียวกับ Linux หรือ UNIX

ไฟล์ที่คุณสร้างด้วยโปรแกรมแก้ไขเรียกว่าไฟล์ต้นฉบับและมีซอร์สโค้ดของโปรแกรม โดยทั่วไปไฟล์ต้นฉบับสำหรับโปรแกรม C จะมีนามสกุลว่า ".c".

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

คอมไพเลอร์ C

ซอร์สโค้ดที่เขียนในไฟล์ต้นฉบับเป็นซอร์สที่มนุษย์สามารถอ่านได้สำหรับโปรแกรมของคุณ ต้องมีการ "คอมไพล์" เพื่อเปลี่ยนเป็นภาษาเครื่องเพื่อให้ CPU ของคุณสามารถรันโปรแกรมได้จริงตามคำแนะนำที่กำหนด

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

คอมไพเลอร์ที่ใช้บ่อยและฟรีที่มีอยู่คือคอมไพเลอร์ GNU C / C ++ มิฉะนั้นคุณสามารถมีคอมไพเลอร์จาก HP หรือ Solaris หากคุณมีระบบปฏิบัติการ (OS) ที่เกี่ยวข้อง

ส่วนต่อไปนี้จะแนะนำวิธีการติดตั้งคอมไพเลอร์ GNU C / C ++ บน OS ต่างๆ เรากำลังพูดถึง C / C ++ ด้วยกันเนื่องจาก GNU GCC คอมไพเลอร์ทำงานได้ทั้งภาษาโปรแกรม C และ C ++

การติดตั้งบน UNIX / Linux

หากคุณกำลังใช้ Linux or UNIXจากนั้นตรวจสอบว่ามีการติดตั้ง GCC ในระบบของคุณหรือไม่โดยป้อนคำสั่งต่อไปนี้จากบรรทัดคำสั่ง -

$ gcc -v

หากคุณติดตั้งคอมไพเลอร์ GNU ไว้ในเครื่องของคุณควรพิมพ์ข้อความดังต่อไปนี้ -

Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix = /usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)

หากไม่ได้ติดตั้ง GCC คุณจะต้องติดตั้งด้วยตัวเองโดยใช้คำแนะนำโดยละเอียดที่มีอยู่ที่ https://gcc.gnu.org/install/

บทช่วยสอนนี้เขียนขึ้นโดยใช้ Linux และตัวอย่างทั้งหมดได้รับการรวบรวมบน Cent OS รสชาติของระบบ Linux

การติดตั้งบน Mac OS

หากคุณใช้ Mac OS X วิธีที่ง่ายที่สุดในการรับ GCC คือดาวน์โหลดสภาพแวดล้อมการพัฒนา Xcode จากเว็บไซต์ของ Apple และทำตามคำแนะนำในการติดตั้งอย่างง่าย เมื่อคุณตั้งค่า Xcode แล้วคุณจะสามารถใช้คอมไพเลอร์ GNU สำหรับ C / C ++ ได้

ขณะนี้ Xcode มีให้บริการที่developer.apple.com/technologies/tools/

การติดตั้งบน Windows

ในการติดตั้ง GCC บน Windows คุณต้องติดตั้ง MinGW ในการติดตั้ง MinGW ให้ไปที่โฮมเพจ MinGW www.mingw.orgและไปที่ลิงค์ไปยังหน้าดาวน์โหลด MinGW ดาวน์โหลดโปรแกรมติดตั้ง MinGW เวอร์ชันล่าสุดซึ่งควรมีชื่อว่า MinGW- <version> .exe

ในขณะติดตั้ง MinWG อย่างน้อยคุณต้องติดตั้ง gcc-core, gcc-g ++, binutils และรันไทม์ MinGW แต่คุณอาจต้องการติดตั้งเพิ่มเติม

เพิ่มไดเร็กทอรีย่อย bin ของการติดตั้ง MinGW ของคุณไปยังไฟล์ PATH ตัวแปรสภาพแวดล้อมเพื่อให้คุณสามารถระบุเครื่องมือเหล่านี้ในบรรทัดคำสั่งโดยใช้ชื่อง่าย ๆ

เมื่อการติดตั้งเสร็จสมบูรณ์คุณจะสามารถเรียกใช้ gcc, g ++, ar, ranlib, dlltool และเครื่องมือ GNU อื่น ๆ จากบรรทัดคำสั่งของ Windows

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

จากมุมมองโครงสร้างข้อมูลต่อไปนี้เป็นหมวดหมู่ที่สำคัญของอัลกอริทึม -

Search - อัลกอริทึมเพื่อค้นหารายการในโครงสร้างข้อมูล
Sort - อัลกอริทึมเพื่อจัดเรียงรายการตามลำดับที่กำหนด
Insert - อัลกอริทึมเพื่อแทรกรายการในโครงสร้างข้อมูล
Update - อัลกอริทึมเพื่ออัปเดตรายการที่มีอยู่ในโครงสร้างข้อมูล
Delete - อัลกอริทึมเพื่อลบรายการที่มีอยู่ออกจากโครงสร้างข้อมูล

ลักษณะของอัลกอริทึม

ขั้นตอนทั้งหมดไม่สามารถเรียกได้ว่าเป็นอัลกอริทึม อัลกอริทึมควรมีลักษณะดังต่อไปนี้ -

Unambiguous- อัลกอริทึมควรชัดเจนและไม่คลุมเครือ แต่ละขั้นตอน (หรือเฟส) และอินพุต / เอาต์พุตควรชัดเจนและต้องนำไปสู่ความหมายเดียวเท่านั้น
Input - อัลกอริทึมควรมีอินพุตที่กำหนดไว้อย่างดี 0 หรือมากกว่า
Output - อัลกอริทึมควรมีเอาต์พุตที่กำหนดไว้อย่างดี 1 รายการขึ้นไปและควรตรงกับเอาต์พุตที่ต้องการ
Finiteness - อัลกอริทึมต้องยุติหลังจากขั้นตอนที่ จำกัด จำนวน
Feasibility - ควรเป็นไปได้ด้วยทรัพยากรที่มีอยู่
Independent - อัลกอริทึมควรมีคำแนะนำทีละขั้นตอนซึ่งควรเป็นอิสระจากรหัสโปรแกรมใด ๆ

วิธีการเขียนอัลกอริทึม?

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

อย่างที่เราทราบกันดีว่าภาษาโปรแกรมทั้งหมดใช้โครงสร้างโค้ดพื้นฐานร่วมกันเช่นลูป (do, for, while), โฟลว์คอนโทรล (if-else) เป็นต้นโครงสร้างทั่วไปเหล่านี้สามารถใช้ในการเขียนอัลกอริทึม

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

ตัวอย่าง

มาลองเรียนรู้การเขียนอัลกอริทึมโดยใช้ตัวอย่าง

Problem - ออกแบบอัลกอริทึมเพื่อเพิ่มตัวเลขสองตัวและแสดงผลลัพธ์

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

อัลกอริทึมบอกโปรแกรมเมอร์ถึงวิธีการเขียนโค้ดโปรแกรม หรืออีกวิธีหนึ่งคืออัลกอริทึมสามารถเขียนเป็น -

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

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

การเขียน step numbersเป็นทางเลือก

เราออกแบบอัลกอริทึมเพื่อหาวิธีแก้ปัญหาที่กำหนด ปัญหาสามารถแก้ไขได้มากกว่าหนึ่งวิธี

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

การวิเคราะห์อัลกอริทึม

ประสิทธิภาพของอัลกอริทึมสามารถวิเคราะห์ได้ในสองขั้นตอนที่แตกต่างกันก่อนการใช้งานและหลังการใช้งาน มีดังต่อไปนี้ -

A Priori Analysis- นี่คือการวิเคราะห์ทางทฤษฎีของอัลกอริทึม ประสิทธิภาพของอัลกอริทึมวัดได้โดยสมมติว่าปัจจัยอื่น ๆ ทั้งหมดเช่นความเร็วของโปรเซสเซอร์มีค่าคงที่และไม่มีผลต่อการนำไปใช้งาน
A Posterior Analysis- นี่คือการวิเคราะห์เชิงประจักษ์ของอัลกอริทึม อัลกอริทึมที่เลือกใช้งานโดยใช้ภาษาโปรแกรม จากนั้นจะดำเนินการในเครื่องคอมพิวเตอร์เป้าหมาย ในการวิเคราะห์นี้จะมีการรวบรวมสถิติจริงเช่นเวลาทำงานและพื้นที่ที่ต้องการ

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

ความซับซ้อนของอัลกอริทึม

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

Time Factor - เวลาถูกวัดโดยการนับจำนวนการดำเนินการหลักเช่นการเปรียบเทียบในอัลกอริทึมการเรียงลำดับ
Space Factor - พื้นที่ถูกวัดโดยการนับพื้นที่หน่วยความจำสูงสุดที่อัลกอริทึมต้องการ

ความซับซ้อนของอัลกอริทึม f(n) ให้เวลาทำงานและ / หรือพื้นที่จัดเก็บที่อัลกอริทึมต้องการในแง่ของ n เป็นขนาดของข้อมูลอินพุต

ความซับซ้อนของอวกาศ

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

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

ความซับซ้อนของพื้นที่ S (P) ของอัลกอริทึมใด ๆ P คือ S (P) = C + SP (I) โดยที่ C เป็นส่วนคงที่และ S (I) เป็นส่วนตัวแปรของอัลกอริทึมซึ่งขึ้นอยู่กับลักษณะของอินสแตนซ์ I ต่อไปนี้ เป็นตัวอย่างง่ายๆที่พยายามอธิบายแนวคิด -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

ที่นี่เรามีสามตัวแปร A, B และ C และค่าคงที่หนึ่งค่า ดังนั้น S (P) = 1 + 3 ตอนนี้พื้นที่ขึ้นอยู่กับประเภทข้อมูลของตัวแปรที่กำหนดและประเภทค่าคงที่และจะคูณตามนั้น

ความซับซ้อนของเวลา

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

ตัวอย่างเช่นการเพิ่มจำนวนเต็ม n-bit สองตัวจะใช้ nขั้นตอน ดังนั้นเวลาในการคำนวณทั้งหมดคือ T (n) = c ∗ n โดยที่ c คือเวลาที่ใช้ในการบวกสองบิต ที่นี่เราสังเกตว่า T (n) เติบโตเป็นเชิงเส้นเมื่อขนาดอินพุตเพิ่มขึ้น

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

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

การวิเคราะห์ Asymptotic หมายถึงการคำนวณเวลาทำงานของการดำเนินการใด ๆ ในหน่วยคำนวณทางคณิตศาสตร์ ตัวอย่างเช่นเวลาทำงานของการดำเนินการหนึ่งคำนวณเป็นf (n) และอาจเป็นสำหรับการดำเนินการอื่นที่คำนวณเป็นg (n ² ) ซึ่งหมายความว่าเวลาทำงานของการดำเนินการครั้งแรกจะเพิ่มขึ้นในเชิงเส้นเมื่อเพิ่มขึ้นn และเวลาทำงานของการดำเนินการที่สองจะเพิ่มขึ้นแบบทวีคูณเมื่อ nเพิ่มขึ้น ในทำนองเดียวกันเวลาทำงานของการดำเนินการทั้งสองจะใกล้เคียงกันถ้าn มีขนาดเล็กมาก

โดยปกติเวลาที่อัลกอริทึมต้องการจะอยู่ภายใต้สามประเภท -

Best Case - เวลาขั้นต่ำที่จำเป็นสำหรับการทำงานของโปรแกรม
Average Case - เวลาเฉลี่ยที่ต้องใช้ในการทำงานของโปรแกรม
Worst Case - ระยะเวลาสูงสุดที่จำเป็นสำหรับการทำงานของโปรแกรม

สัญกรณ์ Asymptotic

ต่อไปนี้เป็นสัญกรณ์ asymptotic ที่ใช้กันทั่วไปในการคำนวณความซับซ้อนของเวลาทำงานของอัลกอริทึม

Οสัญกรณ์
Ωสัญกรณ์
θสัญกรณ์

สัญกรณ์ Big Oh, Ο

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

ตัวอย่างเช่นสำหรับฟังก์ชัน f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

สัญกรณ์ Omega, Ω

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

ตัวอย่างเช่นสำหรับฟังก์ชัน f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

สัญลักษณ์ Theta, θ

สัญกรณ์θ (n) เป็นวิธีที่เป็นทางการในการแสดงทั้งขอบเขตล่างและขอบเขตบนของเวลาทำงานของอัลกอริทึม มันแสดงดังนี้ -

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

สัญกรณ์ Asymptotic ทั่วไป

ต่อไปนี้เป็นรายการสัญกรณ์ asymptotic ทั่วไป -

คงที่	-	Ο (1)
ลอการิทึม	-	Ο (บันทึก n)
เชิงเส้น	-	Ο (n)
n log n	-	Ο (n บันทึก n)
กำลังสอง	-	Ο (n ² )
ลูกบาศก์	-	Ο (n ³ )
พหุนาม	-	n ^{Ο (1)}
เลขชี้กำลัง	-	2 ^{Ο (น)}

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

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

การนับเหรียญ

ปัญหานี้คือการนับเป็นมูลค่าที่ต้องการโดยการเลือกเหรียญที่น้อยที่สุดและวิธีการโลภบังคับให้อัลกอริทึมเลือกเหรียญที่ใหญ่ที่สุด หากเราได้รับเหรียญ₹ 1, 2, 5 และ 10 และเราขอให้นับ₹ 18 ขั้นตอนโลภจะเป็น -

1 - เลือกหนึ่ง₹ 10 เหรียญจำนวนที่เหลือคือ 8
2 - จากนั้นเลือกหนึ่งเหรียญ₹ 5 จำนวนที่เหลือคือ 3
3 - จากนั้นเลือกหนึ่งเหรียญ₹ 2 จำนวนที่เหลือคือ 1
4 - และสุดท้ายการเลือกเหรียญ₹ 1 หนึ่งเหรียญจะช่วยแก้ปัญหาได้

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

สำหรับระบบสกุลเงินที่เรามีเหรียญ 1, 7, 10 มูลค่าการนับเหรียญสำหรับมูลค่า 18 จะเหมาะสมที่สุด แต่สำหรับการนับเช่น 15 อาจใช้เหรียญมากกว่าที่จำเป็น ตัวอย่างเช่นวิธีโลภจะใช้ 10 + 1 + 1 + 1 + 1 + 1 รวม 6 เหรียญ ในขณะที่ปัญหาเดียวกันสามารถแก้ไขได้โดยใช้เพียง 3 เหรียญ (7 + 7 + 1)

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

ตัวอย่าง

อัลกอริธึมเครือข่ายส่วนใหญ่ใช้วิธีโลภ นี่คือรายการบางส่วนของพวกเขา -

ปัญหาพนักงานขายในการเดินทาง
อัลกอริทึมต้นไม้ที่มีระยะครอบคลุมน้อยที่สุดของ Prim
อัลกอริทึมต้นไม้ Spanning Tree น้อยที่สุดของ Kruskal
อัลกอริทึมต้นไม้ Spanning Tree น้อยที่สุดของ Dijkstra
กราฟ - การระบายสีแผนที่
กราฟ - ปกเวอร์เท็กซ์
ปัญหากระเป๋าเป้
ปัญหาการจัดตารางงาน

มีปัญหาคล้าย ๆ กันมากมายที่ใช้วิธีการโลภเพื่อค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุด

ในแนวทางการแบ่งแยกและพิชิตปัญหาในมือแบ่งออกเป็นปัญหาย่อยที่เล็กกว่าจากนั้นแต่ละปัญหาจะได้รับการแก้ไขอย่างอิสระ เมื่อเราแบ่งปัญหาย่อยออกเป็นปัญหาย่อย ๆ ไปเรื่อย ๆ ในที่สุดเราก็อาจถึงขั้นตอนที่ไม่มีการแบ่งแยกอีกต่อไป ปัญหาย่อย (เศษส่วน) "อะตอม" ที่เล็กที่สุดที่เป็นไปได้เหล่านั้นได้รับการแก้ไขแล้ว ในที่สุดการแก้ปัญหาย่อยทั้งหมดจะถูกรวมเข้าด้วยกันเพื่อให้ได้วิธีการแก้ปัญหาเดิม

ในวงกว้างเราสามารถเข้าใจได้ divide-and-conquer แนวทางในกระบวนการสามขั้นตอน

หาร / แบ่ง

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

พิชิต / แก้

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

ผสาน / รวม

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

ตัวอย่าง

อัลกอริทึมคอมพิวเตอร์ต่อไปนี้ขึ้นอยู่กับ divide-and-conquer แนวทางการเขียนโปรแกรม -

ผสานการเรียง
จัดเรียงด่วน
การค้นหาแบบไบนารี
การคูณเมทริกซ์ของ Strassen
คู่ที่ใกล้ที่สุด (คะแนน)

มีหลายวิธีในการแก้ปัญหาคอมพิวเตอร์ แต่วิธีการดังกล่าวเป็นตัวอย่างที่ดีของวิธีการแบ่งแยกและพิชิต

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

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

ดังนั้นเราสามารถพูดได้ว่า -

ปัญหาควรสามารถแบ่งออกเป็นปัญหาย่อยที่ทับซ้อนกันที่เล็กกว่าได้
วิธีแก้ปัญหาที่ดีที่สุดสามารถทำได้โดยใช้วิธีการแก้ปัญหาย่อยที่มีขนาดเล็กที่สุด
อัลกอริธึมแบบไดนามิกใช้ Memoization

การเปรียบเทียบ

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

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

ตัวอย่าง

ปัญหาคอมพิวเตอร์ต่อไปนี้สามารถแก้ไขได้โดยใช้วิธีการเขียนโปรแกรมแบบไดนามิก -

อนุกรมเลขฟีโบนักชี
ปัญหาเป้
หอคอยแห่งฮานอย
เส้นทางที่สั้นที่สุดของ Floyd-Warshall
เส้นทางที่สั้นที่สุดโดย Dijkstra
การจัดกำหนดการโครงการ

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

บทนี้จะอธิบายคำศัพท์พื้นฐานที่เกี่ยวข้องกับโครงสร้างข้อมูล

นิยามข้อมูล

นิยามข้อมูลกำหนดข้อมูลเฉพาะโดยมีลักษณะดังต่อไปนี้

Atomic - คำจำกัดความควรกำหนดแนวคิดเดียว
Traceable - คำจำกัดความควรสามารถจับคู่กับองค์ประกอบข้อมูลบางอย่างได้
Accurate - คำจำกัดความไม่ควรคลุมเครือ
Clear and Concise - คำจำกัดความควรเข้าใจได้

วัตถุข้อมูล

Data Object แสดงถึงออบเจ็กต์ที่มีข้อมูล

ประเภทข้อมูล

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

ประเภทข้อมูลในตัว
ประเภทข้อมูลที่ได้รับ

ประเภทข้อมูลในตัว

ประเภทข้อมูลที่ภาษามีการสนับสนุนในตัวเรียกว่าชนิดข้อมูลในตัว ตัวอย่างเช่นภาษาส่วนใหญ่มีชนิดข้อมูลในตัวต่อไปนี้

Integers
บูลีน (จริงเท็จ)
ลอย (เลขฐานสิบ)
อักขระและสตริง

ประเภทข้อมูลที่ได้รับ

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

List
Array
Stack
Queue

การทำงานขั้นพื้นฐาน

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

Traversing
Searching
Insertion
Deletion
Sorting
Merging

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

Element - แต่ละรายการที่จัดเก็บในอาร์เรย์เรียกว่าองค์ประกอบ
Index - แต่ละตำแหน่งขององค์ประกอบในอาร์เรย์มีดัชนีตัวเลขซึ่งใช้ในการระบุองค์ประกอบ

การเป็นตัวแทนอาร์เรย์

อาร์เรย์สามารถประกาศได้หลายวิธีในภาษาต่างๆ สำหรับภาพประกอบลองใช้การประกาศอาร์เรย์ C

ตามภาพประกอบด้านบนประเด็นสำคัญที่ต้องพิจารณาต่อไปนี้

ดัชนีเริ่มต้นด้วย 0
ความยาวอาร์เรย์คือ 10 ซึ่งหมายความว่าสามารถจัดเก็บองค์ประกอบได้ 10 ชิ้น
แต่ละองค์ประกอบสามารถเข้าถึงได้ผ่านทางดัชนี ตัวอย่างเช่นเราสามารถดึงองค์ประกอบที่ดัชนี 6 เป็น 9

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการพื้นฐานที่อาร์เรย์รองรับ

Traverse - พิมพ์องค์ประกอบอาร์เรย์ทั้งหมดทีละรายการ
Insertion - เพิ่มองค์ประกอบในดัชนีที่กำหนด
Deletion - ลบองค์ประกอบในดัชนีที่กำหนด
Search - ค้นหาองค์ประกอบโดยใช้ดัชนีที่กำหนดหรือตามค่า
Update - อัปเดตองค์ประกอบที่ดัชนีที่กำหนด

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

ประเภทข้อมูล	ค่าเริ่มต้น
บูล	เท็จ
ถ่าน	0
int	0
ลอย	0.0
สองเท่า	0.0f
เป็นโมฆะ
wchar_t	0

Traverse Operation

การดำเนินการนี้คือการสำรวจผ่านองค์ประกอบของอาร์เรย์

ตัวอย่าง

ต่อไปนี้โปรแกรมข้ามผ่านและพิมพ์องค์ประกอบของอาร์เรย์:

#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;   
   printf("The original array elements are :\n");
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

เมื่อเราคอมไพล์และรันโปรแกรมข้างต้นมันจะให้ผลลัพธ์ดังนี้ -

เอาต์พุต

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8

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

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

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

ตัวอย่าง

ต่อไปนี้คือการใช้อัลกอริทึมข้างต้น -

#include <stdio.h>

main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;
   
   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   n = n + 1;
	
   while( j >= k) {
      LA[j+1] = LA[j];
      j = j - 1;
   }

   LA[k] = item;

   printf("The array elements after insertion :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

เมื่อเราคอมไพล์และรันโปรแกรมข้างต้นมันจะให้ผลลัพธ์ดังนี้ -

เอาต์พุต

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
The array elements after insertion :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 10 
LA[4] = 7 
LA[5] = 8

สำหรับรูปแบบอื่น ๆ ของการดำเนินการแทรกอาร์เรย์คลิกที่นี่

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

การลบหมายถึงการลบองค์ประกอบที่มีอยู่ออกจากอาร์เรย์และจัดระเบียบองค์ประกอบทั้งหมดของอาร์เรย์ใหม่

อัลกอริทึม

พิจารณา LA เป็นอาร์เรย์เชิงเส้นที่มี N องค์ประกอบและ K เป็นจำนวนเต็มบวกเช่นนั้น K<=N. ต่อไปนี้เป็นขั้นตอนวิธีในการลบองค์ประกอบที่มีอยู่ที่ตำแหน่ง K ^thของ LA

1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop

ตัวอย่าง

ต่อไปนี้คือการใช้อัลกอริทึมข้างต้น -

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5;
   int i, j;
   
   printf("The original array elements are :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   j = k;
	
   while( j < n) {
      LA[j-1] = LA[j];
      j = j + 1;
   }
	
   n = n -1;
   
   printf("The array elements after deletion :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

เมื่อเราคอมไพล์และรันโปรแกรมข้างต้นมันจะให้ผลลัพธ์ดังนี้ -

เอาต์พุต

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
The array elements after deletion :
LA[0] = 1 
LA[1] = 3 
LA[2] = 7 
LA[3] = 8

การดำเนินการค้นหา

คุณสามารถทำการค้นหาองค์ประกอบอาร์เรย์ตามค่าหรือดัชนีของมัน

อัลกอริทึม

พิจารณา LA เป็นอาร์เรย์เชิงเส้นที่มี N องค์ประกอบและ K เป็นจำนวนเต็มบวกเช่นนั้น K<=N. ต่อไปนี้เป็นอัลกอริทึมในการค้นหาองค์ประกอบที่มีค่า ITEM โดยใช้การค้นหาตามลำดับ

1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

ตัวอย่าง

ต่อไปนี้คือการใช้อัลกอริทึมข้างต้น -

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int item = 5, n = 5;
   int i = 0, j = 0;
   
   printf("The original array elements are :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   while( j < n){
      if( LA[j] == item ) {
         break;
      }
		
      j = j + 1;
   }
	
   printf("Found element %d at position %d\n", item, j+1);
}

เมื่อเราคอมไพล์และรันโปรแกรมข้างต้นมันจะให้ผลลัพธ์ดังนี้ -

เอาต์พุต

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
Found element 5 at position 3

อัปเดตการทำงาน

การดำเนินการอัปเดตหมายถึงการอัปเดตองค์ประกอบที่มีอยู่จากอาร์เรย์ที่ดัชนีที่กำหนด

อัลกอริทึม

พิจารณา LA เป็นอาร์เรย์เชิงเส้นที่มี N องค์ประกอบและ K เป็นจำนวนเต็มบวกเช่นนั้น K<=N. ต่อไปนี้เป็นอัลกอริทึมในการอัปเดตองค์ประกอบที่มีอยู่ที่ตำแหน่ง K ^thของ LA

1. Start
2. Set LA[K-1] = ITEM
3. Stop

ตัวอย่าง

ต่อไปนี้คือการใช้อัลกอริทึมข้างต้น -

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5, item = 10;
   int i, j;
   
   printf("The original array elements are :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   LA[k-1] = item;

   printf("The array elements after updation :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

เมื่อเราคอมไพล์และรันโปรแกรมข้างต้นมันจะให้ผลลัพธ์ดังนี้ -

เอาต์พุต

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
The array elements after updation :
LA[0] = 1 
LA[1] = 3 
LA[2] = 10 
LA[3] = 7 
LA[4] = 8

รายการที่เชื่อมโยงคือลำดับของโครงสร้างข้อมูลซึ่งเชื่อมต่อกันผ่านลิงก์

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

Link - ลิงก์ของรายการที่เชื่อมโยงแต่ละรายการสามารถจัดเก็บข้อมูลที่เรียกว่าองค์ประกอบได้
Next - แต่ละลิงก์ของรายการที่เชื่อมโยงมีลิงก์ไปยังลิงก์ถัดไปที่เรียกว่าถัดไป
LinkedList - รายการที่เชื่อมโยงมีลิงก์การเชื่อมต่อไปยังลิงก์แรกที่เรียกว่า First

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

รายการที่เชื่อมโยงสามารถมองเห็นเป็นห่วงโซ่ของโหนดโดยที่ทุกโหนดชี้ไปยังโหนดถัดไป

ตามภาพประกอบด้านบนประเด็นสำคัญที่ต้องพิจารณาต่อไปนี้

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

ประเภทของรายการที่เชื่อมโยง

ต่อไปนี้เป็นรายการเชื่อมโยงประเภทต่างๆ

Simple Linked List - การนำทางรายการเป็นไปข้างหน้าเท่านั้น
Doubly Linked List - รายการสามารถเลื่อนไปข้างหน้าและข้างหลังได้
Circular Linked List - รายการสุดท้ายมีลิงก์ขององค์ประกอบแรกเป็นรายการถัดไปและองค์ประกอบแรกมีลิงก์ไปยังองค์ประกอบสุดท้ายเหมือนก่อนหน้า

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการพื้นฐานที่รายการสนับสนุน

Insertion - เพิ่มองค์ประกอบที่จุดเริ่มต้นของรายการ
Deletion - ลบองค์ประกอบที่จุดเริ่มต้นของรายการ
Display - แสดงรายการทั้งหมด
Search - ค้นหาองค์ประกอบโดยใช้คีย์ที่กำหนด
Delete - ลบองค์ประกอบโดยใช้คีย์ที่กำหนด

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

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

ลองนึกภาพว่าเรากำลังแทรกโหนด B (NewNode) ระหว่าง A (LeftNode) และ C(โหนดขวา) จากนั้นชี้ B. ไปที่ C -

NewNode.next −> RightNode;

ควรมีลักษณะดังนี้ -

ตอนนี้โหนดถัดไปทางด้านซ้ายควรชี้ไปที่โหนดใหม่

LeftNode.next −> NewNode;

สิ่งนี้จะทำให้โหนดใหม่อยู่ตรงกลางของทั้งสอง รายการใหม่ควรมีลักษณะดังนี้ -

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

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

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

โหนดด้านซ้าย (ก่อนหน้า) ของโหนดเป้าหมายควรชี้ไปที่โหนดถัดไปของโหนดเป้าหมาย -

LeftNode.next −> TargetNode.next;

การดำเนินการนี้จะลบลิงก์ที่ชี้ไปยังโหนดเป้าหมาย ตอนนี้ใช้รหัสต่อไปนี้เราจะลบสิ่งที่โหนดเป้าหมายชี้ไป

TargetNode.next −> NULL;

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

ย้อนกลับการทำงาน

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

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

เราต้องแน่ใจว่าโหนดสุดท้ายไม่ใช่โหนดสุดท้าย ดังนั้นเราจะมี temp node ซึ่งดูเหมือนว่า head node ที่ชี้ไปยังโหนดสุดท้าย ตอนนี้เราจะทำให้โหนดด้านซ้ายทั้งหมดชี้ไปที่โหนดก่อนหน้าทีละโหนด

ยกเว้นโหนด (โหนดแรก) ที่ชี้โดยโหนดส่วนหัวโหนดทั้งหมดควรชี้ไปที่รุ่นก่อนทำให้เป็นผู้สืบทอดใหม่ โหนดแรกจะชี้ไปที่ NULL

เราจะทำให้โหนดหัวชี้ไปยังโหนดแรกใหม่โดยใช้โหนดชั่วคราว

ตอนนี้รายการที่เชื่อมโยงจะกลับรายการ หากต้องการดูการดำเนินรายการที่เชื่อมโยงในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

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

Link - ลิงก์ของรายการที่เชื่อมโยงแต่ละรายการสามารถจัดเก็บข้อมูลที่เรียกว่าองค์ประกอบได้
Next - แต่ละลิงก์ของรายการที่เชื่อมโยงมีลิงก์ไปยังลิงก์ถัดไปที่เรียกว่าถัดไป
Prev - แต่ละลิงก์ของรายการที่เชื่อมโยงมีลิงก์ไปยังลิงก์ก่อนหน้าซึ่งเรียกว่าก่อนหน้า
LinkedList - รายการที่เชื่อมโยงมีลิงก์การเชื่อมต่อไปยังลิงก์แรกที่เรียกว่า First และลิงก์สุดท้ายที่เรียกว่า Last

การแสดงรายการที่เชื่อมโยงแบบทวีคูณ

ตามภาพประกอบด้านบนประเด็นสำคัญที่ต้องพิจารณาต่อไปนี้

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

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการพื้นฐานที่รายการสนับสนุน

Insertion - เพิ่มองค์ประกอบที่จุดเริ่มต้นของรายการ
Deletion - ลบองค์ประกอบที่จุดเริ่มต้นของรายการ
Insert Last - เพิ่มองค์ประกอบที่ส่วนท้ายของรายการ
Delete Last - ลบองค์ประกอบจากส่วนท้ายของรายการ
Insert After - เพิ่มองค์ประกอบหลังรายการของรายการ
Delete - ลบองค์ประกอบออกจากรายการโดยใช้คีย์
Display forward - แสดงรายการทั้งหมดในลักษณะไปข้างหน้า
Display backward - แสดงรายการทั้งหมดในลักษณะย้อนกลับ

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

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

ตัวอย่าง

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

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

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

ตัวอย่าง

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

การแทรกเมื่อสิ้นสุดการทำงาน

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

ตัวอย่าง

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

หากต้องการดูการดำเนินงานในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

รายการที่เชื่อมโยงแบบวงกลมคือรูปแบบของรายการที่เชื่อมโยงซึ่งองค์ประกอบแรกชี้ไปที่องค์ประกอบสุดท้ายและองค์ประกอบสุดท้ายชี้ไปที่องค์ประกอบแรก ทั้งรายการที่เชื่อมโยงแบบเดี่ยวและรายการที่เชื่อมโยงแบบทวีคูณสามารถสร้างเป็นรายการที่เชื่อมโยงแบบวงกลมได้

รายการที่เชื่อมโยงแบบเดี่ยวเป็นแบบวงกลม

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

รายการที่เชื่อมโยงแบบทวีคูณเป็นแบบวงกลม

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

ตามภาพประกอบด้านบนประเด็นสำคัญที่ต้องพิจารณาต่อไปนี้

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

การทำงานขั้นพื้นฐาน

ต่อไปนี้คือการดำเนินการที่สำคัญที่ได้รับการสนับสนุนโดยรายการแบบวงกลม

insert - แทรกองค์ประกอบที่จุดเริ่มต้นของรายการ
delete - ลบองค์ประกอบจากจุดเริ่มต้นของรายการ
display - แสดงรายการ

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

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

ตัวอย่าง

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data= data;
	
   if (isEmpty()) {
      head = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
		
      //point first to new first node
      head = link;
   }   
}

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

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

//delete first item
struct node * deleteFirst() {
   //save reference to first link
   struct node *tempLink = head;
	
   if(head->next == head) {  
      head = NULL;
      return tempLink;
   }     

   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

การทำงานของรายการที่แสดง

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

//display the list
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
	
   printf(" ]");
}

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

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

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

คุณลักษณะนี้ทำให้โครงสร้างข้อมูล LIFO LIFO ย่อมาจาก Last-in-first-out ที่นี่องค์ประกอบที่วาง (แทรกหรือเพิ่ม) สุดท้ายจะถูกเข้าถึงก่อน ในคำศัพท์สแต็กเรียกการดำเนินการแทรกPUSH เรียกว่าการดำเนินการและการกำจัด POP การดำเนินการ.

การแสดงสแต็ค

แผนภาพต่อไปนี้แสดงให้เห็นถึงสแต็กและการดำเนินการ -

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

การทำงานขั้นพื้นฐาน

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

push() - ผลักดัน (จัดเก็บ) องค์ประกอบบนสแต็ก
pop() - การลบ (การเข้าถึง) องค์ประกอบออกจากสแต็ก

เมื่อข้อมูลถูกผลักลงบนสแต็ก

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

peek() - รับองค์ประกอบข้อมูลบนสุดของสแต็กโดยไม่ต้องลบออก
isFull() - ตรวจสอบว่าสแต็กเต็มหรือไม่
isEmpty() - ตรวจสอบว่าสแต็กว่างเปล่า

ตลอดเวลาเรารักษาตัวชี้ไปยังข้อมูล PUSHed ล่าสุดบนสแต็ก เนื่องจากตัวชี้นี้แสดงถึงด้านบนสุดของสแต็กเสมอจึงตั้งชื่อtop. top ตัวชี้ให้ค่าสูงสุดของสแต็กโดยไม่ต้องลบออกจริงๆ

อันดับแรกเราควรเรียนรู้เกี่ยวกับโพรซีเดอร์เพื่อรองรับฟังก์ชันสแต็ก -

แอบมอง ()

อัลกอริทึมของฟังก์ชัน peek () -

begin procedure peek
   return stack[top]
end procedure

การใช้ฟังก์ชัน peek () ในโปรแกรมภาษาซี -

Example

int peek() {
   return stack[top];
}

เต็ม()

อัลกอริทึมของฟังก์ชัน isfull () -

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

การใช้ฟังก์ชัน isfull () ในโปรแกรมภาษาซี -

Example

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

มันว่างเปล่า()

อัลกอริทึมของฟังก์ชัน isempty () -

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

การนำฟังก์ชัน isempty () ไปใช้งานในโปรแกรมภาษาซีมีความแตกต่างกันเล็กน้อย เราเริ่มต้นด้านบนที่ -1 เนื่องจากดัชนีในอาร์เรย์เริ่มต้นจาก 0 ดังนั้นเราจึงตรวจสอบว่าด้านบนต่ำกว่าศูนย์หรือ -1 เพื่อตรวจสอบว่าสแต็กว่างหรือไม่ นี่คือรหัส -

Example

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

ผลักดันการทำงาน

ขั้นตอนการใส่องค์ประกอบข้อมูลใหม่ลงในสแตกเรียกว่า Push Operation การดำเนินการพุชเกี่ยวข้องกับชุดขั้นตอนต่างๆ -

Step 1 - ตรวจสอบว่ากองเต็มหรือไม่
Step 2 - หากสแต็กเต็มสร้างข้อผิดพลาดและออก
Step 3 - หากสแต็กไม่เต็มให้เพิ่มขึ้น top เพื่อชี้พื้นที่ว่างถัดไป
Step 4 - เพิ่มองค์ประกอบข้อมูลไปยังตำแหน่งสแต็กซึ่งชี้ไปที่ด้านบน
Step 5 - คืนความสำเร็จ

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

อัลกอริทึมสำหรับการดำเนินการ PUSH

อัลกอริทึมอย่างง่ายสำหรับการดำเนินการ Push สามารถรับได้ดังนี้ -

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

การใช้อัลกอริทึมนี้ในภาษา C นั้นง่ายมาก ดูรหัสต่อไปนี้ -

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Pop Operation

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

การดำเนินการ Pop อาจเกี่ยวข้องกับขั้นตอนต่อไปนี้ -

Step 1 - ตรวจสอบว่าสแต็กว่างหรือไม่
Step 2 - หากสแต็กว่างเปล่าจะสร้างข้อผิดพลาดและออก
Step 3 - หากสแต็กไม่ว่างเปล่าให้เข้าถึงองค์ประกอบข้อมูลที่ top กำลังชี้
Step 4 - ลดค่าด้านบนลง 1
Step 5 - คืนความสำเร็จ

อัลกอริทึมสำหรับ Pop Operation

อัลกอริทึมอย่างง่ายสำหรับการดำเนินการ Pop สามารถรับได้ดังนี้ -

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

การใช้อัลกอริทึมนี้ใน C มีดังนี้ -

Example

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

สำหรับโปรแกรมสแต็คที่สมบูรณ์แบบในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

วิธีการเขียนนิพจน์เลขคณิตเรียกว่า a notation. นิพจน์ทางคณิตศาสตร์สามารถเขียนได้ในสามรูปแบบที่แตกต่างกัน แต่เทียบเท่ากันกล่าวคือโดยไม่ต้องเปลี่ยนสาระสำคัญหรือผลลัพธ์ของนิพจน์ สัญกรณ์เหล่านี้คือ -

Infix สัญกรณ์
คำนำหน้า (โปแลนด์) สัญกรณ์
สัญกรณ์ Postfix (ย้อนกลับโปแลนด์)

สัญกรณ์เหล่านี้ถูกตั้งชื่อตามวิธีใช้ตัวดำเนินการในนิพจน์ เราจะเรียนรู้สิ่งเดียวกันที่นี่ในบทนี้

Infix สัญกรณ์

เราเขียนนิพจน์ใน infix สัญกรณ์เช่น a - b + c ที่ใช้ตัวดำเนินการ in- ระหว่างตัวถูกดำเนินการ เป็นเรื่องง่ายที่มนุษย์เราจะอ่านเขียนและพูดในสัญกรณ์ infix ได้ แต่สิ่งเดียวกันนี้ไม่สามารถใช้ได้ดีกับอุปกรณ์คอมพิวเตอร์ อัลกอริทึมในการประมวลผลสัญกรณ์ infix อาจเป็นเรื่องยากและมีค่าใช้จ่ายสูงในแง่ของการใช้เวลาและพื้นที่

สัญกรณ์นำหน้า

ในสัญกรณ์นี้ตัวดำเนินการคือ prefixed เป็นตัวถูกดำเนินการกล่าวคือตัวดำเนินการถูกเขียนไว้ข้างหน้าตัวถูกดำเนินการ ตัวอย่างเช่น,+ab. สิ่งนี้เทียบเท่ากับสัญกรณ์ infixa + b. สัญกรณ์นำหน้าเรียกอีกอย่างว่าPolish Notation.

สัญกรณ์ Postfix

รูปแบบสัญกรณ์นี้เรียกว่า Reversed Polish Notation. ในรูปแบบสัญกรณ์นี้ตัวดำเนินการคือpostfixed ไปยังตัวถูกดำเนินการคือตัวดำเนินการถูกเขียนไว้หลังตัวถูกดำเนินการ ตัวอย่างเช่น,ab+. สิ่งนี้เทียบเท่ากับสัญกรณ์ infixa + b.

ตารางต่อไปนี้พยายามแสดงความแตกต่างของสัญกรณ์ทั้งสามโดยย่อ -

ซีเนียร์	Infix สัญกรณ์	สัญกรณ์นำหน้า	สัญกรณ์ Postfix
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	ก ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - ง	- ∗ + abcd	ab + c ∗ d -

การแยกนิพจน์

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

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

ลำดับความสำคัญ

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

เนื่องจากการดำเนินการคูณมีความสำคัญเหนือกว่าการบวก b * c จะได้รับการประเมินก่อน มีการจัดเตรียมตารางลำดับความสำคัญของตัวดำเนินการในภายหลัง

ความสัมพันธ์

Associativity อธิบายกฎที่ตัวดำเนินการที่มีลำดับความสำคัญเดียวกันปรากฏในนิพจน์ ตัวอย่างเช่นในนิพจน์ a + b - c ทั้ง + และ - มีลำดับความสำคัญเหมือนกันดังนั้นส่วนใดของนิพจน์จะได้รับการประเมินก่อนจะถูกกำหนดโดยการเชื่อมโยงของตัวดำเนินการเหล่านั้น ที่นี่ทั้ง + และ - จะเหลือเพียงการเชื่อมโยงดังนั้นนิพจน์จะได้รับการประเมินเป็น(a + b) − c.

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

ซีเนียร์	ตัวดำเนินการ	ลำดับความสำคัญ	ความสัมพันธ์
1	เลขชี้กำลัง ^	สูงสุด	Associative ขวา
2	การคูณ (∗) & หาร (/)	สูงสุดเป็นอันดับสอง	Associative ซ้าย
3	การบวก (+) และการลบ (-)	ต่ำสุด	Associative ซ้าย

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

ใน a + b*cส่วนการแสดงออก b*cจะได้รับการประเมินก่อนโดยมีการคูณเป็นลำดับความสำคัญมากกว่าการบวก เราใช้วงเล็บสำหรับa + b ที่จะประเมินก่อนเช่น (a + b)*c.

Postfix Evaluation Algorithm

ตอนนี้เราจะมาดูอัลกอริทึมเกี่ยวกับวิธีประเมินสัญกรณ์ postfix -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

หากต้องการดูการดำเนินงานในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

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

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

การแทนคิว

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

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

การทำงานขั้นพื้นฐาน

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

enqueue() - เพิ่ม (จัดเก็บ) รายการในคิว
dequeue() - ลบ (เข้าถึง) รายการออกจากคิว

ต้องใช้ฟังก์ชันเพิ่มเติมอีกเล็กน้อยเพื่อให้การทำงานของคิวดังกล่าวข้างต้นมีประสิทธิภาพ เหล่านี้คือ -

peek() - รับองค์ประกอบที่ด้านหน้าของคิวโดยไม่ต้องลบออก
isfull() - ตรวจสอบว่าคิวเต็มหรือไม่
isempty() - ตรวจสอบว่าคิวว่างหรือไม่

ในคิวเราจะจัดคิว (หรือเข้าถึง) ข้อมูลเสมอโดยชี้ด้วย front ตัวชี้และในขณะที่จัดคิว (หรือจัดเก็บ) ข้อมูลในคิวเราใช้ความช่วยเหลือ rear ตัวชี้

ก่อนอื่นเรามาเรียนรู้เกี่ยวกับฟังก์ชันสนับสนุนของคิว -

แอบมอง ()

ฟังก์ชันนี้ช่วยในการดูข้อมูลที่ไฟล์ frontของคิว อัลกอริทึมของฟังก์ชัน peek () มีดังนี้ -

Algorithm

begin procedure peek
   return queue[front]
end procedure

การใช้ฟังก์ชัน peek () ในโปรแกรมภาษาซี -

Example

int peek() {
   return queue[front];
}

เต็ม()

ในขณะที่เราใช้อาร์เรย์มิติเดียวเพื่อใช้งานคิวเราเพียงแค่ตรวจสอบว่าตัวชี้ด้านหลังไปถึงที่ MAXSIZE เพื่อตรวจสอบว่าคิวเต็มแล้ว ในกรณีที่เรารักษาคิวไว้ในรายการที่เชื่อมโยงแบบวงกลมอัลกอริทึมจะแตกต่างกัน อัลกอริทึมของฟังก์ชัน isfull () -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

การใช้ฟังก์ชัน isfull () ในโปรแกรมภาษาซี -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

มันว่างเปล่า()

อัลกอริทึมของฟังก์ชัน isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

ถ้าค่าของ front มีค่าน้อยกว่า MIN หรือ 0 จะบอกว่าคิวยังไม่ได้เริ่มต้นดังนั้นจึงว่างเปล่า

นี่คือรหัสโปรแกรม C -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

จัดคิวการดำเนินการ

คิวรักษาตัวชี้ข้อมูลสองตัว front และ rear. ดังนั้นการดำเนินการจึงค่อนข้างยากที่จะใช้งานได้ยากกว่าการใช้งานแบบสแต็ก

ควรใช้ขั้นตอนต่อไปนี้เพื่อจัดคิว (แทรก) ข้อมูลลงในคิว -

Step 1 - ตรวจสอบว่าคิวเต็มหรือไม่
Step 2 - หากคิวเต็มทำให้เกิดข้อผิดพลาดล้นและออก
Step 3 - หากคิวไม่เต็มให้เพิ่มขึ้น rear ตัวชี้เพื่อชี้พื้นที่ว่างถัดไป
Step 4 - เพิ่มองค์ประกอบข้อมูลไปยังตำแหน่งคิวที่ด้านหลังชี้ไป
Step 5 - คืนความสำเร็จ

บางครั้งเรายังตรวจสอบด้วยว่าคิวเริ่มต้นแล้วหรือไม่เพื่อจัดการกับสถานการณ์ที่ไม่คาดฝัน

อัลกอริทึมสำหรับการดำเนินการจัดคิว

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

การใช้งาน enqueue () ในการเขียนโปรแกรมภาษาซี -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

การยกเลิกคิว

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

Step 1 - ตรวจสอบว่าคิวว่างหรือไม่
Step 2 - หากคิวว่างให้สร้างข้อผิดพลาดที่น้อยเกินไปและออก
Step 3 - หากคิวไม่ว่างให้เข้าถึงข้อมูลที่ front กำลังชี้
Step 4 - เพิ่มขึ้น front ตัวชี้เพื่อชี้ไปยังองค์ประกอบข้อมูลที่มีอยู่ถัดไป
Step 5 - คืนความสำเร็จ

อัลกอริทึมสำหรับการดำเนินการยกเลิกคิว

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

การใช้งาน dequeue () ในการเขียนโปรแกรมภาษาซี -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

สำหรับโปรแกรมคิวที่สมบูรณ์แบบในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

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

อัลกอริทึม

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

รหัสเทียม

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการค้นหาเชิงเส้นในโปรแกรมภาษา C โปรดคลิกที่นี่

การค้นหาแบบไบนารีเป็นอัลกอริธึมการค้นหาที่รวดเร็วโดยมีความซับซ้อนรันไทม์ของΟ (log n) อัลกอริทึมการค้นหานี้ทำงานบนหลักการแบ่งและพิชิต เพื่อให้อัลกอริทึมนี้ทำงานได้อย่างถูกต้องการรวบรวมข้อมูลควรอยู่ในรูปแบบที่เรียงลำดับ

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

การค้นหาแบบไบนารีทำงานอย่างไร

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

ขั้นแรกเราจะกำหนดครึ่งหนึ่งของอาร์เรย์โดยใช้สูตรนี้ -

mid = low + (high - low) / 2

นี่คือ 0 + (9 - 0) / 2 = 4 (ค่าจำนวนเต็ม 4.5) ดังนั้น 4 คือตรงกลางของอาร์เรย์

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

เราเปลี่ยนค่าต่ำเป็นค่ากลาง + 1 และค้นหาค่ากลางใหม่อีกครั้ง

low = mid + 1
mid = low + (high - low) / 2

กลางใหม่ของเราคือ 7 ตอนนี้ เราเปรียบเทียบค่าที่เก็บไว้ที่ตำแหน่ง 7 กับค่าเป้าหมาย 31

ค่าที่เก็บไว้ที่ตำแหน่ง 7 ไม่ตรงกัน แต่เป็นมากกว่าสิ่งที่เรากำลังมองหา ดังนั้นค่าต้องอยู่ที่ส่วนล่างจากตำแหน่งนี้

ดังนั้นเราจึงคำนวณค่ากลางอีกครั้ง คราวนี้เป็น 5

เราเปรียบเทียบค่าที่เก็บไว้ที่ตำแหน่ง 5 กับมูลค่าเป้าหมายของเรา เราพบว่ามันตรงกัน

เราสรุปได้ว่าค่าเป้าหมาย 31 ถูกเก็บไว้ที่ตำแหน่ง 5

การค้นหาแบบไบนารีจะลดจำนวนรายการที่ค้นหาได้ลงครึ่งหนึ่งและลดจำนวนการเปรียบเทียบที่จะทำให้มีจำนวนน้อยลงมาก

รหัสเทียม

รหัสเทียมของอัลกอริทึมการค้นหาแบบไบนารีควรมีลักษณะดังนี้ -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการค้นหาไบนารีใช้อาร์เรย์ในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

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

การค้นหาแบบไบนารีมีข้อได้เปรียบอย่างมากในเรื่องความซับซ้อนของเวลามากกว่าการค้นหาเชิงเส้น การค้นหาเชิงเส้นมีความซับซ้อนของกรณีที่เลวร้ายที่สุดของΟ (n) ในขณะที่การค้นหาแบบไบนารีมีΟ (log n)

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

การวางตำแหน่งในการค้นหาแบบไบนารี

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

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

การตรวจสอบตำแหน่งในการค้นหาการแก้ไข

Interpolation search ค้นหารายการเฉพาะโดยคำนวณตำแหน่งโพรบ ในขั้นต้นตำแหน่งโพรบคือตำแหน่งของรายการที่อยู่ตรงกลางที่สุดของคอลเล็กชัน

หากการแข่งขันเกิดขึ้นดัชนีของรายการจะถูกส่งกลับ ในการแบ่งรายการออกเป็นสองส่วนเราใช้วิธีการต่อไปนี้ -

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

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

ความซับซ้อนของรันไทม์ของอัลกอริทึมการค้นหาการแก้ไขคือ Ο(log (log n)) เมื่อเทียบกับ Ο(log n) ของ BST ในสถานการณ์ที่เอื้ออำนวย

อัลกอริทึม

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

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

รหัสเทียม

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการแก้ไขของการค้นหาในภาษา C เขียนโปรแกรมคลิกที่นี่

Hash Table เป็นโครงสร้างข้อมูลที่จัดเก็บข้อมูลในลักษณะเชื่อมโยง ในตารางแฮชข้อมูลจะถูกจัดเก็บในรูปแบบอาร์เรย์ซึ่งค่าข้อมูลแต่ละค่าจะมีค่าดัชนีเฉพาะของตัวเอง การเข้าถึงข้อมูลจะรวดเร็วมากหากเราทราบดัชนีของข้อมูลที่ต้องการ

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

แฮช

การแฮชเป็นเทคนิคในการแปลงช่วงของค่าคีย์เป็นช่วงดัชนีของอาร์เรย์ เราจะใช้ตัวดำเนินการโมดูโลเพื่อรับค่าคีย์ต่างๆ พิจารณาตัวอย่างของตารางแฮชขนาด 20 และจะจัดเก็บรายการต่อไปนี้ รายการอยู่ในรูปแบบ (คีย์ค่า)

(1,20)
(2,70)
(42,80)
(4,25)
(12,44)
(14,32)
(17,11)
(13,78)
(37,98)

ซีเนียร์	สำคัญ	กัญชา	ดัชนีอาร์เรย์
1	1	1% 20 = 1	1
2	2	2% 20 = 2	2
3	42	42% 20 = 2	2
4	4	4% 20 = 4	4
5	12	12% 20 = 12	12
6	14	14% 20 = 14	14
7	17	17% 20 = 17	17
8	13	13% 20 = 13	13
9	37	37% 20 = 17	17

Linear Probing

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

ซีเนียร์	สำคัญ	กัญชา	ดัชนีอาร์เรย์	หลังจาก Linear Probing ดัชนีอาร์เรย์
1	1	1% 20 = 1	1	1
2	2	2% 20 = 2	2	2
3	42	42% 20 = 2	2	3
4	4	4% 20 = 4	4	4
5	12	12% 20 = 12	12	12
6	14	14% 20 = 14	14	14
7	17	17% 20 = 17	17	17
8	13	13% 20 = 13	13	13
9	37	37% 20 = 17	17	18

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการหลักพื้นฐานของตารางแฮช

Search - ค้นหาองค์ประกอบในตารางแฮช
Insert - แทรกองค์ประกอบในตารางแฮช
delete - ลบองค์ประกอบจากตารางแฮช

DataItem

กำหนดรายการข้อมูลที่มีข้อมูลและคีย์ตามที่จะดำเนินการค้นหาในตารางแฮช

struct DataItem {
   int data;
   int key;
};

วิธีแฮช

กำหนดวิธีการแฮชเพื่อคำนวณรหัสแฮชของคีย์ของรายการข้อมูล

int hashCode(int key){
   return key % SIZE;
}

การดำเนินการค้นหา

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

ตัวอย่าง

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
	
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

แทรกการทำงาน

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

ตัวอย่าง

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

ลบการทำงาน

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

ตัวอย่าง

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินกัญชาในโปรแกรมภาษา C โปรดคลิกที่นี่

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

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

Telephone Directory - สมุดโทรศัพท์จัดเก็บหมายเลขโทรศัพท์ของบุคคลที่เรียงตามชื่อเพื่อให้สามารถค้นหาชื่อได้ง่าย
Dictionary - พจนานุกรมจะจัดเก็บคำตามลำดับตัวอักษรเพื่อให้การค้นหาคำใด ๆ กลายเป็นเรื่องง่าย

การเรียงลำดับในสถานที่และการเรียงลำดับแบบไม่อยู่ในสถานที่

อัลกอริทึมการเรียงลำดับอาจต้องใช้พื้นที่เพิ่มเติมสำหรับการเปรียบเทียบและการจัดเก็บข้อมูลชั่วคราวขององค์ประกอบข้อมูลบางส่วน อัลกอริทึมเหล่านี้ไม่ต้องการพื้นที่เพิ่มเติมใด ๆ และการเรียงลำดับจะเกิดขึ้นในสถานที่หรือตัวอย่างเช่นภายในอาร์เรย์เอง นี้เรียกว่าin-place sorting. การจัดเรียงฟองเป็นตัวอย่างของการจัดเรียงในสถานที่

อย่างไรก็ตามในอัลกอริธึมการเรียงลำดับบางโปรแกรมต้องการพื้นที่ซึ่งมากกว่าหรือเท่ากับองค์ประกอบที่กำลังจัดเรียง การเรียงลำดับที่ใช้พื้นที่เท่ากันหรือมากกว่าเรียกว่าnot-in-place sorting. Merge-sort เป็นตัวอย่างของการจัดเรียงแบบไม่อยู่ในสถานที่

การเรียงลำดับที่เสถียรและไม่เสถียร

หากอัลกอริทึมการเรียงลำดับหลังจากจัดเรียงเนื้อหาแล้วไม่เปลี่ยนลำดับของเนื้อหาที่คล้ายคลึงกันที่ปรากฏขึ้นจะเรียกว่า stable sorting.

หากอัลกอริทึมการเรียงลำดับหลังจากจัดเรียงเนื้อหาแล้วจะเปลี่ยนลำดับของเนื้อหาที่คล้ายคลึงกันที่ปรากฏขึ้นจะเรียกว่า unstable sorting.

ความเสถียรของอัลกอริทึมมีความสำคัญเมื่อเราต้องการรักษาลำดับขององค์ประกอบดั้งเดิมเช่นในทูเพิลเป็นต้น

อัลกอริทึมการเรียงลำดับแบบปรับตัวและไม่ปรับตัว

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

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

เงื่อนไขสำคัญ

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

เพิ่มคำสั่งซื้อ

ลำดับของค่าจะบอกว่าอยู่ใน increasing orderถ้าองค์ประกอบต่อเนื่องมากกว่าองค์ประกอบก่อนหน้า ตัวอย่างเช่น 1, 3, 4, 6, 8, 9 อยู่ในลำดับที่เพิ่มขึ้นเนื่องจากทุกองค์ประกอบถัดไปมีค่ามากกว่าองค์ประกอบก่อนหน้า

กำลังลดคำสั่งซื้อ

ลำดับของค่าจะบอกว่าอยู่ใน decreasing orderหากองค์ประกอบต่อเนื่องน้อยกว่าองค์ประกอบปัจจุบัน ตัวอย่างเช่น 9, 8, 6, 4, 3, 1 อยู่ในลำดับที่ลดลงเนื่องจากทุกองค์ประกอบถัดไปมีค่าน้อยกว่าองค์ประกอบก่อนหน้า

คำสั่งซื้อที่ไม่เพิ่มขึ้น

ลำดับของค่าจะบอกว่าอยู่ใน non-increasing orderถ้าองค์ประกอบต่อเนื่องน้อยกว่าหรือเท่ากับองค์ประกอบก่อนหน้าในลำดับ คำสั่งนี้เกิดขึ้นเมื่อลำดับมีค่าที่ซ้ำกัน ตัวอย่างเช่น 9, 8, 6, 3, 3, 1 อยู่ในลำดับที่ไม่เพิ่มขึ้นเนื่องจากทุกองค์ประกอบถัดไปมีค่าน้อยกว่าหรือเท่ากับ (ในกรณีที่ 3) แต่ไม่มากกว่าองค์ประกอบก่อนหน้าใด ๆ

คำสั่งซื้อที่ไม่ลดลง

ลำดับของค่าจะบอกว่าอยู่ใน non-decreasing orderถ้าองค์ประกอบต่อเนื่องมากกว่าหรือเท่ากับองค์ประกอบก่อนหน้าในลำดับ คำสั่งนี้เกิดขึ้นเมื่อลำดับมีค่าที่ซ้ำกัน ตัวอย่างเช่น 1, 3, 3, 6, 8, 9 อยู่ในลำดับที่ไม่ลดลงเนื่องจากทุกองค์ประกอบถัดไปมีค่ามากกว่าหรือเท่ากับ (ในกรณีที่ 3) แต่ไม่น้อยกว่าองค์ประกอบก่อนหน้า

การเรียงฟองเป็นอัลกอริทึมการเรียงลำดับที่เรียบง่าย อัลกอริทึมการเรียงลำดับนี้เป็นอัลกอริธึมแบบเปรียบเทียบซึ่งแต่ละคู่ขององค์ประกอบที่อยู่ติดกันจะถูกเปรียบเทียบและองค์ประกอบจะถูกสลับหากไม่เรียงตามลำดับ อัลกอริทึมนี้ไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนโดยเฉลี่ยและกรณีที่เลวร้ายที่สุดอยู่ที่Ο (n ² ) โดยที่n คือจำนวนรายการ

Bubble Sort ทำงานอย่างไร

เราใช้อาร์เรย์ที่ไม่ได้เรียงลำดับสำหรับตัวอย่างของเรา การเรียงฟองใช้เวลาΟ (n ² ) ดังนั้นเราจึงทำให้มันสั้นและแม่นยำ

การเรียงฟองเริ่มต้นด้วยสององค์ประกอบแรกเปรียบเทียบกันเพื่อตรวจสอบว่าองค์ประกอบใดสูงกว่า

ในกรณีนี้ค่า 33 มากกว่า 14 ดังนั้นจึงอยู่ในตำแหน่งที่จัดเรียงแล้ว ต่อไปเราเปรียบเทียบ 33 กับ 27

เราพบว่า 27 มีค่าน้อยกว่า 33 และต้องสลับค่าทั้งสองนี้

อาร์เรย์ใหม่ควรมีลักษณะดังนี้ -

ต่อไปเราจะเปรียบเทียบ 33 และ 35 เราพบว่าทั้งคู่อยู่ในตำแหน่งที่จัดเรียงไว้แล้ว

จากนั้นเราย้ายไปยังสองค่าถัดไป 35 และ 10

เรารู้แล้วว่า 10 นั้นเล็กกว่า 35 ดังนั้นจึงไม่เรียงลำดับ

เราแลกเปลี่ยนค่าเหล่านี้ เราพบว่าเรามาถึงจุดสิ้นสุดของอาร์เรย์แล้ว หลังจากการทำซ้ำหนึ่งครั้งอาร์เรย์ควรมีลักษณะดังนี้ -

เพื่อความแม่นยำเรากำลังแสดงให้เห็นว่าอาร์เรย์ควรมีลักษณะอย่างไรหลังจากการวนซ้ำแต่ละครั้ง หลังจากการทำซ้ำครั้งที่สองควรมีลักษณะดังนี้ -

สังเกตว่าหลังจากการทำซ้ำแต่ละครั้งค่าอย่างน้อยหนึ่งค่าจะเคลื่อนไปที่จุดสิ้นสุด

และเมื่อไม่จำเป็นต้องมีการแลกเปลี่ยนประเภทฟองจะเรียนรู้ว่าอาร์เรย์ได้รับการจัดเรียงอย่างสมบูรณ์

ตอนนี้เราควรพิจารณาแง่มุมเชิงปฏิบัติบางประการของการเรียงฟอง

อัลกอริทึม

เราถือว่า list คืออาร์เรย์ของ nองค์ประกอบ เราต่อไปว่าswap ฟังก์ชันแลกเปลี่ยนค่าขององค์ประกอบอาร์เรย์ที่กำหนด

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

รหัสเทียม

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

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

Pseudocode ของอัลกอริทึม BubbleSort สามารถเขียนได้ดังนี้ -

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

การนำไปใช้

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

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการจัดเรียงฟองในโปรแกรมภาษา C โปรดคลิกที่นี่

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

อาร์เรย์ถูกค้นหาตามลำดับและรายการที่ไม่ได้เรียงลำดับจะถูกย้ายและแทรกลงในรายการย่อยที่เรียงลำดับ (ในอาร์เรย์เดียวกัน) อัลกอริทึมนี้ไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนของกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุดคือΟ (n ² ) โดยที่n คือจำนวนรายการ

การเรียงลำดับการแทรกทำงานอย่างไร

เราใช้อาร์เรย์ที่ไม่ได้เรียงลำดับสำหรับตัวอย่างของเรา

การเรียงลำดับการแทรกจะเปรียบเทียบสององค์ประกอบแรก

พบว่าทั้ง 14 และ 33 เรียงลำดับจากน้อยไปมากแล้ว ตอนนี้ 14 อยู่ในรายการย่อยที่จัดเรียง

การเรียงลำดับการแทรกเลื่อนไปข้างหน้าและเปรียบเทียบ 33 กับ 27

และพบว่า 33 ไม่อยู่ในตำแหน่งที่ถูกต้อง.

มันสลับ 33 กับ 27 นอกจากนี้ยังตรวจสอบกับองค์ประกอบทั้งหมดของรายการย่อยที่เรียงลำดับ ที่นี่เราจะเห็นว่ารายการย่อยที่เรียงลำดับมีองค์ประกอบเพียง 14 รายการและ 27 มีค่ามากกว่า 14 ดังนั้นรายการย่อยที่เรียงลำดับจะยังคงเรียงลำดับหลังจากการสลับ

ตอนนี้เรามี 14 และ 27 ในรายการย่อยที่เรียงลำดับ ต่อไปจะเปรียบเทียบ 33 กับ 10

ค่าเหล่านี้ไม่ได้เรียงตามลำดับ

ดังนั้นเราจึงสลับมัน

อย่างไรก็ตามการแลกเปลี่ยนทำให้ 27 และ 10 ไม่เรียงลำดับ

ดังนั้นเราจึงแลกเปลี่ยนพวกเขาด้วย

อีกครั้งเราพบ 14 และ 10 ในลำดับที่ไม่เรียงลำดับ

เราเปลี่ยนใหม่อีกครั้ง เมื่อสิ้นสุดการทำซ้ำครั้งที่สามเรามีรายการย่อยที่จัดเรียงไว้ 4 รายการ

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

อัลกอริทึม

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

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

รหัสเทียม

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการแทรกการดำเนินงานการจัดเรียงในโปรแกรมภาษา C โปรดคลิกที่นี่

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

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

อัลกอริทึมนี้ไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนของกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุดคือΟ (n ² ) โดยที่n คือจำนวนรายการ

การเรียงลำดับการเลือกทำงานอย่างไร

ลองพิจารณาอาร์เรย์ที่ปรากฎต่อไปนี้เป็นตัวอย่าง

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

ดังนั้นเราจึงแทนที่ 14 ด้วย 10 หลังจากหนึ่งการวนซ้ำ 10 ซึ่งเป็นค่าต่ำสุดในรายการจะปรากฏในตำแหน่งแรกของรายการที่เรียงลำดับ

สำหรับตำแหน่งที่สองซึ่งอยู่ที่ 33 เราเริ่มสแกนส่วนที่เหลือของรายการในลักษณะเชิงเส้น

เราพบว่า 14 เป็นค่าต่ำสุดอันดับสองในรายการและควรปรากฏที่ตำแหน่งที่สอง เราแลกเปลี่ยนค่าเหล่านี้

หลังจากการทำซ้ำสองครั้งค่าที่น้อยที่สุดสองค่าจะถูกวางไว้ที่จุดเริ่มต้นในลักษณะที่เรียงลำดับ

กระบวนการเดียวกันนี้ใช้กับส่วนที่เหลือของรายการในอาร์เรย์

ต่อไปนี้เป็นภาพของกระบวนการเรียงลำดับทั้งหมด -

ตอนนี้ให้เราเรียนรู้การเขียนโปรแกรมบางส่วนของการเรียงลำดับการเลือก

อัลกอริทึม

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

รหัสเทียม

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการเลือกการดำเนินการจัดเรียงในโปรแกรมภาษา C โปรดคลิกที่นี่

Merge sort เป็นเทคนิคการเรียงลำดับตามเทคนิคการแบ่งและพิชิต ด้วยความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดคือ n (n log n) จึงเป็นหนึ่งในอัลกอริทึมที่ได้รับการยอมรับมากที่สุด

การเรียงลำดับการผสานจะแบ่งอาร์เรย์ออกเป็นครึ่งเท่า ๆ กันก่อนจากนั้นจึงรวมอาร์เรย์ในลักษณะที่เรียง

Merge Sort ทำงานอย่างไร

เพื่อทำความเข้าใจการเรียงลำดับการผสานเราใช้อาร์เรย์ที่ไม่ได้เรียงลำดับดังต่อไปนี้ -

เราทราบดีว่าการเรียงลำดับการผสานก่อนจะแบ่งอาร์เรย์ทั้งหมดออกเป็นครึ่ง ๆ เท่า ๆ กันเว้นแต่จะได้ค่าอะตอม เราเห็นที่นี่ว่าอาร์เรย์ 8 รายการแบ่งออกเป็นสองอาร์เรย์ขนาด 4

สิ่งนี้ไม่ได้เปลี่ยนลำดับการปรากฏของรายการในต้นฉบับ ตอนนี้เราแบ่งอาร์เรย์ทั้งสองนี้ออกเป็นครึ่งหนึ่ง

เราแบ่งอาร์เรย์เหล่านี้เพิ่มเติมและเราได้ค่าอะตอมซึ่งไม่สามารถหารได้อีกต่อไป

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

ก่อนอื่นเราเปรียบเทียบองค์ประกอบสำหรับแต่ละรายการจากนั้นรวมเข้ากับรายการอื่นในลักษณะที่เรียงลำดับ เราจะเห็นว่า 14 และ 33 อยู่ในตำแหน่งที่เรียงลำดับ เราเปรียบเทียบ 27 และ 10 และในรายการเป้าหมายของ 2 ค่าเราใส่ 10 ก่อนตามด้วย 27 เราเปลี่ยนลำดับของ 19 และ 35 ในขณะที่ 42 และ 44 จะวางตามลำดับ

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

หลังจากการรวมครั้งสุดท้ายรายการควรมีลักษณะดังนี้ -

ตอนนี้เราควรเรียนรู้ลักษณะการเขียนโปรแกรมบางประการของการเรียงลำดับการผสาน

อัลกอริทึม

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

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

รหัสเทียม

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

การเรียงลำดับผสานทำงานร่วมกับการเรียกซ้ำและเราจะเห็นการใช้งานของเราในลักษณะเดียวกัน

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการผสานการดำเนินงานการจัดเรียงในโปรแกรมภาษา C โปรดคลิกที่นี่

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

อัลกอริทึมนี้ใช้การจัดเรียงการแทรกในองค์ประกอบที่แพร่กระจายอย่างกว้างขวางก่อนอื่นเพื่อเรียงลำดับจากนั้นจึงจัดเรียงองค์ประกอบที่มีระยะห่างน้อยกว่า ระยะห่างนี้เรียกว่าinterval. ช่วงเวลานี้คำนวณตามสูตรของ Knuth เป็น -

สูตรของ Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

อัลกอริทึมนี้ค่อนข้างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดกลางเนื่องจากความซับซ้อนของกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุดคือΟ (n) โดยที่ n คือจำนวนรายการ

การเรียงลำดับเชลล์ทำงานอย่างไร

ให้เราพิจารณาตัวอย่างต่อไปนี้เพื่อให้ทราบว่าการจัดเรียงเชลล์ทำงานอย่างไร เราใช้อาร์เรย์เดียวกับที่เราใช้ในตัวอย่างก่อนหน้านี้ สำหรับตัวอย่างและความเข้าใจง่ายของเราเราใช้ช่วงเวลา 4 สร้างรายการย่อยเสมือนของค่าทั้งหมดที่อยู่ในช่วงเวลา 4 ตำแหน่ง ค่าเหล่านี้คือ {35, 14}, {33, 19}, {42, 27} และ {10, 44}

เราเปรียบเทียบค่าในแต่ละรายการย่อยและสลับค่า (ถ้าจำเป็น) ในอาร์เรย์เดิม หลังจากขั้นตอนนี้อาร์เรย์ใหม่ควรมีลักษณะดังนี้ -

จากนั้นเราใช้ช่วงเวลา 2 และช่องว่างนี้สร้างรายการย่อยสองรายการ - {14, 27, 35, 42}, {19, 10, 33, 44}

เราเปรียบเทียบและสลับค่าในอาร์เรย์เดิมหากจำเป็น หลังจากขั้นตอนนี้อาร์เรย์ควรมีลักษณะดังนี้ -

สุดท้ายเราเรียงลำดับส่วนที่เหลือของอาร์เรย์โดยใช้ช่วงของค่า 1 การเรียงเชลล์ใช้การเรียงลำดับการแทรกเพื่อจัดเรียงอาร์เรย์

ต่อไปนี้เป็นภาพทีละขั้นตอน -

เราเห็นว่ามันต้องใช้เพียงสี่ swaps ในการจัดเรียงอาร์เรย์ที่เหลือ

อัลกอริทึม

ต่อไปนี้เป็นอัลกอริทึมสำหรับการจัดเรียงเชลล์

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

รหัสเทียม

ต่อไปนี้คือ pseudocode สำหรับการจัดเรียงเชลล์

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการจัดเรียงเปลือกในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่

สูตรของ Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

อัลกอริทึมนี้ค่อนข้างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดกลางเนื่องจากความซับซ้อนโดยเฉลี่ยและกรณีที่เลวร้ายที่สุดของอัลกอริทึมนี้ขึ้นอยู่กับลำดับช่องว่างที่รู้จักกันดีคือΟ (n) โดยที่ n คือจำนวนรายการ และความซับซ้อนของพื้นที่กรณีที่เลวร้ายที่สุดคือ O (n)

การเรียงลำดับเชลล์ทำงานอย่างไร

จากนั้นเราใช้ช่วงเวลา 1 และช่องว่างนี้จะสร้างรายการย่อยสองรายการ - {14, 27, 35, 42}, {19, 10, 33, 44}

ต่อไปนี้เป็นภาพทีละขั้นตอน -

เราเห็นว่ามันต้องใช้เพียงสี่ swaps ในการจัดเรียงอาร์เรย์ที่เหลือ

อัลกอริทึม

ต่อไปนี้เป็นอัลกอริทึมสำหรับการจัดเรียงเชลล์

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

รหัสเทียม

ต่อไปนี้คือ pseudocode สำหรับการจัดเรียงเชลล์

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

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

Quicksort แบ่งพาร์ติชันอาร์เรย์แล้วเรียกตัวเองซ้ำสองครั้งเพื่อเรียงลำดับสอง subarrays ที่เป็นผลลัพธ์ อัลกอริทึมนี้ค่อนข้างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนโดยเฉลี่ยและกรณีที่เลวร้ายที่สุดคือ O (nLogn) และ image.png (n ² ) ตามลำดับ

พาร์ติชันในการเรียงลำดับด่วน

การแสดงภาพเคลื่อนไหวต่อไปนี้จะอธิบายวิธีการหาค่า Pivot ในอาร์เรย์

ค่า Pivot จะแบ่งรายการออกเป็นสองส่วน และในการวนซ้ำเราจะพบจุดหมุนสำหรับแต่ละรายการย่อยจนกว่ารายการทั้งหมดจะมีองค์ประกอบเดียวเท่านั้น

เรียงลำดับอย่างรวดเร็ว Pivot Algorithm

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

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

เรียงลำดับ Pivot Pseudocode อย่างรวดเร็ว

pseudocode สำหรับอัลกอริทึมข้างต้นสามารถรับมาเป็น -

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

อัลกอริทึมการเรียงลำดับด่วน

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

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

เรียงลำดับ Pseudocode อย่างรวดเร็ว

หากต้องการทราบข้อมูลเพิ่มเติมให้ดูรหัสเทียมสำหรับอัลกอริทึมการเรียงลำดับอย่างรวดเร็ว -

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

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

กราฟคือการแสดงภาพชุดของวัตถุที่คู่ของวัตถุบางคู่เชื่อมต่อกันด้วยลิงก์ วัตถุที่เชื่อมต่อกันจะแสดงด้วยจุดที่เรียกว่าverticesและลิงก์ที่เชื่อมต่อจุดยอดนั้นเรียกว่า edges.

ปกติกราฟคือคู่ของเซต (V, E), ที่ไหน V คือเซตของจุดยอดและ Eคือชุดของขอบที่เชื่อมต่อจุดยอดทั้งคู่ ดูกราฟต่อไปนี้ -

ในกราฟด้านบน

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

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

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

Vertex- แต่ละโหนดของกราฟแสดงเป็นจุดยอด ในตัวอย่างต่อไปนี้วงกลมที่มีป้ายกำกับแสดงถึงจุดยอด ดังนั้น A ถึง G จึงเป็นจุดยอด เราสามารถแสดงโดยใช้อาร์เรย์ดังที่แสดงในภาพต่อไปนี้ ที่นี่ A สามารถระบุได้ด้วยดัชนี 0 B สามารถระบุได้โดยใช้ดัชนี 1 และอื่น ๆ
Edge- Edge แสดงเส้นทางระหว่างจุดยอดสองจุดหรือเส้นระหว่างจุดยอดสองจุด ในตัวอย่างต่อไปนี้เส้นจาก A ถึง B, B ถึง C และอื่น ๆ แทนขอบ เราสามารถใช้อาร์เรย์สองมิติเพื่อแทนอาร์เรย์ได้ดังภาพต่อไปนี้ ที่นี่ AB สามารถแสดงเป็น 1 ที่แถว 0 คอลัมน์ 1 BC เป็น 1 ที่แถว 1 คอลัมน์ 2 และอื่น ๆ โดยเก็บชุดค่าผสมอื่น ๆ เป็น 0
Adjacency- โหนดหรือจุดยอดสองจุดอยู่ติดกันหากเชื่อมต่อกันผ่านขอบ ในตัวอย่างต่อไปนี้ B อยู่ติดกับ A, C อยู่ติดกับ B และอื่น ๆ
Path- เส้นทางแสดงลำดับของขอบระหว่างจุดยอดทั้งสอง ในตัวอย่างต่อไปนี้ ABCD แสดงเส้นทางจาก A ถึง D

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการหลักพื้นฐานของกราฟ -

Add Vertex - เพิ่มจุดยอดให้กับกราฟ
Add Edge - เพิ่มขอบระหว่างจุดยอดทั้งสองของกราฟ
Display Vertex - แสดงจุดยอดของกราฟ

หากต้องการทราบข้อมูลเพิ่มเติมเกี่ยวกับกราฟโปรดอ่านกราฟทฤษฎีการสอน เราจะเรียนรู้เกี่ยวกับการสำรวจกราฟในบทต่อ ๆ ไป

อัลกอริธึม Depth First Search (DFS) สำรวจกราฟในการเคลื่อนที่เชิงลึกและใช้สแต็กเพื่อจำเพื่อให้ได้จุดยอดถัดไปเพื่อเริ่มการค้นหาเมื่อมีทางตันเกิดขึ้นในการวนซ้ำใด ๆ

ดังตัวอย่างที่ให้ไว้ข้างต้นอัลกอริทึม DFS จะข้ามจาก S ไป A ไป D ไป G ถึง E ถึง B ก่อนจากนั้นไปที่ F และสุดท้ายถึง C มันใช้กฎต่อไปนี้

Rule 1- เยี่ยมชมจุดยอดที่ไม่ได้เข้าชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน ดันเข้าไปในกอง
Rule 2- หากไม่พบจุดยอดที่อยู่ติดกันให้เปิดจุดยอดจากสแต็ก (จุดยอดทั้งหมดจะปรากฏขึ้นจากสแต็กซึ่งไม่มีจุดยอดที่อยู่ติดกัน)
Rule 3 - ทำซ้ำกฎ 1 และกฎ 2 จนกว่าสแต็กจะว่างเปล่า

ขั้นตอน	ข้ามผ่าน	คำอธิบาย
1		เริ่มต้นสแต็ก
2		เครื่องหมาย Sตามที่เยี่ยมชมและวางลงในสแต็ก สำรวจโหนดที่อยู่ติดกันที่ไม่ได้เข้าชมจากS. เรามีสามโหนดและเราสามารถเลือกโหนดใดก็ได้ สำหรับตัวอย่างนี้เราจะนำโหนดตามลำดับตัวอักษร
3		เครื่องหมาย Aตามที่เยี่ยมชมและวางลงในสแต็ก สำรวจโหนดที่อยู่ติดกันที่ไม่ได้มาจาก A ทั้งสองS และ D อยู่ติดกับ A แต่เรากังวลสำหรับโหนดที่ไม่ได้เข้าชมเท่านั้น
4		เยี่ยมชม Dและทำเครื่องหมายว่าเยี่ยมชมและวางลงในสแต็ก ที่นี่เรามีB และ C โหนดซึ่งอยู่ติดกับ Dและทั้งคู่ยังไม่ได้เยี่ยมชม อย่างไรก็ตามเราจะเลือกตามลำดับตัวอักษรอีกครั้ง
5		พวกเราเลือก Bทำเครื่องหมายว่าเยี่ยมชมและวางลงในสแต็ก ที่นี่Bไม่มีโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชม ดังนั้นเราจึงปรากฏB จากกอง
6		เราตรวจสอบสแต็กท็อปเพื่อกลับไปยังโหนดก่อนหน้าและตรวจสอบว่ามีโหนดที่ไม่ได้เยี่ยมชมหรือไม่ ที่นี่เราพบD ที่จะอยู่ด้านบนสุดของสแต็ก
7		โหนดที่อยู่ติดกันที่ไม่ได้เข้าชมเท่านั้นที่มาจาก D คือ Cตอนนี้. ดังนั้นเราไปเยี่ยมชมCทำเครื่องหมายว่าเยี่ยมชมแล้ววางลงในสแต็ก

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

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการตามขั้นตอนวิธีนี้ในการเขียนโปรแกรมภาษา C ที่คลิกที่นี่

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

ดังตัวอย่างที่ให้ไว้ข้างต้นอัลกอริทึม BFS จะข้ามจาก A ไป B ไปยัง E ถึง F จากนั้นไปยัง C และ G สุดท้ายถึง D มันใช้กฎต่อไปนี้

Rule 1- เยี่ยมชมจุดยอดที่ไม่ได้เข้าชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน แทรกไว้ในคิว
Rule 2 - หากไม่พบจุดยอดที่อยู่ติดกันให้ลบจุดยอดแรกออกจากคิว
Rule 3 - ทำซ้ำกฎ 1 และกฎ 2 จนกว่าคิวจะว่างเปล่า

ขั้นตอน	ข้ามผ่าน	คำอธิบาย
1		เริ่มต้นคิว
2		เราเริ่มจากการเยี่ยมชม S (โหนดเริ่มต้น) และทำเครื่องหมายว่าเยี่ยมชมแล้ว
3		จากนั้นเราจะเห็นโหนดที่อยู่ติดกันที่ไม่ได้มาจาก S. ในตัวอย่างนี้เรามีสามโหนด แต่เราเลือกตามตัวอักษรAทำเครื่องหมายว่าเยี่ยมชมแล้วและจัดคิว
4		ถัดไปโหนดที่อยู่ติดกันที่ไม่ได้เข้าชมจาก S คือ B. เราทำเครื่องหมายว่าเยี่ยมชมและจัดคิว
5		ถัดไปโหนดที่อยู่ติดกันที่ไม่ได้เข้าชมจาก S คือ C. เราทำเครื่องหมายว่าเยี่ยมชมและจัดคิว
6		ตอนนี้ Sไม่เหลือโหนดที่อยู่ติดกัน ดังนั้นเราจึงตัดสินใจและค้นหาA.
7		จาก A เรามี Dเป็นโหนดที่อยู่ติดกันที่ไม่ได้เข้าชม เราทำเครื่องหมายว่าเยี่ยมชมและจัดคิว

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

การดำเนินการตามขั้นตอนวิธีนี้ในการเขียนโปรแกรมภาษา C สามารถเห็นได้ที่นี่

ต้นไม้แสดงถึงโหนดที่เชื่อมต่อกันด้วยขอบ เราจะพูดถึง binary tree หรือ binary search tree โดยเฉพาะ

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

เงื่อนไขสำคัญ

ต่อไปนี้เป็นคำศัพท์ที่สำคัญเกี่ยวกับต้นไม้

Path - เส้นทางหมายถึงลำดับของโหนดตามขอบของต้นไม้
Root- โหนดที่อยู่ด้านบนสุดของต้นไม้เรียกว่ารูท มีเพียงหนึ่งรูทต่อทรีและหนึ่งเส้นทางจากโหนดรูทไปยังโหนดใด ๆ
Parent - โหนดใด ๆ ยกเว้นโหนดรูทมีขอบขึ้นไปหนึ่งโหนดที่เรียกว่าพาเรนต์
Child - โหนดที่อยู่ด้านล่างโหนดที่กำหนดซึ่งเชื่อมต่อด้วยขอบลงไปเรียกว่าโหนดลูก
Leaf - โหนดที่ไม่มีโหนดลูกเรียกว่าโหนดลีฟ
Subtree - ต้นไม้ย่อยแสดงถึงลูกหลานของโหนด
Visiting - การเยี่ยมชมหมายถึงการตรวจสอบค่าของโหนดเมื่อการควบคุมอยู่บนโหนด
Traversing - การข้ามผ่านหมายถึงการผ่านโหนดตามลำดับที่ระบุ
Levels- ระดับของโหนดแสดงถึงการสร้างโหนด ถ้าโหนดรูทอยู่ที่ระดับ 0 โหนดลูกถัดไปจะอยู่ที่ระดับ 1 หลานของโหนดอยู่ที่ระดับ 2 เป็นต้น
keys - คีย์แสดงถึงค่าของโหนดตามการดำเนินการค้นหาที่จะดำเนินการสำหรับโหนด

การแสดงต้นไม้ค้นหาแบบไบนารี

โครงสร้างการค้นหาแบบไบนารีแสดงพฤติกรรมพิเศษ ชายด์ด้านซ้ายของโหนดต้องมีค่าน้อยกว่าค่าของพาเรนต์และชายด์ด้านขวาของโหนดต้องมีค่ามากกว่าค่าพาเรนต์

เรากำลังจะติดตั้งโครงสร้างโดยใช้วัตถุโหนดและเชื่อมต่อผ่านการอ้างอิง

โหนดต้นไม้

โค้ดสำหรับเขียนโหนดทรีจะคล้ายกับที่ระบุด้านล่าง มีส่วนข้อมูลและการอ้างอิงโหนดลูกด้านซ้ายและขวา

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

ในแผนภูมิโหนดทั้งหมดใช้โครงสร้างร่วมกัน

การใช้งานพื้นฐาน BST

การดำเนินการพื้นฐานที่สามารถทำได้บนโครงสร้างข้อมูลต้นไม้ค้นหาแบบไบนารีมีดังต่อไปนี้ -

Insert - แทรกองค์ประกอบในต้นไม้ / สร้างต้นไม้
Search - ค้นหาองค์ประกอบในต้นไม้
Preorder Traversal - เดินลัดเลาะไปตามต้นไม้ในลักษณะสั่งจองล่วงหน้า
Inorder Traversal - เดินลัดเลาะไปตามต้นไม้ตามลำดับ
Postorder Traversal - สำรวจต้นไม้ในลักษณะโพสต์ออร์เดอร์

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

แทรกการทำงาน

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

อัลกอริทึม

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

การนำไปใช้

การใช้งานฟังก์ชันแทรกควรมีลักษณะดังนี้ -

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

การดำเนินการค้นหา

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

อัลกอริทึม

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

การใช้อัลกอริทึมนี้ควรมีลักษณะดังนี้

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินงานของโครงสร้างข้อมูลแบบต้นไม้ค้นหาแบบทวิภาคโปรดคลิกที่นี่

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

In-order Traversal
พรีออเดอร์ Traversal
Post-order Traversal

โดยทั่วไปเราสำรวจต้นไม้เพื่อค้นหาหรือค้นหารายการหรือคีย์ที่กำหนดในแผนภูมิหรือเพื่อพิมพ์ค่าทั้งหมดที่มีอยู่

In-order Traversal

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

หากมีการข้ามต้นไม้ไบนารี in-orderผลลัพธ์จะสร้างค่าคีย์ที่เรียงลำดับจากน้อยไปหามาก

เริ่มจาก Aและตามลำดับตามลำดับเราจะย้ายไปที่ทรีย่อยด้านซ้าย B. Bยังถูกส่งผ่านตามลำดับ กระบวนการดำเนินต่อไปจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด ผลลัพธ์ของการข้ามตามลำดับของต้นไม้นี้จะเป็น -

D → B → E → A → F → C → G

อัลกอริทึม

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

พรีออเดอร์ Traversal

ในวิธีการข้ามผ่านนี้โหนดรูทจะถูกเยี่ยมชมก่อนจากนั้นทรีย่อยด้านซ้ายและสุดท้ายคือทรีย่อยด้านขวา

เริ่มจาก Aและหลังจากการสั่งซื้อล่วงหน้าเราไปเยี่ยมชมครั้งแรก A แล้วย้ายไปที่แผนผังย่อยด้านซ้าย B. Bนอกจากนี้ยังมีการสั่งซื้อล่วงหน้า กระบวนการดำเนินต่อไปจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด ผลลัพธ์ของการส่งผ่านคำสั่งซื้อล่วงหน้าของต้นไม้นี้จะเป็น -

A → B → D → E → C → F → G

อัลกอริทึม

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Post-order Traversal

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

เริ่มจาก Aและหลังจากผ่านการสั่งซื้อภายหลังเราไปที่แผนผังย่อยด้านซ้ายก่อน B. Bนอกจากนี้ยังมีการส่งผ่านภายหลังการสั่งซื้อ กระบวนการดำเนินต่อไปจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด ผลลัพธ์ของการส่งผ่านหลังการสั่งซื้อของต้นไม้นี้จะเป็น -

D → E → B → F → G → C → A

อัลกอริทึม

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

ในการตรวจสอบการดำเนินงานของ C traversing ต้นไม้โปรดคลิกที่นี่

Binary Search Tree (BST) คือต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง -

ค่าของคีย์ของแผนผังย่อยด้านซ้ายมีค่าน้อยกว่าค่าของคีย์ของโหนดหลัก (รูท)
ค่าของคีย์ของแผนผังย่อยด้านขวามากกว่าหรือเท่ากับค่าของคีย์ของโหนดหลัก (รูท)

ดังนั้น BST จึงแบ่งต้นไม้ย่อยทั้งหมดออกเป็นสองส่วน แผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวาและสามารถกำหนดเป็น -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

การเป็นตัวแทน

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

ต่อไปนี้เป็นการแสดงภาพของ BST -

เราสังเกตว่าคีย์โหนดรูท (27) มีคีย์ที่มีค่าน้อยกว่าทั้งหมดบนแผนผังย่อยด้านซ้ายและคีย์ที่มีมูลค่าสูงกว่าบนแผนผังย่อยด้านขวา

การทำงานขั้นพื้นฐาน

ต่อไปนี้คือการทำงานพื้นฐานของต้นไม้ -

Search - ค้นหาองค์ประกอบในต้นไม้
Insert - แทรกองค์ประกอบในต้นไม้
Pre-order Traversal - เดินลัดเลาะไปตามต้นไม้ในลักษณะสั่งจองล่วงหน้า
In-order Traversal - เดินลัดเลาะไปตามต้นไม้ตามลำดับ
Post-order Traversal - สำรวจต้นไม้ในลักษณะโพสต์ออร์เดอร์

โหนด

กำหนดโหนดที่มีข้อมูลอ้างอิงโหนดลูกด้านซ้ายและขวา

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

การดำเนินการค้นหา

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

อัลกอริทึม

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

แทรกการทำงาน

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

อัลกอริทึม

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

จะเกิดอะไรขึ้นถ้าอินพุตไปยังต้นไม้ค้นหาแบบไบนารีมาในลักษณะเรียงลำดับ (จากน้อยไปมากหรือมากไปหาน้อย)? จากนั้นจะมีลักษณะดังนี้ -

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

ตั้งชื่อตามนักประดิษฐ์ Adelson, Velski & Landis, AVL treesคือความสูงสมดุลต้นไม้ค้นหาไบนารี ต้นไม้ AVL ตรวจสอบความสูงของต้นไม้ย่อยด้านซ้ายและด้านขวาและมั่นใจว่าความแตกต่างไม่เกิน 1 ความแตกต่างนี้เรียกว่าBalance Factor.

เราจะเห็นว่าต้นไม้ต้นแรกมีความสมดุลและต้นไม้สองต้นถัดไปไม่สมดุล -

ในแผนภูมิที่สองแผนผังย่อยด้านซ้ายของ C มีความสูง 2 และทรีย่อยทางขวามีความสูง 0 ดังนั้นความแตกต่างคือ 2 ในต้นไม้ที่สามต้นไม้ย่อยด้านขวาของ Aมีความสูง 2 และด้านซ้ายหายไปมันจึงเป็น 0 และผลต่างคือ 2 อีกครั้ง ต้นไม้ AVL อนุญาตให้ความแตกต่าง (ปัจจัยสมดุล) เป็นเพียง 1

BalanceFactor = height(left-sutree) − height(right-sutree)

หากความแตกต่างของความสูงของต้นไม้ย่อยด้านซ้ายและด้านขวามากกว่า 1 ต้นไม้จะสมดุลโดยใช้เทคนิคการหมุน

การหมุน AVL

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

หมุนซ้าย
หมุนขวา
หมุนซ้าย - ขวา
หมุนขวา - ซ้าย

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

การหมุนซ้าย

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

ในตัวอย่างของเราโหนด Aไม่สมดุลเมื่อมีการแทรกโหนดในแผนผังย่อยด้านขวาของทรีย่อยด้านขวาของ A เราทำการหมุนซ้ายโดยการทำA ทรีย่อยด้านซ้ายของ B.

การหมุนขวา

ต้นไม้ AVL อาจไม่สมดุลหากมีการแทรกโหนดในทรีย่อยด้านซ้ายของทรีย่อยด้านซ้าย ต้นไม้จึงต้องการการหมุนเวียนที่เหมาะสม

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

การหมุนซ้าย - ขวา

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

สถานะ	หนังบู๊
	มีการแทรกโหนดลงในทรีย่อยด้านขวาของทรีย่อยด้านซ้าย สิ่งนี้ทำให้Cโหนดที่ไม่สมดุล สถานการณ์เหล่านี้ทำให้ต้นไม้ AVL ทำการหมุนซ้าย - ขวา
	ก่อนอื่นเราทำการหมุนซ้ายที่แผนผังย่อยด้านซ้ายของ C. สิ่งนี้ทำให้Aทรีย่อยด้านซ้ายของ B.
	โหนด C ยังไม่สมดุลอย่างไรก็ตามตอนนี้เป็นเพราะทรีย่อยด้านซ้ายของทรีย่อยด้านซ้าย
	ตอนนี้เราจะหมุนต้นไม้ไปทางขวาโดยทำ B รูทโหนดใหม่ของทรีย่อยนี้ C ตอนนี้กลายเป็นทรีย่อยด้านขวาของทรีย่อยด้านซ้ายของตัวเอง
	ตอนนี้ต้นไม้สมดุลแล้ว

การหมุนขวา - ซ้าย

การหมุนสองครั้งประเภทที่สองคือการหมุนขวา - ซ้าย เป็นการรวมกันของการหมุนขวาตามด้วยการหมุนซ้าย

สถานะ	หนังบู๊
	มีการแทรกโหนดลงในทรีย่อยด้านซ้ายของทรีย่อยด้านขวา สิ่งนี้ทำให้Aโหนดที่ไม่สมดุลกับปัจจัยความสมดุล 2
	ขั้นแรกเราทำการหมุนไปทางขวา C โหนดทำให้ C แผนผังย่อยด้านขวาของทรีย่อยด้านซ้ายของตัวเอง B. ตอนนี้B กลายเป็นแผนผังย่อยที่ถูกต้องของ A.
	โหนด A ยังไม่สมดุลเนื่องจากทรีย่อยด้านขวาของทรีย่อยด้านขวาและต้องหมุนซ้าย
	การหมุนซ้ายจะดำเนินการโดยการทำ B โหนดรูทใหม่ของทรีย่อย A กลายเป็นทรีย่อยทางซ้ายของทรีย่อยด้านขวา B.
	ตอนนี้ต้นไม้สมดุลแล้ว

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

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

เราพบต้นไม้ที่ทอดสามต้นจากกราฟที่สมบูรณ์ กราฟที่ไม่มีทิศทางที่สมบูรณ์สามารถมีได้สูงสุดn^n-2 จำนวนต้นไม้ที่ทอดโดยที่ nคือจำนวนโหนด ในตัวอย่างที่กล่าวถึงข้างต้นn is 3, ด้วยเหตุนี้ 3³⁻² = 3 สามารถปลูกต้นไม้ได้

คุณสมบัติทั่วไปของ Spanning Tree

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

กราฟที่เชื่อมต่อ G สามารถมีต้นไม้ที่ทอดยาวได้มากกว่าหนึ่งต้น
ต้นไม้ที่ทอดเป็นไปได้ทั้งหมดของกราฟ G มีจำนวนขอบและจุดยอดเท่ากัน
ต้นไม้ที่ทอดไม่มีวงจรใด ๆ (ลูป)
การลบขอบด้านหนึ่งออกจากต้นไม้ที่ทอดจะทำให้กราฟขาดการเชื่อมต่อกล่าวคือต้นไม้ที่ทอดคือ minimally connected.
การเพิ่มขอบด้านหนึ่งให้กับต้นไม้ที่ทอดจะสร้างวงจรหรือลูปกล่าวคือต้นไม้ที่ทอดเป็น maximally acyclic.

คุณสมบัติทางคณิตศาสตร์ของ Spanning Tree

ต้นไม้มีระยะ n-1 ขอบที่ไหน n คือจำนวนโหนด (จุดยอด)
จากกราฟที่สมบูรณ์โดยลบค่าสูงสุด e - n + 1 ขอบเราสร้างต้นไม้ทอดได้
กราฟที่สมบูรณ์สามารถมีได้สูงสุด n^n-2 จำนวนต้นไม้ที่ทอด

ดังนั้นเราสามารถสรุปได้ว่าการขยายต้นไม้เป็นส่วนหนึ่งของกราฟ G ที่เชื่อมต่อและกราฟที่ตัดการเชื่อมต่อไม่มีการทอดต้นไม้

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

Spanning tree ใช้เพื่อค้นหาเส้นทางขั้นต่ำในการเชื่อมต่อโหนดทั้งหมดในกราฟ การใช้ต้นไม้ทอดทั่วไปคือ -

Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis

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

ขั้นต่ำ Spanning Tree (MST)

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

อัลกอริธึม Spanning-Tree ขั้นต่ำ

เราจะเรียนรู้เกี่ยวกับอัลกอริทึมต้นไม้ที่สำคัญที่สุดสองแบบที่นี่ -

อัลกอริทึมของ Kruskal
อัลกอริทึมของ Prim

ทั้งสองเป็นอัลกอริทึมโลภ

ฮีปเป็นกรณีพิเศษของโครงสร้างข้อมูลไบนารีทรีที่สมดุลซึ่งคีย์รูทโหนดจะถูกเปรียบเทียบกับชายด์และจัดเรียงตามลำดับ ถ้าα มีโหนดลูก β แล้ว -

คีย์ (α) ≥คีย์ (β)

เนื่องจากค่าของพาเรนต์มากกว่าค่าของเด็กคุณสมบัตินี้จึงสร้างขึ้น Max Heap. ตามเกณฑ์นี้ฮีปสามารถมีได้สองประเภท -

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap - โดยที่ค่าของโหนดรูทน้อยกว่าหรือเท่ากับลูกของมัน

Max-Heap - โดยที่ค่าของโหนดรูทมากกว่าหรือเท่ากับลูกของมัน

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

Max Heap Construction Algorithm

เราจะใช้ตัวอย่างเดียวกันนี้เพื่อสาธิตวิธีสร้าง Max Heap ขั้นตอนในการสร้าง Min Heap นั้นคล้ายกัน แต่เราใช้ค่า min แทนค่าสูงสุด

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

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note - ในขั้นตอนวิธีการสร้าง Min Heap เราคาดว่าค่าของโหนดแม่จะน้อยกว่าโหนดลูก

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

อัลกอริทึมการลบฮีปสูงสุด

ให้เราได้รับอัลกอริทึมเพื่อลบจากฮีปสูงสุด การลบในฮีปสูงสุด (หรือต่ำสุด) เกิดขึ้นที่รากเสมอเพื่อลบค่าสูงสุด (หรือต่ำสุด)

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

ภาษาโปรแกรมคอมพิวเตอร์บางภาษาอนุญาตให้โมดูลหรือฟังก์ชันเรียกตัวเองได้ เทคนิคนี้เรียกว่าการเรียกซ้ำ ในการเรียกซ้ำฟังก์ชันα เรียกตัวเองโดยตรงหรือเรียกใช้ฟังก์ชัน β ซึ่งจะเรียกฟังก์ชันเดิม α. ฟังก์ชั่นα เรียกว่าฟังก์ชันเรียกซ้ำ

Example - ฟังก์ชันเรียกตัวเอง

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - ฟังก์ชันที่เรียกใช้ฟังก์ชันอื่นซึ่งจะเรียกอีกครั้ง

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

คุณสมบัติ

ฟังก์ชันวนซ้ำสามารถไปได้อย่างไม่มีที่สิ้นสุดเหมือนลูป เพื่อหลีกเลี่ยงการทำงานแบบวนซ้ำไม่สิ้นสุดมีคุณสมบัติสองประการที่ฟังก์ชันเรียกซ้ำต้องมี -

Base criteria - ต้องมีเกณฑ์หรือเงื่อนไขพื้นฐานอย่างน้อยหนึ่งอย่างดังนั้นเมื่อตรงตามเงื่อนไขนี้ฟังก์ชันจะหยุดเรียกตัวเองซ้ำ
Progressive approach - การโทรแบบเรียกซ้ำควรดำเนินไปในลักษณะที่ทุกครั้งที่มีการโทรซ้ำมันเข้าใกล้เกณฑ์พื้นฐานมากขึ้น

การนำไปใช้

ภาษาโปรแกรมจำนวนมากใช้การเรียกซ้ำโดยใช้ stacks. โดยทั่วไปเมื่อใดก็ตามที่ฟังก์ชัน (caller) เรียกใช้ฟังก์ชันอื่น (callee) หรือเรียกตัวเองว่า callee ฟังก์ชันผู้โทรจะโอนการควบคุมการดำเนินการไปยังผู้เรียก กระบวนการถ่ายโอนนี้อาจเกี่ยวข้องกับข้อมูลบางอย่างที่จะส่งผ่านจากผู้โทรไปยังผู้รับสาย

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

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

การวิเคราะห์การเรียกซ้ำ

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

ความซับซ้อนของเวลา

ในกรณีของการทำซ้ำเราจะใช้การวนซ้ำเพื่อนับความซับซ้อนของเวลา ในกรณีของการเรียกซ้ำโดยสมมติว่าทุกอย่างคงที่เราพยายามหาจำนวนครั้งที่มีการเรียกซ้ำ การเรียกใช้ฟังก์ชันคือΟ (1) ดังนั้น (n) จำนวนครั้งที่มีการเรียกซ้ำทำให้ฟังก์ชันวนซ้ำΟ (n)

ความซับซ้อนของอวกาศ

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

หอคอยแห่งฮานอยเป็นปริศนาทางคณิตศาสตร์ซึ่งประกอบด้วยหอคอยสามแห่ง (หมุด) และวงแหวนมากกว่าหนึ่งวงเป็นภาพ -

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

กฎ

ภารกิจคือการย้ายดิสก์ทั้งหมดไปยังหอคอยอื่นโดยไม่ละเมิดลำดับของการจัดเรียง กฎบางประการที่ต้องปฏิบัติสำหรับหอคอยแห่งฮานอย ได้แก่ -

สามารถเคลื่อนย้ายดิสก์ระหว่างหอคอยได้ในช่วงเวลาใดเวลาหนึ่งเท่านั้น
สามารถนำออกได้เฉพาะดิสก์ "ด้านบน" เท่านั้น
ไม่มีดิสก์ขนาดใหญ่ที่สามารถนั่งทับดิสก์ขนาดเล็กได้

ต่อไปนี้เป็นการนำเสนอภาพเคลื่อนไหวของการไขปริศนาหอคอยฮานอยด้วยดิสก์สามแผ่น

ปริศนาหอคอยฮานอยพร้อมดิสก์ n สามารถแก้ไขได้อย่างน้อยที่สุด 2ⁿ−1ขั้นตอน งานนำเสนอนี้แสดงให้เห็นว่ามีการไขปริศนาที่มีดิสก์ 3 แผ่น2³ - 1 = 7 ขั้นตอน

อัลกอริทึม

ในการเขียนอัลกอริทึมสำหรับ Tower of Hanoi อันดับแรกเราต้องเรียนรู้วิธีแก้ปัญหานี้ด้วยจำนวนดิสก์ที่น้อยกว่าพูด→ 1 หรือ 2 เราทำเครื่องหมายสามหอคอยด้วยชื่อ source, destination และ aux(เพื่อช่วยในการเคลื่อนย้ายดิสก์เท่านั้น) หากเรามีดิสก์เพียงแผ่นเดียวก็สามารถย้ายจากหมุดต้นทางไปยังปลายทางได้อย่างง่ายดาย

ถ้าเรามี 2 ดิสก์ -

ขั้นแรกเราย้ายดิสก์ที่เล็กกว่า (บนสุด) ไปที่หมุดเสริม
จากนั้นเราย้ายดิสก์ที่ใหญ่กว่า (ด้านล่าง) ไปยังหมุดปลายทาง
และสุดท้ายเราย้ายดิสก์ขนาดเล็กจาก aux ไปยังหมุดปลายทาง

ตอนนี้เราอยู่ในฐานะที่จะออกแบบอัลกอริทึมสำหรับ Tower of Hanoi ที่มีดิสก์มากกว่าสองแผ่น เราแบ่งกองดิสก์ออกเป็นสองส่วน ดิสก์ที่ใหญ่ที่สุด (n ^th disk) อยู่ในส่วนเดียวและดิสก์อื่น ๆ (n-1) ทั้งหมดอยู่ในส่วนที่สอง

เป้าหมายสูงสุดของเราคือการย้ายดิสก์ nจากต้นทางไปยังปลายทางจากนั้นใส่ดิสก์อื่น ๆ (n1) ทั้งหมดลงบนดิสก์ เราสามารถจินตนาการได้ว่าจะใช้แบบเดียวกันในลักษณะเรียกซ้ำสำหรับชุดดิสก์ที่กำหนดทั้งหมด

ขั้นตอนในการปฏิบัติตามคือ -

Step 1 − Move n-1 disks from source to aux
Step 2 − Move n^th disk from source to dest
Step 3 − Move n-1 disks from aux to dest

อัลกอริทึมแบบวนซ้ำสำหรับหอคอยแห่งฮานอยสามารถขับเคลื่อนได้ดังนี้ -

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

ในการตรวจสอบการดำเนินงานในการเขียนโปรแกรม C ที่คลิกที่นี่

Fibonacci series จะสร้างตัวเลขที่ตามมาโดยการเพิ่มตัวเลขก่อนหน้าสองตัว อนุกรมฟีโบนักชีเริ่มจากตัวเลขสองตัว -F₀ & F₁. ค่าเริ่มต้นของ F ₀และ F ₁สามารถนำมาเป็น 0, 1 หรือ 1, 1 ตามลำดับ

ซีรี่ส์ฟีโบนักชีเป็นไปตามเงื่อนไขต่อไปนี้ -

F_n = F_n-1 + F_n-2

ดังนั้นอนุกรมฟีโบนักชีจึงมีลักษณะดังนี้ -

ฉ₈ = 0 1 1 2 3 5 8 13

หรือนี่ -

ฉ₈ = 1 1 2 3 5 8 13 21

เพื่อจุดประสงค์ในการอธิบาย Fibonacci ของ F ₈จะแสดงเป็น -

Fibonacci Iterative Algorithm

ก่อนอื่นเราพยายามร่างอัลกอริทึมซ้ำสำหรับอนุกรมฟีโบนักชี

Procedure Fibonacci(n)
   declare f₀, f₁, fib, loop 
   
   set f₀ to 0
   set f₁ to 1
   
   display f₀, f₁
   
   for loop ← 1 to n
   
      fib ← f₀ + f₁   
      f₀ ← f₁
      f₁ ← fib

      display fib
   end for
	
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการตามขั้นตอนวิธีการดังกล่าวข้างต้นในการเขียนโปรแกรมภาษา C ที่คลิกที่นี่

อัลกอริทึมการเรียกซ้ำ Fibonacci

ให้เราเรียนรู้วิธีการสร้างชุดฟีโบนักชีอัลกอริทึมแบบเรียกซ้ำ เกณฑ์พื้นฐานของการเรียกซ้ำ

START
Procedure Fibonacci(n)
   declare f₀, f₁, fib, loop 
   
   set f₀ to 0
   set f₁ to 1
   
   display f₀, f₁
   
   for loop ← 1 to n
   
      fib ← f₀ + f₁   
      f₀ ← f₁
      f₁ ← fib

      display fib
   end for

END

หากต้องการดูการดำเนินการตามขั้นตอนวิธีการดังกล่าวข้างต้นในภาษา C เขียนโปรแกรมคลิกที่นี่