21BCS3268 | CSH-211 | Unit 1 practicals

exp1.1.cpp

/*menu driven program to implement various operations on a linear array*/
#include <iostream>
#define MAX_CAPACITY 10

int arr[MAX_CAPACITY];
unsigned int len = 0;

/**
1) shift elements to the right
2) insert element at position
*/
void insert(int position, int element) {
  if (len == MAX_CAPACITY) {
    std::cout << "Array is full\n";
    return;

  } else if (position >= MAX_CAPACITY || position > len) {
    std::cout << "Invalid value for position\n";
    return;
  }

  if (len != 0) {
    // shift to the right
    for (int k = len - 1; k >= position; k--) {
      arr[k + 1] = arr[k];
    }
  }

  arr[position] = element;
  len++;
}

/** 
shift all elements to the left by one step
*/
void delete_at(int position) {
  if (len == 0) {
    std::cout << "Array is empty\n";
    return;

  } else if (position >= len) {
    std::cout << "Invalid value for position\n";
    return;
  }

  for (int k = position; k < len; k++) {
    arr[k] = arr[k + 1];
  }

  len--;
}

void insert_at_start() {
  int element;
  std::cout << "Enter element: ";
  std::cin >> element;

  insert(0, element);
}

void insert_at_position() {
  int position, element;

  std::cout << "Enter position: ";
  std::cin >> position;

  std::cout << "Enter element: ";
  std::cin >> element;

  insert(position, element);
}

void delete_by_position() {
  int position;
  std::cout << "Enter position: ";
  std::cin >> position;

  delete_at(position);
}

void delete_by_value() {
  int position = -1, value;
  std::cout << "Enter value: ";
  std::cin >> value;

  for (int k = 0; k < len; k++) {
    if (arr[k] == value) {
      position = k;
      break;
    }
  }

  if (position != -1) {
    delete_at(position);
  }
}

void display_elements() {
  if (len == 0) {
    std::cout << "No elements in array\n";
    return;
  }

  std::cout << "Elements: ";
  for (int i = 0; i < len; i++) {
    std::cout << arr[i] << ' ';
  }

  std::cout << '\n';
}

int main() {
  // print menu
  std::cout << "Select one of the following\n"
               "1) Add new element\n\t a) At the beginning\t b) At a position\n"
               "2) Delete using\n\t a) Value\t b) Position\n"
               "3) Display elements\n"
               "4) Exit\n";

  while (true) {
    char choice;

    std::cout << "\nEnter your choice: ";
    std::cin >> choice;

    switch (choice) {
    case '1':
      std::cout << "(a)At the beginning/(b)At a position? ";
      std::cin >> choice;

      switch (choice) {
      case 'a':
        insert_at_start();
        break;
      case 'b':
        insert_at_position();
        break;
      }
      
      break;
    case '2':
      std::cout << "(a)Value/(b)Position? ";
      std::cin >> choice;

      switch (choice) {
      case 'a':
        delete_by_value();
        break;
      case 'b':
        delete_by_position();
        break;
      }

      break;
    case '3':
      display_elements();
      break;
    case '4':
      return 0;
    default:
      std::cout << "Invalid Input\n";
    }
  }
} 

exp1.2.cpp

/*demonstrate the use of linear and binary search to search a given element
in an array*/
#include <iostream>
#include <string>
#include <vector>

/*Check if given vector is sorted in ascending order*/
bool isAscSorted(std::vector<int> arr) {
  for (int i = 0; i < arr.size() - 1; i++) {
    if (arr[i] > arr[i + 1])
      return false;
  }
  return true;
}

/*Linearly traverse array and return index of 'x' if found.
Else return -1*/
int linear_search(std::vector<int> arr, int x) {
  for (int i = 0; i < arr.size(); i++) {
    if (arr[i] == x) {
      return i;
    }
  }
  return -1;
}

/* Search for element x using binary search algorithm.
Return -1 if not found.
Assume given vector/array is sorted.*/
int binary_search(std::vector<int> arr, int x) {
  // left most and right most indices
  int left = 0, right = arr.size() - 1;

  while (left <= right) {
    // to prevent integer overflow
    int mid = left + (right - left) / 2;

    if (arr[mid] == x)
      return mid;

    if (arr[mid] > x)
      right = mid - 1;
    else
      left = mid + 1;
  }
  return -1;
}

