數(shù)據(jù)結(jié)構(gòu)與算法——第3章習(xí)題課練習(xí)題1.已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且p結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。(1)p=p->next;(2)p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p!=NULL)p=p->next;(6)while(Q->next!=NULL){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next!=NULL)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q)a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是11314(1)p=p->next;(2)p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p!=NULL)p=p->next;(6)while(Q->next!=NULL){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next!=NULL)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q)b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是1012811314(1)p=p->next;(2)p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p!=NULL)p=p->next;(6)while(Q->next!=NULL){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next!=NULL)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q)c.刪除P結(jié)點(diǎn)的語(yǔ)句序列是107314(1)p=p->next;(2)p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p!=NULL)p=p->next;(6)while(Q->next!=NULL){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next!=NULL)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q)d.刪除首元結(jié)點(diǎn)的語(yǔ)句序列是()1211314(1)p=p->next;(2)p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p!=NULL)p=p->next;(6)while(Q->next!=NULL){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next!=NULL)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q)e.刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是()9113142.已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和n。試寫一個(gè)算法將這兩個(gè)鏈表連接在一起（即令其中一個(gè)表的首元結(jié)點(diǎn)連在另一個(gè)表的最后一個(gè)結(jié)點(diǎn)之后）,假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。Linkmerge(Linkha,intm,Linkhb,intn){Node*p1,*p2;Linkhcif(m<n){p1=ha;p2=hb;}else{p1=hb;p2=ha;}hc=p1;while(p1->next!=NULL)p1=p1->next;p1->next=p2->next;free(p2);returnhc;}第3章棧和隊(duì)列5、試編寫一個(gè)算法，判斷依次讀入的一個(gè)以@為結(jié)束符的字母序列，是否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。voidHuiwen(char*str){ SeqStacka; inti;charch;InitStack(&a); for(i=0;str[i]!='\0'&&str[i]!='&';i++)Push(&a,str[i]); if(str[i]!='&'){ printf("Wrong"); return; }else i++; while(!IsEmpty(&a)&&str[i]!='\0'&&str[i]!='@') {Pop(&a,&ch); if(ch==str[i]) i++; else{ printf("Wrong"); return; } } if(IsEmpty(&a)&&str[i]=='@') printf("Right"); elseif(str[i]!='@')printf("Rightmore"); elseprintf("Leftmore");}7.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)、出隊(duì)算法。隊(duì)列初始化voidInitQueue(LinkList*tail){*tail=(LinkList)Malloc(sizeof(Node));(*tail)->next=(*tail);}入隊(duì)intEnterQueue(LinkListtail,ElemTypee){Node*new;if(new=(Node*)malloc(sizeof(Node))==NULL)return(0);new->data=e;new->next=tail->next;tail->next=new;

tail=new;

return(1);}出隊(duì)intEnterQueue(LinkListtail,ElemType*e){Node*tmp;if(tail->next==tail)return(0);tmp=tail->next->next;tail->next->next=tmp->next;(*e)=tmp->data;

if(tail==tmp)tail=tail->next;free(tmp);return(1);}8.要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用，設(shè)置一個(gè)標(biāo)志域tag,并以tag的值為0或1來(lái)區(qū)分，頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿。試編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)列和出隊(duì)列的算法。typedefstruct{ElemTypeelem[100];intfront;intrear;inttag;}Queue;InitQueue(Queue*Q){Q->front=Q->rear=Q->tag=0;}

EnQueue(Queue*Q,ElemTypee){if(Q->rear==Q->front&&Q->tag==1)return(ERROR)Q->elem[Q->rear]=e;Q->rear=(Q->rear+1)%MAXSIZE;

Q->tag=1;return(OK)}DeQueue(Queue*Q,ElemType*e){if(Q->rear==Q->front&&Q->tag==0)return(ERROR)*e=Q->elem[Q->front];Q->front=(Q->front+1)%MAXSIZE;Q->tag=0;return(OK)}P10210

證明：若借助棧由輸入序列（1,2,…,n）得到輸出序列（p1,p2,…,pn），那么在輸出序列中，不可能出現(xiàn)這種情況：存在i<j<k，使pj<pk<pi，這里（p1,p2,…,pn

）是（1,2,…,n）的一個(gè)全排列，每個(gè)元素只能按1,2,…,n的次序進(jìn)一次棧。注意：入棧序列為（1,2,…,n）因?yàn)閜j<pk<pi所以入棧順序?yàn)椤璸j…pk…pi…