POINTERS

Every variable in C has a name and a value associated with it.

​

When a variable is declared, a specific block of memory within the computer is allocated to hold the value of that variable.

The size of the allocated block depends on the data type.

Consider the following statement.�int x = 10;

Lvalue=rvalur

Printf(“%d”,sizeof(x))

The compiler reserves memory for the integer variable x and stores the rvalue 10 in it.

x refers to the value stored at the memory location set aside for x, in this case 10

​

A pointer is a variable that contains the memory location of another variable. ����

A pointer is a variable that represents the location of a data item, such as a variable or an array element.

​

These applications include:�Pointers are used to pass information back and forth between functions.� Pointers enable the programmers to return multiple data items from a function via function arguments.� Pointers provide an alternate way to access the individual elements of an array.� Pointers are used to pass arrays and strings as function arguments. � Pointers are used to create complex data structures, such as trees, linked lists, linked stacks, linked queues, and graphs.�Pointers are used for the dynamic memory allocation of a variable.

General Syntax

data_type *ptr_name;

​

int *pnum;�char *pch;�float *pfnum; ��

�

int x= 10;�int *ptr;�ptr = &x;

​

The * informs the compiler that ptr is a pointer variable and the int specifies that it will store the address of an integer variable.

X Name of the variable

ptr Name of the pointer variable

ptr = &x; ptr is assigned address of variable x

y = *ptr; y is assigned a value of content of the address pointed by ptr

#include <stdio.h>�int main()�{�int num, *pnum;�pnum = &num; �printf("\n Enter the number : ");�scanf("%d", &num);�printf("\n The number that was entered is : %d\n", *pnum);

printf("\n The number that was entered is : %d\n", num);

printf("\n The address is : %u", ptr);

return 0;�} �

What is the expected output?

​

The number that was entered is :

The number that was entered is :

The address is :

​

* pnum Pointer de-referencing

Pointer referencing

int num1 = 2, num2 = 3, sum = 0, mul = 0, div = 1;�int *ptr1, *ptr2;�ptr1 = &num1;�ptr2 = &num2;�sum = *ptr1 + *ptr2;�mul = sum * (*ptr1);�*ptr2 += 1;�div = 9 + (*ptr1)/(*ptr2) – 30;

​

Valid pointer operations

Addition

Subtraction

Comparing pointer (relational Operations)

Multiplication ( not widely used)

​

No division operation are possible

​

++,--- are valid operations

void *ptr = NULL; Represents null pointer �

Relation between array and pointers

# include <stdio.h>�int main( )�{�int i = 3 ;�printf ( "Address of i = %u\n", &i ) ;�printf ( "Value of i = %d\n", i ) ;�printf ( "Value of i = %d\n", *( &i ) ) ;�return 0 ;�} �

‘*’, called ‘value at address

(pointer de-referencing)

Assume address

What is the program output

• ( &* ) complement in informal

representation

• Hence it is as good as writing i

​

Example

Consider the declaration: int x[5] = {1, 2, 3, 4, 5};

Suppose that each integer requires 4 bytes

Compiler allocates a contiguous storage of size 5x4 = 20 bytes

Suppose the starting address of that storage is 2500 Element Value Address

Compiler allocates sufficient amount of storage to contain all the elements of the array in contiguous memory location

base address is the location of the first element (index 0, x[0] in above table) of the array

such as in above table 2500

The array name as a constant pointer to the first element

Both x and &x[0] have the value 2500

int *p is declared and if we define

p = x;

Or

p = &x[0]; they are equivalent

If we increment with p++ then p=&x[1]

Int x[5]={5,6,7,8};

Int i ;

​

For(i=0;i<5;i++)

printf(“%d”,x[i]);

Int x[5]={5,6,7,8};

Int *p,i;

p=x;

For(i=0;i<5;i++)

printf(“%d”,*(p+i));

Dynamic Memory Management

�

free memory region is called heap

#include <stdio.h>�#include <stdlib.h>�int main ()�{�int i,n;�int *arr;�printf ("\n Enter the number of elements: ");�scanf("%d",&n);�arr = (int*) calloc(n,sizeof(int));�if (arr==NULL) exit (1);�printf("\n Enter the %d values to be stored in the array", n);�for (i = 0; i < n; i++)�scanf ("%d",&arr[i]);�printf ("\n You have entered: ");�for(i = 0; i < n; i++)�printf ("%d",arr[i]);�free(arr);�return 0;�} �

