完全針對(duì)南昌航空大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試

1.1解：數(shù)據(jù)足對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理

的符號(hào)的總稱。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。

數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。

數(shù)據(jù)類型是一個(gè)值的集合利定義在這個(gè)值集上的一組操作的總稱。

抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類型的擴(kuò)展。

1.2解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由

具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型

通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)

據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)

現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。

1.3解：

—^(5?)--->(d3)----->(d4)

1.5試畫出與下列程序段等價(jià)的框圖。

(1)product=l;i=l;

while(i<=n){

product*=i;

i++；

}

(2)i=0;

do{

i++；

}while((i!=n)&&(a[i]!=x));

(3)switch{

casex<y:z=y-x;break;

casex=y:z=abs(x*y);break;

default:z=(x-y)/abs(x)*abs(y);

L6解：(l)exit常用于異常錯(cuò)誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。

(2)以函數(shù)的返回值判斷正確與否常用于子程序的測(cè)試，便于實(shí)現(xiàn)程序的局部控制。

(3)用整型函數(shù)進(jìn)行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出錯(cuò)誤類型，便于迅速確定錯(cuò)誤。

1.7解：(1)用scanf和printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎn)是需要對(duì)其進(jìn)行格式

控制，較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會(huì)引起整個(gè)系統(tǒng)的崩潰。

(2)通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。

(3)通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程

序的維護(hù)較為困難。

1.9解：67(lOg2/7)

countslog2n—2

1.11解：2"=10°n=40

H10=1012n=16

則對(duì)于同樣的循環(huán)次數(shù)n,在這個(gè)規(guī)模"第1種算法所花費(fèi)的代價(jià)要大得多。故在這個(gè)規(guī)模下，第

一種算法更適宜。

1.12解：(1)對(duì)⑵錯(cuò)⑶錯(cuò)(4)對(duì)⑸錯(cuò)

1.13解：的增長(zhǎng)趨勢(shì)快。但在n較小的時(shí)候，50"log2〃的值較大。

當(dāng)n〉438時(shí),n2

>50nlog2n

1.14解：(l)g(n)快(2)g(n)快(3)f(n)快⑷f(n)快

1.16解：

intmax3(intx,inty,intz)

(

if(x>y)

if(x>z)returnx;

elsereturnz;

else

if(y>z)returny;

elsereturnz;

)

1.17解：k>0為階數(shù)，n為數(shù)列的第n項(xiàng)

intFibonacci(intk,intn)

(

if(k<l)exit(OVERFLOW);

int*p,x;

p=newint[k+1];

if(!p)exit(OVERFLOW);

inti,j;

for(i=0;i<k+l;i++){

if(i<k-l)p[i]=0;

elsep[i]=l;

)

for(i=k+l;i<n+l;i++){

x=p[0];

for(j=0;j<k;j++)p[j]=p[j+l];

p[k]=2*p[k-l]-x;

)

returnp[k];

}

L18解：

typedefenum{A,B,C,D,E}SchoolName;

typedefenum{Female,Male}SexType;

typedefstruct(

charevent[3];〃項(xiàng)目

SexTypesex;

SchooINameschool;

intscore;

)Component;

typedefstruct{

intMaleSum;〃男團(tuán)總分

intFemaleSum;〃女團(tuán)總分

intTotalSum;〃團(tuán)體總分

}Sum;

SumSumScore(SchoolNamesn,Componenta[],intn)

(

Sumtemp;

temp.MaleSum=0;

temp.FemaleSum=O;

temp.TotalSum=0;

inti;

for(i=0;i<n;i++){

if(a[i].school==sn){

if(a[i].sex=Male)temp.MaleSum+=a[i].score;

if(a[i].sex=Female)temp.FemaleSum+=a[i].score;

}

)

temp.TotalSum=temp.MaleSum+temp.Ferna1eSum;

returntemp;

2.1解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)

點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為

了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。

2.2解：(1)在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素,具體移動(dòng)的元素個(gè)數(shù)與逐

在表中的位置Z、美。

(2)順序表中邏輯上相鄰的元素的物理位置坐足緊鄰。單鏈發(fā)中邏輯上相鄰的元素的物理位置受友

緊鄰。

(3)在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由具前更練點(diǎn)的鋌腐效倒片小。

(4)在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用造插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。

2.3解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行

隨機(jī)存取。

2.4解：

PQRS

L

2)

QRs

⑶

?TT

—

1^—

pQR

⑹

\

!

/

p

2.5解:

----?

P

L-k----->1?3?5?1A

丁

P

~~GZD-CZI]—<zi—￡H-{ZD-□>—￡ZH

p

L—?——?2-----?47——?8A

p

2.6解：a.(4)(1)

b.(7)(11)(8)(4)(1)

c.(5)(12)

d.(9)(1)(6)

2.7解：a.(11)(3)(14)

b.(10)(12)(8)(3)(14)

c.(10)(12)(7)(3)(14)

d.(12)(11)(3)(14)

e.(9)(11)(3)(14)

2.8解:a.(7)(3)(6)(12)

b.(8)(4)(5)(13)

c.(15)(1)(11)(18)

d.(16)(2)(10)(18)

e.(14)(9)(17)

2.9解：(1)如果L的長(zhǎng)度不小于2,將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。

(2)將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表。

2.10解：StatusDeleteK(SqList&a,inti,intk)

〃從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素

〃注意i的編號(hào)從0開始

intj;

if(i<0||i>a.length-11|k<01|k>a.length-i)returnINFEASIBLE;

for(j=0;j<=k;j++)

a.elem[j+i]=a.elem[j+i+k];

a.length=a.length-k;

returnOK;

)

2.11解：

StatusInsertOrderList(SqList&va,ElemTypex)

(

〃在非遞減的順序表va中插入元素x并使其仍成為順序表的算法

inti;

if(va.length==va.listsize)return(OVERFLOW);

for(i二va.length;i>0,x<va.elem[i-l];i--)

va.elem[i]=va.elem[i-l];

va.elem[i]=x;

va.length++;

returnOK;

)

2.12解：StatusCompareOrderList(SqList&A,SqList&B)

(

inti,k,j;

k=A.length>B.length?A.length:B.length;

for(i=0;i<k;i++){

if(A.elem[i]>B.elem[i])j=l;

if(A.elem[i]<B.elem[i])j=T;

}

if(A.length>k)j=l;

if(B.length>k)j=-l;

if(A.length==B.length)j=0;

returnj;

)

2.13解：intLocateElem_L(LinkList&L,ElemTypex)

(

inti=0;

LinkListp=L;

while(p&&p->data!=x){

p=p->next;

i++；

)

if(!p)return0;

elsereturni;

)

2.14解：〃返回單鏈表的長(zhǎng)度

intListLength_L(LinkList&L)

(

inti=0;

LinkListp=L;

if(p)p=p-next;

while(p){

p=p->next;

i++；

)

returni;

)

2.15解:voidMergeList_L(LinkList&ha,LinkList&hb,LinkList&hc)

(

LinkListpa,pb;

pa=ha;

pb=hb;

while(pa->next&&pb->next){

pa=pa->next;

pb=pb->next;

}

if(!pa->next){

hc=hb;

while(pb->next)pb=pb->next;

pb->next=ha->next;

)

else{

he二ha;

while(pa->next)pa=pa->next;

pa->next=hb->next;

)

)

2.16解:StatusDeleteAndInsertSub(LinkList&la,LinkList&lb,inti,intj,intlen)

(

LinkListp,q,s,prev=NULL;

intk=l;

if(i<0||j<0||len<0)returnINFEASIBLE;

//在la表中查找第i個(gè)結(jié)點(diǎn)

P二la；

while(p&&k<i){

prev=p;

p=p->next;

k++;

)

if(!p)returnINFEASIBLE;

//在la表中查找第i+len-1個(gè)結(jié)點(diǎn)

q=P；k=l;

while(q&&k<len){

q=p->next;

k++;

}

if(!q)returnINFEASIBLE;

//完成刪除，注意，i=l的情況需要特殊處理

if(!prev)la=q->next;

elseprev->next=q->next;

//將從la中刪除的結(jié)點(diǎn)插入到lb中

if(j=D{

q->next=lb;

lb=p;

)

else{

s=lb;k=l;

while(s&&k<j-l){

s=s->next;

k++;

)

if(!s)returnINFEASIBLE;

q->next=s->next;

s->next=p;〃完成插入

)

returnOK;

}

2.19解：StatusListl)elete_L(UnkList&L,ElemTypemink,ElemTypemaxk)

LinkListp,q,prev=NULL;

if(mink>maxk)returnERROR;

P二L;

prev=p;

p=p->next;

while(p&&p->data<maxk){

if(p->data<=mink){

prev=p;

p=p->next;

)

else{

prev->next=p->next;

q=P；

p=p->next;

free(q);

)

)

returnOK;

}

2.20解：voidListDelete_LSameNode(LinkList&L)

(

LinkListp,q,prev;

P=L;

prev=p;

p=p->next;

while(p){

prev=p;

p=p->next;

if(p&&p->data-prev->data){

prev->next=p->next;

q=P；

p=p->next;

free(q);

)

}

)

2.21解：//順序表的逆置

StatusListOppose_Sq(SqList&L)

(

inti;

ElemTypex;

for(i=0;i<L.length/2;i++){

x二L.elem[i];

L.elem[i]=L.elem[L.length-l-i];

L.elem[Llength-l-i]=x;

)

returnOK;

)

2.22試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。

解：

//帶頭結(jié)點(diǎn)的單鏈表的逆置

StatusListOppose_L(LinkList&L)

(

LinkListp,q;

P二L;

p=p->next;

L->next=NULL;

while(p){

q二P；

p=p->next;

q->next=L->next;

L->next=q;

}

returnOK;

)

2.23解;

//將合并后的結(jié)果放在C表中，并刪除B表

StatusListMergeL(LinkList&A,LinkList&B,LinkList&C)

(

LinkListpa,pb,qa,qb;

pa=A->next;

pb=B->next;

OA;

while(pa&&pb){

qa=pa;qb=pb;

pa=pa->next;pb=pb->next;

qb->next=qa->next;

qa->next=qb;

)

if(!pa)qb->next=pb;

pb=B;

free(pb);

returnOK;

)

2.31解：

//在單循環(huán)鏈表S中刪除S的前驅(qū)結(jié)點(diǎn)

StatusListDelete_CL(LinkList&S)

LinkListp,q;

if(S==S->next)returnERROR;

q二S;

p=S->next;

while(p->next!=S){

q=P；

p=p->next;

)

q->next=p->next;

free(p);

returnOK;

1

2.32解：

//建立一個(gè)空的循環(huán)鏈表

StatusInitList_DL(DuLinkList&L)

(

L=(DuLinkList)malloc(sizeof(DuLNode));

if(!L)exit(OVERFLOW);

L->pre=NULL;

L->next=L;

returnOK;

)

//向循環(huán)鏈表中插入個(gè)結(jié)點(diǎn)

StatusListInsert_DL(DuLinkList&L,ElemTypee)

(

DuLinkListp;

p=(DuLinkList)malloc(sizeof(DuLNode));

if(!p)returnERROR;

p->data=e;

p->next=L->next;

L->next=p;

returnOK;

)

//將單循環(huán)鏈表改成雙向鏈表

StatusListCirToDu(DuLinkList&L)

(

DuUnkListp,q;

q=L;

p=L->next;

while(p!=L){

p->pre=q;

q二P；

p=p->next;

)

if(p==L)p->pre=q;

returnOK;

)

2.33解：

//將單鏈表L劃分成3個(gè)單循環(huán)鏈表

StatusListDivideInto3CL(LinkList&L,LinkList&sl,LinkList&s2,LinkList&s3)

(

LinkListp,q,ptl,pt2,pt3;

p=L->next;

ptl=sl;

pt2=s2;

pt3=s3;

while(p){

if(p->data>=,0?&&p->data<-9,){

q二P；

p=p->next;

q->next=pt1->next;

ptl->next=q;

ptl=ptl->next:

)

else

if((p->data>=,A*&&p->data<=,Z*)I|

(p->data>=，a&&p->data<=，z')){

q=P；

p=p->next;

q->next=pt2->next;

pt2->next=q;

pt2=pt2->next;

}

else{

q=P；

p=p->next;

q->next=pt3->next;

pt3->next=q;

pt3=pt3->next;

)

)

q=L;

free(q);

returnOK;

)

2.39解：typedefstruct{

intcoef;

intexp;

}PolyTerm;

typedefstruct{

PolyTerm*data;

intlast;

}SqPoly;

//建立一個(gè)多項(xiàng)式

StatusPolylnit(SqPoly&L)

(

inti;

PolyTerm*p;

cout<<〃請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù):〃;

cin?L.last;

L.data=(PolyTerm*)malloc(L.last*sizeof(PolyTerm));

if(!L.data)returnERROR;

p=L.data;

for(i=0;i<L.last;i++){

cout<<”請(qǐng)輸入系數(shù):";

cin?p->coef:

coutG”請(qǐng)輸入指數(shù):〃；

cin?p->exp;

P++；

)

returnOK;

)

