數(shù)據(jù)結(jié)構(gòu)算法題

前五章習(xí)題算法2.2算法設(shè)計(jì)題設(shè)計(jì)一個(gè)算法從一給定的有序順序表L中刪除元素值在X到Y(jié)(X〈=Y)之間的所有元素，要求以較高的效率實(shí)現(xiàn)，要求算法的空間復(fù)雜度為0(1)voiddelete(SqList&L,ElemTypex,ElemTypey){mti=0.k=0;while(i<L.length)(if(L.elem[i]>=x&&L.elem[i]<=y)k++;//記錄被刪記錄的個(gè)數(shù)elseL.elem[i-k]=L.elem[i];//前移k個(gè)位置1++;)L.length=L.length-k;}2設(shè)一個(gè)有序表L,含有2n個(gè)整數(shù)，其中n個(gè)位負(fù)數(shù),n個(gè)為正數(shù)，設(shè)計(jì)一個(gè)算法將L中所有元素按正負(fù)相間排列.要求算法的空間復(fù)雜度為0(1),時(shí)間復(fù)雜度為O(n)voidmove(SqList&L){mti=OJ=L.length-l;mttemp;while(Kj)//使得正數(shù)都在前半部分，負(fù)數(shù)都在后半部分(wliile(i<j&&L.elem[i]>O)i++;while(i<j&&L.elem[j]<0)j—;if(ivj)〃交換L.elem[i](負(fù)數(shù))和L.elem[j](正數(shù))(temp=L.elem[i];L.elem[i]=L.elemIj];L.elemlj]=temp;}1=1;while(i<L.lengtli'2)〃通過交換使得正負(fù)數(shù)相間(j=L.length-2;temp=L.elem[i];L.elem[i]=L.elem[j];L.elem|j]=temp;i=i+2;J=J?2；)}3,假設(shè)一兩個(gè)元素依之二值遞增有序排列的線性表A和B分別表示兩個(gè)集合(同一元素值各不相同)，要求分別設(shè)計(jì)求A和B交并差集的算法,要求結(jié)果線形表中的元素依值遞增有序排列，試對(duì)順序表實(shí)現(xiàn)上述操作.交集：voidintersection(SqListA.SqListB,SqList&C){hiti=O,j=O,k=O;wliile(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;else{C.elem[k]=A.elem[i];k++；i++j-H-；)//共同的元素}C.length=k;}并集：voidUnion(SqListA,SqListB,SqList&C){hiti=O,j=O,k=O;wliile(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])(C.elem[k]=A.elem[i]:k++；i++；}elseif(A.elem[i]>B.elemfj])(C.elem[k]=B.elem[j];k++J++;}else{C.elem[k]=A.elem[i];k++;i++j-H-；)//共同的元素只放一個(gè)}wliile(i<A.len)(C.elem[k]=A.elem[i];k++;i-H-}wliile(j<B.len)(C.elem[k]=B.elem[j];k-H-J-H-}C.length=k;}差集：voiddiffernce(SqListA.SqListB,SqList&C){hiti=O,j=O,k=O;wliile(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])(C.elem[k]=A.elem[i]:k++；i++；}elseif(A.elem[i]>B.elem|j])(j++；}else{i++j++;}〃共同的元素只放一個(gè)}wliile(i<A.length){C.elem[k]=A.elem[i];k++;i++}C.length=k;2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡答題：描述以下三個(gè)概念的區(qū)別:頭結(jié)點(diǎn)，頭指針，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素疆的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表.非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個(gè)概念對(duì)單鏈表.雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。頭結(jié)點(diǎn)head■adataluik頭指針首元結(jié)點(diǎn)簡而言之，頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。。。┦自亟Y(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素31的結(jié)點(diǎn)。試比較線性表的兩種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)，在什么情況下用順序表比鏈表好？①順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。②鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值,另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。?lt;1）,存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入.刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，旦其主要操作是查找，則采用順序表；若線性表的長度變化較大，旦其主要操作是插入.刪除操作，則采用鏈表。算法設(shè)計(jì)題1試寫一算法，對(duì)單鏈表的實(shí)現(xiàn)就地逆置StatusListOppose_L（LinkList&L）{LinkListp,q;p=L->next;//p指向單鏈表第一個(gè)結(jié)點(diǎn)L->next=NULL;〃形成空的單鏈表while（p）（〃采用頭插入法將p結(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面實(shí)現(xiàn)逆置q=p;p=p->next;q->next=L->next;L->next=q;)returnOK;2試設(shè)計(jì)一個(gè)算法，求A和Bl兩個(gè)單鏈表表示的集合的交集并集和差集，單鏈表中的數(shù)據(jù)遞增有序排列并集：LinkListBmgji(LuikList&HeadLLuikList&Head2XuikList&Head3){LNode*pl=Headl->next;LNode*p2=Head2->next;LNode*p3=Head3=Headl;wliile(pl&&p2){if(pl->data<p2->data){p3->next=pl;p3=p3->next;pl=pl->next;}else{if(pl->data>p2->data)p3->next=p2;p3=p3->next;p2=p2->next;}elsep3->next=pl;p3=p3->next;pl=pl->next;q=p2;fiee(q);p2=p2->next;}}}p3->next=(pl)?pl:p2;free(Head2);returnHead3;}交集：LinkListJiaoji(LuikList&HeadLLuikList&Head2.LuikList&Head3){LinkListpa,pb,r,p;pa=Headl->next;pb=Head2->next;i-Head3=Headl;while(pa&&pb)(if(pa->data<pb->data)(r->next=pa->next;free(pa);pa=r->next;}elseif(pa->data>pb->data)pb=pb->next;else(r->next=pa;r=pa;pa=pa->next;}}while(pa)(r->next=pa->next;free(pa);pa=i?->next;}while(Head2->next)〃釋放Head2鏈表所有的結(jié)點(diǎn)空間{p=Head2->next;Head2->next=p->next;free(p);returnHead3;}差集：LinkListChaji(LuikList&HeadLLuikList&Head2.LinkList&Head3){LinkListpa,pb,r,p;pa=Headl->next;pb=Head2->next;i-Head3=Headl;while(pa&&pb)(if(pa->data<pb->data)r->next=pa;r=i?->next;pa=pa->next;)elseif(pa->data>pb->data)pb=pb->next;else(r->next=pa->next;fiee(pa);pa=r->next;)}while(Head2->next)〃釋放Head2鏈表所有的結(jié)點(diǎn)空間{p=Head2->next;Head2->next=p->next;free(p);returnHead3;}3己知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)，試寫一高效的算法，刪除表中所有值大于Iirnik且小于maxk的元素(若表中存在這樣的元素)，同時(shí)釋放被刪除的結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度(注意:mink和maxk是給定的兩個(gè)參變量，它們的值可以和表中的元素相同,也可以不同)StatusListDelete_L(LuikList&L.ElemTypeniiiik,ElemTypemaxk){LinkListp,q.prev=NULL;if(nuiik>maxk)retiirnERROR;pre=L;p=pre->next;〃pre是p的前驅(qū)，p是pre的后繼while(p&&p->data<=nuiik)(〃尋找第一大于mink的元素，讓p指向它，pre指向其前驅(qū)pre=p;p=p->next;}//whilewlule(p&&p->data<maxk)〃刪除大于mink小于maxk的結(jié)點(diǎn){pre->next=p->next;free(p);p=pre->next;}leturnOK;}3.2算法設(shè)計(jì)題假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊(duì)列初始化，如隊(duì)列和出隊(duì)列的算法l.typedefmtElemType;typedefstmctQNode(ElemTypedata;QNode*next;}QNode,*QPti;typedefstmct(QPtrrear;intsize;}Queue;StatusIiiitQueue(Queue&q)(Q.reai-(Qnode*)malloc(sizeof(QNode));if(IQ.rear)exit(OVERFLOW);q.reai->next=q.rear;〃空的循環(huán)鏈表q.size=0;returnOK;)StatusEnQueue(Queue&q,ElemTypee)(QPtip;p=(Qnode*)malloc(sizeof(QNode));retuniexit(OVERFLOW);p->data=e;〃創(chuàng)建被插入結(jié)點(diǎn)pp->next=q.iear->next;q.reai->next=p;q.reai=p;〃將p所指結(jié)點(diǎn)插入到q.rear的后面}q.size++;returnOK;}StatusDeQueue(Queue&q,ElemType&e){QPtip;if(q.size==O)ieturnFALSE;p=q.reai->next->next;〃p指向循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)(即被刪結(jié)點(diǎn))e=p->data;q.rear->next->next=p->next;//刪除p所指結(jié)點(diǎn)fiee(p);}q.size--;returnOK;}4.1算法設(shè)計(jì)題1.編寫一個(gè)實(shí)現(xiàn)串的置換操作Repalce(&s,T,V)的算法mtReplace(Stringtype&S,StringtypeT^StrmgtypeV)^/將串S中所有子串T替換為V,并返回置換次數(shù)fbr(n=O4=l；i<=Stilen(S)-Strlen(T)+l;i++)〃注意i的取值范圍if(!StrCompare(SubString(S,i,Strlen(T)),T))〃找到了與T匹配的子串(〃分別把T的前面和后面部分保存為head和tailStrAssign(head,SubStiiiig(S.14-1))；StrAssign(taiLSubStrmg(Sj+Strlen(T),Stiien(S)-i-Stilen(T)+l));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail));〃把head,"tail連接為新串i+=Strlen(V);〃當(dāng)前指針跳到插入串以后n++；n++；}//ifleturnn;"/Replace設(shè)計(jì)一個(gè)遞歸算法，利用串的基本運(yùn)算StrleiigthO，SubsUO，CoiicatQ等將非空串s的所有字符逆置.voidreveise(SqStiing&s){SqStringsl,s2;if(StiLength(s)>1)(sl=SubSti<s,l,l)y/sl=^ar,s2=SubStr(s,2,s1.len-1);//s2="a2…an”Reverse(s2);〃s2=”anan-l.….a2ns=Concat(s2,s1);//連接}}利用C的庫函數(shù)strlen.strcpy,strcat寫一算法voidStilens(char*S,char*T,mti),將串T插入到串s的第1個(gè)位置上，若1大于S的長度，則插入不執(zhí)行.voidStrliisert(char*S,char*T,mti){//將串T插入到串S的第i個(gè)位置上char*Temp;if(i<=stiien(S))(Tenip=(char*)malloc(sizeof(char[Maxsize]));//設(shè)置一個(gè)臨時(shí)串strcpy(Temp,&S[i])y/^第1位起以后的字符拷貝到臨時(shí)串中strcpy(&S[i],T);〃將串T拷貝到串S的第1個(gè)位置處，覆蓋后面的字符strcat(S,Temp);//把臨時(shí)串中的字符聯(lián)接到串S后面fiee(Temp);)以Hstring為存儲(chǔ)表示,寫一個(gè)求子串的算法HStrmg是指以動(dòng)態(tài)分配順序串為存儲(chǔ)表示，其定義為：typedefstmct(char*ch;intlength;jHStimg;void*substr(HStiiiig*sub,HStiing*s,intpos.mtlen){〃用sub返回串s的第pos個(gè)字符起長度為len的子串。sub初始時(shí)為一空串//pos的合法位置為0<=pos<=s->lengtli-1inti;if(pos<0||pos>s->length-i||len<=0)Enor(Mparametererror!n);//參數(shù)不合法，子串為空串if(s->lengtli<pos+len)//s串中沒有足夠的元素sub->len=s->length-pos;//設(shè)置子串的串長elsesub->length=len;〃設(shè)置子串的串長sub->ch=(cliar*)malloc(len*sizeof(char))y/sub->ch申請(qǐng)結(jié)點(diǎn)空間foi(i=0;i<sub->length;i++)//將s串中pos位置開始的共sub->length個(gè)字符復(fù)制到sub串中sub->ch[i]=s->ch[pos+i];}6.1編寫算法判別給定二叉樹是否為完全二叉樹.intIsFuU_Bitree(BitreeT)//判斷二叉樹是否完全二叉樹，是則返回1,否則返回0(ImtQueue(Q);flag=0;EiiQueue(Q,T);〃建立工作隊(duì)列while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)flag=l;elseiRflag)return0:else(EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);//不管孩子是否為空，都入隊(duì)列})//wlulereturn1;}//IsFull_Bitree分析:該問題可以通過層序遍歷的方法來解決.不管當(dāng)前結(jié)點(diǎn)是否有左右孩子，都入隊(duì)列.這樣當(dāng)樹為完全二叉樹時(shí)，遍歷時(shí)得到是一個(gè)連續(xù)的不包含空指針的序列.反之測序列中會(huì)含有空指針.6.2.1編寫遞歸算法，計(jì)算二叉樹中椰子節(jié)點(diǎn)的數(shù)目思路：輸出葉子結(jié)點(diǎn)比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子,將其打印出來。法1:核心部分為：DLR(liuyu*root)/*中序遍歷遞歸函數(shù)*/(if(ioot!=NULL)(if((ioot->lchild==NULL)&&(ioot->rcliild==NULL)){sum-H-;prmtf(H%dn'^root^data);}DLR(root->lchild);DLR(root->rchild);)return(O);)法二：mtLeafCount_BiTree(BitieeT)〃求二叉樹中葉子結(jié)點(diǎn)的數(shù)目(if(!T)return0;//空樹沒有葉子elseif(!T->lchild&&!T->rchild)return1;〃葉子結(jié)點(diǎn)elsereturnLeaf_Count(T->lcliild)+LeaCCount(T->rchild)y/左子樹的葉子數(shù)加上右子樹的葉子數(shù)}//LeafCount_BiTree6.2.2寫出求二叉樹深度的算法，先定義二叉樹的抽象數(shù)據(jù)類型，編寫遞歸算法,求