2)从 Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点,然后再从该结点后的下一结 点开始寻找、输出和删除表中的第m个结点,重复此过程 35二维数组(矩阵) ■1.二维数组定义 ◆行关系,列关系均是线性关系 ■2.二维数组的顺序存放 (一)行优先存放:ana12..a1na12.aina12…,aim,am1am2…amn 计算a的存放位置:设每个元紊占据S个存储单元 Loc(aj)=Loc(an)+(i-1)*n+(-1)*S计算前面有多少个元素 (二)列优先存放 ala21…am1a2a2…am2aa2j…ai.alna2n…amn Loc(aij)=Loc(an)+((j-1)m+(i-1))"s ■3.规则矩阵的压缩存储 ◆(1)对称矩阵,三角矩阵的压缩 对称矩阵:ali,j=aj,i 三角矩阵:上三角为0,或下三角为0 只存储上或下三角内的元素,节约近一半的存储空间 (1)对称矩阵,三角矩阵的压缩 i>=j时,元素位于下三角 Loc(aij)=Loc(an)+(i(i-1)/2+(j-1))*S j时,元素位于上三角 Loc(ai)=loc(an)+(j(j-1)/2+(i-1))*S ■(2)稀疏矩阵 矩阵中的非零元素很少,分布没有规律 利用三元存储法(行值,列值,元素值 先形成三元矩阵 再按照行优先顺序方式存储 稀疏矩阵三元组定义 1)定义三元组元素 typedef struct tuple3tpl int row num;/行号 int col num:;/列号* elemtype value;/元素值* 3 tuple3tp 2)定义三元组 typedef struct tuple int row;/行数 int col;/列数* int num;/非零元素个数 tuple3 tp datal MAXNUMI;/三元组* ] tuple 11
11 2）从 Josephus 表中的第 s 个结点开始寻找、输出和删除表中的第 m 个结点，然后再从该结点后的下一结 点开始寻找、输出和删除表中的第 m 个结点，重复此过程， 3.5 二维数组（矩阵） ◼ 1.二维数组定义 ◆ 行关系，列关系均是线性关系 ◼ 2. 二维数组的顺序存放 （一）行优先存放：a11 a12... a1na21 a22... ai1 ai2 ...ain... am1 am2 ... amn ◆ 计算 aij的存放位置：设每个元素占据 S 个存储单元 Loc(aij) = Loc(a11) + (( i - 1)*n + (j - 1))*S 计算前面有多少个元素 ◼ （二）列优先存放 a11 a21... am1a12 a22... am2a1j a2j ...aii... a1n a2n ... amn Loc(aij) = Loc(a11) + (( j - 1)*m + (i - 1))*S ◼ 3. 规则矩阵的压缩存储 ◆ (1)对称矩阵，三角矩阵的压缩 对称矩阵：a[ i , j ] = a[ j , i ] 三角矩阵：上三角为 0，或下三角为 0 只存储上或下三角内的元素，节约近一半的存储空间 (1)对称矩阵，三角矩阵的压缩 i >= j 时，元素位于下三角 Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1))*S i < j 时，元素位于上三角 Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1))*S ◼ (2)稀疏矩阵 ◆ 矩阵中的非零元素很少，分布没有规律 ◆ 利用三元存储法 （行值，列值，元素值） 先形成三元矩阵 再按照行优先顺序方式存储。 稀疏矩阵三元组定义 1)定义三元组元素 typedef struct tuple3tp{ int row_num; /*行号*/ int col_num; /*列号*/ elemtype value; /*元素值*/ } tuple3tp 2)定义三元组 typedef struct tuple3{ int row; /*行数*/ int col; /*列数*/ int num; /*非零元素个数*/ tuple3tp data[ MAXNUM];/* 三元组*/ }tuple3;
3.5树与二叉树 3.51树的基本概念 1.树的定义 ◆树是以分支关系定义的层次结构。 倒生树:树根在上,根上分茎,茎上分叶 是族谱、社会组织机构一类实体的逻辑抽象 对定义的理解 (1)有限集 (2)递归定义:树,根,子树 (3)有且仅有一个根结点不存在空树 ◆(4)子树是互不相交的有限集 ◆(5)树的层次性 除根结点以外的结点有且仅有一个父结点 ■树是一种数据结构 ◆Tree=(D,R) cD:元素的集合 R:元素关系的集合 ◆(父、子关系前驱、后继关系) ◆各结点没有或仅有一个父结点 ◆有且仅有一个根结点 令各结点可以有任意个子树 ■2.树的术语 1)结点 根结点:没有前驱,仅有后继 (茎)分支结点:有且仅有一个前驱,可以有多个后继 叶结点:没有后继,仅有前驱 2)度与深度 结点的度:该结点拥有的子树数目。 树的度:最大的结点度 深度:最大的层次数 3)A节点的双亲,孩子,兄弟,祖先,子孙 4)路径(树枝,分支) 从K1出发自上而下到K2所经历的所有结点序列 5)有序树与无序树 有序树:兄弟有长幼之分,从左至右。交换兄弟位置,变成不同的树。 6)森林 不相交的树的集合
12 3.5 树与二叉树 ◼ 3.5.1 树的基本概念 ◼ 1. 树的定义 ◆ 树是以分支关系定义的层次结构。 ◆ 倒生树：树根在上，根上分茎，茎上分叶 ◆ 是族谱、社会组织机构一类实体的逻辑抽象 ◼ 对定义的理解 ◆ （1）有限集 ◆ （2）递归定义：树，根，子树 ◆ （3）有且仅有一个根结点不存在空树 ◆ （4）子树是互不相交的有限集 ◆ （5）树的层次性 除根结点以外的结点有且仅有一个父结点 ◼ 树是一种数据结构 ◆ Tree = ( D , R ) D：元素的集合 R：元素关系的集合 ❖ （父、子关系 前驱、后继关系） ❖ 各结点没有或仅有一个父结点 ❖ 有且仅有一个根结点 ❖ 各结点可以有任意个子树 ◼ 2. 树的术语 ◼ 1）结点 根结点: 没有前驱，仅有后继 (茎)分支结点: 有且仅有一个前驱，可以有多个后继 叶结点: 没有后继，仅有前驱 2）度与深度 结点的度：该结点拥有的子树数目。 树的度：最大的结点度 深度：最大的层次数 3）A 节点的双亲, 孩子, 兄弟, 祖先, 子孙 4）路径（树枝，分支） 从 K1 出发自上而下到 K2 所经历的所有结点序列 5）有序树与无序树 有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。 6）森林 不相交的树的集合