Introduction

Nothing to say more than hello 👋, In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept. Make sure to follow because I will start more advanced series in future.

Structures

Introduction to structures

We use arrays when we have elements of same type. We use structures when we have elements of different types like name and age one is integer and other is string.

we define structure like this

struct
{
    int i;
    char c;
} x, y , z;

x.i = 10;
x.c = 'a';

now each of x , y and z will have i and c for them self.

we can have structure inside structure

struct {
    struct {
        ...
    }
}

we can use a tag with struct

//this called blueprint and no memory allocated
struct ex 
{
    int i;
    char c;
};
struct ex1
{
    struct ex a;
    struct ex b;
};

// here space will be allocated
struct ex x = {5,'a'};
struct ex1 t;
t.a.i = 10;
t.a.c = 'a';

examples

example 1

struct node
{
    int i;
    int j;
}

struct node a,*p; 
// a is struct of type node
// p is a pointer which point to struct node
p = &a;
// *p.i this is wrong because compiler will treat it like *(p.i) 
(*p).i = 10;
p->i = 10;

accessing it using pointer is commonly used because if it's created using malloc it will not have a name , so programmers introduced a new operator ->

example 2

struct node
{
    int i;
    int *c;
};
struct node a[2] , *p;
int b[2] = {30 , 40};
p = &a[0];
a[0].i = 10;
a[1].i = 20;
a[0].c = b;

image-20200827102423504

that we have till now orange arrow mean pointing to

// assume we are resetting every thing after each line
// x = i++ , will take x = i , then after it assign it i will be i+1
++p -> i; // (++(p->i)) , a[0].i will be 11
x=(++p)->i; // p will point to a[1] then x = 20
x=(p++)->i; // x = 10 , then p will point to a[1]
x=*p->c; // *(p->c) , x = 30
x=*p->c++; //  (*((p->c)++)) , x = 30 then c will change it's pointing
x=(*p->c)++; // (*(p->c))++ , x = 30 after that b[0] = 31 
x=*p++->c; // (*( (p++) -> c)) , x = 30

self referential structures

struct ex
{
    int i;
    struct ex *link;
}
struct ex abc;

those are used in trees and linked list.

you need to make sure before using an pointer that you are already created it or you will get segmentation error

malloc

global variables will be allocated in stack before your program run.

dynamically allocated will be creating in memory.

image-20200827110120761

the stack will grow and allocated most of the space or heap will , or they will both occupy same size. We can ask for a space in the heap and use them.

The Operation system will decide the size of the process.

in Unix sblk(n) will give you pointer of n bytes from the operation system inside the heap and use it.

in C we have malloc() will ask from the operation system to that system call what ever the system is.

for efficiencies you can call system directly.

void* malloc(int);

this will create an empty memory and it will return the pointer of it.

int* p = (int*) malloc(2); // 2 bytes
*p = 100;

if we hard coded like this it may work on our system but other systems have 4 bytes to integer so it will fail.

int *p = (int*)malloc(sizeof(int)); // it will replace with system size of int
free(p);

it will take 4 bytes to the first available space that it will found in heap , if not it will go to operation system to create one.

struct node
{
    int i;
    struct node *l;
};
struct node *p = (struct node*) malloc(sizeof(struct node));
// this how we create a structure
// we can access it using p->i

Recursion

A(n)
{
    if(n>0)//1
    {//2
        printf("%d" , n-1);//3
        A(n-1);//4
    }//5
}

main() {
 A(3)
 ...// line i
}
//output : 2 1 0

image-20200827130902875

then when it return it will start to delete the stacks

image-20200827131022721

required stacks are A(n) = n+1 = O(n)

time complexity T(n)=c+T(n-1)

image-20200827131646449

this is another method if the program is small to represent the stack.

A(n)
{
    if(n>0)
    {
        pf(n);
        A(n-1);
        pf(n);
    }
}
// output : 3 2 1 1 2 3

T(n) = c+T(n-1)

image-20200827132256039

A(n)
{
    if(n>0)
    {
        A(n-1);
        pf(n);
        A(n-1);
    }
}
// output : 1 2 1

image-20200827132648769

only 3 stacks are required here , because we don't repeat A(n) if it's already calculated.

This post is also available on DEV.