M23BCS304

MODULE 1
DATA STRUCTURES AND APPLICATIONS (M23BCS304)

Introduction: Data Structures, Classifications (Primitive & Non-Primitive), Data structure Operations, Review of
pointers and dynamic Memory Allocation
ARRAYS and STRUCTURES: Arrays, Dynamic Allocated Arrays, Structures and Unions, Polynomials, Sparse
Matrices, representation of Multidimensional Arrays, Strings

Introduction to Data Structures

Data may be organized in many different ways logical or mathematical models of a program particularly
organization of data. This organized data is called “Data Structures”.

Data Structure=Organized data +Allowed operations

Data Structure involves two complementary goals. The first goal is to identify and develop useful, mathematical
entities and operations and to determine what class of problems can be solved by using these entities and operations.
The second goal is to determine representation for those abstract entities to implement abstract operations on this
concrete representation.
Data structure is a representation of the logical relationships existing between individual elements of data. A data
structure is a way of organizing all data items that considers not onlythe elements stored but also their relationship to
each other.
The logical or mathematical model of a particular organization of data is called a data structure.

The choice of a particular data model depends on the two considerations:

 It must be rich enough in structure to mirror the actual relationships of the data in the realworld.
 The structure should be simple enough that one can effectively process the data whenevernecessary.
BASIC TERMINOLOGY
Elementary Data Organization
Data: Data are simply values or sets of values.
Data items: Data items refers to a single unit of values. Data items that are divided into sub- items are called Group
items. Ex: An Employee Name may be divided into three subitems- first name, middle name, and last name. Data
items that are not able to divide into sub-items are called Elementary items. Ex: SSN
Entity: An entity is something that has certain attributes or properties which may be assigned values. The values
may be either numeric or non-numeric. Ex: Attributes- Names, Age, Sex, SSN Values- Rohland Gail, 34, F, 134-34-
5533 Entities with similar attributes form an entity set. Each attribute of an entity set has a range of values, the set of
all possible values that could be assigned to the particular attribute. The term “information” is sometimes used for
data with given attributes, of, in other words meaningful or processed data.
Field: is a single elementary unit of information representing an attribute of an entity. Record is the collection of
field values of a given entity.
File: is the collection of records of the entities in a given entity set.

Each record in a file may contain many field items but the value in a certain field may uniquely determine the record
in the file. Such a field K is called a primary key and the values k1, k2, ….. in such a field are called keys or key
values.
Records may also be classified according to length.
A file can have fixed-length records or variable-length records.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 1

 M23BCS304
 In fixed-length records, all the records contain the same data items with the same amount ofspace assigned to each
data item.
 In variable-length records file records may contain different lengths. Example: Student records have variable
lengths, since different students take different numbers of courses. Variable-length records have a minimum and a
maximum length. The above organization of data into fields, records and files may not be complex enough to
maintain and efficiently process certain collections of data. For this reason, data are also organized into more
complextypes of structures.

CLASSIFICATION OF DATA STRUCTURES

Data Structures can be divided into two categories,
i) Primitive Data Structures
ii) Non-Primitive Data Structures

Primitive Data Structures

These are basic data structures and are directly operated upon by the machine instructions. These data types consists
of characters that cannot be divided and hence they also called simple data types.
Example: Integers, Floating Point Numbers, Characters and Pointers etc.
Non-Primitive Data Structures
These are derived from the primitive data structures. The non-primitive data structures emphasizeon structuring of a
group of homogeneous or heterogeneous data items.
Example: Arrays, Lists and Files, Graphs, trees etc.
Based on the structure and arrangement of data, non-primitive data structures isfurtherclassified into
1. Linear Data Structure
2. Non-linear Data Structure
1. Linear Data Structure:
A data structure is said to be linear if its elements form a sequence or a linear list. There are basically two ways of
representing such linear structure in memory.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 2

 M23BCS304
 One way is to have the linear relationships between the elements represented by means of sequential
memory location. These linear structures are called arrays.
 The other way is to have the linear relationship between the elements represented by means of pointers or
links. These linear structures are called linked lists.
The common examples of linear data structure are Arrays, Queues, Stacks, Linked lists
2. Non-linear Data Structure:
A data structure is said to be non-linear if the data are not arranged in sequence or a linear. The insertion and
deletion of data is not possible in linear fashion. This structure is mainly used to represent data containing a
hierarchical relationship between elements. Trees and graphs are the examples of non-linear data structure.

Operations on the Data Structures:

The following operations can be performed on the data structures:
 Traversing
 Searching
 Inserting
 Deleting
 Sorting
 Merging
