Instructions
Requirements and Specifications
Source Code
LIST
//-----------------------------------------------------------------------------
// Nelson Pham, nppham
// 2022 Winter CSE101 PA#4
// List.c
// Implementation file for List ADT
//-----------------------------------------------------------------------------
#include
#include
#include
#include "List.h"
// structs --------------------------------------------------------------------
typedef struct NodeObj* Node;
typedef struct NodeObj{
void* data;
Node prev;
Node next;
}NodeObj;
typedef struct ListObj{
Node front;
Node back;
Node cursorElmt;
int length;
int index; // index of cursor element
}ListObj;
// Constructors-Destructors ---------------------------------------------------
// newNode()
// Returns reference to new Node object. Initializes next and data fields.
Node newNode(int* data){
Node N = malloc(sizeof(NodeObj));
N->data = data;
N->prev = NULL;
N->next = NULL;
return(N);
}
// freeNode()
// Frees heap memory pointed to by *pN, sets *pN to NULL.
void freeNode(Node* pN){
if( pN!=NULL && *pN!=NULL ){
free(*pN);
*pN = NULL;
}
}
List newList(void){ // Creates and returns a new empty List.
List L = malloc(sizeof(ListObj));
L->front = L->back = NULL;
L->cursorElmt = NULL;
L->length = 0;
L->index = -1; // index of cursor element
return(L);
}
void freeList(List* pL){
if (pL != NULL && *pL != NULL){
clear(*pL);
free(*pL);
*pL = NULL;
}
} // Frees all heap memory associated with *pL, and sets
// *pL to NULL.
// Access functions -----------------------------------------------------------
int length(List L){
if (L == NULL){
printf("List Error: calling length() on NULL List reference\n");
exit(EXIT_FAILURE);
}
return(L->length);
} // Returns the number of elements in L.
int index(List L){
if (L == NULL){
printf("List Error: calling index() on NULL List reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
return -1;
}
if (L->cursorElmt != NULL){
return L->index;
}
return -1;
} // Returns index of cursor element if defined, -1 otherwise.
void* front(List L){
if (L == NULL){
printf("List Error: calling front() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling front() on empty List\n");
exit(EXIT_FAILURE);
}
return(L->front->data);
} // Returns front element of L. Pre: length()>0
void* back(List L){
if (L == NULL){
printf("List Error: calling back() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List ErrorL calling back() on empty List\n");
exit(EXIT_FAILURE);
}
return(L->back->data);
} // Returns back element of L. Pre: length()>0
void* get(List L){
if (L == NULL){
printf("List Error: calling get() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling get() on empty List\n");
exit(EXIT_FAILURE);
}
if (index(L) < 0){
printf("List Error: invalid index on List\n");
exit(EXIT_FAILURE);
}
if (L->cursorElmt == NULL){
printf("List Error: calling get() on NULL cursor Element\n");
exit(EXIT_FAILURE);
}
return(L->cursorElmt->data);
} // Returns cursor element of L. Pre: length()>0, index()>=0
int equalsList(List A, List B){
int eq = 0;
Node N = NULL;
Node M = NULL;
if (A==NULL || B==NULL){
printf("List Error: calling equals() on NULL list reference\n");
exit(EXIT_FAILURE);
}
eq = ( A->length == B ->length );
N = A->front;
M = B->front;
while(eq && N != NULL){
eq = (N->data == M->data);
N = N->next;
M = M->next;
}
return eq;
} // Returns true iff Lists A and B are in same
// state, and returns false otherwise.
// Manipulation procedures ----------------------------------------------------
void clear(List L){
if (L==NULL){
printf("List Error: calling clear() on NULL list reference\n");
exit(EXIT_FAILURE);
}
Node N = L->front;
Node M = NULL;
while(N != NULL){
M = N->next;
freeNode(&N);
N = M;
}
// List is back to empty state
L->front = NULL;
L->back = NULL;
L->cursorElmt = NULL;
L->index = -1;
L->length = 0;
} // Resets L to its original empty state.
void set(List L, void* x){
if (L==NULL){
printf("List Error: calling set() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling set() on empty list\n");
exit(EXIT_FAILURE);
}
if (index(L) < 0){
printf("List Error: calling set() with invalid index list\n");
exit(EXIT_FAILURE);
}
L->cursorElmt->data = x;
} // Overwrites the cursor element’s data with x.
// Pre: length()>0, index()>=0
void moveFront(List L){
if (L==NULL){
printf("List Error: calling moveFront() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) > 0){
L->cursorElmt = L->front;
L->index = 0;
}
} // If L is non-empty, sets cursor under the front element,
// otherwise does nothing.
void moveBack(List L){
if (L==NULL){
printf("List Error: calling moveBack() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) > 0){
L->cursorElmt = L->back;
L->index = length(L) - 1;
}
} // If L is non-empty, sets cursor under the back element,
// otherwise does nothing.
void movePrev(List L){
if (L==NULL){
printf("List Error: calling movePrev() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (L->cursorElmt == NULL){
return;
}
if (L->cursorElmt == L->front){
L->cursorElmt = NULL;
L->index = -1;
}
else{
L->cursorElmt = L->cursorElmt->prev;
L->index--;
}
} // If cursor is defined and not at front, move cursor one
// step toward the front of L; if cursor is defined and at
// front, cursor becomes undefined; if cursor is undefined
// do nothing
void moveNext(List L){
if (L==NULL){
printf("List Error: calling moveNext() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if(L->index >= 0){
L->cursorElmt = L->cursorElmt->next;
L->index++;
if(L->index == length(L)){
L->cursorElmt = NULL;
L->index = -1;
}
}
} // If cursor is defined and not at back, move cursor one
// step toward the back of L; if cursor is defined and at
// back, cursor becomes undefined; if cursor is undefined
// do nothing
void prepend(List L, void* x){
Node N = newNode(x);
if (L==NULL){
printf("List Error: calling prepend() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
L->front = N;
L->back = N;
}else{
N->next = L->front;
L->front->prev = N;
L->front = N;
}
L->index++; //increment index of cursor element since everything is being shifted to the right
L->length++;
} // Insert new element into L. If L is non-empty,
// insertion takes place before front element.
void append(List L, void* x){
Node N = newNode(x);
if (L==NULL){
printf("List Error: calling append() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
L->front = L->back = N;
}else{
N->prev = L->back;
L->back->next = N;
L->back = N;
}
L->length++;
} // Insert new element into L. If L is non-empty,
// insertion takes place after back element.
void insertBefore(List L, void* x){
//Node N = newNode(x);
if (L==NULL){
printf("List Error: calling insertBefore() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling insertBefore() on empty list\n");
exit(EXIT_FAILURE);
}
if (index(L) < 0){
printf("List Error: calling insertBefore() on invalid index list\n");
exit(EXIT_FAILURE);
}
if(L->cursorElmt->prev == NULL){
prepend(L, x);
return;
}
Node N = newNode(x);
// Inserting before cursor
N->next = L->cursorElmt;
N->prev = L->cursorElmt->prev;
L->cursorElmt->prev->next = N;
L->cursorElmt->prev = N;
L->index++; // increment index of cursor element
L->length++;
} // Insert new element before cursor.
// Pre: length()>0, index()>=0
void insertAfter(List L, void* x){
//Node N = newNode(x);
if (L==NULL){
printf("List Error: calling insertAfter() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling insertBefore() on empty list\n");
exit(EXIT_FAILURE);
}
if (index(L) < 0){
printf("List Error: calling insertBefore() on invalid index list\n");
exit(EXIT_FAILURE);
}
if (L->cursorElmt->next == NULL){
append(L, x);
return;
}
Node N = newNode(x);
// Insert after cursor
N->next = L->cursorElmt->next;
L->cursorElmt->next->prev = N;
N->prev = L->cursorElmt;
L->cursorElmt->next = N;
L->length++;
} // Insert new element after cursor.
// Pre: length()>0, index()>=0
void deleteFront(List L){
Node N = NULL;
if (L==NULL){
printf("List Error: calling deleteFront() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling deleteFront() on empty list\n");
exit(EXIT_FAILURE);
}
N = L->front;
if (length(L) > 1){
L->front = L->front->next;
L->front->prev = NULL;
}else{
L->front = L->back = NULL;
}
L->length--;
freeNode(&N);
} // Delete the front element. Pre: length()>0
void deleteBack(List L){
Node N = NULL;
if (L==NULL){
printf("List Error: calling deleteBack() on NULL list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling deleteBack() on empty list\n");
exit(EXIT_FAILURE);
}
N = L->back;
if (length(L) > 1){
L->back = L->back->prev;
L->back->next = NULL;
}else{
L->back = L->front = NULL;
}
L->length--;
freeNode(&N);
} // Delete the back element. Pre: length()>0
void delete(List L){
Node N = NULL;
if (L==NULL){
printf("List Error: calling delete() on Null list reference\n");
exit(EXIT_FAILURE);
}
if (length(L) <= 0){
printf("List Error: calling delete() on empty list\n");
exit(EXIT_FAILURE);
}
if (index(L) < 0){
printf("List Error: calling delete() in invalid index\n");
exit(EXIT_FAILURE);
}
N = L->cursorElmt;
L->cursorElmt = NULL;
L->length--;
N->prev->next = N->next;
N->next->prev = N->prev;
L->index = -1;
freeNode(&N);
} // Delete cursor element, making cursor undefined.
// Pre: length()>0, index()>=0
// Other operations -----------------------------------------------------------
void printList(FILE* out, List L){
Node N = NULL;
if (L==NULL){
printf("List Error: calling printList() on NULL list reference\n");
exit(EXIT_FAILURE);
}
for(N=L->front; N != NULL; N = N->next){
fprintf(out, "%p ", N->data);
}
} // Prints to the file pointed to by out, a
// string representation of L consisting
// of a space separated sequence of integers,
// with front on left.
List copyList(List L){
List A = newList();
Node N = NULL;
if (L==NULL){
printf("List Error: calling copyList() on NULL list reference\n");
exit(EXIT_FAILURE);
}
for(N = L->front; N != NULL; N = N->next){
append(A, N->data);
}
return A;
} // Returns a new List representing the same integer
// sequence as L. The cursor in the new list is undefined,
// regardless of the state of the cursor in L. The state
// of L is unchanged.
MATRIX
// Nelson Pham, nppham
// CSE101, PA#4
// Matrix.c
// Matrix.c file to implement all the required functions in Matrix.h
#include
#include
#include
#include "List.h"
#include "Matrix.h"
// Structs for Entry and Matrix
typedef struct EntryObj
{
int column;
double value;
}EntryObj;
typedef struct MatrixObj
{
List *rows; // List of rows of matrix, pointer to a list
int size;
} MatrixObj;
// Creates newEntry with column value and actual value
Entry newEntry(int col, double value)
{
if (col < 0)
{
fprintf(stderr, "Error in newEntry function, col is less than 0\n");
return NULL;
}
Entry a = malloc(sizeof(EntryObj));
a->value = value;
a->column = col;
return a;
}
// Free the entry and set to NULL
void freeEntry(Entry *e){
free(*e);
e = NULL;
}
// newMatrix()
// Returns a reference to a new nXn Matrix object in the zero state.
Matrix newMatrix(int n){
if (n < 0)
{
fprintf(stderr, "Error in newMatrix function, n is less than 0\n");
return NULL;
}
Matrix a = malloc(sizeof(MatrixObj));
a->rows = calloc(n, sizeof(List));
a->size = n;
for (int i = 0; i < n; i++)
{
a->rows[i] = newList();
}
return a;
}
// freeMatrix()
// Frees heap memory associated with *pM, sets *pM to NULL.
void freeMatrix(Matrix* pM){
int i;
for (i = 0; i
List row = (*pM)->rows[i];
int len = length(row);
for (moveFront(row); index(row) != -1; moveNext(row)) {
Entry e = get(row);
freeEntry(&e);
}
freeList(&row);
}
free((*pM)->rows);
free(*pM);
}
// Access functions
// size()
// Return the size of square Matrix M.
int size(Matrix M) {
return M->size;
}
// NNZ()
// Return the number of non-zero elements in M.
int NNZ(Matrix M){
int sum = 0, i;
for (i = 0; i
List row = M->rows[i];
int len = length(row);
sum += len;
}
return sum;
}
// equals()
// Return true (1) if matrices A and B are equal, false (0) otherwise.
int equals(Matrix A, Matrix B){
int i;
int sizeA = size(A);
int sizeB = size(B);
if (sizeA != sizeB) {
return 0;
}
for (i = 0; i
int j;
List rowA = A->rows[i];
List rowB = B->rows[i];
moveFront(rowA);
moveFront(rowB);
while(1) {
int indexA = index(rowA);
int indexB = index(rowB);
if (indexA == -1) {
if (indexB == -1) {
break;
}
else {
return 0;
}
}
else {
if (indexB == -1) {
return 0;
}
else {
Entry eA = get(rowA);
Entry eB = get(rowB);
if (eA->column != eB->column) {
return 0;
}
else {
if (eA->value != eB->value) {
return 0;
}
moveNext(rowA);
moveNext(rowB);
}
}
}
}
}
return 1;
}
// Manipulation procedures
// makeZero()
// Re-sets M to the zero Matrix state.
void makeZero(Matrix M){
int i;
for (i = 0; i
List row = M->rows[i];
for(moveFront(row); index(row) != -1; moveNext(row)) {
Entry e = get(row);
freeEntry(&e);
}
clear(row);
}
}
// changeEntry()
// Changes the ith row, jth column of M to the value x.
// Pre: 1<=i<=size(M), 1<=j<=size(M)
void changeEntry(Matrix M, int i, int j, double x){
List row = M->rows[i-1];
int len = length(row);
moveFront(row);
while (index(row) != -1) {
Entry e;
e = get(row);
if (e->column > j) {
if (x != 0.0) {
insertBefore(row, newEntry(j, x));
}
return;
}
if (e->column == j) {
if (x != 0.0) {
e->value = x;
}
else {
delete(row);
}
return;
}
moveNext(row);
}
if (x != 0.0) {
append(row, newEntry(j, x));
}
}
// Matrix Arithmetic operations
// copy()
// Returns a reference to a new Matrix object having the same entries as A.
Matrix copy(Matrix A){
Matrix M = newMatrix(A->size);
int i;
for (i = 0; i
List row = A->rows[i];
int len = length(row);
for (moveFront(row); index(row) != -1; moveNext(row)){
Entry e = get(row);
changeEntry(M, i+1, e->column, e->value);
}
}
return M;
}
// transpose()
// Returns a reference to a new Matrix object representing the transpose
// of A.
Matrix transpose(Matrix A){
int i;
Matrix M = newMatrix(size(A));
for (i = 0; i
List row = A->rows[i];
int len = length(row), j;
if (len == 0) {
continue;
}
moveFront(row);
while(index(row) != -1) {
Entry e = get(row);
changeEntry(M, e->column, i+1, e->value);
moveNext(row);
}
}
return M;
}
// scalarMult()
// Returns a reference to a new Matrix object representing xA.
Matrix scalarMult(double x, Matrix A){
int i;
Matrix M = newMatrix(size(A));
for (i = 0; i
List row = A->rows[i];
int len = length(row), j;
if (len == 0) {
continue;
}
moveFront(row);
while(index(row) != -1) {
Entry e = get(row);
changeEntry(M, i+1, e->column, x * e->value);
moveNext(row);
}
}
return M;
}
// sum()
// Returns a reference to a new Matrix object representing A+B.
// pre: size(A)==size(B)
Matrix sum(Matrix A, Matrix B){
int i;
int sizeA = size(A);
Matrix M = newMatrix(size(A));
Matrix Bcopy = copy(B);
for (i = 0; i
int j;
List rowA = A->rows[i];
List rowB = Bcopy->rows[i];
moveFront(rowA);
moveFront(rowB);
while(1) {
int indexA = index(rowA);
int indexB = index(rowB);
if (indexA == -1) {
if (indexB == -1) {
break;
}
else {
Entry eB = get(rowB);
changeEntry(M, i+1, eB->column, eB->value);
moveNext(rowB);
}
}
else {
if (indexB == -1) {
Entry eA = get(rowA);
changeEntry(M, i+1, eA->column, eA->value);
moveNext(rowA);
}
else {
Entry eA = get(rowA);
Entry eB = get(rowB);
if (eA->column < eB->column) {
changeEntry(M, i+1, eA->column, eA->value);
moveNext(rowA);
}
else if (eB->column < eA->column) {
changeEntry(M, i+1, eB->column, eB->value);
moveNext(rowB);
}
else {
changeEntry(M, i+1, eA->column, eA->value + eB->value);
moveNext(rowA);
moveNext(rowB);
}
}
}
}
}
freeMatrix(&Bcopy);
return M;
}
// diff()
// Returns a reference to a new Matrix object representing A-B.
// pre: size(A)==size(B)
Matrix diff(Matrix A, Matrix B){
int i;
int sizeA = size(A);
Matrix M = newMatrix(size(A));
Matrix Bcopy = copy(B);
for (i = 0; i
int j;
List rowA = A->rows[i];
List rowB = Bcopy->rows[i];
moveFront(rowA);
moveFront(rowB);
while(1) {
int indexA = index(rowA);
int indexB = index(rowB);
if (indexA == -1) {
if (indexB == -1) {
break;
}
else {
Entry eB = get(rowB);
changeEntry(M, i+1, eB->column, -eB->value);
moveNext(rowB);
}
}
else {
if (indexB == -1) {
Entry eA = get(rowA);
changeEntry(M, i+1, eA->column, eA->value);
moveNext(rowA);
}
else {
Entry eA = get(rowA);
Entry eB = get(rowB);
if (eA->column < eB->column) {
changeEntry(M, i+1, eA->column, eA->value);
moveNext(rowA);
}
else if (eB->column < eA->column) {
changeEntry(M, i+1, eB->column, -eB->value);
moveNext(rowB);
}
else {
changeEntry(M, i+1, eA->column, eA->value - eB->value);
moveNext(rowA);
moveNext(rowB);
}
}
}
}
}
freeMatrix(&Bcopy);
return M;
}
// product()
// Returns a reference to a new Matrix object representing AB
// pre: size(A)==size(B)
Matrix product(Matrix A, Matrix B){
int i;
int sizeA = size(A);
Matrix M = newMatrix(size(A));
Matrix Bt = transpose(B);
for (i = 0; i
int j;
List rowA = A->rows[i];
moveFront(rowA);
if (index(rowA) == -1) {
continue;
}
for (j = 0; j
List rowB = Bt->rows[j];
moveFront(rowB);
if (index(rowB) == -1) {
continue;
}
double sum = 0;
moveFront(rowA);
while(1) {
int indexA = index(rowA);
int indexB = index(rowB);
if (indexA == -1 || indexB == -1) {
break;
}
else {
Entry eA = get(rowA);
Entry eB = get(rowB);
if (eA->column < eB->column) {
moveNext(rowA);
}
else if (eB->column < eA->column) {
moveNext(rowB);
}
else {
sum += eA->value * eB->value;
moveNext(rowA);
moveNext(rowB);
}
}
}
changeEntry(M, i+1, j+1, sum);
}
}
freeMatrix(&Bt);
return M;
}
// printMatrix()
// Prints a string representation of Matrix M to filestream out. Zero rows
// are not printed. Each non-zero row is represented as one line consisting
// of the row number, followed by a colon, a space, then a space separated
// list of pairs "(col, val)" giving the column numbers and non-zero values
// in that row. The double val will be rounded to 1 decimal point.
void printMatrix(FILE* out, Matrix M){
int i;
for (i = 0; i
List row = M->rows[i];
int len = length(row), j;
if (len == 0) {
continue;
}
fprintf(out, "%d: ", i+1);
for(moveBack(row); index(row)>=0; movePrev(row));
moveFront(row);
while(index(row) != -1) {
Entry e = get(row);
fprintf(out, "(%d, %.1f) ", e->column, e->value);
moveNext(row);
}
fprintf(out, "\n");
}
}
SPARSE
#include
#include "Matrix.h"
int main(int argc, char** argv) {
FILE *fin = fopen(argv[1], "r");
FILE *fout = fopen(argv[2], "w");
int n, a, b, k, i, j;
double x;
char buffer[256];
fscanf(fin, "%d", &n);
Matrix A = newMatrix(n), B = newMatrix(n), C, D, E, F, G, H, I, J;
fscanf(fin, "%d", &a);
fscanf(fin, "%d", &b);
fscanf(fin, "%[^\n]", buffer);
for (k = 0; k
fscanf(fin, "%d", &i);
fscanf(fin, "%d", &j);
fscanf(fin, "%lf", &x);
fscanf(fin, "%[^\n]", buffer);
changeEntry(A, i, j, x);
}
for (k = 0; k
fscanf(fin, "%d", &i);
fscanf(fin, "%d", &j);
fscanf(fin, "%lf", &x);
fscanf(fin, "%[^\n]", buffer);
changeEntry(B, i, j, x);
}
fprintf(fout, "A has %d non-zero entries:\n", NNZ(A));
printMatrix(fout, A);
fprintf(fout, "\n");
fprintf(fout, "B has %d non-zero entries:\n", NNZ(B));
printMatrix(fout, B);
fprintf(fout, "\n");
C = scalarMult(1.5, A);
fprintf(fout, "(1.5)*A =\n");
printMatrix(fout, C);
fprintf(fout, "\n");
D = sum(A, B);
fprintf(fout, "A+B =\n");
printMatrix(fout, D);
fprintf(fout, "\n");
E = sum(A, A);
fprintf(fout, "A+A =\n");
printMatrix(fout, E);
fprintf(fout, "\n");
F = diff(B, A);
fprintf(fout, "B-A =\n");
printMatrix(fout, F);
fprintf(fout, "\n");
G = diff(A, A);
fprintf(fout, "A-A =\n");
printMatrix(fout, G);
fprintf(fout, "\n");
H = transpose(A);
fprintf(fout, "Transpose(A) =\n");
printMatrix(fout, H);
fprintf(fout, "\n");
I = product(A, B);
fprintf(fout, "A*B =\n");
printMatrix(fout, I);
fprintf(fout, "\n");
J = product(B, B);
fprintf(fout, "B*B =\n");
printMatrix(fout, J);
fprintf(fout, "\n");
freeMatrix(&A);
freeMatrix(&B);
freeMatrix(&C);
freeMatrix(&D);
freeMatrix(&E);
freeMatrix(&F);
freeMatrix(&G);
freeMatrix(&H);
freeMatrix(&I);
freeMatrix(&J);
fclose(fin);
fclose(fout);
return 0;
}