}
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){ } else{
// 在q之前插入
p->next=q->pre->next; q->pre->next=p; p->pre=q->pre; p->next=q->next; q->next=p; p->pre=q->pre; q->pre=p;
}
return OK;
}
else p=p->next; i++;
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;
}
在2.39至2.40题中，稀疏多项式采用的顺序存储结构SqPoly定义为 typedef struct {
int coef; int exp;
//多项式的顺序存储结构
}
} return p;
q->pre=p;
} PolyTerm; typedef struct {
int last;
PolyTerm *data;
} 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->coef; cout<<\请输入指数:\cin>>p->exp; } // 求多项式的值 double PolySum(SqPoly &L,double x0) { } 2.40 采用2.39题给定的条件和存储结构，编写求P在新辟的空间中，并分析你的算法的时间复杂度。 解： // 求两多项式的差 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 if(p1->exp>p2->exp){ } else{ p->coef=-p2->coef; p->exp=p2->exp; p++; p2++; j++; k++; p->coef=p1->coef; p->exp=p1->exp; p++; p1++; k++; i++; double Pn,x; int i,j; PolyTerm *p; p=L.data; for(i=0,Pn=0;i return Pn; for(j=0,x=1;j return OK; p++; ?x??Pn1?x??Pn2?x?的算法，将结果多项式存放 } 在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为 typedef struct PolyNode { PolyTerm data; struct PolyNode *next; } if(i while(i while(j p->coef=-p2->coef; p->exp=p2->exp; p++; p2++; j++; k++; p->coef=p1->coef; p->exp=p1->exp; p++; p1++; i++; k++; } if(p1->coef!=p2->coef){ } p1++; i++; p2++; j++; p->coef=(p1->coef)-(p2->coef); p->exp=p1->exp; p++; k++; if(j L.last=k; return OK; } PolyNode, *PolyLink; typedef PolyLink LinkedPoly; 2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。 解： Status PolyDifferential(LinkedPoly &L) { LinkedPoly p,q,pt; q=L; p=L->next; while(p!=L){ if(p->data.exp==0){ pt=p; p=p->next; } 2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。 解： // 将单链表L划分成2个单循环链表 Status ListDivideInto2CL(LinkedPoly &L,LinkedPoly &L1) { } LinkedPoly p,p1,q,pt; q=L; p=L->next; p1=L1; while(p!=L){ } return OK; if(p->data.exp%2==0){ } else{ } q=p; p=p->next; pt=p; p=p->next; q->next=p; pt->next=p1->next; p1->next=pt; p1=p1->next; } return OK; } else{ } p->data.coef=p->data.coef*p->data.exp; p->data.exp--; q=p; p=p->next; q->next=p; free(pt); 第3章 栈和队列 3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： (1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？