The commonly used operations on data structures are as follows,
1. Create: The Create operation results in reserving memory for the program elements. The creation of data
structures may take place either during compile time or duringrun time.
2. Destroy: The Destroy operation destroys the memory space allocated for the specifieddata structure.
3. Selection: The Selection operation deals with accessing a particular data within a datastructure.
4. Updating: The Update operation updates or modifies the data in the data structure.
5. Searching: The Searching operation finds the presence of the desired data item in thelist of data items.
6. Sorting: Sorting is the process of arranging all the data items in the data structure in a particular order, say
for example, either in ascending order or in descending order.
7. Merging: Merging is a process of combing the data items of two different sorted listinto a single list.
REVIEW OF POINTERS AND DYNAMIC MEMORY ALLOCATION

Pointers to data significantly improve performance for repetitive operations such as traversing strings, lookup
tables, control tables and tree structures. In particular, it is often much cheaper in time and space to copy and
dereference pointers than it is to copy and access the data to which the pointers point. Pointers are also used to hold
the addresses of entry points for called subroutines in procedural programming and for run-time linking to dynamic
link libraries (DLLs).

Pointer: A pointer is a special variable which contains address of a memory location. Using this pointer, the data
can be accessed. For example, assume that a program contains four occurrences of a constant 3.1459. During the
compilation process, four copies of 3.1459 can be created as shown below:

However, it is more efficient to use one copy of 3.1459 and three pointers referencing a single copy, since less space
is required for a pointer when compared to floating point number. This can be represented pictorially as shown
below:

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 3

 M23BCS304

General form of pointer declaration is –type* name;

where type represent the type to which pointer thinks it is pointing to.
Pointers to machine defined as well as user-defined types can be made PointerInitialization:
variable_type *pointer_name = 0;
or variable_type *pointer_name = NULL;
char *pointer_name = "string value here";

The pointer in C is a variable that stores the address of another variable. This variable can be of type int, char, array,
function, or any other pointer. The size of the pointer depends on the architecture. However, in 32-bit architecture,
the size of a pointer is 2bytes.
Consider the following example to define a pointer that stores the address of an integer.
int n = 10;
int* p = &n; // Variable p of type pointer is pointing to the address of the variable n of type integer.
Example:
void main ()
{
int a, *p;
a=10;
p= &a;
printf (“\n value of a = %d a=%d”, a, *p); // display value using pointer variable
printf (“\n address of a = %u a=%u”, &a, p); // display address using pointer variable
}

