1，? 若入棧的元素為n,則可得到的輸出序列數量為 (2n)!/(n+1)(n!)(n!)。

2，? 用兩個長度相同的棧S1,S2構造一個隊列。在S1中進行入隊操作，S2中進行出隊操作 ，判斷隊列空的條件是，S1和S2同時為空，判斷隊列滿的條件是S1和S2同時為滿。

void?EnQueue(ElemType?x)
{
????if(!Full(S1))
????{//S1未滿直接進入
????????S1.Push(x);
????}
????else
????{
????????if(Empty(S2)==true)
????????{
????????????while(!Empty(S1))
????????????{
????????????????S2.Push(S1.Pop());
????????????}
????????????S1.Push(x);????????
????????}
????}
}

ElemType?DeQueue()
{
????if(!Empty(S2))
????{
????????return?S2.Pop();
????}
????else
????{
????????if(!Empty(S1))
????????{
????????????while(!Empty(S1))
????????????{
????????????????S2.Push(S1.Pop());
????????????}
????????????return?S2.Pop();
????????}
????????
????}
}

3.求兩個正整數的最大公約數的非遞歸算法。

#define?MAX?100
struct?Stack
{
????int?s;
????int?t;
};

int?gcd(int?m,int?n)
{
????int?k;
????Stack?S[MAX];
????int?top?=?-1,tmp;
????if(m<n)
????{
????????tmp?=?m;
????????m?=?n;
????????n?=?tmp;
????}
????top++;
????S[top].s?=?m;
????S[top].t?=?n;
????while(top>=0&&S[top].t!=0)
????{
????????if(S[top].t!=0)
????????{
????????????tmp?=?S[top].s;
????????????m?=?S[top].t;
????????????n?=?m%tmp;
????????????top++;
????????????S[top].s?=?m;
????????????S[top].t?=?n;
????????}
????}
????return?S[top].s;
}

4．

????????????????????? n+1,m =0

Akm(m,n)? =?????????? Akm(m-1,1) m!=0,n=0

????????????????????? Akm(m-1,Akm(m,n-1)),m!=0,n!=0

寫非遞歸算法。

#define?MAXSIZE?100
typedef?struct
{
????int?tm;
????int?tn;
}Stack;

int?akm(int?m,int?n)
{
????Stack?S[MAXSIZE];
????int?top?=?0;
????S[top].tm?=?m;
????S[top].tn?=?n;
????do
????{
????????while(S[top].tm!=0)
????????{
????????????while(S[top].tn!=0)
????????????{
????????????????top++;
????????????????S[top].tm?=?S[top-1].tm;
????????????????S[top].tn?=?S[top-1].tn-1;
????????????}
????????????S[top].tm--;
????????????S[top].tn=1;
????????}
????????if(top>0)
????????{
????????????top--;
????????????S[top].tm--;
????????????S[top].tn?=?S[top].tn+1;
????????}
????????
????}while(top!=0?||?S[top].tm!=0);
????top--;
????return?S[top+1].tn+1;
}

5．寫出和下列遞歸過程等價的非遞歸過程

void?test(int?&sum)
{
????int?k;
????scanf("%d",&k);
????if(k==0)?sum?=?1;
????else
????{
????????test(sum);
????????sum?=?k*sum;
????}
????printf("%d",sum);
}

分析：程序功能是按照輸入的整數，按相反順序進行累計乘法運算

#define?MAXSIZE?100
void?test(int?&sum)
{
????int?Stack[MAXSIZE];
????int?top?=?-1,k;
????sum?=?1;
????scanf("%d",&k);
????while(k!=0)
????{
????????Stack[++top]?=?k;
????????scanf("%d",&k);
????}
????printf("%d",sum);
????while(top!=-1)
????{
????????sum?*=Stack[top--];
????????printf("%d",sum);
????}
}
????????

6．假設表達式由單字母變量和雙目四則運算算符構成，寫一個算法，將一個書寫正確的表達式轉換為逆波蘭式。

void?ConPoland(char?express[],char?suffix[])
{
????char?*p?=?express,ch1?=?*p,ch2;
????int?k?=?0;
????InitStack(S);
????Push(S,'#');
????while(!StackEmpty(S))
????{
????????if(!IsOperator(ch1))
????????????suffix[k++]?=?ch1;
????????else
????????{
????????????switch(ch1)
????????????{
????????????????case?'(':????
????????????????????Push(S,ch1);break;
????????????????case?')':????
????????????????????Pop(S,ch2);
????????????????????while(ch2!='(')????
????????????????????{
????????????????????????suffix[k++]?=?ch2;
????????????????????????Pop(S,ch2);
????????????????????}
????????????????????break;
????????????????default:
????????????????????while(GetTop(S,ch2)&&precede(ch2,ch1))
????????????????????{
????????????????????????suffix[k++]?=?ch2;
????????????????????????Pop(S,ch2);
????????????????????}
????????????????????if(ch1!='#')
????????????????????????Push(S,ch1);
????????????????????break;????????????????????????????
????????????????????
????????????}
????????}
????????if(ch1!="#')????
????????????ch1?=?*++p;
????}
????suffix[k]?=?'\0';
}

總結

以上是生活随笔為你收集整理的数据结构复习笔记(2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。