First Fit algorithm C++ using linked list

  algorithm, c++, linked-list

I’ve been asked to create a worst fit algorithm using linked list , I’ve found a code which works on the first fit algorithm , how is it possible to change the code below to work on the principle of the worst fit algorithm, I know that the process in worst fit algorithm takes up the largest block size as long as the process size is smaller than the block size.

CODE :

   #include <iostream>
   using namespace std;

   // Two global counters
   int g = 0, k = 0;

   // Structure for free list
   struct free {
   int tag;
   int size;
   struct free* next;
  }*free_head = NULL, * prev_free = NULL;

   // Structure for allocated list
   struct alloc {
   int block_id;
   int tag;
   int size;
   struct alloc* next;
  }*alloc_head = NULL, * prev_alloc = NULL;

   // Function to create free
   // list with given sizes
   void create_free(int c)
{
   struct free* p = (struct free*)
   malloc(sizeof(struct free));
   p->size = c;
   p->tag = g;
   p->next = NULL;
  if (free_head == NULL)
    free_head = p;
  else
    prev_free->next = p;
    prev_free = p;
    g++;
}

   // Function to print free list which
   // prints free blocks of given sizes
   void print_free()
{
   struct free* p = free_head;
   cout << "TagtSizen";
   while (p != NULL) {
   cout << p->tag << "t"
        << p->size << "n";
   p = p->next;
}
}

  // Function to print allocated list which
  // prints allocated blocks and their block ids
  void print_alloc()
{
  struct alloc* p = alloc_head;
   cout << "TagtBlock IDtSizen";
   while (p != NULL) {
    cout << p->tag << "t "
        << p->block_id << "tt"
        << p->size << "n";
    p = p->next;
 }
 }

  // Function to allocate memory to
  // blocks as per First fit algorithm
  void create_alloc(int c)
 {
   // create node for process of given size
   struct alloc* q = (struct alloc*)
    malloc(sizeof(struct alloc));
   q->size = c;
   q->tag = k;
   q->next = NULL;
   struct free* p = free_head;

   // Iterate to find first memory
   // block with appropriate size
   while (p != NULL) {
    if (q->size <= p->size)
        break;
    p = p->next;
}

// Node found to allocate
if (p != NULL) {
    // Adding node to allocated list
    q->block_id = p->tag;
    p->size -= q->size;
    if (alloc_head == NULL)
        alloc_head = q;
    else {
        prev_alloc = alloc_head;
        while (prev_alloc->next != NULL)
            prev_alloc = prev_alloc->next;
        prev_alloc->next = q;
    }
    k++;
}
else // Node found to allocate space from
    cout << "Block of size " << c
    << " can't be allocatedn";
}

// Function to delete node from
// allocated list to free some space
void delete_alloc(int t) 
{
// Standard delete function
// of a linked list node
struct alloc* p = alloc_head, * q = NULL;

// First, find the node according
// to given tag id
while (p != NULL) {
    if (p->tag == t)
        break;
    q = p;
    p = p->next;
}
if (p == NULL)
    cout << "Tag ID doesn't existn";
else if (p == alloc_head)
    alloc_head = alloc_head->next;
else
    q->next = p->next;
struct free* temp = free_head;
while (temp != NULL) {
    if (temp->tag == p->block_id) {
        temp->size += p->size;
        break;
    }
    temp = temp->next;
}
}

  // Driver Code
  int main()
{
   int blockSize[400];
   int processSize[400];
   int blockID,processNum,choice;
   int size;
   do
  {
    cout << "1.Add Block/s";
    cout << "n2.Add Processes";
    cout << "n3.Delete Block/s";
    cout << "n4.Add a Process";
    cout << "n5.Display Information";
    cout << "n6.EXIT";
    cout << "nEnter choice : ";
    cin >> choice;
    switch (choice)
    {
    case 1: cout << "Enter how many Blocks would you like to add : ";
        cin >> size;
        cout << "Enter the size of each Block : ";
        for (int i = 0; i < size; i++)
        {
            cin >> blockSize[i];
            create_free(blockSize[i]);
        }
        break;
    case 2: cout << "Enter how many Processess would you like to add : ";
        cin >> size;
        cout << "Enter the size of each Process : ";
        for (int i = 0; i < size; i++)
        {
            cin >> processSize[i];
            create_alloc(processSize[i]);
        }
        break;
    case 3: cout << "Enter which block to delete : ";
        cin >> blockID;
        delete_alloc(blockID);
        break;
    case 4: cout << "Enter a proccess to add to the Block : ";
        cin >> processNum;
        create_alloc(processNum);
        break;
    case 5: print_alloc();
        break;
    default:
        break;
    }
} while (choice != 6);
}

Source: Windows Questions C++

LEAVE A COMMENT