数组和广义表教程.ppt

(a) 1. 广义表((a), a)的表头是______，表尾是_____ (a) a 2. 广义表(a, b,c,d)的表头是______，表尾是_____ (b,c,d) 3. 已知广义表L=((x,y,z),(u,t,w)),从L表中取出原子t的运算是（ ） A. head[tail[tail[L]]] B. tail[head[head[tail[L]]]] C. head[tail[head[tail[L]]]] D. head[head[tail[tail[L]]]] C 3 4. 广义表((a),((b),c),(((d))))的长度是____，深度是_____ 4 b 5. 广义表L=((a,c),(b,d)),则head[head[tail[L]]]的值是____ 6. 广义表L=((a,b,c),(d,e,f)),应用求表头和表尾运算head和tail提取 出原子 f 的操作。 5.5.2 广义表的存储结构(自学） 由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。 由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。 下面介绍广义表的两种链式存储结构。 1、表结点由三个域组成：标志域、指示表头的指针 域和指示表尾的指针域；而原子域只需两个域：标志 域和值域。 表结点 原子结点 tag=1 hp tp tag=0 atom 其类型定义如下： typedef enum{ATOM,LIST}elemtag; typedeg struct glnode{ elemtag tag; union{ atomtype atom; struct { struct glnode *hp,*tp; }ptr; }; } *glist; 1.画出下面广义表的存储结构图，并求它的深度 ((a,c),b,(d,e)), 5.3 特殊矩阵及其压缩存储 5.3.1 特殊矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 ≤i, j≤n-1 ，则称A为对称矩阵。 1．对称矩阵 例如，图5-1是一个3*3的对称矩阵。 2．三角矩阵 （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0，具体形式见图5-2(a)。 图5-2(a) 上三角矩阵 1 1, 1 1, 11 1 0, 01 00 ... ... ... ... ... ... - - - - n n n n a c c c a a c a a a （2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0，具体形式见图5-2(b)。 1 1 1,1 1,0 11 10 00 ... ... ... ... ... ... ... - - - - ,n n n n a a a c a a c c a 图5-2(b) 下三角矩阵 3．对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。 例如，图5-3为7?7的三对角矩阵（即有三条对角线上元素非0）。 66 65 56 55 54 45 44 43 34 33 32 23 22 21 12 11 10 01 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a a a a a a a a a a a a a a a a a a 图 5 - 3 一个 7X7的三对