#include<stdio.h>

// Dynamic array using pointer

Void main()

{

int i,n,*p;

printf(“enter number of elements in an array”);

scanf(“%d”,&n);

for(i=0;i<n;i++)

scanf(“%d”,(p+i));

for(i=0;i<n;i++)

printf(“%u=%d”,(p+i),*(p+i));

}

​

Output

Enter number of elements in an array 5

1 2 3 4 5

1212=1

1214=2

1216=3

1218=4

1220=5

​

int main()�{�int **arr, i, j, ROWS, COLS; // **a is pointer to pointer�printf("\n Enter the number of rows and columns in the array: ");�scanf("%d %d", ROWS, COLS);�arr = (int **)malloc(ROWS * sizeof(int *));

// allocate memory as per row size�if(arr == NULL)�{�printf("\n Memory could not be allocated");�exit(-1);�}�for(i=0; i<ROWS; i++)�{�arr[i] = (int *)malloc(COLS * sizeof(int));// to Each column�if(arr[i] == NULL)�{�printf("\n Memory Allocation Failed");�exit(-1);�}�} �

void main()

{

int i,j,a[3][3];

int **p;

p=(int**) calloc(3,sizeof(int));

for(i=0;i<3;i++)

p[i]=(int*)malloc(3*sizeof(int));

for(i=0;i<3;i++)

for(j=0;j<3;j++)

scanf("%d",(p[i]+j));

for(i=0;i<3;i++)

for(j=0;j<3;j++)

printf("%d",*(p[i]+j));

}

Structures

A structure is in many ways similar to a record.

It stores related information about an entity.�Structure is basically a user-defined data type that can store related information

A structure is therefore a collection of variables under a single name. �The variables within a structure are of different data types

Ex

struct student�{�int r_no;�char name[20];�char course[20];�float fees;�};

Here structure is similar to user defined data type.

As it’s a data type we have to define a new variable to use it

​

struct student stud1;

​

�� �

struct student�{�int r_no;�char name[20];�char course[20];�float fees;�} stud1 = {01, "Rahul", "BCA", 45000};

Or

struct student stud1 = {01, "Rahul", "BCA", 45000};

Or

​

stud1.r_no = 01;�stud1.name = "Rahul";�stud1.course = "BCA";�stud1.fees = 45000; �Or

scanf("%d", &stud1.r_no);�scanf("%s", stud1.name); � scanf("%s", stud1.course);

scanf(“%f", &stud1.fees); � �

#include <stdio.h>�#include <conio.h>�int main()�{�typedef struct complex�{�int real;�int imag;�} COMPLEX;�COMPLEX c1, c2, sum_c, sub_c;

printf("\n Enter the real and imaginary parts of the irst complex number : ");�scanf("%d %d", &c1.real, &c1.imag);�printf("\n Enter the real and imaginary parts of the �second complex number : ");�scanf("%d %d", &c2.real, &c2.imag);

sum_c.real = c1.real + c2.real;�sum_c.imag = c1.imag + c2.imag; � printf("\n The sum of two complex numbers is : %d+%di",sum_c.real, sum_c.imag); � }�

THE POLYNOMIAL

#define�typedef�MAX—DEGREE 101 / * Max degree of polynomial + 1 * /�struct {�int degree;

float coef[MAX-DEGREE];�} polynomial;

THE SPARSE MATRIX

A matrix which has few non-zero entries is called as sparse matrix

A sparse matrix wastes memory space as many entries are zero

To reduce memory space wastage we must consider alternate forms of representation.

​

�

#define MAX-TERMS 101 �typedef struct {� int col;� int row;� int value;�} term;�term a[MAX-TERMS];

​

​

The matrix is represented as a triplet

( Row, Col, Value)

The first row a[0] contains

No.of Rows in original Matrix

No of Column in original Matrix

No of Non Zero Values

​

A[0][0]=6

A[0][1]=6

A[0][2]=8

Transposing a Matrix

for all elements in column j�place element <i, j, value > element in <j, i, value>

REPRESENTATION OF MULTIDIMENSIONAL ARRAYS

