《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集：第2章_線性表

1、1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 第2章線性表 選擇題 表長為N的順序表，當(dāng)在任何位置上插入或刪除一個元素的概率相等時(shí)，插入一個元素所需移動元素的平均 次數(shù)為（E ），刪除一個元素需要移動的元素個數(shù)為（A ）。 A. （N-1）/2 B. N C. N+1 D. N-1 E. N/2 F. （N+1）/2 G. （N-2）/2 線性表是具有N個（C ）的有限序列。 A、表元素B、字符C、數(shù)據(jù)元素 D、數(shù)據(jù)項(xiàng)E、信息 “線性表的邏輯順序和物理順序總是一致的。”這個結(jié)論是（B ）。 A、正確的B、錯誤的C、不一定，與具體結(jié)構(gòu)有關(guān)。 線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)

2、時(shí)，要求內(nèi)存中可用存儲單元的地址（D ）o A、必須是連續(xù)的B、部分地址必須是連續(xù)的 C一定是不連續(xù)的 D、連續(xù)或不連續(xù)都可以o 帶頭結(jié)點(diǎn)的單鏈表為空的判定條件 是（B ）o A、head=NULL B、head-next=NULL C head-next=head D、head!=NULL 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（A ）o A、head=NULL B、head-next=NULL C head-next=head D、head!=NULL 非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)P滿足（C ）o A、P-NEXT=NULL B、p=NULL C p-next=head D、

3、p=head 在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是（B ）o 2 A、0（1） B、0（n）C、O（n ）D、0（nlog2n） 在一個單鏈表中，若刪除 P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（A ）o A、p-next=p-next-nextB、p=p-next;p-next=p-next-next C p-next=p-next;D、p=p-next-next; 在一個單鏈表中，若在P所指結(jié)點(diǎn)之后插入S所指結(jié)點(diǎn)，則執(zhí)行（B ）o A、s-next=p;p-next=s;B、s-next=p-next;p-next=s; C s-next=p-next;p=s;D、p

4、-next=s;s-next=p; 在一個單鏈表中，已知q是p的前趨結(jié)點(diǎn)，若q和p之間插入結(jié)點(diǎn)s,則執(zhí)行（C ） o A、s-next=p-next;p-next=s;B、p-next=s-next;s-next=p; C q-next=s;s-next=p;D、p-next=s;s-next=q; 假設(shè)雙鏈表結(jié)點(diǎn)的類型如下： typedef struct li nkno de int data; /數(shù)據(jù)域 struct linkn ode *lli nk;/指向前趨結(jié)點(diǎn)的指針域 struct linknode *rli nk;/指向后繼結(jié)點(diǎn)的指針域 bnode 現(xiàn)將一個q所指新結(jié)點(diǎn)作為非空雙

5、向鏈表中的p所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)插入到該雙鏈表中，能正確完成此要求 的語句段是（D ）o A、 q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q; 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. B、p-llink=q;q_rlink=p;p_Hink_rlink=q;q_Hink=p_Hink C、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-llink=q; D、以上都不對 如上題結(jié)點(diǎn)結(jié)構(gòu)，如在此非空循環(huán)雙向鏈表的結(jié)點(diǎn)p之后插入結(jié)點(diǎn)s的操作序列是（D ）。

6、A、p-rlink=s;s-llink=p;p-rlink-llink=s;s-rlink=p-rlink; B、p-rlink-s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink; C s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s; D、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s; 在一個長度為n的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（ B ）操作與鏈表的長度有關(guān)。 A、刪除單鏈表中的第一個元素 B、刪除單鏈表中最后一個元素 C在單鏈表第一個

7、元素前插入一個新元素 D、在單鏈表最后一個元素后插入一個新元素 線性結(jié)構(gòu)中的一個結(jié)點(diǎn)代表一個（ A ） A、數(shù)據(jù)元素B、數(shù)據(jù)項(xiàng)C、數(shù)據(jù) D、數(shù)據(jù)結(jié)構(gòu) 非空線性表L=（a1,a2”，ai, ,an）,下列說法正確的是（D ） A、每個元素都有一個直接前驅(qū)和直接后繼 B、線性表中至少要有一個元素 C表中諸元素的排列順序必須是由小到大或由大到小的 D、除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼 順序表是線性表的（B ） B、順序存儲結(jié)構(gòu) D、散列存儲結(jié)構(gòu) A ） A、鏈?zhǔn)酱鎯Y(jié)構(gòu) C索引存儲結(jié)構(gòu) 對于順序表，以下說法錯誤的是（ A、順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)

