數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第三四章習(xí)題答案及解析

..第3章棧和隊(duì)列習(xí)題1．選擇題〔1若讓元素1,2,3,4,5依次進(jìn)棧,則出棧次序不可能出現(xiàn)在〔種情況。A．5,4,3,2,1B．2,1,5,4,3C．4,3,1,2,5D．2,3,5,4,1〔2若已知一個(gè)棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為〔。A．iB．n-iC．n-i+1D．不確定〔3數(shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列,ｆ為當(dāng)前隊(duì)列頭元素的前一位置,ｒ?yàn)殛?duì)尾元素的位置,假定隊(duì)列中元素的個(gè)數(shù)小于ｎ,計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為〔。A．r-fB．<n+f-r>%nC．n+r-fD．〔n+r-f>%n〔4鏈?zhǔn)綏＝Y(jié)點(diǎn)為：<data,link>,top指向棧頂.若想摘除棧頂結(jié)點(diǎn),并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作〔。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；〔5設(shè)有一個(gè)遞歸算法如下intfact<intn>{//n大于等于0if<n<=0>return1;elsereturnn*fact<n-1>;}則計(jì)算fact<n>需要調(diào)用該函數(shù)的次數(shù)為〔。A．n+1B．n-1C．nD．n+2〔6棧在〔中有所應(yīng)用。A．遞歸調(diào)用B．函數(shù)調(diào)用C．表達(dá)式求值D．前三個(gè)選項(xiàng)都有〔7為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題,通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是〔。A．隊(duì)列B．棧C．線性表D．有序表〔8設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S,一個(gè)元素出棧后即進(jìn)入Q,若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1,則棧S的容量至少應(yīng)該是〔。A．2B．3C．4D．6〔9在一個(gè)具有n個(gè)單元的順序棧中,假設(shè)以地址高端作為棧底,以top作為棧頂指針,則當(dāng)作進(jìn)棧處理時(shí),top的變化為〔。A．top不變B．top=0C．top--D．top++〔10設(shè)計(jì)一個(gè)判別表達(dá)式中左,右括號(hào)是否配對(duì)出現(xiàn)的算法,采用〔數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧〔11用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行刪除運(yùn)算時(shí)〔。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改〔12循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中,則入隊(duì)時(shí)的操作為〔。A.rear=rear+1B.rear=<rear+1>%<m-1>C.rear=<rear+1>%mD.rear=<rear+1>%<m+1>〔13最大容量為n的循環(huán)隊(duì)列,隊(duì)尾指針是rear,隊(duì)頭是front,則隊(duì)空的條件是〔。A.<rear+1>%n==frontB.rear==frontC．rear+1==frontD.<rear-l>%n==front〔14棧和隊(duì)列的共同點(diǎn)是〔。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)〔15一個(gè)遞歸算法必須包括〔。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分〔2回文是指正讀反讀均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。<提示：將一半字符入棧>

根據(jù)提示,算法可設(shè)計(jì)為：

//以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義

#defineStackSize100//假定預(yù)分配的?？臻g最多為100個(gè)元素

typedefcharDataType;//假定棧元素的數(shù)據(jù)類(lèi)型為字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen<char*t>

{//判斷t字符向量是否為回文,若是,返回1,否則返回0

SeqStacks;

inti,len;

chartemp;

InitStack<&s>;

len=strlen<t>;//求向量長(zhǎng)度

for<i=0;i<len/2;i++>//將一半字符入棧

Push<&s,t[i]>;

while<!EmptyStack<&s>>

{//每彈出一個(gè)字符與相應(yīng)字符比較

temp=Pop<&s>;

if<temp!=S[i]>

return0;//不等則返回0

elsei++;

}

return1;//比較完畢均相等則返回1

}〔3設(shè)從鍵盤(pán)輸入一整數(shù)的序列：a1,a2,a3,…,an,試編寫(xiě)算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù),當(dāng)ai≠-1時(shí),將ai進(jìn)棧；當(dāng)ai=-1時(shí),輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況〔入棧滿等給出相應(yīng)的信息。#definemaxsize?？臻g容量voidInOutS<ints[maxsize]>//s是元素為整數(shù)的棧,本算法進(jìn)行入棧和退棧操作。{inttop=0;//top為棧頂指針,定義top=0時(shí)為?？铡or<i=1;i<=n;i++>//n個(gè)整數(shù)序列作處理。{scanf<"%d",&x>;//從鍵盤(pán)讀入整數(shù)序列。if<x!=-1>//讀入的整數(shù)不等于-1時(shí)入棧。if<top==maxsize-1>{printf<"棧滿\n">;exit<0>;}elses[++top]=x;//x入棧。else//讀入的整數(shù)等于-1時(shí)退棧。{if<top==0>{printf<"?？誠(chéng)n">;exit<0>;}elseprintf<"出棧元素是%d\n",s[top--]>；}}}//算法結(jié)束?！?從鍵盤(pán)上輸入一個(gè)后綴表達(dá)式,試編寫(xiě)算法計(jì)算表達(dá)式的值。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過(guò)一行,以$符作為輸入結(jié)束,操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運(yùn)算。例如：23434+2*$。[題目分析]逆波蘭表達(dá)式<即后綴表達(dá)式>求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND,對(duì)表達(dá)式從左到右掃描<讀入>,當(dāng)表達(dá)式中掃描到數(shù)時(shí),壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí),從OPND退出兩個(gè)數(shù),進(jìn)行相應(yīng)運(yùn)算,結(jié)果再壓入OPND棧。這個(gè)過(guò)程一直進(jìn)行到讀出表達(dá)式結(jié)束符$,這時(shí)OPND棧中只有一個(gè)數(shù),就是結(jié)果。floatexpr<>//從鍵盤(pán)輸入逆波蘭表達(dá)式,以‘$’表示輸入結(jié)束,本算法求逆波蘭式表達(dá)式的值。｛floatOPND[30];//OPND是操作數(shù)棧。init<OPND>;//兩棧初始化。floatnum=0.0;//數(shù)字初始化。scanf<"%c",&x>;//x是字符型變量。while<x!=’$’>{switch{case‘0’<=x<=’9’:while<<x>=’0’&&x<=’9’>||x==’.’>//拼數(shù)if<x!=’.’>//處理整數(shù){num=num*10+〔ord<x>-ord<‘0’>;scanf<"%c",&x>;}else//處理小數(shù)部分。{scale=10.0;scanf<"%c",&x>;while<x>=’0’&&x<=’9’>{num=num+<ord<x>-ord<‘0’>/scale;scale=scale*10;scanf<"%c",&x>;}}//elsepush<OPND,num>;num=0.0;//數(shù)壓入棧,下個(gè)數(shù)初始化casex=‘’:break;//遇空格,繼續(xù)讀下一個(gè)字符。casex=‘+’:push<OPND,pop<OPND>+pop<OPND>>;break;casex=‘-’:x1=pop<OPND>;x2=pop<OPND>;push<OPND,x2-x1>;break;casex=‘*’:push<OPND,pop<OPND>*pop<OPND>>;break;casex=‘/’:x1=pop<OPND>;x2=pop<OPND>;push<OPND,x2/x1>;break;default://其它符號(hào)不作處理。}//結(jié)束switchscanf<"%c",&x>;//讀入表達(dá)式中下一個(gè)字符。}//結(jié)束while〔x！=‘$’printf<"后綴表達(dá)式的值為%f",pop<OPND>>;}//算法結(jié)束。[算法討論]假設(shè)輸入的后綴表達(dá)式是正確的,未作錯(cuò)誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符,認(rèn)為是數(shù)。這種字符的序號(hào)減去字符‘0’的序號(hào)得出數(shù)。對(duì)于整數(shù),每讀入一個(gè)數(shù)字字符,前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點(diǎn),認(rèn)為數(shù)的整數(shù)部分已完,要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10〔或10的冪數(shù)變成十分位,百分位,千分位數(shù)等等,與前面部分?jǐn)?shù)相加。在拼數(shù)過(guò)程中,若遇非數(shù)字字符,表示數(shù)已拼完,將數(shù)壓入棧中,并且將變量num恢復(fù)為0,準(zhǔn)備下一個(gè)數(shù)。這時(shí)對(duì)新讀入的字符進(jìn)入‘+’、‘-’、‘*’、‘/’及空格的判斷,因此在結(jié)束處理數(shù)字字符的case后,不能加入break語(yǔ)句。〔5假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空,入棧和出棧的操作序列可表示為僅由I和O組成的序列,稱(chēng)可以操作的序列為合法序列,否則稱(chēng)為非法序列。=1\*GB3①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=2\*GB3②通過(guò)對(duì)=1\*GB3①的分析,寫(xiě)出一個(gè)算法,判定所給的操作序列是否合法。若合法,返回true,否則返回false〔假定被判定的操作序列已存入一維數(shù)組中。=1\*GB3①A和D是合法序列,B和C是非法序列。=2\*GB3②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge<charA[]>//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是,返回true,否則返回false。{i=0;//i為下標(biāo)。j=k=0;//j和k分別為I和字母O的的個(gè)數(shù)。while<A[i]!=‘\0’>//當(dāng)未到字符數(shù)組尾就作。{switch<A[i]>{case‘I’:j++;break;//入棧次數(shù)增1。case‘O’:k++;if<k>j>{printf<"序列非法\n">；exit<0>;}}i++;//不論A[i]是‘I’或‘O’,指針i均后移。}if<j!=k>{printf<"序列非法\n">；return<false>;}else{printf<"序列合法\n">；return<true>;}}//算法結(jié)束。[算法討論]在入棧出棧序列〔即由‘I’和‘O’組成的字符串的任一位置,入棧次數(shù)〔‘I’的個(gè)數(shù)都必須大于等于出棧次數(shù)〔即‘O’的個(gè)數(shù),否則視作非法序列,立即給出信息,退出算法。整個(gè)序列〔即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘\0’,入棧次數(shù)必須等于出棧次數(shù)〔題目中要求棧的初態(tài)和終態(tài)都為空,否則視為非法序列。<6假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾元素站點(diǎn)<注意不設(shè)頭指針>,試編寫(xiě)相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。

