}
在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 设以带头结点的双向循环链表表示的线性表L??a1,a2,?,an?。试写一时间复杂度O(n)的算法，将L改造为L??a1,a3,?,an,?,a4,a2?。
解：
// 将双向链表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 已知稀疏多项式
Pn?x??c1xe1?c2xe2???cmxem，其中
n?em?em?1???e1?0，ci?0?i?1,2,?,m?，m?1。试采用存储量同多项式项
数m成正比的顺序存储结构，编写求Pn?x0?的算法（x0为给定值），并分析你的
精选
算法的时间复杂度。
解：
typedef struct{ int coef; int exp; } PolyTerm;
typedef struct{ PolyTerm *data; int last; } SqPoly;
// 建立一个多项式
Status PolyInit(SqPoly &L) {
int i;
PolyTerm *p;
cout<<\请输入多项式的项数:\ cin>>L.last;
L.data=(PolyTerm *)malloc(L.last*sizeof(PolyTerm)); if(!L.data) return ERROR; p=L.data;
for(i=0;i
cout<<\请输入指数:\ cin>>p->exp; p++; }
return OK; }
// 求多项式的值
double PolySum(SqPoly &L,double x0) {
double Pn,x; int i,j;
PolyTerm *p; p=L.data;
for(i=0,Pn=0;i for(j=0,x=1;j return Pn; } 2.40 采用2.39题给定的条件和存储结构，编写求P?x??Pn1?x??Pn2?x?的算法， 精选 将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。 解： // 求两多项式的差 Status PolyMinus(SqPoly &L,SqPoly &L1,SqPoly &L2) { PolyTerm *p,*p1,*p2; p=L.data; p1=L1.data; p2=L2.data; int i=0,j=0,k=0; while(i if(p1->exp>p2->exp){ p->coef=-p2->coef; p->exp=p2->exp; p++; k++; p2++; j++; } else{ if(p1->coef!=p2->coef){ p->coef=(p1->coef)-(p2->coef); p->exp=p1->exp; p++; k++; } p1++; p2++; i++; j++; } } if(i while(i if(j while(j p->coef=-p2->coef; 精选