第2章線(xiàn)性表習(xí)題解答

1、 第2章習(xí)題1第2章習(xí)題2.1若將順序表中記錄其長(zhǎng)度的分量listlen改為指向最后一個(gè)元素的位置last，在實(shí)現(xiàn)各基本運(yùn)算時(shí)需要做那些修改？【解】/用線(xiàn)性表最后一個(gè)元素的下標(biāo)last代替listLen實(shí)現(xiàn)順序表#define MAXLEN 100typedef int elementType;typedef struct sllLastelementType dataMAXLEN;int last;seqList;/初始化void initialList(seqList &S)S.last=-1;/求表長(zhǎng)度int listLength(seqList S)return S.last+

2、1;/按序號(hào)取元素bool getElement(seqList S,int i,elementType &x) if(i<1 | i>S.last+1) /i為元素編號(hào)，有效范圍在1-S.last+1之間return false;elsex=S.datai-1;return true;/查找元素x，成功：返回元素編號(hào)；失敗：返回0int listLocate(seqList S,elementType x)int i;for(i=0;i<=S.last;i+)if(S.datai=x)return i+1; /找到，轉(zhuǎn)換為元素編號(hào)輸出return 0;/插入元素in

3、t listInsert(seqList &S,elementType x, int i)int k;if(S.last>MAXLEN-1)return 0; /表滿(mǎn)，返回0else if(i<1 | i>S.last+2)return 1; /插入位置查處范圍，返回1elsefor(k=S.last;k>=i-1;k-)S.datak+1=S.datak;S.datai-1=x;S.last+;return 2;/刪除元素int listDelete(seqList &S,int i)int k;if(S.last=-1)return 0; /空表，返

4、回0else if(i<1 | i>S.last+1)return 1; /刪除元素編號(hào)超出范圍，返回1elsefor(k=i;k<=S.last;k+)S.datak-1=S.datak;S.last-;return 2;/7. 打印表中所有元素void printList(seqList L)int i;for(i=0;i<=L.last;i+)cout<<L.datai<<"t" /元素之間以制表符分割cout<<endl;/8. 交互輸入數(shù)據(jù)元素-特殊輸入結(jié)束void listInputC(seqList

5、&L)if(L.last>=0)cout<<"順序表已經(jīng)存在，請(qǐng)先初始化，再輸入元素。"<<endl;return;elementType x;cout<<"請(qǐng)輸入數(shù)據(jù)元素(整數(shù)，-9999退出):"<<endl;cout<<"x="cin>>x;while(x!=-9999)L.last+;L.dataL.last=x;cout<<"x="cin>>x;/隨機(jī)數(shù)創(chuàng)建順序表void rndCList(seq

6、List &L)int i;int n,m;L.last=-1;cout<<"請(qǐng)輸入要產(chǎn)生的隨機(jī)數(shù)個(gè)數(shù)，n="cin>>n;if(n>MAXLEN-1)cout<<"您要求產(chǎn)生的隨機(jī)數(shù)個(gè)數(shù)超出了查找表長(zhǎng)度"<<MAXLEN-1<<"，創(chuàng)建順序表失敗。"<<endl;return;cout<<"請(qǐng)輸入控制隨機(jī)數(shù)大小參數(shù)，比如100以?xún)?nèi)數(shù)，請(qǐng)輸入100，m="cin>>m; srand(unsigned)tim

