DS4-扩展线性表.pptx

第4章 扩展线性表—— 数组与广义表;4.1 扩展线性表---数组*;4.1.2 数组的基本操作 ;4.1.3 数组的存储结构 静态数组（定义数组）和动态数组（指针数组） 对于下界为0的一个一维数组a[n]，给定第一个数组元素a0的存储地址是Loc(a0)，每个数据元素所占的存储单元为k，则任意数据元素ai的存储单元地址： Loc(ai)= Loc(a0) + i * k (0≤i＜n) 二维数组推广到一般情况：设二维数组的行下标的取值范围为rl到ru，列下标取值范围为cl到cu。 以行序为主序的存储方式，则任意数据元素ai,j的存储单元地址： Loc(ai,j)= Loc(arl,cl) + ((i – rl) * (cu – cl + 1) + (j – cu)) * k 以列序为主序的存储方式，则任意数据元素ai,j的存储单元地址： Loc(ai,j)= Loc(arl,cl) + ((j – cl) * (ru - rl + 1) + (i – rl)) * k;4.1.4 矩阵的压缩存储 压缩存储是指为多个值相同的矩阵元素分配一个存储空间，值为0的矩阵元素不分配空间的存储方式。 把矩阵元素值相同的或者的0元素分布有一定规律的矩阵，则称之为特殊矩阵。 如果矩阵中的0元素占绝大部分，则称此类矩阵为稀疏矩阵。 ;1.特殊矩阵 若n阶方阵A中的数据元素满足下列性质： ai,j = aj,i （0 ≤ i，j ＜ n） 则称矩阵A为n阶对称矩阵。 假设以一维数组SC[0～n(n+1)/2-1]来存储对阵矩阵A[n][n]，则SC[k]与矩阵元素aij之间存在着一一对应关系： k = i*(i+1)/2 + j 当i≥j k = j*(j+1)/2 + i 当i=j ;2.稀疏矩阵的压缩存储 假设在n*m的矩阵中，有x个数据元素的值不为0，设 则称Γ为稀疏因子，如果某一矩阵的稀疏因子Γ≤ 0.05时，则称该矩阵为稀疏矩阵(Sparse Matrix)。 ;4.2 扩展线性表---广义表*;四个重要结论： （1）层次性。广义表中的元素是不“均匀”的(元素类型不同)，是一个多层次的结构。右图表示的是广义表E,图中○表示广义表，□表示原子。其中○有几层，广义表的深度就为几层。 （2）共享性。如上例中，广义表A、B和C为广义表E的子表，那么，在广义表E中就不必列出子表的值，可以通过广义表的名称来引用。 （3）递归性。如上例中的广义表F可以得知，广义表可以是其本身的一个子表。 （ 4）任何非空广义表的表头可以是原子，也可以???广义表，但其表尾必定是广义表。 ;4.2.2 广义表的存储表示;算法4.2：广义表头尾链表存储表示方式的结点类 struct GenListNode { //广义表结点类定义 public: GenListNode() : utype(0), tlink(NULL), info.ref(0) {} //构造函数 GenListNode(GenListNodeT RL) { //复制构造函数 utype = RL.utype; info = RL.info; } private: int utype; //＝0 / 1 union { //联合 T value; //utype=1,存放数值 struct{ GenListNodeT *hp; GenListNodeT *tp; }ptr; } info; }; ;;在这种存储结构中有几种情况： （1）除空表的头指针为空外，对任何非空列表，其头指针均指向广义表表结点，且该结点中的hp指向表头（或为原子结点，或为表结点），tp指向表尾（除非表尾为空，否则必为表结点）； （2）容易分清列表中原子和子表所在的层次。如在列表D中，原子a和e在同一层次上，而b、c和d在同一层次上且比a和e低一层，B和C是同一层次的子表； （3）最高层的表结点个数为列表的长度。 以上三个特点在某种程度上给列表的操作带来了方便。 其主要缺点是：表结点过多，容易造成空间浪费。;2．广义表的扩展线性链表存储方式 在这种存储结构中，表结点由三个域组成： （1）标志域utype 它用来标明该结点是什么类型的结点。=0，是广义表专用的附加头结点；=1，是原子结点（为简化讨论，不考虑原子结点数据的不同类型）；=2，是子表结点。 （2）信息域info 不同类型的结点在这个域中存放的内容不同。当utype=0时，该信息域存放引用计数（ref）；当utype=1时，该信息域存放元素数据值（value）；当utype=2时，该信息