}

在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>p->coef;

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;jexp;j++) x=x*x0; Pn=Pn+p->coef*x; }

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(iexpexp){ p->coef=p1->coef; p->exp=p1->exp; p++; k++; p1++; i++; } else

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(icoef=p1->coef; p->exp=p1->exp; p++; k++; p1++; i++; }

if(j

while(j

p->coef=-p2->coef;

精选