Data Structures Through C-Yashavant Kanetkar (1).pdf

Data Structures
Through

pha Kancthar BPB PUBLICATIONS
4 — _

Contents
Ineroduction

1 Before We Begin
Analysis of Algorithms

3 Amays

4 Strings

Linked Lists

6 Sparse Matrices

7 Stacks
8 Queues
9 Trees

10 Searching And Sorting

11 Graphs

Index

vi

611

643

Introduction

yehnical book writing is a simple job. Pick up a technology that
appeals you, spend some time understanding it, browse the ret for
do mor «öitional information and then keep writing til the time you
do not reach the end. Easier said than done! I

farther from the truth. For one,
confusing with so many comp
strides in the recent years. Sec
master in a few months
understood in a simple mar

in fact nothing can be
choosing the technology is pretty
uting technologies taking so big
‘ondly, none of them is so easy to
and thirdly presenting what you have
inner is not everybody's cup of tea,

I have realized all these facts

more emphatically while writing this
book, because I have beer

n writing this book for last 10 years!! It

th attempting to write articles that would explain
ılgorithm and Threaded Binary Trees. Once 1 had a
Critical mass of written material 1 thought of compiling it in the
form of a book. I however wanted the book to be a different data
structures book. Different in the sense that it should go beyond
merely explaining how stacks, queues and linked lists work. 1
Wanted the readers to experience sorting of an array, traversing of
a doubly linked list, construction of a binary tree, etc. | had a hell
of a time imagining, understanding and programming these
complicated data structures. 1 wanted that the readers of this book
should not be required to undergo that agony. And today | am
satisfied that I have been able to achieve this through the CD that
comes with this book. It lets the reader experience the working of
different data structures through carefully prepared animations. 1
have pinned my hopes that the readers would appreciate this
approach,

Quick Sort al

1 have tried to make this book different in one more way. Instead
of merely learning how to perform different operations on a linked
list, I think one can appreciate it better if one comes to the
practical applications of it. There are numerous such examples and

vii

emos of them on the

structures with
t the end of

viii

CHAPTER
ONE

Before We Begin

Well begun is half done

Through ©

e in working
in this book
To type any
Once the
machine

mm called Compiler.
Development

well as the

other prog!
Integrate
Editor as

Compiler
Environment (
Compil.
able in the market targeted
es ‘example, Turbo C and
a hat work under MS-DOS;
jon are

2008 Express Edit
whereas gcc compiler

Turbo C+ A
Visual Studio 2008 an
mpilers that work under Windows, mpl
the comple E tat Tue CT Wi a
et M le be al on ashe? running Windows OS.
edition and gce compilers
+ these, Visual Studio 2008 Express Edition and gcc compi
de ple free of cost. They can be downloaded from the
following sites
pps microsof com s/download
‚gwin.com
bove foi

fntpeivwewe
compilers mentioned al
sh to know my personal
two

Land

You are ny of the €
compiling programs in tis book. Ifyou Wi
Maire, I would prefer Visual Studio Express Edition for
Simple reasons— It is a modern compiler with easy to use GI
à is available free of cost

to use

To help you go through the installation process of Visual Studio
Express Édition smoothly I have also recorded a video. You can
teh the same at the following link:

= — per

Thapier 1: Before We Begin

Detailed Compilation Steps

The compilation process with each of the compilers mentioned in
s section is a bit different. So for your benefit | am
ps with,

the previo
giving below the detailed compilation and execution ste

each of these e

Compilation Using TC / TC++
that you need to follow to compile and execute

Here are the steps

(a) Start the compiler
usually present in CATO\BIN directory

(b) Select New from the File menu.

(©) Type the program.

(4) Save the
Programl.c)
(6) Use Ctrl + F9 to compile and execute the program.

