JAVA数据结构第五章数组和广义表.ppt

《JAVA数据结构第五章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《JAVA数据结构第五章数组和广义表.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、广义线性表广义线性表多维数组多维数组广义表广义表逻辑结构逻辑结构存储结构存储结构逻辑结构逻辑结构存储结构存储结构数组的定义数组的定义(2)ADT定义定义(3)基本操作基本操作顺顺序序存存储储压压缩缩存存储储特殊矩阵特殊矩阵对称矩阵对称矩阵三角矩阵三角矩阵对角矩阵对角矩阵稀疏矩阵稀疏矩阵按按行行优优先先按按列列优优先先寻址的计算方法寻址的计算方法基本概念基本概念广义表定义广义表定义表头、表尾表头、表尾长度、深度长度、深度ADT定义定义链链接接存存储储头尾表示法头尾表示法转置算法转置算法线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制插入、删除位置限制插入、删除

2、位置线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。限制元素类型为字符限制元素类型为字符栈栈仅在表尾进行插入和删除操作的线性表。仅在表尾进行插入和删除操作的线性表。队列队列在一端进行插入操作，而另一端进行在一端进行插入操作，而另一端进行删除操作的线性表。删除操作的线性表。串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 。特特殊殊线线性性表表线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。将元素的类型进行扩充将元素的类型进行扩充广广义义线线性性表表（多维）数组（多维）数组线性表中的线性表中的数据元素数据元素可以可以是是

3、线性表线性表，但，但所有元素的类型相同所有元素的类型相同。广义表广义表线性表中的线性表中的数据元素数据元素可以可以是线性表是线性表，且且元素的类型可以不相同元素的类型可以不相同。4.2 数组数组数组（数组（array）：）：是是n(n=0)个个相同数据类型相同数据类型的数据元的数据元素（素（a1,a2,a3,an）构成的）构成的有限线性序列有限线性序列。n为为数组长数组长度度或数组大小。或数组大小。n=0为空数组。为空数组。多维多维数组：一个数组：一个m(m=2)维数组，其维数组，其每个数据元素每个数据元素是一是一个个m-1维的数组维的数组。且每个元素都对应于一组下标。且每个元素都对应于一组下

4、标（j1,j2,jm）,每个每个下标下标的的取值范围取值范围是是cijidi,di-ci+1称为称为第第i维维的的长度长度(i=1,2,n),m为数组的维数。为数组的维数。数组的数组的特点特点：数组中各元素具有数组中各元素具有统一的类型统一的类型；数组元素的下标一般具有数组元素的下标一般具有固定的上界和下界固定的上界和下界。数组的数组的基本操作比较简单基本操作比较简单，除了结构的初始化和销，除了结构的初始化和销毁之外，只有毁之外，只有存取元素存取元素和和修改元素值修改元素值的操作。的操作。数组有数组有顺序存储顺序存储和和链式存储链式存储两种方式。两种方式。一维数组的特点：一维数组的特点：1 1

5、个个下标，下标，a a2 2 是是a a3 3的直接前驱，的直接前驱，a a4 4是是a a3 3的直接后继。注：一维数组的顺序的直接后继。注：一维数组的顺序存储常称为存储常称为向量向量。一维数组存储结构与寻址一维数组存储结构与寻址 设设一一维维数数组组的的下下标标的的范范围围为为闭闭区区间间l，h，每每个个数数组组元元素素占占用用 c 个个存存储储单单元元，则则其其任任一一元元素素 ai 的存储地址可由下式确定：的存储地址可由下式确定：Loc(ai)Loc(al)(il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai)二维数组的特点二维数组的特点：2 2个下标，个下

6、标，每个元素每个元素ai,j受到两个关受到两个关系（行关系和列关系）的约束：系（行关系和列关系）的约束：a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=一个一个mn的二维数组可的二维数组可以看成是以看成是m行的一维数行的一维数组，或者组，或者n列的一维列的一维数数组。组。例如，元素例如，元素a22受两个线性关系的约束，在行上有一个受两个线性关系的约束，在行上有一个行前驱行前驱a21和和一个一个行后继行后继a23，在列上有一个，在列上有一个列前驱列前驱a12和和一个和和一个列后继列后继a32。a11 a12 a1n a21 a22 a2n am1 am2 amnA