//求多項(xiàng)式的值

doublePolySum(SqPoly&L,doublexO)

(

doublePn,x;

inti,j;

PolyTerm*p;

p=L.data;

for(i=0,Pn=0;i<L.last;i++,p++){

for(j=0,x=l;j<p->exp;j++)x=x*x0;

Pn=Pn+p->coef*x;

}

returnPn;

)

2.40解：

//求兩多項(xiàng)式的差

StatusPolyMinus(SqPoly&L,SqPoly&L1,SqPoly&L2)

PolyTerm*p,*pl,*p2;

p=L.data;

pl=Ll.data;

p2=L2.data;

inti=0,j=0,k=0;

while(i<Ll.last&&j<L2.last){

if(pl->exp<p2->exp){

p->coef=pl->coef;

p->exp=pl->exp;

p++;k++;

pl++；i++;

)

else

if(pl->exp>p2->exp){

p->coef=-p2->coef;

p->exp=p2->exp;

p++;k++；

p2++;j++;

}

else{

if(pl->coef!=p2->coef)(

p->coef=(pl->coef)-(p2->coef);

p->exp=pl->exp;

p++;k++;

)

P1++；p2++;

i++；j++；

)

}

if(i<Ll.last)

while(i<Ll.last){

p->coef=pl->coef;

p->exp=pl->exp;

p++;k++;

pl++;i++;

)

if(j<L2.last)

while(j<L2.last){

p->coef=-p2->coef;

p->exp=p2->exp;

p++;k++;

p2++;j++;

)

L.last=k;

returnOK;

)

2.41解：

StatusPolyDifferential(LinkedPoly&L)

(

LinkedPolyp,q,pt;

q二L；

p=L->next;

while(p!=L){

if(p->data.exp==0){

pt二P；

p=p->next;

q->next=p;

free(pt);

)

else(

p->data.coef=p->data.coef*p->data.exp;

p->data.exp—;

q二P；

p=p->next;

}

)

returnOK;

)

2.42解：

//將單鏈表L劃分成2個(gè)單循環(huán)鏈表

StatusListDivideInto2CL(LinkedPoly&L,LinkedPoly&L1)

