Solve problem using Data structure with c code

Question

Solve the problem of sparse 2- dimensional array

A sparse array is an array in which most of the elements have the same value (known

as the default value—usually 0 or null). The occurrence of zero elements in a large

array is inefficient for both computation and storage. It is required to implement

sparse 2- dimensional array in more efficient way. Your implementation should

allow:

 Adding new value in a specific index.

 Removing a value from specific index.

 Search for a value and return its index if found.

 Return a value from specific index.

Answer 1

It's just a linked list...

Since you did not specify the data type, I made it generic, so that it

can store any type of data. So for comparison, you will either need to

specify the data type that the matrix stores, or you will have to

write a Compare callback function whose address gets assigned to

the function pointer and called upon for linear searching the list.

You can then remove the node, if found from the list. I would approach it

in 3 cases (1) removes the first node (2) removes the last node (3) removes

node in betweem

If you don't like the linked list, you will have to use a dynamic array.

I can help you with that too...

Here's part of the linked list that can be done.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

typedef enum _TDataType

{

DataTypeNone,

DataTypeChar,

DataTypeInt,

DataTypeLong=4,

DataTypeDouble=8,

DataTypeStr=16

} TDataType;

typedef struct _TMatrixCellEntry

{

int dataSize;

TDataType dataType;

char * data;

int nRow,nColumn;

} * TMatrixCellEntry;

#define MATRIX_CELL_ENTRY_SIZE (sizeof(struct _TMatrixCellEntry))

MatrixCellEntry_Init(TMatrixCellEntry x, char * data, int nSize, TDataType dataType, int iRow, int iColumn)

{

int N = x->dataSize = nSize;

x->dataType = dataType;

x->data = (char*)malloc(N);

memcpy(x->data,data,N);

x->nRow = iRow;

x->nColumn = iColumn;

}

MatrixCellEntry_Destroy(TMatrixCellEntry x)

{

if (x->data!=NULL)

{

free(x->data);

x->data = NULL;

}

x->dataSize=0;

x->dataType = DataTypeNone;

x->nRow = x->nColumn=-1;

}

typedef struct _TMatrixListNode

{

TMatrixCellEntry matrixCellEntry;

struct _TMatrixListNode * next;

} * TMatrixListNode;

#define MATRIX_LIST_NODE_SIZE (sizeof(struct _TMatrixListNode))

typedef struct _TMatrix

{

TMatrixListNode first;

TMatrixListNode last;

int count;

int numRows,numColumns;

} *TMatrix;

Matrix_Init(TMatrix matrix, int nRows, int nColumns)

{

matrix->first=matrix->last=NULL; matrix->count = 0;

matrix->numRows = nRows; matrix->numColumns = nColumns;

}

Matrix_Push(TMatrix matrix, TMatrixCellEntry newMatrixCellEntry)

{

int iReturn=0;

if (

(newMatrixCellEntry->nRow>=0 && newMatrixCellEntry->nRow<matrix->numRows) &&

(newMatrixCellEntry->nColumn>=0 && newMatrixCellEntry->nColumn<matrix->numColumns)

)

{

TMatrixListNode newMatrixListNode = (TMatrixListNode)malloc(MATRIX_LIST_NODE_SIZE);

newMatrixListNode->matrixCellEntry = (TMatrixCellEntry)malloc(MATRIX_CELL_ENTRY_SIZE);

memcpy(newMatrixListNode->matrixCellEntry,newMatrixCellEntry,MATRIX_CELL_ENTRY_SIZE);

newMatrixListNode->next = NULL;

if (matrix->count==0)

{

matrix->first = matrix->last = newMatrixListNode;

}

else

{

matrix->last->next = newMatrixListNode;

matrix->last = matrix->last->next;

}

matrix->count++;

}

else

{

iReturn=-1;

}

return(iReturn);

}

Matrix_Dump(TMatrix matrix)

{

int iLoop,jLoop;

TMatrixListNode cur = matrix->first;

printf(" Matrix dimensions: # of rows = %d : # of columns = %d \n",matrix->numRows, matrix->numColumns);

printf(" Sparse matrix contains %d entries \n",matrix->count);

for (iLoop=0; iLoop<matrix->count; iLoop++)

{

printf(" Entry # %d of %d \n",(iLoop+1),matrix->count);

printf("==============================================\n");

printf(" row = %d : column = %d \n",cur->matrixCellEntry->nRow,cur->matrixCellEntry->nColumn);

printf(" data size = %d \n",cur->matrixCellEntry->dataSize);

printf(" data type code = %d \n",cur->matrixCellEntry->dataType);

printf(" data hex dump \n");

printf("---------------------\n");

for (jLoop=0; jLoop<cur->matrixCellEntry->dataSize; jLoop++)

{

printf("%x \n",cur->matrixCellEntry->data[jLoop]);

}

cur = cur->next;

}

}

Matrix_Destroy(TMatrix matrix)

{

int iLoop;

TMatrixListNode cur = matrix->first;

for (iLoop=0; iLoop<matrix->count; iLoop++)

{

matrix->first = matrix->first->next;

if (cur->matrixCellEntry!=NULL)

{

printf("freeing list node ...\n");

if (cur->matrixCellEntry->data!=NULL)

{

printf("freeing list node data.........\n");

free(cur->matrixCellEntry->data);

cur->matrixCellEntry->data=NULL;

}

free(cur->matrixCellEntry);

cur->matrixCellEntry = NULL;

}

cur = matrix->first;

}

//matrix->first=matrix->last=NULL;

matrix->count=0;

matrix->numRows=matrix->numRows=0;

}

int main()

{

struct _TMatrix matrix;

struct _TMatrixCellEntry matrixCellEntry;

int N;

Matrix_Init(&matrix,15,15);

double dblAmt = 333.33;

matrixCellEntry.nColumn= matrixCellEntry.nRow =3;

matrixCellEntry.dataType = DataTypeDouble;

N = matrixCellEntry.dataSize = sizeof(double);

matrixCellEntry.data = (char*)malloc(N);

memcpy(matrixCellEntry.data,&dblAmt,N);

Matrix_Push(&matrix,&matrixCellEntry);

free(matrixCellEntry.data);

long longIntNum=77777;

matrixCellEntry.nColumn = matrixCellEntry.nRow = 7;

matrixCellEntry.dataType = DataTypeLong;

N = matrixCellEntry.dataSize = sizeof(long);

matrixCellEntry.data = (char*)malloc(N);

memcpy(matrixCellEntry.data,&longIntNum,N);

Matrix_Push(&matrix,&matrixCellEntry);

free(matrixCellEntry.data);

char str[25]; strcpy(str,"HELLO");

matrixCellEntry.nColumn = matrixCellEntry.nRow = 11;

matrixCellEntry.dataType = DataTypeStr;

N = matrixCellEntry.dataSize = strlen(str)+1;

matrixCellEntry.data = (char*)malloc(N);

memcpy(matrixCellEntry.data,str,N);

Matrix_Push(&matrix,&matrixCellEntry);

Matrix_Dump(&matrix);

Matrix_Destroy(&matrix);

}