線性表習(xí)題練習(xí)附標(biāo)準(zhǔn)答案

1、第 2 章線性表習(xí)題練習(xí)答案2.1 試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。 答： 開始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，也就是沒有直接前趨的那個(gè)結(jié)點(diǎn)。 鏈表的頭指針是一指向鏈表開始結(jié)點(diǎn)的指針 （沒有頭結(jié)點(diǎn)時(shí) ），單鏈表由頭指針唯 一確定，課后答案網(wǎng) 因此單鏈表可以用頭指針的名字來命名。 頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。 有了頭結(jié)點(diǎn)之后， 頭指針指向 頭結(jié)點(diǎn)，不論鏈表否為空， 頭指針總是非空。 而且頭指針的設(shè)置使得對鏈表的第一個(gè)位置 上的操作與在表其他位置上的操作一致 （都是在某一結(jié)點(diǎn)之后 ）。2.2 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的 存儲 結(jié)構(gòu)為宜 ?

2、 答： 在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的 存儲結(jié)構(gòu)，通常有以下幾方面的考慮：1. 基于空間的考慮。 當(dāng)要求存儲的線性表長度變化不大， 易于事先確定其大小時(shí)， 為了節(jié) 約存儲空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲規(guī)模 時(shí)，采用動 態(tài)鏈表作為存儲結(jié)構(gòu)為好。2. 基于時(shí)間的考慮。 若線性表的操作主要是進(jìn)行查找， 很少做插入和刪除操作時(shí)， 采用順 序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)， 宜采用鏈表做存儲結(jié)構(gòu)。 并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端， 則采用 尾指針表示的單循環(huán)鏈表為宜。2.3 在順序

3、表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動多少個(gè)結(jié)點(diǎn) ?具體的移動次數(shù)取 決于哪兩個(gè)因素?答：在等概率情況下， 順序表中插入一個(gè)結(jié)點(diǎn)需平均移動 n/2 個(gè)結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn) 需平均移動 (n-1)/2 個(gè)結(jié)點(diǎn)。具體的移動次數(shù)取決于順序表的長度 n 以及需插入或刪除 的位置i。i越接近 n 則所需移動的結(jié)點(diǎn)數(shù)越少。2.4 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好 ?答：尾指針是指向終端結(jié)點(diǎn)的指針， 用它來表示單循環(huán)鏈表可以使得查找鏈表的開始 結(jié)點(diǎn)和 終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為 rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是 rear-next-next 和 rear, 查找時(shí)

4、間都是 O(1)。 若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為 O(n)。 課后答案網(wǎng) 2.5 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針 p指向某結(jié)點(diǎn)，不知道頭 指針，能否將結(jié)點(diǎn) *p從相應(yīng)的鏈表中刪去 ?若可以，其時(shí)間復(fù)雜度各為多少 ?答：下面分別討論三種鏈表的情況。1. 單鏈表。若指針 p 指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到其直接后繼，能夠順 后繼指針鏈找到 *p 結(jié)點(diǎn)后的結(jié)點(diǎn)。但是由于不知道其頭指針，所以無法訪問到 p 指針 指向的結(jié)點(diǎn)的直接前趨。因此無法刪去該結(jié)點(diǎn)。2. 雙鏈表。由于這樣的鏈表提供雙向指針，根據(jù) *p 結(jié)點(diǎn)的前趨指針和后繼指針 可以查找到其直接前趨和直接后繼，從而

5、可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為 O(1)。3. 單循環(huán)鏈表。根據(jù)已知結(jié)點(diǎn)位置，可以直接得到其后相鄰的結(jié)點(diǎn)位置 (直接后 繼)，又因?yàn)槭茄h(huán)鏈表， 所以我們可以通過查找， 得到 p 結(jié)點(diǎn)的直接前趨。 因此可以刪 去 p 所指結(jié) 點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為 O(n)2.6 下述算法的功能是什么 ?LinkList Demo(LinkList L) / L 是無頭結(jié)點(diǎn)單鏈表ListNode *Q,*P;if(L&L-next)Q=L;L=L-next;P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo答：該算法的功能是： 將開