(D Use Alt +5 to view the output,

A word of e
compiler, you may get an error — “The
To get rid of this error, pet

have a prototype”.
steps and then recompile the program:

ns using TC/TC
at C prompt. The compiler (TC-EXE) is

program using F2 under a proper name

(sy

autiont If you run this program in Turbo GE
function printf should
form the following

——————

jpier 1: Before We Begin

mount D CATurbo\TC

u an
ho Select “option” ME N'a pops YP
D Sehen. Inthe dialog Pen tha PO j
phone e+e Compiler oF ei
sleet “Environment El
A ore spony and eS IC het au
© Aloe: Make sure that te “default ex a
CPP js very simple CE Turbo C++ software. This would bring up De
fowever, if you ins Wr
es very small. So smal s
indo y work ith small ness Me Si ST
you can hardly We! Von en be
screen. For (© Go to the Options Menu (Alt O), select ‘Directories ete

‘upy the entire glo
Jator called DosBox fro 8 wo N nd change the include’ and Library directory such that

they contain the following entries

Window to occ!
download an x86 emul

XATOUNCLUDE
é ci
Once you have downloaded this emulator carry out the Following XATOLB
steps: (@ Once you have typed and saved program do nel compile it
. dome ung the usual Cu F9. Instead, compile it using Ihe Compile
de) Install he DosBox software (hat You have download using the ute it using Run Mena.
create a folder called Turbo on your C: drive.
(b) Create a folder called Turbo 0139 he following are the shorteut keys that can be used while working
tae In Turbo © / Turbo C++ environment. If you use them it will
© Cony ke Türke GA Turbo CH software D this Turbo e Jour prod
der.
2 — Press Alt+ FAN to open anew file
a al Press F2 to save the current file
(4) Start DosBox by double clicking DosBox icon. _ Press Ctrl + F9 to compile and run the program
| - Press Alt-+ FS to view the output of the prog
(e) You would be presented with two screens. You need to use = Press ‘Ait + F3 to close the currently opened ile
the one which has a Z> prompt in it. Type the following _ Press Alt + X to exit Turbo €
command at Z> prompt. È
mount X CiTurbo

Chapter Te Before We Begin I

You can delete his ode and type your program in its place. you
now compile the program using Ctrl FS you would get the

Using Visual $
following error

Compilation fi

ato 2008 Express Edil

and execute programs
Fatal eror C1010:
Forpected end cf fle while looking for precompled header.

Did you forget to add ‘include "stdafch" to your source?

to compile
owing steps
any an te Soni SE

ny Visual Microsoft
«| All Programs

al Sucio 2008 fom Sal AICTE” 2008 Express

08. or start Visual +

SI Programs If you add finclude “stdafich” at the top of your program then it

would compile and run successfully. However, including this file

makes the program Visual Studio-centric and would not get

TC++ and gee compilers. This is not good as

(a) Stat Visu
Visual Studio 2
Edition from Start |

2008 Express Edition
compiled with TC

select Pr
lect File | New Project tion from de I

© ae z le [New Er ins? Console Applic nae ar the program no longer remains portable. To eliminate this error,

Pe at pops up. Give a proper BAN E the proje you need to make a setting in Visual Studio. To make this setting

alg th oF ran Thence on OK nd Finis Carry out the following eps j

from the File me ie

(a) Go to “Solution Explorer’

(©) Type the program
(b) Right click on the project name and select ‘Properties’ from
the menu that pops up. On doing so, a dialog shown in Figure

(&) Save the program using Ctrl + $.
te the program. 1.1 would appear.

(e) Use Ctrt+ ES to compile and execu

When you use Visual Studio to create a Win32 Console
Application fr the above program the wizard would insert Ihe

following code by default

include “idabh"
int main int argo, _TCHAR" a)

{
}

tum;

Figure

ay For te lt pane of is dno, fs sees Conf
Properties’ followed by "C/C++

(&) Select Precompiled Headers

click on ‘Create/Use

for this option

ight pane of the dial

(© From the ri
. On doing so in the value

Precompiled Header
a triangle would appear.

(6) Click on this triangle and a drop down list box would ap)

(g) From the list box select “Not using Precompiled Heade:

(h) Click on OK button to make the setting effective

W

re setting. By default
am and
tell it that

his, you need to make one n
believes that your program is a C++ Pr

ram. So by making a setting you need
program. Carry out

gram is a C program and not a C
make this setting:

your p
the following steps t

(a) Go to "Solution Explorer window

‚ht click on the pr ne Right click on the project
Properties’ from the menu that pops up. On
own in Figure 1.2 would appear

name and select

doing so, a dialo

g first select “Configuration

e) Fr
Properties’ fi

Figure 12
(a) In C/C++ options select “Advanced.

Lo | 10

o Compile as © code

sion 10
(e) Change the compile As 0?
= ee e
cnc his sti i made D he ged 8
De This time no EO Ny
ca compile and nit
tion Using gee
nai lle and execute programs
Camy out the following steps 19 compi
using gee
tay edie ev i FSS and

à) Type the poem a
O ner name Program!

switch o the directory containing

(b) At the command prom

‘Program.’ using the ed command.

(e) Now compile the program using the gee compiler as shown
below:

# gcc Programt.c
(d) On successful compilation, gee produces a file named ‘a.out’.
This file contains the machine code of the program which can

now be executed

(e) Execute the program using the following command.

# aoû

Chapter T: Before We Begin OM

(9 Now you should be able to see the output of Program 1 on the

A Word Of Caution

All

programs given in the chapters to follow have been created
sning that you have installed Visual Studio on your machine. If
have installed TC / TC++, then you would be required to

make some minor changes pertaining to clearing of screen and

positioning of cursor. Let me show this to you using a simple

to

ram that first clears the screen then positions the cursor at 10°
w. 20” column and prints a message at this location. If we were
TC++, the program would look like this...

use TC

include <stdio.h>
include <conio n>
int main)

}

cise); clear existing contents on screen *!
gotoxy (20, 10): /* position cursor I
print ("Helo");

A similar program in Visual Studio would take the following form:

#include <stdio.h>
include <system n>
void gotoxy ( short int col, short int row ) :

int main( )

‘ system (dls); lear existing contents on screen
got (20, 10); /* posiion cusor
printf (“Hello”)

mon )
Li gotony (stor nt col shor Tur, HANDLE

sn
y HANDI LE nsidout: «gerssaande (

Don ct)

Tears

a compiler ten you will
0

so ae te aro

CHAPTER
TWO

Analysis Of Algorithms

Justifying The Means

ot every time is the dictum “ends justify the means”

correct, more so in Computer Science. Just because we got

the right answer (end) does not mean that the method

(means) that we employed to obtain it is correct. In fact the

efficiency of oblaining the correct answer is largely dependent on

the method employed to obtain it. And at times getting a comect
solution late is as bad as getting a wrong solution.

13

=]

algorithm. More
ate that act on
finite number of

The meth isa 5

ne, je ou hs
some it en ut VE À A
steps. An ee
st re
— Am algorithm M pá
externally. ore
1) Output An alge mu oo
( |
e algori
result. vo mares what the Les Soe ee,
(e) Finiteness—No mer. number OF NP series of steps
terminate fet a pp perforin
rocedure which 8065 On
eine mes n the sori
The steps 10

(4) Definiteness — as

must be clear and unam! fom the steps in the

e able 10 perfo ne
es intelligence. For example, the
any ich form a Pythogorian

(e) Effectiveness — One must
algorithm without applying
step—Select three numbers W
triplet—is not effective,

es—Iterative
All algorithms basically fall under wo teva ei ase E
(repetitive) algorithms and Recursive algorithms. UE
algorithms typically use loops and conditional statements. AS
against this, the Recursive algorithms use a ‘divide and conquer
strategy. As per this strategy the Recursive algorithm breaks down
a large problem into small pieces and then applies the algorithm to
cach of these small pieces. This often makes the recursive
algorithm small, straightforward, and simple to understand.

Why Analyze Algorithms

‘An algorithm must not only be able to solve the problem at hand, it
must be able to do so in as efficient a manner as possible. There

Chapter 2: Analysis Of Algorithms W

ight be different ways (algorithms) in which we can solve a
given problem. The characteristics of each algorithm will
determine how efficiently each will operate. Determining which
algorithm is efficient than the other involves analysis of
algorithms.

While analyzing an algorithm time required to execute it js
determined. This time is not in terms of number of seconds or any
such time unit. Instead it represents the number of operations that
are carried out while executing the algorithm. Time units are not
useful since while analyzing algorithms our main concern is the
relative efficiency of the different algorithms. Do also note that an
algorithm cannot be termed as better because it takes less time
units or worse because it takes more time units to execute. À worse
algorithm may take less time units to execute if we move it to a
faster computer, or use a more efficient language. Hence while
comparing two algorithms it is assumed that all other things like
speed of the computer and the language used are same for both the
algorithms.

Note that while analyzing the algorithm we would not be =
interested in the actual number of operations done for some
specific size of input data. Instead, we would try to build an
equation that relates the number of operations that a particular
algorithm does to the size of the input. Once the equations for two.
algorithms are formed we can then compare the two algorithms by
comparing that rate at which their equations grow. This growth
rate is critical since there are situations where one algorithm needs

Through ©
io
combining this information
km unis infor
pe sion e Ma are sizes we then need
ae E ye sale Fi si. This recurrence
a alt Fae the M fo n
re on PE closed form hee dan ES
lation can then
pared wi her
What Is Analysis
i ie that gives us a
Te are ster agar "ill take for solving a
de ance of wo algorithms we
blem using each

general idea of how
ing the

i jo solve a pro

mple, we might

problem. For compart
have to estimate the time

for a set of input values For example,

comparison a searching algorithm does

or we might determine the

algorithm
sto add two matrices of

determine the number

to search a value in a list of N values,
ser oF arithmetic operations it perform:
size N*N.

‘Assad are, a number of algoritmo might be able 10 solve a
problem successful. Analysis of algorithms gives us the
of reason to determine whickalgortim should be chosen to
solve the problem. For example consider the following two
algorithms to find the biggest of four value

Algorithm One:

bg=a
(b> ba)
=b

endif
#(c>bg)
big=c

Chapter 2: igo
ıpter 2: Analysis Of Algorithms

#(b>c)
#(b>4)
retum b

retum d

needs © js not significant if
may be with other
ne. "a record may

the num!
of the algorit
efficiently

that helps us

What Analysis

. ter cycles a particular
ho ht algorithm because t invol 7

algorithm will
information to cho
of variables like:

ose the fi

Type of computer
Instruction set used by t!
What optimization compile

Microprocessor
x performs on the exe

«cutable code,

No doubt that all these factors have 3 direct bearing on how fast a
ram for an algorithm wil run. However, if desde to tke them
PE sideration we might end up with a situation where by
moving a program to a faster computer, the algorithm would
become better because it now completes its job faster. That paints
‘rong picture. Hence the analysis of algorithms should be done
‚ardless of the computer on which the program that implements
rithm is going to get executed.

the al

What To Count And Consider

An algorithm may consist of several operations and it may not be
possible to count every one of them as a function of N, the number
of inputs. The difference between an algorithm that does N+S
operations and one that does N+250 operations becomes
meaningless as N gets very larg:

For example, suppose we have an algorithm that counts the
je. An algorithm for that might look

number of characters in a
like the following

Count = 0
While there are more characters in the fie do
Increment Count by 1
Get the next character
End while
Print Count

If there are 500 characters present in the file we need to initialize
Count once, check the condition 500 + 1 times (the +1 is for the
last check when the file is empty), and increment the counter 500
times. The total number of operations is:

Initializations — 1

Increments ~ 500

Conditional checks — 500 + 1

Printing — |

As can be seen from the above numbers the number of increments
and conditional checks are far too many as compared to number of
initialization and printing operations. The number of initialization
and printing operations would remain same for a file of any size
and they become a much smaller percentage of the total as the file
size increases, For a large file the number of initialization and
printing operations would be insignificant as compared to the

azz

ES

JE

number of inte de values in
pts of Te op hile analyzing an
ingles as the nu count while analy

me desde wit? qe significant operation

important 10 KR which is tne ed, we should
n. We oth. ON Caral to the algorithm
in the e operations ar Ves, There are two
: Sen for the significant

seks, Thus, while doing
| chee jalization becomes

algorith

prison or arithmetie
en 4 sorting algorithms the important
For example, in Seti oro values. While searching
Bor exam ye compan F0 VE one we are

re 10 check if th lone to see
the compac Be ar the comparison is done t
looking for, whereas Y

f order. Comparison
z compared are out 0! ‘ :
au en e equal, less than, greater than, loss
operations include equal,
than orequal and greater than or equal.

s fall under two groups—additive and

Th ai eos melde ation, subtraction,

increment, and decrement. Multiplicative operators include

multiplication, division, and modulus. These two groups are

counted separately because multiplication operations take longer
time to execute than additions.

Cases To Consider During Analysis

Choosing the input to consider when analyzing an algorithm can
have a significant impact on how an algorithm will perform. For
example, ifthe input list is already sorted, some sorting algorithms
will perform very well, but other soning algorithms may perform

very poorly. The opposite may be true if the list is randomly

arranged instead of sorted. Hence multiple input sets must. be

Chapter

Anis OF Agari

Mz

(a) Best Case Input

considered while analyzing an algorithm, These include the
followi

This represents the input set that allows an
algorithm to perform most quickly. With this input the
algorithm takes shortest time to execute, as it causes the
algorithms to do the least amount of work. For example, for a
searching algorithm the best case would be if the value we are
searching for is found in the first location that the search.
algorithm checks. As a result, this algorithm would need only
one comparison irrespective of the complexity of the
algorithm. No matter how large is the input, searching in a
best case will result in a constant time of 1. Since the best
case for an algorithm would usually be very small and
frequently constant value, a best case analysis is often not
done.

(b) Worst Case Input — This represents the input set that allows an

algorithm to perform most slowly. Worst case is an important
analysis because it gives us an idea of the most time an
algorithm will ever take. Worst case analysis requires that we
identify the input values that cause an algorithm to do the
most work. For example, for a searching algorithm, the worst
case is one where the value is in the last place we check or is
not in the list. This could involve comparing the key to each
list value for a total of N comparisons.

(€) Average Case Input — This represents the input set that allows.

an algorithm to deliver an average performance. Doing
Average-case analysis is a four-step process. These steps are
as under:

(i) Determine the number of different groups into which all
possible input sets can be divided.

(ii) Determine the probability that the input will come from
‚each of these groups.

cares Through
nes Through

cun for each of these

will L
n will ig take the same

group group must be split

ula
formo
the

a
where
ne
Rates Of Growth
ne sine ai i ea of al

operations performed by the algorithm,

the size of the
operations as the sin rae
ange, Tris is oñen alkd Me Tae h
nori, What happens with small eS of input data is not as

resting as what happens when the dats sel BES large

es that is of more
blem increases U
ï e of growth of the

Table 1-1 shows rate of growth for some of the common classes of
algorithms for a wide range of input sizes. You can observe that
there isn't significant difference in values when the input is
Small, but once the input value gets large, there are big differences.
Hence while doing analysis of algorithm we must consider what
happens when the size of the input is large, because small input

sets can hide rather dramatic differences.

Chapter 2

Analysis Of Algorithms

n | ge | ntoga| » w Y
1] ol oo! vol

10[ _20| 40! i

33 | 100.0 | 10240
20| 43 s[_so00 | 80000! 10485760 |

Table 2.4. Rate of increase in common algorithm classes.

The data in Table 2-1 also illustrate that the faster growing
functions increase at such a rate that they quickly dominate the

slower-growing functions. Thus, ifthe algorithm's complexity is a

combination of a two of these classes, we can safely ignore the

Slower growing terms. On discarding these terms we are left with
Sa se call the order of the function or related algorithm. Based
on their order algorithms can be grouped into three categories;

(a) Algorithms that grow at least as fast as some function
(b) Algorithms that grow at the same rate
(©) Algorithms that grow no faster

The categories (a), (b), (©) mentioned above are commonly known

as Big Omega Cf), Big Oh O (f) and Big Thew D (os
respectively.

Or these, the Big Omega category of functions is not of much
interest to us since for all values of

a greater than some threshold

ctr TIPO

nat are at least ag
yes E y as fast as for
gr

for an algorith
‚okout for im
the loon ¡dering. Since big

come grow at the same

ons M rest tO US.

Kane cof inte

ctions that grow
es of greater than
alues that are

cet val
El foral y
ns that o) have

as in OCT) M upper bound, so

fer than f. This means
> m (where € is a

be of interest 10 us. While
0 know if the function
big oh of the second. If
no better than the first

ons woul
ve will an

e first is in

considering

categorizing

So, we know hat he se
ie problem.

f Sequential Search Algorithm
dim is the simplest searching
¡cient but

Analysis O)

The Sequential Search Algor a
algorithm. We wil seta this leet is not very e
will successfully search in any is.

ihm the aim is to look through a list to find
le doing a

In any searching alori [
à particular element. Although not required, whi
sequential search the lists considered to be unsorted.

Sequential search looks at elements, one at a time, from the first in
the list until a match is found. It retums the index of where the
value being searched is found, If the value is not found the

nn I

Chapter 3 Analysis OfAlgorihms ES

side the range of the list
are located in
alue -1 if the

algorithm returns an index value that is out
Of elements. Assuming that the elements of the list

ssitions 0 to N-1 in the list, we can retum 8 Y

po
list. The complete algorithm

Clement being searched is not in the
for sequential search in pseudo code form is given below. For the
sake of simplicity, we have assumed that there is no repetition of

values in the list

‘Sequentialsearch (ist, value
List the elements to be searched
value the value being searched for

N the number of elements in the list

W (value = ist
Retum
Endit
End for
Retum 0
Let us now analyze this algorithm

Worst Case Analysis

There are two worst cases for the sequential search algorithm:

The value being searched matches the last element in the list
The value being searched is not present in the list.
For both these cases we need to find out how many comparisons
are done. Since we have assumed all the elements in the list are
unique in both the cases N comparisons would be made.

Su —
à done for a search

Analysis
Average Case nes con ways successful
age par the ae being searched will

ist, it ean be pres
lities are e
ation.

os not be Foun.
= inthe I
e possibil

tial lo

pipe value begin search:
F the N places. 9 ee
any one of th ND IN for

et jue being searched is

id be 1, 2, 3 and so
le is the same
the following

ade
«of comparisons made 1.
mo nd, third location,
2 the numbe

mate

The numb
found at frst
on. This means tha
as the location where the
for this average Case:

er of cor
h occurs. Thi

equation

Let us now consider the possibility that the value being searched is

not present in the list. Now there are N+1 possibilities. For the
case where the value being searched is not in the list there will be
N comparisons. If we assume that all N+1 possibilities are equally
likely, we get the following equation for this average case:

hapier 2

DT 1

We can observe that by including the possibility of the target not
being in the list only increases the average case by Ys. When we
consider this amount relative to the size of the list, which could be
very large, this % is not significant.

ETA

Chapter 2: Analysis Of Al

ene the other is > ba

pxersise a a
has 4 ng algorithm, 16] ghest to lowest order. If any
Speci ame order, circle them on your list
2 log logn Prix
Le n nlogn
log n yn 6
at n Gay
de ta om o. ail statements in the 7) For each of e falling par f functions I) and in), eher
= the fee Kn) = Ofg(a)] or g(n) = Off{n)}, but not both. Determine whic!
ñ De oe A) Oi E {n)], but not both. Determine which
o lel 2
Wir à wilei <= n do (a) fn) = (n?- n)2, a(n) = ón
3 forkeltojdo 3 begin A
3 | eek (>) fn) = n +2Vn, g(n) =n"
5 isitl;
Ged (©) fin) =n +n logn, gn)= nn
(d) fn) =n? +3n + 4, gn)= n°

[4] Compare the two functions nf and 2" /4 for various values for n,
Determine when te second becomes larger than the first. 4
‘ (e) fin) =n logan, g(a) =nyn 2

=n+logn, gin)= Vn

(0 fn)

{5] Which function grows faster?

ra |

CHAPTER
THREE

Arrays

Friends Are Friends

rray is one data structure that has been used (as well as
A abused) more than: other. | a

Trough

catogories—líncar and
yo amo US elements form
ino ii

abe linet ture do not form a
ear data structures
ship between the

e sio
ac rela i
arf locations. Such line

lonship between the
links. Such linear
.4 list each node
jure 3-1(a)
fan array and a linked

and Figure 3-10)

Data Pointerto next node

| node node Enode [Node

Figure 3-4(b). A linked ist containing 4 inlegers.

ka Fa bal! when the number of elements to be stored is
fe ue A \raverse, search and sort, On the other hand
nus When the number of data items in the

© likely lo vary. Linked lists are difficult to maintain

Chapter 3: Arrays E: 7

as compared to an array. We would discuss linked lists in more
detail in Chapter 4

What Are Arrays?

An An

y is a finite

collection of similar elements stored in
adjacent memory locations. By ‘finite’ we mean that there
specific number of elements in an array and by “similar” we m
that all the elements in an array are of the same type. For example.

array may contain all integers or all characters but not both.
However, there can be array of structures, where each structure
may contain an integer and a character.

ning n number of elements is referenced using an

from 0 to m - 1. For example, the elements of an
array arr|n} containing n elements are denoted by arr[0), arr(t},

arr[2]. ... arr[n-1], where 0 is the lower bound and n - 1 is the
upper bound of the array. In general, the lowest index of an array
is called its lower bound and the highest index is called its upper
bound. The number of elements in the array is called its range.
No matter how big an array is, its elements are always stored in
contiguous memory locations.

index that vari

Intuitively, an array is a set of pairs of an index and a value. For
each index there is a value associated with it. This arrangement of
array elements is shown in Figure 3-2.

oy att) af a al) as
ui 1 SB

Figure 3-2. Elements in an array with their indices.

LE!

pe

al array and a
ray can be a 2-D
Hay isa 1-D array or

imension

the array. The
mensional as well

55 25 ‘elements:

yg Seles columns holding 10
arrilS) qa 2 rows
ue p arrays cach of which is

0 as thus holding totally

arrasa, à À

Array Operations .
be performed on an array
ae are several operations DL can

These operations

[ravenal | procesos
| search | Unie: the locaton of an element wil
| Insertion | Adding a new element 10 an array

| Deition | Removing an element rom an aay

| Sorting | Organizing the elements in some order
Merging | Combining two arays into a single array

‘ach element in the array
ith a given

Reversing | Reversing the elements of an array
|

Table 3-1. Operations performed on arrays.

Chapter 3: Arrays

APO

Let us now see
now see a program tha shows how to perform these

include <stdio.h>
include <conio.h>
Hinclude <windows >

fidefine MAX 5

void insert (int
void del (int,
void reverse
void display

pos, int num )
pos

void search (int *, int num )
int main

nt anf}

system ("cs")

insert (ar, 1,11)
insert (ar, 2, 12);
insert (ar, 3, 13):
insert (art, 4, 14);
insert (ar, §, 15);

print (“Elements of Array):
display (arr):

del(am,5);

del (an, 2):

print ("Afer deletion");
display (am);

insert (amr, 2, 222):
insert (arr, 5,585);

5 Through ©

Chapter 3: Arrays M=
anf] = amMAX- 1-1
a aa
)

searches array for a given element num */
void search (int "ar, int num )

Pf Traverse the array */
inti;
for (i=0;1<MAX; i++)

if( nf] = num)

printf ("The element %d is present at %dth position \nin”, num,
ist);
i retum |
}

}

