Program list(input,output);
Type ref=^word;
Word=record
Key: char;
Cont: integer;
Next: ref;
end;
var k:char;
Sentinel, root: ref;
Procedure search ([1])
var w:ref;
Begin
w:=root;
sentinel^key:=x;
while w^.key<>x do
[2];
if [3]
then w^count:=w^.count+1
else
begin
w:=root;
[4];
with root^ do
begin
key:=x;count:=1;next:=w
end
end
End;
Procedure display(w:ref);
begin
while w<>sentinel do
begin
writeln(w^.key,w^.count);
w:=w^.next;
end
End;
Begin
new(sentinel);
with sentinel^ do
begin
key:='#';
count:=0;
next:=nil
end;
root:=sentinel;
while k<>'#' do
begin
search(k,root);
read(k);
end;
display [5];
End.
二、算法题（本题9分）
广义表GL=（a1,a2,……an）,其中ak(k=1,2,3…..n)或是单个数据元素（原子），或仍然是一个广义表。给定如下有关广义表的类型定义：
type
tagtype=0..1;
glist=^gnode;
link:glist;case tag:tagtyoe of
0(data:integer);
1(sublist:glist);
end;
编写一个过程或函数计算一个广义表的所有元素节点数据之和，例如对广义表（3（2，4），（6，3））数据与之和为23。
答案：可以看出，该存储结构为首尾存储结构，求广义表GL=（a1,a2,….an）的各数据域值之和本质上就是遍历广义表并对遍历的数据域求和。这里可采用递归程序来实现。对给定指向的广义表GL＝（a1,a2,……an）的指针L，广义表GL的各数据域值之和f(L)为
f(L)=0 (当L为空时)
f(L)=1+ f(L^Link) (当L^.tag=0时)
f(L)= f(L^Link)+ f(L^sublist) （当L^.tag=1时）
故求广义表GL的各数据域值之和的递归函数如下：
Function f(L:glist):integer;
begin
if L=Nil
then f:=0
else
if L^.tag=0
then f:=1+f(L^.link)
else f:=f(L^.link)+f(L^.sublist)
end;