数据结构

【学习目标】
　1. 掌握广义表的结构特点及其存储表示方法。
　2. 学习利用分治法的算法设计思想编制递归算法。
　

【学习目标】

【重点和难点】
　　本章重点及其难点都是学习并掌握如何对递归定义的数据结构设计实现其操作的递归算法。
　

【重点和难点】

【知识点】
　　广义表的类型定义、广义表的存储表示、广义表操作的实现
　

【知识点】

【学习指南】
　　本章的内容相对其它各章要少得多，由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和"数组"合为一章。但由于广义表比数组更为复杂，它兼有"多层次"的特点，特别是它的存储表示和操作的实现和树的操作极为类似。因此在本章的学习中应善于和第六章的内容相对照，反之通过本章的学习恰好是对实现树操作的递归算法的复习和巩固。希望你通过本章的学习能自己总结出如何利用"分治法"的算法思想设计递归定义的结构的递归算法的规律来。
　

【学习指南】

【课前思考】

1. "数组"可以看成是线性表的一种扩充，若称二维数组是一个线性表，那么它的数据元素是什么？

　二维数组可定义为"其数据元素为一维数组的线性表"。可表示为：
　　A⁽²⁾ = ( A⁽¹⁾0，A⁽¹⁾1，……，A⁽¹⁾m-1 )
　其中每个数据元素是一个一维数组
　　A⁽¹⁾i = ( ai,0，ai,1，……，ai,n-1 ) i = 0，1，……，m-1
　类似地，N维数组是N-1维数组的线性表
　　A^(N) = ( A^(N-1)0，A^(N-1)1，……，A^(N-1)s-1 )
　本章讨论的广义表也可以看成是线性表的一种扩充，但它和数组不同，二维数组中的每个数据元素是结构相同的一维数组，而广义表中的每个数据元素，其结构不一定相同。

【课前思考】