數(shù)據(jù)結(jié)構(gòu)作業(yè)答案第二章作業(yè)答案.doc

第二章作業(yè)解答一、基礎(chǔ)知識(shí)題2.1試描述頭指針、頭結(jié)點(diǎn)、開(kāi)始結(jié)點(diǎn)的區(qū)別，并說(shuō)明頭指針和頭結(jié)點(diǎn)的作用。答：頭指針是指向頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)的指針，我們就是靠它來(lái)描述和訪問(wèn)整個(gè)線性鏈表，如果失去了頭指針，整個(gè)線性鏈表也就無(wú)法訪問(wèn)，因而線性鏈表的存在與否也就失去了意義。頭結(jié)點(diǎn)是為了對(duì)線性鏈表操作的方便而引入的，引入頭結(jié)點(diǎn)主要有兩方面的方便，一是當(dāng)在線性鏈表的第一個(gè)位置進(jìn)行操作時(shí)無(wú)需做特殊處理；二是就整個(gè)線性鏈表而言無(wú)論空表和非空表，對(duì)表的操作可以保持一致性。頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭斩羔樣蛑赶蜷_(kāi)始結(jié)點(diǎn)，如果存在頭結(jié)點(diǎn)，那么線性鏈表的頭指針就指向它。開(kāi)始結(jié)點(diǎn)是真正存儲(chǔ)數(shù)據(jù)的第一個(gè)線性鏈表的結(jié)點(diǎn)，如果有頭結(jié)點(diǎn)的話，頭結(jié)點(diǎn)的指針域就指向它；如果沒(méi)有頭結(jié)點(diǎn)的話，頭指針就指向它。2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜？答：從空間復(fù)雜度上考慮：順序表的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，順序表的存儲(chǔ)密度為1，鏈表的存儲(chǔ)密度小于1，因此如果表的長(zhǎng)度變化較大，事先難以確定表的規(guī)模宜采用鏈表，否則用順序表。從時(shí)間復(fù)雜度上考慮：順序表的最大優(yōu)點(diǎn)是，它是一種隨機(jī)存取結(jié)構(gòu)，查找算法的時(shí)間復(fù)雜度低；最大缺點(diǎn)是插入刪除操作的時(shí)間復(fù)雜度較鏈表高；鏈表的最大優(yōu)點(diǎn)是插入刪除操作的時(shí)間復(fù)雜度低；最大缺點(diǎn)是查找算法的時(shí)間復(fù)雜度較順序表高。因此對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若插入和刪除操作較少，而查找操作較多時(shí)宜采用順序表。2.3在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？答：要?jiǎng)h除某結(jié)點(diǎn)，我們需要知道該結(jié)點(diǎn)的前后兩個(gè)結(jié)點(diǎn)。在單鏈表中，不知道頭指針，則無(wú)法訪問(wèn)該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，因此無(wú)法刪除。在雙鏈表中可以刪除，時(shí)間復(fù)雜度為O(1)。在單循環(huán)鏈表中可以刪除，時(shí)間復(fù)雜度為O(n)。2.4下述算法的功能是什么？LinkList Demo(LinkList L) /L是無(wú)頭結(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功能是：如果線性表的長(zhǎng)度大于1，則將線性表第一個(gè)位置上結(jié)點(diǎn)放到最后一個(gè)位置上。二、算法設(shè)計(jì)題2.5設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(a0,a1,.,an-1)，重寫(xiě)順序表上實(shí)現(xiàn)的插入和刪除算法：InsertList和DeleteList。void InsertList(SeqList *L,DataType x,int i)int j; if(iL-length) Error(position error); if(L-length=ListSize) Error(overflow); for(j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=x; L-length+;void DeleteList(SeqList *L,int i)int j; if(iL-length-1) Error(position error!); for(j=i;jlength-1;j+) L-dataj=L-dataj+1; L-length-;2.6試分別用順序表和單鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)將線性表(a0,a1,.,an-1)就地逆置的操作。順序表：void Trans(SeqList *L)DataType x; int i; for(i=0;ilength/2;i+) x=L-datai; L-datai=L-dataL-length-i-1; L-dataL-length-i-1=x; 單鏈表：void Trans(LinkList *head)/無(wú)頭結(jié)點(diǎn)ListNode *p1,*p2; if(!(head&head-next)return;/如果表的長(zhǎng)度為0或1則直接返回 p2=head;head=p2-next;p1=head-next; for(;) head-next=p2; if(!p1)return; p2=head; head=p1; p1=p1-next; 2.7設(shè)順序表L是一個(gè)遞增有序表，試寫(xiě)一算法將x插入L中，并使L仍是一個(gè)有序表。void Insert(SeqList *L,DataType x) int i,j; for(i=0;ilength;i+) if(xdatai)break; for(j=L-length;jdataj=L-dataj-1; L-datai=x;2.8設(shè)單鏈表L是一個(gè)遞減有序表，試寫(xiě)一算法將x插入其中后仍保持L的有序性。void Insert(LinkList *L,DataType x)ListNode *p1,*p2,*p3; p3=(ListNode *)malloc(sizeof(ListNode); p3-data=x; p1=L;p2=p1-next; while(1) p1=p2; p2=p2-next; if(!p2)|(xp2-data) p1-next=p3;p3-next=p2;return; 2.9寫(xiě)一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。int ListLength(LinkList *L)/沒(méi)有頭結(jié)點(diǎn)int i=0; ListNode *p; p=L; while(p)