else{ q=p;
p=p->next;
q->next=pt3->next; pt3->next=q; pt3=pt3->next; } } q=L; free(q); return OK; }
在2.34至2.36题中
\异或指针双向链表\类型XorLinkedList和指针异或函数XorP定义为： typedef struct XorNode { char data;
struct XorNode *LRPtr; } XorNode *XorPointer;
typede struct { //无头结点的异或指针双向链表 XorPointer Left
Right; //分别指向链表的左侧和右端 } XorLinkedList;
XorPointer XorP(XorPointer p XorPointer q);
// 指针异或函数XorP返回指针p和q的异或值 2.34 假设在算法描述语言中引入指针的二元运算\异或\若a和b为指针
则a⊕b的运算结果仍为原指针类型 且
a⊕(a⊕b)=(a⊕a)⊕b=b (a⊕b)⊕b=a⊕(b⊕b)=a
则可利用一个指针域来实现双向链表L
链表L中的每个结点只含两个域：data域和LRPtr域
其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或 若设指针L.Left指向链表中的最左结点 L.Right指向链表中的最右结点
则可实现从左向右或从右向左遍历此双向链表的操作 试写一算法按任一方向依次输出链表中各元素的值
解：
Status TraversingLinkList(XorLinkedList &L char d) {
XorPointer p left right;
if(d=='l'||d=='L'){ p=L.Left; left=NULL;
while(p!=NULL){
VisitingData(p->data); left=p; p=XorP(left p->LRPtr); } } else
if(d=='r'||d=='R'){ p=L.Right; right=NULL; while(p!=NULL){
VisitingData(p->data); right=p;
p=XorP(p->LRPtr right);
} }
else return ERROR; return OK; }
2.35 采用2.34题所述的存储结构
写出在第i个结点之前插入一个结点的算法
2.36 采用2.34题所述的存储结构 写出删除第i个结点的算法
2.37 设以带头结点的双向循环链表表示的线性表 试写一时间复杂度O(n)的算法 将L改造为
解：
// 将双向链表L=(a1 a2 ...
an)改造为(a1 a3 ...
an ... a2)
Status ListChange_DuL(DuLinkList &L) {
int i;
DuLinkList p q r;
p=L->next; r=L->pre; i=1;
while(p!=r){ if(i%2==0){ q=p;
p=p->next; // 删除结点
q->pre->next=q->next; q->next->pre=q->pre; // 插入到头结点的左面 q->pre=r->next->pre; r->next->pre=q; q->next=r->next; r->next=q; }
else p=p->next; i++; }
return OK; }
2.38 设有一个双向循环链表 每个结点中除有pre data和next三个域外
还增设了一个访问频度域freq 在链表被起用之前
频度域freq的值均初始化为零 而每当对链表进行一次Locate(L x)的操作后
被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1 同时调整链表中结点之间的次序
使其按访问频度非递增的次序顺序排列
以便始终保持被频繁访问的结点总是靠近表头结点 试编写符合上述要求的Locate操作的算法
解：
DuLinkList ListLocate_DuL(DuLinkList &L ElemType e) {
DuLinkList p q;
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; } }
在2.39至2.40题中
稀疏多项式采用的顺序存储结构SqPoly定义为 typedef struct { int coef; int exp; } PolyTerm;
typedef struct { //多项式的顺序存储结构 PolyTerm *data; int last; } SqPoly;
2.39 已知稀疏多项式