熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第三章 答案[13]

2013-11-15 15:00:43  來源: 數據結構 

  typedef struct
  {elemtp q[m];
  int frontcount;  //front是隊首指針count是隊列中元素個數
  }cqnode;           //定義類型標識符
  ()判空int Empty(cqnode  cq)                        //cq是cqnode類型的變量
  {if(cqcount==) return()else return();  //空隊列}
  入隊: int EnQueue(cqnode cqelemtp x)
  {if(count==m){printf(隊滿\n)exit(); }
  cqq[(cqfront+count)%m]=x;    //x入隊
  count++; return();            //隊列中元素個數增加入隊成功
  }
  出隊: int DelQueue(cqnode cq)
  {if (count==){printf(隊空\n)return();}
  printf(出隊元素cqq[cqfront]);
  x=cqq[cqfront];
  cqfront=(cqfront+)%m;  //計算新的隊頭指針
  return(x)
  }

  () 隊列中能容納的元素的個數為m隊頭指針front指向隊頭元素

  循環隊列中元素個數為(REARFRONT+N)%N其中FRONT是隊首指針指向隊首元素的前一位置REAR是隊尾指針指向隊尾元素N是隊列最大長度

  循環隊列解決了用向量表示隊列所出現的假溢出問題但同時又出現了如何判斷隊列的滿與空問題例如在隊列長的循環隊列中若假定隊頭指針front指向隊頭元素的前一位置而隊尾指針指向隊尾元素則front=rear=的情況下連續出隊個元素則front==rear為隊空如果連續入隊個元素則front==rear為隊滿如何判斷這種情況下的隊滿與隊空一般采取犧牲一個單元的做法或設標記法即假設front==rear為隊空而(rear+)%表長==front為隊滿或通過設標記tag若tag=front==rear則為隊空若tag=因入隊而使得front==rear則為隊滿

  本題中隊列尾指針rear指向隊尾元素的下一位置listarray[rear]表示下一個入隊的元素在這種情況下我們可規定隊頭指針front指向隊首元素當front==rear時為隊空當(rear+)%n=front時為隊滿出隊操作(在隊列不空情況下)隊頭指針是front=(front+)%n

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22709.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.