nr it (i== MAX)
lets an cerf be gien POSE os $ printf ("The element %d is not present in the array ww", num);
void del {int ‘ar, intpos) $

{

displays the contents of a array ‘|
void display (int*arr)

ini;
for (i= 0;1<MAK/2; 64)
samp = af]; fe

vie WE

re rame)
Chapter 3: Arrays

The del( ) function deletes the element present at the given
0, we have shifted the numbers placed

position pos. While doin,
after the position from where the number is to be deleted, one
ositions. The place that is vacant

place to the left of their existi
deletion of an clement is filled with 0. The deletion of an

ustrated in Figure 3-

af
element has been ill

which contains 5 ints
Lam we created an N “assed to functions like Ree ar
In his Pema ies of hs A nd search) to perform Le a =
Then te Bie rer Before Deleting After Deleting
insert( ). delt 2 he array:
on thea
fret operation ©
diff no arguments, the position pos at Figure 3-4. Shifting of elements to the left while deleting 2°
The insert) funcion ales NT and the number num that element of an array.
which the new ruber has ob first through a loop, we have
DRAN n, one place to the E
In reverse( ) function, we have reversed the entire array by
swapping the elements, like arr{0] with arr[4}, arr[1] with arr[3]
and so on. The process of reversing is illustrated in Figure 3-5.

has tobe inserted. In cie posíto
shied the numbers, rom e Ser Pd the number
oftheir existing position. Then we ook has Bee
tr u the vacant place. The insertion of an element has been
illustrated in Figure 33.
[ | [ee a)
are] 2
ITeT«ToTo]| (AS [eT 0) j 11 [222] 13 [14 [555] | | [sss] 14 Las [222] 14
[9202 3200 on 2324 CRE 6 175, Aiea
| Before Shitting ‘ier Shining N Bofore Exchanging ‘After Exchanging
: Figure 3-5. Swapping of elements while reversing an array.
Figure 33. fens a aa the right while inserting an
Note that swapping should continue for MAX / 2 times only,
irrespective of whether MAX is even or odd, However, if by

es the
MAX times the array
ints would OCCUpy

done for NE
sis done. ¡mel
elements y, the € :
of mene ull more swapping. |

as a resul cod b in

mistake he ed ere P

a ete ch oi :
the same PIE TY wo rie specified number
ater words the genre) Ot pared with the given

n combi. be same then

de e 0 om PT ich the number is found,

Te runt ie 0 men O
peon displays jed out not found then the
the fun eh

Oitberwise, he cod
usted or a match E nt mess

function displays the =

ction, th
y ply) tio
In ei aon

Of Two Arrays

ee ys doing the array that are to

Temenis of both the arrays to a
Snow see a program that

third array

ves two ste
he sorted el

order. Let u
into a H

arrays invol
and adding t
in a sorted
ging of two array

Merging of
be mere
demonstrates me

include <stdio n>
include <conio.h>
include <maloc.h>
include <windows >

‘define MAX 5
define MAX27
tar

int create (int)
void sort (int. int)
void display (int *, int);

MERS Em mi

Chapter 3: Arrays

in merge (int, int
int main( ) )
{
int a, *b, e
system ("cs")

print ( "Enter elements for frst array )
a= create (MAXI)

printf ("Enter elements for second arrayinin")
b= create ( MAX2 )

sort (a, MAXI
sort (b, M

print ("Fest aan )
display (a, MAXI)
print ("Second arrayin")
display (b, MAX2)
print! (“After Mergingin')

c= merge (a,b);
display ( c, MAXI + MAX2) ;

retum 0

}

I" creates array of given size, dynamically *
int’ create ( int size )
{

int ‘arr i;
int*) malloc (sizeof (int) * size);

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

print (“Enter the element no. Se: *,i+ 1);
scant ( "Sed", ar);

Through E

Thapar 5 Arrays

Romar

)

ar = (int) malloc (sizeof (int) * (size)
for(k=0,]=0,1=0;1<=size; i++)

# (al < bol)
{

) ace
E oct anf] = alk)
; if( >= MAXI
int te ge: it) :
Deimos 1esoe for (t+ |< MAX jos, i++)

Cia den
€ sorgo) a
{
Long 25
so anf = bi
ar= er itt
y #(j>= MAC)
4 {
) ) for (t+ ik MAXI k++, i++)
} anf] a
‘ }
1 splays the contents of aay‘! )
void display (in “ar, int size) }
\ inti, retum ar;
for(i=0;/ se 4) )
pr (“et arf);
prod) Output:
}
merges two arys ol feet size Enter elements for first array.
int merge (t'a no) E
{ Enter the element no. 1: 67
nta; Enter the element no.
ini bj; Enter the element no.
ink ie = MAXI + MAX2; Enter the element no.

es Through &

a 6 7g 10 12 19

122
43 67
functions that are used to
«program we have defined some “ 1
In this progam Be ans on arays. The función
eae ts, function sort( ) is used

rd to create an array of int |
“fan amıy in ascending order, function

dd elements of two arrays Lo the new array
) is used to display the contents of an

create ) is ust
to sort the elements

merge( ) is used o a
and lastly function display(

array

All the arrays used here are created dynamically because the size
of the each array is different from the other. Wuen the size of the
array is not known while declaring it then initially we declare a
pointer. To actually create the array of desired size we have passed
either MAXI or MAX2 to the ereate( ) function. The array is then

created dynamically using the function malloe( ). Finally, the base

address ofthe array is stored in the pointer,

Chapter A E

Inside the function merge( ), a for loop is executed for size
number of times. Here, size fs the sum ofthe numberof elements
present in the arrays that are pointed by a and b respectively
Before placing the elemen inthe new any are thf poined by
we have sequentially compared the elements of two arrays which
are pointed by a and b respectively. The element that is found 10
be smaller is added first to the array that is pointed by arr. Thus,
for example, if afk} is smaller than b{j] then afk] would get copied
to arrli] and k would get incremented by 1. The element bij}
would then get compared with the new element afk}. While
comparing if any of the two arrays gets exhausted, then the
remaining elements of the other array would get copied to the
array that is pointed by arr.

on, the program would ask to enter 5 integers for the

On executi
ers for the array pointed by b.

array pointed by a and 7 inte

Two-Dimensional Arrays

À 2-dimensional array is a collection of elements placed in m rows
‘and n columns, The syntax used to declare a 2-D array includes
two subscripts, of which one specifies the number of rows and the
other specifies the number of columns of an array. These to
subscripts are used to reference an element in an array. Fi
example, arr[3][4] is a 2-D array containing 3 rows and 4 columns
and arr{0}{2} is an element placed at 0% row and 2™ column in the
array. The two-dimensional array is also called a matrix. The
pictorial representation of a matrix is shown in Figure 3-6.

‘or

je rrangement
Row Major And Colama Major Arrang

only a matter of imagination,

x gets str yy all elements of it are stored

hey = parts ‘memory can only be viewed as

consecutive units of memory. This leads to two possible

arrangements of elements in memory-Row Major arrangement

an Major erangenent. Figure 3-7 ilustrates these tg

possible arrangements fra 2-D array.

are
ows and columns of a mat
Rows and columas ola mor

Chapter 3: Arrays

int a(3}04) = {
(12, 1,-9,23)
(14,7, 11, 121) |
(6,78, 15,34}
)

pare”
[— 0° ow —J— 1" rom —}-— 2 row a

— y
GzLı 2314] 7 [Jal 6 [78 l9s [3
| “502 508 510 514 518 522 526 530 534 508 542 546

| Column Major Arrangement

pentes |
Raja Te Te 9] 14 | 15] 23 Ja] 34]
| 502 506 510 514 518 522 526 530 534 538 542 546

Note: Each integer occupies two-bytes

Figure 3-7. Possible arrangements of 2-D array.

Since the array elements are stored in adjacent memory locations
Wwe can access any element of the array once we know the base
address (starting address) of the array and number of rows and
columns present in the array.

For example, if the base address of the array shown in Figure 3-7
is 502 and we wish to refer the element 121, then the calculation
involved would be as follows:

sion of 121 Would be

ie adress of element ati)

ation of 121 would be

the address of element afi]
on on Pot hat C language permits
eras, Pascal uses a Column

In general fora "
would be Base address * }
aly a Row Major arangement
Major arrangement

Common Matrix Operations

Common “marc prions we sddiion, | multiplications
transposition, evaluation ofthe determinant oFa square matrix, ele
The following program demanstes these different matrix
operations.

include <sidioh>
include <conio >
iude <windows >

void create (int (393)) ;

Chapter 3: Arrays

TRE

void display (int (161)

void matadd (int E), nt (31, nt (318)
void matmul (int (3168), int (I), int (3131)
void transpose {int (3), int IS) :

18), ma23J8), ma9(38), mat4[3]S], matS{3}S} +

system ("os"

print (“Enter elements for fist amayı\n\n");
create ( matt )

Enter elements for second array");

p
create ( mat2 )

print (“First Array");
display (mat!)

print ("Second Arrayán")
display ( mat2 )

matadd (matt, mat2, maß);
print! (“After Addition")
display (maß);

matmul (matt, mat2, mal4 )
print! ( “After Multiplication:\n"
display (maté ):

transpose ( matt, ma ) ;
print ("Transpose of first mation");
display (mal

retum 0;

}
1 creates matrix mat

DT ul

(
wii

aux)

„0 jew)
tor(i=0:1
fi gere”)

renter te OR
lo ‘ee anal)

Pie)
{

)
)
PT]
)
spy cones GA
vod spy (nt mat)
ni)
fo(i=0;1< MAXI)
{
forj=0;)< MAXI)
vind", ma):
pe");
)
}

