内容发布更新时间 : 2024/11/20 11:28:59星期一 下面是文章的全部内容请认真阅读。
}
}
}
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)满竊萝锶檩緱还。 { }
在2、39至2、40题中，稀疏多项式采用得顺序存储结构SqPoly定义为 typedef struct {
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;
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) { }
// 求多项式得值
double PolySum(SqPoly &L,double x0) {
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++; } 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 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 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++; } } } if(i while(i while(j p->coef=-p2->coef; p->exp=p2->exp; p++; p2++; k++; j++; p->coef=p1->coef; p->exp=p1->exp; p++; p1++; k++; i++; if(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; pt=p; p=p->next; q->next=p; free(pt); } } } p=p->next; 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 简述栈与线性表得差别。 解：线性表就是具有相同特性得数据元素得一个有限序列。栈就是限定仅在表尾进行插入或删除操作