下面分别是用类程序设计语言和c++语言描述的算法preorder1(由算法revisel调用)和preorder2(由算法revise2调用),其功能是通过二叉树的先序遍历,将二叉树中数据域值等于c的结点修改为数据域值d,并累加修改的结点个数s。
二叉树结点如图2所示,其中,数据域data为字符型,llink、rlink分别为指向左、右孩子的指针域。
请选择一种算法描述形式,在算法中的空格处填入正确内容并回答问题(①、②任选一题,只能选做一题)。
①类程序设计语言描述形式符号&开头的参数为引用参数(即输入输出参数)。bt指向二叉树结点的数据域用bt^.data表示,指向左、右孩子的指针域分别用bt^.llink、bt^.rlink表示。算法中,"<-"为赋值号,nil为空指针。
algorithm preorder1(bt,c,d,&s)
//bt为指向二叉树根结点的指针//
//c,d为字符型//
//s为整型//
{
if bt<>nil
then{if bt^.data=c
then { ();
s<-s+1;
&nb
函数insertdl1和insertdl2分别是用类程序设计语言和C++语言描述的算法。其功能是在d1指向的带表头结点双向循环链表中,将数据域值为x的新结点插在数据域值为ai的结点之前,并返回插入位置i值,如果表中数据域值为ai的结点不存在,则返回值i为0。链表结占加图2所示,结点类型为dnode,数据域data为整型,前、后链域分别为prior和next。
请选择一种算法描述形式,在算法中的空格处填入正确内容并回答问题(1、2任选一题,只能选做一题),
1.类程序设计语言描述形式符号&开头的参数为输入输出参数。d1指向链表结点的数据域用d1^.data表示,前、后链域分别用d1^.prior、d1^.next表示。算法中,nil为空指针。
Algorithm insertd11(&d1,ai,x)
//insertd11函数的类型为整型//
//d1为指向双向循环链表的头指针//
//ai,x为双向循环链表结点数据域类型//
//i为整型//
//p,s为辅助指针//
{
pd1;
i0;
while(())and(p^.next.data<>ai)
{ pp^.next;
()
}
if p^.next^.data=ai then
{new(s);
();
s^.nextp^.next;
();
s^.priorp;
p^.nexts;
ii+1
}
else i0;
return (i)
}
回答以下问题:
设dl指向的双向循环链表为非空表,链表第一个结点数据域在算法描述时应表示为()
设d1=(18,45,36,27),ai=36,x=90,上述算法执行后,d1=( () )。
上述算法中若数据域值为ai的结点存在,则指针s指向的结点位于指针P指向的结点
()(之前/之后)。
②C++语言描述形式
符号&开头的参数
我来回答: