數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案詳解c語(yǔ)言嚴(yán)蔚敏

1、1數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語(yǔ)言版嚴(yán)蔚敏)第2章線性表2.1描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。2.2填空題。解：(1)在順序表中插入或刪除一個(gè)元素，需要平均移

2、動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素在表中的位置有關(guān)。(2)順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。(3)在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。(4)在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。2.3在什么情況下用順序表比鏈表好？解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。

3、2.4對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。解：2.5畫出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(LNode))P=Lf(i=1inext=(LinkList)malloc(sizeof(LNode))P=PnextPdata=i21Pnext=NULLf(i=4i=1i)Ins_LinkList(Li1i2)f(i=1inext=S(2)Pnext=Pnextnext(

4、3)Pnext=Snext(4)Snext=Pnext(5)Snext=L(6)Snext=NULL(7)Q=P(8)while(Pnext!=Q)P=Pnext(9)while(Pnext!=NULL)P=Pnext(10)P=Q(11)P=L(12)L=S(13)L=P解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.7已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾

5、元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是____________________。b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是____________________。c.刪除P結(jié)點(diǎn)的語(yǔ)句序列是____________________。d.刪除首元結(jié)點(diǎn)的語(yǔ)句序列是____________________。3解：StatusK(SqListif(ia.length1||ka.lengthi)re

6、turnINFEASIBLEf(j=0j0xB.lengthA.length:B.lengthf(i=0iB.elem[i])j=1if(A.elem[i]k)j=1if(B.lengthk)j=1if(A.length==B.length)j=0returnj2.13試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(Lx)解：intLocateElem_L(LinkListLinkListp=Lwhile(piif(!p)

7、return0elsereturni2.14試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。解：返回單鏈表的長(zhǎng)度intListLength_L(LinkListLinkListp=Lif(p)p=pnextwhile(p)p=pnextireturni2.15已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起，假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求