char str[] = {'H', 'E', 'L', 'L', 'O', '\0'};

char name[5][10] = {"Ram", "Mohan", "Shyam", "Hari","Gopal"};

STACKS

A stack is a linear data structure, where elements can be added and deleted from the same end called top of the stack.

​

Stack exhibits Last In First Out (LIFO) behavior

Operation of adding / Inserting elements to the stack is called as PUSH operation

Operation of removing / deleting elements to the stack is called as POP operation

Stack has a capacity defined STACK_SIZE

​

Stack full condition:- If total number of elements on the stack are equal to STACK_SIZE , push operation gives STACK FULL error ( Stack Overflow error)

​

Stack Empty: If stack is empty, calling operation POP on stack results in stack empty error ( Stack Underflow Error)

Static using array

#define stack_size 100

typedef stack

{

int Key;

} ;

stack st[stack_size];

int top = -1;

Dynamic representation

typedef stack

{

int key;

} ;

Stack *st;

Malloc(stack, sizeof(*stack));

Capacity=0;

Top=-1;

​

/* when stack full condition error occurs following code is executed */

Realloc(stack,2*capacity*sizeof(stack));

/*this allocates additional space*/

​

int stack[MAX];

void push(int st[], int val)�{

if(top == MAX-1)

{

printf("\n STACK OVERFLOW");

}� else�{� top++;� st[top] = val;�}�}

int pop(int st[])�{�int val;�if(top == -1)�{� printf("\n STACK UNDERFLOW");� return -1;�}�else�{� val = st[top];� top--;� return val;�}�}

void display(int st[])�{int i;�if(top == -1)� printf("\n STACK IS EMPTY");

else�{�for(i=top; i>=0; i--)� printf("\n %d",st[i]);� }

int stacktop(int st[])�{

if(top == -1)

{

printf("\n STACK IS EMPTY");�return -1; }�else�return (st[top]);�}

Reversing a list�Parentheses checker Conversion of an infix expression into a postfix expression�Evaluation of a postfix expression�Conversion of an infix expression into a prefix expression�Evaluation of a prefix expression�Recursion

QUEUE

A queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted first is the first one to be taken out. The elements in a queue are added at one end called the REAR and removed from the other end called the FRONT.

#define MAX 10 // Changing this value will change length of array�int queue[MAX];�int front = -1, rear = -1;

​

void insert()�{�int num;�printf(“\n Enter the number to be inserted in the queue : “);�scanf(“%d”, &num);�if(rear == MAX-1)

{

printf(“\n OVERFLOW”);

Return ;

}�else

if(front == -1 && rear == -1)�front = rear = 0;�else�rear++;�queue[rear] = num;�} �

int delete_element()�{� int val ;

if(front == -1 || front>rear)�{

printf(“\n UNDERFLOW”);�return -1;

}�else�{�val = queue[front];�front++;�if(front > rear)�front = rear = -1;�return val;�}�}

void display()

{

int i;

printf(“\n”);

if(front == -1 || front > rear)

printf(“\n QUEUE IS EMPTY”);

else

{

for(i = front;i <= rear;i++)

printf(“\t %d”, queue[i]);

}

}

TYPES OF QUEUES�A queue data structure can be classified into the following types:�1. Circular Queue

2. De-queue ( Double Ended Queue)

3. Priority Queue

4. Multiple Queue �

Double Ended Queue (DeQueue)

Input restricted

Output Restricted

Priority Queue

Multiple Queues

Linked List

• Linear link list data structure is a collection of NODES
• Each node has two or more parts. One of which points to the address of next node called LINK part.
• The other parts holds DATA, hence can be called DATA part
• The last node in the linked lists points to NULL to designate end of linked list
• A linked list can have an additional node that points to the first node in the list called head node / Start Node.

struct node {

int data;

struct node *next; } �

#define NUMNODES 500�struct nodetype {�int info, next;

}�struct nodetype node[NUMNOOES];

avail = 0;�for (i = 0 i < NUMNODES-1; i++)�node(i] .next= i + 1;�node[ NUMNODES-1].next = -1; �

int getnode(void)

{�int p;�if (avail == -1)

{�printf("overflow\n");�exit(1);

}�p = avail;�avail =node[avail].next;�return(p);�}

