嚴蔚敏版C語言數(shù)據(jù)結(jié)構(gòu)習題集答案

說明: 1. 本文是對嚴蔚敏數(shù)據(jù)結(jié)構(gòu)(c語言版)習題集一書中所有算法設(shè)計題目的解決方案,主要作者為計算機版版主一具.以下網(wǎng)友:siice,龍?zhí)ь^,iamkent,zames,birdthinking等為答案的修訂和完善工作提出了寶貴意見,在此表示感謝;2. 本解答中的所有算法均采用類c語言描述,設(shè)計原則為面向交流、面向閱讀,作者不保證程序能夠上機正常運行(這種保證實際上也沒有任何意義);3. 本解答原則上只給出源代碼以及必要的注釋,對于一些難度較高或思路特殊的題目將給出簡要的分析說明,對于作者無法解決的題目將給出必要的討論.目前尚未解決的題目有: 5.20, 10.40;4. 請讀者在自己已經(jīng)解決了某個題目或進行了充分的思考之后,再參考本解答,以保證復習效果;5. 由于作者水平所限,本解答中一定存在不少這樣或者那樣的錯誤和不足,希望讀者們在閱讀中多動腦、勤思考,爭取發(fā)現(xiàn)和糾正這些錯誤,寫出更好的算法來.請將你發(fā)現(xiàn)的錯誤或其它值得改進之處向作者報告: yi-ju 第一章 緒論 1.16 void print_descending(int x,int y,int z)/按從大到小順序輸出三個數(shù) scanf("%d,%d,%d",&x,&y,&z); if(x<y) x<->y; /<->為表示交換的雙目運算符,以下同 if(y<z) y<->z; if(x<y) x<->y; /冒泡排序 printf("%d %d %d",x,y,z);/print_descending 1.17 Status fib(int k,int m,int &f)/求k階斐波那契序列的第m項的值f  int tempd;  if(k<2|m<0) return ERROR;  if(m<k-1) f=0;  else if (m=k-1) f=1;  else      for(i=0;i<=k-2;i+) tempi=0;    tempk-1=1; /初始化    for(i=k;i<=m;i+) /求出序列第k至第m個元素的值          sum=0;      for(j=i-k;j<i;j+) sum+=tempj;      tempi=sum;        f=tempm;    return OK;/fib分析:通過保存已經(jīng)計算出來的結(jié)果,此方法的時間復雜度僅為O(m2).如果采用遞歸編程(大多數(shù)人都會首先想到遞歸方法),則時間復雜度將高達O(km). 1.18 typedef struct                 char *sport;                 enummale,female gender;                 char schoolname; /校名為'A','B','C','D'或'E'                 char *result;                 int score;                resulttype; typedef struct                 int malescore;                 int femalescore;                 int totalscore;                scoretype; void summary(resulttype result )/求各校的男女總分和團體總分,假設(shè)結(jié)果已經(jīng)儲存在result 數(shù)組中  scoretype score;  i=0;  while(resulti.sport!=NULL)      switch(resulti.schoolname)          case 'A':        score 0 .totalscore+=resulti.score;        if(resulti.gender=0) score 0 .malescore+=resulti.score;        else score 0 .femalescore+=resulti.score;        break;      case 'B':        score.totalscore+=resulti.score;        if(resulti.gender=0) score.malescore+=resulti.score;        else score.femalescore+=resulti.score;        break;                      i+；    for(i=0;i<5;i+)      printf("School %d:n",i);    printf("Total score of male:%dn",scorei.malescore);    printf("Total score of female:%dn",scorei.femalescore);    printf("Total score of all:%dnn",scorei.totalscore);  /summary 1.19 Status algo119(int aARRSIZE)/求i!*2i序列的值且不超過maxint  last=1;  for(i=1;i<=ARRSIZE;i+)   ai-1=last*2*i;   if(ai-1/last)!=(2*i) reurn OVERFLOW;   last=ai-1;   return OK;  /algo119分析:當某一項的結(jié)果超過了maxint時,它除以前面一項的商會發(fā)生異常. 1.20 void polyvalue()  float ad;  float *p=a;  printf("Input number of terms:");  scanf("%d",&n);  printf("Input the %d coefficients from a0 to a%d:n",n,n);  for(i=0;i<=n;i+) scanf("%f",p+);  printf("Input value of x:");  scanf("%f",&x);  p=a;xp=1;sum=0; /xp用于存放x的i次方  for(i=0;i<=n;i+)      sum+=xp*(*p+);    xp*=x;    printf("Value is:%f",sum);/polyvalue第二章 線性表 2.10 Status DeleteK(SqList &a,int i,int k)/刪除線性表a中第i個元素起的k個元素  if(i<1|k<0|i+k-1>a.length) return INFEASIBLE;  for(count=1;i+count-1<=a.length-k;count+) /注意循環(huán)結(jié)束的條件    a.elemi+count-1=a.elemi+count+k-1;  a.length-=k;  return OK;/DeleteK 2.11Status Insert_SqList(SqList &va,int x)/把x插入遞增有序表va中  if(va.length+1>va.listsize) return ERROR;  va.length+;  for(i=va.length-1;va.elemi>x&&i>=0;i-)    va.elemi+1=va.elemi;  va.elemi+1=x;  return OK;/Insert_SqList 2.12 int ListComp(SqList A,SqList B)/比較字符表A和B,并用返回值表示結(jié)果,值為正,表示A>B;值為負,表示A<B;值為零,表示A=B  for(i=1;A.elemi|B.elemi;i+)    if(A.elemi!=B.elemi) return A.elemi-B.elemi;  return 0;/ListComp 2.13 LNode* Locate(LinkList L,int x)/鏈表上的元素查找,返回指針  for(p=l->next;p&&p->data!=x;p=p->next);  return p;/Locate 2.14 int Length(LinkList L)/求鏈表的長度  for(k=0,p=L;p->next;p=p->next,k+);  return k;/Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList &hc)/把鏈表hb接在ha后面形成鏈表hc  hc=ha;p=ha;  while(p->next) p=p->next;  p->next=hb;/ListConcat 2.16 見書后答案. 2.17 Status Insert(LinkList &L,int i,int b)/在無頭結(jié)點鏈表L的第i個元素之前插入元素b  p=L;q=(LinkList*)malloc(sizeof(LNode);  q.data=b;  if(i=1)      q.next=p;L=q; /插入在鏈表頭部    else      while(-i>1) p=p->next;    q->next=p->next;p->next=q; /插入在第i個元素的位置  /Insert 2.18 Status Delete(LinkList &L,int i)/在無頭結(jié)點鏈表L中刪除第i個元素  if(i=1) L=L->next; /刪除第一個元素  else      p=L;    while(-i>1) p=p->next;    p->next=p->next->next; /刪除第i個元素  /Delete 2.19 Status Delete_Between(Linklist &L,int mink,int maxk)/刪除元素遞增排列的鏈表L中值大于mink且小于maxk的所有元素  p=L;  while(p->next->data<=mink) p=p->next; /p是最后一個不大于mink的元素  if(p->next)    /如果還有比mink更大的元素      q=p->next;    while(q->data<maxk) q=q->next; /q是第一個不小于maxk的元素    p->next=q;  /Delete_Between 2.20 Status Delete_Equal(Linklist &L)/刪除元素遞增排列的鏈表L中所有值相同的元素  p=L->next;q=p->next; /p,q指向相鄰兩元素  while(p->next)      if(p->data!=q->data)          p=p->next;q=p->next; /當相鄰兩元素不相等時,p,q都向后推一步        else          while(q->data=p->data) free(q); q=q->next;       p->next=q;p=q;q=p->next; /當相鄰元素相等時刪除多余元素    /else  /while/Delete_Equal 2.21 void reverse(SqList &A)/順序表的就地逆置  for(i=1,j=A.length;i<j;i+,j-)    A.elemi<->A.elemj;/reverse 2.22 void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2  p=L->next;q=p->next;s=q->next;p->next=NULL;  while(s->next)      q->next=p;p=q;    q=s;s=s->next; /把L的元素逐個插入新表表頭    q->next=p;s->next=q;L->next=s;/LinkList_reverse分析:本算法的思想是,逐個地把L的當前元素q插入新的鏈表頭部,p為新表表頭. 2.23 void merge1(LinkList &A,LinkList &B,LinkList &C)/把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲空間  p=A->next;q=B->next;C=A;  while(p&&q)      s=p->next;p->next=q; /將B的元素插入    if(s)          t=q->next;q->next=s; /如A非空,將A的元素插入        p=s;q=t;  /while/merge1 2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)/把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列,使用原空間  pa=A->next;pb=B->next;pre=NULL; /pa和pb分別指向A,B的當前元素  while(pa|pb)      if(pa->data<pb->data|!pb)          pc=pa;q=pa->next;pa->next=pre;pa=q; /將A的元素插入新表        else          pc=pb;q=pb->next;pb->next=pre;pb=q; /將B的元素插入新表        pre=pc;    C=A;A->next=pc; /構(gòu)造新表頭/reverse_merge分析:本算法的思想是,按從小到大的順序依次把A和B的元素插入新表的頭部pc處,最后處理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)/求元素遞增排列的線性表A和B的元素的交集并存入C中  i=1;j=1;k=0;  while(A.elemi&&B.elemj)      if(A.elemi<B.elemj) i+;    if(A.elemi>B.elemj) j+;    if(A.elemi=B.elemj)          C.elem+k=A.elemi; /當發(fā)現(xiàn)了一個在A,B中都存在的元素,      i+;j+; /就添加到C中      /while/SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)/在鏈表結(jié)構(gòu)上重做上題  p=A->next;q=B->next;  pc=(LNode*)malloc(sizeof(LNode);  while(p&&q)      if(p->data<q->data) p=p->next;    else if(p->data>q->data) q=q->next;    else          s=(LNode*)malloc(sizeof(LNode);      s->data=p->data;      pc->next=s;pc=s;      p=p->next;q=q->next;      /while  C=pc;/LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)/求元素遞增排列的線性表A和B的元素的交集并存回A中  i=1;j=1;k=0;  while(A.elemi&&B.elemj)      if(A.elemi<B.elemj) i+;    else if(A.elemi>B.elemj) j+;    else if(A.elemi!=A.elemk)          A.elem+k=A.elemi; /當發(fā)現(xiàn)了一個在A,B中都存在的元素      i+;j+; /且C中沒有,就添加到C中      /while  while(A.elemk) A.elemk+=0;/SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)/在鏈表結(jié)構(gòu)上重做上題  p=A->next;q=B->next;pc=A;  while(p&&q)      if(p->data<q->data) p=p->next;    else if(p->data>q->data) q=q->next;    else if(p->data!=pc->data)          pc=pc->next;      pc->data=p->data;      p=p->next;q=q->next;      /while/LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C) i=0;j=0;k=0;m=0;/i指示A中元素原來的位置,m為移動后的位置 while(i<A.length&&j<B.length&& k<C.length) if(B.elemj<C.elemk) j+; else if(B.elemj>C.elemk) k+; else same=B.elemj;/找到了相同元素same while(B.elemj=same) j+; while(C.elemk=same) k+;/j,k后移到新的元素 while(i<A.length&&A.elemi<same) A.elemm+=A.elemi+;/需保留的元素移動到新位置 while(i<A.length&&A.elemi=same) i+;/跳過相同的元素 /while while(i<A.length) A.elemm+=A.elemi+;/A的剩余元素重新存儲。 A.length=m; / SqList_Intersect_Delete分析:先從B和C中找出共有元素,記為same,再在A中從當前位置開始, 凡小于same的元素均保留(存到新的位置),等于same的就跳過,到大于same時就再找下一個same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)/在鏈表結(jié)構(gòu)上重做上題  p=B->next;q=C->next;r=A-next;  while(p&&q&&r)      if(p->data<q->data) p=p->next;    else if(p->data>q->data) q=q->next;    else          u=p->data; /確定待刪除元素u      while(r->next->data<u) r=r->next; /確定最后一個小于u的元素指針r      if(r->next->data=u)              s=r->next;        while(s->data=u)                  t=s;s=s->next;free(t); /確定第一個大于u的元素指針s        /while        r->next=s; /刪除r和s之間的元素      /if      while(p->data=u) p=p->next;      while(q->data=u) q=q->next;    /else  /while/LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)/刪除單循環(huán)鏈表中結(jié)點s的直接前驅(qū)  p=s;  while(p->next->next!=s) p=p->next; /找到s的前驅(qū)的前驅(qū)p  p->next=s;  return OK;/Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)/完成雙向循環(huán)鏈表結(jié)點的pre域  for(p=L;!p->next->pre;p=p->next) p->next->pre=p;  return OK;/DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)/把單鏈表L的元素按類型分為三個循環(huán)鏈表.CiList為帶頭結(jié)點的單循環(huán)鏈表類型.  s=L->next;  A=(CiList*)malloc(sizeof(CiLNode);p=A;  B=(CiList*)malloc(sizeof(CiLNode);q=B;  C=(CiList*)malloc(sizeof(CiLNode);r=C; /建立頭結(jié)點  while(s)      if(isalphabet(s->data)          p->next=s;p=s;        else if(isdigit(s->data)          q->next=s;q=s;        else          r->next=s;r=s;      /while  p->next=A;q->next=B;r->next=C; /完成循環(huán)鏈表/LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)/從左向右輸出異或鏈表的元素值  p=L.left;pre=NULL;  while(p)      printf("%d",p->data);    q=XorP(p->LRPtr,pre);    pre=p;p=q; /任何一個結(jié)點的LRPtr域值與其左結(jié)點指針進行異或運算即得到其右結(jié)點指針  /Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)/在異或鏈表L的第i個元素前插入元素x  p=L.left;pre=NULL;  r=(XorNode*)malloc(sizeof(XorNode);  r->data=x;  if(i=1) /當插入點在最左邊的情況      p->LRPtr=XorP(p.LRPtr,r);    r->LRPtr=p;    L.left=r;    return OK;    j=1;q=p->LRPtr; /當插入點在中間的情況  while(+j<i&&q)      q=XorP(p->LRPtr,pre);    pre=p;p=q;  /while /在p,q兩結(jié)點之間插入  if(!q) return INFEASIBLE; /i不可以超過表長  p->LRPtr=XorP(XorP(p->LRPtr,q),r);  q->LRPtr=XorP(XorP(q->LRPtr,p),r);  r->LRPtr=XorP(p,q); /修改指針  return OK;/Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)/刪除異或鏈表L的第i個元素  p=L.left;pre=NULL;  if(i=1) /刪除最左結(jié)點的情況      q=p->LRPtr;    q->LRPtr=XorP(q->LRPtr,p);    L.left=q;free(p);    return OK;    j=1;q=p->LRPtr;  while(+j<i&&q)      q=XorP(p->LRPtr,pre);    pre=p;p=q;  /while /找到待刪結(jié)點q  if(!q) return INFEASIBLE; /i不可以超過表長  if(L.right=q) /q為最右結(jié)點的情況      p->LRPtr=XorP(p->LRPtr,q);    L.right=p;free(q);    return OK;    r=XorP(q->LRPtr,p); /q為中間結(jié)點的情況,此時p,r分別為其左右結(jié)點  p->LRPtr=XorP(XorP(p->LRPtr,q),r);  r->LRPtr=XorP(XorP(r->LRPtr,q),p); /修改指針  free(q);  return OK;/Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)/按1,3,5,.4,2的順序重排雙向循環(huán)鏈表L中的所有結(jié)點  p=L.next;  while(p->next!=L&&p->next->next!=L)      p->next=p->next->next;    p=p->next;   /此時p指向最后一個奇數(shù)結(jié)點  if(p->next=L) p->next=L->pre->pre;  else p->next=l->pre;  p=p->next; /此時p指向最后一個偶數(shù)結(jié)點  while(p->pre->pre!=L)      p->next=p->pre->pre;    p=p->next;    p->next=L; /按題目要求調(diào)整了next鏈的結(jié)構(gòu),此時pre鏈仍為原狀  for(p=L;p->next!=L;p=p->next) p->next->pre=p;  L->pre=p; /調(diào)整pre鏈的結(jié)構(gòu),同2.32方法/OEReform分析:next鏈和pre鏈的調(diào)整只能分開進行.如同時進行調(diào)整的話,必須使用堆棧保存偶數(shù)結(jié)點的指針,否則將會破壞鏈表結(jié)構(gòu),造成結(jié)點丟失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)/帶freq域的雙向循環(huán)鏈表上的查找  p=L.next;  while(p.data!=x&&p!=L) p=p->next;  if(p=L) return NULL; /沒找到  p->freq+;q=p->pre;  while(q->freq<=p->freq) q=q->pre; /查找插入位置  if(q!=p->pre)      p->pre->next=p->next;p->next->pre=p->pre;    q->next->pre=p;p->next=q->next;    q->next=p;p->pre=q; /調(diào)整位置    return p;/Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)/求升冪順序存儲的稀疏多項式的值  PolyTerm *q;  xp=1;q=P.data;  sum=0;ex=0;  while(q->coef)      while(ex<q->exp) xp*=x0;    sum+=q->coef*xp;    q+;    return sum;/GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)/求稀疏多項式P1減P2的差式P3  PolyTerm *p,*q,*r;  Create_SqPoly(P3); /建立空多項式P3  p=P1.data;q=P2.data;r=P3.data;  while(p->coef&&q->coef)      if(p->exp<q->exp)          r->coef=p->coef;      r->exp=p->exp;      p+;r+;        else if(p->exp<q->exp)          r->coef=-q->coef;      r->exp=q->exp;      q+;r+;        else          if(p->coef-q->coef)!=0) /只有同次項相減不為零時才需要存入P3中              r->coef=p->coef-q->coef;        r->exp=p->exp;r+;      /if      p+;q+;    /else  /while  while(p->coef) /處理P1或P2的剩余項      r->coef=p->coef;    r->exp=p->exp;    p+;r+;    while(q->coef)      r->coef=-q->coef;    r->exp=q->exp;    q+;r+;  /Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)/對有頭結(jié)點循環(huán)鏈表結(jié)構(gòu)存儲的稀疏多項式L求導  p=L->next;  if(!p->data.exp)      L->next=p->next;p=p->next; /跳過常數(shù)項    while(p!=L)      p->data.coef*=p->data.exp-;/對每一項求導    p=p->next;  /QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)/把循環(huán)鏈表存儲的稀疏多項式L拆成只含奇次項的A和只含偶次項的B  p=L->next;  A=(PolyNode*)malloc(sizeof(PolyNode);  B=(PolyNode*)malloc(sizeof(PolyNode);  pa=A;pb=B;  while(p!=L)      if(p->data.exp!=2*(p->data.exp/2)          pa->next=p;pa=p;        else          pb->next=p;pb=p;        p=p->next;  /while  pa->next=A;pb->next=B; /Divide_LinkedPoly第三章 棧與隊列 3.15 typedef struct                 Elemtype *base2;                 Elemtype *top2;               BDStacktype; /雙向棧類型 Status Init_Stack(BDStacktype &tws,int m)/初始化一個大小為m的雙向棧tws  tws.base0=(Elemtype*)malloc(sizeof(Elemtype);  tws.base1=tws.base0+m;  tws.top0=tws.base0;  tws.top1=tws.base1;  return OK;/Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)/x入棧,i=0表示低端棧,i=1表示高端棧  if(tws.top0>tws.top1) return OVERFLOW; /注意此時的棧滿條件  if(i=0) *tws.top0+=x;  else if(i=1) *tws.top1-=x;  else return ERROR;  return OK;/push Status pop(BDStacktype &tws,int i,Elemtype &x)/x出棧,i=0表示低端棧,i=1表示高端棧  if(i=0)      if(tws.top0=tws.base0) return OVERFLOW;    x=*-tws.top0;    else if(i=1)      if(tws.top1=tws.base1) return OVERFLOW;    x=*+tws.top1;    else return ERROR;  return OK;/pop 3.16 void Train_arrange(char *train)/這里用字符串train表示火車,'H'表示硬席,'S'表示軟席  p=train;q=train;  InitStack(s);  while(*p)      if(*p='H') push(s,*p); /把'H'存入棧中    else *(q+)=*p; /把'S'調(diào)到前部    p+;    while(!StackEmpty(s)      pop(s,c);    *(q+)=c; /把'H'接在后部  /Train_arrange 3.17 int IsReverse()/判斷輸入的字符串中'&'前和'&'后部分是否為逆串,是則返回1,否則返回0  InitStack(s);  while(e=getchar()!='&')    push(s,e);  while(e=getchar()!='')      if(StackEmpty(s) return 0;    pop(s,c);    if(e!=c) return 0;    if(!StackEmpty(s) return 0;  return 1;/IsReverse 3.18 Status Bracket_Test(char *str)/判別表達式中小括號是否匹配  count=0;  for(p=str;*p;p+)      if(*p='(') count+;    else if(*p=')') count-;    if (count<0) return ERROR;    if(count) return ERROR; /注意括號不匹配的兩種情況  return OK;/Bracket_Test 3.19 Status AllBrackets_Test(char *str)/判別表達式中三種括號是否匹配  InitStack(s);  for(p=str;*p;p+)      if(*p='('|*p=''|*p='') push(s,*p);    else if(*p=')'|*p=''|*p='')          if(StackEmpty(s) return ERROR;      pop(s,c);      if(*p=')'&&c!='(') return ERROR;      if(*p=''&&c!='') return ERROR;      if(*p=''&&c!='') return ERROR; /必須與當前棧頂括號匹配      /for  if(!StackEmpty(s) return ERROR;  return OK;/AllBrackets_Test 3.20 typedef struct . int x; int y; coordinate;void Repaint_Color(int gmn,int i,int j,int color)/把點(i,j)相鄰區(qū)域的顏色置換為color  old=gij;  InitQueue(Q);  EnQueue(Q,I,j);  while(!QueueEmpty(Q)      DeQueue(Q,a); x=a.x;y=a.y;    if(x>1)      if(gx-1y=old)              gx-1y=color;        EnQueue(Q,x-1,y); /修改左鄰點的顏色          if(y>1)      if(gxy-1=old)              gxy-1=color;        EnQueue(Q,x,y-1); /修改上鄰點的顏色          if(x<m)      if(gx+1y=old)              gx+1y=color;        EnQueue(Q,x+1,y); /修改右鄰點的顏色          if(y<n)      if(gxy+1=old)              gxy+1=color;        EnQueue(Q,x,y+1); /修改下鄰點的顏色        /while/Repaint_Color分析:本算法采用了類似于圖的廣度優(yōu)先遍歷的思想,用兩個隊列保存相鄰同色點的橫坐標和縱坐標.遞歸形式的算法該怎么寫呢? 3.21 void NiBoLan(char *str,char *new)/把中綴表達式str轉(zhuǎn)換成逆波蘭式new  p=str;q=new; /為方便起見,設(shè)str的兩端都加上了優(yōu)先級最低的特殊符號  InitStack(s); /s為運算符棧  while(*p)      if(*p是字母) *q+=*p; /直接輸出    else          c=gettop(s);      if(*p優(yōu)先級比c高) push(s,*p);      else              while(gettop(s)優(yōu)先級不比*p低)                  pop(s,c);*(q+)=c;        /while        push(s,*p); /運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則      /else    /else    p+;  /while/NiBoLan /參見編譯原理教材 3.22 int GetValue_NiBoLan(char *str)/對逆波蘭式求值  p=str;InitStack(s); /s為操作數(shù)棧  while(*p)      if(*p是數(shù)) push(s,*p);    else          pop(s,a);pop(s,b);      r=compute(b,*p,a); /假設(shè)compute為執(zhí)行雙目運算的過程      push(s,r);    /else    p+;  /while  pop(s,r);return r;/GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype &new)/把逆波蘭表達式str轉(zhuǎn)換為波蘭式new  p=str;Initstack(s); /s的元素為stringtype類型  while(*p)      if(*p為字母) push(s,*p);    else          if(StackEmpty(s) return ERROR;      pop(s,a);      if(StackEmpty(s) return ERROR;      pop(s,b);      c=link(link(*p,b),a);      push(s,c);    /else    p+;  /while  pop(s,new);  if(!StackEmpty(s) return ERROR;  return OK;/NiBoLan_to_BoLan分析:基本思想見書后注釋.本題中暫不考慮串的具體操作的實現(xiàn),而將其看作一種抽象數(shù)據(jù)類型stringtype,對其可以進行連接操作:c=link(a,b). 3.24 Status g(int m,int n,int &s)/求遞歸函數(shù)g的值s  if(m=0&&n>=0) s=0;  else if(m>0&&n>=0) s=n+g(m-1,2*n);  else return ERROR;  return OK;/g 3.25 Status F_recursive(int n,int &s)/遞歸算法  if(n<0) return ERROR;  if(n=0) s=n+1;  else      F_recurve(n/2,r);    s=n*r;    return OK;/F_recursive Status F_nonrecursive(int n,int s)/非遞歸算法  if(n<0) return ERROR;  if(n=0) s=n+1;  else      InitStack(s); /s的元素類型為struct int a;int b;    while(n!=0)          a=n;b=n/2;      push(s,a,b);      n=b;    /while    s=1;    while(!StackEmpty(s)          pop(s,t);      s*=t.a;    /while    return OK;/F_nonrecursive 3.26 float Sqrt