6、始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)， 而原 來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。2.7 設(shè)線性表的 n個(gè)結(jié)點(diǎn)定義為 (a0,a1,.an-1，) 重寫順序表上實(shí)現(xiàn)的插入和刪除算 法：InsertList 和DeleteList.課后答案網(wǎng) 解：算法如下 :#define ListSize 100 / 假定表空間大小為 100 typedef int DataType;/ 假定 DataType 的類型為 int 型 typedef structDataType dataListSize;/ 向量 data 用于存放表結(jié)點(diǎn)int length; / 當(dāng)前的表長度 Seq

7、list;/ 以上為定義表結(jié)構(gòu)void InsertList ( Seqlist *L, Datatype x, int i)/ 將新結(jié)點(diǎn) x 插入L 所指的順序表的第 i 個(gè)結(jié)點(diǎn) ai 的位置上，即插入的合法位置 為： 0=ilengthint j;if ( i L - length )Error(position error);/ 非法位置，退出，該函數(shù)定義見教材 P7.if ( L-length=ListSize )Error( “overflow);for ( j=L-length-1 ; j = i ; j -)L-data j+1=L-data j ;L-data i =x ;L-

8、length+ ;void DeleteList ( Seqlist *L, int i ) / 從L 所指的順序表中刪除第 i 個(gè)結(jié)點(diǎn) ai,合法的刪除位置為 0=ilength-1int j;if ( i= L- length)Error( position error ) ;for ( j = i ; j length ; j+ )L-data j =L-data j+1; / 結(jié)點(diǎn)前移L- length- ; / 表長減小課后答案網(wǎng) 2.8 試分別用順序表和單鏈表作為存儲結(jié)構(gòu)， 實(shí)現(xiàn)將線性表 (a0,a1,.an-1就) 地逆置 的操作，所 聞創(chuàng)溝燴鐺險(xiǎn)愛氌譴凈。謂就地 指輔助空間應(yīng)為

9、 O(1)。答：1. 順序表：要將該表逆置， 可以將表中的開始結(jié)點(diǎn)與終端結(jié)點(diǎn)互換， 第二個(gè)結(jié)點(diǎn)與倒數(shù)第二 個(gè)結(jié)點(diǎn)互換，如此反復(fù)，就可將整個(gè)表逆置了。算法如下：/ 順序表結(jié)構(gòu)定義同上題void ReverseList( Seqlist *L)DataType temp ; / 設(shè)置臨時(shí)空間用于存放 data int i; for (i=0;ilength/2;i+)/L-length/2 為整除運(yùn)算 temp = L-datai; / 交換 數(shù)據(jù)L - data i = L - data L - length-1-i;L - data L - length - 1 - i = temp;2. 鏈

10、表：分析：可以用交換數(shù)據(jù)的方式來達(dá)到逆置的目的。 但是由于是單鏈表， 數(shù)據(jù)的存取不是 隨機(jī)的， 因此算法效率太低。可以利用指針改指來達(dá)到表逆置的目的。具體情況入下： (1)當(dāng)鏈表為空表或只有一個(gè)結(jié)點(diǎn)時(shí)，該鏈表的逆置鏈表與原表相同。(2)當(dāng)鏈表含2 個(gè)以上結(jié)點(diǎn)時(shí)，可將該鏈表處理成只含第一結(jié)點(diǎn)的帶頭結(jié)點(diǎn)鏈表和 一個(gè)無頭結(jié)點(diǎn)的包含該鏈表剩余結(jié)點(diǎn)的鏈表。 然后，將該無頭結(jié)點(diǎn)鏈表中的所有結(jié)點(diǎn) 順著鏈表指針，由前往后將每個(gè)結(jié)點(diǎn)依次從無頭結(jié)點(diǎn)鏈表中摘下， 作為第一個(gè)結(jié)點(diǎn)插入到帶 頭結(jié)點(diǎn)鏈表中。這樣就可以得到逆置的鏈表。算法是這樣的： 結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef char DataType; /假設(shè)結(jié)點(diǎn)

11、的數(shù)據(jù)域類型的字符課后答案網(wǎng) typedef struct node / 結(jié)點(diǎn)類型定義DataType data; /結(jié)點(diǎn)的數(shù)據(jù)域 struct node *next;/ 結(jié)點(diǎn)的指針域 ListNode;typedef ListNode *LinkList;ListNode *p;LinkList head;LinkList ReverseList( LinkList head ) / 將 head 所指的單鏈表 (帶頭結(jié)點(diǎn) )逆置 ListNode *p ,*q ;/ 設(shè)置兩個(gè)臨時(shí)指針變量 if( head-next & head-next-next) / 當(dāng)鏈表不是空表或單結(jié)點(diǎn)時(shí) p=he

