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

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