西北大学《数据结构》典型例题（1-5章）(5)

{

r->next=s;r=s; } }//while

p->next=A;q->next=B;r->next=C; //完成循环链表 }//LinkList_divide 2.34

void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值 {

p=L.left;pre=NULL; while(p) {

printf(\ q=XorP(p->LRPtr,pre);

pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针 }

}//Print_XorLinkedList 2.35

Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x {

p=L.left;pre=NULL;

r=(XorNode*)malloc(sizeof(XorNode)); r->data=x;

if(i==1) //当插入点在最左边的情况 {

p->LRPtr=XorP(p.LRPtr,r); r->LRPtr=p; L.left=r; return OK; }

j=1;q=p->LRPtr; //当插入点在中间的情况

while(++j

q=XorP(p->LRPtr,pre); pre=p;p=q;

}//while //在p,q两结点之间插入

if(!q) return INFEASIBLE; //i不可以超过表长 p->LRPtr=XorP(XorP(p->LRPtr,q),r); q->LRPtr=XorP(XorP(q->LRPtr,p),r); r->LRPtr=XorP(p,q); //修改指针 return OK;

}//Insert_XorLinkedList 2.36

Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素 {

p=L.left;pre=NULL;

if(i==1) //删除最左结点的情况 {

q=p->LRPtr;

q->LRPtr=XorP(q->LRPtr,p); L.left=q;free(p); return OK; }

j=1;q=p->LRPtr; while(++j

q=XorP(p->LRPtr,pre); pre=p;p=q;

}//while //找到待删结点q

if(!q) return INFEASIBLE; //i不可以超过表长 if(L.right==q) //q为最右结点的情况 {

p->LRPtr=XorP(p->LRPtr,q);

L.right=p;free(q); return OK; }

r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点 p->LRPtr=XorP(XorP(p->LRPtr,q),r);

r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针 free(q); return OK;

}//Delete_XorLinkedList 2.37

void reform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点 {

p=L.next;

while(p->next!=L&&p->next->next!=L) {

p->next=p->next->next; p=p->next;

} //此时p指向最后一个奇数结点 if(p->next==L) p->next=L->pre->pre; else p->next=l->pre;

p=p->next; //此时p指向最后一个偶数结点 while(p->pre->pre!=L) {

p->next=p->pre->pre; p=p->next; }

p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p->next!=L;p=p->next) p->next->pre=p; L->pre=p; //调整pre链的结构,同2.32方法 }//reform

分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.

2.38

DuLNode* LOCATE(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找 {

p=L.next;

while(p.data!=x&&p!=L) p=p->next; if(p==L) return NULL; //没找到 p->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; //调整位置 } return p; }//LOCATE 2.39

float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值 {

PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q->coef) {

while(exexp) xp*=x0; sum+=q->coef*xp; q++; }

return sum; }//GetValue_SqPoly 2.40

void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3

{

PolyTerm *p,*q,*r;

Create_SqPoly(P3); //建立空多项式P3 p=P1.data;q=P2.data;r=P3.data; while(p->coef&&q->coef) {

if(p->expexp) {

r->coef=p->coef; r->exp=p->exp; p++;r++; }

else if(p->expexp) {

r->coef=-q->coef; r->exp=q->exp; q++;r++; } else {

if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中 {

r->coef=p->coef-q->coef; r->exp=p->exp;r++; }//if p++;q++; }//else }//while

while(p->coef) //处理P1或P2的剩余项 {

r->coef=p->coef; r->exp=p->exp; p++;r++;