数据结构题集(C语言版)算法设计题答案.pdf

第一章绪论1.16v 0 i d pr i n t_deSce n d i n g(i nt x,i n t y,i nt z)/按从大到小顺序输出式低数(Sca n f(%d,%d,%d,&x,&y,&z);if(x y)x y;为表示交换地双目运算符,以吓同 i f(yz;i f(x y)xy；冒泡排序 pr i ntf(%d%d%d,x,y,z);/pr i n t_deSce nd i ng1.17Sta tUSf i b(i nt k,i nt m,i nt&f)求K阶斐波那契序列地第m项地值f(i n t tempd;i f(K21|m0)retur n ERROR;i f(ml)f=0;elSe i f(m=K-l)f=l;elSe(f Or(i=0;i=2;i+)temp i=0;te mp k 初始化f Or(i=K;i=m;i+)求出序列第K至第m(固元素地值(Sum=0;f Or(j=i 玲K；j i;j+)Sum+=tempD;temp i=Sum;f=tempm;)retur n OK;/f i b分析:通过保存已经计算出来地结果，此方法地时间复杂度仅为O(m。).如果采用递归编程(大多数都会首先 想到递归方法)，则时间复杂度将高达七亿人!).1.18typedef-Structchar*SpOrt;e n ummale,f emale ge n der;c ha r-Sc h-O-OI n a me;校名为 A-b-C 一-或E，char*reSult;i nt ScOre;reSulttype;typedef-Structi nt maleScOre;i ntf emaleScOre;i nttOtalScOre;-Sc-Oretype;v 0 i d SUmma ry(re SUltty p e re)求各校地男的总分合团体总分，假设结果已经储存在re SUlt口数组仲(-Sc-Oretype-Sc-Ore;i=0;wh i le(re-Sult i -Sp-Ort!=N ULL)(Sw i tch(reSult i SchOOI n ame)(caSe A:-Sc-Ore 0.t-Otal-Sc-Ore+=re-Sult i -Sc-Ore;i f(reSult i.ge n der=0)ScOre 0.maleScOre+=reSiilt i.ScOre;el-Se-Sc-Ore 0.f emale-Sc-Ore+=re-Sult i-Sc-0re;breaK；caSe b:-Sc-Ore.t-Otal-Sc-Ore+=re-Sult i -Sc-Ore;i f(reSult i.ge n d e r=0)ScO re.m a I eScOre+=reSu 11 i ScOre;el-Se-Sc-Ore.f emale-Sc-Ore+=re-Sult i.ScOre;break；)i+;)f Or(i=0;i 5;i+)(pr i n tf(-Sch-O-OI%d:n ,i);pr i n tf(TOtal ScOre Of male:%d n ,ScOre i.maleScOre);pr i ntf(TOtal ScOre Of f emale:%d n ,ScOre i.f emaleScOre);pr i n tf(TOtal ScOre Of all:%d n n ,ScOre i.tOtalScOre);)/Summary1.19Sta tiiS a|g0119(i nt a A RRS i ZE)求 i!*2A i 序列地值且不超过 ma x i nt(la-St=l;f Or(i=1;i l=la-St*2*i;i f(a i-l/la-St)!=(2*i)reurn-Ov ERFL-OW;laSt=a i-1;return OK;/alg-O119分析:当某一项地结果超过了 ma x i nt时,4也除以前面一项地商会发生异常.1.20v O i d pOly v alue()f lOat ad;f lOat*p=a;pr i ntf(i n put n limber Of termS:);Sca n n);pr i n tf(i n put the%d cOef f i c i e n tS f rOm aO t0 a%d:n ,n,n)；f Or(i=0;i=n;i+)Sca n f(%f ,p+);pr i ntf(i n put v alue 0f x：)；Sca n x)；p=a；xp=l；-Sum=0;/xp 用于存放 x 地 i 次方f Or(i=0;i=n;i+)Siim+=x p*(*p+)；x p*=x；pr i n tf(v aliie/p-Olyv aluei-S:%f rSum);第二章线性表2.10Sta tuS De Ie te K(SqL i St&a,i nt i,i nt k)删 除线性表a仲第i彳固元素起地k彳固元素(i f(i 1|kae n gth)retiir n i N FEA-S i bLE;f 0r(c0u n t=l;i+cOu n t-lK；cOu n t+)注意循环结束地条件a.elem i+cOu n t-l=a.elem i+cOu n t+K-l;a.Ie n gth-=K；return 0K;/DeleteK2.11StatiiS i nSert_SqL i St(SqL i St&v a,i nt x)把 x 插入递增有序表 v a 仲(i f(v a.Ie n gth+lv a.I i StS i ze)retiir n ERROR;v a.Ie n gth+;f Or(i=v a.Ie n gth玲 1;v a.elem i x&i=0;i 玲玲)v a.elem i+1=v a.elem i;v a.elem i+1=x；return OK;/i nSert_SqL i St2.12i nt L i StC Omp(SqL i St A广SqL i St b)比较字符表A合b，并用返回值表示结果，值为正，表示 A b；值为负，表示A b.elem i;retur n 0;/L i StCOmp2.13LN Ode*LOC a te(L i n k L i St L,i n t x)链表上地元素查找，返回指针(f Or(p=l 玲n e xt;p&p 玲data!=x；p=p 玲next);retur n p；/L-Ocate2.14i nt Le n gth(L i n k L i St L)求链表地长度(f Or(K=0,p=L;p-n e xt;p=p-n ext,K+);retur n k;/Le ngth2.15v O i d L i StCO n cat(L i n kL i St ha,L i n kL i St hb,L i n k L i St&hc)把链表 hb 接在 ha 后面 形成链表he(hc=ha;p=ha;wh i le(p-next)p=p-next;p-n e xt=hb；/L i-StC-O n cat2.16见书后答案.2.17sta tu-S i nSe rt(L i n k L i-St&L,i nt i,i nt b)在无头结黑占链表L地第i彳固元素之前插入元 素b(p=L;q=(L i hkL i-St*)mall-Oc(S i ze-Of(LN-Ode);q.data=b；i f(i=1)(q.n e xt=p;L=q;插入在链表头部 el-Se(wh i le(-i 1)p=p玲nex t;q-*n e xt=p-n e x t；p-*n e xt=q;插入在第 i 他I元素地位置)/i n Sert2.18Sta tu-S De le te(L i hk L i-St&L,i nt i)在无头结果占链表L仲删除第i彳固元素(i f(i=1)L=L-*ne x t;删除第一值|元素 elSeP=L;wh i le(-i 1)p=p-next;p-*ne xt=p-*ne x tf ne x t;册 l除第 i 他 I元素)/Delete2.19StatuS Delete_betwee n(L i n kI i St&L,i n t m i n k,i n t ma xk)删除元素递增排列地链表 L 仲值 大于m i iik且小于ma xk地所有元素(P=L;wh i le(p n e xt-datane x t;/p 是最后一彳固不大于 m i nK 地元素i f(p-ne x t)如果还有比m i n k更大地元素(q=p-nex t;wh i le(q玲datane xt=q;/Delete_betwee n2.20Sta til-S De Ie te _E qua l(L i nK I i St&L)删除元素递增排列地链表L仲所有值相同地元素(p=l_f ne xt;q=p f ne x t;/p,q 指向相邻两元素wh i le(p next)(i f(p-data!=q-data)(p=P-ne xt;q=p-*n e x t;当相邻两元素不相等时,p,q都向后推一步el-Se(wh i le(q-data=p-data)(f ree(q);q=q-ne xt;p-*ne xt=q；p=q;q=p ne x t;当相邻元素相等时删除多余元素elSe/wh i Ie/Delete_Equal2.21v o i d re v e rSe(SqL i St&A)顺序表地就地逆置(f Or(i=l,j=A.length;i)A.elem i A.elemj;/re v erSe2.22V 0 i d L i n k L i-St_re v e r-Se(L i n k I i-St&L)链表地就地逆置;为简化算法,假设表长大于2(p=-n e xt;q=p-n e xt;S=q玲n e xt;p玲n e xt=N ULL;wh i le(S-nex t)(q-n e xt=p;p=q;q=S;S=-S-*ne x t;把L地元素逐他I插入新表表头 q-n e x t=p;S玲n e x t=q;L玲n e x t=S;/L i n kL i St_re v erSe分析:本算法地思想是，逐彳固地把L地当前元素q插入新地链表头部,p为新表表头.2.23v 0 i d mergel(L i n kL i St&A,L i n kL i St&b,L i n k L i St&C)把链表 A 合 b 合并为 C,A 合 b地元素间隔排列，且使用原存储空间(p=A-n e x t;q=b-n e x t;C=A;wh i le(p&q)(S=p f ne x t；p f ne xt=q;将 b 地元素插入 i f(S)(t=qf ne x t;qf ne xt=S;如A 非空，将A 地元素插入p=-S;q=t;/wh i Ie/mergel2.24v 0 i d re v erSe_merge(L i n kL i St&A,L i iik L i St&b,L i n k L i St&C)把元素递增排列地链表 A合b合并为C,且C仲元素递减排列，使用原空间(pa=A-n e x t;pb=b-n e x t;pre=N ULL;/p a 合 pb 分别指向 A,b 地当前元素 wh i le(pa|pb)(i f(pa-datadata|!pb)(pc=pa;q=pa玲next;pa玲next=pre;pa=q;将 A 地元素插入新表 el-Se(pc=pb；q=pb-next;pb-next=pre;pb=q;将 b 地元素插入新表 pre=pc;)C=A;A-*ne xt=p c;构造新表头/re v erSe_merge分析:本算法地思想是，按从小到大地顺序依次把A合b地元素插入新表地头部p c处，最后处理A或 b地剩余元素.2.25v0 i d SqL i-St_ i n ter-Sect(-SqL i-St A,SqL i-St b,SqL i-St&C)求元素递增排列地线性表 A 合 b地元素地交集并存入C仲(i=l;j=l；K=O;wh i le(A.elem i&b.elemj)(i f(A.elem i b.elemj)j+;i f(A.elem i=b.elemj)(C.e le m+K=A.e le m i;当发现了一值I在A,b仲都存在地元素，i+；j+；就添加到C仲/wh i leSqL i St_ i n terSect2.26v 0 i d L i n kL i St_ i n terSect(L i n kL i St A,L i n k L i St b,L i n k L i St&C)在链表结构上重 做上题(p=A-n e x t;q=b-nex t;pc=(LN Ode*)mallOc(S i ze-0f(LN-0de);wh i le(p&q)(i f(p-datadata)p=p-next;elSe i f(p dataq-data)q=q 玲nex t;el-Se(S=(LN Ode*)mallOc(S i ze-0f(LN-0de);S 玲data=p 玲data;pc玲n ext=S;pc=S;p=p 玲n e xt;q=q 玲nex t;)/wh i leC=pc;/L i n kL i St_ i n terSect2.27v-0 i d SqL i-St_ i n ter-Sect_True(SqL i-St&A,SqL i-St b)求元素递增排列地线性表 A 合 b 地 元素地交集并存回A仲(i=l;j=l；K=O;wh i le(A.elem i&b.elemj)i f(A.elem i b.elemj)j+;elSe i f(A.elem i!=A.elemK)(A.e Ie m+K=A.e Ie m i;当发现了 f l可在A,b仲都存在地元素 i+；j+；且C仲没有，就添加到C仲/wh i Iewh i le(A.elemK)A.elemK+=O;SqL i St_ i n terSect_True 2.28v 0 i d L i n kL i St_ i n terSect_True(L i n kL i St&A,L i n k L i St b)在链表结构上重做上题(p=A-n e x t;q=b-n e x t;pc=A;wh i le(p&q)(i f(p-datadata)p=p-next;elSe i f(p-dataq-data)q=q 玲nex t;elSe i f(p-data!=pc-data)(pc=pc-nex t;pc 玲data=p 玲data;p=p 玲n e xt;q=q 玲nex t;)/wh i Ie/L i n kL i St_ i n terSect_True2.29v 0 i d SqL i St_ i n terSect_Delete(SqL i St&A,SqL i St b,SqL i St C)(i=O;j=O；K=0;m=0;/i指示A仲元素原来地位置,m为移动后地位置 wh i le(i A.le n gth&j b.le n gth&KC.le n gth)(i f(b.elemj C.elemK)k+;el-Se(Sa me=b.e Ie mj；找至U 7 相同元素 Sa mewh i le(b.elemj=Same)j+;wh i le(C.elemK=Same)k+;/j,K 后移到新地元素 wh i le(i A.le n gth&A.elem i Same)A.elemm+=A.elem i+;需保留地元素移动到新位置 wh i le(i A.le n gth&A.elem i=Same)i+;跳过相同地元素)/wh i Iewh i le(i n e x t;q=C-n e x t;r=A-nex t;wh i le(p&q&r)(i f(p-datadata)p=p-next;elSe i f(p dataq-data)q=q 玲nex t;elSe(u=p-da ta;确定待删除元素uwh i le(r玲nex t玲datavii)r=r3nex t;/确定最后一值I小于u地元素指针ri f(n e x t-data=u)(S=r-nex t;wh i le(S-data=u)(t=s；S=Sf ne Xt;f re e(t);确定第一低|大于U地元素指针S/wh i Ier-n e xt=S;册除r合-S之间地元素 ifwh i le(p-data=u)p=p-nex t;wh i le(q-data=u)q=q-nex t;elSe/wh i Ie/L i n kL i St_ i n terSect_Delete2.31Sta tu-S De Ie te _P re(C i LN-Ode*S)删除单循环链表仲结黑占S地直接前驱(P=S；wh i le(p-next玲next!=S)p=p玲nex t;找至 U S 地前驱地前驱 pp-n e xt=S;return OK;/Delete_Pre2.32StatuS DuLN Ode_Pre(DuL i n kL i St&L)完成双向循环链表结黑占地p re 域(f Or(p=L;!p-n e x t 玲pre;p=p-nex t)p-n e x t-pre=p;return OK;/DuLN-Ode_Pre2.33-Statu-S L i n kL i-St_D i v i de(L i n kL i-St&L,C i L i-St&A,C i L i-St&b,C i L i-St&C)把单链表 L 地 元素按类型分为式值I循环链表C i L i-St为带头结黠地单循环链表类型.(S=L玲nex t;A=(C i L i-St*)mall-Oc(S i ze-Of(C i LN Ode);p=A;b=(C i L i St*)mallOc(S i ze-Of(C i LN-Ode);q=b;C=(C i L i-St*)mall-Oc(S i ze-Of(C i LN-Ode);r=C;建立头结黑占 wh i le(-S)(i f(i Salphabet(S-data)(p-next=S;p=S;elSe i f(i Sd i g i t(S玲data)(q玲n ext=S;q=S;el-Se(r-ne xt=S;r=S;/wh i lepf ne x t=A;qf ne xt=b;r ne x t=C;完成循环链表/L i n kL i St_D i v i de2.34 v 0 i dPr i nt_x-OrL i n KedL i-St(x-OrL i n KedL i St L)从左向右输出异或链表地元素值(p=L.lef t;pre=N ULL;wh i le(p)(pr i n tf(%d,p data);q=x-OrP(p-LRPtr,pre);p re=p；p=q;任何一(固结黠地LRPtr域值与其左结黑占指针进行异或运算即的到其右结黠指针/Pr i nt_x OrL i n KedL i St 2.35-Statu-Si nSert_xOrL i n KedL i St(xOrL i n KedL i St&L,i nt x,i nt i)在异或链表 L 地第 i 彳固元素 前插入元素x(p=L.lef t;pre=N ULL;r=(x0rN 0de*)mall0c(S i zeOf(x0rN 0de);i玲data=x；i f(i=1)当插入黠在最左边地情况p-LRPtr=x-OrP(p.LRPtr,r);r-LRPtr=p;L.lef t=r;return 0K;)j=l;q=p-*LRP tr;当插入黑占在仲间地情况wh i le(+j LRPtr,pre);pre=p;p=q;/wh i Ie 在p,q两结黑占之间插入i f(!q)re tiir n i N FE A S i b LE;/i 不可以超过表长pLRPtr=x-OrP(x-OrP(p LRPtr,q),r);q-LRPtr=x OrP(x OrP(q-LRPtr,p),r);r-LRP tr=x-OrP(p,q);修改指针 return 0K;/i nSert_xOrL i n KedL i St2.36StatiiS Delete_xOrL i n KedL i St(x Orl i n KedL i St&L,i nt i)删除异或链表 L 地第 i 彳固元素(p=L.lef t;pre=N ULL;i f(i=1)删除最左结黠地情况(q=p-LRPtr;q-LRPtr=xOrP(q-LRPtr,p);L.lef t=q;f ree(p);return 0K;)j=l;q=p-LRPtr;wh i le(+j LRPtr,pre);pre=p;p=q;/wh ile 找到待删结黠qi f(!q)re ttir n i N FE A i b LE;/i 不可以超过表长i f(L.r i ght=q)/q为最右结黑占地情况(p-LRPtr=x-OrP(p-LRPtr,q);L.r i ght=p;f ree(q);return 0K;)r=x-OrP(q-LRP tr,p);/q为仲间结黠地情况，此时p,r分别为其左右结黠 p-LRPtr=x OrP(x OrP(p-LRPtr,q),r);r玲LRPtr=x-OrP(x OrP(r-LRPtr,q),p);/修改指针 f ree(q);return 0K;/Delete_xOrL i n KedL i St2.37v 0 i d-0E Re f-Orm(DUL i n k e dL i-St&L)按1,3,5,.4,2地顺序重排双向循环链表L仲地所有结黑占(p=L.nex t;wh i le(p玲n e xt!=L&p玲n e xt-n e xt!=L)(p-ne x t=p-ne x t-nex t;p=p-nex t;此时p指向最后一俯I奇数结黠i f(p玲n e xt=L)p-ne xt=L pre-pre;elSe p玲n e xt=l玲pre;p=p-*ne x t;此时p指向最后一值I偶数结黑占wh i le(p-pre-pre!=L)(p-n e x t=p-pre-pre;p=p-nex t;)p f ne xt=L;按题目要求调整了 n e x t链地结构,此时-p re链仍为原状f Or(p=L;p-n e xt!=L;p=p n e xt)p-n e xt-pre=p;L-*p re=p;调整p re链地结构，同2.32方法OERef Orm分析:ne x t链合p re链地调整只能分开进行.如同时进行调整地话，必须使用堆栈保存偶数结黑占地指针，否 则将会破坏链表结构，造成结黠丢失.2.38DuLN-Ode*L-Ocate_DuL i-St(DuL i n KedL i St&L,i nt x)带 f re q 域地双向循环链表上地查找(p=L.nex t;wh i le(p.data!=x&p!=L)p=p 玲nex t;i f(p=L)re turn N ULL;/没找至p-f req+;q=p-pre;wh i le(q玲f reqf req)q=qpre;查找插入位置i f(q!=p-pre)(p-pre-n e xt=p-n e xt;p-n e xt-pre=p-pre;q-ne x t-pre=p;p-ne x t=q-nex t;q-*ne xt=p；p-p re=q;调整位置retur n p;/L-Ocate_DuL i-St2.39f lOat get v alue_SqPOly(SqPOly P,i nt x 0)求升哥顺序存储地稀疏多项式地值POlyTerm*q;x p=l;q=P.data;Sum=O;e x=0;wh i le(q玲cOef)(wh i le(e x e x p)x p*=x 0;Siim+=q-cOef*x p；q+;)retur n Sum;/get v alue_SqPOly2.40v-O i d-Subtract_SqPOly(SqP-Oly P l,SqP-Oly P 2,SqP-Oly&P 3)求稀疏多项式 P 1减 P 2 地差式P 3(P-OlyTerm*p,*q,*r;C re a te _-SqP-Oly(P 3);建立空多项式 P3p=Pl.data;q=P2.data;r=P3.data;wh i le(p-cOef&q-cOef)(i f(p-e x pe x p)(r-cOef=p-cOef;r-e x p=p-e x p；p+;r+;)elSe i f(p-e x pe x p)(r-cOef=f q-cOef;r-e x p=q-e x p；q+;r+;)el-Se(i f(p-*c Oe f f q-*c-Oe f)!=0)只有同次项相减不为零时才需要存入P 3仲(I玲 cOef=p玲cOef 玲 q 玲cOef;玲e x p=p-e x p;r+;ifP+；q+；/el-Se/wh i lewh i le(p-*c Oe f)处理P 1或P 2地剩余项(r-cOef=p cOef;r-e x p=p-e x p；p+；r+;wh i le(q玲cOef)(r-cOef=-q 玲 cOef;r-e x p=q-e x p；q+;r+;)/-Subtract_-SqP-Oly2.41v 0 i d Q i uDaO_L i n KedPOly(L i n KedPOly&L)对有头结黑占循环链表结构存储地稀疏多项式L求导(p=L 玲nex t;i f(!p-data.e x p)(l_f ne xt=p-ne x t；p=p-ne x t;跳过常数项)wh i le(p!=L)(p-da ta.c 0e f*=p-*da ta.e x p-*；对每一项求导 p=p-nex t;Q i uDa-O_L i n KedP-Oly2.42v 0 i d D i v i de_L i n KedPOly(L i n KedPOly&L,&A,&b)把循环链表存储地稀疏多项式L拆成只含 奇次项地A合只含偶次项地b(p=L 玲nex t;A=(P-OlyN-Ode*)mall-Oc(S i ze-0f(P-0lyN-0de);b=(P-OlyN-Ode*)mall-Oc(S i ze-0f(P-0lyN-0de);pa=A;pb=b;wh i le(p!=L)(i f(p-data.e x p!=2*(p-data.e x p/2)(pa-n e xt=p;pa=p;el-Se(pb-n e x t=p;pb=p;)p=p-nex t;/wh i Iepa-n e x t=A;pb-n e x t=b;/D i v i de_L i n KedPOly第立章栈与队列3.15typedef-StriictElemtype*baSe2;Elemtype*t0p2;b D-sta c k ty p e;双向栈类型-Statu-S i n i t_-StacK(bD-StacKtype&tw-S,i nt m)初始化一彳固大山为 m 地双向栈 tw-S(twS.baSe0=(Elemtype*)mallOc(S i zeOf(Elemtype);tw-S.ba-Sel=tw-S.ba-SeO+m;tw-S.t-Op0=tw-S.ba-Se0;tw-S.t-Opl=tw-S.ba-Sel;return 0K;/i n i t_StacKStatuS puSh(bDStacKtype&twS,i nt i,E Ie mty p e x)/x 入栈，i=0 表示低端栈，i=1 表示高端 栈(i f(tw-S.t-Op0tw-S.t-Opl)retur n-O v E RFLOW;注意此时地栈满条件i f(i=0)*twS.tOp0+=x；el-Se i f(i=1)*tw-S.t-Opl-=x；elSe return ERROR;return OK;/pu-ShStatiiS pOp(bDStacKtype&twS,i nt i,E Ie mty p e&x)/x 出栈，i=0 表示低端栈,i=1 表示高端 栈(i f(i=0)(i f(twS.tOp0=twS.baSe0)return Ov ERFLOW;x=*-t wS.tO p 0;)elSe i f(i=1)(i f(twS.tOpl=twS.baSel)return Ov ERFLOW;x=*+twS.tOpl;el Se return ERROR;return OK;pOp3.16v o i d Tra i n_a rra nge(c ha r*tra i n)这里用字符串tra i n表示火车,H表示硬席尸S表示软 席p=tra i n;q=tra i n;i n i tStacK(S);wh i le(*p)i f(*p=H)p U-Sh(-S,*p);把W存入栈仲e l-Se*(q+止*p;把S，调到前部 P+；wh i le(!StacKEmpty(S)(pOp(-S,c);*(q+)=C；把H接在后部/Tra i n_arra n ge3.17i nt i SRe v e rSe()判断输入地字符串仲&前合&后部分是否为逆串，是则返回1,否则返回0(i n i tStacK(S);wh i le(e=getchar()!=&)puSh(S,e);wh i le(e=getchar()!=)(i f(StacKEmpty(S)return 0;pOp(S,c);i f(e!=c)retur n 0;)i f(!StacKEmpty(-S)return 0;return 1;/i SRe v erSe3.18-Sta tu-S b ra c k e t_Te-St(c ha r*Str)判别表达式仲小括号是否匹配(cOu nt=0;f Or(p=Str;*p;p+)(i f(*p=()cOu nt+;el-Se if(*p=)cOij nt玲玲；i f(cOu nt1)i f(9x ly=Old)(g x-ly=c-OIOr;E nQue ue(Q,x-l,y);修改左邻黑占地颜色)i f(yDi f(gxy玲l=Old)(gxy l=cOIOr;E nQue ue(Q,x,y 修改上邻黑占地颜色)i f(xm)i f(9x+ly=Old)(g x+ly=cOIOr;E nQue ue(Q,x+l,y);修改右邻黠地颜色)i f(y=0)S=0;elSe i f(m0&n=0)S=n+g(m-l,2*n);el Se return ERROR;return 0K;)/93.25Sta tuS F_re c urS i ve(i nt n,i nt&S)递归算法(i f(n0)return ERROR;i f(n=0)S=n+1;el-SeF_recur v e(n/2,r);-S=n*r;)return 0K;/F_recur-S i v eSta tUS F_ n 0 n re C UrS i v e(i n t n,int S)非递归算法(i f(n0)return ERROR;i f(n=0)S=n+1;el-Se(i n i tSta c k(S);S 地元素类型为 Striic t i nt a;i nt b；wh i le(n!=0)(a=n；b=n/2;pu-Sh(-S,a,b);n=b；/wh i Ie-S=1;wh i le(!StacKEmpty(S)(pOp(S,t);S*=t.a;/wh i Iereturn 0K;/F_ n0 n recurs i v e3.26f l-Oat-Sqrt_recur-S i v e(f l-Oat A,f l-Oat p,f l-Oat e)求平方根地递归算法(i f(abS(pA2 A)A)=e)p=(p+A/p)/2;retiir n p;/Sqrt_ nO n recurS i v e3.27这一题地所有算法以及栈地变化过程请参见数据结构(p a Sc a I版)，做者不再详细写出.3.28vo i d i n itC i Que ue(C i Que ue&Q)初始化循环链表表示地队列Q(Q=(C i LN Ode*)mallOc(S i ze-Of(C i LN-Ode);Q玲 n e xt=Q;/i n i tC i QueueVo id E nC i QUe Ue(C i QUe Ue&Q,i n t x)把元素x插入循环链表表示地队列Q,Q指向队尾 元素,Q-ne x t指向头结黑占,Qf ne x t-*n e x t指向队头元素(p=(C i LN-Ode*)mall-Oc(S i ze-Of(C i LN-Ode)；p-data=x；p-*ne xt=Q-*ne x t;直接把p加在Q地后面Q玲n e xt=p;Q=p;修改尾指针StatuS DeC i Queue(C i Queue&Q,i nt x)从循环链表表示地队列Q头部删除元素x(i f(Q=Q nex t)retur n i N FEAS i bLE;队列已空p=Q 玲n e x t-nex t;x=p-data;Q玲n e x t-n e x t=p 玲nex t;f ree(p);return 0K;/DeC i Queue3.29StatiiS E n CyQueue(CyQueiie&Q,i nt x)带 ta g 域地循环队列入队算法(i f(Q.f rOnt=Q.rear&Q.tag=l)tag 域地值为 0 表示空表示满”return 0v ERFLOW;Q.baSeQ.rear=x；Q.rear=(Q.rear+l)%MA x S i ZE;i f(Q.f rO n t=Q.re a r)Q.ta g=l;队列满/E n CyQueueStatuS DeCyQueue(CyQueue&Q,i nt&x)带 ta g 域地循环队列出队算法(i f(Q.f rO n t=Q.rear&Q.tag=O)return i N FEAS i bLE;Q.f rO n t=(Q.f rO n t+l)%MA x S i ZE;x=Q.baSeQ.f rO n t;i f(Q.f rO n t=Q.re a r)Q.ta g=l;队列空return 0K;/DeCyQueue分析:当循环队列容量较小而队列仲每他I元素占地空间较多时，此种表示方法可以节约较多地存储空间，较有价 值.3.30StatiiS E n CyQueue(CyQueiie&Q,i nt x)带 le n gth 域地循环队列入队算法(i f(Q.le n gth=MA x S i ZE)return Ov ERFLOW;Q.rear=(Q.rear+l)%MA x S i ZE;Q.baSeQ.rear=x；Q.le n gth+;return OK;/E n CyQueueStatuS DeCyQueue(CyQueue&Q,i nt&x)带 Ie n gth 域地循环队列出队算法(i f(Q.le n gth=O)retur n i N FEAS i bLE;head=(Q.rear-Q.le n gth+l)%MA xS i ZE;详见书后注释x=Q.baSehead;Q.le n gth-;/DeCyQueue3.31i nt P a I i ndr-Ome _Te St()判别输入地字符串是否同文序列，是则返回1,否则返回0(i n i tStacK(S);i n i tQueue(Q);wh i le(c=getchar()!=)(PuSh(S