05 第5章 数组和广义表.pptx

第1页：第五章数组和广义表

第五章数组和广义表

第2页：数组的概述

有关数组的概述

• 线性结构中的数据元素可以是：非结构的原子型，也可以是结构型
• 前面讨论的线性结构中的数据元素都是原子型
• 数组是结构型的线性表，它的值由若干分量组成，每一个分量可以是整数、实数，也可以是数组
• 数组中的数据元素本身也是一种数据结构，例如：
• intA[200],数据元素是整数
• floatB[100,20]数据元素是数组，数组中的元素是实数

第3页：第五章内容提要

内容提要:

• 本章目的：掌握数组的相关概念，特殊矩阵存储方法，稀疏矩阵存储方法及其运算的实现，掌握广义表的概念与存储结构
• 第一节数组的定义
• 第二节数组的顺序表示和实现
• 第三节矩阵的压缩存储
• 第四节广义表的定义与存储结构
• 本章重点

第4页：第一节数组的定义

第一节数组的定义

第5页：数组的有关术语

数组是线性表的推广，它是由下标和值组成的偶对的一个集合

• 数组中，每一组有意义的下标(j1j2…jn),总有一个固定的数值与之相对应，这样的数组称为n维数组
• 当n=1,2,3时，分别称为一维数组、二维数组、三维数组
• 值得注意的是：数组中的所有数据元素都必须属于同一数据类型(1)数组的有关术语

第6页：ADTArray的定义

(2)数组的抽象数据类型定义

