Tag: programming

Data structures an introduction

Data structure: Way of organizing data so we can efficiently use it.
Essential ingredients in creating fast and powerful algorithms.
Help to manage and organize data.
makes code cleaner and easier to understand.

Abstract data type: Is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. Interface will not give any specifics to how something should be implemented or in what programming language.

ADT – Implementation(DS)
List – Dynamic Array, Linked list.
Queue – Linked List Based queue, Array based queue, Stack base queue
Map – Tree map, Hash map, Hash table

Computational complexity analysis:
How much time does this algorithm needs to finish the computation?
How much space does this algoritm needs to finish the computation?

Big data
Omega meta data

Big-O notation: Upper bound complexity of the worst case irrespective of the size of data(small data set or large data set)
n – The size of the input
Complexities ordered in from the smallest to largest.
Constant Time : O(1)
Logarithmic Time : O(log(n))
Linear time : O(n)
Linearithmic Time : O(nlog(n))
Quadric Time : O(nsquared)
Cubic Time : O(ncube)
Exponential Time : O(bpowern), b>1
Factorial Time : O(n!)

O(n + c) = O(n)
O(cn) = O(n), c > 0

f(n) = 7 log(n)3 + 15n2 + 2n3 + 8

O(f(n)) = O(n3) as n3 is the biggest value.

Read More…

Variables, data types and variable types in C

Variables are used to store data.  The following are the charateristics for the variable.

  1. Variables will have unique names under a specific scope.
  2. Variable data type defines the storage requirement for the variable.
  3. Storage class of the variable defines the visibility and lifetime of the variable in a program or function or block.

The following are the rules for a variable naming.

  1. Variable can have underscore, letter or alphabet.
  2. Variable can start only with underscore or alphabet.
  3. No whitespaces allowed in a variable name.
  4. Variable name cannot be a reserved keyword.

Data types

  1. char or unsigned char
    1. single byte storage.
    2. signed will have a value -128 to 127
    3. unsigned will have a value 0 to 256
  2. short or unsigned short
    1. double byte storage.
    2. signed will have a value -32,768 to 32,767
    3. unsigned will have value 0 to 65535.
  3. int or unsigned int
    1. 4 byte storage.
    2. signed will have a value -2GB to (2GB -1)
    3. unsigned will have a value 0 to 4GB
  4. long or unsigned long
    1. 4 byte storage on 32 bit machines and 8 byte storage on 64 bit machine.
    2. for 4 bit
      1. signed will have a value -2GB to (2GB -1)
      2. unsigned will have a value 0 to 4GB
    3. for 8 bit
      1. signed will have a value of -2 power 63 to (2 power63 -1)
      2. unsigned will have a value 0 to 2 power 64.
  5. long long and unsigned long long
    1. Both 32 and 64 bit machines certain compilers support long long data type to hold 64 byte values.
    2. signed will have a value of -2 power 63 to (2 power63 -1)
    3. unsigned will have a value 0 to 2 power 64.
  6. void
    1. Data type which can be point to no storage.
    2. Used mainly for pointers to point to any storage types.
  7. pointer type
    1. Qualified with a * to address the variable points to an address which holds the data.
  8. union
    1. combination of multiple types of variable and hold the maximum size of the variable used.
  9. struct
    1. Combination of multiple types of variable and storage will be the combination of all variable datatypes.

Storage class

Storage class defines the scope of the variable and the life time of the variable.

  1. local variables
    1. Variables defined inside a function or block without any storage class specified.
  2. auto variables
    1. auto variables are defined with the keyword auto. By default all local variables are auto type.
  3. static variables
    1. static variables are defined with the keyword static.
    2. static variables can have either scope defined inside a function or a file.
    3. static variables will retain the data even if they goes out of scope and can be accessed when the code access the block/function and file again.
  4. const variables
    1. Constant variables are variable data which cannot be modified later in the code.
    2. Usually they are set to make sure the called API or code executed later cannot modify them.
  5. volatile variables
    1. volatile keyword is used to indicate compiler not to perform any optimization in the code.
  6. extern variable
    1. extern variable is used to indicate the variable is defined somewhere in another file or library.
    2. extern keyword can be used to indicate the variable storage type to compiler so we can modify the data.
  7. register variables
    1. register variables are used to indicate the compiler to use any free register to cache the value.
    2. However the compiler can ignore the register access and treat it as auto variable if not register available or cannot cache the value.

Source: Variables and Keywords in C – GeeksforGeeks

Example code

var.c

 

#include <stdio.h>

int a=1; // initialized global variable.
int b; // uninitialized global variable.

static int c; //global static variable.
extern int d;

typedef struct _abc{
char a;
short b;
int c;
}ABC;

typedef union _def{
char a;
short b;
int c;
}DEF;

int increment()
{
static int p = 5;
a=a+1;
p=p+1;

printf("dataof(p)=%d\n", p);
return 0;
}

int main(int argc, char * argv[])
{
auto int e=5; //auto variable
int f=6; //local variable
const int g=7; // constant variable
long j=10; // long type variable
long long k=11; // long long type variable
ABC h; // structure type variable
DEF i; // union type variable
char l='a'; // character type variable
short m=10; // short type variable
char *n=&l; // pointer variable.
void *o=(void *)n; // void pointer variable.
// Size check
printf("Size of char is %d bytes\n", sizeof(l));
printf("Size of short is %d bytes\n", sizeof(m));
printf("Size of int is %d bytes\n", sizeof(f));
printf("Size of long is %d bytes\n", sizeof(j));
printf("Size of long long is %d bytes\n", sizeof(k));
printf("Size of pointer is %d bytes\n", sizeof(n));
printf("Size of structure ABC is %d bytes\n", sizeof(h));
printf("Size of union DEF is %d bytes\n", sizeof(i));

//Access check
increment();
increment();
printf("dataof(a)=%d, addressof(a)=0x%x\n", a, &a);
printf("dataof(b)=%d, addressof(b)=0x%x\n", b, &b);
printf("dataof(c)=%d, addressof(c)=0x%x\n", c, &c);
printf("dataof(d)=%d, addressof(d)=0x%x\n", d, &d);
printf("dataof(e)=%d\n", e);
printf("dataof(f)=%d\n", f);
// g = g+10; in correct as its a constant 
printf("dataof(g)=%d\n", g);
printf("dataof(j)=%d\n", j);
printf("dataof(k)=%d\n", k);

return 0;
}


ext.c

int d = 4;

compilation

gcc -o test var.c ext.c

Output

yogi@localhost devel]$ ./test
Size of char is 1 bytes
Size of short is 2 bytes
Size of int is 4 bytes
Size of long is 8 bytes
Size of long long is 8 bytes
Size of pointer is 8 bytes
Size of structure ABC is 8 bytes
Size of union DEF is 4 bytes
dataof(p)=6
dataof(p)=7
dataof(a)=3, addressof(a)=0x601024
dataof(b)=0, addressof(b)=0x601038
dataof(c)=0, addressof(c)=0x601034
dataof(d)=4, addressof(d)=0x60102c
dataof(e)=5
dataof(f)=6
dataof(g)=7
dataof(j)=10
dataof(k)=11