Assignment 3

Tên: Trần Phạm Quốc Bảo MSSV: 21IT396

Code:

#include <iostream>

#include <stdexcept> // For std::out_of_range

// Node structure for the singly linked list

struct Node {

int data;
 Node* next;

Node(int val) : data(val), next(nullptr) {}

};

// Singly Linked List class

class SinglyLinkedList {

private:

Node* head;

public:

// Constructor

SinglyLinkedList() : head(nullptr) {}

// Destructor to free memory

~SinglyLinkedList() {

Node* current = head;

while (current != nullptr) {

Node* nextNode = current->next;

delete current;

current = nextNode;

head = nullptr;

// a) Add a node at the beginning

void addAtBeginning(int val) {

 Node* newNode = new Node(val);

newNode->next = head;

head = newNode;

// b) Add a node at the end

void addAtEnd(int val) {

Node* newNode = new Node(val);

if (head == nullptr) {

head = newNode;

return;

Node* current = head;

while (current->next != nullptr) {

current = current->next;

current->next = newNode;

// c) Delete the first node

void deleteFirst() {

if (head == nullptr) {

std::cout << "List is empty. Cannot delete first node." << std::endl;

return;

Node* temp = head;

head = head->next;
 delete temp;

// d) Delete the last node

void deleteLast() {

if (head == nullptr) {

std::cout << "List is empty. Cannot delete last node." << std::endl;

return;

if (head->next == nullptr) { // Only one node

delete head;

head = nullptr;

return;

Node* current = head;

while (current->next->next != nullptr) {

current = current->next;

delete current->next;

current->next = nullptr;

// e) Print the list

void printList() const {

if (head == nullptr) {

std::cout << "List is empty." << std::endl;

return;
 }

Node* current = head;

while (current != nullptr) {

std::cout << current->data;

if (current->next != nullptr) {

std::cout << " -> ";

current = current->next;

std::cout << std::endl;

// f) Count the number of nodes

int countNodes() const {

int count = 0;

Node* current = head;

while (current != nullptr) {

count++;

current = current->next;

return count;

// g) Search for a given value

bool search(int val) const {

Node* current = head;

while (current != nullptr) {

 if (current->data == val) {

return true;

current = current->next;

return false;

// h) Search for a given position (returns value at position)

int searchByPosition(int pos) const {

if (pos < 0) {

throw std::out_of_range("Position cannot be negative.");

Node* current = head;

int currentPos = 0;

while (current != nullptr && currentPos < pos) {

current = current->next;

currentPos++;

if (current == nullptr) {

throw std::out_of_range("Position is out of bounds.");

return current->data;

// i) Delete a node at position n

void deleteAtPosition(int pos) {

 if (head == nullptr) {

std::cout << "List is empty. Cannot delete at position." << std::endl;

return;

if (pos == 0) {

deleteFirst();

return;

if (pos < 0) {

std::cout << "Position cannot be negative." << std::endl;

return;

Node* current = head;

Node* prev = nullptr;

int currentPos = 0;

while (current != nullptr && currentPos < pos) {

prev = current;

current = current->next;

currentPos++;

if (current == nullptr) {

std::cout << "Position " << pos << " is out of bounds. Cannot
delete." << std::endl;

return;
 }

// current is the node to be deleted

prev->next = current->next;

delete current;

// j) Insert a node at position n

void insertAtPosition(int val, int pos) {

if (pos < 0) {

std::cout << "Position cannot be negative. Cannot insert." <<

std::endl;

return;

if (pos == 0) {

addAtBeginning(val);

return;

Node* newNode = new Node(val);

Node* current = head;

int currentPos = 0;

// Traverse to the node *before* the insertion point

while (current != nullptr && currentPos < pos - 1) {

current = current->next;

currentPos++;
 }

if (current == nullptr) {

// If current is nullptr here, it means pos is greater than list size + 1

std::cout << "Position " << pos << " is out of bounds. Cannot
insert." << std::endl;

delete newNode; // Clean up memory

return;

newNode->next = current->next;

current->next = newNode;

// l) Append p2 to the end of p1. (This method belongs to p1)

void appendList(SinglyLinkedList& otherList) {

if (otherList.head == nullptr) {

return; // Nothing to append

if (this->head == nullptr) {

this->head = otherList.head;

} else {

Node* current = this->head;

while (current->next != nullptr) {

current = current->next;

}
 current->next = otherList.head;

otherList.head = nullptr; // Ensure otherList doesn't manage these

nodes anymore

// k) Merge two sorted singly linked lists p1 and p2 into a sorted list.

// This is a static method as it creates a new list from two existing ones.

static SinglyLinkedList mergeSortedLists(SinglyLinkedList& list1,

SinglyLinkedList& list2) {

SinglyLinkedList mergedList;

Node* head1 = list1.head;

Node* head2 = list2.head;

Node* currentMerged = nullptr;

// Determine the head of the merged list

if (head1 == nullptr) {

mergedList.head = head2;

list2.head = nullptr; // Detach nodes from original list2

return mergedList;

if (head2 == nullptr) {

mergedList.head = head1;

list1.head = nullptr; // Detach nodes from original list1

return mergedList;

}
if (head1->data <= head2->data) {

mergedList.head = head1;

currentMerged = head1;

head1 = head1->next;

} else {

mergedList.head = head2;

currentMerged = head2;

head2 = head2->next;

// Merge the remaining nodes

while (head1 != nullptr && head2 != nullptr) {

if (head1->data <= head2->data) {

currentMerged->next = head1;

head1 = head1->next;

} else {

currentMerged->next = head2;

head2 = head2->next;

currentMerged = currentMerged->next;

// Attach remaining nodes from either list (if any)

if (head1 != nullptr) {

currentMerged->next = head1;

} else if (head2 != nullptr) {

currentMerged->next = head2;
 }

// Crucially, detach nodes from original lists to prevent

double-free/incorrect ownership

list1.head = nullptr;

list2.head = nullptr;

return mergedList;

};

int main() {

SinglyLinkedList p, p1, p2;

std::cout << "--- Problem 1: Singly Linked List Management ---" <<
std::endl;

std::cout << "\n1. Add nodes to p:" << std::endl;

p.addAtEnd(10);

p.addAtBeginning(5);

p.addAtEnd(20);

p.addAtBeginning(2);

std::cout << "List p after initial additions: ";

p.printList();

std::cout << "\n2. Count nodes in p: " << p.countNodes() << std::endl;
 std::cout << "\n3. Search for value 10 in p: " << (p.search(10) ? "Found" :
"Not Found") << std::endl;

std::cout << "Search for value 15 in p: " << (p.search(15) ? "Found" : "Not
Found") << std::endl;

std::cout << "\n4. Search by position in p:" << std::endl;

try {

std::cout << "Value at position 1: " << p.searchByPosition(1) <<

std::endl;

std::cout << "Value at position 0: " << p.searchByPosition(0) <<

std::endl;

std::cout << "Value at position 3: " << p.searchByPosition(3) <<

std::endl;

} catch (const std::out_of_range& e) {

std::cerr << "Error: " << e.what() << std::endl;

std::cout << "\n5. Delete first node from p:" << std::endl;

p.deleteFirst();

std::cout << "List p after deleting first: ";

p.printList();

std::cout << "\n6. Delete last node from p:" << std::endl;

p.deleteLast();

std::cout << "List p after deleting last: ";

p.printList();

std::cout << "\n7. Insert node at position in p:" << std::endl;

p.insertAtPosition(15, 1);

std::cout << "List p after inserting 15 at pos 1: ";

p.printList();

p.insertAtPosition(1, 0);

std::cout << "List p after inserting 1 at pos 0: ";

p.printList();

p.insertAtPosition(100, 5);

std::cout << "List p after inserting 100 at pos 5: ";

p.printList();

std::cout << "\n8. Delete node at position in p:" << std::endl;

p.deleteAtPosition(1);

std::cout << "List p after deleting at pos 1: ";

p.printList();

p.deleteAtPosition(0);

std::cout << "List p after deleting at pos 0: ";

p.printList();

p.deleteAtPosition(p.countNodes() - 1);

std::cout << "List p after deleting last (via pos): ";

p.printList();

std::cout << "\n9. Append p2 to p1 (function l):" << std::endl;

p1.addAtEnd(1);

p1.addAtEnd(2);

p1.addAtEnd(3);

std::cout << "List p1: "; p1.printList();

 p2.addAtEnd(4);

p2.addAtEnd(5);

std::cout << "List p2: "; p2.printList();

p1.appendList(p2);

std::cout << "List p1 after appending p2: "; p1.printList();

std::cout << "List p2 after appending (should be empty): "; p2.printList();

std::cout << "\n10. Merge two sorted lists (function k):" << std::endl;

SinglyLinkedList sorted1, sorted2;

sorted1.addAtEnd(1);

sorted1.addAtEnd(3);

sorted1.addAtEnd(5);

std::cout << "Sorted List 1: "; sorted1.printList();

sorted2.addAtEnd(2);

sorted2.addAtEnd(4);

sorted2.addAtEnd(6);

std::cout << "Sorted List 2: "; sorted2.printList();

SinglyLinkedList mergedResult =
SinglyLinkedList::mergeSortedLists(sorted1, sorted2);

std::cout << "Merged Sorted List: "; mergedResult.printList();

std::cout << "Sorted List 1 after merge (should be empty): ";

sorted1.printList();

std::cout << "Sorted List 2 after merge (should be empty): ";

sorted2.printList();
 std::cout << "\n--- End of Problem 1 Test ---" << std::endl;

return 0;

Result:
Report:

 Đánh giá biểu thức: Sử dụng cấu trúc dữ liệu Stack (ngăn xếp) để
chuyển đổi biểu thức trung tố (infix) sang hậu tố (postfix) và sau đó tính toán
giá trị của biểu thức hậu tố. Stack được cài đặt bằng Danh sách liên kết để
quản lý linh hoạt các toán tử và toán hạng.

 Kiểm tra dấu ngoặc đơn: Sử dụng Stack để kiểm tra tính hợp lệ của các
cặp dấu ngoặc đơn (), {}, [] trong một biểu thức. Thuật toán đảm bảo mọi
dấu ngoặc mở đều có dấu ngoặc đóng tương ứng và đúng thứ tự.

 Bài toán Josephus: Giải quyết bài toán bằng cách sử dụng cấu trúc dữ
liệu Queue (hàng đợi) để mô phỏng quá trình loại bỏ người trong một vòng
tròn, tìm ra người sống sót cuối cùng.
Code:

#include <iostream>

#include <vector>

#include <algorithm> // For std::sort

// Node structure for the set's linked list

struct SetNode {

int data;

SetNode* next;

SetNode(int val) : data(val), next(nullptr) {}

};

// Integer Set class using a singly linked list

class IntegerSet {

private:

SetNode* head;
 // Private helper to insert in sorted order (and maintain uniqueness)

void insertSortedUnique(int val) {

SetNode* newNode = new SetNode(val);

if (head == nullptr || val < head->data) {

newNode->next = head;

head = newNode;

return;

SetNode* current = head;

SetNode* prev = nullptr;

while (current != nullptr && val >= current->data) {

if (val == current->data) { // Element already exists, maintain

uniqueness

delete newNode; // Don't insert duplicate

return;

prev = current;

current = current->next;

// Insert newNode between prev and current

newNode->next = current;

prev->next = newNode;

}
public:

// Constructor

IntegerSet() : head(nullptr) {}

// Constructor from vector for easy initialization

IntegerSet(const std::vector<int>& elements) : head(nullptr) {

// Sort and insert to ensure unique and sorted property

std::vector<int> sorted_elements = elements;

std::sort(sorted_elements.begin(), sorted_elements.end());

for (int val : sorted_elements) {

addElement(val); // addElement calls insertSortedUnique

// Destructor

~IntegerSet() {

SetNode* current = head;

while (current != nullptr) {

SetNode* nextNode = current->next;

delete current;

current = nextNode;

head = nullptr;

}
 // a) isSet(): checks if s is a set or not.

// Our design (insertSortedUnique) ensures it's always a set (unique &

sorted).

// So this primarily checks internal consistency.

bool isSet() const {

if (head == nullptr) {

return true;

SetNode* current = head;

while (current->next != nullptr) {

if (current->data >= current->next->data) { // Check for sorted and

uniqueness

return false;

current = current->next;

return true;

// b) subset(s1, s2): checks if set s1 is a subset of set s2.

bool isSubset(const IntegerSet& otherSet) const {

SetNode* currentThis = this->head;

SetNode* currentOther = otherSet.head;

while (currentThis != nullptr) {

bool found = false;

while (currentOther != nullptr && currentOther->data <=

currentThis->data) {
 if (currentOther->data == currentThis->data) {

found = true;

break;

currentOther = currentOther->next;

if (!found) {

return false; // Element from this set not found in otherSet

currentThis = currentThis->next;

return true; // All elements of this set found in otherSet

// c) union(s1, s2): returns the union of two sets s1 and s2.

static IntegerSet unionSets(const IntegerSet& s1, const IntegerSet& s2) {

IntegerSet result;

SetNode* currentS1 = s1.head;

SetNode* currentS2 = s2.head;

while (currentS1 != nullptr || currentS2 != nullptr) {

if (currentS1 == nullptr) {

result.addElement(currentS2->data);

currentS2 = currentS2->next;

} else if (currentS2 == nullptr) {

result.addElement(currentS1->data);

currentS1 = currentS1->next;
 } else if (currentS1->data < currentS2->data) {

result.addElement(currentS1->data);

currentS1 = currentS1->next;

} else if (currentS2->data < currentS1->data) {

result.addElement(currentS2->data);

currentS2 = currentS2->next;

} else { // Elements are equal

result.addElement(currentS1->data); // Add once

currentS1 = currentS1->next;

currentS2 = currentS2->next;

return result;

// d) intersection(s1, s2): returns the intersection of two sets s1 and s2.

static IntegerSet intersectionSets(const IntegerSet& s1, const IntegerSet&

s2) {

IntegerSet result;

SetNode* currentS1 = s1.head;

SetNode* currentS2 = s2.head;

while (currentS1 != nullptr && currentS2 != nullptr) {

if (currentS1->data < currentS2->data) {

currentS1 = currentS1->next;

} else if (currentS2->data < currentS1->data) {

currentS2 = currentS2->next;
 } else { // Elements are equal, add to intersection

result.addElement(currentS1->data);

currentS1 = currentS1->next;

currentS2 = currentS2->next;

return result;

// Helper to print the set

void printSet() const {

if (head == nullptr) {

std::cout << "{}";

return;

std::cout << "{";

SetNode* current = head;

while (current != nullptr) {

std::cout << current->data;

if (current->next != nullptr) {

std::cout << ", ";

current = current->next;

std::cout << "}";

}
// Helper to add an element (maintains set properties)

void addElement(int val) {

insertSortedUnique(val);

// Helper to remove an element

void removeElement(int val) {

if (head == nullptr) {

return;

if (head->data == val) {

SetNode* temp = head;

head = head->next;

delete temp;

return;

SetNode* current = head;

SetNode* prev = nullptr;

while (current != nullptr && current->data < val) {

prev = current;

current = current->next;

if (current != nullptr && current->data == val) {

prev->next = current->next;
 delete current;

// Helper to check if an element exists

bool contains(int val) const {

SetNode* current = head;

while (current != nullptr && current->data <= val) {

if (current->data == val) {

return true;

current = current->next;

return false;

};

int main() {

std::cout << "--- Problem 2: Integer Set Management ---" << std::endl;

// Create sets using vector constructor

IntegerSet s1({1, 3, 5, 7, 9});

IntegerSet s2({2, 4, 6, 8, 10});

IntegerSet s3({1, 2, 3, 4, 5});

IntegerSet s4({1, 3, 5});

IntegerSet s5({1, 5, 3}); // Test duplicate handling and sorting

 std::cout << "\nInitial Sets:" << std::endl;

std::cout << "s1: "; s1.printSet(); std::cout << std::endl;

std::cout << "s2: "; s2.printSet(); std::cout << std::endl;

std::cout << "s3: "; s3.printSet(); std::cout << std::endl;

std::cout << "s4: "; s4.printSet(); std::cout << std::endl;

std::cout << "s5 (from {1,5,3}): "; s5.printSet(); std::cout << std::endl;

std::cout << "s5 should be {1, 3, 5} confirming uniqueness and sorting."

<< std::endl;

std::cout << "\n1. isSet() check (a):" << std::endl;

std::cout << "s1 is a set? " << (s1.isSet() ? "Yes" : "No") << std::endl;

std::cout << "s5 is a set? " << (s5.isSet() ? "Yes" : "No") << std::endl;

std::cout << "\n2. isSubset(s1, s2) check (b):" << std::endl;

std::cout << "s4 is subset of s1? " << (s4.isSubset(s1) ? "Yes" : "No") <<
std::endl; // Expected: Yes

std::cout << "s1 is subset of s4? " << (s1.isSubset(s4) ? "Yes" : "No") <<
std::endl; // Expected: No

std::cout << "s2 is subset of s3? " << (s2.isSubset(s3) ? "Yes" : "No") <<
std::endl; // Expected: No

std::cout << "\n3. Union of sets (c):" << std::endl;

IntegerSet union_s1_s2 = IntegerSet::unionSets(s1, s2);

std::cout << "Union of s1 and s2: "; union_s1_s2.printSet(); std::cout <<

std::endl;

IntegerSet union_s1_s3 = IntegerSet::unionSets(s1, s3);

 std::cout << "Union of s1 and s3: "; union_s1_s3.printSet(); std::cout <<
std::endl;

std::cout << "\n4. Intersection of sets (d):" << std::endl;

IntegerSet intersection_s1_s2 = IntegerSet::intersectionSets(s1, s2);

std::cout << "Intersection of s1 and s2: "; intersection_s1_s2.printSet();

std::cout << std::endl;

IntegerSet intersection_s1_s3 = IntegerSet::intersectionSets(s1, s3);

std::cout << "Intersection of s1 and s3: "; intersection_s1_s3.printSet();

std::cout << std::endl;

// Test add/remove/contains

std::cout << "\n5. Testing add/remove/contains:" << std::endl;

IntegerSet mySet;

mySet.addElement(10);

mySet.addElement(20);

mySet.addElement(10); // Duplicate, should not add

mySet.addElement(5);

std::cout << "mySet after additions: "; mySet.printSet(); std::cout <<

std::endl;

std::cout << "mySet contains 10? " << (mySet.contains(10) ? "Yes" : "No")
<< std::endl;

std::cout << "mySet contains 15? " << (mySet.contains(15) ? "Yes" : "No")
<< std::endl;

mySet.removeElement(10);
 std::cout << "mySet after removing 10: "; mySet.printSet(); std::cout <<
std::endl;

mySet.removeElement(15); // Not existing

std::cout << "mySet after trying to remove 15: "; mySet.printSet();

std::cout << std::endl;

std::cout << "\n--- End of Problem 2 Test ---" << std::endl;

return 0;

}
Report:

 Quản lý Danh sách Liên kết Đơn: Triển khai một lớp Danh sách Liên
kết Đơn (SinglyLinkedList) với các thao tác cơ bản và nâng cao. Các chức
năng chính bao gồm thêm/xóa node ở đầu, cuối và tại vị trí bất kỳ; đếm số
node; tìm kiếm giá trị hoặc theo vị trí; nối hai danh sách; và hợp nhất hai
danh sách đã sắp xếp.
 Triển khai Tập hợp số nguyên (Set): Xây dựng một lớp Tập hợp số
nguyên (IntegerSet) sử dụng danh sách liên kết đơn được sắp xếp. Tập hợp
này tự động đảm bảo tính duy nhất của các phần tử. Các thao tác chính bao
gồm kiểm tra tập hợp con, hợp (union) và giao (intersection) của hai tập hợp.