Scribd
Upload
6 views11 pages

Data Structures Problem Solving

The document outlines the implementation of various Abstract Data Types (ADTs) in C++, including arrays, stacks, linked lists, and queues. It provides functions for basic operations such as adding, removing, searching, and printing elements for each data structure. Additionally, it includes traversal methods for binary trees, demonstrating the use of both array-based and linked-list-based stacks and queues.

Uploaded by

954zjmkzrw
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views11 pages

Data Structures Problem Solving

The document outlines the implementation of various Abstract Data Types (ADTs) in C++, including arrays, stacks, linked lists, and queues. It provides functions for basic operations such as adding, removing, searching, and printing elements for each data structure. Additionally, it includes traversal methods for binary trees, demonstrating the use of both array-based and linked-list-based stacks and queues.

Uploaded by

954zjmkzrw
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Mention the Abstract Data Types (functions) of the following data structures.

Implement these functions in C++ (without classes)

+ Array
+ Stack
+ Linked Lists
+ Queue
+ Traverese inorder, postorder, inorder of the Tree

#include<iostream>
using namespace std ;

int main () {
//constant size
const int size1 = 5;
int arr1[size1] = {5, 3, 2, 9, 7};

//another way
float arr2[] = {3.5, 6.0, 8.9, 23.0, 7.0, 678.9};
int size2 = sizeof(arr2) / sizeof(arr2[0]);

//take size from user


int size3;
cout << "Enter arr3 size: ";
cin >> size3;
char arr3[size3];

//take array 3 from user


for(int i = 0; i < size3; i++){
cout << "Enter arr3[" << i << "]: ";
cin >> arr3[i];
}

//print array 3 elements


for(int i = 0; i < size3; i ++){
cout <<"Arr3[" << i << "] = " << arr3[i] << endl;
}

//arr1 summution of elements


int sum1 = 0;
for(int i = 0; i < size1; i++)
sum1 += arr1[i];
cout << "Arr1 sum = " << sum1 << endl;

//arr1 min element


int Min = arr1[0];
for(int i = 1; i < size1; i++){
if(arr1[i] < Min)
Min = arr1[i];
}
cout << "Arr1 Min = " << Min << endl;

//arr1 max element


int Max = arr1[0];
for(int i = 1; i < size1; i++){
if(arr1[i] > Max)

Page 1 of 11
Max = arr1[i];
}
cout << "Arr1 Max = " << Max << endl;

//arr2 average of element


float sum2 = 0;
for(int i = 0; i < size2; i++)
sum2 += arr2[i];
cout << "Arr2 average = " << sum2 / size2 << endl;

//arr3 search about elemts


char ch;
cout << "Enter character to search in arr3: ";
cin >> ch;
bool found = false;
int index;
for(int i = 0; i < size3; i++){
if(arr3[i] == ch){
found = true;
index = i + 1;
break;
}
}
if(found == true){
cout << ch << " is found at " << index << " index" << endl;
}else{
cout << ch << " is not found at array3" << endl;
}
}
#include <iostream>
using namespace std;

// Function to perform linear search


int linearSearch(int data[], int n, int item) {
int loc = 0; // Initialize location to 0 (not found)

for (int k = 0; k < n; k++) {


if (data[k] == item) {
loc = k + 1; // Found at position k+1 (1-based indexing)
break;
}
}

return loc;
}

