《第五章 数组和广义表.ppt》由会员分享，可在线阅读，更多相关《第五章 数组和广义表.ppt（120页珍藏版）》请在三一办公上搜索。
1、1,第五章 数组和广义表,2,作为抽象数据类型的数组,一维数组一维数组的示例,5.1数组的定义,3,一维数组的特点,连续存储的线性聚集（别名 向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,4,数组的定义和初始化,#include class szcl int e;public:szcl()e=0;szcl(int value)e=value;int get_value()return e;,5,main()szcl a13=3,5,7,*elem;for(int i=0,i3,i+)cout a1i.get_value
2、()“n”;/打印静态数组 elem=,6,一维数组(Array)类的定义,#include#include template class Array Type*elements;/数组存放空间 int ArraySize;/当前长度 void getArray();/建立数组空间 public:Array(int Size=DefaultSize);Array(const Array,7,Array()delete elements;Array,8,template void Array:getArray()/私有函数：创建数组存储空间 elements=new TypeArraySize;
3、if(elements=0)cerr Memory Allocation Error endl;,一维数组公共操作的实现,9,template void Array:Array(int sz)/构造函数 if(sz=0)cerr Invalid Array Size endl;return;ArraySize=sz;getArray();,10,template Array:Array(const Array,11,template Type,12,template void Array:Resize(int sz)if(sz=0,13,行向量 下标 i 页向量 下标 i列向量 下标 j 行向
4、量 下标 j 列向量 下标 k,二维数组 三维数组,14,数组的ADT定义,ADT Array 数据对象：ji=0,bi-1,i=1,2,n D=aj1j2jn|n称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标，aj1j2jn ElemSet R=R1,R2,Rn/每个元素受到n个关系的约束 Ri=|0 jk bk-1,1 k n 且 k i 0 ji bi-2,aj1jijn,aj1,ji+1jn D,i=2,n P:InitArray(&A,n,bound1,boundn)DestoryArray(&A)Value(A,&e,index1,indexn)/取出元素值 A
5、ssign(&A,e,index1,indexn)/给元素赋值ADT Array,15,5.2数组的顺序表示和实现,一维数组,LOC(i)=LOC(i-1)+l=+i*l,16,行优先 LOC(j,k)=a+(j*m+k)*l,二维数组,17,n维数组,各维元素个数为 m1,m2,m3,mn下标为 i1,i2,i3,in 的数组元素的存储地址：,18,1 设二维数组A5,6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?,因含5*6=30个元素，因此A共占30*4=120个字节。a45的起
6、始地址为：Loc(a45)=Loc(a00)+(i*m1+j)*l=1000+(4*6+5)*4=1116,按行优先顺序排列时，a25=1000+(2*6+5)*4=1068按列优先顺序排列时：(二维数组可用行列下标互换来计算)a25=1000+(5*5+2)*4=1108,19,按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便阅读，只要按从左到右的顺序存放就是在内存中的排列位置),请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000.,a0000 a0001 a0002 a0010
7、 a0011 a0012 a0100 a0101 a0102 a0110 a0111 a0112 a0200 a0201 a0202 a0210 a0211 a0212 a1000 a1001 a1002 a1010 a1011 a1012 a1100 a1101 a1102 a1110 a1111 a1112 a1200 a1201 a1202 a1210 a1211 a1212,20,数组的顺序存储表示和实现,p93-94,21,22,5.3矩阵的压缩存储,特殊矩阵 值相同的元素或零元素在矩阵中的分布有规律对称矩阵三角矩阵对角矩阵稀疏矩阵 值相同的元素或零元素在矩阵中的分布无规律，且零元素
8、个数/矩阵所有元素个数=0.05,23,5.3.1 特殊矩阵的压缩存储,24,（a）一个下三角矩阵（b）下三角矩阵的压缩存储形式矩阵及用下三角压缩存储,25,26,27,3对角矩阵我们仅讨论三对角矩阵的压缩存储，五对角矩阵，七对角矩阵等读者可以作类似分析。在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，,sk与aij的对应关系为：3i或 3j 当 i=j k=3i+1或3j-2 当i=j-1,3i-1 或3j+2 当 i=j+1,28,特殊矩
9、阵的压缩存储,小结特殊矩阵(如对称矩阵、三角矩阵、对角矩阵等)中，非零元素的分布有明显的规律，因此我们可以将其压缩存储到一维数组中，并找到每个非零元素在一维数组中的对应关系,29,30,5.3.2 稀疏矩阵(Sparse Matrix),行数m=6,列数n=7,非零元素个数t=6稀疏因子=0.05,31,稀疏矩阵(SparseMatrix)的抽象数据类型 template class SparseMatrix int Rows,Cols,Terms;/行/列/非零元素数 Trituple smArrayMaxTerms;public:/三元组表 SparseMatrix(int MaxRow,
10、int Maxcol);SparseMatrix Transpose();/转置 SparseMatrix/相加 Add(SparseMatrix b);SparseMatrix/相乘 Multiply(SparseMatrix b);,32,三元组(Trituple)类的定义 template class SparseMatrix;template class Trituple friend class SparseMatrix private:int row,col;/非零元素所在行号/列号 Type value;/非零元素的值,33,稀疏矩阵,转置矩阵,34,1 用三元组表表示的稀疏矩阵
11、及其转置,35,稀疏矩阵转置算法5.1思想p99A的列序 B的行序,设矩阵列数为Cols，对矩阵三元组表扫描Cols次。第k次检测列号为k的项。第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。设矩阵三元组表总共有Terms项，其时间代价为 O(Cols*Terms)。若矩阵有200行，200列Cols，10,000个非零元素Terms，总共有2,000,000次处理。,一般矩阵转置算法Rows*Cols Terms=Rows*Cols,36,稀疏矩阵的转置 template SparseMatrix SparseMatrix:Transpose()Spar
12、seMatrix b;b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;/转置矩阵的列数,行数和非零元素个数 if(Terms 0)int CurrentB=0;/转置三元组表存放指针,37,for(int k=0;kCols;k+)for(int i=0;iTerms;i+)if(smArrayi.col=k)b.smArrayCurrentB.row=k;b.smArrayCurrentB.col=smArrayi.row;b.smArrayCurrentB.value=smArrayi.value;CurrentB+;return b;,38,快速转置算法5.2
13、 p100,建立辅助数组rowSize和rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。（转置前为列）扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查rowStart表，按查到的位置直接将该项存入转置三元组表中。转置时间代价为 O(max(Terms,Cols)。若矩阵有200列，10000个非零元素，总共需10000次处理。,39,快速转置算法 例,40,for(int i=0;iCols;i+)rowSizei=0;for(i=0;iTerms;i+)rowSizesmArrayi.col+;/rowStart0=0;for(i=1;i Co
14、ls;i+)rowStarti=rowStarti-1+rowSizei-1;/A的第i列开始存放的位置=A的第i-1列开始存放的位置+A的第i-1列非零个数,41,42,2带行指针的链表把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，图1 的稀疏矩阵M的带行指针的链表描述形式见图2。,图2 带行指针的链表,2带行指针的链表,图1 稀疏矩阵M,43,44,在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元
15、很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种规律，除存放非零元的值外，还必须存储适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。下面将介绍稀疏矩阵的几种存储方法及一些算法的实现。,5.4 稀疏矩阵,45,5.4.1 稀疏矩阵的存储,1三元组表在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号，则称为三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存储（按行优先顺序存放）。一个非零元有行号、列号、值，为一个三元组，整个稀疏矩阵中非零元的三元组合起来称为三元组表。此时，数据类型
16、可描述如下：#define maxsize 100/*定义非零元的最大数目*/struct node/*定义一个三元组*/int i,j;/*非零元行、列号*/int v;/*非零元值*/;struct sparmatrix/*定义稀疏矩阵*/int rows,cols;/*稀疏矩阵行、列数*/int terms;/*稀疏矩阵非零元个数*/node data maxsize;/*三元组表*/;,46,47,2带行指针的链表把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，图5-6的稀疏矩阵M的带行指针的链表描述形式见图5-9。,图5
17、-9 带行指针的链表,48,3十字链表当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组（i,j,v）外，还需增加两个链域：行指针域（rptr），用来指向本行中下一个非零元素；列指针域（cptr），用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零元也通过cptr指针链接成一个带表头结点的循环链表。因此，每个非零元既是第i行
18、循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。另外，为了运算方便，我们规定行、列循环链表的表头结点和表示非零元的结点一样，也定为五个域，且规定行、列、域值为0(因此，为了使表头结点和表示非零元的表结点不发生混淆，三元组中，输入行和列的下标不能从0开始!而必须从1开始)，并且将所有的行、列链表和头结点一起链成一个循环链表。在行（列）表头结点中，行、列域的值都为0，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点本身又可以通过V域（非零元值域，但在表头结点中为next，指向下一个表头结点）相链接。另外，再增加一个
19、附加结点（由指针hm指示，行、列域分别为稀疏矩阵的行、列数目），附加结点指向第一个表头结点，则整个十字链表可由hm指针惟一确定。,49,例如，图5-6的稀疏矩阵M的十字链表描述形式见图5-10。十字链表的数据类型描述如下：struct linknode int i,j;struct linknode*cptr,*rptr;union vnext/*定义一个共用体*/int v;/*表结点使用V域,表示非零元值*/struct linknode next;/*表头结点使用next域*/k;,50,图5-10 稀疏矩阵的十字链表,51,5.4.2 稀疏矩阵的运算,1稀疏矩阵的转置运算下面将讨论三元
20、组表上如何实现稀疏矩阵的转置运算。转置是矩阵中最简单的一种运算。对于一个mn的矩阵A，它的转置矩阵B是一个nm 的，且Bij=Aji，0in,0jm。例如，图5-6给出的M矩阵和图5-7给出的N矩阵互为转置矩阵。在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?从转置的性质知道，将A转置为B，就是将A的三元组表a.data变为B的三元组表b.data，这时可以将a.data中i和j的值互换，则得到的b.data是一个按列优先顺序排列的三元组表，再将它的顺序适当调整，变成行优先排列，即得到转置矩阵B。下面将用两种方法处理：（1）按照A的列序进行转置由于A的列即为B的行，在a.data中，按列扫描，
21、则得到的b.data必按行优先存放。但为了找到A的每一列中所有的非零的元素，每次都必须从头到尾扫描A的三元组表（有多少列，则扫描多少遍），这时算法描述如下：,52,#define maxsize 100struct node int i,j;/*定义三元组的行、列号*/int v;/*三元组的值*/;struct sparmatrix int rows,cols;/*稀疏矩阵的行、列数*/int terms;/*稀疏矩阵的非零元个数*/struct node datamaxsize;/*存放稀疏矩阵的三元组表*/;void transpose(struct sparmatrix a)struc
22、t sparmatrix b;/*b为a的转置*/int ano,bno=0,col,i;b.rows=a.cols;b.cols=a.rows;b.terms=a.terms;if(b.terms0)for(col=0;cola.cols;col+)/*按列号扫描*/for(ano=0;anoa.terms;ano+)/*对三元组扫描*/,53,if(a.dataano.j=col)/*进行转置*/b.databno.j=a.dataano.i;b.databno.i=a.dataano.j;for(i=0;ia.terms;i+)/*输出转置后的三元组结果*/printf(%5d%5d%5
23、dn,b.datai.i,b.datai.j,b.datai.v);void main()int i;struct sparmatrix a;scanf(%d%d%d,/*调用转置算法*/,54,分析这个算法，主要工作在col和ano二重循环上，故算法的时间复杂度为 O(a.cols*a.terms)。而通常的mn阶矩阵转置算法可描述为：for(col=0;coln;col+)for(row=0;rowm;row+)bcolrow=arowcol;它的时间复杂度为O(mn)。而一般的稀疏矩阵中非零元个数a.terms远大于行数m，故压缩存储时，进行转置运算，虽然节省了存储单元，但增大了时间复杂
24、度，故此算法仅适应于a.ternsa.rows a.cols的情形。,（2）按照A的行序进行转置即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。若能在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置potcol（0cola.cols），那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datapotcol中，之后将potcol内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向量pot，只要先求出A的每一列中非零元个数numcol，然后利用下面公式：potcol=potcol-1+
25、numcol-1 当1cola.cols,pot0=0,55,为了节省存储单元，记录每一列非零元个数的向量num可直接放入pot中，即上面的式子可以改为：potcol=potcol-1+potcol，其中1colacols。于是可用上面公式进行迭代，依次求出其他列的第一个非零元素转置后在b.data中的位置potcol。例如，对前面图5-6给出的稀疏矩阵M，有：每一列的非零元个数为pot1=2 第0列非零元个数pot2=2 第1列非零元个数pot3=2 第2列非零元个数pot4=1 第3列非零元个数pot5=0 第4列非零元个数pot6=1 第5列非零元个数pot7=0 第6列非零元个数,每一
26、列的第一个非零元的位置为pot0=0第0列第一个非零元位置pot1=pot0+pot1=2第1列第一个非零元位置pot2=pot1+pot2=4第2列第一个非零元位置pot3=pot2+pot3=6第3列第一个非零元位置pot4=pot3+pot4=7第4列第一个非零元位置pot5=pot4+pot5=7第5列第一个非零元位置pot6=pot5+pot6=8第6列第一个非零元位置,56,则M稀疏矩阵的转置矩阵N的三元组表很容易写出（见图5-8），算法描述如下：#define maxsize 100struct node int i,j;int v;struct sparmatrix int r
27、ows,cols;int terms;struct node datamaxsize;void fastrans(struct sparmatrix a)struct sparmatrix b;int potmaxsize,col,ano,bno,t,i;b.rows=a.cols;b.cols=a.rows;b.terms=a.terms;if(b.terms0),57,for(col=0;col=a.cols;col+)potcol=0;for(t=0;ta.terms;t+)/*求出每一列的非零元个数*/col=a.datat.j;potcol+1=potcol+1+1;pot0=0;f
28、or(col=1;cola.cols;col+)/*求出每一列的第一个非零元在转置后的位置*/potcol=potcol-1+potcol;for(ano=0;anoa.terms;ano+)/*转置*/col=a.dataano.j;bno=potcol;b.databno.j=a.dataano.i;b.databno.i=a.dataano.j;b.databno.v=a.dataano.v;,58,potcol=potcol+1;for(i=0;ia.terms;i+)printf(%dt%dt%dn,b.datai.i,b.datai.j,b.datai.v);/*输出转置后的三元组
29、*/void main()struct sparmatrix a;int i;scanf(%d%d%d,/*输出转置后的三元组*/,59,void main()struct sparmatrix a;int i;scanf(%d%d%d,/*调用快速转置算法*/,该算法比按列转置多用了辅助向量空间pot，但它的时间为四个单循环，故总的时间复杂度为O(a.cols+a.terms)，比按列转置算法效率要高。,60,2稀疏矩阵的相加运算当稀疏矩阵用三元组表进行相加时，有可能出现非零元素的位置变动，这时候，不宜采用三元组表作存储结构，而应该采用十字链表较方便。（1）十字链表的建立下面分两步讨论十字链
30、表的建立算法：第一步，建立表头的循环链表：依次输入矩阵的行、列数和非零元素个数：m,n和t。由于行、列链表共享一组表头结点，因此，表头结点的个数应该是矩阵中行、列数中较大的一个。假设用s 表示个数，即s=max（m，n）。依次建立总表头结点（由hm指针指向）和s个行、列表头结点，并使用next域使s+1个头结点组成一个循环链表，总表头结点的行、列域分别为稀疏矩阵的行、列数目，s个表头结点的行列域分别为0。并且开始时，每一个行、列链表均是一个空的循环链表，即s个行、列表头结点中的行、列指针域rptr和cptr均指向头结点本身。第二步，生成表中结点：依次输入t个非零元素的三元组（i,j,v），生成
31、一个结点，并将它插入到第i行链表和第j列链表中的正确位置上，使第i个行链表和第j个列链表变成一个非空的循环链表。在十字链表的建立算法中，建表头结点，时间复杂度为O(s)，插入t个非零元结点到相应的行、列链表的时间复杂度为O（t*s），故算法的总的时间复杂度为O(t*s)。,61,（2）用十字链表实现稀疏矩阵相加运算假设原来有两个稀疏矩阵A和B，如何实现运算A=A+B呢？假设原来A和B都用十字链表作存储结构，现要求将B中结点合并到A中，合并后的结果有三种可能：1）结果为aij+bij；2）aij（bij=0）；3）bij（aij=0）。由此可知当将B加到A中去时，对A矩阵的十字链表来说，或者是改
32、变结点的v域值（aij+bij0），或者不变（bij=0），或者插入一个新结点（aij=0），还可能是删除一个结点（aij+bij=0）。于是整个运算过程可以从矩阵的第一行起逐行进行。对每一行都从行表头出发分别找到A和B在该行中的第一个非零元结点后开始比较，然后按上述四种不同情况分别处理之。若pa和pb分别指向A和B的十字链表中行值相同的两个结点，则4种情况描述为：1）pa-j=pb-j 且pa-k.v+pb-k.v0，则只要将aij+bij的值送到 pa所指结点的值域中即可，其他所有域的值都不变化。2）pa-j=pb-j且pa-k.v+pb-k.v=0,则需要在A矩阵的链表中删除pa所指的结
33、点。这时，需改变同一行中前一结点的rptr域值，以及同一列中前一结点的cptr域值。3）pa-jj且pa-j0，则只要将pa指针往右推进一步，并重新加以比较即可。4）pa-jpb-j或 pa-j=0，则需在A矩阵的链表中插入pb所指结点。,62,下面将对矩阵B加到矩阵A上面的操作过程大致描述如下:设ha和hb分别为表示矩阵A和B的十字链表的总表头；ca和cb分别为指向A和B的行链表的表头结点，其初始状态为：ca=ha-k.next;cb=hb-k.next;pa和pb分别为指向A和B的链表中结点的指针。开始时，pa=ca-rptr;pb=cb-rptr;然后按下列步骤执行：当ca-i=0时，重
34、复执行、步，否则，算法结束；当pb-j0时，重复执行步，否则转第步；比较两个结点的列序号，分三种情形：a若pa-jj 且pa-j0，则令pa指向本行下一结点，即 qa=pa;pa=pa-rptr;转步;b若pa-jpb-j或pa-j=0，则需在A中插入一个结点。假设新结点的地址为P，则A的行表中指针变化为：qa-rptr=p;p-rptr=pa;同样，A的列表中指针也应作相应改变，用hlj指向本列中上一个结点，则A的列表中指针变化为：p-cptr=hlj-cptr;hlj-cptr=p;转第步；c若pa-j=pb-j，则将B的值加上去，即pa-k.v=pa-k.v+bp-k.v，此时若 pa-
35、k.v0，则指针不变，否则，删除A中该结点，于是行表中指针变为：qa-rptr=pa-rptr;同时，为了改变列表中的指针，需要先找同列中上一个结点，用hlj表示，然后令hlj-cptr=pa-cptr，转第步。一行中元素处理完毕后，按着处理下一行，指针变化为：ca=ca-k.next;cb=cb-k.next;转第1)步。,63,64,5.5.1 基本概念广义表是第2章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。,5.5 广义表,广义表的概念 n(0)个表元素组成的有限序列，记作 LS=(a0,a1,a2,an-
36、1)LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0 的广义表为空表。n 0时，表的第一个表元素称为广义表 的表头(head)，除此之外，其它表元素组 成的表(a1,a2,an-1)称为广义表的表尾(tail)。,65,求下列广义表运算的结果：(1)head(p,h,w);(2)tail(b,k,p,h);(3)head(a,b),(c,d);(4)tail(a,b),(c,d);(5)head(tail(a,b),(c,d);(6)tail(head(a,b),(c,d).,head(p,h,w)=p tail(b,k,p,h)=(k,p,h
37、)head(a,b),(c,d)=(a,b)tail(a,b),(c,d)=(c,d)head(tail(a,b),(c,d)=c tail(head(a,b),(c,d)=b,66,广义表的特性,有次序性有长度有深度,可递归可共享,A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F),67,广义表的分类,（1）线性表：元素全部是原子的广义表。（2）纯表：与树对应的广义表，（3）再入表：与图对应的广义表(允许结点共享)。（4）递归表：允许有递归关系的广义表，例如E=(a,E)。这四种表的关系满足：递归表再入表 纯表 线性表,68,各种广义表的示意图,A=
38、(),B=(6,2),C=(a,(5,3,x),D=(B,C,A),E=(B,D),F=(4,F),存储表示,69,广义表的表示方法,（1）用LS=(a1，a2，an)形式，其中每一个ai为原子或广义表例如：A=(b,c)B=(a,A)E=(a,E)都是广义表。（2）将广义表中所有子表写到原子形式，并利用圆括号嵌套例如，上面提到的广义表A、B、C可以描述为：A(b,c)B(a,A(b,c)E(a,E(a,E（）)（3）将广义表用树和图来描述,70,广义表的表示,只包括整数和字符型数据的广义表链表表示,表中套表情形下的广义表链表表示,表头指针p109层次列表长度,71,广义表结点定义,标志域 u
39、type,表明结点类型。0为表头结点，1 为整型原子结点，2为字符型原子结点，3为子表结点。值域 value。当 utype=0 时为表引用计数，=1时为整数值，=2 时为字符值，=3 时为指向子表的表头结点的指针。尾指针域 tlink。当 utype=0 时为指向该表表头元素的指针；当 utype 0 时为指向同一层下一个表结点的指针。,utype=0/1/2/3,value=ref/intgrinfo/charinfo/hlink,tlink,72,广义表的带表头结点的存储表示,标志域 utype,表明结点类型。0为表头结点，1 为整型原子结点，2为字符型原子结点，3为子表结点。,A=()
40、B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F)各种广义表的示意图,73,广义表的类定义,#define HEAD 0#define INTGR 1#define CH 2#define LST 3class GenList;class GenListNode friend class Genlist;private:int utype;GenListNode*tlink;,74,union int ref;/utype=0,表头结点 int intgrinfo;/utype=1,整型char charinfo;/utype=2,字符型 GenListNod
41、e*hlink;/utype=3,子表结点 value;public:GenListNode*Info(GenListNode*elem);int nodetype(GenListNode*elem)return elemutype;void setInfo(GenListNode*elem,GenListNode*x);,75,class GenList private:GenListNode*first;GenListNode*GenList:Copy(GenListNode*ls);int depth(GenListNode*ls);int equal(GenListNode*s,Gen
42、ListNode*t);void GenList:Remove(GenListNode*ls);public:Genlist();GenList();GenListNode*Head();GenListNode*Tail();,76,GenListNode*First();GenListNode*Next(GenListNode*elem);void Push(GenListNode*x);GenList,77,广义表的访问算法,广义表结点类的存取成员函数GenListNode*GenListNode:Info(GenListNode*elem)/提取广义表中指定表元素elem的值 GenLi
43、stNode*pitem=new GenListNode;pitemutype=elemutype;pitemvalue=elemvalue;return pitem;,78,void GenListNode:setInfo(GenListNode*elem,GenListNode*x)/将表元素elem中的值修改为x elemutype=xutype;elemvalue=xvalue;广义表类的构造和访问成员函数Genlist:GenList()GenListNode*first=new GenListNode;firstutype=0;firstref=0;firsttlink=NULL;
44、/仅建立表头结点,79,GenListNode*GenList:Head()/若广义表非空，返回表的表头元素的值 if(firsttlink=NULL)/空表 cout“无效的head操作.endl;exit(1);else GenListNode*temp=new GenListNode;temputype=fristtlinkutype;tempvalue=fristtlinkvalue;return temp;,80,void GenList:Push(GenListNode*x)/将表结点 x 加到表的最前端 if(firsttlink=NULL)firsttlink=x;else x
45、tlink=firsttlink;firsttlink=x;,81,GenList,82,广义表的递归算法p114,广义表的复制算法void GenList:Copy(const GenList/复制 utype,83,switch(lsutype)case HEAD:qref=lsref;break;case INTGR:qintgrinfo=lsintgrinfo;break;case CH:qcharinfo=lscharinfo;break;case LST:qhlink=Copy(lshlink);break;qtlink=Copy(lstlink);return q;,84,广义表
46、的深度,深度为广义表中括号的重数或（）的层数，是广义表的一种量度。,LS=(a0,a1,a2,an-1),85,求广义表的深度,例如，对于广义表 E(B(a,b),D(B(a,b),C(u,(x,y,z),A()按递归算法分析：,Depth(E)=1+Max Depth(B),Depth(D)Depth(B)=1+Max Depth(a),Depth(b)=1 Depth(D)=1+Max Depth(B),Depth(C),Depth(A),86,E(B(a,b),D(B(a,b),C(u,(x,y,z),A(),Depth(C)=1+Max Depth(u),Depth(x,y,z)Dep
47、th(A)=1 Depth(u)=0 Depth(x,y,z)=1+Max Depth(x),Depth(y),Depth(z)=1 Depth(C)=1+Max Depth(u),Depth(x,y,z)=1+Max 0,1=2 Depth(D)=1+Max Depth(B),Depth(C),Depth(A)=1+Max 1,2,1=3 Depth(E)=1+Max Depth(B),Depth(D)=1+Max 1,3=4,87,int GenList:depth(GenListNode*ls)if(lstlink=NULL)return 1;/空表 GenListNode*temp=l
48、stlink;int m=-1;while(temp!=NULL)/横扫广义表 if(temputype=LST)/子表深度 int n=depth(temphlink);if(m n)m=n;/m:max(depth(ai)/不是子表不加深度 temp=temptlink;return m+1;,88,广 义 表例 1 写出下表的图形表示、存储表示、深度及长度 D(A(c),B(e),C(a,L(b,c,d),例,89,0,D,3,3,3,0,B,2,c,2,e,2,b,3,2,c,0,C,深度为3 长度为3,深度为括号的重数或 的层数长度为最高一层表结点的个数,90,广义表的删除算法,删除
49、x前的广义表链表结构,扫描子链表 若结点数据为x,删除。可能做循环连续删。若结点数据不为x，不执行删除。若结点为子表，递归在子表执行删除。,91,void delvalue(GenListNode*ls,const value x)/在广义表中删除所有含x的结点 if(lstlink!=NULL)GenListNode*p=lstlink;/横扫链表 while(p!=NULL/p指向同层下一结点/链表检测完或遇到子表或走到子表表/头结点或不是含x结点,转出循环,if(p!=NULL)if(putype=LST)/到子表中删除 delvalue(phlink,x);delvalue(p,x);
50、/向后递归删除,92,GenList:GenList()/析构函数 Remove(first);,93,void GenList:Remove(GenListNode*ls)lsref-;/引用计数减一 if(!lsref)/引用计数减至0才能删除 GenListNode*y=ls;while(ytlink!=NULL)/横扫链表 y=ytlink;if(yutype=LST)/遇到子表 Remove(yhlink);/递归删除 ytlink=av;av=ls;/扫描完后,回收到可利用空间表,94,从字符串s建立广义表的链表表示ls,把广义表的书写形式看成是一个字符串S广义表字符串SS=()带
