習(xí)題答案1選擇題ADDACC填空題（1）樹形結(jié)構(gòu)、（2）圖形結(jié)構(gòu)（1）確定性、（2）輸出（1）時(shí)間復(fù)雜度、（2）空間復(fù)雜度（1）1:1、（2）1:n、（3）n:n判斷題1-4錯錯對對習(xí)題答案2選擇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：對錯錯錯錯錯四、應(yīng)用1、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等）。有頭結(jié)點(diǎn)后，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與對其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。2、選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O（1）。3、鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個(gè)弱點(diǎn)。首先，插入、刪除不需移動元素，只修改指針，時(shí)間復(fù)雜度為O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允許時(shí)，就不能克服順序存儲結(jié)構(gòu)的缺點(diǎn)。4、參見2.6節(jié)5、單循環(huán)鏈表往往只設(shè)尾指針而不設(shè)頭指針，用一個(gè)指向尾結(jié)點(diǎn)的尾指針來標(biāo)識單循環(huán)鏈表，好處是既方便查找表尾結(jié)點(diǎn)又方便查找頭結(jié)點(diǎn)，因?yàn)橥ㄟ^尾結(jié)點(diǎn)的指針域很容易找到頭結(jié)點(diǎn)。若使用頭指針查找表尾結(jié)點(diǎn)需要從頭遍歷鏈表，時(shí)間復(fù)雜度是O(n)。五、算法設(shè)計(jì)題1、SeqListRearrange(SeqLista){ inti,j,t; i=0;j=a.Last-1;//i,j為工作指針(下標(biāo)) 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]; //將負(fù)數(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ū)結(jié)點(diǎn)的指針 p=pre->next； ∥p是工作指針，設(shè)鏈表中至少有一個(gè)結(jié)點(diǎn) while（p） if（p->data==pre->data）∥相同元素值,釋放結(jié)點(diǎn){u=p；pre->next=p->next;p=p->next；free（u）；} else {pre=p；p=p->next；} ∥元素值不同 returnla;}(2)算法時(shí)間復(fù)雜度O(n)3、DLinkedListDInsert(DLinkedListla,ElemTypex){ p=la->next; ∥p指向第一元素 ∥MaxElemType是和x同類型的機(jī)器最大值，用做監(jiān)視哨 la->data=MaxElemType; while(p->data<x) ∥尋找插入位置 p=p->next

; s=(DLNode*)malloc(sizeof(DLNode));∥申請結(jié)點(diǎn)空間 s->data=x; s->prior=p->prior; ∥將插入結(jié)點(diǎn)鏈入鏈表 s->next=p; p->prior->next=s; p->prior=s;}4、（1）①分別求出str1和str2所指的兩個(gè)鏈表的長度m和n；②將兩個(gè)鏈表以表尾對齊：即長的鏈表將指針移到|m-n+1|,短鏈表的指針指向鏈表的第一個(gè)字母；=3\*GB3③兩個(gè)鏈表進(jìn)行模式匹配：對應(yīng)字母比較，從最后遇到兩個(gè)鏈表結(jié)點(diǎn)值相等，直至到表尾對應(yīng)結(jié)點(diǎn)值都相等為止。要注意處理雖然首次遇到對應(yīng)結(jié)點(diǎn)值相等，但有后續(xù)結(jié)點(diǎn)值不等的情況,即在匹配中，并非一遇到對應(yīng)字母相等，就結(jié)論后邊是共同后綴。（2）求用單鏈表表示的兩個(gè)單詞的共同后綴的算法typedefstructNode{ ElemTypedata;structNode*next;}LNode,*LinkedList；intListLength(LNode*la){//求鏈表la的長度inti=0;LNode*p=la->next; //p指向鏈表的第一個(gè)元素結(jié)點(diǎn)while(p){i++; //元素個(gè)數(shù)加1p=p->next; //鏈表指針后移}returni; //返回鏈表的長度}LNode*ComPostfix(LNode*str1,LNode*str2){//str1和str2分別是單詞以單鏈表存儲的頭指針，本算法返回兩個(gè)單詞共同后綴的起始位置p=null; //p指向兩個(gè)鏈表共同后綴的起始位置m=ListLength(str1);n=ListLength(str2); //求鏈表str1和str2的長度if(m>n){ s=str1->next; //s指向長鏈表的第一個(gè)元素 q=srt2->next; //q指向短鏈表的第一個(gè)元素 len=m-n+1; //兩個(gè)鏈表開始比較時(shí)，長鏈表應(yīng)移到的位置}else{ s=str2->next; //s指向長鏈表的第一個(gè)元素 q=srt1->next; //q指向短鏈表的第一個(gè)元素 len=n-m+1; //兩個(gè)鏈表比較時(shí)，長鏈表應(yīng)移到的位置}i=1;while(i<len){i++;s=s->next;} //長鏈表要移到兩個(gè)鏈表尾部對齊的位置while(s){while(s&&s->data!=q->data)//對應(yīng)字母不等，后移指針 { s=s->next;q=q->next;}p=s; //p指向兩個(gè)鏈表共同后綴的起始位置while(s&&s->data==q->data)//如對應(yīng)字母相等，后移指針{ s=s->next;q=q->next;}}returnp; //返回兩個(gè)鏈表共同后綴的起始位置}（3）算法中求了兩個(gè)鏈表的長度，接著將長鏈表的指針移到兩鏈表的比較處，進(jìn)行對應(yīng)元素的比較，記住可能共同后綴的開始位置，直到鏈表尾?？偟臅r(shí)間復(fù)雜度為O(m+n)。5、(1)算法思想：定義一個(gè)大小為N的數(shù)組，初始化為0.在遍歷鏈表的同時(shí)將數(shù)組中索引值為節(jié)點(diǎn)的值的絕對值的元素置1.如果此元素已經(jīng)為1，說明此節(jié)點(diǎn)之前已經(jīng)有與此節(jié)點(diǎn)的值的絕對值相等的節(jié)點(diǎn)，需將此節(jié)點(diǎn)刪除。(2)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstructNode{Intdata;StructNode*next;}Node;(3)inta[n];//全局?jǐn)?shù)組標(biāo)志節(jié)點(diǎn)的絕對值的值是否出現(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ù)組中對應(yīng)的元素置1 { a[abs(p->data)]=1;r=p;p=p->next;} } returnhead;}(4)只遍歷一次鏈表，所以時(shí)間復(fù)雜度為O(n)因?yàn)樯暾埓笮閚的數(shù)組，所以空間復(fù)雜度為O(n)（n為節(jié)點(diǎn)絕對值的最大值）。6、(1)算法思想由于數(shù)組中有n個(gè)整數(shù)，則未出現(xiàn)的最小的正整數(shù)一定在1到n+1的范圍，假如：數(shù)組a為[1,2,3,4]，則最小正整數(shù)為5，也就是n+1。如果數(shù)組中介于1到n之間的正整數(shù)個(gè)數(shù)不足n個(gè)，則未出現(xiàn)的最小的正整數(shù)的范圍是1到n。設(shè)置一個(gè)輔助數(shù)組b,大小為n+2,初始值全部為0，然后對a[i]進(jìn)行遍歷，如果0<a[i]<=n+1，則將b[a[i]]賦值為1，接下來遍歷b數(shù)組，遇到的第一個(gè)滿足b[i]==0的就退出，i就是數(shù)組a中未出現(xiàn)過的最小正整數(shù)(2)代碼實(shí)現(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)算法的時(shí)間復(fù)雜度為O(n);空間復(fù)雜度為O(n)。7、(1)算法思想①首先尋找單鏈表的中心結(jié)點(diǎn)，使用兩個(gè)指針p、q，每次p走一步，q走兩步，當(dāng)q到鏈表尾時(shí)，p正好在鏈表中心的位置。②將鏈表后半段利用頭插法逆置。③從單鏈表前后兩段中依次各取一個(gè)結(jié)點(diǎn)，并重新排列。(2)代碼實(shí)現(xiàn)voidrealign(NODE*h){NODE*p,*q,*r,*s;p=q=h;while(q->next!=NULL){ //尋找中間結(jié)點(diǎn)p=p->next; //p向后移動一個(gè)結(jié)點(diǎn)q=q->next;if(q->next!=NULL)q=q->next;//q向后移動兩個(gè)結(jié)點(diǎn)}q=p->next; //p指向中間結(jié)點(diǎn)，q指向p后面的結(jié)點(diǎn)p->next=NULL;while(q!=NULL){ //從q開始逆置后半段r=q->next;q->next=p->next; //p是中間結(jié)點(diǎn)，每次新結(jié)點(diǎn)插入在p之后p->next=q;q=r;}s=h->next; //s指向前半部分的第一個(gè)結(jié)點(diǎn)q=p->next; //q指向后半部分的第一個(gè)結(jié)點(diǎn)p->next=NULL; //分成2個(gè)單鏈表while(q!=NULL){ //歸并單鏈表r=q->next;q->next=s->next; //將q指向的結(jié)點(diǎn)插入到s指向結(jié)點(diǎn)的后面s->next=q;s=q->next;q=r;}}時(shí)間復(fù)雜度為O(n)習(xí)題答案3一、選擇題1-5B、B、D、B、B6-10B、A、D、BD、C、二、填空題1、先進(jìn)后出，先進(jìn)先出2、23.12.3*2-4/34.5*7/++108.9/+3、假溢出4、rear=(rear+1)%ns=newLnode(x)；s->next=r->next；r->next=s；r=s5、O(1),O(n),O(1),O(1)三、判斷題對錯對對對四、應(yīng)用題三個(gè)：CDEBA，CDBEA，CDBAE435612不可以321，325641可以，154623不可以432，135426可以Rear=4和front=2隊(duì)列為滿的條件：(rear+1)%MaxSize==front隊(duì)列為空的條件:front==rear5、(1)A*B*C(2)(A+B)*C-D(3)A*B+C/(D-E)(4)(A+B)*D+E/(F+A*D)+C(1)ABC** (2)AB+C*D- (3)AB*CDE-/+ (4)AB+D*EFAD*+/C+五、算法設(shè)計(jì)題1、#definemaxsize100//兩棧共享順序存儲空間所能達(dá)到的最多元素?cái)?shù)#defineElemTypeint∥假設(shè)元素類型為整型typedefstruct{ ElemTypestack[maxsize];∥?？臻g inttop[2];∥top為兩個(gè)棧頂指針}stk;stks;∥s是如上定義的結(jié)構(gòu)類型變量，//為全局變量入棧操作：intpush(inti,intx)∥入棧。i=0表示左棧s1，i=1表示右棧s2，x是入棧元素。入棧成功返回1，否則返回0{ if(i<0||i>1){printf(“棧號輸入不對\n”);exit(0);} if(s.top[1]-s.top[0]==1){printf(“棧已滿\n”);return(0);} switch(i) {case0:s.stack[++s.top[0]]=x;return(1);break; case1:s.stack[--s.top[1]]=x;return(1); }}∥push退棧操作:ElemTypepop(inti)∥退棧算法。i=0時(shí)為s1棧，i=1時(shí)為s2棧。退棧成功返回退棧元素，否則返回-1{ if(i<0||i>1){printf(“棧號輸入錯誤\n”)；exit(0);} switch(i) {case0:if(s.top[0]==-1){printf(“?？誠n”)；return（-1）；} elsereturn(s.stack[s.top[0]--]); case1:if(s.top[1]==maxsize){printf(“?？誠n”);return(-1);} elsereturn(s.stack[s.top[1]++]);}∥switch}∥算法結(jié)束判斷棧空intEmpty();{return(S.top[0]==-1&&S.top[1]==m);}2、（1）初始化SeQueueQueueInit(SeQueueQ){//初始化隊(duì)列 Q.front=Q.rear=0;Q.tag=0; returnQ;}（2）入隊(duì)SeQueueQueueIn(SeQueueQ,inte){//入隊(duì)列 if((Q.tag==1)&&(Q.rear==Q.front)) printf("隊(duì)列已滿\n");

else{Q.rear=(Q.rear+1)%m; Q.data[Q.rear]=e;if(Q.tag==0)Q.tag=1;//隊(duì)列已不空 } returnQ;}(3)出隊(duì)ElemTypeQueueOut(SeQueueQ){//出隊(duì)列 if(Q.tag==0){printf("隊(duì)列為空\n");exit(0);}

else { Q.front=(Q.front+1)%m; e=Q.data[Q.front]; if(Q.front==Q.rear)Q.tag=0;//空隊(duì)列 } return(e);}3、（1）循環(huán)隊(duì)列的定義typedefstruct{ ElemTypeQ[m];∥循環(huán)隊(duì)列占m個(gè)存儲單元 intrear,length;∥rear指向隊(duì)尾元素,length為元素個(gè)數(shù)}SeQueue;(2)初始化SeQueueQueueInit(SeQueuecq)∥cq為循環(huán)隊(duì)列，本算法進(jìn)行隊(duì)列初始化{ cq.rear=0; cq.length=0; returncq;}(3)入隊(duì)SeQueueQueueIn(SeQueuecq，ElemTypex)∥cq是以如上定義的循環(huán)隊(duì)列，本算法將元素x入隊(duì){ if(cq.length==m)return(0);∥隊(duì)滿 else {cq.rear=(cq.rear+1)%m;∥計(jì)算插入元素位置 cq.Q[cq.rear]=x;∥將元素x入隊(duì)列 cq.length++;∥修改隊(duì)列長度 } return(cq);}（4）出隊(duì)ElemTypeQueueOut(SeQueuecq)∥cq是以如上定義的循環(huán)隊(duì)列，本算法是出隊(duì)算法，且返回出隊(duì)元素{ if(cq.length==0)return(0);∥隊(duì)空 else {intfront=(cq.rear-cq.length+1+m)%m; ∥出隊(duì)元素位置 cq.length--;∥修改隊(duì)列長度

return(cq.Q[front]);∥返回對頭元素 }}4、（1）遞歸intAck(intm,n){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,m-1));}∥算法結(jié)束（2）非遞歸intAckerman(intm,intn){intakm[M][N];intI,j;for(j=0;j<N;j++)akm[0][j];=j+1;for(i=1;i<m;i++){akm[i][0]=akm[i-1][1];for(j=1;j<N;j++)akm[i][j]=akm[i-1][akm[i][j-1]];}return(akm[m][n]);}∥算法結(jié)束5、intsympthy(charstr[],chars[]){inti=0,j,n;while(str[i]!=‘\0’)i++;//查字符個(gè)數(shù)n=i;for(i=0;i<n/2;i++)s[i]=str[i];//前一半字符入棧j=i-1;if(n%2==1)i++;//n為奇數(shù)時(shí)中間字符不用比較while(i<n&&str[i]==s[j])//比較字符串是否是回文{i++;j--;}if(i==n)printf(“字符串是回文\n”)；elseprintf(“字符串不是回文\n”)；}6、VoidPermute(intS[],intj,intn)∥對S[j]――S[n-1]中的n-j個(gè)元素進(jìn)行全排列，j的初值為0{ inti,temp; if(j==n-1)//只有一個(gè)元素 {for(i=0;i<n;i++)printf(“%5d”,S[i]);printf(“\n”);} else for(i=j;i<n;i++)//j位置元素固定，求j+1到n的全排列{temp=S[j];S[j]=S[i];S[i]=temp;Permute(S,j+1,n);temp=S[j];S[j]=S[i];S[i]=temp;}習(xí)題答案4一、選擇題1-6B、A、B、D、C、B二、填空題1．字符2.O(m+n)3．-100112014．-10-10-1310三、判斷題對對錯錯四、應(yīng)用題1、空串：當(dāng)串的長度n=0時(shí)，串中沒有任何字符，稱為空串，如S=“”；空格串：由空格字符組成的串，稱為空格串，如S=“”子串：串中任意個(gè)連續(xù)的字符組成的子序列被稱為該串的子串?？沾侨我獯淖哟?；任意串S都是S自身的子串。主串：包含子串的串又被稱為該子串的主串。2、KMP的特點(diǎn)是主串無需回溯，主串指針一直往后移動，只有子串指針回溯，大大減少算法的比較次數(shù)和回溯次數(shù)。3、五、算法設(shè)計(jì)題1、[題目分析]設(shè)字符串存于字符數(shù)組X中，若轉(zhuǎn)換后的數(shù)是負(fù)數(shù)，字符串的第一個(gè)字符必為'-'轉(zhuǎn)換過程如下：將取出的數(shù)字字符減去字符零（'0'）的ASCII值，變成數(shù)；先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分結(jié)果；如此一個(gè)字符一個(gè)字符的轉(zhuǎn)換，直到字符串結(jié)束，得到結(jié)果。longatoi(char*X){longnum=0; //結(jié)果整數(shù)初始化inti=1; //i為數(shù)組下標(biāo)if(X==NULL){cout<<"PointerisNULL\n";return0;}if(X[0]!='-')num=X[0]-'0'; //如是正數(shù)，x[0]是數(shù)字字符while(X[i]!='\0') //當(dāng)字符串未到尾，進(jìn)行數(shù)的轉(zhuǎn)換num=10*num+(X[i++]-'0'); //先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分結(jié)果if(X[0]=='-')return(-num); //負(fù)數(shù)elsereturn(num); //返回正數(shù)}2、（1）//求重復(fù)子串的長度intrptSubLen(char*p,char*q){ intlen=0;while(*p&&*q){if(*p==*q){ ++len;p++,q++;}elsebreak;}returnlen;}（2）//求最長重復(fù)子串voidlongestRepeatSub(char*arr,intsize,int&maxLen,int&maxIndex){inti,j,len;maxLen=0; //記錄最長重復(fù)子串的長度maxIndex=-1; //記錄最長重復(fù)子串的下標(biāo)for(i=0;i<size;++i){for(j=i+1;j<size;++j){len=rptSubLen(&arr[i],&arr[j]);if(len>maxLen){maxLen=len;maxIndex=i;}}}if(maxLen==0)return;i=maxIndex;cout<<"Thelongestrepeatsubstring：";while(maxLen--)cout<<arr[i++];cout<<endl;}3、//利用4.2.1節(jié)已經(jīng)給定的順序存儲結(jié)構(gòu)的串的類型定義StringString&String::replace(intpos,intnum,constString&t){Stringtemp(*this); inti=0,j=0;if(pos<1||num<0){ //參數(shù)錯誤return*this;}curLen+=t.curLen-j; delete[]str; str=newchar[curLen+1]; assert(str!='\0'); while(i<pos-1) //拷貝原串前pos-1個(gè)元素str[i]=temp.str[i++];while(j<t.curLen) //拷貝t串str[i++]=t.str[j++];j=pos+num-1;while(temp.str[j]!='\0') //拷貝原串從第pos+num個(gè)到串尾的元素str[i++]=temp.str[j++];str[i]='\0';return*this;}4、voidInvertStore(charA[]){∥字符串逆序存儲的遞