广义表删除原子和逆置，在sharp develop2.0下调试通过
详见习题集p320 11.1,p309 11.4
都是基于可重复访问的框架写的,看来正确的算法框架很重要啊。
public void deleteRE(GenListNode p ,GenListNode pre,char x,int visitTime)
{
if(p.type==HEAD) //HEAD
{ p.mark=VISITED;
if(p.visitTime>visitTime) //already visited
{
}
else
{
p.visitTime++;
//head node's next is just the real elements
if(p.next!=null)
deleteRE(p.next,p,x,visitTime);
else //empty head ,clear the mark
p.mark=UNVISITED;
;
}
}
else //ATOM or LIST
{
if(p.type==ATOM)
{
if(p.element==x)
{pre.next=p.next;
p=pre;
}
p.mark=VISITED;
}
else
if(p.type==LIST)
deleteRE(p.child,p,x,visitTime);
//deal with the rest of the list
if((p.next!=null)&&(p.next.mark!=VISITED))
{
p.mark=VISITED; //recurse one by one
deleteRE(p.next,p,x,visitTime);
}
}
//clear the mark in the list
GenListNode tmp=p;
while(tmp!=null)
{
tmp.mark=UNVISITED;
tmp=tmp.next;
}
}
/// <summary>
/// reverse the elements in a genlist
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public GenListNode reverseRE(GenListNode p,GenListNode pre,int visitTime) //return the new first
{ GenListNode tmp,first,tail;
if(p==null) return null;
p.mark=VISITED;
if(p.type==HEAD)
{ if(p.visitTime<=visitTime)
{ p.visitTime++;
p.next=reverseRE(p.next,p,visitTime);
}
}
else
{ //LIST
if(p.type==LIST&&p.child.mark==UNVISITED)
reverseRE(p.child,null,visitTime);
///about next of LIST or ATOM
if(p.next==null) return p;
else //got next's new first
first=reverseRE(p.next,p,visitTime);
p.next=null;
pre.next=first;
//got tail
tail=first;
while(tail.next!=null) tail=tail.next;
tail.next=p;
p=first;
}
tmp=p;
while(tmp!=null)
{
tmp.mark=UNVISITED;
tmp=tmp.next;
}
//ultimate return value
return p;
}
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 计算机考研交流 』 → 今天写的两个算法
(订阅本版)
2006/4/23 16:00:00
新浪微博
今天写的两个算法