int main() {
int data[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int n = sizeof(data) / sizeof(data[0]); // Calculate array size

int item;
cout << "Enter the item to search: ";
cin >> item;

int loc = linearSearch(data, n, item);

if (loc == 0) {
cout << item << " is not in the array DATA." << endl;

Page 2 of 11
} else {
cout << item << " is found at location " << loc << " in the array
DATA." << endl;
}

return 0;
}
#include<iostream>
using namespace std ;

struct Node{
int data;
Node* next;
};

//add node at the beginning of the list


void add_first(Node* &head, int value){
Node* new_node = new Node();
new_node -> data = value;
new_node -> next = NULL;
if(head == NULL){
head = new_node;
}else{
new_node -> next = head ;
head = new_node;
}
}

//add node at the end of the list


void add_last(Node* &head, int value){
Node* new_node = new Node();
new_node -> data = value;
new_node -> next = NULL;
if(head == NULL){
head = new_node;
}else{
Node* current = head;
while(current -> next != NULL){
current = current -> next;
}
current -> next = new_node;
}
}

//remove node from list at any place by value


void remove_node(Node* &head, int value){
if(head == NULL){
cout << "List is empty";
return ;
}
if(head -> data == value){
Node* temp = head;
head = head -> next;
delete temp;
return ;
}

Node* current = head;

Page 3 of 11
while(current -> next != NULL && current -> next -> data != value){
current = current -> next;
}
if(current -> next == NULL)
cout << "Element not Found to delete";

Node* temp = current -> next;


current -> next = temp -> next;
delete temp;

//search node in the list


void search_node(Node* head, int value){
if(head == NULL){
cout << "List is empty";
return ;
}
bool found = false;
int position = 1;
while(head != NULL){
if(head -> data == value){
found = true;
break;
}
position ++;
head = head -> next;
}

if(found){
cout << value << " is found at position " << position << endl;
}else
cout << value << " not found" << endl;
}

//print each value in the list


void print_list(Node* head){
while(head != NULL){
cout << head -> data << " ";
head = head -> next;
}
cout << endl;
}

int main () {
Node* head = NULL;
add_first(head, 3);
add_first(head, 12);
add_first(head, 1);

add_last(head, 22);
add_last(head, 5);
add_last(head, 60);
print_list(head);

remove_node(head, 5);
print_list(head);

Page 4 of 11
search_node(head, 4);
}
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

int stack[MAX_SIZE];
int top = -1;

void push(int value) {


if (top >= MAX_SIZE - 1) {
cout << "Stack overflow" << endl;
return;
}
stack[++top] = value;
}

int pop() {
if (top < 0) {
cout << "Stack underflow" << endl;
return -1; // Error value
}
return stack[top--];
}

int peek() {
if (top < 0) {
cout << "Stack is empty" << endl;
return -1; // Error value
}
return stack[top];
}

int size() {
return top + 1;
}

bool isEmpty() {
return top == -1;
}

#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
};

Node* top = nullptr;

void push(int value) {


Node* newNode = new Node();
if (!newNode) {
cout << "Memory allocation failed" << endl;
return;

Page 5 of 11
}
newNode->data = value;
newNode->next = top;
top = newNode;
}

int pop() {
if (!top) {
cout << "Stack underflow" << endl;
return -1; // Error value
}
Node* temp = top;
int value = temp->data;
top = top->next;
delete temp;
return value;
}

int peek() {
if (!top) {
cout << "Stack is empty" << endl;
return -1; // Error value
}
return top->data;
}

int size() {
int count = 0;
Node* current = top;
while (current) {
count++;
current = current->next;
}
return count;
}

bool isEmpty() {
return top == nullptr;
}

void freeStack() {
while (!isEmpty()) {
pop();
}
}

void testArrayStack() {
cout << "Testing Array Stack:" << endl;
push(10);
push(20);
push(30);

cout << "Top: " << peek() << endl;


cout << "Size: " << size() << endl;
cout << "Pop: " << pop() << endl;
cout << "Pop: " << pop() << endl;
cout << "Is empty? " << (isEmpty() ? "Yes" : "No") << endl;

Page 6 of 11
}

void testLinkedListStack() {
cout << "\nTesting Linked List Stack:" << endl;
push(100);
push(200);
push(300);

cout << "Top: " << peek() << endl;


cout << "Size: " << size() << endl;
cout << "Pop: " << pop() << endl;
cout << "Pop: " << pop() << endl;
cout << "Is empty? " << (isEmpty() ? "Yes" : "No") << endl;

freeStack(); // Clean up memory


}

int main() {
testArrayStack();
testLinkedListStack();
return 0;
}
#include <iostream>
#include <stdexcept>

#define MAX_SIZE 100 // Maximum size of the queue

int queue[MAX_SIZE]; // Array to store the queue


int front = -1; // Front of the queue
int rear = -1; // Rear of the queue

// Function to check if the queue is empty


bool isEmpty() {
return front == -1 && rear == -1;
}

// Function to check if the queue is full


bool isFull() {
return rear == MAX_SIZE - 1;
}

// Function to return the size of the queue


int size() {
if (isEmpty()) return 0;
return rear - front + 1;
}

// Function to insert an object at the rear of the queue


void Enqueue(int o) {
if (isFull()) {
throw std::overflow_error("Queue is full");
}
if (isEmpty()) {
front = rear = 0;
} else {
rear++;
}
queue[rear] = o;

Page 7 of 11
}

// Function to remove and return the object from the front of the queue
int Dequeue() {
if (isEmpty()) {
throw std::underflow_error("Queue is empty");
}
int item = queue[front];
if (front == rear) {
front = rear = -1; // Reset the queue
} else {
front++;
}
return item;
}

// Function to return the front object without removing it


int Front() {
if (isEmpty()) {
throw std::underflow_error("Queue is empty");
}
return queue[front];
}

int main() {
// Example usage
Enqueue(10);
Enqueue(20);
Enqueue(30);

std::cout << "Front element: " << Front() << std::endl;


std::cout << "Dequeued element: " << Dequeue() << std::endl;
std::cout << "Size of queue: " << size() << std::endl;

return 0;
}

#include <iostream>
#include <stdexcept>

#define MAX_SIZE 100 // Maximum size of the queue

int queue[MAX_SIZE]; // Array to store the queue


int front = -1; // Front of the queue
int rear = -1; // Rear of the queue

// Function to check if the queue is empty


bool isEmpty() {
return front == -1 && rear == -1;
}

// Function to check if the queue is full


bool isFull() {
return (rear + 1) % MAX_SIZE == front;
}

Page 8 of 11
// Function to return the size of the queue
int size() {
if (isEmpty()) return 0;
if (front <= rear) {
return rear - front + 1;
} else {
return MAX_SIZE - front + rear + 1;
}
}

// Function to insert an object at the rear of the queue


void Enqueue(int o) {
if (isFull()) {
throw std::overflow_error("Queue is full");
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE; // Circular increment
}
queue[rear] = o;
}

// Function to remove and return the object from the front of the queue
int Dequeue() {
if (isEmpty()) {
throw std::underflow_error("Queue is empty");
}
int item = queue[front];
if (front == rear) {
front = rear = -1; // Reset the queue
} else {
front = (front + 1) % MAX_SIZE; // Circular increment
}
return item;
}

// Function to return the front object without removing it


int Front() {
if (isEmpty()) {
throw std::underflow_error("Queue is empty");
}
return queue[front];
}

int main() {
// Example usage
Enqueue(10);
Enqueue(20);
Enqueue(30);

std::cout << "Front element: " << Front() << std::endl;


std::cout << "Dequeued element: " << Dequeue() << std::endl;
std::cout << "Size of queue: " << size() << std::endl;

Enqueue(40);
std::cout << "Front element after enqueue: " << Front() << std::endl;
std::cout << "Size of queue: " << size() << std::endl;

Page 9 of 11
return 0;
}

#include <iostream>
#include <stdexcept>

struct Node {
int data;
Node* next;
};

Node* front = nullptr; // Front of the queue


Node* rear = nullptr; // Rear of the queue
int queueSize = 0; // Size of the queue

// Function to check if the queue is empty


bool isEmpty() {
return front == nullptr;
}

// Function to return the size of the queue


int size() {
return queueSize;
}

// Function to insert an object at the rear of the queue


void Enqueue(int o) {
Node* newNode = new Node();
newNode->data = o;
newNode->next = nullptr;

if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
queueSize++;
}

// Function to remove and return the object from the front of the queue
int Dequeue() {
if (isEmpty()) {
throw std::underflow_error("Queue is empty");
}
Node* temp = front;
int item = temp->data;

if (front == rear) {
front = rear = nullptr; // Reset the queue
} else {
front = front->next;
}
delete temp;
queueSize--;
return item;

Page 10 of 11
}

// Function to return the front object without removing it


int Front() {
if (isEmpty()) {
throw std::underflow_error("Queue is empty");
}
return front->data;
}

int main() {
// Example usage
Enqueue(10);
Enqueue(20);
Enqueue(30);

std::cout << "Front element: " << Front() << std::endl;


std::cout << "Dequeued element: " << Dequeue() << std::endl;
std::cout << "Size of queue: " << size() << std::endl;

return 0;
}
public static void preOrder(Tree t)
{
if (t != null)
{
visit(t);
preOrder([Link]);
preOrder([Link]);
}
}

public static void inOrder(Tree t)


{
if (t != null)
{
inOrder([Link]);
visit(t);
inOrder([Link]);
}
}

public static void postOrder(Tree t)


{
if (t != null)
{
postOrder([Link]);
postOrder([Link]);visit(t);
}
}

Page 11 of 11

You might also like