Unit 1-Introduction to Data Structures-BCA.pdf

Introduction to Data Structures Unit 1 Dr. Mary Jacob Assistant Professor Kristu Jayanti College(Autonomous) Bangalore

Definition: ØA data structure is a particular way of storing and organizing data in a computer. In other words the organised collection of data is known as data structure. Ø Data structure = organised data + operations ØCommon data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables. Classification of data structures: 1. Primitive data structure 2. Non primitive data structure Data Structure

Primitive Data Structure It is a basic data structure and it is directly operated upon the machine instructions. These structures have different representation on different computers. If the data contains a single value then it can be organized using primitive data type. Primitive data structure in C includes, int , char, float. INTEGERS: The quantity representing objects that are discrete in nature can be represented by an integer. For example: 2, 4, 6, 0, -23,-56 etc. are integers FLOAT: Float is a simple data type which takes 4 bytes in memory and we can assign decimal fraction numbers into it. For example: 2.5, 245.67 etc. Data Structure - Classification

Primitive Data Structure(Contd..) CHARACTERS : Characters are the literal representation of some elements selected from alphabets and characters and are defined in the single quotes. For example: '*', 'r', 'A', '2' etc. are character constants. POINTERS : Pointers is a reference to the data structure and a simple type of variable which store the address of the another variable. Pointer is a single fixed size data item. For example: int x; int *p; p=&x; Here x is the integer, where p is a pointer of integer type and pointer p points to integer x. Data Structure - Classification

Non-Primitive Data Structure These are more sophisticated data structure and are derived from the primitive data structures. Non-Primitive data structures can be classified into two types 1. Linear data structures 2. Non-linear data structures Data Structure - Classification

Non-Primitive Data Structure 1. LINEAR DATA STRUCTURES In linear data structure the elements are stored in the memory in a sequential order and there exists an adjacency relationship between the elements. The linear data structures are: Array: Array is a collection of data items of same data type, stored in consecutive memory location and is referred by common name. It means an array can contain one type of data, either all integers or characters. Declaration of an array: int a[n]; Data Structure - Classification

Non-Primitive Data Structure 1. LINEAR DATA STRUCTURES Linked list Ø A list is a linear sequence of data objects of the same type. The list may be single, double or circular linked list. Ø The linked list is a linear collection of data items called as nodes; node is divided into two parts (1) information field (2) Link field. Data Structure - Classification

Non-Primitive Data Structure 1. LINEAR DATA STRUCTURES Stack: Ø A stack is a Last-In-First-Out linear data structure in which insertion and deletion takes place at only one end called the top of the stack. Data Structure - Classification

Non-Primitive Data Structure 1. LINEAR DATA STRUCTURES Queue: Ø A Queue is a First in First-Out Linear data structure in which insertions takes place one end called the rear and the deletions takes place at one end called the Front. Data Structure - Classification

Non-Primitive Data Structure 2. NON-LINEAR DATA STRUCTURE Data structures in which the data items are not arranged in order are called non linear data structures. They establish relationship other than the adjacency relationship. Trees: Ø Trees are used to represent data that has some hierarchical relationship among the data elements. Ø Tree contains the data in the nodes which are linked to one another using pointers. Ø The primary node is called the root node from which all the branches called the sub-trees descend. Data Structure - Classification Root node Right Subtree Left Subtree

Non-Primitive Data Structure 2. NON-LINEAR DATA STRUCTURE Graph Ø Graph is used to represent data that has relationship between pair of elements not necessarily hierarchical in nature. Ø It is a non linear data structure consisting a set of elements called nodes or vertices and a set of edges. Ø It is used in electrical and communication networks, airline routes, flow chart, graphs for planning projects. Data Structure - Classification

Data structures may also be classified as i)Homogeneous ii)Non-homogeneous Homogeneous Data structure In a homogeneous data structure, all elements are of the same type. Example: Arrays. Non-Homogeneous Data structure In a Non-Homogeneous Data structure, the elements may or may not be of the same type. Data values of different types are grouped together. Example: records, structures, classes. Data Structure - Classification

Data structures may also be classified as i)Static ii)Dynamic Static data structure: In a static data structure, size and structure associated with memory location are fixed at compile time. The value of static variables remains in the memory throughout the program. Dynamic data structure: A dynamic data structure can shrink or expand during program execution as required by the program. Here in data structures such as references and pointers, the size of memory locations can be changed during program execution. Data Structure - Classification