12、ad-next;q=p-next;p - next=NULL; / 將開始結(jié)點(diǎn)變成終端結(jié)點(diǎn) while (q) / 每次循環(huán)將后一個(gè)結(jié)點(diǎn)變成開始結(jié)點(diǎn) p=q;q=q-next ;p-next = head- next ; head-next = p;return head;return head; / 如是空表或單結(jié)點(diǎn)表，直接返回 head2.9 設(shè)順序表 L是一個(gè)遞增有序表，試寫一算法，將 x插入L中，并使 L仍是一個(gè)有 序表。答：課后答案網(wǎng) 因已知順序表 L 是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)(設(shè)為 i 位置元素) 開始向前尋找到第一個(gè)小于或等于 x 的元素位置 i 后插入該位置即可。

13、 在尋找過程中，由于大于 x 的元素都應(yīng)放在 x 之后，所以可邊尋找，邊后移元素， 當(dāng)找到第一個(gè)小于或等于 x 的元素位置 i 時(shí)，該位置也空出來了。算法如下：/ 順序表存儲結(jié)構(gòu)如題 2.7void InsertIncreaseList( Seqlist *L , Datatype x )int i;if ( L-length=ListSize)Error( “overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-) 殘騖樓諍錈瀨濟(jì)溆塹籟。L-data i =L-data i ; / 比較并移動元素L-data i =x;L - length