7、=A=(A1，A2，An)其中：其中：Ai=(a1i，a2i，ami)(1in)二维数组是数据元素为一维数组（线性表）二维数组是数据元素为一维数组（线性表）的线性表。的线性表。m m维数组的特点：维数组的特点：m m个下标，个下标，每个元素受到每个元素受到m m个关系约束。个关系约束。一个一个m维数组维数组可以看成可以看成是是由若干个由若干个m1维数组维数组组组成的线性表。成的线性表。问题：计算机的存储结构是一维的问题：计算机的存储结构是一维的，而数组一，而数组一般是般是多维多维的，的，怎样存放怎样存放？解决办法：解决办法：事先事先约定按某种次序约定按某种次序将数组元素排将数组元素排成一列序列

8、，然后成一列序列，然后将这个线性序列存入将这个线性序列存入存储器中。存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存存储，也可以规定按储，也可以规定按列列存储存储。注意：注意：若规定好了次序，则数组中任意一个元素的存若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有约定的次序不同，则计算元素地址的公式也有所不同；所不同；常用的常用的映射方法映射方法有两种：有两种：按按行行优先：优先：先行后列先行后列，先存储行号较小的元素，行，先存储行号较小的元素

9、，行号相同者先存储列号较小的元素。号相同者先存储列号较小的元素。按按列列优先：优先：先列后行先列后行，先存储列号较小的元素，列，先存储列号较小的元素，列号相同者先存储行号较小的元素。号相同者先存储行号较小的元素。2、二维数组的存储结构与寻址、二维数组的存储结构与寻址二维数组二维数组内内 存存二维结构二维结构一维结构一维结构0n-1 0m-1(a)二二维维数数组组aij按按行行优先存储的寻址优先存储的寻址 a0,1 a0,n-1 aij am-1,0 am-1,n-1 Amn=数组大小数组大小：（m-1-0+1）*（n-1-0+1）=m*n;设二维数组设二维数组Amn的的首地址首地址A00为为p

10、,每个每个元素占元素占L个存储单元。个存储单元。若已知若已知aij是数组的是数组的第第k个元素，则可得：个元素，则可得：Loc(i,j)=p+k*L;目标：求目标：求aij是数组是数组的第几个元素。的第几个元素。0n-1 0m-1(a)二二维维数数组组本行中本行中aij前面的元素个数前面的元素个数每行元素个数每行元素个数整整行行数数aij按按行行优先存储的寻址优先存储的寻址aij前面的元素个数前面的元素个数=阴影部分的面积阴影部分的面积=整整行行数数每每行行元元素素个个数数+本本行中行中aij前面的元素个数前面的元素个数=(i-0)(n-1-01)(j-0)LOC(aij)=LOC(a00)+

11、i*n+j*Lc2b2 c1b1(a)二维数组二维数组aij前面的元素个数前面的元素个数=阴影部分的面积阴影部分的面积=整整行行数数每每行行元元素素个个数数+本本行行中中aij前面的元素个数前面的元素个数=(i-c1)(b2-c21)(j-c2)本行中本行中aij前面的元素个数前面的元素个数每行元素个数每行元素个数整整行行数数aij通用按通用按行行优先存储的寻址公式：优先存储的寻址公式：数组大小数组大小：（b1-c1+1）*（b2-c2+1）;计算二维数组元素地址的通式计算二维数组元素地址的通式设一般的二维数组是设一般的二维数组是AcAc1 1.d.d1 1,c,c2 2.d.d2 2，这里这

12、里c c1 1,c,c2 2不一不一定是从定是从0 0开始。每个元素占开始。每个元素占L L个存储单位。个存储单位。二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1*L数组的大小数组的大小:(d1-c1+1)*(d2-c2+1)单个单个元素元素长度长度aij之前之前的行数的行数数组基址数组基址总列数，总列数，即第即第2 2维维长度长度aij本行本行前面的前面的元素个元素个数数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)

13、+j-c2*L例例2、已知二维数组已知二维数组Am,m按行存储的元素地址公式是：按行存储的元素地址公式是：Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*K,按列存储的公式是按列存储的公式是？Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）（尽管是方阵，但公式仍不同）例例1、一个二维数组一个二维数组A，行下标的范围是行下标的范围是1到到6，列下标的范围，列下标的范围是是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器按字节个字节存储，存储器按字节编址。那么，这个数组的体积是编址。那么，这个数组的体积是 个字

14、节。个字节。288例例3、设数组设数组a160,170的基地址为的基地址为2048，每个，每个元素占元素占2个存储单元，若以个存储单元，若以列列序为主序顺序存储，则序为主序顺序存储，则元素元素a32,58的存储地址为的存储地址为 。8950答：答：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288Loc(aijk)=Loc(a000)+(im2m3+jm3+k)L 若三维数组若

