深圳大型網(wǎng)站建設(shè)服務(wù)公司汕頭seo外包機(jī)構(gòu)
第三章
【3.1】
03、
-
假設(shè)以
I
和O
分別表示入棧和出操作。棧的初態(tài)和終態(tài)均為空,入棧和出棧的操作序列可表示為僅由I
和O
組成的序列,可以操作的序列稱為合法序列,否則稱為非法序列。如
IOIIOIOO
和IIIOOIOO
是合法的,而IOOIOIIO
和IIIOIOIO
是不合法的。通過分析,寫出一個(gè)算法,判定所給的操作序列是否合法。若合法,返回true,否則返回 false(假定被判定的操作序列已存入一維數(shù)組中)
個(gè)人理解:
就構(gòu)造一個(gè)棧S,然后將這個(gè)序列進(jìn)行處理,其中
I
表示入棧、O
表示出棧,直接對棧S進(jìn)行Push和Pop操作,有錯(cuò)誤就報(bào)錯(cuò),沒錯(cuò)誤就表示該序列合法,即可。
答案好像并沒有創(chuàng)建棧,也沒有執(zhí)行Push、Pop的操作。而是直接對序列進(jìn)行分析,只作了數(shù)學(xué)上的判定。
算法思想:
??掃描該序列,每掃描至任意一個(gè)位置均需檢查出棧次數(shù)(即“O”
的個(gè)數(shù))是否小于等于入棧次數(shù)(“I”的個(gè)數(shù)
),若大于則為非法序列。掃描結(jié)束后,再判斷入棧和出棧次數(shù)是否相等,若不相等則也不合法。
bool Judge(char A[]) {int i=0;int j=0; //j表示字母I的個(gè)數(shù)int k=0; //k表示字母O的個(gè)數(shù)while(A[i]!='\0') { //對字符串的遍歷操作if(A[i]=='I')j++;if(A[i]=='O')k++;if(k>j) {printf("序列非法\n");return false;}}if(j!=k) {printf("序列非法\n");return false;}else {printf("序列合法\n");return true;}}
另一種算法思想:
??入棧后,棧內(nèi)元素個(gè)數(shù)增加1個(gè);出棧后,棧內(nèi)元素個(gè)數(shù)減少1個(gè)。因此可將判定一組出入棧序列是否合法轉(zhuǎn)化為一組由+1
和-1
組成的序列,它的任意前綴子序列的累加和不能小于0(每執(zhí)行一次出?;蛉霔2僮骱罅⒓磁袛?#xff09;則合法,否則非法。此外,整個(gè)序列的累加和必須等于0。
思考:
??這個(gè)問題是否和括號匹配問題一樣?——感覺好像是沒啥區(qū)別。
04、
-
設(shè)單鏈表的表頭指針為
L
,結(jié)點(diǎn)結(jié)構(gòu)由data
和next
兩個(gè)域構(gòu)成,其中data
域?yàn)樽址?。試設(shè)計(jì)算法判斷該鏈表的全部n
個(gè)字符是否中心對稱。例如
xyx
、xyyx
都是中心對稱。
個(gè)人理解:
第二章單鏈表部分的算法應(yīng)該已經(jīng)解決過這個(gè)問題了。
我大概有三種思路:
1)將單鏈表的后半段原地逆置,之后使用兩個(gè)間距為k(k為表長的一半)的指針同步遍歷比較。
分析:原地逆置但鏈表需要 O ( n ) O(n) O(n),兩指針同步遍歷需要 O ( n ) O(n) O(n)。因此時(shí)間復(fù)雜度為 O ( n ) O(n) O(n),空間復(fù)雜度為 O ( 1 ) O(1) O(1)。
2)把單鏈表中的元素復(fù)制到數(shù)組里,然后用數(shù)組直接判斷中心對稱。
分析:復(fù)制需要 O ( n ) O(n) O(n),數(shù)組判斷中心對稱需要 O ( n ) O(n) O(n)。時(shí)間復(fù)雜度為 O ( n ) O(n) O(n),空間復(fù)雜度為 O ( n ) O(n) O(n)。
3)從前往后把單鏈表中的各個(gè)結(jié)點(diǎn)元素依次入棧。之后將棧中元素一一出棧,并與單鏈表中從前往后元素進(jìn)行比較。(如果知道鏈表的表長,只入棧前半個(gè)表的元素即可,一一出棧并與后半個(gè)表的元素比較)
分析:單鏈表元素一一入棧需要 O ( n ) O(n) O(n),一一出棧再進(jìn)行比較需要 O ( n ) O(n) O(n)。時(shí)間復(fù)雜度為 O ( n ) O(n) O(n),空間復(fù)雜度為 O ( n ) O(n) O(n)。
05、
- 設(shè)有兩個(gè)棧
s1、s2
都采用順序棧方式,并共享一個(gè)存儲區(qū)[0,...,maxsize-1]
,為了盡量利用空間,減少溢出的可能,可采用棧頂相向、迎面增長的存儲方式。試設(shè)計(jì)s1、s2
有關(guān)入棧和出棧的操作算法。
個(gè)人理解:
就是考察共享?xiàng)5娜霔?、出棧具體操作上的細(xì)節(jié)。(不難,但是比較重要,各方面都要想清楚)
那就是棧
s1
初始棧頂指針為-1
,棧s2
初始棧頂指針為maxsize
,對于兩個(gè)棧而言,入棧操作都是先將指針移動(dòng)一位(s1是往大了加1,s2是往小了減1的區(qū)別),然后再賦值。出棧操作反之,先取出當(dāng)前棧頂指針的元素,然后棧頂指針移動(dòng)一位(與入棧相反)。此外還有判斷???、棧滿的問題,??盏膯栴}好說,棧滿的問題就是根據(jù)s2的棧頂指針
是否和s1的棧頂指針
相鄰即可。
分析:
??兩個(gè)棧共享向量空間,將兩個(gè)棧的棧底設(shè)在向量兩端。初始時(shí),s1
棧頂指針為-1
,s2
棧頂指針為maxsize
。當(dāng)兩個(gè)棧頂指針相鄰時(shí)判定為棧滿。兩個(gè)棧頂相向、迎面增長,棧頂指針指向棧頂元素。
【注意】
1)主要就是注意一下兩個(gè)棧各自在入棧、出棧時(shí),棧頂指針是如何變化的。對于s1而言,它是一個(gè)傳統(tǒng)意義上的棧,而對于s2而言,它的操作大約是要反過來一下的。
2)對于所有入棧、出棧操作,都要時(shí)刻牢記**“入棧判滿?出棧判空?”**的檢查。
(0)如下定義共享?xiàng)5臄?shù)據(jù)結(jié)構(gòu):
(當(dāng)然,不這樣定義,也無所謂。直接定義一個(gè)數(shù)組,然后定義兩個(gè)變量指向棧頂位置也一樣)
/* 共享?xiàng)5慕Y(jié)構(gòu)定義 */
#define maxsize 100
typedef struct {int stack[maxsize]; //??臻gint top[2]; //存放兩個(gè)棧頂指針
}stk;stk s; //定義棧s為上述結(jié)構(gòu)類型的變量,而且為全局變量
s.top[0] = -1;
s.top[1] = maxsize; //初始化兩個(gè)棧頂指針的值
(1)入棧操作
int push(int i, int x) {//入棧操作,i為棧號,當(dāng)i=0時(shí)表示是s1執(zhí)行入棧,當(dāng)i=1時(shí)表示s2執(zhí)行入棧//x是入棧元素//入棧成功返回1,失敗返回0if(i<0 || i>1) {printf("棧號輸入不對");exit(0);}if(s.top[1]-s.top[0] == 1) {printf("棧已滿\n");return 0;}if(i==0) {s.stack[++s.top[0]] = x;return 1;}if(i==1) {s.stack[--s.top[1]] = x;return 1;}
}
(2)出棧操作
int pop(int i) {//出棧操作,i為棧號,當(dāng)i=0時(shí)表示是s1執(zhí)行出棧,當(dāng)i=1時(shí)表示s2執(zhí)行出棧//出棧成功,函數(shù)返回值為出棧的元素值;失敗則返回-1if(i<0 || i>1) {printf("棧號輸入錯(cuò)誤");exit(0);}if(i==0) {if(s.top[0] == -1) {printf("棧s1已為空,無法出棧");return -1;} elsereturn s.stack[s.top[0]--];}if(i==1) {if(s.top[1] == maxsize) {printf("棧s2已為空,無法出棧");return -1;} else return s.stack[s.top[1]++];}
}
【3.2】
01、
- 若希望循環(huán)隊(duì)列中的元素都能得到利用,則需設(shè)置一個(gè)標(biāo)志域 tag,并以 tag 的值為0或1來區(qū)分隊(duì)頭指針 front 和隊(duì)尾指針 rear 相同時(shí)的隊(duì)列狀態(tài)是“空”還是“滿”試編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)和出隊(duì)算法。
個(gè)人理解:
既然隊(duì)空、隊(duì)滿的依據(jù)都是
front==rear
,只不過隊(duì)空時(shí)tag==0
,隊(duì)滿時(shí)tag==1
。那么,首先,隊(duì)列為空時(shí),初始化為
tag=0
,之后不斷入隊(duì)、出隊(duì)操作。若最后一次操作執(zhí)行入隊(duì),并使得隊(duì)滿,則tag=1
;若最后一次操作執(zhí)行出隊(duì),并使得隊(duì)空,則tag=0
。咋樣在隊(duì)滿的時(shí)候再檢查一下上次操作的性質(zhì)?——沒必要。我們每次執(zhí)行入隊(duì),都設(shè)
tag=1
,每次執(zhí)行出隊(duì),都同時(shí)設(shè)tag=0
,這樣,如果發(fā)現(xiàn)front==rear
了,同時(shí)就再去看看tag
是幾就行了。沒那么復(fù)雜。
算法思想:
??在循環(huán)隊(duì)列的類型結(jié)構(gòu)中,增設(shè)一個(gè)tag
的整型變量,進(jìn)隊(duì)時(shí)置tag為1,出隊(duì)時(shí)置tag為0(因?yàn)橹挥腥腙?duì)操作可能導(dǎo)致隊(duì)滿,也只有出隊(duì)操作可能導(dǎo)致隊(duì)空)。隊(duì)列Q初始時(shí),置tag=0, front=rear=0
。這樣,隊(duì)列的4要素如下:
隊(duì)空條件:Q.front==Q.rear && Q.tag==0
隊(duì)滿條件:Q.front==Q.rear && Q.tag==1
進(jìn)隊(duì)操作:Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MaxSize; Q.tag=1
出隊(duì)操作:x=Q.data[Q.rear]; Q.front=(Q.front+1)%MaxSize; Q.tag=0
1)入隊(duì)算法
int EnQueue(SqQueue &Q, int x) {if(Q.front==Q.rear && Q.tag==1)return 0; //隊(duì)滿Q.data[Q.rear] = x;Q.rear = (Q.rear+1)%MaxSize;Q.tag = 1; //可能隊(duì)滿return 1;
}
2)出隊(duì)算法
int DeQueue(SqQueue &Q, int &x) {if(Q.front==Q.rear && Q.tag==0)return 0; //隊(duì)空x = Q.data[Q.front];Q.front = (Q.front+1)%MaxSize;Q.tag = 0; //可能隊(duì)空return 1;
}
02、
- Q 是一個(gè)隊(duì)列,S 是一個(gè)空棧,實(shí)現(xiàn)將隊(duì)列中的元素逆置的算法。
個(gè)人理解:
很簡單了。隊(duì)列元素依次出隊(duì),并依次入棧。最后棧中元素依次全部出棧即可。不是光輸出元素值,那就再入回到隊(duì)列中去。
算法思想:
??這個(gè)問題主要考察對于隊(duì)列和棧的特性的理解。由于僅對隊(duì)列進(jìn)行一系列操作不可能將其中的元素逆置,而??梢詫⑷霔5脑啬嫘蛱崛〕鰜?#xff0c;因此我們可以讓隊(duì)列中的元素逐個(gè)地出隊(duì)、入棧;全部入棧后再逐個(gè)出棧、入隊(duì)列。
void Inverser(Stack &S, Queue &Q) {//本算法實(shí)現(xiàn)將隊(duì)列中的元素逆置while(!QueueEmpty(Q)) {x = DeQueue(Q); //隊(duì)列中全部元素依次出隊(duì)Push(S, x); //元素依次入棧}while(!StackEmpty(S)) {Pop(S, x); //棧中全部元素依次出棧EnQueue(Q, x); //再入隊(duì)}
}
03、
- 利用兩個(gè)棧 S1 和 S2 來模擬一個(gè)隊(duì)列,已知棧的 4 個(gè)運(yùn)算定義如下:
Push(S, x); //元素x入棧S
Pop(S, x); //S出棧并將出棧的值賦給x
StackEmpty(S); //判斷棧是否為空
StackOverflow(S); //判斷棧是否滿
如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的 3 個(gè)運(yùn)算(形參由讀者根據(jù)要求自己設(shè)計(jì))?
Enqueue;
Dequeue;
QueueEmpty;
有兩個(gè)棧,S1和S2。兩種棧的操作:入棧、出棧,此外還可以判棧空、判棧滿。
以此來完成:入隊(duì)、出隊(duì)、判隊(duì)空,的操作。
什么叫實(shí)現(xiàn)隊(duì)列的入隊(duì)、出隊(duì),就是,必須得是先進(jìn)先出的運(yùn)算邏輯才叫隊(duì)列。
棧是后進(jìn)先出的邏輯,怎么達(dá)到先進(jìn)先出的效果?——兩個(gè)棧配合使用。
讓序列依次入棧到S1中,例如
abcd
進(jìn)入S1:[a b c d]
此時(shí)S1出棧,肯定是
d c b a
,這肯定達(dá)不到隊(duì)列的要求;但是可以把S1的出棧序列再次入棧到S2中,進(jìn)入S2:[d c b a]
。之后S2再出棧,就能得到a b c d
。從而達(dá)到隊(duì)列的效果。但是好像有個(gè)問題:如果是一個(gè)元素、一個(gè)元素的這樣操作的話,例如把
a
入棧S1后,立馬出棧,再入棧到S2中,這樣,元素a
和直接入棧沒區(qū)別,最后也不是隊(duì)列的效果。必須一次性把所需序列全部入棧S1、再出棧S1、再入棧到S2中,才有效果。但是對于單個(gè)元素、單個(gè)元素這種的,就不能這樣做。看下答案怎么說。
算法思想:
??利用兩個(gè)棧 S1 和 S2 來模擬一個(gè)隊(duì)列,當(dāng)需要向隊(duì)列中插入一個(gè)元素時(shí),用 S1 來存放已輸入的元素,即 S1 執(zhí)行入棧操作。當(dāng)需要出隊(duì)時(shí),則對S2執(zhí)行出棧操作;注意,此時(shí)需要判斷S2是否為空,若為空,則需要將S1先出棧并入棧到S2;若S2不為空則直接執(zhí)行S2出棧即可??偨Y(jié)如下兩點(diǎn):
(主要要搞清楚到底啥叫出隊(duì),啥叫入隊(duì)。不是說入隊(duì)就是abc
進(jìn)入,出隊(duì)就是cba
出來。入隊(duì)、出隊(duì)都只是一個(gè)元素的事。)
1)對S2的出棧操作,用作出隊(duì)。若S2為空,則先將S1中的所有元素送入S2。
2)對S1的入棧操作,用作入隊(duì)。若S1滿,必須先保證S2為空,才能將S1中的元素全部插入S2中。
入隊(duì)算法:
int EnQueue(Stack &S1, Stack &S2, int e) {if(!StackOverflow(S1)) {Push(S1, e);return 1;}if(StackOverflow(S1) && !StackEmpty(S2)) {printf("隊(duì)列滿");return 0;}if(StackOverflow(S1) && StackEmpty(S2)) {while(!StackEmpty(S1)) {Pop(S1, x);Push(S2, x);}}Push(S1, e);return 1;
}
出隊(duì)算法:
void DeQueue(Stack &S1, Stack &S2, int &x) {if(!StackEmpty(S2))Pop(S2, x);else if(StackEmpty(S1))printf("隊(duì)列為空"); //S2為空,此時(shí)去S1找,發(fā)現(xiàn)S1也為空else {while(!StackEmpty(S1)) { //S2為空,如果S1里有,就先運(yùn)過來Pop(S1, x);Push(S2, x);}Pop(S2, x); //都運(yùn)過來之后,S2出棧一下}
}
判斷隊(duì)列為空的算法:
int QueueEmpty(Stack S1, Stack S2) {if(StackEmpty(S1) && StackEmpty(S2))return 1;elsereturn 0;
}
04、
[2019 統(tǒng)考真題]
-
請?jiān)O(shè)計(jì)一個(gè)隊(duì)列,要求滿足:①初始時(shí)隊(duì)列為空;②入隊(duì)時(shí),允許增加隊(duì)列占用空間;③出隊(duì)后,出隊(duì)元素所占用的空間可重復(fù)使用,即整個(gè)隊(duì)列所占用的空間只增不減;④入隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度始終保持為 0(1)。請回答下列問題:
1)該隊(duì)列是應(yīng)選擇鏈?zhǔn)酱鎯Y(jié)構(gòu),還是應(yīng)選擇順序存儲結(jié)構(gòu)?
2)畫出隊(duì)列的初始狀態(tài),并給出判斷隊(duì)空和隊(duì)滿的條件。
3)畫出第一個(gè)元素入隊(duì)后的隊(duì)列狀態(tài)。
4)給出入隊(duì)操作和出隊(duì)操作的基本過程。
根據(jù)題意,應(yīng)該是要使用鏈?zhǔn)疥?duì)列。主要是因?yàn)槿腙?duì)時(shí)允許增加隊(duì)列占用空間這一點(diǎn)。如果是順序存儲空間會比較難實(shí)現(xiàn)。鏈表若想增加空間,則插入一個(gè)新結(jié)點(diǎn)即可。
此外,由于出隊(duì)元素所占空間可以重復(fù)使用,因此應(yīng)該還是個(gè)循環(huán)隊(duì)列。
對于單鏈表存放隊(duì)列而言,通常單鏈表表頭對應(yīng)的是隊(duì)頭,單鏈表表尾對應(yīng)的是隊(duì)尾??芍?#xff0c;出隊(duì)操作在隊(duì)頭完成,入隊(duì)操作在隊(duì)尾完成。
綜上,大概使用一個(gè)循環(huán)單鏈表(可以帶上一個(gè)頭結(jié)點(diǎn),效果更好了),作為該循環(huán)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)即可實(shí)現(xiàn)題目要求。
個(gè)人理解:
1)應(yīng)選擇鏈?zhǔn)酱鎯Y(jié)構(gòu)。而且選用帶頭、尾指針的循環(huán)單鏈表比較合適。
2)初始狀態(tài)為僅有一個(gè)頭結(jié)點(diǎn)
L
,此時(shí)Q->front=Q->rear=NULL
。隊(duì)空判斷條件為Q->front == Q->rear
;隊(duì)滿判斷條件為Q->rear->next = Q->front
。3)含有一個(gè)頭結(jié)點(diǎn)、一個(gè)成員結(jié)點(diǎn)的循環(huán)單鏈表。
4)入隊(duì)操作:若隊(duì)列未滿,則尾指針后移一位、元素賦值到尾指針?biāo)附Y(jié)點(diǎn)上;若隊(duì)列已滿,則建立一個(gè)新結(jié)點(diǎn),將新結(jié)點(diǎn)插入到尾指針后面。
出隊(duì)操作:若隊(duì)列非空,則輸出頭指針?biāo)冈?#xff0c;并將頭指針后移一位。若隊(duì)列已經(jīng)為空,則無法出隊(duì)。
下面看下答案。
答案:
1)采用鏈?zhǔn)酱鎯Y(jié)構(gòu),循環(huán)單鏈表,即可滿足四點(diǎn)要求。而順序存儲結(jié)構(gòu)無法滿足要求②。
2)可以參考循環(huán)隊(duì)列的思維。不過此處由于是鏈?zhǔn)酱鎯?#xff0c;因此入隊(duì)時(shí)空間不夠還可以動(dòng)態(tài)增加。同樣地,循環(huán)鏈?zhǔn)疥?duì)列也要區(qū)分隊(duì)滿、隊(duì)空的情況,這里參考循環(huán)隊(duì)列犧牲一個(gè)存儲單元的思想來做分析。初始時(shí),創(chuàng)建只有一個(gè)空閑結(jié)點(diǎn)的循環(huán)單鏈表,頭指針front和尾指針rear均指向空閑節(jié)點(diǎn),如下圖所示。
隊(duì)空的判定條件:front == rear
隊(duì)滿的判定條件:front == rear->next
不要用死板的眼光看待問題??催@里可能會覺得:現(xiàn)在不是“隊(duì)空”嗎,什么也沒有,而此時(shí)
front == rear->next
啊,這隊(duì)空和隊(duì)滿怎么判定條件一樣?人家這就是隊(duì)滿。現(xiàn)在隊(duì)列的實(shí)際空間為0,若想要入隊(duì)一個(gè)元素,那就是隊(duì)滿的情形。同時(shí),若想要出隊(duì)一個(gè)元素,那就是隊(duì)空的情形。
這個(gè)地方,鏈?zhǔn)疥?duì)列要和順序循環(huán)隊(duì)列區(qū)分清楚,不要混為一談。
3)插入第一個(gè)元素后的狀態(tài)如下圖所示:
個(gè)人認(rèn)為就在頭結(jié)點(diǎn)的后面做頭插即可。
4)操作的基本過程:
(他這個(gè)操作是根據(jù)他第(3)問畫的圖那樣來弄的;如果畫的圖不一樣,操作相應(yīng)也有區(qū)別)
1.入隊(duì)操作
若(front == rear->next) //隊(duì)滿則 在rear后面插入一個(gè)新的空閑結(jié)點(diǎn);
入隊(duì)元素保存到rear所指結(jié)點(diǎn)中;
rear = rear->next;
return;
2.出隊(duì)操作
若(front == rear) //隊(duì)空則 出隊(duì)失敗,返回;
取 front所指結(jié)點(diǎn)中的元素e;
front = front->next;
return e;