数据结构Ch数组和广义表.pptVIP

数 据 结 构 Ch.5数组和广义表 计 算 机 学 院 肖明军 Email: xiaomj@ /~xiaomj * * * * * * * * * * * * * * * * * §5.3 广义表（Lists） 图示 E=NIL * §5.3 广义表（Lists） 特点 除空表的表头指针为空外，头指针均指向表结点。 任一表结点的hp均指向表头部（原子结点或表结点） 任一表结点的tp均指向表尾部（当表尾部为空表时，tp=NIL，否则必指向表结点） 易分清表中原子和子表所在层次。 如x、L在第一层，a、b在第二层。 最高层的表结点数即为广义表的长度。 浪费空间，易求表长和表深度。 * §5.3 广义表（Lists） (2) 单链表示法 模仿线性表的单链表结构，当所有元素为原子时，等价于单链表。 结点结构： 图示：E=NIL C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) =(A(x, L(a, b)), B(A(x, L(a, b)), y)) * §5.3 广义表（Lists） 存储结构说明 typedef struct GLNode{ int atom; //亦可定义为枚举类型，标志域 struct GLNode *slink; //指向同层后继 union { struct GLNode *slink; //指向子表的第一个结点 DataType data； //原子结点数据域 }optval; //候选值 } *GList; * §5.3 广义表（Lists） 缺点： 若要在某一表中开始处插入或删除一个结点，则要找出所有指向该结点的指针，逐一加以修改。 例如，上图中，删除A表中的x，修改A的头指针外，须修改来自于B、C表的指针，引用来源点不易知道。 删除一个表可能导致错误。 例如，删除A表时，A的所有结点释放后，会引起B、C表的错误。 * §5.3 广义表（Lists） 改进 引入表头结点，使子表内部的变化不会涉及外部元素的变化，插删第一个结点方便。头结点和其他结点结构相同，只是以示区别： 删除表时，头结点引用计数减1，仅当引用计数为0时，才释放表中所有结点。 * §5.3 广义表（Lists） (3) 双链表示法 该方法类似于第6章的二叉链表。 结点结构 存储说明 typedef struct GLNode{ DataType data; //子表名字或原子数据 struct GLNode *link1, *link2; } *GList; * §5.3 广义表（Lists） 图示 特点 简洁方便，类似于二叉链表，可借助于二叉链表表示处理，易求长度深度。 在表结点中保存了子表的名字信息，有时子表名字和原子信息同样重要。 * §5.3 广义表（Lists） 例子 (姓名,工资收入(基本工资,午餐补助,津贴),扣除(公积金,水电费,其它),实发工资) 3. 运算：略 * * * * * * * * * * * * * * * * * * * * * * * * §5.1 多维数组 多维数组 是最易处理的非线性结构。因为各元素类型一致，各维上下界固定，所以它最容易线性化，故可看做是线性表的拓广。例如：二维数组可以看做是由列向量组成的线性表。 * §5.1 多维数组 结构特性 例：二维数组 ，它属于两个向量；i th行和j th列。 除边界外，每个aij恰有两个直接前驱和两个直 接后继。 * §5.1 多维数组 非线性特征 i th行：前驱aij-1，后继aij+1 j th列：前驱ai-1j，后继ai-1j 仅有一个开始结点：a11 仅有一个终端节点：amn 其他边界上的结点只有一个直接前驱或一个直接后继，类似的m维数组 的每一个元素都属于m个向量。 * §5.1 多维数组 存储 一般均采用顺序方式存储，原因是结构中的结点不变动，内存是一维的，必须将多维数组线性化。 行优先（行主序）方式： 将(i+1)th行向量紧接在i th行向量之后： 特点：列下标变化快。Pascal、C等均是此方法。先排最右下标（多维）。 * §5.1 多维数组 列优先（列主序）方法 特点行下标变化最快，先排最左下标（可推广至多维）。Fortan是用此方法。 地址计算 一维存储地址（内部实现）。 基地址——开始结点存储地址Loc(a11). 维数——每维的上下界（若下界固定，则只须知道维长度） 每个元素占用的单元