15、三维数组am1m2m3中，总中，总共有共有m1*m2*m3个数个数组元素。组元素。求求aijk存储地址。存储地址。若按先页、再行后若按先页、再行后列。列。多维数组的存储结构与寻址多维数组的存储结构与寻址链式存储链式存储顺序存储方式：顺序存储方式：按低地址优先（或高地址优先）按低地址优先（或高地址优先）顺序存入一维数组。顺序存入一维数组。（难点难点是是多维数组多维数组与与一维数组一维数组的的地址映射地址映射关系）关系）行指针向量行指针向量a11a12a1nam1am2amn链式存储方式链式存储方式：用用带行指针向量的单链表带行指针向量的单链表来表来表示。示。矩阵类。矩阵类。矩阵运算主要有矩阵加、

16、矩阵减、矩阵乘、矩阵转置等。矩阵加（C=A+B）定义为 public class Matrix private int value;5.2 矩阵的压缩存储矩阵的压缩存储讨论：讨论：1.1.矩阵是很多科学与工程计算问题中研究的数学矩阵是很多科学与工程计算问题中研究的数学对象对象.如何如何存储矩阵中的元素存储矩阵中的元素,使对矩阵的各种操使对矩阵的各种操作作更方便、效率更高更方便、效率更高。2.2.在实际问题中，常遇到一些矩阵，其在实际问题中，常遇到一些矩阵，其元素元素有有许许多值相同多值相同或或大量元素值大量元素值为为零零。如何。如何节省空间节省空间。.什么是压缩存储？什么是压缩存储？多个值多个

17、值相同的元素相同的元素，只分配一个只分配一个元素值的元素值的存储存储空间空间，且，且零零元素元素不占存储空间不占存储空间。.所有二维数组（矩阵）都能压缩吗？所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。未必，要看矩阵是否具备以上压缩条件。.什么样的矩阵具备以上压缩条件？什么样的矩阵具备以上压缩条件？一些一些特殊矩阵特殊矩阵（如：对称矩阵，三角矩阵，对（如：对称矩阵，三角矩阵，对角矩阵）和角矩阵）和稀疏矩阵稀疏矩阵等。等。.什么叫特殊矩阵？什么叫特殊矩阵？若值若值相同的元素相同的元素或者或者零元素零元素在矩阵中的在矩阵中的分布分布有一定规律有一定规律，则该类矩阵称为特殊矩阵

18、。，则该类矩阵称为特殊矩阵。.什么叫稀疏矩阵？（重点）什么叫稀疏矩阵？（重点）若值若值相同的元素相同的元素或者或者零元素零元素在矩阵中的在矩阵中的分布分布不具有规律不具有规律，且矩阵中，且矩阵中非零元素非零元素的的个数个数较少较少（一般（一般小于小于5%5%）时。（无确切定义）时。（无确切定义）一、特殊矩阵一、特殊矩阵、n n阶阶对称矩阵对称矩阵：若：若n n阶矩阵中的元素满阶矩阵中的元素满足如下条件：足如下条件：aij=aji 1i,jn。如：如：压缩存储方案压缩存储方案：为为每一对每一对对称元素对称元素分配一个分配一个存储空间，则可将存储空间，则可将n*nn*n个元素压缩存储到个元素压缩存

19、储到n(n+1)/2n(n+1)/2个元素的空间中。个元素的空间中。方法：方法：）按行序为主序存储其下三角（含对角线）按行序为主序存储其下三角（含对角线元素）（以此为例）元素）（以此为例）按行序为主序存储其上三角（含对角线）按行序为主序存储其上三角（含对角线元素）元素）按列序为主序存储其下三角（含对角线）按列序为主序存储其下三角（含对角线元素）元素）按列序为主序存储其上三角（含对角线）按列序为主序存储其上三角（含对角线元素）元素）aij在一维数组中的序号在一维数组中的序号=阴影部分的面积阴影部分的面积一维数组下标从一维数组下标从0开始开始aij在一维数组中的下标在一维数组中的下标k=i(i+1

20、)/2+j 0 in-10 j n-1 aij每行元素个数每行元素个数12iaij在本行中的序号在本行中的序号aij第第0行行第第1行行第第i-1行行对称矩阵的压缩存储（对称矩阵的压缩存储（存储下三角存储下三角）(c)计算方法计算方法(b)存储说明存储说明(a)下三下三(b)角矩阵角矩阵第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 k n(n+1)/2-1问：如何获取矩阵中的元素（或赋值）？问：如何获取矩阵中的元素（或赋值）？关键关键：找到该元素：找到该元素在一维数组在一维

