數(shù)據(jù)結構第三章

可編輯數(shù)據(jù)結構第三章精品文檔，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載二、簡述棧和線性表的區(qū)別。答：線性結構的特點是在數(shù)據(jù)元素的非空有限集中，存在惟一的一個被稱為“第一個”的數(shù)據(jù)元素；存在惟一的一個被稱做“最后一個”的數(shù)據(jù)元素；除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅；；除最后一個之外，集合中每個數(shù)據(jù)元素均只有一個后繼。線性表是最常用且最簡單的一種數(shù)據(jù)結構。一個線性表是n個數(shù)據(jù)元素的有限序列。線性表是一個相當靈活的數(shù)據(jù)結構，它的長度可根據(jù)需要增長或縮短，即對線性表的數(shù)據(jù)元素不僅可以訪問，還可在在任意位置進行插入和刪除操作等。棧是一種特殊的線性結構，從數(shù)據(jù)的邏輯結構角度來看，棧是線性表，從操作的角度來看，棧的基本操作是線性表操作的子集，是操作受限制的線性表，其特點是棧限定僅在表尾進行插入和刪除操作的線性表，它的存取特征是后進先出。三、寫出下列程序段的輸出結果（棧的元素類型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);}輸出結果：stack四、簡述以下算法的功能（棧的元素類型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]);}答案：對棧中元素進行反序入棧。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ù)結構第三章全文共10頁，當前為第1頁。}數(shù)據(jù)結構第三章全文共10頁，當前為第1頁。可編輯精品文檔，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載}答案：利用棧T輔助將棧S中所有值為e的數(shù)據(jù)元素刪除。二十八、．假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素結點（注意不設頭指針），試編寫相應的置空隊、判隊空、入隊和出隊等算法?！痉治觥繋ь^結點的循環(huán)鏈表表示的隊列如圖3-7所示，僅有隊尾指針rear，但可通過rear->next找到頭結點，再通過頭結點找到隊頭，即rear->next->next。

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

{

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;//隊列滿

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

{

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;//隊列空

returnOK;

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

解：

根據(jù)題意，可定義該循環(huán)隊列的存儲結構：

#defineQueueSize100

typedefcharDatatype;//設元素的類型為char型

typedefstruct{

intlength;

intrear;

DatatypeData[QueueSize];

}CirQueue;

CirQueue*Q;

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

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

(1)判斷隊滿

intFullQueue(CirQueue*Q)

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

returnQ->length==QueueSize;

}

(2)入隊

voidEnQueue(CirQueue*Q,Datatypex)

{//入隊

if(FullQueue(Q))

Error("隊已滿，無法入隊");

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

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

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

}

(3)出隊

DatatypeDeQueue(CirQueue*Q)

{//出隊

if(Q->length==0)

Error("隊已空，無元素可出隊");

inttmpfront;//設一個臨時隊頭指針

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

Q->length--;

returnQ->Data[tmpfront];

}三十一、回文是指正讀和反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。解：#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ù)結構第三章全文共10頁，當前為第5頁。數(shù)據(jù)結構第三章全文共10頁，當前為第5頁。可編輯精品文檔，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載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ù)結構第三章全文共10頁，當前為第6頁。數(shù)據(jù)結構第三章全文共10頁，當前為第6頁?？删庉嬀肺臋n，歡迎下載精品文檔，歡迎下載可編輯精品文檔，歡迎下載printf("\nitistrue.");}補充題：一、設將整數(shù)1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：

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

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

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

答：

(1)出棧序列為：1324

(2)不能得到1423序列。因為要得到14的出棧序列，則應做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種排列中，可通過相應入出棧操作得到的序列是：

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

不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312二、鏈棧中為何不設置頭結點?

答：

鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。三、循環(huán)隊列的優(yōu)點是什么?如何判別它的空和滿?

答：

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

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

(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;

...//假設棧tmp和S2已做過初始化

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)

{//設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)

{//設DataType為int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

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