算法與數(shù)據(jù)結構（C++語言版）（第2版） 第2章課后習題答案

PAGEPAGE2習題答案選擇1-10：ADBACABDAD填空1、（a）元素的存儲位置（b）指針2、p->next!=NULL3、L->next==L或L->prior==L或L->prior==L&&L->next==L…或L->next==L->next…..（a）O(1)（b）O(n)判斷1-6：對錯錯錯錯錯四、應用1、在線性表的鏈式存儲結構中，頭指針指鏈表的指針，若鏈表有頭結點則是鏈表的頭結點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結點是為了操作的統(tǒng)一、方便而設立的，放在第一元素結點之前，其數(shù)據(jù)域一般無意義（當然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等）。有頭結點后，對在第一元素結點前插入結點和刪除第一結點，其操作與對其它結點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結點也就是第一元素結點，它是頭結點后邊的第一個結點。2、選順序存儲結構。順序表可以隨機存取，時間復雜度為O（1）。3、鏈式存儲結構一般說克服了順序存儲結構的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復雜度為O(1)；其次，不需要預先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當空間不允許時，就不能克服順序存儲結構的缺點。4、參見2.6節(jié)5、單循環(huán)鏈表往往只設尾指針而不設頭指針，用一個指向尾結點的尾指針來標識單循環(huán)鏈表，好處是既方便查找表尾結點又方便查找頭結點，因為通過尾結點的指針域很容易找到頭結點。若使用頭指針查找表尾結點需要從頭遍歷鏈表，時間復雜度是O(n)。五、算法設計題1、SeqListRearrange(SeqLista){ inti,j,t; i=0;j=a.Last-1;//i,j為工作指針(下標) t=a.data[0];//暫存樞軸元素。 while(i<j) { while(i<j&&a.data[j]>=0)j--; //j指針前移找小于0的元素 if(i<j)a.data[i++]=a.data[j]; //將負數(shù)前移 while(i<j&&a.data[i]<0)i++;//i指針后移找大于等于0的元素 if(i<j)a.data[j--]=a.data[i]; //正數(shù)后移 } a.data[i]=t; //將原第一元素放到最終位置 returna;}2、(1)LinkedListDelSame（LinkedListla）{ pre=la->next； ∥pre是p所指向的前驅(qū)結點的指針 p=pre->next； ∥p是工作指針，設鏈表中至少有一個結點 while（p） if（p->data==pre->data）∥相同元素值,釋放結點{u=p；pre->next=p->next;p=p->next；free（u）；} else {pre=p；p=p->next；} ∥元素值不同 returnla;}(2)算法時間復雜度O(n)3、DLinkedListDInsert(DLinkedListla,ElemTypex){ p=la->next; ∥p指向第一元素 ∥MaxElemType是和x同類型的機器最大值，用做監(jiān)視哨 la->data=MaxElemType; while(p->data<x) ∥尋找插入位置 p=p->next

; s=(DLNode*)malloc(sizeof(DLNode));∥申請結點空間 s->data=x; s->prior=p->prior; ∥將插入結點鏈入鏈表 s->next=p; p->prior->next=s; p->prior=s;}4、（1）①分別求出str1和str2所指的兩個鏈表的長度m和n；②將兩個鏈表以表尾對齊：即長的鏈表將指針移到|m-n+1|,短鏈表的指針指向鏈表的第一個字母；=3\*GB3③兩個鏈表進行模式匹配：對應字母比較，從最后遇到兩個鏈表結點值相等，直至到表尾對應結點值都相等為止。要注意處理雖然首次遇到對應結點值相等，但有后續(xù)結點值不等的情況,即在匹配中，并非一遇到對應字母相等，就結論后邊是共同后綴。（2）求用單鏈表表示的兩個單詞的共同后綴的算法typedefstructNode{ ElemTypedata;structNode*next;}LNode,*LinkedList；intListLength(LNode*la){//求鏈表la的長度inti=0;LNode*p=la->next; //p指向鏈表的第一個元素結點while(p){i++; //元素個數(shù)加1p=p->next; //鏈表指針后移}returni; //返回鏈表的長度}LNode*ComPostfix(LNode*str1,LNode*str2){//str1和str2分別是單詞以單鏈表存儲的頭指針，本算法返回兩個單詞共同后綴的起始位置p=null; //p指向兩個鏈表共同后綴的起始位置m=ListLength(str1);n=ListLength(str2); //求鏈表str1和str2的長度if(m>n){ s=str1->next; //s指向長鏈表的第一個元素 q=srt2->next; //q指向短鏈表的第一個元素 len=m-n+1; //兩個鏈表開始比較時，長鏈表應移到的位置}else{ s=str2->next; //s指向長鏈表的第一個元素 q=srt1->next; //q指向短鏈表的第一個元素 len=n-m+1; //兩個鏈表比較時，長鏈表應移到的位置}i=1;while(i<len){i++;s=s->next;} //長鏈表要移到兩個鏈表尾部對齊的位置while(s){while(s&&s->data!=q->data)//對應字母不等，后移指針 { s=s->next;q=q->next;}p=s; //p指向兩個鏈表共同后綴的起始位置while(s&&s->data==q->data)//如對應字母相等，后移指針{ s=s->next;q=q->next;}}returnp; //返回兩個鏈表共同后綴的起始位置}（3）算法中求了兩個鏈表的長度，接著將長鏈表的指針移到兩鏈表的比較處，進行對應元素的比較，記住可能共同后綴的開始位置，直到鏈表尾?？偟臅r間復雜度為O(m+n)。5、(1)算法思想：定義一個大小為N的數(shù)組，初始化為0.在遍歷鏈表的同時將數(shù)組中索引值為節(jié)點的值的絕對值的元素置1.如果此元素已經(jīng)為1，說明此節(jié)點之前已經(jīng)有與此節(jié)點的值的絕對值相等的節(jié)點，需將此節(jié)點刪除。(2)節(jié)點的數(shù)據(jù)結構定義如下：typedefstructNode{Intdata;StructNode*next;}Node;(3)inta[n];//全局數(shù)組標志節(jié)點的絕對值的值是否出現(xiàn)過voidDeleteABSEqualNode(Node*head){ memset(a,0,n);//初始化為0 if(head==NULL)returnNULL; Node*p=head; Node*r=head; while(p!=NULL) { if(a[abs(p->data)]==1) //如果此絕對值已經(jīng)在數(shù)組中出現(xiàn)過，則刪除 { r->next=p->next;deletep;p=r->next;} else//否則，將數(shù)組中對應的元素置1 { a[abs(p->data)]=1;r=p;p=p->next;} } returnhead;}(4)只遍歷一次鏈表，所以時間復雜度為O(n)因為申請大小為n的數(shù)組，所以空間復雜度為O(n)（n為節(jié)點絕對值的最大值）。6、(1)算法思想由于數(shù)組中有n個整數(shù)，則未出現(xiàn)的最小的正整數(shù)一定在1到n+1的范圍，假如：數(shù)組a為[1,2,3,4]，則最小正整數(shù)為5，也就是n+1。如果數(shù)組中介于1到n之間的正整數(shù)個數(shù)不足n個，則未出現(xiàn)的最小的正整數(shù)的范圍是1到n。設置一個輔助數(shù)組b,大小為n+2,初始值全部為0，然后對a[i]進行遍歷，如果0<a[i]<=n+1，則將b[a[i]]賦值為1，接下來遍歷b數(shù)組，遇到的第一個滿足b[i]==0的就退出，i就是數(shù)組a中未出現(xiàn)過的最小正整數(shù)(2)代碼實現(xiàn)intfindMissMin(intA[],intn){int*B=newint[n]; //創(chuàng)建動態(tài)數(shù)組memset(B,0,n*sizeof(int)); //賦初值inti;for(i=0;i<n;++i){ if(A[i]>0&&A[i]<n){//僅處理A中范圍在1~n的元素B[A[i]-1]++;}}for(i=0;i<n;++i){if(B[i]==0)break;}delete[]B;returni+1;}(3)算法的時間復雜度為O(n);空間復雜度為O(n)。7、(1)算法思想①首先尋找單鏈表的中心結點，使用兩個指針p、q，每次p走一步，q走兩步，當q到鏈表尾時，p正好在鏈表中心的位置。②將鏈表后半段利用頭插法逆置。③從單鏈表前后兩段中依次各取一個結點，并重新排列。(2)代碼實現(xiàn)voidrealign(NODE*h){NODE*p,*q,*r,*s;p=q=h;while(q->next!=NULL){ //尋找中間結點p=p->next; //p向后移動一個結點q=q->next;if(q->next!=NULL)q=q->next;//q向后移動兩個結點}q=p->next; //p指向中間結點，q指向p后面的結點p->next=NULL;while(q!=NULL){ //從q開始逆置后半段r=q->next;q->next=p->next; //p是中間結點，每次新結點插入在p之后p->next=q;q=r;}s=h