7、e(NULL);/產(chǎn)生隨機(jī)數(shù)種子/srand(unsigned)GetTickCount();/產(chǎn)生隨機(jī)數(shù)種子for(i=0;i<n;i+) /隨機(jī)數(shù)寫(xiě)入排序表AL.datai=rand()%m; L.last=n-1; /表長(zhǎng)度為ncout<<endl;2.2試用順序表表示較多位數(shù)的大整數(shù)，以便于這類(lèi)數(shù)據(jù)的存儲(chǔ)。請(qǐng)選擇合適的存放次序，并分別寫(xiě)出這類(lèi)大數(shù)的比較、加、減、乘、除等運(yùn)算，并分析算法的時(shí)間性能。【解】順序表0單元存放操作數(shù)的符號(hào)，區(qū)分操作數(shù)是正數(shù)還是負(fù)數(shù)；為方便處理運(yùn)算時(shí)進(jìn)位和借位，數(shù)據(jù)的低位存放數(shù)組低位，高位存放數(shù)組高位?！緯r(shí)間性能】加減法：O(max(m,n)乘

8、除法：O(m´n)2.3試用順序表表示集合，并確定合適的約定，在此基礎(chǔ)上編寫(xiě)算法以實(shí)現(xiàn)集合的交、并、差等運(yùn)算，并分析各算法的時(shí)間性能?！窘狻?求C=AB依次讀取A的元素，檢查次元素是否在B中，若在B中，則為交集元素，插入C中。void interSet(seqList A, seqList B, seqList &C)int i;for(i=0;i<A.listLen;i+)if(listLocate(B,A.datai)!=0) /A.datai在B中出現(xiàn)，是交集元素，插入C中l(wèi)istInsert(&C,A.datai,C.listLen+1);/求C=AB現(xiàn)

9、將A中元素全部插入C中。依次讀取B中元素，檢查是否出現(xiàn)在A(yíng)中，若不在A(yíng)中，則為并集元素，插入C中。void mergeSet(seqList A, seqList B, seqList &C)int i;for(i=0;i<A.listLen;i+) /A中元素全部插入C中l(wèi)istInsert(&C,A.datai,C.listLen+1); for(i=0;i<B.listLen;i+)if(listLocate(A,B.datai)=0) /B.datai不在A(yíng)中，插入ClistInsert(&C,B.datai,C.listLen+1);/求C=A-B

10、依次讀取A中元素，檢查是否在B中出現(xiàn)，若不在B中，則為差集元素，插入C中。void differenceSet(seqList A,seqList B,seqList &C)int i;for(i=0;i<A.listLen;i+)if(listLocate(B,A.datai)=0)listInsert(&C,A.datai,C.listLen+1); /A.datai不在B中，插入C【算法分析】時(shí)間復(fù)雜度：O( |A| ´ |B| )2.4假設(shè)順序表L中的元素遞增有序，設(shè)計(jì)算法在順序表中插入元素x，要求插入后仍保持其遞增有序特性，并要求時(shí)間盡可能少?！窘狻咳?/p>

11、果表空間滿(mǎn)，插入失敗，返回-1；否則，從L最后一個(gè)元素開(kāi)始，與x比較，若大于x，元素后移，直到L中元素小于或等于x，這個(gè)元素的后面的單元即為x的插入位置，插入成功返回插入位置。/空間滿(mǎn)：返回值-1；正確插入：返回表中的插入位置int incInsert(seqList &L,elementType x)int i=L.listLen-1;if(L.listLen=MAXLEN)return -1; /表空間已滿(mǎn)，不能插入新的元素else while(i>=0 && L.datai>x)L.datai+1=L.datai;i-;L.datai+1=x; /插入

12、xL.listLen+; /修改表長(zhǎng)度return i+2; /成功插入，返回x在順序表中的插入位置（元素編號(hào)）【算法分析】時(shí)間復(fù)雜度：O(n)2.5假設(shè)順序表L中的元素遞增有序，設(shè)計(jì)算法在順序表中插入元素x，并要求在插入后也沒(méi)有相同的元素，即若表中存在相同的元素，則不執(zhí)行插入操作。【解】與上題相似，只是在移動(dòng)插入元素之前，檢查L(zhǎng)中是否已經(jīng)存在值x，若存在，插入失敗，返回-2。/空間滿(mǎn)：返回值-1；x已經(jīng)存在返回-2；正確插入：返回表中的插入位置int incInsert(seqList &L,elementType x)int i;if(L.listLen=MAXLEN)return

13、 -1; /表空間已滿(mǎn)，不能插入新的元素else for(i=0;i<L.listLen;i+) if(L.datai=x) return -2; /元素x已經(jīng)存在，插入失敗，返回-2i=L.listLen-1;while(i>=0 && L.datai>x) /后移元素L.datai+1=L.datai;i-;L.datai+1=x; /插入xL.listLen+; /修改表長(zhǎng)度return i+2; /成功插入，返回x在順序表中的插入位置（元素編號(hào)）2.6設(shè)計(jì)算法以刪除順序表中重復(fù)的元素，并分析算法的時(shí)間性能?！窘狻俊痉治觥咳匮h(huán)實(shí)現(xiàn)。第一層循環(huán)，從左往

14、右依次取出L元素，用i指示；第二層循環(huán)，對(duì)i元素在L中循環(huán)查重，用下標(biāo)j指示；第三重循環(huán)，刪除重復(fù)元素。查重和刪除從j=L.listLen-1開(kāi)始，效率稍微好一點(diǎn)，因?yàn)檫@樣重復(fù)元素本身不需重復(fù)移動(dòng)。如果從i+1開(kāi)始查重、刪除，則j+1以后的重復(fù)元素會(huì)被移動(dòng)?！舅惴枋觥縱oid DeleteRepeatData(seqList & L)int i,j;if(L.listLen=0)cout<<"當(dāng)前順序表空！"<<endl;return;if(L.listLen=1)cout<<"當(dāng)前順序表只有一個(gè)元素！"&l

