第五章 5-5～5-8
5-5 已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法:
(1)求链表中的最大整数；
(2)求链表的结点个数;
(3)求所有整数的平均值；

和整型数组A[]的算法一样；另外与参考答案同步，假设是不带表头结点的单链表。
(1)思路:把f->data的值和Max(f->link)比较；套用广义表的说法，就是比较表头和表尾即可，顺便递归定义表尾。
int Max(ListNode *f){
  if(f->link == NULL) return f->data;
  int tmp=Max(f->link);
  if(f->data >= tmp)
     return f->data;
  else return tmp;
}

(2)求链表长度

int Length(ListNode *f){
  if(f == NULL) return 0;
  else return 1+Length(f->link);
}

(3)求所有整数的平均值

float Avg(ListNode *f){
  if(f->link == NULL) return f->data;
  else{int n=length(f->link);    //时间代价够高的  呵呵
   return  (f->data+Avg(f->link)*n)/n;
}


5-7 利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来:
(1)L1(apple,pear,banana,orange)
(2)L2((apple,pear),(banana,orange))
(3)L3(((apple),(pear),(banana),(orange)))
(4)L4((((apple))),((pear)),(banana),orange)
(5)L5((((apple),pear),banana),orange)
(6)L6(apple,(pear,(banana),orange))

(1)   head(tail(tail(L1)))
(2)   head(head(tail(L2)))
(3)   head(head(tail(tail(head(L3)))))
(4)   head(head(tail(tail(L4))))
(5)   head(tail(head(L5)))
(6)   head(head(tail(head(tail(L6)))))


5-8 广义表具有可共享性，因此在遍历一个广义表时必须为每一个结点增加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。
(1)试定义该广义表的类结构；
(2)采用递归的算法对一个非递归的广义表进行遍历。
(3)试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。

(1)声明：按照参考答案的思路；广义表中假定只存放了一种元素类型char，统称为原子结点 atom。 这样，广义表中结点类型只有3种:表头结点、char原子结点和子表结点.大写的字母表示表，小写表示原子结点 等同于教材。
class GenList;
class GenListNode{
friend class GneList;
private:
  int mark,utype;
  GenListNode* link;
  union{
    char listname;            //utype=0,表头结点，存放表名.
    char atom;                //utype=1,存放原子结点的数据.
    GenLisNode* hlink;        //utype=2,存放指向子表的指针.
  }value;
public:
  GenListNode(int tp,char info):mark(0),utype(tp),tlink(NULL)
//表头或者原子结点的构造函数.
    {if(utype==0)value.listname=info;
     else value.atom=info;
    }
  GenListNode(GenListNode* hp)  //子表构造函数.
    :mark(0),utype(2),value.hlink(hp){}
  char Info(GenListNode* elem)  //返回元素elem的值.
    {return(utype==0)?elem->value.listname:elem->value.atom;}
};

class GenList{
private:
   GenListNode* first;             //表头.
   void traverse(GenListNode* ls); //广义表遍历.
   void remove(GenListNode* ls);   //删除.
public:
   GenList(char& value);     //构造函数,value停止标记
   ~GenList(); 
   void traverse();
}

(2)广义表遍历的递归算法

void GenList::traverse(){
  if(first==NULL){
    cout<< "error"<    return;
  }
  traverse(first);
}

void GenList::traverse(GenListNode* ls){
  if(ls!=NULL){
    ls->mark=1;
    if(ls->utype==0)                  //表头结点;
      cout<< ls->value.listname<< '('; 
    else if(ls->utype==1){             //原子结点;
      cout<< ls->value.atom;
      if(ls->linke!=NULL)cout<< ',';
    }
      else if(ls->utype==2){           //子表结点;
        if(ls->value.hlink->mark==0)
           traverse(ls->value.hlink);
        else cout<< ls->value.hlink->value.listname;
        if(ls->tlink!=NULL)cout<< ',';
      }
    traverse(ls->link);
  }
  else cout<< ')';
}

(3)按照上题的遍历顺序，改写成利用栈的非递归方式。依然方便处理，pop()直接弹出并返回元素结点.
下面这段程序不同于参考答案，感觉参考答案写的有点乱，修改了。
void GenList::traverse(GenListNode *ls){
  Stack< GenListNode* >st;
  st.Push(ls);
  while(!st.IsEmpty()){
    ls=st.Pop();            //取出结点
    if(ls==NULL){           //空结点，当前层结束
       cout<< ')';
       return;
    }
    else st.Push(ls->link); //压入当前层下一个结点
    ls->mark=1;
    switch(ls->utype){
      case 0:cout<< ls->value.listname<< '(';
      //表头结点
      case 1:cout<< ls->value.atom;
             if(ls->link!=NULL)cout<< ',';
      //原子结点
      case 2:if(ls->value.hlink->mark==0)
               st.Push(ls->value.hlink);
             else{
               cout<< ls->value.hlink->value.listname;
               if(ls->link!=NULL)cout<< ',';
             }
      //子表结点
    }
}

多简洁啊，参考答案的栈用的让人觉着不和谐。
15:32 | Category: | 0 评论

Comments (0)

发表评论