《C語(yǔ)言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《C語(yǔ)言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社答案.doc（83頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第1章 緒論 一、基礎(chǔ)知識(shí)題 1. 簡(jiǎn)述下列概念 數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)，邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，算法。 【解答】數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。 數(shù)據(jù)類型是對(duì)數(shù)據(jù)的取值范圍、數(shù)據(jù)元素之間的結(jié)構(gòu)以及允許施加操作的一種總體描述。每一種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言都定義有自己的數(shù)據(jù)類型。 “數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語(yǔ)有兩種含義，一是作為一門課程的名稱；二是作為一個(gè)科學(xué)的概念。作為科學(xué)概念，目前尚無(wú)公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個(gè)方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，三是對(duì)數(shù)據(jù)進(jìn)行的操作（運(yùn)算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡(jiǎn)化情況。 數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運(yùn)算是對(duì)數(shù)據(jù)定義的一組操作，運(yùn)算是定義在邏輯結(jié)構(gòu)上的，和存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，而運(yùn)算的實(shí)現(xiàn)則依賴于存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)，又稱存儲(chǔ)結(jié)構(gòu)。是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像，包括數(shù)據(jù)元素的表示和關(guān)系的表示。邏輯結(jié)構(gòu)與計(jì)算機(jī)無(wú)關(guān)。 算法是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法應(yīng)該具有下列特性：有窮性、確定性、可行性、輸入和輸出。 2. 數(shù)據(jù)的邏輯結(jié)構(gòu)分哪幾種，為什么說(shuō)邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面？ 【解答】數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（也可以分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形即網(wǎng)狀結(jié)構(gòu)）。 邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種“本質(zhì)性”的東西： （1）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)。 （2）邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)。 （3）邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個(gè)數(shù)無(wú)關(guān)。 3. 試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三方面的內(nèi)容。 【解答】學(xué)生成績(jī)表，邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，可以順序存儲(chǔ)（也可以鏈?zhǔn)酱鎯?chǔ)），運(yùn)算可以有插入、刪除、查詢、等等。 4. 簡(jiǎn)述算法的五個(gè)特性，對(duì)算法設(shè)計(jì)的要求。 【解答】算法的五個(gè)特性是：有窮性、確定性、可行性、零至多個(gè)輸入和一至多個(gè)輸出。 對(duì)算法設(shè)計(jì)的要求：正確性，易讀性，健壯性，和高的時(shí)空間效率（運(yùn)算速度快，存儲(chǔ)空間?。?。 5. 設(shè)n是正整數(shù)，求下列程序段中帶@記號(hào)的語(yǔ)句的執(zhí)行次數(shù)。 (1)i=1;k=0; (2) i=1;j=0; while(ij)j++; @ } else i++; } @ (3)x=y=0; (4)x=91;y=100; for(i=0;i0) for(j=0;j100) {x++; @ {x=x-10; y--; @ for(k=0;i4時(shí)，算法A2好于A1。 7. 選擇題：算法分析的目的是（ ） A、找出數(shù)據(jù)結(jié)構(gòu)的合理性 B、研究算法中的輸入和輸出的關(guān)系 C、分析算法的效率以求改進(jìn) D、分析算法的易懂性和文檔特點(diǎn) 【解答】C 二、算法設(shè)計(jì)題 8. 已知輸入x，y，z三個(gè)不相等的整數(shù)，設(shè)計(jì)一個(gè)“高效”算法，使得這三個(gè)數(shù)按從小到大輸出?！案咝А钡暮x是用最少的元素比較次數(shù)、元素移動(dòng)次數(shù)和輸出次數(shù)。 void Best() {//按序輸出三個(gè)整數(shù)的優(yōu)化算法 int a,b,c,t; scanf(“%d%d%d”,&a,&b,&c); if(a>b) {t=a; a=b; b=t:} //a和b已正序 if(b>c) {t=c; c=b; //c已到位 if(a>t) {b=a; a=t;} //a和b已正序 else b=t; } printf(“%d,%d,%d\n”,a,b,c); //最佳2次比較，無(wú)移動(dòng)；最差3次比較，7個(gè)賦值 } 9. 在數(shù)組A[n]中查找值為k的元素，若找到則輸出其位置i(1≤i≤n)，否則輸出0作為標(biāo)志。設(shè)計(jì)算法求解此問(wèn)題，并分析在最壞情況下的時(shí)間復(fù)雜度。 【題目分析】從后向前查找，若找到與k值相同的元素則返回其位置，否則返回0。 int Search(ElemType A[n+1], ElemType k) {i=n; wile(i>=1)&&(A[i]!=k)) i--; if(i>=1) return i; else return 0; } 當(dāng)查找不成功時(shí)，總的比較次數(shù)為n+1次，所以最壞情況下時(shí)間復(fù)雜度為O(n)。 第2章 線性表 一、基礎(chǔ)知識(shí)題 2.1 試述頭指針、頭結(jié)點(diǎn)、元素結(jié)點(diǎn)、首元結(jié)點(diǎn)的區(qū)別，說(shuō)明頭指針和頭結(jié)點(diǎn)的作 【解答】指向鏈表第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針?lè)Q為頭指針?！邦^指針”具有標(biāo)識(shí)一個(gè)鏈表的作用，所以經(jīng)常用頭指針代表鏈表的名字，如鏈表L既是指鏈表的名字是L，也是指鏈表的第一個(gè)結(jié)點(diǎn)的地址存儲(chǔ)在指針變量L中，頭指針為“NULL”則表示一個(gè)空表。 有時(shí)，我們?cè)谡麄€(gè)線性鏈表的第一個(gè)元素結(jié)點(diǎn)之前加入一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，它的數(shù)據(jù)域可以不存儲(chǔ)任何信息（也可以做監(jiān)視哨或存放線性表的長(zhǎng)度等附加信息），指針域中存放的是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址，空表時(shí)為空。 “頭結(jié)點(diǎn)”的加入，使插入和刪除等操作方便統(tǒng)一。 元素結(jié)點(diǎn)即是數(shù)據(jù)結(jié)點(diǎn)，至少包括元素自身信息和其后繼元素的地址兩個(gè)域。 首元結(jié)點(diǎn)是指鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)；為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。 2.2分析順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)，說(shuō)明何時(shí)應(yīng)該利用何種結(jié)構(gòu)。 【解答】①?gòu)目臻g上來(lái)看，當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置指針域，因此當(dāng)線性表長(zhǎng)度變化不大，易于事先確定規(guī)模時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序存儲(chǔ)結(jié)構(gòu)。 ②從時(shí)間上看，順序表具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)，在順序表中按序號(hào)訪問(wèn)數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(1)；而鏈表中按序號(hào)訪問(wèn)的時(shí)間復(fù)雜度為O(n)。所以如果經(jīng)常按序號(hào)訪問(wèn)數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。 在順序表中做插入刪除操作時(shí)，平均移動(dòng)大約表中一半的元素，因此n較大時(shí)順序表的插入和刪除效率低。在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作。從這個(gè)角度考慮顯然鏈表優(yōu)于順序表。 總之，兩種存儲(chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇那一種存儲(chǔ)結(jié)構(gòu)，由實(shí)際問(wèn)題中的主要因素決定。 2.3 分析在順序存儲(chǔ)結(jié)構(gòu)下插入和刪除結(jié)點(diǎn)時(shí)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)。 【解答】平均移動(dòng)表中大約一半的結(jié)點(diǎn)，插入操作平均移動(dòng) 個(gè)結(jié)點(diǎn)，刪除操作平均移動(dòng) 個(gè)結(jié)點(diǎn)。具體移動(dòng)的次數(shù)取決于表長(zhǎng)和插入、刪除的結(jié)點(diǎn)的位置。 2.4 為什么在單循環(huán)鏈表中常使用尾指針，若只設(shè)頭指針，插入元素的時(shí)間復(fù)雜度如何？ 【解答】單循環(huán)鏈表中無(wú)論設(shè)置尾指針還是頭指針都可以遍歷表中任一個(gè)結(jié)點(diǎn)。設(shè)置尾指針時(shí)，若在表尾進(jìn)行插入元素或刪除第一元素，操作可在O(1)時(shí)間內(nèi)完成；若只設(shè)置頭指針，表尾進(jìn)行插入或刪除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為O(n)。 2.5 在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結(jié)點(diǎn)，能否刪除該結(jié)點(diǎn)，時(shí)間復(fù)雜度如何？ 【解答：】以上三種鏈表中，若知道指針p指向某結(jié)點(diǎn)，都能刪除該結(jié)點(diǎn)。雙鏈表刪除p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，而單鏈表和單循環(huán)鏈表上刪除p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。 2.6 下面算法的功能是什么？ LinkedList Unknown(LinkedList la) {LNode *q，*p; if(la && la->next) {q=la; la=la->next; p=la; while(p->next) p=p->next; p->next=q; q->next=null; } return la; } 【解答】將首元結(jié)點(diǎn)刪除并插入到表尾（設(shè)鏈表長(zhǎng)度大于1）。 2.7 選擇題：在循環(huán)雙鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是（ ） la、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; lc、s->prior=p; s->next=p->next; p->next:=s; p->next->prior=s; D、s->prior=p; s>next=p>next; p>next->prior =s; p->next=s; 【解答】D 2.8 選擇題：若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。 la．順序表 B．雙鏈表 lc．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表 【解答】la 二、算法設(shè)計(jì)題 2.9 設(shè)ha和hb分別是兩個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表的頭指針，試設(shè)計(jì)算法， 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求使用原鏈表空間，表中無(wú)重復(fù)數(shù)據(jù)。 【題目分析】因?yàn)閮涉湵硪寻丛刂捣沁f減次序排列，將其合并時(shí)，均從第一個(gè)結(jié)點(diǎn)起進(jìn)行比較，將小的鏈入鏈表中，同時(shí)后移鏈表工作指針，若遇值相同的元素，則刪除之。該問(wèn)題要求結(jié)果鏈表按元素值非遞增次序排列，故在合并的同時(shí)，將鏈表結(jié)點(diǎn)逆置。 LinkedList Union(LinkedList ha,hb) ∥ha,hb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針，鏈表中的元素值按遞增序排列 ∥本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表,并刪除重復(fù)元素 { pa=ha->next; ∥pa是鏈表ha的工作指針 pb=hb->next; ∥pb是鏈表hb的工作指針 ha->next=null; ∥ha作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空 while(pa!=null && pb!=null) ∥當(dāng)兩鏈表均不為空時(shí)作 {while(pa->next && pa->data==pa->next->data) {u=pa->next; pa->next=u->next; free(u)}∥刪除pa鏈表中的重復(fù)元素 while(pb->next && pb->data==pb->next->data) {u=pb->next; pb->next=u->next; free(u)}∥刪除pb鏈表中的重復(fù)元素 if(pa->datadata) {r=pa->next; ∥將pa 的后繼結(jié)點(diǎn)暫存于r pa->next=ha->next; ∥將pa結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置 ha->next=pa; pa=r; ∥恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn) } else if(pb->datadata) {r=pb->next; ∥ 將pb 的后繼結(jié)點(diǎn)暫存于r pb->next=ha->next; ∥將pb結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置 ha->next=pb; pb=r; ∥恢復(fù)pb為當(dāng)前待比較結(jié)點(diǎn) } else{u=pb;pb=pb->next;free(u)}∥刪除鏈表pb和pa中的重復(fù)元素 }// while(pa!=null && pb!=null) if(pa) pb=pa; ∥避免再對(duì)pa寫下面的while語(yǔ)句 while(pb!=null) ∥將尚未到尾的表逆置到結(jié)果表中 {r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; } return ha }∥算法Union結(jié)束 2.10 設(shè)la是一個(gè)雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入元素x，使表中元素依然遞增有序。 【問(wèn)題分析】雙向鏈表的插入與單鏈表類似，但需修改雙向指針。 DLinkedList DInsert(DLinkedList la, ElemType x) ∥在遞增有序的雙向循環(huán)鏈表la中插入元素x，使表中元素依然遞增有序 {p=la->next; ∥p指向第一元素 la->data=MaxElemType;∥MaxElemType是和x同類型的機(jī)器最大值，用做監(jiān)視哨 while(p->datanext; s=(DLNode *)malloc(sizeof(DLNode));∥申請(qǐng)結(jié)點(diǎn)空間 s->data=x; s->prior=p->prior; s->next=p; ∥將插入結(jié)點(diǎn)鏈入鏈表 p->prior->next=s; p->prior=s; } 2.11 設(shè)p指向頭指針為la的單鏈表中某結(jié)點(diǎn)，試編寫算法，刪除結(jié)點(diǎn)*p的直接前驅(qū)結(jié)點(diǎn)。 【題目分析】設(shè)*p是單鏈表中某結(jié)點(diǎn)，刪除結(jié)點(diǎn)*p的直接前驅(qū)結(jié)點(diǎn)，要找到*p的前驅(qū)結(jié)點(diǎn)的前驅(qū)*pre。進(jìn)行如下操作：u=pre->next; pre->next=u->next;free(u); LinkedList LinkedListDel(LinkedList la，LNode *p) {∥刪除單鏈表la上的結(jié)點(diǎn)*p的直接前驅(qū)結(jié)點(diǎn),假定*p存在 pre=la; if(pre-next==p) printf(“*p是鏈表第一結(jié)點(diǎn)，無(wú)前驅(qū)\n”); exit(0); } while(pre->next->next !=p) pre=pre->next; u=pre->next; pre->next=u->next; free(u); return(la); } 2.12 設(shè)計(jì)一算法，將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式各自僅有奇次冪或偶次冪項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)造這兩個(gè)鏈表。 【題目分析】設(shè)循環(huán)鏈表表示的多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)為： typedef struct node {int power; ∥冪 float coef; ∥系數(shù) ElemType other; ∥其他信息 struct node *next; ∥指向后繼的指針 }PNode,*PolyLinkedList; 則可以從第一個(gè)結(jié)點(diǎn)開始，根據(jù)結(jié)點(diǎn)的冪是奇數(shù)或偶數(shù)而將其插入到奇次冪或偶次冪項(xiàng)的鏈表中。假定用原鏈表保存偶次冪，要為奇次冪的鏈表生成一個(gè)表頭，為了保持鏈表中結(jié)點(diǎn)的原來(lái)順序，用一個(gè)指針指向奇次冪鏈表的表尾，注意鏈表分解時(shí)不能“斷鏈”。 void PolyDis(PolyLinkedList poly) ∥將poly表示的多項(xiàng)式鏈表分解為各含奇次冪或偶次冪項(xiàng)的兩個(gè)循環(huán)鏈表 {PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode)); ∥poly2表示只含奇次冪的多項(xiàng)式 r2=poly2; ∥r2是只含奇次冪的多項(xiàng)式鏈表的尾指針 r1=poly; ∥r1是只含偶次冪的多項(xiàng)式鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針 p=poly->next; ∥鏈表帶頭結(jié)點(diǎn)，p指向第一個(gè)元素 while(p!=poly) if(p->power % 2)∥處理奇次冪 {r=p->next; ∥暫存后繼 r2->next=p; ∥結(jié)點(diǎn)鏈入奇次冪鏈表 r2=p; ∥尾指針后移 p=r; ∥恢復(fù)當(dāng)前待處理結(jié)點(diǎn) } else ∥處理偶次冪 {r1->next=p; r1=p; p=p->next;} } r->next=poly2; r1->next=poly; ∥構(gòu)成循環(huán)鏈表 }∥PolyDis 2.13 以帶頭結(jié)點(diǎn)的雙向鏈表表示的線性表L=(a1，a2，…，an)，試寫一時(shí)間復(fù)雜度為O(n)的算法，將L改造為L(zhǎng)=(a1，a3，…，an，…，a4，a2)。 【題目分析】分析結(jié)果鏈表，易見鏈表中位置是奇數(shù)的結(jié)點(diǎn)保持原順序，而位置是偶數(shù)的結(jié)點(diǎn)移到奇數(shù)結(jié)點(diǎn)之后，且以與原來(lái)相反的順序存放。因此，可從鏈表第一個(gè)結(jié)點(diǎn)開始處理，位置是奇數(shù)的結(jié)點(diǎn)保留不動(dòng)，位置是偶數(shù)的結(jié)點(diǎn)插入到鏈表尾部，并用一指針指向鏈表尾，以便對(duì)偶數(shù)結(jié)點(diǎn)“尾插入”。 DLinkedList DInvert(DLinkedList L) ∥將雙向循環(huán)鏈表L位置是偶數(shù)的結(jié)點(diǎn)逆置插入到鏈表尾部 {p=L->next; ∥p指向第一元素 Q=p->prior; ∥Q指向最后一個(gè)元素 pre=L; ∥pre指向鏈表中位置為奇數(shù)的結(jié)點(diǎn)的前驅(qū) r=L; ∥r指向鏈表中偶數(shù)結(jié)點(diǎn)的尾結(jié)點(diǎn) i=0; ∥i記錄結(jié)點(diǎn)序號(hào) while(p!= Q) ∥尋找插入位置 {i++; if(i%2) ∥處理序號(hào)為奇數(shù)的結(jié)點(diǎn) {p->prior=pre;pre->next=p;pre=p; p=p->next;} else ∥處理序號(hào)為偶數(shù)的結(jié)點(diǎn) {u=p; ∥記住當(dāng)前結(jié)點(diǎn) p=p->next;∥p指向下個(gè)待處理結(jié)點(diǎn) u->prior=r->prior;∥以下4個(gè)語(yǔ)句將結(jié)點(diǎn)插入鏈表尾 u->next=r; r->prior->next=u; r->prior=u; r=u; ∥指向新的表尾 } } 2.14 設(shè)單向鏈表的頭指針為head，試設(shè)計(jì)算法，將鏈表按遞增的順序就地排序。 【題目分析】本題中的“就地排序”，可理解為不另辟空間，這里利用直接插入原則把鏈表整理成遞增有序鏈表。 LinkedList LinkListInsertSort(LinkedList head) ∥head是帶頭結(jié)點(diǎn)的單鏈表，本算法利用直接插入原則將鏈表整理成遞增的有序鏈表 {if(head->next!=null) ∥鏈表不為空表 {p=head->next->next; ∥p指向第一結(jié)點(diǎn)的后繼 head->next->next=null; ∥直接插入原則認(rèn)為第一元素有序，然后從第二元素起依次插入 while(p!=null) {r=p->next; ∥暫存p的后繼 q=head; while(q->next && q->next->datadata) q=q->next;∥查找插入位置 p->next=q->next; ∥將p結(jié)點(diǎn)鏈入鏈表 q->next=p; p=r; } } } 2.15 已知遞增有序的三個(gè)單鏈表分別代表集合A，B和C，設(shè)計(jì)算法實(shí)現(xiàn)A=A∪（B∩C），并使結(jié)果鏈表仍保持遞增。要求算法的時(shí)間復(fù)雜度為O(|A|+|B|+|C|)。其中，|A|為集合A的元素個(gè)數(shù)。 【題目分析】本題首先求B和C的交集，即求B和C中共有元素，再與A求并集，同時(shí)刪除重復(fù)元素，以保持結(jié)果A遞增。 LinkedList union(LinkedList A,B,C) ∥A、B和C均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表,本算法實(shí)現(xiàn)A=A∪(B∩C) ∥使結(jié)果表A保持遞增有序 {pa=A->next;pb=B->next;pc=C->next;∥設(shè)置三個(gè)工作指針 pre=A; ∥pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū) A->data=MaxElemType;∥同類型元素最大值，起監(jiān)視哨作用 while(pa || pb && pc) {while(pb && pc) if(pb->datadata) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; ∥B表和C表有公共元素 if(pb && pc) {while(pa && pa->datadata)∥先將A中小于B，C公共元素部分鏈入 {pre->next=pa;pre=pa;pa=pa->next;} if(pre->data!=pb->data) {pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;} else{pb=pb->next;pc=pc->next;} ∥ 若A中已有B，C公共元素，則不再存入結(jié)果表 } }∥ while(pa||pb&&pc) if(pa) pre->next=pa; else pre->next=null; ∥當(dāng)B，C無(wú)公共元素，將A中剩余鏈入 }∥算法Union結(jié)束 2.16 順序表la與lb非遞減有序，順序表空間足夠大。試設(shè)計(jì)一種高效算法，將lb中元素合到la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動(dòng)元素。 【題目分析】順序存儲(chǔ)結(jié)構(gòu)的線性表的插入，其時(shí)間復(fù)雜度為O(n)，平均移動(dòng)近一半的元素。線性表la和lb合并時(shí)，若從第一個(gè)元素開始，一定會(huì)造成元素后移，這不符合本題“高效算法”的要求。應(yīng)從線性表的最后一個(gè)元素開始比較，大者放到最終位置上。設(shè)兩線性表的長(zhǎng)度各為m和n ，則結(jié)果表的最后一個(gè)元素應(yīng)在m+n位置上。這樣從后向前，直到第一個(gè)元素為止。 SeqList Union(SeqList la, SeqList lb) ∥la和lb是順序存儲(chǔ)的非遞減有序線性表，本算法將lb合并到la中，元素仍非遞減有序 { m=la.last;n=lb.last;∥m，n分別為線性表la和lb的長(zhǎng)度 k=m+n-1; ∥k為結(jié)果線性表的工作指針（下標(biāo)） i=m-1;j=n-1; ∥i，j分別為線性表la和lb的工作指針（下標(biāo)） while(i>=0 && j>=0) if(la.data[i]>=lb.data[j]) la.data[k--]=la.data[i--]; else la.data[k--]=lb.data[j--]; while(j>=0) la.data[k--]=lb.data[j--]; la.last=m+n; return la; } 【算法討論】算法中數(shù)據(jù)移動(dòng)是主要操作。在最佳情況下（lb的最小元素大于la的最大元素），僅將lb的n個(gè)元素移（拷貝）到la中，時(shí)間復(fù)雜度為O（n），最差情況，la的所有元素都要移動(dòng)，時(shí)間復(fù)雜度為O（m+n）。因數(shù)據(jù)合并到la中，所以在退出第一個(gè)while循環(huán)后，只需要一個(gè)while循環(huán)，處理lb中剩余元素。第二個(gè)循環(huán)只有在lb有剩余元素時(shí)才執(zhí)行，而在la有剩余元素時(shí)不執(zhí)行。本算法 “最大限度的避免移動(dòng)元素”，是“一種高效算法”。 2.17 已知非空線性鏈表由head指出，試寫一算法，將鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請(qǐng)新的鏈結(jié)點(diǎn)。 【題目分析】 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。首先要查找最小值結(jié)點(diǎn)。將其移到鏈表最前面，實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下（不是刪除并回收空間），再插入到鏈表的最前面。 LinkedList Delinsert(LinkedList head） ∥本算法將非空線性鏈表head中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面 {p=head->next；∥p是鏈表的工作指針 pre=head； ∥pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū) q=p； ∥q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn) while （p->next） {if（p->next->datadata）{pre=p；q=p->next；} ∥找到新的最小值結(jié)點(diǎn) p=p->next； } if(q!=head->next) ∥若最小值是第一元素結(jié)點(diǎn)，則不需再操作 {pre->next=q->next； ∥將最小值結(jié)點(diǎn)從鏈表上摘下 q->next=head->next； ∥將q結(jié)點(diǎn)插到鏈表最前面 head->next=q； } }∥Delinsert 2.18 設(shè)la是帶頭結(jié)點(diǎn)的非循環(huán)雙向鏈表的指針，其結(jié)點(diǎn)中除有prior，data和next外，還有一訪問(wèn)頻度域freq，其值在鏈表初始使用時(shí)為0。當(dāng)在鏈表中進(jìn)行ListLocate(la，x)運(yùn)算時(shí)，若查找失敗，則在表尾插入值為x的結(jié)點(diǎn)；若查找成功，值為x的結(jié)點(diǎn)的freq值增1，并要求鏈表按freq域值非增（遞減）的順序排列，且最近訪問(wèn)的結(jié)點(diǎn)排在頻度相同的結(jié)點(diǎn)的后面，使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試編寫符合上述要求的ListLocate(la，x)運(yùn)算的算法，返回找到結(jié)點(diǎn)的指針。 【題目分析】首先在雙向鏈表中查找數(shù)據(jù)值為x的結(jié)點(diǎn)，查到后，將結(jié)點(diǎn)從鏈表上摘下，然后再順結(jié)點(diǎn)的前驅(qū)鏈查找該結(jié)點(diǎn)的位置。 DLinkList ListLocate(DLinkedList L，ElemType x) ∥ L是帶頭結(jié)點(diǎn)的按訪問(wèn)頻度遞減的雙向鏈表,本算法先查找數(shù)據(jù)x ∥查找成功時(shí)結(jié)點(diǎn)的訪問(wèn)頻度域增1，最后將該結(jié)點(diǎn)按頻度遞減插入鏈表中 {DLinkList p=L->next,q; ∥p為L(zhǎng)表的工作指針，q為p的前驅(qū)，用于查找插入位置 while(p && p->data!=x) p=p->next;∥ 查找值為x的結(jié)點(diǎn) if(!p) {printf(“不存在所查結(jié)點(diǎn)\n”); exit(0);} else { p->freq++; ∥ 令元素值為x的結(jié)點(diǎn)的freq域加1 p->next->prior=p->prior; ∥ 將p結(jié)點(diǎn)從鏈表上摘下 p->prior->next=p->next; q=p->prior; ∥ 以下查找p結(jié)點(diǎn)的插入位置 while(q !=L && q->freqfreq) q=q->prior; p->next=q->next; q->next->prior=p;∥ 將p結(jié)點(diǎn)插入 p->prior=q; q->next=p； } return(p); ∥返回值為x的結(jié)點(diǎn)的指針 } ∥ 算法結(jié)束 2.19 三個(gè)帶頭結(jié)點(diǎn)的線性鏈表la、lb和lc中的結(jié)點(diǎn)均依元素值自小至大非遞減排列（可能存在兩個(gè)以上值相同的結(jié)點(diǎn)），編寫算法對(duì)la表進(jìn)行如下操作：使操作后的la中僅留下三個(gè)表中均包含的數(shù)據(jù)元素的結(jié)點(diǎn)，且沒有值相同的結(jié)點(diǎn)，并釋放所有無(wú)用結(jié)點(diǎn)。限定算法的時(shí)間復(fù)雜度為O（m+n+p），其中m、n和p分別為三個(gè)表的長(zhǎng)度。 【題目分析】 留下三個(gè)鏈表中公共數(shù)據(jù)，首先查找兩表la和B中公共數(shù)據(jù)，再去lc中找有無(wú)該數(shù)據(jù)。要消除重復(fù)元素，應(yīng)記住前驅(qū)，要求時(shí)間復(fù)雜度O（m+n+p），在查找每個(gè)鏈表時(shí)，指針不能回溯。 LinkedList lcommon（LinkedList la，lb，lc） ∥本算法使la表留下la、lb和lc三個(gè)非遞減有序表共同結(jié)點(diǎn)，無(wú)重復(fù)元素 {pa=la->next；pb=lb->next；pc=lc->next； ∥pa,pb和pc分別是la,lb和lc三個(gè)表的工作指針 pre=la； la->data=MaxElemType ∥pre是la表當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針,頭結(jié)點(diǎn)作監(jiān)視哨 while（pa && pb && pc） ∥當(dāng)la,lb和lc表均不空時(shí)，查找三表共同元素 {while(pa&&pa->data==pre->data) {u=pa; pa=pa->next; free(u);}//刪la中相同元素 while（pb && pc） if（pb->datadata）pb=pb->next; ∥結(jié)點(diǎn)元素值小時(shí)，后移指針 else if（pb->data>pc->data）pc=pc->next； else break ;∥處理lb和lc表元素值相等的結(jié)點(diǎn) if(pb && pc) {while（pa && pa->datadata）{u=pa；pa=pa->next；free（u）；} if(pa && pa->data>pc->data){pb=pb->next; pc=pc->next;} else if(pa && pa->data==pc->data)∥pc，pa和pb對(duì)應(yīng)結(jié)點(diǎn)元素值相等 {pre->next=pa；pre=pa；pa=pa->next；∥將新結(jié)點(diǎn)鏈入la表 pb=pb->next；pc=pc->next； ∥鏈表的工作指針后移 }∥pc，pa和pb對(duì)應(yīng)結(jié)點(diǎn)元素值相等 } }∥while（pa && pb && pc） pre->next=null； ∥置新la表表尾 while（pa!=null） ∥刪除原la表剩余元素。 {u=pa；pa=pa->next；free（u）；} }∥算法結(jié)束 【算法討論】 算法中l(wèi)a表、lb表和lc表均從頭到尾（嚴(yán)格說(shuō)lb、lc中最多一個(gè)到尾）遍歷一遍，算法時(shí)間復(fù)雜度符合O（m+n+p）。算法主要由while（pa && pb && pc）控制。三表有一個(gè)到尾則結(jié)束循環(huán)。要注意頭結(jié)點(diǎn)的監(jiān)視哨的作用，否則第一個(gè)結(jié)點(diǎn)要特殊處理。算法最后要給新la表置結(jié)尾標(biāo)記，同時(shí)若原la表沒到尾，還應(yīng)釋放剩余結(jié)點(diǎn)所占的存儲(chǔ)空間。 第3章 棧和隊(duì)列 一、基礎(chǔ)知識(shí)題 3.1 有五個(gè)數(shù)依次進(jìn)棧：1，2，3，4，5。在各種出棧的序列中，以3，4先出的序列有哪幾個(gè)。（３在４之前出棧）。 【解答】34215 ，34251， 34521 3.2 鐵路進(jìn)行列車調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)，若進(jìn)站的六輛列車順序?yàn)椋?，2，3，4，5，6， 那么是否能夠得到435612， 325641， 154623和135426的出站序列，如果不能，說(shuō)明為什么不能； 如果能， 說(shuō)明如何得到(即寫出"進(jìn)棧"或"出棧"的序列)。 【解答】輸入序列為123456，不能得出435612和154623。不能得到435612的理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能讓棧底元素1在棧頂元素2之前出棧。不能得到154623的理由類似，當(dāng)棧中元素只剩23，且3在棧頂，2不可能先于3出棧。 得到325641的過(guò)程如下：1 2 3順序入棧，32出棧，得到部分輸出序列32；然后45入棧，5出棧，部分輸出序列變?yōu)?25；接著6入棧并退棧，部分輸出序列變?yōu)?256；最后41退棧，得最終結(jié)果325641。 得到135426的過(guò)程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。 3.3 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？ 【解答】2和 4 3.4 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e3，e5，e4，e6，e2，e1，則棧S的容量至少應(yīng)該是多少？ 【解答】 4 3.5 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么，如何判斷“空”和“滿”。 【解答】循環(huán)隊(duì)列解決了常規(guī)用0--m-1的數(shù)組表示隊(duì)列時(shí)出現(xiàn)的“假溢出”（即隊(duì)列未滿但不能入隊(duì)）。在循環(huán)隊(duì)列中我們?nèi)杂藐?duì)頭指針等于隊(duì)尾指針表示隊(duì)空，而用犧牲一個(gè)單元的辦法表示隊(duì)滿，即當(dāng)隊(duì)尾指針加1（求模）等于隊(duì)頭指針時(shí)，表示隊(duì)列滿。也有通過(guò)設(shè)標(biāo)記以及用一個(gè)隊(duì)頭或隊(duì)尾指針加上隊(duì)中元素個(gè)數(shù)來(lái)區(qū)分隊(duì)列的“空”和“滿”的。 3.6 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)和出隊(duì)的時(shí)間如何？若只設(shè)尾指針呢？ 【解答】若只設(shè)頭指針，則入隊(duì)的時(shí)間為O(n），出隊(duì)的時(shí)間為O(1)。若只設(shè)尾指針，則入隊(duì)和出隊(duì)的時(shí)間均為O(1)。 3.7 指出下面程序段的功能是什么？ (1) void demo1(SeqStack S) {int i，arr[64]，n=0; while(!StackEmpty(S)) arr[n++]=Pop(S); for(i=0;i1) printf(i--); } 【解答】void digui(int n) {if(n>1){printf(n); digui(n-1); } } 3.9 寫出下列中綴表達(dá)式的后綴表達(dá)式： (1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C 【解答】(1)ABC** (2)AB+C*D- (3)AB*CDE-/+ (4)AB+D*EFAD*+/+C+ 3.10 選擇題：循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為( )。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1) 【解答】D 3.11 選擇題：4個(gè)園盤的Hahoi塔，總的移動(dòng)次數(shù)為( )。 A.7 B. 8 C.15 D.16 【解答】C 3.12選擇題：允許對(duì)隊(duì)列進(jìn)行的操作有( )。 A. 對(duì)隊(duì)列中的元素排序 B. 取出最近進(jìn)隊(duì)的元素 C. 在隊(duì)頭元素之前插入元素 D. 刪除隊(duì)頭元素 【解答】D 二、算法設(shè)計(jì)題 3.13 利用棧的基本操作，編寫求棧中元素個(gè)數(shù)的算法。 【題目分析】 將棧值元素出棧，出棧時(shí)計(jì)數(shù)，直至?？?。 【算法】 int StackLength(Stack S) {//求棧中元素個(gè)數(shù) int n=0; while(!StackEmpty(S) {n++; Pop(S); } return n; } 算法討論：若要求統(tǒng)計(jì)完元素個(gè)數(shù)后，不能破壞原來(lái)?xiàng)?，則在計(jì)數(shù)時(shí)，將原棧導(dǎo)入另一臨時(shí)棧，計(jì)數(shù)完畢，再將臨時(shí)棧倒入原棧中。 int StackLength(Stack S) {//求棧中元素個(gè)數(shù) int n=0; Stack T; StackInit(T); //初始化臨時(shí)棧T while(!StackEmpty(S) {n++; Push(T,Pop(S)); } while(!StackEmpty(T) {Push(S,Pop(T)); } return n; } 3.14 雙向棧S是在一個(gè)數(shù)組空間V[m]內(nèi)實(shí)現(xiàn)的兩個(gè)棧，棧底分別處于數(shù)組空間的兩端。試為此雙向棧設(shè)計(jì)棧初始化Init(S)、入棧Push(S，i，x)、出棧Pop(S，i)算法，其中i為0或1，用以指示棧號(hào)。 [題目分析]兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥耍跏紩r(shí)，s1棧頂指針為-1，s2棧頂為m。兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。 #define ElemType int ∥假設(shè)元素類型為整型 typedef struct {ElemType V[m]; ∥?？臻g int top[2]; ∥top為兩個(gè)棧頂指針 }stk; stk S; ∥S是如上定義的結(jié)構(gòu)類型變量，為全局變量 (1) 棧初始化 int Init() {S.top[0]=-1; S.top[1]=m; return 1; //初始化成功 } (2) 入棧操作： int push(stk S ,int i,int x) ∥i為棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，否則返回0 {if(i<0||i>1){printf(“棧號(hào)輸入不對(duì)\n”);exit(0);} if(S.top[1]-S.top[0]==1) {printf(“棧已滿\n”);return(0);} switch(i) {case 0: S.V[++S.top[0]]=x; return(1); break; case 1: S.V[--S.top[1]]=x; return(1); } }∥push (3) 退棧操作 ElemType pop(stk S,int i) ∥退棧。i代表?xiàng)Ｌ?hào)，i=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功返回退棧元素 ∥否則返回-1 {if(i<0 || i>1){printf(“棧號(hào)輸入錯(cuò)誤\n”)；exit(0);} switch(i) {case 0: if(S.top[0]==-1) {printf(“?？誠(chéng)n”)；return（-1）；} else return(S.V[S.top[0]--]); case 1: if(S.top[1]==m {printf(“?？誠(chéng)n”); return(-1);} else return(S.V[S.top[1]++]); }∥switch }∥算法結(jié)束 (4) 判斷?？? int Empty(); {return (S.top[0]==-1 && S.top[1]==m); } [算法討論] 請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。s1(左棧)是通常意義下的棧，而s2(右棧)入棧操作時(shí)，其棧頂指針左移（減1），退棧時(shí)，棧頂指針右移（加1）。 3.15設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)置一個(gè)標(biāo)志tag，以tag=0和tag=1來(lái)區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“不空”。試編寫相應(yīng)的入隊(duì)(QueueIn)和出隊(duì)(QueueOut)算法。 （1） 初始化 SeQueue QueueInit(SeQueue Q) {//初始化隊(duì)列 Q.front=Q.rear=0; Q.tag=0; return Q; } （2） 入隊(duì) SeQueue QueueIn(SeQueue Q,int e) {//入隊(duì)列 if((Q.tag==1) && (Q.rear==Q.front)) printf("隊(duì)列已滿\n"); else {Q.rear=(Q.rear+1) % m; Q.data[Q.rear]=e; if(Q.tag==0) Q.tag=1; //隊(duì)列已不空 } return Q; } (3)出隊(duì) ElemType QueueOut(SeQueue Q) {//出隊(duì)列 if(Q.tag==0) printf("隊(duì)列為空\(chéng)n"); else {Q.front=(Q.front+1) % m; e=Q.data[Q.front]; if(Q.front==Q.rear) Q.tag=0; //空隊(duì)列 } return(e); } 3.16假設(shè)用變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的定義，并寫出相應(yīng)的入隊(duì)(QueueIn)和出隊(duì)(QueueOut)算法。 【算法設(shè)計(jì)】 （1）循環(huán)隊(duì)列的定義 typedef struct {ElemType Q[m]; ∥ 循環(huán)隊(duì)列占m個(gè)存儲(chǔ)單元 int rear,length; ∥ rear指向隊(duì)尾元素,length為元素個(gè)數(shù) }SeQueue; (2) 初始化 SeQueue QueueInit (SeQueue cq) ∥cq為循環(huán)隊(duì)列，本算法進(jìn)行隊(duì)列初始化 { cq.rear=0; cq.length=0; return cq; } (3) 入隊(duì) SeQueue QueueIn(SeQueue cq，ElemType x) ∥cq是以如上定義的循環(huán)隊(duì)列，本算法將元素x入隊(duì) {if(cq.length==m) return(0); ∥ 隊(duì)滿 else {cq.rear=(cq.rear+1) % m; ∥ 計(jì)算插入元素位置 cq.Q[cq.rear]=x; ∥ 將元素x入隊(duì)列 cq.length++; ∥ 修改隊(duì)列長(zhǎng)度 } return (cq); }