Data Structures Using C
Introduction
Data structures are a way to store and organize data in memory efficiently. The logical and mathematical model of organizing data is called a data structure. There are many types of data structures, such as arrays, graphs, linked lists, stacks, queues, etc.
1. Types of Data Structures
Data structures are categorized into two types:
1.1 Primitive Data Structures
- The basic data structures that directly operate upon machine instructions.
- Examples:
int,char,float,double,pointer.
1.2 Non-Primitive Data Structures
- Derived from primitive data structures.
- Types:
- Linear Data Structures: Arrays, Stacks, Queues, Linked Lists.
- Non-Linear Data Structures: Trees, Graphs.
Linear Data Structures
2. Stacks
- A stack follows the LIFO (Last In, First Out) principle.
- Operations on a stack:
- Push: Adding an element.
- Pop: Removing an element.
- Peek: Viewing the top element.
3. Queues
- A queue follows the FIFO (First In, First Out) principle.
- Operations on a queue:
- Enqueue: Adding an element.
- Dequeue: Removing an element.
4. Linked Lists
- A linked list consists of nodes, each containing:
- Data: The actual value.
- Pointer: A reference to the next node.
- Types of linked lists:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Non-Linear Data Structures
5. Trees
- A tree consists of nodes connected by edges.
- Special types:
- Binary Tree: Each node has at most two children.
- Binary Search Tree (BST): Left child < Parent < Right child.
6. Graphs
- A graph consists of vertices and edges.
- Two common representations:
- Adjacency Matrix
- Adjacency List
Arrays in C
Introduction
An array is a collection of similar data types stored at contiguous memory locations.
Properties of Arrays:
- Each element is of the same data type.
- Stored at contiguous memory locations.
- Allows random access using an index.
Advantages of Arrays
- Code Optimization: Less code is required to access data.
- Ease of Traversing: Simple loop-based access.
- Ease of Sorting: Sorting can be done efficiently.
- Random Access: Direct access using an index.
Disadvantages of Arrays
- Fixed Size: Cannot exceed the declared size.
- Inefficient Insertion and Deletion: Requires shifting elements.
Types of Arrays
- One-Dimensional Array: Stores data in a single row/column.
- Multi-Dimensional Array: Stores data in tabular form (matrix).
Array Implementation in C
Declaration of 1D Array
int marks[5];Initialization of 1D Array
marks[0] = 80;
marks[1] = 60;
marks[2] = 70;
marks[3] = 85;
marks[4] = 75;Example of a 1D Array
#include<stdio.h>
int main(){
int marks[5] = {80, 60, 70, 85, 75};
for(int i = 0; i < 5; i++){
printf("%d \n", marks[i]);
}
return 0;
}Declaration of 2D Array
int twodimen[4][3];Initialization of 2D Array
int arr[4][3] = {{1,2,3},{2,3,4},{3,4,5},{4,5,6}};Example of a 2D Array
#include<stdio.h>
int main(){
int i, j;
int arr[4][3] = {{1,2,3},{2,3,4},{3,4,5},{4,5,6}};
for(i=0; i<4; i++){
for(j=0; j<3; j++){
printf("arr[%d][%d] = %d \n", i, j, arr[i][j]);
}
}
return 0;
}Operations on Arrays in C
1. Traversing
Accessing each element sequentially.
#include<stdio.h>
int main(){
int arr[] = {1, 2, 3, 4, 5};
for(int i = 0; i < 5; i++){
printf("%d ", arr[i]);
}
return 0;
}2. Insertion
Adding an element at a specific position.
#include <stdio.h>
int main() {
int arr[6] = {1, 2, 3, 4, 5};
int pos = 2, value = 10;
for (int i = 5; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value;
for (int i = 0; i < 6; i++) {
printf("%d ", arr[i]);
}
return 0;
}Adding an element at a specific position.
3. Deletion
Removing an element from a specific position.
#include <stdio.h>
int main() {
int arr[5] = {1, 2, 3, 4, 5};
int pos = 2;
for (int i = pos; i < 4; i++) {
arr[i] = arr[i + 1];
}
for (int i = 0; i < 4; i++) {
printf("%d ", arr[i]);
}
return 0;
}Removing an element from a specific position.
Conclusion
Data structures help in organizing and managing data efficiently. Arrays, stacks, queues, linked lists, trees, and graphs each have their own strengths and applications. Understanding these structures is essential for efficient programming in C.