Data Structures using C - Hanumantha Reddy
Data Structures using C
MCA- 25
| |Topic |Hrs |
|1 |Introduction to data structures |10 |
| |Information and meaning | |
| |Abstract Data Types, Sequences as value definitions, ADT for varying length character strings, Data types in C, Pointers I n C, | |
| |Data structures and C. | |
| |Arrays in C | |
| |The Array as an ADT, Using one-dimensional arrays, Implementing one-dimensional arrays, Arrays as parameters, Character strings | |
| |in C, Character string operations | |
| |Structures in C | |
| |Implementing structures, Unions, Implementation of unions, Structure parameters, Representing other data structures, Rational | |
| |numbers, Allocation of storage and scope of variables. | |
| |Dynamic memory allocation and cancellation in C | |
|2 |The Stack |5 |
| |Definition and examples | |
| |Primitive operation, Example, Stack as an ADT | |
| |Representing stacks in C | |
| |Implementing the POP operation, Testing for exceptional conditions, Implementing the PUSH operation | |
| |Example: Infix , Postfix and Prefix | |
| |Basic definitions and examples, Evaluation a postfix expression, Program to evaluate a postfix expression, Converting an | |
| |expression from infix to postfix, Program to converting an expression from infix to postfix | |
|3 |Recursion |4 |
| |Recursive definition and processes | |
| |Factorial function, Multiplication of natural numbers, Fibonacci Sequence, Binary Search, Properties of recursive definition or | |
| |algorithm | |
| |Recursion in C | |
| |Factorial in C, Fibonacci numbers in C, Binary Search in C and Towers of Hanoi problem. | |
|4 |Queues and Lists |10 |
| |Queue and it sequential representation | |
| |Queue as an ADT, C implementation of queues, Insert operation, Priority Queue, Array implementation of a priority. | |
| |Linked Lists | |
| |Inserting and removing nodes from a list, Linked implementation of stacks, Getnode and Free node operations, Linked | |
| |implementation of queue, Linked list as a data structure, Example of list operations, Header nodes. | |
| |Lists in C | |
| |Array implementation of lists, Limitations of Array implementation, Allocating and freeing dynamic variables, Linked lists using| |
| |dynamic variable, Queues as lists in C, Examples of list operations in C, Non integer and non-homogeneous lists. | |
| |Other list structures | |
| |Circular lists, Stack as a circular list, Queue as a circular list, Primitive operations on circular lists, Doubly linked lists | |
|5 |Trees |10 |
| |Binary trees | |
| |Operations on binary trees, Applications of binary trees | |
| |Binary tree representation | |
| |Node representation of binary tree, Internal end external nodes, Implicit array representation of binary trees, Choosing a | |
| |binary tree representation, Binary tree traversals in C, Threaded Binary trees | |
| |Trees and their application | |
| |C representation of trees, Tree traversals, General expressions as trees, Evaluating an expression tree, Constructing a tree. | |
|6 |Sorting |8 |
| |Exchange sort | |
| | Bubble sort | |
| | Quick sort | |
| |Selection and tree sorting | |
| |Binary tree sort | |
| |Heapsort | |
| |Insertion sorts | |
| |Simple insertion | |
| |Shell sort | |
| |Address Calculation sort | |
| |Merge and Radix sort | |
| |Radix Sort | |
|7 |Searching |5 |
| |Basic Search Techniques | |
| |Algorithmic notation, Sequential searching, Searching an ordered table, Indexed sequential search, Binary search, Interpolation | |
| |search | |
| |Tree Searching | |
| |Inserting into a binary search tree, Deleting from a binary search tree | |
| |Hashing | |
| |Resolving hash clashes by open addressing, Choosing a hash function. | |
Chapter 2. The Stack
Syllabus
|The Stack |
|Definition and examples |
|Primitive operation, Example, Stack as an ADT |
|Representing stacks in C |
|Implementing the POP operation, Testing for exceptional conditions, Implementing the PUSH operation |
|Example: Infix , Postfix and Prefix |
|Basic definitions and examples, Evaluation a postfix expression, Program to evaluate a postfix expression, Converting an expression from infix to|
|postfix, Program to converting an expression from infix to postfix |
STACK
It is an ordered collection of data items in which insertions and deletions are made at one end called the top.
It is known as a Last-In-First-Out (LIFO) list.
The size of the stack changes dynamically. As elements are entered into the stack its size grows and as elements are removed the size decreases.
An abstract data type in stack includes the following operations
1. MAKENULL(S) – Stack S is made empty.
2. TOP(S) – The element at the top of the stack S is returned.
3. POP(S) – The top element of the stack S is deleted.
4. PUSH(x, S) – The element x is inserted into the stack S.
5. EMPTY(S) – It returns true if stack S is empty otherwise it returns false.
Stack Representation
An array can be used to represent a stack. One dimensional array can be used.
Ex: Stack[max_stack_size] where max_stack_size is the maximum number of entries.
The first element of the stack is stored in stack[0], the second in stack[1] and the ith element in stack[i-1].
The variable top points to the top element of the stack. Initially top=-1 to indicate an empty stack.
The operations on a stack are
Push – inserting an element into the stack.
Pop– deleting an element from the stack.
| max_stack | max_stack | max_stack |
|_size |_size |_size |
| | | |
| |top | |
| | |top |
|top | | |
|(i) |(ii) |(iii) |
(i) normal stack (ii) inserting an element (iii) deleting an element
Each time an element is entered in to the stack top is incremented. The elements can be entered into the stack until top >= max_stack_size - 1.
When a new insertion is attempted after this condition it becomes the STACK OVERFLOW condition.
Each time an element is deleted from the stack top is decremented. The elements can be deleted from the stack until top = - 1.
When a new deletion is attempted after this condition it becomes the STACK UNDERFLOW condition.
Representing Stack in C
It can be declared as a structure using two objects:
▪ Array to hold the elements of the stack
▪ Integer to indicate the position of the current stack top within the array
|#define STACKSIZE 100 |Actual stack S may be declared as |
|struct stack |Struct stack s; |
|{ | |
|int top; | |
|int items[STACKSIZE]; | |
|}; | |
Algorithm for PUSH and POP
|PUSH(stack, top, max_stack_size, item) |This algorithm inserts the element item into the |
| |stack stack implemented using an array. Top points |
| |to the top element of the stack. The stack can |
| |contain at most max_stack_size elements i.e. item. |
|If(top=max_stack_size-1) | |
| Print “OVERFLOW” | |
| Return | |
|End if | |
|Top ← top+1 | |
|Stack[top] ←item | |
|Return | |
|POP(stack, top, data) |This algorithm removes the top element from the |
| |stack stack implemented using an array. The top |
| |element of the stack is assigned to stack. |
|If(top = -1) | |
| Print “UNDERFLOW” | |
| Return | |
|End if | |
|Data ← Stack[top] | |
|Top ← top-1 | |
|Return | |
PUSH Operation:
Step 1: [Overflow Check]
If TOP = MAXSTACK – 1
THEN "STACK OVERFLOW”.
Step 2: [Increment top Value]
TOP = TOP +1
Step 3: [Insert the item]
S[TOP] = item
POP Operation:
Step 1: [Under Flow Check]
If TOP = -1
THEN “STACK UNDERFLOW”
Step 2: [Delete the item]
Item = S[TOP]
Step 3: [Decrement the TOP]
TOP = TOP -1
DISPLAY Operation:
Step 1: [Under Flow Check]
If TOP = -1
THEN “STACK UNDERFLOW”
Step 2: [Display the item]
From i = TOP to i = 0
Print S[i]
PROGRAM:
|#include |Header files |
|#include | |
|#define N 5 |Declaration of the max number of elements in the stack. |
|struct stack |Declaration of the stack as a structure containing two objects |
| |- Array to hold the elements of the stack- data |
| |- Integer to indicate the position of the current stack top within the array-top |
|{ | |
| int top; | |
| int data[N]; | |
|}; | |
| | |
|struct stack s; |Declaration of actual stack |
| | |
|void push(struct stack*,int); |Declaration of the functions used to push, pop and display elements of the stack.|
| |Push and display have the return type as void. |
| |Pop has the return type as int since the function returns the items stored in the|
| |stack. The items stored are of the data type int. |
|int pop(struct stack*); | |
|void display(struct stack*); | |
| | |
|void main() |Main function |
|{ | |
| int ch, item, a; | |
| clrscr(); | |
| = -1; |Initializing top = -1i.e stack is empty |
| printf("1.Push\n"); |Displaying the menu |
| printf("2.Pop\n"); | |
| printf("3.Display\n"); | |
| printf("4.Exit\n"); | |
| while(1) | |
| { | |
| printf("\n Enter your choice:"); | |
| scanf("%d",&ch); | |
| switch(ch) | |
| { | |
| case 1 : printf("Enter the |If the choice is the push operation |
|item:"); | |
| scanf("%d",&item); | |
| Push(&s,item); |Call the function push. The base address of stack and the item to be pushed are |
| |passed to the function. |
| Break; | |
| case 2 : a=pop(&s); |The choice is pop. The function pop is called and the return value is assigned to|
| |a. The base address of the stack is passed to the function. |
| if (a) | |
| printf("The item popped : %d\n", a); | |
| break; | |
| case 3 :display(&s); |The choice is display. The function display is called. The base address of the |
| |stack is passed to the function. |
| break; | |
| case 4 : exit(); |The choice is exit. The system defined function exit is called. |
| Break; | |
| default: printf("\n Enter correct choice."); | |
| } | |
| } | |
|} | |
|// The function push | |
|void push(struct stack *ps, int x) |The base address of the stack is passed as the value of ps. The item is passed as|
| |x. |
|{ | |
| If(ps->top == N-1) |If the top of the stack is equal to max size of stack -1 i.e. it has reached the |
| |maximum limit, no more elements can be stored in the stack. The over flow |
| |condition is printed. |
| printf("Stack Overflow\n"); | |
| Else |If not |
| |The top is incremented by 1 value. |
| |The array data will now point to the top and will |
| |store the value of x. |
| { | |
| (ps->top)++; | |
| ps->data[ps->top]=x; | |
| } | |
|} | |
|//The function pop | |
|int pop(struct stack *ps) |The base address of the stack is passed as the value of ps. |
|{ | |
| int temp; | |
| If(ps->top == -1) |If the top of the stack is equal to -1 i.e. the stack is completely empty, no |
| |element can be deleted from the stack. The under flow condition is printed. |
| { | |
| printf("Underflow\n"); | |
| return(0); | |
| } | |
| Else | |
| { |If not |
| |The temporary variable temp is assigned the |
| |value of the item present in the stack at the top |
| |of the stack. |
| |Top is decremented by 1. |
| |The value of temp is returned to the main |
| |function. |
| temp = ps->data[ps->top]; | |
| (ps->top)--; | |
| return(temp); | |
| } | |
|} | |
|// The function display | |
|void display(struct stack *ps) |The base address of the stack is passed as the value of ps. |
|{ | |
| int i; | |
| If(ps->top == -1) |If the top of the stack is equal to -1 i.e. the stack is completely empty, no |
| |element can be displayed from the stack. |
| printf("Stack is Empty\n"); | |
| Else | |
| { | |
| printf("The stack contains:\n"); |If not |
| |The top most element is first displayed and so on |
| |until the index I of the stack is greater than or |
| |equal to zero. |
| for(i=ps->top; i>=0;i--) | |
| { | |
| printf("| %d |\n",ps-> | |
|data[i]); | |
| } | |
| } | |
|} | |
Evaluation of Expressions
Infix Expression
Ex: A+B*C-D
To evaluate this expression
• We need to have the knowledge of the precedence of all the operators used in an expression.
• The parenthesis has to be written.
Such an expression is known as the infix expression.
The order of precedence of the binary operators is
1. Exponentiation
2. Multiplication / Division
3. Addition / Subtraction
When we have the operators of the same precedence scanned without the parenthesis the order is assumed left to right.
In the case of exponentiation the order is assumed to be right to left.
Ex: A + B + C => (A + B) + C
A ^ B ^ C => A ^ (B ^ C)
By using parenthesis we override the default precedence.
Prefix Expression or Polish Notation
Ex: *+ABC
This equivalent to (A+B)*C
The operator symbols are placed before the operands.
|Infix |Prefix |
|A + B |+ AB |
|A + B – C |+AB - C |
| |- + AB |
|(A+B)*(C-D) |* (A + B) (C - D) |
| |* + AB (C - D) |
| |* + AB - CD |
|((A+B)*C-(D+E))/(F+G) |(+ AB * C - (+ DE)) / ( + FG) |
| |(* + ABC - ( + DE)) / ( + FG) |
| |( - * + ABC + DE) / ( + FG) |
| |/ - * + ABC + DE + FG |
|A – B / (C * D ^ E) |A – B / ( C * ^ DE) |
| |A – B / ( * C ^ DE) |
| |A - / B * C ^ DE |
| |- A / B * C ^ DE |
|A^B*C-D+E/F/(G+H) |A ^ B * C - D + E / F / ( + GH) |
| |^ AB * C – D + E / F / ( +GH) |
| |* ^ ABC – D + E / F / ( + GH) |
| |- * ^ ABCD + E / F / ( + GH) |
| |- * ^ ABCD + / EF / ( + GH) |
| |- * ^ ABCD + / / EF + GH |
| |+ - * ^ ABCD // EF + GH |
|((A+B) * C –( D – E)) ^ ( F+G) |( ( + AB ) * C – ( - DE)) ^ (+ FG) |
| |( * + ABC – ( - DE)) ^ ( + FG) |
| |( - * + ABC – DE) ^ ( + FG) |
| |^ - * + ABC – DE + FG |
Postfix Expression or Reverse Polish Notation
Ex: AB + C *
Is equivalent to (A+B)*C
The operator symbols are placed after the operands.
|Infix |Postfix |
|A + B |AB + |
|A + B – C |AB + -C |
| |AB + C - |
|(A+B)*(C-D) |(AB +) * (CD -) |
| |AB + CD - * |
| | |
|((A+B)*C-(D+E))/(F+G) |((AB +) * C – ( DE +)) / (FG +) |
| |( AB + C* - (DE +)) / (FG + ) |
| |(AB + C * DE + - ) / (FG +) |
| |AB + C * DE + - FG + / |
|A^B*C-D+E/F/(G+H) |A^ B * C – D + E / F / (GH +) |
| |AB ^ * C – D + E / F / (GH +) |
| |AB ^ * C – D + EF / / (GH+) |
| |AB ^ * C – D + EF / GH + / |
|((A+B) * C –( D – E)) ^ ( F+G) |( (AB +) * C – ( DE - ) ) ^ ( FG + ) |
| |( AB + C * - (DE - )) ^ ( FG + ) |
| |( AB + C * DE - - ) ^ ( FG + ) |
| |AB + C * DE - - FG + ^ |
|A – B / (C * D ^ E) |A – B / ( C * DE ^ ) |
| |A - B / ( C DE ^ * ) |
| |A – B C DE ^ * / |
| |A B C DE ^ * / - |
Program to evaluate a given postfix expression.
ALGORITHM:
Step 1: Add “#” at the end of P.
Step 2: Repeat scanning P from left to right and repeat step 3 and 4 for each
element of P until “#” is encountered .
Step 3: If an operand is encountered, push it onto STACK.
Step 4: If an operator @ is encountered:
1) Remove the two top elements of the STACK. If A is the top element, B is the next top element.
2) Evaluate B @ A. [NOT A @ B]
3) Push the result of (2) of step 4 back on to STACK.
Step 5: Evaluated value is equal to the top of the STACK.
Step 6: Exit.
Program
|#include |Header files |
|#include | |
|#include | |
|#include | |
|#include | |
| |Declaration of the stack as a structure containing two |
|struct stack |objects |
|{ |- Array to hold the elements of the stack- data |
|int top; |- Integer to indicate the position of the current stack top |
|int data[20]; |within the array - top |
|}s1; | |
| |Declaration of the functions used to push, pop and display |
| |elements of the stack. |
|void push(struct stack *s, int ch); |Push and display have the return type as void. |
| |Pop has the return type as int since the function returns |
|int pop(struct stack *s); |the items stored in the stack. The items stored are of the |
| |data type int. |
|void main() |Main function |
|{ | |
| char ch, postfix[20]; |Postfix is a character array which stores the postfix |
| |expression. |
| Int i,op1,op2,result; | |
| Struct stack s; |Declaration of actual stack |
| clrscr(); | |
| printf("Enter the valid postfix expression\n"); | |
| scanf("%s", postfix); |Entering the valid postfix expression |
| for(i = 0;i top); | |
| s->data[s->top] = x; | |
|} | |
| | |
|int pop(struct stack *s) | |
|{ | |
| int temp; | |
| temp = s->data[s->top]; | |
| --(s->top); | |
| return(temp); | |
|} | |
To convert an infix expression to postfix expression.
ALGORITHM
Step 1: PUSH the left parenthesis “(“ on to STACK and add right parenthesis “)”
at the end of Q.
Step 2: Scan Q from left to right and repeat step 3 to 6 for each element of Q,
until the attack is empty.
Step 3: If an operand is encountered, add it to P.
Step 4: If “(“ is encountered , push it onto stack and this “(“ can be removed or
popped only when “)” is encountered .
Step 5: If an operator @ is encountered
a. Repeatedly pop from the STACK and add to P each operator ( on the top of stack, which has the same precedence or higher precedence than operator @.
b. PUSH to stack.
Step 6: If “)” is encountered
a. Repeatedly pop from the STACK and add to P each operator (on the top of stack ) until left parenthesis “(“ is encountered .
b. Remove the left parenthesis “(“.
[Do not add left parenthesis to P].
Program
|#include | |
|#include | |
|#include | |
|#define N 10 | |
|struct stack | |
|{ | |
|int top; | |
|char data[N]; | |
|}; | |
|void push(struct stack*,char); | |
|char pop(struct stack*); | |
|int precedence(char); | |
|void main() | |
|{ | |
| struct stack s; | |
| char infx[10],post[10]; | |
| char ch; | |
| int i,j=0; | |
| =-1; | |
| Clrscr(); | |
| = -1; | |
| Printf("Enter the Infix Expression:\n"); | |
| scanf("%s",infx); | |
| for(i=0;i= precedence(ch))&&( != -1)) | |
| post[j++] = pop(&s); | |
| push(&s,ch); | |
| } | |
| } | |
| While( != -1) | |
| post[j++] = pop(&s); | |
| post[j]='\0'; | |
| Printf("\nPostfix Expression is %s",post); | |
| Getch(); | |
|} | |
| | |
|void push(struct stack *s,char x) | |
|{ | |
| s->top++; | |
| s->data[s->top] = x; | |
|} | |
| | |
|char pop(struct stack *s) | |
|{ | |
| int temp; | |
| Temp = s->data[s->top]; | |
| s->top--; | |
| return(temp); | |
|} | |
| | |
|int precedence(char ch) | |
|{ | |
| switch(ch) | |
| { | |
| case '+' : | |
| case '-' : return(1); break; | |
| case '*' : | |
| case '/' : return(2); break; | |
| case '^' : return(3); break; | |
| case '(' : return(0); | |
| } | |
| return; | |
|} | |
Chapter 3. Recursion
Syllabus
|Recursion |
|Recursive definition and processes |
|Factorial function, Multiplication of natural numbers, Fibonacci Sequence, Binary Search, Properties of recursive definition or |
|algorithm |
|Recursion in C |
|Factorial in C, Fibonacci numbers in C, Binary Search in C and Towers of Hanoi problem. |
RECURSION
It is defined as the process in which a procedure invokes itself or invokes other procedures that eventually invoke the first procedure.
When a procedure contains a call to itself it is called direct recursion and when a procedure calls another procedure, which in turn calls the first procedure it is called as indirect recursion.
FACTORIAL FUNCTION
Given a positive integer n, n factorial is defined as the product of all integers between n and 1.
Ex: 5 factorial is 5 * 4 * 3 * 2 * 1 = 120
! is often used to denote the factorial function.
n ! = 1 if n == 0
n ! = n * ( n – 1) * ( n – 2 ) * ( n – 3 ) * ------- * 1 if n > 0
The pseudocode can be written as
product = 1;
for( i = n ; i > 0 ; i - - )
product = product * i;
return(product);
This is called as an iterative procedure. It calls for the explicit repletion of a process until a certain condition is satisfied. It can be written as a function that returns the product n ! when n is the input.
To write this using the recursive definition the algorithm is
Factorial (Fact, N)
Step 1: if (N = 0)
Fact = 1
Return
Step 2: Factorial (Fact, N -1)
Step 3: Fact = Fact * N
|#include | |
|#include | |
|#include | |
|int fact(n); | |
|void main() | |
|{ | |
| Int n, f = 1; | |
| clrscr(); | |
| printf(“\n Enter the number\n”); | |
| scanf(“%d”, &n); | |
| f= fact (n) | |
| printf(“\n The factorial of %d is %d”, n, f); | |
| getch(); | |
|} | |
|//The function fact | |
|int fact( n) | |
|{ | |
| int f; | |
| if (n < 0) | |
| { | |
| printf(“ \n Factorial of negative numbers not possible”); | |
| exit; | |
| } | |
| else | |
| If ( n == 0) | |
| return(1); | |
| Else | |
| { | |
| f = n * fact(n –1); | |
| return(f); | |
| } | |
|} | |
Multiplication of natural numbers
Iterative Definition
The product a * b can be defined as a added to itself b times where a and b are positive integers.
Recursive Definition
a * b = a if b == 1
a * b = a * ( b – 1 ) + a if b > 1
|#include | |
|#include | |
|int prod(int,int); | |
|void main() | |
|{ | |
| int a,b; | |
| clrscr(); | |
| printf("\n Enter the two numbers\n"); | |
| scanf("%d%d",&a,&b); | |
| printf("\nThe product of two numbers %d and %d is %d",a,b,a*b); | |
| printf("\nThe product of two numbers %d and %d is %d",a,b,prod(a,b)); | |
| getch(); | |
|} | |
| | |
|int prod(int a,int b) | |
|{ | |
| int p; | |
| if(a==0||b==0) | |
| return(0); | |
| else if(b==1) | |
| return(a); | |
| Else | |
| { | |
| p=a+prod(a,b-1); | |
| return(p); | |
| } | |
|} | |
Fibonacci Series
The fibonacci sequence is 0,1,1,2,3,5,8,13,21,34,…….
Each element in this sequence is the sum of the two preceding elements.
It is written as
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8…..
Recursive definition
Fib(n) = n if n == 0 or n == 1
Fib(n)= fib( n - 2 ) + fib( n – 1 ) if n > = 2
Program to get the fibonacci sum
|#include | |
|#include | |
|int fib(int); | |
|void main() | |
|{ | |
| int f,n; | |
| clrscr(); | |
| printf("\n ENTER THE VALUE OF N - - - > "); | |
| scanf("%d",&n); | |
| f=fib(n); | |
| printf("\n The Fibonacci Sum is - - - > "); | |
| printf("%d",f); | |
| getch(); | |
|} | |
|fib(int n) | |
|{ | |
| int f; | |
| if(n==0||n==1) | |
| return(n); | |
| Else | |
| { | |
| f=fib(n-2)+fib(n-1); | |
| return(f); | |
| } | |
|} | |
Program to get the fibonacci series
|#include | |
|#include | |
|void main() | |
|{ | |
| int fib[20]; | |
| int i,n; | |
| clrscr(); | |
| printf("\n ENTER THE VALUE OF N - - - > "); | |
| scanf("%d",&n); | |
| fib[0]=0; fib[1]=1; | |
| printf("\n The Fibonacci Series is - - - > \n"); | |
| for(i=1;i Last
Return ( -1 ).
Else go to Step 2
Step 2: [Calculate the middle]
Mid = (First + Last) / 2
Step 3: If item < List [mid]
Binary_search (List [ ], item, First, Mid -1)
Step 4: Else if Item > List [Mid]
Binary_search (List [ ], item, Mid + 1, Last)
Step 5: Else
Return (Mid + 1).
Step 6: Stop.
Ex: Array a contains the elements 1,3,4,5,7,9,31,33
The item to be searched is 7. This is a sorted list.
First has the value 0. Last has the value 7.
The middle position in this list is (First + Last) / 2 = (0+7) / 2 = 3.
The middle element is a[3] = 5.
If Item < a [Mid]
Binary_Search (a [ ], Item, First, Mid -1)
Else if Item > a [Mid]
Binary_Search (a [ ], Item, Mid + 1, Last)
Is 7 < 5 then search the list between the first element i.e. 0 and the element with the value Mid – 1 i.e. 2
Is 7 > 5 then search the list between the element with the value Mid + 1 i.e. a[4] and the last element i.e. a[7].
The search process is repeated in the lower half of the list. The list is 7,9,31,33
The middle position in this list is now ( 4 + 7 ) / 2 = 5 and the middle element in this new list is 9.
Is 7 < 9 or 7 > 9? Is 7 < 9 then search the list between the element at position 4 and the element with the value Mid – 1 i.e. 4 . The list is 7,9.
The middle position in this list is (4 + 4 ) / 2 = 4 and the middle element is now 7.
The search returns the element 7.
Program
|#include | |
|#include | |
|#define N 20 | |
|int a[N]; | |
|int binary(); | |
|void sort(); | |
|void main() | |
|{ | |
| Int ch, n,no,i,j,c; | |
| clrscr(); | |
| printf("Enter the size of Array:"); | |
| scanf("%d",&n); | |
| printf("Enter the Array Elements :\n"); | |
| for(i=0;irear==MAXSIZE-1) |If pq->rear is pointing to the last element then make pq->rear=0. |
| pq->rear=0; | |
| Else |Otherwise increment pq->rear |
| (pq->rear)++; | |
| if(pq->rear==pq->front) |If queue’s rear and front value are equal i.e. the queue is full, print|
| |the overflow condition. |
| { | |
| printf(“Queue Overflow”); | |
| exit(1); | |
| } | |
| pq->elements[pq->rear]= ele; |The ele is stored at the position of pq->rear. |
| return; | |
|} | |
Algorithm
|Insert Operation |Delete Operation |
|QINSERT ( Q, FRONT, REAR, N, ITEM ): |QDELETE ( Q, FRONT, REAR, ITEM ) |
| |Step 1 : [ Underflow check ] |
|Step 1 : [ Overflow check ] |If FRONT = -1 |
|If FRONT = ( REAR + 1 ) % N |Then write ( ‘Underflow ‘ ) |
|Then write ( ‘overflow ‘ ) |Return. |
|Return. |Step 2 : [ Delete the item ] |
|Step 2 : [ Increment rear pointer ] |ITEM = Q[FRONT] |
|If FRONT = -1 |Write “ The ITEM is Deleted “. |
|FRONT = REAR = 0. |Q[ FRONT ] = NULL. |
|Else |Step 3 : If FRONT = REAR [ When there is only one item ] |
|REAR = (REAR +1) % N. |FRONT = REAR = -1. |
|Step 3 : [ Insert the item ] |Else |
|Q[REAR] = ITEM |FRONT = ( FRONT + 1 ) % N. |
|Step 4 : Return. |Step 4 : Return. |
|Display Operation |
|QDISPLAY ( Q, FRONT, REAR, ITEM ): |
|Step 1: [ Underflow check ] |
|If FRONT = -1 |
|Then write ( ‘QUEUE is empty ‘ ) |
|Return. |
|Step 2: [ Display the items ] |
|If ( FRONT rear==q->front) |If the last element is going to be deleted |
| { | |
| printf("\n The last element to be deleted is %d", |Display the last element |
|q->items[q->front]); | |
| q->front=0; |Reinitialize front and rear |
|q->rear=-1; | |
| } | |
| Else | |
| { | |
| printf("\n The deleted item is %d",q->items[q->front]); |Display the deleted item |
| q->front++; |Increment front |
| } | |
| return; | |
|} | |
|//Function to display the elements | |
|qdisplay(struct queue *q) |A pointer variable q of the structure is used as the |
| |argument. |
|{ | |
| int i; | |
| if(q->rear==q->front-1) |The Underflow condition |
| printf("\n Queue is empty"); | |
| Else | |
| { | |
| printf("\n The elements are:"); |Display the elements |
|for(i=q->front;irear;i++) | |
|printf("\n %d \t",q->items[i]); | |
| printf("\n The front of queue is %d",q->items[q->front]); |Display the front and rear of the queue. |
|printf("\n The rear of queue is %d",q->items[q->rear]); | |
| } | |
| return; | |
|} | |
Circular Queue
Ex: Size of circular queue (N) is 4.
|Sl. No. |Operation |Status of Queue |Front and Rear |
| | |0 | |
|1. |Insert 10 |1 |Front= 0, Rear=0 |
| | |2 | |
| | |3 | |
| | | | |
| | |10 | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | |0 | |
|2. |Insert 11 |1 |Front= 0, Rear=1 |
| | |2 | |
| | |3 | |
| | | | |
| | |10 | |
| | |11 | |
| | | | |
| | | | |
| | | | |
| | | | |
| | |0 | |
|3. |Insert 12 |1 |Front= 0, Rear=2 |
| | |2 | |
| | |3 | |
| | | | |
| | |10 | |
| | |11 | |
| | |12 | |
| | | | |
| | | | |
| | | | |
|4. |Insert 14 |0 | |
| | |1 |Front= 0, Rear=3 |
| | |2 | |
| | |3 | |
| | | | |
| | |10 | |
| | |11 | |
| | |12 | |
| | |14 | |
| | | | |
| | | | |
|5. |Insert 15 |0 |Front= 0, Rear=3 |
| | |1 |The condition Front=(Rear+1)%N is true |
| | |2 | |
| | |3 | |
| | | | |
| | |10 | |
| | |11 | |
| | |12 | |
| | |14 | |
| | | | |
| | |Queue Overflow | |
|6. |Delete |0 | |
| | |1 |Front =1, Rear=3 |
| | |2 | |
| | |3 | |
| | | | |
| | | | |
| | |11 | |
| | |12 | |
| | |14 | |
| | | | |
| | | | |
|7. |Delete |0 | |
| | |1 |Front =2, Rear=3 |
| | |2 | |
| | |3 | |
| | | | |
| | | | |
| | | | |
| | |12 | |
| | |14 | |
| | | | |
| | | | |
|8. |Insert 15 |0 |Front= 2, Rear=0 |
| | |1 |Rear=(Rear+1)%N is true |
| | |2 |Rear=(3+1)%4=0 |
| | |3 | |
| | | | |
| | |15 | |
| | | | |
| | |12 | |
| | |14 | |
| | | | |
| | |Queue Overflow | |
|9. |Delete |0 | |
| | |1 |Front =3, Rear=0 |
| | |2 | |
| | |3 | |
| | | | |
| | |15 | |
| | | | |
| | | | |
| | |14 | |
| | | | |
| | | | |
|10. |Delete |0 | |
| | |1 |Front =0, Rear=0 |
| | |2 | |
| | |3 | |
| | | | |
| | |15 | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
Priority Queue
Insertion Operation
First specify the priority and the item to be inserted. If the queue of the given priority is full display the condition Queue Overflow. If the queue is not full insert the elements at the rear end of the given priority queue.
1. If rear[priority]=N-1
Display “Queue Overflow”
Exit
2. rear[priority]=rear[priority]+1
3. queue[priority][rear[priority]]=item
Deletion Operation
Scan the first non-empty queue and delete the first element of that queue.
1. Scan all the queues till a non empty queue is reached.
2. if queue[ ][ ] is empty
Display “Queue Underflow”
Exit
3. Delete the element which is in front of the first non empty queue.
DEQUES
It is a double ended queue. It is maintained by a circular queue.
1. Input restricted Deque
It allows insertions only at one end of the queue but allows deletion at both the ends. The insertions are possible only at the rear end.
2. Output restricted Deque
It allows deletions only at one end of the queue but allows insertion at both the ends. The deletion is possible only at the front end.
Linked Lists
It is a data structure where the data items are stored by explicit ordering. Each item in the list is called a node and contains two fields.
The fields are the information field info-it contains the actual element and an address field next- it contains the address of the next element.
The address is used to access a particular node is called a pointer.
The entire list is accessed from an external pointer – list that contains the address of the first node in the list.
The next field of the last node in the list contains a special value known as null. It is used to signal the end of a list.
The list with no nodes is called an empty list or null list.
Inserting and Removing Nodes from a list
Inserting Nodes
The list is a dynamic structure.
| Info next Info next Info next |
|List Fig: 1 |
| |
| Info next |
|P |
| |
|Info next Info next Info next Fig: 2 |
| |
|List |
| Info next |
|P |
| |
|Info next Info next Info next |
|List Fig: 3 |
| |
| |
| |
| |
|Info next |
|info next info next info next |
|P |
| |
|List Fig: 4 |
| |
|P |
| |
|List |
|Fig: 5 |
| |
| |
|List |
|Fig: 6 |
Fig: 1 consists of a list which contains three nodes.
1. We need to insert the integer 6 into the list at the front of the list. To do this we need a mechanism that obtains empty nodes and then adds them to the existing nodes.
The mechanism for obtaining the empty nodes is p=getnode();.
It obtains an empty node and then sets the contents of the variable p to the address of that node. The value of p is now a pointer to this newly allocated table.
Fig: 2 consists of a new node P. This is to be inserted into the list at the front of the list.
2. To insert the integer 4 into the info portion of the allocated node.
info(p)=4;
Fig: 3 consists of the new node P with the value 4 in the info field.
3. The next field of the node P should be set. Since this node has to be inserted at the beginning of the list this node should point to the current first node i.e. the node having the value 1.
next(p)=list;
This operation places the value of list into the next field of node(p).
Fig: 4 shows this operation. P points to the list.
4. The external pointer list should now point to the new additional node since it is at the beginning of the list.
list = p;
This changes the value of list to the value of p.
Fig: 5 shows this operation. This shows p as an auxiliary variable which is used during the process of modifying the list.
5. The value of p is not necessary after the process of modifying. The value of p may be changed now.
Fig: 6 shows the final list.
The pseudo code for this insertion in general is
p=getnode();
info(p) =x;
next(p)=list;
list = p; where x is the value of the node to be inserted.
Removing nodes
The process is to remove the first node of a nonempty list and store the value of the info field into the variable x.
| Info next Info next Info next |
|List Fig: 1 |
| |
| |
|P |
| |
|List Fig: 2 |
|X = 1 |
|Info next |
|info next info next |
|P |
|List Fig: 3 |
|X = 1 |
|Info next P Fig: 3 |
|Info next Info next |
| |
|List Fig: 4 |
| X = 1 Info next Info next Fig: 5 |
|List |
| |
1. We first have the list as shown in Fig: 1.
2. We have to assign the value of the external pointer list to the new pointer p. This is done using the operation
p =list;
This changes the value of p to the value of list as shown in Fig: 2.
3. Now p contains the address of the list. Since we are removing the first node of the list, the external pointer list should point to the second node. This cane be done by the operation
list = next(p);
This operation places the value of the next field of node(p) into the list. This is shown in Fig: 3.
4. The value of the info node of the first node is now set as the value of the variable x.
x=info(p);
This operation sets the value of x as the value of the info field of the node i.e. 1. This is shown in Fig: 4.
5. At this point the first node has been removed from the list and x has been set to the desired value i.e. 1. p still points to the node that was present at the first position in the list. This node is not necessary as it is not present in the list and its information is stored in x.
The node(p) should be able to be reused again.
freenode(p) frees the node.
After this operation node(p) cannot be referenced as the node is not allocated any more. Any reference to p is also illegal.
The node can be reallocated again and a pointer to it can be reassigned to p by the operation p=getnode().
Algorithm
|Insert at Beginning |Delete a node based on an item. |
| | |
|Step 1: |Step 1: |
|Create a new node that is to be inserted |Check for the position whether the deletion is at first position |
|NEWNODE = getnode( ); |If ( POS = 1 ) |
|Step 2: |DELETE_AT_BEGINING ( ); |
|Enter the item into the INFO field of the |Else GO TO Step 2. |
|NEWNODE |Step 2: |
|INFO [ NEWNODE ] = ITEM |Set CURRPTR to start |
|Step 3: |CURRPTR = start |
|Assign the item into INFO field of the |Step 3: |
|NEWNODE |Set PV to NULL |
|LINK [ NEWNODE ] = Start. |PV = NULL |
|It makes a link from NEWNODE to the |Step 4: |
|previous first node. Now both ‘start’ and |If the item to be deleted is not at first position |
|‘NEWNODE’ are pointing to the original |From I = 0 to I < POS |
|first node of the linked list |PV = CURRPTR |
|Step 4 : |CURRPTR = CURRPTR ( LNK |
|Reassign ‘start’ with the NEWNODE so |Step 5: |
|that a link is developed start and new |LINK of PV is assigned with LINK of CURRPTR i.e. make a link |
|node |between the PV and the next node of CURRPTR |
|start = NEWNODE |PV ( LINK = CURRPTR(LINK |
|Step 5: Exit |Step 6: Exit. |
|Search a node based on an item. |Display all the contents of the list. |
| | |
|Step 1: |Step 1: |
|Set CP to START |Set CP to START |
|CP = START |CP = START |
|Step 2: |Step 2: |
|Start searching from the first node |Start displaying from the first node |
|WHILE CP(VAL != ITEM and CP != NULL repeat step3 |WHILE CP not = NULL |
|Step 3: |repeat step3 through step 4 |
|Assign CP to next node of the list |Step 3: |
|CP = CP(LINK |Display the contents |
|Step 4: |WRITE CP( VAL |
|Check if item is found |Step 4: |
|If CP = NULL |Assign CP to next node of the list |
|WRITE “ Item not in the list “ |CP = CP(LINK |
|Else |Step 5: Exit |
|WRITE “ Item found “ | |
|Step 5: Exit | |
Program
|#include |Header Files |
|#include | |
|struct list | |
|{ |Declaration of list as a structure variable. |
|int id; |The list consists of id of type int, name – a |
|char name[10]; |char array, sem of type int. |
|int sem; | |
|struct list *link; | |
|}; | |
|typedef struct list NODE; |Assigns the symbol name Node to the data type |
|NODE *start = NULL; |definition struct list. |
|void insrt_beg(); | |
|void delinfo(); | |
|void display(); |Function declarations |
|void search(); | |
|void main() | |
|{ | |
| int ch; | |
| clrscr(); | |
| while(1) | |
| { | |
| printf("1.Insert at beginning\n"); | |
|printf("2.Delete Id info\n"); | |
|printf("3.Search ID\n"); |Menu items |
|printf("4.Display\n"); | |
|printf("5.Exit\n"); | |
| printf("Enter ur choice\n"); |Read choice of menu |
|scanf("%d",&ch); | |
| switch(ch) | |
| { | |
| case 1 : insrt_beg(); break; |Call fn insrt_beg() |
| case 2 : delinfo(); break; |Call fn delinfo() |
| case 3 : search(); break; |Call fn search() |
| case 4 : display(); break; |Call fn display() |
| case 5 : exit(0); break; |Call exit() |
| default : printf("Not a valid choice\n"); | |
| } |End of switch statement |
| } |End of while loop |
|} |End of main fn |
|// Function delinfo | |
|void delinfo() | |
|{ | |
| NODE *curptr,*pptr; |Pointer variables curptr and pptr of the type |
|int idno; |NODE |
|curptr = start; |curptr points to start |
|pptr = NULL; |pptr points to NULL |
| printf("Enter Id to be deleted\n"); |Read the id to be deleted |
|scanf("%d", &idno); | |
| if(start == NULL) |If start is null the list is empty |
|printf("List is Empty\n"); | |
| else if (start->id == idno) |If start is pointing to the id that is equal to |
| |the idno |
| { | |
| start =start->link; |Start is pointed to link |
|printf("\n id deleted\n"); | |
|free(curptr); |The curptr is freed from memory |
|return; | |
| } | |
| Else | |
| { | |
| while((curptr->id != idno) && (curptr !=NULL)) |If the curptr is not pointing to the idno and it |
| |is not equal to NULL, store the value of curptr |
| |in pptr and curptr points to the next node |
| { | |
| pptr = curptr; | |
| curptr = curptr->link; | |
| } | |
| if(curptr == NULL) |If curptr is pointing to NULL the id is not |
|printf("\n id no not found\n"); |found. |
| Else | |
| { |Else the item is deleted. |
| |Value of curptr->link is stored in ptr->link |
| printf("\n id deleted \n"); | |
|pptr->link = curptr->link; | |
| } |End of else |
| } |End of else |
|} |End of function |
|//Function insrt_beg | |
|void insrt_beg() | |
|{ | |
| NODE *newnode; |Initialize newnode and allocate space to it |
|newnode = (NODE *)malloc(sizeof(NODE)); | |
| printf("Enter ID:"); |Read the id to be inserted |
|scanf("%d",&newnode->id); | |
| fflush(stdin); | |
| printf("\nEnter Name:"); | |
|gets(newnode->name); |Read name and semester |
|printf("\nEnter semester:"); | |
|scanf("%d",&newnode->sem); | |
| newnode->link =start; |Since the id is inserted at the beginning newnode|
|start=newnode; |is linked to start |
|} | |
|//Function Search | |
|void search() | |
|{ | |
| NODE *curptr; | |
| int e, c=0; | |
| curptr=start; | |
| if(start==NULL) |If start has the value of NULL the list is empty |
|printf("List is Empty\n"); | |
| Else |If not |
| { | |
| printf("Enter Id to be searched:"); |Read the id to be searched |
|scanf("%d", &e); | |
| while(curptr != NULL) |If curptr not equal to NULL |
| { | |
| if(curptr->id == e) |If the id pointed by curptr is equal to the id |
| { | |
| c=1; | |
|printf("\n Id No : %d Found \n", curptr->id); |Print that the id is found |
|break; | |
| } | |
| curptr=curptr->link; |Point to the next link |
| } | |
| if(c==0) |No id is found |
|printf("\nNO such ID number in the list\n"); | |
| } |End of else |
|} | |
|//Function Display | |
|void display() | |
|{ | |
| NODE *curptr; | |
| curptr=start; | |
| if(start==NULL) |If start has the value of NULL the list is empty |
|printf("List Empty\n"); | |
| Else |If not |
| { | |
| printf("\n LIST \n"); | |
|printf("---------------------------\n"); | |
|printf("STU_ID\tNAME \tSEMESTER"); | |
|printf("\n------\t------\t---------"); | |
| while(curptr != NULL) |If curptr not equal to NULL |
| { | |
| printf("\n%d",curptr->id); | |
|printf("\t%s\t%d",curptr->name,curptr->sem); |Print the information |
|curptr=curptr->link; | |
| } |End of while |
| } |End of else |
| printf("\n \n"); | |
|} | |
Result
|1.Insert at beginning |1.Insert at beginning |1.Insert at beginning |
|2.Delete Id info |2.Delete Id info |2.Delete Id info |
|3.Search ID |3.Search ID |3.Search ID |
|4.Display |4.Display |4.Display |
|5.Exit |5.Exit |5.Exit |
|Enter ur choice: 1 |Enter ur choice: 1 |Enter ur choice: 4 |
|Enter ID:12 |Enter ID:13 |LIST |
|Enter Name: Lekha |Enter Name: Manish |-------------------------------------- |
|Enter semester:4 |Enter semester:4 |STU_ID NAME SEMESTER |
| | |---------- --------- --------------- |
| | |13 Manish 4 |
| | |12 Lekha 4 |
|1.Insert at beginning |1.Insert at beginning |1.Insert at beginning |
|2.Delete Id info |2.Delete Id info |2.Delete Id info |
|3.Search ID |3.Search ID |3.Search ID |
|4.Display |4.Display |4.Display |
|5.Exit |5.Exit |5.Exit |
|Enter ur choice: 3 |Enter ur choice: 2 |Enter ur choice: 3 |
|Enter Id to be searched: 12 |Enter Id to be deleted: 12 |Enter Id to be searched:12 |
|Id No : 12 Found |id deleted |NO such ID number in the list |
|1.Insert at beginning |1.Insert at beginning | |
|2.Delete Id info |2.Delete Id info | |
|3.Search ID |3.Search ID | |
|4.Display |4.Display | |
|5.Exit |5.Exit | |
|Enter ur choice: 4 |Enter ur choice: 5 | |
|LIST | | |
|-------------------------------------- | | |
|STU_ID NAME SEMESTER | | |
|---------- --------- --------------- | | |
|13 Manish 4 | | |
Linked Implementation of Stacks
The operation of adding the element in the beginning of the list is similar to pushing the element into a stack. The stack can be accessed only thru the top element. The list can be accessed only from the pointer to its first element.
The operation of deleting the first element from the linked list is similar to popping the element from the stack. The only immediately accessible element is removed and the next element becomes immediately accessible.
The stack can be represented as a linear linked list. The first node of the list is the top of the stack.
| |push(s,x) |
|If the external pointer s points to the linked list, the operation push(s, | |
|x) can be implemented as | |
| |p =getnode(); |
| |info(p)=x; |
| |next(p)=s; |
| |s=p; |
| | |
| |if (empty(s)) |
| | |
|The operation empty(s) will test whether s is equal to null. The operation x| |
|= pop(s) removes the first node from a non empty list and signals the | |
|underflow condition if the list is empty. | |
| |{ |
| | printf(“Stack underflow”); |
| | exit(1); |
| |} |
| |Else |
| |{ |
| |p = s; s = next(p); |
| |x = info(p); |
| |freenode(p); |
| |} |
The stack implemented as a linked list.
| Info next Info next Info next |
|Stack |
| |
| |
| |
|Stack |
The advantage of the implementation of stacks as linked lists is that all the stacks used by the program can share the same available list. When any stack needs a node, it can obtain it from a single available list. When the stack no longer needs a node it returns the node to that available list.
This is possible only when the total amount of space needed by all the stacks at any one time is less than the amount of space initially available to them. The stacks are able to grow and shrink to any size. There is no space preallocated to any single stack. No stack will be using any space which it does not need.
Getnode and Freenode operations
Computers do not have an infinite amount of storage and cannot manufacture extra storage for immediate use. The function of freenode is to make a node that is no longer used currently be reused in another context.
The nodes cannot be accessed by the programmer without the getnode and freenode operations. The nodes that are available for access is implemented as a stack using linked list. The list is linked together by the next field in each node.
The getnode operation removes the first node from this list and makes that node available for use. The freenode operation adds the unused node to the front of the list and makes the node available for reallocation by the getnode. The list of available nodes is called available list.
|if(avail==null) |
|{ |
| printf(“Overflow”); |
| exit(1); |
|} |
|p= avail; |
|avail = next(avail); |
When the available list is empty it means that all the nodes are currently in use and a new allocation cannot be done. When a program calls the getnode in this situation there is an overflow condition.
p = getnode(); can be implemented as
|next(p) = avail; |
|avail = p; |
freenode(p); can be implemented as
Program to implement stack as a linked list
|#include |Header Files |
|#include | |
|struct list |Declaration of the list as a structure containing |
|{ |- Integer to hold the elements of the list- info |
|int info; | |
|struct list *link; | |
|}; | |
|int c=0; |global variable |
|typedef struct list NODE; |Assigning the node to the data type definition struct list |
|NODE *start = NULL,*curptr; | |
|void push(); | |
|void pop(); | |
|void display(); | |
|void main() | |
|{ | |
| int ch; | |
| clrscr(); | |
| printf("\n Stack Size = 4"); | |
| while(1) | |
| { | |
| printf("\n1.Push"); | |
|printf("\n2.Pop"); | |
|printf("\n3.Display"); | |
|printf("\n4.Exit"); | |
| printf("\nEnter choice:"); | |
|scanf("%d",&ch); | |
| switch(ch) | |
| { | |
| case 1 : if(cinfo); | |
| newnode->link =start; | |
|start=newnode; | |
|} | |
| | |
|void pop() | |
|{ | |
| NODE *curptr, *preptr; | |
| c=c-1; | |
| if(start!=NULL) | |
|printf("The deleted item is %d\n",start->info); | |
| if(start==NULL) | |
|printf("Stack is empty\n"); | |
| Else | |
| { | |
| curptr=start; | |
|start = start->link; | |
|free(curptr); | |
| } | |
|} | |
| | |
|void display() | |
|{ | |
| NODE *curptr; | |
| clrscr(); | |
| curptr=start; | |
| if(start==NULL) | |
|printf("Stack Empty\n"); | |
| Else | |
| { | |
| printf("\nNumber of elements :%d\n",c); | |
|printf("\nStack\n"); | |
|printf("------\n\n\n"); | |
|printf("Start "); | |
| while(curptr!=NULL) | |
| { | |
| printf(" --> %d",curptr->info); | |
|curptr=curptr->link; | |
| } | |
| printf("\n\n"); | |
| } | |
|} | |
Linked List Implementation of Queues
The items are deleted from the front of the queue and inserted at the rear. The pointer to the first element of a list represents the front of the queue. The pointer to the last element of the list represents the rear of the queue.
| rear |
| |
|Front |
The queue q consists of a list and two pointers – q.front and q.rear. The operations empty(q) and x=remove(q) are similar to empty(s) and x=pop(s) with s replacing q. When the last element is removed from the queue both q.front and q.rear should be set to null.
|if(empty(q)) |
|{ |
| printf(“Queue Underflow”); |
| exit(1); |
|} |
|p = q.front; |
|x = info(p); |
|q.front = next(p); |
|if(q.front==null) |
| q.rear=null; |
|freenode(p); |
|return(x); |
x = remove(q); can be implemented as
|p= getnode(); |
|info(p)=x; |
|next(p)=null; |
|if(q.rear==null) |
| q.front=p; |
|Else |
| next(q.rear)=p; |
|q.rear=p; |
insert(q, x) is implemented as
After the insertion the queue now has a new entry.
| rear |
| |
|Front |
| |
Disadvantages
1. It occupies more storage than an array. This is because a node in the list contains two fields – info and next. The array contains only one field to store the information.
2. Additional time is spent in managing the available list. Each addition and deletion of the element from a stack or a queue involves the corresponding addition and deletion to the available list.
Advantages
1. All stacks and queues of a program will have the access to the same available free nodes list.
2. Nodes not used by a stack may be used by another as long as the total number of nodes in use at any time is not greater than the total number of nodes available for that program.
Linked list as a data structure
An item is accessed in a linked list by traversing from the beginning. The advantage of a list over an array occurs when it is necessary to insert or delete an element in the middle of a group of other elements.
Linked Lists
Inserting and removing nodes from a list, Linked implementation of stacks, Getnode and Free node operations, Linked implementation of queue, , Example of list operations, Header nodes.
-----------------------
A
B
A
C
B
A
C
B
A
D
C
B
A
C
B
A
--top
--top
--top
--top
--top
D
C
B
A
E
B
A
D
C
BB
C
B
C
B
A
5
43
2
1
0
C
B
A
Que.front=0
Que.rear=-1
5
43
2
1
0
5
43
2
1
0
F
E
D
C
5
43
2
1
0
C
Que.rear=2
Que.front=0
Que.front=Que.rear=2
5
43
2
1
0
F
E
D
C
Que.rear=5
Que.front=2
5
43
2
1
0
Que.rear=Que.front=5
Que.rear = 5
Que.front = 2
F
E
D
C
G
5
43
2
1
0
Que.front = 2
Que.rear = 0
F
G
5
43
2
1
0
Que.front = 5
Que.rear = 0
Que.front = 5
Que.rear = 1
F
H
G
5
43
2
1
0
Que.rear =1
Que.front=0
H
G
5
43
2
1
0
Que.rear = 5
Que.front = 1
F
E
D
C
5
43
2
1
0
F
E
D
C
G
5
43
2
1
0
Que.front = 1
Que.rear = 0
Que.front = Que.rear = 1
F
E
D
C
H
G
5
43
2
1
0
3 null
3 null
2
3 null
2
1
1
4
3 null
2
1
4
3 null
2
1
4
3 null
2
1
2
1
4
3 null
2
1
3 null
'+,MNQR
2
Linear Queue
3 null
3 null
2
1
2
Queue
Priority Queue
2
1
3 null
2
1
3 null
Double ended Queue
Circular Queue
3 null
2
1
1
4
3 null
2
1
4
1
2
3 null
Descending
Ascending
Input-restricted
Output-restricted
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- data analysis using excel
- using sas for data analysis
- using excel for data analysis
- aggregating data using queries
- using c code in unity
- c using tuple
- data analytics using excel examples
- analyzing data using excel
- find data value using z score
- data analysis using spss pdf
- c using strings
- data structure using java