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

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

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

  [題目分析]本題要求用鏈接結構實現一個隊列我們可用鏈表結構來實現一般說由於隊列的先進先出性質所以隊列常設隊頭指針和隊尾指針但題目中僅給出一個全局指針p且要求入隊和出隊操作的時間復雜性是O(因此我們用只設尾指針的循環鏈表來實現隊列

  PROC addq(VAR p:linkedlistx:elemtp);
  //p是數據域為data鏈域為link的用循環鏈表表示的隊列的尾指針本算法是入隊操作
  new(s);      //申請新結點假設有內存空間否則系統給出出錯信息
  s↑data:=x; s↑link:=p↑link;//將s結點入隊
  p↑link:=s; p:=s;              //尾指針p移至新的隊尾
  ENDP;
  PROC deleq(VAR p:linkedlistVAR x:elemtp);
  // p是數據域為data鏈域為link的用循環鏈表表示的隊列的尾指針本算法實現隊列元素的出隊若出隊成功返回出隊元素否則給出失敗信息
  IF (p↑link=p)THEN[writeln(空隊列);return();]//帶頭結點的循環隊列
  ELSE[s:=p↑link↑link;           //找到隊頭元素
  p↑link↑link:=s↑link;    //刪隊頭元素
  x:=s↑data;                  //返回出隊元素
  IF (p=s) THEN p:=p↑link;    //隊列中只有一個結點出隊後成為空隊列
  dispose(s);                   //回收出隊元素所占存儲空間
  ]
  ENDP;

  [算法討論]上述入隊算法中因鏈表結構一般不必考慮空間溢出問題算法簡單在出隊算法中首先要判斷隊列是否為空另外對出隊元素要判斷是否因出隊而成為空隊列否則可能導致因刪除出隊結點而將尾指針刪掉成為懸掛變量

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


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