📄 xtjd2.htm
字号:
r->data=x;<br>
if(i==1) //当插入点在最左边的情况<br>
{<br>
p->LRPtr=XorP(p.LRPtr,r);<br>
r->LRPtr=p;<br>
L.left=r;<br>
return OK;<br>
}<br>
j=1;q=p->LRPtr; //当插入点在中间的情况<br>
while(++j<i&&q)<br>
{<br>
q=XorP(p->LRPtr,pre);<br>
pre=p;p=q;<br>
}//while //在p,q两结点之间插入<br>
if(!q) return INFEASIBLE; //i不可以超过表长<br>
p->LRPtr=XorP(XorP(p->LRPtr,q),r);<br>
q->LRPtr=XorP(XorP(q->LRPtr,p),r);<br>
r->LRPtr=XorP(p,q); //修改指针<br>
return OK;<br>
}//Insert_XorLinkedList
<p>2.36
<p>Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素<br>
{<br>
p=L.left;pre=NULL;<br>
if(i==1) //删除最左结点的情况<br>
{<br>
q=p->LRPtr;<br>
q->LRPtr=XorP(q->LRPtr,p);<br>
L.left=q;free(p);<br>
return OK;<br>
}<br>
j=1;q=p->LRPtr;<br>
while(++j<i&&q)<br>
{<br>
q=XorP(p->LRPtr,pre);<br>
pre=p;p=q;<br>
}//while //找到待删结点q<br>
if(!q) return INFEASIBLE; //i不可以超过表长<br>
if(L.right==q) //q为最右结点的情况<br>
{<br>
p->LRPtr=XorP(p->LRPtr,q);<br>
L.right=p;free(q);<br>
return OK;<br>
}<br>
r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点<br>
p->LRPtr=XorP(XorP(p->LRPtr,q),r);<br>
r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针<br>
free(q);<br>
return OK;<br>
}//Delete_XorLinkedList
<p>2.37
<p>void reform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点<br>
{<br>
p=L.next;<br>
while(p->next!=L&&p->next->next!=L)<br>
{<br>
p->next=p->next->next;<br>
p=p->next;<br>
} //此时p指向最后一个奇数结点<br>
if(p->next==L) p->next=L->pre->pre;<br>
else p->next=l->pre;<br>
p=p->next; //此时p指向最后一个偶数结点<br>
while(p->pre->pre!=L)<br>
{<br>
p->next=p->pre->pre;<br>
p=p->next;<br>
}<br>
p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状<br>
for(p=L;p->next!=L;p=p->next) p->next->pre=p;<br>
L->pre=p; //调整pre链的结构,同2.32方法<br>
}//reform<br>
分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.
<p>2.38
<p>DuLNode* LOCATE(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找<br>
{<br>
p=L.next;<br>
while(p.data!=x&&p!=L) p=p->next;<br>
if(p==L) return NULL; //没找到<br>
p->freq++;q=p->pre;<br>
while(q->freq<=p->freq) q=q->pre; //查找插入位置<br>
if(q!=p->pre)<br>
{<br>
p->pre->next=p->next;p->next->pre=p->pre;<br>
q->next->pre=p;p->next=q->next;<br>
q->next=p;p->pre=q; //调整位置<br>
}<br>
return p;<br>
}//LOCATE
<p>2.39
<p>float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值<br>
{<br>
PolyTerm *q;<br>
xp=1;q=P.data;<br>
sum=0;ex=0;<br>
while(q->coef)<br>
{<br>
while(ex<q->exp) xp*=x0;<br>
sum+=q->coef*xp;<br>
q++;<br>
}<br>
return sum;<br>
}//GetValue_SqPoly
<p>2.40
<p>void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3<br>
{<br>
PolyTerm *p,*q,*r;<br>
Create_SqPoly(P3); //建立空多项式P3<br>
p=P1.data;q=P2.data;r=P3.data;<br>
while(p->coef&&q->coef)<br>
{<br>
if(p->exp<q->exp)<br>
{<br>
r->coef=p->coef;<br>
r->exp=p->exp;<br>
p++;r++;<br>
}<br>
else if(p->exp<q->exp)<br>
{<br>
r->coef=-q->coef;<br>
r->exp=q->exp;<br>
q++;r++;<br>
}<br>
else<br>
{<br>
if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中<br>
{<br>
r->coef=p->coef-q->coef;<br>
r->exp=p->exp;r++;<br>
}//if<br>
p++;q++;<br>
}//else<br>
}//while<br>
while(p->coef) //处理P1或P2的剩余项<br>
{<br>
r->coef=p->coef;<br>
r->exp=p->exp;<br>
p++;r++;<br>
}<br>
while(q->coef)<br>
{<br>
r->coef=-q->coef;<br>
r->exp=q->exp;<br>
q++;r++;<br>
}<br>
}//Subtract_SqPoly
<p>2.41
<p>void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导<br>
{<br>
p=L->next;<br>
if(!p->data.exp)<br>
{<br>
L->next=p->next;p=p->next; //跳过常数项<br>
}<br>
while(p!=L)<br>
{<br>
p->data.coef*=p->data.exp--;//对每一项求导<br>
p=p->next;<br>
}<br>
}//QiuDao_LinkedPoly
<p>2.42
<p>void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B<br>
{<br>
p=L->next;<br>
A=(PolyNode*)malloc(sizeof(PolyNode));<br>
B=(PolyNode*)malloc(sizeof(PolyNode));<br>
pa=A;pb=B;<br>
while(p!=L)<br>
{<br>
if(p->data.exp!=2*(p->data.exp/2))<br>
{<br>
pa->next=p;pa=p;<br>
}<br>
else<br>
{<br>
pb->next=p;pb=p;<br>
}<br>
p=p->next;<br>
}//while<br>
pa->next=A;pb->next=B;<br>
}//Divide_LinkedPoly</p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"> </p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"> </p>
<hr>
<p align="left"><b><span style="font-size:24.0pt;font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";color:blue;mso-font-kerning:1.0pt;
mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">数据结构辅导站</span><span style="mso-spacerun: yes; font-size: 24.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; color: blue; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
</span></b><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;
mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:
EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"><a href="index.htm">返回主页</a></span></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -