Govt. of Karnataka, Department of Technical Education Diploma in Computer Science & Engineering Third Semester Subject:
Data Structures Using C++Full description
GOVERNMENT OF TAMILNADU DIRECTORATE OF TECHNICAL EDUCATION CHENNAI – 600 025 STATE PROJECT COORDINATION UNIT Diploma in
DATA STRUCTURES USING C++ SECOND EDITION D.S. MALIK Australia Brazil Japan Korea Mexico Singapore Spain
Download Data Structures Using C book - E Balagurusamy .pdf 328 Pages ISBN: 978-9383286584 Download: • Data Structures
Data Structures c Using Second Edition Reema Thareja Assistant Professor Department of Computer Science Shyama Prasa
Data Structures 9788176567060, DOWNLOAD http://bit.ly/1gg06j9 http://goo.gl/R3Qcf DOWNLOAD Through C, 2003, BPB Ya
1 2014 Data Structure Using C++ Easy With DS Notes For a MCA (Mgt./ Sem-III) And other Cources. On Pune University Syl
SYSTEMATIC APPROACH TO
* Do not buy the old book - you will not get the latest updated version. * Helpful for placement.
A. M. PADMA REDDY
-r=:=====tPurchase Book with Hologram Only
Systematic Approach To
Data structures (with C) aoot b ) ? a : b; big = 20 Output BIg - 2.0
1.7.10Bitwise operators In thissection let us see "What are bitwise operators?" Definition:The data is stored in the memory in terms of binary digits i.e., O's and 1'So Sometimes, it may be necessary to manipulate these bits. The operators that are used tomanipulatethe bits are called bit wise operators. . The various symbols used and the associated meanings are shown in the table below: Associativitv Precedence Operator Description Bit-wise Negate
1.28 Q Introduction to C
1.7.11 Special operators Let us discuss some special operators that are supported in C language.
1.7.1 J.l Comma operator (, operator) ow, let us see "What is a comma operator and what is its advantage?" Definition: The comma operator represented as a comma ( , ) accepts two operant and it is used to combine two or more statements into a single statement. Th compact statements can be written using comma operator. The statements executed one by one from left to right and hence it is Ieft associative operator. It ill the least precedence during evaluation of an expression. Example 1.7.11.1: Consider the set of statements shown below: temp = a; a=b; b = temp; These three different statements can be written as a single statement using cornm operator as shown below: temp = a, a = b, b = temp;
1* Exchange the values of a and b */
Example 1.7.11.2: Consider the statements shown below: a = 5 + 5, 6 * 5; II Output a = 30 b = 3, 25; . II Output b = 25 1.7.11.2 sizeof operator This operator is used to fmd the number of bytes occupied by a variable or a constan in the computer memory. The syntax is shown below: sizeof (operand); For example, sizeof( char) sizeof(int) sizeof(float)
1 byte 2 bytes 4 bytes
Systematic Approach to Data Structures using C 1. 22-
1.8The precedence of operators
(Hierarchy of operators)
Sofarwe have discussed various types of operators. To evaluate any expression, we shouldknow the hierarchy or precedence of all types of operators. Now, let us see . II'ha/is precedence of operators or hierarchy of operations ;11 C language?" Definition:In C language, each operator is associated with priority value. Based on thepriority,the expressions are evaluated. The priority of each operator is pre-defined in C language. The pre-defined priority or precedence order given to each of the operatoris called precedence of operator. The operations that are carried out based ontheprecedence of operators are called hierarchy of operations. Operator category
0 [] unaryoperators Memberaccess arithmeticoperators arithmeticoperators Shiftoperator Relationaloperators equalityoperators Bitwiseand Bitwisexor Bitwiseor logicaland logicalor conditionaloperator assignmentoperator commaoperator
~perators in order of precedence. (highest to lowest) Innermost brackets/function calls Array element reference ++, --, l, sizeof, -, +, -, &, *
Associativity L~R (Left to right) R~L (Right to left) L~R L~R L~R L~R L~R L~R L~R L~R L~R L~R L~R R~L R~L L~R
1.8.1Left associative operator ow, let us see "What is associativity elt fica/ions based 011 assosciativity? ..
What are the different
1.30 Q Introduction to C Definition: If all the operators in an expression have equal priority, then the directs order chosen (left to right evaluation or right to evaluation) to evaluate an expressi is calledassociativity of operators. They are classified into two categories based lY. the direction of evaluation chosen as shown below: • Left associative (Left to right associative) • Right associative (Right to left associative) 1.8.2 Right associative operator Now, let us see "What is left to right associative? Give examples" Definition: In an expression, if there are two or more operators having the sam priority and are evaluated from left-to-right, then the operators are called Left to Rig associative operators. We normally denote using L ---+R. They are also called s associative operators. This process of evaluating from left to right is called For example, 8+4+3=15 8-4-3=1
Here, + and - are left associative operators
Now, let us see" What is right to left associative? Give examples" ,
Definition: In an expression, if there are two or more operators having the sam priority and are evaluated from right-to-left, then the operators are calledRight to le associative operators. We normally denote using R---+L.They are also called rig associative operators. This process of evaluating from right to left is called rig associativity. For example, i = j = k = 10; f/ The operator is right associative operator and // assignment will be done from right to left Note: All unary operators are right associative operators. Now, we should see"What are control statel~ents? What are the types of contt statements?" Definition: The order in which the statements are executed is calledcolltroljlow. 11: statements that are used to control the flow of execution of the program are calk control statements. These statements alter the sequence of execution of the progra Based on the order in which the statements are executed, the various con statements are classified as shown below:
Systematic Approach to Data Structures using C l.l~Jl Sequential statements
simple-if Conditional branch statements
if-else Nested-if else-if-ladder
Un conditional branch statements
Now,let us concentrate on each of the control statement one by one.
1 9 Sequential statements First,we shall see "What are ~eqllential statements? quential control statements?"
Why they are considered as
efinltionThe programmer writes a sequence of statements to do a specific activity. Allthese statements in a program are executed in the order in which they appear in the program. These programming statements that are executed sequentially, that is one after the other, are called sequential control statements. Here, no separate statementsare required to make these statements executed in sequence. The flowchart andthe equivalent programming statements are shown below:
Statemen~2.1 I I I
1.32 Q Introduction
Here, statement-l is executed first followed by statement-2 followed by statement) and so on. In short, we say that execution of a program is normally sequential (one after the other). For example, let us write a program to convert degrees in Fahrenhei to degrees in Celsius which is given by the following relation: C = (5/9)(F-32) The sequence of steps to be followed are: • Input degrees in Fahrenheit • Compute Celsius using C = (5/9)(F-32) • Display the result • Stop execution The C program to convert Fahrenheit to Celsius is shown below: Example
to convert Fahrenheit
TRACING void mainO
Execution starts from main
printf("Enter degree in Fahrenheit\n"); scanf("%f' ,&f);
>rput . nter degree in Fahrenheit
/*Convert into Celsius */ c = (float) 5 / 9 * (f - 32);
Compute the degrees in Celsius c-4.4444
printf'(rResult = o/c f\n" "c), . 0
Out ut esu t = 4.4444
Advantage No separate control statements are required to execute the sequential statements one after the other. •..•. u!-- ..• -·-- •••• ~I' l~aUV.lInnF>_
The sequence in which the statements are executed can not be .
Now, "flow 10 O\'C/'COlllC this advantage?" This is where branching statements will make their existence. .
Q Systematic Approach to Data Structures using C \.33
1.10Branching statements Now,thequestion is "What are branching statements? What are the different types of 'wenching statements?" Definition:In sequential control, we know that all the statements are executed in the orderspecifiedin the program one after the other. However, computer can skip the executionof some statements. This skipping facility is provided by a group of instructions called skip instructions. These skip instructions are also called branching instructions/statements. Thus, the statements that alter the sequence of execution of theprogramare called branching statements. The branching instructions are classified asshownbelow: simple-if Conditional ----i branch statements
if-else Nested-if else- if-ladder . switch
goto Un conditional branch statements
break continue return
Now,let us see" What are conditional and unconditional branch statements? Wliat ire the various types?" Definition: Normally, all the statements are executed one after the other. The computercan skip the execution of some statements based on some condition. These statementsthat alter the sequence of execution of the program based on some conditionare called conditional branch statements. They are also called selection statements or decision statements. For example, if, if-else, else-if-ladder and switch statement.
1.10.1The if statement/simple-if
Inthissection, we concentrate on an important selection statement called if-statement. Now,let us see" What is if-statement/simple-if? When if-statement call be used?"
J.34 Q Introduction to C Definition: The simple-if or if-statement is a simple selection/decision stateme When a set of statements have to be executed or skipped when the condition is true false, then if-statement is used. The syntax of if statement is shown below:
Stat-An; If statement false
if ( condition) < Stat_Bl;>: ~ Stat-Bn;
The statements B 1 to Bn are executed if the condition is true
The statements Bl to Bn are skipped if the condition is false
Stat-Cl; Stat-C2; I I I
T I Stat-C21 I I
After executing the statements AI, A2 An one after the other, the condition ii checked. If the condition is true, the block of statements B 1, B2, . Bn are executed otherwise they are skipped. After executing the statements B 1 to Bn or after skipping the statements Cl, C2, . Cn are executed.
1.10.2 The if-else statement In this section, let us see a variation of if-statement called if-else statement and see , What is if-else statement? When if-else-statement can be used?"
~ Systematic Approach to Data Structures using C 1.35 Definition: The if-else-statement is a simple selection/decision statement. It is a twoway decision statement which does one thing or does another. If one set of activities haveto be performed when the condition is true and another set of activities have to beperformedwhen the condition isfalse, then if-else-statement is used. The syntax of ifelse statement along with equivalent flowchart is shown below: Syntax of if-else Equivalent flowchart Stat-BI;
. Execute T I to T2 if condition is true
Stat-Tn; > else Stat-El ; Stat'jE2; I I '(
Execute E 1 to E2 if condition is false
marks[O] marks[l] marks[2] marks[3] marks [4] , Toreferan item in the array, we specify the name of the array along with position of theitem.The position of the item must be written within square brackets (m. The positionof the item enclosed within square brackets is called "subscript" or "index". 1.11.1Single-dimensional arrays Dcfinition:Asingle-dimensional array (also called one-dimensional array) is a linear list consistingof related and similar data items. In memory all the data items are storedin contiguous memory locations one after the other. Pictorial representation of a singledimensional array is shown below: array
, 1000~1001 2 bytes
1002~1O03 1\ 1004.;1005 I 2 bytes
1006~1O07 I ,1 008-~009 / 2 bytes
1.46 Q Introduction 1.1-1.2Initialization
to C of single dimensional arrays
Now, we shall answer the question "What is initialization? initialized?"
Definition: Assigning the required information to a variable before processing called initialization. As we initialize a variable to some initial value (for exam sum = before the loop), we can initialize the individual elements of an array. Am elements can be initialized at the time of declaration. Now, let us see "HOI initialize all the specified memory locations?"
1.11.3 Initializing 'all specified memory locations
Arrays can be initialized at the time of declaration when theirinitial values are knee in advance. Array elements can be initialized with data items of type intege character, float etc. Example 1.11.3.1: Consider integer initialization shown below: int
~uring compilation, 5 contiguous memory locations are reserved by the compiler ~ the variable a and all these locations are initialized as shown below:
If the size of integer is 2 bytes, 10 bytes will be allocated for the variable a. Other examples, int a[5] =
Ilerror: Number of initial values Ilare more than the size of array
Example 1.11.3.2: Consider character initialization shown below: char b[8] = ·, During compilation, 8 contiguous memory locations are reserved by the compiler for the variable b and all these locations are initialized as shown below:
In fact, instead of characters, ASCII values are stored in the memory. characteroccupies 1 byte, 8 bytes will be allocated for the variable b. Other examples, charb[5]
Number of initial values /Iare more than the size of array
) .11.4 Partial array initialization Partialarray initialization is possible in C language. If the number of values to be initializedis less than the size of the array, then the elements are initialized in the order from oth location. The remaining locations will be initialized to zero automatically.For example, consider the partial initialization shown below: int a[5] = < 10, 15>; Eventhough compiler allocates 5 memory locations, using this declaration statement, thecompiler initializes first two locations with 10 and 15. The next set of memory locationsare automatically initialized to O's by the compiler as shown below:
1.11 Ii Initialization without
Considerthe declaration along with initialization shown below: char b[] = ' ., In this declaration, even though we have not specified exact number of elementsto be used in array b, the. array size will be set to the total number of initial valuesspecified. So, the array size will be set to 8 automatically. The array b is initializedas shown below. I
1.11.6 rray initialization
Considerthe declaration with string initialization: char b[] = "COMPUTER"; Thearray b is initialized as shown below.
1.48 Q Introduction
Even though the string "COMPUTER" contains 8 characters, because it is a string, always ends with null character. So, the array size is 9 bytes (i.e., string length + byte for null character).
1* Correct. Tll~ size of the array is string length + 1 *
char b[9] = "COMPUTER"; char b[8] = "COMPUTER";
I*Wrong. Size of the array should be minimum 9*
For string initialization, usually the programmers prefer the following declaration: char b[] = "COMPUTER"; 1.11.7 Reading/writing
In this section, let us concentrate on how to read the data from the keyboard and ho to display data Items stored in the array. Consider the declaration shown below: int a[5]; Here, 5 memory locations are reserved and each item in the memory location can~ accessed by specifying the index as shown below: Using
a[O] through a[4] we can access 5 data items. ~
general, Using a[Oj through a[n-lJ we call access n data items.
Once we know how to access each location in the memory, next question is "How store the data items ill these locations?" This is achieved by reading the n data ite fro the keyboard using scanfO function as shown below: scanf("%d", scanf("%d", scanf("%d",
In general, scanf("%d",&a[i)) where i = 0, 1, 2, 3, n-I. So, in C language,' we want to reap n data items from the keyboard, the following statement can be used: for fi==Oi i c=n-It if+) li=O 1 2 n-I
The above for loop can also be written by replacing '
Example 1.13.2.1 to these
Using this statement" the function returns the evaluated result. If a fimdion 0 not retum any value, the return statement can be omitted In the example, the function returns sum of two numbers. Function to accept two values a and b using formal parameters, and return the result is shown below:
Function header = type + name + parameters Function body = . declaration part +
return statement end of the function body "
Example 1.13.2.2: FWldion to accept two values a and b, add these two numbers, . res.Wt. d 00 Tetum any value i shown below: to) smn; s:mn=a+b;
I accept two values I I declare the variables used
: Add the two accepted values
Display the result
1.13.3 Return values and their type As discussed earlier, a function may not send the value or may send the calling function. This is possible only using the returnstatement as bel • return; 1* This statement is used when function ~ sending any value to the callingfunctimt *1 • 'retum expression; 1* This statement is used wh~ function is sending a value to the calling fimctio *~ Now, let us see how to write a function which computes the gest of 0 DlImbreIE and sends the larger value. Since the function has to find largest of 0 DUllnbelS • It requires two values and hence two variables ace required in the :fi.ulCtiiLn • It is expected to return a value and hence the type of e specified. The complete function to return the larger of two numbers is shown be
1* Function definition to return larger of two numbers *1 int maximum(int in, int n)
if (m > n) return In;
1* Return m as largest *1
1* Return n as largest *1
1.13.4Function calls After writing the functions, appropriate functions have to be invo ell to ge j b done from those functions. This invocation of a function is caIled.fiuwtio raJll For example, in the previous section, we have written a function maximumO 110 !the larger of two numbers. This function can be invoked using e ion I'TJlliin(j shown below: void maim)
printf("Enter the values for m and n\n"'); seanCe %d o/od",&m, &n);
res = maximum(m, n); printf("Maximum >
1* Function call which calls function maximum */
1.64 Q Introduction
Execution starts from the function maint>. After reading the values of m and n, the function is invoked using the statement:
The variables that are used while calling the function are called actual parameters. Next, control is transferred to the function maximums). The function fmds the larger of two items and control is returned back to the function maint> along with the result. The value returned is copied into the variable res and is displayed on the screen in function mainO. This isillustrated in the figure shown below: I-void ~ain()
prtntf(t'Enter m and n\n")·, scanf("%d %d",&m, &n)·
r:----->--t-, int maximum(int rn, int n)
if (m > n) return m; else
Q Systematic Approach to Data Structures using C 1.75
intj; for (j = 0; j -
2 bytes Fig. 4.5.1 Memory map for members of a structure Note: The address of a member = address of its immediate previous member + the size of its immediate previous member
4.24 ,!;!, Derived types - enumerated, Structure and Union Address of member name = 2000 Address of member roll number = 2000 + 10 = 2010 Address of member average_marks = 2010 + 4 = 2014 . Note: The address of each member is greater than the address of its previous member and hence, address of each member is different. Some times, the size of the structure will not be equal to-sum of sizes of the individual members. This is because of slack bytes. Now, let us see "yv'hat are slack bytes?" Definition: In some computers, the memory for the members of a structure is allocated in sequence based purely on the size of individual members. In some computers, the memory for the members of a structure is allocated at certain boundaries called "word boundaries". In such case, extra bytes are padded at the end of each member whose size is less than the largest data type so that the address of each member starts at the word boundary. These extra bytes that are inserted to maintain the boundary requirements are called slack bytes. These extra bytes do not contain any valid information and are useless and waste the memory. For example, if char, int, float and double are the data types of members of a structure, then a member whose type is double occupy more -memory. Assuming sizeof double is 8 bytes, then the address of each member is multiple of 8. Consider the structure declaration shown below: struct student
char int double
namej l O]; roll_number; average_marks;
1* Assume size of char is 1 byte *1 1* Assume size of int is 4 bytes *1 1* Assume size of double is 8 bytes *1
>a ; The size of each member of the structure is shown below: a.name
array of 10 characters
10 bytes 4 bytes
Sum of sizes of individual structure members
8 bytes 22 bytes
to Data Structures
Let us see "What is the size of structure if slack bytes are introduced?" If 2000 is the starting address of the variable a, then the starting address of each member depends on sum of sizes of previous members along with the word boundary and the complete memory map is shown below: Divisible by 8
2006 2008 2010 2012
2014 Divisible by 8
2022 Divisible by 8
2028 2030 2 bytes Fig. 4.5.2 Memory map showing slack bytes Note: The size of the structure is 32 bytes which is greater than the sum of sizes of each member. So, when slack bytes are used, the size of a structure is greater than or equal to the sizes of its individual members, Note: Data can be accessed much faster way if present in word boundaries. So, even though slack bytes do not contain valid information, they are useful so that data is available always in word boundaries and can be accessed very fast.
4.26 Q Derived types - enumerated, Structure and Union Nete: In the structure definition, double is the largest data type with size 8 bytes. So, the starting address of each member should be divisible by 8. Note: The starting address of each member is divisible by 8. But, we can access only the specified number of bytes of a member. The extra bytes that are not used are slack bytes. The shaded region represents the slack bytes. 4.5.2 Structure
The various operations can be performed on structures and structure members. Any operation that can be performed on ordinary variables can also be performed on structure members. But, some operations 'Cannot be performed on structure variables. The following sections deals with operations that are carried on structure and structure members \ 4.5.2.1 Copying of structure variables Copying of two structure variables is achieved using assignment operator. But, one structure variable can be assigned to another structure variable of the same type. Example: 4.5.2.1.1: Usage of assignment operators using structure variables. Consider the structure definition and declaration statements shown below: .1
char name[lO]; int salary; int id; > c, d;
Note: Observe that even though the members of both structures are same in number and type, both are considered to be of different structures. So, the statements a =b;
are valid. But, the following statements a=c; b=d; are invalid.
Q Systematic Approach to Data Structures using C - 4.27
4.5.2.2 Comparison of two structure variables or members In the previous section, we have seen that copying of two structure variables of same type is allowed. But, we should remember that comparing of two structure variables of same type or dissimilar type is not allowed. For example, the following operations are invalid, even though a and b are of the same type. a=b;. 1* Invalid: Comparison is not allowed between structure variables *1 a !=b; 1* Invalid: Comparison is not allowed between structure variables *1 However, the members of two structure variables of same type can be compared using relational operators. For example, if a and b are two structures, then the following relational operations are valid: Operation a.member l
Meaning Compare member! of a with member2 of b and return true if they are same, false otherwise Return true if the member! of a and member2 of b are not same and false otherwise.
a.member I != b.member2
Note: The arithmetic, relational, logical and other various operations can be performed on individual members of structures but not on structure variables. But, if we want to compare we can do so by comparing the individual members of a structure. 4.5.2.3 Arithmetic operations on structures The members of a structure are similar to anyother variables and so any operation that can be performed on a variable, the same operation can be performed on structure members also. So, members of a structure can be manipulated by using expressions and operators. For example, ++a.salary is equivalent to ++(a.salary) and &a.salary is equivalent to &(a.salary). The expression &a denotes the starting address of the structure variable. Some of the expressions involving the variable a and its members are shown below:
4.28 Q Derived types - enumerated, Structure and Union
Increment the salary before accessing its value.
Increment the salary after accessing its value
Access the address of a.salary
Access the beginning address of the structure
4.5.2.4 Difference between structures and arrays /
Now, let us see "What are the differences between arrays and structures?" Both arrays and structures are derived data types. The various differences between the two are: Arrays
An array IS a collection of related data elements of the same type. In other words, array is used to represent homogenous data An array items can be accessed by using its subscript or using de-referencing/indirection (*) operator for pointers
Structure IS a collection of variables of similar or dissimilar data type. In other words, structures are used to represent the heterogeneous data. Structure items can be accessed using ''." (read as dot operator) or "->" (called selection operator in case of pointers)
4.5.3 Pointer to Structures We know that a pointer is a variable which contains address of another variable. On similar lines we can have pointer to structures. Now, let us see "What is pointer to a structure?" Definition: A variable which contains address of a structure variable is called pointer to a structure. For example, consider the following declaration: typedef struct
char int float > STUDENT;
name[lO]; ro 11_number; average_marks;
Q Systematic Approach to Data Structures
STUDENT a; STUDENT *p; p=&a;
> Here, p is a pointer to a structure. Using this pointer, various members of the structure can be accessed using two methods:
Using de-referencing operator * and dot (.) operator Using selection operator (-»
4.5.3.1 Using de-referencing operator * and dot (.) operator If p is pointer to a structure, then the structure itself can be accessed using indirection operator as shown below: *p
1* Refers to the whole structure *1
Once the structure is accessed, each member of the structure can be accessed using dot operator as shown below: (*p).name 1* Access the name *1 (*p).roll_number 1* Access roll number *1 (*p ).average _marks 1* Access average marks *1 Note: The parentheses in all the three expressions are necessary. We should not omit the parentheses. For example, *p.name 1* Invalid way of accessing the member >1:1 *p.roll_ number 1* Invalid way of accessing the member *1 *p.average _marks 1* Invalid way of accessing the member *1 4.5.3.2 Using selection operator If P is pointer to a structure, then the members of the structure can also be accessed using selection operator denoted by -> (which is formed by the minus sign and
4.30 Q Derived types - enumerated,
greater- than symbol). Using this operator, various members of the structure can be accessed as shown below: 1* Access the name *1 p->name 1* Access roll number *1 p->roll_ number 1* Access average marks *1 p->average_marks Note: This method is preferred over the previous method. So, (*p ).name can be written as p->name (*p).roll_number can be written as p->roll_number (*p ).average _ marks can be written as p->average _marks 4.5.3.3 Simulation of digital clock Now, let us see how to design and write the program to simulate the digital clock. Design: A structure with three members representing seconds, minutes and hours is shown below: typedef struct
int int int > CLOCK;
1* Represent seconds *1 1* Represent minutes *1 1* Represent hours *1
where CLOCK is considered as user-defined data type. If the variable c can be declared as shown below: CLOCKc; The following condition and codes help us to simulate the digital clock: • If value of seconds reaches 60, then we reset the seconds value to 0 and increment minutes. The code for this case can be written as shown below: if (c->sec = 60)
,!;l Systematic Approach to Data Structures using C - 4.31
+ When minutes is being incremented, if value of minutes reaches 60, then we reset the minutes value to 0 and increment hours. The code for this case can be written as shown below: if (c->min = 60)
+ When hours is being incremented, if the value reaches to 24, it is reset to O. The code for this case can be written as shown below: if (c->hrs = 24) < c->hrs = 0; > So, the complete C program is shown below: Example 4.5.3.1: Program to simulate the digital clock #include /* Structure definition for the clock */ typedef struct < int hrs; int mm; int see; >CLOCK; /* Function to increment the time by one second */ void increment(CLOCK < clock ->sec++;
if (clock->sec = 60) < clock->sec = 0; clock ->t:nin++;
4.32 ~ Derived types - enumerated, Structure and Union if (clock->min = 60)
clock->min = 0; clock ->hrs++; if (clock->hrs = 24) clock->hrs = 0; >
/* Function to show the time */ void show(CLOCK *clock)
clock->hrs, clock->min, clock->sec);
CLOCK clock int 1
/* Initialize time to 11:58:57 */
for (i = 0; i ' or * operators are used to access the fields within the structure? 5. What is a structure? How does a structure differ from an array? How are structure members assigned values and are accessed? Explain. 6. Explain array of structures with example 7. What are nested structures? Explain with an example 8. Is it possible to have structures within structures? Explain with an example 9. Is it possible to return the value of a structure using return statement? If the values of two or more structures is needed in the calling function, what to do? Explain with an example. 10. Write a C program to add, subtract, multiply and divide two complex numbers. Each function should return a complex number after performing the respective operations. r 11. What is a union? How is it different from structure? With a suitable example show how union is declared and used in C. 12. What is the difference between structure and union? 13. Write a C program to arrange the student record based on increasing order ofro11 numbers, increasing order of marks, increasing order of their age. Assume the student record contains the following fields': name, age, branch, marks, roll number and address.
What are we studying in this chapter? '~~ e;;;: __
S.1 'Files and Classification
We know that the function scanf() is used to enter the data from the keyboard and printl'() is used to display the result on the video display unit. This works fine when the input data is very small. But, as the volume of input data increases, in most of the applications. we find it necessary to store the data permanently on the disk and read from it for the following reasons: • It is very di Ificult to input large volume of data through terminals • It is time consuming to enter large volume of data using keyboard. • When we are entering the data through the keyboard, if the program is -terminatcd for any of the reason or computer is turned off, the entire input data is lost. To overcome all these problems, the concept of storing the data in disks was introduced. Here, the data can be stored on the disks; the data can be accessed as and when required and any number of times without destroying the data. The data is stored in the form of a file. Now, let us see "What is a file? How the data is stored in a file?"
Definition: A file is defined as a collection
of related data stored in auxiliary devices such as disks, CDs etc. The data is recorded on the auxiliary devices using Os and 1s (called bits). The auxiliary devices will not assign any relationship between the various bits. The pictorial representation of data on auxiliary storage device is shown below: 01 00
001 0 0100 0011 0000 1101 0011 0001 0000 110 I
Note: EOF stands for End Of f.ile
• Classification of Files • Using Binary Files • Standard Library functions
Once we know the definition of file, let us see "What are the various types of files?" When the data stored in auxiliary device is read by the program, the data (stored in terms of as and Is) can be interpreted as either a text file or a binary file. Thus, there are two types of files as shown below: EOF Data on an auxiliary device
01000001 0100 0010 0100 0011 0000] 101 0011 0001 0000 1101 6
4 Binary File Thus, it is very clear that even though the data is stored in terms of as and 1s on a disk, wc can interpret them either as text file or binary file.
5.1.1 Text file Now, let us see "What is a text file?" Definition: A text file is the one where data is stored as a stream of characters that can b processed sequentially. In the text format, data are organized into lines terminated by newline character. The text files are in human readable form and they can be created and read using any text editor. Since text files process only characters, they can read or write only one character at a time. A newline may be "converted to carriage return and line feed character. Note: newline character = carriage return + linefeed Because of these translations, the number of characters written/read may not be the same as the number of characters written/read on the external device. Therefore, there may not be a one-to-one relationship between the characters written/read into the file and those stored on the external devices. For example, the data 2345 requires 4 bytes with each character occupying exactly one byte. A text file can not contain integers, floating-point numbers etc. To store the data such as integers, floating point numbers etc., they must be converted to their character-equivalent formats, For example, the data 2345 in text file is stored as sequence of4 characters '2', '3', '4' and '5'. The following figure shows • How 6 characters are entered from the keyboard • How the 6 characters entered from keyboard are stored in file t How the 6 characters stored in a file are displayed on the monitor/printer
0000 1101 0011 0001 00001101 [.
Note: In the above figure, the symbol.J represent the return key and its ASCIl character is osoo (13 in decimal). The ASCII values of A, B, Care Ox41 (65 decimal),Ox42 (66 in decimal), Ox43 (67 in decimal) respectively. The ASCII values of 1,2,3 etc. are Ox31 (48 in decima\) ,Ox32(49 in decima\) and so on. The symbol 6. represents end of file.
5.1.2 Binary file Now, let us see "What is a binary file?" Definition: A binary file is the one where data is stored on the disk in the same way
as it is represented in the computer memory. The binary files are not in human readable form and they can be created and read only by specific programs written for them. The binary data stored in the file can not be read using any of the text editors. For example, the data 2345 takes 2 bytes of memory and is stored as Ox0929 i.e., Ox09 is stored as one byte and Ox029 is stored as other byte. The number of characters written/read is same as the number of characters written/read on the external device. Therefore, there is one-to-one relationship between the characters written/read into the file and those stored on the external devices. Now the question is "What is the difference between a text file and a binary file?" TIle differences between these two types of files are shown below: Text file
1. Human readable format
1. Not in human readable format
5.4 Q Binary files 2. Data is stored as lines of characters with each line terminated by \n which may be translated into carriage return -I- line feed
2. Data is stored on the disk in the same III the way as it IS represented computer memory
3. Translation of newline character carriage return + line feed
3. No translation
4. Data can be read using any of the text editor
5. The number of characters written/read may not be the same as the number of characters written/read on the external device . ch as disk
5. The number of characters written/read is same as the number of characters written/read on the external device such as disk
6. There may not be a one-to-one relationship between the characters written/read into the file and those stored on the external devices.
7. The data 2345 requires
7. The data 2345 requires
4 bytes with each character requiring one byte. So, it is stored as Ox32, Ox33, Ox34, Ox35 (ASCII values) thus requiring 4 bytes
Data can be read only by specific programs written for them
one-to-one relationship between the characters written/read into the file and those stored on the external devices. IS
2 bytes and stored as Ox0929.The data 2345 is stored as Ox09 and Ox29 thus requiring 4 bytes.
5.2 Using Binary files Normally the binary files are associated
as shown in figure below:
Q Systematic Approach to Data Structures using C 5.5 Each rectangle in the figure represents a structure. At the end of a file there is a file marker (6) which denotes end of file (EOF) marker. The four steps that are used during the manipulation of binary files are shown below: Declare a file pointer variable Open a file
Steps in using the files
Read the data from the file or write the data into file Close the file
5.2.1 Declare a file pointer variable We know that all the pointer variable also pointer variable?" A structure of type FILE
variables are declared before they are used. Likewise, a file should be declared. Now, let us see "How to declare a file file pointer variable fp should be declared as a pointer to a as shown below:
#include FILE *fp;
/* Here, fp is a pointer to a structure FILE */
Note that rILE is the derived data type which is defined already in header file stdio.h. as a structure. The structure details are hidden from the programmer and this structure is used to store information about a file.
Note: The file pointer fp can be used either as a local or global variable. In the above syntax, the file pointer fp is used as a global variable. The file pointer fp can be used to open a file, update a file and to close a file in sequence. Analogy: The information of all the students in a college is maintained by the college office. The information of a particular student such as name, address, branch and semester details along with CET ranking, percentage of marks in PUC etc. is stored in a file. If we want to read, write or update the student details we have to open a file,
5.6 Q, Binary files update a file and finally close it. The same sequence of operations can be carried out with respect to files in C also. Here too, before updating a file, it has to be opened and after updating the file, it has to be closed.
Note: The first operation to be done before updating the file is opening a file. The last operation to be done after updating is closing the file.
5.2.2 States and modes of a file Before opening a file, let us see "What are the various modes in which a file can be opened/created successfully?" The various modes in which a file can be opened/created successfully along with meanings are shown below:
open a text file for reading
create a text file for writing
Append to a text file
open a text file for read/write
'.create a text file for read/write
append or create read/write
open a binary file [or reading
create a binary file for writing
append to an existing binary file
Open a binary file for read/write
Create a binary file for read/write
Append or create a binary file for read/write
Modes of a file
Note: It is clear from the above figure that the file can be either in read or write state. If the file can not be opened successfully or can not be created then it is an error and the file state will be error state. This results in three possible below: .
file states as shown
Q Systematic Approach to Data Structures
read state write state
Now, let us discuss each of the modes in detail: r (read mode) This mode is used for opening an existing file to perform read operation. The various features of this mode are shown below: • Used only for the text file • If the file does not exist, an error is returned IEOF • The contents of the file are not lost 1..-----------, '+' • The file pointer points to the beginning File contents 16
I File position after opening w (write mode) This mode is used to create a file. The various features of this mode
are shown below: . • Used only for the text file • If the file does not exist, a file is created. . • If the file already exists, the original contents of the file are lost • The file pointer points to the beginning EOF
Pile position after opening a (append mode) This mode is used to insert the data at the end of the existing file. The various features of this mode are shown below: • Used only for the text file • If the file does not exist, a file is created • If the file already exists, the file point er pomts to teen h d I EOF ' , 'V • The new data' is inserted at the end ~ File contents • Existing data can not be modified
File position after opening
5.8 g Binary files Note: lfwe have + as the suffix for the above modes, then in all the above three cases the file is opened for read/write operation with the same features as specified earlier. For example, r+ (read/write), w+Iread/write), a+(read/write at the end) rb (read mode) This mode is used for opening an existing file to perform read operation. The various features of this mode are shown below: + Used only for the binary file IEep + If the file does not exist, an error is returned r----------------, ~ + The contents of the file are not lost 6 File contents • The file pointer points to the beginning T---------------~1 File position after opening wb (write mode) This mode is used to create a file. The various features of this mode are shown below: + Used only for the binary tile + If the file does not exist, a tile is created. + If the file already exists, the original contents of the file are lost • The file pointer points to the beginning EOF
File position after opening ab (append mode) This mode is used to insert the data at the end of the existing file. The various features of this mode are shown below: + Used only for the binary tile +. If the file does not exist, a tile is created + If the file already exists, the file pointer points to the end + The new data is inserted at the end 1. ( )F + Existing data can not be modifiedf-;' ~ 1
File position after opening Note: Having a suffix -\- for the above three modes, then the tile is opened for read/write operation. The remaining features remain same. The modes rb+, wb+ and ab+ are same as r+b, w+b and a+b respectively.
~ Systematic Approach to Data Structures using C 5.9 Note: A mode with substring + is called update mode. This is because; the substring which is part of the mode as explained earlier represent read/write operation.
5.3 Standard library functions for files Now, let us see "What are the standard .library functions that are used for binary files?" The various standard file library functions that we discuss with, respect to binary files are shown below: File open and close functions ~-~ Block read and write functions Categories of tile functions . ---11---" File positioning functions
System file operations File status functions
Now, let us discuss each of these separately 5.3.1 File open and close functions Once we know various modes in which a file can be opened or created, let us see "How to open a file?" The file should be opened before reading a file or before writing into a file. The syntax to open a file for either read/write operation is shown below: . #include FILE *fp;
fp = fopen(char *filename, char *mode) where • fp is a file pointer of type FILE • filename holds the name of the file to be opened. The filename should be a valid identifier. • mode details are provided in section 5.2.2. This informs the library function about the purpose of opening a file. Return valuesThe function may return the following: • File pointer of type FILE if successful • NULL if unsuccessful
5.10 Q Binary files If the file pointer fp is not NULL, the necessary data can be accessed from the specified file. If a file cannot be opened successfully for some reason, the function retuins NULL. We can use this NULL character to test whether a file has been successfully opened or Hot using the statement: if (fp = NULL)
in opening the file\n");
> 1* Using fp access file contents *1
Now, let us see "When to close d how to close a file?" When we no longer need a file, we should close the file. This is the last operation to be performed on a file. A file can be closed using close function. This ensures that all buffers are flushed and all the links to the file are broken. Once the file is closed, to access the file, it has to be re-opened. If a file is closed successfully, 0 is returned otherwise EOF is returned. The syntax is shown below: #include void maim) < FILE *fp;
if( fclose(fp) = EOF)
in closing the file\n");
to Data Structures
ote: If a program is terminated, all the opened files will be closed automatically. But, as a programming practice, it is better to close all the opened files once we know that the file pointers are not required.
5.3.2 Block read and write (Block 1/0) functions We know that data are stored in the memory in the form ofO's and 1's. When we read and write the binary files, the data are transferred just as they are found in memory and hence there are no format conversions. Now, let us see "What are the functions that are required to transfer the block of data to/from binary files?" The various input and output functions that transfer block of data are shown below: Categories of I/O functions
Now, let us discuss each of these one by one.
5.3.2.1 File read - freadf) Now, let us see "What is the syntax of fread? How does the function work.')" This function is used to read a block of data from a given file. The prototype of freadi) which is defined in header file "stdio.h" is shown below: int fread (void *ptr, int size, int n, FILE *fp); Before executing the function, we have to pass the following parameters: • fp is a file pointer of an opened file from where the data has to be read from. • ptr: The data read from the file should be stored in memory. For this purpose, it is required to allocate the sufficient memory and address of the first byte is stored in ptr. We say that ptr now points to buffer. • n is the number of items to be read from the file. • size is the length of each item in bytes. Working: When the freadt) function is executed, the function reads n number of items, each of length size bytes (n * size bytes) from the file associated with fp. The data read from the file is copied into the memory location pointed to by ptr. Returns • Number of items successfully read • If no items have been read or when error has occurred or end-of-file encountered, the function returns 0 (zero).
5.12 Q Binary files Note: Since this function will not return EOF, we have to check for possible using feof'() or ferrort) functions.
Example 5.3.2.1.1: Read a floating point value from the file and store it in variable f. fread( &f, sizeof(float),
Example 5.3.2.1.2: C function to read 5 integers from the file and store it in array a. #include
> The pictorial representation
freadt) is shown below:
fp - before fread
fp - after fread
[JJJJ III:: . [JJJJ' III :' [JJJJ void maim)
1* Pointer to the input file name *1
1* Input file name *1 1* Holds the character read from file *1
int int int int
char_count = 0; blank count = 0; tab_count = 0; line_count = 0;
1* Holds 1* Holds 1* Holds 1* Holds
count count count count
all characters typed *1 blank characters *1 only tabs *1 lines *1
printf("Enter the file name\n"); scanf("%s" ,file_name);
1* Open file only in read mode *1 if ( (fp = fopentfile jiame,"r") = NULL) < printf("Error in opening the file\n"); exit(O); >1* read each character till end of file encountered *1 while ( ( ch = getc(fp) ) != EOF)
1* Update character count *1 if ( ch
if ( ch = '\t' ) tab_count++;
1* Update blank count *1 1* Update line count *1 1* Update tab count *1
fclose(fp); printf("Number printf("Number printf("Number printf("Number >
of characters = %d\n", char_count); of tabs = %d\n", tab_count); oflines = %d\n", line_count); of blanks = %d\n", blank_count);
Systematic Approach to Data Structures using C 5.35
5.4.2 fscanf'(), fprintft) Now, let us see "What is the use of fscanfi) function? Explain with syntax" The function of fscanf and scanf are exactly same. But, instead of getting the input from the keyboard, we get the input from the file specified. Because input is read from the file, extra parameter file pointer has to be passed as the parameter. Rest of the functionality of fscanf remains same as scanf. The syntax of fscanfl) is shown below: fscanf(fp, "control string", list); where • fp is a file pointer • format string and list have the same meaning as in scanfi) i.e., the variables specified in the list will take the values from the file specified by fp using the specifications provided in format string. Example 5.4.2.1: Explain what will happen if the following statement is executed. fscanf(fp, "%d %s %f', &id, name, &salary); Solution: After executing fscanf, the values for the variables id, name and salary are obtained from the file associated with file pointer fp. This function returns the number of items that are successfully read from the file.
Now, let us see "What is the use of fprintfi) function? Explain with syntax" The function of fprintf and printf are exactly same. But, instead of displaying the resulton the screen, the result is sent to the file. Since file is used, extra parameter file pointer has to be passed as parameter. Rest of the functionality of fprintf remains sameas printf. The syntax of fprintfi) is shown below: fprintf'(fp, "format string", list); where • fp is a file pointer associated with a file that has been opened for writing. • format string and list have the same meaning as in printf() function i.e., the values of the variables specified in the list will be written into the file associated with file pointer fp using the specifications provided in format string.
5.36 Q Binary files Example 5.4.2.2: Explain what will happen if the following statement is executed. fprintf(fp, "%d %s %f', id, name, salary); Solution: After executing fprintf, the values of the variables id, name and salary are 'written into the file associated with file pointer fp. This function returns the number of items that are successfully written into the file.
Example 5.4.2.3: Structure defmition for the following table: USN +ve integer
Name 25 characters
Marks! +ve integer
Marks2 +ve integer
Marks3 +ve integer
Solution: The above table can be represented using structure definition as shown b elow: typedef struct < int char int int int >STUDENT;
usn; name[20]; marks l ; marks2; marks3;
Note: In the above definition, STUDENT is the user-defined data type
Example 5.4.2.4: C function to search for key_usn in the table shown in example 5.&2.3. 1* function to search for USN *1 int search_record(int key_usn, FILE *fp)
to Data Structures
1* While not end of file *1 for (;;)
1* Obtain the student details from the file *1 fscanf(fp,"%d %s %d %d %d", &st.usn, st.name, &st.marks1, &st.marks2, &st.marks3); if (feof(fp)) break;
1* If end of file quit *1
if (key_usn = st.usn) return 1;
1* search successful *1
1* Search failed *1
Example 5.4.2.5: C function to append the student record at the end of file for the structure shown in example 5.6.2.3. -
* To append the student record at the end of the file *1 void append Jecord(FILE *fp) < . STUDENT
printf("USN printf("Name printf("Marks printf("Marks printf("Marks
1* Holds the details of a student *1 scanf("%d" ,&st.usn); scanf("%s" ,st.name); scanf("%d",&st.marks1 ); scanf("%d",&st.marks2); scanf("%d" ,&st.marks3);
1* Write the student details into the file *1 1* Note: Insert \n at the end of each record as a delimiter *1 fprintf(fp,"%d %s %d %d %d\n", st.usn, st.name, st.marks1, st.marks2, st.marks3);
Example 5.4.2.6: C function to display the contents of the file for the structure shown in example 5.6.2.3. void display Jecords(FILE
5.38 Q Binary files printf("USN for (;;)
fscanf(fp, "%d %s %d %d %d", &st.usn, st.name, &st.marks1, &st.tnarks2, &st.marks3); if (feof(fp)) break; printf("%-5d %-10s %-5d\t %-5d\t %-5d\n", st.usn, st.name, st.marks1, st.marks2, st.marks3); >
Example 5.4.2.7: The complete C ·program to create a sequential file with at least 5 records, each record having the following structure: USN +ve integer
Name 25 characters
Marks 1 +ve integer
Marks2 +ve integer
Marks3 +ve integer
where USN stands for University Seat Number, Marksl, Marks2 and Marks3 are the marks scored by a student in subjectl , subject2 and subject3 respectively. Let us write necessary functions to • Display all the records in the file • To search for a specific record based on USN. Display suitable message #include #include #include typedef struct
int char int int int > STUDENT;
usn; name[20]; marks1; marks2; marks3;
~ Systematic Approach to Data Structures using C 5.39 1* Include: Example 5.4.2.4: C function to search for the key USN *1 1* Include: Example 5.4.2.5: C function to append the student record *1 1* Include: Example 5.4.2.6: C function to display the student records *1 void maint)
STUDENT char FILE int int int
st; fname[10]; *fp; key_usn; flag; choice;
1* Student details are stored *1 1* File name where student info is stored *1 1* File pointer to access the contents*1 1* University seat number *1 1* Holds either true or false *1 1* Select the various options add,search,display *1
printf("Enter the file name\n"); scanf("%s" ,fname); for (00) ,
printf(" 1:Insert Record 2:Search record\n"); printf("3:Display record 4:Quit\n"); printf("Enter the choice\n"); scanf("%d" ,&choice); switch( choice) < case 1: fp = fopen(fname,"a+"); if (fp = NULL)
append _record( fp); fclose(fp); break;
5.40 Q Binary files case 2: fp = fopen(fuame,"r"); if (fp = NULL)
printf("File open failed\n"); break; > printf("Enter USN:"); scanf("%d" ,&key _usn); flag = search _record(key _usn,fp); if (flag = 0) printf("Unsuccessful search \n "); else printf("Successful search\n"); fclose(fp); break; case 3: fp = fopen(fuame,"r"); if (fp = NULL) < printf("File opened failed\n"); break; >display Jecords(fp); fclose(fp ); break; default: exit(O); > > >
,!;lSystematic Approach to Data Structures using C 5.41 Note: Even though the program is lengthy, the program is straightforward
and easier to understand. By looking at the comments the reader is required to understand the logic.
5.5 Command line arguments" The operating systems such 'as MS-DOS provide a command line interface. Now, we shall see "What is command line interface?" The interface which allows the user to interact with the computer by providing instructions in the form of typed commands (which are in text form) is called command line interface. In the command prompt (see the figure below), the user types the commands. These commands are made up of equal-sized alphanumeric and other symbols. Keyboard is the input device to enter these commands. The screen shot of MS-DOS (MicrnSoft Disk Operating System) is shown below:
The above function ,COPY accepts the file Tl.C and copies the T2.C. In the command prompt, if the .user types "COpy function of COpy program accepts three parameters namely These parameters are called command line arguments ..Now, command line arguments?"
the contents, of Tl.C to ,Tl.C T2.C" the main COPY, Tl.C and T2.C. we shall see "What are
Definition: As parameters
are passed to the functions, on similar lines, parameters can also be passed to the function main whenever the program is invoked from the command prompt. The words that are typed at the command prompt are passed to the function main of the program which is being invoked at the command prompt.. These arguments that are passed by the operating system to the function main when the program is invoked are called command line arguments. To access the command line parameters the function main should have the followi~g format; ';" i«. ;,', ' ! . void main(int argc,
5.4~ Q Binary files where • argc is an integer value. Here, argc means argument count • argv is an array of strings. Here, argv means argument vector. Those strings that are part of the command prompt are copied into argv[O], argv[l] and so on. Example 5.5.1: Argument vector and argument count with respect to the command: C:\> COPY Tl.C T2.C argv[O]~ argv[l]~ argv[2]~
Since there are three strings at the command line prompt, integer variable argc has the value 3. The value for the variable argc is not explicitly passed as the parameter and argv[O] will always have the first parameter i.e, program name. In our example, argv[O] will have the string "COPY".
5.5.1 Display contents of file Now, let us write a program to display the contents of file. The file if specified in the command line has to be opened and the contents have to be displayed. If file is not specified in the command line, the user should be prompted for the file and that file should be opened and displayed. The complete program is shown below Example 5.5.1: C Program to accept a file either through command line or as specified by user during run time and displays the contents #include #include #include void main(int < FILE char char
argc, char *argv[]) *fp; fname[lO]; ch;
1* File pointer used to display a file *1 1* File to be opened and displayed *1 1* Holds the character to be displayed *1
to Data Structures
printf("Enter the file name:"); scanf("%s" ,fname);
/* No command line file name
/* Command line file exists */
fp = fopen(fname, "r"); . if (fp = NULL)
> priotf("The contents of the file are:\n"); \n") ,. prlo. t4"(" I' --------------------------/* File opened successfully and display the contents */ while ( (ch = getc(fp)) != EOF)
Note: Let us assume, the file name of the above program is "disp.c". Before executing this program make sure that the file by name "Hello" exists in the current directory from where we are running the executable file "disp". Also make sure that some text is stored in the file "Hello". Use any editor, create a file called "Hello" and enterthe following text: Hello how are you This is the first program using command line arguments Good luck Have Fun Finally save the program in the file name "Hello". Now, compile and execute the program as shown below:
5.44 Q Binary files Output
C:\>disp hello The contents of the file are: Hello how are you This is the first program using command line arguments Good luck Have Fun Oufput C:\>disp Enter the file name: Hello The contents of the file are: Hello how are you This is the first program using command line arguments Good luck Have Fun
Note: In the first output argv[O] corresponds to disp and argv[ 1] corresponds to the string "Hello". In the second output argv[l] is NULL. In this ,program, in the beginning of the function main we are checking whether a file has been specified in the command line. If file is not specified, the value of argc will be 1 and so the user is prompted to enter the file name during run time. But, if the value of argc is greater than 1, the control comes to else statement and the file specified in the command line is copied to fname which will be used for opening. Rest of the statements in the program are self-explanatory. . 5.5.2 Obtain text and create file (use only command line parameters) Let lis consider another program which accepts a file name followed by a text only through command line parameters. The text appearing in the command line should be stored in a file which is also passed as a command line parameter. The corresponding C program is shown below:
roach to Data Structures usin C 5.45
Example 5.5..2: C Program to accept a file name and text through command line arguments and create a file with the text #inc1ude #inc1ude void main(int argc, char *argv[])
/* File pointer used to display a file */ /* To access command line parameters */ /* Temporary storage */
FILE *fp; int 1; char sp-[30]; if (argc = 1)
name missing in the command iine\n");
name should be followed by some text\n");
> /*Command line has file name and text */ /* So, create and open the file */ fp = fopen(argv[l], "w"); if (fp = NULL)
file can not be opened for writing\n");
/* Write text in command line into file */ for (i = 2; i Gfsymbol) ) postfix[j++] = s[top--];
I Infix to postfix
if (F(s[topD != Gtsymbolj ) sf ++top] = SYmbol; else top--; >
Output configuration . Stack #
The complete C function to convert from infix expression to postfix expression is shown below:
Example 6.4.2.4: C function to convert from infix expression into postfix expression void infixyostfix( char infix[], char postfixjj) < int top; 1* points to top of the stack *1 int 1* Index for postfix expression *1 J; 1·, int 1* Index to access infix expression *1 char char
top = -1; s[++top] j =0;
1* Acts as storage for stack elements *1 1* Holds scanned char from infix expression *1 1* Stack is empty *1 1* Initialize stack to # *1 1* Output is empty. So, j = 0 *1
6.24 Q Stacks fore i = 0; i G(symbol) )
!= G(symbol) s[ ++top] = symbol;
1* push the input symbol *1
1* discard '(' from stack *1
1* Pop remaining symbols and place 1* them in postfix expression *1
1* Attach NULL char .at the end to frame a string *1
The complete C program shown below:
a valid infix expression
Example 6.4.2.5: C Program to convert an infix expression
1* Include: Example 6.4.2.3: Precedence functions F and G *1 1* Include: Example 6.4.2.4: Function to convert from infix to postfix *1
to Data Structures
I Input and output I Enter a valid infix expression I (a+b)* c-(d-e))" (f+g) I The postfix expression is I ab+c=de=fg+? I Enter a valid infix expression I a"b*c-d+e/f/(g+h) I The postfix expression is I ab c*d-ef/l!h+/+
Let us trace the above program for the given expression: ( A + ( B - C ) Example 6.4.2.6: The complete trace of the program for the expression: (A+(B-C)*D) F(s[topl) > C(S) mbol)
(-1 0) Pop C (2) 0) Pop -
(0 = 0) Pop ( don't place in postfix. expr.
/* Pop from stack and place into prefix */
• Once the condition in while-loop is failed, if the precedence of the symbol on top of the stack is not equal to the precedence value of the current input symbol, push the current symbol on to the stack. Otherwise, delete an item from the stack but do not place it in the prefix expression. The code for this statement can be of the form if (F(s[top]) != G(symbol) ) s[++top] = symbol; else top--;
/* Push symbol on the stack */ /* Drop an element from stack */
Not: These two steps have to be performed for each input symbol in the infix expression,
6.30 Q Stacks The complete C function to convert from infix expression to postfix expression is shown below: Example 6.4.3.4: C function to convert from infix expression into prefix expression void infix-'prefix( char infix]'], char prefix[])
int char int int char
1* Points to top of the stack *1 1* Acts as storage for stack elements *1 ;* Index for prefix expression *1 1* Index to access infix expression *1 1* Holds scanned char from infix expression *1
-.top = -1; s[++top] = '#'; j =0;
1* Stack is empty *1 1* Initialize stack to # *1 1* Points to first char of prefix expression *1 1* Reverse the infix expression *1
fore i = 0; i G(symbol) )
1* Pop from stack and place *1 1* into prefix *1
if ( F(s[top]) != G(symbol) ) s[++top] = symbol; else
1* push the input symbol *1 1* discard '(' from stack *1
1* Attach NULL char at the end of string *1
1* To obtain the actual prefix expression *1
to Data Structures
The complete C program to convert a valid infix expression to postfix expression is shown below: Example 6.4.3.5: C program to convert from infix expression into prefix expression #include #include l" Include: Example 6.4.3.3: Two functions F and G */ /* Include: Example 6.4.3.4: Function to convert from infix to prefix */
void mainO Input and Outputs
char infix[20]; char prefix[20]; printf("Enter a valid infix expression\n"); scanf("%s" ,infix); infix~refix( iniix,prefix); printf("The prefix expression is\n"); printf("%s\n",prefix);
Enter a valid infix expression ((a+b )*c-( d-e»)"(f+g) The prefix expression is A_*+abc-de+fg Enter a valid infix expression a Ab *c-d+e/f/ (g+h) The prefix expression is +-*Aabcd//ef+gh
Note: The precedence values of the operands in functions G and F in example 6.4.2.3 are 7 and 8. The same values are used in example 6.4.3.3. This is because the order of the operands in the prefix, postfix and infix expressions are same. Only the order of the operators changes. So, care should be taken while taking the precedence values for the operators. For example, consider the following expressions: a+b*c abc*+ +a*bc
( Infix expression) ( Postfix expression) ( Prefix expression)
If we look at above expressions, the operands a, band c appear in the same sequence where as the operators are not is same sequence. So, the precedence value of the operands is same, but the precedence values of operators are different while converting from infix to postfix and from infix to prefix.
6. 2 ~ Stacks 6.4.4 Evaluation of Postfix expression Let us see "What is the problem in evaluatmg the infix expressions? What is the need for evaluating postfix/prefix expressions?" The evaluation of infix expression is not recommended because of the following reasons: . • Evaluation of infix expression requires the knowledge of precedence of operators and the associativity of operators. • •
The problem becomes complex, if there are parentheses because they change the order of precedence.
in the expression
During evaluation, we may have to scan from left to right and right to left ~ repeatedly thereby complexity of the program increases.
All these problems can be' avoided if the infix expression is converted to its corresponding postfix or prefix expression and then evaluate. Evaluation of a postfix expression or prefix expression is yery simple. Now, let us see "How to evaluate the postfix expression?" The postfix expression can be evaluated using the following procedure: • Scan the symbol from left to right • If the scanned symbol is an operand, push it on to the stack • If the scanned symbol is an operator, pop two elements from the stack. The first popped element is operand2 and the second popped element is operand 1. This can be achieved using the statements op2 = s[top--]; /* First popped element is operand2 *i opl = s[top--]; 1* Second popped element is operand l *1 • Perform the indicated operation res = op 1 o<> op2
1* op is an operator such +, -, I,
• Push the result on to the stack. • Repeat the above procedure till the end of input is encountered. The algorithm or pseudocode to evaluate the postfix expression is shown below: Example 6.4.4.1: Algorithm to evaluate the postfix expression while end of input is not reached do (
1* Access the position of topmost element *1
1* To access the top most element *1
Let us implement stacks using structures also. We know that the stack is empty, if the position of the top most element is -1 .. The function is_ emptyt) which returns true whenever the stack is empty and returns false whenever the stack is not empty is' shown below: Example 6.5.1: Function to check whether the stack is empty or not
retum-t: 1* Stackempty+/ 1* Stack is not empty *1
The function is MIO retUrns true if stack is full and returns false if the stack is not full. This function is shown below: . Example 6.5.2: Function to check whether the stack is full or not
int is_ful1(STACK =s)
·1*. Stack is full *1 return 0;
1* Stack is not full *1
The function to insert an integer item into the stack is shown below:
to Data Structures using C.- 6.55
Example 6.5.3: Function to insert an integer item into the stack void push(int item, STACK *s) < if (is_full(s) ) < printflvStack Overflowin"); return; >s->top++; s->items[ s->top]
/* Update top to point to next item */ /* Insert the item into the stack* /
The function to insert a character item into the stack is shown below: Example 6.5.4: Function to insert a character item into the stack void push(char item, STACK *s) < if (is_full(s) )
printf(tlStack Overflowm"); return; >
s->top++; s->items[ s->top] = item;
/* Update top to point to next item */ /* Insert the item into the stack'v
The function to delete an integer item from the stack is shown below: Example 6.5.5:Function to delete an integer item from the stack intpop(STACK *s) < iot item;
6.56 Q Stacks if ( is_ empty( s) )
item = s->items[s->top]; s->top--;
1* Access the top element *1 1* Update the pointer to 'point to previous item */
1* Return the top item to the calling function */
The function to delete a character item from the stack is shown below: Example 6.5.6: Function to delete a character item from the stack char pop(STACK *s)
char item; if (is_empty(s) )
item = s->items[s->top]; s->top--;
1* Access the top element *1 1* Update the pointer to point to previous item *1
1* Return the top item to the calling function *1
The program to display the contents of stack is shewn below: Example 6.5.7: Function to display the contents of the stack void display(STACKtfsf
,!;l Systematic if (is_empty(&s)
to Data Structures
contents of the stack\n");
for (i = 0; i top++; 1* Update top to point to next item *1 s->items[ s->top] = item;
1* Insert the item into the stack* I
1* Function to delete an item of type double from stack *1 double pop(STACK *s)
double item; item
's-:>top--; return item;
1* Access the top element *1 1* Update the pointer to previous item *1 1* Return the top item *1
1* function to evaluate *1 double op(char symbol, double opl, double op2)
Design: Let us design the program to compute factorial of a number. According to the definition, if n >0, n! can be computed as shown below: 1*2
The above series can be multiplied as shown below: 1
From the above figure we can write the following steps Initial: Step 1: Step ~: Step 3:
fact fact fact fact
--+ fact = fact * i; for i = 1, 2 , 3 , 4 , to n
In the recursive version, we let the function fact call itself, each time with a different set of parameters. Observe that recursive solution does not need a loop. Because, recursion is itself repetition. The main program to compute factoria] is shown below: Example 7.1.2.2: C Program to find the factorial of N #include /* Include: Example 7.1.2.1:Function to compute factorial ofn *1 void mainf)
int n; printf(t'Enter nxn''): scanf(If%dlf,&n); printft'The
I Input I Enter n I 5 I Output I Factorial
Note: Comparing iterative function (example 7.1.1.1) and recursive function (example 7.1.2.1), we know that • Recursive function is much simpler. • No loops are present. Only simple if statement which returns either 1 or product of two values using recursion. 7.1.3 How recursion works Let us visualize how the control glows from one function call to another call. The figure 7.1 shows exactly what happens when recursive function factt) gets called. The execution sequence for the above factorial function is shown below.,
7.6 Q Recursion void maint)
1 int fact(int n)
Fig 7.1 Ste sin executin
a recursive function
a. The first time when function factt) is called, 3 is passed to n. b. Since n is not 0, the if statement is skipped and facn) is called again with argument n-l i.e., 2. c. Since n is not 0, the if statement IS skipped and factt) IS called agam with argument n-I i.e., l. d. Since n is not 0, the if statement IS skipped and factt) IS called again with argument n-I i.e., O. e. Since n is 0, control goes previous call with value 1 and 1* 1 = 1 is computed and sent to the previous point of invocation. f. The resulting value 1 is passed to the point of previous invokation and 2* 1 = 2 is computed and sent to the previous point of invokation. g. The resulting value 2 is passed to the point of previous invokation and 3*2 = 6 is computed and sent to the previous point of invokation. h. The resulting value 6 is passed to the point of previous invocation and 6 is copied into variable n in the main program. Now,llet us see "How recursion works?" When a function is called, C allocates the memory space in the stack (called stackframe) and stores the following items in the stack: • The parameters passed to the recursive function • Local variables of the calling function
to Data Structures
The return address so that after executing the function, control should be returned back to the calling function The variable that receive the value from the recursive function.
For each call of the function, the corresponding stackframe consisting of above items is placed on top of the stack and then removed from the stack when the execution of the called function is completed as shown below: Step 1:
Stack empty Calls
Stack after 1st call framel Step 3:
Stack after 1st call is executed
Step 6: Stack after
Stack after 2nd call is executed
framel frame21 Step 4:
Rerrns Stack after 3rd call Fig 7.1 Sequence
After 3rd call is executed
of events that take place during function
Once we know how recursion works, the next question is "How to design recursive functions?" Observe the following points from the factorial function:
+ Each time the function fact is called, the size of the problem is reduced. Here, the value of n is reduced by 1. This is often called general case. + Finally, we solve the problem by returning the value 1 to the calling function. This is called base caseor base/terminal condition. otc: Every recursive call must solve one part- of the problem using base case or reduce the size of the problem using general case. Now, let us see "What is base case? What is a general cease?" Dcfinition: A base case is a special case whose solution can be obtained without using recursion. This is also called base/terminal condition. Each recursive function must have a base case. A base case serves two purposes: +_ It acts as terminating condition. + The recursive function obtains the solution from the base case it reaches. For example, in the function factorial, fact of 0 is 1 is the base case or terminal condition. Definition: In any recursive function, the part of the function except base case is called general case. This portion of the code contains the logic required to reduce the size of the problem so as to move towards the base case or terminal condition. Here, each time the function is called, the size of the problem is reduced. For example,in the function fact, n*fact(n-l) is general case. By decreasing the value of n by 1, the function fact is heading towards the base case. Once we reached the base case, the solution begins. We know one part of the answer and can return that part of the answer to the more general case. As we solve each general case, we are able to solve the next higher general case and move towards the most general case which is the original problem as shown below:
Decompose the problem from top to bottom
Arrive at the solution
Compute the solution from bottom to top
~ Systematic Approach to Data Structures using C - 7.9 ote: In our factorial program, base case is fllCt(()) and general case is n*fact(n-l). So, the general rules that we are supposed to follow while designing any recursive algorithm are: • Determine the base case. Careful attention should be given here, because: when base case is reached, the function must execute a return statement without a call to recursive function. • Determine the general case. Here also careful attention should be given and see that each call must reduce the size of the problem and move it towards base case. • Combine the base case and general cascinto a function. otc: A recursive function should never generate infinite sequence of calls on itself. An algorithm exhibiting this sequence of calls will never terminate. If a base case does not exist, no recursive function can ever be computed. 7.2 Fibonacci series Now, let us see "What are Fibonacci numbers?" Definition: The Fibonacci numbers are a series of numbers such that each number is the sum of the previous two numbers except the first and second number. These numbers are named after an Italian mathematician "Leonardo Fibonacci" who lived in earlythirteenth century. The Fibonacci numbers are shown below: 0, 1, 1,2,3, 5, 8, 13,
Now, let us see "What is the base case and general rase to compute Fibonacci numbers?"To write a recursive defmition we should know the base case and general case. Base casc: Fib(O) = O> These numbers are given. Since the solution already exists it Fib(l)
is the base case
General case: NthFibonacci number = N-l thFibonacci number + N_2"d Fibonacci number i.e., Fib(n) = Fib(n-l) + Fib(n-2) ow, we know "What is the recursive definition to compute a Fibonacci number?" Therecursive definition to find nthFibonacci number can be written shown below:
7.10 Q Recursion
The way to find fib(4) is shown below: The thick arrows represent either a call to function fibt) or to the value. The dotted arrows point to the result after computation. The iterative technique for this is much more efficient than the recursive technique. fib(5) = 3
The C function to fmd the nth Fibonacci number using recursive definition is below: Example 7.2.1: C Function to fmd nth Fibonacci number int fib(int n)
if ( n = 0 ) return 0;
/* Base case: l" number */
if ( n = 1 ) return 1;
/* Base case: 2nd number */
return fib(n-l) + fib (n-2);
/* General case: Computation of */ /* subsequent Fibonacci numbers */
The C program to display nth Fibonacci number is shown below:
to Data Structures
Example 7.2.2: C program to display nth Fibonacci number #include
1* Include: Example 7.2.1: To compute nth Fibonacci number *1 void maint)
int n; printf("Enter n\n"); scanf("%d",&n); printf("fib(%d)
I I I Input I Enter n I 6 I Output I Fib(6) = 8 I.
Example 7.2.2: C program to display n Fibonacci numbers #include
General case: GCD(M,N) = GCD( ,M) GCD(M,N) = GCD(N, M % N)
So, "What is the recursive definition to compute GCD of two numbers?" The recursive definition to compute GCD of two numbers M and N using EUCLID's algorithm is shown below:
The C function to compute GCD of two numbers for the above recursive definition can be written as shown below: Example 7.2.1: C function to compute GCD of two numbers (Euclid's algorithm) int gcd(int m, int n)
if(m high) return -1 ;
/* Base case: Item not found */
mid = (low + high) /2;
/* compute the position of middle item */
/* Base case: Item found */
1* General case: to search left or right part */ if (key big) return a[n]; else return big; The above statement is repeatedly executed corresponding c function is shown below: Example 7.6.1: C functionto
for the values ranging
find largest ofn elements
from 1 to n-I. The
in an array(Recursion)
/* General case: */ /* Recursively find big */
if (a[n] > big) return
/* Base case: Return 1st item as big */
1* Return the largest number
The complete program below:
to read n elements
biggest element is shown
Example 7.6.2: C function to find largest ofn elements in an array(Recursion) #include
1* Include: Example
7.6.1: To compute the largest ofn numbers */
7.22 Q Recursion printf("Enter the numbers to sort\n"); scanf("%d" ,&n); printf("Enter n items\n"); for (i = 0; i r)
> printfC"The element deleted is %d\n",q[(f)++]);
1* Initialize to queue empty conditions *(
Note: After deleting an item, it may so happen that queue may be empty. So, immediately after deleting an element, if queue is empty, it is better to initialize f = 0 and r = -1 as shown in the above function. This is the initial status of queue when no items are inserted and it indicates that queue is initially empty. Now, let us write the above function without using global variables and by passing appropriate parameters. Note that f and r contents changes as we delete the items. So, they should be declared as pointers. The complete C function (by passing parameters) is shown below: Example 8.2.1.2.2: C function to delete an integer item (by passing parameters) void delete_front(int q[], int *f, int *r)
element deleted is %d\n",q[(*f)++]);
if (*f> *r) *f= 0, "r = -1; I
8.8 ~ Queues 8.2.1.3 Display queue contents In the display procedure, if the queue already has some items, all those items are displayed one after the other. If no items are present, the appropriate error message is displayed. Let us design the display function. Design: Consider the following situation where 4 items were inserted and first item has already been deleted.
Usually, the contents of the queue are displayed from the front end and moving towards right till we get the rear end. So, first item to be displayed is 20, next item to be displayed is 30 and final item to be displayed is 40. This can be achieved using the following statements: Output 20
Design printf("%d\n"'!IDl ); printf("%d\n", [2); printf("%d\n", 3);
In general, we can use printf("%d\n",
Note: i = 1 to 3 i = fto r
Note: Please note how the value of i change from f to r (i = 0 to r is wrong). Now, the code takes the following form: for (i = f; i r)
/* Display contents of queue */ printf("Contents of the queue\n"); for (i = f; i r)
printf("Contents of queue is\n"); for ( i = f; i front a->rear a->q The item at the front end can be accessed using a->q[ a->front] and the item at the rear end can be accessed using a->q[ a->rear] Note: We know that initial values of front and rear are 0 and -1 respectively. Queue is empty whenever front is greater than rear. Example 8.3.1: C function to insert an item at the front end of queue void insert_front(int item, QUEUE *a)
if (a->front = 0 && a->rear = -1 ) a->q[ ++(a->rear)] = item; else if ( a->front != 0 ) a->q[ --(a->front)] = item; else printff'Tront insertion not possible\n"); >
/* Case 1: of section 8.2.2.1 */ /* Case 2: of section 8.2.2.1 */ /* Case 3: of section 8.2.2.1 */
to Data Structures
Note: The design aspects of dequeue are provided in the section 8.2.2. The function to insert an item at the rear end of the queue is shown below: Example 8.3.2: C function to insert an item at the rear end of queue void insertrearfint item, QUEUE *a) < if ( a->rear = QUEUE _ SIZE-l )
1* Is right insertion possible *1
insertion not possible\n");
1* Increment rear and insert item *1
The function to delete an item from the front end of the queue is shown below: Example 8.3.3: C function to delete an item from front end of queue void delete_front(QUEUE *a) < if ( a->front > a->rear )
1* Check for underflow *1
> !* Access first item and delete *1 printf("The element delted is %d\n",a->q[a->front++]); if (a->front> a-> rear) < a->front = 0; a->rear = -1; >
1* Queue empty *1 1* Reset to initial values *1
8.34 Q Queues The function to delete an item from the rear end of the queue is shown below: Example 8.3.4: C function to delete an item from rear end of queue void delete Jear(QUEUE
1* Check for underflow *1
> " 1* Access the last it m and delete *1 printf("The deleted element is %d\n",a->q[a->rear--]); if (a-c-Iront > a-> rear)
a->front = 0; a->rear =. -1;
1* Queue empty *1 1* Reset to initial values *1
The function to display the contents of the queue is shown below: Example 8.3.5: C function 10 display the contents of queue void display(QUEUE *a.)
int i; if ( a->fiont > a.->rear)
1* Check for queue empty *1
coni nts of queue\:n"); for ( i = a->fiont; i rear; i++) printf("%d\n":a->q[i]);
1* Display Q contents *1
to Data Structures
The main function to implement double-ended queue is shown below: Example 8.3.6: C program to implement dequeue using structures #include #include #define QUEUE_SIZE
typedef struct < int q[QUEUE_SIZE]; int front; int rear; >QUEUE; /* Include: Example 8.3.1: C function to insert an item at the front end of queue */ /* Include: Example 8.3.2: C function to insert an item at the rear end of queue */ /* Include: Example 8.3.3: C function to delete an item from front end of queue */ /* Include: Example 8.3.4: C function to delete an item from rear end of queue */ /* Include: Example 8.3.5: C function to display the contents of queue*/ void maim) < QUEUE a; int item.choice; a.front = 0; a.rear = -1; for (;;)
printf(" 1:Insert front 2:Insert rear\n"); printf("3:Delete front 4:Delete rear\n"); printf("S:Display 6:Exit\n"); printf("Entcr the choice\n"); scanf("%d" ,&choice);
8.36 Q Queues switch ( choice)
case 1: printf("Enter the item to be, inserted\n"); scanf("%d", &item); insert_front(item, &a); break; case 2: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); insert_rear(item, &a); break; case 3: delete _front( &a); break; case 4: delete_rear(&a); break; case 5: display( &a); break; default: exit(O); > > >
8.4 Circular queue using structures l
The design detail of circular queue is already discussed in section 8.2.3. The various attributes associated with circular queue are: front end identified by f, the rear end identified by r, the number of elements in queue identified by count and the storage for the items inserted which is identified by q. The structure declaration for this can be of the form:
Systematic Approach to Data Structures using C - 8.32
q[QUEUE _ SIZE]; count; ,
> QUEUE; Note: If there is a declaration of the form QUEUE a; the value associated with each attribute of the structure can be obtained using' .' operator and if there is a declaration of the form QUEUE *a; the value associated with each attribute of the structure can be obtained using' :->' operator as discussed in the previous section. The C function to insert an item into circular queue is shown below: Example 8.4.1: Function to insert an item at the rear end void insert_rear(int item, QUEUE *a)
if ( a->count = QUEUE_SIZE)
/* Check for overflow */
a->r = (a->r + 1) % QUEUE_SIZE; a->q[a->r] = item; . (a->count )++;
/* increment rear pointer */ /* Insert the item */ /* update the counter */
Thefunction to delete an item from circular queue is shown below:
8.38 ~ Queues Example 8.4.2: Function to delete an item from th front end of circular queue void delete_front(QUEUE *a) < if ( a->count = 0 )
/* Check for underflow */
/* Access the item */ ._printf("The deleted element is %d\n",a->q[a->f]); a->f= (a->f + 1) % QUEUE_SIZE; (a->count)--;
/* Point to next first item /* update counter */
> The function to display contents of circular queue is shown below: Example 8.4.3: Function to display the contents of circular queue void display(QUEUE *a)
int i; if ( a->count =0 ) < printf("Q is empty\n"); I return; >printf("Contents of queue is\n"); for ( i = 1; i q[f]); f= (f+ 1) % QUEUE_SIZE;
/* access the item */ /* Point to next item */
The complete program to implement circular queue using structures is shown below:
Q Systematic Approach
to Data Structures
Example 8.4.4: C Program to implement circular queues using structures #include #include #define QUEUE_SIZE 5 typedef st ruet
/* Include: Example 8.4.1: Function to insert an item at the rear end *1 /* Include: Example 8.4.2: Function to delete an item from circular queue *1 /* Include:ExampJe
8.4.3: Function to display the contents of circular queue */
int choice, item; QUEUE a; a.f= 0; a.r=-l; a.count = 0; I" quen
printf(" 1:lnse t printtC'3:D'splay priDtf("Entu the scan .(" fod", "ell
c: lcl 1 J "); ~.:"xit\n' . c. ice\ "). rc e);
8.40 Q Queues switch ( choice) < case 1: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); insert . rear(item,&a); break; case 2: delete _front( &a); break; case 3: display( &a); break; default: exit(O); >> > 8.5 Priority queue using structures Each item is inserted at the appropriate position based on the priority and the item is always deleted from the front end. The design details are provided in section 8.2.4. In this section, the priority queue is implemented using structures. The structure declaration for this can be of the form: typedef struct
int int int > QUEUE;
Note: If there is a declaration of the form QUEUE a;
Q Systematic Approach to Data Structures using C - 8.41 the value associated with each attribute of the structure can be obtained using' .' operator and if there is a declaration of the form QUE~
the value associated with each attribute of the structure can be obtained using' ->' operator as discussed in the previous section. The function to insert an item into priority queue is shown below: Example 8.5.1: Function to insert item into priority queue
void insert_item(iot item, QUEUE *a) < int
1* Check for overflow *1
I*Compare from this initial point *1
1* Find the appropriate position to make room for mserting * an item based on the priority *1
to be inserted is less than a[j] *1
while (j >= 0 && item q[j])
a->q[j+ 1] = a->q[j]; 1* Move the item at a[j] to its nex position *i J--; >
1* Insert an item at the appropriate position *1
1* Update the rear pointer *1
8.42 Q Queues The function to delete an item from priority queue using structures is shown below: Example 8.5.2: Function to delete an item from priority queue void delete _front(QUEUE *a)
1* Check for underflow *1
.. 1* Access the item and remove from front end *1 printf("The
element deleted is %d\n",a->q[a->f++]);
if (a->f> a->r) < a->f= 0, a->r = -1;
1* Queue empty *1 1* Reset to initial values *1
The function to display the contents of priority queue using structures is shown below: Example 8.5.3: Function to display contents of priority queue void display(QUEUE *a) < int i; if ( a->f> a->r )
1* Check for underflow *1
printf("Queue return; l
printf("Contents of queue is\n"); for ( i = a->f; i r; i++) printf(" %d\n",a->q[i]); >
1* Display the contents queue *1 .
Q Systematic Approach to Data Structures using C - 8.43 The complete program to implement priority queue using structures is shown below: Example 8.5.4: C Program to implement priority queues using structures #include #include #define QUEUE_SIZE 5 typedef struct
int int int >QUEUE;
int choice,item; QUEUE a; a.f=O; a.r = -1; for (;;)
8.44 Q Queues case 2: delete _front( &a); break; case 3: display( &a); break; default: exit(O); >
Note: In this program the input can be in any order. But, the items are inserted at the appropriate position and are arranged in ascending order. The item at Oth position is having highest priority; the item at 1st position is having next highest priority and so on. Finally, the item at the end of the queue is having the least priority. 8.6 Input restricted queue Now, let us see "What is input restricted dequeue?" Definition: An input restricted dequeue is a variation of double ended queue which .support only the following operations: • Delete front • Delete rear • Insert front • Display Note: Input is restricted only to front end. Here, rear insertion is not permitted. Hence the name input restricted queue. If rear insertion is permitted then front insertion should not be permitted. The C program to implement input restricted queue is shown below: Example 8.6.1: C program to implement input restricted queue 1
#include #include #define QUEUE_SIZE 5
to Data Structures
/* Include: Example 8.2.1.2.2: Function to delete an item at the front end */ /* Include: Example 8.2.2.1.2: Function to insert an item at the front end */ ." Include: Example 8.2.2.2.2: Function to delete an item at the rear end */ /*
Include: Example 8.2.1.3.2: To display contents of queue
case 1: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); insert_ front(item, q, &f, &r); break; case 2: . delete_front(q, &f, &r); break; case 3: delete_rear(q, &f, &r); break; case 4: display(q, f, r); break; default: exit(O); > >
8.46 Q Queues 8.7 Output restricted
Now, let us see "What is output restricted dequeue?" Definition: An output restricted dequeue is a variation of double ended queue which support only the following operations: • Delete front . • Insert front • •
Insert rear Display
Note: Output is restricted only to front end. Here, rear deletion is not permitted. Hence the name output restricted queue. If rear deletion is permitted then front deletion should not be permitted. The C program to implement output restricted queue is shown below: Example 8.7.1: C program to implement output restricted queue #include #include #define QUEUE SIZE 5 /* Include: Example 8.2.1.1.2: Function to insert an item at the rear end */ /* Include: Example 8.2.1.2.2: Function to delete an item at the front end */ /* Include: Example 8.2.2.1.2: Function to insert an item at the front end */ /* Include: Example 8.2.1.3.2: To. display contents of queue void mainC)
int choice,item,f,r,q[l 0]; f= 0; r = -1; l
printf(" 1:Insert _front 2:Insert_rear\n"); printf("3:Delete front \nil); printf(II4:Display 5:Exit\n~I);
to Data Structures
printf("Enter the choice\n"); scanf("%d" ,&choice); switch ( choice)
case 1: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); insert_front(item, q, &f, &r); break; case 2: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); insertrearfitem, &r, q); break; case 3: delete_front(q, &f, &r); break; case 4: display(q, f, r); break; default: exit(O); > >
EXERCISES 1. What is a queue? What are the various operations that can be performed on queues? 2. What are the different types of queues? 3. Explain an ordinary queue and write a C program to implement the same (VTU Jul/ Aug 2004)
8.48 Q Queues 4. What is the disadvantage of an ordinary queue? How you can overcome this disadvantage? 5. What is a circular queue? How it is different from an ordinary queue? (VTU Jan/Feb 2004) 6. Write a C program to implement circular queues using arrays (VTU JullAug 2003) 7.. Write a C program to implement circular queues using structures 8. What is a double ended queue or deque? What are the operations that can be performed on double-ended queues? 9. Write a C program to implement deques using arrays 10. Write a C program to implement deques using structures 11. What is a priority queue? How, it is different from an ordinary queue? (VTU Jan/Feb 2003) Explain how a priority queue can be implemented? (VTU Jul/Aug 2005) 13. Write a C program to implement priority queues using arrays 14. Write a C program to implement priority queues using structures 15. Define input restricted queue and output restricted queue with suitable diagrams (VTU July/Aug 2006) 16. If we define an input-restricted deque as a queue which performs the operations delete_front, delete Jear and insert_front, how we can implement a stack and how we can implement a queue? 17. If we define an output-restricted deque as a queue which performs the operations delete_front, insert front and insert right, how a stack can be implemented? How a queue can be implemented? 18. How a stack of queues can be implemented? 19. How a queue of stack can be implemented? 20. How a queue of queues can be implemented? 21. A Circular queue the size of which is 5 has 3 elements 10,40,25, where F = 2 and R = 4. After inserting 50,60, what is the value of F and R? Trying to insert an element 30 at this stage what will happen? Delete 2 elements from the queue and insert 100. Show the sequence of steps with necessary diagrams with the value of F and R. 22. What is an ascending priority queue and descending priority queue? 23. Implement an ascending priority queue using arrays 24. Implement an ascending priority queue using structures 25. Explain how elements can be arranged in ascending order in priority queue while inserting? After arranging them in ascending order, what other functions are necessary to implement priority queues? info = 10; p->link = NULL;
1* Store lOin info field *1 1* make node as last node *1
The pictorial representation of the new node thus created after storing the necessary information is shown below:
Now,let us see "How does getnode work when available list is empty?" Theempty available list is shown in figure 9.2.2.b. Note that pointer AVAIL points to\0 (null) which indicates that the available list is empty and there are no free nodes tobe given to the user. If the user request a free node using the getnode function, the getnodefunction returns \0 (null). This means that all free nodes are currently in use by various programs and memory is used to full extent resulting overflow condition. Now,we can easily know "How getnodet) function is implemented?" Thegetnodet) function is implemented based on whether the available list is empty or notas shown below: • If the available list is empty, getnode function should display appropriate error message and then it should return NULL. This is achieved using the following statements: if (AVAIL = '\0')
Note: In place of '\0' we can use NULL
printf("Overflow return '\0';
> • If the available list is not empty, get node function returns the free node pointed to by AVAIL using the statement: p = AVAIL;
9.10 Q Linked Lists
The pointer AVAIL points to the next free node using the statement: AVAIL = link (AVAIL);
Thus, complete below:
Example 9.7.1.2: Algorithm to implement the function getnode Algorithm getnodet)
1* If available list does not exist, it is overflow */ of memory\n");
1* Get a free node from available list *1
AVAIL = link(A VAIL);
1* Point to next free node of available list *1
1* Return the free node to the user program *1
Now, let us see "How to implement the function getnodet) in C language?" In C language, we can use malloct) to allocate memory explicitly as and when required and exact amount needed during execution (Refer section 2.9.2.1, page 2.85 for details) • On successful allocation, the function returns the address of first byte of allocated memory. Since address is returned, the return type is a void pointer. By type casting appropriately we can use it to point to any desired data type • I specified size of memory is not available, the condition is called "overflow of memory". In such case, the function returns NULL. Note: It is the responsibility of the programmer to check whether the sufficient memory is allocated or not as shown below:
to nata Structures
/* Memory has been successfully allocated
Thus, in C language getnode function is implemented as shown below: Example 9.2.1.3: C Function to get a new node from the availability list NODE getnodet)
NODE x; /* Try to allocate the required size of memory */ x = (NODE) malloc(sizeof(struct node)); if(x=NULL)
/* Free nodes don't exist */
/* Allocation failed */ 1* Terminate the program */
> /* allocation successful and return the address */ return x;
ote: The return type of getnodet) is NODE and its type definition is available in example 9.2.1.1 (see this example for details on NODE) Note:The prototype ofm~l1ocO is defmed in header file "stdlib.h"
9.12 Q Linked Lists First, let us see "What is freenode?" Definition: A node which is no longer being used can be returned to available list so that when a next getnode is called, the node can be re-used. For this purpose, free node is used. So, a freenodet) is a function which returns unused node to the available list. The node thus returned is added at the beginning of the available list. Now, let us see "How does freenode work?" The syntax to use freenode function is shown below:
1* Declare a pointer variable p *1
1* Get a node from available list *1
1* Return a node to the available list *1
Consider the following availability list before executing freenodet): AVAIL
Assume the variable p points to a node as shown below and it is no longer used. So, it is required to return this node back to the available list. 1000 p~ The following activities take place after executing the freenodet): •
After executing the function freenode(p), the node pointed to by p is returned to the available list. The pictorial representation of pointer p after executing the function freenodet) is shown below: p
~ Systematic Approach to Data Structures using C - 9.13 Now, the pointer p does not contain valid address. So, pointer p is now a dangling pointer. • The returned node is thus added at the beginning of the available list as shown below: AVAIL
It is clear from above figure that link(p) should contain address of the first node of the available list. This is achieved using the following statement: link(p) = AVAIL; Then make the new returned itself as the starting address of the available list by executing the statement: AVAIL =p; So, the final available list is shown below:
Now, let us see "How to implement the function freenodet) algorithm" The corresponding algorithm is shown below: Algorithm freenode(p)
link(P) = AVAIL; AVAIL=p; >
9.14 Q Linked Lists The corresponding C function to de-allocate or free a node is shown below: Example 9.2.1.4: C Function to free a node to the availability list void freenode(NODE x)
free(x); > So far we learnt how to get a node from the available list and how to return that node to the available list whenever it is not being used. 9.2.2 Operattons
on singly linked lists
Now, let us see "What are the various operations that can be performed on singly linked lists?" The basic operations that can be performed on a linked list are shown below: Inserting a node into the list Deleting a node from the list Various Operations of linked lists Search in a list Display the contents of list 9.2.2.1 Insert a node at the front end In this section , let us see "How to insert a node at the front end of the list?" Design: To design the function easily, let us consider a list with 4 nodes. Here, pointer first contains address of the first node of the list. Let us try to insert the item 50 at the front end of the list. The sequence of steps to be followed are shown below Step 1: Obtain a free node from the availability list and -identify the node with variable temp using the following statement: 1
Step 2: Copy item = 50 to the info field of temp using the following statement: info(temp)
to Data Structures
Step3: Attach pointer first to the link field of temp using the statement: link( temp)
Step4: Now, a node temp has been inserted and observe from the figure that temp is thefirst node. Let us always return address of the first node using the statement: return temp; Thesesteps and the changes made as per these steps are shown in figure below:
Fig.9.2.2.1.1 To insert an item at the front end (called function)
Thealgorithmic function to insert an item at the front of the list is shown below:
Example9.2.2.1.1: Algorithm to insert an item at the front of list Algorithminsert_fropt(item, first)
/* Get a node from the availability list */
/* Insert the item */
/* Attach to the existing first node of the list */
/* Make temp as new first node */
ote: in the calling function (say main), let us use first always to point to the first node of the list. This can be achieved by calling the function insert _ frontt) as shown below
9.16 Q Linked Lists first = insert_front(item,
After executing this statement, we know that function insertfrontt) returns temp which is the address of the first node in that function. This returned value is copied into first in the calling function. The entire linked list as seen in calling function is shown below: .
Fig.9.2.2.1.2 After inserting 50 at the front end (calling function)
ote: The variable first in the calling function (say main) always points to the first node. The previous node which was pointed to by first before executing insert _ frontt) is shown in gray color. Note: The algorithm insert_frontO has been designed by assuming that the list already exists. Assume now that the list is empty i.e., the pointer variable first contains NULL. Now try to insert an item into the empty list and see that the function insertfrontt) works for this case also. Just now, we have inserted one node at the front end of the list. Now, the question is to create a linked list?" The answer is very simple. Consider the following statement: first = insert _front(item, first);
If first is NULL and the above statement is executed, a linked list with only one node is created. If it is executed for the second time, a new node is inserted at the front end and there by number of nodes' in the list is 2 If it is executed for the third time, the number of nodes in the list will be 3. Thus, if the function insert _ fronn) is called n times, we have a list with n nodes.
ote: Thus, repeated inserting an element at the front end of the list we can create a linked list. The C function to insert an item at the front end of the list is shown below:
to Data Structures
Example 9.2.2.1.2: C Function to insert an item at the front end of the list NODE insert_front(int item, NODE first)
NODE temp; temp = getnodet);
/*obtain a node from the available list*1
1* Insert an item into the newly created node */
/* Attach new node at the front end of list *1
1* return the new first node *1
9.2.2.2 Display singly linked list Now, let us see "How to display the contents of list?" Consider the list shown in fig.9.2.2.2. Here, first contains address of the first node. Instead of updating first from left to right to access each node, let us use another pointer temp which initially points to the first node of the list. By pointing temp to each subsequent nodes and printing the info field of each node, entire contents of list can be displayed.
Fig. 9.2.2.2 Singly linked list to be displayed
Now,let us see "How to point temp to point to next node?" Note that link(temp) is 1004. If we copy this value to temp, now temp has the address 1004 which is the addressof the second node. Thus, using the statement: temp = link( temp) wecan point temp to next node. Now, the items to be displayed are 20, 45, 10 and 80. This is achieve by repeatedly printing info field of temp and updating temp to point tonextnode as shown below:
9.18 Q Linked Lists write (info(temp)) temp = link(temp)
After displaying 80, note that temp points to NULL, indicating all the nodes in the list have been displayed. Now, there is no need to go back and execute those statements i.e., those two statements have to be repeatedly executed, as long as temp is not NULL. So, the next version of the algorithm can be written as temp = first while ( temp != NULL)
write (info(temp)) temp = link( temp) >
Note that all these statements have to be executed only if the list is existing. If first is NULL, display the message "List is empty" The algorithmic function to display the list is shown below: Example 9.2.2.2.1: Algorithm to display the contents of the list Algorithm displaytfirst)
1* Check for empty list *1
> write('The contents of the list') temp = first while ( temp != NULL)
1* Holds address of the first node *1 1* As long as no end oflist *1 1* Display the info field of a node *1 1* Update to point to next node *1
TheC function to display the contents of the list is shown below:
to Data Structures
Example 9.2.2.2.2: C function to display the contents oflinked list void display(NODE first) < NODE temp;
1* Check for empty list *1
if ( first = NULL)
contents of singly linked list\n");
temp = first; while (temp!= NULL) < printf("%d ",temp->info); temp = temp->link;
1* Holds address of the first node *1 1* As long as no end of list *1 1* Display the info field of node *1 1* Point to the next node *1
The complete C program to create a list and to display the contents of list is shown below: Example 9.2.2.2.3: C program to create a list and to display the contents oflist #include #include #include struct node int struct node
>; I typedef struct node* NODE;
9.20 Q Linked Lists 1* Include: Example
9.2.1.3: C Function to get a new node from availability list */
/* Include: Example 9.2.2.1.2: C Function to insert an item at the front end of list */ 1*
Include: Example 9.2.2.2.2: C function to display the contents oflinked·list
NODE first = NULL; int choice, item;
/* To start with list is empty. */
printf("Enter the item to be inserted\n"); scanf("%d" ,&item); first = insert _ fronuitem.first); break; case 2: displaytfirst); break; default: exit(O); >
> > 9.3 Other operations
on linked lists
This section describes the implementation of stacks, queues and dequeues using linked representation and various operations that can be performed on linked lists along with design aspects.
Systematic Approach to Data Structures using C - 9.21
9.3.1 Delete a node from the front end Now, let us see "How to delete a node from the front end of the li t?" Design: To design the function easily, let us consider a list with 5 nodes. Here, pointer first contains address of the first node of the list. Let us try to delete an item from the front end of the list. The sequence of steps to be followed are shown below:
Fig.9.3.1 To delete an item from the front end
Step 1: An auxiliary pointer temp should point to the first node of the list using the following statement temp = first;
9.22 Q Linked Lists Step 2: Update the pointer temp to point to the next node. This is achieved using the statement: temp = link( temp); Step 3: Note that first points to first node of the list and temp points to the second node of the list. Using the pointer first, the first node can be deleted as shown below: freenode( first); The node pointed to by first is deleted and is returned to the availability list. The resulting linked list is shown in fig.9.3.l.c. Step 4: Once the node first is deleted, the node temp will become first node. So, return temp as the first node to the calling function using the statement: return temp; Note that all these statements have to be executed, only when the list exists. If the list is empty, display the message "List empty, can not delete" and return NULL. The C function to delete an item from the front end of the list is shown below: Example 9.3.1: C function to delete an item from the front end of the list NODE delete_front(NODE < NODE temp; if ( first = NULL)
1* Check for empty list *1
printf("List is empty can not delete\n"); return first; >
1* Retain address of the node to be deleted *1
1* Obtain address of the second node *1
1* access first node *1
1* delete the front node *1
1* return address of the first node *1
Systematic Approach to Data Structures using C - 9.23
ote: Now, onwards let us write only C functions. Algorithmic writtenas shown in earlier examples.
functions can be
9.3.2Insert a node at the rear end Now,let us see "How to insert a node from the rear end of the list?"
Design:To design the function easily, let us consider a list with 5 nodes. Here, pointer first contains address of the first node of the list. Let us try to insert an item at the rear end of the list. The sequence of steps to be followed are shown below:
Fig.9.3.1 To insert an item at the rear end of the list
9.24 Q Linked Lists Step 1: Create a node to be inserted and insert the item using the following statements: temp = getnodet); temp->info = item; temp->link = NULL; ,Step 2: If the node temp is inserted into the list for the first time (i.e., into the empty llist), then return temp itself as the first node using the following code. if(first = NULL) return temp; Step 3: The moment control comes here, we have an existing list. We need to obtain the address of the last node. This is possible only if we start from the first node. So, we use pointer cur which initially points to the first node using the statement: cur
Step 4: Now, we should obtain the address of the last node. This is possible by repeatedly updating cur till last node is reached.
Note: if cur->link contains \0 (null) then cur points to the last node. So, keep updating cur as long as cur->link is not NULL. This is achieved using the following statement: while ( cur->link != NULL) cur = cur->link; Step 5: Once cur points to the last node, we can easily insert temp at the end of the list. This is achived by copying temp to link field of cur using the statement: cur->link
Step 6: After updating always return address of the first node of the list using: return first; The complete C function to insert an item at the rear end of the list is below:
Systematic Approach to Data Structures using C - 9.25
Example 9.3.2: Function to insert an item at the rear end of the list NODE insertrear/int item, NODE first)
temp = getnodet); temp->info = item; temp->link = NULL;
1* Points to newly created node *1 1* To hold the address of the last node *1 1* Obtain new node, insert the item into node *1
1* If list is empty return new node as the first node* I if ( first = NULL) return temp; 1* Iflist exists, obtain address of the last node *1 cur = first; while ( cur->link != NULL)
1* Insert the node at the end *1
1* return address of the first node *1
9.3.3Delete a node from the rear end Now,let us see "How to delete a node from the rear end of the list?" Design: To design the function easily, let us consider a list with 5 nodes. Here, pointerfirst contains address of the first node of the list. Let us try to delete an item fromthe rear end of the list. The sequence of steps to be followed are shown below: Step 1: It is not possible to delete an item from the empty list. Appropriate error messagecan be displayed as shown below: if (first = NULL)
printf("List is empty can not delete\n"); return first; >
9.26 Q Linked Lists
Step 2: Consider a list with single node shown in figure 9.3.3.a. After deleting this node, the list should be empty. The code for this case is shown below. I*If only one node is present, delete it *1 if ( first ->link = NULL)
printf ("The item to be deleted is %d\n",first->info); freenode(first); 1* Delete and return to availability list */ return NULL; /* return empty list */ >
(a) only one node first
prev Note: cur and prev points to last and last but one node (final dotted lines) (b)
.L ~ (c) Deleting the last node
to Data Structures
Step 3: Once control comes to this step, the list has more than one node. To delete the last node, we need to find the address of the last node and address of the last but one node. For this reason, we use two pointers: cur and prev, Initially, cur points to the first node and prey points to \0 (null). Now, let us point cur to point to last node and prey to last but one node. This is possible by repeatedly updating cur and prey as long as link field of cur is not NULL. Just before updating cur, assign cur to prey so that prev->link always contains address of cur node. This can be achieved by using the following sets of statements. prev=NULL; cur = first; while( cur->link != NULL ) < prey = cur; cur = cur->link; >
After executing the above statements, cur points to the last node and prey points to last but one node as shown in figure 9.3.3.b. Step 4: To delete the last node pointed to by cur, the function freenodet) is used as shownbelow: (gray color in 9.3.3.c) printf("The item deleted is %d\n",cur->info); freenode( cur); Step 5: Once the last node is deleted, the node pointed to by prey should be the last node.This is achived by copying NULL to link field of prey as shown below: prev->link = NULL;
1* Node pointed to by prey is the last node *1
Step 6: Finally return address of the first node. return first;
1* return address of the first node *1
Thecomplete C function to delete a node from the rear end of the list is shown below:
9.28 Q Linked Lists Example 9.3.3: Function to delete an item from the rear end of the list NODE delete _rear(NODE first) < NODE cur,prev;
1* Check for empty list *1 if (first = NULL)
if ( first ->link = NULL )
I*Only one node is present and delete it *1
printf ("The item to deleted is %d\n",first->info); freenode(first) ;
I*·return to availability list *1
1* List is empty so return NULL *1
1* Obtain address of the last node and just previous to that *1 prev = NULL; cur = first; while( cur->link != NULL)
prev = cur; cur = cur->link; >
1* delete the last node and return to available list* I printf("The item deleted is %d\n",cur->info); freenode( cur); prev->link
1* Make last but one node as the last node *1 1* return address of the first node *1
.d Systematic 9.3.4 Implementation
to Data Structures
of queues using linked lists
Now, "How to implement queues using linked lists?" We have discussed the concept .of queues in chapter 8. It is a FIFO data structure. Here, insertion is done from one end and deletion is done from the other end. So, we can utilize the functions • insert_rearO • delete_ frontt) • displayt) to implement queues using linked list. The complete C program to implement queues is shown below: Example 9.3.4: Program to implement gueues using singly linked lists #include #include #include struct node < int struct node >;
typedef struct node* NODE;
1* Include: Example 9.2.1.3: C Function to get a new node from availability list */ ./* Include: Example
9.2.1.4: C Function to free a node to the availability list */
1* Include: Example 9.2.2.2.2: C function to display the contents of linked list */ 1* Include: Example 9.3.1: C function to delete an item from the front end oflist */ 1* Include: Example 9.3.2: Function to insert an item at the rear end of the list */ void maint) < NODE first = NULL; int choice, item;
Note: Using the functions insertfrontt), implement queues. 9.3.5 Implementation
delete_rearO and displayt) also, we can
of stacks using linked lists
Now, "How to implement stacks using linked lists?" We have discussed the concept of stacks in chapter 6. It is a LIFO data structure. Here, insertion is done from one end and deletion is done from same end. So, we can utilize the functions • insert _frontt) • insert _rearO ,. • delete _frontt) or. delete JearO . • displayt) • displayt)
to Data Structures
to implement stacks using linked list. The complete C program to implement stacks is shownbelow: Example 9.3.5: Program to implement stacks using singly linked lists #include #include #include struct node int struct node
typedef struct node* NODE;
1* Include: Example 9.2.1.3: C Function to get a new node from availability list */ 1* Include: Example 9.2.1.4: C Function to free a node to the availability list */ 1* Include: Example 9.2.2.1.2: C Function to insert an item at the front end of list */ /* Include: Example 9.2.2.2.2: C function to display the contents of linked list */
1* Include: Example 9.3.1: C function to delete an item from the front end of list */ voidmaint) < NODE first = NULL; int choice, item; for (;;)
printf("1 :Insert front 2:Delete front \n"); printf("3 :Display 4:Exit\n"); printf("Enter the choice\n"); scanf("%d" ,&choice);
9.32 Q Linked Lists switch ( choice)
case 1: printf(t'Enter the item to be insertedm''); scanf(tI%dtl ,&item); first = insert _front(item,first); break; case 2: first = delete_front(first); break; case 3: display(first); break; default: exit(O); > >
9.3.6 Implementation of double ended queues using linked lists
Now, "How to implement dequeus using linked lists?" We have discussed the concept of dequeues in chapter 8. It is a special type of data structure where insertion and deletion operations are p .formed on both ends. So, we can utilize the functions • insert _ frontt) • insert JearO • delete _ frontt) • delete JearO • displayt) to implement deques using linked list. The complete C program to implement de que! is shown below: Example 9.3.6: Program to implement deques using singly linked lists #include #include #inclu~e struct node
int struct node >;
to Data Structures
typedef struct node* NODE; 1*
9.2.1.3: C Function to get a new node from availability list */
1* Include: Example 9.2.1.4: C Function to free a node to the availability list */ 1* Include: Example 9.Z.2.1.2: C Function to insert an item at the front end oflist */ 1* Include: Example 9.2.2.2.2: C function to display the contents oflinked list ~/ 1* Include: Example 9.3.1: C function to delete an item from the front end of list */ 1* Include: Example 9.3.2: Function to insert an item at the rear end of the list */ 1* Include: Example 9.3.3: Function to delete an item from the rear end oflist */ void maim) < NODE first = NULL; int choice, item; for (;;)
printf("l :Insert front 2:Jnsert rear\n"); printf("3:Delete front 4:Delete rear\n"); printf(" 5 :Display 6:Exit\n"); printf("Enter the choice\n"); scanf("%d" ,&choice); switch ( choice)
case 1: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); first = insertfronuitem.first); break; case 2: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); first = insert Jear(item,first); break;
9.34 Q Linked Lists case 3: first = delete _ front(first); break; case 4: first = delete. reanfirst); break; case 5: display(frrst); break; default: exit(O); > >
> 9.3.7 Creating an ordered linked list Now, let us see "What is an ordered linked list?" Definition: A linked list in which the items are stored in some specific order is an ordered linked list. The elements in an ordered linked list can be in ascending or descending order or based on key information. A key is one or more fields within a structure that are used to identify the data. For example, an ordered linked list shown in fig.9.3.7.a. Now, let us see "How to create an ordered linked list?" Design: To design the function easily, let us consider a list with 4 nodes. Here, pointer first contains address of the first node of the list. After inserting any item into this existing list, the order of list should be maintained i.e., the items in the list should be arranged in ascending/descending order only. The pointer first, contains the address of the first node of the list. To insert an item into the list, the sequence of steps to be followed are: Step 1: Create a node to be inserted and insert the item usmg the following statements: temp = getnodet); temp->info = item; temp->link = NULL;
Q Systematic Approach to Data Structures using C - 9.35
Step 2: If the node temp is inserted into the list for the first time (i.e., into the empty llist), then return temp itself as the first node using the following code. if (first
NULL) return temp;
Case 1: Insert at front end
Case 2: Insert at the middle
Fig.9.3.1 To create an ordered linked list Case 1: Inserting an item at the front end of the list: Let the item to be inserted be 5.
Step 3: Consider the list with 4 nodes having 10, 20, 30, 40 as the info of each node. The item 5 is less than i0 which is the info of first node of the list. To maintain the order, the created node temp should be inserted at the front of the list as shown in fig.9.3.7.b. The code corresponding to this is shown below.
9.36 Q Linked Lists
/* Insert the node at the front end of the list */
Step 4: Once the node temp is inserted at the front end, let us return temp indicating temp itself is the first node of the list using:
/* Make new node as the first node */
Case 2: Inserting an item at the middle/end: Let the item to be inserted is 35 Step 5: Find the appropriate position (Fib 9.3.1b or Fib 9.3.1c): The node temp containing item 35 should be inserted between two nodes prey and cur. So, it is required to find appropriate positions so that the node temp is inserted maintaining the order. This is possible if traversing is done from the first node of the list. Let us use two pointers cur and prey with cur pointing to first node and prey pointing NULL as shown below: prev = NULL; cur = first; Then, as long as the item to be inserted is greater than info of cur, keep updating the cur and prey to point to their successor nodes one after the other. The code to find the appropriate position is shown below. while ( cur != NULL && item> cur->info )
Note: While updating cur and prey, we should see that cur should never be NULL
Note: The moment we find the appropriate place, control comes out of the while loop. Now, we have cur and prey between which node temp has to be inserted. Step 6: Insert at middle/end:
The corresponding code is shown below:
/* connect node prey with node temp */
/* connect new node temp with next node cur */
Step 7: Always we return the address of the first node as shown below: return first;
/* return address of the first node */
~ Systematic Approach to Data Structures using C - 9.37 The complete C function to insert an item into an ordered linked list is below: Example 9.3.7: Cfunction to create an ordered linked list NODE insert(int item, NODE first) < NODE temp, prey, cur;
1* obtain a node to be inserted *1
temp = getnodet); temp->info = item; temp->link = NULL;
1* Inserting the node for the first time *1 if ( first = NULL) return temp;
1* Inserting the node in the beginning of the list *1
if ( item info ) < temp->link = first; return temp; >
1* find prey and cur locations so that node temp has to be inserted *1 prey = NULL; cur = first;
1* Insert the node between prey and cur *1
prev-c-link = temp; temp->link = cur;
1* return the first node *1 return first;
9.38 Q Linked Lists 9.3.8 Search for an item in a list Before writing the algorithm/program for searching, let us see "What is searching?" Definition: More often we will be working with large amount of data. It may be necessary to determine whether a particular key or item is present in the large amount of data. This process of finding a particular key or item in the large amount of data is called searching. Now, let us see "How to search for an item in a linked list?" Searching for a key item is very simple and straight forward technique. We know how to display info of each node. The partial code can be written as: . " cur = first; while (cur!= NULL)
1* As long as no end oflist */
1* Display the info of a node */ 1* point cur to the next node */ >
Note: Replace printf by the if
Note: Replacing the printf by the above statement our searching is over. The partial code for searching can be written as shown below: cur = first; while (cur!= NULL)
1* As long as no end oflist */
if (key = cur->info) break; cur = cur-c-link;
/* If found go out of the loop *1 /* point cur to the next node */
1* If end of list, key no.t found *1
pri t ("Search is unsuccessful\n"); return;
> printf("Serach is successfu1\n");
1* Yes, key found
The complete C function to search for a key item is shown below:
to Data Structures
Example 9.3.8.1: Function to search for key item in the list void search(int key, NODE first) < NODE cur; if ( first = NULL)
/* Search for empty list */
> /* Compare one after the other */ cur = first; while (cur != NULL)
/* As long as no end of list */
if (key = cur->info) break; cur = cur->link;
/* If found go out of the loop of link
G) Delete the first node pointed to by cur using the statement: freenode(cur);
. 1* Deleted node is shown in Gray color *1
address of the first node using the statement: return first; b
The code corresponding to this is shown below. if ( key = first->info )
1* Save the address of the first node *1 1* Point first to second node in the list *1
, 1* Delete the first node *1
, 1* Return second node as the first node *1
~ Systematic Approach to Data Structures using C - 9.41 Step 3: Control comes to step 3, if key is not present in the first node of the list. It may be present or may not be present. So, we have to search for key in the list. The code can be written as shown below: prev=NULL; cur = first;
1* As long as no end of list *1
while (cur != NULL)
if (key = cur->info) break;
1* If found go out of the loop *1 1* Save the address of cur node *1 1* point cur to the next node *1
cur; cur - cur-e-link;
1* If end of list, key not found *1 is unsuccessful\n");
1* Yes, key found *1
Step 4: Once search is successful, the node pointed to by cur has to be deleted. Also, observe that if cur is the node to be deleted, prev is the predecessor of the node to be deleted. Assume key = 30. Now, to delete the node pointed to by cur consider the figure shown below:
9.42 Q Linked Lists Now, to delete the node pointed to by cur, we have to establish a link between the successor and the predecessor of the node to be deleted. This can be done using the following statement:
CD prev->link = cur->link; Step 5: Once a link has been established, the node pointed to by cur is isolated and it can be deleted by calling the function freenodet)
Finally return the address of the first node. The code for this is shown below. return first;
The complete C function to delete a node whose information field is specified is shown below: Example 9.3.9.1: Function to delete a node whose info field is specified NODE delete_info(int key, NODE first)
NODE prev, cur; if ( first = NULL )
1* Check for empty list *
printf'(t'List is emptyin"); return NULL;
if (key = first-s-info )
1* Save the address of the first node *1
1* Point first to second node in the list ~I
1* Delete the first node ~.I .'
1* Return second node as the first node *1
> prev=NULL; cur = first;
Systematic Approach to Data Structures using C - 9.43
1* As long as !I0 end Of list */ 1* If found go out of the loop *1 1* Save the address of cur node *1 1* point cur to the next node *1
prev = cur; cur = cur->link; >
1* If end oflist, key not found *1
printf("Search return first;
1* Search successful. So, delete the node *1 prev->link = cur->link; 1* Establish link between the freenode(cur);
predecessor and successor *1 1* Delete the node with info key *1
1* Return address of first node *1
9.3.1 0 Delete a node at the specified position Thisproblem is similar to the previous method. Instead of deleting a node whose info fieldis specified, we obtain a node at the specified position and then delete from that position. If the specified position is 1, the node at the front end of the list has to be deleted as shown in fig.9.11.a. The code corresponding to this can be Now,let us see "How to delete a node at the specified position?" Design: To design the function easily, let us follow the sequence of steps shown below: Step 1: Check for empty list. The equivalent code can be written as shown below: if (first = NULL II pos link;
/* Point first to second node in the list */
/* Delete the first node */
/* Return second node as the first node */
> Step link = cur->link; freenode( cur); return first;
to Data Structures
The complete C function to delete a node whose information field is specified is shown below: Example 9.3.10.1: Function to delete a node at the specified position NODE delete ---'pos(intpos, NODE first)
if ( first = NULL
1* Address of the node to be deleted *1 1* Address of the previous node *1 • 1* Update till desired node is found *1
1* Save the address of cur node *1 1* point cur to the next node *1
1* If end of list, invalid posi tion *1
printf("Invalid return first; >
9.46 Q Linked Lists if ( count l= pos )
1* Invalid position *1 position specified\n");
1* Position found. So, delete the node *1 prev->link
1* Establish link between the
predecessor and successor *1 1* Delete the node with info key */
1* Return address of first node *1
Now, let us see "What is concatenation of two lists?" Definition: Concatenation of two lists is nothing but joining the second list at the end of the first list. Design: Concatenation of two lists is possible if two lists exist. If one of the lists is empty, return the address of the first node of the non-empty list as shown below: if (first = NULL)
If both lists exist, obtain the address of the"last node of the first list and attach this to the first node of the second list as shown in figure 9.3.1l. The code to obtain address of the last node of the first list is shown below: cur = first; while (cur->link != NULL) I*Traverse till the end *1
Once control comes out of the loop, pointer cur contains address of the last node of the first list (see the figure below). Now, attach address of the first node of the second list identified by second to cur node as shown in red line. The code corresponding to this can be written as cur->link = second;
Q Systematic Approach to Data Structures
Now, first contains the address of the first node of the concatenated list and return this node to the calling function using the statement: return first;
Fig. 9.3.11 Concatenation of two lists Thecorresponding C function is shown below: Example 9.3.11.1: Function to concatenate two lists ODE concat (NODE first, NODE see)
/* holds the address of the last node of first list" return second; return first;
/* Obtain address of the last node of first list*/ cur = first; while ( cur->Iink != NULL)
cur == cur->link; cur->Iink = sec;
/* Attach first node of second list to end of 1irst list */
/* Return the first node of the concatenated list ~/
9.48 Q Linked Lists 9.3.12 Reverse a list without creating new nodes Let us concentrate on another operation namely reversing a linked list. Consider the list shown in figure 9.3.12.a. After reversing, the first node becomes the last node, second node becomes the last but one node and so on. Finally, the last node becomes the first node. All existing links of the list shown in figure 9..3.12.a are reversed to 01?tainthe reversed list as shown in figure 9.3.12.b.
(a) before reversing
(b) After reversing Fig. 9.3.12 Linked list before and after reversing The C function to reverse a linked list is shown in example 9.23. Example 9.3.12.1: Function to reverse a list NODE reverse ( ODE first)
/* Initial reversed list */
while (first != NULL) < temp = first; first' = first->link; temp->link cur
Hold part of the list not yet reversed*/ The node marked in above step will be reversed*/ So it is updated to point to the list to be reversed */ The node marked for reversing is */ linked to the partial reversed list */ /* Points to the partial revered list */ /* Contains address of the reversed list */
to Data Structures
9.3.13Insert a node at the specified position In an ordered linked list an item is inserted at the appropriate position so that the list remains in ascending order. If item to be inserted is less than the first element, the item is inserted in the beginning of the list. If item to be inserted is larger than all items present in the list, that item will be inserted at the end of the list. Otherwise, somewhere in the middle at the appropriate position the item is inserted with the condition that the list remains ordered. For details, the reader can refer section 9.3.7 (page9.34) for creating an ordered list. The same logic with minor modifications can be used to insert an item at the specified position. The C function to insert an item at thespecified position is shown below: Example 9.3.13: Function to insert an item at the specified position NODE insertposfint
NODE NODE int count;
item, int pos, NODE first) temp; prey, cur;
1* Node to be inserted *1 1* A node is inserted between these two nodes *1 1* To find the exact position to insert an item *1
temp = getnodet); temp->info = item; temp->link = NULL;
obtain a node to be inserted *1
1* Inserting the node for the first time *1
1* Check for empty list *1
printf("Invalid return first;
temp->link = first; return temp; >
1* Find the appropriate position *1 count = 1; prev = NULL; cur = first;
1* Insert the node at the front of the list *1
9.50 Q Linked Lists while ( cur != NULL && count != pos )
prev.= cur; cur = cur->link; count++; >
/* If valid position, insert the node */
prev->link = temp; temp->link = cur; return first; > printf(" Invalid position\n"); return first; > 9.3.14 Priority queue using linked lists
A priority queue can be implemented by using an unordered linked list and an ordered linked list as well. Using an unordered linked list, an ascending priority queue can be implemented by selecting a node with least value and then deleting it from the list. To implement a descending priority queue, select a node with highest item and delete that node. A priority queue can also be implemented using an ordered linked list. If the elements of the list are in ascending order, deleting a node from the front end results in ascending priority queue. Here, a node containing a least item is considered to be a node with the highest priority and that is the node to be deleted first. To implement a descending priority queue, create an ordered ·list in descending order and delete from the front end. Here, a node with highest item is considered to be a node with the highest priority and that is the node to be deleted first. 9.3.15 Non-homogenous
Let us see "What is non-homogenous list?" Definition: A linked list with two or more fields with different data types considered as non-homogenous list.
For example, in the linked lists so far we have seen, the type of info field of each node in the list was integer. But, the data type can be float? double or array of characters of real or any other complex entity. For example, to store the student names, corresponding id's and semester using a linked list, we can have the following declaration struct
student char int int struct
name[lO]; id; sem; link;
Here, the student details such as name, id and semester are the inputs. Let us provide the facilities to: • Enter the student details and insert a node at the front end/rear end/at the specified position. • Delete all the details of a student based on a given id. • Search a node based on student id and update the information content. • To display full details of a student after searching for a given id. By looking at • insert student • insert details
the problem description, the operations to be supported are front( char name[], int id, int sem, STUDENT first) i.e., to insert details from the front end rearrchar name[], int id, int sem, STUDENT first) i.e., to insert student from the rear end insertpostchar name[], int id, int sem, int pos, STUDENT first) i.e., to insert student details at the specified position. delete_student (int id, STUDENT first) i.e., to delete the student details given an id search(int id, STUDENT first,) i.e., to search for the existence of a student based on id and update display(STUDENT first) i.e., to display all the student details
The pointer variable first points to the first node of the list where each node of the list contains unique information of a student. All the basic operations of this problem are already discussed and the code for this is shown below:
9.52 Q Linked Lists Example 9.3.15.1:Function to get a node from the availability list STUDENT getnode(void) < STUDENT x; x = ( STUDENT)
printf("Out of memory\n"); exit(O); > '- return x; >
Example 9.3.15.2:Function to return node to availability list void freenode(STUDENT
Example 9.3.15.3:Function to insert at the front end STUDENT insert_front(char
name[], int id, int sem, STUDENT first) .
STUDENT temp; temp = getnodet);
1* Obtain a node *1
1* Insert the student information into the node *1 strcpy( temp->name,name); temp->sem=sem; temp->id = id; temp->link = first;
1* Created node is made the first node *1 first = temp; return first;
Systematic Approach to Data Structures using C - 9.53
Example 9.3.15.4: Function to insert at the rear end STUDENTinsertJear(char < STUDENT temp; STUDENT cur;
name[], int id, int sem, STUDENT first) /* Node to be inserted */ /* To hold the address of the last node */
1* Obtain the node to be inserted and copy the item*/ temp = getnodet); strcpy(temp->name, name); temp->id = id; temp->sem = sem; temp->link = NULL; 1* Return new node created as the first node iflist is empty *1 if ( first = NULL) return temp; 1* If list exists, obtain address of the last node *1 cur = first; while ( cur->link != NULL)
/* Insert the node at the end *1
1* return address of the first node *1
Example 9.3.15.5: Function to insert item into specified position linked list STUDENT insertpost char name[], int id, int sem, int pos, STUDENT first)
STUDENT STUDENT int count;
1* Node to be inserted */ 1* A node is inserted between these two nodes *1 1* To find the exact position to insert an item *1
1* obtain a node to be inserted */ temp = getnodet);
9.54 Q Linked Lists
1* Insert the student information into the node *1 strcpy( temp->name, name); temp->id = id; temp->sem = sem; temp->link = NULL; if ( first = NULL && pos = 1) return temp;
1* Inserting the node for the first time *1
printf("Invalid position\n"); return first; .->
1* Inserting the node in the beginning of the list *1
temp->link = first; return temp; >
1* Find the appropriate position */
count = 1; prev = NULL; cur = first; while ( cur != NULL && count != pos)
1* Find the valid position *1
prey = cur; cur =cur->link; count++; >
1* If valid position, insert node *1
printf("Invalid positionvn"); return first; >
1* return the first node *1
to Data Structures
Example 9.3.15.6: Function to delete student details of an id specified STUDENT delete_student(int < STUDENT prev,cur;
id, STUDENT first)
if ( first = NULL)
printf("No students in the organization\n"); return NULL; >
1* Compare one after the other *1 prev=NULL; cur = first; while ( cur != NULL && id != cur->id )
pre v = cur; cur = cur->link; >
1* id specified is invalid *1
printf("Student return first;
j> Of( prey = NULL) first = first->link; else prev->link = cur->link; free(cur); return first; .
1* to delete the first student *1 1* to be deleted is in middle or end *1
9.56 Q Linked Lists
Example 9.3.15.7: Function to search for the student details based on id STUDENT search(int id, STUDENT first) < STUDENT cur; ehar name[20]; int sem; if (first = NULL)
printf("No students in the organization\n"); return NULL; >
1* Compare one after the other *1 . cur = first; while ( cur != NULL)
if (id = cur->id) break; cur = cur->Iink; >
1* Student id not four,
printf("Student retu rn first;
with id %d not found\n",id);
printf("Student found with following informationin''); printf("Name: %s\nJD : %d\n Sem: %d\n", cur-e-name, cur->id, cur->sem); printf("Name : "); 1 printf "Jd : "); printf("Sem : ");
Systematic Approach to Data Structures using C - 9.57
/* Update the student information strcpy( cur->name, name); cur->id = id; cur->sem = sem; return first;
/* Return address of the first node */
9.3.15.8: Function to display the information
students in the organization\n");
> printf("Student Name Student 10 Semester\n"); \n")', prln. tf'(" l' -------------------------------------------for ( temp = first; temp != NULL; temp = temp->iink) printf("%10s %4d %4d\n",temp->name, temp->id, printf("\n");
f1inciullc flindlldc /Ii,lclllcle I!incillclc
9.3.15.9: C Program to add/delete/search
link. But, using an array representation, this can be achieved by the following statements.
to Data Structures
x = avail; avail = L[avail].link; return x; In the linked list while updating the pointer variable, it may point to NULL, indicating last node in the list is reached. In this representation, while updating avail, this may point to null, which in this case is -1. If avail has the value -1, it indicates that availability list is empty and memory cannot be allocated. The function to allocate memory is shown below: Example 9.3.16.1: Function arrays NODE
to implement linked lists usrng
NODE x; if ( avail = null )
printf(tlOut of memoryvn"); cxit( 1);
x = avail; avail= L[avail].link; return x;
Suppose3 items 30, 40 and 20 are inserted into the list in the same order. The user list anti the availability list is shown in fig.9.3.17.b. Note that the index variable first containsthe index of the first item i.e., 30. To delete a node and to return this to the availability list, consider the array shown in fig.9.3.17.c. Suppose x is the node to be returned to the availability listThen, the node x should be the first node in the availability list and avail should point tox, so that when a new node is requested, the node just returned to the availability listcan be re used. This can be achieved by assigning avail to link field of the noele to be deleted i.e., x and then assigning x to avail. After deleting the node x, the resulting
9.64 Q Linked Lists user list and the availability list is shown in fig.9.3.17.d. The C function to return a node to the availability list is shown below: Example 9.3.16.2: Function to return a node to the availability list using arrays void freenode(NODE x)
L[x].link = avail; avail = x; return; '-
Given an array representation of a linked list, we see how to implement deques. The algorithm remains same. But, in the program, instead of using pointers and dynamic variables, we use an array representation. Note that to access info field of a node x, in linked representation we use the notation x->info where as in the array representation we use the notation L[x] .info. The complete program to implement deques using an array representation of a linked list is shown below: Example 9.3.16.3: Deque using an array representation of a linked list #inc1ude #inc1ude #defme MAX SIZE 100 #define null -1 typedef int NODE; struct node
int info; NODE link; >; 1
struct node L[100]; NODE avail;
1* Global variables *1
,!;l Systematic Approach to Data Structures using C - 9.65 void freenode(NODE x)
L[x].link = avail; avail = x;
return; void initialize( void)
NODE i; avail for (i
In an array representation the corresponding fields can be accessed using L[x].link and L[x].info
It is left to the reader to implement rest of the programs on linked lists using an-array representation. Now, we should be in a position to answer the question "What are the drawbacks of using sequential storage (arrays) to represent stacks and queues?". The various drawbacks are listed below: • A fixed amount of storage is allocated: The compiler allocates only specified number of memory locations for stacks and queues. If more memory is allocated
9.70 Q Linked Lists but using only small amount of memory results in wastage of memory space. II' less memory is allocated when we insert more items, there is possibly of ovcrl1ow • Items are stored contiguously: Some times enough contiguous memory locations may not be available. There are situations where a number of chunks 01 contiguous memory locations are available. Even though the total free memory space is sufficient, this space cannot be used since stack items and queue items . require contiguous storage space. Now, let us see "What are the drawbacks of representing a stack or a queue using linked list?"The various drawbacks are listed below: • A node in a linked list may have two or more tields and naturally occupies more storage space than the corresponding element in the array. • Accessing the data related to stack or a queue is much slower using linked list since additional time is spent in managing the available list. Only when required memory is allocated. So, time is required to get a node ti"OI11 the available list. When a node is returned using free, the unused node has to be added to the beginning of available list. Thus, each addition and deletion of an clement involves corresponding deletion and addition in available list.
9.4. Static allocation Vs Linked allocation Now, let us see "What are the differences allocation?"The differences are listed below:
Used only when the data size IS fixed and known in advance before
2. The size of the memory to be allocated IS fixed during compilation time and can not be . altered during execution time
Linked allocation technique
Static allocation technique l.
2. As and when memory is required, memory can be allocated. Ir not required, memory can be deallocated. The size or the memory required may vary during execution time. 3.
Used only for memory requirement.
Systematic Approach to Data Structures using C - 9.7l
4. Execution is faster, since memory is 4. Execution is slower since memory already allocated and data has to be allocated during run time. Data manipulation is done onl y manipulation IS done on these after allocating the memory. allocated memory locations 5. Memory is allocated either in stack area (for local variables) or data area (for global and static variables).
5. Memory is allocated only in heap area
6. Data accessing is very fast and is 6. Data accessing is very slow. Data done by specifying the array name stored in the beginning of the list can be accessed very fast. But, to along with index. Time take to access a[O] and a[ 1000], in general access any other data, the list has to a[i] is same. be traversed and definitely requires more time 7. It is difficult to insert or delete the 7. The data can be inserted anywhere in the list. Addition or deleting of a data in the beginning or middle of the array. First, we have to make a node is done just by manipulating the links. room by copying the items into successive locations and then insert. While deleting an item, the subsequent elements should he copied into previous locations. 8. If we can predict the size of the data 8. If the size of the data can not be or if the size of the data is known in predicted or number of items to be advance, then it is better to go for inserted is not known in advance, static allocation then it is better to go for linked allocation 9. For n items only n memory 9. For n items, apart from n memory locations are allocated locations extra memory required for each node to store the addre~f the next node. So, more memory space is used for n items when compared with arrays. ote: For certain operations and applications linked allocation is more useful ail I efficientand for some other operations and applications sequential allocation is mor.: usefuland efficient. So, it is the responsibility of the programmer to choose the cI~![;! structuresproper! y for the efficient utilization of the resources.
9.72 Q Linked Lists
EXERCISES 1. Write a C function which will perform an insertion to the immediate left of the klh node in the singly linked list. 2. Write a C function to count the number of nodes' in a singly linked list. . - ' 3•. Write a C function to change theinfo field of the k" node to the value given by X. 4. Write a C function to concatenate two lists into a single list. 5. Write a C function to reverse a given. singly linked list without creating new nodes. (l. Write a C function search(p,x) that accepts a pointer p to a list of integers and an integer x and .rctums a pointer to a node containing x, if it exists, and the NULL pointer otherwise. 7. Write a C function srchinsrt(p,x) that adds an item x to the list pointed-to by p, provided x is not in the list. Insertion can be done at the front end or rear end. 8. Write a C function to delete a node from the front end and insert it at the-end of the list. 9. Write a recursive program to implement the following functions. a. To insert an item into an ordered singly linked list b. To insert an item into an ordered doubly linked list c. To display the contents of singly linked list d. To display the contents of doubly linked list e. To search for a specific node. f. To find the union of two linked lists g. To find the intersection of two linked lists h. To delete a node in a singly linked list whose position is specified
to Data Structures
Chapter 9: Other List structures' :.;~ ..
9.5 Circular sib-gly linked list, .
Note: IQ singly linked .list that we have discussed earlier, note that link field of las node contains \0 (null) indicating there are no more nodes from this point onwards.
Now, let us see "What are the disadvantages of singly linked lists?" The variou: disadvantages of singly linked lists are listed below: , • In a singly linked list, there is only one link field and hence traversing (visitin] each node) is done only in one direction. So, given the address of a node x, onh those nodes which' follow x are teachable but, the nodes 'that precede x are nr reachable. To reach the nodes that precede x, it is required to preserve a pointe first which contain the address of the first node of the list. .
Note: Since traversing is only in one direction, singly linked lists are also caller one W~ly lists. '
• To delete a designated node cur, address of the first node of the list should b provided. This is necessary because, to delete node cur, the predecessor of thi: node has to be found. For this, search has to begin from the first node ofthe list. These disadvantages can be overcome using special type of list called circular list Now, let us see "What is circular list?"
Definition: In singly linked list, the link field of the last node contains \0 (null) Instead of storing \0 in the link field. of last node, a number of advantages can be gained if link field of the last node contains starting address of the first node. Such l list is called circular list. In general, a circular list is a variation of ordinary linked Ii: in which link field of the last node contains address of the first node.
This list is primarily used in structures that allow access to nodes in the middle of the list without starting from the first node. The' pictorial representation of l circular list is shown below:
9.7~ Q Linked Lists
Fig. 9.5.1 Circular singly linked list
Now.Jet us see "What are the advantages circular list are shown below: . . • •
of circular lists?" The various advantages -
Every node is accessible from agiven link . field To delete a node cur, the address of necessary in singly linked list). Search initiated from cur itself. Certain operations on circular lists such will be more efficient
Now, let us see "What is the disadvantage
node by traversing
. the first node is not necessary (but it is tor the predecessor of node cur, can be •.
info = item; Step 2: Establish a link between the newly created node pointed to by temp and the first node. The corresponding code to accomplish this tusk is temp->link = head->link; Step 3: The newly created node pointed to by temp is made the first node by establishing a link between header node and temp using the following statement. head->link = temp; Step 4: Finally return the address of the header node using the following statement: return head;
to Data Structures
The complete C function is shown below: Example 9.7.1.1: Function to insert at the front end of the list NODE insert _front(int item, NODE head) < NODE temp;
temp = getnodet); temp->info = item;
1* Create a node, insert the item *1
temp->link = head->link; head->link = temp;
1* Insert at the front end *1
1* Return the header node */
9.7.2 Insert a node at the rear end Now, let us see "How to insert an item at the rear end?" To insert an item at the rear end of the list, it is necessary to obtain the address of the last node. This can be achieved by traversing the list from the first node. An auxiliary pointer variable cur, which initially points to the first node, can be used to traverse till the end. The statements to accomplish this task are: cur = head->link; while ( cur->link != head) < cur = cur->link; >
Once the address of the last cur is known, the node pointed to by temp can be easily inserted by following the sequence of steps shown in figure 9.7.2.1. The steps to be followed are shown below: Step 1: Establish a link between the last node cur and the node to be inserted at the end temp. This can be accomplished using the following statement cur->link = temp; Step 2: Establish a link between the new last node temp and the header node. This canbe achieved by using the following statement. temp->link = head; Step 3: Finally return address of the header node using the following statement: return head;
9.90 Q Linked Lists
Fig. 9.7.2.1 Insert an item at the rear Note:" All these steps have been designed by assuming the address of the node to be inserted i.e., temp is known. So, just before these steps, obtain the node to be inserted and store the item. The C function to insert an item at the rear end of the circular linked list is shown below: Example 9.7.2.1: Function to insert at the rear end of the list NODE insert reartint item, NODE head)
NODE temp, cur; temp = getnodet); temp->info = item;
1* node to be inserted *1
cur = head->link; while ( cur->link != head)
1* obtain address of the last node *1
.• cur->link = temp; temp->link = head; retu rn head; >
1* inscrt at the end *1 1* Return the address of the header
Systematic Approach to Data Structures using C - 9.9!.
9.7.3 Delete a node whose info field is specified Note: Refer section 9.3.9 for the details. As we discussed earlier in section 9.3.9, it is required to search for the node whose info field is specified and obtain the address of the node to be deleted along with its predecessor. So, two auxiliary pointer variables prey pointing to the predecessor of the node to be deleted and cur pointing to the node to be deleted are used. The search starts from the first node of list (head->link). So, point cur to the first node and prey to header node initially. When cur finally points to the header node, stop searching and indicate that the specified item is not there in the list. Otherwise, delete the node. The C function for this is shown below: Example 9.7.3.1: Function to delete a node whose info field is specified NODE delete _item(int item, NODE head) < NODE prev,cur; if ( head->link = head)
1* Check for empty list *1
printf("List is empty\n"); return NULL; >
prey = head; cur = head->link; while ( cur != head) < if (item = cur->info) break; prey = cur; cur = cur->link;
1* search for the item *1
1* Item not found *1
printf("Item not found\n"); return head; > the node
prev->link = cur->link; freenode( cur);
1* Rctui n the header node *1
9.92 Q Linked Lists 9.7.4 Insert a node at the specified position Note: Already discussed in section 9.3.13. But, because we are using header node, the design becomes simple and more efficient. Now, let us see "How to insert an item at specified position end?" Follow the sequence of operations: Step 1: As in the previous problem, obtain the address of the cur node and prey based on the position. We have to keep track of count to find the exact position. The equivalent statements are shown below: prey = head; cur = head->link; count = 1; ".while (cur != head) < if (count = pos) break; prey = cur; cur = cur->link; count++; >
Step 2: Check for the appropriate position. This statement: if (count != pos)
done usmg the following
printf("Invalid return head;
Note: If count is same as pos, it is valid position and it is required to insert a newly created node between cur and prey as shown in figure 9.7.4.1 Step 3:
/* obtain the node and insert the item */ temp = getnodet); temp->info = item;
" Step 4 and 5: /* insert the newly created node between prey and cur */ temp->link = cur; prev->link = temp; Step 6: Finally, return the address of the first node of the list. retu rn head;
Q Systematic Approach to Data Structures using C - 9.93 At 3rd position insert the node
Fig. 9.7.1.1. To delete a node at the specified position
The complete C function to insert an it~m at the specified position is shown below: Example 9.7.4.1: Function to insert an item at the specified position NODE insert ~osition(int
item, int pos, NODE head)
NODE prev, cur, temp; int i; prev = head; cur = head->link, count = 1; while (cur != head)
/* find the appropriate position*/
if (count = pos) break; prev = cur, cur = cur->link; count++; >
printf("Invalid return head; >
9.94 Q Linked Lists temp = getnodet); temp-e-info = item;
1* obtain a node and insert item*'
prev->link = temp; temp->link = cur;
/* Insert between prev an
9.7.5 Delete a node at the specified position Note: Already discussed in section 9.3.10. But, because we are using header node, the design becomes simple and complexity of the program will be simple. Follow the sequence
Step 1: Check for empty list and display the appropriate following code: if (head->link = head)
printf("List is empty\n"); return head;
Step 2: As in the previous problem, obtain the address of the cur node-to be deleted along with its prev node (predecessor of cur node). For this we have to keep track of counter to find the exact position. The equivalent statements are shown below: prev = head; cur = head->link; count = 1;
while (cur l= head)
if (count = pos) break; prev = cur; cur = cur->link; count++; >
to Data Structures
Step 3: Check for the appropriate position. This statement:
done usmg the following
printf("Invalid return head;
> Note: If count is same as pos, it is valid position and using cur node can be deleted asshown below:
3. So, third node is deleted.
Fig. 9.7.1.1. To delete a node at the specified position Step 4: Isolate the node pointed to by cur by establishing the link between the predecessor and successor of the node to be deleted using the statement: prev->link = cur->link; Step5: Delete the node pointed to by cur using the statement: freenode (cur); Step6: Finally return address of the header node. return head TheC function to delete at the specified position is shown below:
9.96 Q Linked Lists Example 9.7.5.1: Function to delete an item at the specified position NODE delete ~osition(int
NODE prev,cur; int i; if ( head->link = head)
1* Check for empty list *1
prey = head; cur = head->link; count = 1; while (cur != head) < if (count = pos) break; prey = cur; cur = cur->link; count++;
1* Find the appropriate position */
1* Position is invalid *1 position\n");
prev->link = cur->link; freenode( cur);
1* Delete at specified position */
The C function to display the contents of circular list with a header node is shown below:
to Data Structures
Example 9.7.5.2: Function to display the contents of circular list with header node void display(NODE head)
NODE temp; if (head->link = head)
printf("Contents of the list is\n"); temp = head->link; while(temp != head)
printf("%d ",temp->info); temp = temp->link; >
The complete C program to implement insert_front/rear or delete based on item and pas is shown below: Example 9.7.5.3: Program to insert_front/rear or delete based on item and pos #include #include #include struct node int struct node
>; typedef struct node* NODE;
9.98 .Q Linked Lists , t
1* Include: 1* Include: 1* Include: 1* Include: 1* Include: 1* Include: 1* Include: 1* Include:
Example Example Example Example Example Example Example Example
9.2.1.3: 9.2.1.4: 9.7.1.1: 9.7.2.1: 9.7.3.1: 9.7.4.1: 9.7.5.1: 9.7.5.2:
Function to get new node from the availability list *1 C Function to free a node to tOOa ai t list.>! rlink; The node pointed to by temp can be easily inserted between head node and the node pointed to by cur (follow the dotted lines). This can be accomplished by using the following statements. head->rlink = temp; temp->llink = head; temp->rlink = cur; cur->llink = temp;
Figure 9.8.1.1 To insert a node at the front end
The C function to insert at the front of a doubly linked circular list with a header node is shown in example 9.8.1.1. Example 9.8.1.1: Function to insert a node at the front end of the list NODE insert_front(int item, NODE head)
to Data Structures
temp = getnodet); temp->info = item;
1* Node to be inserted *1
1* obtain address of first node *1
head->rlink = temp; temp->l1ink = head; temp->rlink = cur; cur->llink = temp;
1* Insert between header node and first node *1
1* return the header node *1
9.8.2 Insert a node at the rear end To insert a node at the rear end of the list, consider the list shown in fig.9.8.2.1 and try to write the corresponding code. After writing the code compare this with the function insert _ frontt). Note that the two functions are same except that llink and rlinkhave been exchanged. Note: The reader should know the simplicity of the code using double linked circular list with header node. The C function to insert an item at the rear end of the list is shownbelow:
Figure 9.8.2.1 To insert a node at the rear end
9.104 Q Linked Lists Example 9.8.2.1: Function to insert an item at the rear end NODE insertrearunt
temp = getnode 0; temp->info = item;
1* Node to be inserted *1
1* obtain address of the last node *1
head->llink = temp; temp->rlink = head; temp->llink = cur; cur->rlink = temp;
1* Insert at the end of the list *1
1* return the header node *1
> 9.8.3 Delete a node from the front end Consider the list shown in fig.9.8.3.l. Find the address of the first node to be deleted using the statement: cur = head->rlink; Also obtain the successor of the node to be deleted using the statement: next = cur->rlink;
Figure 9.8.3.1 To delete a node at the front end Once the addresses of the node to be deleted, its predecessor and successor are known, following the sequence of numbers shown in fig.9.8.3.1, the node at the front end can be deleted. The steps to be followed are shown below.
to Data Structures
Step 1, 2: Establish a link between the header node and successor of the node to be deleted i.e., next in both directions. This can be accomplished using the statement head ->rlink = next; next->llink = head; Step 3: Once these statements are executed, the node to be deleted namely cur is isolated and it can be deleted. The corresponding statements are: printf("The item deleted is %d\n",cur->info); freenode( cur); Finally return the address of the header node. Note that all these steps have been designed by assuming list is already existing. If list is empty display the appropriate message. The C function to delete an item from the front end of the list is shown below: Example 9.8.3.1: Function to delete a node from the front end NODE delete_front(NODE < NODE cur, next; if ( head->rlink
1* Check for empty list *1
printf("Deque return head;
> cur = head->rlink; next = cur->rlink;
1* Obtain the first node *1 1* Obtain the second node*1
head->rlink = next; next->llink = head;
1* adjust pointers and delete the node *1
printf("The node to be deleted is %d\n",cur->info); freenode( cur);
1* Delete the first node *1
1* Return the address of the last node *1
9.106 Q Linked Lists 9.8.4 Delete a node from the rear end To delete a node at the rear end of the list, consider the list shown in fig.9.8.4.1 and try to write the corresponding code. After writing the code compare this with the function deletefrontt), Note: The two functions are same except that llink and rlink have been exchanged. The pointer variable next is replaced by the pointer variable pr;ev.
Figure 9.8.4.1 To delete a node at the rear end The C function to insert an item at the rear end of the list is shown below: Example 9.8.4.1: Function to delete a node from the rear end NODE delete _rear(NODE head)
NODE cur,prev; if ( head->llink = head)
printf("Deque is empty\n"); return head; >
cur = head->llink; prey = cur->llink;
1* obtain address of the last and last but one node *1
head->llink = prey; lprev->rlink = head;
1* adjust links in both directions *1
printf("The node to be deleted is %d\n",cur->info); freenode(cur); 1* delete the node
9.8.5 Delete a node whose information
to Data Structures
field is specified
This problem has already been discussed in section 9.7.3 using a singly linked circular list. Here, the address of the node to be deleted is obtained in the beginning using the statements: cur = head->rlink; while ( cur != head)
if (item = cur->info) break; cur = cur->rlink; >
If the item specified is not there in the list, the pointer variable cur points to the header node and so, display the appropriate message. The code for this can be if ( cur = head)
printf("Item not found\n"); return head; >
If item is present in the list, the address of the node to be deleted i.e., cur is known. Its predecessor can be obtained from the left link and its successor can be obtained from the right link using the statements: prev = cur->llink; /* address of the predecessor */ next = cur->rlink; /* address of the successor */ Now, consider the linked list shown below:
Figure 9.8.5.1 To delete a node whose information field is specified
9.108 Q Linked Lists The node pointed to by cur is the node to be deleted, the node pointed to by prey is the predecessor and the node pointed to by next is the successor of the node to be deleted. Once the addresses of these nodes are known, establish the link between predecessor and successor nodes and delete the node pointed to by cur. Following the sequence of steps shown in fig.9.8.5. the node cur can be deleted. The corresponding statements are: prev->rlink = next; next->llink = prev; freenode( cur); Finally, return the address of the header node. All these steps have been designed by assuming list is present. If list is not present, display the appropriate message. The C function to delete a node whose information field is specified is shown below: Example 9.8.5.1: Function to delete a node whose info is provided NODE delete_item(int item, NODE head)
NODE prev, cur, next; if ( head->rlink = head)
cur = head->rlink; while ( cur != head)
if (item = cur->info) break; cur = cur->rlink; > if ( cur = head)
printf("Item not found\n"); return head; >
/* find the address of node to be deleted */
to Data Structures
/* Obtain the address of the predecessor */
/* Obtain the address of the successor */
prev->rlink = next; next->llink = prev;
/* Adjust the pointers and delete */
freenode( cur); return head;
/* Return the header node */
9.8.6 Delete all nodes whose information
field is specified as key
The procedure for this problem is same as discussed in previous section. But, immediately after deleting the specified node, search for the key specified again from successor node onwards. If the key is found, delete the node and repeat the process. The modified C function to delete all nodes whose information is same as the key specified is shown below: Example 9.8.6.1: Function to delete all nodes whose info is same as key item NODE delete_all(int item, NODE head)
NODE prev, cur, next; int count; if ( head->rlink
printf("List is empty\n"); return head; >
/*assume key initially not present */
/* find the address of node to be deleted */
9.110 Q Linked Lists while ( cur != head) < if (item != cur->info) cur = cur->rlink; else
1* Update the number of occurrences *1
count++; prev next
I*Obtain the address of the predecessor*1 1* Obtain the address of the successor *1 1* Adjust the pointers and delete the node*1
next->llink = prev; freenode( cur); cur
1* seach for key from this point *1
if( count = 0) printf("Key not found\n"); else printf("Key found at %d positions and are deleted'n't.count); return head; >
In this function the variable count is used to find the number of occurrences of the key in the list. If key is found, the variable count is incremented by one and the corresponding node is deleted and search for the key from the next node onwards and repeat the process. Even after searching the entire list, if count is zero, it means that key is not there in the list. 9.8.7 Insert a node after the key and before the key Search for the specified key as explained in the section 9.7.5. Insert the specified item towards right of the node whose info is same as the key. Similarly an item can be inserted to the left of a designated node. The C functions, to insert an item towards right of a node and towards left of a.node are shown in examples 9.48 and 9.49 respectively. The reader is supposed to write the appropriate figures and trace these functions. The code is straightforward and simple.
to Data Structures
Example 9~8.7.1: Function to insert to the right of a specified node NODE insertrighuint item,NODE head) < NODE temp,cur,next; if ( head->rlink = head)
/* Check for empty list
printf("List is empty\n"); return head;
/* search for the key */
while ( cur != head) < if (item = cur->info ) break; cur = cur->rlink; >
/* Key information not found */
/*A node with key is found */ next = cur->rlink; .
/*obtain the address of the successor */
printf("Enter the item to insert towards right of %d = ",item); temp = getnodet); scanf("%d" ,&temp->info); cur->rlink = temp; temp->llink = cur; next->llink = temp; temp->rlink = next;
/* insert this new node between cur and next */
/* Return the header node */
9.112 Q Linked Lists Example 9.8.7.2: Function to insert to the left of a specified node NODE insert_left(int item,NODE head) < NODE temp, cur, prey; if ( head->r1ink = head)
1* Check for empty list */
printf("List is empty\n"); return head; >
cur = head->r1ink; while (cur != head)
1* search for the key *1
if (item = cur->info ) break; cur = cur->r1ink; >
1* Key not found *1
printf("Key not found\n"); return head; >
I*A node with key is found *1 prey = cur->l1ink; printf("Enter
1* Obtain the prdedessor *1
the item to inser towards left of%d
prev-e-rlink = temp; temp-xllink = prey; cur->1link = temp; temp->r1ink = cur;
1* insert between prey and cur *1
1* Return address of header *1
Systematic Approach to Data Structures using C - 9.11~
TheC program to implement all these operations discussed in this section, is shown below:
Example 9.8.7.3: Program to implement insert at front/rear/before/after deletefront/rearlbased on i,m/all nodes etc.
#include #include #include struct node
int info; struct node *llink; struct node *rlink; >; typedef struct node* NODE;
1* Include: Example 9.2.1.3: Function to get new node from the availability list */ 1* Include: Example 9.2.1.4: C Function to free a node to the availability list */ I
1* Include: Example 9.8.1.1: Function to insert a node at the front end of the list */ 1* Include: Example 9.8.2.1: Function to insert an item at the rear end */ 1* Include: Example 9.8.3.1: Function to delete a node from the front end */. 1* Include: Example 9.8.4.1: Function to delete a node from the rear end */ /
1* Include: Example 9.8.5.1: Function to delete a node whose info is provided */ / 1* Include: Example 9.8.6.1: Function to delete all nodes after searching for key *1, 1* Include: Example 9.8.7.1: Function to insert to the right of a specified node */ f
1* Include: Example 9.8.7.2: Function to insert to the left of a specified node */ /'
9.114 Q Linked Lists /* function to display the contents of the list */ void display(NODE head)
NODE temp; if ( head->rlink == head)
> .. printf("Contents of the deque is\n"); temp = head->rlink; while (temp != head)
p rin tf("%d ",temp->info ); temp = temp->rlink; >
to Data Structures
case 1: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); head = insert_ front(item,head); break; case 2: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); head = insertrearutem.head); break; case 3: head = delete_front(head); break; case 4: head = delete Jear(head); break; case 5: display(head); break; case 6: printf("Enter the item to be deleted\n"); scanf("%d" ,&item); head = delete_item(item,head); break; case 7: printf("Enter the key to be delted\n"); scanf("%d" ,&item); head = delete _ all(item,head); break; case 8: printf("Enter the key\n"); scanf("%d" ,&item); head = insert _right(item,head); break; case 9: printf("Enter the key\n"); scanf("%d" ,&item);
9.116 Q Linked Lists head = insert_Ieft(item,head); break; default: exit(O); > > >
'9.8.8 Singly Vs Doubly linked lists Now, let us see "What is the difference between singly linked and doubly linked list?" Singly linked list 1. Traversing is only in one direction
Doubly linked list 1. Traversing
2. While deleting a node, its predessor is 2. required and can be found only after traversing from the beginning of list 3. Occupy less memory 4. Programs will be lengthy and need more time to design
5. Care is taken to modify only one link ofa node
can be done m both directions deleting x, it While a node predecessor can be obtained using llink of node x. No need to traverse the list Occupy more memory Using circular linked list with header, . efficient and small programs can be written and hence design is easier Care is taken to modify both links of a node
Now, let us see "What are the advantages of doubly linked lists?" The advantages of doubly linked lists are shown below: • Using doubly linked lists with a header node most of the problems can be solved very easily and effectively. • The doubly linked lists are extensively used in trees. The hierarchical structure of the tree can be easily represented using a doubly linked list. • Graphs can be represented using doubly linked list. Now, let us see "What are the disadvantages of doubly linked lists?" Some of the disadvantages of doubly linked lists are: • Each node in the list requires two links one is forward link and the other backward link requiring additional storage for each field. • While manipulating the lists extra care should be taken to manipulate both links.
to Data Structures
Exercises 1. Write a C function to check whether a given string is a palindrome using a doubly linked list. 2. Mention few advantages of a header node. 3. What are the advantages and disadvantages of dynamic data structures? 4. Compare and contrast static data structures with dynamic data structures. 5. Explain the advantages and disadvantages of representing a groups of items as an array versus a linear linked list. 6. What are the shortcomings of a singly linked list? How these are eliminated in circular list? 9.9 Application of linked lists In this section, let us see "What are the applications of linked lists?" The various applications of linked lists are shown below: Arithmetic operations on long positive numbers Applications of linked lists
Manipulation of polynomials
Evaluation of polynomials In symbol table construction (Compiler design)
9.9.1 Addition of two long positive numbers Now, Ietus see "Why very large numbers can not be added using + operator?" Some applications may require various operations on very large numbers. But, all the computers have a certain maximum number of bits required for representing an integer, float etc. If the size of the numbers exceed this limit, ordinary arithmetic operations can not be performed. Using linked lists, we can represent these large numbers and any arithmetic operation can be performed on these large numbers. Now, let us see "How to write algorithm/function to add two long positive numbers?" This achieved by splitting the program into various modules based on activity performed as shown below: • Reading a long positive number • Writing a long positive number • Adding tw9 long positive numbers Now, let us see "How to read a long positive number using linked list?"
9.118 Q Linked Lists Design: Let us design by taking the number 6698274. This number can be split into groups of one digit each as shown below from the most significant digit to least significant digit. 6,6,9,8,2,7,4 Since there are 7 digits, a singly linked list with seven nodes can be used to store each digit in each node. Consider the way the numbers are displayed on the display portion of the calculator. If the number 6698274 is typed, display portion of the calculator may look like as shown below. 6 66 669 6698 66982 669827 6698274 Note that as the new digits are typed, old digits will be shifted one digit left thereby making room for the most recently typed digit. Thus the first digit typed will be the leftmost digit of the number and the last digit typed will be the right most digit of the number. Ifthe position of the least significant digit i.e., right most digit of a number is considered as the front end, the digits that are typed will be inserted at the front end. The linked representation for the number typed i.e., 669827 using circular singly linked list with a header node is shown in fig.9.9.1.1. The next digit typed i.e., 4 will be the new least significant digit and has to be inserted immediately after the header node. Inserting immediately after the header node is considered as inserting an element from the front end. Inserting temp, a node containing the digit 4 at the front end of the list is shown using gray lines in fig.9.9.1.1. The resultant integer stored in the result will be 6698274.
1* Check for empty number *1
does not exist\n");
1* number of digits in the number *1
a = (int *) malloc( n * sizeof(int) );1* allocate memory for n digits *1 cur
1* Copy the number into array a *1 1* Copy the number into an array *1
while (cur != head)
a[k++] = cur->info; cur = cur->link; >
while (--k != -1 ) printf("%d",a[k]);
1* display the result in reverse form *1
Now, we know the method of reading and displaying a number. Now, let us see "How to add two numbers using linked list?" Suppose the two numbers to be added are 987 and 86. These two numbers can be represented using circular linked list with a header node as shown below:
Figure 9.9.1.2 Two numbers represented as linked lists These two numbers should be added digit by digit from right to left i.e., from least significant digit to most significant digit. A pointer variable c1 can be used to access the digits from the first list and a pointer variable c2 can be used to access the digits
Systematic Approach to Data Structures using C - 9.121
fromthe second list. The corresponding digits along with a carry (initial carry 0 ) are added. From the result obtained say sum, extract the digit using: digit = sum % 10; and carry by dividing sum by 10 i.e., carry = sum / 10; In this case when we add 7 and 6, the sum obtained is 13. digit = 13 % 10 = 3 carry = 13 / 10 = 1 Add the resulting digit at the end of the partial result obtained so far. So, function insertrear shown in example 9.5.2.1 section 9.5.2 can be used. Move on to the next digit in both the numbers by updating c1 and c2 and repeat the process. When the end of one of the list is encountered, add the carry to the remaining digits of the other list. The C function to add two long positive numbers is shown below: Example 9.9.1.3: Function to add two long positive numbers ODE add_long(NODE
hI, NODE h2, NODE h3)
NODE c,c 1,c2,h; int sum, carry, digit; carry = 0; cl = hl->link; c2 = h2->link;
/*Initial carry is zero */ /* Points to the first digit of the first number */ /* Points to the first digit of the second number */
/* add the two numbers digit by digit along with carry */ while (cl != hI && c2 != h2 ) < sum = c 1->info + c2->info + carry; digit = sum % 10; /* Extract the result */ carry = sum / 10; /* Extract the carry */
h3 = insert Jear( digit,h3);
/* add the result to the partial output */
cl = cl->link; c2 = c2->link;
/* Point to the next digit of 1st number */ /* Point to the next digit of ~nd number */
9.122 Q Linked Lists
1* Obtain the address of the remaining digits of bigger number *1 if( cl !=hl) c=cl,h=hl; else c =c2, h=h2;
1* Add the carry to the remaining digits of bigger number *1 while ( c l= h )
sum = c->info + carry; digit = sum % 10; carry = sum I 10; h3 = insertreartdigit.h'I); c = c->link; >
1* If carry add at the end of the result *1 if ( carry = 1 ) h3 = insertreartcarry.hs); return h3; > The complete structure of C program to add two long positive numbers is shown below: Example 9.9.1.4: C program to add two long positive numbers #include #include #include #include #include
int struct node
>; typedef struct node* NODE;
1* Include: Example 9.2.1.3: Function to get new node from the availability list *1 1* Include: Example 9.9.1.1: Function to read a long positive number *1
Include: Include: Include: Include:
Example Example Example Example
Function Function Function Function
to Data Structures
add two long positive numbers */ insert an item at the front end of the list * insert an item at the rear end of the list */ display a long positive integer */
NODE hl,h2,h3; hl = getnode/); h2 = getnodei); h3 = getnodet); h 1->link = hl ; h2->link = h2; h3->link = h3; hl->info = h2->info = h3->info = 0; Input printf("Enter the first number\n"); hl = read_number(hl);
Enter 1st number 99999
printf("Enter the second number\n"); h2 = read_number(h2);
Enter 2nd number 99999
printf("Numl printf("Num2 printf("Sum
); How to represent a polynomial using linked list?" us assume we have a polynomial consisting of only two variables x and y. Here, need to store co-efficient, power of x and power of y. So, a polynomial can be ear represented using a .linked list where each term can be considered as a node consist of four fields as shown below: • cf - to store the coefficient • px - to store the power of x • py - to store the power of y • link - which contains the address of the next term(node).
9.124 Q Linked Lists
The declaration for a node can be written as shown below: struct node
float float float struct node
typedef struct node* NODE; Now'; let us see "How to represent a polynomial 5x\,z + 3x2 + 4x3y -5 using a linked?" The following figure shows how the given polynomial is stored in a linked list. . cf
Figure 9.9.2.1 Representing a polynomial using linked list
Since there are four terms in the polynomial, it is represented as. a linked list consisting of four nodes. To design the algorithm, for the sake of simplicity we assume each term in the polynomial is unique i.e., each term has different powers ofx and y. Each term in the polynomial can have the same or different coefficient. We use a singly linked circular list with a header node. The pointer variable poly is used which contains address of the header node. 1 Each term of the polynomial can be inserted into the list from the rear end as . discussed in section 9.5.2. The C function to add a term from the rear end of the list is shown below:
~ Systematic Approach to Data Structures using C - 9.125
Example 9.9.2.1: Function to insert a term at the rear end NODE insertreartfloat
cf, float x, float y ,NODE head) .
NODE temp,cur; temp = getnodet); temp->cf = cf; temp->px = x; temp->py = y;
1* create a node and write polynomial */
cur = head->link; , while ( cur->link != head) cur = cur-c-link;
1* Obtain the address of the last node */
cur->link = temp; temp->link = head;
1* insert at the end of the list *1
1* return the header of a polynomial */
> By repeatedly invoking the function insertreari), while adding a term, a linked list representing a polynomial can be created. Once the co-efficient of term is -9999, stop adding the term to the list. If the co-efficient of a term is not equal to -9999, it is end of the polynomial and address of the header node is returned. The C function to read a polynomial is shown below: Example 9.9.2.2: Function to read a polynomial NODE read yoly(NODE
int i; float px; float py; float cf;
1* to hold power of x */ 1* To hold power ofy *1
the coefficient as -999 to end the polynomial\n");
/* To hold the co-efficient */
head = insert_rear(cf,px,py,head); > return head; >
Now, let us see "How to evaluate the polynomial?" To evaluate the polynomial we should know the values of the variables x and y. Once these values are known, substitute these values for the corresponding variables in each term and by adding all the terms, the result is obtained. The function to evaluate the polynomial is shown below: Example 9.9.2.3:Function to evaluate a polynomial with two variables float evaluate(NODE head) < float x,y,sum = 0; NODE poly; printf("Enter the value ofx and y\n"); scanf("%f %f' ,&x,&y); poly = head->link; while (poly != head)
/* Access each term, substitute x and y */
sum += poly->cf * pow(x,poly->px) poly = poly->link;
Now, let us see "How to display a polynomial represented as a linked list?" The function to display the polynomial represented as a circular linked list with a header node is shown below:
to Data Structures
Example 9.9.2.4: Function to display a polynomial void display(NODE head)
NODE temp; if ( head->link = head)
does not exist\n");
temp = head->link; while (temp != head)
printf("+%5.2fxl\%3.1fyl\%3.1f",temp->cf,temp->px,temp->py); temp = temp->link; >
printf("\n"); The main program to evaluate the polynomial is shown below: Example 9.9.2.5: C Program to evaluate a given polynomial #include #include #include #include struct node float float float struct node
>; typedef struct node* NODE; 1* Include: Example 1* Include: Example 1* Include: Example
'* Include: Example 1* Include: Example
9.2.1.3: 9.9.2.4: 9.9.2.3: 9.9.2.2: 9.9.2.1:
Function Function Function Function Function
get new node from the availability list */ display a polynomial */ evaluate a polynomial with two variables read a polynomial */ insert a term at the rear end */
9.12& Q Linked Lists void mairu)
NODE head; float res; head = getnodet); head->link = head; printf("Enter the polynomial'n"); head = readpolyihead); res = evaluate(head); printf("The given polynomial is\n"); display(head); printf("The result = %f\n",res); > Note: The polynomial 5x\,z + 3x2 + 4x3y - 5 with value x = 1 and y = 2 can b entered as shown below: Output Enter the polynomial Enter the co-efficient as -999 to end the polynomial Enter the 1stterm Coeff = 5 pow x = 3 pow y = 2 Enter the 2nd term Coeff= 3 pow x = 2
Enter the 3rd term Coeff= 4 pow x = 3
Enter the 4th term Coeff= -5 pow x = 0
Enter the 5th term Coeff= -999 Enter the value of x and y 12 The given polynomial is +5.00xI\3.0yI\2.0
The result = 26.00000
~ Systematic Approach to Data Structures using C - 9.129 9.9.3 Addition of two polynomials Once we know the method of reading, displaying and evaluating a polynomial, now the next question is "How to add two polynomials?" Design: Let use circular list with a header node to represent a polynomial as discussed in previous section. The pointer variable h I contains address of the header node of the first polynomial and pointer variable h2 points to the header node of the second polynomial. The first polynomial can be accessed from link of h l and the second polynomial can be accessed from link of h2. The procedure to be followed while adding two polynomials is shown below. • Search for the next term of first polynomial in the second polynomial • if found then add the coefficients of both terms. If the result is not zero add the result to the resulting polynomial. else add the term of first polynomial to the resulting polynomial endif This process has to be repeated until all the terms of the first polynomial are over. So, the first version of the algorithm can be pI = link(hI) while p l !=hI < Search for the next term of first polynomial in the second polynomial if found then add the coefficients of both terms. If the result is not zero i.e., two terms can not be cancelled, add the result to the resulting polynomial. else add the term of first polynomial to the resulting polynomial
endif p l = link(pl);
Let us discuss how to search for the next term of the first polynomial in the second polynomial. The first term of the first polynomial can be obtained using the statements
9.130 Q Linked Lists xl = px(PI); yl = py(pI); cfl = cf(PI); provided the pointer variable p l contains the address of the first term in the polynomial. To obtain the successive terms using the above sets of statements, point the , pointer variable p l to successive nodes one after the other. This term should be compared with each term of the second polynomial. This can be done using the following set of statements p2 = link(h2); while (p2 != h2 )
x2 = px(P2); y2 = py(P2); cf'2 = cf(P2); if(xl
After executing these statements, if p2 and h2 are same, it means that the term of the first polynomial is not present in the second polynomial. Otherwise, the term is present. Searching for the next term in the first polynomial is over. After searching, the following statement has to be executed. if found then add the coefficients of both terms. If the result is not zero add the result to the resulting polynomial. else add the term of first polynomial to the resulting polynomial endif The code for the above statement can be written as if (p2 != h2) 1* term is present */ < cf= cfl + cf'2 if ( cf!= 0) h3 = insertreartcf.x l.y l.hf); >else h3 = insert Jear( cfl,x 1,yl ,h3);
Systematic Approach to Data Structures using C - 9.131
else /* add the first term to the resultant polynomial */ h3 = insertreartcft.x l.yl.hj); /* point the pointer variable p l to point to the next term */ p l = link(pl);
9.132 Q Linked Lists When all the terms in the first polynomial are compared with the second polynomial, the remaining terms of the second polynomial can be simply inserted into the resultant polynomial. To check for the remaining terms of the second polynomial, one more field called flag can be added. Initially, flag field of each node in the second polynomial is zero. Once the coefficients of two terms are added make flag field of the current term in. the second polynomial as 1. So, the flag field of each node in the second list corresponding to the second polynomial may be 1 or 0. If flag field is 0, it means that the corresponding term is not there in the first polynomial. The code to copy the remaining terms of the second polynomial is p2 = link(h2) while (p2 != h2 )
Finally address of the header node of the resultant polynomial function to add two polynomials is shown below: Example 9.9.3.1: Function to add two polynomials NODE add . ooly(NODE hI, NODE h2, NODE h3) < ·~uJJ.I!, 1.p2; in l x i ,Al,y 1,y2,ct1 ,c12,ct;
p l = h i -;-1:1li(; while (pI !=h1)
1* obtain the next term of the first polynomial *1 xl = p1->px; y1 = p1->py; cfl = p l->cf;
to Data Structures
1* seach for this term in the second polynomial *1 p2 = h2->link; while ( p2 != h2 )
x2 = p2->px; y2 = p2->py; cfl = p2->cf; if (xl = x2 && y1 = y2 ) break; p2 = p2->link; >
1* if term of 1st polynomial is present */
1* add the coefficients *1
p2->f1ag = 1; 1* insert into resultant polynomial */ if( cf!= 0) h3 = insertreartcf.x l.y l.h.l); >
1* insert 1st term into resultant polynomial */ insert rearfcflx I.y l.h'I);
1* obtain the next term of 1st polynomial *1
the remaining terms of second polynomial to the result *1 p2 = h2->link; while (p2 1=h2 )
The complete C program to add two polynomials is shown below:
9.134 Q Linked Lists Example 9.9.3.2: Program to add two polynomials #include #include #include #include
float cf; float px; float py; int flag; struct node *link; >; typedef struct node* NODE; /* /* /* /*
Include: Include: Include: Include:
Example Example Example Example
Function Function Function Function
get new node from the availability list */ display a polynomial */ add two polynomials */ read a polynomial */
NODE insertreartfloat cf, float x, float y ,NODE head) < NODE temp, cur; temp = getnodet); temp->cf = cf; temp->px = x; temp->py = y; temp->flag
cur = head->link; while ( cur->link != head) cur = cur->link;
/* Obtain the address of the last node */
cur->link = temp; temp->link = head;
/* insert at the end of the list */
Systematic Approach to Data Structures using C - 9.13!
h l = getnodet); h2 = getnodet); h3 = getnodet); hl->link = hl ; h2->link = h2; h3->link = h3; printf("Enter the first polynomial\n"); hl = read polythl ); printf("Enter the second polynomial\n"); h2 = read polythz); h3 = add--'poly(hl,h2,h3); printf("The first polynomial is\n"); displayfhl ); printf("The second polynomial is\n"); display(h2); printf("The sum of two polynomials is\n"); display(h3);
ote: Consider the two polynomials: 5x\,2 + 6xy + 3xy + 5 and 10x3y + 4x3 + 3xl + lO~ + 7. The sum of these two polynomials will be 5x\,2 + 9xy + 3xy + 12 + 10x3~ + 4x3 + 101. The polynomials should be entered as shown below: Output Enterthe first polynomial Enterthe co-efficient as -999 to end the polynomial Enterthe I5t term Coeff= 5 pow x = 3 pow Y = 2 Enterthe 2nd term Coeff= 6 pow x = I pow y = 3 Enterthe 3rd term Coeff= 3 pow x = I pow Y = I Enterthe 4 tit. term Coeff= 5 pow x = 0 pow y = 0 Enterthe s" term -999 Enterthe second polynomial
9.136 Q Linked Lists Enter the co-efficient as -999 to end the polynomial Enter the 1SI term Coeff = 10 pow x = 3 pow y = 3 Enter the 2nd term Coeff = 4 pow x = 3 pow y = 0 Enter the 3rd term Coeff = 3 pow x = 1 pow Y = 3 Enter the 41h term Coeff = 10 pow x = 0 pow y = 3 Enter the 5th term Coeff = 7 pow x = 0 pow y = 0 Enter'the 6th term Coeff= -999 The first polynomial is '.. +5.00x"3.0y"2.0 + 6.00x"1.0y"3.0 + 3.00xilltO);
/* visit leftsubtree in postorder*/ /* visit rightsubtree in postorder*/ /* visit the node */
Example 12.4.2.4: Traverse the following tree in preorder Solution: Easiest method of writing pre order traversal is to start from innermost square and visit each node in the sequence specified as shown below:
.Q Systematic Approach to Data Structures using C - 10.17
The above tree now can be written as shown below:
The above tree can be now written as shown below:
10.18 Q Trees The preorder traversal by observing the tree and following the numbers in sequence is shown below:
Example 12.4.2.5: Easiest method of writing inorder traversal is to start from innermost square and visit each node in the sequence specified as shown below:
G D H The above ee now can be written as:
Systematic Approach to Data Structures using C - 10.1
Theabove tree can be now written as shown below:
In order traversal is G D H B A E I C F The inorder traversal by observing the tree and following the numbers in sequence shownbelow:
Example 12.4.2.6: Easiest method of writing postorder traversal is to start frc innermost square and visit each node in the sequence specified as shown below:
'ryl~above tree now =1'
F can be written as:
to Data Structures
if (root = NULL) return; display(root->rlink,
for (i = 0; i info);
> 10-4.3 Searching Now, let us see "How to search for a key in a binary tree?" By traversing the tree in any of the order one can visit each node. As we visit the node we can compare the information field of each node with the key to be searched. If found, display successful search, otherwise display unsuccessful search. Here, we use inorder traversal technique. The equivalent C function is shown below: Example 10.4.3.1: Function to search for an item using inorder traversal void search(int item, NODE root, int *flag)
search(item, root->llink, flag);
/* Traverse left subtree */
if ( item = root->info )
*flag = 1; return; > search(item, root->rlink, flag);
/* Traverse right subtree */
Note: In the above function, apart from item and root the other parameter passed is flag which is a pointer to an integer. If an item is present in the tree, its value is set to 1 and the control is returned to the calling function. So, just before invoking the function searcht), the flag should be set to 0 and should be invoked as shown below:
flag = 0; search(item, root, &flag); if (flag = 1) printf("Search successful"); else printf("Unsuccessful search");
Note: .The program to search for an item using preorder is shown below: Example 10.4.3.2: Function to search for an item using preorder traversal void search(int item, NODE root, int *flag) < if ( root = NULL) return; if (item = root->info )
1* Visit the node *1'
*flag = 1; return; > search(item, root->llink, flag); search(item, root->rlink, flag);
1* Traverse left subtree *1 1* Traverse right subtree *1
> Note: The program to search for an item using postorder is shown below: Example 10.4.3.3: Function to search for an item using postorder traversal void search(int item, NODE root, int *flag)
if ( root = NULL) return; search(item, root->llink, flag); search(item, root->rlink, flag);
1* Traverse left subtree *1 1* Traverse right subtree *1
to Data Structures
1* Visit the node *1
The complete C program for creating a tree, traversing the tree and searching for a specified item in the tree is shown below: Example 10.4.3.4: C Program to create a tree, traverse and search for an item #include #indude #include #include struct node int struct node struct node
info; *llink; *rlink;
typedef struct node* NODE;
1* Include: 1* Include: 1* Include: 1* Include: 1* Include: 1* Include: 1* Include:
Example Example Example Example Example Example Example
9.2.1.3:C Function to get a new node from availability list *1 10.4.2.1: Display the contents of the tree in preorder *1 10.4.2.2: Function traverse the tree in inorder *1 10.4.2.3: Function traverse the tree in postorder *1 12.4.2.7: C function to print the tree in tree form *1 10.4.3.1/2/3: Function to search for item *1 10.4.1.1: Function to insert item into tree based on direction *1
NODE root = NULL; int choice, item, flag;
to Data Structures
break; case 5: if ( root = NULL) printf("Tree is empty\n"); else
printf("The given tree is\n"); display(root, 1); printf("Enter item to search\n"); scanf("%d", &item); flag = 0; searchiitem, root, &flag); if (flag = 1 ) printf("Seach successful\n"); else printf("Unsuccessful search\n"); >
ote:Let us create the tree shown in figure 10.5.a. The sequence of input to be providedto create the tree is shown below:
Systematic Approach to Data Structures using C - 10.27
10-4.4 Copying a tree The C function to obtain the exact copy of the given tree using recursion is shown below: It is self-explanatory. In this function address of the root node is given and after copying, it returns address of the root node of the new tree. ,
Example 10.4.4.1: Function to get the exact copy of a tree NODE copy(NODE root)
1* Tree does not exist *1
if ( root = NULL) return NULL; temp
temp->info temp->lptr temp->rptr
root->info; = copy(root->lptr); = copy(root->rptr); =
I*Create a new node */ I*copy the information *1 /*Copy the appropriate links */
1* return address of the new root *1
10-5Binary search tree (RST) Now, let us see "What is a binary search tree?" Definition: A binary search tree is a binary tree in which for each node say x in the tree, elements in the left-subtree are less than info(x) and elements in the right subtree . are greater or equal to info(x). Every node in the tree should satisfy this condition, if leftsubtree or right subtree exists. Fig. 10.4.4.1 shows some of the binary search trees. Note: Traversal of a binary search tree is same as traversal of a binary tree as explainedin see 10-4.2. Other common operations performed on binary search trees are .• Insertion - An item is inserted • Searching - Search for a specific item in the tree ,. Deletion - Deleting a node from a given tree.
Figure 10.4.4.1 Binary search trees 10-5.1 Insertion Now, let us see "How to create a binary search?" Creating a binary search tree is nothing but repeated insertion of an item into the existing tree. So, we concentrate on how to insert an item into the tree. In a BST (Binary Search Tree), items towards left subtree of a node x will be less than info(x) and the items in the right subtree are greater or equal to info(x). Consider the BST shown below: l
if ( item info ) prev->llink = temp; else prev->rlink = temp; Note: The above steps can be executed provided the tree exists. If the tree is empty initially, then make the node pointed to by temp itself as root node. The complete C function to insert an item into a binary search tree is shown below:
10.30 Q Trees Example 10.5.1.1: Function to insert an item into a binary search tree (with duplicate elements) NODE insert(int item, NODE root) < NODE temp,cur,prev; temp = getnodet); temp->info = item; temp->llink = NULL; temp->rlink = NULL;
1* Obtain new node from the availability list */ 1* Copy appropriate data *1
if ( root = NULL) return temp;
1* Insert a node for the first time *1
prev = NULL; cur = root; while ( cur != NULL) < pre v = cur; if (item info ) cur = cur->llink; else cur = cur->rlink;
1* find the position to insert *1
1* Obtain parent position *1 1* Obtain left child position *1 1* or *1 1* Obtain right child position *1
if ( item info ) prev->llink = temp; else prev->rlink = temp;
1* Ifnode to be inserted info = item; temp->llink: = NULL; temp->rlink = NULL; if ( root
to Data Structures
1* Copy appropriate data *1
NULL) return temp;
prey = NULL; cur = root; while ( cur != NULL )
1* Insert a node for the first time *1 1* find the position to insert *1
1* Obtain parent position *1
if ( item = cur->info )
1* do not insert duplicate item *1
printf("Duplicate free(temp); return root;
items not allowed\n");
if (item info ) cur = cur->llink; else cur = cur->rlink;
1* Obtain left child position *1 1* or *1 1* Obtain right child position *1
if ( item info ) prev->llink: = temp; else prev->rlink = temp;
1* If node to be inserted info) break; if ( item info ) root = root->l1ink; else root = root->rlink; >
1* Key not found *1
printf("Item not found\n"); return root; >
The recursive function to search for an item is shown below: Example 10.5.2.1: Function to search for an item in BST using recursion NODE recursive_search(int
root->info ) return root;
if ( item info ) return recursive_search(item, root->l1ink); return recursive _ search(item, root->rlink); >
Q Systematic Approach to Data Structures using C - 10.33
10-5.3 Other operations Various other useful operations are shown below. • find maximum - to return maximum item in the tree • find minimum - to return minimum item in the tree • to find height of the tree • to count the number of nodes • to count the leaf nodes • deletion - deleting a node: from the tree 10-5.3.1 To find maximum value in a tree BST Let us see "How to fmd maximum value in a binary search tree?" Given a binary search"tree, a node with maximum value is obtained by traversing and obtaining the right most node in the tree. If there is no right subtree then return root itself as the node containing the item with highest value. The corresponding C function is shown below: Example 10.5.3.1.1:
Function to return the address of highest item in BST
if (root = NULL) return root; cur = root; while ( cur->rlink: != NULL)
/* obtain right most node in BST */
10-5.3.2 To find minimum value in a BST Let us see "How to find minimum value in a binary search tree?" Given a binary search tree, a node with least value is obtained by traversing and obtaining the left most node in the tree. If there is no left subtree then return root itself as the node containing an item with least value. The corresponding C function is shown below:
10.34 Q Trees Example 10.5.3.2.1: Function to return the address of least item in BST NODE minimum(NODE
NODE cur; if (root = NULL) return root; cur = root; while ( cur->llink != NULL )
1* obtain left most node in BST *1
return cur; > 10-5.3.3 Height of tree Let us see "How to find the height of the tree?" Height of the tree is nothing but the maximum level in a tree. The recursive definition to compute the height of the tree is shown below: -I
< 1 + max ( height(root->llink), height(root->rlink )) otherwise
The corresponding C function to find the height of the tree is shown below: Example 10.5.3.3.1: Function to find the height of the tree
1* function to find maximum of two numbers *1 int max(iot a, int b)
return ( a> b ) ? a : b; >
1* Function to find the height of the tree *1 int height(NODE root)
if ( root = NULL) return -1; return 1 + max( height(root->llink), height(root->rlink) ); >
to Data Structures
10-5.3.4 Count nodes in a tree Now, let us see "How to is obtained by traversing counter whenever a node is initialed to zero before used to visit each node. shown below:
count the nodes in a tree?" The number of nodes in the tree the tree in any of the traversal technique and increment the is visited. The variable count can be a global variable and it calling this function. In this example, the inorder traversal is The C function to obtain the number of nodes in a tree is
Example 10.5.3.4.1: Function to count the number of nodes in a tree void count_node(NODE
if ( root = = NULL) return; count_ node(root->llink); count++; count_ node(root->r1ink);
·10-5.3.5 Count leaves in a tree Now, let us see "How to compute the number of leaves in a tree?" As in the previous case visit each node in a given tree. Whenever a leaf is encountered update count by one. A leaf or a terminal node is one, which has an empty left and empty right child. The variable count can be a global variable and it is initialed to zero to start with. The function to count the leaves in a binary tree is shown below: Example 10.5.3;5.1: Function to count the leaves or terminal nodes in a tree void count_leaf(NODE root) < if ( root = NULL) return ; count_leaf(root->llink);
/* Traverse recursively towards left */
/* if a node has empty left and empty right child? */ if (root->llink = NULL && root->r1ink = NULL) count++; count_leaf(root->r1ink); >
/* Traverse recursively towards right */
10.36 Q Trees 10-5.3.6 Delete a node from the tree It is very important to remember that once the required node is found and deleted, ina binary search tree the ordering of the tree should be maintained i.e., even after deleting a node, elements in the left subtree should be lesser and elements in the right subtree should be greater or equal. Let us see "What are the activities to be performed to delete a node?" The various activities to be performed are shown below: Case 1: An empty left subtree and non empty right subtree or an empty right subtree and nonempty left subtree Note: A node having empty left child and empty right child is also deleted using this case. Consider the figures shown below where cur denotes the node to be deleted and in both cases one of the subtrees is empty and the other is non-empty. The node identified by parent is the parent of node cur. The non empty subtree can be obtained and is saved in a variable q. The corresponding code is: if (cur->llink = NULL) q = cur->rlink; else if ( cur->rlink = NULL) q = cur->llink;
1* Ifleft subtree is empty *1 1* non empty right sub tree is saved*1 1* If right subtree is empty *1 1* non empty left sub tree is saved*1
Figure 10.5.3.6.1. To delete a node cur from the tree
Case 2: Non empty left subtree and non empty right subtree: Consider the figures shown below where cur denotes the node to be deleted. In both cases both the subtrees are non-empty. The node identified by parent is the parent of the node cur.
~ Systematic Approach to Data Structures using C - 10.37 parent
Figure 10.5.3.6.1. To delete a node cur from the tree parent
Obtain right subtree of the node to be deleted
Attach left subtree of node to be deleted to left of inorder successor
Fig.10.5.3.6.2: To delete node cur from the tree
10.38 Q Trees The node can be easily deleted using the following procedure in sequence: Step 1: Find the inorder successor of the node to be deleted. The corresponding code is shown below: suc = cur->rlink;
1* Inorder successor always lies towards right */ 1* and immediately keep traversing left *
while ( suc->llink != NULL)
Step 2: Attach left sub tree of the node to be deleted to the left of successor of the node to be .deleted. The corresponding code is: suc->llink
1* Attach left of node to be deleted to left of
successor of the node to be deleted */ Step 3: Obtain the right subtree of the node to be deleted. The corresponding codeis: q = cur->rlink;
1* Right subtree is obtained *1
Attach the node q to parent: Now, after case 1 or case 2, it is required to attachthe right sub tree of the node to be deleted to the parent of the node to be deleted. If parent of the node to be deleted does not exist, then return q itself as the root node usingthe statement: if (parent = NULL) return q; If parent exists for the node to be deleted, attach the subtree pointed to by q, to the parent of the node to be deleted. In this case, attach q to parent based on the direction. If cur is the left child, attach q to left(parent) otherwise attach q to right(parent). This can be achieved by using the following statement
1* connecting parent of the node to be deleted to q *1 if ( cur
= parent->llink ) parent->llink = q
else parent->rlink = q; Once the node q is attached to the parent, the node pointed to by cur can be deleted and then return the address of the root node. The corresponding statements are:
to Data Structures
free (cur); return root; All these statements have been written by assuming the node to be deleted cur and its parent node is known. So, just before deleting, search for the specified node, obtain its parent and then delete the node. The complete function to delete an item from the tree is shown below: Example 10.5.3.6.1: Function to delete an item from the tree NODE delete _item(int item, NODE root)
printf("Tree is empty! Item not found\n"); return root; >
parent = NULL, cur = root; while (cur != NULL)
I*obtain node to be deleted, its parent *1
if (item = cur->info) break; parent = cur; cur = ( item info ) ? cur->llink : cur->rlink; >
printf("Item not found\n"); return root; >
1* Item found and delete it *1 if ( cur->llink = NULL) q = cur->rlink; else if ( cur->rlink = NULL) q = cur->l1ink; else
1* CASE 1 *1 1* If left subtree is empty *1 1* obtain non empty right sub tree *1 1* If right subtree is empty *1,. 1* obtain non empty left subtree *1 1* CASE 2 *1 1* obtain the inorder successor *1
10.40 Q Trees while (suc->llink != NULL) sue = suc->llink; suc->llink = cur->llink;
1* Attach left of node to be deleted to *1 I*left of successor of node to be deleted•
1* Right subtree is obtained *1
> if (parent = NULL) return q;
1* If parent does not exist return q as root*
1* connecting parent of the node to be deleted to q *1 if ( cur = parent->llink ) parent->llink = q; else parent->rlink = q; free(cur); return root; > The complete program for creating a tree, traversing and deleting a specified itemis shown below: Example 10.5.3.6.2: C program to create a tree, traverse a tree and delete an item from the tree #include #include . #include struct node
int struct node struct node
info; *llink; *rlink;
>; typedef struct node* NODE;
1* Include: Example 10.5.3.6.1: Function to delete an item from the tree *1 1* Include: Example 10.5.1.2: Function to insert an item into binary search tree *1 1* Include Example 10.4.2.1: Display the c ntents of the tree in preorder *1
to Data Structures
10.4.2.2: Function traverse the tree in inorder */ '* Include: Example 10.4.2.3: Function traverse the tree in post order */ '* Include: Example 12.4.2.7: C function to print the tree in tree form */ * Include: Example 9.2.1.3: C Function to get a new node from availability list */ void maim)
NODE root, temp; int choice, item; root = NULL; for (;;)
printf("The given tree in tree form is\n"); display(root, 1); printf("Inorder traversal is\n"); inorder(root); printf("\n"); >
break; case 3: if ( root = NULL) printf("Tree is empty\n");
10-5.3.7 Binary search tree as a priority queue Let us see "How a binary search tree can be used as a priority queue?" Binary search tree can be used as a priority queue. To implement ascending priority queue, create a binary search tree such that elements in the left subtree of any node say x will be less than info(x) and elements in the right subtree will be greater than or equal to info(x). Once the tree is created search for the least item and delete from the tree. All these functions are already implemented and the C program for this is shown below: Example 10.5.3.7.1: C program to implement priority queue #include #include #include #include
int struct node struct node >;
info; *llink; *rlink;
to Data Structures
typedef struct node* NODE;
1* Include: Example 1* Include: Example 1* Include: Example 1* Include: Example 1* Include: Example 1* Include: Example
10.5.3.6.1: Function to delete an item from the tree */ 10.5.1.2: Function to insert an item into binary search tree */ 10.4.2.2: Function traverse the tree in inorder */ 12.4.2.7: C function to print the tree in tree form */ 9.2.1.3: C Function to get a new node from availability list */ 10.5.3.2.1: Function to return the address ofleast item in BST */
printf(" 1:Insert 2:Display\n"); printf("3 :delete 4:Exit\n"); printf("Enter the choice\n"); scanf("%d" ,&choice); switch( choice)
case 1: prlntf(t'Enter the item to be inserted\n"); scanf("%d~' ,&item); root = insert (item, root); break; . case 2: if ( root = NULL) printf("Priority que is empty\n"); else
10.44 Q Trees case 3: temp = minimum(root); if ( temp = NULL ) printf("Priority que is empty\n"); else < -
item = temp->info; printf("The deleted item is %d\n",item); root = delete_item(item, root); > break; default: exit(O); > >
> 10-6 Applications Now, let us see "What are the applications of binary search trees?" Some of the applications of binary search trees are shown below: • searching and sorting • manipulation of arithmetic expressions • Constructing symbol table. • The trees are also used in syntax analysis of compiler design and are used to display the structure of a sentence in a language. Some applications are discussed in this section. 10.6.1 Searching In binary tree to search for an item, each node has to be compared. But, if the treeis binary search tree then the comparison will be restricted to either the left subtree or the right subtree. Comparison starts from the root node and moves downward towards the leaves. The number of comparisons can be greatly reduced using binary search tree. It has been discussed in detail in section 10.5.2 10.6.2 Sorting Once the binary search tree is created, traversing this tree in inorder, the elements will be displayed in ascending order.
Q Systematic Approach to Data Structures
10.6.3 Expression trees A sequence of operators and operands that reduces to a single value is called an expression.Let us consider only arithmetic operators such as: +, -, * and /. First, let us see"What is an expression tree?"
Definition:An expression tree is a binary tree that satisfy the following properties: Any leaf is an operand t, The root and internal nodes and operators t The subtrees represent sub expressions with root of the subtree as an operator. t
Letus see "How an infix expression can be written using expression tree?" An infix expressionconsisting of operators and operands can be represented using a binary tree withroot as the operator. The left and right subtrees are the left and right operands of thatoperator. A node containing an operator is not a leaf where as a node containing anoperand is a leaf. The tree representation for the infix expression ((6+(3-2)*5) /\ 2 + 3) isshown in figure below: Let us traverse the tree in preorder and postorder as shown:
Systematic Approach to Data Structures using C - 10.47'
+ D 3 +$C23 +$+6B23 +$+6*A523 +$+6*-32523
D 3+ C2 $3+ 6B+2$3+ 6A5*+2$3+ 632-5*+2$3+
Note: In an expression tree, we observe that if the expression tree is traversed in preorder we get prefix expression and if we traverse in postorder we get postfix expression.In fact, if we traverse in inorder, we get infix expression without brackets. 10.6.4Create binary tree for the postfix expression Letus see "What is the procedure to obtain an expression tree from the postfix expression?" The procedure to be followed while creating an expression tree using postfixexpression is shown below: • Scan the symbol from left to right. • Create a node for the scanned symbol. • If the symbol is an operand push the corresponding node onto the stack. • If the symbol is an operator, pop one node from the stack and attach to the right of the corresponding node with an operator. The first popped node represents the right operand. Pop one more node from the stack and attach to the left. Push the node corresponding to the operator on to the stack. • Repeat through step 1 for each symbol in the postfix expression. Finally when scanning of all the symbols from the postfix expression is over, address of the root node of the expression tree is on top of the stack. Thefollowing C function creates a binary tree for the valid postfix expression.
10.48 Q Trees Example 10.6.4.1: Function to create an expression tree for the postfix expression NODE creat_tree(char
NODE temp, st[20]; int i,k; char symbol; for ( i = k = 0; ( symbol = postfix[i] ) != '\0'; i++) < temp = getnode(); 1* Obtain a node for each operator *1 temp->info = symbol; temp->llink = temp->rlink = NULL; if( isalnum(symbol) ) st[k++] = temp; else
1* Push the operand node on to the stack */
1* Obtain 2nd operand from stack */ 1* Obtain 1st operand from stack */
temp->rlink = st[--k]; temp->llink = st[--k]; st[k++] = temp;
i* Push operator node on to stack */
1* Return the root of the expression tree */
Now, let us see "How to evaluate the expression?" In the expression trees, whenever an operator is encountered, evaluate the expression in the left subtree and evaluate the expression in the right sub tree and perform the operation. The recursive definition to evaluate the expression represented by an expression tree is shown below: Eval(root->llink) op E~al(roo!->rlink)
if root ->info is operator
ifroot->info is operand
The C function for the above recurrence relation to evaluate represented by an expression tree is shown below:
to Data Structures
Example10.6.5.1: Function to evaluate the tree floateval(NODE root)
I float nurn; switch( root->info)
case '+': return eval(root->llink) + eval(root->rlink); case '_I: return eval(root->llink) - eval(root->rlink); case 'I': return eval(root->llink) I eval(root->rlink); case '*': return eval(root->llink) * eval(root->rlink); case '$': case '''I: return pow (eval(root->llink),eval(root->rlink)); default : if (isalpha(root->info) ) < printf("%c %f' ,&nurn); return num; >else return root->info - '0'; > Thecomplete C program to evaluate an expression using expression tree is shown below: Example 10.6.5.2: C program to create an expression tree and evaluate #inc!ude #include #include #include #include #include
10.50 Q Trees #defme STACK SIZE 20 struct node < char struct node struct node
info; *llink; *rlink;
typedef struct node* NODE;
1* Include: Example 9.2.1.3: C Function to get a new node from availability list */ 1* Include: Example 10.6.5.1: Function to evaluate the tree *1 1* Include: Example 10.6.4.1: Function to create expression tree for postfx exprsin*1 void maim) < char postfix[40]; float res; NODE root = NULL; printf("Enter the postfix expression\n"); scanf("%s" ,postfix); root = creat_ tree(postfix); res = eval(root); printf("Result
> Output Enter the postfix expression abc-d*+e"f+ e=1 a=6 b=3 c=2 d=5 f=7 Result = 18.0000
I I Input I Enter postfix expression I 632-5*+ 1"7+ I I I Output I Result I
10.7 Tree operations
to Data Structures
using sequential representation
Insection 10.3 we have seen as to how a tree can creation of a binary search tree and different representation is ~iscussed in this section. The sequentialrepresentation over linked representation
be represented using an array. The traversal techniques using array advantages and disadvantages of is also discussed.
10.7.1 Creation of a binary search tree and traversal techniques The second approach discussed in section 10.3 to represent a binary tree using sequential allocation is used. The complete program in C to create the binary search treeand to traverse the tree in inorder, preorder and postorder is shown below: Example 10.7.1.1: C Program to create a tree and traverse the tree using array representation #inc1ude include #defineMAX SIZE 100 typedef int NODE; /*function to insert an item */ voidinsert(int item, NODE am
only if cur points to root node. So, initially cur points to the root node. Once thenode is visited, next is to traverse the left subtree in preorder. For this descend the tree towards left. Once all the nodes in the left subtree are displayed, it may be requiredto ascend the parts of the tree to display the nodes in the right subtree, To ascend thetree later, just before descending towards left, push the address of current node cur and then descend the tree left. This process has to be repeated till end of left subtreeis encountered. The code corresponding to this can be written as while ( cur != NULL)
printf("%d ",cur->info); s[++top] = cur; cur = cur->1link; >
1* Visit the node *1 1* push(cur, &top, s) *1 1* traverse left *1
Q Systematic Approach to Data Structures
In the tree shown in figure below, after executing these statements 100,50 and 25 will be displayed.
Figure 10.8.1 Binary search tree Once traversing the left subtree in pre order is over, traverse the right subtree in preorder i.e., ascend the tree by poppipg the address of the node most recently pushed and descend towards right subtree. This is possible only when the stack is not empty. If the stack is empty traversing the tree in preorder is complete and the program terminates. The code corresponding to this is shown below: if ( top != -1 )
1* If stack is not empty *1
cur = s[top-- ]; cur = cur->rlink;
1* Obtain the recent node from the stack *1 1* traverse right *1
else return; After descending the tree towards right, entire right sub tree has to be traversed in preorder. So, the above set of statements has to be repeated. The complete C function forthis is shown below: Example 10.8.1: Function for iterative preorder traversal void preorder(NODE root)
NODE cur, s[20]; int top = -1;
10.56 Q Trees if ( root = NULL)
while (cur != NULL)
printf("%d ",cur->info); s[++top] = cur; cur = cur->llink;
/* Visit the node */ /* push(cur, &top, s) */ /* traverse left */
/* If stack is not empty */
cur = s[top--]; cur = cur-c-rlink;
/* Obtain the recent node from the stack */ /* traverse right */
> else return; > > 1
8.2 Iterative inorder traversal
In this traversal technique, first left subtree is traversed in inorder, then the node is visited and finally the right subtree is traversed. As in iterative preorder traversal, traverse the left sub tree in inorder by descending the tree towards left until cur which initially points to root node is NULL. Before updating the pointer cur towards left, push its address so as to descend towards right subtree later. The code corresponding to this can be while ( cur != NULL ) < s[++top] = cur; cur = cur->llink; >
/* push(cur,&top,s); /* traverse left*/
to Data Structures
Oncethe left subtree is traversed, visit the node by popping the most recently pushed node on to the stack and then traverse towards right if the stack is not empty. If the stackis empty, traversing the tree in inorder is over and the procedure is terminated. Thecode to achieve this can be if (top !=-1)
/* If stack not empty */
cur = s[top--]; printf("%d ",cur->info); cur = cur->r1ink;
/* Remove recent node from stack */ /* visit node */ /* traverse right */
else return; Aftertraversing towards right, traverse the tree in inorder and repeat the process. This canbe achieved by executing all the above statements. The C function to traverse the treein inorder is shown below: Example 10.8.2: Function for iterative inorder traversal '* display the contents of the tree in inorder *1 void inorder(NODE root) < NODE cur,s[20]; int top = -1; if ( root = NULL)
s[++top] = cur; cur = cur->l1ink; >
/* push(cur,&top,s); /* traverse left*/
10.58 Q Trees /* If stack not empty */ if (top != -1 ) < cur = s[top--]; /* Remove recent node from stack */ printf("%d ",cur->info); /* visit node */ cur = cur->rlink; /* traverse right */ >
10.8.3 Iterative postorder
In postorder traversal, traverse the left subtree in postorder, then traverse the right subtree in postorder and fmally visit the node. Here also stack is used. But, each node will be stacked twice once during traversing the left-subtree and another while traversing towards right. Just to distinguish that traversing the right subtree is over, we set the flag to -1. So, check the flag field of the corresponding node. If flag field of a node is -ve, right subtree is traversed and one can visit the node. Otherwise traverse the right subtree. This process is repeated till the stack is empty. The C function for this is shown below: 1
Example 10.8.3: Function for iterative postorder traversal void postorder(NODE
NODE struct stack int
/* Check for empty stack */
Systematic Approach to Data Structures using C - 10.59
while ( cur != NULL)
top++; s[top].address = cur; s[top].f1ag = 1; cur = cur->llink;
> /* -ve values on stack indicate right subtree is * traversed and the node can be visited */ while ( s[top ].f1ag info);
if (top = -1 ) return; > /* ascend to traverse the right subtree */ cur = s[top].address; /* cur = pop(&top,s); */ cur = cur->rlink; s[top ].f1ag = -1; /*-ve indicates right subtree is traversed */ >
Thecomplete C program to create the tree and traversing using iterative technique is shownbelow: Example 10.8.3: Program to create a tree and to traverse (Iteration) #include #include #include
10.60 Q Trees struct node
int struct node struct node
info; *llink; *rlink;
typedef struct node* NODE; 1* 1* 1* 1* 1*
Include: Include: Include: Include: Include:
Example Example Example Example Example
10.8.1: Function for iterative preorder traversal *1 10.8.2: Function for iterative inorder traversal *1 10.8.3: Function for iterative postorder traversal *1 10.5.1.1: Function to insert an item into a binary search tree *1 9.2.1.3: C Function to get a new node from availability list */
case 1: printf("Enter the item to be inserted\n"); scan f("%d" ,&item); root = insert(item,root); break; case 2: preorder( root); printf("\n"); break;
Q Systematic Approach to Data Structures using C - 10.61 case 3: inorder(root); printf("\n"); break; case 4: postorder( root); ~ printf("\n"); break; default: exit(O); >
Now, let us see "What are the disadvantages of binary trees?" The various disadvantages of the binary tree are shown below: • In a binary tree, more than 50% of link fields have \0 (null) values and more memory space is wasted by storing \0 (null) values • Traversing a tree with binary tree is time consuming. This is because, the traversal of a tree either uses implicit stack (in case of recursive programs) or explicit stack (in case of iterative programs). Whatever it is stack is must. Most of the time is spent in pushing and popping activities during traversing. • Computations of predecessor and successor of given nodes is time consuming • In binary trees, only downward movements are possible All these disadvantages can be overcome using threaded see"What is threaded binary tree?"
binary tree. Now, let us
Definition: In a binary tree, more than 50% of link fields have \0 (null) values and more space is wasted by the presence of \0 (null) values. These link fields which contains \0 characters can be replaced by address of some nodes in the tree which facilitate upward movement in the tree. These extra links which contains addresses of somenodes (pointers) are called threads and the tree is termed as threaded binary tree. In general, a threaded binary tree is a binary tree which contains threads (i.e., addresses of some nodes) which facilitate upward movement in the tree.
10.62 Q Trees Now, let us see "What are the various types of threaded binary trees?" A binary treeis threaded based on the traversal technique. Since there are three traversal techniques, threaded binary trees are classified into three types as shown below:
Types of threaded bi tr mary ees
In-threaded binary trees . Pos-threaded bmary trees Pre-threaded binary trees
Now, let us see "What is in-threaded binary trees?" Definition: In a binary tree, if llink (left link) of any node contains \0 (null) andifit is replaced by address of the inorder predecessor, then the resulting tree is calledleft in-threaded binary tree. In a binary tree, if rlink (right link) of a node is NULL andif it is replaced by address of inorder successor, the resulting tree is called right in threaded binary tree, An in-threaded binary tree or inorder threading of a binary tree is the once which is both left in-threaded and right in-threaded. For example, consider the binary tree shown below:
Fig. 10.9.1 Binary tree with a header node In the above binary tree, if the right link of a node is NULL and if it is replaced by the address of the inorder successor as shown using dotted lines in fig. 10.9.2, then the tree is said to be right in-threaded binary tree.
to Data Structures
(b) Figure 10.9.2: Right in-threaded binary tree Now, let us see "How to implement right in-threaded binary tree in C language?" To implement a right in-thread an extra field rthread is used. If rthread is 1 the corresponding right link represents a thread and if rthread is 0 the right link represents an ordinary link connecting the right subtree. Thus a node can be defined as shown below: struct node
int info; struct node *llink; struct node *rlink; int rthread;
Pointer to the left subtree */ Pointer to the right subtree */ 1 indicates the presence of a thread*/ 0 indicates the absence of a thread */
typedef struct node* NODE; For a binary tree shown in figure 10.9.1, if the left field of a node is NULL and is replaced by the inorder predecessor as shown in fig.10.9.3, then the tree is said to be left in-threaded binary tree. Here also an extra field [thread is used where 1 indicates the presence of a thread and ordinary link connecting the left subtree.
tTI:J2J Figure 10.9.3 Left in threaded binary tree
Figure 10.9.4 In-threaded binary tree (inorder threading of binary tree)
to Data Structures
Thus a node can be defined as struct node
int struct node struct node int
info; *llink; *r1ink; lthread;
1* Pointer to the left subtree */ 1* Pointer to the right subtree *1 1* 1 indicates a thread else ordinary link */
>; typedef struct node* NODE; An inorder threading of a binary tree or in-threaded binary tree is one which is left in-threaded and right in-threaded and is shown in fig. 10.9.4. Here two extra fields [thread and rthread as defined earlier are used and the structure of the node can be defined as shown below: struct node
int info; struct node *llink; 1* Pointer to the left sub tree *1 struct node *r1ink; /* Pointer to the right subtree *1 int lthread; 1* 1 indicate a thread else ordinary link */ int rthread; >; It is desirable to have a header node so as to solve the problems more easily. In this case, the header node serves as the predecessor of the first node and successor of the last node. This imposes a circular structure on the tree. When the tree is empty, the header node is represented as shown in fig. 10.9.5. The tree is attached always to the left field of the header node. head
Fig.10.9.S Empty tree with a header node Now let us see, "How to find the inorder successor and predece sor?' and "How to traverse the tree in inorder?"
10.66 Q Trees 10.9.1 Inorder successor for right in-thread Consider the right in-threaded binary tree shown in fig. 10.9.2. Given a node X, if rthread is 1, which indicates the presence of thread, its rlink gives the address of the inorder successor. If rthread is 0, rlink contains the address of the right subtree. Left most node in the right sub tree is the inorder successor. The C function is shown below: Example 10.9.1.1: Function to fmd the inorder successor NODE inorder_successor(NODE < NODE temp; temp
if (x->rthread = 1 ) return temp; /*Obtain the left most node in the right subtree */ while ( temp->llink != NULL) temp = temp->llink; return temp; >
10.9.2 Inorder traversal
of right in-thread
The C function to traverse the tree in inorder is straightforward required to trace this program. The C function is shown below: Exa
pIe 10.9.2.1: Function to traverse the tree in inorder
void inorder(NODE head) < NODE temp; if ( head->llink = head)
and the reader is
Q Systematic Approach to Data Structures
printf("The inorder traversal of the tree is\n"); temp = head; for (;;) < temp
if (temp = head) return; printf("%d ",temp->info); >
10.9.3 Insert left and insert right This function inserts item towards left of node x only if its left child is empty and is shownbelow: Example 10.9.3.1: Function to insert towards left of a node void insert_Ieft(int item, NODE x) < NODE temp; temp = getnodet); temp->info = item; x->llink = temp; temp->llink = NULL; temp->rlink = x; temp->rthread = 1;
Thisfunction inserts an item towards right of node x only if its right child is a thread and is shown below: Example 10.9.3.2: Function to insert towards right void insertrightfint
Q Systematic Approach to Data Structures using C - 10.67 printf("The inorder traversal of the tree is\n"); temp = head; for (;;)
temp = inorder_successor(temp); if ( temp = head) return; printf("%d ",temp->info); >
10.9.3Insert left and insert right This function inserts item towards left of node x only if its left child is empty and is shownbelow: Example 10.9.3.1: Function to insert towards left ofa node void insert_left(int item, NODE x)
temp->info = item; x->llink = temp; temp->Hink = NULL; temp->rlink = x; temp->rthread = 1;
Thisfunction inserts an item towards right of node x only if its right child is a thread and is shown below: Example 10.9.3.2: Function to insert towards right void insertrightfint
10.68 Q Trees temp
r = x->rlink; x->rlink = temp; x->rthread = 0; temp->llink = NULL; temp->rlink = r; temp->rthread = 1; >
10.9.4 Insert an item to a right threaded binary tree This function finds the appropriate position to insert an item based on the directions. . Initially the pointer variable cur points to the root node. If the direction is '1'('L') and if left child is NULL then the item is inserted towards left of cur, otherwise cur is updated to point towards left subtree. Similarly if the direction is 'r' and rthread of cur is 1 indicating a thread, item is inserted towards right at that point, otherwise cur is updated to point towards the right subtree. The function to insert an item into a right in-threaded binary tree is shown below: Example 10.9.4.1: Function to construct the threaded binary tree NODE insert(int item, NODE head)
char direction; NODE cur; if ( head->llink = NULL) . < insert _left( item,head); retu rn head; >cur = head->llink; for (;;)
printff'Tnsert %d towards left",item); printf(" or right of%d (l/r) ",item,cur->info);
Q Systematic Approach to Data Structures using C - 10.69 direction
printf("\n"); fflush(stdin); if ( direction = '1')
if (cur->llink = NULL)
insert_left(item,cur); return head; >
insert Jight(item,cur); return head; > else cur
The complete program to create a right in-threaded binary tree and traversing the tree in inorder is shown below: Example 10.9.4.2: Construct a threaded tree and traverse in inorder #include #inc1ude #inc1ude #include
10.70 Q Trees '. struct node
int struct node struct node int
info; *llink; *rlink; rthread;
typedef struct node* NODE; /* /* /* /* /* /*
Include: Example Include: Example Include: Example Include: Example Include: Example Include:Example
9.2.1.3: C Function to get a new node from availability list */ 10.9.1.1: Function to find the inorder successor */ 10.9.2.1: Function to traverse the tree in inorder */ 10.9.3.1: Function to insert towards left of a node */ 10.9.3.2: Function to insert towards right */ 10.9.4.1: Function to construct the threaded binary tree */
NODE head; int choice, item; head = getnodet); head->rlink = head; head->rthread = 0; head->llink = NULL; for (;;)
printf(" 1:Insert 2:Inorder\n"); printf("3 :Exit\n"); printf("Enter the choice\n"); scanf("%d" ,&choice); switch( choice)
case 1: printf("Enter the item to be inserted\n"); scanf("%d" ,&item); head = insert(item,head); break;
to Data Structures
case 2: inorder(head) ; printf("\n"); break; default: exit(O); >
for left in-thread
Itis symmetric to the function inorder_successorO i.e., llink is replaced by rlink and viceversa and rthread is replaced by lthread. The C function for this is shown below: Example10.9.5.1: Function to find the inorder predecessor NODE inorderyredecessor(NODE
NODE temp; temp = x->llink; if (x->lthread = 1 ) return temp; /*Obtain the right most node in the left subtree */ while (temp->r1ink l= NULL) temp = temp->r1ink; return temp;
Now, let us see "What is pre-threaded binary trees?" Definition:In a binary tree, if llink (left link) of any node contains \0 (null) and isreplacedby address of the preorder predecessor, then the resulting tree is called re-threadedbinary tree In a binary tree, if rlink (right link) of a node is NULL if itis replaced by address of preorder successor, the resulting tree is called right hreadedbinary tree. A pre-threaded binary tree or preorder threading of a binary istheonce which is both left pre-threaded and right pre-threaded.
if it left and pretree
10.72 Q Trees Now, let us see "What is post-threaded binary trees?" Definition: In a binary tree, if Ilink (left link) of any node contains \0 (null) and if it is replaced by address of the postorder predecessor, then the resulting tree is called left post-threaded binary tree. In a binary tree, if rlink (right link) of a node is NULL and if it is replaced by address of postorder successor, the resulting tree is called right post-threaded binary tree. A post-threaded binary tree or postorder threading of a binary tree is the once which is both left pro-threaded and right pro-threaded. 10.9.6 Advantages and disadvantages Now, let us see "What are the advantages of threaded binary trees?" The various advantages of the binary tree are shown below: • In a binary tree, more than 50% of link fields have \0 (null) values and more memory space is wasted by storing \0 (null) values. This wastage of memory space is avoided by storing addresses of some nodes. • Traversing of a threaded binary tree is very fast. This is because, it does not use implicit or explicit stack. • Computations of predecessor and successor of given nodes is very easy and efficient • Any node can be accessed from any other node. Using threads, upward movement is possible and using links downward movement is possible. Thus, in a threaded binary tree, we can move in either directions. This is not possible in un-threaded binary trees. • Even though insertion into a threaded binary tree and deletion from a threaded binary are time consuming operations, they are very easy to implement. Now, let us see "What are the disadvantages of threaded binary trees?" The various disadvantages of threaded binary trees are shown below: • Here extra fields are required to check whether a link is a thread or not and hence occupy more memory when compared with un-threaded binary trees. • Insertion and deletion of a node consumes more time than its counter part because many fields have to be modified. EXERCISES 1. What is a tree? What are the various operations that can be performed on trees? 2. Write recursive functions to implement various traversal techniques 3. Write an iterative function to traverse the tree in inorder
Q Systematic Approach to Data Structures
Write an iterative function to traverse the tree in preorder Write an iterative function to traverse the tree in postorder Write an iterative function inseru) to insert an element into a tree Write a recursive function to insert an element into a tree Write a program to create a tree and traverse the tree in preorder, inorder and postorder using arrays. 9. Obtain a directed tree for the given infix expression (A+B)*(C+DY'E. 10.Write a program to implement priority queues 11.Write a program to implement find maximum and minimum in a tree 12.Show that in a complete binary tree the total number of edges is given by 2(nt - 1), where n, is the number of leaf nodes. 13.Write a C function to obtain the sum of contents of all the nodes in a given binary tree of integers. 14.Write a C function that accepts a pointer to a node in a binary search tree and deletes the smallest/largest item from the tree. 15.Write an iterative C function to obtain the copy of a given binary tree. 16.Write a C function to determine the number of leaves in a threaded binary tree (right in thread or left in thread) 17.Write a C function to find the kth element in the pre order traversal of an unthreaded binary tree. Lab Problem 3: Write a C program, which accepts the Internet Protocol (IP) address in decimal dot format (ex:153.18.8.105) and convert it into 32-bit long integer (ex:2568095849) using strtok library function and unions. Solution: The structure of the IP-ADDRESS is shown below: 1000
LJii4L~Llitl1bJ (Decimal) (Binary) (Hexadecimal)
So, given the string 153.18.8.105, extract 153 and copy into field4, extract 18 and copy into field3, extract 8 and copy to field2 and extract 105 and copy to fieldl. Then, print 32-bit long integer as shown in following program.
10.74 Q Trees #include #include #include typedef struct
unsigned field4:8; unsigned field3:8; unsigned field2:8; unsigned field 1:8; > IP-DOT - FORMAT; typedef union < IP_DOT_FORMAT long int
> IP_ADDRESS; void maint)
char a[13]; IP ADDRESS t:, char *p;
printf("Enter IP address in dot format\n"); scanf("%s",a);
Enter IPaddress in dot format 153.18.8.105
p = strtok(a,"."); i.ip.fieldl = atoi(p); p = strtok(NULL, "."); i.ip.field2 = atoi(p); p = strtok(NULL, "."); i.ip.field3 = atoi(p); p = strtok(NULL, "."); i.ip.field4 = atoi(p); printf("32 bit long int >
32 bit long int
Chapter 11: Sorting and'Searching What are we studying in this chapter?
• Bubble sort • Selection sort • Simple merge • Merge sort • Quick sort
Tree sorts such as binary tree sort and heap sort
Priority queue using heap
Insertion sorts such as simple insertion sort, Shell sort, Address calculation sort
11.1 Introduction Sorting is an important concept that is extensively used in the field of computer science and in day today life. Suppose we want to search for the telephone number of a person in the telephone directory. If the telephone directory is not sorted in alphabetical order, we may have to search for the entire telephone directory just to know whether the telephone number of a person exists or not. Since the telephone directory is sorted, we know how easy is to search for telephone number. So, it is required to arrange the names in alphabetical order. There are so many such applications in day to day life. Before proceeding further, let us ask the question "What is sorting? What are the various sorting techniques?" Definition: More often programmers will be working with large amount of data and it may be necessary to arrange them in ascending or descending order. This process of . rearranging the given elements so that they are in ascending order or descending order is called sorting. For example, consider the unsorted elements: 10,50,25,20,
11.2 Q Sorting and searching After sorting them in ascending order, the elements are rearranged as shown below: 10, 15,20,25,50 After sorting them in descending order, the elements are rearranged as shown below: 50,25,20,15,10 11.2 Bubble sort Before writing the algorithm or the program let us know the answer for" What is the concept used in bubble sort (Why it is also called sinking sort)?"
Procedure: This is the simplest and easiest sorting technique. In this technique, the two successive items A[i] and A[i+ 1] are exchanged whenever A[i] »= A[i+ 1]. For example, consider the elements shown below: 40,50,30,20,10 The elements can be sorted as shown in figure 11.2.1. In the first pass 40 is compared with 50 and they are in order. So, no exchange has been done. Next 50 is compared with 30 and they are exchanged since 50 is greater than 30. If we proceed in the same manner, at the end of the first pass the largest item occupies the last position. On each successive pass, the items with the next largest value will be moved to the bottom and thus elements are arranged in ascending order.
2nd Pass I 3rd Pass 14th Pass 'I~I/A\I~ 40P 30 30 30P20 20 IJ 10