8、組的下標(biāo)可以看成是元素的絕對地址 B、順序表的所有存儲結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C順序表的特點(diǎn)是：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰 D、順序表的特點(diǎn)是：邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中 B ）為標(biāo)準(zhǔn)操作。 對順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來說，通常以（ A、插入操作B、結(jié)點(diǎn)移動C、算術(shù)表達(dá)式D、刪除操作 對于順序表的優(yōu)缺點(diǎn)，以下說法錯誤的是（C） A、無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間 B、可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn) C插入和刪除運(yùn)算較方便 （靜態(tài)分配） D、由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進(jìn)行 若某線性表中

9、最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（A ）存儲方式最節(jié)省時(shí)間 A、順序表B、單鏈表C、雙鏈表D、單循環(huán)鏈表 循環(huán)鏈表主要優(yōu)點(diǎn)是（D ） A、不再需要頭指針了 B、已知某個結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨 C在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開 D、從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個鏈表 在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是（D ） A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表 二、 填空題 1. 在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)(沒有)前趨結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有(1)個前趨結(jié)點(diǎn)。 2. 在順序表中插入或刪除一個元素，需要平均移動(表中一半)元素，具

10、體移動的元素個數(shù)與(該元素的位置) 有關(guān)。 3. 已知L是無表頭結(jié)點(diǎn)的單鏈表，試從下列提供的答案中選擇合適的語句序列，分別實(shí)現(xiàn)： (1) 表首插入S結(jié)點(diǎn)的語句序列是( FC )。 (2) 表尾插入S結(jié)點(diǎn)的語句序列是( BIAG )。 A、P -next=S; E、P=L; C、L=S; D、P-next=S-next; E、S-next=P-next; F、S-next=L; G、S-next=NULL; H、while(P-next!=Q)p=p-next; I、while(P-next!=NULL)P=P-next; 4. 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，試從下列提供的答案中選擇合適的語句

11、序列。 (1) 刪除首元結(jié)點(diǎn)的語句序列是( HGBJ ), (2) 刪除尾元結(jié)點(diǎn)的語句序列是( HFDBJ ) A、P=P-next; B、P-next=P-next-next; C、while(P!=NULL)p=p-next; D、while(Q-next!=NULL)P=Q;Q=Q-next; E、while(P-next!=Q)P=P-next; F、Q=P; G、Q=P-next; H、P=L; I、L=L-next; J、free(Q); 5. 已知L是帶表頭結(jié)點(diǎn)的非空鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合 適的語句序列。 (1) 刪除P結(jié)點(diǎn)的直接

12、后繼結(jié)點(diǎn)的語句序列是( FAI ), (2) 刪除P結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的語句序列是( EGDFAI ) A、P-next=P-next-next; B、P=P-Pnext-next; C、while(P-next!=Q)P=P-next; D、while(P-next-next!=Q)P=P-next; E、Q=P; F、Q=P-next; G、P=L; H、L=L-next; I、free(Q); 6. 已知結(jié)點(diǎn)編號，在各結(jié)點(diǎn)查找概率相等的情況下，從n個結(jié)點(diǎn)的單鏈表中查找一個結(jié)點(diǎn)，平均要訪問(n/2) 個結(jié)點(diǎn)，從n個結(jié)點(diǎn)的雙鏈表中查找一個結(jié)點(diǎn)，平均要訪問(n/4 )個結(jié)點(diǎn)。 7. 對于一個具