15、t;<endl;return;i=0;while(i<L.listLen-1)for(j=L.listLen-1; j>i; j-) /從后往前刪除，效率較高if(L.datai=L.dataj) /元素重復(fù)，調(diào)用刪除listDelete(&L,j+1); /調(diào)用刪除函數(shù)，下標(biāo)差1，所以+1 /以下部分代碼是直接刪除，沒(méi)有調(diào)用刪除函數(shù)/int k;/for(k=j; k<L.listLen-1; k+)/L.datak=L.datak+1;/L.listLen-;i+; 【算法分析】時(shí)間性能：O(n3)2.7假設(shè)順序表L中的元素按從小到大的次序排列，設(shè)計(jì)算法以刪

16、除表中重復(fù)的元素, 并要求時(shí)間盡可能少。要求：（1）對(duì)順序表（1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9）模擬執(zhí)行本算法，并統(tǒng)計(jì)移動(dòng)元素的次數(shù)。（2）分析算法的時(shí)間性能?！窘狻俊痉治觥繉⒃胤殖蓛蓚€(gè)部分：已經(jīng)處理元素和待處理元素。已經(jīng)處理部分返回L中，用下標(biāo)i指示最后一個(gè)元素，初始化i=0。待處理部分用下標(biāo)j指示第一個(gè)元素，初始化j=1.左邊下標(biāo)小于i的元素已經(jīng)處理好重復(fù)，等于i是當(dāng)前正在處理的元素，將datai與dataj進(jìn)行比較，會(huì)出現(xiàn)下列情況： datai=dataj，說(shuō)明j指示的是i的重復(fù)元素，繼續(xù)處理j的下一個(gè)元素，即執(zhí)行j+。 datai<data

17、j， 說(shuō)明j指示元素與i的元素不同，如果i+1!=j，將j元素復(fù)制到i+1，即：L.datai+1=L.dataj，再執(zhí)行j+，i+；若i+1=j，說(shuō)明j是i的直接后繼，無(wú)需復(fù)制，直接執(zhí)行i+，j+。循環(huán)執(zhí)行上述操作，直到表尾。修改L的長(zhǎng)度為i+1?！舅惴枋觥縱oid DeleteRepeatData(seqList & L)int i,j; /分別指向已處理部分最后元素和未處理部分第一個(gè)元素，皆為數(shù)組下標(biāo)if(L.listLen<2)return; /少于2個(gè)元素，直接退出i=0; /初始化i指向第一個(gè)元素j=1; /j指向第二個(gè)元素while(j<L.listLen)

18、if(L.datai=L.dataj) /j為重復(fù)元素，j后移j+;else /因?yàn)長(zhǎng)遞增，所以剩下情況即L.datai<L.dataj，j為目標(biāo)元素 /如果j=i+1，說(shuō)明j緊隨i，無(wú)需移動(dòng)元素，直接i+、j+即可if(i+1)!=j)L.datai+1=L.dataj; /j元素復(fù)制到i+1i+; /無(wú)論那種情況，都需要同時(shí)后移i、jj+;L.listLen=i+1; /修改表的實(shí)際長(zhǎng)度【算法分析】時(shí)間復(fù)雜度O(n)。上例中只需移動(dòng)8個(gè)元素。2.8若遞增有序順序表A、B分別表示一個(gè)集合，設(shè)計(jì)算法求解A=AÇB，并分析其時(shí)間性能?！窘狻俊痉治觥繉忣}：A、B為集合，說(shuō)明兩個(gè)表中

