Data Structures using C Language PDF

Page Number: 1 Prepared by: P.V.MAHESH KUMAR Data Structures using C language By P.V.MAHESH KUMAR  Page Number: 2 Prepared by: P.V.MAHESH KUMAR What is Data structure? Data structure is a representation of the logical relatio...

Page Number: 1 Prepared by: P.V.MAHESH KUMAR Data Structures using C language By P.V.MAHESH KUMAR  Page Number: 2 Prepared by: P.V.MAHESH KUMAR What is Data structure? Data structure is a representation of the logical relationship existing between individual elements of data. Data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other. We can also define data structure as a mathematical or logical model of a particular organization of data items. The representation of particular data structure in the main memory of a computer is called as storage structure. The storage structure representation in auxiliary memory is called as file structure. Data structure mainly specifies the following four things: Organizing the data Accessing methods Degree of associativity Processing alternatives for information Classification of Data structure Data structures Primitive Data structures Non-Primitive Data structures Int float char double… Linear Data structure Non-linear DS Arrays Trees Stacks Graphs Queues Hash Tables Linked list Primitive Data structures Primitive data structures are basic structures and are directly operated upon by machine instructions. Primitive data structures have different representations on different computers. Int, float, char, double, long. etc. are examples of primitive data structures, these are available in most programming languages as built-in type. Non-primitive Data structures These are more sophisticated data structures. These are derived from primitive data structures. The non-primitive data structures emphasize on structuring of a group of homogeneous data items. Eg: Array, Stacks, Queues, Linked lists Linear Data structure A data structure is said to be linear, If its elements are connected in linear fashion by means of logically or in sequence memory locations.  Page Number: 3 Prepared by: P.V.MAHESH KUMAR There are two ways to represent a linear data structure in memory, Static memory allocation Dynamic memory allocation The possible operations on the linear data structure are: Traversal, Insertion, Deletion, Searching, Sorting and Merging. Eg: Stacks, Queues Stack is a data structure in which insertion and deletion operations are performed at one end only. The insertion operation is referred as PUSH and deletion operation is referred as POP Stack is also called as LAST-IN-FIRST-OUT data structure. Queue is a data structure which permits the insertion at one end and deletion at another end. End at which deletion is occurs is known as FRONT end and another end at which insertion occurs is as REAR. Queue is also called as FIRST-IN-FIRST-OUT data structure. Non-Linear Data structure Nonlinear data structures are those data structure in which data items are not arranged in a sequence. Eg: Trees, Graph, Hash tables A tree can be defined as finite set of data items (nodes) in which data items are arranged in branches and sub branches according to requirement. Trees represent the hierarchical relationship between various elements. Tree consists of nodes connected by edge, the node represented by circle and edge lives connecting to circle. Graph is a collection of nodes (information) and connecting edges (logical relation) between nodes. A tree can be viewed as restricted graph. Graphs have many types: Un-directed graph Directed graph Mixed graph Multi graph Simple graph Null graph Weighted graph. Difference between Linear data structure and nonlinear data structure Linear Data Structures: Every item is related to its previous and next time. Data is arranged as linear sequence. Data items can be traversed in a single run. Eg: Array, Stack, Queue, Linked list Implementation is very easy. Non-linear data structure: Every item is attached with many other items. Data is not arranged in sequence. Data cannot be traversed in a single run.  Page Number: 4 Prepared by: P.V.MAHESH KUMAR Eg: tree, graph Implementation is difficult. Operation on Data Structures: Create The create operation results in reserving memory for program elements. This can be done by declaration statement. Creation of data structure may take place either during compile-time or run-time. Malloc () function of C language is used for creation. Destroy Destroy operation destroys memory space allocated for specified data structure. Free () function of C language is used to destroy data structure. Selection Selection operation deals with accessing particular data within a data structure Updation It updates or modifies the data in the data structure Searching It finds the presence of desired data item in the list of data items; it may also find the location Of all elements that satisfy certain conditions. Sorting Sorting is a process of arranging all data items in a data structure in a particular order. Merging Merging is a process of combining the data items of two different sorted list into a single list. Splitting Splitting is a process of partitioning single list to multiple list Traversal Traversal is a process of visiting each and every node of a list in systematic manner. ARRAYS An array is a group of related data items that share a common name. Ex: salary. Array name salary to represent a set of salaries of group employees. A particular value is indicated by writing a number called index number or subscript in brackets after the array name.While the complete set of values is referred to as an array, the individual values are called elements. Arrays can be of any variable type. One-dimensional arrays: A list of items can be given one variable name using only one subscript and such a variable is called a single subscripted variable or a one-dimensional array. If we want to represent a set of three numbers, say (34,56,45) by an array variable number, then we may declare the variable number as follows Ex:- int number={34,56,45}; number(0) number (1) number(2)  Page Number: 5 Prepared by: P.V.MAHESH KUMAR 34 56 45 Declaration of arrays: char name; declares the name as a character array (string) variable that can hold a maximum of 10 characters. name (0) name (1) name (2) S R I ‘\0’ When the compiler sees a character string, it terminates it with an additional null character. Thus name holds the holds the null character ‘\0’ at the end. When declaring character arrays, we must allow one extra element space for the null terminator. Program 84: Program 85: main() main() { { int a={1,2,3} int a={1,2,3},i clrscr(); clrscr(); printf(“%d”,a); for(i=0;i=k 4. Set a[j+1]= a[j] 5. Set j=j-1 6. Set a[k]=item 7. Stop #include Main() { Int a[]={1,3,5,7,8}; Int item=10,k=3,n=5; Int i=0,j=n; Printf(“\n Original array elements :\n”); For(i=0;i=k) {  Page Number: 7 Prepared by: P.V.MAHESH KUMAR A[j+1]=a[j]; J=j-1; } A[k]=item; Printf(“\n Array Elements after insertion:\n”); For(i=0;i %d", data); break; case 3: if (isempty()) printf("Queue is empty."); else printf("Queue size => %d", size); break; case 4: data = getrear(rear); if (data == INT_MIN) printf("Queue is empty."); else printf("Rear => %d", data); break; case 5: data = getfront(front); if (data == INT_MIN) printf("Queue is empty."); else printf("Front => %d", data); break; case 6: printf("Exiting from app.\n"); exit(0); default: printf("Invalid choice, please input number between (0-5)."); break; } printf("\n\n");  Page Number: 77 Prepared by: P.V.MAHESH KUMAR } } int enqueue(struct node ** rear, struct node ** front, int data) { struct node * newnode = NULL; // Check queue out of capacity error if (isfull()) { return 0; } // Create a new node of queue type newnode = (struct node *) malloc (sizeof(struct node)); // Assign data to new node newnode->data = data; // Initially new node does not point anything newnode->next = NULL; // Link new node with existing last node if ((*rear)) { (*rear)->next = newnode; } // Make sure newly created node is at rear *rear = newnode; // Link first node to front if its NULL if (!(*front)) { *front = *rear; } // Increment quque size size++; return 1; } int dequeue(struct node ** front) { struct node *todequque = NULL; int data = INT_MIN; // Queue empty error if (isempty()) { return INT_MIN; } // Get element and data to dequeue todequque = *front;  Page Number: 78 Prepared by: P.V.MAHESH KUMAR data = todequque->data; // Move front ahead *front = (*front)->next; // Decrement size size--; // Clear dequeued element from memory free(todequque); return data; } int getrear(struct node * rear) { // Return INT_MIN if queue is empty otherwise rear. return (isempty()) ? INT_MIN : rear->data; } int getfront(struct node * front) { // Return INT_MIN if queue is empty otherwise front. return (isempty()) ? INT_MIN : front->data; } int isempty() { return (size CAPACITY); } Doubly Linked List A Doubly linked list (DLL) contains an extra pointer, typically called PREVIOUS pointer together with NEXT pointer and data which are there in singly linked list Struct node { Int data; Struct node *next; //pointer to NEXT node in DLL Struct node *prev; // pointer to PREVIOUS node in DLL };  Page Number: 79 Prepared by: P.V.MAHESH KUMAR Advantages: 1. A DLL can be traversed in both forward and backward direction. 2. The delete operation in DLL is more efficient if pointer to the node to be deleted is given. 3. We can quickly insert a new node before a given node In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer. Disadvantages: 1. Every node of DLL requires extra space for an previous pointer. It is possible to implement DLL with single pointer though. 2. All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. Insertion 1. At the front of the DLL 2. After a given node 3. At the end of the DLL 4. Before a given node. Add a node at the front: Add a node after a given node:  Page Number: 80 Prepared by: P.V.MAHESH KUMAR Add a node at the end: Add a node before a given node: 1. Check if the next_node is NULL or not. If it’s NULL return from the function because any new node cannot be added before a NULL 2. Allocate memory for the new node, let it be called new_node 3. Set new_node -> data = new_data 4. Set the previous pointer of this new_node as the previous node of the next_node, new_node -> prev = next_node->prev 5. Set the previous pointer of the next_node as the new_node, Next_node -> prev = new_node 6. Set the next pointer of this new_node as the next_node , New_node -> next_node= next_node 7. If the previous node of the new_node is not NULL , then set the next pointer of this previous node as new_node, new_node -> prev->next =new_node Steps to insert a new node in Doubly Linked List 1. Traverse to n-1 node in the list. N is the position to insert 2. Create a new node that is to be inserted and assign some data to its data field 3. Connect the next address field of newnode with the node pointed by next address field of temp node  Page Number: 81 Prepared by: P.V.MAHESH KUMAR 4. Connect the previous address field of newnode with the temp node 5. Check if temp->next is not NULL then, connect the previous address field of node pointed by temp.next to newnode 6. Connect the next address field of temp node to newnode i.e temp->next will now point to newnode 7. Final list  Page Number: 82 Prepared by: P.V.MAHESH KUMAR //C program to insert a node in Doubly linked list #include #include struct node { int data; struct node * prev; struct node * next; }*head, *last; void createList(int n); void displaylist(); void insertatbeginning(int data); void insertatend(int data); void insertatn(int data, int position); int main() { int n, data, choice=1; head = NULL; last = NULL; while(choice != 0) { printf("1. Create List\n 2.Insert node - at beginning\n 3.Insert node - at end \n 4. Insert node - at N \n 5. Display list\n 6. Exit\n"); printf("Enter your choice [1/2/3/4/5/6] : "); scanf("%d", &choice); switch(choice) { case 1: printf("Enter the total number of nodes in list: "); scanf("%d", &n); createList(n); break; case 2: printf("Enter data of first node : "); scanf("%d", &data); insertatbeginning(data); break; case 3: printf("Enter data of last node : "); scanf("%d", &data); insertatend(data); break; case 4: printf("Enter the position where you want to insert new node: "); scanf("%d", &n); printf("Enter data of %d node : ", n);  Page Number: 83 Prepared by: P.V.MAHESH KUMAR scanf("%d", &data); insertatn(data, n); break; case 5: displaylist(); break; case 6: break; default: printf("Error! Invalid choice. Please choose between 0-5"); } printf("\n\n\n\n\n"); } } void createList(int n) { int i, data; struct node *newnode; if(n >= 1) { head = (struct node *)malloc(sizeof(struct node)); printf("Enter data of 1 node: "); scanf("%d", &data); head->data = data; head->prev = NULL; head->next = NULL; last = head; for(i=2; idata = data; newnode->prev = last; // Link new node with the previous node newnode->next = NULL; last->next = newnode; // Link previous node with the new node last = newnode; // Make new node as last/previous node } printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n"); } } void displaylist() { struct node * temp;  Page Number: 84 Prepared by: P.V.MAHESH KUMAR int n = 1; if(head == NULL) { printf("List is empty.\n"); } else { temp = head; printf("DATA IN THE LIST:\n"); while(temp != NULL) { printf("DATA of %d node = %d\n", n, temp->data); n++; temp = temp->next; } } } void insertatbeginning(int data) { struct node * newnode; if(head == NULL) { printf("Error, List is Empty!\n"); } else { newnode = (struct node *)malloc(sizeof(struct node)); newnode->data = data; newnode->next = head; // Point to next node which is currently head newnode->prev = NULL; // Previous node of first node is NULL head->prev = newnode; head = newnode; printf("NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST\n"); } } void insertatend(int data) { struct node * newnode; if(last == NULL) {  Page Number: 85 Prepared by: P.V.MAHESH KUMAR printf("Error, List is empty!\n"); } else { newnode = (struct node *)malloc(sizeof(struct node)); newnode->data = data; newnode->next = NULL; newnode->prev = last; last->next = newnode; last = newnode; printf("NODE INSERTED SUCCESSFULLY AT THE END OF LIST\n"); } } void insertatn(int data, int position) { int i; struct node * newnode, *temp; if(head == NULL) { printf("Error, List is empty!\n"); } else { temp = head; i=1; while(inext; i++; } if(position == 1) { insertatbeginning(data); } else if(temp == last) { insertatend(data); } else if(temp!=NULL) { newnode = (struct node *)malloc(sizeof(struct node));  Page Number: 86 Prepared by: P.V.MAHESH KUMAR newnode->data = data; newnode->next = temp->next; // Connect new node with n+1th node newnode->prev = temp; // Connect new node with n-1th node if(temp->next != NULL) { temp->next->prev = newnode; } temp->next = newnode; printf("NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position); } else { printf("Error, Invalid position\n"); } } } CIRCULAR LINKED LIST Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list Advantages: 1. Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again. 2. Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last. 3. Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making  Page Number: 87 Prepared by: P.V.MAHESH KUMAR them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list. 4. Circular doubly linked lists are used for implementation of advanced data structures like Fibonacci heap. Insertion in an empty List Initially when the list is empty, last pointer will be NULL. After inserting a node T After insertion, T is the last node so pointer last points to node T. And Node T is first and last node, so T is pointing to itself. Function to insert node in an empty List struct node *addtoempty(struct node *last, int data) { // This function is only for empty list if (last != NULL) return last; // Creating a node dynamically. struct node *last = (struct node*)malloc(sizeof(struct node)); // Assigning the data. last -> data = data; // Note : list was empty. We link single node // to itself. last -> next = last; return last; } Insertion at the beginning of the list To insert a node at the beginning of the list, follow these step: 1. Create a node, say T. 2. Make T -> next = last -> next. 3. last -> next = T. After insertion, Function to insert node in the beginning of the List struct node *addbegin(struct node *last, int data) { if (last == NULL) return addtoempty(last, data); // Creating a node dynamically. struct node *temp = (struct node *)malloc(sizeof(struct node)); // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = last -> next; last -> next = temp; return last; }  Page Number: 88 Prepared by: P.V.MAHESH KUMAR Insertion at the end of the list To Insert a node at the end of the list, follow these step: 1. Create a node, say T. 2. Make T -> next = last -> next; 3. last -> next = T. 4. last = T. Function to insert node in the end of the List struct node *addend(struct node *last, int data) { if (last == NULL) return addtoempty(last, data); // Creating a node dynamically. struct node *temp = (struct node *)malloc(sizeof(struct node)); // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = last -> next; last -> next = temp; last = temp; return last; } Steps to insert new node in a circular linked list 1. Create a new node and assign some data to its data field 2. Traverse to n-1 position in the list, in our case since we want to insert node at 3 rd position therefore we would traverse to 3-1 =2nd position in the list. Current pointer points to n-1th node 3. Link the next pointer field of newnode with the node pointed by the next pointer field of current(n-1) node. Newnode.next = current.next  Page Number: 89 Prepared by: P.V.MAHESH KUMAR 4. Connect the next pointer field of current node with the newly created node which means now next pointer field of current node will point to newnode // C program to insert a new node in a Circular Linked List #include #include struct node { int data; struct node *next; }*head; void createlist(int n); void displaylist(); void insertatbeginning(int data); void insertatn(int data, int position); int main() { int n, data, choice=1; head = NULL; while(choice != 0) { printf("1. Create List \n 2.Display list\n 3.Insert at beginning\n 4.Insert at any position\n 5.Exit\n"); printf("Enter your choice [1/2/3/4/5]: "); scanf("%d", &choice);  Page Number: 90 Prepared by: P.V.MAHESH KUMAR switch(choice) { case 1: printf("Enter the total number of nodes in list: "); scanf("%d", &n); createlist(n); break; case 2: displaylist(); break; case 3: printf("Enter data to be inserted at beginning: "); scanf("%d", &data); insertatbeginning(data); break; case 4: printf("Enter node position: "); scanf("%d", &n); printf("Enter data you want to insert at %d position: ", n); scanf("%d", &data); insertatn(data, n); break; case 5: break; default: printf("Error! Invalid choice. Please choose between 0-4"); } } } void createlist(int n) { int i, data; struct node *prevnode, *newnode; if(n >= 1) { head = (struct node *)malloc(sizeof(struct node)); printf("Enter data of 1 node: "); scanf("%d", &data); head->data = data; head->next = NULL; prevnode = head; for(i=2; idata = data; newnode->next = NULL; //Links the previous node with newly created node prevnode->next = newnode; //Moves the previous node ahead prevnode = newnode; } //Links the last node with first node prevnode->next = head; printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n"); } } void displaylist() { struct node *current; int n = 1; if(head == NULL) { printf("List is empty.\n"); } else { current = head; printf("DATA IN THE LIST:\n"); do { printf("Data %d = %d\n", n, current->data); current = current->next; n++; }while(current != head); } } void insertatbeginning(int data) { struct node *newnode, *current; if(head == NULL) { printf("List is empty.\n"); } else {  Page Number: 92 Prepared by: P.V.MAHESH KUMAR newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = data; newnode->next = head; current = head; while(current->next != head) { current = current->next; } current->next = newnode; head = newnode; printf("NODE INSERTED SUCCESSFULLY\n"); } } void insertatn(int data, int position) { struct node *newnode, *current; int i; if(head == NULL) { printf("List is empty.\n"); } else if(position == 1) { insertatbeginning(data); } else { newnode = (struct node *)malloc(sizeof(struct node)); newnode->data = data; current = head; for(i=2; inext; } newnode->next = current->next; current->next = newnode; printf("NODE INSERTED SUCCESSFULLY.\n"); } }  Page Number: 93 Prepared by: P.V.MAHESH KUMAR TUNE YOUR BRAIN TRUE OR FALSE 1. Pop() is used to add an element on the top of the stack 2. Postfix operation does not follow the rules of operator precedence 3. Recursion follows a divide-and-conquer technique to solve problems 4. Using a recursive function takes more memory and time to execute 5. Recursion is more of a bottom-up approach to problem solving 6. An indirect recursive function if it contains a call to another function which ultimately calls it 7. The peek operation displays the topmost value and deletes it from the stack 8. In a stack, the element that was inserted last is the first one to be taken out 9. Underflow occurs when TOP=MAX-1 10. The storage requirement of linked representation of the stack with n elements is O(n) 11. A push operation on linked stack can be performed in O(n) time 12. Overflow can never occur in case of multiple stacks 13. A queue stores elements in a manner such that the first element is at the beginning of the list and the last element is at the end of the list. 14. Elements in a priority queue are processed sequentially 15. In a linked queue, a maximum of 100 elements can be added 16. Conceptually a linked queue is same as that of a linear queue 17. The size of linked queue cannot change during run time 18. In a priority queue, two elements with the same priority are processed on a FCFS basis 19. Output restricted dequeue allows deletions to be done only at one end of the dequeue, while insertions can be done at both the ends 20. If FRONT = MAX -1 and REAR =0 then the circular queue is full Fill in the Blanks 1. ______ is used to convert an infix expression into a postfix expression 2. ______ is used in a non-recursive implementation of a recursive algorithm 3. The storage requirement of a linked stack with n elements is ______ 4. Underflow takes when ________ 5. The order of evaluation of a postfix expression is from _____ 6. Whenever there is a pending operation to be performed, the function becomes _____ recursive 7. A function is said to be _____ recursive if it explicitly calls itself 8. New nodes are added at _______ of the queue 9. ______allows insertion of elements at either ends but not in the middle 10. The typical time requirement for operations in a linked queue is _______ 11. In ____ insertions can be done only at one end, while deletions can be done from both the ends 12. Dequeue is implemented using ______  Page Number: 94 Prepared by: P.V.MAHESH KUMAR 13. _____ are appropriate data structures to process batch computer programs submitted to the computer centre 14. ______ are appropriate data structures to process a list of employees having a contract for a seniority system for hiring and firing 15. ______ is used to store the address of the first free memory location 16. The complexity to insert a node at the beginning of the linked list is ______ 17. The complexity to delete a node from the end of the linked list is _________ 18. Inserting a node at the beginning of the doubly linked list needs to modify ______ pointers 19. Inserting a node in the middle of the singly linked list needs to modify _____ pointers 20. Inserting a node at the end of the circular linked list needs to modify ____ pointers 21. Inserting a node at the beginning of the circular doubly linked list needs to modify _____ pointers 22. Deleting a node from the beginning of the singly linked list needs to modify ____ pointers 23. Each element in a linked list is known as a ____ 24. First node in the linked list is called the _____________ 25. Data elements in a linked list are known as _____ 26. Overflow occurs when ____ 27. In a circular linked list , the last node contains a pointer to the ____ node of the list 28. Stack follows ____ 29. Queue follows _______ 30. Primitive operations of stack is _____ , primitive operations of Queue is __________ MCQs 1. A linked list is a a. Random access structure b. Sequential access structure c. Both d. None of the above 2. An array is a a. Random access structure b. Sequential access structure c. Both d. None of the above 3. Linked list is used to implement data structures like a. Stacks b. Queues c. Trees d. All the above 4. Which type of linked list contains a pointer to the next as well as the previous node in the sequence a. Singly linked list b. Doubly linked list c. Circular linked list d. All the above 5. Which type of linked list does not store NULL in the next field a. Singly linked list  Page Number: 95 Prepared by: P.V.MAHESH KUMAR b. Doubly linked list c. Circular linked list d. All the above 6. Which type of linked list stores the address of the header node in the next field of the last node a. Singly linked list b. Doubly linked list c. Circular linked list d. Circular header linked list 7. Which type of linked list can have four pointers per node? a. Circular doubly linked list b. Multi linked list c. Header linked list d. Doubly linked list 8. Stack is a a. LIFO b. FIFO c. FILO d. None of these 9. Which function places an element on the stack? a. Pop() b. push() c. peek() d. None of these 10. Disks piled up one above the other represent a a. Stack b. Queue c. linked list d. Array 11. Reverse polish notation is the other name of a. Infix expression b. Prefix expression c. Postfix expression d. Algebraic expression 12. A line in a grocery store represents a a. Stack b. Queue c. linked list d. Array 13. In a queue, insertion is done at a. Rear b. front c. back d. top 14. The function that deletes values from a queue is called a. Enqueue b. dequeue c. pop d. peek 15. Typical time requirement for operations on queues is a. O(1) b. O(n) c. O(logn) d. O(n2) 16. The circular queue will be fully only when a. FRONT = MAX-1 and REAR = MAX-1 b. FRONT =0 and REAR = MAX -1 c. FRONT =MAX -1 and REAR =0 d. FRONT =0 and REAR =0 Polynomial List A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. + jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative integer, which is called the degree of polynomial. An important characteristics of polynomial is that each term in the polynomial expression consists of two parts:  Page Number: 96 Prepared by: P.V.MAHESH KUMAR one is the coefficient other is the exponent Example: 10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential value. Points to keep in Mind while working with Polynomials: The sign of each coefficient and exponent is stored within the coefficient and the exponent itself Additional terms having equal exponent is possible one The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent Representation of Polynomial Polynomial can be represented in the various ways. These are: By the use of arrays By the use of Linked List Representation of Polynomials using Arrays There may arise some situation where you need to evaluate many polynomial expressions and perform basic arithmetic operations like: addition and subtraction with those numbers. For this you will have to get a way to represent those polynomials. The simple way is to represent a polynomial with degree 'n' and store the coefficient of n+1 terms of the polynomial in array. So every array element will consists of two values: Coefficient and Exponent Representation of Polynomial Using Linked Lists A polynomial can be thought of as an ordered list of non zero terms. Each non zero term is a two tuple which holds two pieces of information:  Page Number: 97 Prepared by: P.V.MAHESH KUMAR The exponent part The coefficient part Adding two polynomials using Linked List Given two polynomial numbers represented by a linked list. Write a function that add these lists means add the coefficients who have same variable powers. Example: Input: 1st number = 5x^2 + 4x^1 + 2x^0 2nd number = 5x^1 + 5x^0 Output: 5x^2 + 9x^1 + 7x^0 Input: 1st number = 5x^3 + 4x^2 + 2x^0 2nd number = 5x^1 + 5x^0 Output: 5x^3 + 4x^2 + 5x^1 + 7x^0 Page Number: 98 Prepared by: P.V.MAHESH KUMAR  Page Number: 99 Prepared by: P.V.MAHESH KUMAR struct Node { int coeff; int pow; struct Node *next; }; void create_node(int x, int y, struct Node **temp) { struct Node *r, *z; z = *temp; if(z == NULL) { r =(struct Node*)malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y;  Page Number: 100 Prepared by: P.V.MAHESH KUMAR r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } } void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly) { while(poly1->next && poly2->next) { if(poly1->pow > poly2->pow) { poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next; } else if(poly1->pow < poly2->pow) { poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next; } else { poly->pow = poly1->pow; poly->coeff = poly1->coeff+poly2->coeff;  Page Number: 101 Prepared by: P.V.MAHESH KUMAR poly1 = poly1->next; poly2 = poly2->next; } poly->next = (struct Node *)malloc(sizeof(struct Node)); poly = poly->next; poly->next = NULL; } while(poly1->next || poly2->next) { if(poly1->next) { poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next; } if(poly2->next) { poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next; } poly->next = (struct Node *)malloc(sizeof(struct Node)); poly = poly->next; poly->next = NULL; }  Page Number: 102 Prepared by: P.V.MAHESH KUMAR } void show(struct Node *node) { while(node->next != NULL) { printf("%dx^%d", node->coeff, node->pow); node = node->next; if(node->next != NULL) printf(" + "); } } int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; // Create first list of 5x^2 + 4x^1 + 2x^0 create_node(5,2,&poly1); create_node(4,1,&poly1); create_node(2,0,&poly1); // Create second list of 5x^1 + 5x^0 create_node(5,1,&poly2); create_node(5,0,&poly2); printf("1st Number: "); show(poly1); printf("\n2nd Number: "); show(poly2);  Page Number: 103 Prepared by: P.V.MAHESH KUMAR poly = (struct Node *)malloc(sizeof(struct Node)); // Function add two polynomial numbers polyadd(poly1, poly2, poly); // Display resultant List printf("\nAdded polynomial: "); show(poly); return 0; } Output: 1st Number: 5x^2 + 4x^1 + 2x^0 2nd Number: 5x^1 + 5x^0 Added polynomial: 5x^2 + 9x^1 + 7x^0  Page Number: 104 Prepared by: P.V.MAHESH KUMAR TREES A Tree is a Non-liner hierarchical Data structure that consists of nodes connected by edges. B , C are Child nodes of A D ,E child node of B F and G child nodes of C Who does not have Child Nodes , those are called LEAF nodes Here We can n number of Parent nodes, but only one ROOT node H,E,F,G are LEAF NODES Level 0 - Root Level -1 B C Level 2 – D E F G Level 3 - H  Page Number: 105 Prepared by: P.V.MAHESH KUMAR Root: It is the topmost node of a tree Height of a Node : The height of a node is the number of edges from the node to the deepest leaf (i.e. the longest path from the node to a leaf node) Eg: Height of B node is 2 Depth of a Node: The depth of a node is the number of edges from the root to the node Parent Node: If the Node contains any sub-node then the node is said to be the parent of that sub-node Child Node: If the Node is descendant of any node then the node is known as a child node Degree of a Node: The degree of a node is the total number of branches of that node Height of x = No of edges in the longest path from x to a leaf Height of B = 2 Height of root = 3 = Height of Tree Applications: 1. Storing naturally hierarchical data , eg : file system 2. Organize data for quick search , insertion, deletion 3. Network routing algorithm ,…. etc. TYPES OF TREES General Tree - A node can have either 0 or Maximum N number of Nodes Binary Tree -Each node in a tree can have the utmost two child nodes Binary Search Tree -A node can be connected to the utmost two child nodes in a binary search tree AVL Tree -Self Balancing Tree Trie -It is a fast and efficient way for dynamic spell checking  Page Number: 106 Prepared by: P.V.MAHESH KUMAR Heap -It is used to implement priority Queues BINARY TREE In Binary Tree , each Node can have utmost two child Binary Tree is either empty or consists of a node called root node together with two binary tree Left Sub Tree : B D E H I Right Sub Tree : C F G Leaf Nodes : H I E F G  Page Number: 107 Prepared by: P.V.MAHESH KUMAR Other Tree Terms The number of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1, or 2. A node of degree zero is called a terminal node or leaf node. A non-leaf node is often called a branch node. The degree of a tree is the maximum degree of a node in the tree. A binary tree is degree 2. A directed path from node n1 to nk is defined as a sequence of nodes n1, n2,..., nk such that ni is the parent of ni+1 for 1 Array[j+1] then temp ← Array[j] Array[j] ← A [j+1] Array[j+1] ← temp //Program  Page Number: 158 Prepared by: P.V.MAHESH KUMAR #include main() { int a,i,j,n,temp; printf("\n Howmany elements to be read :"); scanf("%d",&n); printf("\n Enter %d Elements :\n ",n); for(i=0;i valueToInsert do: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 end while A[holePosition] = valueToInsert end for end procedure  Page Number: 164 Prepared by: P.V.MAHESH KUMAR PROGRAM : #include main() { int i,j,n,temp,a; printf("\n Howmany elements to be in array :"); scanf("%d",&n); printf("\n Enter %d Elements :\n ",n); for(i=0;i j. Step 7 - Exchange the pivot element with a[j] element. a a a a a a a a  Page Number: 165 Prepared by: P.V.MAHESH KUMAR 5 3 8 1 4 6 2 7 Here pivot =5 left > pivot right < pivot 3>5 false 8>5 true so left element is 8 7 5 4 >5 6>5 so left =6 84 16 7