13、有n個結(jié)點(diǎn)的單鏈表，在已知 p所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(0(1);在值域 為給定值的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(0 (n )。 8. 單鏈表是(線性表)的鏈接存儲表示。 9. 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是(插入和刪除首元素時(shí)不必進(jìn)行特殊處理)。 10. 在單鏈表中，除首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由(其直接前趨結(jié)點(diǎn)的鏈域)指示。 11. 在非空雙向循環(huán)鏈表中，在結(jié)點(diǎn) q的前面插入結(jié)點(diǎn)p的過程如下： p_prior=q_prior; q-prior- n ext=p; p_n ext=q; ( q-prior=p; )； 12. 在雙向鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向(

14、前趨結(jié)點(diǎn))，另一個指向(后繼結(jié)點(diǎn))。 13順序表中邏輯上相鄰的元素的物理位置( 必定)相鄰。單鏈表中邏輯上相鄰的元素的物理位置(不定) 相鄰。 14. 為了便于討論，有時(shí)將含n(n0)個結(jié)點(diǎn)的線性結(jié)構(gòu)表示成(a1,a2,an),其中每個ai代表一個結(jié)點(diǎn)。a1稱 為_第一個結(jié)點(diǎn)，an稱為_最后一個結(jié)點(diǎn)，i稱為ai在線性表中的位置。對任意一對相鄰結(jié) 點(diǎn)ai、ai十1(1 inext=NULL 。 判斷題 1. 順序存儲的線性表可以隨機(jī)存取。V 2. 順序存儲的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话氲脑匦枰苿?。X 3. 線性表中的元素可以是各種各樣的，但同一線性表

15、中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象。V 4. 在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。X 5. 在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。V 6. 在單鏈表中，可以從頭結(jié)點(diǎn)進(jìn)行查找任何一個元素。V 7. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。X 8. 在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時(shí)，移動元素的個數(shù)與該元素的位置有關(guān)。V 9. 在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。X 10. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。X 四、 簡答題 1. 若較頻繁地對一個線性表進(jìn)行插入和

16、刪除操作，該線性表宜采用哪種存儲結(jié)構(gòu)？為什么？ 宜采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，因?yàn)樗咕€性表的插入和刪除操作的時(shí)間復(fù)雜度為0( 1),而順序存儲結(jié)構(gòu)的為O (n) 2. 描述概念：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)的區(qū)別？ 首元結(jié)點(diǎn)是指鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一 個結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存線性表的數(shù)據(jù)元素，其作用是為了對鏈表進(jìn)行操作時(shí)，可以對空 表非空表的情況以及對首元結(jié)點(diǎn)進(jìn)行統(tǒng)一的處理。頭指針是指向鏈表第一個結(jié)點(diǎn)(頭結(jié)點(diǎn)或首元結(jié)點(diǎn))的指針。 若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。這三 個

17、概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用 3. 設(shè)A是一個線性表(a1a2, an),采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的 元素個數(shù)為多少？若元素插在ai與ai+1之間(0=l next) q=L ; L=L-n ext; p=L; while(p- next) p=p-n ext; p_n ext=q; q- next=NULL; return L; 解答：如果長度大于1,則將首元結(jié)點(diǎn)刪除并插入到表尾 7. 如果有n個線性表同時(shí)共存，并且在處理過程中各表的長度會發(fā)生動態(tài)變化，線性表的總長度也會自動地改變。 在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)。為什么？ 解答：應(yīng)選用鏈

18、式存儲結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲結(jié)構(gòu)，只能預(yù)先分配存儲單元，不能隨著線性表長度的改 變而變化。而鏈表則可根據(jù)需要動態(tài)的申請空間，因此適用于動態(tài)變化表長的線性表。 8. 若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存 儲結(jié)構(gòu)。為什么？ 解答：應(yīng)該用順序存儲結(jié)構(gòu)。因?yàn)轫樞虼鎯Y(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為0(1) 9. 設(shè)有多項(xiàng)式 a(x)=9+8x+9x4+5x10 710 b(x)=-2x+22x -5x (1) 用單鏈表給出a(x)、b(x)的存儲表示； (2) 設(shè)c (x)=a(x)+b(x)，求得c(x)并用單鏈表給出其存儲表示。 五、

19、設(shè)計(jì)題 1. 將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另外占 用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。 2. 將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另 外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。 3. 已知兩個鏈表 A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出 A與B的交集，并存放于A鏈表中。 4. 已知兩個鏈表 A和B分別表示兩個集合， 其元素遞增排列。請?jiān)O(shè)計(jì)算法求出兩個集合 A和B的差集(即僅由在 A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合)，并以同樣的形式存儲，同時(shí)返回該

20、集合的元素個數(shù)。 5. 設(shè)計(jì)算法將一個帶頭結(jié)點(diǎn)的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C,其中B表的結(jié)點(diǎn)為A表中值小于零 的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn))。 6. 設(shè)計(jì)一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。 7. 設(shè)計(jì)一個算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。 8. 設(shè)計(jì)一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素(mink和maxk是給定的兩個參數(shù)， 其值可以和表中的元素相同，也可以不同)。 9. 已知p指向雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、p

21、rior、next三個域，寫出算法 change(p),交換 p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。 知道雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，與前驅(qū)交換涉及到四個結(jié)點(diǎn)(p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié) 點(diǎn))六條鏈。 10. 已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時(shí)間復(fù)雜度為0(n)、空間復(fù)雜度為 0(1)的算法，該算法 刪除線性表中所有值為item的數(shù)據(jù)元素。 算法討論因元素只掃描一趟，算法時(shí)間復(fù)雜度為0( n)。刪除元素未使用其它輔助空間，最后線性表中的 兀素個數(shù)是j。 （1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間7不 另外占用其它的存儲空

