李云清揭安全數(shù)據(jù)結(jié)構(gòu)答案數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版）習(xí)題解析揭安全李云清楊慶紅江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院聯(lián)系方式：janquan@163（習(xí)題答案僅供參考）2第1章緒論1什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合。數(shù)據(jù)結(jié)構(gòu)涉及哪幾個(gè)方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算集八口O兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同，但是它們的運(yùn)算集合中有一個(gè)運(yùn)算的定義不一樣，它們是否可以認(rèn)作是同一個(gè)數(shù)據(jù)結(jié)構(gòu)？為什么？【答】：不能，運(yùn)算集合是數(shù)據(jù)結(jié)構(gòu)的重要組成部分，不同的運(yùn)算集合所確定的數(shù)據(jù)結(jié)構(gòu)是不一樣的，例如，棧與隊(duì)列它們的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)可以相同，但由于它們的運(yùn)算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)的特點(diǎn)是什么？非線性結(jié)構(gòu)的特點(diǎn)是什么？【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對(duì)一的，在線性結(jié)構(gòu)中只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，一其他的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。而非線性結(jié)構(gòu)則沒(méi)有這個(gè)特點(diǎn)，元素之間的關(guān)系可以是一對(duì)多的或多對(duì)多的。數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)等四種方式。算法有哪些特點(diǎn)？它和程序的主要區(qū)別是什么？【答】：算法具有（D有窮性（2）確定性（3）0個(gè)或多個(gè)輸入（4）1個(gè)或多個(gè)輸出（5）可行性等特征。程序是算法的一種描述方式，通過(guò)程序可以在計(jì)算機(jī)上實(shí)現(xiàn)算法。抽象數(shù)據(jù)類型的是什么？它有什么特點(diǎn)？【答】：抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進(jìn)一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。抽象數(shù)據(jù)類型是與表示無(wú)關(guān)的數(shù)據(jù)類型，是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)類型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。算法的時(shí)間復(fù)雜度指的是什么？如何表示?【答】：算法執(zhí)行時(shí)間的度量不是采用算法執(zhí)行的絕對(duì)時(shí)間來(lái)計(jì)算的，因?yàn)橐粋€(gè)算法在不同的機(jī)器上執(zhí)行所花的時(shí)間不一樣，在不同時(shí)刻也會(huì)由于計(jì)算機(jī)資源占用情況的不同，使得算法在同一臺(tái)計(jì)算機(jī)上執(zhí)行的時(shí)間也不一樣，另外，算法執(zhí)行的時(shí)間還與輸入數(shù)據(jù)的狀態(tài)有關(guān)，所以對(duì)于算法的時(shí)間復(fù)雜性，采用算法執(zhí)行過(guò)程中其基本操作的執(zhí)行次數(shù)，稱為計(jì)算量來(lái)度量。算法中基本操作的執(zhí)行次數(shù)一般是與問(wèn)題規(guī)模有關(guān)的，對(duì)于結(jié)點(diǎn)個(gè)數(shù)為n的數(shù)據(jù)處理問(wèn)題，用T(n)表示算法基本操作的執(zhí)行次數(shù)。為了評(píng)價(jià)算法的執(zhí)行效率，通常采用大寫(xiě)0符號(hào)表示算法的時(shí)間復(fù)雜度，大寫(xiě)0符號(hào)給出了函數(shù)f的一個(gè)上限。其它義如下：3定義：f(n)=0(g(n))當(dāng)且僅當(dāng)存在正的常數(shù)c和nO,使得對(duì)于所有的ndnO,有f(n)Wcg(n)?上述定義表明，函數(shù)f頂多是函數(shù)g的c倍，除非n小于nO。因此對(duì)于足夠大的n(如n》nO),g是f的一個(gè)上限(不考慮常數(shù)因子c)。在為函數(shù)f提供一個(gè)上限函數(shù)g時(shí)，通常使用比較簡(jiǎn)單的函數(shù)形式。比較典型的形式是含有n的單個(gè)項(xiàng)(帶一個(gè)常數(shù)系數(shù))。表1T列出了一些常用的g函數(shù)及其名稱。對(duì)于表1T中的對(duì)數(shù)函數(shù)logn,沒(méi)有給出對(duì)數(shù)基，原因是對(duì)于任何大于1的常數(shù)a和b都有l(wèi)ogan=logbn/logba,所以logan和logbn都有一個(gè)相對(duì)的乘法系數(shù)1/logba,其中a是一個(gè)常量。表1-1常用的漸進(jìn)函數(shù)算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中占用的額外的輔助空間的個(gè)數(shù)。可以將它表示為問(wèn)題規(guī)模的函數(shù)，并通過(guò)大寫(xiě)。符號(hào)表示空間復(fù)雜度。對(duì)于下面的程序段，分析帶下劃線的語(yǔ)句的執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度T(n)0i++;for(i-0;i<n;i++)if(a[i]<x)x=a[i];for(i=0;i<n;i++)for(j=0;j<n;j++)printf(“%d”，i+j)：for(i=l;i<=n-l;i++){k=i：for(j=i+l;j<=n;j++)if(a[j]>a[j+l])k=j;t=a[k];a[k]=a[i];a[i]=t;}for(i=0;i<n;i++)for(j=0;j<n;j++){++x;s=s+x;}【答】：(1)0(1)；(2)0(n)；(3)0(n2)；(4)0(n)；(5)0(n2)4第2章線性表及其順序存儲(chǔ)1選擇題(1)表長(zhǎng)為n的順序存儲(chǔ)的線性表，當(dāng)在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為(E),刪除一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為(A)。A.(n—1)/2B.nC.n+1D.n—1E.n/2F.(n+1)/2G.(n-2)/2(2)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的序列為e2、e4、e3、e6、e5和el,則棧S的容量至少應(yīng)該為(C)。A.6B.4C.3D.2(3)設(shè)棧的輸入序列為1、2、3…n,若輸出序列的第一個(gè)元素為n,則第i個(gè)輸出的元素為(B)?A.不確定B.n—i+lC.iD.n-i(4)在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1<=i<=n)時(shí)，需向前移動(dòng)(A)個(gè)元素。A.n-iB.n-i+1C.n-i—1D.i(5)若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第i個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為(A)。A.0(n)B.0(1)C.0(n2)D.0(n3)(6)表達(dá)式a*(b+c)-d的后綴表達(dá)式是(B)。A.abcd*+—B.abc+*d—C.abc*+d—D.—+*abcd(7)隊(duì)列是一種特殊的線性表，其特殊性在于(C)。A.插入和刪除在表的不同位置執(zhí)行B.插入和刪除在表的兩端位置執(zhí)行C.插入和刪除分別在表的兩端執(zhí)行D.插入和刪除都在表的某一端執(zhí)行(8)棧是一種特殊的線性表，具有(B)性質(zhì)。A.先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.順序進(jìn)出(9)順序循環(huán)隊(duì)列中(數(shù)組的大小為n),隊(duì)頭指示front指向隊(duì)列的第1個(gè)元素，隊(duì)尾指示rear指向隊(duì)列最后元素的后1個(gè)位置，則循環(huán)隊(duì)列中存放了n-1個(gè)元素，即循環(huán)隊(duì)列滿的條件為（B）。A.（rear+l）%n=front-IB.（rear+l）%n=frontC.（rear）%n=frontD.rear+1=front（10）順序循環(huán)隊(duì)列中（數(shù)組的大小為6）,隊(duì)頭指示front和隊(duì)尾指示rear的值分別為3和0,當(dāng)從隊(duì)列中刪除1個(gè)元素，再插入2個(gè)元素后，front和rear的值分別為（D）.A.5和1B.2和4c.1和5D.4和2什么是順序表？什么是棧？什么是隊(duì)列？5【答】：當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，即為順序表。棧是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入與刪除操作只能在這種線性表的同一端進(jìn)行（即棧頂），因此，棧具有先進(jìn)后出、后進(jìn)先出的特點(diǎn)。隊(duì)列也是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入在表的一端進(jìn)行，數(shù)據(jù)的刪除在表的另一端進(jìn)行，因此隊(duì)列具有先進(jìn)先出，后進(jìn)后出的特點(diǎn)。設(shè)計(jì)一個(gè)算法，求順序表中值為x的結(jié)點(diǎn)的個(gè)數(shù)。【答】：順序表的存儲(chǔ)結(jié)構(gòu)定義如下（文件名seqlist.h）：Sinclude<stdio.h>?tdefineN100/*預(yù)定義最大的數(shù)據(jù)域空間*/typedefintdatatype;/*假設(shè)數(shù)據(jù)類型為整型*/typedefstruct{datatypedata[N];/*此處假設(shè)數(shù)據(jù)元素只包含一個(gè)整型的關(guān)鍵字域*/intlength;/*線性表長(zhǎng)度*/}seqlist;/*預(yù)定義的順序表類型*/算法countx(L,x)用于求順序表L中值為x的結(jié)點(diǎn)的個(gè)數(shù)。intcountx(seqlist*L,datatypex){intc=0;inti;for(i=0;i<L->length;i++)if(L->data[i]==x)c++;returnc;}設(shè)計(jì)一個(gè)算法，將一個(gè)順序表倒置。即，如果順序表各個(gè)結(jié)點(diǎn)值存儲(chǔ)在一維數(shù)組a中，倒置的結(jié)果是使得數(shù)組a中的a[0]等于原來(lái)的最后一個(gè)元素，a[l]等于原來(lái)的倒數(shù)第2個(gè)元素，…，a的最后一個(gè)元素等于原來(lái)的第一個(gè)元素。【答】：順序表的存儲(chǔ)結(jié)構(gòu)定義同題2.3,實(shí)現(xiàn)順序表倒置的算法程序如下：voidverge(seqlist*L){intt,i,j;i=0;j=L->length~l;while(i<j){t=L->data[i];L->data[i++]=L->data[j];L->data[j-]=t;已知一個(gè)順序表中的各結(jié)點(diǎn)值是從小到大有序的，設(shè)計(jì)一個(gè)算法，插入一個(gè)值為x的結(jié)點(diǎn)，使順序表中的結(jié)點(diǎn)仍然是從小到大有序。【答】：順序表的定義同題2.3,實(shí)現(xiàn)本題要求的算法程序如下：6voidinsertx(seqlist*L,datatypex){intj;if(L->length<N){j=L->length-l;while(j>=0&&L->data[j]>x){L->data[j+l]=L->data[j];j—；)L->data[j+l]=x;L->length++;))將下列中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式。5+6*7(5-6)/75-6*7*85*7-85*(7-6)+8/97*(5-6*8)-9【答】：5+6*7后綴表達(dá)式：567*+(5-6)/7后綴表達(dá)式：56-7/5-6*7*8后綴表達(dá)式：567*8*-5*7-8后綴表達(dá)式：57*85*(7-6)+8/9后綴表達(dá)式：576-*89/+(12)7*(5-6*8)-9后綴表達(dá)式：7568*-*9-循環(huán)隊(duì)列存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組大小為n,隊(duì)首指針和隊(duì)尾指針?lè)謩e為front和rear,請(qǐng)寫(xiě)出求循環(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的表達(dá)式。【答】：循環(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的計(jì)算公式是：(n+rear-front)%n編號(hào)為1,2,3,4的四列火車(chē)通過(guò)一個(gè)棧式的列車(chē)調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有n列火車(chē)通過(guò)調(diào)度站，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，輸出所有可能的調(diào)度結(jié)果。【答】：解題思路：棧具有先進(jìn)后出、后進(jìn)先出的特點(diǎn)，因此，任何一個(gè)調(diào)度結(jié)果應(yīng)該是1,2,3,4全排列中的一個(gè)元素。由于進(jìn)棧的順序是由小到大的，所以出棧序列應(yīng)該滿足以下條件：對(duì)于序列中的任何一個(gè)數(shù)其后面所有比它小的數(shù)應(yīng)該是倒序的，例如4321是一個(gè)有效的出棧序列，1423不是一個(gè)有效的出棧結(jié)果(4后面比它小的兩個(gè)數(shù)2,3不是倒序)。據(jù)此，本題可以通過(guò)算法產(chǎn)生n個(gè)數(shù)的全排列，然后將滿足出棧規(guī)則的序列輸出。產(chǎn)生n個(gè)數(shù)的全排列有遞歸與非遞歸兩種實(shí)現(xiàn)算法。產(chǎn)生全排列的遞歸算法:7設(shè)R={rl,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}o集合X中元素的全排列記為perm(X)o(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴列得到的排列。R的全排列可歸納定義如下：當(dāng)n=l時(shí)，perm(R)=(r),其中r是集合R中惟一的元素；當(dāng)n>l時(shí)，perm(R)由(rl)perm(Rl),(r2)perm(R2),…，(rn)perm(Rn)構(gòu)成。依此遞歸定義，可設(shè)計(jì)產(chǎn)生perin(R)的遞歸算法如下：遞歸解法：(2_8」.c)#include<stdio.h>intcont=l;/*全局變量，用于記錄所有可能的出棧序列個(gè)數(shù)*/voidprint(intstr[],intn);/*求整數(shù)序列str口從k到n的全排列*/voidperm(intstr[],intk,intn){inti,temp;if(k==n-l)print(str,n);else{for(i=k;i<n;i++){temp=str[k];str[k]=str[i];str[i]=temp;perm(str,k+1,n);/*遞歸調(diào)用*/temp=str[i];str[i]=str[k];str[k]=temp;/*本函數(shù)判斷整數(shù)序列str口是否滿足進(jìn)出棧規(guī)則，若滿足則輸出*/voidprint(intstr[],intn)(inti,j,k,1,m,flag=l,b[2];for(i=0;i<n;i++)/*對(duì)每個(gè)str[i]判斷其后比它小的數(shù)是否為降序序列*/{m=0;for(j=i+l;j<n&&flag;j++)if(str[i]>str[j]){if(m==0)b[m++]=str[j];else{if(str[j]>b[0]){flag=0;}elseb[0]=str[j];if(flag)/*滿足出棧規(guī)則則輸出str□中的序列*/{printf(，z%2d:",cont++);for(i=0;i<n;i++)printfstr[i]);printf(〃\n");8)}intmainO{intstr[100],n,i;printf(*inputaint:*);/*輸出排列的元素個(gè)數(shù)*/scanf&n);for(i=0;i<n;i++)/*初始化排歹U集合*/str[i]=i+l;printf("inputtheresult:\n，z);perm(str,0,n);printf("\n");return0;當(dāng)參與進(jìn)出棧的元素個(gè)數(shù)為4時(shí)，輸出的結(jié)果如下圖所示。該算法執(zhí)行的時(shí)間復(fù)雜度為0(n!)o隨著n的增大，算法的執(zhí)行效率非常的低。非遞歸解法：(2_7_8.c)對(duì)一組數(shù)窮盡所有排列，還可一種更直接的方法，將一個(gè)排列看作一個(gè)長(zhǎng)整數(shù)，則所有排列對(duì)應(yīng)著一組整數(shù)，將這組整數(shù)按從小到大的順序排成一個(gè)數(shù)列，從對(duì)應(yīng)最小的整數(shù)開(kāi)始，按數(shù)列的遞增順序逐一列舉每個(gè)排列對(duì)應(yīng)的每一個(gè)整數(shù)，這能更有效地完成排列的窮舉。從一個(gè)排列找出對(duì)應(yīng)數(shù)列的下一個(gè)排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整來(lái)實(shí)現(xiàn)。倘若當(dāng)前排列為1,2,4,6,5,3,并令其對(duì)應(yīng)的長(zhǎng)整數(shù)為124653。要尋找比長(zhǎng)整數(shù)124653更大的排列，可從該排列的最后一個(gè)數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個(gè)數(shù)字比它前一個(gè)數(shù)字大時(shí)，如本例中的6比它的前一位數(shù)字4大，則說(shuō)明還有可能對(duì)應(yīng)更大整數(shù)的排列。但為順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6與數(shù)字4交換得到的排列為126453就不是排列124653的下一個(gè)排列。為得到排列124653的下一個(gè)排列，應(yīng)從已考察過(guò)的那部分?jǐn)?shù)字中選出比數(shù)字4大，但又是它們中最小的那一個(gè)數(shù)字，比如數(shù)字5,與數(shù)字4交換。該數(shù)字也是從后向前考察過(guò)程中第一個(gè)比4大的數(shù)字，5與4交換后，得到排列125643。在前面數(shù)字2,5固定的情況下，還應(yīng)選擇對(duì)應(yīng)最小整數(shù)的那個(gè)排列，為此還需將后面那部分?jǐn)?shù)字的排列顛倒，如將數(shù)字6,4,3的排列順序顛倒，得到排列1,2,5,3,4,6,這才是排列1,4,6,95,3的下?個(gè)排列。按照以上想法可以編寫(xiě)非遞歸程序?qū)崿F(xiàn)n個(gè)數(shù)的全排列，對(duì)滿足進(jìn)出棧規(guī)則的排列則計(jì)數(shù)并輸出。/*本程序輸出12.??n個(gè)序列進(jìn)棧出棧的序列*/ttinclude<stdio.h>intpl(intn){inta[100];/*最大處理范圍為99個(gè)數(shù)*/intflag=l,flagl=O;FILE*rf;inti,j,k,x,count=0;rf=fopen("stack.txt","w");/*pl.txt用于存放進(jìn)出棧序列結(jié)果*/for(i=l;i<=n;i++)/*初始序列*/while(flag)/*還剩余未輸出的排列*/{flagl=l;/*判斷本次排列是否符合進(jìn)棧出棧序列*/for(i=l;i<=n;i++){j=i+l;while(j<=n&&a[j]>a[i])j++;/*找a[i]后第一個(gè)比a[i]小的元素a[j]*/k=j+l;while(k<=n)/*如果后還有比a[i]小且比a[j]大的元素，則此排列無(wú)效*/{if(a[k]<a[i]&&a[k]>a[j])flagl=0;k++;if(flagl){for(i=l;i<=n;i++)/*輸出當(dāng)前排列*/{printf(z/%4d，z,a[i]);fprintf(rf,"%4d”,a[i]);}printf('\n");fprintf(rf,"\n");count++;/*計(jì)數(shù)器加1*/}i=n;/*從后向前找相鄰位置后大前小的元素值*/while(i>l&&a[i]<a[i-l])i一一;if(i==l)flag=0;/*未找到則結(jié)束*/else若找到，則在該位置的后面從右向左找第一個(gè)比該元素大的值*/while(i>j&&a[i]<a[j])i—;k=a[j];/*交換兩元素的值*/a[i]=k;k=j+1;/*對(duì)交換后后面的數(shù)據(jù)由小到大排序*/10for(i=k+l;i<=n;i++)/*插入排序*/{j=i-l；x=awhile(j>=k&&x<a[j]){a[j+l]=a[j]：j—;)a[j+l]=x;fclose(rf);returncount;/*返回排列總個(gè)數(shù)*/)voidmain(){intn,m=0;printf("pleaseinputn:*);/*輸入排列規(guī)模*/scanf(*%(!*,&n);m-pl(n);printf("\nm=%d”,m)；/*輸出滿足進(jìn)出棧的排列總個(gè)數(shù)*/}程序運(yùn)行時(shí)如果輸入4,則輸出的結(jié)果如下圖所示。該算法的時(shí)間復(fù)雜度也是0(n!)?結(jié)論：如果n個(gè)數(shù)按編號(hào)由小到大的順序進(jìn)棧，進(jìn)棧的過(guò)程中可以出棧，則所有可能的出棧序列的總數(shù)為：1)!!(2)!nnn第3章線性表的鏈?zhǔn)酱鎯?chǔ)1選擇題(1)兩個(gè)有序線性表分別具有n個(gè)元素與m個(gè)元素且nWm,現(xiàn)將其歸并成一個(gè)有序表，其最少的比較次數(shù)是(A)。A.nB.mC.n—1D.m+n(2)非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足(C)。A.p->next==NULLB.p==NULLC.p->next==headD.p==head(3)在帶頭結(jié)點(diǎn)的單鏈表中查找x應(yīng)選擇的程序體是(C)。node*p=head->next;while(p&&p->info!=x)p=p->next;if(p->info-x)returnpelsereturnNULL;node*p=head;while(p&&p->info!=x)p=p->next;returnp;node*p=head->next;while(p&&p->info!=x)p=p->next;returnp;node*p=head;while(p->info!=x)p=p->next;returnp;(4)線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址(D)。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以(5)在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是(B)。A.0(1)B.0(n)C.0(n2)D.0(nlog2n)(6)用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)(D)。A.僅修改隊(duì)頭指針B,僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都可能要修改（7）若從鍵盤(pán)輸入n個(gè)元素，則建立一個(gè)有序單向鏈表的時(shí)間復(fù)雜度為（B）。A.0（n）B.0（n2）C.0（n3）D.0（n?Iog2n）（8）下面哪個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)（D）。A.順序表B.鏈表C.散列表D.隊(duì)列（9）在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A）。A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;C.p->next=p->next;D.p=p->next->next;（10）在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（B）。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;設(shè)計(jì)一個(gè)算法，求一個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)。【答】：?jiǎn)捂湵泶鎯?chǔ)結(jié)構(gòu)定義如下（相關(guān)文件：linklist.h）ttinclude<stdlib.h>12ffinclude<stdio.h>typedefstructnode{intdata;structnode*next;}linknode;typedeflinknode*linklist;/*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表*/linklistcreatlinklist(){linklisthead,r,x,s;head=r=(1inklist)malloc(sizeof(linknode));printfC\n請(qǐng)輸入一組以0結(jié)束的整數(shù)序列：\n〃);scanf&x);while(x){s=(linklist)malloc(sizeof(linknode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;returnhead;}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/voidprint(linklisthead){linklistp;p=head->next;printf(*Listis:\n");while(p){printfp->data);p=p->next;printf("\n");}基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點(diǎn)個(gè)數(shù)的算法程序如下：intcount(linklisthead){intc=0;linklistp=head;while(p){c++;13p=p->next;)returnc;)設(shè)計(jì)一個(gè)算法，求一個(gè)帶頭結(jié)點(diǎn)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)。【答】：帶頭結(jié)點(diǎn)的單鏈表的存儲(chǔ)結(jié)構(gòu)定義同題3.2,實(shí)現(xiàn)本題功能的算法程序如下(3_3.c)ttinclude"linklist,h”intcount(linklisthead){intc=0;linklistp=head->next;while(p){c++;p=p->next;returnc;main()/*測(cè)試函數(shù)*/{linklisthead;head=creatlinklist0;print(head);printf(zz\nLengthofheadis:%dzz,count(head));getchO;}當(dāng)輸入5個(gè)數(shù)據(jù)時(shí)，產(chǎn)生的輸出結(jié)果如下圖所示：設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表中值為y的結(jié)點(diǎn)前面插入一個(gè)值為x的結(jié)點(diǎn)。即使值為x的新結(jié)點(diǎn)成為值為y的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。【答】：ttinclude"linklist,h”voidinsert(linklisthead,inty,intx){/*在值為y的結(jié)點(diǎn)前插入?個(gè)值為x的結(jié)點(diǎn)*/linklistpre,p,s;pre=head;p=head->next;14while(p&&p->data!=y){pre=p;p=p->next;if(p)/*找到了值為y的結(jié)點(diǎn)*/{s=(linklist)malloc(sizeof(linknode));s->data=x;s->next=p;pre->next=s;}}voidmain()/*測(cè)試程序*/{linklisthead;inty,x;head=creatlinklist0;/*創(chuàng)建單鏈表*/print(head);/*輸出單鏈表*/printf(*\n請(qǐng)輸入y與x的值:\n");scanf("%d%d”,&y,&x);insert(head,y,x);print(head);)程序的一種運(yùn)行結(jié)果如下圖所示：設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中各個(gè)結(jié)點(diǎn)值是否有序。【答】：^include"linklist.h"intissorted(linklisthead,charc)/*當(dāng)參數(shù)c='a'時(shí)判斷鏈表是否為升序，當(dāng)參數(shù)c='d'是判斷鏈表是否為降序*/{intflag=l;linklistp=head->next;switch(c){caseJa:/*判斷帶頭結(jié)點(diǎn)的單鏈表head是否為升序*/15while(p&&p->next&&flag){if(p->data<=p->next->data)p=p->next;elseflag=O;}break;case'd':/*判斷帶頭結(jié)點(diǎn)的單鏈表head是否為降序*/while(p&&p->next&&flag){if(p->data>=p->next->data)pzzp->next;elseflag=O;}break;)returnflag;}intmain()/*測(cè)試程序*/{linklisthead;head=creatlinklist();print(head);if(issorted(head,*a*))printf("單鏈表head是升序排列的!\n");elseif(issorted(head,'d'))printf("單鏈表head是降序排列的！\n");elseprintf("單鏈表head是無(wú)序的！\n");}程序運(yùn)行時(shí)的三種輸出結(jié)果如下圖所示：6設(shè)計(jì)一個(gè)算法，利用單鏈表原來(lái)的結(jié)點(diǎn)空間將一個(gè)單鏈表就地轉(zhuǎn)置。【答】：^include"linklist.h"voidverge(1inklisthead){/*本函數(shù)的功能是就地倒置帶頭結(jié)點(diǎn)的單鏈表*/16linklistp,q;p=head->next;head->next=NULL;while(p)/*每次從原表取一個(gè)結(jié)點(diǎn)插入到新表的最前面*/{q=p;p=p->next;q->next=head->next;head->next=q;intmain()/*測(cè)試函數(shù)*/(linklisthead;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/verge(head);/*就地倒置單鏈表*/print(head);/*輸出倒置后的單鏈表*/)設(shè)計(jì)一個(gè)算法，將一個(gè)結(jié)點(diǎn)值自然數(shù)的單鏈表拆分為兩個(gè)單鏈表，原表中保留值為偶數(shù)的結(jié)點(diǎn)，而值為奇數(shù)的結(jié)點(diǎn)按它們?cè)谠碇械南鄬?duì)次序組成一個(gè)新的單鏈表。【答】：ttinclude"linklist.h"linklistsprit(1inklisthead){/*將帶頭結(jié)點(diǎn)的單鏈表head中的奇數(shù)值結(jié)點(diǎn)刪除生成新的單鏈表并返回*/linklistL,pre,p,r;L=r=(1inklist)malloc(sizeof(linknode));r->next=NULL;pre二head;p=head->next;while(p){if(p->data%2==l)/*刪除奇數(shù)值結(jié)點(diǎn)*/{pre->next=p->next;r->next=p;r=p;p=pre->next;else/*保留偶數(shù)值結(jié)點(diǎn)*/{pre=p;p=p->next;}17}r->next=NULL;/*置鏈表結(jié)束標(biāo)記*/returnL;}intmain()/*測(cè)試函數(shù)*/{linklisthead,L;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/L=sprit(head);/*分裂單鏈表head*/printf(*\n原單鏈表為：\n");print(head);/*輸出倒置后的單鏈表*/printfC\n分裂所得奇數(shù)單鏈表為：\n〃)；print(L);)本程序的一組測(cè)試情況如下圖所示。設(shè)計(jì)一個(gè)算法，對(duì)一個(gè)有序的單鏈表，刪除所有值大于x而不大于y的結(jié)點(diǎn)。【答】：ttinclude"linklist,h”voiddeletedata(linklisthead,datatypex,datatypey){/*刪除帶頭結(jié)點(diǎn)單鏈表中所有結(jié)點(diǎn)值大于x而不大于y的結(jié)點(diǎn)*/linklistpre=head,p,q;p=head->next;/*初始化*/while(p&&p->data<=x)/*找第1處大于x的結(jié)點(diǎn)位置*/{pre=p;p=p->next;}while(p&&p->data<=y)/*找第1處小于y的位置*/p=p->next;q=pre->next;/*刪除大于x而小于y的結(jié)點(diǎn)*/pre->next=p;pre=q->next;18while(pre!=p)/*糅放被刪除結(jié)點(diǎn)所占用的空間*/{free(q);q=pre;pre=pre->next;})voidmain()/*測(cè)試函數(shù)*/{linklisthead,L;datatypex,y;head=creatlinklist();/*創(chuàng)建單鏈表*/print(head);/*輸出原單鏈表*/printfC\n請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)區(qū)間：\n")；scanf("%d%d”,&x,&y);deletedata(head,x,y);print(head);/*輸出刪除后的單鏈表*/}設(shè)計(jì)一個(gè)算法，在雙鏈表中值為y的結(jié)點(diǎn)前面插入一個(gè)值為x的新結(jié)點(diǎn)。即使值為x的新結(jié)點(diǎn)成為值為y的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。【答】：首先定義雙鏈表的數(shù)據(jù)結(jié)構(gòu)，相關(guān)文件dlink.h,內(nèi)容如下：typedefintdatatype;/*預(yù)定義的數(shù)據(jù)類型*/typedefstructdlink_node{/*雙鏈表結(jié)點(diǎn)定義*/datatypedata;structdlink_node*llink,*rlink;}dnode;typedefdnode*dlinklist;/*雙鏈表結(jié)點(diǎn)指針類型定義*//*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表*/dlinklistcreatdlinklist(void){dlinklisthead,r,s;datatypex;head=r=(dlinklist)malloc(sizeof(dnode));/*建立雙鏈表的頭結(jié)點(diǎn)*/head->llink=head->rlink=NULL;printfC\n請(qǐng)輸入雙鏈表的內(nèi)容：(整數(shù)序列，以0結(jié)束)\n〃)；scanf&x);while(x)/*輸入結(jié)點(diǎn)值信息,以0結(jié)束*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=r->rlink;/*將新結(jié)點(diǎn)s插入到雙鏈表鏈尾*/19s->llink=r;r->rlink=s;r=s;scanf("%d",&x);}returnhead;}/*輸出雙鏈表的內(nèi)容*/voidprint(dlinklisthead){dlinklistp;p=head->rlink;printfC\n雙鏈表的內(nèi)容是：\n");while(p){printf(*%5d*,p->data);p=p->rlink;本題的求解程序如下:ftinclude<stdio.h>ttinclude"dlink.h"voidinsertxaty(dlinklisthead,datatypey,datatypex){dlinklists,p;/*首先在雙鏈表中找y所在的結(jié)點(diǎn)，然后在y前面插入新結(jié)點(diǎn)*/p=head->rlink;while(p&&p->data!=y)p=p->rlink;if(!p)printf(*\n雙鏈表中不存在值為y的結(jié)點(diǎn)，無(wú)法插入新結(jié)點(diǎn)!\n");else/*插入值為x的新結(jié)點(diǎn)*/{s=(dlinklist)malloc(sizeof(dnode));s->data=x;s->rlink=p;s->llink=p->llink;p->llink->rlink=s;p->llink=s;}}voidmain()/*測(cè)試函數(shù)*/{dlinklisthead;datatypex,y;20head=creatdlinklist();print(head);printfC\n請(qǐng)輸入要輸入的位置結(jié)點(diǎn)值y:\n");scanf&y);printf(*\n請(qǐng)輸入要輸入的結(jié)點(diǎn)值x:\n");scanf&x);insertxaty(head,y,x);/*在值為y的結(jié)點(diǎn)前插入值為x的新結(jié)點(diǎn)*/print(head);/*輸出新的雙鏈表*/getchO;)本程序的一組測(cè)試情況如下圖所示。10設(shè)計(jì)一個(gè)算法，從右向左打印一個(gè)雙鏈表中各個(gè)結(jié)點(diǎn)的值。【答】：本題的雙鏈表定義同題3.9,實(shí)現(xiàn)從右向左打印雙鏈表的各個(gè)結(jié)點(diǎn)的值可以用遞歸程序?qū)崿F(xiàn)如下：ttinclude<stdio.h>ftinclude"dlink.h"voidvprint(dlinklisthead){/*遞歸方法從右向左打印雙鏈表的值*/if(head->rlink){vprint(head->rlink);printf("%5d”,head->r1ink->data);voidmain()/*測(cè)試函數(shù)*/{dlinklisthead;head=creatdlinklist();print(head);printfCXn從右向左打印的雙鏈表的內(nèi)容是:\n〃)；21vprint(head);getchO;}本程序的一組測(cè)試情況如下圖所示。3.11設(shè)計(jì)一個(gè)算法，將一個(gè)雙鏈表改建成一個(gè)循環(huán)雙鏈表。【答】：ttinclude<stdio.h>ttinclude"dlink.h"/*將一個(gè)雙鏈表改成循環(huán)雙鏈表*/voiddlinktocdlink(dlinklisthead){dlinklistr;r=head;while(r->rlink)/*尋找尾結(jié)點(diǎn)*/r=r->rlink;head->11ink=r;r->rlink=head;voidprintcd1ink(dlinklisthead){/*打印雙鏈表*/dlinklistp;p=head->r1ink;whi1e(p!=head){printf(*%5d*,p->data);p=p->rlink;}}intmain()/*測(cè)試函數(shù)*/{dlinklisthead;head=creatdlinklist();dlinktocdlink(head);printf("\n循環(huán)雙鏈表的內(nèi)容是：\n");printcdlink(head);}22第4章字符串、數(shù)組和特殊矩陣稀疏矩陣常用的壓縮存儲(chǔ)方法有(三元組順序存儲(chǔ))和(十字鏈表)兩種。設(shè)有一個(gè)10X10的對(duì)稱矩陣A采用壓縮方式進(jìn)行存儲(chǔ)，存儲(chǔ)時(shí)以按行優(yōu)先的順序存儲(chǔ)其下三角陣，假設(shè)其起始元素a00的地址為1,每個(gè)數(shù)據(jù)元素占2個(gè)字節(jié)，則a65的地址為(53)。若串S二usoftware",其子串的數(shù)目為(36)。常對(duì)數(shù)組進(jìn)行的兩種基本操作為(訪問(wèn)數(shù)據(jù)元素)和(修改數(shù)組元素)。要計(jì)算一個(gè)數(shù)組所占空間的大小，必須已知(數(shù)組各維數(shù))和(每個(gè)元素占用的空間)。對(duì)于半帶寬為b的帶狀矩陣，它的特點(diǎn)是：對(duì)于矩陣元素aij,若它滿足(|i-jI>b),則aij=Oo字符串是一種特殊的線性表，其特殊性體現(xiàn)在(該線性表的元素類型為字符)。試編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)在順序存儲(chǔ)方式下字符串的strcompare(SI,S2)運(yùn)算。【答】：#include<stdio.h>ttinclude<string.h>ttdefineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;/*函數(shù)strcompare()的功能是：當(dāng)sl>s2時(shí)返回1,當(dāng)si二二s2時(shí)返回0,當(dāng)sl<s2時(shí)返回-1*/intstrcompare(seqstringsi,seqstrings2){inti,m=0,len;len=sl.Iength<s2.length?sl.length:s2.length;for(i=0;i<=len;i++)if(si.str[i]>s2.str[i]){m=l;break;}elseif(si.str[i]<s2.str[i]){m=-l;break;}returnm;intmainO{seqstringsi,s2;inti,m;printf("inputchartosl:\n");23gets(si.str);length=strlen(si.str);printf(''inputchartos2:\n");gets(s2.str);length=strlen(s2.str);m=strcompare(si,s2);if(m=l)printf("sl>s2\n");elseif(m==-l)printf("s2>sl\n");elseif(m==0)printf(*sl=s2\nzz);}4.9試編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)在順序存儲(chǔ)方式下字符串的replace(S,Tl,T2)運(yùn)算。【參考程序1】：/*本程序用來(lái)在順序存儲(chǔ)下用快速匹配模式實(shí)現(xiàn)在字符串S中用T2替換所有T1出現(xiàn)的可能*/#include<malloc.h>#include<string.h>#include<stdio.h>#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;〃求next口函數(shù)voidgetnext(seqstring*p,intnext[]){inti,j;next[0]=-l;i=0;j=-l;while(i<p->length)(if(j==-l||p->str[i]==p->str[j]){++i;++j;next[i]=j;}elsej=next[j];}}〃快速模式匹配算法intkmp(seqstring*t,seqstring*p,intnext[],inttemppos){inti,j;24i=temppos,j=0;while(i<t->length&&j<p->length)if(j==-lIt->str[i]==p->str[j]){i++；j++；}elsej=next[j];}if(j==p->length)return(i-p->length);elsereturn(-1);}〃替換函數(shù)voidtakeplace(seqstring*S,seqstring*Tl,seqstring*T2){intnext[maxsize],temppos=0,pos,i;intlent1,lent2;lentl=strlen(Tl->str);//求T1串長(zhǎng)度lent2=strlen(T2->str);〃求T2串長(zhǎng)度getnext(Tl,next);〃求T1串的next[]向量do{pos=kmp(S,Tl,next,temppos);〃快速模式匹配temppos=pos+T1->1ength;if(pos!=-l)〃匹配成功(if(lentl>lent2)//Tl串長(zhǎng)度大于T2串長(zhǎng)度f(wàn)or(i=temppos;i<S->length;i++)〃前移S->str[i-lentl+lent2]=S->str[i];for(i=0;i<T2->length;i++)〃替換S->str[pos+i]=T2->str[i];S->length-=lentl-lent2;//修改長(zhǎng)度)elseif(lent2>lentl)//T2串長(zhǎng)度大于T1串長(zhǎng)度ifor(i=S->length-l;i>=temppos;i-)〃后移留空S->str[i+lent2-lentl]=S->str[i];for(i=0;i<T2->length;i++)〃替換25S->str[pos+i]=T2->str[i];S->length+=lent2-lentl;〃修改長(zhǎng)度}else//Tl長(zhǎng)度與T2長(zhǎng)度相等{for(i=0;i<T2->length;i++)S->str[pos+i]=T2->str[i];}temppos=pos+T2->length;〃修改下一次模式匹配的起點(diǎn)位置}}while(pos!=-1);S->str[S->length]=，\0f;intmain(){seqstring*S,*T1,*T2;printf("\n\n本程序用來(lái)實(shí)現(xiàn)字符串替換，將S中用T2替換T1所有出現(xiàn)\nThisprogramisusedforcharactersbatchtakeingplace,TheT1charactersbatchwilltakeplaceal1theT2'sappearancesincharactersbatchS:\n\n");printf(“請(qǐng)輸入S中的字符(pleseinputcharactersbatchS:)\n");S=(seqstring*)malloc(sizeof(seqstring));Tl=(seqstring*)malloc(sizeof(seqstring));T2=(seqstring*)malloc(sizeof(seqstring));scanfS->str);S->length=strlen(S->str);printf("輸入要被替換的串(inputTl):\n*);scanf('%s”,Tl->str);Tl->length=strlen(Tl->str);printf("輸入替換串(inputT2):\n");scanfT2->str);T2->length=strlen(T2->str);takeplace(S,Tl,T2);printf(〃替換后的字符串為：\n〃)；printf("%s\n”,S->str);free(S);free(Tl);free(T2);[參考程序2]：#include<stdio.h>26ftdefineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;voidgetnext(seqstringp,intnext[])〃求模式的next函數(shù){inti,j;next[0]=-l;i=0;j=-l；while(i<p.length){if(j==-l!p.str[i]==p.str[j]){++i;++j;next[i]=j;}elsej=next[j];}}voidreplace(seqstring*s,seqstringtl,seqstringt2,intnext[]){inti,j,k,c,m;i=0;j=O;k=O;while(i<s->length)｛產(chǎn)0；while(i<s->length&&j<tl.length){if(j==-ls->str[i]==tl.str[j]){i++；j++;}elsej=next[j];}if(j=tl.length)//匹配成功{c=i-tl.length;if(tl.Iength==t2.length)〃兩串長(zhǎng)度相等直接替換for(k=0;k<t2.length;k++)s->str[c+k]=t2.str[k];elseif(tl.Iength<t2.length){for(m=s->length-l;m-)s->str[t2.length-tl.length+m]=s->str[ni];//后移留空f(shuō)or(k=0;k<t2.length;k++)s->str[c+k]=t2.str[k];s->length=s->length-tl.Iength+t2.length;s->str[s->length]=，\0J;)27else{for(m=i-l;m<s->length;m++)〃前移s->str[m-tl.Iength+t2.length]=s->str[m];for(k=0;k<t2.length;k++)s->str[c+k]=t2.str[k];s->length=s->length-tl.Iength+t2.length;s->str[s->length]=，\0*;)i=i+t2.length-tl.length;}i++；}}intmainO{intnext[MAXSIZE];seqstrings,tl,t2;printf("Inputstrings:");〃輸入主串gets(s.str);printf(*\nlnputstringtl:*)；//輸入模式串gets(tl.str);printfCAnlnputstringt2:〃)；//輸入擬替換的串gets(t2.str);s.length=strlen(s.str);tl.length=strlen(tl.str);t2.Iength=strlen(t2.str);getnext(tl,next);replace(&s,tl,t2,next);puts(s.str);4.10試編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)在鏈?zhǔn)酱鎯?chǔ)方式下字符串的strcompare(SI,S2)運(yùn)算。【參考程序】：/*建立字符串鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)文件linkstring,h*/ttinclude<stdio.h>ttinclude<stdlib.h>typedefstructnode[chardata;structnode*next;}linkstrnode;28typedeflinkstrnode*1inkstring;/* *//*尾插法建立單鏈表*//* */voidstrcreate(1inkstring*S){charch;linkstrnode*p,*r;*S=NULL;r=NULL;while((ch=getchar())!=>\n){p=(linkstrnode*)malloc(sizeof(linkstrnode));p->data=ch;/*產(chǎn)生新結(jié)點(diǎn)*/if(*S==NULL)/*新結(jié)點(diǎn)插入空表*/{*S=p;r=p;}else{r->next=p;r=p;}}if(r!=NULL)r->next=NULL;/*處理表尾結(jié)點(diǎn)指針域*/}/* *//*輸出單鏈表的內(nèi)容*//* */voidprint(linkstringhead)(linkstrnode*p;p=head;while(p){printf(，z%c->”,p->data);p=p->next;}printf("\n");}ttinclude"linkstring,h”intstrcompare(1inkstrnode*Sl,1inkstrnode*S2){while(S1&&S2){if(Sl->data>S2->data)return1;elseif(Sl->data<S2->data)29return-1;Sl=Sl->next;S2=S2->next;}if(SI)return1;elseif(S2)return-1;return0;}intmainO{linkstringsi,s2;intk;printfCAnPleaseinputstrcreate(&sl);/*建立字符串si*/print(si);printf("\nPleaseinputs2:");strcreate(&s2);/*建立字符串s2*/print(s2);k=strcompare(sl,s2);if(k==l)printf("sl>s2");elseif(k=="l)printfCsl<s2*);elseprintf("si二二s2〃)；4.11試編寫(xiě)一個(gè)函數(shù)，實(shí)現(xiàn)在鏈?zhǔn)酱鎯?chǔ)方式下字符串的replace(S,Tl,T2)運(yùn)算。/*題目：鏈?zhǔn)酱鎯?chǔ)方式下字符串的replaced,T1,T2)運(yùn)算*/【參考程序】：ttinclude“l(fā)inkstring,h”/*單鏈表拷貝函數(shù)*/linkstringcopy(linkstringhead){linkstringL=NULL,r=NULL,s,p;p=head;while(p){s=(linkstring)malloc(sizeof(1inkstrnode));s->data=p->data;if(L==NULL)L=r=s;else{r->next=s;30r=s;}p=p->next;}if(r!=NULL)r->next=NULL;returnL;/*-—*//*-/*在字符串S中用T2替換T1*/—*/linkstringreplace(linkstringS,linkstringTl,linkstringT2){linkstringp,q,r,s,pre,temp,pos;intflag=l;if(S==NULL||T1==NULL)returnS;/*若S為空或T1為空，則原串不變*/pre=NULL;pos=S;/*pos表示可能的T1串在S中的起始位置*/while(pos&&flag)/*flag表示S中存在Tl*/{P二pos;q=Tl;while(p&&q)/*從pos開(kāi)始找子串Tl*/{if(p->data==q->data){p=p->next;q=q->next;}else{pre=pos;pos=pos->next;p=pos;q二Tl;}}if(q!=NULL)flag=0;/*未找到子串Tl*/else{flag=1;/*找到了子串門(mén)，用T2代替Tl*/r=pos;while(r!=p)/*首先刪除子串Tl,最后p指向刪除串T1的下一個(gè)結(jié)點(diǎn)*/{s=r;r=r->next;free(s);}if(T2!=NULL)/*T2不為空*/31{temp=r=copy(T2);/*復(fù)制一個(gè)T2串*/while(r->next!=NULL)/*找temp串的尾結(jié)點(diǎn)*/r=r->next;r->next=p;if(pre==NULL)/*如果T1出現(xiàn)在S的鏈頭*/S二temp;/*新串成為鏈?zhǔn)?/else/*T1不是鏈?zhǔn)状?/pre->next=temp;pre=r;pos=p；/*從p開(kāi)始繼續(xù)找子串n*/)else/*原T2子串為空*/{if(pre=NULL)/*T1為鏈?zhǔn)状?/S=p;elsepre->next=p;pos=p;returnS;intmain(){linkstringS,Tl,T2;printfCAnPleaseinputS:");strcreate(&S);/*建立字符串S*/print(S);printf(*\nPleaseinputT1:*);strcreate(&T1);/*建立字符串Tl*/print(Tl);printf(*\nPleaseinputT2:');strcreate(&T2);/*建立字符串T2*/print(T2);S=replace(S,Tl,T2);printf(*\nTheresultis:\n");print(S);}4.12已知如下字符串，求它們的next數(shù)組值：“bbdcfbbdac”32【答】：-1010001230waaaaaaa【答】：-1012345ababbabab”【答】：-1001123213已知正文t="ababbaabaa"，模式p:“aab”,試使用KMP快速模式匹配算法尋找P在t中首次出現(xiàn)的起始位置，給出具體的匹配過(guò)程分析。【答】：模式P的next向量如下表所示：012aab-101第一趟匹配：0123456789ababbaabaaaai=l,j=l,匹配失敗，此時(shí)j取next[l]=0,即下一趟匹配從i=l,j=0開(kāi)始；第二趟匹配：0123456789ababbaabaaai=Lj=0,匹配失敗,此時(shí)j=next[0]=T,下一趟匹配從i=2,j=0開(kāi)始;第三趟匹配：0123456789ababbaabaai=3,j=l,匹配失敗，此時(shí)j=next[l]=O,下一趟匹配從i=3,j=0開(kāi)始；第四趟匹配：0123456789ababbaabaaai=3,j=0,匹配失敗，此時(shí)j=next[0]=配,下一趟匹配從i=4,j=0開(kāi)始；第五趟匹配：0123456789ababbaabaaai=4,j=0,匹配失敗,此時(shí)j=next[0]=T,下一趟匹配從i=5,j=0開(kāi)始；第五趟匹配：012345678933ababbaabaaaabi=8,j=3,匹配完成，表明匹配成功的位置是：i-j=5。4.14已知三維數(shù)組A[3][2][4],數(shù)組首地址為100,每個(gè)元素占用1個(gè)存儲(chǔ)單元，分別計(jì)算數(shù)組元素A[0][1][2]在按行優(yōu)先和按列優(yōu)先存儲(chǔ)方式下的地址。【答】：A[0][1][2]按行優(yōu)先方式在內(nèi)存的存儲(chǔ)地址為：100+0*8+1*4+2=106[2]按列優(yōu)先方式在內(nèi)存的儲(chǔ)儲(chǔ)地址為：100+2*6+1*3+0*8=1154.15已知兩個(gè)稀疏矩陣A和B,其行數(shù)和列數(shù)均對(duì)應(yīng)相等，編寫(xiě)一個(gè)函數(shù)，計(jì)算A和B之和，假設(shè)稀疏矩陣采用三元組表示。【參考程序1】：#include<stdio.h>typedefstruct{intdata[100][100];intm,n;/*分別存放稀疏矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}matrix;typedefintspmatrix[100][3];〃三元組存儲(chǔ)結(jié)構(gòu)spmatrixc;voidadd(spmatrixa,spmatrixb,spmatrixc)〃基于三元組結(jié)構(gòu)的矩陣相加算法{inti,j,k,t,r;i=j=k=l;while(i<=a[0][2]&&j<=b[0][2]){if(a[i][0]<b[j][0]||(a[i][0]==b[j][0]&&a[i][l]<b[j][l])){c[k][0]=a[i][0]:c[k][l]=a[i][1];c[k「2]=a⑴⑵;i++;k++;)elseif(a[i][0]>b[j][0]||(a[i][0]==b[j][0]&&a[i][l]>b[j][1])){c[k][O]=b[j][0];c[k][l]=b[j][1];c[kH2]=b[j]⑵;j++；k++;elseif(a[i][O]=b[j][0]&&(a[i][l]=b[j][1])){c[k][O]=a[i][0];34c[k][l]=a⑴[1];c[k][2]=a[i][2]+b[j][2];i++;j++;if(c[k][2]!=0)k++;/*如果相加的和不為0,則生成一個(gè)有效項(xiàng)*/))while(j<=b[0][2])(c[k][0]=b[j][0];c[k][l]=b[j][l]：c[k][2]=b[j][2];j++；k++;)while(i<=a[0][2])!c[k][0]=a[i][0];c[k][l]=a[i][l];c[k][2]=a[i]⑵；i++;k++;c[0][0]=a[0][0]:c[0][l]=a[O][1];c[0][2]=k-l;)//函數(shù)compressmatrix將普通矩陣存儲(chǔ)轉(zhuǎn)換為二元組存儲(chǔ)結(jié)構(gòu)voidcompressmatrix(matrix*A,spmatrixB){inti,j,k：k=l;for(i=0;i<A->m;i++)for(j=0;j<A->n;j++)if(A->data[i][j]!=0){B[k][0]=i;B[k][l]=j;B[k][2]=A->data[i][j]：k++;)B[0][0]=A->m;B[0][l]=A->n;B[0][2]=k-l：35i=0;printf("thespmatrixis:\n");while(i<=B[0][2]){printf("%d%5d%5d\n",B[i][0],B[i][1],B[i][2]):i++；voidcreat(intr,intw,matrix*s){inti,j,data;printf('inputnumbers:\n/z);for(i=0;i<r;i++)for(j=0;j<w;j++)scanf("%d”,&data);s->data[i][j]=data;}printf(/zthearrayis:\n");for(i=0;i<r;i++){for(j=0;j<w;j++)printf("%5d”,s->data[i][j]);printf;)s->m=r;s->n=w;}intmain(){matrixp,q;spmatrixa,b,c;intr,w,i;i=0;printf(*inputr,w<);/*輸入行和列*/scanf("%d%d”,&r,&w);creat(r,w,&p);creat(r,w,&q);compressmatrix(&p,a);compressmatrix(&q,b);i=0;add(a,b,c);printf(，zthespmatrixcis:\n〃)；36while(i<=c[0][2]){printf(*%d%5d%5d\n*,c[i][0],c[i][1],c[i][2]);i++；}}程序運(yùn)行時(shí)先輸入矩陣的行和列，然后按普通矩陣格式輸入矩陣值，一組程序測(cè)試用例運(yùn)行結(jié)果如下圖：【參考程序2】：37#include<stdio.h>#include<malloc.h>ttdefineMAX100typedefstruct{intdata[MAX][3];intm,n,value;}matrix;matrix*Input(matrix*A){inti,j;A=(matrix*)malloc(sizeof(matrix));scanf("%d%d%d”,&A->m,&A->n,&A->value);A->data[0][0]=A->m;A->data[0][1]=A->n;A->data[0][2]=A->value;for(i=1;i<=A->value;i++){for(j=0;j<3;j++)scanf("%d”,&A->data[i][j]);)returnA;)voidOutput(matrix*A){inti,j;printf("************************************\n");for(i=0;i<=A->value;i++){for(j=0;j<3;j++)printf(*%d*,A_>data[i][j]);printf('\n");}printf("************************************\n");}matrix*addmatrix(matrix*A,matrix*B,matrix*C){inti=1,j=1,k=1;C=(matrix*)malloc(sizeof(matrix));while(i<=A->value&&j<=B->value)(if(A->data[i][0]==B->data[j][0])(38if(A->data[i][1]==B->data[j][1]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2]+B->data[j][2];if(C->data[k][2]!=0)k++;i++；j++；elseif(A->data[i][1]<B->data[j][1]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++；}else(C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];k++;j++；}}elseif(A->data[i][0]<B->data[j][0]){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++；elseC->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];39k++;j++；}}while(i<=A->value){C->data[k][0]=A->data[i][0];C->data[k][1]=A->data[i][1];C->data[k][2]=A->data[i][2];k++;i++;}while(j<=B->value){C->data[k][0]=B->data[j][0];C->data[k][1]=B->data[j][1];C->data[k][2]=B->data[j][2];k++;j++；C->data[O][0]=(A->data[0][0]>=B->data[0][0])?A->data[0][0]:B->data[0][0];C->data[0][1]=(A->data[0][l]>=B->data[0][l])?A->data[0][1]:B->data[0][1];C->data[0][2]=k-1;C->value=k-l;returnC;}intmainO{matrix*A=NULL,*B=NULL,*C=NULL;printf("提示：請(qǐng)按三元組格式輸入矩陣內(nèi)容。\n");printf(，zInputAmatrix:\nz，);A=Input(A);printf("InputBmatrixAn"");B=Input(B);C=addmatrix(A,B,C);Output(C);free(A);free(B);40free(C);return0;程序運(yùn)行時(shí)按照三元組的格式輸入矩陣信息，程序運(yùn)行結(jié)果如下圖所示:16寫(xiě)出兩個(gè)稀疏矩陣相乘的算法，計(jì)算：Cpn=Apm*Bmn其中，A、B和C都采用三元組表示法存儲(chǔ)。【答】：clude<stdio.h>ttinclude<malloc.h>#defineMAX100typedefstruct{intdata[MAX][3];intm,n,value;}matrix;matrix*Input(matrix*A){inti,j;A=(matrix*)malloc(sizeof(matrix));scanf("%d%d%d”,&A->m,&A->n,&A->value);A->data[0][0]=A->m;41A->dat