(

LinkedPolyp,pl,q,pt;

q二L;

p=L->next;

P1=L1;

while(p!=L){

if(p->data.exp%2==0){

Pt二P；

p=p->next;

q->next=p;

pt->next=pl->next;

pl->next=pt;

pl=pl->next;

}

else{

q二P；

p=p->next;

returnOK;

）

3.1解：⑴123231321213132

（2）可以得到135426的出站序列，但不能得到435612的出站序列。因?yàn)?356出站說明12已經(jīng)在棧

中，1不可能先于2出棧。

3.2解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線

性表。

3.3解：stack

3.4解：（1）棧中的數(shù)據(jù)元素逆置（2）如果棧中存在元素e,將其從棧中清除

3.7按照四則運(yùn)算加、減、乘、除和寤運(yùn)算（t）優(yōu)先關(guān)系的慣例，并仿照教科書3.2節(jié)例3-2的格式，畫

出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：

A-BXC/D+EtF

解：BC=GG/D=HA-H=IE*F=JI+J=K

步驟OPTR棧OPND棧輸入字符主要操作

1耳A-B*C/D+E'F#PUSH(OPND,A)

2nAZB*C/D+E"F#PUSH(OPTR,-)

3n-AB*C/D+E*F#PUSH(OPND,B)

4n-AB*C/D+E-F#PUSH(OPTR,*)

5#-*ABC/D+E'F#PUSH(OPND,0

6#-*ABC/D+E'F#Operate(B,*,C)

7AG/D+E￥#PUSH(OPTR,/)

8#-/AGD+E"F#PUSH(OPND,D)

9#-/AGD+E"F#Operate(G,/,D)

10AH+E￥#Operate(A,H)

11I+E-F#PUSH(OPTR,+)

12#+IE'F#PUSH(OPND,E)

13#+IE二#FPUSH(OPTR,■)

14#+"IEE#PUSH(OPND,F)

15#+"IEF#Operate(E,\F)

16#+IJOperated,+,J)

17#KRETURN

3.8解：2n—1

3.9解：

voidditui(intj)

(

if(j>l)(

cout<<j;

ditui(j-1);

)

return;

)

3.10解：

voidtest(int&sum)

Stacks;

InitStack(s);

intx;

do{

cin?x;

Push(s,x);

}while(x>0);

while(!StackEmpty(s)){

Pop(s,x);

sum+=x;

cout?sum?endl;

}

DestoryStack(s);

)

3.11解：棧是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。

隊(duì)列也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。

3.12解：char

3.13解：隊(duì)列逆置

3.15解：

classDStack(

ElemType*top[2];

ElemType*p;

intstacksize;

intdi;

public:

DStack(intm)

(

p=newElemType[m];

if(!p)exit(OVERFLOW);

top[0]=p+m/2;

top[l]=top[0];

stacksize=m;

)

^DStack(){deletep;}

voidPush(inti,ElemTypex)

(

di=i;

if(di=0){

if(top[0]>=p)*top[0]一=x;

elsecerr?z，Stackoverflow!

)

else{

if(top[1]<p+stacksize-1)*++top[l]=x;

elsecerr?/zStackoverflow!”;

}

)

ElemTypePop(inti)

(

di=i;

if(di==O){

if(top[0]<top[l])return*++top[0];

elsecerr?”Stackempty!”;

}else{

if(top[l]>top[01)return*top[l]一;

elsecerr?/zStackempty!”;

)

returnOK;

)

}；

//鏈棧的數(shù)據(jù)結(jié)構(gòu)及方法的定義

typedefstructNodeType{

ElemTypedata;

NodeType*next;

}NodeType,*LinkType;

typedefstruct{

LinkTypetop;

intsize;

}Stack;

voidInitStack(Stack&s)

(

s.top=NULL;

s.size=0;

}

voidDestroyStack(Stack&s)

(

LinkTypep;

while(s.top){

p=s.top;

s.top=p->next;

deletep;

s.size一；

)

voidC1earStack(Stack&s)

LinkTypep;

while(s.top){

p=s.top;

s.top=p->next;

deletep;

s.size一;

)

)

intStackLength(Stacks)

(

returns.size;

)

StatusStackEmpty(Stacks)

(

if(s.size-0)returnTRUE;

elsereturnFALSE;

)

StatusGetTop(Stacks,ElemType&e)

(

if(!s.top)returnERROR;

else{

e=s.top->data;

returnOK;

)

)

StatusPush(Stack&s,ElemTypee)

(

LinkTypep;

p二newNodeType;

if(!p)exit(OVERFLOW);

p->next=s.top;

s.top=p;

p->data=e;

s.size++;

returnOK;

)

StatusPop(Stack&s,ElemType&e)

LinkTypep;

if(s.top){

e=s.top->data;

p=s.top;

s.top=p->next;

deletep;

s.size一;

)

returnOK;

)

//從棧頂?shù)綏５子肰isit()函數(shù)遍歷棧中每個(gè)數(shù)據(jù)元素

voidStackTraverse(Stacks,Status(*Visit)(ElemTypee))

(

LinkTypep;

p=s.top;

while(p)Visit(p->data);

}

3.16解：

intmain()

(

Stacks;

charBuffer[80];

inti=0,j=0;

InitStack(s);

cout?〃請(qǐng)輸入硬席(H)和軟席車廂(S)序列：〃；

cin>>Buffer;

cout<<Buffer<<endl;

while(Buffer[i]){

if(Buffer[i]==,S*){

Buffer[j]=Buffer[i];

j++；

)

elsePush(s,Buffer[i]);

i++;

)

while(Buffer[j]){

Pop(s,Buffer[j]);

)

cout<<Buffer<<end1;

return0;

3.17解：

BOOLSymmetry(chara[])

inti=0;

Stacks;

InitStack(s);

ElemTypex;

while(a[i]!='&'&&a[i]){

Push(s,a[i]);

i++；

)

if(a[il)returnFALSE;

i++；

while(a[i]){

Pop(s,x);

if(x!=a[i]){

DestroyStack(s);

returnFALSE;

}

i++；

)

returnTRUE;

)

3.18解：

BOOLBracketCorrespondency(chara口)

{

inti=0;

Stacks;

InitStack(s);

ElemTypex;

while(a[i]){

switch(a[i]){

case'(':

Push(s,a[i]);

break;

case':

Push(s,a[i]);

break;

case')':

GetTop(s,x);

if(x=-C)Pop(s,x);

elsereturnFALSE;

break;

case':

GetTop(s,x);

if(x=-r)Pop(s,x);

elsereturnFALSE;

break;

default:

break;

)

i++；

)

if(s.size!=0)returnFALSE;

returnTRUE;

)

3.21解：

//輸入的表達(dá)式串必須為#...#格式

voidInversePolandExpression(charBuffer口)

(

Stacks;

InitStack(s);

inti=0,j=0;

ElemTypee;

Push(s,Buffer[i]);

i++；

while(BufferEi]!='#'){

if(!IsOperator(Buffer[i])){//是操作數(shù)

Buffer[j]=Buffer[i];

i++；

j++；

)

else{//是操作符

GetTop(s,e);

if(Prior(e,Buffer[i])){//當(dāng)棧頂優(yōu)先權(quán)高于當(dāng)前序列時(shí),退棧

Pop(s,e);

Buffer[j]=e;

j++；

}

else(

Push(s,Buffer[i]);

i++；

)

)

)

while(!StackEmpty(s)){

Pop(s,e);

Buffer[j]=e;

J++；

}

}

StatusIsOpertor(charc)

{

char

while(*p){

if(*p-c)

returnTRUE;

p++；

)

returnFALSE;

)

StatusPrior(charcl,charc2)

(

charch□=〃#+-*/〃；

inti=0,j=0;

while(ch[i]&&ch[i]!=cl)i++;

if(i-2)i-;//加和減可認(rèn)為是同級(jí)別的運(yùn)算符

if(i==4)i-;//乘和除可認(rèn)為是同級(jí)別的運(yùn)算符

while(ch[j]&&ch[j]!=c2)j++;

if(j==2)j—;

if(j==4)j—;

if(i>=j)returnTRUE;

elsereturnFALSE;

)

3.22如題3.21的假設(shè)條件，試寫一個(gè)算法，對(duì)以逆波蘭式表示的表達(dá)式求值。

解：

charCalVal_InverPoland(charBuffer口)

(

StackOpnd;

InitStack(Opnd);

inti=0;

charc;

ElemTypeel,e2;

while(Buffer[i]!='#'){

if(!IsOperator(Buffer[i])){

Push(Opnd,Buffer[i]);

)

else{

Pop(Opnd,e2);

Pop(Opnd,el);

c=Cal(el,Buffer[i],e2);

Push(Opnd,c);

)

i++；

)

returnc;

)

charCal(charcl,charop,charc2)

{

intx,xl,x2;

charch[10];

ch[0]=cl;

ch[l]=\0J;

xl=atoi(ch);

ch[O]=c2;

ch⑴八O';

x2=atoi(ch);

switch(op){

case'+':

x=xl+x2;

break;

case':

x=xl-x2;

break;

case':

x=xl*x2;

break;

case'r:

x=xl/x2;

break;

default:

break;

)

itoa(x,ch,10);

returnch[0];

}

3.24解：

intg(intm,intn);

intmainO

(

intm,n;

cout＜〈”請(qǐng)輸入m和n的值：”；

cin>>m>>n;

if(n>=0)cout?g(m,n)?endl;

elsecout?”NoSolution!”;

return0;

}

intg(intm,intn)

(

if(m>0)

return(g(m-l,2*n)+n);

elsereturn0;

}

假設(shè)主函數(shù)的返回地址為0,遞歸函數(shù)3條語句的地址分別為1、2、30

16~64-

3132

3216

338

344

052

3.25解：

^include<iostrearn.h>

#defineN20

intmain()

{

inti;

inta[N];

intn;

cout<X"請(qǐng)輸入n:”;

cin?n;

for(i=0;i<n+l;i++){

elsea[i]=i*a[i/2];

)

cout<<a[n]<<endl;

return0;

}

3.28解：

typedefintElemType;

typedefstructNodeType{

ElemTypedata;

NodeType*next;

}QNode,*QPtr;

typedefstruct{

QPtrrear;

intsize;

}Queue;

StatusInitQueue(Queue&q)

q.rear=NULL;

q.size=O;

returnOK;

}

StatusEnQueue(Queue&q,ElernTypee)

(

QPtrp;

p=newQNode;

if(!p)returnFALSE;

p->data=e;

if(!q.rear){

q.rear=p;

p->next=q.rear;

}

else{

p->next=q.rear->next;

q.rear->next=p;

q.rear=p;

)

q.size++;

returnOK;

}

StatusDeQueue(Queuedq,ElemType&e)

(

QPtrp;

if(q.size==0)returnFALSE;

if(q.size==l){

p=q.rear;

e=p->data;

q.rear=NULL;

deletep;

)

else{

p=q.rear->next;

e=p->dat