In this project we will
design,develop and demonstrates eight queens and knights problem using multi linked lists,heap
and sortings, with appropriate algorithms having following tasks :Firstly, we
implement a program to check rows, columns, diagonals for guarding queens,
Print positions of queens on the game
board using quick sort tail recursion
and stooge sort (array data structure) is a recursive sorting algorithm. It is slower than bubble sort but efficient than slow sort with worst case
time complexity O(n).Secondly, 8 knights is chosen
on the chess board .In order to
do that, the bottom-up version of Merge sort should be used i.e; first merges pairs of adjacent arrays of 1
elements, then merges pairs of adjacent arrays of 2 elements and so on...and in-place of
Mergesort too which doesn't
require allocating any additional memory for sorting. We have to assign
position based on their moves from the
corners. Thirdly, a program is to be implemented to allocate memory for heap and
returns address of heap head structure where heap sort (Non-linear DS)which is similar to selection sort. Data
should be inserted into the heap.Reestablishes heap by moving data in child up
to correct location heap array. The root of heap is to be deleted and data
should be passed to caller. Finally,a program is to be implemented to find
maximum and minimum number moves of queens and knights using non recursive
Quick sort,Bucket Sort , CircularDoublyLinked List , Multilinked List ,
Implementation of Presidents List a. The Time complexity of the routines
developed are compared with other data structures and proved to be efficient.
Introduction
This project is about eight queens and knights tour. Backtracking is an algorithmic
paradigm that tries different solutions until finds a solution that “works”.
Problems which are typically solved using backtracking technique have following
property in common. These problems can only be solved by trying every
possible configuration and each configuration is tried only once. A Naive
solution for these problems is to try all configurations and output a
configuration that follows given problem constraints. Backtracking works in
incremental way and is an optimization over the Naive solution where all
possible configurations are generated and tried. Eight queens are a
classic chess problem in which eight queens are placed on a chess board in
positions such that no queen can capture another queen. get Size: Prompt user
for a valid board size. fill Board: Position chess queens on game board so that
no queen can capture any other queen. Guarded: Checks rows, columns, diagonals
for guarding queens.printBoard: Print positions of chess queens on a game
board. Program to implement the Quick sort using tail recursion. Program to
implement Stooge sort. In the project is
to Solve the problem of a knight's tour without backtracking. Assume that it
starts from a corner of the chessboard.
One can implement Merge sort without a recursion by starting with
merging adjacent elements of a given array, then merging sorted pairs, and so
on. Implement this bottom-up version of Merge sort.
Develop
an in-place version of Merge sort – that is, version that does not use an
auxiliary array and uses only a few additional bookkeeping variables. Implement
an Algorithm that, given an array a consisting
of a stored sub array of size m followed
by a sorted sub array of size n, merges
them into a using an
extra array b of size min {m, n}.
Platform
requirements
Hardware/Software
|
Hardware / Software
element
|
Specification /version
|
Hardware
|
Processor
|
Intel
core to duo
|
RAM
|
1
GB
|
|
Hard
Disk
|
100
GB
|
|
Software
|
OS
|
Windows
XP
|
Java
and NetBeans IDE
|
EFFECIENCY
This software can be more
reliable and efficient. This facilitates the user to register a hall easily.
PROJECT SPECIFICATIONS
Development tool is :Dev c++
Development
language is: c
MODULE
DESCRIPTION
In
the project is to create a Eight Queens
Mainline.This program tests the eight queen’s algorithm. Eight queens is
a classic chess problem in which eightqueens are placed on a chess board in
positions such that no queen can capture another queen .getSize: Prompt user
for a valid board size.fillBoard: Position chess queens on game board so that
no queen can capture any other queen. Guarded: Checks rows, columns, diagonals
for guarding queens.printBoard: Print positions of chess queens on a game
board.
Program to implement the Quick sort using tail
recursion. Program to implement Stooge sort.
In the project is to Solve the problem of a knight's tour without
backtracking. Assume that it starts from a corner of the chessboard. One can implement Merge sort without a
recursion by starting with merging adjacent elements of a given array, then
merging sorted pairs, and so on. Implement this bottom-up version of Merge sort.
Develop
an in-place version of Merge sort – that is, version that does not use an
auxiliary array and uses only a few additional bookkeeping variables. Implement
an Algorithm that, given an array a consisting
of a stored sub array of size m followed
by a sorted sub array of size n, merges them into a using an extra array b of size min {m, n}.
SOURCE CODE
Module 1:
#include<stdio.h>
#include<math.h>
int board[100],count;
int main()
{
int n,i,j;
void queen(int row,int n);
printf("\n\nEnter valid board
size:");
scanf("%d",&n);
queen(1,n);
return 0;
}
void print(int n)
{
int i,j;
printf("\n\nSolution
%d:\n\n",++count);
for(i=1;i<=n;++i)
printf("\t%d",i);
for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j)
{
if(board[i]==j)
printf("\tQ");
else
printf("\t-");
}
}
}
int guard(int row,int column)
{
int i;
for(i=1;i<=row-1;++i)
{
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}
return 1;
}
void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(guard(row,column))
{
board[row]=column;
if(row==n)
print(n);
else
queen(row+1,n);
}
}
}
Stooge sort
#include<stdio.h>
void
stoogesort(int [], int, int);
void
main()
{
int b[7], i;
printf("Enter the values you want to
sort using STOOGE SORT!!!:\n");
for (i = 0;i < 5;i++)
scanf(" %d", &b[i]);
stoogesort(b, 0, 4);
printf("sorted by stooge sort
\n");
for (i = 0;i < 5;i++)
{
printf("%d ", b[i]);
}
printf("\n");
}
void
stoogesort(int a[], int i, int j)
{
int temp, k;
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
if ((i + 1) >= j)
return;
k = (int)((j - i + 1) / 3);
stoogesort(a, i, j - k);
stoogesort(a, i + k, j);
stoogesort(a, i, j - k);
}
Module
2:
1. Solve the problem of a knight's tour
without backtracking. Assume that it starts from a corner of the chessboard.
#include<stdio.h>
int solve(int,int,int);
void print(void);
intnextx(int,int);
intnexty(int,int);
int grid[8][8]={0};
int main()
{
print();
solve(0,0,0);
print();
return
0;
}
int solve(intx,inty,int n)
{
int
m=0;
if(n==64)
{
return
1;
}
if(grid[x][y]==0)
{
while(m<8)
{
if(nextx(x,m)!=-1&&nexty(y,m)!=-1)
{
grid[x][y]=n;
if(solve(nextx(x,m),nexty(y,m),n+1))
{
return
1;
}
}
m++;
}
grid[x][y]=0;
}
return
0;
}
void print(void)
{
inti,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
printf("
%d ",grid[j][i]);
}
printf("
\n ");
}
printf("
\n\n\n ");
}
intnextx(intx,int move)
{
if(move==0)
{
x=x+1;
}
else
if(move==1)
{
x=x+2;
}
else
if(move==2)
{
x=x+2;
}
else
if(move==3)
{
x=x+1;
}
else
if(move==4)
{
x=x-1;
}
else
if(move==5)
{
x=x-2;
}
else
if(move==6)
{
x=x-2;
}
else
if(move==7)
{
x=x-1;
}
if(x<0||x>7)
{
return
-1;
}
else
{
return
x;
}
}
intnexty(inty,int move)
{
if(move==0)
{
y=y-2;
}
else
if(move==1)
{
y=y-1;
}
else
if(move==2)
{
y=y+1;
}
else
if(move==3)
{
y=y+2;
}
else
if(move==4)
{
y=y+2;
}
else
if(move==5)
{
y=y+1;
}
else
if(move==6)
{
y=y-1;
}
else
if(move==7)
{
y=y-2;
}
if(y<0||y>7)
{
return
-1;
}
else
{
return
y;
}
}
Recursive insertion sort
#include <stdio.h>
// Recursive function to sort an array
using
// insertion sort
voidinsertionSortRecursive(intarr[], int
n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive(arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 &&arr[j] >
last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// A utility function to print an array of
size n
voidprintArray(intarr[], int n)
{
for (inti=0; i< n; i++)
// Recursive C++ program for insertion
sort
#include <stdio.h>
// Recursive function to sort an array
using
// insertion sort
insertionSortRecursive(intarr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive(arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 &&arr[j] >
last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// A utility function to print an array of
size n
voidprintArray(intarr[], int n)
{
for (inti=0; i< n; i++)
printf("%d",&a[i]);
}
/* Driver program to test insertion sort
*/
int main()
{
intarr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSortRecursive(arr, n);
printArray(arr, n);
return 0;
}
}
/* Driver program to test insertion sort
*/
int main()
{
intarr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSortRecursive(arr, n);
printArray(arr, n);
return 0;
}
C program to implement Merge Sort without
using Recursion
#include <stdio.h>
#define MAX 30
intmain()
{
intarr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;
printf("Enter
the number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter
element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted
list is : ");
for(i=0;i<n
;i++)
printf("%d",arr[i]);
/*l1
lower bound of first pair and so on*/
for(size=1;
size < n; size=size*2)
{
l1=0;
k=0;/*Index
for temp array*/
while(
l1+size < n)
{
h1=l1+size-1;
l2=h1+1;
h2=l2+size-1;
/*
h2 exceeds the limlt of arr */
if(
h2>=n )
h2=n-1;
/*Merge
the two pairs with lower limits l1 and l2*/
i=l1;
j=l2;
while(i<=h1
&& j<=h2 )
{
if(arr[i]<=arr[j])
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=h1)
temp[k++]=arr[i++];
while(j<=h2)
temp[k++]=arr[j++];
/**Merging
completed**/
/*Take
the next two pairs for merging */
l1=h2+1;
}/*End
of while*/
/*any
pair left */
for(i=l1;
k<n;i++)
temp[k++]=arr[i];
for(i=0;i<n;i++)
arr[i]=temp[i];
printf("\nSize=%d\nElements
are : ",size);
for(i=0;i<n
;i++)
printf("%d",arr[i]);
}/*End
of for loop */
printf("Sorted
list is :\n");
for(i=0;i<n
;i++)
printf("%d",arr[i]);
printf("\n");
return0;
}/*End of main()*/
Module
3 :
struct node* sortedmerge(struct node* a,
struct node* b);
void frontbacksplit(struct node* source,
struct node** frontRef, struct node** backRef);
void mergesort(struct node** headRef){
struct
node* head = *headRef;
struct node* a;
struct node* b;
if
((head == NULL) || (head -> next == NULL))
{
return;
}
frontbacksplit(head, &a, &b);
mergesort(&a);
mergesort(&b);
*headRef = sortedmerge(a, b);
}
struct node* sortedmerge(struct node* a,
struct node* b)
{
struct node* result = NULL;
if (a
== NULL)
return(b);
else if (b == NULL)
return(a);
if ( a-> data <= b -> data)
{
result = a;
result -> next = sortedmerge(a -> next, b);
}
else
{
result = b;
result -> next = sortedmerge(a, b -> next);
}
return(result);
}
void frontbacksplit(struct node* source, struct node** frontRef, struct node** backRef)
{
struct node* fast;
struct node* slow;
if
(source==NULL || source->next==NULL)
{
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source -> next;
while (fast != NULL)
{
fast = fast -> next;
if (fast != NULL)
{
slow = slow -> next;
fast = fast -> next;
}
}
*frontRef = source;
*backRef = slow -> next;
slow -> next = NULL;
}
}
void printlist(struct node *node)
{
while(node != NULL)
{
printf("%d ", node -> data);
node = node -> next;
}
}
void push(struct node** head_ref, int
new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node -> data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
struct node* a = NULL;
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&a, 20);
push(&a, 3);
push(&a, 26775);
mergesort(&a);
printf("\n Sorted Linked List is: \n");
printlist(a);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int
data;
struct Node* next;
};
void sortedInsert(struct Node**, struct
Node*);
void insertionSort(struct Node **head_ref)
{ struct Node *sorted = NULL;
struct Node *current = *head_ref;
while (current != NULL) {
struct Node *next = current->next;
sortedInsert(&sorted, current);
current = next;
}
*head_ref = sorted;
}
void sortedInsert(struct Node** head_ref,
struct Node* new_node)
{
struct Node* current;
if
(*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}void printList(struct Node *head)
{
struct Node *temp = head;
while(temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
void push(struct Node** head_ref, int
new_data)
{ struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
struct Node *a = NULL;
push(&a, 5);
push(&a, 20);
push(&a, 4);
push(&a, 3);
push(&a, 30);
printf("Linked List before sorting
\n");
printList(a);
insertionSort(&a);
printf("\nLinked List after sorting
\n");
printList(a);
return 0;
}
#include<conio.h>
#include<stdio.h>
void main()
{
int i,j,temp,beg,end,mid,item;
int arr[]={34,67,23,1,89,2,36,12,20,61};
clrscr();
for(i=0;i<=9;i++)
{
for(j=i+1;j<=9;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
for(i=0;i<=9;i++)
{
printf("\n%d",arr[i]);
}
printf("Enter the number to find:");
scanf("%d",&item);
beg=0;
end=9;
mid=(int)(end+beg)/2;
while(item!=arr[mid] && beg<=end)
{
if(item>arr[mid])
{
beg=mid+1;
}
else
{
end=mid-1;
}
mid=(int)(end+beg)/2;
}
if(beg<=end)
{
printf("\nPosition is %d",mid+1);
}
else
printf("\nPosition may be become %d",mid+1);
getch();
}
#include<stdio.h>
void main()
{
int i,j,temp,beg,end,mid,item;
int arr[]={34,67,23,1,89,2,36,12,20,61};
clrscr();
for(i=0;i<=9;i++)
{
for(j=i+1;j<=9;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
for(i=0;i<=9;i++)
{
printf("\n%d",arr[i]);
}
printf("Enter the number to find:");
scanf("%d",&item);
beg=0;
end=9;
mid=(int)(end+beg)/2;
while(item!=arr[mid] && beg<=end)
{
if(item>arr[mid])
{
beg=mid+1;
}
else
{
end=mid-1;
}
mid=(int)(end+beg)/2;
}
if(beg<=end)
{
printf("\nPosition is %d",mid+1);
}
else
printf("\nPosition may be become %d",mid+1);
getch();
}
#include <stdio.h>
#include <stdlib.h>
struct bucket
{
int count;
int* value;
};
int compareIntegers(const
void* first, const void* second)
{
int x = *((int*)first), y = *((int*)second);
if (x == y)
{
return 0;
}
else if (x < y)
{
return -1;
}
else
{
return 1;
}
}void bucketSort(int
array[],int n)
{
struct bucket buckets[3];
int i, j, k;
for (i = 0; i < 3; i++)
{
buckets[i].count = 0;
buckets[i].value =
(int*)malloc(sizeof(int) * n);
}
for (i = 0; i < n; i++)
{
if (array[i] < 0)
{
buckets[0].value[buckets[0].count++] = array[i];
}
else if (array[i] > 10)
{
buckets[2].value[buckets[2].count++] = array[i];
}
else
{
buckets[1].value[buckets[1].count++] = array[i];
}
}
for (k = 0, i = 0; i < 3; i++)
{
qsort(buckets[i].value, buckets[i].count,
sizeof(int), &compareIntegers);
for (j = 0; j < buckets[i].count;
j++)
{array[k + j] = buckets[i].value[j];
}
k += buckets[i].count;
free(buckets[i].value);
}
}
int main(char *arg[]) {
int array[100] = { 5, -34,
10, 1, -42, 123, 2, 395, 5, 4, 1234, 7 };
int i = 12,j,k,n;
n=i;
printf("Before Sorting\n");
for (j = 0; j<i; j++)
{
printf("%d ", array[j]);
}
bucketSort(array, n);
printf("\n After
Sorting\n");
for (k = 0; k<i; k++;
printf("%d ", array[k]);
}
Module
4:
BUCKET SORT
#include <stdio.h>
/* Function for bucket sort */
voidBucket_Sort(int array[], int n)
{
inti, j;
int count[n];
for (i = 0; i< n; i++)
count[i] = 0;
for (i = 0; i< n; i++)
(count[array[i]])++;
for (i = 0, j = 0; i< n; i++)
for(; count[i] > 0; (count[i])--)
array[j++] = i;
}
/* End of Bucket_Sort() */
/* The main() begins */
int main()
{
int array[100], i, num;
printf("Enter the size of array :
");
scanf("%d", &num);
printf("Enter the %d elements to be
sorted:\n",num);
for (i = 0; i<num; i++)
scanf("%d", &array[i]);
printf("\nThe array of elements
before sorting : \n");
for (i = 0; i<num; i++)
printf("%d ", array[i]);
printf("\nThe array of elements after
sorting : \n");
Bucket_Sort(array, num);
for (i = 0; i<num; i++)
printf("%d ", array[i]);
printf("\n");
return 0;
}
NON RECURSIVE QUICK SORT
#include<conio.h>
#include<stdio.h>
void main()
{
inti,j,temp,beg,end,mid,item;
intarr[]={34,67,23,1,89,2,36,12,20,61};
clrscr();
/*printf("Enter value:\n");
for(i=0;i<=9;i++)
{
scanf("%d",&arr[i]);
}
*/
for(i=0;i<=9;i++)
{
for(j=i+1;j<=9;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
for(i=0;i<=9;i++)
{
printf("\n%d",arr[i]);
}
printf("Enter the number to
find:");
scanf("%d",&item);
beg=0;
end=9;
mid=(int)(end+beg)/2;
while(item!=arr[mid] &&
beg<=end)
{
if(item>arr[mid])
{
beg=mid+1;
}
else
{
end=mid-1;
}
mid=(int)(end+beg)/2;
}
if(beg<=end)
{
printf("\nPosition is
%d",mid+1);
}
else
printf("\nPosition may be become
%d",mid+1);
getch();
}
C Program to Implement Circular Doubly
Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
intval;
struct node *next;
struct node *prev;
};
typedefstruct node n;
n* create_node(int);
voidadd_node();
voidinsert_at_first();
voidinsert_at_end();
voidinsert_at_position();
voiddelete_node_position();
voidsort_list();
void update();
void search();
voiddisplay_from_beg();
voiddisplay_in_rev();
n *new, *ptr, *prev;
n *first = NULL, *last = NULL;
int number = 0;
void main()
{
intch;
printf("\n linked list\n");
printf("1.insert at beginning \n
2.insert at end\n 3.insert at position\n4.sort linked list\n 5.delete node at
position\n 6.updatenodevalue\n7.search element \n8.displaylist from beginning\n9.display
list from end\n10.exit ");
while (1)
{
printf("\n enter your choice:");
scanf("%d", &ch);
switch (ch)
{
case 1 :
insert_at_first();
break;
case 2 :
insert_at_end();
break;
case 3 :
insert_at_position();
break;
case 4 :
sort_list();
break;
case 5 :
delete_node_position();
break;
case 6 :
update();
break;
case 7 :
search();
break;
case 8 :
display_from_beg();
break;
case 9 :
display_in_rev();
break;
case 10 :
exit(0);
case 11 :
add_node();
break;
default:
printf("\ninvalid choice");
}
}
}
/*
*MEMORY ALLOCATED FOR NODE DYNAMICALLY
*/
n*
create_node(int info)
{
number++;
new = (n *)malloc(sizeof(n));
new->val = info;
new->next = NULL;
new->prev = NULL;
return new;
}
/*
*ADDS NEW NODE
*/
voidadd_node()
{
int info;
printf("\nenter the value you would
like to add:");
scanf("%d", &info);
new = create_node(info);
if (first == last && first ==
NULL)
{
first = last = new;
first->next = last->next = NULL;
first->prev = last->prev = NULL;
}
else
{
last->next = new;
new->prev = last;
last = new;
last->next = first;
first->prev = last;
}
}
/*
*INSERTS ELEMENT AT FIRST
*/
voidinsert_at_first()
{
int info;
printf("\nenter the value to be
inserted at first:");
scanf("%d",&info);
new = create_node(info);
if (first == last && first ==
NULL)
{
printf("\ninitially it is empty
linked list later insertion is done");
first = last = new;
first->next = last->next = NULL;
first->prev = last->prev = NULL;
}
else
{
new->next = first;
first->prev = new;
first = new;
first->prev = last;
last->next = first;
printf("\n the value is inserted at
begining");
}
}
/*
*INSERTS ELEMNET AT END
*/
voidinsert_at_end()
{
int info;
printf("\nenter the value that has to
be inserted at last:");
scanf("%d", &info);
new = create_node(info);
if (first == last && first ==
NULL)
{
printf("\ninitially the list is empty
and now new node is inserted but at first");
first = last = new;
first->next = last->next =
NULL;
first->prev = last->prev = NULL;
}
else
{
last->next = new;
new->prev = last;
last = new;
first->prev = last;
last->next = first;
}
}
/*
*INSERTS THE ELEMENT AT GIVEN POSITION
*/
voidinsert_at_position()
{
int info, pos, len = 0, i;
n *prevnode;
printf("\n enter the value that you
would like to insert:");
scanf("%d", &info);
printf("\n enter the position where
you have to enter:");
scanf("%d", &pos);
new = create_node(info);
if (first == last && first ==
NULL)
{
if (pos == 1)
{
first = last = new;
first->next = last->next =
NULL;
first->prev = last->prev = NULL;
}
else
printf("\n empty linked list you cant
insert at that particular position");
}
else
{
if (number <pos)
printf("\n node cant be inserted as
position is exceeding the linkedlist length");
else
{
for (ptr = first, i = 1;i <=
number;i++)
{
prevnode = ptr;
ptr = ptr->next;
if (i == pos-1)
{
prevnode->next = new;
new->prev = prevnode;
new->next = ptr;
ptr->prev = new;
printf("\ninserted at position %d
succesfully", pos);
break;
}
}
}
}
}
/*
*SORTING IS DONE OF ONLY NUMBERS NOT LINKS
*/
voidsort_list()
{
n *temp;
inttempval, i, j;
if (first == last && first ==
NULL)
printf("\nlinked list is empty no
elements to sort");
else
{
for (ptr = first,i = 0;i <number;ptr =
ptr->next,i++)
{
for (temp =
ptr->next,j=i;j<number;j++)
{
if (ptr->val> temp->val)
{
tempval = ptr->val;
ptr->val = temp->val;
temp->val = tempval;
}
}
}
for (ptr = first, i = 0;i <number;ptr =
ptr->next,i++)
printf("\n%d", ptr->val);
}
}
/*
*DELETION IS DONE
*/
voiddelete_node_position()
{
intpos, count = 0, i;
n *temp, *prevnode;
printf("\n enter the position which u
wanted to delete:");
scanf("%d", &pos);
if (first == last && first == NULL)
printf("\n empty linked list you cant
delete");
else
{
if (number <pos)
printf("\n node cant be deleted at
position as it is exceeding the linkedlist length");
else
{
for (ptr = first,i = 1;i <= number;i++)
{
prevnode = ptr;
ptr = ptr->next;
if (pos == 1)
{
number--;
last->next = prevnode->next;
ptr->prev = prevnode->prev;
first = ptr;
printf("%d is deleted",
prevnode->val);
free(prevnode);
break;
}
else if (i == pos - 1)
{
number--;
prevnode->next = ptr->next;
ptr->next->prev = prevnode;
printf("%d is deleted",
ptr->val);
free(ptr);
break;
}
}
}
}
}
/*
*UPDATION IS DONE FRO GIVEN OLD VAL
*/
void update()
{
intoldval, newval, i, f = 0;
printf("\n enter the value old
value:");
scanf("%d", &oldval);
printf("\n enter the value new
value:");
scanf("%d", &newval);
if (first == last && first ==
NULL)
printf("\n list is empty no elemnts
for updation");
else
{
for (ptr = first, i = 0;i <number;ptr =
ptr->next,i++)
{
if (ptr->val == oldval)
{
ptr->val = newval;
printf("value is updated to %d",
ptr->val);
f = 1;
}
}
if (f == 0)
printf("\n no such old value to be
get updated");
}
}
/*
*SEARCHING USING SINGLE KEY
*/
void search()
{
int count = 0, key, i, f = 0;
printf("\nenter the value to be
searched:");
scanf("%d", &key);
if (first == last && first ==
NULL)
printf("\nlist is empty no elemnets
in list to search");
else
{
for (ptr = first,i = 0;i
<number;i++,ptr = ptr->next)
{
count++;
if (ptr->val == key)
{
printf("\n the value is found at
position at %d", count);
f = 1;
}
}
if (f == 0)
printf("\n the value is not found in
linkedlist");
}
}
/*
*DISPLAYING IN BEGINNING
*/
voiddisplay_from_beg()
{
inti;
if (first == last && first ==
NULL)
printf("\nlist is empty no elemnts to
print");
else
{
printf("\n%d number of nodes are
there", number);
for (ptr = first, i = 0;i
<number;i++,ptr = ptr->next)
printf("\n %d", ptr->val);
}
}
/*
*
DISPLAYING IN REVERSE
*/
voiddisplay_in_rev()
{
inti;
if (first == last && first ==
NULL)
printf("\nlist is empty there are no
elments");
else
{
for (ptr = last, i = 0;i
<number;i++,ptr = ptr->prev)
{
printf("\n%d", ptr->val);
}
}
}
CONCLUSION
By the end of the project
result, an employee of a particular company knows the usage of CPU and its
duration time by generating the process id by using the priority queues/Binary
heap concept. In future too, there will be companies and MNC’s using the completely
duration time and process utilization approach in every facility. This project
based on the duration time and CPU usage is just the start, in future there
will be more easy and advanced approach.
Comments
Post a Comment