I have an assignment which requires students to conduct matrix multiplication given inputs of dimension mxn followed by the number of nonzero elements on each row. For example, the input
4 5
3 3 5 4 0
3 5 4 7 0
0
2 2 3 6 0
Represents the matrix
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
So far I have written this implementation of linked lists:
//LinkedList.h
#pragma once
#include<iostream>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(NULL) {};
ListNode(int x) : val(x), next(NULL) {};
friend class LinkedList;
};
class LinkedList
{
public:
LinkedList();
void Push_back(int x);
void Push_front(int x);
void Insert(int index, int x);
void Delete(int index);
void Reverse();
void Swap(int index_1, int index_2);
void Print();
int Find(int);
~LinkedList();
private:
ListNode* Head; //first
ListNode* Tail;
};
//LinkedList.cpp
#include "LinkedList.h"
LinkedList::LinkedList() {
// Constructor
Head = NULL;
}
void LinkedList::Push_back(int x) {
// TODO : Insert a node to the end of the linked list, the node¡¦s value is x.
ListNode* temp = new ListNode(x);
if (Head ==0) {
Head = temp;
return;
}
ListNode* current = Head;
while (current->next != 0) {
current = current->next;
}
current->next = temp;
}
void LinkedList::Push_front(int x) {
if (!Head) {
Head = new ListNode(x);
return;
}
ListNode* temp = new ListNode(x);
temp->next = Head;
Head = temp;
}
void LinkedList::Insert(int index, int x) {
// TODO : Insert a node to the linked list at position ¡§index¡¨, the node's
// value is x. The index of the first node in the linked list is 0.
ListNode* temp = new ListNode(x);
temp->val = x;
temp->next = NULL;
if (Head == NULL) {
Head = temp;
}
else if (index == 0) {
temp->next = Head;
Head = temp;
}
else {
ListNode* cur = Head;
int d = 1;
while (cur != NULL) {
if (d == index) {
temp->next = cur->next;
cur->next = temp;
break;
}
cur = cur->next;
d++;
}
}
}
void LinkedList::Delete(int index) {
// TODO : Remove the node with index ¡§index¡¨ in the linked list.
if (Head == NULL)
return;
ListNode* temp = Head;
// If head needs to be removed
if (index == 0) {
Head = temp->next;
temp = 0;
return;
}
// previous node of the node to be deleted
for (int i = 0; temp != NULL && i < index - 1; i++) {
temp = temp->next;
}
// If position is more than number of nodes
if (temp == NULL || temp->next == NULL)
return;
// Node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
ListNode* next = temp->next->next;
// Unlink the node from linked list
free(temp->next); // Free memory
// Unlink the deleted node from list
temp->next = next;
}
void LinkedList::Reverse() {
// TODO : Reverse the linked list.
// Example :
//
// Original List : 1 -> 2 -> 3 -> 4 -> NULL
// Updated List : 4 -> 3 -> 2 -> 1 -> NULL
if (Head == 0 || Head->next == 0) {
return;
}
ListNode *previous = 0;
ListNode *current = Head;
ListNode *preceding = Head->next;
while (preceding != 0) {
current->next = previous;
previous = current;
current = preceding;
preceding = preceding->next;
}
current->next = previous;
Head = current;
}
void LinkedList::Swap(int index_1, int index_2)
{
// TODO : Swap two nodes in the linked list
// Example :
// index_1 : 1 , index_2 : 3
//
// Original List : 1 -> 2 -> 3 -> 4 -> NULL
// Updated List : 1 -> 4 -> 3 -> 2 -> NULL
if (index_1 == index_2) return;
int value_1 = Find(index_1);
int value_2 = Find(index_2);
Delete(index_1);
Insert(index_1, value_2);
Delete(index_2);
Insert(index_2, value_1);
}
void LinkedList::Print() {
cout << "List: ";
// TODO : Print all the elements in the linked list in order.
if (Head == NULL) {
cout << "List empty." << endl;
}
ListNode* current = Head;
while (current != 0) {
cout << current->val << " ";
current = current->next;
}
cout << endl;
}
int LinkedList::Find(int index)
{
ListNode* current = Head;
// the index of the node we're currently
// looking at
int count = 0;
while (current != NULL) {
if (count == index) {
return (current->val);
}
else {
count++;
current = current->next;
}
}
}
LinkedList::~LinkedList()
{
while (Head) {
ListNode* temp = Head;
Head = Head->next;
delete temp;
}
}
I am trying to construct sparse matrices based on the algorithm in E. Horowitz's Fundamentals of Data Structures, Revised Edition though I am having a hard time understanding how matrix operations work with no use of vector/array. Where should I start?
You only really need to define Insert and Multiply:
#include <iostream>
struct Node {
int value;
int row_position;
int column_position;
Node* next;
};
void Insert(Node** head, int row, int col, int value) {
Node* new_node = new Node();
new_node->value = value;
new_node->row_position = row;
new_node->column_position = col;
new_node->next = *head;
*head = new_node;
}
void Multiply(Node* a, Node* b, Node** result) {
Node *ptr_a, *ptr_b;
for (ptr_a = a; ptr_a != nullptr; ptr_a = ptr_a->next) {
for (ptr_b = b; ptr_b != nullptr; ptr_b = ptr_b->next) {
if (ptr_a->column_position == ptr_b->row_position) {
int row = ptr_a->row_position;
int col = ptr_b->column_position;
int sum = 0;
Node* ptr = *result;
bool found = false;
// Check if the position already has a value
while (ptr != nullptr) {
if (ptr->row_position == row && ptr->column_position == col) {
ptr->value += ptr_a->value * ptr_b->value;
found = true;
break;
}
ptr = ptr->next;
}
// If not found, insert new value
if (!found) {
sum = ptr_a->value * ptr_b->value;
Insert(result, row, col, sum);
}
}
}
}
}
void PrintMatrix(Node* head, int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
Node* temp = head;
bool found = false;
while (temp != nullptr) {
if (temp->row_position == i && temp->column_position == j) {
std::cout << temp->value << " ";
found = true;
break;
}
temp = temp->next;
}
if (!found) {
std::cout << "0 ";
}
}
std::cout << '\n';
}
}
void ReadMatrix(Node** head, int& rows, int& cols) {
std::cin >> rows >> cols;
for (int i = 0; i < rows; ++i) {
while (true) {
int col, value;
std::cin >> col;
if (col == 0) break; // A col value of 0 indicates the end of input for the current row
std::cin >> value;
Insert(head, i, col - 1, value); // Adjust column index to be 0-based
}
}
}
void DeleteList(Node* head) {
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
}
Example Usage:
int main() {
Node* a = nullptr;
Node* b = nullptr;
int rows_a, cols_a, rows_b, cols_b;
std::cout << "Enter matrix A:" << '\n';
ReadMatrix(&a, rows_a, cols_a);
std::cout << "Matrix A (" << rows_a << "x" << cols_a << "):" << '\n';
PrintMatrix(a, rows_a, cols_a);
std::cout << "Enter matrix B:" << '\n';
ReadMatrix(&b, rows_b, cols_b);
std::cout << "Matrix B (" << rows_b << "x" << cols_b << "):" << '\n';
PrintMatrix(b, rows_b, cols_b);
if (cols_a != rows_b) {
std::cout << "Matrices cannot be multiplied: incompatible dimensions." << '\n';
DeleteList(a);
DeleteList(b);
return 1;
}
Node* result = nullptr;
Multiply(a, b, &result);
std::cout << "Resultant Matrix (" << rows_a << "x" << cols_b << "):" << '\n';
PrintMatrix(result, rows_a, cols_b);
DeleteList(a);
DeleteList(b);
DeleteList(result);
return 0;
}
Output:
Enter matrix A:
4 5
3 3 5 4 0
3 5 4 7 0
0
2 2 3 6 0
Matrix A (4x5):
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
Enter matrix B:
5 2
1 8 2 7 0
1 6 0
2 5 0
0
1 3 2 4 0
Matrix B (5x2):
8 7
6 0
0 5
0 0
3 4
Resultant Matrix (4x2):
12 31
0 25
0 0
12 30