C LANGUAGE
DATA STRUCTURES THROUGH C
Unit I- Structure and Unions in C Language
Structures – Introduction, Features of Structures. Declaration and Initialization of Structures, Accessing structure members, structure initialization. Nested Structures, Array of Structures, Arrays within structures and Pointers to Structures, Structures and Functions, Bit Fields, Unions, Union of Structures. Example Programs on the topics mentioned above.
Unit II- File Input/Output: Introduction, Types of Files, File I/O Operations- High level I/O functions- Open & Close a file, Read and Write data into a file, Searching data in the file, Error handling during I/O operations on files. Command Line Arguments, Applications of Command Line Arguments. Example Programs on the topics covered in this unit.
Unit III- Introduction to data structures: classification of data structures, dynamic memory allocation functions in C language. Stacks: Definition, Various representation methods, operations on stacks and their implementation in C language, applications of stacks.
Unit IV- Queues: Definition, Various representation methods, operations on queues and their implementation in C language, applications of queues. Circular queues- operations on circular queues and their implementation in C language.
Unit V- Linked lists: Definition, Various representation methods, operations on linked lists and their implementation in C language.
Unit VI- Searchingand Sorting Techniques:
Searching Techniques- Linear search and Binary Search Techniques.
Sorting techniques- Bubble Sort, Selection Sort, Quick Sort, Insertion Sort, and Merge Sort. Implementation of all the above mentioned techniques in C language and trace them by giving different test data.
UNIT-I
STRUCTURES AND UNIONS
As we have seen earlier, Arrays can be used to represent a group of data items that belong to the same data type, such as int (or) float. However we cannot use an array if we want to represent a collection of data items of different types using a single name. Fortunately, c supports a constructed data type known as structures which is a mechanism for packing of data belong to different data types. A structure is a convenient tool for handling a group of logically related data items. For example is an employee record that consists of the name, date of birth, address, salary, ID number etc. of the person involved. A structure allows the programmer to group all these properties into one unit. Structures help to organize complex data in a more meaningful way.
Examples:
time:seconds,minutes,hours
date:day,month,year
book:author,title,price,year
address:name,doornumber,street,city
customer:name,telephone,city,catagory
Features of Structures:
To copy elements of one array to another array of same data type elements are copied one by one. It is not possible to copy elements at a time. Where as in structure it is possible to copy the contents of all structure elements of different data types to another structure variable of its type using assignment (=) operator. It is possible because structure elements are stored in successive memory locations.
Nesting of structures is possible i.e. one can create structure within the structure. Using this feature one can handle complex data types.
It is possible to pass structure elements to a function. This is similar to passing an ordinary variable to a function. One can pass individual structure elements (or) entire structure by value (or) address.
It is also possible to create structure pointers. We can also create a pointer pointing to structure elements. For this we require “->‟ operator.
Define a structure:
Definition: A structure is a collection of one or more variables grouped together under a single name for convenient handling. Here the variables that are grouped together can have different types.
(or)
A structure is a collection of heterogeneous data elements.
(or)
C Structure is a collection of different data types which are grouped together and each element in a C structure is called member.
If you want to access structure members in C, structure variable should be declared.
Many structure variables can be declared for same structure and memory will be allocated for each separately.
It is a best practice to initialize a structure to null while declaring, if we don’t assign any values to structure members.
Defining a structure: structure must be defined first their format and that may be used later to declare structure variables. Structureis defined using a keyword struct followed by the name of the structure (optional) followed by the body of the structure. The members of the structure are declared within the structure body. The general format of defining a structure is
Syntax: struct struct-name
{
data_type var-name1;
data_type var-name2;
.
.
data_type var-nameN;
};
Example:struct book_bank
{
char title[20];
char author[15];
int pages;
float price;
};
The keyword struct declares a structure to hold the details of structure members(or)structure elements .Each member may belong to a different type .structure name is the identifier which represents the name of the structure and is also called as structure tag. The tag name may be used subsequently to declare variables that have the tags structure. The structure body contains structure members(or)structure elements .For example
Example:struct book_bank
{
char title[20];
char author[15];
int pages;
float price;
};
Declaring structure variables: After defining a structure format we can declare variables of that type. we can declare structure variables using the structure-tag anywhere in the program. A structure variable declaration is similar to the declaration of variables of any other data types. It includes the following elements.
The keyword struct
The structure tag name
List of variable names separated by commas
A terminating semicolon
Syntax:struct structure_tag structure_var1, structure _var2,...... structure _varN;
Example:struct book_bank book1,book2,book3;
Each one of the variables has four members as specified by the template.
The complete declaration may look like this
Declaring Structure variables separately:
syntax:struct book_bank
{
char title[20];
char author[15];
int pages;
float price;
};struct book_bank book1,book2,book3;
Remember that the members of a structure themselves are not variables. They do not occupy any memory until they are associated with the structure variables.
Declaring Structure Variables with Structure definition (or) Tagged structure:
Tagged structure: It is also allowed to combine both the template declaration and variable declaration in one statement.
Syntax:struct book_bank
{
char title[20];
char author[15];
int pages;
float price;
} book1,book2,book3;
variable structure:The use of tag name is optional
syntax:struct
{
char title[20];
char author[15];
int pages;
float price;
} book1,book2,book3;
The above declares book1,book2, book3 as structure variables representing three books, but does not include a tag name. However, this approach is not recommended for two reasons.
Without a tag name, we cannot use it for future declarations
Normally, structure definitions appear at the time of beginning of the program file, before any variables (or) functions are defined. They may also appear before the main, along with macro definitions, such as #define. In such cases, the definition is global and can be used by other functions as well.
Accessing the Members of a structure:we can access and assign values to the members of structure in a number of ways. As we mentioned earlier, the members of the structure themselves are not the variables. They should be linked to the structure variable in order to make them meaningful members. The link between a member and a variable is established using the member operator '.' which is also known as 'dot operator'(or) period operator.
For example, book1.price is the variable representing the price of book1.
Here we can see how we would assign values to the members of book1
strcpy(book1.title,”basic”);
strcpy(book1.author,”balagurusamy”);
book1.pages=240;
book1.price=120.36;
We can also use scanf to give the values through the keyboard
scanf(“%s”,book1.title);
scanf(“%d”,&book1.pages);
Example: Define a structure type, struct personal that would contain person name, date of joining and salary, using this structure, write a c program to read this information for one person from the keyboard and print the same on the screen.
#include<stdio.h>
struct personal
{
char name[20];
int day;
char month[10];
int year;
float salary;
};
main()
{
struct personal person;
printf(“input values”);
scanf(“%s%d%s%d%f”,person.name,&person.day, person.month,
&person.year,&person.salary);
printf(“%s%d%d%d%f”,person.name,person.day,person.month,person.year,
person.salary);
}
Example#include <stdio.h>
#include <string.h>
struct student
{
int id;
char name[20];
float percentage;
} record;
main()
{
record.id=1;
strcpy(record.name, "Raju");
record.percentage = 86.5;
printf(" Id is: %d \n", record.id);
printf(" Name is: %s \n", record.name);
printf(" Percentage is: %f \n", record.percentage);
}
Example:#include <stdio.h>
#include <string.h>
struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
};
main( )
{
struct Books Book1; /* Declare Book1 of type Book */
struct Books Book2; /* Declare Book2 of type Book */
/* book 1 specification */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;
/* book 2 specification */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;
/* print Book1 info */
printf( "Book 1 title : %s\n", Book1.title);
printf( "Book 1 author : %s\n", Book1.author);
printf( "Book 1 subject : %s\n", Book1.subject);
printf( "Book 1 book_id : %d\n", Book1.book_id);
/* print Book2 info */
printf( "Book 2 title : %s\n", Book2.title);
printf( "Book 2 author : %s\n", Book2.author);
printf( "Book 2 subject : %s\n", Book2.subject);
printf( "Book 2 book_id : %d\n", Book2.book_id);
}
Output:Book 1 title : C Programming
Book 1 author : Nuha Ali
Book 1 subject : C Programming Tutorial
Book 1 book_id : 6495407
Book 2 title : Telecom Billing
Book 2 author : Zara Ali
Book 2 subject : Telecom Billing Tutorial
Book 2 book_id : 6495700
Structure Initialization:Like other variables, a structure variable also can be initialized at compile time.
Syntax: main()
{
struct
{
int age;
float height;
} student={50,150.96};
------
------
}
The above syntax assigns the value 50 to student.age and 150.96to student.height. There is one to one correspondence between the members and their initializing values.
Suppose you want to initialize more than one structure variable
syntax:main()
{
struct st_record
{
int age;
float height;
};
struct st_record student1={50,150.96};
struct st_record student2={30,120.16};
------
------
}
we have another method to initialize a structure variable outside of the function.\
syntax:struct st_record
{
int age;
float height;
}student1={50,150.96};
main()
{
struct st_record student2={30,120.16};
------
------
}
Note that compile time initialization of a structure variable must have the following elements.
The keyword struct
The structure tag name
The name of the variable to be declared
The assignment operator '='
A set of values for the members of the structure variable, separated by commas and enclosed in braces.
A terminating semicolon.
Rules for initializing structures:
We cannot initialize individual members inside the structure template.
The order of values enclosed in braces must match the order of members in the structure definition.
It is permitted to have partial initialization. we can initialize only the first few members and leave the remaining blank. The uninitialized members should be only at the end of the list.
The uninitialized members will be assigned default values as follows.
zero for integer and floating point numbers.
'\0' for character strings.
Example: write program for demonstrating structure member initialization
#include<stdio.h>
void main()
{
struct student/*Declaraing the student structure*/
{
int marks1,marks2,parks3;
};
struct student std1=(55,66,80):/*initializing ,marks for student 1*/
struct student std2=(60,85,78):/initializing marks for student 2*/
clrscr();
/*Displaying marks for student 1*/
print(“marks obtained by 1st student: %d and %d”,std1.marks1,std1.marks2.std1.marks3);
/*Displaying marks for student 2*/
printf(*\nMarks obtained by 2nd student: %d.%d”,std2.marks1.std2.marks2.std2.marks3);
getch();
}
Copying & Comparing Structure Variables:Two variables of the same structure type can be copied the same way as ordinary variables. If person1 and person2 belongs to the same structure, then the fallowing assignment operations are valid:
person1 = person2; ------assigns person1 to person2
person2 = person1; ------assigns person2 to person1
However, the statements such as,
person1 = = person2
person1! = person 2 are not permitted.
C does not permit any logical operations on structure variables. In such cases, we need to compare them by comparing the members individually.
Example: program to illustrate the comparison & copying of structure variables
#include<stdio.h>
struct class
{
int no;
char name[20];
float per;
};
main()
{
int x;
struct class stu1={111,”Ramu”,72.50};
struct class stu2={222,”Reddy”,67.00};
struct class stu3;
stu3=stu2;
x=(stu2.no==stu3.no&stu2.per==stu3.per)?1:0;
if(x==1)
printf(“\n student2 and student3 are same\n”);
else
printf(“\n student2 and student3 are different\n”);
}
Operations on Individual Members of the Structure:As pointed earlier, the individual members are identified using the member operator (.). A member with the dot operator along with its structure variable can be treated like any other variable name and therefore it can be manipulated using expressions and operators. Consider the previous example program; we can perform the following operations.
if( stu1.no = = 111)
stu1.per +=10.00;
float sum =stu1. per + stu2.per;
stu2.per *= 0.5;
We can also apply the increment and decrement operators to numeric type members. For example, the following statements are valid:
stu1.no++;
++ stu2.no;
Example: C Program to Store Information (name, roll and marks) of a Student Using Structure
#include <stdio.h>
struct student
{
char name[50];
int roll;
float marks;
};
main()
{
struct student s;
printf("Enter information of students:\n\n");
printf("Enter name: ");
scanf("%s",s.name);
printf("Enter roll number: ");
scanf("%d",&s.roll);
printf("Enter marks: ");
scanf("%f",&s.marks);
printf("\nDisplaying Information\n");
printf("Name: %s\n",s.name);
printf("Roll: %d\n",s.roll);
printf("Marks: %.2f\n",s.marks);
}
Output:Enter information of students:
Enter name: Adele
Enter roll number: 21
Enter marks: 334.5
Displaying Information
name: Adele
Roll: 21
Marks: 334.50
Structures within Structures [Nested Structures]:A structure within a structure means nesting of structures. Nesting of structures is permitted in C. Let us consider the fallowing structure defined to store information about the salary of employees.
struct salary
{
char name[20];
char dept[20];
int basic_pay;
int dearness_allowance;
int house_rent_allowance;
int city_allowance;
} employee;
This structure defines name, department, basic pay and three kinds of allowances. We can group all the items related to allowances together and declare them under a substructure as shown below:
struct salary
{
char name[20];
char dept[20];
struct
{
int dearness;
int house_rent;
int city;
} allowance;
} employee;
The “salary‟ structure contains a member named „allowance‟, which itself is a structure with three members. The members contained in the inner structure namely, dearness, house_rent, and city. These members can be referred to as:
employee.allowance.dearness;
employee.allowance.house_rent;
employee.allowance.city;
An inner-most member in a nested-structure can be accessed by chaining all the concerned structure variables (from outer-most to inner-most) with the member using the dot operator. The fallowing statements are invalid:
employee.allowance ------actual member is missing
employee.house_rent ------inner structure variable is missing
We can also use tag names to define inner structures. For example,
struct pay
{
int da;
int hra;
};
struct salary
{
char name[10];
struct pay allowance;
struct pay arrears;
};
struct salary employee [100];
Here, pay template is defined outside the salary template and is used to define the structure of allowance and arrears inside the salary structure. C permits nesting up to 15 levels
The pay structure members can be referred to as:
employee.allowance.da;
employee.allowance.hra;
employee.arrears.da;
employee.arrears.hra;
Example:#include <stdio.h>
struct Employee
{
char ename[20];
int ssn;
float salary;
struct date
{
int date;
int month;
int year;
}doj;
}emp = {"Pritesh",1000,1000.50,{22,6,1990}};
int main()
{
printf("\nEmployee Name : %s",emp.ename);
printf("\nEmployee SSN : %d",emp.ssn);
printf("\nEmployee Salary : %f",emp.salary);
printf("\nEmployee DOJ : %d/%d/%d",
emp.doj.date,emp.doj.month,emp.doj.year);
}
Output :Employee Name : Pritesh
Employee SSN : 1000
Employee Salary : 1000.500000
Employee DOJ : 22/6/1990
Example: implement following student information fields using nested structures
#include<stdio.h>
#include<conio.h>
void main()
{
struct student;
{
int roll_no;
struct name
{
char First[20];
char Middle[20];
char Last[20];
}st_name;
struct dob
{
int day ,month,year;
}std_dob;
struct course
{
char elective 1[20];
char elective2[20];
}st_course;
};
struct student std1;
clrscr();
std.roll_no=34;
strcpy(sdt1.st_name.First,”Krishna”);
strcpy(sdt1.st_name.Middle,”sai”);
strcpy(sdt1.st_name.Last,”reddy”);
std1.st_dob.day=21;
std1.st_dob.month=12;
std1.st_dob.year=1993;
strcpy(std1.st_course.elective1,”Mechanics”);
strcpy(std1.st_course.elective2,”Animation”);
Printf(“\nRoll No.:%d”,std1.Roll _No);
Printf(“\n Name: %s%s%s”,
std1.st_name.First,std1.st_name.Middle,std1.st_name.Last);
Printf(“\n Date of birth(DD MM YYYY):%d%d%d”,
std1.st_dob.day,std1.st_dob.Month,std1.st_dob.Year);
Printf(“\ncourse electives:%s&%s”,
std1.st_course.elective1,std1.st_course.elcetive2);
getch();
}
Example: Implement the following employee information fields using nested structures
#include<stdio.h>
#include<conio.h>
void main()
{
struct employee
{
int emp_id;
struct name
{
char First[20];
char Mibble[20];
char Last[20];
}emp_name;
char doj[20];
struct G_sal
{
float basic,HRA;
float spl_allow;
}emp_sal;
};
struct employee emp1l
clrscr();
emp1.emp_id=37;
strcpy(emp1.emp_name.first,”M”);
strcpy(emp1.emp_name.middle,”Mahesh”);
strcpy(emp1.emp_name.last,”reddy”);
strcpy(emp1.doj,”22/10/2004”);
emp1.emp_sal.basic=17432.00;
emp1.emp_sal.HRA=10032.00;
emp1.emp_sal.spl_allow=5000.00;
Printf(“\n emp id:%d”, emp1.emp_id);
Printf(“\n name:%s%s%s”,emp1.emp_name.First ,emp1.emp_name.Middle ,emp1.emp_name.Last);
Printf(“\n date of joining (DD MM YYYY): %s”,emp1.doj);
Printf(“\n Gross salary:%.2f”,
emp1.emp_sal.basic+emp1.emp_sal.HRA+emp1.emp_sal.spl_allow);
getch();
}
Arrays of Structures:As you know, C Structure is collection of different data types ( variables ) which are grouped together. Whereas, array of structures is nothing but collection of structures. Arrays of structures represent each element of an array must be structure type. For example, in analyzing the marks obtained by a class of students, we may use a template to describe student name and marks obtained in various subjects and then declare all the students as structure variables. In such cases, we may declare an array of structures, each element of the array representing a structure variable.
Syntax:struct structurename
{
datatype var1;
datatype var2;
.
.
datatype varN;
}structurevariable[size];
(or)
struct structurename structurevariable[size];
Example:struct class student [100];
The above defines an array called „student‟ that consists of 100 elements. Each element is defined
to be of the type struct class.
Consider the following declaration:
struct marks
{
int eng;
int tel;
int sci;
};
main( )
{
struct marks student[3]={45,76,87},{78,68,79},{34,23,14};
......
......
}
This declares the student as an array of three elements student [0], student [1],student [2] and initializes the members as follows:
student[0].eng=45;
student[0].tel=76;
......
......
student[2].sci=14;