SHARE
TWEET

Untitled

a guest Oct 20th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Jevin Olano
  2. // jolano
  3. // CSE 101
  4. // October 24, 2019
  5. // Matrix.c - implementation file for Matrix ADT
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <assert.h>
  10.  
  11. // structs ----------------------------------------------
  12.  
  13. // EntryObj
  14. typedef struct EntryObj {
  15.     int column;
  16.     double value;
  17. } EntryObj;
  18.  
  19. // Entry
  20. typedef EntryObj Entry;
  21.  
  22. // MatrixObj
  23. typedef struct MatrixObj {
  24.     List* rows;
  25.     int size;
  26. } MatrixObj;
  27.  
  28. // Matrix
  29. typedef MatrixObj Matrix;
  30.  
  31. #include "List.h"
  32. #include "Matrix.h"
  33.  
  34. // Constructors & Destructors ---------------------------
  35.  
  36. // Returns a reference to a new nXn Matrix object in the zero state.
  37. Matrix newMatrix(int n) {
  38.     Matrix M = malloc(sizeof(MatrixObj)); // matrix
  39.     M->rows = calloc(n, sizeof(ListObj)); // rows
  40.     for (int i = 0; i < n; i++) {
  41.         M->rows[i] = newList(); // array elements
  42.     }
  43.     M->size = n;
  44.     return M;
  45. }
  46.  
  47. // Frees heap memory associated with *pM, sets *pM to NULL.
  48. void freeMatrix(Matrix* pM) {
  49.     Matrix M = *pM;
  50.     makeZero(M);
  51.     for (int i = 0; i < (M->size); i++) {
  52.         freeList(&(M->rows[i])); // array elements
  53.     }
  54.     free(M->rows); // rows
  55.     free(M); // matrix
  56.     M = NULL;
  57. }
  58.  
  59. // Access Functions -------------------------------------
  60.  
  61. // size()
  62. // Return the size of square Matrix M.
  63. int size(Matrix M) {
  64.     return M->size;
  65. }
  66.  
  67. // NNZ()
  68. // Return the number of non-zero elements in M.
  69. int NNZ(Matrix M) {
  70.     int nonZeroCount = 0;
  71.     for (int i = 0; i < (M-size); i++) {
  72.         nonZeroCount += length(M->rows[i]);
  73.     }
  74.     return nonZeroCount;
  75. }
  76.  
  77. // doubleEquals()
  78. int doubleEquals(double a, double b) {
  79.     return a - b < 0.0000001 ? 1 : 0
  80. }
  81.  
  82.  
  83. // equals()
  84. // Return true (1) if matrices A and B are equal, false (0) otherwise.
  85. int equals(Matrix A, Matrix B) {
  86.     if (size(A) != size(B)) {
  87.         return 0;
  88.     }
  89.     for (int i = 0; i < size(A); i++) {
  90.         List rowA = A->rows[i];
  91.         List rowB = B->rows[i];
  92.         if (length(rowA) != length(rowB)) {
  93.             return 0;
  94.         }
  95.         moveFront(rowA);
  96.         moveFront(rowB);
  97.         while (get(rowA) != NULL) {
  98.             Entry entryA = (Entry) get(rowA);
  99.             Entry entryB = (Entry) get(rowB);
  100.             if (entryA->column != entryB->column || doubleEquals(entryA->value, entryB->value) == 0) {
  101.                 return 0;
  102.             }
  103.             moveNext(rowA);
  104.             moveNext(rowB);
  105.         }
  106.     }
  107.     return 1;
  108. }
  109.  
  110. // Manipulation Procedures ------------------------------
  111.  
  112. // makeZero()
  113. // Re-sets M to the zero Matrix.
  114. void makeZero(Matrix M) {
  115.     for (int i = 0; i < (M->size); i++) {
  116.         moveFront(M->rows[i]);
  117.         while (get(M->rows[i]) != NULL) {
  118.             free(get(M->rows[i]));
  119.             moveNext(M->rows[i]);
  120.         }
  121.         clear(M->rows[i]); // array elements
  122.     }
  123. }
  124.  
  125. // newEntry()
  126. Entry newEntry(int column, double value) {
  127.     Entry entry = malloc(sizeof(EntryObj));
  128.     entry->column = column;
  129.     entry->value = value;
  130.     return entry;
  131. }
  132.  
  133. // changeEntry()
  134. // Changes the ith row, jth column of M to the value x.
  135. // Pre: 1<=i<=size(M), 1<=j<=size(M)
  136. void changeEntry(Matrix M, int i, int j, double x) {
  137.     if (i < 1 || i > size(M)) {
  138.         fprintf(stderr, "Error: row number is out of bounds\n");
  139.         exit(1);
  140.     }
  141.     if (j < 1 || j > size(M)) {
  142.         fprintf(stderr, "Error: column number is out of bounds\n");
  143.         exit(1);
  144.     }
  145.     List row = M->rows[i-1];
  146.     if (isEmpty(row)) {
  147.         Entry entry = newEntry(j, x);
  148.         append(row, entry);
  149.     } else {
  150.         moveFront(row);
  151.         int append = 1;
  152.         while (get(row) != NULL) {
  153.             Entry entry = (Entry) get(row);
  154.             if (entry->column == j) {
  155.                 entry->value = x;
  156.                 append = 0;
  157.             } else if (entry->column < j) {
  158.                 moveNext(row);
  159.             } else {
  160.                 insertBefore(row, entry);
  161.                 append = 0;
  162.             }
  163.             if (append == 1) {
  164.                 append(row, entry);
  165.             }
  166.         }
  167.     }
  168. }
  169.  
  170. // Matrix Arithmetic Operations -------------------------
  171.  
  172. // copy()
  173. // Returns a reference to a new Matrix object having the same entries as A.
  174. Matrix copy(Matrix A) {
  175.     Matrix B = newMatrix(size(A));
  176.     for (int i = 0; i < size(A); i++) {
  177.         List rowA = A->rows[i];
  178.         List rowB = B->rows[i];
  179.         moveFront(rowA);
  180.         while (get(rowA) != NULL) {
  181.             Entry entryA = (Entry) get(rowA);
  182.             Entry entryB = newEntry(entryA->column, entryA->value);
  183.             append(rowB, entryB);
  184.             moveNext(rowA);
  185.         }
  186.     }
  187.     return B;
  188. }
  189.  
  190. // transpose()
  191. // Returns a reference to a new Matrix object representing the transpose of A.
  192. Matrix transpose(Matrix A) {
  193.     Matrix B = newMatrix(size(A));
  194.     for (int i = 0; i < size(A); i++) {
  195.         List rowA = A->rows[i];
  196.         moveFront(rowA);
  197.         while (get(rowA) != NULL) {
  198.             Entry entryA = (Entry) get(rowA);
  199.             List rowB = B->rows[entryA->column - 1];
  200.             Entry entryB = newEntry(i + 1, entryA->value);
  201.             append(rowB, entryB);
  202.             moveNext(rowA);
  203.         }
  204.     }
  205.     return B;
  206. }
  207.  
  208. // scalarMult()
  209. // Returns a reference to a new Matrix object representing xA.
  210. Matrix scalarMult(double x, matrix A) {
  211.     for (int i = 0; i < size(A); i++) {
  212.         List rowA = A->rows[i];
  213.         moveFront(rowA);
  214.         while (get(rowA) != NULL) {
  215.             Entry entry = (Entry) get(rowA);
  216.             entry->value *= x;
  217.             moveNext(rowA);
  218.         }
  219.     }
  220. }
  221.  
  222. // sum()
  223. // Returns a reference to a new Matrix object A+B
  224. // pre: size(A) == size(B)
  225. Matrix sum(Matrix A, Matrix B) {
  226.     if (size(A) != size(B)) {
  227.         fprintf(stderr, "Error: calling sum() on matrices of different size\n");
  228.         exit(1);
  229.     }
  230.     Matrix C = newMatrix(size(A));
  231.     for (int i = 0; i < size(A); i++) {
  232.         double *pSums = calloc(size(A), sizeof(double));
  233.  
  234.         List rowA = A->rows[i];
  235.         moveFront(rowA);
  236.         while (get(rowA) != NULL) {
  237.             Entry entry = (Entry) get(rowA);
  238.             pSums[entry->column - 1] = entry->value;
  239.             moveNext(rowA);
  240.         }
  241.  
  242.         List rowB = B->rows[i];
  243.         moveFront(rowB);
  244.         while (get(rowB) != NULL) {
  245.             Entry entry = (Entry) get(rowB);
  246.             pSums[entry->column - 1] += entry->value;
  247.             moveNext(rowB);
  248.         }
  249.  
  250.         List rowC = C->rows[i];
  251.         for (int j = 0; j < size(A); j++) {
  252.             if (pSums[j] != 0) {
  253.                 Entry sumEntry = newEntry(j + 1, pSums[j]);
  254.                 append(rowC, sumEntry);
  255.             }
  256.         }
  257.  
  258.         free(pSums);
  259.     }
  260. }
  261.  
  262. // diff()
  263. // Returns a reference to a new Matrix object A-B
  264. // pre: size(A) == size(B)
  265. Matrix diff(Matrix A, Matrix B) {
  266.     if (size(A) != size(B)) {
  267.         fprintf(stderr, "Error: calling diff() on matrices of different size\n");
  268.         exit(1);
  269.     }
  270.     Matrix C = newMatrix(size(A));
  271.     for (int i = 0; i < size(A); i++) {
  272.         double *pDiffs = calloc(size(A), sizeof(double));
  273.  
  274.         List rowA = A->rows[i];
  275.         moveFront(rowA);
  276.         while (get(rowA) != NULL) {
  277.             Entry entry = (Entry) get(rowA);
  278.             pDiffs[entry->column - 1] = entry->value;
  279.             moveNext(rowA);
  280.         }
  281.  
  282.         List rowB = B->rows[i];
  283.         moveFront(rowB);
  284.         while (get(rowB) != NULL) {
  285.             Entry entry = (Entry) get(rowB);
  286.             pDiffs[entry->column - 1] -= entry->value;
  287.             moveNext(rowB);
  288.         }
  289.  
  290.         List rowC = C->rows[i];
  291.         for (int j = 0; j < size(A); j++) {
  292.             if (pDiffs[j] != 0) {
  293.                 Entry sumEntry = newEntry(j + 1, pDiffs[j]);
  294.                 append(rowC, sumEntry);
  295.             }
  296.         }
  297.  
  298.         free(pSums);
  299.     }
  300. }
  301.  
  302. // vectorDot()
  303. // Computes the vector dot product of two matrix rows represented by Lists Q and P
  304. double vectorDot(List P, List Q, int size) {
  305.     double *pProducts = calloc(size, sizeof(double));
  306.  
  307.     moveFront(P);
  308.     while (get(P) != NULL) {
  309.         Entry entry = (Entry) get(P);
  310.         pProducts[entry->column - 1] = entry->value;
  311.         moveNext(P);
  312.     }
  313.  
  314.     moveFront(Q);
  315.     while (get(Q) != NULL) {
  316.         Entry entry = (Entry) get(Q);;
  317.         pProducts[entry->column - 1] *= entry->value;
  318.         moveNext(Q);
  319.     }
  320.  
  321.     double product = 0.0;
  322.  
  323.     for (int i = 0; i < size; i++) {
  324.         product += pProducts[i];
  325.     }
  326.  
  327.     free(pProducts);
  328.  
  329.     return product;
  330. }
  331.  
  332. // product()
  333. // Returns a reference to a new Matrix object AB
  334. // pre: size(A) == size(B)
  335. Matrix product(Matrix A, Matrix B) {
  336.     if (size(A) != size(B)) {
  337.         fprintf(stderr, "Error: calling product() on matrices of different size\n");
  338.         exit(1);
  339.     }
  340.  
  341.     Matrix C = newMatrix(size(A));
  342.     Matrix bTr = transpose(B);
  343.  
  344.     for (int i = 0; i < size(A); i++) {
  345.         for (int j = 0; j < size(bTr); j++) {
  346.             Entry dotProduct = newEntry(j + 1, vectorDot(A->rows[i], bTr->rows[j]));
  347.             append(C->rows[i], dotProduct);
  348.         }
  349.     }
  350.     return C;
  351. }
  352.  
  353. // printMatrix()
  354. // Prints a string representation of Matrix M to filestream out. Zero rows // are not printed. Each non-zero is represented as one line consisting
  355. // of the row number, followed by a colon, a space, then a space separated
  356. // list of pairs "(col, val)" giving the column numbers and non-zero values
  357. // in that row. The double val will be rounded to 1 decimal point.
  358. void printMatrix(FILE* out, Matrix M) {
  359.  
  360. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top