数据结构习题集答案(c版)(清华大学严蔚敏)

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 OEReform(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方法 }//OEReform

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

DuLNode * Locate_DuList(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_DuList 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 & 3)//求稀疏多项式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++; }

while(q->coef) {

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

}//Subtract_SqPoly 2.41

void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导 {

p=L->next;

if(!p->data.exp) {

L->next=p->next;p=p->next; //跳过常数项 }

while(p!=L) {

p->data.coef*=p->data.exp--;//对每一项求导 p=p->next; }

}//QiuDao_LinkedPoly 2.42

void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只

含奇次项的A和只含偶次项的B {

p=L->next;

A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) {

if(p->data.exp!=2*(p->data.exp/2)) {

pa->next=p;pa=p; } else {

pb->next=p;pb=p; }

p=p->next; }//while

pa->next=A;pb->next=B; }//Divide_LinkedPoly

3.15

typedef struct{

Elemtype *base[2]; Elemtype *top[2];

}BDStacktype; //双向栈类型

Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws {

tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack

Status push(BDStacktype &tws,int i,Elemtype x)//x入栈,i=0表示低端栈,i=1表示高端栈 {

if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件 if(i==0) *tws.top[0]++=x;

else if(i==1) *tws.top[1]--=x; else return ERROR;