Transcript TCS1011 - DATA STRUCTURES AND ALGORITHMS

Lecture 2
• Pointers
• Pointers with Arrays
• Dynamic Memory Allocation
Recollection of the Previous
Lecture
• Why Data Structure Needed?
– Programming and Data Processing requires
efficient algorithms for accessing data in main
memory and on secondary storage devices.
– This efficiency is directly linked to the structure
of the data being processed.
• What is Data Structure?
– It is a way of organizing data that considers not
only the items stored but also their relationship to
each other.
Cont.
• Basic Data Types
–
–
–
–
Integer
Real
Boolean
Character
• Arrays
– and some operations on arrays
Pointer
• What is a POINTER?
A pointer variable contains an address. A
pointer variable can be declared as follows:
int *ptr;
int a = 23, b;
• This declares ptr to be a (pointer) variable that
can contain the address of an integer variable.
Pointer
• ptr = &b; /* Assigns ptr the address of b */
• *ptr = a; /* The contents of the variable
pointed by ptr
becomes the value of a*/
Pointer
c = *ptr;
/* Assigns the value of the variable pointed by ptr
(i.e. contents of b) to the variable c, (i.e. c
becomes 23). */
cout << c << *ptr; /* prints c and contents of address ptr */
/*prints 23,23 */
Pointer
 In C++, pointer arithmetic is scaled.
Consider the following program:
int a,*ptr;
ptr = &a;
if &a is equal to 276314 then ptr+1 will
contain 276314+sizeof(int)
Pointers and Arrays
Consider the following program:
#include<iostream.h> The two cout will have the same
output because the name of an
void main()
array is actually representing the
{
address of element 0 of the array.
int a[10];
cout<<&a[0]<<endl;
Therefore
cout<<a;
&a[i] is the same as a+i
a[i] is the same as *(a+i )
}
Pointers and Arrays
Example
#include <stdio.h>
void main()
{
int a[5],i;
for (i=0;i<5;i++) cin >>a+i ;
for (i=0;i<5;i++) cout <<*(a+i);
}
Pointers and Arrays
Two dimensional Arrays:
 The case of two dimensional array is interesting. Every
two dimensional array is stored in the memory row by
row. From the row and column index (i and j), we can
calculate exactly where an element a[i][j] is stored in the
memory.
 In a 2-D array, the name of the array represent the address
of the first row.
Pointers and Arrays
 If we know the address of the first element, then
given the index i and j of any element, we can find
its address as
i*maximum number of columns +j.
 Example - Next Slide
Pointers and Arrays
#include<iostream.h>
void main()
{
char
a[4][3]={{'m','a','t'},{'s','a','t'},{'h','a','t'},{'c','
a','t'}};
int i,j;
char c;
Pointers and Arrays
for (i=0;i<4;i++)
{
for (j=0;j<3;j++)
{
cout<<*((char*) a+i*3+j));
}
cout<<endl;
}
}
DYNAMIC MEMORY ALLOCATION
 Memory is allocated for variables in two
ways:
 Static (or at compile-time)
 Dynamic (or at run-time)
C-DATA TYPES AND DATA STRUCTURE CLASSIFICATION
 In a program which declares an integer
variable x, at compile time itself, memory
locations of size enough for an integer ( 2
locations since size of an integer is 2 bytes)
is reserved for x.
• Arrays are also known as static data
structures since they also get their required
memory allocated during compile time..
C-DATA TYPES AND DATA STRUCTURE CLASSIFICATION
Disadvantage :
The problem with static memory allocation is that the memory
usage may not be efficient
Example : Consider the case of array marks to store the marks of
a class of a maximum size 100. It is likely that in each semester
the number of students may vary. In a given semester even if 25
students are there, 100 locations will still be reserved and 75 of
them wasted.
We can re-write the program each time with the array declaration
exactly matching the number of students, but then the program is
no longer a general one.
DMA
 Dynamic memory allocation is in contrast with this. Memory
gets allocated at the time of running the program and hence
we can use memory to exactly meet our needs.
 Allocated memory can be many types:
Contiguous memory allocation: Allocation of adjacent memory
locations
Non-Contiguous memory allocation: Allocation of non adjacent
memory locations
Heap: Collection of all free memory locations available for allocation
De-allocation:
Releasing of allocated memory after use, to be added back to
the heap.
DMA
• The new and delete operators do dynamic allocation and
deallocation in much the same manner that the malloc() and
free() functions do in C .
 The new operator requires one modifier which must be a type.
 The delete operator can only be used to delete data allocated by a new
operator. If the delete is used with any other kind of data, the
operation is undefined and anything can happen.
DMA
Example :
#include<iostream.h>
void main()
{
int *p;
p=new int;
*p=56;
cout<<“Memory allocated at ”<<p<<endl;
cout<<“Integer in memory="<<*p<<endl;
}
DMA
Another Example :
#include<iostream.h>
void main()
{
struct pair
{
int x;
int y;
};
(*p).x is equivalent to p->x
struct pair *p;
p= new pair;
(*p).x=56;
(*p).y=47;
cout<<p>x<<endl<<p->y;
}
(*p).y is equivalent to p->y
DMA
• Proper programming practice requires that all
memory that is allocated to be freed after use
• In the previous programs, when the program
finishes running the operating system frees all
memory allocated.
DMA
#include <iostream.h>
#include <string.h>
int main()
{
struct date
{
int month;
int day;
int year;
};
int index, *pt1,*pt2;
pt1 = &index;
*pt1 = 77;
pt2 = new int;
*pt2 = 173;
cout<<"The values are "<<index<<" "
<<*pt1<<" "<<*pt2<<endl;
pt1 = new int;
pt2 = pt1;
*pt1 = 999;
cout<<"The values are "<<index<<"
"<<*pt1<<" "<<*pt2<<endl;
delete pt1;
date *date_pt;
date_pt = new date;
date_pt->month = 10;
date_pt->day = 18;
date_pt->year = 1938;
DMA
cout<<date_pt->day<<"/"<<date_pt>month<<"/"<<date_pt->year<<endl;
delete date_pt;
char *c_pt;
c_pt = new char[37];
strcpy(c_pt,"John");
cout<<c_pt<<endl;
delete c_pt;
return 0;
}