cdsa
1.0.0
ไลบรารีโครงสร้างข้อมูลและอัลกอริทึมทั่วไปใน ANSI C
พื้นที่เก็บข้อมูลนี้เป็นโครงการต่อเนื่องของการใช้โครงสร้างข้อมูลและอัลกอริ ทึม ใน ANSI C. ฉันพบว่าฉันมักจะใช้โครงสร้างเดียวกันที่ต้องใช้รหัสหม้อไอน้ำจำนวนมากดังนั้นฉันจึงสร้างที่เก็บนี้เพื่อจัดระเบียบโครงสร้างเหล่านี้และอนุญาตให้รวมโครงสร้างเหล่านี้เข้ากับโครงการที่มีอยู่
ปรัชญาการออกแบบของฉันด้วยพื้นที่เก็บข้อมูลนี้คือการเสนอ API ที่เรียบง่ายสำหรับแต่ละโครงสร้างข้อมูลที่มีเครื่องมือทั้งหมดที่จำเป็นในการสร้างโครงสร้างที่ซับซ้อน/ซอกมากขึ้นได้อย่างง่ายดาย การพกพาเป็นสิ่งสำคัญที่สุดดังนั้นจึงใช้ ANSI C เท่านั้นและไม่มีคู่ส่วนหัว/แหล่งที่มาอาศัยส่วนหัว/แหล่งที่มาอื่น นอกจากนี้เพื่อส่งเสริมการใช้ในระบบฝังตัวอัลกอริทึมซ้ำจะถูกใช้โดยเฉพาะกับอัลกอริทึมแบบเรียกซ้ำและโครงสร้างข้อมูลแต่ละตัวนั้นล่วงล้ำ (สำหรับพื้นที่หน่วยความจำที่ดีกว่า)
อย่าลังเลที่จะใช้โครงสร้างข้อมูลและอัลกอริทึมในแบบของคุณเอง รหัสได้รับใบอนุญาตภายใต้ใบอนุญาต ISC (รุ่นที่ง่ายของใบอนุญาต BSD ที่เหมือนกัน); ดังนั้นจึงอาจถูกนำกลับมาใช้ใหม่ในโครงการใด ๆ ไม่ว่าจะเป็นกรรมสิทธิ์หรือโอเพ่นซอร์ส
แต่ละส่วนหัวได้รับการบันทึกไว้อย่างหนักและหวังว่าควรตอบคำถามทั้งหมดเกี่ยวกับการทำงาน คำอธิบายเชิงลึกเกี่ยวกับวิธีการทำงานของโครงสร้างข้อมูลแต่ละตัวที่อยู่ด้านบนของไฟล์ส่วนหัว
// Define your struct somewhere.
struct Object {
int some_value ;
...
// Don't forget to embed the ListNode!
ListNode node ;
};
...
// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . some_value = 1 ;
obj2 . some_value = 2 ;
// Create your List.
List my_list ;
list_init ( & my_list );
// Populate your List. Notice how the API abstracts itself and only cares about the ListNode.
list_insert_back ( & my_list , & obj1 . node );
list_insert_back ( & my_list , & obj2 . node );
// Let's see what is stored in the List:
int i = 1 ;
ListNode * n ;
list_for_each ( n , & my_list ) {
if ( i == 1 ) {
assert ( n == & obj1 . node );
} else if ( i == 2 ){
assert ( n == & obj2 . node );
}
++ i ;
}
...
// Let's get the ListNode at the front of the List.
ListNode * front_node_ptr = list_front ( & my_list );
// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "list_entry":
struct Object * obj_ptr = list_entry ( front_node_ptr , struct Object , node );
assert ( obj_ptr == & obj1 ); // Define your struct somewhere.
struct Object {
int key ;
...
// Don't forget to embed the RBTreeNode!
RBTreeNode node ;
};
...
// You must define a compare function which compares a key with the key of a RBTreeNode.
int compare ( const void * some_key , const RBTreeNode * some_node ) {
return * ( const int * ) some_key - rbtree_entry ( some_node , struct Object , node ) -> key ;
}
// You can OPTIONALLY define a collide function which handles key collisions. When a key
// collision happens, no matter what, the old RBTreeNode will be replaced by the new
// RBTreeNode. If this function is defined, then it will be called after the old
// RBTreeNode is replaced in the RBTree. This function is great if you need to free up
// resources in the Object variable pertaining to the discarded RBTreeNode. This function
// is also great for enabling multi-key functionality in the RBTree.
void collide ( const RBTreeNode * old_node , const RBTreeNode * new_node , void * auxiliary_data ) {
// When a RBTree is created, we can give it auxiliary data to hold onto. This data is then
// passed to this function for usage. This data, for example, could be a memory pool struct
// that is needed to free up the resources used by the Object variable pertaining to the
// old_node parameter.
...
}
...
// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . key = 1 ;
obj2 . key = 2 ;
// Create you RBTree. In this case we don't have any auxiliary data that needs to be used
// in the collide function, so we just pass NULL. As previously mentioned, the collide
// function itself is optional. If you don't need to do any special resource management,
// just pass "NULL" in place of "collide" in the initialize function.
RBTree my_rbtree ;
rbtree_init ( & my_rbtree , compare , collide , NULL );
// Populate your RBTree. Notice how the API abstracts itself and only cares about the
// RBTreeNode and its key. Because red black trees are always ordered in some way, order
// of insertion will never affect the inorderness of the tree.
rbtree_insert ( & my_rbtree , & obj2 . key , & obj2 . node );
rbtree_insert ( & my_rbtree , & obj1 . key , & obj1 . node );
// Because of the way our compare function is designed, the RBTree stores its RBTreeNodes
// inorder from smallest key to greatest key. Let's see what is stored in the RBTree:
int i = 1 ;
RBTreeNode * n ;
rbtree_for_each ( n , & my_rbtree ) {
if ( i == 1 ) {
assert ( n == & obj1 . node );
} else if ( i == 2 ) {
assert ( n == & obj2 . node );
}
++ i ;
}
...
// Let's get the RBTreeNode with the greatest key.
RBTreeNode * greatest_node_ptr = rbtree_last ( & my_rbtree );
// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "rbtree_entry":
struct Object * obj_ptr = rbtree_entry ( greatest_node_ptr , struct Object , node );
assert ( obj_ptr == & obj2 ); // Define your struct somewhere.
struct Object {
int key ;
...
// Don't forget to embed the HashTableNode!
HashTableNode node ;
};
...
// You must define a hash function which takes in a key and returns its hashcode. In this
// case we aren't going to do anything fancy since this is just an example.
size_t hash ( const void * key ) {
return * ( const int * ) key ;
}
// You must define an equal function which determines if a key is equal to the key of a HashTableNode.
int equal ( const void * some_key , const HashTableNode * some_node ) {
return * ( const int * ) some_key == hashtable_entry ( some_node , struct Object , node ) -> key ;
}
// You can OPTIONALLY define a collide function which handles key collisions. When a key
// collision happens, no matter what, the old HashTableNode will be replaced by the new
// HashTableNode. If this function is defined, then it will be called after the old
// HashTableNode is replaced in the HashTable. This function is great if you need to free up
// resources in the Object variable pertaining to the discarded HashTableNode. This function
// is also great for enabling multi-key functionality in the HashTable.
void collide ( const HashTableNode * old_node , const HashTableNode * new_node , void * auxiliary_data ) {
// When a HashTable is created, we can give it auxiliary data to hold onto. This data is then
// passed to this function for usage. This data, for example, could be a memory pool struct
// that is needed to free up the resources used by the Object variable pertaining to the
// old_node parameter.
...
}
...
// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . key = 1 ;
obj2 . key = 2 ;
// You must create a bucket array which is an array of pointers to HashTableNodes. This
// array is used by the HashTable for the duration of its lifetime. In this case we will
// have 50 buckets in the bucket array.
HashTableNode * bucket_array [ 50 ];
// Create you HashTable. In this case we don't have any auxiliary data that needs to be used
// in the collide function, so we just pass NULL. As previously mentioned, the collide
// function itself is optional. If you don't need to do any special resource management,
// just pass "NULL" in place of "collide" in the initialize function.
HashTable my_hashtable ;
hashtable_init ( & my_hashtable , bucket_array , 50 , hash , equal , collide , NULL );
// Populate your HashTable. Notice how the API abstracts itself and only cares about the
// HashTableNode and its key.
hashtable_insert ( & my_hashtable , & obj1 . key , & obj1 . node );
hashtable_insert ( & my_hashtable , & obj2 . key , & obj2 . node );
// HashTable provides no guarantee on the ordering of HashTableNodes in the bucket array.
// Let's see what is stored in the HashTable:
int sum_of_keys = 0 , bucket_index ;
HashTableNode * n ;
hashtable_for_each ( n , bucket_index , & my_hashtable ) {
sum_of_keys += hashtable_entry ( n , struct Object , node ) -> key ;
}
assert ( sum_of_keys == 3 );
...
// Let's get the HashTableNode with the key that equals 1.
int key = 1 ;
HashTableNode * node_ptr = hashtable_lookup_key ( & my_hashtable , & key );
// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "hashtable_entry":
struct Object * obj_ptr = hashtable_entry ( node_ptr , struct Object , node );
assert ( obj_ptr == & obj1 ); // Define your struct somewhere.
struct Object {
int some_value ;
...
// Don't forget to embed the StackNode!
StackNode node ;
};
...
// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . some_value = 1 ;
obj2 . some_value = 2 ;
// Create your Stack.
Stack my_stack ;
stack_init ( & my_stack );
// Populate your Stack. Notice how the API abstracts itself and only cares about the StackNode.
stack_push ( & my_stack , & obj1 . node );
stack_push ( & my_stack , & obj2 . node );
// Let's see what is stored in the Stack:
int i = 1 ;
StackNode * n ;
stack_for_each ( n , & my_stack ) {
if ( i == 1 ) {
assert ( n == & obj2 . node );
} else if ( i == 2 ){
assert ( n == & obj1 . node );
}
++ i ;
}
...
// Let's get the StackNode at the top of the Stack.
StackNode * top_node_ptr = stack_peek ( & my_stack );
// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "stack_entry":
struct Object * obj_ptr = stack_entry ( top_node_ptr , struct Object , node );
assert ( obj_ptr == & obj2 ); // Define your struct somewhere.
struct Object {
int some_value ;
...
// Don't forget to embed the QueueNode!
QueueNode node ;
};
...
// Create some Object variables.
struct Object obj1 , obj2 ;
obj1 . some_value = 1 ;
obj2 . some_value = 2 ;
// Create your Queue.
Queue my_queue ;
queue_init ( & my_queue );
// Populate your Queue. Notice how the API abstracts itself and only cares about the QueueNode.
queue_push ( & my_queue , & obj1 . node );
queue_push ( & my_queue , & obj2 . node );
// Let's see what is stored in the Queue:
int i = 1 ;
QueueNode * n ;
queue_for_each ( n , & my_queue ) {
if ( i == 1 ) {
assert ( n == & obj1 . node );
} else if ( i == 2 ){
assert ( n == & obj2 . node );
}
++ i ;
}
...
// Let's get the QueueNode at the front of the Queue.
QueueNode * front_node_ptr = queue_peek ( & my_queue );
// Getting the "node" member from an Object variable is easy: ("obj1.node"),
// but how do you get the Object variable when you only have the "node" member?
// Solution: the macro "queue_entry":
struct Object * obj_ptr = queue_entry ( front_node_ptr , struct Object , node );
assert ( obj_ptr == & obj1 );ห้องสมุดนี้เขียนใน Ansi C ดังนั้นรหัสควรทำงานกับคอมไพเลอร์ทุกตัว คู่ส่วนหัว/แหล่งที่มาแต่ละคู่เป็นอิสระจากคนอื่น ๆ สิ่งนี้ทำให้การใช้โครงสร้างข้อมูลแต่ละตัวง่าย เพียงแค่ลากและวางคู่ส่วนหัว/แหล่งที่มาลงในโครงการของคุณโดยตรงและตรวจสอบให้แน่ใจว่าได้รวบรวมไฟล์ต้นฉบับพร้อมกับไฟล์อื่น ๆ ของคุณ
คุณต้องมีคอมไพเลอร์ GNU เพื่อเรียกใช้การทดสอบ ตรวจสอบให้แน่ใจว่าคุณมีไฟล์ทั้งหมดที่ดาวน์โหลดเกี่ยวกับไลบรารีนี้เช่นกัน
เพียงเรียกใช้คำสั่งนี้หนึ่งครั้งในไดเรกทอรี "ทดสอบ" เพื่อเรียกใช้การทดสอบทั้งหมด:
make
ตัวอย่าง:
cd tests/
make
gcc test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -pedantic-errors -std=c89
./test_list C89
PASSED: List C89
rm -f test_list
gcc test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -std=gnu89
./test_list GNU89
PASSED: List GNU89
rm -f test_list
g++ test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -pedantic-errors -std=c++11
./test_list C++11
PASSED: List C++11
rm -f test_list
g++ test_list.c ../src/list.c -o test_list -Wall -Wextra -Werror -std=gnu++11
./test_list GNU++11
PASSED: List GNU++11
rm -f test_list
gcc test_rbtree.c ../src/rbtree.c -o test_rbtree -Wall -Wextra -Werror -pedantic-errors -std=c89
./test_rbtree C89
PASSED: RBTree C89
rm -f test_rbtree
gcc test_rbtree.c ../src/rbtree.c -o test_rbtree -Wall -Wextra -Werror -std=gnu89
./test_rbtree GNU89
PASSED: RBTree GNU89
etc... (this goes on for a while)
ยินดีต้อนรับ!
หากคุณมีคำขอคุณสมบัติหรือพบข้อผิดพลาดอย่าลังเลที่จะเปิดปัญหาใหม่ หากคุณต้องการมีส่วนร่วมในรหัสโปรดจัดทำเอกสารอย่างละเอียดและตรวจสอบให้แน่ใจว่าได้เขียนการทดสอบสำหรับแต่ละฟังก์ชั่น/มาโคร ฉันจะช่วยสรุปรหัสและจะช่วยให้แน่ใจว่าอนุสัญญาที่ใช้นั้นสอดคล้องกัน