• ADTArray{数据对象：ji=0,1,…,bi-1,i=1,2,…,nD={aj1j2…jn|n(>0)称为数组的维数，bi是第i维的长度，ji是数组元素的第i维下标，aj1j2…jnElemset}数据关系：R={R1,R2, …Rn}Ri={<aj1…ji…jn,aj1…ji+1…jn>|0≤jk≤bk-1,0≤k≤n,k !=i//除ji维之外的其他维0≤ji≤bi-2//这样，aj1…ji+1…jn中的ji+1才会≤bi-1aj1…ji…jn,aj1…ji+1…jnD,i=2,…n}例如：D(50,32)二维数组，n=2, b1=50,b2=32J1=0,1,…,49;J2= 0,1,…,31

第7页：数组的基本操作

(2)数组的抽象数据类型定义(续)基本操作：InitArray(&A,n,bound1,…,boundn)//构造数组DestroyArray(&A)//销毁数组Value(A,&e,index1,…,indexn)//返回指定数组的元素Assign(A,e,index1,…,indexn)//给数组元素赋值

• }ADTArray

第8页：数组的讨论

(3)数组的讨论

• 元素aj1…ji…jn(0≤ji≤bi-2)都有一个直接后继
• 数组中的每个元素都对应于一组下标(j1,j2,…jn),每个下标的取值范围是0≤ji≤bi-1,bi称为第i维的长度
• 当n=1时，n维数组退化为定长的线性表，反之n维数组可以看成是线性表的推广
• 例如，对二维数组A[m,n]，可以看成是线性表的线性表n
• n维数组元素个数为bib1b2
• bni1
• 每个元素受着n个关系的约束(n个下标)

第9页：二维数组的线性表视角

(3)数组的讨论(续)

• 二维数组A[m,n]可以是线性表A=(1,2,…,p)，p=m或n
• 其中i可以是行向量，也可以是列向量
• 行向量为i=(i1,i2,…,in)
• 列向量为i=(1i,2i,…,mi)
• 注意：
• n维数组一旦定义，它的维数和维界就不再改变
• 数组的操作：除了初始化和销毁，只能存取和修改元素

第10页：按行序与按列序存放

0a11按行序为主序存放1a12…….n-1a1nna21a11a12……..a1na22a21a22……..a2n……..a2n………………….……….am1am2……..amnam1am2Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*L……..m*n-1amn按列序为主序存放01m-1ma11a21…….am1a12a22……..am2……….a1na2n……..amna11a12a21a22……..……..a1na2n……..am1am2amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*Lm*n-1

第11页：第二节数组的顺序表示和实现

第二节数组的顺序表示和实现

第12页：数组元素存储约定

(1)数组元素存储约定

• 由于数组一旦定义，数据元素的个数和它们之间的关系就不会发生变动，所以采用顺序存储结构
• 对多维结构的数组，采用连续存储单元存放数组的元素需要进行约定
• 例如二维数组有两种存储方式：行主序、列主序
• 通常：BASIC、PASCAL、C语言采用行主序，FORTRAN则采用列主序
• 数组一旦定义了维数和各维的长度，它的存储空间就被确定，各元素的地址也可按一定的公式求得

第13页：二维数组元素存储位置公式

(1)数组元素存储约定(续)n

• 例如，二维数组元素aij的存储位置为
• Loc(i,j)=Loc(0,0)+(b2*i+j)*L
• 其中Loc(0,0)为a00元素的存储位置,L为一个数据元素所占据的存储单元，b2为列数
• 推广到n维时的情况：Loc(j1,j2,...,jn)Loc(0,0,...,0)cijii1其中Cn= L,Ci-1=bi*Ci
• 一旦知道数组数据元素的下标，就可计算其存储位置，所以是随机存储结构

第14页：数组的顺序存储表示

(2)数组的顺序存储表示 #defineMAX_ARRAY_DIM8 typedefstruct{ ElemType*base;//数组维数int*bounds;//数组映象函数基址，由Initarray分配 } Array;

第15页：数组的基本操作函数

(2)数组的顺序存储表示(续)

• 基本操作函数：
• StatusInitArray(Array&A,intdim,…);//构造数组A并返回OK
• StatusDestroyArray(Array&A);//销毁数组A
• StatusValue(Array&A,Elemtype&e, …);//获得某个元素的值并赋给e
• Status Assign(Array &A,Elemtype e, …);//将e的值赋给所指定的元素

第16页：构造数组算法InitArray

(3)算法描述StatusInitArray(Array&A,intdim,…){ if(dim＜1‖dim＞MAX_ARRAY_DIM)returnERROR; A.dim=dim; A.bounds=(int*)malloc(dim*sizeof(int)); if(!A.bounds)exit(OVERFLOW);//ap为va_list类型，是存放变长参数表信息的数组,等价于一次性执行多个scanf(“%d”,&dim)函数for(i=0; i＜dim; ++i); { A.bounds[i]=va_arg(ap,int);elemtotal*=A.bounds[i];va_end(ap);

第17页：InitArray续：映象常数计算

(3)算法描述(续)A.base=(Elemtype*)malloc(elemtotal*sizeof(Elemtype)); if(!A.base)exit(OVERFLOW);if(!A.constants)exit(OVERFLOW); B.constants[dim－1]=1;i＞=0; --i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];}

第18页：销毁数组算法DestroyArray

(3)算法描述(续)

• //销毁数组A
• StatusDestroyArray(Array&A){if(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;returnOK;
• }

第19页：定位数组元素算法Locate

(3)算法描述(续)

• //若ap指示的各下标值合法，则求出该元素在A中相对地址off
• StatusLocate(ArrayA,va_listap,int&off){
• off=0;
• for(i=0;i＜A.dim;++i);{ind=va_arg(ap,int);if(ind＜0||ind＞=A.bounds[i])returnOVERFLOW;noff+=A.bounds[i]*ind//off为ci偏ji移量(offset)i1
• }
• returnOK;
• }

第20页：取数组元素值算法Value

//A是n维数组，e为元素变量，随后是n个下标值。

• //若各下标不超界，则e赋值为所指定的A的元素值，并返回OK
• StatusValue(ArrayA,Elemtype&e,…){Va_start(ap,e);if((result=Locate(A,ap,off))result;//地址错误e=*(A.base+off);returnOK;＜=0)return
• }(3)算法描述(续)

第21页：数组元素赋值算法Assign

//A是n维数组，e为元素变量，随后是n个下标值。

• //若下标不超界，则将e的值赋给所指定的A的元素，并返回OK
• StatusAssign(Array&A,Elemtypee,…){Va_start(ap,e);if((result=Locate(A,ap,off))＜=0)returnresult;*(A.base+off)=e;returnOK;
• }(3)算法描述(续)

第22页：矩阵转置运算

（4）以二维数组（矩阵）讨论多维数据的基本运算

• 转置矩阵
• 一个m*n的矩阵Amn的转置矩阵是n*m的矩阵Bnm，其中B[i,j]=A[j,i]。
• Voidtrsmat(maxixA,MaxixB){inti,j;for(i=0;i<m;i++)for(j=0;j<n;j++)B[j][i]=A[i][j];
• }

第23页：矩阵相加运算

一个m*n的矩阵Amn和一个n*m的矩阵Bnm相加得到一个m*n的矩阵Cmn其中cij=aij+bij。

• Voidaddmat(maxixC,maxixA,MaxixB){inti,j;for(i=0;i<m;i++)for(j=0;j<n;j++)C[i][j]=B[j][i]+A[i][j];
• }
• 矩阵相加

第24页：矩阵相乘运算

矩阵相乘

• 一个m*n的矩阵Amn和一个n*o的矩阵Bno相乘得到一个m*o的矩阵Cmo。
• Voidmutmat(maxixC,maxixA,MaxixB){inti,j,k;for(i=0;i<m;i++)for(j=0;j<o;j++)C[i][j]=0;for(k=0;k<n;k++)C[i][j]=C[i][j]+A[i][k]+B[k][j];
• }

第25页：第三节矩阵的压缩存储

第三节矩阵的压缩存储

第26页：矩阵的压缩存储讨论

(1)矩阵的讨论

• 矩阵的存贮通常用二维数组来表示，一个数据元素占据一个存储空间
• 当相邻数据元素相同或有许多零元素时，可以采用一定的方法进行压缩存储
• 压缩存储就是为多个相同的元素分配一个存储空间，零元素不分配存储空间
• 当相同元素在矩阵中的分布有一定的规律称为特殊矩阵

第27页：特殊矩阵的类型

(2)特殊矩阵

• 常见特殊矩阵的类型
• 对称矩阵：aij=aji
• 下(上)三角矩阵：上(下)三角(不含对角线)中的元素均为常数c或零的n阶矩阵
• 对角矩阵：所有非零元素都集中在以主对角线为中心的两侧

第28页：特殊矩阵的压缩思路

(2)特殊矩阵(续)

• 压缩思路
• 将二维数组压缩成一维数组，但必须找到二维与一维的对应关系
• 例如：对称矩阵的二维存储空间为n2,可以压缩成n(n+1)/2，一维下标k和二维下标(i,j)的对应公式为：ki1,当ij当ij2j(j1)2i(i1)j1,

第29页：对称矩阵的压缩存储

对称矩阵的压缩存储j(j1)/2i1,ija11a12a21….……..a1n……..an1an2anna22……..…….a2n………………….ann…...an1…...a32a31a22a21a11k=01234ki(i1)/2j1，ijn(n-1)/2n(n+1)/2-1按行序为主序：

第30页：三角矩阵的压缩存储

a11a2100……..0a220……..0an1an2an3……..………………….0annijLoc(a)=Loc(a11+(j-1)]*l2ann…...an1…...a32a31a22a21a11k=01234)+[(i(i-1)n(n-1)/2n(n+1)/2-1按行序为主序：三角矩阵的压缩存储

第31页：对角矩阵的压缩存储

00…an-1,n-200……0…………….a120a1100……………a22a23a210a340………a32a330an-1,n-1an,n-1an-1,nann……………………………Loc(aij)=Loc(a11)+2(i-1)+(j-1)annann-1…...…...a23a22a21a12a11k=012343n-2按行序为主序：对角矩阵的压缩存储

第32页：对角矩阵元素个数计算

前面的例子中有3条非0元素（m=3），元素个数为3*n-2;

• 对一个非0元素的条数为m(1<=m<n)的n阶对角矩阵，元素的个数应该为：
• m*n-(m/2)*(m/2+1)
• 其中符号a为取a的下整，3/2=1，5/2=2

第33页：稀疏矩阵与三元组

东华理工学院程朋根十字链表法(3)稀疏矩阵

• 当矩阵中的非零元素比较少，且分布没有一定的规律，称为稀疏矩阵
• 稀疏矩阵的衡量标准，可以用稀疏因子表示，通常认为当≤0.05是称为稀疏矩阵其中t为矩阵中非零元素的个数
• 如果进行压缩，只需存储矩阵中非零元素，同时记录它在矩阵中的行、列号，既(i, j,aij),称为三元组，它唯一确定矩阵中的一个非零元素
• 稀疏矩阵的存储方式：三元组顺序表示法行逻辑链接的顺序表示法mnt

第34页：三元组表存储结构

三元组表所需存储单元个数为3(t+1)其中t为非零元个数8761221931-3131463243418251516-746M.datae012345678data[0].i,data[0].j,data[0].e分别存放矩阵行列维数和非零元个数行列下标ij非零元值00009012000000014000030M00002400000000180067070150稀疏矩阵的压缩存储方法

第35页：ADTSparseMatrix的定义

(4)稀疏矩阵抽象数据类型定义

• ADTSparseMatrix{
• 数据对象：D={aij|i=1,2,…,m,j= 1,2,…,n,aijElemset, m,n称为行数和列数}
• 数据关系：R={Row,Col}Row{<ai,j,ai,j+1>|0≤i≤m,0≤j≤n-1}Col{<ai,j,ai+1,j>|0≤i≤m-1,0≤j≤n}

第36页：稀疏矩阵的基本操作

(4)稀疏矩阵抽象数据类型定义(续)

• 基本操作：CreateSMatrix(&M)//创建稀疏矩阵MDestroySMatrix(&M)//销毁稀疏矩阵AddSMatrix(M,N,&Q)//求稀疏矩阵的和MultiSMatrix(M,N,&Q)//求稀疏矩阵的积TransposeSMatrix(M,&T)//求稀疏矩阵的转置…………
• }ADTSparseMatrix

第37页：三元组顺序表示法

(5)三元组顺序表示法

• #defineMAXSIZE12500//非零元个数的最大值为12500
• typedefstruct{//该非零元的行下标和列下标e;inti,j;Elemtype
• }Triple;
• typedefstruct{Tripledata[MAXSIZE+1];//非零元三元组表，data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元个数
• }TSMatrix;
• 并以行为主序顺序排列

第38页：矩阵转置算法思路

(6)三元组顺序表示的矩阵转置算法

• 二维矩阵M的转置T矩阵是使的T(i,j) =M(j,i)，其算法为
• for(col=1;col<=mu;++col)
• for(row=1;row<=nu;++row)
• T[col][row]=M[row][col]
• 显然时间复杂度是O(mu*nu)
• 稀疏矩阵的转置必须进行的操作(解决思路)：矩阵的行列号相互交换、三元组的i和j互换、重排三元组的次序

第39页：稀疏矩阵转置示例

0002400001800000150070006700000000901200001400003M09T08761221931-3131463243418251516-746ijv012345678Mv8-3151218924-70030015000180120024000007000000001400000000076ij76131621253134466314012345678T?

第40页：稀疏矩阵转置的两种方法

(6)三元组顺序表示的矩阵转置算法(续)

• 转置两种方法：
• (1)按转置后的三元组的次序依次在转置前的三元组中寻找相应的值
• (2)先将转置前的三元组进行转置，然后将转置后的三元组置入转置后矩阵的恰当位置

第41页：方法一：按列序转置

方法一：按M的列序转置

• 按T.data中三元组次序依次在M.data中找到相应的三元组进行转置；
• 为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍;O由于M.data中以M行序为主序来存放每个非零元素，所以由此得到的恰是T.data中应有的顺序。即列相同时，行是依次存放，这样找到的元素在T.data中不需要重新排序
• 例如：

第42页：列序转置三元组对照

vji1221931-3131463243418251516-746vji-3311561121218529132443-7641436原矩阵M转置矩阵TM中（3，1，-3）、（6，1，15）的顺序和T中（1，3，-3）（1，6，15）顺序一致

第43页：列序转置过程示意

8761221931-3131463243418251516-746ijv012345678m867-3311561121218529132443-7641436ijv012345678tkppppppppkkkkppppppppcol=1col=2

第44页：算法5.1求转置矩阵T

算法5.1求稀疏矩阵M的转置矩阵TStatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){ q=1; for(col=1; col＜=M.nu; ++col)for(p=1; p＜=M.tu; ++p)if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++q; } } returnOK; } 
第45页：方法二：快速转置
方法二：快速转置0即按M中三元组次序转置，转置结果放入T中恰当位置0此法关键是要预先确定M中每一列第一个非零元在T中位置0为确定这些位置，转置前应先求得M的每一列中非零元个数0设置num和cpot两个向量，num[col]表示矩阵M中第col列非零元素的个数，cpot[col]指示M中第col列的第一个非零元素在T中的恰当位置0其中：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]算法5.2的思路
第46页：快速转置的num与cpot
7654321col0101222num[col]9887531cpot[col]0009120000014000000024000001800700000006700001503M算法5.2的思路vji1221931-3131463243418251516-746
第47页：算法5.2快速转置
//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col＜=M.nu;++col)num[col]=0;for(t=1;t＜=M.tu;+ +t)++num[M.data[t].j];//求M中每一列含非零元个数cpot[1]=1;//求第col列中第一个非零元在T(b.data)中的序号for(col=2;col＜=M.nu;++col）cpot[col]=cpot[col－1]+num[col－1];算法5.2
第48页：快速转置续：元素放置
for(p=1;p＜=M.tu;++p)col=M.data[p].j;{q=cpot[col];//col为M中的列号，q为当前数据（M.data[p]）在Ｔ中的顺序号T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}//for}//ifreturnOK;//时间复杂度为O(nu+tu),
}//当tu和mu*nu接近时，时间复杂度为O(mu*nu)算法5.2(续)
第49页：快速转置过程示意
8761221931-3131463243418251516-746ijv012345678maijv012345678mb867-3311561121218529132443-76414367654321col0101222num[col]9887531cpot[col]pppppppp9246357
第50页：稀疏矩阵转置应用程序
稀疏矩阵的转置算法应用程序
第51页：行逻辑链接的顺序表
(7)行逻辑链接的顺序表
为了便于随机存取任一行的非零元素，需要知道每一行非零元素在三元组表中的位置，方法是将上述方法的rpot保存在稀疏矩阵的存储结构中,具体为：
Typedefstruct{Tripledata[MAXSIZE+1];//非零元三元组表intrpos[MAXRC]；//各行第一个非零元的位置表intmu,nu,tu;
}
第52页：稀疏矩阵相乘思路
矩阵相乘
稀疏矩阵相乘：找到M中的j值和N中的i值相等的元素相乘即可，即(i,k,M(i,k))与(k,j,N(k,j))相乘。
为了快速找到N中对应的i值，设置rpos[]可以提高速度ni1Q(i,j)M(i,k)N(k,j)vji221112-2134234321row5321rpos[row]
第53页：稀疏矩阵相乘的累计和
稀疏矩阵相乘时，对M中的M.data[p]在N中寻找所有满足M.data[p].j=N.data[q].i条件的N.data[q],并求M.data[p].v和N.data[q].v的乘积；这个乘积只是乘积矩阵Q(i,j)中的一部分，为此需要设置一个累计和变量ctemp[]，其初值为零：ctemp[] =0;
稀疏矩阵相乘积不一定是稀疏矩阵
第54页：算法5.3矩阵相乘
vji311541-122根2学1院程朋东3华理工算法5.3StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){ if(M.nu!=N.mu)returnERROR; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;//Q是非零矩阵for(arrow=1; arow＜=M.mu; ++arrow){Q.rops[arrow]=Q.tu+1;p＜M.rpos[arrow+1]; ++p){ brow=M.data[p].j;else{ t=N.tu +1} 
第55页：算法5.3续：压缩存储结果
算法5.3(续)for(q=N.rpos[brow];q＜t;++q){ccol=N.data[q].j//乘积元素在Q中列号ctemp[ccol]+=M.data[p].e*N.data[[q].e;}//forq}//forq,求得Q中第crow(=arow)行的非零元for(ccol=1;ccol＜=Q.nu;++ccol)//压缩存储该行非零元if(ctemp[cool]){if(++Q.tu＞MAXSIZE)returnERROR;Q.data[Q.tu]={arrow,ccol,ctemp[ccol]};}//if}//forarrow}//ifreturnOk;
｝//MultSMatrix
第56页：十字链表的提出
(8)十字链表
当矩阵的非零元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表
例如:两个矩阵相加时，非零元素的插入会使线性表中的元素移动，此时用链式存储结构表示三元组的线性表更为恰当
链表中，一个结点含５个域：行号、列号、非零元的值、右链指针，下链指针
第57页：十字链表结点结构
结构设计为：
typedefsstructOLNode{intElemtypei,j ;//该非零元的行和列下标e;StructOLNode*right,*down ;//该非零元所在行表和列表的后继链域
}OLNode;*Olink;
typedefsstruct{Olink*rhead,*chead;//行和列链表头指针向量基址由CreatSMatrix分配intmu,nu,tu ;//稀疏矩阵的行数、列数和非零元个数
} Crosslist;ejirightdown
第58页：算法5.4创建稀疏矩阵
算法5.4创建稀疏矩阵 StatusCreatSMatrix_OL(Crosslist&M){ if(M)free(M); Scanf ( &m ,&n, &t ) ;M.nu:=n; M.tu:=t; if(!(M..rhead=(Olink*)malloc((m+1)*sizeof(Olink))))exit(OVERFLOW); if(!(M.chead=(Olink*)malloc((n+1)*sizeof(Olink))))exit(OVERFLOW); M.rhead[ ]=M.chead[ ]=NULL; 
第59页：算法5.4续：结点插入
for(scanf(&i,&j,&e); i!=0; scanf(&i,&j,&e)){P->i=i; P->j=j; P->e=e;else{(q->right)&&q->right->j<j; q=q->right; )p->right=q->right; q->right=p; }else{(q->down)&&q->down->i＜i; q=q->down; )p->down=q->down; } returnOk; q->down=p; }} 
第60页：十字链表创建实例
814^^432^^m=4,n=31,1,32,2,52,3,44,1,82,1,7113^^217^^225^^04043083000500A创建稀疏矩阵—实例
第61页：第四节广义表的定义与存储结构
第四节广义表的定义与存储结构
第62页：广义表的术语
(1)广义表的术语
广义表是线性表的推广,广泛应用于人工智能领域的LISP与语言
广义表一般记作LS=(1,2,…,n)，其中LS为广义表(1,2,…,n)的表名，n是它的长度
线性表与广义表的区别：
线性表的元素只限于单个元素
广义表的元素可以是单个元素、也可以是广义表，并分别成为广义表LS的原子或子表
当广义表非空时，第一个元素1为表头(head),其余元素(2,…,n)组成表尾(Tail)
第63页：广义表举例
(2)广义表举例
A= (),A是空表，表长为０
B=(e),列表B只有一个原子e,长度为１
C=(a,(b,c,d)),列表C长度为２，有一个原子a和一个子表(b,c,d)
D=(A,B,C),列表D的长度为３，三个元素都是列表，显然D=((),(e),(a,(b,c,d)))
E=(a,E),列表E是一个递归表，长度为２，相当于(a,(a,(a,…)))BCeaDAbcd
第64页：广义表的结构特点
结论：Bea
列表的元素可以是子表，而子表的元素还可以是子表，是一个多层次的结构；
列表可为其他列表所共用，并通过子表名来引用,例如，D可以不必列出子表的值，而直接通过子表A,B,C名称来引用；
列表可以是一个递归表；
m元多项式表示是典型实例
注意表()与表(())的不同：前者为空表，长度为零；后者长度为1，可以分解成表头表尾均为空表()DACbcd
第65页：ADTGlist的定义
(3)抽象数据类型广义表定义
ADTGlist{
数据对象：D={ei|i=1,2,…,n;n≥0;eiAtomset或eiGlist,Atomset为某个数据元素}
数据关系：R= {<ei-1,ei>|ei-1,eiD, 2≤i≤n-2}
基本操作：InitGList(&L)//创建一个空广义表CreateGList(&L,S)//由S创建广义表CreateGList(&L,S)//销毁广义表GListLength(L)//求广义表的长度，即元素的个数GetHead(L)//得到广义表L的头InsertFirst(&L,e)//插入元素作为广义表L的第一个元素…………
} ADTGLIst
第66页：广义表的存储结构
(4)广义表的存储结构
广义表的数据元素具有不同的数据结构，难以用顺序存储结构来表示，通常采用链式存储结构
表中的元素分原子和列表，结点分表结点、原子结点
表结点包括：标志域、表头指针、表尾指针
原子结点包含：标志域、值域
第67页：头尾链表存储表示
结构一：头尾链表存储表示
Typedefenum{ATOM,LIST}ElemTag;ATOM==0原子，LIST==1子表
TypedefstructGLNode{ElemTagtag;
Union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域，ptr.hp和ptr.tp分别志向表头和表尾
};
}*Glist;(4)广义表的存储结构(续)tag=0atomtphptag=1
第68页：头尾链表存储实例
A=NULLB10eC110a1110b0c0dD111E110a
除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点
容易分清列表中原子和列表的层次
最高层次结点个数即为列表的长度BCeaDAbcd
第69页：扩展线性链表存储表示
结构二：扩展线性链表存储表示
Typedefenum{ATOM,LIST}ElemTag;ATOM==0原子，LIST==1子表
TypedefstructGLNode{
ElemTagtag;
Union{AtomTypeatom;structGLNode*hp; 
第70页：本章重点
本章重点
数组的定义、特点
数组的顺序表示
稀疏矩阵与表示方法
广义表的定义与存储结构
第71页：课堂练习
课堂练习：
1、一维数组和线性表的区别是：前者长度固定，后者的长度可变。
2、对数组进行的两种操作是：查找和修改。
3、数组中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内。该数组按行存放时，A[8][5]的起始地址为：SA+((8-1)*10+(5-1))*3=SA+222。
5、稀疏矩阵一般的压缩存储方法有两种：三元组和十字链表。
6、广义表((a,b),c,d)的表头是:(a,b)，表尾是:(c,d)。
7、广义表((a),((b),c),(((d))))的长度是:3，深度是:4。
第72页：习题（一）
习题：
1、一维数组和线性表的区别是：前者长度固定，后者的长度可变。
2、对数组进行的两种操作是：查找和修改。
3、数组中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内。该数组按行存放时，A[8][5]的起始地址为：SA+((8-1)*10+(5-1))*3=SA+222。该数组按列存放时，A[5][8]的起始地址为：SA+((8-1)*8+(5-1))*3=SA+180。
4、设矩阵A是对称矩阵，为了节省次、存储空间，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对任一下三角元素aij（i>=j），在一维数组B的下标位置k的值是:i(i-1)/2+j。
第73页：习题（二）
5、稀疏矩阵一般的压缩存储方法有两种：三元组和十字链表。
6、广义表((a,b),c,d)的表头是:(a,b)，表尾是:(c,d)。
7、广义表((a),((b),c),(((d))))的长度是:3，深度是:4。
8、假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也采用三元组表示。习题：