#include<iostream> using namespace std; class Element { public: int row; int col; int data; }; class Sparse { public: int countElements; Element * elementArr = new Element[10000]; Sparse() { countElements = 0; } void insert(int row , int col, int data) { Element newElem; newElem.row = row; newElem.col = col; newElem.data = data; elementArr[countElements] = newElem; elementArr[0].data = countElements; countElements++; } // void add() }; void display(Sparse* sp) { for (int i = 0; i <= sp->elementArr[0].data ; ++i) { cout << sp->elementArr[i].row << " " << sp->elementArr[i].col << " " << sp->elementArr[i].data; cout << endl; } } void add ( Sparse *s1 , Sparse *s2 , Sparse *s3) { s3->elementArr[0].row = s1->elementArr[0].row; s3->elementArr[0].col = s1->elementArr[0].col; int i = 1; //points to sp1 int j = 1; //points to sp2 int k = 1; //points to sp3 while (i <= s1->elementArr[0].data && j <= s2->elementArr[0].data ) { if (s1->elementArr[i].row < s2->elementArr[j].row) { s3->elementArr[i].row = s1->elementArr[j].row; s3->elementArr[i].col = s1->elementArr[j].col; s3->elementArr[k++] = s1->elementArr[i++]; s3->elementArr[0].data ++; s3->countElements++; } else if (s1->elementArr[i].row > s2->elementArr[j].row) { s3->elementArr[k].row = s2->elementArr[j].row; s3->elementArr[k].col = s2->elementArr[j].col; s3->elementArr[k++] = s2->elementArr[j++]; s3->elementArr[0].data ++; s3->countElements++; } else if (s1->elementArr[i].row == s2->elementArr[j].row) { if (s1->elementArr[i].col < s2->elementArr[j].col) { s3->elementArr[k].row = s1->elementArr[j].row; s3->elementArr[k].col = s1->elementArr[j].col; s3->elementArr[k++] = s1->elementArr[i++]; s3->elementArr[0].data ++; s3->countElements++; } else if (s1->elementArr[i].col > s2->elementArr[j].col) { s3->elementArr[k].row = s2->elementArr[j].row; s3->elementArr[k].col = s2->elementArr[j].col; s3->elementArr[k++] = s2->elementArr[j++]; s3->elementArr[0].data ++; s3->countElements++; } else if (s1->elementArr[i].col == s2->elementArr[j].col) { s3->elementArr[k].row = s2->elementArr[j].row; s3->elementArr[k].col = s2->elementArr[j].col; s3->elementArr[k++].data = s2->elementArr[j++].data + s1->elementArr[i++].data; s3->elementArr[0].data ++; s3->countElements++; } } cout << "hi" << endl; display(s3); cout << endl; } } // void display(Sparse* sp) // { // for (int i = 0; i <= sp->elementArr[0].data ; ++i) // { // cout << sp->elementArr[i].row << " " << sp->elementArr[i].col << " " << sp->elementArr[i].data; // cout << endl; // } // } void transpose(Sparse *s1, Sparse*s3) { //no. of elements in each col of s1 int col_count_s1 = s1->elementArr[0].col + 1; int *col_s1 = new int [col_count_s1] {0}; col_s1[0] = s1->elementArr[0].col; for (int i = 1; i <= s1->elementArr[0].data; ++i) { col_s1[s1->elementArr[i].col]++; //it will act as row element for s2 } // for (int i = 0; i < col_count_s1; ++i) // { // cout << col_s1[i] << " "; // //it will act as row element for s2 // } cout << endl; int *row_index = new int [col_count_s1 + 1]; //one size greater than col_s1; row_index[1] = 1; for (int i = 2; i <= col_count_s1 ; ++i) { row_index[i] = row_index[i - 1] + col_s1[i - 1]; } // for (int i = 0 ; i <= col_count_s1; ++i) // { // cout << row_index[i] << " "; // //it will act as row element for s2 // } cout << endl; cout << endl; for (int i = 0; i <= s1->elementArr[0].data; ++i) { if (i == 0) { s3->elementArr[i].row = s1->elementArr[i].col; s3->elementArr[i].col = s1->elementArr[i].row; s3->elementArr[i].data = s1->elementArr[i].data; } else { int r_index = s1->elementArr[i].col; int index = row_index[r_index]; s3->elementArr[index].row = s1->elementArr[i].col; s3->elementArr[index].col = s1->elementArr[i].row; s3->elementArr[index].data = s1->elementArr[i].data; row_index[r_index]++; } } } void matrix(Sparse *s) { int k = 1; for (int i = 1; i <= s->elementArr[0].row; ++i) { for (int j = 1; j <= s->elementArr[0].col; j++) { if (i == s->elementArr[k].row && j == s->elementArr[k].col) cout << s->elementArr[k++].data << " "; else cout << "0 "; } cout << endl; } } void multiply ( Sparse *s1 , Sparse *s2 , Sparse *s3) { Sparse *s4 = new Sparse(); display(s1); cout << endl; display(s2); cout << endl; s3->insert(s1->elementArr[0].row , s2->elementArr[0].col , 0 ); for (int i = 1; i <= s1->elementArr[0].data; i++ ) { int sum = 0; for (int j = 1; j <= s2->elementArr[0].data; j++) { int sum = 0; if (s1->elementArr[i].col == s2->elementArr[j].row) { sum = s1->elementArr[i].data * s2->elementArr[j].data; s3->insert(s1->elementArr[i].row , s2->elementArr[j].col , sum); } } } display(s3); cout << endl; cout << endl; transpose (s3, s4);//saved in new transpose matrix s4 transpose (s4, s3);//saved in new transpose matrix s3 //now s3 is in sorted order Sparse *s5 = new Sparse(); for (int i = 0; i <= s3->elementArr[0].data; ++i) { if (i == 0) { s5->insert(s3->elementArr[i].row, s3->elementArr[i].col, 0); } else if (i == 1) { s5->insert(s3->elementArr[i].row, s3->elementArr[i].col, s3->elementArr[i].data); } else { int flag = 0; for (int k = 1; k <= s5->elementArr[0].data; k++) { if (s3->elementArr[i].row == s5->elementArr[k].row && s3->elementArr[i].col == s5->elementArr[k].col) { s5->elementArr[k].data += s3->elementArr[i].data; flag = 1; break; } } if (flag == 0) { s5->insert(s3->elementArr[i].row, s3->elementArr[i].col, s3->elementArr[i].data); } } } display(s3); cout << endl; s3 = s5; display(s3); cout << endl; matrix(s3); cout << s3->elementArr[0].row ; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int type; int op; int R1, R2, C1, C2; // do { cout << "What operation do you want to perform? " << " Select Option number. Enter 0 to exit." << endl; cout << "1. Array" << endl; cout << "2. Link list" << endl; cout << "Enter datastructure to use :\n"; cin >> type; cout << "Type of operation :\n"; cout << "1. Addition" << endl; cout << "2. Transpose " << endl; cout << "3. Multiplication " << endl; cin >> op; int data; Sparse *sp1 = new Sparse(); Sparse *sp2 = new Sparse(); int n = 0; if (type == 1 ) { //MATRIX 1 cin >> R1 >> C1; sp1->insert(R1, C1, 0);// FOR Checking #r , #c , #elements for (int i = 1; i <= R1; ++i) { for (int j = 1; j <= C1; ++j) { cin >> data; if (data != 0) sp1->insert(i, j, data); } } if (op == 2)//transpose { Sparse*sp3 = new Sparse(); transpose(sp1 , sp3); display(sp1); cout << endl; display(sp3); cout << endl; // sp1 = sp3; //after transpose just change the pointer matrix(sp1); cout << endl; matrix(sp3); cout << endl; } if (op == 1 || op == 3)//addition or mul { //MATRIX 2 cin >> R2 >> C2; sp2->insert(R2, C2, 0); for (int i = 1; i <= R2; ++i) for (int j = 1; j <= C2; ++j) { cin >> data; if (data != 0) sp2->insert(i, j, data); } Sparse *sp3 = new Sparse();; if (op == 1) //add { if (R1 != R2 || C1 != C2) { cout << " wrong matrix sizes: \n"; return 0; } add(sp1, sp2, sp3); cout << endl; display(sp1); cout << endl; display(sp2); cout << endl; display(sp3); cout << endl; cout << sp1->elementArr[0].data << endl; cout << sp2->elementArr[0].data << endl ; cout << sp3->elementArr[0].data << endl ; matrix(sp1); cout << endl; matrix(sp2); cout << endl; matrix(sp3); cout << endl; } else if (op == 3) //multiplication { if (C1 != R2) { cout << " wrong matrix sizes: \n"; return 0; } multiply(sp1, sp2, sp3); cout << endl; // display(sp1); // cout << endl; // display(sp2); // cout << endl; // display(sp3); // cout << endl; // matrix(sp1); // cout << endl; // matrix(sp2); // cout << endl; // matrix(sp3); // cout << endl; } // for (int i = 0; i < 5 ; ++i) // { // cout << sp3->elementArr[i].row << " " << sp3->elementArr[i].col << " " << sp3->elementArr[i].data; // cout << endl; // } // cout << sp3->elementArr[0].row << " " << sp3->elementArr[0].col << " " << sp3->elementArr[0].data; } } // switch (option) { // case 0: // break; // case 1: // cout << "Enter VALUE of TREE sp to INSERT in AVL Tree: "; // cin >> val; // obj_avl.root = obj_avl.insert(val); // cout << endl; // break; // case 2: // cout << "Enter VALUE of TREE sp to delete in AVL Tree: "; // cin >> val; // obj_avl.root = obj_avl.deleteData(val); // break; // case 3: // cout << "Enter VALUE of TREE sp to search in AVL: "; // cin >> val; // cout << obj_avl.search(val); // break; // default: // cout << "Enter Proper Option number " << endl; // } // } while (option != 0); return 0; }