算法如下：

//先定義鏈隊(duì)結(jié)構(gòu):

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是結(jié)點(diǎn)類(lèi)型的定義

typedefstruct{

queuenode*rear;

}LinkQueue;//只設(shè)一個(gè)指向隊(duì)尾元素的指針

<1>置空隊(duì)

voidInitQueue<LinkQueue*Q>

{//置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素

QueueNode*s;

Q->rear=Q->rear->next;//將隊(duì)尾指針指向頭結(jié)點(diǎn)

while<Q->rear!=Q->rear->next>//當(dāng)隊(duì)列非空,將隊(duì)中元素逐個(gè)出隊(duì)

{s=Q->rear->next;

Q->rear->next=s->next;

free<s>;

}//回收結(jié)點(diǎn)空間

}

<2>判隊(duì)空

intEmptyQueue<LinkQueue*Q>

{//判隊(duì)空

//當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì)

returnQ->rear->next->next==Q->rear->next;

}

<3>入隊(duì)

voidEnQueue<LinkQueue*Q,Datatypex>

{//入隊(duì)

//也就是在尾結(jié)點(diǎn)處插入元素

QueueNode*p=<QueueNode*>malloc<sizeof<QueueNode>>;//申請(qǐng)新結(jié)點(diǎn)

p->data=x;p->next=Q->rear->next;//初始化新結(jié)點(diǎn)并鏈入

Q-rear->next=p;

Q->rear=p;//將尾指針移至新結(jié)點(diǎn)

}

<4>出隊(duì)

DatatypeDeQueue<LinkQueue*Q>

{//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下

Datatypet;

QueueNode*p;

if<EmptyQueue<Q>>

Error<"Queueunderflow">;

p=Q->rear->next->next;//p指向?qū)⒁碌慕Y(jié)點(diǎn)

x=p->data;//保存結(jié)點(diǎn)中數(shù)據(jù)

if<p==Q->rear>

{//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí),p結(jié)點(diǎn)出隊(duì)后,要將隊(duì)尾指針指向頭結(jié)點(diǎn)

Q->rear=Q->rear->next;Q->rear->next=p->next;}

else

Q->rear->next->next=p->next;//摘下結(jié)點(diǎn)p

free<p>;//釋放被刪結(jié)點(diǎn)

returnx;

}〔7假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素,同時(shí)設(shè)置一個(gè)標(biāo)志tag,以tag==0和tag==1來(lái)區(qū)別在隊(duì)頭指針<front>和隊(duì)尾指針<rear>相等時(shí),隊(duì)列狀態(tài)為"空"還是"滿"。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的插入<enqueue>和刪除<dlqueue>算法。[解答]循環(huán)隊(duì)列類(lèi)定義 #include<assert.h> template<classType>classQueue{ //循環(huán)隊(duì)列的類(lèi)定義 public:Queue<int=10>; ~Queue<>{delete[]Q;}voidEnQueue<Type&item>;TypeDeQueue<>;TypeGetFront<>;voidMakeEmpty<>{front=rear=tag=0;} //置空隊(duì)列intIsEmpty<>const{returnfront==rear&&tag==0;} //判隊(duì)列空否intIsFull<>const{returnfront==rear&&tag==1;} //判隊(duì)列滿否 private:intrear,front,tag; //隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)志Type*Q; //存放隊(duì)列元素的數(shù)組intm; //隊(duì)列最大可容納元素個(gè)數(shù) }構(gòu)造函數(shù) template<classType>Queue<Type>::Queue<intsz>:rear<0>,front<0>,tag<0>,m<sz>{ //建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。Q=newType[m]; //創(chuàng)建隊(duì)列空間assert<Q!=0>; //斷言:動(dòng)態(tài)存儲(chǔ)分配成功與否 }插入函數(shù)template<classType>voidQueue<Type>::EnQueue<Type&item>{ assert<!IsFull<>>;//判隊(duì)列是否不滿,滿則出錯(cuò)處理rear=<rear+1>%m;//隊(duì)尾位置進(jìn)1,隊(duì)尾指針指示實(shí)際隊(duì)尾位置Q[rear]=item; //進(jìn)隊(duì)列tag=1; //標(biāo)志改1,表示隊(duì)列不空 }刪除函數(shù)template<classType>TypeQueue<Type>::DeQueue<>{ assert<!IsEmpty<>>;//判斷隊(duì)列是否不空,空則出錯(cuò)處理front=<front+1>%m; //隊(duì)頭位置進(jìn)1,隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置tag=0; //標(biāo)志改0,表示棧不滿returnQ[front]; //返回原隊(duì)頭元素的值}讀取隊(duì)頭元素函數(shù)template<classType>TypeQueue<Type>::GetFront<>{ assert<!IsEmpty<>>;//判斷隊(duì)列是否不空,空則出錯(cuò)處理returnQ[<front+1>%m]; //返回隊(duì)頭元素的值}<8如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求：=1\*GB3①寫(xiě)出循環(huán)隊(duì)列的類(lèi)型定義；=2\*GB3②寫(xiě)出"從隊(duì)尾刪除"和"從隊(duì)頭插入"的算法。[題目分析]用一維數(shù)組v[0..M-1]實(shí)現(xiàn)循環(huán)隊(duì)列,其中M是隊(duì)列長(zhǎng)度。設(shè)隊(duì)頭指針front和隊(duì)尾指針rear,約定front指向隊(duì)頭元素的前一位置,rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空,<rear+1>%m=front為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展,隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展?！?#defineM隊(duì)列可能達(dá)到的最大長(zhǎng)度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;〔2elemtpdelqueue<cycqueueQ>//Q是如上定義的循環(huán)隊(duì)列,本算法實(shí)現(xiàn)從隊(duì)尾刪除,若刪除成功,返回被刪除元素,否則給出出錯(cuò)信息。 {if<Q.front==Q.rear>{printf<"隊(duì)列空">;exit<0>;} Q.rear=<Q.rear-1+M>%M;//修改隊(duì)尾指針。return<Q.data[<Q.rear+1+M>%M]>;//返回出隊(duì)元素。}//從隊(duì)尾刪除算法結(jié)束voidenqueue<cycqueueQ,elemtpx>//Q是順序存儲(chǔ)的循環(huán)隊(duì)列,本算法實(shí)現(xiàn)"從隊(duì)頭插入"元素x。{if<Q.rear==<Q.front-1+M>%M>{printf<"隊(duì)滿";exit<0>;>Q.data[Q.front]=x;//x入隊(duì)列Q.front=<Q.front-1+M>%M;//修改隊(duì)頭指針。}//結(jié)束從隊(duì)頭插入算法。〔9已知Ackermann函數(shù)定義如下:=1\*GB3①寫(xiě)出計(jì)算Ack<m,n>的遞歸算法,并根據(jù)此算法給出出Ack<2,1>的計(jì)算過(guò)程。=2\*GB3②寫(xiě)出計(jì)算Ack<m,n>的非遞歸算法。intAck<intm,n>{if<m==0>return<n+1>;elseif<m!=0&&n==0>return<Ack<m-1,1>>;elsereturn<Ack<m-1,Ack<m,m-1>>;}//算法結(jié)束〔1Ack<2,1>的計(jì)算過(guò)程Ack<2,1>=Ack<1,Ack<2,0>>//因m<>0,n<>0而得=Ack<1,Ack<1,1>>//因m<>0,n=0而得=Ack<1,Ack<0,Ack<1,0>>>//因m<>0,n<>0而得=Ack<1,Ack<0,Ack<0,1>>>//因m<>0,n=0而得=Ack<1,Ack<0,2>>//因m=0而得=Ack<1,3>//因m=0而得=Ack<0,Ack<1,2>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<1,1>>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<0,Ack<1,0>>>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<0,Ack<0,1>>>>//因m<>0,n=0而得=Ack<0,Ack<0,Ack<0,2>>>//因m=0而得=Ack<0,Ack<0,3>>//因m=0而得=Ack<0,4>//因n=0而得=5//因n=0而得〔2intAckerman<intm,intn>{intakm[M][N];inti,j;for<j=0;j<N;j++>akm[0][j];=j+1;for<i=1;i<m;i++>{akm[i][0]=akm[i-1][1];for<j=1;j<N;j++>akm[i][j]=akm[i-1][akm[i][j-1]];}return<akm[m][n]>;}//算法結(jié)束〔10已知f為單鏈表的表頭指針,鏈表中存儲(chǔ)的都是整型數(shù)據(jù),試寫(xiě)出實(shí)現(xiàn)下列運(yùn)算的遞歸算法：=1\*GB3①求鏈表中的最大整數(shù)；=2\*GB3②求鏈表的結(jié)點(diǎn)個(gè)數(shù)；=3\*GB3③求所有整數(shù)的平均值。#include<iostream.h>//定義在頭文件"RecurveList.h"中classList; classListNode{ //鏈表結(jié)點(diǎn)類(lèi)friendclassList;private:intdata; //結(jié)點(diǎn)數(shù)據(jù)ListNode*link; //結(jié)點(diǎn)指針ListNode<constintitem>:data<item>,link<NULL>{} //構(gòu)造函數(shù)};classList{ //鏈表類(lèi)private:ListNode*first,current;intMax<ListNode*f>;intNum<ListNode*f>;floatAvg<ListNode*f,int&n>;public:List<>:first<NULL>,current<NULL>{} //構(gòu)造函數(shù) ~List<>{} //析構(gòu)函數(shù)ListNode*NewNode<constintitem>; //創(chuàng)建鏈表結(jié)點(diǎn),其值為itemvoidNewList<constintretvalue>; //建立鏈表,以輸入retvalue結(jié)束voidPrintList<>; //輸出鏈表所有結(jié)點(diǎn)數(shù)據(jù)intGetMax<>{returnMax<first>;} //求鏈表所有數(shù)據(jù)的最大值intGetNum<>{returnNum<first>;} //求鏈表中數(shù)據(jù)個(gè)數(shù)floatGetAvg<>{returnAvg<first>;} //求鏈表所有數(shù)據(jù)的平均值}; ListNode*List::NewNode<constintitem>{ //創(chuàng)建新鏈表結(jié)點(diǎn)ListNode*newnode=newListNode<item>;returnnewnode;}voidList::NewList<constintretvalue>{ //建立鏈表,以輸入retvalue結(jié)束first=NULL;intvalue;ListNode*q;cout<<"Inputyourdata:\n"; //提示cin>>value; //輸入while<value!=retvalue>{//輸入有效q=NewNode<value>; //建立包含value的新結(jié)點(diǎn)if<first==NULL>first=current=q; //空表時(shí),新結(jié)點(diǎn)成為鏈表第一個(gè)結(jié)點(diǎn)else{current->link=q;current=q;} //非空表時(shí),新結(jié)點(diǎn)鏈入鏈尾cin>>value; //再輸入}current->link=NULL; //鏈尾封閉}voidList::PrintList<>{ //輸出鏈表cout<<"\nTheListis:\n";ListNode*p=first;while<p!=NULL>{ cout<<p->data<<'';p=p->link;} cout<<‘\n’;}intList::Max<ListNode*f>{ //遞歸算法:求鏈表中的最大值if<f->link==NULL>returnf->data; //遞歸結(jié)束條件 inttemp=Max<f->link>; //在當(dāng)前結(jié)點(diǎn)的后繼鏈表中求最大值if<f->data>temp>returnf->data; //如果當(dāng)前結(jié)點(diǎn)的值還要大,返回當(dāng)前檢點(diǎn)值 elsereturntemp; //否則返回后繼鏈表中的最大值}intList::Num<ListNode*f>{ //遞歸算法:求鏈表中結(jié)點(diǎn)個(gè)數(shù) if<f==NULL>return0; //空表,返回0return1+Num<f->link>; //否則,返回后繼鏈表結(jié)點(diǎn)個(gè)數(shù)加1}floatList::Avg<ListNode*f,int&n>{//遞歸算法:求鏈表中所有元素的平均值if<f->link==NULL> //鏈表中只有一個(gè)結(jié)點(diǎn),遞歸結(jié)束條件{n=1;return<float><f->data>;}else{floatSum=Avg<f->link,n>*n;n++;return<f->data+Sum>/n;}}#include"RecurveList.h" //定義在主文件中intmain<intargc,char*argv[]>{Listtest;intfinished;cout<<"輸入建表結(jié)束標(biāo)志數(shù)據(jù)：";cin>>finished; //輸入建表結(jié)束標(biāo)志數(shù)據(jù)test.NewList<finished>; //建立鏈表test.PrintList<>; //打印鏈表cout<<"\nTheMaxis:"<<test.GetMax<>;cout<<"\nTheNumis:"<<test.GetNum<>;cout<<"\nTheAveis:"<<test.GetAve<><<'\n'; printf<"HelloWorld!\n">;return0;}第4章串、數(shù)組和廣義表習(xí)題1．選擇題〔1串是一種特殊的線性表,其特殊性體現(xiàn)在〔。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符若〔2串下面關(guān)于串的的敘述中,〔是不正確的？A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ),也可以采用鏈?zhǔn)酱鎯?chǔ)〔3串"ababaaababaa"的next數(shù)組為〔。〔4串"ababaabab"的nextval為〔。A．010104101B．010102101C．010100011D．010101011〔5串的長(zhǎng)度是指〔。A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)〔6假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100],設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元,基地址為10,則LOC[5,5]=〔。A．808B．818C．1010D．1020〔7設(shè)有數(shù)組A[i,j],數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié),i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放,當(dāng)用以列為主存放時(shí),元素A[5,8]的存儲(chǔ)首地址為〔。A．BA+141B．BA+180C．BA+222D．BA+225〔8設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式,以行序?yàn)橹鞔鎯?chǔ),a11為第一元素,其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間,則a85的地址為〔。A．13B．33C．18D．40〔9若對(duì)n階對(duì)稱(chēng)矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?lt;包括主對(duì)角線上所有元素>依次存放于一維數(shù)組B[1..<n<n+1>>/2]中,則在B中確定aij〔i<j的位置k的關(guān)系為〔。A．i*<i-1>/2+jB．j*<j-1>/2+iC．i*<i+1>/2+jD．j*<j+1>/2+i〔10A[N,N]是對(duì)稱(chēng)矩陣,將下面三角〔包括對(duì)角線以行序存儲(chǔ)到一維數(shù)組T[N<N+1>/2]中,則對(duì)任一上三角元素a[i][j]對(duì)應(yīng)T[k]的下標(biāo)k是〔。A．i<i-1>/2+jB．j<j-1>/2+iC．i<j-i>/2+1D．j<i-1>/2+1〔11設(shè)二維數(shù)組A[1..m,1..n]〔即m行n列按行存儲(chǔ)在數(shù)組B[1..m*n]中,則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為〔。A．<i-1>*n+jB．<i-1>*n+j-1C．i*<j-1>D．j*m+i-1〔12數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)〔。A．55B．45C．36D．16〔13廣義表A=<a,b,<c,d>,<e,<f,g>>>,則Head<Tail<Head<Tail<Tail<A>>>>>的值為〔。A．<g>B．<d>C．cD．d〔14廣義表<<a,b,c,d>>的表頭是〔,表尾是〔。A．a(chǎn)B．<>C．<a,b,c,d>D．<b,c,d>〔15設(shè)廣義表L=<<a,b,c>>,則L的長(zhǎng)度和深度分別為〔。A．1和1B．1和3C．1和2D．2和3〔1已知模式串t=‘a(chǎn)bcaabbabcab’寫(xiě)出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105〔2設(shè)目標(biāo)為t="abcaabbabcabaacbacba",模式為p="abcabaa"=1\*GB3①計(jì)算模式p的naxtval函數(shù)值；=2\*GB3②不寫(xiě)出算法,只畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。=1\*GB3①p的nextval函數(shù)值為0110132?！瞤的next函數(shù)值為0111232。=2\*GB3②利用KMP<改進(jìn)的nextval>算法,每趟匹配過(guò)程如下：第一趟匹配：abcaabbabcabaacbacbaabcab<i=5,j=5>第二趟匹配：abcaabbabcabaacbacbaabc<i=7,j=3>第三趟匹配：abcaabbabcabaacbacbaa<i=7,j=1>第四趟匹配：abcaabbabcabaacbacba<成功>abcabaa<i=15,j=8>〔3數(shù)組A中,每個(gè)元素A[i,j]的長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9,列下標(biāo)從1到11,從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中,主存儲(chǔ)器字長(zhǎng)為16位。求：=1\*GB3①存放該數(shù)組所需多少單元？=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元？=3\*GB3③數(shù)組按行存放時(shí),元素A[7,4]的起始地址是多少？=4\*GB3④數(shù)組按列存放時(shí),元素A[4,7]的起始地址是多少？每個(gè)元素32個(gè)二進(jìn)制位,主存字長(zhǎng)16位,故每個(gè)元素占2個(gè)字長(zhǎng),行下標(biāo)可平移至1到11?！?242〔222〔3s+182〔4s+142<4>請(qǐng)將香蕉banana用工具H<>—Head<>,T<>—Tail<>從L中取出。L=<apple,<orange,<strawberry,<banana>>,peach>,pear>H〔H〔T〔H〔T〔H〔T〔L〔5寫(xiě)一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件〔字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字。voidCount〔//統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。｛inti,num[36]；charch；for〔i＝0；i<36；i++num[i]＝０；//初始化while〔〔ch＝getchar〔!=‘#’//‘#’表示輸入字符串結(jié)束。if〔‘0’<=ch<=‘9’｛i=ch－48;num[i]++；｝//數(shù)字字符elseif〔‘A’<=ch<=‘Z’｛i=ch-65+10;num[i]++；｝//字母字符for〔i=0；i<10；i++//輸出數(shù)字字符的個(gè)數(shù)printf〔"數(shù)字％d的個(gè)數(shù)＝％d\n",i,num[i]；for〔i＝10；i<36；i++//求出字母字符的個(gè)數(shù)printf〔"字母字符％c的個(gè)數(shù)＝％d\n",i＋55,num[i]；｝//算法結(jié)束?！?寫(xiě)一個(gè)遞歸算法來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ),要求不另設(shè)串存儲(chǔ)空間。[題目分析]實(shí)現(xiàn)字符串的逆置并不難,但本題"要求不另設(shè)串存儲(chǔ)空間"來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ),即第一個(gè)輸入的字符最后存儲(chǔ),最后輸入的字符先存儲(chǔ),使用遞歸可容易做到。voidInvertStore<charA[]>//字符串逆序存儲(chǔ)的遞歸算法。{charch;staticinti=0;//需要使用靜態(tài)變量scanf<"%c",&ch>;if<ch!='.'>//規(guī)定'.'是字符串輸入結(jié)束標(biāo)志 {InvertStore<A>; A[i++]=ch;//字符串逆序存儲(chǔ) }A[i]='\0';//字符串結(jié)尾標(biāo)記}//結(jié)束算法InvertStore。〔7編寫(xiě)算法,實(shí)現(xiàn)下面函數(shù)的功能。函數(shù)voidinsert<char*s,char*t,intpos>將字符串t插入到字符串s中,插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入?！舱f(shuō)明：不得使用任何庫(kù)函數(shù)[題目分析]本題是字符串的插入問(wèn)題,要求在字符串s的pos位置,插入字符串t。首先應(yīng)查找字符串s的pos位置,將第pos個(gè)字符到字符串s尾的子串向后移動(dòng)字符串t的長(zhǎng)度,然后將字符串t復(fù)制到字符串s的第pos位置后。對(duì)插入位置pos要驗(yàn)證其合法性,小于1或大于串s的長(zhǎng)度均為非法,因題目假設(shè)給字符串s的空間足夠大,故對(duì)插入不必判溢出。voidinsert<char*s,char*t,intpos>//將字符串t插入字符串s的第pos個(gè)位置。{inti=1,x=0;char*p=s,*q=t;//p,q分別為字符串s和t的工作指針if<pos<1>{printf<"pos參數(shù)位置非法\n">;exit<0>;}while<*p!=’\0’&&i<pos>{p++;i++;}//查pos位置//若pos小于串s長(zhǎng)度,則查到pos位置時(shí),i=pos。if<*p=='/0'>{printf<"%d位置大于字符串s的長(zhǎng)度",pos>;exit<0>;}else//查找字符串的尾while<*p!='/0'>{p++;i++;}//查到尾時(shí),i為字符‘\0’的下標(biāo),p也指向‘\0’。while<*q!='\0'>{q++;x++;}//查找字符串t的長(zhǎng)度x,循環(huán)結(jié)束時(shí)q指向'\0'。for<j=i;j>=pos;j-->{*<p+x>=*p;p--;}//串s的pos后的子串右移,空出串t的位置。q--;//指針q回退到串t的最后一個(gè)字符for<j=1;j<=x;j++>*p--=*q--;//將t串插入到s的pos位置上[算法討論]串s的結(jié)束標(biāo)記<'\0'>