14、+;2.10 設(shè)順序表 L是一個(gè)遞減有序表， 試寫一算法， 將x插入其后仍保持 L 的有序性。 答：與上題相類似，只要從終端結(jié)點(diǎn)開始往前找到第一個(gè)比 x 大(或相等 )的結(jié)點(diǎn)數(shù)據(jù)， 在這個(gè)位置插入就可以了。(邊尋找，邊移動)算法如下：void InsertDecreaseList( Seqlist *L, Datatype x )int i;if ( L-length=ListSize)Error( “overflow);for ( i=L - length ; i0 & L-data i-1 data i =L-data i ; / 比較并移動元素L-data i =x;課后答案網(wǎng) L -

15、length+;2.11 寫一算法在單鏈表上實(shí)現(xiàn)線性表的 ListLength(L)運(yùn)算。解： 由于在單鏈表中只給出一個(gè)頭指針， 所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點(diǎn) 個(gè)數(shù)了。算法如下：int ListLength ( LinkList L )int len=0 ;ListNode *p;p=L; / 設(shè)該表有頭結(jié)點(diǎn)while ( p-next )p=p-next;len+;return len;2.12 已知 L1和L2分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且已知其長度分別為 m和n。試 寫一算法將這兩個(gè)鏈表連接在一起，請分析你的算法的時(shí)間復(fù)雜度。解：分析：由于要進(jìn)行的是兩單鏈表的連接， 所以應(yīng)找到

16、放在前面的那張表的表尾結(jié)點(diǎn)， 再 將后表 的開始結(jié)點(diǎn)鏈接到前表的終端結(jié)點(diǎn)后即可。 該算法的主要時(shí)間消耗是用在尋找第 一張表的終端尾結(jié)點(diǎn)上。 這兩張單鏈表的連接順序無要求， 并且已知兩表的表長， 則為了提 高算法效率，可選表長小的單鏈表在前的方式連接。具體算法如下：LinkList Link( LinkList L1 , LinkList L2 ， int m,int n )彈貿(mào)攝爾霽斃攬磚鹵廡。課后答案網(wǎng) / 將兩個(gè)單鏈表連接在一起ListNode *p , *q, *s ;/s 指向短表的頭結(jié)點(diǎn) ,q 指向長表的開始結(jié)點(diǎn)，回收長表頭結(jié)點(diǎn)空間if (mnext;free(L2);else s=

17、L2;q=L1-next;free(L1);p=s;while ( p-next ) p=p-next; / 查找短表終端結(jié)點(diǎn)p-next = q; / 將長表的開始結(jié)點(diǎn)鏈接在短表終端結(jié)點(diǎn)后return s;本算法的主要操作時(shí)間花費(fèi)在查找短表的終端結(jié)點(diǎn)上， 所以本算的法時(shí)間復(fù)雜度 為：O(min(m,n)2.13 設(shè)A和 B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將 A和 B歸并成一 個(gè)按元素值遞減有序的單鏈表 C，并要求輔助空間為 O(1)，請分析算法的時(shí)間復(fù)雜度。 解：根據(jù)已知條件， A 和B 是兩個(gè)遞增有序表，所以可以先取 A 表的表頭建立空的 C 表。然后同時(shí)掃描 A 表和 B 表

18、，將兩表中最大的結(jié)點(diǎn)從對應(yīng)表中摘下，并作為開始 結(jié)點(diǎn)插入 C表中。如此反復(fù)，直到 A 表或 B 表為空。最后將不為空的 A 表或 B 表中的結(jié)點(diǎn) 依次摘下并作為開始結(jié)點(diǎn)插入 C 表中。這時(shí)，得到的 C 表就是由 A 表和 B 表歸并成的一個(gè) 按元素值遞減有序的單鏈表 C。并且輔助空間為 O(1)。算法如下：LinkList MergeSort ( LinkList A , LinkList B )/ 歸并兩個(gè)帶頭結(jié)點(diǎn)的遞增有序表為一個(gè)帶頭結(jié)點(diǎn)遞減有序表 ListNode *pa , *pb , *q , *C ;pa=A-next;/pa 指向 A 表開始結(jié)點(diǎn)C=A;C-next=NULL;/

19、 取 A 表的表頭建立空的 C 表 pb=B-next;/pb 指向 B 表開始結(jié)點(diǎn) free(B);/ 回收 B 表的頭結(jié)點(diǎn)空間 課后答案網(wǎng) while ( pa & pb)if ( pb-data data ) / 當(dāng) B 中的元素小于等于 A 中當(dāng)前元素時(shí)，將 pa 表的開始結(jié)點(diǎn)摘下 q=pa;pa=pa-next;else/ 當(dāng)B 中的元素大于 A 中當(dāng)前元素時(shí)，將 pb 表的開始結(jié)點(diǎn)摘下 q=pb;pb=pb-next;q-next=C-next;C-next=q;/ 將摘下的結(jié)點(diǎn) q 作為開始結(jié)點(diǎn)插入 C 表 / 若 pa 表非空，則處理 pa 表while(pa) q=pa;pa

20、=pa-next;q-next=C-next;C-next=q;/ 若pb 表非空，則處理 pb 表while(pb) q=pb;pa=pb-next;q-next=C-next;C-next=q;return(C);該算法的時(shí)間復(fù)雜度分析如下： 算法中有三個(gè) while 循環(huán)，其中第二個(gè)和第三個(gè)循環(huán)只執(zhí)行一個(gè)。每個(gè)循環(huán)做的 工作都是對鏈表中結(jié)點(diǎn)掃描處理。整個(gè)算法完成后， A 表和 B 表中的每個(gè)結(jié)點(diǎn)都被處 理了一遍。所以若 A 表和B表的表長分別是 m和n，則該算法的時(shí)間復(fù)雜度 O(m+n)2.14 已知單鏈表 L是一個(gè)遞增有序表，試寫一高效算法，刪除表中值大于 min 且 小于 max的結(jié)

21、點(diǎn) (若表中有這樣的結(jié)點(diǎn) )，同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里 min 和max是兩 個(gè)給定的參數(shù)。請分析你的算法的時(shí)間復(fù)雜度。解：課后答案網(wǎng) 要解這樣的問題，我們首先想到的是拿鏈表中的元素一個(gè)個(gè)地與 max 和min 比 較，然后刪除這個(gè)結(jié)點(diǎn)。由于為已知其是有序鏈表，則介于 min 和max 之間的結(jié)點(diǎn)必 為連續(xù)的一段元素序列。所以我們只要先找到所有大于 min 結(jié)點(diǎn)中的最小結(jié)點(diǎn)的直接前趨結(jié) 點(diǎn) *p 后，依次刪除小于 max 的結(jié)點(diǎn)，直到第一個(gè)大于等于 max 結(jié)點(diǎn) *q 位置，然后將 *p 結(jié) 點(diǎn)的直接后繼指針指向 *q 結(jié)點(diǎn)。算法如下： void DeleteList ( LinkList

22、 L, DataType min , DataType max謀 )蕎摶篋飆鐸懟類蔣薔。ListNode *p , *q , *s;p=L;while( p-next & p-next-data next;q=p-next;/p 指向第一個(gè)不大于 min 結(jié)點(diǎn)的直接前趨， q 指向第一個(gè)大于 min 的結(jié)點(diǎn)while(q &q-datanext;free(s);/ 刪除結(jié)點(diǎn)，釋放空間p-next=q;/ 將*p 結(jié)點(diǎn)的直接后繼指針指向 *q 結(jié)點(diǎn)2.15 寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不 相同。解： 本題可以這樣考慮，先取開始結(jié)點(diǎn)中的值，將它與其后的所有結(jié)點(diǎn)值一

23、一比較， 發(fā)現(xiàn)相 同的就刪除掉，然后再取第二結(jié)點(diǎn)的值，重復(fù)上述過程直到最后一個(gè)結(jié)點(diǎn) 具體算法：void DeleteList ( LinkList L )ListNode *p , *q , *s;課后答案網(wǎng) p=L-next;while( p-next&p-next-next)q=p;/ 由于要做刪除操作，所以 q 指針指向要?jiǎng)h除元素的直接前趨 while (q-next)if (p-data=q-next-data)s=q-next;q-next=s-next;free(s);/ 刪除與 *p 的值相同的結(jié)點(diǎn)else q=q-next;p=p-next;s為指向鏈表中2.16 假設(shè)在長度大

24、于 1的單循環(huán)鏈表中， 既無頭結(jié)點(diǎn)也無頭指針。 某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn) *s的直接前趨結(jié)點(diǎn)。解： 已知指向這個(gè)結(jié)點(diǎn)的指針是 *s，那么要?jiǎng)h除這個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)，就只要找到一個(gè) 結(jié)點(diǎn)，它的指針域是指向 *s 的直接前趨，然后用后刪結(jié)點(diǎn)法，將結(jié)點(diǎn) 前趨結(jié)點(diǎn)刪除即可。算法如下：void DeleteNode( ListNode *s)/ 刪除單循環(huán)鏈表中指定結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)ListNode *p, *q;p=s;while( p-next-next!=s)p=p-next;/ 刪除結(jié)點(diǎn)q=p-next; p-next=q-next;free(p); / 釋放空間課后答案網(wǎng) 若單循環(huán)

