以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  今天写的两个算法  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=31102)

--  作者：yapi
--  发布时间：4/23/2006 4:00:00 PM

--  今天写的两个算法
广义表删除原子和逆置，在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;
   }

--  作者：Logician
--  发布时间：4/23/2006 9:32:00 PM

--  
用sharp develop。听上去不错啊！呵呵。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 7,148.438ms