数据结构习题集答案（C语言版严蔚敏）(7)

}

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->expexp){ } else

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

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，则可能得到的出站车厢序列是什么？