C - malloc()
The name malloc stands for "memory allocation".
The function malloc() reserves a block of memory of specified size and return
a pointer of type void which can be casted into pointer of any form.
Syntax of malloc()
ptr = (cast-type*) malloc(byte-size)
Here, ptr is pointer of cast-type. The malloc() function returns a pointer to an area of
memory with size of byte size. If the space is insufficient, allocation fails and returns
NULL pointer.
C free()
Dynamically allocated memory created with either calloc() or malloc() doesn't get freed
on its own. You must explicitly use free() to release the space.
syntax of free()
free(ptr);
C realloc()
If the previously allocated memory is insufficient or more than required, you can change
the previously allocated memory size using realloc().
Syntax of realloc()
ptr = realloc(ptr, newsize);
Here, ptr is reallocated with size of newsize.
Lists
• A list is a finite, ordered sequence of data items.
• Two standard approach to implement list - Arrays, Linked list
• Arrays – static data structure
• Linked list – dynamic data structure
Arrays
An array is a finite, ordered and collection of homogeneous data elements.
C : int A[100]
Size : Number of elements in an array.
Type : data type
Base : base address
Index : subscript used to refer array
elements
Range of Index : Indices change from lower bound LB to and upper bound UB
1 D - Arrays
Indexing formula
B = Base address
w = Storage Size of one element stored in the array (in byte)
i = Subscript of element whose address is to be found
LB = Lower limit / Lower Bound of subscript, if not specified assume 0 (zero)
Given the base address of an array A[1300…..1900] as 1020 and size of each
element is 2 bytes in the memory. Find the address of A[1700].
Solution:
The given values are: B = 1020, L B= 1300, W = 2, i = 1700
Address of A [ i ] = B + W * ( i – LB)
= 1020 + 2 * (1700 – 1300)
= 1020 + 2 * 400
= 1020 + 800
= 1820 [Ans]
Operations on Arrays
Traversing
Sorting
Searching
Insertion
Deletion
Two dimensional Arrays
Memory Representation
1. Row-major form
2. Column major form
Row Major System:
The address of a location in Row Major System is calculated using the following formula:
Address of A [ I ][ J ] = B + w * [ N * ( I – Lr ) + ( J – Lc ) ]
Address of A [ I ][ J ] Column Major Wise = B + w * [( I – Lr ) + M * ( J – Lc )]
B = Base address
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
w = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)
M = Number of row of the given matrix
N = Number of column of the given matrix
Usually number of rows and columns of a matrix are given ( like A[20][30] or A[40][60] )
but if it is given as A[Lr- – – – – Ur, Lc- – – – – Uc]. In this case number of rows and
columns are calculated using the following methods:
Number of rows (M) will be calculated as = (Ur – Lr) + 1
Number of columns (N) will be calculated as = (Uc – Lc) + 1
Q 1. An array X [-15……….10, 15……………40] requires one byte of storage. If
beginning location is 1500 determine the location of X [15][20].
Solution:
As you see here the number of rows and columns are not given in the
question. So they are calculated as:
Number or rows say M = (Ur – Lr) + 1 = [10 – (- 15)] +1 = 26
Number or columns say N = (Uc – Lc) + 1 = [40 – 15)] +1 = 26
1. Row Major wise calculation of X[15][20]
B=1500, W=1 byte, I=15, J=20, Lr=-15, Lc=15,N=26
Address of A[I][J]= B+W*[N*(i-Lr)+(J-Lc)]
= 1500+1*[26*(15-(-15))+(20-15)]
=1500+1*[26*30+5]
=1500+785
=2285
2. Column Major wise calculation of X[15][20]
B=1500, W=1; i=15,J=20,Lr=-15,Lc=15, M=26
X[15][20]= B+W*[(i-Lr)+M*(j-Lc)]
=1500+1*[(15-(-15)+26*(20-15))]
=1500+1*[30+26*5]
=1500+1*(160)
=1660
PRACTICE QUESTION.
Q 1. An array X [4……….7, -1……………3] requires
TWO byte of storage. If beginning location is 100
determine the location of X [6][2].
[ans:126]
Q 2. An array X [1……….5, 1……………4] requires
FOUR byte of storage. If beginning location is
1000 determine the location of X [4][3].