西安电子科技大学计算机学院数据结构课件 第5章（2）.pptVIP

1. 广义表的定义（列表） 广义表是线性表的推广，是由零个或多个单元素或子表所 组成的有限序列。 LS=(a1,a2,…,ai,…,an) ai：是单个数据元素,则ai是广义表的原子；如果ai是一个广义表,则ai是广义表的子表。 规定用小写字母表示原子,用大写字母表示广义表的 表名。 广义表与线性表的区别： 线性表的成份都是结构上不可分的单个数据元素，而广 义表的成份即可以是单元素，也可以是有结构的表，其定义 是递归的定义。 广义表的长度：广义表中所含元素的个数n,n≥0。 广义表的深度：广义表展开后所含的括号的最大层数。（广义表中括号嵌套的最大次数，广义表中括弧的重数） D=( )空表，长度为0，深度为1。 A=(a, (b, c)) 长度为2，第一个元素为原子a，第二个元素为子表(b, c)，深度为2。 B=(A, A, D) 长度为3， 其前两个元素为表A， 第三个元素为空表D，深度为3。 C=(a, C) 长度为2递归定义的广义表，C相当于无穷表C=(a,(a, (a,…)))，深度无限。 递归表的深度是无穷值,长度是有限值。 F=((a, (a, b), ((a, b), c))) 长度为1，深度为4。 广义表的表头(Head)和表尾(Tail)： 当广义表非空时，称第一个元素a1为广义表的表头， 其余元素组成的表(a2, a3, …,an)称为广义表的表尾。 表头可能是原子，也可能是广义表，但表尾一定是广 义表。 广义表的图形表示 用方框表示原子，用圆圈表示广义表。 2. 广义表的基本操作 取表头 GetHead(LS) = a1。 取表尾 GetTail(LS) = (a2,a3,…,an)。 ①B=(e) GetHead(B) = e; GetTail(B) = ( ). ②A=(a, ((b, c), d, e)) GetHead( GetHead( GetTail(A))) = GetHead( GetHead( ( ((b, c), d, e) ) )) = GetHead( ((b, c), d, e) ) = (b, c). ③A=( ); B = ( ( ) ) A空表，长度0，深度1，无表头和表尾； B长度1，深度2，表头( )，表尾( )。 3. 广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构。 广义表的头尾链表存储表示 广义表的扩展线性链表存储表示 广义表的头尾链表存储表示 C=(a, (b, c, d)) A=( ) A = NULL; D=( ); A= (a, b, c); B=(A, A, D); C = (a, C). 广义表的扩展线性链表存储表示（带表头结点） D=( ); A=(a, (b, c)); B=(A, A, D); C=(a, C) 作业（5.25 ）矩阵相加。 typedef struct{ ?? ?int rows, cols; ???????int *elem; //存储数组中的非零元 ????????bool **map;//矩阵中相应元素是否为零元素 } BMMatrix; //用位图表示的矩阵类型 void BMMatrixAdd(BMMatrix A,BMMatrix B,BMMatrixC) { C.rows=A.rows; C.cols=A.cols; pa=1; pb=1; pc=1; ?for(i=0; iA.rows; i++) //每一行的相加???? for(j=0; jA.cols; j++) { //每一个元素的相加 if(A.map[i][j]B.map[i][j](A.elem[pa]+B.elem[pb])){ C.elem[pc]=A.elem[pa]+B.elem[pb]; ??C.map[i][j]=1;???pa++; pb++; pc++; ?????? } else if(A.map[i][j]!B.map[i][j]) { C.elem[pc]=A.elem[pa]; C.map[i][j]=1; pa++; pc++; } else if