c – 双阵列特里问题
发布时间：2020-12-16 06:56:24 所属栏目：百科 来源：网络整理
导读：我试图从 http://linux.thai.net/~thep/datrie/datrie.html了解Double-Array Trie实现 但我不明白以下部分. check[base[s] + c] = sbase[s] + c = t 在这里添加c意味着什么. 任何人都可以用简单的语言解释算法. 解决方法 想象一下,您将2D数组折叠为一维数组
|
我试图从
http://linux.thai.net/~thep/datrie/datrie.html了解Double-Array Trie实现
但我不明白以下部分. check[base[s] + c] = s base[s] + c = t 在这里添加c意味着什么. 任何人都可以用简单的语言解释算法. 解决方法
想象一下,您将2D数组折叠为一维数组：
int arr2D[2][3];
int arr1D[2 * 3]; // # of rows * # of columns
// access element [1][2] of 2D array,i.e.,the last element
int elem2D = arr2D[1][2];
// access element [1][2] of 1D array,the last element
int elem1D = arr1D[1 * 3 + 2];
// =========================================================
lets visualize the array access:
arr2D => x/y 0 1 2
0 [N][N][N]
+1 on x > 1 [N][N][N]
+2 on y ---------- ^
y_len => ^-------^ 3 elements
so the access happens with x * y_len + y
1 * 3 + 2
now for the 1D array
we want the second row,so we go with 1 * 3
(0-based access,y_len = 3)
and then we want the 3rd element,so + 2
(again,0-based access)
arr1D => x 0 1 2
[N][N][N]
3 4 5
1 * 3 = 3 > [N][N][N]
+ 2 = 5 ---- ^
我希望我没有让这太复杂(尽管我认为我做了……). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |