數(shù)據(jù)結(jié)構(gòu)第2章典型例題解析(存儲(chǔ)版)
【正文】 三、簡(jiǎn)答題1．如圖211所示的雙向鏈表中，欲在結(jié)點(diǎn)p前插入一個(gè)結(jié)點(diǎn)s，請(qǐng)完成有關(guān)操作。在下面的語(yǔ)句順序下，可有兩個(gè)答案進(jìn)行選擇。else{for (j=(i+2)。amp。} 【解答】算法的功能是把單鏈表的第一個(gè)結(jié)點(diǎn)從表頭移到了鏈尾。開(kāi)始結(jié)點(diǎn)指第一個(gè)元素結(jié)點(diǎn)。四、算法設(shè)計(jì)題1．設(shè)線性表存放在一維數(shù)組A[arrsize]的前num個(gè)分量中，且遞增有序。amp。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法刪除結(jié)點(diǎn)s的直接前驅(qū)結(jié)點(diǎn)。}3．已知兩個(gè)單鏈表A與B分別表示兩個(gè)集合，其元素遞增排列，編寫(xiě)一個(gè)函數(shù)求出A和B的交集C，要求C同樣以元素值遞增的單鏈表形式存儲(chǔ)。 while (p amp。 q=qnext?！痉治觥坑捎趩捂湵鞮是一個(gè)遞減有序表，即由大到小有序，故可從表頭開(kāi)始查找第一個(gè)比max小的結(jié)點(diǎn)，記住其位置，再接著向后查找第一個(gè)不大于min的結(jié)點(diǎn)，然后將它們之間的結(jié)點(diǎn)刪除。 pdatamin) //p繼續(xù)下移 p=pnext。 cur_a=anext。next=temp224。 } cur_b224。 cur_b=cur_b224。(temp=cur_a224?！痉治觥看祟}用一個(gè)while循環(huán)來(lái)處理，一次循環(huán)處理兩個(gè)結(jié)點(diǎn)：將前一個(gè)仍留在a中，后一個(gè)從a中刪除，鏈接到b的尾部，直到整個(gè)鏈表處理完畢。 } //p指向第一個(gè)值小于max的結(jié)點(diǎn),s指向其前驅(qū) while (p!=L amp。}4．單鏈表L是一個(gè)遞減有序表，試編寫(xiě)一個(gè)高效算法，刪除表中值大于min且小于max的結(jié)點(diǎn)（若表中有這樣的結(jié)點(diǎn)），同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里min 和max 是兩個(gè)給定的參數(shù)。 r=s。 p=A。 } qnext=s。 }}時(shí)間復(fù)雜度為O(n)。 else{ i=*num。雙鏈表：可以實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(1)。頭結(jié)點(diǎn)是附加在第一個(gè)元素結(jié)點(diǎn)之前的一個(gè)結(jié)點(diǎn)，頭指針指向頭結(jié)點(diǎn)。 qnext=NULL。3．下述算法的功能是什么？LinkList Demo(LinkList L){ // L是無(wú)頭結(jié)點(diǎn)的單鏈表 LNode *q,*p。 i=1?！??！痉治觥看嫒【€性表中數(shù)據(jù)元素的時(shí)間開(kāi)銷與其存儲(chǔ)結(jié)構(gòu)有關(guān)?！敬鸢浮垮e(cuò)誤7．靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)?！痉治觥挎湵硎峭ㄟ^(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素的，為建立起數(shù)據(jù)元素之間的線性關(guān)系，對(duì)每個(gè)數(shù)據(jù)元素，除了存放數(shù)據(jù)元素自身的信息之外，還需要存放其后繼元素所在的存儲(chǔ)單元的地址?！痉治觥烤€性表是一種邏輯結(jié)構(gòu)，其數(shù)據(jù)元素屬于相同數(shù)據(jù)類型，之間的關(guān)系是線性關(guān)系。 B．pnext=snext。 pnextprior=s。 sprior=p。A．pnext==head B．pnext==NULL C．p==NULL D．p==head【分析】非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)的后繼指針指向鏈表的頭結(jié)點(diǎn)。A．所有的操作算法簡(jiǎn)單 B．便于插入和刪除C．便于利用零散的存儲(chǔ)器空間 D．便于隨機(jī)存取【分析】靜態(tài)鏈表采用的是鏈?zhǔn)椒绞酱鎯?chǔ)線性表，因此其具有鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)?！敬鸢浮緼6．設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用 最節(jié)省時(shí)間。A．head==NULL B．headnext==NULLC．headnext==head D．head!=NULL【分析】鏈表為空時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?。A．表元素 B．字符 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項(xiàng)【分析】線性表是具有相同數(shù)據(jù)類型的n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，通常記為(a1,a2,…,an)，其中n為表長(zhǎng)，n=0時(shí)稱為空表。【答案】D5．若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用 存
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1