Arrays
An array is a collection of items stored at contiguous memory locations. The idea is to declare multiple items of the same type together. Array declaration: In C, we can declare an array by specifying its and size or by initializing it or by both.
int arr[10];
// Array declaration by specifying size
int arr[] = {10, 20, 30, 40};
// Array declaration by initializing elements
int arr[6] = {10, 20, 30, 40}
// Array declaration by specifying size and initializing elements
Formulas:
Length of Array = UB - LB + 1
UB = Upper bound
LB = Lower bound
Given the address of the first element, the address of any other element is calculated using the formula:-
Loc (arr [k]) = base (arr) + w * k
w = number of bytes per storage location
of for one element
k = index of the array whose address we want
to calculate
Elements of two-dimensional arrays (men) are stored in two ways:-
Column major order: Elements are stored column by column, i.e. all elements of the first column are stored, and then all elements of the second column stored and so on.
Loc(arr[i][j]) = base(arr) + w (m *j + i)
Row major order: Elements are stored row by row, i.e. all elements of first row are stored, and then all elements of second row stored and so on.
Loc(arr[i][j]) = base(arr) + w (n*i + j)
Stacks
A stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Basic operations :
Push:
Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition. (Top=Top+1)
Pop:
Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.(Top=Top-1)
Peek:
Get the topmost item.
Infix, prefix, Postfix notations
Infix notation:
X + Y - Operators are written in-between their operands. This is the usual way we write expressions. An expression such as
A * ( B + C ) / D
Post fix notation (also known as "Reverse Polish notation"):
X Y + Operators are written after their operands. The infix expression given above is equivalent to
A B C + * D/
Prefix notation (also known as "Polish notation"):
+ X Y Operators are written before their operands. The expressions given above are equivalent to
/ * A + B C D
Converting between these notations:
Tower of Hanoi
PROBLEM :
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
For n disks, total 2n – 1 move are required
Time complexity : O(2n) [exponential time]
SOLUTION :
//author @v
#include <iostream>
using namespace std;
void towerOfHanoi(int n, char A, char B, char C)
{
if (n == 1)
{
cout << "Move disk from rod " << A << " to rod " << B<<endl;
return;
}
towerOfHanoi(n - 1, A, C, B);
cout << "Move disk " << n << " from rod " << A << " to rod " << B << endl;
towerOfHanoi(n - 1, C, B, A);
}
int main()
{
int n = 4; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
}
Queues
The queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
Stack:
Remove the item the most recently added Queue: Remove the item the least recently added Operations on Queue:
Enqueue:
Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue:
Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from the queue.
Rear: Get the last item from the queue.
Linked Lists
Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.
Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
SINGLE LINK LIST :
ADVANTAGE OF LINK LIST
DOUBLY LINK LIST
CIRCULAR LINK LIST
DIFFERENCE BETWEEN ARRAY AND LINK LIST
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list. Representation in C: A linked list is represented by a pointer to the first node of the linked list. The first node is called ahead. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) data
2) pointer to the next node In C, we can represent a node using structures. Below is an example of a linked list node with integer data.
// A linked list node
struct node
{
int data;
struct node *next;
};
let's make it simple
by av
Comments