21、数组sa中中的的位置位置k。即确定。即确定sak与矩阵元素与矩阵元素aij之间存在的之间存在的一一对应关系一一对应关系。（可获得下三角元素）（可获得下三角元素）（可获得上三角元素（不含主对角线）（可获得上三角元素（不含主对角线）注：注：我们将我们将sa就称为就称为n阶对称矩阵的阶对称矩阵的压缩存储压缩存储。若计算若计算aij存放地址，则可以利用以下公式获得：存放地址，则可以利用以下公式获得：LOCaij=LOCa00+（i(i+1)/2+j）*L,i=j，L为每个元素的存储单元大小。为每个元素的存储单元大小。2 2、三角矩阵：、三角矩阵：（）（）上三角矩阵上三角矩阵：是指矩阵的下三角（不包括：

22、是指矩阵的下三角（不包括对角线）中的元均为对角线）中的元均为常数或零常数或零的的n n阶矩阵。阶矩阵。（）（）下三角矩阵下三角矩阵：是指矩阵的上三角（不包括：是指矩阵的上三角（不包括对角线）中的元均为常数或零的对角线）中的元均为常数或零的n n阶矩阵。阶矩阵。压缩存储压缩存储方案方案：只存储其只存储其下（上）三角中的元素下（上）三角中的元素之外，需之外，需加加一个存储一个存储常数常数c c的存储空间即可。的存储空间即可。特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵三角矩阵 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩阵下三角矩阵3 4 8 1

23、0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩阵上三角矩阵矩阵中任一元素矩阵中任一元素aij在数组中的下标在数组中的下标k与与i、j的对应关系：的对应关系：i(i1)/2j 当当ijn(n1)/2 当当ijk=0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22存储存储下三角下三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个如何只存储非零元素？如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。0 12

24、 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0二、稀疏矩阵二、稀疏矩阵、稀疏矩阵的压缩存储、稀疏矩阵的压缩存储问题：问题：如果只存储如果只存储稀疏矩阵中的非零元素，那这些元稀疏矩阵中的非零元素，那这些元素的素的位置信息位置信息该如何表示？该如何表示？解决思路：解决思路：对每个非零元素对每个非零元素增开增开若干存储单元，例如存放若干存储单元，例如存放其所在的其所在的行号行号和和列号列号，便可，便可准确准确反映该元素所在反映该元素所在位位置置。实现方法：实现方法：1)三元组法三元组法 2)十字链表法十字链

25、表法如如:将每个非零元素用一个三元组将每个非零元素用一个三元组（i，j，aij）来表）来表示，则每个示，则每个稀疏矩阵可用一个稀疏矩阵可用一个三元组表三元组表来表示。来表示。方法一方法一:三元组三元组将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值行号，列号，非零元素值)三元组三元组(0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,5,28)，(4,4,50)行号行号列号列号元素元素值值rowcolumnvalue可还原吗？可还原吗？不可以，不可以，须须再加一再加一行行“总体总体”信息：信息：即即总行数、总列数、总行数、总列

26、数、非零元素总个数。非零元素总个数。三元组单链表 行/列的单链表 方法二：方法二：用用三元组链表三元组链表表示表示方法三：方法三：用用十字链表十字链表表示表示用途：用途：方便方便稀疏矩阵的加减稀疏矩阵的加减运算；运算；方法：方法：每个每个非非0元素元素占用占用5个域个域。row：存储非零元素的行号：存储非零元素的行号col：存储非零元素的列号：存储非零元素的列号item：存储非零元素的值：存储非零元素的值right：指针域，指向同一行中的下一个三元组：指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组：指针域，指向同一列中的下一个三元组right downitemc

27、olrow十字链表的特点：十字链表的特点：每行非零元素链接每行非零元素链接成带表头结点的链表成带表头结点的链表(或循或循环链表环链表)；每列非零元素也链接每列非零元素也链接成带表头结点的链表成带表头结点的链表(或或循环链表循环链表)。则每个非零元素既是行链表中的一个结点；又是则每个非零元素既是行链表中的一个结点；又是列链表中的一个结点，即列链表中的一个结点，即呈十字链状呈十字链状。2 0 2M=3 0 0 50 1 0 02 0 0 0 0 0 3 0 3 5 1 1 1稀疏矩阵的压缩存储稀疏矩阵的压缩存储十字链表十字链表(实例实例)rheadchead三、广义表三、广义表1 1、广义表的广义