22、間。表中不允許有重復(fù)的數(shù)據(jù)。 void MergeList_L(LinkList pb=Lb-n ext; Lc=pc=La;II用La的頭結(jié)點(diǎn)作為 Lc的頭結(jié)點(diǎn) while(pa pc=pa;pa=pa-n ext; else if(pa-datapb-data) pc- n ext=pb; pc=pb; pb=pb-n ext; else II相等時(shí)取La的元素，刪除Lb的元素 pc-n ext=pa;pc=pa;pa=pa-n ext; q=pb-n ext;delete pb ;pb =q; pc-n ext=pa?pa:pb; II插入剩余段 delete Lb;II釋放Lb的頭結(jié)點(diǎn)

23、 (2) 將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間， 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。 void union(Lin kList pb = Lb-n ext;II初始化 Lc=pc=La; II 用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) Lc- next = NULL; while ( pa | pb ) if ( !pa ) q = pb; pb = pb-n ext; else if ( !pb ) q = pa; pa = pa-n ext; else if (pa-data data ) q = pa; pa = pa-n ext

24、; else q = pb; pb = pb-n ext; q-n ext = Lc-n ext; Lc-n ext = q; II插入 delete Lb;II釋放Lb的頭結(jié)點(diǎn) (3) 已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于 A 鏈表中。 void Mix(Li nkList pb=lb-next; 設(shè)工作指針 pa禾口 pb; Lc=pc=La; II 用La的頭結(jié)點(diǎn)作為 Lc的頭結(jié)點(diǎn) while (papc=pa;pa=pa-n ext; u=pb;pb=pb-n ext; delete u; else if (pa-datadata)

25、u=pa;pa=pa-next; delete u; else u=pb; pb=pb-next; delete u; while (pa) u=pa; pa=pa-next; delete u; / 釋放結(jié)點(diǎn)空間 while (pb) u=pb; pb=pb-next; delete u; 釋放結(jié)點(diǎn)空間 pc- next=null; 置鏈表尾標(biāo)記。 delete Lb; /注： 本算法中也可對 B表不作釋放空間的處理 (4) 已知兩個鏈表 A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出兩個集合A和B的差集(即 僅由在A中出現(xiàn)而不在 B中出現(xiàn)的元素所構(gòu)成的集合),并以同樣的形式存儲，同

26、時(shí)返回該集合的元素個數(shù)。 void Differenee ( LinkedList A ， B, *n ) / A和B均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，分別存儲了一個集合，本算法求兩集合的差集，存儲于單鏈表A中, *n是結(jié)果集合中元素個數(shù)，調(diào)用時(shí)為0 p=A-next ;/ p和q分別是鏈表 A和B的工作指針。 q=B-next ; pre=A ;/ pre為A中p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針。 while (p!=null p=p-next ; *n+ ; / A 鏈表中當(dāng)前結(jié)點(diǎn)指針后移。 else if (p-dataq-data ) q=q-next ;/ B 鏈表中當(dāng)前結(jié)點(diǎn)指針后移。 els

27、e pre-next=p-next;/處理A, B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除。 u=p ; p=p-next ; delete u ; 刪除結(jié)點(diǎn) (5) 設(shè)計(jì)算法將一個帶頭結(jié)點(diǎn)的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C,其中B表的結(jié)點(diǎn)為A表中值 小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表A的元素類型為整型，要求B C表利用A表的結(jié)點(diǎn))。 (6) 設(shè)計(jì)一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。 ElemType Max (Lin kList L ) if(L-next=NULL) return NULL; pmax=L- next; /假定第一個結(jié)點(diǎn)中數(shù)據(jù)具有最大值 p=L

28、-n ext- n ext; while(p != NULL )/如果下一個結(jié)點(diǎn)存在 if(p-data pmax-data) pmax=p; p=p-n ext; return pmax-data; (7) 設(shè)計(jì)一個算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。 void in verse(L in kList L-n ext=NULL; while ( p) q=p-next; / q指向*p的后繼 p-n ext=L-n ext; L- next=p; / *p插入在頭結(jié)點(diǎn)之后 p = q; (8) 設(shè)計(jì)一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素(mink和maxk是給定的兩個參 數(shù)，其值可以和表中的元素相同，也可以不同)。 void delete(L in kList /首元結(jié)點(diǎn) while (p /查找第一個值 mink 的結(jié)點(diǎn) if (p) while (p /查找第一個值 maxk的結(jié)點(diǎn) q=pre _n ext; pre_n ext=p; /修改指針 while (q!=p) s=q-n ext; del