The data that is stored or organized in the data structures are processed by certain operations that are performed. 1.Common operations Some of the common operations performed on primitive data structures so as to design the data structure are i) CREATE ii) DESTROY iii) SELECT iv) UPDATE 2. Basic operations Some basic operations performed on non-primitive data structures are i)Traversal ii)Searching iii)Insertion iv)Deletion 3. Special operations The special operations on data structures are i) Sorting ii) Merging Data Structure Operations

Data Structure -Applications Applications of data structures Ø It provides the method of representing the data elements in the memory of computer efficiently. Ø It enables to solve relationships between the data elements that are relevant to the solution of the problem. Ø It helps to describe various operations that can be performed on data such as creating, displaying, inserting and deleting. Ø It describes the physical and logical relationship between the data items. Ø It provides a method of accessing each element in the data structure. Ø It provides freedom to the programmer to choose any programming language best suited to the problem.

MEMORY ALLOCATION There is memory allocation techniques for programs depending on the programming language used. They are: i)Static memory allocation (eg. Array) ii)Dynamic memory allocation (eg. Linked list)

MEMORY ALLOCATION Static Memory Allocation: v Static memory allocation means we reserve a certain amount of memory by default, inside our program to use for variables. v It is fixed in size. It need not grow or shrink in size. v The standard method of creating an array of 10 integers on the stack is: v int arr[10]; v This means 10 memory locations are allocated to hold 10 integers. Memory is said to be allocated statically. v In real world problems, we do not exactly know how much static data space to declare. If we declare more static data space, we waste space. If we declare less static data space, we run out of space.

MEMORY ALLOCATION Dynamic Memory Allocation: v Memory can be allocated at run-time for the variables - called Dynamic Memory Allocation. v Dynamic data refers to data structures which can grow and shrink to fit changing data requirements. v We can allocate additional storage whenever required and de-allocate whenever it is done. v The advantage is that we can reserve as much memory we require not more not less. It offers great flexibility. v Dynamic memory allocation is performed by the operating system when the program is executed and memory is requested by the program (user).Three issues need to be addressed by the operating system for dynamic memory allocation. They are: 1)Allocating variable-length dynamic storage when needed. 2)Freeing up storage when requested 3)Managing the storage(e.g. reclaiming freed up memory for later use)

MEMORY ALLOCATION Heap v The region of memory consisting of contiguous elements that is dedicated to dynamic memory allocation is called dynamic memory or the heap. v Dynamic data structures allocate blocks of memory from the heap as required, and link those blocks together into some kind of data structure using pointers. When the data structure no longer needs a block of memory, it will return the block to the heap for reuse. v Heap contains 3 kinds of nodes at all times, 1. Nodes that are in use because they appear in dynamic data structure 2. Nodes that are not in use and appear in no dynamic data structures and are on the current list of available memory space. 3. Nodes that are not in use and appear in no dynamic data structures and are not on the current list of available memory space.

MEMORY ALLOCATION Garbage Collection: vThe management (reclaiming and recycling) of garbage nodes is called garbage collection. vThe basic components of garbage collection are: i)Initialisation phase: Initialise all memory blocks to be free (set mark bit to be “0”). ii)Marking phase: Set mark bit to be “1” for all nodes currently in use. Here, the garbage collector must know the names of all data structures in use. iii)Gathering phase: Search through memory and collect all nodes that are marked free (mark bit equal to “0”) into a linked list of available nodes. Advantages of Dynamic Memory Allocation 1)It can be used when we do not know how much memory is needed in advance. 2)It can save space in memory until we actually need to use it.

MEMORY MANAGEMENT FUNCTIONS i)malloc( ) v malloc is used to allocate a block of memory on the heap. v The program accesses this block of memory via a pointer that malloc returns. v void *malloc(size_t size); v This allocates size bytes of memory. If the allocation succeeds, a pointer to the block of memory is returned, otherwise a NULL pointer is returned. malloc ( ) returns a NULL pointer to indicate that no memory is available, or that some other error occurred which prevented memory being allocated. v By default the values stored in the memory space allocated by malloc () is garbage values.

MEMORY MANAGEMENT FUNCTIONS ii) calloc( ) v An alternative approach to allocate memory is to use the calloc ( ) function, which allocates memory and then initializes it. v void *calloc(size_t nelements, size_t elementSize); which allocates a region of memory, initialized to 0, of size (nelements * elementSize) Example: char *word = calloc(200, sizeof(char));

