sparse data structure - matrix

sparse data structure

 

sparse data structure - means most element are empty(or have a very same value), 

so we can try to use some better data structure to reduce memory use,

 

------

matrix

 

we can use 'header array' & 'link list' to represent matrix,

 

how to:

define a data structure to represent a element in matrix, the element include: x, y, value, next,

use a linked list to store the elements of a column, in order of increasing x, 

use a header array to store the first element's pointer of each column,

 

memory:

only exists element will use memory,

 

search time:

in matrix of size a * b, the max count is Nmax, and the actural count is N elements, 0 <= N <= Nmax,

then the time to search an element by (i,j) is:

N/2b

or

a*t/2 (t = N/Nmax,Nmax = a * b)

 

drawback:

the search/insert/delete/update operation take a little longer time, than the original matrix(two-dimensional array),

 

------

code

 

#include <stdio.h>
/**
 * (sparse data structure - use less memory to store element)
 * matrix might be a sparse data structure, we can use head array & linked list to represent matrix, this might free a lot memory,
 */

/** data struct for each element in link list */
struct matrix_ele { 
	int x,y,value;
	struct matrix_ele *next;
};
typedef struct matrix_ele matrix_ele;

/**
 * add element to matrix,
 * @param colheader
 	store pointer of all column's first element,
 * @param me_new
 	pointer of new element to insert,
 * 
 * @return
 	1 means add the new element, 0 means update the value of old element,
 */

int matrix_add(matrix_ele **colheader, matrix_ele *me_new) {
	matrix_ele *me = *(colheader + me_new->y);
	if(me == NULL) { // linked list is empty
		*(colheader + me_new->y) = me_new;
		return 1;
	} else { // linked list is not empty
		matrix_ele *me_pre = NULL;
		for(; me != NULL; me = me->next) {
			if(me->x == me_new->x) { // element already exists,
				me->x == me_new->x;
				return 0;
			} else if(me->x > me_new->x) {
				if(*(colheader+me_new->y)==me) { // replace the first in linked list,
					*(colheader+me_new->y)=me_new;
					me_new->next = me;
					me->next = NULL;
				}
				else { // the one replaced is not first in linked list,
					me_new->next = me;
					me_pre->next = me_new;
				}
				return 1;
			} else {
				me_pre = me; // record previous ele in linked list,
			}
		}

		// new element has largest x, put it at the end of linked list,
		me_pre->next = me_new;
		return 1;
	}
}

/**
 * delete element from matrix,
 * @param colheader
 	store pointer of all column's first element,
 * @param me_new
 	pointer of new element to delete,
 * 
 * @return
 	1 means delete, -1 mean the element does not exists,
 */

int matrix_del(matrix_ele **colheader, matrix_ele *me_del) {
	matrix_ele *me = *(colheader + me_del->y);
	if(me == NULL) { // linked list is empty
		return -1;
	} else { // linked list is not empty
		matrix_ele *me_pre = NULL;
		for(; me != NULL; me = me->next) {
			if(me->x == me_del->x) { // element found
				me->x == me_del->x;
				if(me_pre == NULL) { // deleted element is the first element in linked list
					*(colheader + me_del->y) == me_del->next;
				} else {
					me_pre->next = me->next;
				}
				me == NULL;
				me_del == NULL;
				return 1;
			} else if(me->x < me_del->x) {
				me_pre = me; // record previous ele in linked list,
			} else { // not found
				return -1;
			}
		}
	}
}

/**
 * search element in the matrix,
 * equal time: N/2b, (N is the total count,b is count of column)
 */
int matrix_search(matrix_ele **colheader, int x, int y) {
	matrix_ele *me = *(colheader+y);
	for(; me != NULL; me = me->next) {
		if(me->x == x)
			return me->value;
	}
	return -1;
}

int main() {
	int row = 10,col = 20;
	matrix_ele *colheader[20] = {};
	int i;
	for(i = 0;i<col;i++) { // init pointer to NULL, this is necessary, if not init, the init value might not be NULL,and bug might happen,
		colheader[i] = NULL;
	}
	matrix_ele e_1_1 = {1,1,101,NULL};
	matrix_ele e_3_1 = {3,1,301,NULL};
	matrix_ele e_4_1 = {4,1,401,NULL};
	matrix_ele e_3_2 = {3,2,302,NULL};
	matrix_ele e_6_2 = {6,2,602,NULL};
	matrix_ele e_7_2 = {7,2,702,NULL};

	// add
	matrix_add(colheader, &e_1_1);
	matrix_add(colheader, &e_3_1);
	matrix_add(colheader, &e_4_1);
	matrix_add(colheader, &e_3_2);
	matrix_add(colheader, &e_6_2);
	matrix_add(colheader, &e_7_2);

	// search
	int v_1_1 = matrix_search(colheader, 1, 1);
	printf("expect: %d,\tactural: %d,\n",101,v_1_1);

	int v_3_1 = matrix_search(colheader, 3, 1);
	printf("expect: %d,\tactural: %d,\n",301,v_3_1);

	int v_4_1 = matrix_search(colheader, 4, 1);
	printf("expect: %d,\tactural: %d,\n",401,v_4_1);

	int v_3_2 = matrix_search(colheader, 3, 2);
	printf("expect: %d,\tactural: %d,\n",302,v_3_2);

	int v_6_2 = matrix_search(colheader, 6, 2);
	printf("expect: %d,\tactural: %d,\n",602,v_6_2);

	int v_7_2 = matrix_search(colheader, 7, 2);
	printf("expect: %d,\tactural: %d,\n",702,v_7_2);

	int v_4_2 = matrix_search(colheader, 4, 2);
	printf("expect: %d,\tactural: %d,\n",-1,v_4_2);

	int v_x_x = matrix_search(colheader, 3, 9);
	printf("expect: %d,\tactural: %d,\n",-1,v_x_x);
	
	// test delete
	int d_3_1 = matrix_del(colheader, &e_3_1);
	v_3_1 = matrix_search(colheader,3,1);
	printf("expect: %d,%d,\tactural: %d,%d,\n",1,-1,d_3_1,v_3_1);

	matrix_ele e_x_x = {3,9,309,NULL};
	int d_x_x = matrix_del(colheader, &e_x_x);
	v_x_x = matrix_search(colheader,3,9);
	printf("expect: %d,%d,\tactural: %d,%d,\n",-1,-1,d_x_x,v_x_x);
}

 

 

------