19、都沒(méi)有重復(fù)元素 A=AB，即要求交集元素就放在A(yíng)表中，而不是創(chuàng)建一個(gè)新表來(lái)存放。設(shè)置兩個(gè)指針ia、ib分別指向A、B表當(dāng)前處理的元素；設(shè)置一個(gè)指針i指示已經(jīng)求取的交集元素在A(yíng)的表中的最后元素位置；比較A、B表當(dāng)前元素，會(huì)出現(xiàn)以下三種情況(1) A.dataia=B.dataib，則ia或ib是交集元素，如果ia!=i+1，將ia元素復(fù)制到i+1,即：A.datai+1=A.dataia；否則，若ia=i+1，說(shuō)明ia就在i的后面，無(wú)需復(fù)制元素。最后，無(wú)論那種情況，修改指針：ia+，ib+，i+(2) A.dataia<B.dataib，當(dāng)前元素為非交集元素，只需移動(dòng)ia，即ia+(3)

20、A.dataia>B.dataib，當(dāng)前元素為非交集元素，只需移動(dòng)ib，即ib+重復(fù)以上過(guò)程，直至A、B中至少一個(gè)表結(jié)束。修改A表長(zhǎng)度為i+1?！舅惴枋觥縱oid InterSet(seqList &A, seqList &B)int i=-1; /為了最后更新交集元素表長(zhǎng)度操作一致，初始化為-1int ia=0, ib=0; /A、B表當(dāng)前元素的數(shù)組下標(biāo)while(ia<A.listLen && ib<B.listLen)if(A.dataia=B.dataib) /ia和ib指示的是交集元素if(ia!=i+1) /ia元素復(fù)制到i+1，

21、否則ia位置即目標(biāo)位置，不需復(fù)制元素A.datai+1=A.dataia;i+;ia+;ib+;else if(A.dataia<B.dataib) /以下為非交集元素處理ia+;elseib+;A.listLen=i+1; /更新A表長(zhǎng)度，使等于交集元素個(gè)數(shù)。2.9遞增有序順序表A、B分別表示一個(gè)集合，設(shè)計(jì)算法求解A=AB，并分析其時(shí)間性能?！窘狻俊痉治觥繉忣}：A=A-B，即要求要利用A表的空間保存差集元素，而不是創(chuàng)建一個(gè)新表。設(shè)置兩個(gè)指針ia、ib分別指向A、B表當(dāng)前處理的元素；設(shè)置一個(gè)指針i指示已經(jīng)求取的差集元素在A(yíng)的表中的最后元素位置；比較A、B表當(dāng)前元素，會(huì)出現(xiàn)以下三種情況(1

22、) A.dataia=B.dataib，則ia或ib是交集元素，不是A-B中元素，直接跳過(guò)，修改指針：ia+，ib+。(2) A.dataia>B.dataib，ia指示的元素可能在B表ib指示的元素后面，ia不動(dòng)，移動(dòng)ib，即ib+。(3) A.dataia<B.dataib，ia指示的元素不可能在B中出現(xiàn)，故比為A-B中元素。需要的話(huà)遷移到目標(biāo)位置，即 (i+1)!=ia時(shí)，執(zhí)行A.datai+1=A.dataia。若(i+1)=ia，ia即為目標(biāo)位置，無(wú)需復(fù)制遷移。遷移完成，移動(dòng)指示器：i+，ia+。重復(fù)以上過(guò)程，直至A、B中至少一個(gè)表結(jié)束。還有一種情況：B表已結(jié)束，但A表尚

23、未結(jié)束，說(shuō)明A剩下元素不在B中，全為A-B中元素，全部遷移到目標(biāo)位置。最后，修改A表長(zhǎng)度為i+1?！舅惴枋觥縱oid SetSubtraction(seqList & A, seqList & B)int i=-1; /指示A中已經(jīng)處理的最后元素int ia=0, ib=0; /指示A、B中，當(dāng)前待處理的元素，初始指向第一個(gè)元素while( ia<A.listLen && ib<B.listLen )if(A.dataia=B.dataib) /非A-B中元素，ia、ib同時(shí)后移ia+;ib+;else if(A.dataia>B.dataib) ib+; /此時(shí)，ia指示元素可能在B中ib指示的元素后面，移動(dòng)ib。else /此為，A.dataia<B.dataib，因?yàn)檫f增性，i