โครงสร้างข้อมูล
ห้องสมุดนี้ให้การใช้งานอัลกอริทึมและโครงสร้างข้อมูลคลาสสิก
องค์กร
โครงการแบ่งออกเป็นสองแพ็คเกจอัลกอริทึมและโครงสร้าง แพ็คเกจอัลกอริทึมประกอบด้วยการใช้งานอัลกอริทึมแบบสแตนด์อโลนส่วนใหญ่ในขณะที่แพ็คเกจโครงสร้างมีโครงสร้างข้อมูลและอัลกอริทึมที่ทำงานโดยเฉพาะ
อัลกอริทึม
นี่คือรายการอัลกอริทึมภายใต้แพ็คเกจอัลกอริทึม:
ใน binarysearch.py:
- การค้นหาไบนารีมาตรฐาน: การค้นหาไบนารีมาตรฐาน https://en.wikipedia.org/wiki/binary_search_algorithm
- การค้นหาไบนารีครั้งแรก: การค้นหาไบนารีมาตรฐานยกเว้นว่าพบองค์ประกอบแรกที่ตรงกับรหัสการค้นหา
ใน Expression.py:
อัลกอริทึมการแบ่งลาน: อัลกอริทึมของ Dijkstra สำหรับการแปลง Infix เป็นสัญลักษณ์ Postfix https://en.wikipedia.org/wiki/shunting-yard_algorithm
อัลกอริทึมสแต็กสองอัลกอริทึมของ Dijkstra: อัลกอริทึมของ Dijkstra สำหรับการตีความนิพจน์ postfix
ในปัญหา olver.py:
- อัลกอริทึม*: อัลกอริทึมการค้นหาเส้นทาง https://en.wikipedia.org/wiki/a*_search_algorithm
- A* อัลกอริทึมที่ปรับให้เข้ากับปัญหา 8-puzzle: https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html
ใน sort.py:
- การเลือกเรียงลำดับ: https://en.wikipedia.org/wiki/selection_sort
- การเรียงลำดับการแทรก: https://en.wikipedia.org/wiki/insertion_sort
- การเรียงลำดับของเชลล์: https://en.wikipedia.org/wiki/shellsort
- รูปแบบของการเรียงลำดับการผสาน: https://en.wikipedia.org/wiki/merge_sort
- การนับการผกผัน: นับจำนวนการรุกรานด้วยการเรียงลำดับที่ดัดแปลง
- รูปแบบของการเรียงลำดับอย่างรวดเร็ว: รวมถึงการเรียงลำดับอย่างรวดเร็วมาตรฐานการเรียงลำดับแบบเร็ว 3 ทางและการสุ่มตัวอย่างการเรียงลำดับอย่างรวดเร็ว https://en.wikipedia.org/wiki/quicksort
- HEAP เรียงลำดับ: https://en.wikipedia.org/wiki/heapsort
- เลือก KTH: เลือกองค์ประกอบ KTH ตามลำดับ ขึ้นอยู่กับพาร์ติชันการเรียงลำดับอย่างรวดเร็ว
โครงสร้าง
นี่คือรายการของโครงสร้างข้อมูลที่นำไปใช้และอัลกอริทึมที่ทำงานกับพวกเขา:
ใน linkedList.py:
- รายการที่เชื่อมโยง: https://en.wikipedia.org/wiki/linked_list
- สแต็คที่เชื่อมโยง: สแต็กนำไปใช้กับรายการที่เชื่อมโยง
- คิวที่เชื่อมโยง: คิวนำไปใช้กับรายการที่เชื่อมโยง
ใน unionfind.py: https://en.wikipedia.org/wiki/disjoint-set_data_structure
- การค้นหาอย่างรวดเร็ว: ชุดแยกใช้งานกับอาร์เรย์เช่นโครงสร้างข้อมูล o (1) ค้นหา
- Union Quick: Disjoint Set นำมาใช้กับต้นไม้ลิงค์หลัก
- Balanced Quick Union: Set Disjoint นำมาใช้กับ Parent Link Tree และ Balancing on Union O (log (n)) ประสิทธิภาพสำหรับการค้นหาและสหภาพ
- Path Compression Quick Union: Disjoint Set นำมาใช้กับ Parent Link Tree และเพิ่มด้วยการบีบอัดเส้นทาง
- การบีบอัดเส้นทางที่สมดุลอย่างรวดเร็วยูเนี่ยน: ชุดแยกติดตั้งกับต้นไม้ลิงค์แม่ด้วยการปรับสมดุลและการบีบอัดเส้นทาง เกือบจะตัดจำหน่าย O (1) ประสิทธิภาพในการค้นหาและสหภาพ
ใน symboltable.py:
- ทรีค้นหาไบนารี: มาตรฐาน BST https://en.wikipedia.org/wiki/binary_search_tree
- Tree Red & Black: BST ที่สมดุลโดยใช้การเป็นตัวแทน 2-3 https://en.wikipedia.org/wiki/red%E2%80%93black_tree
- ตารางการผูกมัดแยกกัน: ตารางแฮชที่แก้ไขการชนโดยการผูกมัดพวกเขาในรายการ https://en.wikipedia.org/wiki/hash_table#separate_chaining
- ตารางที่อยู่เปิดแฮช: ตารางแฮชที่แก้ไขการชนกับการตรวจเชิงเส้น https://en.wikipedia.org/wiki/hash_table#open_addressing
ใน heap.py:
- Binary HEAP: การดำเนินการคิวลำดับความสำคัญกับกองไบนารี https://en.wikipedia.org/wiki/binary_heap
ใน graph.py:
- กราฟที่ไม่ได้กำกับ: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)
- กราฟกำกับกำกับ: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)
- กราฟถ่วงน้ำหนักที่ไม่ได้กำกับ: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- กราฟถ่วงน้ำหนักโดยตรง: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)
- ความลึกการค้นหาครั้งแรก: https://en.wikipedia.org/wiki/depth-first_search
- การค้นหาครั้งแรกที่กว้าง: https://en.wikipedia.org/wiki/breadth-first_search
- ส่วนประกอบที่เชื่อมต่อไม่ได้ทิศทาง: https://en.wikipedia.org/wiki/Component_(graph_theory)
- การตรวจจับวัฏจักรที่ไม่ได้บอกทิศทาง: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- ตรวจจับวัฏจักรกำกับ: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- การตรวจจับ Biparte: https://en.wikipedia.org/wiki/bipartite_graph
- การสั่งซื้อทอพอโลยี: https://en.wikipedia.org/wiki/topological_sorting
- ส่วนประกอบที่เชื่อมต่ออย่างมาก (อัลกอริทึมของ Kosaraju): https://en.wikipedia.org/wiki/Kosaraju%27S_ALGORITHM
- อัลกอริทึมของ Prim (ขี้เกียจ): https://en.wikipedia.org/wiki/prim%27s_algorithm
- อัลกอริทึมของ Kruskal: https://en.wikipedia.org/wiki/kruskal%27s_algorithm
- เส้นทางที่สั้นที่สุดของ Dijkstra: https://en.wikipedia.org/wiki/dijkstra%27s_algorithm
- ทอพอโลยี acyclic เส้นทางที่สั้นที่สุด: https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- Bellman Ford เส้นทางที่สั้นที่สุด: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_Algorithm
การใช้งาน
ส่วนประกอบทั้งหมดได้รับการทดสอบ อย่างไรก็ตามพวกเขาไม่ได้ทดสอบมาตรฐานการผลิตที่เข้มงวด โครงสร้างข้อมูลเช่นรายการที่เชื่อมโยงและสัญลักษณ์มีอินเทอร์เฟซเช่นรายการ Python มาตรฐานและพจนานุกรม