adds two matrices mi andm2

:i-< MAK; t+)

fr(j=0:j<MAX; je)
P mög] = nf) + map,
} h

void mat (it tnt m3)

med ro

)

I" multiples two matrices mi and m2 ‘1
void matmul (int mA, int mail, int maß]?

inti,j.k
for (k=O; k<MAX; ket)

for (1=0;1< MAK; i++)

map = 0
for(j=0;] <MAX:j++)
en += mil" mau

}
}

I obtains transpose of matrix mt */
void transpose (int m {33} int m2IB1)

inti, j
for (i= 0;1< MAX; i+)

for (j= 0;] < MAX; j++)
magia) mon;
y

)

Output:

Enter elements for first array:

Zu:

AA

Chapter 3: Arrays

In this program we have defined some functions that perform
different matrix operations like addition, multiplication,
n, etc. The function create( ) is used to create an array
lements of the

transpositi
of ints. The display( ) function displays the el

The function matadd( ) adds the elements of two matrices matl
res the result in the third matrix mat3. Similarly

and mat2 and st
atl

the function matmul( ) multiplies the elements of matrix m:
with the elements of matrix mat2 and stores the result in matá.

n transpose( ), transposes a matrix. A transpose of a
changing the rows with corresponding
matrix. The transposed matrix is stored in

The functic
matrix is obtained by

columns of a giv

mat!

More Matrix Operations

In addition to matrix operations that we discussed in previous
program there are some more operations that can be performed on
a matrix. These operations include calculating the determinant
value for a given matrix, checking whether a matrix is a singular
matrix or an orthogonal matrix, etc. Let us see a program in which
we have implemented these operations, fora 3 x 3 matrix.

#include <stdio.h>
include <conio.h>
#include <math h>
#include <windows h>

#define MAX 3
void matrix (int (313) );

void create (int (81681);
void display (int FR]

geet) jen
ricos ai fo

0) ir
1 isdn)

ese in)

pit "Matix is not singular
d= isortho( mat)
(0)

pint "Matix othogonal in")

ese
prin ("Mabixs nt rhogoral nn");

retum 0
)

P indes the matrix mat wih O
void mats int ma)

Chapter Arrays SS

void create (int mat

ma KA, d)

tj
for(\=0;1< MAX: i++)

for (j= 0; |< MAX: j++

for (i= 0;1< MAX is

{

for (j= 0] < MAX; jr)

print ("Enter the element *)
scant (En)
mail =0

}

}
printf ("a")
}

Pr displays the contents of matrix
void display (int mat{3}(3} )

inti,

7

sum = sum + (matüjf]* (matitll”
ma mat"
matin)" P

)

ven matri is an ortogonal matrix"

ot mL mí

transpose (mat. mt )

P multiply the matrix with is transpose
matmul ( mat, ml, m2)

P check for the identity matrix *
for (i=0 ;1<MAX; i++)

)

(200
conte

mat

Pins he deteminant value o
double determinant int

itijk |
double sum,
sum=00:j=1;k=MAK-f

for(i=0:1<MAX: i++)

p= pom (-10,i)

A= MAK 1 j

HET ITS
LT

Matrix is no snguat

Matias otogoral
functions create( ), display( ),
hich we discussed in previous
functions determinant( ) and

In this program, in addition to
matmul( ), and transpose( ) (W
program), there are two more

isortho().

The determinant() function calculates the determinant value for a

given matrix. Here, the matrix for which the determinant value has

to be calculated is a square matrix. A square matrix is the one in

which the number of rows is equal to the number of columns. We

Pat calculated the determinant value through a loop as shown.
low:

ln 1* iteration when i= 0:
p= pom 4,0);

mean 1

Chapter Arrays

sum = sum + (matOJO]*( mai) * mat)
Ina mat)
204(49(1"420°0))4

In 2% iteration when i= 1

p=pow(-1,1)

sum = sum + (mato) * ( maï{N0]* mat
JO): matif2)))"

y

In 3rd iteration when i =2:
p=pow(-1,2)
sum = sum + ( mat{O}2)*
matiz] * matí
=1+(0*(0*0-0*1)

* mat?
NP

A matrix is called singular if the determinant value of a matrix is
0. The determinant value for the matrix that we have keyed in is 1
hence it is not a singular matrix.

The isortho( ) function checks whether or not a given matrix is
orthogonal. A square matrix is said to be orthogonal, if the matrix
obtained by multiplying the matrix with its transpose is an identity
matrix. In other words, if A is a matrix and T is its transpose, then
matrix B obtained by multiplying A with T is called orthogonal if
it is an identity matrix. An identity matrix is a square matrix in
which the elements in the leading diagonal are 1.

Hence in isortho( ) function, first we have called transpose( )
function which stores the transpose of the given matrix, in mi.
Then we have called matmul( ) function to obtain the product of
the matrix and its transpose. The resultant matrix is stored in m2.
Then through a loop we have checked if the matrix m2 is an
identity matrix or not and retumed a suitable value.

a

cures Through es

Irre
aie)
inter® of floats,

pointer an am © 3

Ane ae afin oF inter variable always

ver, Sic would be nothing hae
BEE ne 5 Parables or. even the
collection SE ade a Tre ules that apply to an
e y Me pointers as well. Figure

tation of an array of

fo] Ca] os] bi] bis]

| m — — A 8128 8132

L
Figure 36). Memory representation of an array of pointers.

Multidimensional Arrays

A Siena! ay cn e hough of an ray olaa of
ot ‘igure 3-9 shows a 3-D array, which is a collection of
D arrays each containing 4 rows and 2 columns.

This array can be defined as:

b

"Figure 39. Representation 1830 array

ures Through er

soa Structures Through e

=.
Lie ae

each of which is a tg

«eee igs four one dimensional

D other words, a ong,

eh structed first. Then four

5 ca pe below the other ty

‘pur rows. Then, three

one behind the other 1

it the arrangement shown

pasaran 18-0 array

Figure 310, Meno

sa id ei, © perno ul a Rap Major STARE for
Ani dimensional ars. So te element 9 in the array shown in
Figure 3-10 can be accessed as follows:

The amay a can be defined as int al3J4)12) Element 9 is present
at af2J10)11) indicating that it is present in 0% row, 1“ column of
22D array. Hence address of 9 can be obtained as:
402+2*4*240*241=402+17
= 41
For any 3-D array alx]|y](2] the element afi}[j}{k] can be accessed
as Base address +i* y*z+j*z+k. 1

Chapter 3: Arrays — ©;
Arrays And Polynomials
Polynomials like SX* + 2: + 10X — 8 can be maintained.
using an amay. Arithmetic

operations like addition and
multiplication of polynomials are common and often we need to
write a program involving the:

e operations. If we want to write a
program that lets us perform these operations then we nes

to represent the polynomial. sent 4

The simplest way to represent a
polynomial of degree “n” is to store the coefficient of (n + 1) terms

f a polynomial in an array. To achieve this, each element of the
array should consist of two values, namely coefficient and
exponent. While maintaining the polynomial it is assumed that the
xponent of each successive term is less than that of the previous

m. Once we build an array to represent a polynomial, we can
use such an array to perform common polynomial operations like
addition and multiplication. The following program demonstrates
how we can store polynomials and add them.

finchude <stdio.h>
include <conio.h>
include <windows.h>
#define MAX 10
struct term,
int coeff ;
intexp;
b
struct poly

struct term t (10);
int noofterms ;

retum 0;

aa Structures Trough EN o
—_ Chapter 3: Arrays ES
64 J

vei inp
void poyanpend
sme "initializes elements of struct poly */
Soret ea
|
| inti;
pon i i > nooflerms =0;
Ta | for (i= 01 <MAX ie)
Sok f p>fcoef=0;
inipoly (801); ‘En
intpoly (892); à
inipoW (893);
7 adds the term of polynomial to the array t*/
void polyappend (struct poly“, int, inte)

p> tip > noofemms] coeff = ¢;
> ip > noohemslexp = e;
ee

SESES

ee

€ tures Thon

=

a —

(29) np)

printf ("a
}

rads wo pain
nt pol pora

inti
struct poly p9
intpo (93)

fr(iz0,j=0;1<0;p8nmetemst*)
(pere = 088 co == 0)
break
pt ep >= 92.10) )
ee)
3 3 rooms] coef =
papa noofems]erp = pf. exp ;

itt;
je

a
es
{
P3.4p3 noofems} coeff = pti. coeff ;
PS meters) exp =p exp;
ile
}
ee

A coef + p2 1 coat

TENER =

a — a

P3:(03 nooferme] coef = p20} coett

P3.1Ib3.noofterms) exp = pl exp

)

}
Output:

First polynomial
1x7 +256 43

544x445 x02

Second polynomial:
14143 + 1 02 + 1x +2

Resultant polynomial:
PT +2098 4345 +5244 1x3 460824 10 42

In this program, the structure poly contains another structure

clement of the type struct term. This structure stores the

coefficient and exponent of the term of a polynomial. The element

noofterms stores the total number of terms that a variable of the

type struct poly is supposed to hold. The function potyappend( )
adds the term of a polynomial to the array t. The function
polyadd( ) adds the polynomials represented by the two variables
pl and p2. The function display( ) displays the polynomial.

In main( ), we have called the function polyappend( ) several
times to build the two polynomials which are represented by the
variables pl and p2. Next, the function polyadd( ) is called by
passing three arguments pl and p2 which retums the addition of
polynomials pl and p2 which we are collecting in p3. In this
function, arrays representing the two polynomials are traversed.
While traversing, the polynomials are compared on a term-by-term

se E
i compared are equal

ne results stored in the third
nd te

al

a ist equal then the
sci rn ee Ms ar ce
sa et ped PO AL I
pe EXPO is added only one OF the two

in
othe third polynomial

mamial ave displayed using

polynomials then
asily, the teams of De resulting
the fanetion display)

f Poly! nomials

Multiplication O! .
gram tat caries OU! multiplication of two
Let us now see a PUE

polynomials.

include <stéio!”
include <conio.h
‘include <windows IP.

define MAX 10
struct term

net:
intexp;
»

struct poly
struct term 110);
4 intnooherns ;
vorpal pete
suc ply tt);
ep poh eta

Chapter 3 Arrays

set polyp (set
void display ( struct poly ) sate!)

int main( )

{
struct poly p1, p2, p3

system ("cls")

intpoly (891)
iitpoly( 292)
initpoly ( 8p3 )

polyappend ( 3p1, 1
polyappend ( 891.2.
polyappend (891.2
polyappend (391.2
polyappend ( 892, 2,3)
polyappend ( 8p2, 3,2)
polyappend (852, 4,1);

p= po (91,92):
print (“Fis pam");
display (pt):
prt (Seno pom)
display (92);
print ("Resultant polyno")
display (93);

4)
3)
2)
1)

retum 0;
}

‘initializes elements of struct poly“!
vol inital (struct pol "P)

ES

oc

en
port)
for (i=

A ds

ano

aay!"
ana
term of pve, int, in
ro (stc POY
PER
ers) Fr
resperns}eX *
yherms ) *

}
}

radiste

void polyappe!
>?
papa 100
(p> mo

} 4
ial equation

(displays be payor
1 papaya?)

20,1;
sa)

tomer ar pos PTE):

else
Cera pot):
fag=4;

}
}
Alta)

pint ("Bb *);
pent“);

eat pena a
sinus poly poled sn polyp, sac poly 92)

ae —NE

{

ti, j,c
struct poly p3
initpoly ( &p3 )
if (_p1.noofterms > p2.noofterms )

c= ptnoofterms
else

0= p2.noofterms
0,)=0:1<=c;p3nooftemst+)

= pa.ti.exp )

exp = p2fjep)

(p3.thp3.noofterms}.exp = pt.til.exp ;

or

else
'p3.tip3.noofterms], coeff = p1 ti coeff;
1p3.{p3.noofterms) exp = pt tl. exp :
Laat

}
}
else
.tp3.noofterms} coef = p2.ti.coef
ne pep:

ar

}
as

P3ip3.noofterms] coeff = p1.tf].coeff + p2.f].coeff

a

struct pay
intpoy (80);

aq pates)

Cata:

(150)
; p3=poladá (temp, p)
temp =p3 :

}
ese
temp =p;

}
}
um

Through
res Tiros

Chapter 3:

}

Output:

First polynomial:
AWM + DUB + 2 302 42x04

Second polynomial
294324410

Resultant polynomial
2x17 +7096 + 14 x45 + 1814 + 14 309 + B x°2

To carry out multiplication of two given polynomial equations, the
function polymul( ) is used. As done in previous program, here too
we have called polyappend( ) function several times to build the
two polynomials which are represented by the variables pl and p2.
Next the function polymul( ) is called by passing two arguments
pl and p2 which retums the multiplication of polynomials pt and

p2 and returns the resultant polynomial which we are collecting in
the third polynomial p3.

In polymul( ) function, first we have checked that whether the two
polynomials pl and p2 are non-empty. If they are not then the
control goes in a pair of for loop. Here each term of first
polynomial contained in pl is multiplied with every term of
second polynomial contained in p2. While doing so we have called
polyappend( ) to add the terms to p. The first resultant polynomial
equation is stored in temporary variable temp of the type struct
poly. There onwards the function polyadd( ) is called to add the
resulting polynomial equations.

Lastly, the terms of the resulting polynomial are displayed using
the function display(). = 8 ; :

Through,
Girictures Through &
Data

if its elements

y Finn bet ne
us à da ser À elements stored in
ee

P ‚lee! ions.
(0) an Are Da Ce acto ements varies forn

el
containing.»

na — 5
(a) A2-Dam) is also 6 rive for each of the following
oa
correct alte
{By Pick up the
: Y sesion

er 7
(a) To traverse an array nan army
(D Tome
delete i
a ay
(4) To combine two amays into à

ing refers 10
a) (D ining lement into an rs)
(2) Processing elements ofan array
(3) Combining two arrays into a single array
(4) Delting element rom an amay

(c) Sorting of an array refers to

* (1) Processing elements ofan array
(2) Deleting elements from an array y
(3) Both (1) and (2) Ae
(4) Organizing elements in an array in some order

Chapter 3: Arrays

| ME
IC] Write programs for the following:

(a) Write a program to find out the maximum and the second
maximum number from an array of integers.

(b) Write a program that accepts a number as input in English

language format such as One Twenty Three (for 123) and
prints the decimal form of it,

(©) The Mode of an array of numbers is the number m in the
array that is repeated most frequently. If more than one
number is repeated with equal maximal frequencies, there is
no mode. Write a program that accepts an array of numbers
and returns the mode or an indication that the mode does not
exist.

(4) Write a program to delete duplicate elements from an array of
20 integers.

(e) A square matrix is called symmetric if for all values ofi and j
ali] = aljllil. Write a program, which verifies whether a
given 5 x 5 matrix is symmetric, or not,

(N Build an array called chess to represent a chessboard and

write a function that would be capable of displaying position
of each coin on the chessboard.

(g) There are two arrays A and B. A contains 25 elements,

whereas, B contains 30 elements. Write a function to create an

array € that contains only those elements that are common to
Aand B.

A magic

Dana Str

ve aranged in increasing

wll

hs onder so D pow the terms Y
order.
poy Answer the followin
ent ee from à 4D

ic he
da) Find te bean e H xe address of th
day al ‘ite e array is
in for a banking system wil
i 5 ere

©] ere "310. Information 10 be Pe
sin rte count no., balance, status as

igh dep AS balance.

(c) Design a data pa sure for Income Tax department to hold
information for maximum 200. a Information to be
i oe pe EE tax amount, name,
ares, whether tx paid oc not for previous Year, group ag

ax 10. be paid. and

High/Low depending ‘on amount
category which would vary fom 11010.

uctures Through >

1
4

CHAPTER

FOUR

Strings

Appearances Are Misleadi
ıng

FR

ares TIRE
he

ode string
es
vital issues.

sored in an integer array, q
es > character array. AN array
js be Store aracter arrays are used by
fext such as words and

anipulste

Lessons aray of character

ie terminating null (10) jg

© function that works with
oran à string not terminated

porn, because JS TS ends Infact, a SUD ©

sting ann ee pends. collection of characters

0 is tre asin

one-di

Representation of Strings

can be represented using an aray OF 3 linked list. À string

of characters having length m can be implemented by a ones
dimensional aray of elements where the i® element of the array
Stores the i character of the string, The advantage of such a
representation is tha he aray elements can be directly accessed
and this could speed up several operations on strings. Array
representation of string in memory is shown in Figure 4-1.

A string

| GREG Tepe) |

| m m 44 405 406 407 408

Figure 44, Array representation of characters

ran.

An alternative representation of strings can be done using a linked
list. A pointer to the linked list identifies a string represented by @
linked list. Each node in the list contains a character and pointer
to the next character in the string. The pointer of the node
e string is set to NULL. The

containing the last character in
string as a linked list is shown in Figure 4-2.

representation ¢

Data Pointer to next node N stands for NULL

Lt |
[Ple +h a0 +1] |

Evous) Fede} Frodo] [nose] nose |
|

Figure 42. Representation of a string as a linked ist

Operations On Strings

While working with strings, we are often required to alter the
characters present in a string. Table 4-1 gives a list of operations
that can be performed to manipulate a string.

"The number of characters in a string is called its length. The string
With zero character is called an empty string or the null string.

print ("String st: seein, 1)
len =xstrien (st)
print (‘length ofthe string st: 22d, len)

one sting to anothe

2)

print (Strings

ys of

xs
print (“String s after copying s1 to

of another string

ns)

ya the end
nd finds whether hey are

cal or not

(83,52

ter concatenation: sin", 53)

i ( xstromp (st, s2
(The strings s1 and s2 are similar);

ow to implement operations shown
‚show «
print (“The strings st and s2 are not similar);

he following program show

in Table 4-1
retum ©
include <dl> }
en finds the length of the string */
Be Almen re
À y
intl =0;
int xstrien ( char *) ; :
void xstrepy ( char *, char"); ie 's)
void xstreat ( char”, char*); Mr
int xstremp ( char *, char"); M
void show ( char*) ; ) Y
retum | ;
nate ;
chars i : pes
= "Nagpur I" copies source string s to the target string
ah i void xstrepy (chart, char °s )
; (
ne while (*s)
{

system ("cis");

nes
pe
se

copar ostias LL
int stn (cars char)

while (*s=="0)

us
retum 0

se

tH)

Is
setum (*s-"t);
}

Output:

‘String st: hc

Jg ofthe sting 51: 5

Sas
copying st tot ct

Sting 59 ater concalenation:kctNagpur

Gaia Structures

Chapter 4: —=

3 : Me

The stings 51 and s2 are not similar

In this program we have created three arrays of characters, sf, $
ee sys of characters, sl, s2

The function xstrlen( ) is fairly simple. It receives only one
parameter as the base address of a character array. All that it does
is it keeps counting the characters till the end of string is not met

Or in other words it keeps counting characters till the pointer s
doesn't point to %0'

The function xstrepy( ) receives two parameters. Both the
para are the base addresses to the target and source strings
respectively. This function copies the source string whose base
address is received in pointer s, to the target string whose base
address is stored in the pointer t. The function goes on copying the
source string into the target string till it doesn't encounter the end
of source string. It is our responsibility to see to it that target

string’s dimension is big enough to hold the string being copied
into it

The function xstreat( ) also receives two parameters. Here also the
parameters are the pointers to the base addresses of the target and
source strings respectively. This function adds the source string
whose base address is stored in pointer s at the end of target string
whose base address is stored in pointer t. In the first while loop we
have made the pointer t to point to the end of the string. In the
second while loop the contents of source string pointed to by s are
added character by character to the target string pointed to by £
Lastly, we have added a null terminating character 0" at the end
of the target string pointed 10 byt.

TA

€ two Strings arg
ise, it returns the
f the first non.

frst. If the
> 0, otherw

ef us
a ae

of
matching pair ©

5 rings

Pointers And $ | Wemay either sore it in a string
eae ocation in memory
ing toa char

¡some lo

store
pointer. This is shown

sompil
ofthe

o we wish
SER may ask he €
ecg the aes
pelo

char st] = Hel"
char p= "Helo"

se of these two forms. For
iference in usage

le e sing to another, whereas, We can

her char pointer. This is shown in the

There is a sul
example, we cannot assi

assign a char pointer to ano
following program:

int main)
{
charstri(]= "Helo;
char si2(0)
chars = "Good Moning’
charg
St2= st; Pemor*/
4=8; [wos /
retum 0.

Also, once a string has been defined it ini 1
cannot lised 10
another set of characters. Unlike strings, ae ie pee is

TR

JE

perfectly valid
program:

With char pointers. This is shown in the following

A Two-Dimensional Array of Strings
In the previous chapter we saw how to create and maintain 2-D
at a similar phenomenon, but one
dealing with characters. The best way to understand this concept is
through a program. Our example program asks you to type your
name. When you do so, it checks your name against a master list to
see if you are worthy of entry to the palace, Here's the program...

numeric arrays. Let's now

“include <skdioh>
include <conio h>
include <string.h>
#include <windows.h>

#define MAXI 6
#define MAX2 20

char mastetst{MAX1]MAX2} ;

int count ;

int add (chars)
int find (chars):

fog = ade (ana)
ie

=0) p
ent (‘nate sig)

fag = add "ajsh'");
(fiag==0)

prin “Unable oad tig");
pitt “Enter you rae: *);
gets ( youmame );

flag = Ind youmane);
(fog == 1)

PO si! econ pacan ee the placa");

PS) Yost opa

Chapter 4: Strings |

retum 0
}
I" adds string to the array *
int add (char*s)
{

if (count < MAX )

{

if ( stlen (5) <MAX2)

stropy ( Smasteristfcounf]0], s);
count++
retum 1

}

retum 0

}

I" finds the given sting *
int find (char*s)

int flag = 0,1;
for (i= 0;i< count; it+)

if ( stremp ( &mastertist{]j0), s ) == 0)
{

me 2

Chapter 4: Strings HE

at: if svien (s) < MAX2)
Out:
ie stvepy ( 8masteistcouniO), s )
Eat hen st[count][0), 5)
retum 1
oer 0 128 A are =
bone, you" te ï
ee D ch couté print (“Sting length should not be more than Ya,
Here we have used me, called count which counts the À ce
called mast a i get added lo the masterlist array. The MAK2
number of string that eee declaration is important. The firg ;
rates Be ms in he ara: Bi 7
sub MI age me enth ofeach item in the array,
seconds E
‘The function find ) checks if the given name i aie
encesonal character array has been | : k da Her me i
the ‘weg funtion to add new string to the masterlist array. While comparing the strings ace 5
We have ale on allows addition of a string 10 the mote that the addresses of the two strings are being passed 10
2-D array. The add) fu a sip cms ES
0, otherwise it would retum a non-zero value. nie

two conditions are satisfied.

array if following
stings o be added to the array is less than

(a) The number of
MAXI.
(6) The length string to be added is less than MAX2.

Instead of initializing names, we could have supplied these n
from the keyboard using the scanf() function. In such a case
add() function would have then looked like thi

the contro! reaches
means that none of the names in the
‘one supplied from the keyboard.

int add)
fiestas
char sag];

rin "Ener sting: *)
ls;

4081 1101

N ‚character;
[mn m TL] haracters
¡A 3
Figure ape bse adresses of success
2001, 1021, 104), figure, some of the ae 10
Here, 1001, 102) pe bo even though
As sen fo ‘
names. res y”, it occupie
tes . nam s
copy al he for sorin e Tact more the number of

so bes ae m
20 es Ts, Ban his not be avoided? Yes,
only ore would be the ME called an array Of pointers 19

by usines © ico sion.

To Strings
able always contains an address,

ray of pointers it would contain a
how the names in the earlier

Array of Pointers

‘As we know, a pointer var
Therefore, if we construct an a
number of addresses. Let us see

‘example can be stored in an array ‘of pointers.
chartrames[]=(
“parag’,
“ramman',
) lee

In this declaration names is an array of poi 4
addresses of respect iy of pointers. It contains
Preive names. That is, base address of “akshay”

TZ Mr

stored in names[0), base address of “parag” is stored in names(1]
and so on. This is depicted in Figure 4-4.

== |
1048 2006

Gew] Ge)
4008 6002 7118
names[]
oa a

8112 BE 8120 812481288132.

Figure 4-4. Memory representation of array of pointers.

In the two-dimensional array of characters, the strings were
occupying a total of 120 bytes. As against this, by using the array
of pointers to strings the same strings can now be stored using 65
bytes, 41 bytes for the actual strings and 24 for the array of
pointers, A substantial saving that goes on increasing with the
number of names being stored.

‘Thus, one reason to store strings in an array of pointers is to make
more efficient use of available memory.

Another reason to use array of pointers to store strings is to obtain
greater ease in the manipulation of the strings. The following

‘shows this. The purpose of the program is very simple.
Wed E positions of the names “raman and

We want to exchange the

Chapter 4: Strings
MA

print (“Unable to add stringin?

or
ie oe |
Foote STD,
A | flag = add (“rajesh") ;
a a Cora
etre! L Po ana)
(er di
= | Br ("Names bee app):
pré
2 = N ea:
Ba int (1
zum : Bil ans er secs)
Er retum O;
int main() '
| pr F adds given string */
= int add (char*s)
# (count < MAX
og = ad (‘esta
namesfcounf = s;
unter;
retum À;

1(ta9=0) '
D Una af st):
fag = ad ('pareg'):
#(feg=0)
prin ("Unable lo add string");

ag = af (amar);
t(fag=0)
= pint ("Unable fo add sting );

eg = ad ‘sinivas');

ae

wa Structures Throughes
Dat —

it gent)
por Cas ¡ret
prin (vi

Output:

akshay

In this program all that we are required to do is exchange
addresses of the names stored in the array of pointers, rather
the names themselves. Thus, by effecting just one change we
able 10 interchange names, This makes managing strings
convenient.

‘Thus, from the point of view of efficient memory usage and

programming an amay of pi i e 0
E > AO array Pointers to strings definitely scores

EZ

Limitation Of Array Of Pointers To Strings

mar |.

dimensional array of characters, in actual practice it is the array of
Pointers to strings, which is more commonly used.

Chapter 4,

When we are using a two-dimensional array of characters we are at
liberty to either initialize the strings where we are declaring the
array, or receive the strings using scanfí ) function. However,
when we are using an array of pointers to strings we can initialize
the strings at the place where we are declaring the array, but we
cannot receive the strings from keyboard using scanf( ). Thus, the

following program would never work out.

#include <stdio.h>
int main( )

char *names{6]

inti;

for(i=0;i<=5; i++)
print (“Enter name: *)
scanf ("%s", namesfi)) ;

)
retum 0;

The program doesn’t work because when we are declaring the
pe is containing garbage values. It would hora borg 4
to send these garbage values to sean ) as Ihe addresses where
should keep the strings received from the keyboard.

promise solution we may first allocate space for each
Be 1 mall) and then sor the adress etre by

qe

gs This is shown in yy

system ("08")
for(i=0;1<5;i#)
5 pin ("Ener a Sting")
ee nr) nalo (ses) +1);
stroy (namef) st);

Pit);
print (“The stings area");
for (i=0;1<5; i+)
print (sr, name)
for(i=0;i<5;i44)
fee ( i

Chapter 4: Strings LE

Output:

Enter a String: akshay
Enter a String: parag
Enter a String: srinivas
Enter a String: raman
Enter a Sting: gopal

The strings are:
akshay

Pattern Matching

Today word processing is no longer restricted to simply creating a
textual file and getting it printed out. Word processing applications
that are used today perform a wide variety of jobs, the most
challenging of them is to search for a given sequence of characters
or a word. Finding the position where a string (usually called
pattern string) first appears in the given string is called Pattern
Matching.

In pattern matching we check whether or not a given pattern string |
P appears in a text string en Ses erento
blem is to an it be

prot construct sand

parameters, a pattern string p and a search |
position at which a match is found. :

R

Structures. rouges
Ur

pr algorithm, Boyer Mo
tine out MOT ine scope oF this book Moore
be

rithm

sed for pattern ma

re lis used for FALE mati
A fm the sing $ I which the pattern stein
o dis algo e by character. Begining fro

f characte is compared wip

According
isto be sea ing s, ec
the 0? cha de Of the pattern string P. This process
her there is 90 mismatch or the pattern string p jy

match is found then the index of the character op

arson began is retumed as the position

y pis found. However, ifthere is a mismatch

considered and there onward,

vere te pattern Sin

then next character of Ü
ed with the cl

ss continue? The process ends either

the string $ IS
haracters of the pattern string p

again it is compare
How long would this proc

when a match is found or wh
string that remain to be scan
characters in te patter string P.

Let us now see a program that implements this algorithm.

ven the number of characters in the
ed is less than the total number of

include <sidio >
include <onic.h>
include <sting >
‘clude <windows >

ink xstrsearch (char char
ia: i;
inma)

{
chars] = Mogul;

chars} = "Ket
toos.

Chapter # Sin

system (
Print ("Sting st: sia", st )

Print “Sting 52: ini", $2

* search if s2 is present in st +
pos = xstrsearch (51, 52
Print (“The patter string is found at positon: Yin’, pos )

i
reas pen
nt re mi

inti,j.
int = stien (st)
int 12 = strlen ( s2)

-Q;i+)

$2) 88 (j<12))

Dana Structures Tiro
— ee :

| — —

include <stdio.h>
include <conio.h>

Ke
ome fat position: 6
rg b include <sting.h>
The pattem ‚arch( ) implements the logic of #include <malloc.h>
ram, he ution at include <windows h>
in this Prog it
he ate Fore leon” clés: The TER int search ( char *, char)
ree Pond is the add int isequals (char *, char")
The function 25796900 ring sf and the see length ress of int issmaller ( char *, char*)
base address OF we have obtained the length 11 of the int isgreater (char *, char *)
mm sing 2 THON pater string. The process of Char" getub (chain, it)
g and length Fe Loop. This loop gets terminated ¡fa char" leftsub ( char’, int n})
ins through a Sr if the number of characters thay char * rightsub ( char, int)
matching pater is TOUR han the number of characters present void upper ( char")
remain to be scanned is less M he Joop runs till the value of veld ese ec)
void reverse ( char")

2. in other wor

2
Jess than 11 — 12 int replace (char, char, char)

in the patter string
int sett (char, char, nt)

oop counter i (of for loop) is
loop 12 number of characters of search string al
th all characters of pattern string $2. The loop int mein)
sa mismatch or the pattern string is exhausted, {

IF match were found ten at this stage the value of j would be

Hence the index i would be retumed as the position at

which the pattem string is found. However, if string s1 does not

contain any matching string hen -1 is retumed.

Through the whil
are compared wit
terminates if there i

equal to D.

In the program given above (11 - 12 + 1) * 12 (i.e. 35) comparisons
would be required to find a mismatch, Still, due to simplicity of”
algorithm, this algorithm is implemented very often for string

print ("Sting st: sin’, st)

searching applications.
| check forthe frst occurence ofa character“!
Few More Strii i a FES
ing Functions u
Ha: 5 weh
ving gained knowledge about how strings are managed in Cı fi 4)

1 ton st gear an tg 2":

ant‘ sot gtr han Sng soit);

1 extrac characters algien positon /
pit ("Sting si sn, 3);

= gets (53 5,7);

prin "Sub sting: sin
free (s);

extract efimostn characters "/
= leftib (3,4)
printf (“Left sub sting: usin’, s);
fee(s);

tra tms characters "|
semis (53,3);

Chapter Sings

prin "Right sub sting: %sin, s)
free (s)

convert sting to uppercase *
upper (83)
print! (Sting in upper case: ”

P convert string to lowercase *

lower (
print ("String in lower case:

rs)

1,3)

* replace frst occurrence of one char with new one *

replace (51, 4, M
printf ("String st: sn, st

sets a char at a given position
i= setat (st, M,3)
(i)

print ("Sting st: sin", S1 )

else
‘print ("invalid postin in");

retum 0;
}
1° check forthe fst occurence ofa character"!
int search (char st, char ch)
{
inti=0;
while (str)

it(*st=ch)
retum i

nm

mes
Mo:
ras ego)
insu

Ue (sI
cea
et,

se
wi
muni
}

checks weber
Léa (ed)

y while (*)

i ee

signed

Y

Chapter 4: Strings os

intisgreater (char *s, chart)
while (*s)
tes")

if(*s>"t)
retum À ;

retum 0 ;

PP extracts the character at given position *
char* getsub (char str, int spos, int). -
char "s = str + spos
char*t= (char) aoe {+ 1);
inti=0;

while (i<n)
{

oe E

wa
N:
ae
nied |
| | Iles>- gran
z Le ae 's <= 123)
à sie
: )
‘ 1 converts string to lowercase
rer (cha) E
ets sd
| “sel
ae ones! if(*s >=
roto ct) y a
| | se; é
iene }
=sten( st) |
a se (1-0); :
: 4 a string “
void reverse J
5 | | =i
int |= sten.
ns ES =
si rn |
| E while
ge; { ae 2 | |
retumt;
> i
converts sting
to uppercase
void upper (cars) i

{
wen

Output:

Sting st: Helio
Enter character to search: | he
The first occurence ofeharace is found at index no. 2

Sting s2 Helo Word

Stings sands? are not en
Sting sis smale than sings?
Sting 51 ot greater then sting s2

Sting: Fur unde ity wo
Sub sing hunde
Let sub ting Four

Pata Structures Tipo,

ER

Right sub string: two

‘Sting in upper case: FOUR HUNDRED THIRTY TWO
‘Sting in lower case: four hundred thiny two
Reversed string: om ytrht derdnuh ruof

Sting 51: Mello

Sting sí: MelMo

In this program several functions are called from main() that are
used to perform different types of operations on the string.

The function search( ) searches for the first occurrence of a
character in the string. It receives two parameters as the base
address of the string and the character to be search in the string. It
returns the index position of the character where it was first found.
If the character is not present in the string then it returns —1

The functions isequals( ), issmaller( ) and isgreater( } checks

whether the first string is equal to, smaller than or greater than the

second string respectively. Each of these functions receives as

parameters the addresses of the first and the second string. In each
of these functions a while loop is executed that compares two
strings. The function isequals( ) retums 1 if the two strings are
identical, otherwise it returns 0. The other two functions also work
on similar lines

The functions getsub( ), leftsub( ) and rightsub( ) are used to
extract specified number of characters from a specified position in

a string. They differ only in the starting position from which the
characters are to be extracted. The function
getsub( ) receives three parameters. The first is the base address of
the string from which the characters are to be extracted. The second
is the starting position of the string from where the extraction
should begin and the third is the number of characters to be
extracted. Both the functions leftsub( ) and rightsub() receive two
parameters that represents the base address of the string and the
number of characters to be extracted from the left side or right side

ja Structures Throyge~
è

m. $
Chapter 4: Strings

EINE

iw) of these three fy
wa ote tat OT ne string font
ect of ofen a new sti hic A
re ad de © tin at which the ch
othe ste “ Inste‘ . returns t 8 thy aracter is to be sel
nse oes ee set esse set. The function returns 1 if the
dass sie nd ly set, otherwise its returns 0 ®
allocating E ratio | the conversion fi
uote ee on ES
po PPT ara lower cage
i ee one parameter the
ted. In case of u
PPer(

anio PP
pane en de El

comer
vic ely. Bol pat is 10 tin a string ar
= string are cs
sent onverte

el DOS y
adress ol le ng under Pom the ASCIL value: of
funciona, ty subi jed out in Jower( ) function, exe
ey in ete ndded 32 to the ASCII vá]
subtracing >
eee
‚string. Here we have
re anio ree Md cad ofthe Sing St Then a wid
Gr pi lraunber o times as the length ha
e E SUP ith the element in the last position. In the
ei rain o te ile IP the second element is swapped
‘ith the second last element, and so on.
ce) replaces he frst occurrence of a given
"he string with the new character. This function
Reese parameter. The ist parameter is the base address of
the string, the second is the old character oldch that is to be
replaced andthe third is the new character newch that is to be
placed inthe sting Inthe function a while loop is executed which
— forthe first occurence ofthe oldeh, and if it is found
copies the contents of neweh in place of oldch.

cons
fi be convert

The function repla
character preset it

— ) sets a given character at a particular
ie pe is the base address of the
second is the character that is to be set and the third is the :
x

TETAS

(2) To add one st
a string at the end of the other
o To add one sting atthe beginning of the other

string containing unique characters from

Exercise 2
blanks: y of characters: both the strings
ja Filtin the coran roy E
. isnohing character, which ig
Wee E (e) The \0' character indicates
@ A string À LE (1), Where the string begins
written 95 = S (2) Where the be
© An sm (5) The string is empty
strings pais twostioes to know if (4) The length ofa string
(d) The fi Cara {CI Answer the following:
rings are ident
two , (a) How many bytes woul i pl
loros (9. How many bytes would Bo series by te ins sy oF
us strings? How many bytes would be required to

jtemative for the

18] Choose the comet store the
fa ore the same strings, if they are stored in a two-dimensional

(Pan main ae in the other string character array?
E To check ftw sings are ie eee A car*s[1=(
(9) To check iftwo strings ale 4 ml A
(3) To compares two stings 19 know the count of similar Mas ee +
characters. “Spit and posh
(b) The length ofa string 2 : IN
(1) Is the total number of characters of the string excluding k
blank space L (b) Can an array of pointers to strings be used to coll i
(2) Isthe total numberof characters in the string à from the keyboard? If not, a etna
(8) Is the total numberof characters which are repeated in the
e foe ens iu 4 [D] Write programs for the following:
(a) Write a program using Brute-Force algorithm to search for
(©) To copy one string into another means | pers = a
| ttern str where scanned from right
(1) To add one string at the end of another string fee shire rer I
(2) To create new string ; ‘
a Jo copy te arg Sting the source sting (b) Write a program to delete a sub-string of given string. For
}) To copy source string to the target string example if the string is “What is life’ and the sub-string to be
Gh Tees shee deleted is “life” then first check if sub-string “life” is present in
Kan the string and if present then delete it.

(1) To copy one string to another

ares

ee

the blank spaces except
ais sample, if a string jg

(owe et ne de POE ould a
i pe Di
No PaO gins, No ge“ ee
De Eo pios NO ys umber of words, lines ang
ring sch &

ee O css di

© oes program © men, er mo wor on lo e
program elas eS
seit Oo onsen of character en

(0. Wren gaa opi PTE

chars act ou on D
“yore aroun
“Level abuling’
“erase he past,
“Make a mio
DT LA

CHAEMER
FIVE

Linked Lists

Stay Connected

nited we stand, divided we fall! This has been proved

umpteen numbers of times. More united and connected we

are, more is the flexibility and scalability. Same is true with
linked lists. This is perhaps one data structure that has been used at
more number of places in computing than you can count, But,
beware, they are not simple, But the flexibility and performance
they offer is worth the pain of learning them.

us

— E

Sirictures Through &

Data

Ce Y

use either an array op q

TE à
wen and elements of
ee sind am ofa
wing similar HR ple 1° under fer from the following A
St a fa my What Is A Linked List
ed ail :
D are casi the size of an array Linked 1
: oon y is inked list is a very common
mio ud dimension creased during execution, ciclo data in memory Whites O ÓN
atom e fae re a sais | memory. While the elements of an array ocou
pa nape Gel ts and contiguous memory loc ee
q sp eee Constrained to be sored in adjacent locations. The individual
Fecal re re ny 10 elements then elements are stored "somewhere in memory, rater like a family
fot cs vas dispersed, but sill bound together. The order ofthe elements is
ert mer Sg coniguous memory maintained by explici Inks between them. For instance, the marks
ray elements are Bi so happen that enough contiguous es a fee students can be stored in a linked list as
Don, Actes ye for the array that We are
Jocaons might ol a, Le total space requirement of
ing to create. E Imbination of non-contiguou: r —
ping 10 € rough a co s
the aray can be met ME not be allowed to create the =
data | ink | N stands for NULL

Opens in moe nem element in an anses
peri a erg coment Im Ihe array ar: BEA =
during insertion or deletion each OPE

200 100

tedious. This is because i
sear afer the specified position has to be shifted one
son ote right (in case of insertion) or one position to as ee

the lft (in case of deletion). Refer Chapter 2 for more details.

Linked list overcomes all these disadvantages. A linked list can
row and shrink in size during is lifetime. In other words, there is Observe that the linked list is a collection of elements called
no maximum sizeof inked is. The second advantage of linked oma: of which stores two items of information—an element
iss más een) a red at diferent memory a rors de snes a
los yop at el st of memory whe explicitly the Ka as
third advantage is that, unlike arrays, while inserting ie de En pare pe ants is cai crepes re
s ‘obtained by a student and

babes the nodes of the linked list, shifting of nodes is not the link part is a pointer to the next node. The NULL in the last
L £ in
f node indicates that this is the last node in the list.

mare Tro

ed jist . append ( &p, 25)
can think of performing, on append (Bp, 42)
«tat we 8" “how to build a linkeg append ( &p, 17)
rt peri gram SHOT tthe end Or in the ß
à follomins he weer funtion display ) system ("dls")
wading jo conta.” the linked list and E
fa oe ee des pesan ie Linked list, Go display (p)
ys all the q
ich can dele time addalbeg ( &p, 999)
J ram carol addatbeg ( 8p, 888)
through the PE addatbeg ( &p, 777)
rede Ho display (Pp)
include <conio
Froude <raoe!? addafter (p,7,0);
ice cuindons > 2 addatter (p, 2, 1):
caro ang date EP addafter ( p, 5, 99);
shuctrode display (p)
int data printf ( "No. of elements in the Linked List = %din", count (p));
‘ struct node ink; del ( &p, 99);
: del (8,1);
vi gpd (sac ode tt) del ( 8p, 10);
vod adateg (struct node" int):
void addafer struct node * int, int); display (p):
‘oid display (struct rode *) printf "No. of elements in the linked list = Yin’, count(p ));
int count (stuct node * retum 0 ;
void el (strc nade nt); )
int main) 1" adds a node at the end of a linked is
{ 4 void append ( struct node “a, int num )
struct node'p ; {
p= NULL; empty inked st) struct node “temp, 'r;
pe No.of enensin be Liked List = ed’, count (p)) if ("q== NULL ) Pifthe istis empty, create fist node “|

append (Bp, 14); {
perd (4p, D); temp = (struct node *) malloc ( sizeof ( struct node ) ) ;

=

rotas, anne):

snare")
Lae
pon NULL:
DATE

1

1 Inked ist‘!

ode the begining of

a ey tote tru)

(
stunde “emp;

"add new node */
dar eme) nal [seo (set node

temp -> data = num;

}

als à new node ar he specified
[Ane tn thr,

Chapter 5: Linked Lists We

desired portion
for(i=0;i<loc i++)
temp = temp > ink;
Tr end of linked list is encountered *)
AT
print ("There are less than %d elements in ist", loc);

}

}

FF insert new node *]

r= (struct node *

5 er *) malls ( sizeof ( struct node ));

+ link = temp > link:

temp -> link =r;
}
poo LE
ess)

