【正文】 e(i) [m++]=[i++]。 //A的剩余元素重新存儲。=m。 }// SqList_Intersect_Delete分析:先從B和C中找出共有元素,記為same,再在A中從當(dāng)前位置開始, 凡小于same的元素均保留(存到新的位置),等于same的就跳過,到大于same時就再找下一個same. void LinkList_Intersect_Delete(LinkList amp。A,LinkList B,LinkList C)//在鏈表結(jié)構(gòu)上重做上題{p=Bnext。q=Cnext。r=Anext。while(pamp。amp。qamp。amp。r){if(pdataqdata) p=pnext。else if(pdataqdata) q=qnext。else{u=pdata。 //確定待刪除元素uwhile(rnextdatau) r=rnext。 //確定最后一個小于u的元素指針rif(rnextdata==u){s=rnext。while(sdata==u){t=s。s=snext。free(t)。 //確定第一個大于u的元素指針s}//whilernext=s。 //刪除r和s之間的元素}//ifwhile(pdata=u) p=pnext。while(qdata=u) q=qnext。}//else}//while}//LinkList_Intersect_Delete Status Delete_Pre(CiLNode *s)//刪除單循環(huán)鏈表中結(jié)點s的直接前驅(qū){p=s。while(pnextnext!=s) p=pnext。 //找到s的前驅(qū)的前驅(qū)ppnext=s。return OK。}//Delete_Pre Status DuLNode_Pre(DuLinkList amp。L)//完成雙向循環(huán)鏈表結(jié)點的pre域{for(p=L。!pnextpre。p=pnext) pnextpre=p。return OK。}//DuLNode_Pre Status LinkList_Divide(LinkList amp。L,CiList amp。A,CiList amp。B,CiList amp。C)//.{s=Lnext。A=(CiList*)malloc(sizeof(CiLNode))。p=A。B=(CiList*)malloc(sizeof(CiLNode))。q=B。C=(CiList*)malloc(sizeof(CiLNode))。r=C。 //建立頭結(jié)點while(s){if(isalphabet(sdata)){pnext=s。p=s。}else if(isdigit(sdata)){qnext=s。q=s。}else{rnext=s。r=s。}}//whilepnext=A。qnext=B。rnext=C。 //完成循環(huán)鏈表}//LinkList_Divide void Print_XorLinkedList(XorLinkedList L)//從左向右輸出異或鏈表的元素值{p=。pre=NULL。while(p){printf(%d,pdata)。q=XorP(pLRPtr,pre)。pre=p。p=q。 //任何一個結(jié)點的LRPtr域值與其左結(jié)點指針進行異或運算即得到其右結(jié)點指針}}//Print_XorLinkedList Status Insert_XorLinkedList(XorLinkedList amp。L,int x,int i)//在異或鏈表L的第i個元素前插入元素x{p=。pre=NULL。r=(XorNode*)malloc(sizeof(XorNode))。rdata=x。if(i==1) //當(dāng)插入點在最左邊的情況{pLRPtr=XorP(,r)。rLRPtr=p。=r。return OK。}j=1。q=pLRPtr。 //當(dāng)插入點在中間的情況while(++jiamp。amp。q){q=XorP(pLRPtr,pre)。pre=p。p=q。}//while //在p,q兩結(jié)點之間插入if(!q) return INFEASIBLE。 //i不可以超過表長pLRPtr=XorP(XorP(pLRPtr,q),r)。qLRPtr=XorP(XorP(qLRPtr,p),r)。rLRPtr=XorP(p,q)。 //修改指針return OK。}//Insert_XorLinkedList Status Delete_XorLinkedList(XorlinkedList amp。L,int i)//刪除異或鏈表L的第i個元素{p=。pre=NULL。if(i==1) //刪除最左結(jié)點的情況{q=pLRPtr。qLRPtr=XorP(qLRPtr,p)。=q。free(p)。return OK。}j=1。q=pLRPtr。while(++jiamp。amp。q){q=XorP(pLRPtr,pre)。pre=p。p=q。}//while //找到待刪結(jié)點qif(!q) return INFEASIBLE。 //i不可以超過表長if(==q) //q為最右結(jié)點的情況{pLRPtr=XorP(pLRPtr,q)。=p。free(q)。return OK。}r=XorP(qLRPtr,p)。 //q為中間結(jié)點的情況,此時p,r分別為其左右結(jié)點pLRPtr=XorP(XorP(pLRPtr,q),r)。rLRPtr=XorP(XorP(rLRPtr,q),p)。 //修改指針free(q)。return OK。}//Delete_XorLinkedList void OEReform(DuLinkedList amp。L)//按1,3,5,...4,2的順序重排雙向循環(huán)鏈表L中的所有結(jié)點{p=。while(pnext!=Lamp。amp。pnextnext!=L){pnext=pnextnext。p=pnext。} //此時p指向最后一個奇數(shù)結(jié)點if(pnext==L) pnext=Lprepre。else pnext=lpre。p=pnext。 //此時p指向最后一個偶數(shù)結(jié)點while(pprepre!=L){pnext=pprepre。p=pnext。}pnext=L。 //按題目要求調(diào)整了next鏈的結(jié)構(gòu),此時pre鏈仍為原狀for(p=L。pnext!=L。p=pnext) pnextpre=p。Lpre=p。 //調(diào)整pre鏈的結(jié)構(gòu),}//OEReform分析:,必須使用堆棧保存偶數(shù)結(jié)點的指針,否則將會破壞鏈表結(jié)構(gòu),造成結(jié)點丟失. DuLNode * Locate_DuList(DuLinkedList amp。L,int x)//帶freq域的雙向循環(huán)鏈表上的查找{p=。while(!=xamp。amp。p!=L) p=pnext。if(p==L) return NULL。 //沒找到pfreq++。q=ppre。while(qfreq=pfreq) q=qpre。 //查找插入位置if(q!=ppre){pprenext=pnext。pnextpre=ppre。qnextpre=p。pnext=qnext。qnext=p。ppre=q。 //調(diào)整位置}return p。}//Locate_DuList float GetValue_SqPoly(SqPoly P,int x0)//求升冪順序存儲的稀疏多項式的值{PolyTerm *q。xp=1。q=。sum=0。ex=0。while(qcoef){while(exqexp) xp*=x0。sum+=qcoef*xp。q++。}return sum。}//GetValue_SqPoly void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly amp。 3)//求稀疏多項式P1減P2的差式P3{PolyTerm *p,*q,*r。Create_SqPoly(P3)。 //建立空多項式P3p=。q=。r=。while(pcoefamp。amp。qcoef){if(pexpqexp){rcoef=pcoef。rexp=pexp。p++。r++。}else if(pexpqexp){rcoef=qcoef。rexp=qexp。q++。r++。}else{if((pcoefqcoef)!=0) //只有同次項相減不為零時才需要存入P3中{rcoef=pcoefqcoef。rexp=pexp。r++。}//ifp++。q++。}//else}//whilewhile(pcoef) //處理P1或P2的剩余項{rcoef=pcoef。rexp=pexp。p++。r++。}while(qcoef){rcoef=qcoef。rexp=qexp。q++。r++。}}//Subtract_SqPoly void QiuDao_LinkedPoly(LinkedPoly amp。L)//對有頭結(jié)點循環(huán)鏈表結(jié)構(gòu)存儲的稀疏多項式L求導(dǎo){p=Lnext。if(!p){Lnext=pnext。p=pnext。 //跳過常數(shù)項}while(p!=L){p*=p。//對每一項求導(dǎo)p=pnext。}}//QiuDao_LinkedPoly void Divide_LinkedPoly(LinkedPoly amp。L,amp。A,amp。B)//把循環(huán)鏈表存儲的稀疏多項式L拆成只含奇次項的A和只含偶次項的B{p=Lnext。A=(PolyNode*)malloc(sizeof(PolyNode))。B=(PolyNode*)malloc(sizeof(PolyNode))。pa=A。pb=B。while(p!=L){if(p!=2*(p)){panext=p。pa=p。}else{pbnext=p。pb=p。}p=pnext。}//whilepanext=A。pbnext=B。 }//Divide_LinkedPolytypedef struct{ Elemtype *base[2]。 Elemtype *top[2]。 }BDStacktype。 //雙向棧類型 Status Init_Stack(BDStacktype amp。tws,int m)//初始化一個大小為m的雙向棧tws{ [0]=(Elemtype*)malloc(sizeof(Elemtype))。 [1]=[0]+m。 [0]=[0]。 [1]=[1]。 return OK。}//Init_StackStatus push(BDStacktype amp。tws,int i,Elemtype x)//x入棧,i=0表示低端棧,i=1表示高端棧{ if([0][1]) return OVERFLOW。 //注意此時的棧滿條件 if(i==0) *[0]++=x。 else if(i==1) *[1]=x。 else return ERROR。 return OK。}//pushStatus pop(BDStacktype amp。tws,int i,Elemtype amp。x)//x出棧,i=0表示低端棧,i=1表示高端棧{ if(i==0) { if([0]==[0]) return OVERFLOW。 x=*[0]。 } else if(i==1) { if([1]==[1]) return OVERFLOW。 x=*++[1]。 } else return ERROR。 return OK。}//popvoid Train_arrange(char *train)//這里用字符串train表示火車,39。H39。表示硬席,39。S39。表示軟席{ p=train。q=train。 InitStack(s)。 while(*p) { if(*p==39。H39。) push(s,*p)。 //把39。H39。存入棧中 else *(q++)=*p。 //把39。S39。調(diào)到前部 p++。 } while(!StackEmpty(s)) { pop(s,c)。 *(q++)=c。 //把39。H39。接在后部 }}//Train_arrangeint IsReverse()//判斷輸入的字符串中39。amp。39。前和39。amp。39。后部分是否為逆串,是則返回1,否則返回0{ InitStack(s)。 while((e=getchar())!=39。amp。39。) push(s,e)。 wh