- Welcome to DataStructures: Mastering Data Structures!
- What are Data Structures
- What is C++?
- Why C++?
- What is C Programming Language?
- History of C Language
- Key Applications
- How C Programming Language Works?
- Syntax
- Operators
- Memory Management
- Automatic Memory Allocation
- What to Expect
- Who Can Benefit?
- Contributions Welcome
- Stay Connected
- References
- 📦What are Data Structures
- 🏗️ What is C++ ?
- 🔨 Why C++?
- 🔍What is C Programming Language ?
- 🏰History of C Language
- 🔑Key Applications
- 🔧How C Programming Language Works?
- 📝Syntax
- 🌳Operators
- 💾Memory management
- 📚 What to Expect
- 🌈 Who Can Benefit?
- 📌 Contributions Welcome
- 📡 Stay Connected
- ⛳ References
If you're new to C++ or looking to refresh your knowledge, you can start with the introductory writeups and simple code examples in this repository. Each topic is organized into a separate folder with relevant writeups and code files.
- Browse through the topics in the repository.
- Read the writeups and explanations for the concepts you want to learn.
- Experiment with the provided code examples and practice on your own.
- Feel free to open issues or pull requests if you have questions or suggestions.
C++ is a general-purpose programming language that was created as an extension of the C programming language. It was developed by Bjarne Stroustrup at Bell Labs in the early 1980s. C++ is designed with a focus on system programming, embedded systems, and performance-critical applications, while also providing features for general-purpose programming.
Key features of C++ include:
-
Object-Oriented Programming (OOP): C++ supports the principles of object-oriented programming, including encapsulation, inheritance, and polymorphism. This allows developers to structure code in a way that models real-world entities and relationships.
-
Low-Level Manipulation: Like C, C++ provides low-level programming features such as pointers and manual memory management, making it suitable for systems programming and tasks where fine control over hardware resources is required.
-
Standard Template Library (STL): C++ includes a powerful library known as the Standard Template Library, which provides a collection of generic classes and functions with templates. It includes data structures, algorithms, and other utilities that help in writing efficient and reusable code.
-
Performance: C++ allows for direct manipulation of memory, which can lead to highly efficient code. It's often used in applications where performance is critical, such as game development, real-time systems, and high-performance computing.
-
Portability: C++ programs can be written to be highly portable across different platforms. This is particularly important for software that needs to run on various operating systems and hardware architectures.
-
Versatility: C++ is versatile and can be used for a wide range of applications, including system software, game development, embedded systems, web development, and more.
C++ has gone through several standardizations over the years, with each version introducing new features and improvements. The most recent major version is C++20, which was released in 2020. The C++ standards committee continues to work on future versions to enhance the language and address the evolving needs of developers.
Timeline of C++ language development
| Year | Event Occured |
|---|---|
| 1979 | Bjarne Stroustrup starts working on "C with Classes" at Bell Labs. |
| 1983 | First edition of "The C++ Programming Language" released. |
| 1985 | Adoption of the name "C++." |
| 1989 | First edition of the Annotated C++ Reference Manual published. |
| 1990 | AT&T releases the first commercial implementation of C++. |
| 1998 | ISO adopts the first international standard for C++ (C++98 or C++03). |
| 2003 | Release of C++03, incorporating bug fixes and clarifications. |
| 2011 | Major update with C++11, introducing significant features. |
| 2014 | Release of C++14, including bug fixes and small improvements. |
| 2017 | Release of C++17, introducing additional features and improvements. |
| 2020 | Release of C++20, bringing major language and library enhancements. |
Now, you might wonder, "Why C++?" Well, it's like having the perfect toolset for the job. C++ gives you the ability to play with high-level abstractions while also getting your hands dirty with low-level details. Firstly, C++ is a powerful, versatile programming language, well-suited for implementing data structures. Its combination of high-level abstractions and low-level control makes it an ideal choice for understanding the inner workings of these critical components. Whether you're new to C++ or already experienced, you'll find this repository helpful in mastering data structures within the context of this language. 🚀
According to Wikipedia, C is a general-purpose, procedural computer programming language supporting structured programming, lexical variable scope, and recursion, with a static type system. By design, C provides constructs that map efficiently to typical machine instructions. It is a structured programming language that is machine-independent and extensively used to write various applications, Operating Systems like Windows, and many other complex programs like Oracle database, Git, Python interpreter, and more.
Data structures are like the superheroes of programming, helping us organize and work with data in the most efficient way possible. Think of them as the secret sauce that makes our software awesome. In this cozy corner of the internet, we'll take you on a delightful tour of various data structures, from the basics to the advanced, giving you a sneak peek into their magic tricks and practical uses.
C is an imperative language designed to compile relatively straightforwardly, which provides low-level memory access. With the gradual increase in the program's popularity, the vocabulary and its compiler have become available on various platforms, from embedded microcontrollers to supercomputers.
Several features have been included in the C language with the introduction of the K&R C language (a new edition of C published in 1978 by Brian Kernighan and Denis Ritchie).
- C is a general-purpose, high-level language that was originally developed by Dennis M.Ritchie and Ken Thompson to develop the UNIX operating system at AT&T Bell Labs.
- C was originally first implemented on the DEC PDP-11 computer in 1972 and was developed in assembly language.
- The language was named “C” because its features were derived from “B”, which according to Ken Thompson was a stripped-down version of the type less BCPL programming language.
- In 1977, Oracle database development started, and in 1983 its code was rewritten from assembly to C. It became one in all the foremost widespread databases within the world.
- In 1989 the American National Standards Institute (ANSI) committe published a standard for C (generally called “ANSI C”)
Timeline of language development
| Year | Event |
|---|---|
| 1972 | Dennis Ritchie and Ken Thompson develop the C programming language at Bell Labs. |
| 1973 | C is used to rewrite the Unix operating system, providing portability. |
| 1978 | Brian Kernighan and Dennis Ritchie publish "The C Programming Language" book. |
| 1983 | The American National Standards Institute (ANSI) establishes a committee to standardize C. |
| 1989 | ANSI releases the first standardized version of the C language (ANSI C). |
| 1990 | The International Organization for Standardization (ISO) adopts ANSI C. |
| 1999 | ISO releases the C99 standard, introducing new features and improvements. |
| 2011 | ISO releases the C11 standard, providing further enhancements to the language. |
| 2018 | ISO releases the C18 standard, which is a bug fix release with no new features. |
- As a middle-level language, C combines the features of both high-level and low-level languages. C can be used for low-level programming, such as scripting for drivers and kernels. It also supports functions of high-level programming languages, such as scripting for software applications, etc.
- It is used for developing browsers and their extensions. Google’s Chromium is built using ‘C’ programming language.
- ‘C’ language is widely used in embedded systems.
- C language has a rich library which provides a number of built-in functions. It also offers dynamic memory allocation.
- C is a general-purpose programming language and can efficiently work on enterprise applications, games, graphics, and applications requiring calculations, etc.
- C is highly portable and is used for scripting system applications which form a major part of Windows, UNIX, and Linux operating system.
C is a compiled programming language. This means that we need to convert our source files (human-readable text files) into object files (which can be understood by the machine: microcontroller, computer/laptop).
Developing software using the C programming language involves several tasks/phases. To successfully create an application/program, we need to have an editor, a compiler, a linker, and a loader. Most of the IDE (e.g., Code Blocks, Eclipse, Geany, etc.) for C programming provide all these necessary tools.
The process of developing an application in C is described in the picture below:
-
Editing: Editing or writing source code containing all the instructions that need to be executed by the machine in a text format (understandable by humans) is the first step of developing an application by a plain text editor (Notepad etc.) or the editor provided by the IDE (Integrated development environment). The source code must be in C language syntax and saved as a .c file.
-
Compiling: If we want to use a simple text editor for the source code, we need to install a C compiler. The compilation task contains the initial phase, which is known as preprocessing. A preprocessor invoked by the compiler executes the preprocessing. The preprocessor goes over the source for all the lines starting with the
#(hash) key called compiler directives.One of the compiler's directives includes external functions from our source code. The preprocessor removes all the compiler directives from the source code but remembers what additional files need to be included later in the process. A temporary file will be created at the end of the preprocessing, which is not visible to the user.
After the preprocessing, the compiler converts our source file into an object file. The object file is also named machine code. It can be interpreted by the computer's Central Processing Unit or microcontroller.
The object file is ready, but some undefined references are missing. These vague references are pieces of code that must be retrieved from another place. In our case, the undefined reference is the
printf()function. We know where to get the code for this function because the compiler directive specified it (#include<stdio.h>).stdio.his a header file (extension.h) which includes the declaration ofprintf()function. We can specify where to find the definition of theprintf()function by including the header file. -
Linking: Both Object files and Static library files for the external functions are needed. The static library files (
.lib) contain the definition of the external functions used in our source file. In our particular case, the static library file will have the machine code of theprintf()function.A linker performs the linking. It will search all the object files and replace all the undefined references with the referenced machine code within the library files. We will have an executable file at the end of the linking process (e.g.,
.exefor Windows applications,.hexfor microcontrollers). -
Loading: A loader performs that loading the program file into the computer’s memory. Usually, the link will include the loader in the executable file. When we run the executable, it will trigger the loader, which will load the program into the memory and begin the execution.
Tthe basic C reference character set includes the following:
- Lowercase and uppercase letters of ISO Basic Latin Alphabet:
a–zA–Z - Decimal digits:
0–9 - Graphic characters:
! " # % & ' ( ) * + , - . / : ; < = > ? [ \ ] ^ _ { | } ~ - Whitespace character
Keywords are predefined, reserved words used in programming with special meanings to the compiler. Keywords are part of the syntax, and they cannot be used as an identifier.
int rabbit;Here, int is a keyword that indicates rabbit which is a variable of type integer. Here is the list of keywords allowed in ANSI C.
An arithmetic operator performs mathematical operations on numerical values such as addition, subtraction, multiplication, division, etc.
| Operator | Description |
|---|---|
| + | addition or unary plus |
| - | subtraction or unary minus |
| * | multiplication |
| / | Divides numerator by de-numerator. |
| % | Modulus Operator and remainder of after an integer division. |
An expression containing logical operator returns either 0 or 1 depending upon whether expression results true or false. Logical operators are commonly used in decission making in C programming.
| Operator | Description | Example |
|---|---|---|
| && | Logical AND operator. If both the operands are non-zero, the condition becomes true(1). | If c = 5 and d = 2 then, expression ((c==5) && (d>5)) equals to 0. |
| ll | Called OR Operator, If any of the two operands are non-zero, the condition becomes true (1). | If c = 5 and d = 2 then, expression ((c==5) |
| ! | It is called Logical NOT Operator. It is used to reverse the logical state of its operand. If a condition is true (1), the Logical NOT operator will make it false (0). | If c = 5 then, expression !(c==5) equals to 0. |
An assignment operator is used for assigning a value to a variable.
| Operator | Meaning | Example |
|---|---|---|
| = | The most common and simple assignment operator. Assigns values from right side operands to left side operand | x = y |
| += | It adds the right operand to the left operand and assign the result to the left operand. | x = x+y |
| -= | It subtracts the right operand from the left operand and assigns the result to the left operand. | x = x-y |
| *= | It multiplies the right operand with the left operand and assigns the result to the left operand. | x = x*y |
| /= | It divides the left operand with the right operand and assigns the result to the left operand. | x = x/y |
| %= | It takes modulus using two operands and assigns the result to the left operand. | x = x%y |
| Operator | Description |
|---|---|
| == | If the values of two operands are equal or not. If yes, then the condition becomes true. |
| != | Checking that if the values of two operands are equal or not. If the values are not equal, then the condition becomes true. |
| > | Suppose the value of the left operand is greater than the value of the right operand. If yes, then the condition becomes true. |
| < | Let's say the value of the left operand is less than the value of the right operand. If yes, then the condition becomes true. |
| >= | If the value of the left operand is greater than or equal to the value of the right operand. If yes, then the condition becomes true. |
| <= | Checks if the value of the left operand is less than or equal to the value of the right operand. If no, then the condition becomes false. |
During computation, mathematical operations are converted to bit-level, making processing faster and saving power. They are used in C programming to perform bit-level operations.
| Operator | Description |
|---|---|
| & | Bitwise AND |
| l | Bitwise OR |
| ^ | Bitwise exclusive OR |
| ~ | Bitwise complement |
| << | Shift left |
| >> | Shift right |
💡 Bitwise operator perform bit-by-bit operation. The truth tables for the operators.
| p | q | p & q | p l q | p ^ q |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| Operator | Description | Example |
|---|---|---|
| sizeof() | Gives the size of a variable. | sizeof(int) = 4 |
| & | (Ampersand) Returns adress of the variable. In other words, the answer of "where is the variable stored?" | &x; gives the actual address of the variable. |
| * | Pointer to a variable. | *c; |
| ? : | Conditional Expression. | If Condition is true ? then value X : otherwise value Y |
Memory management in C++ involves allocating and deallocating memory for variables and data structures during program execution. C++ provides both manual and automatic memory management mechanisms. Here are the key aspects of memory management in C++:
Automatic Variables: Variables declared inside a function are typically allocated on the stack. They are automatically deallocated when they go out of scope.
void exampleFunction() {
int localVar = 10; // localVar is allocated on the stack
} // localVar is automatically deallocated when the function exitsDynamic Memory Allocation: C++ provides operators new and delete for dynamic memory allocation on the heap. The new operator allocates memory, and the delete operator deallocates it.
int* dynamicVar = new int; // Allocates memory on the heap
delete dynamicVar; // Deallocates memorystd::unique_ptr and std::shared_ptr: These smart pointers manage memory automatically and help prevent memory leaks. std::unique_ptr is used when ownership is unique, while std::shared_ptr is used when multiple pointers share ownership.
#include <memory>
std::unique_ptr<int> uniqueVar = std::make_unique<int>(42);
std::shared_ptr<int> sharedVar = std::make_shared<int>(42);RAII (Resource Acquisition Is Initialization): It is a C++ programming technique that binds the lifecycle of a resource to the scope of an object.
class MyResource {
public:
MyResource() { /* Acquire resource */ }
~MyResource() { /* Release resource */ }
};
void exampleFunction() {
MyResource resource; // Resource is automatically released when 'resource' goes out of scope
}Arrays with new and delete: If you need to allocate memory for an array dynamically, use new[] and delete[].
int* dynamicArray = new int[5]; // Allocates an array of 5 integers on the heap
delete[] dynamicArray; // Deallocates the arrayAvoid Manual Memory Management When Possible: Use smart pointers and standard containers to manage memory automatically.
-
Always Free Dynamically Allocated Memory: To prevent memory leaks, ensure that memory allocated with new is deallocated with
deleteordelete[]. -
Prefer Stack Allocation: Use the stack for short-lived variables, and the heap for dynamic data with longer lifetimes.
-
Be Cautious with Pointers: Avoid using raw pointers when possible. If necessary, use smart pointers to manage ownership and lifetimes.
C++ provides a flexible and powerful memory management system, but it requires developers to be mindful of memory allocation and deallocation to prevent issues like memory leaks and dangling pointers. Smart pointers and RAII principles are crucial for effective and safe memory management in modern C++ code.
One of the essential functions of a programming language is to provide facilities for managing memory and the objects stored in memory. C provides three distinct ways to allocate memory for objects:
- Static memory allocation
- Dynamic memory allocation
- Automatic memory allocation
In Static Memory Allocation, the memory for your data is allocated when the program starts. The size is fixed when the program is created. It applies to global variables file scope variables and is qualified with statically defined inside functions. Each static or global variable defines one block of space of a fixed size. The area is allocated once your program starts (part of the exec operation) and is never freed. This memory allocation is set and cannot be changed, i.e., increased or decreased after allocation. Example as following for static memory allocation:
int b;
int c[10];
char x; The concept of dynamic memory allocation in c language allows users to allocate memory at runtime. Dynamic memory allocation is possible by four functions already defined in stdlib.h header file.
malloc()calloc()realloc()free()
The name "malloc" stands for memory allocation.
The malloc() function reserves a block of memory of the specified number of bytes. It gives a pointer of void which can be casted into pointers of any form.
Syntax
pointer = (castType*) malloc(size);The calloc() function allocates multiple blocks of requested memory. It initializes all bytes to zero. It returns NULL if memory is not sufficient.
pointer = (castType*) calloc(number, byte-size) If the dynamically allocated memory is insufficient or more than required, we can change the size of previously allocated memory using the realloc() function.
pointer = realloc(pointer, newsize) Dynamically allocated memory created with either calloc() or malloc() is not freed independently. You must explicitly use free() to release the space.
free(pointer); Automatic allocation happens when you declare an automatic variable, such as a function argument or a local variable. An automatic variable is allocated when the compound statement containing the declaration is entered and freed when that compound statement is exited.
In DataStructures, you'll find a comprehensive collection of resources, including:
📖 Tutorials: Step-by-step guides to understanding each data structure, complete with examples and explanations.
📦 Implementation: Hands-on coding experience to grasp the practical side of data structures.
🔗 References: Links to further readings, documentation, and external resources for deeper knowledge.
🗂️ Sample Projects: Real-world applications of data structures in action.
This repository is designed to cater to a wide audience:
-
Beginners: If you're new to data structures and programming, you'll find a welcoming environment to learn and grow.
-
Intermediate Developers: For those looking to strengthen their skills and deepen their knowledge.
-
Experienced Coders: Even if you're a pro, there's always something new to discover or reinforce.
This repository is a community effort, and we encourage you to get involved! Whether you want to contribute tutorials, improve existing content, or report issues, your participation is valued and appreciated.
To stay updated with the latest content and discussions, follow this repository and participate in the community. Together, we can make DataStructures a go-to resource for data structures in C++. Let's learn, code, and explore the world of data structures together!
Ready to get started? Let's deep dive into the world of data structures. 💻🔍
Happy meows :3! 🐱
-
C (programming language). (2001, November 10). Wikipedia, the free encyclopedia. Retrieved February 4, 2022, from https://en.wikipedia.org/wiki/C_(programming_language)
-
Kernighan, Brian W.; Ritchie, Dennis M. (February 1978). The C Programming Language (1st ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 978-0-13-110163-0.
-
Fruderica (December 13, 2020). "History of C". The cppreference.com. Archived from the original on October 24, 2020. Retrieved October 24, 2020.
-
Moore. (2021, July 26). Benefits of C / C++ over other programming languages. Invensis Technologies. https://www.invensis.net/blog/benefits-of-c-c-plus-plus-over-other-programming-languages/?utm_source=invensis-blog&utm_campaign=blog-post&utm_medium=content-link&utm_term=applications-of-c-c-plus-plus-in-the-real-world
-
X-engineer. (2022). How C programming works. x-engineer.org. https://x-engineer.org/c-programming-works/
-
C if...else statement. (n.d.). Programiz: Learn to Code for Free. https://www.programiz.com/c-programming/c-if-else-statement
-
Stanford University - Programming Abstractions (in C++), Online course with lecture videos and materials: https://see.stanford.edu/Course/CS106B
-
Stack Overflow, C++ tagged questions: https://stackoverflow.com/questions/tagged/c%2B%2B
-
Stack Overflow, C tagged questions: https://stackoverflow.com/questions/tagged/c