Be

) RE us
rae ae a)

© ete‘, #0
temp="9

vie (emp NULL)

PT Lu)

(node tobe deleted
(temp ==")

a temp > ink;
1" dellesteintemediale nodes in the linked list vi
el

the fstnode in te linked list */

se
> p> ink

fee the memory occupied by the node
fee (temp) ;
rem,

]

zes ied els ode reached /

si

Chapter 5 ne

Le eee

ld = temp ; 7 old points tothe previous node *!
y MP MP > ink; goto tenet node
)

printf (“Element %d not found, num)
)

Output:

14302542 17

777 888 999 14 30 25 4217

777 888 999 1 14 30 99 25 42 170
No. of elements in the Linked List = 11
Element 10 not found

777 888 999 14 30 25 42 170

No. of elements in the linked list = 9

To begin with we have defined a structure for a node. It contains a

data part and a link part. The variable p has been declared as

pointer to a node. We have used this pointer as pointer to the first

node in the linked list. No matter how many nodes get added to the
linked list, p would continue to pointer to the first node in the list.
When no node has been added to the list, p has been set to NULL
to indicate that the list is empty.

The append( ) function has to deal with two situations:
(a) The node is being added to an empty list.

(b) The node is being added at the end of an existing list.
In the first case, the condition

if (“== NULL)

GASTE Thron

ed for the node usin

loc Setup Up tal
is aloe de are Set UP using «ye
Lei Far of
satisticd. # link
gets sy pa
allo
Siemens
> datan 5
temp > ok NL ode, since the first node hay
int 10 this MOT point to the first node
jx made o PO must always PO le,
Lastly, P jst am
Den ses o cl a
Note that 445 jc linked ist iS not empty, the condition
when the i
Inthe other ca,
pen) JLL). Now temp is made tp
an “ Ge pis om NULL) statement
woul fal sn CR dough the

point tothe first m

fen? through the entire linked list

Then usin

t
y temp we have Inversed
using the statements

while {temp => ink != NULL)
temp = temp» lnk;

The position of the pointers before and after traversing the linked

list is shown in Figure 5-2.

node being
added

Figure 5-2. Working of append) funcion

Each time through the loop the statement temp = temp > link
makes temp point to the next node in the list. When temp reaches
the last node the condition temp -> link != NULL would fail.
Once outside the loop we allocate space for the new node through
the statement

r= (struct node * ) malloc ( sizeof ( struct node ) );

Once the space has been allocated for the new node its data part
stuffed with num and the link part with NULL. Note that this
node is now going to be the last Node in the list.

All that now remains to be done is connecting the previous last
node with the new last node. The previous last node is being
pointed to by temp and the new last node is being pointed to by r.
‘They are connected through the statement

temp > link =r;
this link gets established.

—_— D
_ Bere Tree

du temp
whe ge in the list. Lap ©

e Uy
Je. SUPPOSE in a ing A
the fist node, Tyas temp p

10 OW

son ne met

pele OF inting
is pol

ip

After Addition
Figure 5-4. Working of addatbeg( ) function.

je we have shor
showing te inks 10 ee node. ail
tead of showing ink A
Inte fie next oe inte For adding a new node at the beginning, firstly space is allocated
addr: > for this node and data is stored in it through the statement
teme
When we execute th sta

temp -> data = num;

stored it Now we need to make the link of this node point to the
ow stored in t 5 =
the righthand side yield BT nie prisa at ade existing first node. This has been achieved through the statement
a resul, temp starts pointing ! N
rane fet te semen has shifted temp so that it has started à

pointing tothe next node in thelist temp > fink ="q;

Let us now understand the addatbeg( ) function. Suppose there are Lastly, this new node must be made the first node in the list. This
already 5 nodes in the list and we wish to add a new node at the has been attained through the statement
beginning of tis existing linked list, This situation is shown in
Figure 54, | u E

The addafter( ) function permits us to add a new node after a
> specified number of node in the linked list.

esired number of nog,
she desi les
esti te ose we wish to add y
cd SE rode in the lis, The
a usd the for loop
ed for the node to pe

(b) After Insertion 4
Figure 5-5. Working of addafter( function.

‚All that remains to be done is readjustment of links such that 99°

goes in between 30 and 25. This is achieved through
statements

1 ok ep > ek;
temp > b=;

ae

— ee

The first statement makes link part of node containing 99 to point
to the node containing 25. The second statement ensures that the
link part of node containing 30 points to the node containing 99.
On execution of the second statement the earlier link between 30
and 25 is severed. So now 30 no longer points to 25, it points to
99.

The display( ) and eount( ) functions are straight forward. We
leave them for you to understand.

That brings us to the last function in the program i.e. del( ). In this

function through the while loop, we have traversed through the

entire linked list, checking at each node, whether it is the node to

be deleted. If so, we have checked if the node being deleted is the
first node in the linked list. If it is so, we have simply shifted p
(which is same as *q) to the next node and then deleted the earlier
node.

If the node to be deleted is an intermediate node, then the position
of various pointers and links before and after the deletion is shown
in Figure 5-6.

am 56 Wego de ton
ession that beginne:
e eee integers. However, a linked lig
en ed storing any similar data. For example,
dere can esta inked list of ost, a linked list of names, or even
a inked ls of record, where each record contains name, age and
salary of an employee. These linked lists are shown in Figure 5.7,

ET?

a ee nn
[Es] 342 Hs E 57 Ca ||

Linked list of floats \

Gore ie son D |

Linked list of names

[jay 24] 5000 CES sooo] |
|
iL
AUDE ona

Linked list of Structures / Records
Figure 5-7. Different types of linked list.

Ascending Order Linked List

Now that we have understood how a linked list can be maintained
how about ensuring that every element added to the linked list gets
inserted at such a place that the linked list is always maintained in
ascending order? Here itis...

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

