数据结构(Java)-第5章.ppt

4、广义表的运算 （1）创建广义表：initGList() 初始条件：广义表不存在。 操作结果：创建一个空的广义表。 （2）插入数据元素：insert(x) 初始条件：广义表已存在。 操作结果：将新的数据元素x插入到广义表的第一个位置。 （3）删除数据元素：delete() 初始条件：广义表已存在。 操作结果：删除广义表中的第一个数据元素，同时将广义表的长度减1。 （4）求长度：length() 初始条件：广义表已存在。 操作结果：返回广义表的长度，即广义表中数据元素的个数。 （5）求深度：getDepth() 初始条件：广义表已存在。 操作结果：返回广义表的深度。 （6）判断广义表是否为空：isEmpty() 初始条件：广义表已存在。 操作结果：若广义表为空表，返回true，否则返回false。 （7）取表头：getHead( ) 初始条件：广义表已存在。 操作结果：判断广义表是否为空，如false则返回该广义表的第一个数据元素。如true则返回null。 （8）取表尾：getTail() 初始条件：广义表已存在。 操作结果：判断广义表是否为空，如false则返回该广义表除第一个数据元素外的所有其他元素。如true则返回null。 其中最重要的基本操作即是取表头操作和取表尾操作。 【例】求下列广义表操作的结果 （1）getHead[(p,h,w)] （2）getTail[（b，k，p，h）] （3）getHead[（（a，b），（c，d））] （4）getTail[（（a，b），（c，d））] 5、广义表的存储结构 在广义表的链式存储结构中，一个结点表示一个元素。元素分为原子和子表两种，为了使广义表中的各结点既能在形式上保持一致，有能进行区别，可以如下图所示定义结点。 其中，atom是一个标志位，表示该元素是否为原子。取值如下： 当atom=0时，结点为原子，第2个域为data，保存相应原子元素的信息；当atom=1时，结点为子表，第2个域为sublist，保存相应子表第1个结点的地址。next域保存与本结点同一层的下一个结点地址，当本结点是其所在层的最后一个结点时，next域为null。 以广义表C=（c，（a，b））为例，其存储结构如下所示。 五、?数组项目实践 调查问卷的结果统计 【问题描述】某学校膳食委员会针对学生食堂的食物质量满意度向学生发放调查问卷，问卷设置的满意度分为五个等级，如表5.2所示。本次调查现收集到50份有效反馈意见，试汇总本次调查的结果，并给出各评级所占的比例。 表5.2 膳食质量满意度调查表。 评级 说明 A 满意 B 良好 C 一般 D 差强人意，有待改进 E 非常不满意 NEXT Neusoft 基本内容 1.数组的定义和运算? 第5章 数组和广义表 2.数组顺序存储结构? 3.矩阵的压缩存储 ? 4.广义表 5.数组项目实践 ? 1、数组（array）的定义 数组是由n个（n≥1）具有相同数据类型的数据元素（a0，a1，…，ai-1，ai，ai+1，…，an-1）构成的有限序列，并且这些数据元素占用一片地址连续的内存单元。在Java语言中，数组的本身是堆中的对象，它能保存基本类型变量或其他对象的引用。在使用数组之前，需要声明并构造数组。 例如：声明一个用于保存学生考试成绩的一维数组scores，即 double [ ] scores; 然后构造数组， scores = new double[5]; 一. 数组的定义和运算? 2、数组的运算 数组的基本操作主要有以下3种，以一维数组为例： （1）求数组的长度：length（） 初始条件：数组已存在。 操作结果：返回数组中数据元素的个数。 （2）取值：getValue（index） 初始条件：数组已存在。 操作结果：返回数组下标为index的数组元素的值。 （3）赋值：setValue（index，newValue） 初始条件：数组已存在。 操作结果：将数组下标为index的数组元素的值设置为newValue。 二、数组顺序存储结构? 1、一维数组 一维数组占用一片地址连续的内存单元，设数组第一个元素a0 的存储地址为，每个元素占用c字节，则数组任意一个元素ai的存储地址为： 2、多维数组 以二维数组为例，一个m行n列的二维数组如下所示： 二维数组的两种存储方式 【例5.1】有二维数组double[ ][ ] arr=new double[4][5]，试问： （1）数组arr中存放多少个数据元素？数组arr总共占用多少字节的存储空间？ （2）假设数组arr的首地址（数组一个元素的地址）为8000，如果采用按行为主序的存储方式，则数组元素arr[2][3]的存储地址是多少？ 三、矩阵的压缩存储 ?? 1