25、鏈表的長度等于 1，則只要把表刪空即可。2.17 已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素 (如：s 的直接字母字符、數(shù)字字符和 其它字符 )，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同 一類的字符， 且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。 解：要解決這樣的問題， 只要新建三個(gè)頭結(jié)點(diǎn)， 然后在原來的單鏈表中依次查詢， 到一類字符結(jié)點(diǎn)時(shí)，就摘下此結(jié)點(diǎn)鏈接到相應(yīng)頭結(jié)點(diǎn)指明的新鏈表中就是了。 算法如下：/ 設(shè)已建立三個(gè)帶頭結(jié)點(diǎn)的空循環(huán)鏈表 A,B,C 且 A、B、C 分別是尾指針 . void DivideList( LinkList L, Lin

26、kList A, LinkList B, LinkList C) 廈礴懇蹣駢時(shí)盡繼價(jià)騷。ListNode *p=L-next, *q;while ( p )if ( p-data=a &p-datadata=A &p-datanext;p=p-next;/ 指向下一結(jié)點(diǎn)q-next=A-next;/ 將字母結(jié)點(diǎn)鏈到 A 表中A-next=q;A=q;else if( p-data=0 & p-datanext;p=p-next;/ 指向下一結(jié)點(diǎn)q-next=B-next;/ 將數(shù)字結(jié)點(diǎn)鏈到 B 表中B-next=q;B=q;課后答案網(wǎng) else / 分出其他字符結(jié)點(diǎn)q=p-next;p=p-next;/ 指向下一結(jié)點(diǎn)q-next=C-next;/ 將其他結(jié)點(diǎn)鏈到 C 表中C-next=q;C=q;/ 結(jié)束2.18 設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有 prior、 data和next三個(gè)域外，還有一個(gè)訪 問頻度域fre