int main() {
  int len;
  int x;
  int position;
  std::cout << "Enter array length: ";
  std::cin >> len;

  std::vector<int> arr(len);

  std::cout << "Enter array: ";
  for (int i = 0; i < len; i++) {
    std::cin >> arr[i];
  }

  std::cout << "Enter element to search: ";
  std::cin >> x;

  char choice;
  std::cout
      << "Use\na) Linear Search \t b) Binary Search (array must be sorted)\n";
  std::cout << "Your choice: ";
  std::cin >> choice;

  switch (choice) {
  case 'a':
  case 'A':
    position = linear_search(arr, x);
    break;

  case 'b':
  case 'B':
    if (!isAscSorted(arr)) {
      std::cout << "Given array is not sorted. Using linear search\n";
      position = linear_search(arr, x);
      break;
    }
    position = binary_search(arr, x);
    break;
  default:
    std::cout << "Invalid Input. Using linear search\n";
    position = linear_search(arr, x);
  }

  std::cout << (position == -1
                    ? "Element doesn't exist in array"
                    : "Element is in position: " + std::to_string(position));
  std::cout << '\n';
}

exp1.3.cpp

#include <iostream>

class Node {
public:
  int data;
  Node *next;

  Node() {}
  Node(int data) {
    this->data = data;
    this->next = nullptr;
  }
} * linkedList;

int length = 0;

/*Display all elements forming a linked list starting with
head.*/
void displayAll(Node *head) {
  if (!head) {
    std::cout << "No elements to display\n";
    return;
  }
  Node *tempHead = head;

  while (tempHead != nullptr) {
    std::cout << tempHead->data << ' ';
    tempHead = tempHead->next;
  }

  std::cout << '\n';
}

/*Return position of first node which has given data.
Return -1 if not found.*/
int search(int data) {
  int position = 0;

  Node *tempHead = linkedList;
  while (tempHead) {
    if (tempHead->data == data) {
      break;
    }

    tempHead = tempHead->next;
    position++;
  }
  if (!tempHead)
    position = -1;

  return position;
}

/*insert element while keeping sorted order in mind*/
void insert(Node *element) {
  length++;
  if (linkedList == nullptr)
    linkedList = element;

  else {
    Node *tempHead = linkedList;
    if (linkedList->data > element->data) {
      element->next = linkedList;
      linkedList = element;

    } else {
      while (tempHead->next != nullptr) {
        if (element->data < tempHead->next->data) {
          element->next = tempHead->next;
          tempHead->next = element;
          return;
        }
        tempHead = tempHead->next;
      }
      // tempHead->next is nullptr
      // element->data is greatest in size, append at back
      tempHead->next = element;
    }
  }
}

/*Delete element at position.
Delete last element if position > length.*/
void delNode(int position) {
  if (linkedList == nullptr)
    return;

  Node *tempHead = linkedList;

  if (position == 0) {
    linkedList = linkedList->next;

  } else {
    if (length < position)
      position = length - 1;

    // . . . . i x . .
    // 0 1 2 3 4 5 6 7
    // traverse till 'i'
    for (int i = 0; i < position - 1; i++) {
      tempHead = tempHead->next;
    }

    Node *toRelease = tempHead->next;
    if (!toRelease) // only one element in list
      linkedList = nullptr;
    else
      tempHead->next = toRelease->next;
    delete toRelease;
  }
  length--;
}

int main() {
  char choice;
  std::cout << "Linked List\n"
               "a) Insert a new element\t"
               "b) Delete an existing element (by position)\n"
               "c) Search an element\t"
               "d) Display all elements\n"
               "e) Exit\n";

  while (true) {
    std::cout << "\nYour choice: ";
    std::cin >> choice;

    switch (choice) {
    case 'a':
    case 'b':
    case 'c':
      int val;
      std::cout << "Enter value: ";
      std::cin >> val;

      switch (choice) {
      case 'a':
        insert(new Node(val));
        break;
      case 'b':
        delNode(val);
        break;
      case 'c':
        int position = search(val);
        if (position == -1)
          std::cout << "Element not found";
        else
          std::cout << "Found at position: " << position;
        std::cout << '\n';
        break;
      }
      break;

    case 'd':
      displayAll(linkedList);
      break;
    case 'e':
      return 0;
    default:
      std::cout << "Weird Input\n";
    }
  }
}