Data Structures using „C‟ - Arrays, Pointers and Structures

Data Structures using „C‟ Unit 1

Unit 1 Arrays, Pointers and Structures
Structure:
1.0 Introduction
1.1 Definition and concept of an Array
1.1.1 Array Used in „C‟ Language
1.1.2 Single – Dimensional Arrays (One Dimensional Array)
1.1.3 Two Dimensional Arrays. [Matrix]
Self Assessment Questions
1.2 Pointers
1.3 Declaring a pointer variable
1.3.1 Pointer Operators:
1.4 Pointers and Arrays
1.5 Pointers used in function
1.6 Pointers used in an Array
Self Assessment Questions
1.7 Structures
1.7.1 Declaration of structure
1.7.2 Initialization of structure
1.7.3 Processing of Structure
1.7.4 Structure used with an Array
1.8 Summary
1.9 Terminal Questions
1.0 Introduction
The need of the arrays can be best understood by thinking, what if its not there. If we had to write a program to add three integers, we may declare a,b,c as three integers and display the result as “a+b+c”. What if we had to add 100 numbers only after accepting all of them? We would need 100
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 2
different variables with 100 different identifiers with no of variable locations as relative of each other. This approach is very cumbersome and lengthy. Hence is the need of arrays. Arrays are the basis for creating any new data structures; understanding of arrays is essential and becomes the backbone in this field. Using arrays one can declare and define multiple variables of same type with one identifier. For e.g. int a[10] is a declaration of 10 variables which are clustered together.
The pointer are special type of variables that hold the address value. Pointers are special variables as they simply point to other variable. The pointers are the powerful tool for instance, are used to setup complicated data structure and are used to link variables together.
In general variables are defined with its type and these can be find with the addresses for ordinary variables by using the address operator „&‟. Thus in C and C++ variables that tell a computer where data is placed that are know as pointer variable.
Objectives
At the end of this unit, you will be able to understand the:
 Arrays and its usage in programming languages
 Brief introduction of pointers
 Pointer operators and
 Implementation concepts of Pointers using Arrays, Functions
 Brief about the structure and its usages.
1.1 Definition and Concept of an Array
Array is a list or collection of data items which are stored in the form of a table, referred to by a common variable name. i.e., called “Array name” or “Subscript variable name”.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 3
 Advantage of using an array:
1) Multi huge quantity of data items can be stored under single variable name
2) Arrays saves the memory space
3) Arrays helps to arrange the data (Sorting) items in particular order [Ascending / descending]
4) Data items searching is faster.
Concept of an Array:
Concept of an array can be classified into two types that are :
1. Single dimensional array
2. Double/ multi dimensional array or matrix.
 Concept of Single dimensional Array.
Data items are stored in one single column with specified subscript variable name by using subscript range.
Example:
Storing 6 sales amount in an array
SALEAMOUNT
1000
1100
950
1200
1050
1250
Note : In the single dimensional Array , values are stored or arranged Column wise with its respective range and each element range addressed by common single variable name.
Subscript range
Array name or subscript variable name
Cell or Element
1
2
3
4
5
6
With out using an array
SALEAMOUNT1 = 1000
SALEAMOUNT2 = 1100
SALEAMOUNT3 = 950
SALEAMOUNT4 = 1200
SALEAMOUNT5 = 1050
SALEAMOUNT6 = 1250
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 4
Concept of two Dimensional or Double Dimension Array
In double dimensional array, values are referred with respect to specified Row & column using subscript variable name. double dimensional array also called as matrix.
Example : Holding the Different Brands Electrical Bulbs quantity with respect to its wattages(W).
QTY
CELL 1 CELL 2 CELL 3 CELL 4
0(W)
40(W)
60(W)
100(W)
50
40
10
20
25
20
10
0
0
40
20
25
25
10
5
10
5
4
10
20
Above Example indicates the 4 / 5 Matrix, all cell values are referred by the subscript name (Array name) QTY with respect to row and column.
1.1.1 Array Used in ‘C’ Language
In any High Level Language[HLL] when we used an array the following 3 sequence steps must be followed.
1. Defining or Declaring an array (Creating a specified blank table in main memory)
2. Storing values in an Array (By the source accepting values and storing)
3. Reading or retrieving a values from an array for any process task.
1.1.2 Single – Dimensional Arrays (One Dimensional Array)
 Declaration or Defining an Array.
