第三章 3-4~3-8
3-4 设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

声明：在单链表类的基础上加入一个操作（公共函数）
思路：设置一个变量max暂存当前找到的最大值的结点，然后从单链表的第一个结点开始比较，如果找到比max值大的点则，替换max值。

template< class Type > ListNode< Type > *List< Type >::Max(){
//在当前的单链表中找出值最大的结点，并返回该结点的地址.
  ListNode *p=first->link;
  ListNOde *max=p;
  while(p != NULL){
    if(p->data > max->data)
      max=p;
    p=p->link;           //遍历
  }
  return max;
}


3-5 设计一个算法，在非递减有序的单链表中删除值相同的多余结点。

声明：在单链表类的基础上加入一个操作（公共函数）。
思路：同上题，依然是一次遍历，因为单链表本身已经按照非递减顺序排好，只需要检查p->link是否和p的值一样，如果一样的话，就删除。

template< class Type > void List< Type >::Zip(){
//将非递减有序链表压缩，删去拥有相同值的多余结点。
  ListNode *p=first->link,*q=NULL;
  while(p != NuLL&&p->link != NULL){
    if(p->data==p->link->data){   //相邻两点是否相等
      q=p->link;p->link=q->link;  //重新拉链
      delete q;                     
    }
    eles p=p->link;               //指针p进到下一位
  }
}


3-6 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

声明：和参考答案的思路有区别。
思路：与3-3类似，p循链检测链表，并将当前指针p所指向的结点插到第一个结点位置，再重置p=pnext。pnext为预先保留的指针，指向原链中p的下一个结点。

void Inverse(ListNode *h){
  ListNode *p=h->link,*pnext;
  while(p!=NULL){
    pnext=p->link;             //保留p的下一个指针
    p->link=h->link;h->link=p;    //插到第一个节点位置
    p=pnext;                   //p再往前走一位
  }
}


3-7 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如p102页图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。
(1)编写一个算法，从任一给定的位置(pr，p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。
(2)编写一个算法，从任一给定的位置(pr，p)开始，将指针p左移k个结点。如果pr移出链表，则将pr置为0，并让p停留在链表最左边的结点上。(ps:题目应该把p和pr弄反了)

(1)思路：用tmp暂存p，然后p右移一位，tmp->link指向pr，逆转连，然后pr=tmp。检查p有没有溢出。
void moveright(ListNode *pr,ListNode *p,int k){
  ListNode *tmp;
  for(int i=1;i <= k;i++){
    if(p==NULL||p==0){
      p=0;
      return;
    }
    tmp=p;p=p->link;       //向右逆转
    tmp->link=pr;pr=tmp;
  }
}


(2)和上一样 p和pr对换
void moveleft(ListNode *pr,ListNode *p,int k){
  ListNode *tmp;
  for(int i=1;i <= k;i++){
    if(pr==NULL||pr==0){
      pr=0;
      return;
    }
    tmp=pr;pr=pr->link;   //向左逆转     
    tmp->link=p;p=tmp;
  }
}


3-8 试写出适合循环链表的游标类定义，并编写它的3个成员函数First()、Next()和NextNotNull()的实现程序。这些函数的功能应该和单链表的相应操作相同。

思路：模仿单链表的Iterator类

ListNode前视定义 CLIterator类为友元
CircList前视定义 CLIterator类为友元
……
enum Boolean{False,True};
temple< class Type > class CLIterator{
public:
   CLIterator(const CircList< Type > &l):list(l),current(l.first){}
   Boolean NextNotNull();
   Type *First();
   Type *Next();
private:
   const CircList< Type > &list;
   ListNode< Type > *current;
}

template< class Type > Boolean CLIterator< Type >::NextNotNull(){
//检查链表中下一个元素是否非空.
   if(current!=NULL&¤t->link!=NULL)
      return Ture;
   else return False;
}

template< class Type > Type * CLIerator< Type >::First(){
//返回指向链表中第一个结点的指针.
   if(list.first->link!=NULL){
      current=list.first;
      return & current->data;
   }
   else{current=NULL;return NULL;}
}

template< class Type > Type * CLIerator< Type >::Next(){
//返回当前指针的下一个结点的指针.
  if(current!=NULL){
     current=current->link;
     return & current->data;
  }
  else{ current=NULL;return NULL;}
}
09:41 | Category: | 0 评论

Comments (0)

发表评论