DS-1.pdf

ADIKAVI NANNAYA UNIVERSITY:: RAJAHMAHENDRAVARAM BCA 2nd Semester Syllabus(w.e.f:2020-21 A.Y) UNIT- I: Concept of Abstract Data Types (ADTs)- Data Types, Data Structures, Primitive and Non- primitive Data Structures, Linear and Non-linear Structures. Linear Lists - ADT, Array...

ADIKAVI NANNAYA UNIVERSITY:: RAJAHMAHENDRAVARAM BCA 2nd Semester Syllabus(w.e.f:2020-21 A.Y) UNIT- I: Concept of Abstract Data Types (ADTs)- Data Types, Data Structures, Primitive and Non- primitive Data Structures, Linear and Non-linear Structures. Linear Lists - ADT, Array and Linked representations (Single and Double Linked lists), Pointers. UNIT- II: Stacks: Definition, Stacks using Array and Linked representations, expressions, notations. Queues: Definition, Queue using Array and Linked representations, Circular Queues, Dequeues. UNIT- III: Trees: Binary Tree, Definition, Properties, Trees using Array and Linked representations, Implementations and Applications, Heaps Trees. Binary Search Trees (BST) - Definition, Operations and Implementations. B Trees, B+ Trees Implementation UNIT IV: Graphs – Graph and its Representation, Graph Traversals, Connected Components, Basic Searching Techniques, Minimal Spanning Trees. UNIT- V: Sorting and Searching: Selection, Insertion, Bubble, Merge, Quick, Sequential and Binary Searching. BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 1  Data Structure Using C BCA UNIT -01 Q. What is a data structure? Write its advantages. Introduction to the Theory of Data Structures:  Data Structures in C are used to store data in an organized and efficient manner.  A programmer selects an appropriate data structure and uses it according to their convenience.  A data structure is a particular way of organizing data in a computer so that it can be used effectively.  A data structure in computer science is a system used to store data, keep it organized, and enable easy modification and access. Put simply, a data structure refers to a group of data values, how they relate to each other, and the operations or functions that can be carried out on them. Examples : Array, Linked List, Stack, Queue, Trees ,Graphs etc. Advantages of Data Structure Efficient Memory use: With efficient use of data structure memory usage can be optimized. Ex Arrays Vs linked List Reusability: Data structures can be reused, i.e. once we have implemented a particular data structure, we can use it at any other place Abstraction: Data structure serves as the basis of abstract data types, Ex ADT Q. EXPLAIN ABOUT “DATA TYPES” IN C. Data types in C: Data type determines the type of data a variable will hold. If a variable ‘x’ is declared as ‘int’. it means x can hold only integer values. Every variable which is used in the program must be declared as what data-type it is. The c language supports fallowing data types: BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 2 1. PRIMITIVE DATA TYPES (OR) SYSTEM DEFINED DATA TYPES: These data types can be defined by C compiler, these are two types: Numeric data types: These are two types: integers and floating. Character data types: These are two types’ single characters and string characters. INTEGER DATA TYPE:  Integer data type allows a variable to “store numeric values”.  “int” keyword is used to refer integer data type.  The storage size of int data type is 2 or 4 or 8 Byte.  It is represented with “%d” sign. int 2 or 4 bytes -32,768 to 32,767 or -2,147,483,648 to 2,147,483,647 unsigned int 2 or 4 bytes 0 to 65,535 or 0 to 4,294,967,295 short 2 bytes -32,768 to 32,767 unsigned short 2 bytes 0 to 65,535 long 4 bytes -2,147,483,648 to 2,147,483,647 unsigned long 4 bytes 0 to 4,294,967,295 FLOATING POINT DATA TYPE: Floating point data type consists of 2 types. They are: 1. Float 2. Double Float:  Float data type allows a variable to store decimal values.  Storage size of float data type is 4 Bytes. This also varies depend upon the processor in the CPU.  We can use up-to 6 digits after decimal using float data type.  For example, 10.456789 can be stored in a variable using float data type.  It is represented with “%f”. Double:  Double data type is also same as float data type which allows up-to 10 digits after decimal.  It is also represented with “%f” Type Storage size Value range Precision float 4 byte 3.4E-38 to 3.4E+38 6 decimal places double 8 byte 1.7E-308 to 1.7E+308 15 decimal places long double 10 byte 3.4E-4932 to 1.1E+4932 19 decimal places CHARACTER DATA TYPE:  Character data type allows a variable to store only one character.  Storage size of character data type is 1 Byte. We can store only one character using character data type.  “char” keyword is used to refer character data type. BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 3   For example, ‘A’ can be stored using char data type. You can’t store more than one character using char data type.  It is represented with “%c” Type Storage size Value range char 1 byte -128 to 127 or 0 to 255 unsigned char 1 byte 0 to 255 signed char 1 byte -128 to 127 VOID DATA TYPE  Void is an empty data type that has no value.  This can be used in functions and pointers. 2. DERIVED DATA TYPES These data types can be declared by user by deriving the system defined data type concepts. These are two types. Arrays: It is a Set of similar data elements are called as arrays.  Ex: int a,  char name; Pointers: Pointer is a variable which holds the address of similar data variable.  Ex: int *p;  Here p is a pointer variable declared with * character. Function: Function is a block of code used to perform a specific task in a program. Every function has a name and ends with braces, in the braces we are passing arguments.  Ex: function name ( arguments list ); Structures: It is a group of deferent data items combined together are called as structures. All the data items can stored in individual memory locations. Q. Explain in detail on Abstract data type (ADT). When an application requires a special kind of data type which is not available as a built-in data type, then it is the programmer’s responsibility to implement his own data type. The programmer has to specify the following things while designing his own data type:  How to store that data?  Operations that can be performed on that data.  Amount of memory required to store that data. The data type that is designed by the programmer for a specific purpose is called as an Abstract Data Type (ADT). It is alternatively called as user defined data type. BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 4 It is a concept of hiding certain background details like storing and maintaining data. It provides users with an abstract view of the data. This leads to design complex data structures for the representation of data in database. Ex: structures and classes Structure: A structure is a user defined data type. It is similar to records. It is a collection of data elements of different type with a single name. It helps us to organize complex data in a meaningful way. Class: Class is a user defined data type. It consists of the entire set of data and methods that are used to manipulate the data. A class is a collection of similar type of objects. Once a class is created we create any number of objects belonging to that class. Ex: Fruit is a class and mango, apple and orange are the objects of class fruit. Q. Explain the classification of data structures. DATA STRUCUTES Linear Data Non-Linear Data Structures Structures Arrays Trees Stacks Graphs Queues Tables Linked Lists Sets Classification of Data Structures: Data structures are classified into 2 types. They are 1. Primitive Data Structures: The primitive data types are the basic data types that are available in most of the programming languages. The primitive data types are used to represent single values. Ex: char, int, float and double 2. Non-Primitive Data Structures: The data types that are derived from primary data types are known as non-Primitive data types. These data types are used to store group of values. Ex: Arrays, structures, unions and classes Linear Data structures: Linear data structures can be constructed as a continuous arrangement of data elements in the memory. In the linear data structures, a relationship will be maintained between adjacent elements. Ex: arrays, stacks, queues and linked lists BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 5 a. Stack: A stack is a collection of data elements in which elements may be inserted and deleted at only one end that is the top end. Since the last element inserted into a stack in the first element to be removed stack is called as Last In First Out (LIFO). b. Queue: A queue is a collection of data elements in which elements may be inserted at one end called as rear end and deleted at another end called as front. Since the first element inserted into a stack in the first element to be removed stack is called as First In First Out (FIFO). c. Linked Lists: Linked list is a collection of elements known as nodes that are stored in different locations and are linked each other using pointers. Non-Linear Data structures: Non-Linear data structures can be constructed as a collection of randomly distributed set of elements in the memory. In the non-linear data structures, there will be no relationship between adjacent elements. Ex: trees, graphs, tables and sets a. Trees: Trees are non-linear data structures that can be represented in a hierarchical manner. A tree is a finite set of one or more nodes such that there is specially designed node called root and the remaining BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 6 nodes are partitioned into disjoint sets T1, T2, …. Tn Where each of these sets is a tree. T1, T2, …., Tn are called the sub trees of the root. b. Graphs: A graph is a collection of nodes called vertices and the connections between them called edges. Q. Explain in detail on structured data type. Structure: Structure is a user-defined data type in C which allows you to combine different data types to store a particular type of record. (Or) Structure is a non linear collection of heterogeneous elements with a common name. (Or) Structure defines different data types to store different values with a common name. Syntax: struct Example { struct student-info data type member1; { data type member12; Int sno; data type member3; char s-name; char group;;. data type member n; float percentage; char address; }; }; BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 7 Program: #include #include struct employee { int id; char name; }e1; //declaring e1 variable for structure void main( ) { //store first employee information e1.id=101; strcpy(e1.name, "Amrutha Varshini");//copying string into char array //printing first employee information printf( "employee 1 id : %d\n", e1.id); printf( "employee 1 name : %s\n", e1.name); } Output: employee 1 id : 101 employee 1 name : Amrutha Varshini Q. What is array? Explain the types of array. Array: Array is a group of elements of same type with a common name. (OR) An array is defined as finite ordered collection of homogenous data, stored in contiguous memory locations. Types of arrays: 1. One Dimensional arrays 2. Two dimensional arrays 1. One dimensional arrays: An array with just one dimension or subscriptions called one-dimensional array. Dimension of an array is specified by a pair of square brackets called subscript immediately after the name of array.  Declaration of one dimensional Array: Like any other variable, arrays must be declared before they are used. Syntax: type array Name [array Size]; Example: int arr; BCA 2nd Sem/DS using ‘C’/Mr. G.Chiranjeevi,Lect in CS/AWDC,KKD 8  Initialization of one dimensional an Array: After an array is declared it must be initialized. Otherwise, it will contain garbage value (any random value). An array can be initialized at either compile time or at runtime. Compile time Array initialization: Compile time initialization of array elements is same as ordinary variable initialization and it done at the time of writing a program. The general form of initialization of array is: Syntax: array-name [size] = { list of values }; Runtime Array initialization: An array can also be initialized at runtime using scanf() function. This approach is usually used for initializing large array, or to initialize array with user specified values. Syntax: scanf(“control string”,&arrayname[ ]); Example: int arr; for(i=0;i