Skip to content

Latest commit

 

History

History
510 lines (430 loc) · 16.2 KB

README.md

File metadata and controls

510 lines (430 loc) · 16.2 KB
Raw

C Data Structures And Algorithms

  • Generic
  • Unit tested
  • Terminating errors
  • Documented

General overview:

library C files total lines of code total lines of comments
implemented data structures implemented algorithms

Implemented Data Structures

Trees

  1. Red Black Tree

    • Initialization
    • Insertion
    • Deletion
    • Searching
    • Contains
    • Print
    • Pre order traversal
    • In order traversal
    • Post order traversal
    • Get Size
    • Is Empty
    • Transform to array
    • Clear
    • Destroy

  2. AVL Tree

    • Initialization
    • Insertion
    • Deletion
    • Searching
    • Contains
    • Pre order traversal
    • In order traversal
    • Post order traversal
    • Breadth first traversal
    • Get Size
    • Is Empty
    • Transform to array
    • Clear
    • Destroy

  3. Binary Tree

    • Initialization
    • Insertion
    • Deletion
    • Searching
    • Contains
    • Pre order traversal
    • In order traversal
    • Post order traversal
    • Get Size
    • Is Empty
    • Transform to array
    • Clear
    • Destroy

  4. Splay Tree

    • Initialization
    • Insertion
    • Deletion
    • Searching
    • Contains
    • Get Size
    • Is Empty
    • Transform to array
    • Clear
    • Destroy

  5. Binary Heap

    • Initialization
    • Insertion
    • Deletion
    • Searching
    • Contains
    • Get Size
    • Is Empty
    • Transform to array
    • Clear
    • Destroy

  6. Trie

    • Initialization
    • Add word
    • Remove Word
    • Contains Word
    • Auto completion
    • Generate suggestions
    • Print words
    • Clear
    • Destroy

