BCA_Sem-3_Data Structure_Unit-4

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

2 Unit 4: Structures Internal representation of structures self–referential structures. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Data Definition 3 Data Definition defines a particular data with the following characteristics. Atomic − Definition should define a single concept. Traceable − Definition should be able to be mapped to some data element. Accurate − Definition should be unambiguous. Clear and Concise − Definition should be understandable. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Data Type 4 Data type is a way to classify various types of data such as integer, string, etc. which determines the values that can be used with the corresponding type of data, the type of operations that can be performed on the corresponding type of data. There are two data types − •Built-in Data Type •Derived Data Type www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Built-in Data Type 5 Those data types for which a language has built-in support are known as Built-in Data types. For example, most of the languages provide the following built-in data types. Integers Boolean (true, false) Floating (Decimal numbers) Character and Strings www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Derived Data Type 6 Those data types which are implementation independent as they can be implemented in one or the other way are known as derived data types. These data types are normally built by the combination of primary or built-in data types and associated operations on them. For example − List Array Stack Queue www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Structure 7 A structure is a composite data type that defines a grouped list of variables that are to be placed under one name in a block of memory. It allows different variables to be accessed by using a single pointer to the structure. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Advantages 8 •It can hold variables of different data types. •We can create objects containing different types of attributes. •It allows us to re-use the data layout across programs. •It is used to implement other data structures like linked lists, stacks, queues, trees, graphs etc www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

#include<stdio.h> 9 #include<conio.h> void main( ) { struct employee { int id ; float salary ; int mobile ; }; struct employee e1,e2,e3 ; clrscr(); printf (\"\\nEnter ids, salary & mobile no. of 3 employee\\n\" scanf (\"%d %f %d\", &e1.id, &e1.salary, &e1.mobile); scanf (\"%d%f %d\", &e2.id, &e2.salary, &e2.mobile); scanf (\"%d %f %d\", &e3.id, &e3.salary, &e3.mobile); printf (\"\\n Entered Result \"); printf (\"\\n%d %f %d\", e1.id, e1.salary, e1.mobile); printf (\"\\n%d%f %d\", e2.id, e2.salary, e2.mobile); printf (\"\\n%d %f %d\", e3.id, e3.salary, e3.mobile); getch(); } www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Linked List Data Structure 10 A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Stack Data Structure 11 Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Queue Data Structure 12 A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Binary Tree Data 13 Structure A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

14 Graph A graph is a data structure that consists of the following two components: 1. A finite set of vertices also called as nodes. 2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Self Referential Structures 15 Self Referential structures are those structures that have one or more pointers which point to the same type of structure, as their member. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

In other words, structures pointing to the same type of structures are self-referential in nature. 16 Example: Unit-1(MAP-607) All right are reserved with CU-IDOL struct node { int data1; char data2; struct node* link; }; int main() { struct node ob; return 0; } www.cuidol.in

17 In the above example ‘link’ is a pointer to a structure of type ‘node’. Hence, the structure ‘node’ is a self-referential structure with ‘link’ as the referencing pointer. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Types of Self Referential 18 Structures 1.Self Referential Structure with Single Link 2.Self Referential Structure with Multiple Links www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Self Referential Structure 19 with Single Link These structures can have only one self-pointer as their member. The following example will show us how to connect the objects of a self-referential structure with the single link and access the corresponding data members. The connection formed is shown in the following figure. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

EXAMPLE 20 #include <stdio.h> // Initialization ob2.link = NULL; struct node { ob2.data1 = 30; int data1; ob2.data2 = 40; char data2; struct node* link; // Linking ob1 and ob2 ob1.link = &ob2; }; // Accessing data members of ob2 using ob1 int main() printf(\"%d\", ob1.link->data1); { printf(\"\\n%d\", ob1.link->data2); return 0; struct node ob1; // Node1 } // Initialization Unit-1(MAP-607) All right are reserved with CU-IDOL ob1.link = NULL; ob1.data1 = 10; ob1.data2 = 20; struct node ob2; // Node2 www.cuidol.in

Self Referential Structure with 21 Multiple Links Self referential structures with multiple links can have more than one self-pointers. Many complicated data structures can be easily constructed using these structures. Such structures can easily connect to more than one nodes at a time www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

#include <stdio.h> // Accessing data of ob1, ob2 and ob3 by 22 ob1 struct node { struct node ob3; // Node3 int data; printf(\"%d\\t\", ob1.data); struct node* prev_link; // Initialization printf(\"%d\\t\", ob1.next_link->data); struct node* next_link; ob3.prev_link = NULL; printf(\"%d\\n\", ob3.next_link = NULL; ob1.next_link->next_link->data); }; ob3.data = 30; int main() // Accessing data of ob1, ob2 and ob3 by { // Forward links ob2 ob1.next_link = &ob2; struct node ob1; // Node1 ob2.next_link = &ob3; printf(\"%d\\t\", ob2.prev_link->data); // Initialization printf(\"%d\\t\", ob2.data); ob1.prev_link = NULL; // Backward links printf(\"%d\\n\", ob2.next_link->data); ob1.next_link = NULL; ob2.prev_link = &ob1; ob1.data = 10; ob3.prev_link = &ob2; // Accessing data of ob1, ob2 and ob3 by struct node ob2; // Node2 ob3 Unit-1(MAP-607) // Initialization printf(\"%d\\t\", ob2.prev_link = NULL; ob3.prev_link->prev_link->data); ob2.next_link = NULL; ob2.data = 20; printf(\"%d\\t\", ob3.prev_link->data); printf(\"%d\", ob3.data); www.cuidol.in return 0; } All right are reserved with CU-IDOL

23 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Textbooks / Reference Books 24 TEXT BOOKS •T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. •T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Reference Books: •R1 Trembley &Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. •R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

25 THANK YOU www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL