數(shù)據(jù)結(jié)構(gòu)第三章

可編輯數(shù)據(jù)結(jié)構(gòu)第三章精品文檔，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載二、簡(jiǎn)述棧和線性表的區(qū)別。答：線性結(jié)構(gòu)的特點(diǎn)是在數(shù)據(jù)元素的非空有限集中，存在惟一的一個(gè)被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素；存在惟一的一個(gè)被稱(chēng)做“最后一個(gè)”的數(shù)據(jù)元素；除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；；除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短，即對(duì)線性表的數(shù)據(jù)元素不僅可以訪問(wèn)，還可在在任意位置進(jìn)行插入和刪除操作等。棧是一種特殊的線性結(jié)構(gòu)，從數(shù)據(jù)的邏輯結(jié)構(gòu)角度來(lái)看，棧是線性表，從操作的角度來(lái)看，棧的基本操作是線性表操作的子集，是操作受限制的線性表，其特點(diǎn)是棧限定僅在表尾進(jìn)行插入和刪除操作的線性表，它的存取特征是后進(jìn)先出。三、寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類(lèi)型SelemType為char）。Voidmain(){stacks;Charx,y;Initstack(s);x=’c’;y=’k’;Push(s,x);push(s,’a’);push(s,y);Pop(s,x);push(s,’t’);push(s,x);Pop(s,x);push(s,’s’);While(!stackempty(s)){pop(s,y);printf(y);}Printf(x);}輸出結(jié)果：stack四、簡(jiǎn)述以下算法的功能（棧的元素類(lèi)型SelemType為int）。1、statusalgol(stacks){IntI,n,A[255];n=0;while(!stackempty(s)){n++;pop(s,A[n]);}for(i=1;i<=n;i++)push(s,A[i]);}答案：對(duì)棧中元素進(jìn)行反序入棧。2、statusalgo2(stackS,inte){stackT;intd;Initstack(T);While(!stackempty(s)){pop(s,d);If(d!=e)push(T,d);}While(!stackempty(T)){pop(T,d);Push(S,d);數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第1頁(yè)。}數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第1頁(yè)。可編輯精品文檔，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載}答案：利用棧T輔助將棧S中所有值為e的數(shù)據(jù)元素刪除。二十八、．假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫(xiě)相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法?！痉治觥繋ь^結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列如圖3-7所示，僅有隊(duì)尾指針rear，但可通過(guò)rear->next找到頭結(jié)點(diǎn)，再通過(guò)頭結(jié)點(diǎn)找到隊(duì)頭，即rear->next->next。

圖3-7帶頭結(jié)點(diǎn)的循環(huán)鏈表隊(duì)列【算法】①置空隊(duì)LinkListSetNull(){LinkListrear;rear=newLNode;rear->next=rear;returnrear;}②判隊(duì)空intEmpty(LinkListrear){if(rear->next==rear)return1; //若隊(duì)列為空返回1elsereturn0; //否則返回0}③入隊(duì)LinkListENQUEUE(LinkListrear,DataTypex){LinkListp;p=newLinkList;p->data=x;p->next=rear->next; //將p插入到rear->next之后rear->next=p;rear=p;returnrear; //返回新的隊(duì)尾指針}④出隊(duì)LinkListDEQUEUE(LinkListraer,DataType*x){LNode*p,*q;if(rear->next==rear) //若隊(duì)空，則輸出隊(duì)空信息cout<<“EMPTY”;else{q=rear->next;p=q->next;} //否則q指向頭結(jié)點(diǎn)，p指向隊(duì)頭if(p==rear)rear=q; //若隊(duì)中僅有一個(gè)元素，則將rear指向頭結(jié)點(diǎn)q->next=p->next; //將p所指結(jié)點(diǎn)出隊(duì)*x=p->data;deletep; //將對(duì)頭結(jié)點(diǎn)的值賦給形參*x數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第2頁(yè)。returnrear; //數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第2頁(yè)?？删庉嬀肺臋n，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載}二十九、如果希望循環(huán)隊(duì)列中的元素都能得到利用，則需設(shè)置一個(gè)標(biāo)志域tag，并以tag的值為0或1來(lái)區(qū)分，尾指針和頭指針值相同時(shí)的隊(duì)列狀態(tài)是“空”還是“滿”。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的入隊(duì)列和出隊(duì)列的算法。解：StatusEnCyQueue(CyQueue&Q,intx)//帶tag域的循環(huán)隊(duì)列入隊(duì)算法

{

if(Q.front==Q.rear&&Q.tag==1)//tag域的值為0表示"空",1表示"滿"

returnOVERFLOW;

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE;

if(Q.front==Q.rear)Q.tag=1;//隊(duì)列滿

}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)//帶tag域的循環(huán)隊(duì)列出隊(duì)算法

{

if(Q.front==Q.rear&&Q.tag==0)returnINFEASIBLE;

Q.front=(Q.front+1)%MAXSIZE;

x=Q.base[Q.front];

if(Q.front==Q.rear)Q.tag=1;//隊(duì)列空

returnOK;

}//DeCyQueue數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第3頁(yè)。三十、假設(shè)循環(huán)隊(duì)列中只設(shè)rear和length來(lái)分別指示隊(duì)尾元素的位置和隊(duì)中元素的個(gè)數(shù)，試給出判別此循環(huán)隊(duì)列的隊(duì)滿條件，并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法，要求出隊(duì)時(shí)需返回隊(duì)頭元素。

解：

根據(jù)題意，可定義該循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)：

#defineQueueSize100

typedefcharDatatype;//設(shè)元素的類(lèi)型為char型

typedefstruct{

intlength;

intrear;

DatatypeData[QueueSize];

}CirQueue;

CirQueue*Q;

循環(huán)隊(duì)列的隊(duì)滿條件是：Q->length==QueueSize

知道了尾指針和元素個(gè)數(shù)，當(dāng)然就能計(jì)算出隊(duì)頭元素的位置。算法如下：

(1)判斷隊(duì)滿

intFullQueue(CirQueue*Q)

{//判隊(duì)滿,隊(duì)中元素個(gè)數(shù)等于空間大小

returnQ->length==QueueSize;

}

(2)入隊(duì)

voidEnQueue(CirQueue*Q,Datatypex)

{//入隊(duì)

if(FullQueue(Q))

Error("隊(duì)已滿，無(wú)法入隊(duì)");

Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//在循環(huán)意義上的加1

數(shù)據(jù)結(jié)構(gòu)第三章全文共數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第3頁(yè)。數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第4頁(yè)?？删庉嬀肺臋n，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載length++;

}

(3)出隊(duì)

DatatypeDeQueue(CirQueue*Q)

{//出隊(duì)

if(Q->length==0)

Error("隊(duì)已空，無(wú)元素可出隊(duì)");

inttmpfront;//設(shè)一個(gè)臨時(shí)隊(duì)頭指針

tmpfront=(QueueSize+Q->rear-Q->quelen+1)%QueueSize;//計(jì)算頭指針位置

Q->length--;

returnQ->Data[tmpfront];

}三十一、回文是指正讀和反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。解：#include"stdio.h"#definestacksize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;stacknull(seqstack*p){p->top=-1;}Intstackfull(seqstack*p){returnp->top==stacksize-1;}tackempty(seqstack*p){if(p->top==-1)return1;elsereturn0;}push(seqstack*p,datatypex){if(stackfull(p)){printf("itiswrong.");exit(0);}數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第5頁(yè)。數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第5頁(yè)?？删庉嬀肺臋n，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載p->data[p->top]=x;}pop(seqstack*p){if(stackempty(p)){printf("error");exit(0);}return(p->data[p->top--]);}main(){chartemp;intn,i,length=0;seqstackl;stacknull(&l);clrscr();printf("thetopis%d",l.top);printf("\ninputchar:");printf("\ninputn:");scanf("%d\n",&n);for(i=0;i<n;i++){scanf("%c",&l.data[i]);length++;}printf("\n");length=length-1;printf("\nthelengthis%d",length);for(i=0;i<(length/2);i++){ push(&l,l.data[i]);}if(length%2==0){for(i;i<length;i++)if(temp=pop(&l)!=l.data[i]){printf("\nitiserror.");exit(0);}printf("\nitistrue.");}else{for(i;i<length-1;i++)if(temp=pop(&l)!=l.data[i+1])數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第6頁(yè)。數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第6頁(yè)?？删庉嬀肺臋n，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載printf("\nitistrue.");}補(bǔ)充題：一、設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問(wèn)題：

(1)若入、出棧次序?yàn)镻ush(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop()表示出棧)?

(2)能否得到出棧序列1423和1432?并說(shuō)明為什么不能得到或者如何得到。

(3)請(qǐng)分析1，2，3，4的24種排列中，哪些序列是可以通過(guò)相應(yīng)的入出棧操作得到的。

答：

(1)出棧序列為：1324

(2)不能得到1423序列。因?yàn)橐玫?4的出棧序列，則應(yīng)做Push(1),Pop(),Push(2),Push

(3),Push(4),Pop()。這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2，3，4的24種排列中，可通過(guò)相應(yīng)入出棧操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321

不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312二、鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?

答：

鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。三、循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么?如何判別它的空和滿?

答：

循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的"空"或"滿"不能以頭尾指針是否相等來(lái)確定，一般是通過(guò)以下幾種方法：一是另設(shè)一布爾變量來(lái)區(qū)別隊(duì)列的空和滿。二是少用一個(gè)元素的空間,每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第7頁(yè)。四、設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何?若只設(shè)尾指針呢?

答數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第7頁(yè)。可編輯精品文檔，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載數(shù)據(jù)結(jié)構(gòu)第三章全文共10頁(yè)，當(dāng)前為第8頁(yè)。五、指出下述程序段的功能是什么?

(1)voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr[i]);

}//Demo1

(2)SeqStackS1,S2,tmp;

DataTypex;

...//假設(shè)棧tmp和S2已做過(guò)初始化

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2,x);

}

(3)voidDemo2(SeqStack*S,intm)

{//設(shè)DataType為int型

SeqStackT;inti;

InitStack(&T);

while(!StackEmpty(S))

if((i=Pop(S))!=m)Push(&T,i);

while(!StackEmpty(&T))

{

i=Pop(&T);Push(S,i);

}

}

(4)voidDemo3(CirQueue*Q)

{//設(shè)DataType為int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(&S,x);}