Data Structures and Algorithms in C ดาวน์โหลด - Data Structures and Algorithms in C แหล่งข้อมูล C Download

Data Structures and Algorithms in C

ซอร์สโค้ดอื่น ๆ

1.0.0

ดาวน์โหลด

โครงสร้างข้อมูลและอัลกอริทึมที่ใช้ใน C

ที่นี่คุณจะพบโครงสร้างข้อมูลและอัลกอริทึมที่นำมาใช้ใน C. อัลกอริทึมเหล่านี้ส่วนใหญ่ขึ้นอยู่กับหนังสือ แนะนำอัลกอริทึมโดย Thomas H. Cormen

คำแนะนำ

ทุกโมดูลประกอบด้วยไฟล์ส่วนหัวอย่างน้อยหนึ่งไฟล์ (.H) และไฟล์ต้นฉบับหนึ่งไฟล์ที่มีรหัส CORPUS (.C) เพื่อที่จะใช้หนึ่งในโมดูลเหล่านี้ฉันขอแนะนำให้คุณทำตามขั้นตอนเหล่านี้:

ค้นหาโครงสร้างข้อมูลหรืออัลกอริทึมที่คุณต้องการจาก /modules
ดาวน์โหลดไดเรกทอรีโมดูล (เช่น /modules/List ) ที่มีไฟล์ซอร์สโค้ดไฟล์. c (เช่น List.c )
ไปที่ /include/ โฟลเดอร์ค้นหาไฟล์ส่วนหัว (.h) ที่คุณต้องการ (เช่น List.h ) และดาวน์โหลด
❕ยังไม่เสร็จ❕ตอนนี้ไปตรวจสอบไฟล์ส่วนหัว (.h) และดาวน์โหลดสิ่งที่รวมอยู่ (คำสั่ง #include "foo.h" ) โมดูลส่วนใหญ่รวมถึงตัวอย่าง HashFunctions หรือ Comparators หรือแม้กระทั่งโครงสร้างข้อมูลอื่น ๆ มองเห็นสิ่งที่จำเป็นและดาวน์โหลดไฟล์ ทั้งหมด
แก้ไขเส้นทางไปยัง #include "foo.h" หากคุณเปลี่ยนโครงสร้างโฟลเดอร์ปัจจุบัน
ทุกอย่างพร้อมหวังว่ามันจะช่วยคุณได้!

รวบรวมและดำเนินการ

หากคุณโคลนโฟลเดอร์ทั้งหมดคุณสามารถเรียกใช้:

make : นั่นเป็นเรื่องที่น่ารำคาญทุกโมดูล
make run-tests : ซึ่งรวบรวมทุกโมดูลและดำเนินการทดสอบทั้งหมด
make valgind-tests : ซึ่งรวบรวมทุกโมดูลและดำเนินการทดสอบทั้งหมดโดยใช้ valgrind

ภาคผนวก

โครงสร้างข้อมูล	คำนิยาม
ตัวกรองบาน	Bloom Filter เป็นโครงสร้างข้อมูลความน่าจะเป็นที่ประหยัดพื้นที่โดย Burton Howard Bloom ในปี 1970 ซึ่งใช้เพื่อทดสอบว่าองค์ประกอบเป็นสมาชิกของชุดหรือไม่ การจับคู่ที่ผิดพลาดเป็นไปได้ แต่เชิงลบเท็จไม่ได้ - กล่าวอีกนัยหนึ่งการสืบค้นจะส่งคืนทั้ง "อาจเป็นในชุด" หรือ "ไม่ได้อยู่ในชุด" องค์ประกอบสามารถเพิ่มลงในชุด แต่ไม่ลบออก (แม้ว่าจะสามารถแก้ไขได้ด้วยตัวแปรตัวกรอง Bloom Counting); ยิ่งมีการเพิ่มรายการมากเท่าใดความน่าจะเป็นของผลบวกที่ผิดพลาดก็จะยิ่งใหญ่ขึ้นเท่านั้น
ต้นไม้สีแดงดำ	ต้นไม้สีแดง-สีดำเป็นต้นไม้ค้นหาไบนารีแบบบาลานซ์ แต่ละโหนดเก็บบิตพิเศษที่แสดงถึง "สี" ("สีแดง" หรือ "ดำ") ใช้เพื่อให้แน่ใจว่าต้นไม้ยังคงมีความสมดุลในระหว่างการแทรกและการลบ เมื่อต้นไม้ได้รับการแก้ไขต้นไม้ใหม่จะถูกจัดเรียงใหม่และ "ทาสีใหม่" เพื่อกู้คืนคุณสมบัติการระบายสีที่ จำกัด ว่าต้นไม้จะไม่สมดุลในกรณีที่เลวร้ายที่สุด คุณสมบัติได้รับการออกแบบเพื่อให้การจัดเรียงใหม่และการปรับสีนี้สามารถทำได้อย่างมีประสิทธิภาพ การปรับสมดุลไม่สมบูรณ์แบบ แต่รับประกันการค้นหาในเวลา O (logn) โดยที่ n คือจำนวนโหนดของต้นไม้ การดำเนินการแทรกและการลบพร้อมกับการจัดเรียงต้นไม้และการปรับสีใหม่จะดำเนินการในเวลา O (logn)
รายการที่เชื่อมโยง	รายการที่เชื่อมโยงเป็นคอลเลกชันเชิงเส้นขององค์ประกอบข้อมูลที่ไม่ได้รับคำสั่งซื้อจากตำแหน่งทางกายภาพในหน่วยความจำ แต่ละองค์ประกอบชี้ไปที่ถัดไป มันเป็นโครงสร้างข้อมูลที่ประกอบด้วยคอลเลกชันของโหนดซึ่งเป็นตัวแทนของลำดับ
คิว	ลำดับความสำคัญคิวเป็นประเภทข้อมูลนามธรรมคล้ายกับโครงสร้างข้อมูลคิวหรือสแต็กปกติซึ่งแต่ละองค์ประกอบยังมี "ลำดับความสำคัญ" ที่เกี่ยวข้อง ในคิวลำดับความสำคัญองค์ประกอบที่มีลำดับความสำคัญสูงจะถูกเสิร์ฟก่อนองค์ประกอบที่มีลำดับความสำคัญต่ำ
Hashtable พร้อมรายการ	การใช้งานทั่วไปของแฮชแต้มที่ง่ายมากด้วยกุญแจและโซ่ ไม่มีการสร้างใหม่
แฮชช์กับต้นไม้สีแดงดำ	ประกอบด้วยตารางซึ่งทุกแถวมีตัวชี้ไปที่ต้นไม้สีแดงดำด้วยวิธีนี้เราจะได้รับความซับซ้อนที่ดีที่สุดข้างต้นและในเวลาเดียวกันหลีกเลี่ยงการชนกันมากเกินไป
แฮชช์กับถังกับต้นไม้สีแดงดำ	Hashtable ประกอบด้วยถังพอยน์เตอร์ไปยังต้นไม้สีดำสีแดง
สูงสุด	Max-heap เป็นต้นไม้ไบนารีที่สมบูรณ์ซึ่งค่าในโหนดภายในแต่ละโหนดมากกว่าหรือเท่ากับค่าในลูกของโหนดนั้น การทำแผนที่องค์ประกอบของกองลงในอาร์เรย์นั้นเป็นเรื่องเล็กน้อย: หากโหนดถูกเก็บไว้ดัชนี k แล้วเด็กด้านซ้ายจะถูกเก็บไว้ที่ดัชนี 2K+1 และลูกด้านขวาที่ดัชนี 2K+2
การแยกออกจากกัน	โครงสร้างข้อมูลแบบแยกส่วนหรือที่เรียกว่าโครงสร้างข้อมูลสหภาพ-ค้นหาหรือชุดผสม-ค้นหาเป็นโครงสร้างข้อมูลที่เก็บชุดของชุดแยก (ไม่ทับซ้อน) อย่างเท่าเทียมกันมันเก็บพาร์ติชันของชุดลงในชุดย่อยที่แยกจากกัน มันให้การดำเนินการสำหรับการเพิ่มชุดใหม่การรวมชุด (แทนที่พวกเขาด้วยสหภาพของพวกเขา) และค้นหาสมาชิกตัวแทนของชุด การดำเนินการครั้งสุดท้ายช่วยให้สามารถค้นหาได้อย่างมีประสิทธิภาพหากองค์ประกอบทั้งสองอยู่ในชุดเดียวกันหรือต่างกัน
ตัวกำหนดตารางงานพร้อมเธรด	ตัวกำหนดตารางงานแบบมัลติเธรดโดยใช้ Unix Pthreads

อัลกอริทึม	คำนิยาม
กองซุปเปอร์	HEAPSORT เป็นอัลกอริทึมการเรียงลำดับการเปรียบเทียบ HEAPSORT สามารถคิดได้ว่าเป็นตัวเลือกที่ดีขึ้น: เช่นเดียวกับการเลือกการเลือก HEAPSORT แบ่งอินพุตออกเป็นภูมิภาคที่เรียงลำดับและไม่ได้เรียงลำดับและมันจะหดตัวลงในภูมิภาคที่ไม่ได้เรียงลำดับโดยการแยกองค์ประกอบที่ใหญ่ที่สุดจากนั้นและแทรกเข้าไปในภูมิภาคที่จัดเรียง HEAPSORT ไม่เสียเวลากับการสแกนระยะเวลาเชิงเส้นของภูมิภาคที่ไม่ได้เรียงลำดับ แต่การเรียงลำดับฮีปจะรักษาภูมิภาคที่ไม่ได้เรียงลำดับไว้ในโครงสร้างข้อมูลกองเพื่อค้นหาองค์ประกอบที่ใหญ่ที่สุดในแต่ละขั้นตอนได้อย่างรวดเร็วยิ่งขึ้น
การทำแบบฉุนเฉียว	Quicksort เป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพ พัฒนาโดยนักวิทยาศาสตร์คอมพิวเตอร์ชาวอังกฤษ Tony Hoare ในปี 1959 และตีพิมพ์ในปี 1961 มันยังคงเป็นอัลกอริทึมที่ใช้กันทั่วไปสำหรับการเรียงลำดับ เมื่อนำไปใช้งานได้ดีอาจเร็วกว่าการเรียงลำดับการรวมและเร็วกว่า heapsort ประมาณสองหรือสามเท่า

อัลกอริทึม

คำนิยาม

กองซุปเปอร์

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

การทำแบบฉุนเฉียว

Quicksort เป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพ พัฒนาโดยนักวิทยาศาสตร์คอมพิวเตอร์ชาวอังกฤษ Tony Hoare ในปี 1959 และตีพิมพ์ในปี 1961 มันยังคงเป็นอัลกอริทึมที่ใช้กันทั่วไปสำหรับการเรียงลำดับ เมื่อนำไปใช้งานได้ดีอาจเร็วกว่าการเรียงลำดับการรวมและเร็วกว่า heapsort ประมาณสองหรือสามเท่า

คุณประโยชน์	คำนิยาม
เครื่องเปรียบเทียบ	ฟังก์ชั่นที่เปรียบเทียบสองค่าและส่งคืน 0,> 0, <0
ฟังก์ชั่นแฮช	ฟังก์ชันแฮชสตริง