【文章內(nèi)容簡(jiǎn)介】 構(gòu)？為什么？4. 對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說(shuō)明理由。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?6. 假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫出所有可能的出棧序列。7. 什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無(wú)頭結(jié)點(diǎn)的單鏈表LinkList *q,*p。if(Lamp。amp。Lnext){ q=L。 L=Lnext。 p=L。　　　while (pnext) p=pnext?！　? pnext=q。 qnext=NULL。　　}　　return (L)。}四、算法設(shè)計(jì)題1. 設(shè)計(jì)在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法。2. 在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength(L)運(yùn)算。3. 設(shè)計(jì)將帶表頭的鏈表逆置算法。4. 假設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data, next和prior。其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來(lái)，試編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來(lái)。5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫一個(gè)刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。6. 已知線性表的元素是無(wú)序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)一個(gè)刪除表中所有值小于max但大于min的元素的算法。7. 假定用一個(gè)單循環(huán)鏈表來(lái)表示隊(duì)列（也稱為循環(huán)隊(duì)列），該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)隊(duì)首指針，試編寫下列各種運(yùn)算的算法：（1）向循環(huán)鏈隊(duì)列插入一個(gè)元素值為x的結(jié)點(diǎn)；（2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。8. 設(shè)順序表L是一個(gè)遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。習(xí)題2參考答案一、單項(xiàng)選擇題1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A二、填空題1．線性 2．ni+1 3．相鄰 4．前移，前，后5．物理存儲(chǔ)位置，鏈域的指針值 6．前趨，后繼7．順序，鏈接 8．一定，不一定9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)13．棧滿，?？?，m，棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇14．315．O(1)三、簡(jiǎn)答題1．頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2．線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。3．應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4．應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rearnextnext 和 rear, 查找時(shí)間都是O(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6．共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。 一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。 第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。 第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。8．該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題 1．算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)i0或in1時(shí)，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：（3）當(dāng)０in時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：delete(LinkList *q,int i){ //在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn) LinkList *p,*s。 int j。 if(i0) printf(Can39。t delete)。 else if(i= =0) { s=q。 q=qnext。 free(s)。 }else { j=0。 s=q。 while((ji) amp。amp。 (s! = NULL)) { p=s。 s=snext。j++。}if (s= =NULL) printf(Cant39。t delete)。 else { pnext=snext。 free(s)。 } }}2．由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來(lái)數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：int ListLength ( LinkList *L ){ //求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng)　 int len=0?！?ListList *p?！?p=L。　 while ( pnext!=NULL ){ p=pnext?！　　en++?！?}　 return (len)。}3．設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行qnext=s。操作即可，算法描述如下：void invert(LinkList *head){ //逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s。 q=head。 p=headnext。 while (p!=head) //當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置 { s=q。 q=p。 p=pnext。 qnext=s。 } pnext=q。 }4．定義類型LinkList如下：typedef struct node{ int data。 struct node *next,*prior。}LinkList。此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：insert (LinkList *head){ LinkList *p,*s,*q。 p=headnext。 //p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn) while(p!=NULL) { s=head。 // s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn) q=headprior。 //q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn) while((q!=NULL) amp。amp。 (pdataqdata)) //查找插入結(jié)點(diǎn)p的合適的插入位置{ s=q。 q=qprior。 } sprior=p。 pprior=q。 //結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間 p=pnext。}}5．算法描述如下：delete(LinkList *head, int max, int min){ linklist *p, *q。 if (head!=NULL) { q=head。 p=headnext。 while((p!=NULL) amp。amp。 (pdata=min)) { q=p。p=pnext。}while((p!=NULL) amp。amp。 (pdatamax)) p=pnext。 qnext=p。　}}6．算法描述如下：delete(LinkList *head, int max, int min){ LinkList *p,*q。 q=head。 p=headnext。 while (p!=NULL) if((pdata=min) || (pdata=max)) { q=p。 p=pnext。 }else{ qnext=pnext。free(p)。p=qnext。} }7．本題是對(duì)一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：（1）插入（即入隊(duì)）算法：insert(LinkList *rear, elemtype x){ //設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear,x為待插入的元素 LinkList *p。p=(LinkList *)malloc(sizeof(LinkList))。if(rear= =NULL) //如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一個(gè)結(jié)點(diǎn){ rear=p。rearnext=p。 //鏈接成循環(huán)鏈表}else //否則在隊(duì)尾插入p結(jié)點(diǎn) { pnext=rearnext。rearnext=p。 rear=p。}}（2）刪除（即出隊(duì)）算法：delete(LinkList *rear){ //設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif (rear= =NULL) //空隊(duì) printf(underflow\n)。if(rearnext= =rear) //隊(duì)中只有一個(gè)結(jié)點(diǎn)rear=NULL。elserearnext=rearnextnext。 //rearnext指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)}8．只要從終端結(jié)點(diǎn)開始往前找到第一個(gè)比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ){ int i。if ( (*L).len= maxlen){ printf(“overflow)。return(0)。}for ( i=(*L).len 。 i0 amp。amp。 (*L).elem[ i1 ] x 。 i) (*L).elem[ i ]=(*L).elem[ i1 ] 。 // 比較并移動(dòng)元素 (*L).elem[ i ] =x。 (*L).len++。return(1)。} 習(xí)題3一、單項(xiàng)選擇題1. 空串與空格字符組成的串的區(qū)別在于（ ）。 2. 一個(gè)子串在包含它的主串中的位置是指（ ）。3. 下面的說(shuō)法中，只有（ ）是正確的。，則T一定是S的一個(gè)子串4. 兩個(gè)字符串相等的條件是（ ）。