1.假定有四個元素A、B、C、D，按所列次序進棧，試寫出所有可能的出棧列，注意，每一
個元素進棧后都允許出棧，如ACDB就是一種出棧序列。
解：
ABCD ABDC ACBD ADCB BACD BADC BCAD
BCDA BDCA CBAD CDBA DCBA
2.在一個數(shù)組空間stack[StackMaxSize]中可以同時存放兩個順序棧，棧底分別在數(shù)組的兩端
，當(dāng)?shù)谝粋€棧的棧頂指針top1等于-1時則棧1為空，當(dāng)?shù)诙€棧的棧頂指針top2等于StackMax
Size時棧2為空。兩個棧均向中間增長，當(dāng)向棧1插入元素時，使top1增1得到新的棧頂位置，
當(dāng)向棧2插入元素時，則使top2減1才能夠得到新的棧頂位置。當(dāng)top1等于top2-1或者top2等
于top1+1時，存儲空間用完，無法再向任一棧插入元素。用于雙棧操作的順序存儲類型可定
義為：
struct Bothstack{
ElemType stack[stackMaxSize];
int top1,top2;
};
雙棧操作的抽象數(shù)據(jù)類型可定義為：
DAT BSTACK is
Data:采用順序結(jié)構(gòu)存儲的雙棧，其存儲類型為Bothstack
operations:
void InitStack(Bothstack& BS,int k);
//初始化棧。當(dāng)k=1或2時對應(yīng)置棧1或棧2為空，k=3時置兩個格均為空
void Clearstack(BothStack& BS,int k)
//清除棧。當(dāng)k=1或2時對應(yīng)棧1或棧2被清除，k=3時兩個棧均被清除
int StackEmpty(BothStack& BS,int k)
//判斷棧是否為空。當(dāng)k=1或2時判斷對應(yīng)的棧1或棧是否為空，k=3時
//判斷兩個棧是否同時為空。若判斷結(jié)果為空則返回1，否則返回0
ElemType Peek(BothStack& BS,int k)
//取棧頂元素。當(dāng)k=1或2時對應(yīng)返回棧1或棧2的棧頂元素
void Push(BothStack& Bs,int k,const ElemType& item)
//進棧。當(dāng)k=1或2時對應(yīng)向棧1或棧2的頂端壓入元素item
End BSTACK
1.試寫出上述抽象數(shù)據(jù)類型中每一種操作的算法。
解：
void InitStack(BothStack& BS,int k)
{
if(k==1)
BS.top1=-1;
else if(k==2)
BS.top2=StackMaxSize;
else if(k==3){
BS.top1=-1;
BS.top2=StackMaxSize;
}
}
void ClearStack(BothStack& BS,int k)
{ //函數(shù)體同上
}
int StackEmpty(BothStack& BS,int k){
if(k==1)
return BS.top1==-1;
else if(k==2)
return BS.top2==StackMaxSize;
else if(k==3)
return(BS.top1==-1)&&(BS,top2==StackMaxSize);
else{
cerr<<"k的值不正確!"';
exit(1);
}
}
ElemType peek(BothStack& BS,int k)
{
if(k==1){
if(BS.top1==-1){
cerr<<"Stack 1 is empty!"<<end1;
exit(1);
}
return BS,stack(bs,top1);
}
else if(k==2){
if(BS.top2==StackMaxSize){
cerr<<"Stack 2 is empty!"<<end1;
exit(1);
}
return BS,stack[BS,top2];
}
else{
cerr<<"k的值不正確!";
exit(1);
}
}
void push(BothStack& BS,int k,const ElemType& item)
{
if(BS.top1==BS.top2-1){
cerr<<"Stack overflow!"<<end1;
exit(1);
}
if(k==1){
BS.top1++;
Bs.stack[BS.top1]=item;
}
else if(k==2){
BS.top1--;
BS.stack[BS.top2]=item;
}
}
ElemType pop(BothStack& BS,int k]
{
if(k==1){
if(BS.top==-1){
cerr<<"Stack 1 is empty!"<<end1;
exit(1);
}
BS.top--;
return BS,stack[BS.top1+1];
}
else if(k==2){
if(BS.top==StackMaxSize){
cerr<<"Stack 2 is empty!"<<end1;
exit(1);
}
BS.top2++;
return BS.stack[BS,top2-1];
}
else{
cerr<<"k的值不正確!";
exit(1);
}
}
2.假定上述所有操作的算法已存于頭文件"bstack.h"中，試編寫一個程序，讓計算機隨機
產(chǎn)生出100以內(nèi)的20個正整數(shù)并輸出，同時把它們中的偶數(shù)依次存入到第一個棧中，奇數(shù)
依次存入到第二個棧中，接著按照存入每個棧中元素的次序分別輸出每個棧中的所有元素
(此操作不改變棧的狀態(tài))，然后按照后進先出的原則輸出每個棧中的所有元素。
解：
#include<iostream.h>
#include<stdlib.h>
const int StackMaxSize=50;
typedef int ElemType;
struct BothStack{
ElemType stack[StackMaxSize];
int top1,top2;
};
#include"bstack.h"
void main()
{
BothStack a;
InitStack(a,3);//初始化兩個棧
int i,j,k;
//計算機產(chǎn)生20個隨機數(shù)并輸出，同時按奇偶數(shù)不同分別放入不同的棧中
for(i=0;i<20;i++){
j=rand()%100;
cout<<j<<"";
if(j%2==0)
push(a,1,j);
else
push(a,2,j);
}
cout<<end1;
//按照存入棧1中元素的次序輸出棧1中的所有元素
cout<<"棧1：";
for(i=0;i<=a.top1;i++)
cout<<a.stack[i]<<"";
cout<<end1;
//按照存入棧2中元素的次序輸出棧2中的所有元素
cout<<"棧2：";
for(i=StackMaxSize-1;i>=a.top2;i--)
cout<<a.stack[i]<<"";
cout<<end1;
//按照后進先出的原則輸出每個棧中的所有元素
for(k=1;k<=2;k++){
if(k==1)
cout<<"棧1：";
else
cout<<"棧2：";
while(!StackEmpty(a,k))
cout<<Pop(a,k)<<"";
cout<<end1;
}
}
該程序輸入并運行后將得到如下結(jié)果(由于機器系統(tǒng)和C++版本不同，你得到的結(jié)果可能
與此不同)：
41 67 34 0 69 24 78 58 62 5 45 81 27 61 91 95 42 27 36
棧1：34 0 24 78 58 62 64 42 36
棧2：41 67 69 5 45 81 27 61 91 95 27
棧1：36 42 64 62 58 78 24 0 34
棧2：27 95 91 61 27 81 45 5 69 67 41
3.設(shè)用第二章定義的類型為AlinkList的一維數(shù)組MS[MaxSize]建立三個鏈接堆棧，其中前三個元
素的next域用來存儲三個棧頂指針，從下標(biāo)為3的元素起作為空閑元素提供給三個棧共同使用，
試編寫一個算法把從鍵盤上輸入的n個整數(shù)按照下列條件分別進入不同的棧：
⑴若輸入的整數(shù)x小于60，則進第一個棧；
⑵若輸入的整數(shù)x大于等于60同時小于100，則進第二個棧；
⑶若輸入的整數(shù)大于100，則進第三個棧。
解：
void MoreStack(ALinkList MS,int n)
//把從鍵盤上輸入的n個整數(shù)按不同條件分別進入到三個不同的鏈接棧中
{
if(n>MaxSize-3){
cerr<<"存儲空間不足!";
exit(1);
}
int i,x,av;
for(i=0;i<3;i++)
MS[i].next=0//置空棧，即給三個棧頂指針賦0
av=3;//av指向可利用元素的下標(biāo)，賦初值為3
cout<<"輸入"<<n<<"個整數(shù)："<<end1;
for(i=0;i<n;i++){
//從鍵盤讀入一個整數(shù)并把它賦給av元素的值域
cin>>x;
MS[av].data=x;
//按條件把av元素壓入不同的棧，即鏈接到相應(yīng)棧的棧頂
if(x<60){
Ms[av].next=MS[0].next;
MS[0].next=av;
}
else if(x>=60&&x<=100){
MS[av].next=MS[1].next;
MS[1].next=av;
}
else{
MS[av].next=MS[2].next;
MS[2].next=av;
}
//使av指向下一個可利用元素
av++;
}
}
4.編寫一個程序，首先調(diào)用上題算法，然后分別打印出每個棧中的內(nèi)容。
解：
#include<iostream.h>
#include<stdlib.h>
const int MaxSize=50;//要至少定義為比輸入的整數(shù)個數(shù)大3
typedef int ElemType;
struct ALNode{
ElemType data;
int next;
};
typedef ALNode ALinkList[MaxSize];
void MoreStack(ALinkList MS,int n)
{//函數(shù)體在此省略
}
void main()
{
ALinkList a;
int n;
cout<<"從鍵盤輸入的整數(shù)個數(shù)(1～47):";
cin>>n;
MoreStack(a,n);
for(int i=0;i<3;i++)
{ //依次將每個棧中的元素全部出棧并打印出來
int j=a[i].next;
while(j!=0){
cout<<a[j].data<<"";
j=a[j].next;
}
cout<<end1;
}
}
一次輸入和運行結(jié)果如下：
從鍵盤上輸入的整數(shù)個數(shù)為(1～47)：12
輸入12個整數(shù)：
38 64 97 120 78 33 45 214 88 25 143 60
25 45 33 38
60 88 78 97 64
143 214 120
5.已知一個中綴算術(shù)表達式為：
3+4/(25-(6+15))*8@
⑴寫出對應(yīng)的后綴算術(shù)表達式。
解：3 4 25 6 15 + - /8 * + @
⑵畫出在轉(zhuǎn)換成后綴表達式的過程中運算符棧的變化。
解：略
6.已知一個后綴算術(shù)表達式為：
24 8 + 3 * 4 10 7 - * / @
⑴寫出對應(yīng)的中綴算術(shù)表達式。
解： (24+8)*3/(4*(10-7))
⑵畫出在進行后綴算術(shù)表達式求值的過程中數(shù)值棧的變化。
解：略
7.為了計算表達式的值：
把棧Stack類型定義為帶模板的類型，該類型中包含順序存儲的棧和對棧的每一種基
本操作的實現(xiàn)。
解：把進行后綴表達式求值的Compute算法改寫為使用Stack類的算法。
解：把進行中綴表達式轉(zhuǎn)換為后綴表達式的Change算法改寫為使用Stack類的算法。
解：寫出計算C(n,k)的遞歸算法。
解：利用二維數(shù)組寫出計算C(n,k)的非遞歸算法。
解：分析遞歸算法和非遞歸算法的時間復(fù)雜度和空間復(fù)雜度。
解：
template<class ElemType>
class Stack{
ElemType stack[StackMaxSize];
int top;
public:
void InitStack()
//初始化棧對象，即把它置為空
{
top=-1;
}
void ClassStack()
//清除棧對象中的所有元素，使之成為一個空棧
{
top=-1;
}
int StackEmpty()
//判斷棧對象是否為空，若是則返回1，否則返回0
{
return top==-1;
}
ElemType peek()
//返回棧對象的棧頂元素，但不移動棧頂指針
{
if(top==-1){
cerr<<"Stack is empty!"<<end1;
exit(1);
}
return stack[top];
}
void push(const ElemType& item)
//元素item進棧，即插入到棧頂
if(top==StackMaxSize-1){
cerr<<"Stack overflow!"<<end1;
exit(1);
}
top++;
stack[top]=item;
}
ElemType Pop()
//刪除棧頂元素并返回之
{
if(top==-1){
cerr<<"Stack is empty!"<<end1;
exit(1);
}
ElemType temp=stack[top];
top--;
return temp;
}
}
float Compute(char* str)
{
Stack<float> s;//定義元素類型為float的棧
S.InitStack();
istrstream ins(str);
char ch;
float x;
ins>>ch;
while(ch!='@')
{ //掃描每一個字符并進行相應(yīng)處理
switch(ch)
{
cass'+':
X=S.Pop()+S.Pop();
break;
cass'-':
X=S.Pop();
X=S.Pop()-X;
break;
cass'*':
X=S.Pop()*S.Pop();
break;
cass'/':
X=S.Pop();
if(X!=0.0)
X=S.Pop()/X;
else{
cerr<<"Divide by 0!"<<end1;
exit(1);
}
break;
default://讀入的必為一個浮點數(shù)的最高位數(shù)字
ins.putback(ch);
ins<<X;
}
S.Push(X);
ins>>ch;
}
if(!S.StackEmpty())
{
x=s.Pop();
if(!S.StackEmpty())
return X;
else{
cerr<<"expression error!"<<end1;
exit(1);
}
}
else{
cerr<<"Stack is empty!"<<end1;
exit(1);
}
}
void Change(char* s1,char* s2)
{
Stack<char>R;//定義元素類型為char的棧
R.InitStack();
R.push('@');
int i,j;
i=0;
j=0;
char ch=s1[i];
while(ch='@')
{
if(ch=='')
ch=s1[++i];
else if(ch=='('){
R.Push(ch);
ch=s1[++i];
}
else if(ch==')'){
while(R.peek()!='(')
s2[j++]=R.Pop();
R.Pop();
ch=s1[++i];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){
char w=R.peek();
while(precedence(w)>=Precedence(ch){
s2[j++]=w;
R.Pop();w=R.Peek();
}
R.Push(ch);
ch=s1[++i];
}
else{
while(isdigit(ch)||ch=='.'){
s2[j++]=ch;
ch=s1[++i];
}
s2[j++]='';
}
}
ch=R.Pop();
while(ch!='@'){
s2[j++]=ch;
ch=R.Pop();
}
s2[j++]='@';
s2[j++]='\0';
}
8.編寫把十進制正整數(shù)轉(zhuǎn)換為十六進制數(shù)輸出的算法。
解：
void Transform(long num)
//把一個正整數(shù)num轉(zhuǎn)為一個十六進制數(shù)輸出
{
Stack a;
InitStack(a);
while(num!=0){
int k=num % 16;
Push(a,k);
num/=16;
}
while(!StackEmpty(a))
{
int X=Pop(a);
if(x<10)
cout<<x;
else{
switch(x)
{
cass 10:
cout<<'A';
break;
cass 11:
cout<<'B';
break;
cass 12:
cout<<'C';
break;
cass 13:
cout<<'D';
break;
cass 14:
cout<<'E';
break;
cass 15:
cout<<'F';
}
}
}
cout<<end1;
}
9.編寫把十進制正整數(shù)轉(zhuǎn)換為S進制(2≤S≤9)數(shù)輸出的遞歸算法，然后若把425轉(zhuǎn)換為六進制
數(shù)，畫出每次遞歸調(diào)用前和返回后系統(tǒng)棧的狀態(tài)。
解：
只給出遞歸算法，畫圖從略。
void Transform(long num,int s)
//把十進制正整數(shù)轉(zhuǎn)換為S進制數(shù)的遞歸算法
{
int k;
if(num!=0){
k=num%S;
Transfrom(num/S,S);
cout<<k;
}
}
10.裴波那契(Fibonacci)數(shù)列的定義為：它的第一項和第二項均為1，以后各項為其前兩項之和。
若裴波那契數(shù)列中的第n項用Fid(n)表示，則計算公式為：
1 (n=1或n=2)
Fib(n)= Fib(n-1)+Fib(n-2) (n>=2)
試編寫計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復(fù)雜度和空間復(fù)雜度。
解：
遞歸算法為：
long Fib(int n)
{
if(n==1||n==2) //終止遞歸條件
return 1;
else
return Fib(n-1)+Fib(n-2);
}
非遞歸算法為
long Fib1(int n)
{
int a,b,c;//C代表當(dāng)前項，a和b分別代表當(dāng)前項前面的第2項和第1項
a=b=1; //給a和b賦初值1
if(n==1||n==2)
return 1;
else
for(int i=3;i<=n;i++){
c=a+b; //求出當(dāng)前項
a=b;//把前面第1項賦給前面第2項
b=c;//把當(dāng)前項賦給前面第1項
}
return c;//返回所求的第n項
}
11.根據(jù)代數(shù)中的二項式定理，二項式(x+y)n的展開式的系數(shù)序列可以表示成
圖4-1那樣的三角形，其中除每一行最左和最右兩個系數(shù)等于1以外，其余各數(shù)均等于上一
行左右兩系數(shù)之和。這個系數(shù)三角形稱作楊輝三角形。
(x+y)0 1
(x+y)1 1 1
(x+y)2 1 2 1
(x+y)3 1 3 3 1
(x+y)4 1 4 6 4 1
(x+y)5 1 5 10 10 5 1
(x+y)6 1 6 15 20 15 6 1
(x+y)7 1 7 21 35 35 21 7 1
(x+y)8 1 8 28 56 70 56 28 8 1
圖4-1 楊輝三角形
設(shè)C(n,k)表示楊輝三角形中第n行(n≥0)的第k個系數(shù)(0≤k≤n)，按照二項式定理，C(n,k)
可遞歸定義為：
1 (k=0或k=n)
C(n,k)=
C(n-1,k-1)+C(n-1,k) (n>=2)
int C(int n,int k)
//求出指數(shù)為n的二項展開式中第k項(0<=k<=n)系數(shù)的遞歸算法
{
if(k==0||k==n)
return 1;
else
return C(n-1,k-1)+C(n-1,k);
}
int C1(int n,int k)
//求出指數(shù)為n的二項展開式中第k項(0<=k<=n)系數(shù)的非遞歸算法
{
typedef int b[15];
//定義一維整型數(shù)組類型[15]為b，其尺寸要大于參數(shù)n
b*a=new b[n+1];
//動態(tài)分配具有b類型的一維數(shù)組，其尺寸為n+1，這樣a就指向了一個具有
//[n+1][15]的二維數(shù)組。
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
//外循環(huán)每循環(huán)一次計算出指數(shù)為i的二項展開式的所有系數(shù)，內(nèi)循環(huán)每循環(huán)
//一次計算出此展開式中第j項的系數(shù)
if(j==0||j==1)
a[i][j]=1;
else
a[i][j]=a[i-1][j-1]+a[i-1][j];
return a[n][k]; //返回指數(shù)為n的二項展開式中第k項的系數(shù)
}
遞歸時間復(fù)雜度和空間復(fù)雜度分別為O(2n)和O(n)，非遞歸算法的時間復(fù)雜
度和空間復(fù)雜度均為O(n2)。
12.利用堆棧編寫出求解迷宮問題的非遞歸算法。
解：
設(shè)描述迷宮中當(dāng)前位置的結(jié)構(gòu)如下
struct item
{//定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)
int x,y,d; //x和y分別表示當(dāng)前位置的行坐標(biāo)和列坐標(biāo)，d表示移動到下一步的方向
};
此題的算法如下:
void Seekpath(int m,int n)
//查找m*n迷宮從入口(1,1)到出口(m,n)的一條通路
{
mark[1][1]=1;
Stack S;//棧的元素類型應(yīng)定義為item
InitStack(s);
items temp;
temp.x=1;temp.y=1;temp.d=-1;
push(s,temp);//將入口點壓入棧
while(!stackEmpty(s))
{ //每循環(huán)一次從查找的路徑中退回一步
temp=Pop(S);//將保存的上一個位置出棧
int x=temp.x;int y=temp.y;int d=temp.d+1;
//沿著該位置的下一個方向前進
while(d<4)
{//按順時針方向試探著前進
if(x==m&&y==n)//到達出口，按逆序輸出路徑中每個位置的坐標(biāo)，然后返回
{
cout<<m<<""<<n<<end1;
while(!StackEmpty(S)){
temp=Pop(S);
cout<<temp.x<<""<<temp.y<<end1;
}
return;
}
int g=x+move[d][0];int h=y+move[d][1];
//按方向d前進，求出下一個位置的坐標(biāo)
if(mase[g][h]==0&&mark[g][h]==0)
{//對未訪問過的可通行的下一個位置，應(yīng)將當(dāng)前位置進棧，并將下一個位置
//變?yōu)楫?dāng)前位置，否則改變沿當(dāng)前位置前進的方向
mark[g][h]=1;
temp.x=x;temp.y=y;temp.d=d;
Push(S,temp);
x=g;y=h;d=0;
//進入一個新位置后，重新從初開始方向東開始
}
else
d++;
}
}
cout<<"不存在從入口到出口的通路"<<end1;
}
調(diào)用此算法的完整程序如下。
#include<iostream.h>
#include<stdlib.h>
const int StackMaxSize=30;
struct item
{//定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)
int x,y,d;//x和y分別表示當(dāng)前位置的行坐標(biāo)和列坐標(biāo)，d表示移動到下一步的
//方向
};
typedef items ElemType; //定義棧中元素的類型為items類型
struct stack{
ElemType stack[StackMaxSize];
int top;
};
#include"stack.h"http://保存棧基本操作算法的頭文件
const M=10,N=10; //定義M和N常量，由它們決定迷宮的最大尺寸
int maze[M+2][N+2];//定義保存迷宮數(shù)據(jù)的數(shù)組
int mark[M+2][N+2];//定義保存訪問標(biāo)記的數(shù)組
int move[4][2]={{0,1},{0,-1},{-1,0}};
//行下標(biāo)0,1,2,3分別代表東,南,西,北方向
void SeekPath(int m,int n)
//查找m*n迷宮中從入口(1,1)到出口(m,n)的一條通路
{//函數(shù)體在此省略
}
void main(void)
{
int i,j;
int m,n;
//輸入迷宮尺寸
do{
cout<<"輸入迷宮的行數(shù)m和列數(shù)n："；
cin>>m>>n;
if(m>M||n>N)cout<<"重新輸入m和n的值."<<end1;
}while(m>M||n>N);
//輸入迷宮數(shù)據(jù)
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)
cin>>maze[i][j];
//初始化mark數(shù)組
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)
mark[i][j]=0;
//求解maze迷宮中從入口(1,1)到出口(m,n)的一條路徑
Seekpath(m,n);
}
13.編寫一個遞歸算法，輸出自然數(shù)1～n這n個元素的全排列。
分析：由排列組全的知識可知，n個元素的全排列共有n!種，如對于1,2,3這三個元素,其全排
列為123,132,213,231,321,312,共3!=6種。n!種可分解為n*(n-1)!種，而(n-1)!種又可分解
為(n-1)(n-2)!種，依次類推。對于n個元素 ,可把它們分別放入到n個位置上，讓第一個元素
依次取每一個元素，共有n種不同的取法，對其后n-1個位置上的n-1個元素，共有(n-1)!種不
同的排列，所以總共有n(n-1)!種不同的排列；同樣，
解：
對n個元素的全排列是一個遞算法，具體描述如下。
void Permute(int a[],int s,int n)
//對a[s]～a[n-1]中的n-s個元素進行全排列，s的初始值為0
{
int i,temp;
if(s==n-1)
{ //當(dāng)遞歸排序到最后一個元素時結(jié)束遞歸，輸出a中保存的一種排列
for(i=0;i<n;i++)
cout<<a[i]<<"";
cout<<"";
}
else //繼續(xù)遞歸排列
for(i=s;i<n;i++)
{ //每循環(huán)一次使a[s]取一個新值，并對其后的所有元素進行遞歸排序
temp=a[s];a[s]=a[i];a[i]=temp;
//交換a[s]與a[i]的元素值
Permute(a,s+1,n);
//對a[s+1]～a[n-1]中的元素進行遞歸排序
temp=a[s];a[s]=a[i];a[i]=temp;
//恢復(fù)a[s]與a[i]的原有值
}
}
調(diào)用此算法的完整程序如下。
#include<iostream.h>
const int UpperLimit=6;//定義全排列的元素個數(shù)的最大值
void Permute(int a[],int s,int n)
//對a[s]～a[n-1]中的n-s個元素進行全排列，s的初值為0
{
}//函數(shù)體在此省略
void main(void)
{
int a[UpperLimt];//定義存儲n個整型元素的數(shù)組
int n;
cout<<"Enter a number'n'between 1and"
<<UpperLimit<<":";
cin>>n;//輸入待全排的元素的個數(shù)
for(int i=0;i<n;i++)
a[i]=i+1; //給數(shù)組a賦初值
cout<<end1;
Permute(a,0,n);//對數(shù)組a中的n個元素(即1-n)進行全排列
cout<<end1;
}
14.根據(jù)
解： 略
15.假定用于順序存儲一個隊列的數(shù)組的長度為N，隊首和隊尾指針分別為front和rear
，寫出求此隊列長度(即所含元素個數(shù))的公式。
解：
隊列長度的計算公式為：
(N+rear-front)%N
16.假定在一個鏈接隊列中只設(shè)置隊尾指針，不設(shè)置隊首指針，并且讓隊尾結(jié)點的指針域
指向隊首結(jié)點(稱此為循環(huán)鏈隊)，試分別寫出在循環(huán)鏈隊上進行插入和刪除的算法。
解：
插入操作的算法如下。
void QInsert(LNode*&Rear,const ElemType& item)
//使新元素item的值插入到循環(huán)鏈隊中
{
LNode*newptr=new Lnode;
//得到一個由newptr指針?biāo)赶虻男陆Y(jié)點
if(newptr==NULL){
cerr<<"Memory allocation failare"<<end1;
exit(1);
}
newptr->data=item;//把item的值賦給新結(jié)點的值域
if(Rear==NULL)
Rear=newptr->next=newptr;
//若鏈隊為空，則新結(jié)點即是隊首結(jié)點又是隊尾結(jié)點
else{
newptr->next=Rear->next;
//使新結(jié)點的指針域指向隊首結(jié)點
Rear->next=newptr;
//使隊尾結(jié)點的指針域指向新結(jié)點
Rear=newptr;
//使新結(jié)點成為新的隊尾結(jié)點
}
}
刪除操作的算法如下。
ElemType QDelete(LNode*&Rear)
//從循環(huán)鏈隊中刪除隊首元素
{
if(Rear==NULL){
cerr<<"Linked queue is empty!"<<end1;
exit(1);
}
LNode* p=Rear->next; //使p指向隊首結(jié)點
if(p==Rear)
Rear=NULL;
//若鏈隊中只有一個結(jié)點，則刪除后隊尾指針為空
else
Rear->next=p->next;
//使隊尾結(jié)點的指針域指向隊首結(jié)點的后繼結(jié)點
ElemType temp=p->data;//暫存隊首元素
delete p;//回收原隊首結(jié)點
return temp;//返回被刪除的隊首元素
}
