数据结构中存储的方式几种？是不是编码存储和压缩存储？

数据结构中存储的方式几种？是不是编码存储和压缩存储？

应该是链式存储、顺序存储、索引存储和散列存储四种表示

2.1.6 栅格数据存储的压缩编码

1 直接编码

    直接栅格编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为图像文件或栅格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐象元记录，也可奇数行从左到右，而偶数行由右向左记录，为了特定目的还可采用其它特殊的顺序,右图直接编码可表示为矩阵：

2 链式编码

    链式编码又称为弗里曼链码（freeman,1961）或边界链码。由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东＝0，南＝3，西＝2，北＝1等。右图多边形边如果确定原点为像元（10，1），则该多边形界按顺时方向的链式编码为： 链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易。但是，叠置运算如组合、相交等则很难实施，

3 行程编码

   行程编码1

    只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数。左图可沿行方向进行行程编码：

   行程编码2

    逐个记录各行（或列）代码发生变化的位置和相应的代码，左图可沿列方向进行行程编码： 1列：（1，3），（3，1）；     2列：（1，3），（4，1）；     3列：（1，3），（5，1）；     4列：（1，4），（2，3），（5，1）；     5列：（1，4），（4，3），（6，2），（7，1）；     6列：（1，4），（4，2）；     7列：（1，4），（4，2）；     8列：（1，4），（3，2）。

   行程编码3

    按行（或列）记录相同代码的始末象元的列号（或行号）和相应的代码，左图可沿行方向进行程编码：

4 块式编码

    把多边形范围划分成由象元组成的正方形，然后对各个正方形进行编码。块式编码数据结构中包括3个数字：块的初始位置（行、列号）和块的大小（块包括的象元数），再加上记录单元的代码组成。左图块式编码：

5 四叉树编码

2.1.6 栅格数据存储的压缩编码

 1 直接编码

    直接栅格编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为图像文件或栅格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐象元记录，也可奇数行从左到右，而偶数行由右向左记录，为了特定目的还可采用其它特殊的顺序,右图直接编码可表示为矩阵：

   

 2 链式编码

    链式编码又称为弗里曼链码（freeman,1961）或边界链码。由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东＝0，南＝3，西＝2，北＝1等。右图多边形边如果确定原点为像元（10，1），则该多边形界按顺时方向的链式编码为：

链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易。但是，叠置运算如组合、相交等则很难实施，

   

 3 行程编码

   行程编码1

    只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数。左图可沿行方向进行行程编码：

   

   行程编码2

    逐个记录各行（或列）代码发生变化的位置和相应的代码，左图可沿列方向进行行程编码：

1列：（1，3），（3，1）；

    2列：（1，3），（4，1）；

    3列：（1，3），（5，1）；

    4列：（1，4），（2，3），（5，1）；

    5列：（1，4），（4，3），（6，2），（7，1）；

    6列：（1，4），（4，2）；

    7列：（1，4），（4，2）；

    8列：（1，4），（3，2）。

   行程编码3

    按行（或列）记录相同代码的始末象元的列号（或行号）和相应的代码，左图可沿行方向进行程编码：

   

 4 块式编码

    把多边形范围划分成由象元组成的正方形，然后对各个正方形进行编码。块式编码数据结构中包括3个数字：块的初始位置（行、列号）和块的大小（块包括的象元数），再加上记录单元的代码组成。左图块式编码：

   

 5 四叉树编码

   四叉树分割

    将图像区域按四个大小相同的象限四等分，每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，无论分割到哪一层象限，只要子象限上仅含一种属性代码或符合既定要求的少数几种属性时，则停止继续分割。否则就一直分割到单个象元为止。按照象限递归分割的原则所分图像区域的栅格阵列应为2n×2n（n为分割的层数）的形式。

   四叉树结构

    把整个2n×2n象元组成的阵列当作树的根结点，树的高度为ｎ级（最多为ｎ级）。每个结点有分别代表南西（sw）、南东（se）、北西（nw）、北东（ne）四个象限的四个分支。四个分支中要么是树叶，要么是树叉。树叶代表不能继续划分的结点，该结点代表子象限具有单一的代码；树叉不只包含一种代在码，必须继续划分，直到变成树叶为止。

   四叉树编码

    1 指针四叉树编码

    通过在子结点与父结点之间设立指针的方式建立起整个结构。按这种方式，四叉树的每个结点通常存储6个量，即四个子结点指针、一个父结点指针和该结点的属性代码。这种方法除了要记录叶结点外，还要记录中间结点，一般要占用较大存储空间。

   2 线性四叉树编码

    为美国马里兰大学地理信息系统中采用的编码方法，该方法记录每个终止结点（或叶结点）的地址和值，值就是子区的属性代码，其中地址包括两部分，共32位（二进制），最右边4位记录该叶结点的深度，即处于四叉树的第几层上，有了深度可以推知子区大小；左边的28位记录路径，从右边第五位往左记录从叶结点到根结点的路径，0，1，2，3分别表示sw、se、nw、ne。

