數(shù)據(jù)結(jié)構(gòu)作業(yè)答案市公開課金獎市賽課一等獎?wù)n件

線性表作業(yè)答案1、編寫算法實現(xiàn)次序表就地逆置。#defineMaxSize<次序表最大元素個數(shù)>typedefstruct

{DataTypelist[MaxSize];

intsize;

}SeqList;

第1頁voidConverseSeqList(SeqList*L){intmid,i;DataTypex;mid=L->size/2;for(i=0;i<mid;i++){x=L->list[i];L->list[i]=L->list[L->size-1-i];L->list[L->size-1-i]=x;}}第2頁2.編寫算法實現(xiàn)單鏈表就地逆置。先定義結(jié)點結(jié)構(gòu)：typedefstructNode{DataTypedata;structNode*next;}SLNode;第3頁voidConverseSList(SLNode*head){SLNode*p,*q;p=head->next;head->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=head->next;head->next=q;}}第4頁3、已知線性表中元素以值遞增有序排列，并以單鏈表作存放結(jié)構(gòu)。設(shè)計算法刪除表中全部值大于mink且小于maxk元素。分析：刪除結(jié)點特點：

<=mink>mink<maxk>=maxk第5頁voidDelete_Between(SLNode*L,intmink,intmaxk)//刪除元素遞增排列鏈表L中值大于mink且//小于maxk全部元素

{

SLNode*p,*pre,*q,*s;p=L->next;while(p&&p->data<=mink){pre=p;p=p->next;}if(p){while(p&&p->data<maxk)p=p->next;q=pre->next;pre->next=p;while(q!=p){s=q;q=q->next;free(s);}}

第6頁4、已知A、B和C為三個有序鏈表，編寫算法從A表中刪除B表和C表中共有數(shù)據(jù)元素。分析：被刪元素特點：ai=bj=ck其它元素則為：ai<bj或bj<ck或ck<ai

第7頁設(shè)三個指針pa,pb,pc分別指向這三個鏈表中對應(yīng)結(jié)點，則算法中主要操作為：if(pa->data<pb->data){pre=pa;pa=pa->next;}elseif(pb->data<pc->data)pb=pb->next;elseif(pc->data<pa->data)pc=pc->next;else{pre->next=pa->next;free(pa);pa=pre->next;}循環(huán)條件：三個指針均不為空。第8頁voidDelSame(SLNode*la,SLNode*lb,SLNode*lc){SLNode*pre,*pa,*pb,*pc;pre=la;pa=la->next;pb=lb->next;pc=lc->next;while(pa&&pb&&pc){if(pa->data<pb->data){pre=pa;pa=pa->next;}elseif(pb->data<pc->data)pb=pb->next;elseif(pc->data<pa->data)pc=pc->next;else{pre->next=pa->next;free(pa);pa=pre->next;}}}第9頁5、設(shè)將n(n>1)個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面盡可能高效算法，將R中序列循環(huán)左移p（0<p<n）個位置，即將R中數(shù)據(jù)由（x0,x1,…,xn-1）變換為（xp,xp+1,…,xn-1,x0,x1,…,xp-1）。要求：（1）給出算法基本設(shè)計思想。（2）依據(jù)設(shè)計思想，采取C或C++語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法時間復(fù)雜度和空間復(fù)雜度。第10頁（1）算法基本設(shè)計思想：先將n個數(shù)（x0,x1,…,xp,…,xn-1）原地逆置，得到（xn-1,…,xp,xp-1,…x0），然后再將前n-p個和后p個元素分別原地逆置，得到最終止果：xp,xp+1,…,xn-1,x0,x1,…,xp-1。算法能夠用兩個函數(shù)實現(xiàn)：一個是逆置函數(shù)reverse()，它將給定數(shù)據(jù)逆置；另一個是循環(huán)左移函數(shù)leftShift()，它調(diào)用reverse()函數(shù)三次，實現(xiàn)對應(yīng)功效。第11頁（2）算法實現(xiàn)：voidreverse(intr[],intleft,intright){intk=left,j=right,temp;//k等于左邊界left，j等于右邊界rightwhile(k<j){//交換r[k]與r[j]temp=r[k];r[k]=r[j];r[j]=temp;k++;//k右移一個位置j--;//j左移一個位置}}第12頁voidleftShift(intr[],intn,intp){if(p>0&&p<n){reverse(r,0,n-1);//將全部數(shù)據(jù)逆置reverse(r,0,n-p-1);//將前n-p個元素逆置reverse(r,n-p,n-1);//將后p個元素逆置}}（3）算法時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。第13頁6、假設(shè)利用兩個線性表LA和LB分別表示兩個集合A和B（即：線性表中數(shù)據(jù)元素即為集合中組員），現(xiàn)要求一個新集合A=A∪B。采取單鏈表作為存放結(jié)構(gòu)，編寫算法。

上述問題等價于：要求對線性表作以下操作：擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中數(shù)據(jù)元素插入到線性表LA中去。