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

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

2022-06-13   來源: 數據結構 

  [題目分析] 本題與上面題基本相同現用類C語言給出該雙端隊列的定義

  #define maxsize 
  typedef struct
  {datatype elem[maxsize];
  int endend; //end和end取值范圍是maxsize
  } deque;

  [題目分析] 根據隊列先進先出和棧後進先出的性質先將非空隊列中的元素出隊並壓入初始為空的棧中這時棧頂元素是隊列中最後出隊的元素然後將棧中元素出棧依次插入到初始為空的隊列中棧中第一個退棧的元素成為隊列中第一個元素最後退棧的元素(出隊時第一個元素)成了最後入隊的元素從而實現了原隊列的逆置

  void Invert(queue Q)
  //Q是一個非空隊列本算法利用空棧S和已給的幾個棧和隊列的ADT函數將隊列Q中的元素逆置
  {makempty(S); //置空棧
  while (!isEmpty(Q))  // 隊列Q中元素出隊
  {value=deQueue(Q);  push(Svalue);  }// 將出隊元素壓入棧中
  while(!isEmpty(S)) //棧中元素退棧
  {value=pop(S);   enQueue(Qvalue); }//將出棧元素入隊列 Q
  }//算法invert 結束


  為運算方便設數組下標從開始即數組v[m]設每個循環隊列長度(容量)為L則循環隊列的個數為n=ém/Lù為了指示每個循環隊列的隊頭和隊尾設如下結構類型
  typedef struct
  {int fr;
  }scq;
  scq q[n];

  ()初始化的核心語句
  for(i=;i<=n;i++) q[i]f=q[i]r=(i)*L;   //q[i]是全局變量

  ()入隊 int addq(int i;elemtp x)
  //n個循環隊列共享數組v[m]和保存各循環隊列首尾指針的q[n]已經定義為全局變量數組元素為elemtp類型本過程將元素插入到第i個循環隊列中若入隊成功返回否則返回隊滿標記(入隊失敗)
  { if (i<||i>n) {printf(隊列號錯誤);exit();}
  if (q[i]r+)%L+(i)*L==q[i]f) {printf(隊滿\n);exit();}
  q[i]r=(q[i]r+)%L+(i)*L; // 計算入隊位置
  v[q[i]r]=x; return();//元素x入隊
  }

  ()出隊 int deleteq (int i)// n個循環隊列共享數組v[m]和保存各循環隊列首尾指針的q[n]已經定義為全局變量數組元素為elemtp類型本過程將第i個循環隊列出隊若出隊成功打印出隊列元素並返回表示成功若該循環隊列為空返回表示出隊失敗
  {if (<||>n) {printf(隊列號錯誤\n);exit();}
  if (q[i]r==q[i]f) {printf(隊空\n); return();}
  q[i]f=(q[i]f+)%L+(i)*L;
  printf(出隊元素q[i]f); return();
  }

  ()討論上述算法假定最後一個循環隊列的長度也是L否則要對最後一個循環隊列作特殊處理另外未討論一個循環隊列滿而相鄰循環隊列不滿時需修改個循環隊列首尾指針的情況(即各循環隊列長度不等)

  n個循環隊列共享數組v[m]的示意圖如下

  第i個循環隊列從下標 (i)L 開始到iL為止設每個循環隊列均用犧牲一個單元的辦法來判斷隊滿即為(q[i]r+)%L+(i)*L=q[i]f時判定為隊滿

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


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