当前位置：首页 > 数据结构严蔚敏习题册 答案
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&&p!=L) 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(ex 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->exp r->coef=p->coef; r->exp=p->exp; p++;r++; } else if(p->exp 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; return OK; }//push Status pop(BDStacktype &tws,int i,Elemtype &x)//x出栈,i=0表示低端栈,i=1表示高端栈 { if(i==0) { if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } 搜索更多关于： 数据结构严蔚敏习题册 答案 的文档
本文作者：...共分享92篇相关文档