28位 4位

0 0 0 0 ... ... 0 0 0 0 1 1 1 0 0 0 1 1

（路径0sw,3ne,2nw） 0 3 2 深度3

记录了各个叶子的地址，再记录相应代码值，就记录了整个图像。

   四叉树优点

    1.容易而有效地计算多边形的数量特征；

    2.阵列各部分的分辨率是可变的，边界复杂部分四叉树较高，即分级多，分辨率也高，而不需要表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存储量；

    3.栅格到四叉树及到四叉树到简单栅格结构的转换比其他压缩方法容易；

    4.多边形中嵌套异类多边形的表示较方便。

   四叉树分割

    将图像区域按四个大小相同的象限四等分，每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，无论分割到哪一层象限，只要子象限上仅含一种属性代码或符合既定要求的少数几种属性时，则停止继续分割。否则就一直分割到单个象元为止。按照象限递归分割的原则所分图像区域的栅格阵列应为2n×2n（n为分割的层数）的形式。

   四叉树结构

    把整个2n×2n象元组成的阵列当作树的根结点，树的高度为ｎ级（最多为ｎ级）。每个结点有分别代表南西（sw）、南东（se）、北西（nw）、北东（ne）四个象限的四个分支。四个分支中要么是树叶，要么是树叉。树叶代表不能继续划分的结点，该结点代表子象限具有单一的代码；树叉不只包含一种代在码，必须继续划分，直到变成树叶为止。

   四叉树编码

    1 指针四叉树编码

    通过在子结点与父结点之间设立指针的方式建立起整个结构。按这种方式，四叉树的每个结点通常存储6个量，即四个子结点指针、一个父结点指针和该结点的属性代码。这种方法除了要记录叶结点外，还要记录中间结点，一般要占用较大存储空间。

   2 线性四叉树编码

    为美国马里兰大学地理信息系统中采用的编码方法，该方法记录每个终止结点（或叶结点）的地址和值，值就是子区的属性代码，其中地址包括两部分，共32位（二进制），最右边4位记录该叶结点的深度，即处于四叉树的第几层上，有了深度可以推知子区大小；左边的28位记录路径，从右边第五位往左记录从叶结点到根结点的路径，0，1，2，3分别表示sw、se、nw、ne。 28位 4位 0 0 0 0 ... ... 0 0 0 0 1 1 1 0 0 0 1 1 （路径0sw,3ne,2nw） 0 3 2 深度3 记录了各个叶子的地址，再记录相应代码值，就记录了整个图像。

   四叉树优点

    1.容易而有效地计算多边形的数量特征；

    2.阵列各部分的分辨率是可变的，边界复杂部分四叉树较高，即分级多，分辨率也高，而不需要表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存储量；

    3.栅格到四叉树及到四叉树到简单栅格结构的转换比其他压缩方法容易；

    4.多边形中嵌套异类多边形的表示较方便。