Graphs

  1. Directed Graph

    • Initialization
    • Add node
    • remove node
    • add edge
    • remove edge
    • Contains node
    • Contains edge
    • Get size
    • Is empty
    • Print
    • Depth first traversal
    • Breadth first traversal
    • Topological sort
    • Check if node is a part of cycle
    • Graph Contains Cycles
    • Clear
    • Destroy

  2. Undirected Graph

    • Initialization
    • Add node
    • remove node
    • add edge
    • remove edge
    • Contains node
    • Contains edge
    • Get edge weight
    • Get size
    • Is empty
    • Print
    • Shortest distance (Dijkstra's algorithm)
    • Shortest path (Dijkstra's algorithm)
    • Minimum spanning graph (Prim's algorithm)
    • Check if node is a part of cycle
    • Graph Contains Cycles
    • Clear
    • Destroy

Tables

  1. Hashmap

  2. Linked list hashmap

    • Initialization
    • Insertion
    • Deletion
    • Search for value
    • Search for key
    • Contains
    • Transform to value array
    • Transform to entry array
    • Get size
    • Is empty
    • Clear
    • Destroy

  3. Hashset

    • Initialization
    • Insertion
    • Deletion
    • Search
    • Contains
    • Transform to array
    • Get size
    • Is empty
    • Clear
    • Destroy

Strings

  1. String
    • Initialization
    • Append character
    • Add character at index
    • Update character
    • Remove character
    • Append char array or string
    • Change string by another char array or string
    • Get character index
    • Get character at index
    • Is sub string of another char array or string
    • Convert to char array
    • Convert to char array between specific range
    • Is equal to char array or to string
    • Compare with char array or with string
    • Get length
    • Trim, trim start, and trim end
    • Custom trim, trim start, and trim end
    • Scan input
    • Print
    • Split
    • Clear
    • Destroy

Lists

  1. Vector

  2. Array list

    • Initialization
    • Insertion
    • Deletion
    • Contains
    • Get
    • Get index and get last index
    • Transform to array and sub array
    • Sort
    • Get length
    • Is empty
    • Print
    • Clear
    • Destroy

  3. Set

    • Initialization
    • Insertion
    • Deletion
    • Contains
    • Get
    • Get index
    • Transform to array
    • Get length
    • Is empty
    • Clear
    • Destroy

  4. Linked list

  5. Doubly linked list

    • Initialization
    • Insertion
    • Deletion
    • Get
    • Get index
    • Get item
    • Get at index
    • Get first and last
    • Contains
    • Transform to array
    • Get length
    • Is empty
    • Print
    • Clear
    • Destroy

Matrices

  1. Matrix

    • Initialization
    • Insertion
    • Deletion
    • Get
    • Get index
    • Contains
    • Add row at last and at index
    • Add column at last and at index
    • Remove row at index
    • Remove column at index
    • Get number of rows
    • Get number of columns
    • Get number of items
    • Is empty
    • Transform to array
    • Print
    • Clear
    • Destroy

Pairs

  1. Pair

    • Initialization
    • Get first and second
    • Set first and second
    • Set first and second without freeing the old elements
    • Swap elements
    • Destroy

Stacks

  1. Stack

  2. Doubly linked list stack

    • Initialization
    • Push
    • Pop
    • Peek
    • Contains
    • Is equal to another stack
    • Transform to array
    • Get length
    • Is empty
    • Clear
    • Destroy

Queues

  1. Queue

  2. Linked list queue

  3. Stack queue

  4. Priority queue

  5. Priority queue implemnted using binary heap

    • Initialization
    • Enqueue
    • Dequeue
    • Peek
    • Get length
    • Is empty
    • Transform to array
    • Clear
    • Destroy

Deque

  1. Deque

  2. Doubly linked list deque

    • Initialization
    • Insert front and end
    • Get front and end
    • Peek front and end
    • Get length
    • Is Empty
    • Transform to array
    • Clear
    • Destroy

Implemented Algorithms

Arrays Algorithms

Function Complexity Comments
reverse array O (n)
get most frequent value A O (n ^ 2) this function will use a resizable array to store the repeated values
get most frequent value H O (n) this function will use a hash map to store the repeated values
print array O (n) this function will need a helper printing function
resize array O (n)
array resize and copy O (n) this function will allocate a new array with the new length and then it will copy the values in the original array into the new one
array resize and copy of range O (k) and k is the length of the copying range this function will allocate a new array with the new length and then it will copy the values between the provided into the new array
array copy O (n) this function will allocate a new array then it will copy the values in the original array into the new one
array copy of range O (k) and k is the length of the copying range this function will allocate a new array then it will copy the values between the provided range into the new array
fill array O (n)
fill array in range O (k) and k is the length of the range
compare arrays O (n)
compare arrays in range O (k) and k is the length of the range
array mismatch O (n)
array mismatch in range O (k) and k is the length of the range
array anagrams S O (n log(n)) this function will sort the array first to determine if they are equals
array anagrams H O (n) this function will use a hash map the compare the arrays
array remove duplicates A O (n ^ 3) this function will use a resizable array to detect the duplicates
array remove duplicates H O (n ^ 2) this function will use a hash map to detect the duplicates
array count values O (n)
is sub array O (n ^ 2)
array get index O (n)
array contains O (n)
array remove at index O (n)
array sort O (n log(n)) this function will use quick sort algorithm to sort the array, note that quick sort complexity can be O (n ^ 2)
array get first O (n)
array get last O (n)
array get all O (n)
array binary search O (log(n))
array is palindrome O (n)
array is rotation of an array O (n)
array update element O (1)
array add O (n)
array add all O (n)
array swap two indices O (1)

Char Array Algorithms

Function Complexity Comments
is sub string O (n ^ 2)
reverse words O (n)
custom trim start O (n ^ 2)
trim start O (n ^ 2)
custom trim end O (n)
trim end O (n)
custom trim O (n ^ 2)
trim O (n ^ 2)
contains O (n)
remove character O (n)
is integer O (n)
is floating point O (n)
sum characters ASCII O (n)
hash char array O (n) this function actually will return the sum the the characters ASCII
generate char array O (n) this function will allocate a new char array then it will copy the original char array into the new one
generate char pointer O (1) this function will generate a char pointer to a character
is alphabet C O (1) this function will take a character value then it will check if it's an alphabet character
is alphabet O (1) this function will take a character pointer then it will check if it's an alphabet character
comparison function P O (1) this function will take two character pointers then it will compare there ASCII values
comparison function O (1) this function will take two character value then it will compare there ASCII values
split S O (n) this function will split the char array into strings vector
split C O (n) this function will split the char array into char arrays vector
most repeated character O (n) this function will use a hash map

Search Algorithms

Function Complexity Comments
binary search O (log(n)) the log is to base 2
ternary search O (log(n)) the log is to base 3
linear search O (n)
jump search O (sqrt(n))
exponential search O (log(i)) and i represents the length of searching area )

Sort Algorithms

Function Complexity Comments
bubble sort O (n ^ 2) in best case the complexity could be O ( n )
selection sort O (n ^ 2)
insertion sort O (n ^ 2) in best case the complexity could be O ( n )
merge sort O (n log(n)) there are two implementations first one with space complexity O ( n ) and worst case time complexity O ( n log(n) ), and the another one with space complexity O ( 1 ) and worst case time complexity O ( n ^ 2 )
quick sort O (n log(n)) in the worst case the complexity could be O (n ^ 2)
heap sort O (n log(n))
counting sort A O (n) this type of sorting works only on unsigned integers, note this function will use an array to count the values so it will allocate an extra memory
counting sort H O (n) this type of sorting works only on unsigned integers, note this function will use a hashmap so it will use less memory that the array implementation

Integer Operations

  • Get number of digits
  • Transform to char array
  • Max int
  • Min int
  • Compare integers
  • Compare integers reverse
  • Compare integers pointers
  • Compare integers pointers reverse
  • Generate integer pointer from another integer pointer
  • Generate integer pointer from an integer value
  • Integer hash function
  • Sum two integers
  • Sum array of integers

Extra

Text Files Handler

  1. Text File Loader

    • Initialization
    • Read file as string or as char array
    • Read file lines
    • Read file using a delimiter
    • Count lines
    • Read a specific line as a string or a char array
    • Write a string or a char array
    • Append a string or a char array at the end of the file
    • Append a string or a char array at the end of a specific line
    • Add a string or a char array at a specific line index
    • Update a specific line using a string or a char array
    • Remove a specific line
    • Change file
    • Clear the text file
    • Destroy

  2. Input Scanner

    You should pass stdin file to the function to scan the input.

    • Scan String
    • Scan char array
    • Scan character
    • Scan integer
    • Scan long
    • Scan long long
    • Scan short
    • Scan double
    • Scan float

Error Codes

The errors codes generated by summing the words ASCII values of the characters and multiply every character value by it's ( index + 1 ).
The first four error code numbers are the sum of the "DATA_STRUCTURE" characters,
and the rest of the error code is the sum of the error enum.
ex: INVALID_ARG is 4987.

Error Error code Message
FAILED_ALLOCATION -833811484 "The %s allocation in %s failed."
FAILED_REALLOCATION -833814245 "The %s reallocation in %s failed."
FAILED_COPY -83385167 "Copying %s in %s failed."
INVALID_ARG -83384987 "The passed arg %s in %s is invalid."
NULL_POINTER -83386157 "The %s pointer in %s is NULL."
OUT_OF_RANGE -83385991 "The passed index is out of the %s range."
EMPTY_DATA_STRUCTURE -833816740 "The passed %s pointer is empty."
SOMETHING_WENT_WRONG -833816834 "Can't %s in %s."