A Data Structure is a way of organizing and storing data in a computer system. It provides a systematic and efficient way of accessing and manipulating data. Data structures are designed to suit different types of data and various operations that need to be performed on that data.
An Array is a fundamental Data Structure that allows storing a fixed-size sequence of elements of the same type. It provides a way to organize and access data in a contiguous block of memory. Each element in an array is identified by its index, which represents its position within the Array.
Click here to see its implementation.
A Matrix is a two-dimensional Array (like an Array of Arrays) organized in rows and columns. A Matrix is made up of rows and columns. The number of rows and columns in a Matrix determines its size or dimensions. For example, an "m x n" Matrix has "m" rows and "n" columns.
Click here to see its implementation.
A List is a Data Structure that stores a collection of elements in a specific order. It is a fundamental data structure in computer science and is commonly used to organize and manipulate data.
A Singly Linked List is a Data Structure used to store a collection of elements. It consists of a sequence of nodes, where each node contains both the element and a reference (or pointer) to the next node in the List. The last node in the List has a reference to null, indicating the end of the List.
Click here to see its implementation.
A Doubly Linked List is a Data Structure that extends the functionality of a Singly Linked List by providing links or references to both the previous and next nodes in the List. Each node in a Doubly Linked List contains three components: the data or element to be stored, a reference to the previous node, and a reference to the next node.
Click here to see its implementation.
A Circular Doubly Linked List is a variation of a Doubly Linked List where the last node in the List has a reference to the first node, creating a circular structure. This means that the next node of the last node points back to the first node, and the previous node of the first node points to the last node.
Click here to see its implementation.
A Stack is a fundamental Data Structure in computer science that follows the LIFO (Last-In, First-Out) principle. It models a collection of elements with two primary operations: push and pop.
A Static Stack is a Stack Data Structure that is implemented using a fixed-size Array or a static memory allocation. Unlike a Dynamic Stack, where the size can grow or shrink dynamically as elements are pushed or popped, a Static Stack has a predetermined size that is allocated at the time of its creation.
Click here to see its implementation.
A Dynamic Stack is a Stack Data Structure that can grow or shrink in size dynamically as elements are pushed or popped. Unlike a Static Stack, which has a fixed size allocated at the time of creation, a Dynamic Stack can adjust its capacity based on the number of elements it currently holds.
Click here to see its implementation.
A Queue is a Data Structure that follows the FIFO (First-In, First-Out) principle, where elements are added at the rear and removed from the front. It allows for efficient insertion and deletion operations.
A Static Queue, if referring to a fixed-size Queue, would be implemented using a fixed-size array or a static memory allocation. The capacity of the Static Queue would be predetermined and remain constant throughout its lifetime.
Click here to see its implementation.
A Dynamic Queue is a Queue Data Structure that can grow or shrink dynamically as elements are enqueued (added) or dequeued (removed). Unlike a Static Queue, which has a fixed size allocated at the time of creation, a Dynamic Queue can adjust its capacity based on the number of elements it currently holds.
Click here to see its implementation.
A Graph is a Data Structure that represents a collection of interconnected nodes or vertices, often referred to as "points", and the connections between them, known as "edges." Graphs are used to model relationships between objects or entities.
An undirected weighted graph is a type of graph in graph theory that consists of a set of vertices and a set of edges.
The edges between vertices have no direction, which means they do not have a specific starting or ending point. If there's an edge between vertex A and vertex B, it implies that you can traverse it from A to B or from B to A with the same ease. This property reflects a symmetric relationship between connected vertices.
Each edge in the graph has an associated weight, which is a numerical value. These weights represent some measure or value associated with the relationship between the vertices connected by the edge.
Here Undirected Weighted Graph were implemented with an adjacency matrix and Array of Vertex, where the rows and columns correspond to the vertices of the graph, and the values in the matrix represent the weights of the edges between those vertices.
Click here to see its implementation.
In this context, Helpers means "more primitives Data Structures", that does not allow dependency from other complex Data Structure.
The Exception Handler is a special "class" designed to help with exception handling in the development of Data Structures.
Click here to see its implementation.
A Node is an individual element or item in the data structure. Each Node contains both data and references to the previous and next nodes.
Click here to see its implementation.
A Vertex is a “point” on a Graph that represents an entity or element. Here it was implemented with data and valency property (which means how many connections the Vertex has).
Click here to see its implementation.
To abstract some repetitive steps in the process of implementing new Data Structures or Helpers, adding dependencies, running tests, compiling, building the library, among other things, a Build Tool was created using Makefile and Shell scripts.
Is possible to create a new Data Structure or a new Helper directly in CLI instead create each directory manually.
To create a new Data Structure, in the root of the project you can run one of the commands below:
make create-dsmake create datastructureand enter the name of new Data Structure.
To create a new Helper, in the root of the project you can run one of the commands below:
make create-hmake create helperand enter the name of new Helper.
You can also add local dependencies to a Data Structure or a Helper already created.
What does means local dependencies? It means that you can add only Data Structures and Helpers created in this project.
Note that, like Helpers does not allow dependency from complex Data Structure, you can add only other Helpers as its dependencies.
If you want to add other Data Structure as dependency:
make install_dsor
make install dsIf you want to add a Helper as dependency:
make install_helperor
make install hIf you want to add other Helper as dependency:
make install_helperor
make install hTo get headers of dependencies already added on a or Data Structure on a Helper, on its directory run:
make install Each dependency has an access modifier that rule where it will be added during Adding a new dependency. There are 3 access modifiers: Public, Protected and Private.
- Public (pub): The dependency include will be on header of the parent, it means that everyone with access on header can see how this dependency is used.
- Protected (ptd): The dependency include will be on source code of parent, it means that only who can access source code is able to see how the dependency is used.
- Private (pvt): The dependency include will not be put anywhere, just on .info file. It means that it is not a direct dependency and will be used only during compile time.
The .info File is list of the Dependencies of a Data Structure or Helper during. It is used to verify if the dependency is already added during adding a new Dependency. The pattern of element of this list is: modifier_type_NameOfDependency, or modifier is the Access Modifier, type is about being a Data Structure (ds) or Helper (hp).
For example:
- Adding the Exception Handler as a public dependency:
pub_hp_ExceptionHandler - Adding the Undirected Weighted Graph version 1 as a protected dependency:
ptd_ds_UndirectedWeightedGraph1 - Adding the Array as a private dependency:
pvt_ds_Array
To test any of Listed Data Structures or Helpers, you may navigate to their respective directory and run the following command in the terminal:
make run_testsFor example, if I want to run Unit Tests for Array, then:
cd main/Array && make run_testsTo maintain a high level of quality, there are a lot of unit test for each Data Structure and Helper. If one want to run all tests at once, there are 3 modes and one can choose which is better for each situation.
It runs quicly and silent. During execution, it shows only which Data Structure or Helper are executing, time spent of executed Data Structure and Helper. At final of execution, it shows how many test was executed, how many tests passes or fail and total time of execution.
One can execute test suite in this mode by running the following command in the root of project:
make testThis mode is used to debug the test suite, and it runs slowly when compared with make test.
It shows the same as when execute make test, in addiction it shows each test executed (description and result).
One can execute test suite in this mode by running the following command in the root of project:
make test-debugThe third is a more restrictive mode and always runs before make build or make pack, ensuring that if any test fails
the entire build or pack process is interrupted.
One can execute test suite in this mode by running the following command in the root of project:
make checkThe Build Command is used to generate and compile the Library headers .h and Static Lib libds.a
when you run in the terminal:
make buildor
make bit runs check command and if all tests passes, it will create some directories:
LIBDSLIBDS/includeLIBDS/lib
The headers are in LIBDS/include and the Static Liblibds.a in LIBDS/lib.
The Pack Command goes one step further than the Build Command, as its life cycle ends after
packing the contents of the LIDBDS directory as libds.tar.gz and deleting the LIDBDS directory. Since the
Pack Command depends on the Build Command, when executed in the terminal:
make packor
make pif any tests fail, the process is interrupted.
It is said at the beginning of every header of a Data Structure in this library, but it is worth mentioning here that, as the implementation followed a concept of generics, to use it with any data type, it is necessary to implement at least 3 functions:
- TYPE printing function: To print data correctly.
- like:
void (*TYPE_print_function)(void *data) - example:
- like:
void int_print_function(void *data) {
printf("%d", int_convert_function(data));
}- TYPE convert function: As some functions returns void*, one must use a function to convert void* to TYPE*.
- like:
TYPE (*TYPE_convert_function)(void *data) - example:
- like:
int int_convert_function(void *data) {
return *((int *) data);
}- TYPE comparison function: To compare correctly data.
- like:
int (*TYPE_compare_function)(void *data1, void *data2) - example:
- like:
int int_compare_function(void *data1, void *data2) {
int d1 = int_convert_function(data1), d2 = int_convert_function(data2);
return d2 - d1;
}You can write some code, just to test some features while developing (you may consider write unit tests instead), that
implements the created Data Structures. Just write it in the file (app_X.c) inside the /main/apps directory and in
its Data Structure directory run:
make run_appsA Self-Organizing List is a Data Structure that reorganizes its elements based on the frequency of access or some other criteria in order to optimize future access patterns. It dynamically adjusts the order of elements to improve the efficiency of common operations, such as searching or accessing frequently used elements.
-
Define a Self-Organizing List of Product and implements it.
-
Can run the app in the terminal:
make run_apps- Can run tests in the terminal:
make run_testsADT is a high-level description of a Data Structure that defines the behavior of a data type independently of its implementation details. ADTs provide a logical representation of data and operations that can be performed on that data, without specifying how those operations are implemented.
- Define an ADT called float_vector and implements it.
- OS: Ubuntu 20.04.6 LTS (Focal Fossa)
- GCC: 9.4.0
- C: C17 (201710L)
- Unity Framework: 2.5.2
- Make: 4.2.1