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

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

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

  [題目分析] 雙端隊列示意圖如下(設maxsize =

  用上述一維數組作存儲結構把它看作首尾相接的循環隊列可以在任一端(end或end)進行插入或刪除初始狀態end+=end被認為是隊空狀態end=end被認為是隊滿狀態(左端隊列)end指向隊尾元素的前一位置end指向(右端隊列)隊尾元素的後一位置入隊時判隊滿出隊(刪除)時判隊空刪除一個元素時首先查找該元素然後從隊尾將該元素前的元素依次向後或向前(視end端或end端而異)移動

  FUNC add (Qu:deque; var x:datatype;tag ):integer;
  //在雙端隊列Qu中插入元素x若插入成功返回插入元素在Qu中的下標插入失敗返回tag=表示在end端插入tag=表示在end端插入
  IF Quend=Quend THEN [writeln(隊滿);return();]
  CASE tag OF
  : //在end端插入
  [Quend:=x;                       //插入x
  Quend:=(Quend) MOD maxsize; //修改end
  RETURN(Quend+) MOD maxsize);   //返回插入元素的下標
  : //在end端插入
  [Quend:=x;
  Quend:=(Quend+) MOD maxsize;
  RETURN(Quend) MOD maxsize);
  ]
  ENDC; //結束CASE語句
  ENDF; //結束算法add
  FUNC delete (Qu: deque; VAR x:datatype; tag:):integer;
  //本算法在雙端隊列Qu中刪除元素xtag=時從end端刪除tag=時從end端刪除刪除成功返回否則返回
  IF (Quend+) MOD maxsize=Quend THEN [writeln(隊空);return();]
  CASE tag OF
  : //從end端刪除
  [i:=(Quend+) MOD maxsize; //i是end端最後插入的元素下標
  WHILE(i<>Quend) AND (Quelem[i]<>x) DO
  i=(i+) MOD maxsize;//查找被刪除元素x的位置
  IF (Quelem[i]=x) AND (i<>Quend) THEN
  [ j:=i;
  WHILE((j+maxsize) MOD maxsize <>Quend) DO
  [Quelem[j]:=Quelem[(j+maxsize) MOD maxsize];
  j:=(j+maxsize) MOD maxsize;
  ]//移動元素覆蓋達到刪除
  Quend:=(Quend+) MOD maxsize; //修改end指針
  RETURN();
  ]
  ELSE RETURN();
  ]//結束從end端刪除
  : //從end端刪除
  [i:=(Quend+maxsize) MOD maxsize; //i是end端最後插入的元素下標
  WHILE(i<>Quend) AND (Quelem[i]<>x) DO
  i=(i+maxsize) MOD maxsize;//查找被刪除元素x的下標
  IF (Quelem[i]=x) AND (i<>Quend) THEN //被刪除元素找到
  [ j:=i;
  WHILE((j+) MOD maxsize <>Quend) DO
  [Quelem[j]:=Quelem[(j+) MOD maxsize];
  j:=(j+) MOD maxsize;
  ]//移動元素覆蓋達到刪除
  Quend:=(Quend+maxsize) MOD maxsize; //修改end指針
  RETURN();//返回刪除成功的信息
  ]
  ELSE RETURN();//刪除失敗
  ]//結束在end端刪除
  ENDC;//結束CASE語句
  ENDF;//結束delete

  [算法討論]請注意下標運算(i+) MOD maxsize容易理解考慮到i可能為負的情況所以求下個i時用了(i+maxsize) MOD maxsize

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


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