§6广义表§6.1广义表的定义广义表（Lists）又称列表，是线性表的推广，广义表是n(n≥0)个元素（子表）a1,a2,…,an组成的有限序列，一般记作：LS＝（a1,a2,…,an）LS是广义表的名字，n为其表的长度其中ai或者是原子(单个元素)或者是一个广义表，分别称为广义表LS的单元素和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示单元素。广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表的概念。例如：E=()E是一个空表，其长度为0。L=(a,b)L是长度为2的列表，它的两个元素都是原子，因此它是一个线性表。A=(x,L)=(x,(a,b))A是长度为2的列表，第一个元素是原子x，第二个元素是子表LB=(A,y)=((x,(a,b)),y)B是长度为2的列表，第一个元素是子表A，第二个元素是原子yC=(A,B)=((x,(a,b)),((x,(a,b)),y))C的长度为2，两个元素都是子表。D=(a,D)=(a,(a,(a,(...))))D的长度为2，第一个元素是原子，第二元素是D自身。展开后，它是一个无限列表。一个表的深度是指表展开所含括号的层数，例如，表A的深度为2，表D的深度为∞。值得注意的是广义表()和(())不同，前者是空表，长度n=0；后者长度n=1，它有一个元素是空表，可分解得到表头和表尾均是空表()。广义表的特点：（1）列表可以是递归的，如表D是它本身元素的子表。（2）列表是多层次的结构，表中的元素可以是子表，子表的元素还可以是子表，……（3）列表可以为其它列表所共享，如上例中，表A和表B是表C的子表。§6.2广义表的存储结构由于广义表中的元素可以有不同的结构，单元素或子表，因此难以用顺序存储结构表示，通常采用链式存储结构。结点的结构可以这样设计：其中，tag是标志域，若tag＝0，则第二个域中为data，存储单元素；若tag＝1，则第二个域中为hp，存储指向子表的指针。link为指向同一层下一个结点的指针。【例6.2.1】L＝((a,(b)),a,((a,(c)),c),d)【例6.2.2】在一个广义表（不共享）中查找某元素。输入：第一行：广义表，如：((a,(b)),a,((a,(c)),c),d)第二行：要查找的元素，如：d输出：广义表中有该元素，则输出：Yes否则输出:No[参考程序]programgyb;typepointer=^node;node=recordlink:pointer;casetag:0..1of0:(data:char);1:(hp:pointer);end;vari:integer;Q:string;tagdata/hplink^10a10a10b11000d0cac^^^^^procedurefind(p:pointer);beginifp<>nilthenifp^.tag=0thenbeginifp^.data=cthenbegint:=true;exit;endelsefind(p^.link);endelsebeginfind(p^.hp);find(p^.link);end;end;Beginreadln(Q);readln(c);i:=1;t:=false;creat(head);find(head);iftthenwrite('Yes')elsewrite('No');End.c:char;t:boolean;head:pointer;procedurecreat(varp:pointer);varx:char;beginx:=Q[i];i:=i+1;casexof'(':beginnew(p);p^.tag:=1;creat(p^.hp);creat(p^.link);end;'a'..'z':beginnew(p);p^.tag:=0;p^.data:=x;creat(p^.link);end;',':creat(p);')':p:=nil;end;end;
