Software Engineering Lab – 4
23MCMI16
K DASHRATH
Question 1:
implement 3 concepts of Data Structure Simple Linear, Non-Linear and applicable Tree or
Graph based data Structure.
Linear data structure
• Array
Non-linear data structure
• Heap
Tree or Graph
• Binary Search Tree
Operations: Insertion, Deletion and Traversing
1. Linear data structure: - ArrayExample
Java programming
public class ArrayExample {
int[] arr;
int size;
public ArrayExample(int capacity) {
arr = new int[capacity];
size = 0;
}
void insert(int element, int position) {
if (position > size || position < 0) {
System.out.println("Invalid position");
return;
}
for (int i = size; i > position; i--) {
arr[i] = arr[i - 1];
}
arr[position] = element;
size++;
}
void delete(int position) {
if (position >= size || position < 0) {
System.out.println("Invalid position");
return;
}
for (int i = position; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
size--;
}
void traverse() {
for (int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
ArrayExample array = new ArrayExample(10);
array.insert(10, 0);
array.insert(20, 1);
array.insert(30, 2);
array.insert(40, 3);
array.insert(50, 4);
System.out.print("Array after insertion: ");
array.traverse();
array.delete(1);
System.out.print("Array after deletion: ");
array.traverse();
}
}
Output:
Array after insertion: 10 20 30 40 50
Array after deletion: 10 30 40 50
2. Non-linear data structure: - MaxHeap
Java programming:
public class MaxHeap {
private int[] heap;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity + 1];
size = 0;
}
public void insert(int element) {
if (size == capacity) {
System.out.println("Heap is full. Cannot insert " + element);
return;
}
heap[++size] = element;
int index = size;
while (index > 1 && heap[index] > heap[index / 2]) {
swap(index, index / 2);
index /= 2;
}
}
public int deleteMax() {
if (size == 0) {
System.out.println("Heap is empty");
return -1;
}
int max = heap[1];
heap[1] = heap[size--];
maxHeapify(1);
return max;
}
private void maxHeapify(int index) {
int largest = index;
int left = 2 * index;
int right = 2 * index + 1;
if (left <= size && heap[left] > heap[largest]) {
largest = left;
}
if (right <= size && heap[right] > heap[largest]) {
largest = right;
}
if (largest != index) {
swap(index, largest);
maxHeapify(largest);
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public int peek() {
if (size == 0) {
System.out.println("Heap is empty");
return -1;
}
return heap[1];
}
public void display() {
if (size == 0) {
System.out.println("Heap is empty");
return;
}
System.out.print("Heap elements: ");
for (int i = 1; i <= size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap(10);
heap.insert(50);
heap.insert(30);
heap.insert(20);
heap.insert(15);
heap.insert(60);
heap.insert(10);
heap.display();
System.out.println("Peek Max Element: " + heap.peek());
System.out.println("Max Element Deleted: " + heap.deleteMax());
heap.display();
}
}
Output:
Heap elements: 60 50 20 15 30 10
Peek Max Element: 60
Max Element Deleted: 60
Heap elements: 50 30 20 15 10
3. Trees: - Binary Search Tree
Java programming:
public class BST {
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
Node root;
Node insert(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value < node.data) {
node.left = insert(node.left, value);
} else {
node.right = insert(node.right, value);
}
return node;
}
Node search(Node node, int key) {
if (node == null || node.data == key) {
return node;
}
if (key < node.data) {
return search(node.left, key);
} else {
return search(node.right, key);
}
}
void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.data + " ");
inOrderTraversal(node.right);
}
}
public static void main(String[] args) {
BST bst = new BST();
bst.root = bst.insert(bst.root, 40);
bst.insert(bst.root, 20);
bst.insert(bst.root, 60);
bst.insert(bst.root, 10);
bst.insert(bst.root, 30);
System.out.print("In-Order Traversal: ");
bst.inOrderTraversal(bst.root);
}
}
Output:
In-Order Traversal: 10 20 30 40 60