structure containing a data part and link part */
struct node A
{

int data ;

ructures Troe,
ess Troie
=a

Dr 5 Dur

{

("traverse the entre inked Histo search Ihe position to insert the
new node */

while (temp != NULL)

i (temp > data <= num 88 (temp > link == NULL |
temp > link > data > num) )
{

13 link = temp > fink ;
temp-> ink =r;
retum

}

temp = temp-> link; 7 go to the next node */

}

I" displays the contents of the linked lst */

, void display ( struct node ‘a )
Gp (ph e pied ist= Wan’, count (P )) ‘
mo. Er l' traverse the entre inked ist
= while (q = NULL)
! {
7 adds node lo an ascending order inked it Ben
dosel nina) f q=q> lnk:
stuctnode emp = "9; print ("a

+= (setae "mac. seo stuct node ))
12 dala = num;

counts the number of nodes present in the linked list */

int count ( struct node *q)
‘ists emply er new node slo be inserted before the first node */ {
(= NULL [(*9)-> data> num) intc=0;
{
traverse the entire linked list *)
while (q!= NULL)
{
9592 link;

Data

sion add) that is responsible
vending order. It takes two
ining ¿of the type struct node «e
for maintain fst parameter 4 ae p. The pointer p holds

andes A. p “pho
pace Aes of PE Eau, or a NULL
er the address ofthe HIS TTT oûher parameter num holds

iked lis
itis

forthe new node, its address is stored
oc of num is stored in its data pan,

value in case of empty lint
the data that i to be inserte

located

emory is al
Initial memory isa

in pointer and using F

lis four
Now tablish the links. ‘There are c
ao ah

value it contains, they are as follows;

(a) To the empty lst
(6) Before the frst node in thelist
(©) Atthe end ofan existing list
(8) In the middle ofthe list

All these four cases are discussed below,
Case (a) and (b);

A condition is checked through the statement

EA
Br = AG

Chapter 5: Linked Lits —

if (a == NULL II("q) > data > num)
this is done to check whether the list i empty or whether the new
node to be added is the first node. In either caso using q the pointer

p is made to point to the new node (as q holds the address of p).
This is done through the statement

q="

The value of temp is stored in the link part of the new node
Pointer temp holds a value NULL if the list is empty and holds the
address of the first node if the new node that is to be added is
added before the first node.

[ case :mpty Linked List
| p=NULL r

on

New node
Befo Addition

After Addition

Figure 5-8(a). To the empty list.

mr

Thapter 5: Linked Lists

equal to the num and

be inserted if temp > dat
data is smaller than
jens than temp => link = Bata GER a pate fe ae pet

Ge: temp > link NULL)

rex nation at beginning

p
Case (6): Non-empty linked list, Addition at end

—
cg
Lee
3-6 e

D

Before Addition
| temo d

ls Kr Before Addition

a 2 >. in,

TA Jess

4
DIE „EIER Gr
Alter Addition a

Figure 60). Before the fs
the end of an existing Ist

Figure 5-8(6). At

Case (0) and (8):
ed to search the position

false then we n
a such that the al
‘maintained inthe ascending order. For this, we need to traverse the
list and ths is done though a while loop
Initially the pointer temp points to the first node and each time
through the while loop it is made to point to the next node in the
list. This is done through the statement

emp = temp > ink:

Inside the while Joop, num is compared with the data part of the

current node fs Pointed to by temp) and the data part of the
pointed to by temp > link). The new node shot

A

ATTE)

ee

or in middie
e Addition In mic the first node and the first beco

mes the last? Here is a program that
shows how this reversal of tay, me

5 can be achieved.

if a include <stdio n>
[IN #include <conio ho
Ts include <malloc.h>

Hinclude <windows h>

I Shure containing a data part and nk part
struct node
{

int data

struct node “link

qa void addatbeg (sit node» in)
void reverse (struct nade =)
an void display (struct node)
pls] 3 int count struct node *)

int main( )

struct node *p ;
OE; P= NULL; /* empty linked ist 7
| New node (89,7);
| After Addition Pre (8, 43);
4} | addalbeg ( &p, 17):
addalbeg ( &p, 3):

L
Figure 5-8(d). In the middle of te list

Reversing The Links aren cen

Having had a feel of linked list jet us explore what further display (p);

Operations can be performed on a linked list, How about reversing "No. of elements: = É
the nl in existing liked lis such thatthe Ios node bec mae ee esto);

9 struct node ) )

rats mo seas
(sei

pink

temp.

}

voi reverse stuct ro")
snetnode 91

q=%
r= NUL

traverse te entre Inked ist
while (q!= NULL)

Linked Lists

void display (struct nade *q)
(
7 traverse the entr inke ist
vine (q l= NULL)
{
print (*%a,q> data)
4-9 Ink
pr (ur)
)

y counts the number of nodes present
int count (struct node * q)

in the linked lst *)

{
entre inked [st
while (q f= NULL)
{
9=q> link
cH
}
retum ¢
)
Output:
523317437
No. of elements in the linked list = 6
743173235

No, of elements in the linked list = 6

The function reverse( ) receives the parameter struct mode ** x,
which is the address of the pointer to the first node of the linked
list. To traverse the linked list a variable q of the type struct node

the value of x. So
LE

is required. We de
ed 0 5% je statements rt
roti wih de poh te ss a
the fist
pines.
ode + is initialized to
+ which is of the OPS struct A a NU
a at pointing to the first ra
Fall r > lik is assigned § that > link becomes NULS
ai put the link part ofthe first node. A

which is nothing
ue inthe link part of the first node th
ren

address ofthe second node is ost Hence before storin,
NULL value in the ink part ofthe first node, q is made to pola a
to

the second node trough he statement

But if we store a NULL val

9=9> lnk;

During the second iteration of the while loo] i
pr points
ode nd ps ote nd node Now tte lnk port UN
e should point othe fst i ke
seconde stl y fst node, which is done through

Re

Chapter 5: Linked bie

_ Ta

ee
e Fina
link starts pointing to tre ro, ln à

lak starts poling foe irre a Pes ge
would be lost. Hence tenet e if we store the value of
made to point tothe area one he value of of the third node

node thr lve of s in r > lin}
rough the stateme ka q is
ment

q=9-> link

White traven
se previous node. As a ps
Le = been adjusted :
est node and first node ae

irst node becomes the last node.

Re EI
co E
g=NUL Ss 4
3 EJ GL) CA
For
r

|

Figure 58, Reversing the links.

Chapter 5: Linked Lis —

ma 7:

Merging Of Linked Lists

Suppose we have two linked lists pointed to by two independent
pointers and we wish to merge the two lists into a third list, While
carrying out this merging we wish to ensure that those elements
which are common to both the lists occur only once in the third
list, The program to achieve this is given below. It is assumed that
within a list all elements are unique.

#include <stdio.h>
include <conioh>
#include <malloc.h>
include <windows.h>

Fr structure containing a data part and link part“!
struct node

int data
struct node “link

)

void add | struct node ", int);

void display ( struct node *);

int count ( struct node *);

void merge ( struct node *, struct node *, struct node **);

int main()
{

struct node “frst, "second, “third ;

first = second = third = NULL ; /* empty inked fists */

add ( &fst, 9);
add (&frst, 12);
add ( fist, 14);
add ( fist, 17);
add ( first, 95);
add ( first, 61);

> PU =
{

(a) > link = temp

aussi)
sent)
rss) ount (fist) ) )
pind St) vines use wae com (Ft); Ma,
ÉTÉ CR {
F traverse the entire:
as ts 2) e ne ie entire inked isto seach the poston o insert the
Blasco 1) vie (orn be HL
ag asec 24) )
gzeond, 35) ice
oe 29) temp > data < num &8 (temp > fink == NULL |
aa second, 54) { temp -> link > data > num ))
xs (asec. 87) A
pot (acord si)
display (second) sedirin’, count ( second )
7 in Linked List Di
pri (No ofeenens A
merge (ist, second, third)
; 1 link = NULL
5
rollen in Linked ist: ed’, count (ir); }
COTE
A I" displays the contents of the linked list”
3 vo spay (a
ads node o an ascending order inked list */ | {
o Fe =
PROS i while ( q != NULL)
node temp ="9; q {
\ print (°94d*,@-> data)
} q=q-> link;
printf ("\n") ;

gee:
{aot ssl su ode)

}
"counts the numberof nodes present in he linked ist”)

("fists empl or new node sto be inserted before the first node *!

#("¢==MUL{('4)>éaa>m)

EE

vacant soar

hes st’
11005 ete ted

NULL)
EM

PELLE
ce

rue
1 mon elements to oc
seg he com cure
Los, Wy
te wo inked

Pan te alt sructnode “a struct node “*s )
void mere (set node D.

© snetrot 2:
2=NULL
bolt are empty")
if(p==NULL 88 q== NULL)
retum;
traverse both inked ists til the end. Ifend of any one list is reached

‘oop is teminated
while (p = NULL 88 q = NULL)

/ itnode being added in he frst node */
if(*s==NULL)
{

2 LE Ho [st poda

}
else
{
#22 (ed mal (seco (tut node;

ee

252 link

)

(p> data<q-> data)
(
22 data = p-> data
P=p-> link
}
else
{

i(q> data <p> data)

2 data = q > data;
q=q => link

else
{

ln ee qee]
2> data = q-> data;
P= link;
54 link;

/* if end of first ist has not been reached */
arcs

2> link = Et node mata sina ut node):
2= 2 link

2-> data = p> data;
p=p-iink;
}

li end of second list has not been reached */
while (q != NULL)

Gaia Structures

de ¿geof (struct node ) )

oupu
Fat
e in noté?
Secar ined it
RIADA ar
No.of elements Led
Te megedist a
HAE
io ofeements in Lint Uist 1

usual, we begin by pr a structure to
and link, which together represent a node,
ee faire first, second and third to point to the three
linked lists, Since to begin with all the three linked lists are empty,
these pointers contain NULL. Next, by calling the function add()
repeatedly two linked lists are built, one being pointed to by first
and other by the pointer second. Finally, the merge( ) function ig
called to merge the two lists into one. This merged list is pointed
10 by the pointer third.

In this program, as

While ‘merging the two lists it is assumed that the lists themsel
are in ascending order. While building the two lists the add(

CT ad Pate

AER

function makes sure that when a node is added the elements in the
lists are maintained in ascending order.

The function merge( ) receives three parameters. The first two
parameters p and q are of the type struct node * which point to
the two lists that are to be merged. The third parameter s is of the
type struct node ** which holds the address of pointer third
which is @ pointer to the resultant merged list. Before calling
merge{) third contains a NULL value.

First of all we check if both the lists that are to be merged, are
empty or not. If the lists are empty then the control simply returns
from the function. Otherwise, a loop is executed to traverse the
lists, that are pointed to by p and q. If end of any of the list is
reached then the loop is terminated.

To begin with, a NULL value is stored in z, which is going to

point to the resultant merged list. Inside the while loop, we check
the special case of adding the first node to the merged list pointed
to by z. If the node being added is the first node then z is made to
point to the first node of the merged list through the statement

Next, the data from both the lists are compared and whichever is

found to be smaller is stored in the data part of the first node of
the merged list, The pointers that point to the merged list and to
the list from where we copied the data are incremented
appropriately.

During the next iteration of the while loop the if condition for first
node fails and we reach the else block. Here we allocate the
memory for the new node and its address is stored in z > link.
Then z is made to point to this node, through the statement

TT

nd hat ih data OF both the
we M once o the merged fj

lis
a

id
igh

)
2 the data to the me
> ‚Feomparing, adding merged
The procedure of miner ofthe merged list and the list fan

and incrementing
where the dats is 3

leg repeat til any of the list ends,

of first and/or second list the while [oop

If we reach end 2
only one list then the remaining

terminates. If we have reached ens
Sens ofthe othe ist are simply dumped in the merged list ag
they are already in the ascending order. The working of the mes
function is shown in Figure 5-10. ge

SS

Grape

P first

|
LESS En
LN
EE NUE EE PEO |

Um

Figure 5-10. Merging of two linked lists

first P

"| coe IN)

q second |
|

third 2

Figure 5-10. Merging two linked lists (Contd).

Data Structures Through C-Yashavant Kanetkar (1).pdf

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Data Structures Through C-Yashavant Kanetkar (1).pdf

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77