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