28、表的定义定义广义表广义表是线性表的推广，也称为是线性表的推广，也称为列表列表（lists）记为：记为：LS =(a1,a2,，an)广义表名广义表名 表头表头(Head）表尾表尾(Tail)第一个元素第一个元素是是表头表头，而，而其余元素组成的表其余元素组成的表称为称为表尾表尾；用用小写字母小写字母表示表示原子类型原子类型，用，用大写字母大写字母表示表示列表列表。n n是表长是表长在广义表中约定在广义表中约定：讨论：讨论：广义表与线性表的区别和联系？广义表与线性表的区别和联系？广义表中元素既可以是原子类型，也可以是列表；广义表中元素既可以是原子类型，也可以是列表；当每个元素都当每个元素都为为原

29、子且类型相同时，就是线性表。原子且类型相同时，就是线性表。广义表的广义表的逻辑结构逻辑结构：直接元素之间是线性关系，：直接元素之间是线性关系，1对对1。常用术语：常用术语：长度：长度：广义表广义表LS中的中的直接元素的个数直接元素的个数；深度：深度：广义表广义表LS中括号的中括号的最大嵌套层数最大嵌套层数。表头：表头：广义表广义表LS非空时，称非空时，称第一个元素第一个元素为为LS的表头；的表头；表尾：表尾：广义表广义表LS中除表头外中除表头外其余元素组成的广义表其余元素组成的广义表。E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递为递归表归表1）A=()2）B=(e)3）C=

30、(a,(b,c,d)4）D=(A,B,C)5）E=(a,E)实训实训1：求下列广义表的长度。求下列广义表的长度。n=0，因为因为A是空表是空表n=1，表中元素表中元素e是原子类型是原子类型n=2，a 为原子，为原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=(),(e),(a,(b,c,d)，共享表共享表ABDCeabcd A=(a,(b,A)实训实训2 2：试用图形表示下列广义表。试用图形表示下列广义表。（设（设 代表原子，代表原子，代表子表）代表子表）D=(A,B,C)=(),(e),(a,(b,c,d)A

31、ab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为 深度括号的层数深度括号的层数 结点的层数结点的层数两种特殊的基本操作：两种特殊的基本操作：GetHead(L)取表头取表头(可能是原子或列表可能是原子或列表);GetTail(L)取表尾取表尾(一定是列表一定是列表)。广义表广义表()和广义表和广义表()不同不同？():长度为长度为0，深度为，深度为 1;():长度为长度为1,深度为深度为2;1.GetTail【(b,k,p,h)】;2.GetHead【(a,b),(c,d)】;3.GetTail【(a,b),(c,d)】;4.GetTail【GetHead【(a,b)

32、,(c,d)】;实训实训3：求下列广义表操作的结果求下列广义表操作的结果(k,p,h)（b）(a,b)5.GetTail【（e）】;6.GetHead【()】.7.GetTail【()】.()(a,b)()()(c,d)2、广义表的存储结构、广义表的存储结构广义表可以采用顺序存储结构吗？广义表可以采用顺序存储结构吗？由于广义表中的数据元素的由于广义表中的数据元素的类型不统一类型不统一（原子（原子或广义表），因此难以采用顺序存储结构来存储。或广义表），因此难以采用顺序存储结构来存储。若若广义表不空广义表不空，则可分解为，则可分解为表头表头和和表尾表尾；反之，；反之，一对确定的表头和表尾可唯一地确

33、定一个广义表。一对确定的表头和表尾可唯一地确定一个广义表。注：采用注：采用头尾表示头尾表示法存储广义表法存储广义表如何采用如何采用链接存储结构链接存储结构存储广义表？存储广义表？广义表的存储结构广义表的存储结构头尾表示法头尾表示法广义表中的数据元素既可以是广义表也可以是单元素广义表中的数据元素既可以是广义表也可以是单元素头尾表示法中的结点结构？头尾表示法中的结点结构？表结点表结点存储广义表；存储广义表；元素结点元素结点存储单元素存储单元素 tag=1 hp tp tag=0 data 表结点表结点 元素结点元素结点tag：区分表结点和元素结点的标志；区分表结点和元素结点的标志；hp：指向指向表头结点表头结点的指针；的指针；tp：指向指向表尾结点表尾结点的指针；的指针；data：数据域，存放单元素。数据域，存放单元素。结点结构结点结构A()B(e)C(a,(b，c，d)NULLA实例如下：实例如下：10eC=(a,(b,c,d)1110a0b0d0c11 B=(e)E(a,E)F()1E0 a11Ftpdatatag=0 标志域标志域 值域值域 指针指针扩展表示扩展表示：三个域结点结构：三个域结点结构指向下一结点指向下一结点tphptag=1 标志域标志域 表头指针表头指针 指针指针原子结点原子结点表结点表结点如如:C=(a,(b,c,d)110c0d0a0b