第二章 線性表

第二章線性表StatusDeleteK(SqList&a,inti,intk)〃刪除線性表a中第i個(gè)元素起的k個(gè)元素(returnOK;}//DeleteKStatusInsert_SqList(SqList&va,intx)〃把x插入遞增有序表va中returnOK;}//Insert_SqListintListComp(SqListA,SqListB)〃比較字符表A和B,并用返回值表示結(jié)果，值為正,表示A>B;后為負(fù)，表示AvB;值為零，表示A=B{return0;}//ListCompLNode*Locate(LinkListLJntx)〃鏈表上的元素查找，返回指針(for(p=l->next;p&&p->data!=x;p=p->next);returnp;}//LocateintLength(LinkListL)〃求鏈表的長(zhǎng)度(for(k=0,p=L;p->next;p=p->next,k++);returnk;}//LengthvoidListConcat(LinkListha,LinkListhb,LinkList&hc)〃把鏈表hb接在ha后面形成鏈表he)〃此時(shí)P指向最后一個(gè)奇數(shù)結(jié)點(diǎn)if(p->next==L)p->next=L->pre->pre;elsep->next=l->pre;p=p->next;//此時(shí)p指向最后一個(gè)偶數(shù)結(jié)點(diǎn)while(p->pre->pre!=L)(p->next=p->pre->pre;p=p->next;)p->next=L;〃按題目要求調(diào)整了next鏈的結(jié)構(gòu)，此時(shí)pre鏈仍為原狀for(p=L;p->next!=L;p=p->next)p->next->pre=p;}//OEReform分析:next鏈和pre鏈的調(diào)整只能分開(kāi)進(jìn)行.如同時(shí)進(jìn)行調(diào)整的話，必須使用堆棧保存偶數(shù)結(jié)點(diǎn)的指針，否則將會(huì)破壞鏈表結(jié)構(gòu)，造成結(jié)點(diǎn)丟失.DuLNode*Locate_DuList(DuLinkedList&L,intx)〃帶freq域的雙向循環(huán)鏈表上的查找if(p==L)returnNULL;〃沒(méi)找至Up->freq++;q=p->pre;while(q->freq<=p->freq)q=q-〉pre;〃查找插入位置if(q!=p->pre)(p->pre->next=p->next;p->next->pre=p->pre;q->next->pre=p;p->next=q->next;q〉next=p;p->pre=q;〃調(diào)整位置)returnp;}//Locate_DuListfloatGetValue_SqPoly(SqPolyP,intx0)〃求升幕順序存儲(chǔ)的稀疏多項(xiàng)式的值|PolyTerm*q;sum=0;ex=0;while(q->coef)(while(ex<q->exp)xp*=xO;sum+=q->coef*xp;q++；returnsum;}//GetValue_SqPolyvoidSubtract_SqPoly(SqPolyPl,SqPolyP2,SqPoly&P3)〃求稀疏多項(xiàng)式Pl減P2的差式P3(PolyTerm*p,*q,*r;Create_SqPoly(P3);//建立空多項(xiàng)式P3while(p->coef&&q->coef)(if(p->exp<q->exp)(r->coef=p->coef;r->exp=p->exp;p++;r++;}elseif(p->exp<q->exp)(r->coef-q->coef;r->exp=q->exp;q++;r++;)else{if((p->coef-q->coef)!=0)//只有同次項(xiàng)相減不為零時(shí)才需要存入P3中(r->coef=p->coef-q->coef;r->exp=p->exp;r++;}//ifp++;q++;}//else}//whilewhile(p->coef)〃處理Pl或P2的剩余項(xiàng)(r->coef=p->coef;r->exp=p->exp;p++;r++;)while(q->coef)(r->coef=-q->coef;r->exp=q->exp;q++;r++;}//Subtract_SqPolyvoidQiuDao_LinkedPoly(LinkedPoly&L)〃對(duì)有頭結(jié)點(diǎn)循環(huán)鏈表結(jié)構(gòu)存儲(chǔ)的稀疏多項(xiàng)式L求導(dǎo)(P=L->next;{L-〉next=p->next;p=p-〉next;//跳過(guò)常數(shù)項(xiàng))while(p!=L)(p=p->next;)}//QiuDao_LinkedPolyvoidDivide_LinkedPoly(LinkedPoly&L,&A,&B)〃把循環(huán)鏈表存儲(chǔ)的稀疏多項(xiàng)式L拆成只含奇次項(xiàng)的A和只含偶次項(xiàng)的B(p=L->next;A=(PolyNode*)malloc(sizeof(PolyNode));B=(PolyNode*)malloc(sizeof(PolyNode));pa=A;pb=B;while(p!=L)pa->next=p;pa=p;)else(pb->next=p;pb=p;)p=p->next;}//whilepa->next=A;pb->next=B;}//Divide_IJnkedPolyhc=ha;p=ha;while(p->next)p=p->next;p->next=hb;}//ListConcat見(jiàn)書(shū)后答案.StatusInsert(LinkList&L,inti,intb)〃在無(wú)頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素b(p=L;q=(LinkList*)malloc(sizeof(LNode));if(i==l)()else(while(—i>l)p=p->next;q->next=p-〉next;p->next=q;//插入在第i個(gè)元素的位置)}//InsertStatusDelete(LinkList&L,inti)〃在無(wú)頭結(jié)點(diǎn)鏈表L中刪除第i個(gè)元素(if(i==l)L=L->next;〃刪除第一個(gè)元素else(P=L;while(-i>l)p=p->next;p->next=p->next->next;i個(gè)元素)}//DeleteStatusDelete_Between(Linklist&L,intmink,intmaxk)//刪除元素遞增排列的鏈表L中值大于mink且小于maxk的所有元素(P=L;while(p->next->data<=mink)p=p->next;//p是最后——個(gè)不大于mink的元素if(p->next)//如果還有比mink更大的元素(q=p->next;while(q->data<maxk)q=q->next;//q是第——個(gè)不小于maxk的元素p->next=q;}//Delete_BetweenStatusDelete_Equal(Linklist&L)/刪除元素遞增排列的鏈表L中所有值相同的元素{_p=L->next;q=p->next;〃p,q指向相鄰兩元素while(p->next)(if(p->data!=q->data)(p=p->next;q=p-〉next;//當(dāng)相鄰兩元素不相等時(shí),p,q都向后推一步)else(while(q->data==p->data)(free(q);q=q->next;)p->next=q;p=q;q=p->next;//當(dāng)相鄰元素相等時(shí)刪除多余元素}//else}//while}//Delete_Equalvoidreverse(SqList&A)〃順序表的就地逆置(for(i=lJ=A.length;i<j;i++J—)}//reversevoidLinkList_reverse(Linklist&L)〃鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next)(q->next=p;p=q;q=s;s=s->next;//把L的元素逐個(gè)插入新表表頭)q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析:本算茯的思想是，逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭.voidmergel(LinkList&A,LinkList&B,LinkList&C)〃把鏈表A和B合并為C,A和B的元素間隔排列，且使用原存儲(chǔ)空間p=A->next;q=B->next;C=A;while(p&&q)s=p->next;p->next=q;〃將B的元素插入if(s)(一t=q->next;q->next=s;〃如A非空，將A的元素插入)p=s;q=t;}//while}//merge1voidreverse_merge(LinkList&A,LinkList&B,LinkList&C)〃把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列，使用原空間{_pa=A->next;pb=B->next;pre=NULL;//pa和pb分別指向A,B的當(dāng)前元素while(pa||pb)(if(pa->data<pb->data||!pb){_pc=pa;q=pa->next;pa->next=pre;pa=q;//^A的元素插入新表)else{一pc=pb;q=pb->next;pb->next=pre;pb=q;〃將B的元素插入新表}pre=pc;)C=A;A->next=pc;〃構(gòu)造新表頭}//reverse_merge分析:本M去的思想是，按從小到大的順序依次把A和B的元素插入新表的頭部pc處，最后處理A或B的剩余元素.voidSqList_Intersect(SqListA,SqListB,SqList&C)〃求元素遞增排列的線性表A和B的元翥的交集并存入C中i=l;j=l;k=O;i++;j++;〃就添加到C中}}//while}//SqList_IntersectvoidLinkList_Intersect(LinkListA,LinkListB,LinkList&C)〃在鏈表結(jié)構(gòu)上重做上題(p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode));while(p&&q)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;else(s=(LNode*)malloc(sizeof(LNode));s->data=p->data;pc->next=s;pc=s;p=p->next;q=q->next;)}//whileC=pc;}//LinkList_IntersectvoidSqList_Intersect_True(SqList&A,SqListB)〃求元素遞增排列的線性表A和B的元素的交集并存直A中(i=l;j=l;k=O;i++;j++;//且C中沒(méi)有，就添加到C中)}//while}//SqList_Intersect_TruevoidLinkList_Intersect_True(LinkList&A,LinkListB)〃在鏈表結(jié)構(gòu)上重做上題p=A->next;q=B->next;pc=A;while(p&&q)(if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;elseif(p->data!=pc->data)(pc=pc->next;pc->data=p->data;p=p->next;q=q->next;)}//while}//LinkList_Intersect_TruevoidSqList_Intersect_Delete(SqList&A,SqListB,SqListC)(i=0;j=0;k=0;m=0;〃i指示A中元素原來(lái)的位置,m為移動(dòng)后的位置else}//while}//SqList_Intersect_Delete分析:先從B和C事找出共有元素，記為same,再在A中從當(dāng)前位置開(kāi)始，凡小于same的元素均保留(存到新的位置)，等于same的就跳過(guò),到大于same時(shí)就再找下一個(gè)same.voidLinkList_Intersect_Delete(LinkList&A,LinkListB,LinkListC)〃在鏈表結(jié)構(gòu)上重做上題{p=B->next;q=C->next;r=A-next;while(p&&q&&r)if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;else(u=p-〉data;//確定待刪除元素uwhile(r->next->data<u)r=r->next;〃確定最后一個(gè)小于u的元素指針rif(r->next->data==u)(s=r->next;while(s->data==u)(一t=s;s=s->next;free(t);//確定第一個(gè)大于u的元素指針s}//whiler->next=s;//刪除r和s之間的元素}//ifwhile(p->data=u)p=p->next;while(q->data=u)q=q->next;}//else}//while}//LinkList_Intersect_DeleteStatusDelete_Pre(CiLNode*s)〃刪除單循環(huán)鏈表中結(jié)點(diǎn)s的直接前驅(qū)(P=S；while(p->next->next!=s)p=p->next;//找到s的前驅(qū)的前驅(qū)pp->next=s;returnOK;}//Delete_PreStatusDuLNode_Pre(DuLinkList&L)〃完成雙向循環(huán)鏈表結(jié)點(diǎn)的pre域(for(p=L;!p->next->pre;p=p->next)p->next->pre=p;returnOK;}//DuLNode_Pres=L->next;A=(CiList*)malloc(sizeof(CiLNode));p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C;//建立頭結(jié)點(diǎn)while(s)if(isalphabet(s->data))p->next=s;p=s;)elseif(isdigit(s->data))(q->next=s;q=s;}else(r->next=s;r=s;)}//whilep->next=A;q->next=B;r->next=C;//完成循環(huán)鏈表}//LinkList_DividevoidPrint_XorLinkedList(XorLinkedListL)〃從左向右輸出異或鏈表的元素值(while(p)(printf(n%dn,p->data);q=XorP(p->LRPtr,pre);pre=p;p=q;〃任何一個(gè)結(jié)點(diǎn)的LRPtr域值與其左結(jié)點(diǎn)指針進(jìn)行異或運(yùn)算即得到其右結(jié)點(diǎn)指針)}//Print_XorLinkedListStatusInsert_XorLinkedList(XorLinkedList&L,intx,inti)〃在異或鏈表L的第i個(gè)元素前插入元素x(r=(XorNode*)malloc(sizeof(XorNode));r->data=x;if(i==l)//當(dāng)插入點(diǎn)在最左邊的情況(r->LRPtr=p;returnOK;)j=l;q=p->LRPtr;//當(dāng)插入點(diǎn)在中間的情況while(++j<i