Chapter 12 ndash; Data Structures.ppt

Chapter 12 – Data Structures Objectives In this chapter, you will learn: To be able to allocate and free memory dynamically for data objects. To be able to form linked data structures using pointers, self-referential structures and recursion. To be able to create and manipulate linked lists, queues, stacks and binary trees. To understand various important applications of linked data structures. 12.1 Introduction Dynamic data structures Data structures that grow and shrink during execution Linked lists Allow insertions and removals anywhere Stacks Allow insertions and removals only at top of stack Queues Allow insertions at the back and removals from the front Binary trees High-speed searching and sorting of data and efficient elimination of duplicate data items 12.2 Self-Referential Structures Self-referential structures Structure that contains a pointer to a structure of the same type Can be linked together to form useful data structures such as lists, queues, stacks and trees Terminated with a NULL pointer (0) struct node {  int data; struct node *nextPtr;} nextPtr Points to an object of type node Referred to as a link Ties one node to another node 12.3 Dynamic Memory Allocation 12.3 Dynamic Memory Allocation Dynamic memory allocation Obtain and release memory during execution malloc Takes number of bytes to allocate Use sizeof to determine the size of an object Returns pointer of type void * A void * pointer may be assigned to any pointer If no memory available, returns NULL Example newPtr = malloc( sizeof( struct node ) ); free Deallocates memory allocated by malloc Takes a pointer as an argument free ( newPtr ); 12.4 Linked Lists Linked list Linear collection of self-referential class objects, called nodes Connected by pointer links Accessed via a pointer to the first node of the list Subsequent nodes are accessed via the link-pointer member of the current node Link pointer in the last node is set to NULL to mark the list’s end Use a link