malloc,calloc-Differences malloc() calloc() One argument Two arguments Memory created contains garbage values Memory created is initialized with zeros or blank spaces

MEMORY MANAGEMENT FUNCTIONS iii) realloc( ) Ø It is often useful to be able to grow or shrink a block of memory. Ø This can be done using realloc which returns a pointer to a memory region of the specified size, which contains the same data as the old region pointed to by pointer . Ø If realloc is unable to resize the memory region in place, it allocates new storage, copies the required data, and frees the old pointer. Ø If this allocation fails, realloc maintains the original pointer unaltered, and returns the null pointer value. Ø The newly allocated region of memory is uninitialized (its contents are not predictable). Ø void * realloc(void *pointer, size_t size);

MEMORY MANAGEMENT FUNCTIONS iv) free( ) Ø Memory allocated via malloc is persistent: it will continue to exist until the program terminates or the memory is explicitly deallocated by the programmer (that is, the block is said to be "freed"). This is achieved by use of the free function. Its prototype is void free(void *pointer); Ø which releases the block of memory pointed to by pointer. Ø pointer must have been previously returned by malloc, calloc, or realloc and then only be passed to free once. Ø It is safe to call free on a NULL pointer, which has no effect.

RECURSION Ø A function is said to be recursive if the function calls itself repeatedly either directly or indirectly. A recursive function is said to be well defined if it possesses the following properties, 1. There must be certain arguments called the base values for which the function does not refer to itself. 2. Each time the function does refer to itself the argument of the function must be closer to a base value. Ø A recursive function must have 2 parts: 1) Basis 2) Recursive Formula Ø The Basis of a recursive function is its starting point in its definition. Ø The recursive part of a recursive function is the assignment that includes the function on the right side of the assignment operator, causing the function to call itself.

RECURSION Example: In factorial function The base case is n! = 1 if n = 0 and the recursive formula is n*f(n-1) if n>0 ↓ function call

RECURSION Ø When a recursive function is executed the recursion calls are not implemented instantly. Ø All the recursive calls are pushed onto the tack until the terminating condition is detected. Ø When the termination condition is detected the recursive calls stored in the stack are popped and executed. The last call is executed first then second last and so on. Ø Recursion can be implemented using stacks. Ø At each call the new memory is allocated to all the local variables, their previous values are pushed onto the stack and with its call all these values can be available to corresponding function call when it is popped from the stack.

Types of Recursions i)Direct ii) Indirect Ø Direct method Ø In the direct recursion type, function calls itself repeatedly until certain condition is satisfied. In this type, only one function is involved. int fact( ) { …. fact() }

Types of Recursions Indirect method In indirect method two functions call each other. int fact( ) { ------ fact1( ); } int fact1( ) { ------ fact( ); }

Factorial-Recursion Recursive definition of factorial: fact (n) = 1, if (n=0) n*fact (n-1) if (n>0) The recursive solution is n!=n*(n-1)! Example: factorial(4) = 4 * factorial(3) = 4 * (3 * factorial(2)) = 4 * (3 * (2 * factorial(1))) = 4 * (3 * (2 * (1 ) = 4 * (3 * (2 * (1 )) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

Fibonacci-Recursion Example: fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) fib(3) = fib(2) + fib(1) fib(2) = fib(1) + fib(0) fib(1)=1,fib(0)=0 fib(2) = 1 + 0 =1 fib(3) = 1+1=2 fib(4)=2+1=3 fib(5) = 3+2=5 Recursive Formula 0 if (n=0) fib(n) = 1 if (n=1) fib(n-1) + fib (n-2) if (n>1)

Fibonacci-Recursion Example: gcd(288,108)=gcd(108,288 %108)=gcd(108,72) gcd(108,72) = gcd(72,108 % 72)=gcd(72,36) gcd(36,72 % 36) = gcd(36,0) gcd(36,0)=36 gcd(72,36)=36 gcd(108,72)=36 gcd(288,108)=36 Recursive Formula x if(y==0) GCD (x,y) = GCD(y,x) if (y>x) GCD (y, x % y) otherwise

Unit 1-Introduction to Data Structures-BCA.pdf

More Related Content

What's hot

Similar to Unit 1-Introduction to Data Structures-BCA.pdf

More from MaryJacob24

Recently uploaded

In this document

Unit 1-Introduction to Data Structures-BCA.pdf