}
}
return OK;
2.38 设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。
解：
DuLinkList ListLocate_DuL(DuLinkList &L,ElemType e) { }
在2.39至2.40题中，稀疏多项式采用的顺序存储结构SqPoly定义为 typedef struct {
int coef; int exp; DuLinkList p,q; p=L->next;
while(p!=L && p->data!=e) 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{ }
return p;
// 在q之前插入 p->next=q->pre->next; q->pre->next=p; p->pre=q->pre; q->pre=p; p->next=q->next; q->next=p; p->pre=q->pre; q->pre=p;
p=p->next;
} 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) { }
// 求多项式的值
double PolySum(SqPoly &L,double x0) {
double Pn,x; int i,j; PolyTerm *p; 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 return OK; cout<<\请输入系数:\cin>>p->coef; cout<<\请输入指数:\cin>>p->exp; p++; } p=L.data; for(i=0,Pn=0;i return Pn; for(j=0,x=1;j 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(i if(p1->exp if(p1->exp>p2->exp){ } else{ } if(p1->coef!=p2->coef){ } p1++; i++; p2++; j++; p->coef=(p1->coef)-(p2->coef); p->exp=p1->exp; p++; k++; p->coef=-p2->coef; p->exp=p2->exp; p++; p2++; k++; j++; p->coef=p1->coef; p->exp=p1->exp; p++; k++; p1++; i++; } while(i p->coef=p1->coef; p->exp=p1->exp; p++; p1++; k++; i++; if(j while(j p->coef=-p2->coef; p->exp=p2->exp; p++; p2++; k++; j++; L.last=k; return OK; 在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为 typedef struct PolyNode { PolyTerm data; struct PolyNode *next; } 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){ } else{ } p->data.coef=p->data.coef*p->data.exp; p->data.exp--; q=p; p=p->next; pt=p; p=p->next; q->next=p; free(pt); } return OK; 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; 第3章 栈和队列 3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： (1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ (2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列）。 解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。 3.2 简述栈和线性表的差别。 解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。 3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。 void main() 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构及应用算法 课后复习题（附答案 严蔚敏版）(7)在线全文阅读。
相关推荐：