【文章內(nèi)容簡(jiǎn)介】 +。return(0)。}/**/int delet_char(char X) /* 刪除元素X，注意保存X的前趨元素指針！ */{ p=head。if(headdata==X){head=headlink。free(p)。}else{ while((pdata!=X)amp。amp。(plink!=NULL)) {q=p。 p=plink。}if(pdata==X) { qlink=plink。 free(p)。 } else return(1)。}L。return(0)。}/**/void main(void) /*字母線性表的生成和輸出*/{ L=26。 build()。display()。printf(insert return value=%d\n,insert_char(39。L39。,39。W39。))。display()。printf(delete return value=%d\n,delet_char(39。z39。))。display()。}附：屏幕上顯示的執(zhí)行結(jié)果是：a b c d e f g h i j k l m n o p q r s t u v w x y zinsert return value=0a b c d 9 e f g h i j k l m n o p q r s t u v w x y z Ldelete return value=0a b c d e f g h i j k l m n o p q r s t u v w x y L0301陳建武修改意見(jiàn)：一. display()函數(shù)代碼可優(yōu)化為四行void display() /*字母鏈表的輸出*/{p=head。while (plink!=NULL)//改為while(p),因?yàn)楫?dāng)p指向尾結(jié)點(diǎn)時(shí),p不為null,條件成立循環(huán), //printf(),然后p被賦值為null,此時(shí)循環(huán)條件不符退出,正好.{ printf(%c,pdata)。p=plink。 }printf(%c\n,pdata)。 //用while(p),此行可刪} insert_char(char X,char Y) ,若用帶頭結(jié)點(diǎn)的鏈表,代碼可減為10行我的程序如下(若參數(shù)沒(méi)有slist p,代碼要多一行,讓q指向頭指針)void InsertFind(slist p,char insertchar,char insertpos)//字母insertpos前插入字母insertchar{ slist pprior,newnode。 //newnode新結(jié)點(diǎn),pprior為插入位置結(jié)點(diǎn)的直接前驅(qū) newnode = new liuyu。 //為新結(jié)點(diǎn)分配內(nèi)存 newnodedata = insertchar。 //對(duì)結(jié)點(diǎn)數(shù)據(jù)域初始化 while(p) //當(dāng)p指向尾結(jié)點(diǎn)時(shí)最后一次循環(huán) { pprior = p。 //pprior從頭指針開(kāi)始,指向p的直接前驅(qū) p = pnext。 //p從首元結(jié)點(diǎn)開(kāi)始,不斷前移 ,直至最后,p為null if(pamp。amp。(pdata == insertpos)) //當(dāng)p為null或者結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)樗迦氲淖帜? break。 //則退出循環(huán) } newnodenext = ppriornext。 //在找到的位置前插入 ppriornext = newnode。 }對(duì)刪除結(jié)點(diǎn)的操作,若有頭結(jié)點(diǎn),同樣可以減少代碼,由此可見(jiàn)創(chuàng)建一個(gè)頭結(jié)點(diǎn)對(duì)簡(jiǎn)化程序有很大的幫助.上面的觀點(diǎn),僅供參考,不對(duì)之處,請(qǐng)指教!第3章 棧和隊(duì)列 自測(cè)卷答案 姓名 班級(jí) 題號(hào)一二三四五六總分題分151020202015100得分一、填空題（每空1分，共15分）1. 【李春葆】向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對(duì)于棧只能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。3. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。4. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 前一個(gè) 位置。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n1 個(gè)元素。6. 向棧中壓入元素的操作是先 移動(dòng)棧頂指針 ，后 存入元素 。7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先 移動(dòng)隊(duì)首指針 ，后 取出元素 。8. 〖00年統(tǒng)考題〗帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于 0 。L=head頭結(jié)點(diǎn)R=headhead解：二、判斷正誤（判斷下列概念的正確性，并作出簡(jiǎn)要的說(shuō)明。）（每小題1分，共10分）（ ）1. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。（ ）2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。 錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。（ √ ）3. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（ √ ）4. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（ ）5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。（ ）6. 棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（ √ ）7. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。 （ √ ）8. 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 （ ）9. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 錯(cuò)，后半句不對(duì)。（ ）10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 錯(cuò)，有可能。三、單項(xiàng)選擇題（每小題1分，共20分）（ B ）1. 〖00年元月統(tǒng)考題〗棧中元素的進(jìn)出原則是 Ａ．先進(jìn)先出 Ｂ．后進(jìn)先出 Ｃ．?？談t進(jìn) Ｄ．棧滿則出（ C ）2. 〖李春葆〗若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為 Ａ．i Ｂ．n=i Ｃ．ni+1 Ｄ．不確定解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的，那么輸入順序必定是1，2，3，…，n，則出棧的序列是n，…，3，2，1。（ B ）3. 〖李春葆〗判定一個(gè)棧ST（最多元素為m0）為空的條件是 Ａ．STtop0 Ｂ．STtop=0 Ｃ．STtopm0 Ｄ．STtop=m0（ B ）4. 〖李春葆〗判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 Ａ．QUrear － QUfront = = m0 Ｂ．QUrear － QUfront －1= = m0 Ｃ．QUfront = = QUrear Ｄ．QUfront = = QUrear+1（ D ）5．?dāng)?shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素的公式為（Ａ）r－f。 （Ｂ）（n＋f－r）% n。 （Ｃ）n＋r－f。 （Ｄ）（n＋r－f）% n6. 【98初程P71】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素aaa3和a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按aaaa4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案：A～D：①a1 ②a2 ③ a3 ④a4E： ①1 ②2 ③ 3 ④ 0答：ABCDE＝2, 4, 1, 2, 27. 【94初程P75】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A[1,…,n]來(lái)表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值 B ；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)棧空時(shí)，有輸入序列a，b，c，經(jīng)過(guò)PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： ① 先進(jìn)先出 ②后進(jìn)先出 ③進(jìn)優(yōu)于出 ④出優(yōu)于進(jìn) ⑤ 隨機(jī)進(jìn)出B，C： ① 加1 ②減1 ③不變 ④清0 ⑤ 加2 ⑥減2D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,cE：① n+1 ②n+2 ③ n ④ n1 ⑤ n2答案：ABCDE=2, 2, 1, 6, 4注意，向地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8. 【91初程P77】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B：①空 ② 滿 ③ 上溢 ④ 下溢C： ①n1 ② n ③ n+1 ④ n/2D： ① 長(zhǎng)度 ②深度 ③ 棧頂 ④ 棧底E：①兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn) ②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn) ③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇 ④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE＝2, 1, 2, 4, 3四、簡(jiǎn)答題（每小題4分，共20分）1. 【①①】說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。② 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2. 【統(tǒng)考書(shū)P60 411，①】設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫(xiě)出這四輛列車開(kāi)出車站的所有可能的順序。劉答：至少有14種。① 全進(jìn)之后再出情況，只有1種：4，3，2，1② 進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4③ 進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4④ 進(jìn)1個(gè)之后再出的情況，有5種