<data type><array name or subscript variable> [< array Range or order >]
(or array type)
Row 1 – Brand 1
Row 2 – Brand 2
Row 3 – Brand 3
Row 4 – Brand 4
Row 5 – Brand 5
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 5
Example
int num [10];
char name [20];
float avg [100];
 Initialize An Array:
Example:
int num [10] = {40, 50, 10, 20, 11, 20, 15, 100, 90, 17}
char name [6] = {„s‟, „h‟, „a‟, „k‟, „t‟, „i‟}
char Colorx [5] = {„W‟, „h‟, „i‟, „t‟, „e‟}
float avg[3] = {55.99,78.50,80.70}
Example: Write a program to store 10 salesmen‟s amount in an array and find out total sale & best sales amount.
/* Storing 10 sales amount in an array and
find out total sale & Best sale amount */
#include <iostream.h>
#include <conio.h>
main ( )
{
const int n = 10;
int sale_amt [100]; tot_amt; best = 0;
clrscr ( )
/* storing values in an array */
for (i = 0; i< = n ; i + +)
{
printf(“Enter sales amount: \n”);
scanf(“%d”, &sale_amt[i]);
}
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 6
/* Calculate the total sale & find out best amount */
tot_sale = 0; best = 0;
for (i = 0; i<n; i+ +)
{
prntf(“ \n sale amount %d , = %d ” , i, sale_amt [i]);
tot_amt = tot_amt + sale_amt[i];
if sale_amt[i] > best
best = sale_amt [i];
}
/* Printing Total and Best Sale amount */
printf( “ \n Total sale amount = %d ”, tot_amt);
printf(“ \n Best sale amount = %d ” ,best);
}
Sorting an array : [ Using Bubble sorting Technique]
Example : Write program to read N number of observations and print them in ascending order.
/* sorting an array. */
#include<iostream.h>
#include <conio.h>
main()
{
int num [100], i, j, temp, n;
clrscr( );
printf( “Enter the number of observations:”);
scanf(“%d “, &n);
/* Entering value of observation */
printf( “Enter the Observations = \n”;
for (i=0; i<n; i+ +)
{
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 7
scanf(“%d”, &num [i]) ;
}
/* sorting observations in ascending order */
for (i = 0; i < n; i + +)
{
for (j = i +1; j < n; j + +)
{
if num [i]>num [j]
{
temp = num [i];
num [i] = num [j];
num [j] = temp;
}
}
}
/ * Printing sorted array */
printf( “observations in Ascending order \n”);
for (i = 0; i < n; i + +)
printf(“%d \n “, num[i] );
}
Example: Write a program to search a given number from an array and display appropriate message. [linear search]
#include < iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <iomanip.h>
{
/* Program for linear search for given number */
int a[100], i, n, sc, key ,pos;
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 8
clrscr( );
printf( “Enter the array limit: \n”);
scanf(“%d”, &n);
/* Enter array values */
printf( “Enter the elements value \n”);
for (i = 0; i< n; i + +);
scanf(“%d”, &a[i]);
printf( “Enter the key value for searching: \n ”);
scanf(“%d”, &key);
/* linear search */
sc=0;
for (i = 0; i< n; i + +);
{
if (a[i]==key )
{
sc = 1;
pos=i;
}
}
if (sc ==1)
printf( “ \n The element is found in location : %d ”, pos+1).;
else
printf( “ \n given value is not found” ) ;
}
1.1.3 Two Dimensional Arrays. [Matrix]
It is possible for array to have two or more dimensions. We shall go through two-dimensional array only. Two dimensional array is called matrix.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 9
 Declaration of TWO dimensional array
<type> < subscript Name> [ Row Range ] [col Range ];
Example: int a[3][3]; /* declaration of 3/3matrix int type */
float x[3][3]; /* declaration of 3/3matrix float type */
Initialization of an array.
Example: int a[3][2] = {
{10, 15};
{25, 11};
{9, 3};
}
Storing values in an array
with help of two for() statements forming nested loop, we can store the element values in an array
a[i][j]
Example. int a[3][3], i,j; a[0][0] 1
/* storing values */ a[0][1] 1
for (i = 0; i< 3; i + +) a[0][1] 1
{ a[1][0] 2
for (j = 0; j< 3; j + +) a[1][1] 2
scanf(“%d”,&a[i][j]); a[1][2] 2
a[2][0] 3
} a[2][1] 3
a[2][2] 3
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 10
Reading values from an array for process just printing array values.
for (i = 0; i< 3; i + +)
{ output for above values
for (j = 0; j< 3; j + +) 1 1 1
printf(“%d”, a[i][j] ); 2 2 2
printf( “\n”); 3 3 3
}
Key Note for array in C :
1. Selection of array name is similar to selecting a variable name or identifiers in C.
2. The range of subscript start from zero (0) up to specified final value.
3. Subscript range must be +ve integer constant .
Example: Write a program to define order of matrix and find the sum of all elements .
#include < iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <iomanip.h>
main ( )
{
/* Array declaration */
int a[10][10];
int i, j, sum = 0, m, n;
clrcsr ( );
printf( “Enter the order of matrix \n” );
printf( “Enter Row Range: \n” );
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 11
scanf(“%d “,&m);
printf( “Enter Col Range: \n”);
scanf(“%d”,&n);
/* storing values in an array */
printf( “Enter Elements values \n ”);
for (i = 0; i < m; i + +)
{
for (j = 0; j < n; j + +)
scanf(“%d”,&a[i] [j]);
}
/* Printing matrix &finding sum of elements */
printf( “printing given matrix \n”)
for (i = 0; i < m; i + +)
{
for (j = 0; j < n; j + +)
{
printf(“%d ”,&a[i] [j]);
sum = sum + a[i] [j];
}
printf(“\n”);
}
printf( “sum of all element = %d ”, sum);
}
Self Assessment Questions
1. Define an array? Write its advantages using in Program.
2. Write the syntax of declaration of an array with example of each.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 12
3. What are the points should remember using array in program.
1.2 Pointers
Definition of pointer
“A pointer is a variable that can hold the address of the variables, structures and functions that are used in the program. It contains only the memory location of the variable rather than its containts”.
Pointers are used with followings:
1. Basic data type variable.
2. Array Subscript variable.
3. Function names.
4. Structure and Union names.
Advantages of Pointers:
1. Pointers are pointing to different data types and structures
2. Manipulation of data at different memory locations is easier.
3. To achieve a clarity and simplicity
4. More compact and efficient coding.
5. To return multiple value via functions.
6. Dynamic memory allocations.
1.3 Declaring a pointer variable
Pointers are declared similar to normal variables, but we must specify when we declare them what they are going to point to it. We declare a pointer to point to an integer, then it cant be used to point a floating-point value etc.
1.3.1 Pointer Operators:
To declare and refer a pointer variable, provides two special operators & and *.
1. Address Operator (ampersand) : &
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 13
2. Indirectional Operator : *
&  (ampersand ) This Operator gives the memory Address of the variable.
*  This Operator gives the value of the variable.
Example : if i = 100
i Memory address

&i  it points the memory address i.e. 1004
*i  it points value of the variable i i.e. 100
Types of pointer variable declaration :
Example :
char *cptr; pointer to character type variables
int *iptr; *num pointer to integer type variables
float *fptr; pointer to float type variables
char *name[15] pointer to character array
Note: * symbol is part of the variables type.
Example : long int *x, *y;
float *avg, *ratio; etc.
Example: Program to assign the pointer values. (using operator & and *)
#include< iostream.h>
#include<conio.h>
main( )
{
int *x, y; /* xis pointer to integer variable */
clrscr ( );
y = 10;
x = &y; /* y value stored in pointer x.*/
100
1004
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 14
printf( “Address of y = %d \n ” , &y);
printf (“value of y = %d \n” , y);
printf( “Address of y = %d \n ” , x);
printf( “value of y = %d \n ”, *x);
}
output
Address of y = 65555
Value of y = 10
Address of y = 65555
Value of y = 10
Note:
i) 65555 is a address of &y it should be unsigned +ve.
ii) last statement value of y indirectly by using *x. *x-value at address stored by x.
Therefore * is called indirection operator when used in conjunction with pointers.
Example: Program to assign the values using operator *and &.
#include <iostream.h>
#include <conio.h>
main()
{
int x, y, *ipt; /* ipt is a pointer to integer variable */
clrscr ( );
x = 8;
ipt = & x; /*Address of x is stored in ipt */
y = *ipt; /* Content of pointer goes to y */
printf( “The value of y is = %d \n “, y);
}
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 15
output
The value of y is = 8
Note: Variable y is assigned to value at the address stored in ipt. since ipt contains address of x, the value at address of x is 8, so * ipt is equal to 10.
Example: Program to use arithmetic operations with pointers.
#include <iostream.h>
#include <conio.h>
main ( )
{
int a, *ipt; /* ipt is a pointer to integer variable. */
int m, n, k;
clrscr( );
a = 150;
ipt = &a; /* address of a is assign to pointer */
m = (*ipt) + +;
n = (*ipt) - -;
k = (*ipt) + +;
print( “value of m = %d \n” ,m);
print( “value of n = %d \n ” , n);
print( “value of k = %d \n ”,k);
}
1.4 Pointers and Arrays
There is a close association between pointers and arrays, array elements can be accessed using pointers.
Example: Program to reads 10 array elements & prints the elements using pointer technique.
#include <iostream.h>
#include <conio.h>
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 16
#include <iomanip.h>
main ( )
{
int a[10], *arpt, i;
clrscr( );
printf( “Enter arry values\n”);
for (i = 0; i < 10; i + +)
scanf(“%d \n ”,&a[i]);
/* arpt points to array */
arpt = a;
/* printing by technique 1 */
for (i = 0; i < 10; i + +)
printf(“%d \n “ arpt +i);
/*printing by technique 2 */
for (i = 0; i < 10; i + +)
printf(“%d” , *(arpt + +);
}
Note: arpt is a pointer variable, in the first technique, in the for loop *(arpt + i) it start from 0 element i.e. *(arpt = 0).
In the second technique (*arpt = 0) in first cycle then increment operation i is used with the pointer instead of adding loop index to the pointer.
Example: Program to read n number of element and find the biggest elements among them.
#include <iostream.h>
#include <conio.h>
main ( )
{
int a[100], *arpt, i; big, n;
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 17
clrscr();
printf( “ Enter number of elements: \n”);
sacnf(“%d “, &n);
printf( “Enter number of elements: \n”);
for (i = 0; i < n; i + +)
scanf(“ %d”, &a[i]);
/*the first element address stored in arpt */
arpt = a;
big =*arpt /* first element value stored in big */
for (i = 1; i < n; i + +)
{
if big <*(arpt + i)
big = *(arpt + i);
}
printf( “The biggest among the elements = \n ”, big );
}
1.5 Pointers used in function
It is mechanism by which pointers can be passed as arguments to the function. Thus, the data items of the calling program can be accessed by the called program. No values is copied when pointers are passed as arguments, as in the called by value method. Another important point is that, if the values are changed in the function this will modify the original contents of the actual parameters, this is not true in case of call by value method.
When the pointers are passed as an argument we must follow the following points.
a. In the calling program, the function is invoked with a function name and addresses of actual parameters enclosed within the parenthesis.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 18
Example :
< Function Name>(&var1,&var2,&var3………….&var n)
var  all are actual parameters.
b. In the called program parameter list, each & every formal parameter (pointers) must be preceeded by an indirection operatore(*)
Example :
<data type> <function Name>(*v1,*v2,*v3…………*vn )
v --> all are formal parameters (pointers)
Example : Program to illustrate the call by reference method to interchange the value of 2 integer variable.
main()
{
int num1,num2;
int interchange( int *n1, int *n2);
printf( “Enter any Two integer number\n”);
scanf(“%d %d “, &num1,&num2);
printf(“before interchanging \n);
printf(“num1 = %d and num2 = %d”,num1,num2);
interchange(&num1,&num2);
printf(“after interchanging \n);
printf(“num1 = %d and num2 = %d” num1, num2);
}
int interchange(int *n1, int *n2)
{
int temp;
temp=*n1;
* n1=*n2;
*n2=temp;
}
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 19
1.6 Pointers used in an Array
Pointers can be used with array to increase the efficiency of the execution of the program. Pointers can be used with single dimensional or multi-dimensional arrar.
Pointers using in Single Dimensional Array.: The name of a array itself designates some memory location & this location in memory is the address of the very first element of an array, the address of the first element of array & num[0], where num is an array name.
Example :
Write a program to use an array of 5 elements & illustrate the relationship between elements of an array & their address.
main()
{
int arrlist[5];
int *ptr,index,value=3;
ptr = arrlist;
for(index=0; index<5; index++)
{
*(ptr+index)=value++;
printf(“*(ptr+index)=%d\tarrlist(index)=%d \n”,*(ptr+index),arrlist[index]);
}
}
Output :
*(ptr+index)= 3 arrlist(index)= 3
*(ptr+index)= 4 arrlist(index)= 4
*(ptr+index)= 5 arrlist(index)= 5
*(ptr+index)= 6 arrlist(index)= 6
*(ptr+index)= 7 arrlist(index)= 7
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 20
Example :
Write a program to find the sum of 5 elements static in nature using pointers with function.
main()
{
static int array[5]={200,400,600,800,1000};
int addnum(int *ptr); / * function protype */
int sum;
sum = addnum(array);
printf(“ Sum of all array elements = %d \n”,sum);
}
int addnum(int *ptr)
{
int total = 0, index;
for(index=0; index<5; index++)
total +=(ptr+index);
return(total);
}
Self Assessment Questions [ 1.2 to 1.6 ]
1. Define pointer?
2. Write a advantages of using pointers in programs.
3. Explain with an example of Pointers operators.
1.7 Structures
Definitions : Structure is a meaningful organized Collection of data items of different type under a unique name that name we called as structure name.
In „C‟ declaration of such related data items or fields of different types by using reserve word ‘struct’ .
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 21
1.7.1 Declaration of structure
Each and every structure must be defined or declared before it appears or using in program.
Syntax: struct <structurer name>
{
<type1> <field/data1>
<type2> <field/data2>
<type3> <field/data3>
………………………
……………………….
<type n> <field/data n>
};
Example :
Struct student
{
int rollno;
char name[30];
char address[30];
char city[15];
float marks;
};
1.7.2 Initialization of structure
Initializing a structure description of structure member is similar to initializing static type declaration.
Example : structure student={122,”Sakshi”, “Arvind Appt.”,”Manipal”,560};
Embedded Structure declaration : [Nested]
It means that, Structure within the another structure is called an embedded structure.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 22
These type of structure declared mainly in two ways that are:
a) Structure may completely defined within the another structure.
b) There may be a separate structure, the embedded structure declared first and the other structure declared next.
Example:
1. sruct emp
{
int empno;
char emp_name[30];
int salary;
struct date_join
{
int day;
int month;
int year;
};
};
2. sruct emp
{
int empno;
char emp_name[30];
int salary;
struct date_join
};
struct date_join
{
int day;
int month;
int year;
};
1.7.3 Processing of Structure
The process of structure is mainly concerned with the accessing structure member. Each member of a structure is accessed with .(dot) operator to access a particular member of the structure, the dot operator must be placed between the name of the structure & the name of the structure member.
Examples :
emp.emp_name, emp.empno , emp.salary etc.
1. Write a program to accept the student details as roll_no, name, city, marks using structure and print the details.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 23
struct std
{
int rollno;
char name[30];
char city[15];
int marks;
} st; /* structure definition */ /* st -> is the structure point */
main() /*main program */
{
printf(“enter the Roll no \n”);
scanf(“%d “, &st.rollno);
printf(“enter the Name \n”);
scanf(“%s “, st.name);
printf(“enter the city \n”);
scanf(“%d “, st.city);
printf(“enter the Marks \n”);
scanf(“%d “, &st.marks);
/* printing details */
printf(“Roll Number : %d”,st.rollno);
printf(“Name : %s”, st.name);
printf(“City : %s”, st.city);
printf(“Marks : %d”,st.marks)
}
1.7.4 Structure used with an Array
However we know that different type of data sets cannot be stored an array, So, to overcome this disadvantage structure can be stored along with its members in array structure.
Example: Storing 10 students details structure in an array.
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 24
struct student
{
int rollno;
char name[30];
char city[15];
int marks;
} std[10]; /* Array defining */
Self Assessment Questions
1. Define Structure ?
2. Write a advantages of Structure over Arrays using in programs.
3. Give one suitable example of Structure using an array.
1.8 Summary
Arrays are the basis for creating any new data structures; understanding of arrays is essential and becomes vital role of programmer while implementing the codes. Using arrays one can declare and define multiple variables of same type with one identifier. For e.g. int a[10] is a declaration of 10 variables which are clustered together. It also saves a memory space, easy for sorting and searching the homogeneous type of data.
std ( array name)
int rollno;
char name[30]; char city[15];
int marks;
int rollno;
char name[30];
char city[15];
int marks;
int rollno;
char name[30];
char city[15];
int marks;
-------------------
--------------------
…………………
int rollno;
char name[30];
char city[15];
int marks;
std[1]
std[0]
std[2]
std[9]
Data Structures using „C‟ Unit 1
Sikkim Manipal University Page No.: 25
The pointer are special type of variables that hold the address value. Pointers are special variables as they simply point to other variable. The pointers are the powerful tool for instance, are used to setup complicated data structure and are used to link variables together.
1.9 Terminal Questions
1. Define Array ? Write the Syntax with example of declaring a single and double dimension array in „C‟.
2. Write a „C‟ program to read N number of observations and print them in ascending order.
3. Accept an array of elements and divide each element in array by 3.
4. Find total occurrence of the given number 'n' in an array of 10 numbers entered by the user.
5. Numbers in array are stored in linear fashion, find the biggest and the smallest of 10 numbers in the given array.
6. Array elements are stored from 0th location, relocate the elements to start from 4th location
7. Find occurrence of each number in the array.
8. Check whether the given array is a palindrome or not.
9. Reverse the given array without using extra memory.
10. Store a string in an array and find the frequency of occurrence of each character in the array.
11. Without using string functions find the length of the string.
12. Define Pointer? Discuss the advantages of using pointers in Program.
13. Explain the pointer operators with an example of each.
14. Illustrates the „C‟ programs which is represents the pointers with array and pointers with functions.
15. Define Structure ? Write Syntax with appropriate example for declaration of Structure.