Data Structures using C Notes

Download Assignment 1

Download Assignment 2

Download Assignment 3

Download unit 1

Download unit 2

Download unit 3-5

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:

1. Each element is of the same data type.
2. Stored at contiguous memory locations.
3. Allows random access using an index.

Advantages of Arrays

1. Code Optimization: Less code is required to access data.
2. Ease of Traversing: Simple loop-based access.
3. Ease of Sorting: Sorting can be done efficiently.
4. Random Access: Direct access using an index.

Disadvantages of Arrays

1. Fixed Size: Cannot exceed the declared size.
2. 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.