Declaring a pointer
The pointer in the c language can be declared using * (asterisk symbol). It is also known as an indirection
pointer used to dereference a pointer.
1. int *a;//pointer to int
2. char *c;//pointer to char
Example:
void main ()
{
int number=50;
int *p;
p=&number; //stores the address of the number variable
printf ("Address of p variable is %x \n”, p); // p contains the address of the number,printing p gives the address of the
number.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 4

 M23BCS304
printf ("Value of p variable is %d \n”, *p); // As we know that * is used to dereference
a pointer therefore if we print *p, we will get the value stored at the address containedby p.
}

Dangling Pointers- The most common bug related to pointers and memory management is dangling/wild pointers.
Sometimes the programmer fails to initialize the pointer with a valid address, then this type of initialized pointer is
known as a dangling pointer in C.
Memory Allocation

Static Allocation – The process of allocating memory for variables during compilation time is called static memory
allocation.
Disadvantages of static allocations are:
 The size of allocated memory space is fixed, it can’t be altered during runtime.
 Wastage of memory space if more memory is allocated

 Overflow if less memory is allocated

DYNAMIC MEMORY ALLOCATION
This is process of allocating memory-space during execution-time (or run-time).
• This is used if there is an unpredictable storage requirement.
• Memory-allocation is done on a heap.
• Memory management functions include:
→ malloc (memory allocate)
→ calloc (contiguous memory allocate)
→ realloc (resize memory)
→ free (deallocate memory)

1. malloc () function:

The “malloc” or “memory allocation” method in C is used to dynamically allocate a single large block of memory
with the specified size. It returns a pointer of type void which can be cast into a pointer of any form. It doesn’t
Initialize memory at execution time so that it has initialized each block with the default garbage value initially.
Syntax of malloc() in C:

ptr = (cast-type*) malloc(byte-size)

For Example:
ptr = (int*) malloc(100 * sizeof(int));

Since the size of int is 4 bytes, this statement will allocate 400 bytes of memory. And, the pointer ptr holds the
address of the first byte in the allocated memory.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 5

 M23BCS304

#include <stdio.h>
#include <stdlib.h>
int main()
{
int* ptr;
int n, i;
printf("Enter number of elements:");
scanf("%d",&n);
printf("Entered number of elements: %d\n", n);
// Dynamically allocate memory using malloc()
ptr = (int*)malloc(n * sizeof(int));
// Check if the memory has been successfully
// allocated by malloc or not
if (ptr == NULL) {
printf("Memory not allocated.\n");
exit(0);
}
else {
printf("Memory successfully allocated using malloc.\n");
for (i = 0; i < n; ++i) {
ptr[i] = i + 1;
}
printf("The elements of the array are: ");
for (i = 0; i < n; ++i) {
printf("%d, ", ptr[i]);
}
}
return 0;
}
Output
Enter number of elements:7
Entered number of elements: 7
Memory successfully allocated using malloc.
The elements of the array are: 1, 2, 3, 4, 5, 6, 7,

2. Calloc () function:
1. “calloc” or “contiguous allocation” method in C is used to dynamically allocate the specified number of
blocks of memory of the specified type. it is very much similar to malloc() but has two different points and
these are:
2. It initializes each block with a default value ‘0’.
3. It has two parameters or arguments as compare to malloc().
Syntax of calloc() in C
ptr = (cast-type*)calloc(n, element-size);
here, n is the no. of elements and element-size is the size of each element.

For Example:

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 6

 M23BCS304
ptr = (float*) calloc(25, sizeof(float));
This statement allocates contiguous space in memory for 25 elements each with the size of the float.

If space is insufficient, allocation fails and returns a NULL pointer.

Example of calloc() in C
C
#include <stdio.h>
#include <stdlib.h>
int main()
{
int* ptr;
int n, i;
n = 5;
printf("Enter number of elements: %d\n", n);
// Dynamically allocate memory using calloc()
ptr = (int*)calloc(n, sizeof(int));
// Check if the memory has been successfully
// allocated by calloc or not
if (ptr == NULL) {
printf("Memory not allocated.\n");
exit(0);
}
else {
// Memory has been successfully allocated
printf("Memory successfully allocated using calloc.\n");
// Get the elements of the array
for (i = 0; i < n; ++i) {
ptr[i] = i + 1;
}
// Print the elements of the array
printf("The elements of the array are: ");
for (i = 0; i < n; ++i) {
printf("%d, ", ptr[i]);
}
}
return 0;
}

Output
Enter number of elements: 5
Memory successfully allocated using calloc.
The elements of the array are: 1, 2, 3, 4, 5,

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 7

 M23BCS304
3. Realloc () function:
If memory is not sufficient for malloc () or calloc (), you can reallocate the memory by the realloc () function. In
short, it changes the memory size either by extending or deleting the memory at the end of the block.
If the existing memory can be extended, the ptr value will not be changed. If the memory cannot be extended, this
function allocates a completely new block and copies the contents of the existing memory block into a new memory
block, and then deletes the old memory block.

Let's see the syntax of the realloc () function.

ptr=(cast-type *) realloc (ptr, new-size)

ptr pointer to a block of previously allocated memory either using malloc () /calloc().Size new size of the block.
It returns the address of the first byte of the allocated memory block if memory allocation is successful. The return
type of pointer is void. By typecasting appropriately, we can use it to store int, float, and char. etc.
It returns NULL if memory is not sufficient.

Example:

#include<stdlib.h>
void main ()
{
char * str;
str= (char *) malloc (10); strcpy (str,” Computer”); str= (char *)realloc(str,40);
strcpy (str,” Computer Science and Engineering”);
}
4. free () function:
The memory occupied by malloc () or calloc () functions must be released by calling the free () function. Otherwise,
it will consume memory until the program exits. It is the responsibility of the programmer to deallocate memory
whenever it is not required bythe program and initialize it to NULL.
Let's see the syntax of the free () function.
free(ptr)
ptr = NULL;

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 8

 M23BCS304

Difference between malloc () and calloc ():

malloc () calloc ()
Allocates a block of memory of size Allocates multiple blocks of memory,
bytes each block with the same size
Allocated space will not be initialized Allocated space is initialized to zero.
Syntax of malloc is: Syntax of calloc is:
ptr =(data type *)malloc(size); ptr =(data type *)calloc(n, size);
It can allocate the memory block even if It can allocate multiple blocks of memory
the memory is not available only if the memory is available
contiguously. contiguously.

Arrays

An array is a special and very powerful data structure in C language. An array is a collection of similar data items.
All elements of the array share a common name. Each element in the array can be accessed by the subscript (or
index). An array is used to store, process, and print large amounts of data using a single variable.
Example: Marks of all students, Names of all employees, etc.

Single-Dimensional Array: A single-dimensional array (one-dimensional array) consists of related data items of
the same type. In Memory, all the data items are stored in contiguous locations one after the other.

Since an array is identified by a common name, any element in the array can be accessed by specifying one
subscript.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 9

 M23BCS304
For example,

0th item can be accessed by specifying a[0], similarly we can access 1st ,2nd,3rd,and 4th item by specifying
a[1],a[2],a[3], and a[4] respectively.

Declaration of 1-D array:

Syntax:
Datatype ArrayName [size];
 Where, Datatype ->Type of an array
ArrayName -> Name of an array
Size ->Number of elements in the array
Example:
int arr [5]; // arr is an array of 5 integers
Here, each item in the array can be accessed by specifying the index arr [0] througharr [4].

A simple program to read and display 1-dimensional array elements is shownbelow:

void main ()
{
int a [10], n, i;
printf (“\n enter value to n”);
scanf (“%d”, &n);
printf (“\n enter array elements”);
for (i=0; i<n; i++)
scanf (“%d”, &a[i]);
printf (“\n the array elements are”);
for (i=0; i<n; i++)
printf (“%d\t”, a[i]);
}
Arrays and Pointers:
The array name can be considered as a pointer containing the address of the firstelement of the array.
Let us consider,
int a [5] = {1,2,3,4.5};
The compiler reserves 5 memory locations and stores 5 integer values 1,2,3,4,5 inthese memory locations as
shown below:
Values a [0] a [1] a [2] a [3] a [4]

1 2 3 4 5

1000 1004 1008 1012 1016

Address &a[0] &a[1] &a[2] &a[3] &a[4]
The starting address of the first byte of the array ‘a’ i.e. 1000 is called the baseaddress.
Here, array name ‘a’ can be considered as a pointer and contains the address of a [0].
Hence we can write
& a[0] as (a+0) a[0] as *(a+0)

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 10

 M23BCS304
& a[1] as (a+1) a[1] as *(a+1)
………………. ………………
……………….. ………………
& a[4] as (a+4) a[4] as *(a+4)

&a[i] or (a+i) or (i+a) a[i] or *(a+i) or *(i+a) or i[a]

NOTE: The address of array element in 1-dimensional array can be obtained by,
Address of a[i] = base address + sizeof (data type) * i

The difference between int * a and int a [5] and int *a [5] declarations are as shownbelow:
int *a; Pointer to an integer.

The address of the first memory location is copied into a.

int *a [5]; Array of 5 pointers to integers. The compiler allocates 5 memory locations to store 5 pointers to
integers and the address of the first memory locationis copied into a.

Program to insert an element at a given position in an array.

#include <stdio.h>
void main ()
{
int a[10], n, i, item, pos;
printf ("\n enter size of the array");
scanf ("%d", &n);
printf ("\n enter array elements");
for (i=0; i<n; i++)
scanf ("%d”, &a[i]);
printf ("\enter the position at which item to be inserted");
Pradeep B M, Assistant professor, Dept of CE, MITM. Page 11
 M23BCS304
scanf ("%d", &pos);
printf ("\n enter element to be inserted");
scanf ("%d", &item);
for (i=n-1; i>=pos; i--)
a[i+1] =a[i];a[pos]=item;
n=n+1;
printf ("\n the array after insertion of %d is”, item);
for (i=0; i<n; i++)
printf ("%d “, a[i]);
}
Program to delete an element from a given position in an array.
#include <stdio.h>void main ()
{
int a[10], n, i, item, pos;
printf ("\n enter size of the array");
scanf ("%d", &n);
printf ("\n enter array elements");
for (i=0; i<n; i++)
scanf ("%d”, &a[i]);
printf ("\enter the position at which item to be inserted");
scanf ("%d", &pos);
printf ("\n enter element to be inserted");
scanf ("%d", &item);
for (i=pos; i<n-1; i++)
a[i] =a[i+1];
n--;
printf ("\n the array after deletion of %d is”, item);for (i=0; i<n; i++)
printf ("%d “, a[i]);
}
Program to Search a key element in an array using Linear Search Technique.
#include <stdio.h>
#include <stdlib.h>
#define MALLOC(p, s) \ //Macro for malloc( )
if (! (p=malloc(s))) \
{ \
printf ("\n Memory Insufficient"); \
exit (0); \
}
void main ()
{
int *a, n, i, key, flag=0;
printf ("\n enter size of the array");
scanf ("%d", &n);
MALLOC (a, n*sizeof(int));
printf ("\n enter array elements");
for (i=0; i<n; i++)
scanf ("%d”, &a[i]);
printf ("\n enter key element to be searched");
Pradeep B M, Assistant professor, Dept of CE, MITM. Page 12
 M23BCS304
scanf ("%d”, &key);
for (i=0; i<n; i++)
{
if(a[i]==key)
{
printf ("\n key found");flag=1;
break;
}
}
if(flag==0)
printf ("\n key not found");
}
Program to Search a key element in an array using Binary Search Technique.
#include<stdio.h>
#include<stdlib.h>
#define MALLOC(p, s)\
if (!(p = malloc(s)))\
{\
printf ("\n Memory Insufficient");\exit (0); \
}
void main ()
{
int *a, n, i, key, flag=0, low, high, mid;
printf ("\n enter size of the array");
scanf ("%d", &n);
MALLOC (a, n*sizeof(int));
printf ("\n enter array elements");
for (i=0; i<n; i++)
scanf ("%d”, &a[i]);
printf ("\n enter key element to be searched");
scanf ("%d”, &key);
low=0;
high=n-1;
while (low <= high)
{
mid= (low + high)/2;
if(a[mid]==key)
{
printf ("\n key found");flag=1;
break;
}
else if(a[mid] > key)high = mid-1;
else
low = mid+1;
}
if(flag==0)
printf ("\n key not found");
}

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 13

 M23BCS304
Pointer to Pointer
A variable that contains the address of a pointer variable is called a Pointer toPointer.
Example:
int a; //data variable
int * p1; // pointer variable
int **p2; //pointer to pointer variable
a=10;
p1 = &a;
p2 = &p1;
a
a=10

2- Dimensional arrays using Pointer to Pointer:

A 2D array is also known as a matrix (a table of rows and columns). To create a 2D array of integers, take a look at
the following example:int matrix [2][3] = { {1, 4, 2}, {3, 6, 8} };
The first dimension represents the number of rows [2], while the second dimension represents the number of
columns [3]. The values are placed in row order, and can be visualized like this:

To access an element of a two-dimensional array, you must specify the index number of both the row and column.

int matrix [2][3] = { {1, 4, 2}, {3, 6, 8} };

To loop through a multi-dimensional array, you need one loop for each of the array's dimensions.
The following example outputs all elements in the matrix array:
int matrix [2][3] = { {1, 4, 2}, {3, 6, 8} };
int i, j;
for (i = 0; i < 2; i++)
{
for (j = 0; j < 3; j++)
{
printf ("%d\n", matrix[i][j]);
}
}

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 14

 M23BCS304
A 2-dimensional array is represented as a 1-dimensional array of pointers whereeach pointer contains the address of
the one-dimensional array.
In the above example, it contains 2 rows and 3 columns. 2 rows, matrix [0] and matrix [1] are 2 pointers points to a
one-dimensional array consisting of 3 elements.
Create a 2-Dimensional Array:
Step 1: Allocate memory dynamically for specified no. of row pointers as follows:
MALLOC (ptr, rows * sizeof (* ptr)) ; //MALLOC is a MACRO
Step 2: Allocate memory dynamically for each row with a specified no. of columns.
for (i=0; i<rows; i++) MALLOC (ptr[i], cols * sizeof(int)) ;
The function to create a 2D array dynamically is as follows:
int ** make2Darray (int row, int col)
{
int **x, i;
MALLOC (x, rows * sizeof (* x)); //MALLOC is a MACRO
for (i=0; i<rows; i++)
MALLOC (x[i], col * sizeof(int));return x;
}
Write a program to find the sum of 2 matrices using dynamic array.
#include<stdio.h>
#include<stdlib.h>
#define MALLOC(p, s)
\if (! p = malloc(s)) \
{ \
printf (“\n insufficient memory”); \
exit (0); \
}
int ** make2Darray (int rows, int cols)
{
int **x, i;
MALLOC (x, rows * sizeof (* x)); //MALLOC is a MACROfor (i=0; i<rows; i++)
MALLOC (x[i], cols * sizeof(int));return x;
}
void read_array (int **a, int r, int c)
{
int i, j;
for (i=0; i<r;i++)
for (j=0; j<c; j++)
scanf (“%d”, &a[i][j]);
}
void display_array (int **a, int r, int c)
{
int i,j;
for (i=0; i<r;i++)
{
for (j=0; j<c; j++)

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 15

 M23BCS304
printf (“%d\t”, a[i][j]);printf(“\n”);
}
}
void main()
{
int **a, **b, **c;
int row, col;
printf (“\n enter size of the matrix”);scanf (“%d %d”, &row, &col); a=make2Darray(row,col);
printf (“\nenter matrix A elements”);read_array(a,row,col);

b=make2Darray(row,col);
printf (“\nenter matrix B elements”);read_array(b,row,col);

c=make2Darray(row,col);for (i=0;i<row;i++)
for (j=0;j<col;j++) c[i][j] = a[i][j] + b[i][j];
printf (“\n addition of 2 matrices”); display_array(c,row,col);
}
Structures

A structure is defined as a group of variables of the same or different datatypes. Thevariables that are used to store
the data are called members of the structure Or fields of the structure.
We can define a structure by using the struct keyword and declare each of itsmembers inside curly braces:
struct person
{
// Structure definitionint age;
// Member (int variable)
char name[25];
// Member (string variable)
}; // End the structure with a semicolon

Structure declaration: A structure can be declared using three different ways:

 Tagged Structure
 Structure variables
 Type defined structures
a) Tagged Structure: The structure definition with the tag name is calledtagged structure. The tag name is the
name of the structure.
Syntax:
struct tagname
{
type1 member1;
type2 member2;
……. ………..
……. …………
};
Example:
struct student

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 16

 M23BCS304
{ tag name
char name [10];
int id;
float marks;
};
To allocate memory for structure members, we have to declare the variables as shown below:
struct student S1, S2;
b) Structure variables:

Syntax:
struct
{
type1 member1;
type2 member2;
……. ………..
……. …………
} v1,v2,……vn;
20
Example:
struct student
{
char name [10];
int id;
float marks;
} S1, S2;
NOTE: This method of defining and declaring structure variables is rarely used.

c) Type-defined Structure:

The typedef keyword is associated with the structure definition. There are two ways to define the structure using
typedef.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 17

 M23BCS304

Structure initialization: Structures can be initialized as shown below:

Method 1:
struct str1
{
int i; char c;float f;
}
var1 = {10,’ A’,18.95};
Method 2:
struct str1
{
int i; char c;float f;
};
struct str1 var1 = {10,’A’,18.95};

NOTE: Members of the structure cannot be initialized in the structure definition asshown below. It results in a
syntax error.
struct str1
{
int i=10; char c=’A’;
float f=18.95;
};
Access Structure Members
We can access structure members by using the (.) dot operator through thestructure variable.
Syntax:
structure variable. member1;
structure variable. Member2;
Example:
struct str1
{
int i;
char c;
float f;
}s1;

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 18

 M23BCS304
We can read values to members of the structure using the variable s1:
scanf (“%d %c %f”, &s1. i, &s1.c, &s1. f);
Also, we can print the values of members of the structure using s1 as:
printf (“%d %c %f”, s1.i, s1.c, s1.f);
In the case where we have a pointer to the structure, we can also use the arrow(->) operator to access the
members.
Example:
struct sample
{
int i;
char c;
float f;
} s1;
struct sample *s2= &s1;
scanf (“%d %c %f”, s2-> i, s2->c, s2->f);

Self-referential Structures:

A structure in which one or more of its members is a pointer to itself is called a self-referential structure.
Self-referential structures are widely useful in dynamic data structures like linked lists, trees, etc.

Example:
struct node
{
int data;
struct node *next; // next is a pointer to a struct node variable
};
typedef struct node *NODE;NODE first, last;

Unions:
The Union is a user-defined data type in C language that can contain elements of the different data types just like
structure. But unlike structures, all the members in the C union are stored in the same memory location. Due to
this, only one membercan store data at a time.
Syntax: Example:
typedef union typedef union
{ {
type1 member1; char grade;
type2 member2; int id;
……. ……….. float marks;
……. ………… } STUDENT;
} TYPE_ID; STUDENT x;

The size of the union is equal to the size of the largest [Link] the members share the same memory space.

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 19

 M23BCS304
The difference between Structures and Union:

Structures Union
Keyword struct is used to define a The keyword union is used to define a
structure union.
When a variable is associated with a structure, When a variable is associated with a union, the
the compiler allocates the memory for each compiler allocates the memory by considering
member. The size of the structure is greater the size of the largest member. So, the size of
than or equal to the sum of the sizes of its the unionis equal to the size of the largest
members. member.

Each member within a structure Memory allocated is shared by individual

is members of the union.
assigned a unique storage area oflocation.
Altering the value of a member will not Altering the value of any of the members
affect other members of the structure. will alter other members values.
Individual members can be accessed at Only one member can be accessed at a
a time time.
Several members of a structure can Only the first member of a union can be
initialize at once. initialized.
Polynomials:

A polynomial is an expression that contains more than two terms. A term is made up of coefficient and
exponent.
Example: P(x) = 4x3+6x2+7x+9P(x)

A polynomial may be represented using an array or structures. A structure may be defined such that it
contains two parts – one is the coefficient and the second is the corresponding exponent. The structure
definition may be given as shown below:

Polynomial Structure Declaration:

struct polynomial
{
int coefficient;
int exponent;
};

Write a program to add two polynomials using structures.

#include <stdio.h>
#include<stdlib.h>
#define MAX_TERMS 50
#define COMPARE(x,y) ((x==y)?0:(x>y)?1:-1)
typedef struct
{
int coeff;

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 20

 M23BCS304
int expon;
} POLYNOMIAL;
int avail=0;
void attach (int c, int e, POLYNOMIAL *p)
{
if (avail == MAX_TERMS)
{
Printf ("\n Too many terms"); exit(0);
}
p[avail].coeff = c; p[avail].expon = e;avail++;
}
void readpolynomial(POLYNOMIAL *p,int *start,int *end)
{
int c,e,i=1;
*start =avail;for(;;)
{
printf("Term No: %d\n",i++);printf("Coefficient:"); scanf("%d",&c);
if(c==0) break; printf("Exponent :");scanf("%d",&e);
attach(c,e,p);
}
*end=avail-1;
}
void printpolynomial(POLYNOMIAL *p,int start,int end)
{
while(start<=end)
{
printf ("%dx^%d + ",p[start].coeff,p[start].expon); start++;
}
}
void addpolynomial(POLYNOMIAL *p,int sa,int ea,int sb,int eb,int *sc,int *ec)
{
*sc=avail;int coef;
while (sa<=ea && sb<=eb)
{
switch (COMPARE(p[sa].expon,p[sb].expon))
{
case 0: coef = p[sa].coeff+p[sb].coeff; if(coef!=0) attach(coef,p[sa].expon,p);sa++;
sb++; break;
case 1: attach(p[sa].coeff,p[sa].expon,p);sa++;
break;
case -1: attach(p[sb].coeff,p[sb].expon,p);sb++;
break;
}
}
while(sa<=ea)
{
attach(p[sa].coeff,p[sa].expon,p);sa++;
}

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 21

 M23BCS304
while(sb<=eb)
{
attach(p[sb].coeff,p[sb].expon,p);sb++;
}
*ec=avail-1;
}
void main ()
{
POLYNOMIAL p[MAX_TERMS];
int startA,startB,endA,endB,startC,endC;printf("\n enter the first polynomial");
readpolynomial(p,&startA,&endA);
printf("\n enter the second polynomial"); readpolynomial(p,&startB,&endB);
addpolynomial(p,startA,endA,startB,endB,&startC,&endC);
printf("\n sum of Polynomials\n");printpolynomial(p,startC,endC);
}
Sparse Matrices:

The sparse matrix can be defined as a matrix that has a greater number of zeroelements than the non-
zero elements.
Why do we need a sparse matrix?
The following are the benefits of using the sparse matrix -
Storage - We know that a sparse matrix contains fewer non-zero elements than zero, so less memory can be
used to store elements. It evaluates only the non-zero elements.
Computing time: In the case of searching in the sparse matrix, we need to traverse only the non-zero
elements rather than traversing all the sparse matrix elements. It saves computing time by logically designing
a data structure traversing non-zero elements.
Representation of sparse matrix:
Representing a sparse matrix by a 2D array leads to the wastage of lots of memory as zeroes in the matrix are
of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero
elements. This means storingnon-zero elements with triples- (Row, Column, value).
#define MAXTERMS 50
typedef struct
{
int row;
int col;
int val;
} term;
term a[MAXTERMS];

Example: Consider a matrix A [4][4] shown below:

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 22

 M23BCS304

The above Sparse matrix has 4 rows and 4 columns which means it contains 4*4
which is 16 elements inside it and each element is an integer value which contains 2 bytes of storage and the total
storage in the sparse matrix is 2*16 that is 32.
we can reduce this storage by eliminating the zero values. This can be done by
representing the non-zero values in array form as shown below.
ROW COLUMN VALUE
A[0] 4 4 5
A[1] 0 2 3
A[2] 1 3 8
A[3] 2 0 1
A[4] 2 2 3
A[5] 3 2 7
Transpose of Matrix
To transpose a matrix, interchange the rows and columns. This means that eachelement a[i][j] in the
original matrix becomes element a[j][i] in the transpose matrix.

Algorithm: -
 for all elements in column j
 place element in <i, j> value in element <j, i> value
The transpose function of the sparse matrix:
void transpose (term a [ ], term b [ ])
{
/* b is set to the transpose of a */ int n, i, j, k;
n = a [0].value; /* total number of elements */ b[0].row = a[0].col; /* rows in b = columns in a */
b[0].col = a[0].row; /* columns in b = rows in a */b[0].value = n;
k=1;
for (i = 0; i < a[0].col; i++) for (j = 1; j <= n; j++)
if (a[j]. col == i)
{
b[k]. row = a [ j]. col;
b[k]. col = a [ j]. row;
b[k]. val = a [ j]. val;k++;
}
}

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 23

 M23BCS304
Transpose of the above Sparse Matrix is:

ROW COLUMN VALUE

B[0] 4 4 5
B[1] 0 2 1
B[2] 2 0 3
B[3] 2 2 2
B[4] 2 3 7
B[5] 3 1 8
Strings:

A String is a sequence of characters terminated with a null character ‘\0’. The String is stored as an array of
characters. The difference between a character array and a string is that the string in is terminated with a
unique character ‘\0’.
String Declaration:
Declaring a string is as simple as declaring a one-dimensional array. Below is the basic syntax for
declaring a string.
char stringname[size];
where, char ->data type
stringname ->variable name
size ->number of characters string can store (including ‘\0’)
Example:
char str [5];
char name [20];
String Initialization:
A string can be initialized in different ways as follows:
1) String literals(constants) can be assigned without size. Here, the nameof the string str acts as a
pointer because it is an array.
Example: char str [ ] = “Hello! Welcome to the class”;
2) String literals can be assigned with a predefined size. But we shouldalways account for one
extra space which will be assigned to the null character. If we want to store a string of size n then we
should always declare a string with a size equal to or greater than n+1.
Example: char str [6] = “Hello”;

3) We can also assign a string character by character. But we should remember to set the end character
as ‘\0’ which is a null character.
Example: char str [6] = {‘H’,’e’,’l’,’l’,’o’,’\0’};

4) We can assign character by character without size with the NULL character at the end. The size of
the string is determined by the compiler automatically.
Example: char str [ ] = {‘H’,’e’,’l’,’l’,’o’,’\0’};

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 24

 M23BCS304
Read a string input:
There are many ways to read a string. The two of the common ones are:
1. scanf (): scanf () function can be used to read a string without a white space.
2. gets (): gets () function can also be used to read a string with white spaces fromthe standard input
until a newline character is reached.
Write a string output:
There are many ways to write a string. The two of the common ones are:
1. printf (): printf () function can be used to print a string without white space.
2. puts (): puts () function can also be used to write a string with white spaces to theconsole and it
automatically adds a newline character at the end.
C program to illustrate string input and output functions.
#include <stdio.h>void main ()
{
char str [20];
printf (“\n enter a string”);
scanf ("%s", str);
printf ("the string is %s", str);
printf (“\n enter a string”);
gets(str);
printf (“string is:”);
puts(str);
}
Output:
enter a string MIT Mysorethe string is: MIT
enter a string MIT Mysorethe string is: MIT Mysore
Standard String Built-in Functions in C:
Some useful string-handling functions are as follows:

Function Name Description

strlen(string_name) Returns the length of the string name.
strcpy (s1, s2) Copies the contents of string s2 to string s1.
strcmp (str1, str2) Compares the first string with the second string. If stringsare the same it
returns 0.
strcat (s1, s2) Concat s1 string with s2 string and the result is stored in thefirst string.
strstr (s1, s2) Find the first occurrence of s2 in s1.
NOTE: Strings handling functions are defined under the "string.h" header file
Write a function
i) To find the length of the string without using built-in functions.
int stringlen (char str [ ])
{
int i, len=0;
for (i=0; str[i]! =’\0’; i++)
len++;
return len-1;
}
Pradeep B M, Assistant professor, Dept of CE, MITM. Page 25
 M23BCS304
ii) String concatenation, without using built-in functions.
void stringconcat (char s1 [ ], char s2 [ ])
{
int i, k;
for (i=0; s1[i]! = ‘\0’; i++); // To reach the end of string s1for (j=0; s2[k]! = ‘\0’; k++)
{
s1[i] = s2[k];i++;
}
s1[i] = ‘\0’;
}
iii) String copy, without using built-in functions.
void stringcpy(char s1[ ], char s2[ ])
{
int i,k;
for (i=0, k=0; s1[i]! = ‘\0’; i++, k++)s2[k] = s1[i];
s2[k] = ‘\0’;
}
iv) String compare, without using built-in functions.
void stringcmp(char s1[ ], char s2[ ])
{
int i, k, diff;
for (i=0, k =0; s1[i]!= ‘\0’ ; i++, k++)
if(s1[i] != s2[k] ) break;
diff =s1[i] – s2[k];if (diff == 0)
printf (“\n strings are equal”);else
printf (“\n strings are not equal”);
}
v) String reverse, without using built-in functions.
void stringrev (char s1[ ], char s2[ ])
{
int i, k;
for (i=0; s1[i]! = ‘\0’; i++);
for (k=0, i=i-1; i>=0; k++, i--)s2[k] = s1[i];
s2[k] =’\0’;
printf (“\n reverse of string %s is %s”, s1, s2);
}

Pradeep B M, Assistant professor, Dept of CE, MITM. Page 26