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

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

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

  )每個棧僅用一個順序存儲空間時操作簡便但分配存儲空間小了容易產生溢出分配空間大了容易造成浪費各棧不能共享空間

  ()多個棧共享一個順序存儲空間充分利用了存儲空間只有在整個存儲空間都用完時才能產生溢出其缺點是當一個棧滿時要向左右棧查詢有無空閒單元如果有則要移動元素和修改相關的棧底和棧頂指針當接近棧滿時查詢空閒單元移動元素和修改棧底棧頂指針的操作頻繁計算復雜並且耗費時間

  ()多個鏈棧一般不考慮棧的溢出(僅受用戶內存空間限制)缺點是棧中元素要以指針相鏈接比順序存儲多占用了存儲空間

  設top和top分別為棧的棧頂指針

  ()入棧主要語句

  if(toptop==) {printf(棧滿\n); exit();}
  case:top++SPACE[top]=x;    //設x為入棧元素
  case:topSPACE[top]=x;

  出棧主要語句

  caseif(top==) {printf(棧空\nexit(}
  topreturn(SPACE[top+])    //返回出棧元素
  caseif(top==N){printf(棧空\nexit(}
  top++return(SPACE[top])    //返回出棧元素

  ()棧滿條件toptop=

  棧空條件top=並且top=N   //top=為左棧空top=N為右棧空

  設順序存儲隊列用一維數組q[m]表示其中m為隊列中元素個數隊列中元素在向量中的下標從到m設隊頭指針為front隊尾指針是rear約定front指向隊頭元素的前一位置rear指向隊尾元素當front等於時隊空rear等於m時為隊滿由於隊列的性質(刪除在隊頭而插入在隊尾)所以當隊尾指針rear等於m若front不等於則隊列中仍有空閒單元所以隊列並不是真滿這時若再有入隊操作會造成假溢出其解決辦法有二一是將隊列元素向前平移(占用至rearfront二是將隊列看成首尾相連即循環隊列(m在循環隊列下仍定義front=rear時為隊空而判斷隊滿則用兩種辦法一是用犧牲一個單元即rear+=front(准確記是(rear+)%m=frontm是隊列容量)時為隊滿另一種解法是設標記方法如設標記tagtag等於情況下若刪除時導致front=rear為隊空tag=情況下若因插入導致front=rear則為隊滿

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


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