Scribd
Importer
6 vues62 pages

DSA Module-3

Le document traite des listes chaînées, en soulignant leurs avantages par rapport aux tableaux, notamment en matière d'utilisation efficace de la mémoire et de facilité d'insertion et de suppression. Il présente également des opérations fondamentales sur les listes chaînées, telles que l'insertion et la suppression d'éléments, ainsi que des exemples de code en C pour illustrer ces concepts. Enfin, le document aborde l'implémentation de piles et de files d'attente à l'aide de listes chaînées.

Transféré par

wadofas620
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
6 vues62 pages

DSA Module-3

Le document traite des listes chaînées, en soulignant leurs avantages par rapport aux tableaux, notamment en matière d'utilisation efficace de la mémoire et de facilité d'insertion et de suppression. Il présente également des opérations fondamentales sur les listes chaînées, telles que l'insertion et la suppression d'éléments, ainsi que des exemples de code en C pour illustrer ces concepts. Enfin, le document aborde l'implémentation de piles et de files d'attente à l'aide de listes chaînées.

Transféré par

wadofas620
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Lecture Notes Data Structures and Applications [BCS304] Linked Lists Advantages of Linked Lists over Arrays 1, Efficient Memory Utilization: The memory of a linked list is not pre-allocated Memory is allocated whenever required and de-allocated when it is no longer required Insertion and deletion operations are easier and efficient. 3. Extensive manipulations: Without any prior idea of memory space available we can perform the computations. Example, there is no “overflow condition” while implementing stacks or queues. 4, Data can be stored in non-contiguous blocks of memory which exhibits logical adjacency i.e. they are linked by pointers. Disadvantages of Linked Lists 1. Itrequires extra space because each node requires to hold the address of the next node within it (ie, a pointer field) Accessing a particular node in the list may take more time compared with arrays because the list needs to be traversed from the beginning, Singly Linked Lists and Chains Linked list is a linear collection of data elements called nodes and there exi: sa logical relationship between nodes (ic. given the address of first node, any node in that list can be obtained) The pictorial representation of a singly linked list is as shown below. 1000-2000 1500 3000 first [10 f20 £30 a \ 1 Tt Info field Link field Paes Each and every node has 2 fields pera a Ce, Bast Y Info field — Here some useful information can be stored Y Link field — This field contains address of the next node. So this field should be of type pointer Note: A chain is a singly linked list that is compromised of zero or more nodes. When the number of nodes is zero, the chain is empty. The nodes of a chain are ordered so that the first node links to the second, second to the third and so on, The last node of a chain has a zero link (NULL). Module 3 1 Lecture Notes Data Structures and Applications [BCS304] Representing Chains in C The following capabilities are needed to make linked representation possible Y A mechanism to define the nodes structure. This is done using self-referential structures Y Away to create new nodes when we need them, This is done using malloc ) function, Y Away to remove nodes that we no longer need. This is done using free( ) function ion for each in the list. The following is the structure defi: struct node { int info: Dr. Mahesh G struct node "link; Dept of CSE, BMSIT & ME h In the above structure definition the type of field or member (link) is same as the structure name and therefore known as self referential structure. Note: ¥ The variable ‘first’ contains the address of first node (initially NULL) All functions require first Functions that manipulate the linked list should return the address of the first node first = NULL => List is empty first link = NULL => There is one element in the List SKK K first >link ! = NULL => There is more than one element in the List Module 3 2 Lecture Notes Data Structures and Applications [BCS304] Fundamental Operations of a Linked List In the following functions we use the structure definition as shown below struct node { int info, struct node “link; ub typedef struct node * NODE; Function to create a 2-node list NODE create2() { NODE first, second; first = (NODE)malloe(sizeof{struct node); second = (NODE)malloe(sizeof(struet node)); first->info = 105 first->link = second; second->info = 20; Dr. Mahesh G 5 , Professor, second->link ULL; Dept of CSE, BMSIT & M return first; } Function to insert an element at the front end NODE insert_front(int item, NODE first) { NODE temp; temp = (NODE)mallloe(sizeof{struet node)); temp->info = item; temp->link return tem } Function to delete an element at the front end NODE delete_front(NODE first) { NODE temp; if(first==NULL) // no node { printf("list is empty\n"); return firsts Module 3 Lecture Notes } temp = first; first = first->link; printf("the deleted item is %d", temp->info); free(temp); return(first); Function to insert an element at the rear end NODE insert_rear(int item,NODE first) { } NODE temp, curs temp=(NODE)malloc(sizeof(struct node); temp->info = items temp->link = NULL; if(first==NULL) //no node Data Structures and Applications [BCS304] { return temp; } cur = firsts // node exists while(cur->link != NULL) { = cur->link; } cur cursiny Dr. Mahesh G Professor, cur->link = temp; Dept of OSE, BMSIT ® M return first; Function to delete an element at the rear end NODE delete_rear(NODE first) { NODE prev, cur; if(first==NULL) //no node { printf("list is empty\n"); return first; } if(first ->link = { NULL) //only one node printf("the deleted item is %d", first->info); free(first); return( NULL ); 3 prev = NULL; // more than one node cur = first; Module 3 Lecture Notes Data Structures and Applications [BCS304] while(cur->link { NULL) prev = cur; cur = cur->link; 3 printf("the deleted item is %d", cur->info); free(cur); prev->link = NULL; return(first); ction to display the contents of the list void display(NODE first) DaManesnG) Professor, ‘ NODE cur; Day of SF BAIT Mt if(first = = NULL) { printf("the list is empty\n"); returns } cur = firsts printf("the contents of the list are:\n")s while(cur != NULL) { printf("%d\n" ,cur->info); cur = cur->links } Note: 1. To implement stacks using linked lists the functions required are Y Insert_front( ), Delete front and Display() OR Y Insert_rear( ), Delete_rear and Display( ) 2. Toimplement queues using linked lists the function required are ¥ Insert_front( ), Delete_rear and Display() OR Y Insert_rear( ), Delete_front and Display( ) 3. To implement De-queues using linked lists the function required are ¥ Insert front( ), Delete front, Insert_rear( ), Delete_rear and Display( ) // Main function for Stacks using Linked void main( ) { int choice, item; NODE first = NULL; elrser( ); Module 3 Lecture Notes Data Structures and Applications [BCS304] for(s3) { printf("\n1:push\n2:pop\n3:display\ndzexit\n" printf("enter your choice"); seanf("%d" choice); switch(choice) { case 1: printf("enter the item to be pushed\n"); seanf("%d"écitem); first = insert_front(item,first); break; case 2: first = delete_front({first); break; case 3: display(first); break; default : exit(0); } geteh( ); } } // Main function for queues using linked lists void main() { int choice, item; NODE first = NULL; peMahesh elrser( ); Dap of 1. DUSTTA M for(s3) { printf("\n1:insert\n2zdelete\n3:display\n4zexitin"); printf(“enter your choice"); seanf("%d" &choice); switeh(choice) { case 1: printf("enter the item to be pushed\n"); seanf("%d" item) first = insert_rear(item, first); break; case 2: first = delete_front( first); break; case 3: display(first); break; default : exit(0); } getch( ): } } Module 3 6 Lecture Notes Data Structures and Applications [BCS304] Design, Develop and Implement a menu driven Program in C for the following operations on Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo a. Create a SLL of N Students Data by using front insertion », Display the status of SLL and count the number of nodes in it c. Perform Insertion / Deletion at End of SLL 4, Perform Insertion / Deletion at Front of SLL(Demonstration of stack) e, Exit #include struct node { char usn{10]; char name[20], char branch{20]; int sem; char phnof20]; struct node "link; 1 typedef struct node * NODE; Function to insert at the front end NODE insert_front(char usn{], char name[], char branch[], int sem, char phno[], NODE { NODE temp; temp = (NODE)malloc(sizeof(struct node)); strepy(temp->usn, usn); strepy(temp->name, name); strepy(temp->branch, branch); cree n S temp->sem = sem; Dept of CSE, BMSIT & M strepy(temp->phno, phno); temp->link = firs return temp; } Function to delete at the front end NODE delete_front(NODE first) { NODE temp; if(first==NULL) // no node { printf("list is empty\ return firsts } Module 3 7 Lecture Notes Data Structures and Applications [BCS304] } temp = first; first = first->links printf(’Student with following details is deleted\n" printf(‘usn ; %s\n", temp->usn); printf("name : %s\n", temp->name); printf("branch : %s\n", temp->branch); printf(’sem : %d\n", temp->sem); printf("phone no : %s\n", temp->phno); free(temp); return(first); Function to insert at the rear end NODE insert_rear(char usn[], char name[]. char branch{], int sem, char phno[], NODE first) { NODE temp, curs temp=(NODE)malloe(sizeof(struct node)); strepy(temp->usn, usn); strepy(temp->name, name); Dr, Mahesh G strepy(temp->branch, branch); Professor, femp->sem = sem; Dap of CSE BST M strepy(temp-phno, phno); temp->link = NULL; if(first==NULL) //no node { return temp; 3 cur = firsts J node exists while(cur->link != NULL) { cur = cur->link; } cur->link = temp; return first; Module 3 8 Lecture Notes Data Structures and Applications [BCS304] Function to delete at the rear end NODE delete_rear(NODE first) { NODE prev, curs if(first==NULL) // no node { printf(“list is empty\n"); return first; } if(first >link == NULL) // only one node { printf("Student with following details is deleted\n"); printf(usn : %s\n", first->usn); printf(’name ; %s\n", first ->name)3 printf("branch ; %s\n", first >branch); printf("sem : %d\n", first ->sem); printf("phone no : %s\n", first ->phno); free(first); return( NULL ); } prev=NULL; _// more than one node cur = firsts while(cur->link != NULL) { Dr. Mahesh G prev = cur, Dent of SE BMGT @M cur = cur->link; } printf("Student with following details is deleted\n"); printf("usn : %s\n", cur->usn); printf("name : %s\n", cur >name); printf("branch : %s\n", cur ->branch); printf("sem : %d\n", cur ->sem); printf("phone no : %s\n", cur ->phno); free(cur); prev->link = NULL; return(first); Module 3 Lecture Notes Data Structures and Applications [BCS304] Function to display the contents of the list and count the number of nodes void display(NODE first) { NODE cur: it count ; if(first = = NULL) { printf("the list is empty\n"); printf("the number of nodes in the list is %d\n", count); return; } fe cur = firsts printf("the contents of the list are:\n"); printf("usn\t nameit branch\t sem\t phoneno\n"); while(cur != NULL) { count = count + 1; printf("usn : %s\t", cur->usn); printf("name : %s\t", cur >name); printf("branch ; %s\t", cur ->branch); printf(’sem : %d\t", cur ->sem); printf("phone no : %s\n", cur ->phno); cur = cur->link; } printf("the number of nodes in the list is %d\n", count); Dr. Mahesh G Professor, void main() Dept. of OSE, BMSIT A ML { int choice, sem, n,i; char usn[20], name[20], branch{20}, phno[20]; NODE first = NULL; clrser()s // Creating a list of 'n’ students using front insertion printf("Enter the number of students"); seanf("%d", &n); for(i=0; i struct node { int info; struct node *link; 4 typedef struct node * NODE; // Function to insert an element at the front end // Function to delete an element from the front end // Bunction to display the contents of the list 1 Main function for Multiple Stacks using Linked Lists void main() { int choice, item, NODE first{ 100]; int n3 // number of stacks; printf(“enter the number of stacks\n”); seanf(“%od”, &n); for(i=0; isn; i++) { } for(;3) first{i] = NULL; printf("\n1:push\n2:pop\n3:display\n4:exit\n"); printf(“enter your choice"); scanf("%d" &choice); switch(choice) { case 1: printf("enter the stack number to push\n"); seanf("%d" i); printi("enter the item to be pushed\n"); seanf("%d" item); first[i] = insert_front(item,first{i]); breaks Module 3 13 Lecture Notes Data Structures and Applications [BCS304] case 2: printf("enter the stack number to pop\n"); seanf("%d",&i); first[i] = delete_front(firstfi]); break; case 3: printf("enter the stack number to display\n"); seanf("%d" i); display(first[i))s break; default it(0); 3 Implementation of multiple queues using linked lists, #include Dr. Mahesh G struct node Manes t Dap of OSE BUSI M int info, struct node *link; ); typedef struct node * NODE; // Function to insert an element at the rear end // Function to delete an element from the front end // Bunetion to display the contents of the list // Main function for Multiple Queues using Linked Lists void main() { int choice, item, i; NODE first{ 100]; int n; // number of queues; printf(“enter the number of queues\n”); seanf(“%d”, &n); for(i=0; in; i++) t 3 first{i] = NULL; Module 3 4 Lecture Notes for(33) { print Data Structures and Applications [BCS304] "\n Lsinsert \n2:delete \n3:display\n4zexit\n"); printf("enter your choice”); scanf("%d" choice); switch(choice) { case 1: case 2: case 3: printf("enter the queue number to insert\n"); seanf("%d" Sci); printf("enter the item to be inserted\n"); scanf(""%d"écitem); first{i] = insert_rear(item,first{i]); break; printf("enter the queue number to delete\n"); seanf("%d" i); first[i] = delete_front(first[i)); breaks printf("enter the queue number to display\n"); seanf("%d" i); display(firsti))s break; default : exit(0); Module 3 Dr. Mahesh G Professor Dept of CSE, BMSIT & M 15 Lecture Notes Data Structures and Applications [BCS304] Other operations of a linked list Function to count the number of nodes in a list int count_nodes(NODE first) { int count = 0; NODE curs cur = firsts while(cur = NULL) { count = count + 1; cur = cur->link; } return count; } Function to concatenate 2 lists NODE concatenate(NODE first, NODE second) { NODE cur if(first = = NULL) return second; if(second = = NULL) return first; cur = firsts while(cur >link!= NULL) { Dr. Mahesh G 7 Professor cur = cur->link; Dept. of CSE, BMSIT.& M. } cur->link = seconds return first; } Function to reverse a singly li NODE reverse(NODE first) { ked list without creating a new node NODE temp, curs if(first = = NULL) return first: temp = NULL; while(first!= NULL) { cur = first; first = first->link; cur->link = temps temp = cur; } return temp; Module 3 16 Lecture Notes Data Structures and Applications [BCS304] Note: At first or beginning, first contains address of the list to be reversed, later temp contains address of the reversed list. Function to delete a node whose information field is given NODE delete_info(int item, NODE first) { NODE cur, temp, prev, next; if(first = = NULL) // empty list { printf("the list is empty\n"); return first; } if(item == first->info) _//if it is the first node { temp=first; first = first->link; printf(“item deleted is %d",temp->info); free(temp); return first; } prev=NULL; other than first node cur = first; while(cur != NULL && item != cur->info) { our = eurinks Dr: Mahesh G } Dept. of CSE, BMSIT & Mt if(cur = = NULL) { printf("item not found\n"); return first; } next = cur>link prev->link = next; printf(“item deleted is %d" ,cur->info); free(cur); return firsts Module 3 17 Lecture Notes Data Structures and Applications [BCS304] Function to insert an item at a specified position NODE insert_pos(int item, int pos, NODE first) { NODE temp, cur, prevs int count; temp=(NODE)malloe(sizeof{struct node)); temp->info = item; temp->link = NULL; first = = NULL && pos == 1) // no elements in the list return temp; if(pos { =) //insert at the beginning temp->link = firsts return temp; } prev=NULL; —_// find appropriate position cur = firsts count = 1; while(cur != NULL && count != pos) { prev = curs cur = cur->links count++; } if(count != pos) { printf("invalid position\n"); free(temp); return first; } prev->link = temp; temp->link = cur; return firsts Module 3 18 Lecture Notes Data Structures and Applications [BCS304] Function to insert an element into the list such that after insertion the list remains sorted. NODE insert_order(int item, NODE first) { } NODE temp, cur, prev; temp=(NODE)mallloc(sizeof(struct node)); temp->info = item; temp->link = NULL; if(first==NULL) // no elements in the list return temp; if(item < first->info) //insert at the beginning temp->link = firsts return temp; } prev = NULL; //insert at middle or end cur = firsts while(cur != NULL && item > cur->info) { prev = curs cur = cur->link; } prev->link = temp; temp->link = curs return first; Function to merge 2 sorted lists into a single sorted list NODE merge(NODE a, NODE b) { NODE k, c, temp: c= (NODE) malloc(sizeof{struct node)): k=c; while(a!= NULL && b!= NULL) { iffa->info info) Module 3 19 Lecture Notes Data Structures and Applications [BCS304] } } Function to search for an item in the list and display the positios else { k->link = b; b= b->link; k = k->link; } } if(b!=NULL) k->link = b; else k->link = a; temp = c= clink; free(temp); return c; found void search_item(int item, NODE first) { int pos, if(first = = NULL) { printf(“list is empty\n”), return; } Dr. Mahesh G Professor, ao Dept of OSE, BAIS & ME pos while(cur != NULL && item != cur->info) { cur = curlink; pos = pos + 1; } JULL) printi(“Unsuccessful search\n”); return; } printi(“Successful search and item found at position %d\n”, pos); Module 3 20 Lecture Notes Data Structures and Applications [BCS304] Function to delete an element at the specified position NODE delete_pos(int pos, NODE first) { NODE cur, prev, next, temps if(first = = NULL) // empty list { printf("the list is empty\n"); return first; } if(pos = = 1) if { is the first position temp=firsts first = first->link; printf(“item deleted is %d",temp->info); free(temp); return first; } prev=NULL; —_// other than first position cur = firsts count = 1; while(cur != NULL && count != pos) { cur = cur->link; count = count +1; = NULL) printf("invalid position\n"); return first; next = cur->link prev->link = next; printf("item deleted is %d" free(cur); return first; Module 3 2 Lecture Notes Data Structures and Applications [BCS304] Function to delete all the nodes whose info field is same as the item specified (E) NODE delete_all_specified_items(int item, NODE first) 4 int flag; NODE prev, cur; flag = 0; prev = NULL; cur = first; while( cur != NULL ) 4 iffitem == cur>info) { flag = flag + 1; iffprev != NULL) _ // other than first { prev->link = cur->link; free(cur); cur = prev->link; J update eur } else _//if it is the first node { first = first->link: free(cur); cur = first; } 3 he Dr. Mahesh G Professor, eee Dept. of CSE, BNISTT & M cur = cur->link; } } if(flag = = 0) printf(“item not found\n”); else printf(“%d number of nodes are deleted\n”, flag): return first; } Module 3 2 Lecture Notes Data Structures and Applications [BCS304] Write a ‘C’ function to remove DUPLICATE elements in a singly linked list. (E) NODE remove_duplicate(NODE first) { if(first = = NULL) / empty printf("the list is empty\n"); return first; } temp = first; while(temp != NULL) { item = temp->info; prev = temp: cur = temp->link; while( cur != NULL ) { iffitem = = curinfo) { prev->link = cur->link; free(cur): cur = prev->link; update cur } else { prev = cur; cur = cur } } temp = temp->link; } return first; Module 3 23 Lecture Notes Data Structures and Applications [BCS304] Write a ‘C’ function to find UNION of two singly linked lists. (E) Assumption: No duplicate elements in the list int search(int item, NODE first) // return 1 if item found else return 0 { } if(first = = NULL) return 0; } cur = first; while(cur = NULL && item != cur->info) { } if(cur = = NULL) { } return 1; cur = cur->link; return 0: NODE union(NODE a , NODE b) { } NODE e=NULL, cur, NULL) retumn b; = NULL) return a; cur=a; while(cur != NULL) { c= insert_rear(cur->info, ¢); cur = cur>link; } cur=b; while(cur != NULL) { flag = search(cur->info, a); ififlag == 0) c= insert_rear(cur->info, ); cur = cur>link; } return ¢; Module 3 24 Lecture Notes Data Structures and Applications [BCS304] Write a ‘C’ function to find INTERSECTION of two singly linked lists. (E) Assumption: No duplicate elements in the list int search(int item, NODE first) // return { item found else return 0 if{first = = NULL) { } return 0; cur = first; while(cur != NULL && item != cur->info) f } cur = cur->link; if(ou NULL) { } return 0; return 1; } NODE intersection(NODE a , NODE b) { NODE c=NULL, cur; int fla if NULL) return NULL; if(b = = NULL) return NULL; cur =a; while(cur != NULL) { flag = search(cur>info, b); if(flag = 1) c= insert_rear(cur->info, c); cur = cur->link; } return c; Module 3 25 Lecture Notes Data Structures and Applications [BCS304] Header Nodes Some times it is desirable to keep an extra node at the front of a list which simplifies the deign process of some list operations, Such a node does not represent an item in the list and is called a header node or a list header The info field of such a header node generally contains the global information of the entire list, like the number of nodes in the list./ Ex head 3 >10 $20 p30 \ head —_// empty list with header node oN In both the cases the info field of head contains the total number of nodes in the list. Each time a node is added or deleted, the count in this field (i.e info field of the header) must be readjusted so as to contain actual number of nodes currently present which is certainly a overhead, Dr. Mahesh G Professor, Dept of CSE, BMSIT & M Note: Y If the list is empty, link field of the header node points to NULL. Otherwise, link field of the header node contains the address of the first node of the list and the link field of the last node contains NULL. Given a list with header node, any node in the list can be accessed without the need for a pointer variable (first, which points to the first node as in before examples) Module 3 26 Lecture Notes Data Structures and Applications [BCS304] Circular Singly Linked List In normal singly linked list, ¥- The link part of the last node has NULL value, speci ng that itis the last node. Y Given the address of any node ‘x’, itis only possible to reach the nodes which follow “x and it is not possible to reach the nodes that precedes ‘x’ (previous nodes). To reach the nodes that precedes ‘x’, it is required to preserve a pointer variable first, which contains the address of the first node in the list and use this for traversing. Y Also, given the address of the first node to get the address of the last node, the list has to be traversed from the beginning till the last node is reached These disadvantages can be overcome using circular singly linked list. In a circular singly linked list the link field of the last node points to the first node in the list, which makes the list a circular one. The pictorial representation is as shown below. last 10t #30 P40 last 1054-420 Dr. Mahesh G Professor, Dept. of CSE, BMSIT'& M last Gy Y Here the link field of the last node contains address of the first node. Note: ¥ In the following functions we use the structure definition as shown below. v struct node t int info, struct node “link; h typedef struct node * NODE; Module 3 27 Lecture Notes Data Structures and Applications [BCS304] Function to insert an element at the rear end NODE insert_rear(int item, NODE last) { NODE tem temp=(NODE)malloe(sizeof(struet node)); temp->info = item; temp->link = temp; if(last==NULL) //no node { return temp; } temp->link = last->link; last->link = temp; return temp; } Function to insert an element at the front end NODE insert_front(int item, NODE last) { NODE temp; temp=(NODE)malloc(sizeof(struct node)); temp->info = item; temp->link = temp; if(last==NULL) //no node { return temp; } temp->link = last->link; ae last->link = temp; Dept of OSE, BMSTT& M Dr. Mahesh G return last; Function to delete an element at the front end NODE delete_front(NODE last) { NODE first; if(last==NULL) // no node { printf("list is empty\n"); return last; } if(last ->link==last) _// only one node { printf("the deleted item is %d", last->info); free(last); return( NULL ); } Module 3 28 Lecture Notes Data Structures and Applications [BCS304] } first = last->link; _ // more than one node last->link = first->link; printf("the deleted item is %d", first->info); free(first); return(last); Function to delete an element at the rear end NODE delete_rear(NODE last) { } NODE cur; if(last==NULL) //no node printf("list is empty\n"); return lasts } if(last >link==last) —_// only one node { printf("the deleted item is %d", last->info); free(last); return( NULL ); } cur=last->link; _// more than one node while(cur->link != last) { } cur->link = last->links printf("the deleted item is %d", last->info); free(last); return(cut); Dr. Mahesh G Professor, BM cur = cur->link; Dept. o Te M Function to display the contents of the list void display(NODE last) { NODE cur; if(last = = NULL) { printf("the list is empty\n"); return; } cur = last->links Module 3 29 Lecture Notes Data Structures and Applications [BCS304] printf("the contents of the list are:\n"); while(cur != last) { printf("%d\n" cur->info); cur = cur->link; } printf("%d\n",last->info); } // Main function for circular singly linked lists void main() { Dr. Mahesh G it choice, item; Professor, NODE last = NULL} Dept of CSE, BMSIT & M clrser(); for(33) { printf("\n1:insert-front\n 2:insert-rear\n "); printf("\n3:delete-frontin 4:delete-rear\n "); printf("\nS:display\n 6:exit\n ")s printf("enter your choice"); seanf("%d",&choice); switch(choice) { case 1: printf("enter the item to be inserted\n"); scanf("%d",&item) last = insert_front(item, last); break; case 2: printf("enter the item to be inserted\n"); anf("%d" item); last = insert_rear(item, last); break; case 3: last = delete_front(last); break; case 4: last = delete_rear(last); break; case 5: display(last); break; default : exit(0); } getch( ): ; } Module 3 30 Lecture Notes Data Structures and Applications [BCS304] Function to find the length of a circular list void length(NODE last) { } NODE cur; int count; if(last = = NULL) { printf("the length of the list is 0 \n"); return; 3 cur = last-Links count = 1; while(cur != last) { count = count + 1; cur = cur->link; 3 printf("the length of the list is %d \n", count); Function to search for an item in the list. The function should return a pointer to the node containing the item if found and NULL otherwise NODE search_item(int item, NODE last) { NODE cur; if{last = = NULL) { printf(“list is empty\n”), return NULL; Or. Mahesh G ) Dept of OSE. BMSIT @ M iffitem = = last->info) { printi(“Successful search\n”), return last; printi(“Unsuccessful search\n”); return NULL; 3 printi(“Successful search \n”) return cur, Module 3 31 Lecture Notes Data Structures and Applications [BCS304] Circular Singly Linked List with header node Here if the list is empty, link of head contains head, otherwise link field of header node contains address of the first node. The link field of last node contains address of header node. The pictorial representation of this is as shown below head last 3 FH 10 +20 p30 Head 44 Note: In the following functions we use the structure definition as shown below struct node { int info; struct node *link; } typedef struct node * NODE; Function to insert an element at the front end NODE insert_front(int item, NODE head) { NODE temp; temp=(NODE)malloe(sizeof(struct node)); temp->info = item; temp->link = head->link; head->link = temps head->info = head->info + 1; Dr. Mahesh G return head; Seanad } Function to insert an element at the rear end NODE insert_rear(int item, NODE head) { NODE temp, curs temp=(NODE)malloc(sizeof(struct node)); temp->info = item; cur = head->link; while(cur->link != head) { } cur->link = temp; temp->link = heads head->info = head->info + return heads cur = cur->link; } Module 3 32 Lecture Notes Data Structures and Applications [BCS304] Function to delete an element at the front end NODE delete_front(NODE head) { NODE curs if(headlink==head) _ // no node { printf("list is empty\n")s return heads } cur = head->links head->link = cur->link; printf("the deleted item is %d", cur->info); free(cur); head->info = head->info - 13 return(head); } Function to delete an element at the rear end NODE delete_rear(NODE head) { NODE prev, curs if(head->link==head) _ // no node { printf(“list is return head; mpty\n"); } prev = head; cur = head->links while(cur->link != head) { prev = cur; cur = cur->links } prev->link = head; printf("the deleted item is %d", cur->info)s free(cur); head->info = head->info - 1; return(head); } Function to display the contents of the list void display(NODE head) { NODE cur; if(head-link = = head) { printf("the list is empty\n"); Module 3 33 Lecture Notes return; } cur = head->link; printf("the contents of the list ares\n"); while(cur != head) { printf("%d\n" cur->info); cur = cur->link; // Main function for circular singly linked lists with header node main() t choice, item; NODE head: head = (NODE) malloc(sizeof(struct node)): head->info = 0; head->link Dr. Mahesh G ; Professor, elrser()5 Dept. of CSE, BMSIT & M for(33) { printf("\n1:insert-front\n 2zinsert-rear\n ")s printf("\n3:delete-frontin 4zdelete-rear\n "); printf("\nS:display\n 6:exit\n "); printf("enter your choice"); scanf("%d",&-choice) switeh(choice) { case 1: printf("enter the item to be inserted\n"); scanf("%d" item) head = insert_front(item, head); break; case 2: printf("enter the item to be inserted\n"); scanf("%d" item); head = insert_rear(item, head); break; case 3: head = delete_front(head); break; case 4: head = delete_rear(head); break; case 5: display(head); break; default : exit(0); Module 3 Data Structures and Applications [BCS304] Lecture Notes Data Structures and Applications [BCS304] Doubly Linked List Disadvantages of Singly Linked List V Given the address of a node in the list, it is difficult to find the address of previous node. Y Traversing of list is possible only in the forward direction and hence singly linked list is also termed as one-way list. Doubly Linked List Representation To increase the performance and efficiency of algorithms, it is required to traverse the list in either forward or backward direction. Therefore a two-way list called as doubly linked list can be made use of, so that traversing from left to right (forward) or right to left (backward) is possible. Definition A list where each node has 2 links ¥ Left link (Hlink) ~ Contains the address of the left node Y Right link (rlink) ~ Contains the address of the right node So that both forward and backward traversal is possible is called doubly linked list 1000 2000 1500 3000 first {\ 10 J == ee = tT TT link Info rlink Dr. Mahesh G ge Dept of Se BNETT AM Each node in the list consists of ¥ link ~ Contains the address of the left node or previous node Y info Itis the data to be processed Y link ~ Contai s the address of the right node or next node The structure declaration for each node is as shown below struct node { int info; struct node *llink; struct node *rlink; 4 typedef struct node * NODE, Disadvantages of Doubly Linked List ¥ Each nod Y If anode the list requires an extra link and hence more memory is consumed inserted or deleted both Hin and rlink should be manipulated Module 3 35 Lecture Notes Data Structures and Applications [BCS304] Fundamental Operations of a Doubly Linked List Function to insert an element at the front end NODE insertfront(int item, NODE first) NODE temp; temp = (NODE) malloc(sizeof(struct node)); temp->info =item; ‘temp-llink = NULL; temp->rlink = NULL; if{first == NULL) return temp: temp->rlink = first, Dr. Mahesh G ate Dept of SE BNSTT @M return temp; } Function to insert an element at the rear end NODE insertrear(int item, NODE first) t NODE temp, cur, temp = (NODE) malloc(sizeofistruct node); ‘temp->info = item; temp->llink = NULL; temp->tlink = NULL; ifffirst == NULL) return temp; cur = first; while(cur->rlink != NULL) cur = cur->rlink. cur->rlink = temp; temp->llink = cur; return first; } Function to delete an element at the front end NODE deletefront( NODE first) i NODE cur, if(first NULL) printi(“list is empty\n”), return first; link = = NULL) printi(“item deleted is %ed\n”, first>info); free(first) return NULL; cur = first; Module 3 36 Lecture Notes } printf(“item deleted is %d\n”, cur->info); free(cur), frist->llink = NULL; return first; Function to delete an element at the rear end NODE deleterear( NODE first) { } NODE prev, cur; if(first = = NULL) { printi(“list is empty\n"); return first; } fifirst-rlink == NULL) { printf(“item deleted is %d\n”,first->info); free(first) NULL; ,— ULL; Dr. Mahesh G Professor. cur= first; Day of SE BNI M while(cur->rlink != NULL) cur = cur->rlink; prev =cur-Hlink; printf(“item deleted is %d\n”, cur->info), free(cur); prev->rlink = NULL; return first; Function to display the contents of the list void display(NODE first) { } NODE cur; if(first = = NULL) { printf("the list is empty\n") return; } printf("the contents of the list are:\n"); cur = firsts while(cur != NULL) { printf("%d\n" cur->info); cur = cur->rlinks Module 3 Data Structures and Applications [BCS304] 37 Lecture Notes Data Structures and Applications [BCS304] Other Operations of a Doubly Linked List Function to insert a new node to the left of a node whose key value is read as input NODE insert_lefi(int key, int item, NODE first) { NODE cur, prev, temp; temp=(NODE)malloe(sizeof{struct node)); temp->info = item; temp->llink = temp->rlink = NULL; first = = NULL) printf("the list is empty!cannot insert"); free(temp); return first; } if(key = = first->info) { Dr. Mahesh G temp->rlink = firsts Da of SE BNSTT 2M first->Ilink = temp; return temp; } cur = firsts while(cur != NULL && key != cur->info) cur = cur->rlink; if(cur = = NULL) { printf("the node with key value not present!cannot insert\n"); free(temp); return first; 3 prev = cur->llinks prev->rlink = temp; temp->llink = prev temp->rlink = curs cur->llink = temp; return first; Module 3 38 Lecture Notes Data Structures and Applications [BCS304] Function to delete a node whose info field is specified NODE delete_info(int item,NODE first) { NODE cur,prev,next; if(first = = NULL) { printf(“list is empty\n"); return firsts } iffitem = { first->info) cur = firsts first = first->rlink; if(first != NULL) first->llink = NULLs printf("item deleted is %d" cur->info); free(cur); return first; Dr. Mahesh G Profesor, } Dept. of CSE, BMSIT & M cur = firsts while(cur != NULL && item != cur->info) cur = cur->rlink; if(cur = = NULL) { printf(“item not found\n"); return first; } prev = cur->llink; next = cur->rlinks prev->rlink = nexts if(next |= NULL) next->llink = prevs printf("deleted item is %d",cur->info); free (cur); return firsts Module 3 39 Lecture Notes Data Structures and Applications [BCS304] Design, Develop and Implement a menu driven Program in C for the following operations on Doubly Linked List (DLL) of Employee Data with the fields: SS! Name, Dept, Designation, Sal, PhNo a, Create a DLL of N Employees Data by using end insertion. », Display the status of DILL and count the number of nodes in it c. Perform Insertion and Deletion at End of DLL 4. Perform Insertion and Deletion at Front of DLL e. Demonstrate how this DLL can be used as Double Ended Queue f. Exit #include struct node { char ssn{10}; char name[20]; char dept[20]; char desg{20]; float sal; char phno{20); struct node *link; ib typedef struct node * NODE; Function to insert at the front end NODE insert_front(char ssn{], char name[], char dept[], char desg[], float sal, char phnof], NODE first) { NODE temp; temp = (NODE) malloc(sizeof(struct node)); strepy(temp->ssn, ssn): strepy(temp->name, name); strepy(temp->dept, dept); strepy(temp->desg, desg); temp->sal = sal; strepy(temp->phno, phno); temp->llink = NULL; temp->rlink = NULL; if(first == NULL) return temp: temp->rlink = first, first->Hlink = temp, return temp; Module 3 40 Lecture Notes Data Structures and Applications [BCS304] Function to insert at the rear end NODE insert_rear(char ssn[], char name[], char dept{], char desg[], float sal, char phno[], NODE first) { NODE temp, cur; temp = (NODE) malloc(sizeofstruct node)); strepy(temp->ssn, ssn); strepy(temp->name, name); strepy(temp->dept, dept); strepy(temp->desg, desg); temp->sal = sal; strepy(temp->phno, phno); temp->llink = NULL; temp->rlink = NULL; if(first = = NULL) return temp; cur = first, while(cur->rlink != NULL) cur = cur->rlink, cur>rlink = temp, Dr. Mahesh G temp->llink = cur, return first; BMSIT & M } Function to delete at the front end NODE delete_front( NODE first) t NODE cur; first = = NULL) { printf(“list is empty\n”); return first; 3 ifffirst->rlink = = NULL) { printf(’Employee with following details is deleted\n"); printf("ssn : %s\n", first->ssn)s printf("name ; %s\n", first ->name)3 printf("dept : %s\n", first ->dept)s printf("desg : %s\n", first ->desg)s printf("sal : %fin", first ->sal); printf("phone no : %s\n', first->phno); free(first) return NULL; 3 cur = first; Module 3 4 Lecture Notes Data Structures and Applications [BCS304] 3 Function to delete at the rear end NODE delete_rear( NODE first) { first “first->rlink; printf("Employee with following details is deleted\n"); printf("ssn : %s\n", cur->ssn); printf("name ; %s\n", cur->name); printf("dept : %s\n", cur->dept); printf("desg : %s\n", cur->desg); printf("sal : %f\n", cur->sal); printf("phone no : %s\n", cur->phno); free(cur), fis k = NULL; return first; Dr. Mahesh G Professor Dept of CSE, BMSIT & M NODE prev, cur; = NULL) printf(“list is empty\n” return first; first>rlink = = NULL) t printf("Employee with following details is deleted\n"); printf("ssn : %s\n", first->ssn); printf("name ; %s\n", first ->name); printf("dept : %s\n", first >dept); printf("desg : %s\n", first ->desg)s printf("sal : %fin", first ->sal); printf("phone no : %s\n", first->phno); free(first) return NULL; bar fst while(cur->rlink != NULL) cur = cur->tlink; prev ~cur->llink; printf("Employee with following details is deleted\n"); printf("ssn : %s\n", cur->ssn); printf(’name : %s\n", cur->name); printf(“dept : %s\n", cur->dept); printf("desg : %s\n", cur->desg)s printf("sal : %f\n", cur->sal) Module 3 4a Lecture Notes Data Structures and Applications [BCS304] printf("phone no : %s\n", cur->phno); free(cur); prev->rlink = NULL; return first Function to display the contents of the list and count the number of nodes display(NODE first) NODE cur; t count = 0; first = = NULL) { printf("the list is empty\n"); printf("the number of nodes in the list is %d\n", count); returns } cur = firsts printf(’the contents of the list ares\n"); printf("ssn\t name\t deptit desgit sal\t phoneno\n"); while(cur != NULL) Dr. Mahesh G t Profesor ee Dept of OS, BST M printf("ssn : %s\n", cur->ssn); printf("name ; %s\n", cur->name); printf("dept : %s\n", cur->dept); printf("desg : %s\n", cur->desg)s printf("sal : %fin", cur->sal); printf("phone no : %s\n", cur->phno); cur = cur->rlink; } printf("the number of nodes in the list is %d\n", count) } void main() { int choice, n, is char ssn[20], name[20}, dept[20], desg[20], phno[20}; float sal; NODE first = NULL; elrser( )5 Module 3 a3 Lecture Notes Data Structures and Applications [BCS304] 1/ Creating a list of 'n' employees using end (rear) insertion printf("Enter the number of employees"); seani("%d", &n); for(i=0; iinfo = item; cur = head->rlink; head->rlink = temp, Dr. Mahesh G temp->llink = head; Professor, fain See Dept of CSE, BMSIT & M curllink = temp; return head; } Function to insert an element at the rear end NODE insertrear(int item, NODE head) { NODE temp, last; temp = (NODE) malloc(sizeof(struct node)); temp->info = last->rlink = temp; slink = head; temp; return head; Module 3 46 Lecture Notes Function to delete an element at the front end NODE deletefront(NODE head) { 3 NODE cur, next; ifhead->rlink { ead) printf(“list is empty\n”), return head; } cur = head->rlink; next = cur->tlink; -rlink = next; llink = head, printf(“element deleted is %d\n”, cur->info); free(cur); return head; Function to delete an element at the rear end NODE deleterear(NODE head) t } NODE cur, last; iff head->rlink = = head) { printf(“list is empty\n”), return head; } Dr. Mahesh G cur = head->llink; Professor, last = cur->llink; Dept of CSE, BMSIT & MC last->rlink = head; head-Ilink = last; printi(“element deleted is %odin”, cur->info); free(cur); return head; Function to display the contents of the list void display(NODE head) { NODE cur; if(head->rlink = = head) { printf("the list is empty\n"); return; } printf("the contents of the list are:\n"); cur = head->rlinks Module 3 Data Structures and Applications [BCS304] 47 Lecture Notes Data Structures and Applications [BCS304] while(cur != head) { printf("%d\n",cur->info); cur = cur->rlinks Note: Updating head->info is optional. // Main function for circular doubly linked lists with header node void main( ) { int choice, item; NODE head; head = (NODE) malloc(sizeof(struct node)); head->Ilink = head->rlink=head; elrser(); for(33) { printf("\nl:insert-front\n 2:insert-rear\n "); printf("\n3:delete-front\n 4:delete-rear\n "); printf("\nS:display\n 6:exit\n ")s printf("enter your choice"); seanf("%d",& choice); switeh(choice) { case 1: printf("enter the item to be inserted\n"); seanf("%d" item); head = insert_front(item, head); break; case 2: printf("enter the item to be inserted\n"); scanf("%d",&item); head = insert_rear(item, head); break; case 3: head = delete_front(head); break; case 4: head = delete_rear(head); break; case 5: display(head)s break; default : exit(0); } getch( ): } Module 3 48 Lecture Notes Data Structures and Applications [BCS304] Sparse Matrix Representation using linked lists 1s 0 0 2015 013 000 000 600 . Consider the sparse matrix, . the link list representation of this is 000000 910 0 0 0 0 0 2% 000 as shown below. + ‘ ’ y colhead{0} | cothead{t] | cothead[2]| cothead{3} | cofhead|4]] cothead[5] v X v X v v rowlfead[0] _¥ ¥ 15[0]0 22 [0|3 ols 1 > rowMead[1] fio] Bo 1 >, > rowhead|2] + -6 [2[3 1 > ro#head[3] Dr. Mahesh G YT t+4 Profesor, Dept of OE, BATT M rowhead|4] _¥ x1] 40 1 > rowhead|5]} 1 Module 3 49 Lecture Notes Data Structures and Applications [BCS304] Sparse Matrix Using Linked Lists (E) #include struct node { int value; int row; int col; struct node *rlink; struct node “dlink; aH typedef struct node* NODE; void insert_matrix(NODE rowhead[ ], NODE colheadf J, int value, int row, int col) { NODE temp, cur, prev, head; temp = (NODE)malloe(sizeof(struct node)); temp->value = value; temp->row = row; temp->col = col; //Tnsert into appropriate column head = rowhead[row/; prev = head; cur = head->rlink; while(cur!=head && cur->col < col) { prev = cur, cur = cur->rlink; 3 Dr. Mahesh G prev->rlink = temp; Professor. femp->ilink = cur, Dept of CSE, BMSIT & M (/ Insert into appropriate row head = colhead{col]; prev = head; cur = head->dlink; while(cur!=head && cur->row dlink; } prev->dlink = temp; temp->dlink = cur; Module 3 50 Lecture Notes Data Structures and Applications [BCS304] void read_matrix(NODE rowhead[ ], NODE colheadf J, int m, int n) { int value, i, j; printf("\n\nEnter the elements of the matrix"); for(i-0:irlink; while(cur != head) t printi("(%d, %d) = %d\n”, cur->row, cur->col, cur->value), cur = cur>rlink 3 } 3 void search(int key, NODE rowhead{ J,int m) { inti, NODE head, cur; for(i=0; irlink, while(cur != head) t if(key = cur>value) { printf(“Successful Search\n”); printi(* Element found at row %d and column %d\n”), cur->row, cur->col); return; } cur = cur->tlink; } 3 Module 3 51 Lecture Notes } printi( Unsuccessful Search Element not Found\n”), void main( ) t intm,n NODE rowhead[20], colhead[20], temp, printi("Enter the number of rows"); scanft"%d" &m), printi("Enter the number of columns"); scanf{"%d" &n); // Initialize row headers for(i=0; irlink = temp; temp-dlink = NULL rowheadfi] = temp; Dr. Mahesh G Professor, Dept of CSE, BMSIT A ME } //Mnitialize column headers for(i=0; irlink = NULL; temp-dlink = temp; cotheadfi] = temp; } // Read the matrix elements read_matrix(rowhead, colhead, m, n); (/ Print the matrix display(rowhead, m); 1 Read the key element to be searched printi("Enter the element to be searched \n"); scanft"%d" &key), / Search for the key in the matrix search(key, rowhead, m); getch( ); Module 3 Data Structures and Applications [BCS304] 52 Lecture Notes Data Structures and Applications [BCS304] Polynomial — Using Singly Linked List Representation Consider the polynomial 9x* + 7x? + 6x + 9. This polynomial can be represented using a singly linked list as shown below First. [9 3 +7 [2 6 [1 +9 [ols t t Cooefficient Power of x Every node has 3 fields Y cf coefficient field Y px —power of x ¥ link —contains the address of next node. Therefore, the structure declaration to represent this node will be struct node { int cf, int px; struct node “link; BB typedef struct node* NODE; Program to add two Polynomials using Singly #include // Function to display the polynomial void display(NODE first) { NODE cur; if(first = = NULL) { printf("Polynomial does not exist\n"); return; } cur = firsts while(cur != NULL) { if(cur>cf> 0) printf("+"); printf("%d x’ %d",cur->cf, cur->px); cur = cur->link; } } Module 3 53 Lecture Notes Data Structures and Applications [BCS304] // Function to insert an element at the rear end NODE insert_rear(int ef, int px, NODE first) { NODE temp, curs temp=(NODE)malloc(sizeof(struct node)); temp->ef = ef temp->px = px; temp->link ULL; if(first = =NULL) //no node { } return temp; cur = first; J node exists while(cur->link != NULL) { } cur = cur->link; cur->link = temps return firsts } 1/ Function to read a polynomial NODE readpoly(NODE first) { ef, px; “Enter the number of terms \n”); %d", &n);, for(i = 1; i<-n; i++) { printf(“Enter the coefficient and power of x of %d term\ scanft“%d%d” ef, &px); first = insert_rear(ef, px, first), } return first; } // Function to compare 2 numbers int compare(int x, int y) { ifxpx, p2->px )) case 0: // pl’s exponent = p2’s exponent sumef = pl->cf + p2>ef, if(sumef = 0) 3 = insert_rear(sumef, p1->px, p3); pl =pl->link; p2 =p2->link break: ‘case 1: //pl’s exponent > p2’s exponent p3 = insert_rear(p1->ef, p1->px, p3): pl =pl-link break: ‘case -1: // pls exponent < p2’s exponent p3 = insert_rear(p2->ef, p2->px, p3) p2 = p2->link; break: 3 ) ; Dept. of CSF, BMSIT& M 1/ Add remaining terms of Polynomial 1 while(pl != NULL) p3 = insert_rear(p!-ef, pl->px, p3) pl =pl>link i 11 dd remaining terms of Polynomial 2 while(p2 != NULL) p3 = insert_rear(p2->ef, p2->px, p3): p2 ink; return p3 3 void main( ) { NODE p! = NULL, p2 = NULL, p3 = NULL; printi(“enter the first polynomial\n”); pl =readpoly(p1), Module 3 38 Lecture Notes Data Structures and Applications [BCS304] printi(“enter the second polynomial\n”); p2=readpoly(p2); p3 = addpoly(p1, p2, p3) printi(“The first polynomial is\n”); display(p1); printf(“The second polynomial is\n”); display(p2), Dr. Mahesh G Professor, printi(Their sum is\n”); Dept of CSE, BMS & M display(p3); Polynomial — Using Circular Singly Linked List with header node Representation Consider the polynomial 9x° + 7x? + 6x + 9. This polynomial can be represented using a circular singly linked list with header node as shown below. head +9 3 ae) 6 [1 +9 [0 1 1 Cooefficient Power of x Note: link field of last node contains the address of head and link field of header node points to the first node of the list. Every node has 3 fields ¥ of — coefficient field Y. px power of x ¥ link —contains the address of next node. Therefore, the structure declaration to represent this node will be struct node fi int cf; int px; struct node *link; 8 typedef struct node* NODE; Program to add two Polynomials using Circular Singly Linked List header node #include // Funetion to display the polynomial Module 3 56 Lecture Notes Data Structures and Applications [BCS304] void display(NODE head) { NODE cur; iff head->link = = head) { printf(’Polynomial does not exist\n return; } cur =head=links while(cur != head) { if(cur->cf> 0) printf("+"); printf("%d x” %d” ;cur->ef, cur->px)s cur = cur->link; } Dr. Mahesh G } Professor, Dept of OSE BNSTT eM // Function to insert an element at the rear end NODE insert_rear(int ef, int px, NODE head) { NODE temp, cur; temp=(NODE)malloe(sizeof(struct node)); temp->cf = cfj temp->px = px3 temp->link = NULL; cur = head->links while(cur->link != head) { } cur->link = temp; temp->link = heads return head; cur = cur->link; } / Function to read a polynomial NODE readpoly(NODE head) { 1, i, cf, px; printf(“Enter the number of terms \n”), scanf(“%d", &n), for(i = 1; i<=n; i++) Module 3 Lecture Notes Data Structures and Applications [BCS304] { printi(“Enter the coefficient and power of x of %d term\n”,i); scanft“%d%d” def, &px); head = insert_rear(ef, px, head); } return head; } // Function to compare 2 numbers int compare(int x, int y) t ifxlink: ee p2=h2->link: Dent of (SE BNST& M int sumef, while(pl != hl & p2 !=h2) t switeh( compare(pl>px, p2>px)) case 0 :// p1"s exponent = p2°s exponent sumef = pl->of + p2->ef. if{sumef = 0) h3 = insert_rear(sumef, p1->px, h3); pl=pl-link; case 1: /I_pl’s exponent > p2’s exponent h3 = insert_rear(p|ef. pl->ps, h3); 1->link; case -1: /! pl’s exponent ps, h3), p2=p2>link; break: 3 // Add remaining terms of Polynomial 1 while(pl = hl) Module 3 58 Lecture Notes Data Structures and Applications [BCS304] h3 = insert_rear(p1->ef, p1->px, h3); 1 = pltink. } 1) Add remaining terms of Polynomial 2 while(p2 != h2) h3 = insert_rear(p2->ef. p2->px. h3): p2=p2->link return h3; 3 void main( ) { NODE hl, h2, h3; hi = (NODE)malloc(sizeof{struct node)); h2 = (NODE)malloc(sizeof(struct node)); h3 = (NODE)malloc(sizeof{struct node)); hi-link = hl; h2->link = h2; h3>link = h3; printi(“enter the first polynomial\n”); hl =readpoly(hl); printi(“enter the second polynomial\n”); h2 = readpoly(h2), h3 = addpoly(hl, h2, h3) printf(‘“The first polynomial is\n”), display(hl); printf(‘“The second polynomial is\n”); display(h2); printf(“Their sum is\n”); display(h3); Module 3 59 Lecture Notes Data Structures and Applications [BCS304] Miscellaneous Functions Write a as lists L1 and L2. This function should return ‘0” if L! >L2. int strempl(NODE L1, NODE L2) { NODE C1, C2; C1=LI; C2=12; while( C1 != NULL && C2 { NULL) if(C1->info > C2->info) return 1 else if(C1>info < C2->info) return -1; else { C1=Cl->tink; Dr. Mahesh G Professor, C2=C: ink; Dept of B 3 } if(C1 = NULL && C2 != NULL) return -1; if(C2 = NULL && C1 |= NULL) return 1; return 0: } function called strempl(L1, L2) to compare 2 character strings represented 12, -1 if Lt info != last-> { printf(“string is not a palindrome\n”); return; 3 cur = cur->tlink last = last->llink, 3 printf(“string is a palindrome\n”); } Module 3 60 Lecture Notes Data Structures and Applications [BCS304] Write a ‘C’ function search(P, x) that accepts a pointer ‘P* to the list of integers and an integer ‘x’ and returns a pointer to a node containing ‘x’ if it exists and NULL otherwise. NODE search(NODE P, int x) { } NODE cur; cur=P; while(cur != NULL && x != cur->info) cur=cur-link; return cur, Write a ‘C’ function srehinst(P, x) that adds ‘x’ to P if it is not found and always returns a pointer containing ‘x’. NODE stchinst(NODE P, int x) { } NODE cur, temp, prev; cur prev = NULL; while(cur != NULL && x != eur->info) t prev =cur, cur=cur-link; 3 if{cur!= NULL) peMahesh return cur, Dap of 1. DUSTTA M else { temp = (NODE)malloc(sizeof(struct node)); temp-info = x. temp-> link ~ NULL iffprev--NULL) i P-temp; return temp: i prev=>link-temp; return temp 3 Note: Instead of | temp->link = NULL; if(prev--NULL) { P=temp; return temp; } prev->link-temp; we can write only temp->link = Ps Module 3 61 Lecture Notes Data Structures and Applications [BCS304] Write a ‘C’ function rotate which accepts the header pointer to a circular doubly linked list and ‘n’ a integer value to rotate the elements to the left ‘n’ times. NODE rotate_lefi(int n, NODE head) { NODE cur, prev. inti; for(i=0; irlink; while(cur!=head) H prev->info = cur->info; prev = cur, cur = cur->rlink, } prev->info = cur->info; } return head; 3 Wi a‘C’ function to find the mi um node in a singly linked NODE minimum(NODE first) { NODE min, cur; ia, Dr. Mahesh G Professor, printi(“list is empty\n"); Dept of (SE, BAISIT & ML return NULL; 3 min=first; curfirst-link, while(cur!=NULL) { if(min->info > prev->info) min=cur cur = cur->link; } else cur=cur->link; } return min; Module 3 62

Vous aimerez peut-être aussi