Memory allocation in C

In a C program we can have three types of variables


static variables, global variables {initialized + uninitialized}, automatic variables


a computer program memory is divided into three sections


data segment {DATA + BSS + HEAP}
stack
code segment


1) Data segment :


a)DATA : contains
----> global and static variables used by the program that are initialized.
Ex: static int i = 10 will be stored in data segment and global int i = 10 will be stored in data segment.


can be further divided into
=> initialized read-only area
e.g. const char* string = "hello world" makes the string literal "hello world" to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.
=> initialized read-write area.
string defined by char s[] = "hello world" in C and a C statement like int debug=1 outside the main would be stored in initialized read-write area.


b)BSS
The BSS segment also known as uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code. For instance a variable declared static int i; would be contained in the BSS segment.


c)Heap
The Heap area is managed by malloc, realloc, and free, The Heap area is shared by all shared libraries and dynamically loaded modules in a process.


2) Stack
The stack area is just below the heap area and they grow the opposite direction.
The stack area contains the program stack, a LIFO structure, A "stack pointer" register tracks the top of the stack; it is adjusted each time a value is "pushed" onto the stack.
stores local (auto) variables, passing function arguments, storing return address, etc


3) Code segment,
also known as a text segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.
It has a fixed size and is usually read-only. If the text section is not read-only, then the particular architecture allows self-modifying code.


links
http://www.bravegnu.org/gnu-eprog/c-startup.html
http://blog.ooz.ie/2008/09/0x03-notes-on-assembly-memory-from.html
http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap
http://www.maxi-pedia.com/what+is+heap+and+stack

difference between pointers and arrays

Are these two things same?

char* firstname = "rohit;

char secondname[] ="jangid";

answer is NO, they are not same .

why ?

suppose both these lines are there in a program hello.c.
two things happen

memory to "rohit" is allocated in a write protected area of the program also called "data section" of the program, means that we can't make any changes in "rohit". obviously firstname is only pointing to this memory section and we can use firstname++ without any error

whereas memory to "jangid" is actually allocated in a local stack, in array secondname.
here secondname can be treated as const pointer, which means that we can's use secondname++, but we can modify the string "jangid" without any error as it is not protected.

longest increasing subsequence

problem: given an integer array, find the longest increasing subsequence in it.

solution : trivial dp problem.

code // ->

finding binomial coefficient

problem: find the coefficient of x^r in the expansion of (x+1)^n . nCr basically

solution : using dynamic programming

8 queens problem

problem : you have to place 8 queens on a chess board in such a way that no two queens are able to kill each other. generate all such ways

solution : use backtracking to trace all the possible ways to do this. there are 92 such ways

note: there is no need to use 2d array to represent chess board , here chess board can be represented as single dimension array chess[], where chess[i] = j implies a piece is there on i'th row and j'th column.