sparse data structure - matrix
6759 단어 Matrix
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,
",101,v_1_1);
int v_3_1 = matrix_search(colheader, 3, 1);
printf("expect: %d,\tactural: %d,
",301,v_3_1);
int v_4_1 = matrix_search(colheader, 4, 1);
printf("expect: %d,\tactural: %d,
",401,v_4_1);
int v_3_2 = matrix_search(colheader, 3, 2);
printf("expect: %d,\tactural: %d,
",302,v_3_2);
int v_6_2 = matrix_search(colheader, 6, 2);
printf("expect: %d,\tactural: %d,
",602,v_6_2);
int v_7_2 = matrix_search(colheader, 7, 2);
printf("expect: %d,\tactural: %d,
",702,v_7_2);
int v_4_2 = matrix_search(colheader, 4, 2);
printf("expect: %d,\tactural: %d,
",-1,v_4_2);
int v_x_x = matrix_search(colheader, 3, 9);
printf("expect: %d,\tactural: %d,
",-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,
",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,
",-1,-1,d_x_x,v_x_x);
}
------
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Matrix RGB LED Funduino를 Colorduino에서 사용Matrix LED가 장착된 ATmega328P 보드 Funduino를 사용해 봅시다. Funduino는 Colorduino, RGB LED 8x8 Matrix Board with Driver Shield for A...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.