void freenode(int p)

{�node[ p. next] = avail;�avail = p;�return;

}

void insafter(int p, int x )

{

int q;� If(p=-1) {�printf("vod insertion\n');�return; }�q = getnode();�node[q].info=x;�node[q] next = node[p] .next;�node[p].next=q; return;�}

NOOEPTR getnodé(void)

{

NODEPTR p;

p= (NODEPTR) malloc (sizeof(struct node));

return(p);

}

void freenode(NODEPTR p)

{

free(p);

}�

struct node

{

int info;

struct node *next;

}

typedef struct node *NODEPTR; �

p= (NODEPTR) malloc(sizeof (struct node));

NODEPTR list;

list=NULL;

p->info=10;

p=list;

list=p;

/*free(p)*/

Linked list as stack implementation

struct node

{�int info;�struct node next;

};�typedef struct node *NODEPTR; �NODEPTR p ;�

P=getnode();�

NODEPTR push(int x)

{

NODEPTR p;

P=getnode();

P->info=x;

P=list;

List=p;

Return list;

}

int pop()

{

NODEPTR P=list;

If(p==NULL)

{ printf(“List empty”);

return 0;

}

X=p->info;

List=p->next;

Free(p);

Return x;

}

Void display()

{

NODEPTR p;

P=list;

If(p==NULL)

{ printf(“List empty”);

return ;

}

For(p=list;p!=NULL;p=p->next)

printf(“%d”,p->info);

return; }

void insafter(NODEPTR p, int x)

{�NODEPTR q;�if (p ==NULL)

{�printf("void insertion\n”);�exit(1);

}�q= getnode();�q -> info =x;�q -> next = p -> next;�P -> next =q;�} �

void deafter(NODEPTR p, int *px)�{

NODEPTR q;�if((p == NULL) || (p -> next == NULL))�{

printf(ojd deletion\n);�exit(1);

}�q=p -> next;�px = q -> info.;�P -> next = q -> next;�freenode(q);�} �

LINKED LIST PRIORITY QUEUES

void place(NOOEPTR *plist, int x)

{�NOOEPTR p, q;�q = NULL;�for (p =*plist; p != NULL && x > p->info; p =p->next)

q =p;

�if (q ==NULL)

push(*plist, x);�else�insafter(q, x);

}

int pop()

{

NODEPTR P=list;

If(p==NULL)

{

printf(“List empty”);

return 0;

}

X=p->info;

List=p->next;

Freenode(p);

Return x;

}

//Insert at end of list

void insend(NODEPTR *piist, int x)

{�NODEPTR p, q;�p= getnode();�p->info= x;�p->next = NULL; �if (*pljst == NULL) �*plist = p:�else�for (q = *plist; q->next != NULL; q =q->next);

q->next = p;�} ��

NODEPTR search(NODEPTR list, int x)

{�NODEPTR p;�for (p = list; p != NULL; p = p->next)�if (p->info== x)�return (p);�else�return (NULL);�} �

typedef struct poly_node *poly_pointer;�typedef struct poly_node

{�int coef;�int expon;�poly_pointer link;�};

poly_pointer a,b,d; �

NODEPTR insert(NODEPTR *clist,int x)

{

NODEPTR p;

p=getnode();

P->info=x;

If(CLIST==NULL)

{

CLIST=p;

CLIST->next=CLIST; }

Else

{ p->next=clist->next;

clist->next=p;

}

Return clist; }

Int delete(NODEPTR *clist)

{

NODEPTR p;

If(clist==NULL)

{ printf(“List empty”);

exit(0); }

p=clist->next;

X=P->info;

If( p->next==clist->next)

clist=NULL;

else

c->next=p->next;

}

int empty(NODEPTR *pstack)

{�return ((pstack == NULL) ? TRUE : FALSE);

} �

Void push(NODEPTR pstack, int x)�{�NODEEPTR p;�P – getnode();�p->info=x;�if (empty(pstack) ==TRUE)�pstack =p;�else�p->next =(*pstack) -> next;�(*psrack) -> next =p;

}�

int POP(NODEPTR pstack)�{�int x;�NOOEPTR p;�if (empty(pstack) ==TRUE)

{�printf('stack underflow\n");�exit(1);� }

P = (*pstack) -> next;�x = p->info;�if (p== *pstack)�*pstack = NULL;�else�(pstack) -> next =p->next;�freenode(p);�return(x);�}�

void insert(NODEPTR *pq, int x)�{

NODEPTR p;�p =getnode();�p->info =x;�if (empty(pq) == TRUE)�*pq =p;�else�p->next=(*pq) -> next;�(*pq) -> next =p;�*pq =p;�return;�}�// CLIST as a queue

int Delete(NODEPTR pq)�{�int x;�NOOEPTR p;�if (empty(pq) ==TRUE)

{�printf(‘Queue Empty\n");�exit(1);� }

P = (*pq) -> next;�x = p->info;�if (p== *pq)�*pq = NULL;�else�(pq) -> next =p->next;�freenode(p);�return(x);�}�

SPARCE MATRIX REPRESENTAION AS LINKED LIST

• Represent each column of a sparse matrix as a circularly linked list with a head node.
• Similar representation for each row of a sparse matrix.
• Each node has a tag field, which we use to distinguish between head nodes and entry nodes ( Head Node 3 fields and Entry Node 5 fields)
• Head node has three additional fields: down, right, Next
• down field to link into a column list and the right field to link into a row list and The next field links the head nodes together
• head node for row i is also the head node for column i
• total number of head nodes is equal to max number of rows and columns
• Each entry node has five fields in addition to the tag field: row, col, down, right, value
• down field to link to the next nonzero term in the same column and the right field to link to the next nonzero term in the same row ���������

Representation of sparse Matrix as

Circular Linked List

Doubly linked list

Doubly Linked list contains two pointes , 1 pointing to previous node, called left pointer

Right pointer points to Successor node or next node

Hence each node has Left pointer and right pointer

They are symmetric in nature

The list can be traversed in any direction

A Doubly Linked List ( DLL) may contain a header node

Left(right(p))=p=right(left(p))

ALGORITHM BruteForceStringMatch(T [0..n - 1], P[0..m - 1])�//Implements brute-force string matching�//Input: An array T [0..n - 1] of n characters representing a text and�for i ← 0 to n - m do�j ← 0�      while j < m and P[j] = T[i + j] do�                    j ← j + 1�                  if j = m 

return i�return -1

Knuth-Morris-Pratt Algorithm�

KMP algorithm is used to find a "Pattern" in a "Text".

This algorithm compares character by character from left to right.

Whenever a mismatch occurs, it uses a preprocessed table called "Prefix Table" to skip characters comparison while matching.

The prefix table is also known as "Longest proper Prefix which is also Suffix" LPS Table.

Steps for Creating LPS Table (Prefix Table)

• Step 1 - Define a one dimensional array with the size equal to the length of the Pattern. (LPS[size])
• Step 2 - Define variables i & j. Set i = 0, j = 1 and LPS[0] = 0.
• Step 3 - Compare the characters at Pattern[i] and Pattern[j].
• Step 4 - If both are matched then set LPS[j] = i+1 and increment both i & j values by one. Goto to Step 3.
• Step 5 - If both are not matched then check the value of variable 'i'. If it is '0' then set LPS[j] = 0 and increment 'j' value by one, if it is not '0' then set i = LPS[i-1]. Goto Step 3.
• Step 6- Repeat above steps until all the values of LPS[] are filled.

a pattern...

​

void computeLPSArray(const char* pat, int M, int* lps)

{

int len = 0;

lps[0] = 0;

int i = 1;

while (i < M) {

if (pat[i] == pat[len]) {

len++;

lps[i] = len;

i++;

}

else {

if (len != 0) {

len = lps[len - 1];

}

else {

lps[i] = 0;

i++;

}

}

}

}

KMPSearch

(const char* pat, const char* txt, int* count)

{

computeLPSArray(pat, M, lps);

while ((N - i) >= (M - j)) {

if (pat[j] == txt[i]) {

j++; i++;

}

if (j == M) {

result[*count] = i - j + 1; (*count)++;

j = lps[j - 1];

}

else if (i < N && pat[j] != txt[i]) {

if (j != 0) {

j = lps[j - 1];

}

else {

i = i + 1;

}

}

}

free(lps);

return result;

}