假设在算法描述语言中引入指针的二元运算
异或
若a和b为指针
则a⊕b的运算结果仍为原指针类型
且
a⊕(a⊕b)=(a⊕a)⊕b=b
(a⊕b)⊕b=a⊕(b⊕b)=a
则可利用一个指针域来实现双向链表L链表L中的每个结点只含两个域data域和LRPtr域其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或若设指针LLeft指向链表中的最左结点LRight指向链表中的最右结点则可实现从左向右或从右向左遍历此双向链表的操作试写一算法按任一方向依次输出链表中各元素的值
解
Status TraversingLinkList(XorLinkedList &Lchar d)
{
XorPointer pleftright;
if(d==l||d==L){
p=LLeft;
left=NULL;
while(p!=NULL){
VisitingData(p>data);
left=p;
p=XorP(leftp>LRPtr);
}
}
else
if(d==r||d==R){
p=LRight;
right=NULL;
while(p!=NULL){
VisitingData(p>data);
right=p;
p=XorP(p>LRPtrright);
}
}
else return ERROR;
return OK;
}
设有一个双向循环链表每个结点中除有predata和next三个域外还增设了一个访问频度域freq在链表被起用之前频度域freq的值均初始化为零而每当对链表进行一次Locate(Lx)的操作后被访问的结点（即元素值等于x的结点）中的频度域freq的值便增同时调整链表中结点之间的次序使其按访问频度非递增的次序顺序排列以便始终保持被频繁访问的结点总是靠近表头结点试编写符合上述要求的Locate操作的算法
解
DuLinkList ListLocate_DuL(DuLinkList &LElemType e)
{
DuLinkList pq;
p=L>next;
while(p!=L && p>data!=e)p=p>next;
if(p==L) return NULL;
else{
p>freq++;
// 删除结点
p>pre>next=p>next;
p>next>pre=p>pre;
// 插入到合适的位置
q=L>next;
while(q!=L && q>freq>p>freq) q=q>next;
if(q==L){
p>next=q>next;
q>next=p;
p>pre=q>pre;
q>pre=p;
}
else{
// 在q之前插入
p>next=q>pre>next;
q>pre>next=p;
p>pre=q>pre;
q>pre=p;
}
return p;
}
}
试以循环链表作稀疏多项式的存储结构编写求其导函数的方法要求利用原多项式中的结点空间存放其导函数多项式同时释放所有无用结点
解
Status PolyDifferential(LinkedPoly &L)
{
LinkedPoly pqpt;
q=L;
p=L>next;
while(p!=L){
if(p>dataexp==){
pt=p;
p=p>next;
q>next=p;
free(pt);
}
else{
p>datacoef=p>datacoef*p>dataexp;
p>dataexp;
q=p;
p=p>next;
}
}
return OK;
}
试编写算法将一个用循环链表表示的稀疏多项式分解成两个多项式使这两个多项式中各自仅含奇次项或偶次项并要求利用原链表中的结点空间构成这两个链表
解
// 将单链表L划分成个单循环链表
Status ListDivideIntoCL(LinkedPoly &LLinkedPoly &L)
{
LinkedPoly ppqpt;
q=L;
p=L>next;
p=L;
while(p!=L){
if(p>dataexp%==){
pt=p;
p=p>next;
q>next=p;
pt>next=p>next;
p>next=pt;
p=p>next;
}
else{
q=p;
p=p>next;
}
}
return OK;
}
[] [] []
![数据结构与算法线性表复习习题【6】[3]](/UploadFiles/6.jpg)