![]() |
![]() |
![]() |
![]() |
2 |
ABSTRACT DATA TYPE In programming each program is breakdown into modules, so that no routine should ever exceed a page. Each module is a logical unit and does a specific job modules which inturn will call another module. Modularity has several advantages 1. Modules can be compiled separately which makes debugging process easier. 2. Several modules can be implemented and executed simultaneously. 3. Modules can be easily enhanced. Abstract Data type is an extension of modular design. An abstract data type is a set of operations such as Union, Intersection, Complement, Find etc., The basic idea of implementing ADT is that the operations are written once in program and can be called by any part of the program. 2.1 THE LIST ADT List is an ordered set of elements. The general form of the list is A1, A2, A3, ..... ,AN A1 - First element of the list AN - Last element of the list N - Size of the list If the element at position i is Ai then its successor is Ai+1 and its predecessor is Ai-1. Various operations performed on List 1. Insert (X, 5) - Insert the element X after the position 5. 2. Delete (X) - The element X is deleted 3. Find (X) - Returns the position of X. 4. Next (i) - Returns the position of its successor element i+1. 5. Previous (i) - Returns the position of its predecessor i-1. 6. Print list - Contents of the list is displayed. 7. Makeempty - Makes the list empty. 2.1 .1 Implementation of List ADT 1. Array Implementation 2. Linked List Implementation 3. Cursor Implementation. | ||
| |||
Data Structures 2.1 | |||
![]() |
![]() |
![]() |
Array Implementation of List Array is a collection of specific number of data stored in a consecutive memory locations. * Insertion and Deletion operation are expensive as it requires more data movement * Find and Printlist operations takes constant time. * Even if the array is dynamically allocated, an estimate of the maximum size of the list is required which considerably wastes the memory space.
Linked List Implementation Linked list consists of series of nodes. Each node contains the element and a pointer to its successor node. The pointer of the last node points to NULL.
Insertion and deletion operations are easily performed using linked list. Types of Linked List 1. Singly Linked List 2. Doubly Linked List 3. Circular Linked List. 2.1.2 Singly Linked List A singly linked list is a linked list in which each node contains only one link field pointing to the next node in the list.
Fig. 2.1 LINKED LIST
Data Structures 2.2 | ||
![]() |
![]() |
![]() |
Fig. 2.1 LINKED LIST WITH A HEADER DECLARATION FOR LINKED LIST Struct node ; typedef struct Node *List ; typedef struct Node *Position ; int IsLast (List L) ; int IsEmpty (List L) ; position Find(int X, List L) ; void Delete(int X, List L) ; position FindPrevious(int X, List L) ; position FindNext(int X, List L) ; void Insert(int X, List L, Position P) ; void DeleteList(List L) ; Struct Node { int element ; position Next ; }; ROUTINE TO INSERT AN ELEMENT IN THE LIST void Insert (int X, List L, Position P) /* Insert after the position P*/ {
position Newnode; Newnode = malloc (size of (Struct Node));
Data Structures 2.3 | ||
| ||
![]() |
![]() |
![]() |
|||
|
P |
| |||
|
| ||||
|
Data Structures 2.4 |
If (Newnode! = NULL) { Newnode Newnode P } }
INSERT (25, P, L)
ROUTINE TO CHECK WHETHER THE LIST IS EMPTY int IsEmpty (List L) /*Returns 1 if L is empty */ { if (L return (1); }
ROUTINE TO CHECK WHETHER THE CURRENT POSITION IS LAST int IsLast (position P, List L) /* Returns 1 is P is the last position in L */ { if (P return (1);
P
Data Structures 2.4 |
![]() |
![]() |
![]() |
}
FIND ROUTINE position Find (int X, List L) { /*Returns the position of X in L; NULL if X is not found */ position P; P = L while (P! = NULL && P P = P return P; }
}
FIND PREVIOUS ROUTINE position FindPrevious (int X, List L) { /* Returns the position of the predecessor */ position P; P = L; while (P P = P return P; }
| ||
| ||
Data Structures 2.5 | ||
![]() |
![]() |
![]() |
||
|
| |||
|
| |||
|
Data Structures 2.6 |
FINDNEXT ROUTINE position FindNext (int X, List L) { /*Returns the position of its successor */ P = L while (P P = P return P }
ROUTINE TO DELETE AN ELEMENT FROM THE LIST void Delete(int X, List L) { /* Delete the first occurence of X from the List */ position P, Temp; P = Findprevious (X,L); If (!IsLast(P,L)) { Temp = P P Free (Temp); } }
Data Structures 2.6 |
![]() |
![]() |
![]() |
||
|
| |||
| ||||
ROUTINE TO DELETE THE LIST
void DeleteList (List L) { position P, Temp; P = L L while (P! = NULL) { Temp = P free (P); P = Temp; } }
Data Structures 2.7 | ||||
![]() |
![]() |
![]() |
||
|
| |||
Temp, P = NULL
2.1.3 Doubly Linked List A Doubly linked list is a linked list in which each node has three fields namely data field, forward link (FLINK) and Backward Link (BLINK). FLINK points to the successor node in the list whereas BLINK points to the predecessor node.
Fig. 2.1.3 (a) NODE IN DOUBLY LINKED LIST
Fig. 2.1.3 (b) DOUBLY LINKED LIST
STRUCTURE DECLARATION : - Struct Node { int Element; Struct Node *FLINK; Struct Node *BLINK };
Data Structures 2.8 | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
ROUTINE TO INSERT AN ELEMENT IN A DOUBLY LINKED LIST void Insert (int X, list L, position P) { Struct Node * Newnode; Newnode = malloc (size of (Struct Node)); If (Newnode ! = NULL) { Newnode Newnode P P Newnode } }
P | ||||
Newnode | ||||
| ||||
Data Structures 2.9 | ||||
![]() |
![]() |
![]() |
ROUTINE TO DELETE AN ELEMENT void Delete (int X, List L) { position P; P = Find (X, L); If ( IsLast (P, L)) { Temp = P; P free (Temp); } else { Temp = P; P P free (Temp); } }
Advantage * Deletion operation is easier. * Finding the predecessor & Successor of a node is easier. Disadvantage * More Memory Space is required since it has two pointers.
| ||
| ||
Data Structures 2.10 | ||
![]() |
![]() |
![]() |
2.1.4 Circular Linked List In circular linked list the pointer of the last node points to the first node. Circular linked list can be implemented as Singly linked list and Doubly linked list with or without headers. Singly Linked Circular List A singly linked circular list is a linked list in which the last node of the list points to the first node.
Fig. 2.1.4 Singly Linked Circular List With Header
Doubly Linked Circular List A doubly linked circular list is a Doubly linked list in which the forward link of the last node points to the first node and backward link of the first node points to the last node of the list.
Fig. 2.1.4 (b) Doubly Linked Circular List With Header Advantages of Circular Linked List It allows to traverse the list starting at any point. It allows quick access to the first and last records. Circularly doubly linked list allows to traverse the list in either direction.
| ||
| ||
Data Structures 2.11 | ||
![]() |
![]() |
![]() |
2.1.5 Applications of Linked List 1. Polynomial ADT 2. Radix Sort 3. Multilist Polynomial ADT We can perform the polynomial manipulations such as addition, subtraction and differentiation etc. DECLARATION FOR LINKED LIST IMPLEMENTATION OF POLYNOMIAL ADT Struct poly { int coeff ; int power; Struct poly *Next; }*list 1, *list 2, *list 3; CREATION OF THE POLYNOMIAL poly create (poly *head1, poly *newnode1) { poly *ptr; if (head1= =NULL) { head1 = newnode1; return (head1); } else { ptr = head1; while (ptr ptr = ptr ptr } return (head1); } | ||
| ||
Data Structures 2.12 | ||
![]() |
![]() |
![]() |
ADDITION OF TWO POLYNOMIALS void add ( ) { poly *ptr1, *ptr2, *newnode; ptr1 = list1; ptr2 = list2; while (ptr1! = NULL && ptr2! = NULL) { newnode = malloc (sizeof (Struct poly)); if (ptr1 { newnode newnode newnode list 3 = create (list3, newnode); ptr1 = ptr1 ptr2 = ptr2 } else { if (ptr1 { newnode newnode newnode list3 = create (list3, newnode); ptr1 = ptr1 }
| ||
| ||
Data Structures 2.13 | ||
![]() |
![]() |
![]() |
else { newnode newnode newnode list3 = create (list3, newnode); ptr2 = ptr2 } } } SUBTRACTION OF TWO POLYNOMIAL void sub ( ) { poly *ptr1, *ptr2, *newnode; ptr1 = list1 ; ptr2 = list 2; while (ptr1! = NULL && ptr2! = NULL) { newnode = malloc (sizeof (Struct poly)); if (ptr1 { newnode newnode newnode list3 = create (list 3, newnode); ptr1 = ptr1 ptr2 = ptr2 } else {
| ||
| ||
Data Structures 2.14 | ||
![]() |
![]() |
![]() |
if (ptr1 { newnode newnode newnode list 3 = create (list 3, newnode); ptr1 = ptr1 } else { newnode newnode newnode list 3 = create (list 3, newnode); ptr2 = ptr2 } } } } POLYNOMIAL DIFFERENTIATION void diff ( ) { poly *ptr1, *newnode; ptr1 = list 1; while (ptr1 ! = NULL) { newnode = malloc (sizeof (Struct poly)); newnode newnode newnode list 3 = create (list 3, newnode); ptr1 = ptr1 } } | ||
| ||
Data Structures 2.15 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
|||||
| |||||||||
| |||||||||
|
|
Data Structures 2.16 |
Radix Sort : - (Or) Card Sort Radix Sort is the generalised form of Bucket sort. It can be performed using buckets from 0 to 9. In First Pass, all the elements are sorted according to the least significant bit. In second pass, the numbers are arranged according to the next least significant bit and so on this process is repeated until it reaches the most significant bits of all numbers. The numbers of passes in a Radix Sort depends upon the number of digits in the numbers given. PASS 1 : INPUT : 25, 256, 80, 10, 8, 15, 174, 187
Buckets After Pass 1 : 80, 10, 174, 25, 15, 256, 187, 8 PASS 2 : INPUT : 80, 10, 174, 25, 15, 256, 187, 8
After Pass 2 : 8, 10, 15, 25, 256, 174, 80, 187 PASS 3 : INPUT : 8, 10, 15, 25, 256, 174, 80, 187
After pass 3 : 8, 10, 15, 25, 80, 175, 187, 256
Data Structures 2.16 |
![]() |
![]() |
![]() |
Maximum number of digits in the given list is 3. Therefore the number of passes required to sort the list of elements is 3. Multi Lists More complicated application of linked list is multilist. It is useful to maintain student registration, Employee involved in different projects etc., Multilist saves space but takes more time to implement.
Fig. 2.1.5 Multilist Implementation For Employee Project Allocation An employee can involve in any number of projects and each project can be implemented by any number of employees. Employee E1 is working on project P1, E2 is working on project P2 & E3 is working on project P1. Project P1 is implemented by the Employees E1 & E3. Project P2 is implemented by the Employee E2. 2.1.6 Cursor Implementation of Linked Lists Cursor implementation is very useful where linked list concept has to be implemented without using pointers. Comparison on Pointer Implementation and Curson Implementation of Linked List. Pointer Implementation Cursor Implementation 1. Data are stored in a collection of structures. Data are stored in a global array of Each structure contains a data and next structures. Here array index is pointer. considered as an address.
| ||
| ||
Data Structures 2.17 | ||
![]() |
![]() |
![]() |
Pointer Implementation Cursor Implementation 2. Malloc function is used to create a node and It maintains a list of free cells called free function is used to released the cell. cursors space in which slot 0 is considered as a header and Next is equivalent to the pointer which points to the next slot. Slot Element Next 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 Fig. 2.1.6 Initialized Cursorspace Declaration typedef int ptrtoNode; typedef ptrtoNode position; void Initialize cursorspace (void); int IsEmpty (List L); int IsLast (position P, List L); position Find (int X, List L); void Delete (int X, List L); void Insert (int X, List L, position P); Struct Node { int Element; | ||
| ||
Data Structures 2.18 | ||
![]() |
![]() |
![]() |
position Next; }; Struct Node Cursorspace [space size]; ROUTINE FOR CURSOR ALLOC & CURSOR FREE Static position CursorAlloc (void) { position P; P = CursorSpace [0].Next; CursorSpace [0].Next = CursorSpace [P].Next; return P; } Static void CursorFree (position P) { CursorSpace [P].Next = CursorSpace [0].Next; CursorSpace [0].Next = P; } ROUTINE TO CHECK WHETHER THE LIST IS EMPTY int IsEmpty (List L) { /* Returns 1 if the list is Empty */. if (Cursorspace [0]. Next = = 0) return (1); } ROUTINE FOR ISLAST int IsLast (Position P, List L) { /* Returns 1 if the p is in last position */ if (CursorSpace [P].Next = = 0) return (1); } | ||
| ||
Data Structures 2.19 | ||
![]() |
![]() |
![]() |
ROUTINE TO FIND AN ELEMENT position Find (int X, List L) { position P; P = CursorSpace [L].Next; while (P && CursorSpace [P].Element ! = X) P = CursorSpace [P].Next; return P; } ROUTINE TO DELETE AN ELEMENT void Delete (int X, List L) { position P, temp; P = Findprevious (X, L); if (! IsLast (P, L)) { temp = CursorSpace [P].Next; CursorSpace [P].Next = CursorSpace [temp].Next; CursorFree (temp); } } ROUTINE FOR INSERTION void Insert (int X, List L, position P) { position newnode; newnode = CursorAlloc ( ); if (newnode ! = 0) CursorSpace [newnode].Element = X; CursorSpace [newnode]. Next = CursorSpace [P].Next; CursorSpace [P].Next = newnode; } | ||
| ||
Data Structures 2.20 | ||
![]() |
![]() |
![]() |
Example of a Cursor Implementation of Linked List Slot Element Next 0 - 8 1 B 0 The List X has A, B and 2 header X 4 list Y has C, D 3 C 6 4 A 1 5 header Y 3 6 D 0 7 - 0 8 - 7 Fig. 2.1.6 (a) 2.2 THE STACK ADT 2.2.1 Stack Model : A stack is a linear data structure which follows Last In First Out (LIFO) principle, in which both insertion and deletion occur at only one end of the list called the Top.
Fig. 2.2 Stack Model Example : - Pile of coins., a stack of trays in cafeteria. 2.2.2 Operations On Stack The fundamental operations performed on a stack are 1. Push 2. Pop | ||
| ||
Data Structures 2.21 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
|||
|
| ||||||
| |||||||
|
Data Structures 2.22 |
Fig. 2.2.2 Operations on stack PUSH : The process of inserting a new element to the top of the stack. For every push operation the top is incremented by 1.
Fig. 2.2.2(a) Push Operation POP : The process of deleting an element from the top of stack is called pop operation. After every pop operation the top pointer is decremented by 1.
Fig.2.2.2(b) Pop operation EXCEPTIONAL CONDITIONS OverFlow Attempt to insert an element when the stack is full is said to be overflow. UnderFlow Attempt to delete an element, when the stack is empty is said to be underflow.
Data Structures 2.22 |
![]() |
![]() |
![]() |
2.2.3 Implementation of Stack Stack can be implemented using arrays and pointers. Array Implementation In this implementation each stack is associated with a pop pointer, which is -1 for an empty stack. To push an element X onto the stack, Top Pointer is incremented and then set Stack [Top] = X. To pop an element, the stack [Top] value is returned and the top pointer is decremented. pop on an empty stack or push on a full stack will exceed the array bounds. ROUTINE TO PUSH AN ELEMENT ONTO A STACK void push (int x, Stack S) { if (IsFull (S)) Error ("Full Stack"); else { Top = Top + 1; S[Top] = X; } } int IsFull (Stack S) { if (Top = = Arraysize) return (1); } ROUTINE TO POP AN ELEMENT FROM THE STACK void pop (Stack S) { if (IsEmpty (S)) Error ("Empty Stack"); else { X = S [Top]; Top = Top - 1; | ||
| ||
Data Structures 2.23 | ||
![]() |
![]() |
![]() |
} } int IsEmpty (Stack S) { if (S return (1); } ROUTINE TO RETURN TOP ELEMENT OF THE STACK int TopElement (Stack S) { if (! IsEmpty (s)) return S[Top]; else Error ("Empty Stack"); return 0; } LINKED LIST IMPLEMENTATION OF STACK Push operation is performed by inserting an element at the front of the list. Pop operation is performed by deleting at the front of the list. Top operation returns the element at the front of the list.
Fig. 2.2.3 Stack ADT
Fig. 2.2.3(b) Linked List Implementation of Stack ADT 20
| ||
| ||
Data Structures 2.24 | ||
![]() |
![]() |
![]() |
DECLARATION FOR LINKED LIST IMPLEMENTATION Struct Node; typedef Struct Node *Stack; int IsEmpty (Stack S); Stack CreateStack (void); void MakeEmpty (Stack S); void push (int X, Stack S); int Top (Stack S); void pop (Stack S); Struct Node { int Element ; Struct Node *Next; }; ROUTINE TO CHECK WHETHER THE STACK IS EMPTY int IsEmpty (Stack S) { if (S return (1); } ROUTINE TO CREATE AN EMPTY STACK Stack CreateStack ( ) { Stack S; S = malloc (Sizeof (Struct Node)); if (S = = NULL) Error (" Outof Space"); MakeEmpty (s); return S; } void MakeEmpty (Stack S) | ||
| ||
Data Structures 2.25 | ||
![]() |
![]() |
![]() |
{ if (S = = NULL) Error (" Create Stack First"); else while (! IsEmpty (s)) pop (s); } ROUTINE TO PUSH AN ELEMENT ONTO A STACK void push (int X, Stack S) { Struct Node * Tempcell; Tempcell = malloc (sizeof (Struct Node)); If (Tempcell = = NULL) Error ("Out of Space"); else { Tempcell Tempcell S } } ROUTINE TO RETURN TOP ELEMENT IN A STACK int Top (Stack S) { If (! IsEmpty (s)) return S Error ("Empty Stack"); return 0; } | ||
| ||
Data Structures 2.26 | ||
![]() |
![]() |
![]() |
ROUTINE TO POP FROM A STACK void pop (Stack S) { Struct Node *Tempcell; If (IsEmpty (S)) Error ("Empty Stack"); else { Tempcell = S S Free (Tempcell); } } 2.2.4 APPLICATIONS OF STACK Some of the applications of stack are : (i) Evaluating arithmetic expression (ii) Balancing the symbols (iii) Towers of Hannoi (iv) Function Calls. (v) 8 Queen Problem. Different Types of Notations To Represent Arithmetic Expression There are 3 different ways of representing the algebraic expression. They are * INFIX NOTATION * POSTFIX NOTATION * PREFIX NOTATION INFIX In Infix notation, The arithmetic operator appears between the two operands to which it is being applied. For example : - A / B + C | ||
| ||
Data Structures 2.27 | ||
![]() |
![]() |
![]() |
POSTFIX The arithmetic operator appears directly after the two operands to which it applies. Also called reverse polish notation. ((A/B) + C) For example : - AB / C + PREFIX The arithmetic operator is placed before the two operands to which it applies. Also called as polish notation. ((A/B) + C) For example : - +/ABC INFIX PREFIX (or) POLISH POSTFIX (or) REVERSE POLISH 1. (A + B) / (C - D) /+AB - CD AB + CD - / 2. A + B*(C - D) +A*B - CD ABCD - * + 3. X * A / B - D - / * XABD X A*B/D- 4. X + Y * (A - B) / +X/*Y - AB - CD XYAB - *CD - / + (C - D) 5. A * B/C + D + / * ABCD AB * C / D + 1. Evaluating Arithmetic Expression To evaluate an arithmetic expressions, first convert the given infix expression to postfix expression and then evaluate the postfix expression using stack. Infix to Postfix Conversion Read the infix expression one character at a time until it encounters the delimiter. "#" Step 1 : If the character is an operand, place it on to the output. Step 2 : If the character is an operator, push it onto the stack. If the stack operator has a higher or equal priority than input operator then pop that operator from the stack and place it onto the output. Step 3 : If the character is a left paraenthesis, push it onto the stack. Step 4 : If the character is a right paraenthesis, pop all the operators from the stack till it encounters left parenthesis, discard both the parenthesis in the output. | ||
| ||
Data Structures 2.28 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
Infix Expression : A * B + ( C - D / E) # Read Character Stack Output | ||||
| ||||
| ||||
Data Structures 2.29 | ||||
![]() |
![]() |
![]() |
Read Character Stack Output
Fig. 2.2.4 (a) Conversion of Infix Expression to Postfix Expression
| ||
| ||
Data Structures 2.30 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Evaluating Postfix Expression Read the postfix expression one character at a time until it encounters the delimiter `#'. Step 1 : - If the character is an operand, push its associated value onto the stack. Step 2 : - If the character is an operator, POP two values from the stack, apply the operator to them and push the result onto the stack. Example : Let us consider the symbols A, B, C, D, E had the associated values : Symbol Value A 4 B 5 C 5 D 8 E 2 Read Character Stack Read Character Stack | ||||||||
(i) (ii) (iv) (iii) | ||||||||
(v) | ||||||||
(vi) | ||||||||
| ||||||||
Data Structures 2.31 | ||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||||||
|
(vii) |
(viii) |
(xi) |
Fig. 2.2.4 (b) Evaluation of AB*CDE / - + 2. BALANCING THE SYMBOLS Read one character at a time until it encounters the delimiter `#'. Step 1 : - If the character is an opening symbol, push it onto the stack. Step 2 : - If the character is a closing symbol, and if the stack is empty report an error as missing opening symbol. Step 3 : - If it is a closing symbol and if it has corresponding opening symbol in the stack, POP it from the stack. Otherwise, report an error as mismatched symbols. Step 4 : - At the end of file, if the stack is not empty, report an error as Missing closing symbol. Otherwise, report as Balanced symbols. Let us consider the expression as (a + b) # Read Character Stack Read character Stack
Fig. 2.2.4 (c) Illustration for Balanced Symbols
(vii) (viii) (xi) |
(i) (ii) (iv) (iii) (v) | |||||||
(vi) | ||||||||||||
| ||||||||||||
Data Structures 2.32 | ||||||||||||
![]() |
![]() |
![]() |
![]() |
|
Consider the expression ((a + b) # : - Read Character Stack Read Character Stack
Fig. 2.2.4 (d) Illustration For Unbalanced Symbols Towers of Hanoi Towers of Hanoi is one of the example illustrating the Recursion technique. The problem is moving a collection of N disks of decreasing size from one pillar to another pillar. The movement of the disk is restricted by the following rules. Rule 1 : Only one disk could be moved at a time. Rule 2 : No larger disk could ever reside on a pillar on top of a smaller disk. Rule 3 : A 3rd pillar could be used as an intermediate to store one or more disks, while they were being moved from source to destination.
(i) (ii) (iii) (iv) (vi) (v) (vii) | ||||
| ||||
Data Structures 2.33 | ||||
![]() |
![]() |
![]() |
Fig. 2.2.4 (e) Towers of Hanoi problems Recursive Solution N - represents the number of disks. Step 1. If N = 1, move the disk from A to C. Step 2. If N = 2, move the 1st disk from A to B. Then move the 2nd disk from A to C, The move the 1st disk from B to C. Step 3. If N = 3, Repeat the step (2) to more the first 2 disks from A to B using C as intermediate. Then the 3rd disk is moved from A to C. Then repeat the step (2) to move 2 disks from B to C using A as intermediate. In general, to move N disks. Apply the recursive technique to move N - 1 disks from A to B using C as an intermediate. Then move the Nth disk from A to C. Then again apply the recursive technique to move N - 1 disks from B to C using A as an intermediate. RECURSIVE ROUTINE FOR TOWERS OF HANOI void hanoi (int n, char s, char d, char i) { /* n if (n = = 1) { print (s, d); return;
| ||
| ||
Data Structures 2.34 | ||
![]() |
![]() |
![]() |
} else { hanoi (n - 1, s, i, d); print (s, d) hanoi (n-1, i, d, s); return; } } Source Pillar Intermediate Pillar Destination Pillar
(i) (ii) (iii) | ||
| ||
Data Structures 2.35 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Source Pillar Intermediate Pillar Destination Pillar | |||||||||
| |||||||||
(iv) | |||||||||
(v) | |||||||||
(vi) | |||||||||
(vii) | |||||||||
(viii) | |||||||||
Fig. 2.2.4 (f) Towers of Hanoi Problem for 3 Disks | |||||||||
| |||||||||
Data Structures 2.36 | |||||||||
![]() |
![]() |
![]() |
4. Function Calls When a call is made to a new function all the variables local to the calling routine need to be saved, otherwise the new function will overwrite the calling routine variables. Similarly the current location address in the routine must be saved so that the new function knows where to go after it is completed.
RECURSIVE FUNCTION TO FIND FACTORIAL : - int fact (int n) { int s; if (n = = 1) return (1); else s = n * fact (n - 1); return (s); } 2.3 The Queue ADT 2.3.1 Queue Model A Queue is a linear data structure which follows First In First Out (FIFO) principle, in which
insertion is performed at rear end and deletion is performed at front end.
| ||
| ||
Data Structures 2.37 | ||
![]() |
![]() |
![]() |
Fig. 2.3.1 Queue Model Example : Waiting Line in Reservation Counter, 2.3.2 Operations on Queue The fundamental operations performed on queue are 1. Enqueue 2. Dequeue Enqueue : The process of inserting an element in the queue. Dequeue : The process of deleting an element from the queue. Exception Conditions Overflow : Attempt to insert an element, when the queue is full is said to be overflow condition. Underflow : Attempt to delete an element from the queue, when the queue is empty is said to be underflow. 2.3.3 Implementation of Queue Queue can be implemented using arrays and pointers. Array Implementation In this implementation queue Q is associated with two pointers namely rear pointer and front pointer. To insert an element X onto the Queue Q, the rear pointer is incremented by 1 and then set Queue [Rear] = X To delete an element, the Queue [Front] is returned and the Front Pointer is incremented by 1. ROUTINE TO ENQUEUE void Enqueue (int X) { if (rear > = max _ Arraysize) print (" Queue overflow"); else
| ||
| ||
Data Structures 2.38 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
{ Rear = Rear + 1; Queue [Rear] = X; } } ROUTINE FOR DEQUEUE void delete ( ) { if (Front < 0) print (" Queue Underflow"); else { X = Queue [Front]; if (Front = = Rear) { Front = 0; Rear = -1; } else Front = Front + 1 ; } } | ||||
| ||||
| ||||
Data Structures 2.39 | ||||
![]() |
![]() |
![]() |
![]() |
In Dequeue operation, if Front = Rear, then reset both the pointers to their initial values. (i.e. F = 0, R = -1)
Fig. 2.3.3 (a) Illustration for Array Implementation of Queue. Linked List Implementation of Queue Enqueue operation is performed at the end of the list. Dequeue operation is performed at the front of the list.
Queue ADT
Fig. 2.3.6 (b) Linked List Implementation of Queue ADT
| |||
Data Structures 2.40 | |||
![]() |
![]() |
![]() |
DECLARATION FOR LINKED LIST IMPLEMENTATION OF QUEUE ADT Struct Node; typedef Struct Node * Queue; int IsEmpty (Queue Q); Queue CreateQueue (void); void MakeEmpty (Queue Q); void Enqueue (int X, Queue Q); void Dequeue (Queue Q); Struct Node { int Element; Struct Node *Next; }* Front = NULL, *Rear = NULL; ROUTINE TO CHECK WHETHER THE QUEUE IS EMPTY int IsEmpty (Queue Q) // returns boolean value / { // if Q is empty if (Q return (1); } ROUTINE TO CHECK AN EMPTY QUEUE Struct CreateQueue ( ) { Queue Q; Q = Malloc (Sizeof (Struct Node)); if (Q = = NULL) Error ("Out of Space"); MakeEmpty (Q); return Q; } void MakeEmpty (Queue Q) { if (Q = = NULL) | ||
| ||
Data Structures 2.41 | ||
![]() |
![]() |
![]() |
Error ("Create Queue First"); else while (! IsEmpty (Q) Dequeue (Q); } ROUTINE TO ENQUEUE AN ELEMENT IN QUEUE void Enqueue (int X) { Struct node *newnode; newnode = Malloc (sizeof (Struct node)); if (Rear = = NULL) { newnode newnode Front = newnode; Rear = newnode; } else { newnode newnode Rear Rear = newnode; } } ROUTINE TO DEQUEUE AN ELEMENT FROM THE QUEUE void Dequeue ( ) { Struct node *temp; if (Front = = NULL) Error("Queue is underflow"); else { temp = Front; if (Front = = Rear) | ||
| ||
Data Structures 2.42 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
{ Front = NULL; Rear = NULL; } else
Front = Front Print (temp free (temp); } } 2.3.4 Double Ended Queue (DEQUE) In Double Ended Queue, insertion and deletion operations are performed at both the ends.
2.3.5 Circular Queue In Circular Queue, the insertion of a new element is performed at the very first location of the queue if the last location of the queue is full, in which the first element comes just after the last element. Advantages It overcomes the problem of unutilized space in linear queues, when it is implemented as arrays. | |||||||||||||
| |||||||||||||
|
|
|
|
| |||||||||
| |||||||||||||
| |||||||||||||
Data Structures 2.43 | |||||||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
| ||||||||||
|
| ||||||||||
|
| ||||||||||
Fig. 2.3.5 Insertion in a Circular Queue To perform the insertion of an element to the queue, the position of the element is calculated by the relation as Rear = (Rear + 1) % Maxsize. and then set Queue [Rear] = value. ROUTINE TO INSERT AN ELEMENT IN CIRCULAR QUEUE void CEnqueue (int X) { if (Front = = (rear + 1) % Maxsize) print ("Queue is overflow"); else { if (front = = -1) front = rear = 0; else rear = (rear + 1)% Maxsize; CQueue [rear] = X; } }
Data Structures 2.44 | |||||||||||
![]() |
![]() |
![]() |
To perform the deletion, the position of the Front printer is calculated by the relation Value = CQueue [Front] Front = (Front + 1) % maxsize. ROUTINE TO DELETE AN ELEMENT FROM CIRCULAR QUEUE int CDequeue ( ) { if (front = = -1) print ("Queue is underflow"); else { X = CQueue [Front]; if (Front = = Rear) Front = Rear = -1; else Front = (Front + 1)% maxsize; } return (X); } 2.3.6 Priority Queues Priority Queue is a Queue in which inserting an item or removing an item can be performed from any position based on some priority. 2.3.7 Applications of Queue * Batch processing in an operating system * To implement Priority Queues. * Priority Queues can be used to sort the elements using Heap Sort. * Simulation. * Mathematics user Queueing theory. * Computer networks where the server takes the jobs of the client as per the queue strategy. | ||
| ||
Data Structures 2.45 | ||
![]() |
![]() |
![]() |
Questions Part - A 1. Define ADT. 2. What are the advantages of linked list over arrays? 3. What are the advantages of doubly linked list over singly linked list? 4. List the applications of List ADT. 5. Write a procedure for polynomial differentiation. 6. What are the operations performed on stack and write its exceptional condition? 7. What do you mean by cursor implementation of list? 8. List the application of stack 9. Convert the infix expression a + b * c + (d * e + f) * g to its equivalent postfix expression and prefix expression. 10. Convert the infix expression (a * b) + ((c * g) - (e / f)) to its equivalent polish and reverse polish expression. 11. Write the recursive routine to perform factorial of a given number. 12. Define Queue data structure and give some applications for it. 13. What is Deque? 14. What is Circular Queue? 15. What is Priority Queue? 16. Write a routine to return the top element of stack. 17. Write a routine to check IsEmpty and Islast for queue. 18. Write a procedure to insert an element in a singly linked list 19. What is the principle of radix sort? 20. What is Multilist? Part - B 1. Explain the array and linked list implementation of stack. 2. Explain the array and linked list implementation of Queue. 3. What are the various linked list operations? Explain 4. Explain how stack is applied for evaluating an arithemetic expression. 5. Write routines to implement addition, subtraction & differentiation of two polynomials. 6. Write the recursive routine for Towers of Hanoi. | ||
| ||
Data Structures 2.46 | ||
![]() |
![]() |
![]() |
7. Explain Cursor implementation of List? 8. Write the operations performed on singly linked list? 9. Write the insertion and deletion routine for doubly linked list? 10. Write the procedure for polynomial addition and differentiation? | ||
| ||
Data Structures 2.47 | ||
![]() |
![]() |
![]() |
1. ARRAY IMPLEMENTATION OF STACK
#include<stdio.h> #include<conio.h> #include"stackadt.c"
void main() { int s; clrscr();
printf("\n1.Push \t"); printf("2.Pop \t"); printf("3.Display ");
do { printf("\nEnter your choice :"); scanf("%d", &c); switch(c) { case 1: push(); break; case 2: pop(); break; case 3: printf("The Contents of Stack are : \t"); display(); break; default: printf("Invalid choice"); exit(0); } }while(c<4); getch(); } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
//PROGRAM FOR stackadt.c
#define size 2 int stack[size], top=-1,b,cn; int c,res; void push(); void pop(); void display(); void push() { if(top>=size) { printf("The stack is overflow"); return; } else { printf("Enter the number to pushed in \n"); scanf("%d", &b); top++; stack[top]=b; printf("The number pushed is %d", stack[top]); return; } } void pop() { if(top==-1) { printf("The stack is underflow"); return; } else {
res=stack[top]; top; printf("The deleted number is %d \n", res); return; } } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
void display() { int i; if(top==-1) { printf("The stack is underflow"); return; } for(i=0;i<=top;i++) { printf("%d \t", stack[i]); } } SAMPLE INPUT AND OUTPUT:
1.Push 2.Pop 3.Display
Enter your choice :1 Enter the number to pushed in 10 The number pushed is 10
Enter your choice :1 Enter the number to pushed in 20 The number pushed is 20
Enter your choice :3 The Contents of Stack are : 10 20
Enter your choice :2 The deleted number is 20
Enter your choice :2 The deleted number is 10
Enter your choice :2 The stack is underflow
Enter your choice :4 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
2. LINKEDLIST IMPLEMENTATION OF STACK
#include<stdio.h> #include<conio.h> #include<alloc.h> #include"adt_link.c" int count; void main() { int choice; clrscr(); printf("\n\t1.Push "); printf("\t\t2.Pop"); printf("\t\t3.Display"); do { printf("\n\tEnter the choice:"); scanf("%d", &choice); switch(choice) { case 1: push(); break; case 2: pop(); break; case 3: display(); break; default: printf("\n\t Invalid choice"); break; } }while(choice<4); getch(); } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
//PROGRAM FOR adt_link.c
void push(); void pop(); void display(); struct node { int data; struct node *next; }*top = NULL;
void push() { int x; struct node *newnode; newnode=malloc(sizeof(struct node)); printf("\n\t Enter the number:"); scanf("%d", &x); newnode->data=x; if(top==NULL) { newnode->next=NULL; top=newnode; } else { newnode->next=top; top=newnode; } printf("\n\t The element %d is inserted.", x); getch(); } void pop() { struct node *temp; if(top==NULL) printf("\n\t The stack is underflow"); else | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ temp=top; top=top->next; printf("\n\t The element deleted is %d", temp->data); free(temp);
} getch();
} void display() { struct node *i; printf("\n\t The element of stack is :"); for(i=top; i!=NULL;i=i->next) printf("\t%d", i->data); if(top==NULL) printf(" STACK IS EMPTY"); getch(); }
SAMPLE INPUT AND OUTPUT:
1.Push 2.Pop 3.Display Enter the choice:1
Enter the number:10 The element 10 is inserted.
Enter the choice:1
Enter the number:20 The element 20 is inserted. Enter the choice:3
The element of stack is : 20 10
Enter the choice:2
The element deleted is 20
Data Structures | ||
![]() |
![]() |
![]() |
Enter the choice:2
The element deleted is 10
Enter the choice:2
The stack is underflow
3. BALANCING THE PARANTHESIS USING ARRAY IMPLEMENTATION
#include<stdio.h> #include<conio.h> #include<string.h> #include"stack.c" void main() { char expr[20]; char ch; int i,len; clrscr(); printf("Enter the Expression:\t"); scanf("%s",expr); len=strlen(expr); for(i=0;i<len;i++) { if(expr[i]=='(`) push(expr[i]); if(expr[i]==')') pop(); } if(top==-1) printf("Balanced Expression"); else printf("Imbalanced right paranthesis"); getch(); } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
// PROGRAM FOR STACK.C
int top=-1; char stack[20]; void push(char); void pop(); void push(char item) { stack[top++]=item; } void pop() { if(top==-1) { printf("Imbalanced Left paranthesis\n"); exit(0) ; } else top; }
SAMPLE INPUT AND OUTPUT:
Enter the Expression: (A+B) Balanced Expression
Enter the Expression: (A+B)) Imbalanced Left paranthesis
Enter the Expression: ((A+B) Imbalanced right paranthesis | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
4. BALANCING THE PARANTHESIS USING LINKED LIST IMPLEMENTATION
#include<stdio.h> #include<conio.h> #include<string.h> #include<stdlib.h> #include"linkstack.c" void main() { char expr[20]; char ch; int i,len; clrscr(); printf("Enter the Expression:\t"); scanf("%s",expr); len=strlen(expr); for(i=0;i<len;i++) { if(expr[i]=='(`) push(expr[i]); if(expr[i]==')') pop(); } if(top==NULL) printf("Balanced Expression"); else printf("Imbalanced right paranthesis"); getch(); }
//PROGRAM FOR LINKSTACK.C
struct node { int data; struct node *next; }*top=NULL; void push(char); void pop(); void push(char item) | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ struct node *newnode; newnode=malloc(sizeof(struct node)); newnode->data=item; if(top==NULL) { newnode->next=NULL; top=newnode; } else { newnode->next=top; top=newnode; }
} void pop() { if(top==NULL) { printf("Imbalanced Left paranthesis\n"); exit(0) ; } else top=top->next; }
SAMPLE INPUT AND OUTPUT:
Enter the Expression: (A+B) Balanced Expression
Enter the Expression: ((A+B) Imbalanced right paranthesis
Enter the Expression: (A+B)) Imbalanced Left paranthesis | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
5. POSTFIX EVALUATION USING ARRAY IMPLEMENTATION
# include<stdio.h> #include<conio.h> # include "postarr.c" void main() { char expr[20]; int x,len,a,b,c,i; printf("Enter the expression\n"); scanf("%s",expr); len=strlen(expr); for(i=0;i<len;i++) { if(expr[i]=='+'||expr[i]=='-'||expr[i]=='*'||expr[i]=='/') { b=pop(); a=pop(); switch(expr[i]) { case `+': c=a+b; push(c); break; case `-': c=a-b; push(c); break; case `*': c=a*b; push(c); break; case `/': c=a/b; push(c); break; } } else | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ printf("Enter the value of %c",expr[i]); scanf("%d",&x); push(x); } } printf("%d",stack[top]); }
//PROGRAM FOR POSTARR.C
int top=0; int stack[20]; void push(int); int pop(); void push(int item) { stack[top++]=item; } int pop() { int stackval; stackval=stack[top]; top; return stackval; }
SAMPLE INPUT AND OUTPUT:
Enter the postfix expression: abc+* Enter the value of a 10 Enter the value of b 20 Enter the value of c 30 The resultant value is : 500 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
6. PROGRAM FOR POSTFIX EVALUATION USING LINKED LIST IMPLEMENTATION OF STACK
# include<stdio.h> #include<conio.h> #include<alloc.h> #include<stdlib.h> # include "postlink.c" void main() { char expr[20]; int x,len,a,b,c,i; clrscr(); printf("Enter the postfix expression:\t"); scanf("%s",expr); len=strlen(expr); for(i=0;i<len;i++) { if(expr[i]=='+'||expr[i]=='-'||expr[i]=='*'||expr[i]=='/') { b=pop(); a=pop(); switch(expr[i]) { case `+': c=a+b; push(c); break; case `-': c=a-b; push(c); break; case `*': c=a*b; push(c); break; case `/': c=a/b; push(c); break; } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
}else { printf("Enter the value of %c",expr[i]); scanf("%d",&x); push(x); } } printf("The resultant value is :\t"); printf("%d",top->data); }
// PROGRAM FOR postlink.c
struct node { int data; struct node *next; }*top=NULL;
void push(int); int pop(); void push(int item) { struct node *newnode; newnode=malloc (sizeof(struct node)); newnode->data=item; if(top==NULL) { newnode->next=NULL; top=newnode; } else { newnode->next=top; top=newnode; } } int pop() { int stackval;
Data Structures | ||
![]() |
![]() |
![]() |
struct node *temp;temp=top; stackval=temp->data; top=top->next; free(temp); return stackval; }
SAMPLE INPUT AND OUTPUT:
Enter the postfix expression: ab+cd-g/* Enter the value of a1 Enter the value of b2 Enter the value of c8 Enter the value of d2 Enter the value of g3 The resultant value is : 6 7. ARRAY IMPLEMENTATION OF QUEUE
#include<stdio.h> #include<conio.h> #include"queuearr.c" void main() { void insert(); void deleted(); void display(); int a; clrscr(); do { printf("1. To insert an element by queue \n"); printf("2. To delete an element by queue \n"); printf("3. To display element by queue \n"); printf("4. To exit \n"); printf("Enter your choice"); scanf("%d", &a); switch(a) { case 1: insert(); | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
break; case 2: deleted(); break; case 3: display(); break; case 4: break; default: printf("Invalid choice"); break; } } while(a<4); getch(); }
//PROGRAM FOR queuearr.c
void insert(); void deleted(); void display(); int q[20], n=2, f=0, r=0;
void insert() { int b; if(r>=n) { printf("Queue overflow"); return; } else { printf("Enter the element to insert \n"); scanf("%d", &b); r++; q[r]=b; printf("The element inserted is %d \n", q[r]); f=1; return; } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
} void deleted() { int b; if(f==0) { printf("Queue underflow"); return; } else { b=q[f]; printf(" The element deleted is %d \n", b); if(f==r) f=r=0; else f++; return; } } void display() { int i; if(r==0) { printf("Queue is empty"); return; } else { for(i=1;i<r;i++) printf(" The element is %d \n", q[i]); } }
SAMPLE INPUT AND OUTPUT:
1.Push 2.Pop 3.Display Enter your choice :1 Enter the number to pushed in 10 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
The number pushed is 10
Enter your choice :1 Enter the number to pushed in 20 The number pushed is 20 Enter your choice :3 The Contents of Stack are : 10 20
Enter your choice :2 The deleted number is 20
Enter your choice :2 The deleted number is 10
Enter your choice :2 The stack is underflow
Enter your choice :4
8. PROGRAM FOR LINKED LIST IMPLEMNTATION OF QUEUE
#include<stdio.h> #include<conio.h> #include<alloc.h> #include "queue.c" void main() { int ch; clrscr(); do { printf("\n1.Insertion\t"); printf("2.Deletion\t"); printf("3.Display\t"); printf("4.Exit\t"); printf("\n Enter your choice:\t"); scanf("%d",&ch); switch(ch) | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ case 1: insert(); break; case 2: delet(); break; case 3: display(); break; } }while(ch<4); }
// program for queue.c
void insert(); void delet(); void display(); struct node { int element; struct node *next; }*front=NULL,*rear=NULL;
void insert() { int x; struct node *newnode; newnode=malloc(sizeof(struct node)); printf("\nEnter the data to be inserted:\t"); scanf("%d",&x); newnode->element=x; newnode->next=NULL; if(rear==NULL) { front=newnode; rear=newnode; } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
else { rear->next=newnode; rear=newnode; } printf("Inserted element is %d\n",newnode->element); }
void delet() { struct node *temp; if(front==NULL) { printf("\nQueue is Empty\n"); return; } temp=front; if(front==rear) front=rear=NULL; else front=front->next; printf("\nDeleted elemnet is %d\n",temp->element); free(temp); }
void display() { struct node *temp; if(front==NULL) { printf("\nQueue is Empty\n"); return; } temp=front; printf("\nContents of the Queue are\t"); while(temp!=NULL) { printf("%d\t",temp->element); temp=temp->next; } } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
SAMPLE INPUT AND OUTPUT:
1.Insertion 2.Deletion 3.Display 4.Exit Enter your choice: 1
Enter the data to be inserted: 12 Inserted element is 12
1.Insertion 2.Deletion 3.Display 4.Exit Enter your choice: 1
Enter the data to be inserted: 123 Inserted element is 123
1.Insertion 2.Deletion 3.Display 4.Exit Enter your choice: 1 Enter the data to be inserted: 1234 Inserted element is 1234
1.Insertion 2.Deletion 3.Display 4.Exit Enter your choice: 3
Contents of the Queue are 12 123 1234 1.Insertion 2.Deletion 3.Display 4.Exit Enter your choice: 2 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
9. program for linked list implementation of List
#include<stdio.h> #include<conio.h> #include<alloc.h> #include<stdlib.h> #include"listadt.c" void main() { int data,ch; clrscr(); printf("1.Insert\t2.Deletion\t3.display\t4.Exit"); do { printf("\nEnter your choice :"); scanf("%d",&ch); switch(ch) { case 1: printf("Enter the element to insert :"); scanf("%d",&data); insert(data); break; case 2: printf("Enter the element to Delete :"); scanf("%d",&data); deletion(data); break; case 3: display(); break; case 4: exit(0); } }while(ch<4); getch(); } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
//program for listadt.c
struct node *find(int); struct node *findprevious(int); struct node { int element; struct node *next; }*List=NULL,*P; void insert(int X); void deletion(int X); void display();
void insert(int X) { struct node *newnode; int pos; newnode=malloc(sizeof (struct node)); newnode->element=X; if(List->next==NULL) { List->next=newnode; newnode->next=NULL; } else { printf("\nEnter the value after which the element to be inserted :"); scanf("%d",&pos); P=find(pos); newnode->next=P->next; P->next=newnode; } } struct node *find(int s) { P=List->next; while(P!=NULL && P->element!=s) P=P->next; return P; }
Data Structures | ||
![]() |
![]() |
![]() |
void deletion(int X) { struct node *temp; temp=malloc(sizeof (struct node)); P=findprevious(X); if(P->next!=NULL) { temp=P->next; P->next=temp->next; printf("\nThe deleted element is %d",temp->element); free(temp); } else printf("\nElement not found in the List");
}
struct node *findprevious(int s) { P=List; while(P->next!=NULL && P->next->element!=s) P=P->next; return P; }
void display() {
if(List->next== NULL) printf("List is Empty"); else { P=List->next; printf("\n The contents of the List are :\n"); while(P!=NULL) { printf("%d>",P->element); | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
P=P->next; } printf("NULL"); } } SAMPLE INPUT AND OUTPUT:
1.Insert 2.Deletion 3.display 4.Exit Enter your choice :1 Enter the element to insert :12
Enter your choice :1 Enter the element to insert :13
Enter the value after which the element to be inserted :12
Enter your choice :1 Enter the element to insert :14
Enter the value after which the element to be inserted :12
Enter your choice :3
The contents of the List are : 12>14>13>NULL Enter your choice :2 Enter the element to Delete :14
The deleted element is 14 Enter your choice :3
The contents of the List are : 12>13>NULL Enter your choice :2
Enter the element to Delete :13
The deleted element is 13 Enter your choice :3 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
The contents of the List are : 12>NULL Enter your choice :4
10. doubly linked list implementation
#include<stdio.h> #include<conio.h> struct node { int data; struct node *1ptr, *rptr; }*head; struct node *ins_beg(int x, struct node *first); struct node *ins_end(int x, struct node *first); void display(struct node *first); struct node *dele(struct node *first,int del); void main() { int choice,x,del; head=NULL; clrscr(); printf("1.insert_Beg \n 2.Insert_End \n 3. Delete"); printf("\n 4.Display \n 5.Exit"); while (1) { printf("\n Enter your choice:"); scanf("%d",&choice); switch(choice) { case 1 : printf("\n Enter the data to be inserted :"); scanf("%d",&x); head=ins_beg(x,head); break; case 2 : printf("\n Enter the data to be inserted :"); scanf("%d",&x); head=ins_end(head,del); break;
Data Structures | ||
![]() |
![]() |
![]() |
case 3 : printf("\n Enter the data to be deleted :"); scanf("%d",&del); head=dele(head,del); break; case 4 : display(head); break; case 5 : exit(0); default:printf("\n Invalid Entry !!!"); getch(); } } getch(); } struct node *ins_beg(int x, struct node *first) { struct node *new, *cur, *prev; new=malloc(sizeof(struct node)); if(first==NULL) { new->data=x; new->lptr=NULL; new->rptr=NULL; return new; } else { new->data=x; new->lptr=NULL; new->rptr=first; return new; } } struct node *ins_end(int x,struct node *first) { struct node *new, *cur, *prev; new=malloc(sizeof(structnode)); if(first==NULL)
Data Structures | ||
![]() |
![]() |
![]() |
{ new->data=x; new->lptr=NULL; new->rptr=NULL; return new; } else { cur=first; while(cur->rptr!=NULL) { prev=cur; cur=cur->rptr; } cur->rptr=new; new->data=x; new->lptr=cur; new->rptr=NULL; return first; } } void display(struct node *first) { struct node *temp; temp=first; if(temp==NULL) printf("\n No data present!!!"); while(temp!=NULL) { printf("%d\t",temp->data); temp=temp->rptr; } getch(); } struct node *dele(struct node *fist, int del) { struct node *prev,*cur; cur=first; if(first==NULL) | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ printf("\n No data present!!!"); getch(); } else if(first->data==del) { printf("\n Data %d is deleted",first->data); first=first->rptr; getch(); return first; } else { while(cur->rptr!=NULL&&cur->data!=del) { prev=cur; cur=cur->rptr; } if(cur->rptr==NULL&&cur->data!=del) printf("\n Data not present!!!"); else if(cur->rptr!=NULL&&cur->data==del) { prev->rptr=cur->rptr; (cur->rptr)->lptr=prev; printf("\n Data %d is deleted",cur->data); } else if(cur->rptr==NULL&&cur->data==del) { prev->rptr=NULL; printf("\n Data %d is deleted",cur->data); } getch(); return first; } } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
Sample Input and Output:- 1.Insert_Beg 2.Insert_End 3.Delete 4.Display 5.Exit Enter your choice:1
Enter the data to be inserted :10
Enter your choice:1
Enter the data to be inserted :20
Enter your choice:2
Enter the data to be inserted :15
Enter your choice:4 20 10 15 Enter your choice:3
Enter the data to be deleted :10
Data 10 is deleted | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
/*CIRCULAR SINGLY LINKED LIST*/ #include<stdio.h> #include<conio.h> #include<stdlib.h> struct node { int data; struct node *link; }*head=NULL; void main() { void insert(); void disp(); void search(); void delet(); int ch; do { clrscr(); printf("1. Insert\n"); printf("2. Delete\n"); printf("3. Display\n"); printf("4. Search\n"); printf("5. Exit\n"); printf("enter the choice\n"); scanf("%d",&ch); switch(ch) { case 1: insert(); break; case 2: delet(); break; case 3: disp(); break; case 4: search(); break; case 5: break; } } while(ch!=5); } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
void insert (void) { struct node *temp,*temp1,*prev,*next; int elem; printf("enter the data u want to insert\n"); scanf("%d",&elem); temp=(struct node *)malloc(sizeof(struct node)); temp->data=elem; temp->link=head; if(head==NULL) { head=temp; head->link=head; printf("data inserted\n"); } else if(elem<head->data) { temp->link=head; head=temp; temp1=head; next=temp1->link; while(temp1->data<next->data) { temp1=next; next=next->link; } temp1->link=head; printf("data inserted\n"); } else { temp1=head; while((temp1->data<elem)&&(temp1->link!=head)) { prev=temp1; temp1=temp1->link; } if(temp1->data==elem) printf("data already inserted\n"); else if(temp1->data>elem) | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ prev->link=temp; temp->link=temp1; printf("data inserted\n"); } else if(temp1->link==head) { temp1->link=temp; temp->link=head; printf("data inserted\n"); } } getch(); } void disp(void) { struct node*temp; printf("%d\t",head->data); for(temp=head->link;temp!=head;temp=temp->link) printf("%d\t",temp->data); getch(); } void search(void) { int item,flag=0; struct node *temp; printf("enter the data u want to search\n"); scanf("%d",&item); temp=head; while((temp->data<=item)&&(temp->link!=head)) { if(temp->data==item) { flag=1; break; } else | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
temp=temp->link; } if(temp->link==head) { if(temp->data==item) flag=1; } if(flag==0) printf("the data u searched is not found\n"); else printf("the data u searched is found\n"); getch(); } void delet() { int item,flag=0; struct node *prev,*temp,*temp1,*next,*temp2; printf("enter the data u want to delete\n"); scanf("%d",&item); if(head->data==item) { temp2=head; head=head->link; flag=1; temp1=head; next=temp1->link; while(temp1->data<next->data) { temp1=next; next=next->link; } temp1->link=head; free(temp2); printf("data deleted\n"); } else { temp=head; while((temp->data<item)&&(temp->link!=head)) | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
{ prev=temp; temp=temp->link; } if(temp->data==item) { temp1=temp; prev->link=temp->link; free(temp1); printf("data deleted\n"); flag=1; } } if(flag==0) printf("the data u want to delete is not found in the list\n"); getch(); } OUTPUT: 1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 1 enter the data u want to insert 4
1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 1 enter the data u want to insert 9 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 1 enter the data u want to insert 2
1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 3
2 4 9
1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 2 enter the data u want to delete 2
1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 3 4 9 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
1. Insert 2. Delete 3. Display 4. Search 5. Exit enter the choice 4
enter the data u want to search 9 the data u searched is found as element 2
RESULT: Thus Circular Singly Linked list is implemented. | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
INTRODUCTION TO DATA STRUCTURES As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute which inturn requires choosing suitable algorithm with more efficiency, therefore the study of data structures because an important task which describes, methods of organizing large amounts of data and manipulating them in a better way. DATA A collection of facts, concepts, figures, observation, occurrences or instructions in a formalized manner. INFORMATION The meaning that is currently assigned to data by means of the conventions applied to those data (i.e processed data). RECORD Collection of related fields. DATA TYPE Set of elements that share common set of properties used to solve a program. DATA STRUCTURE A way of organizing, storing and retrieving data and their relationship with each other. ALGORITHM An algorithm is a logical module designed to handle a specific problem relative to a particular data structure. DESIRABLE PROPERTIES OF AN EFFECTIVE ALGORITHM * It should be clear / complete and definite. * It should be efficient. * It should be concise and compact. * It should be less time consuming. * Effective memory utilization. APPLICATIONS OF DATA STRUCTURES Some of the applications of data structures are : * Operating systems * Compiler design * Statistical and Numerical analysis * Database Management systems * Expert systems * Network analysis. | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
CLASSIFICATION OF DATA STRUCTURE Data Structure
Primitive Data Structure Non Primitive Data Structure
Integer float char pointer Linear Non Linear
Stacks Arrays Linked List Queue Trees Graph Primitive Data Structure It is a basic data structure which can be directly operated by the machine instruction. Non Primitive Data Structure Data Structures emphasize on structuring of a group of homogeneous or hetrogeneous data items. Linear Data Structure A data structure which contains a linear arrangement of elements in the memory. Non - Linear Data Structure A data structure which represents a hierarchical arrangement of elements. | ||
| ||
Data Structures | ||