_______________________________________________________________________________
_______________________________________________________________________________
/* This code can be made more abstract by using operations such as */
/* Retrieve and IsPastEnd to replace L1Pos->Element and L1Pos != NULL. */
/* We have avoided this because these operations were not rigorously defined. */
List
Intersect( List L1, List L2 )
{
List Result;
Position L1Pos, L2Pos, ResultPos;
L1Pos = First( L1 ); L2Pos = First( L2 );
Result = MakeEmpty( NULL );
ResultPos = First( Result );
while( L1Pos != NULL && L2Pos != NULL )
{
if( L1Pos->Element < L2Pos->Element )
L1Pos = Next( L1Pos, L1 );
else if( L1Pos->Element > L2Pos->Element )
L2Pos = Next( L2Pos, L2 );
else
{
Insert( L1Pos->Element, Result, ResultPos );
L1 = Next( L1Pos, L1 ); L2 = Next( L2Pos, L2 );
ResultPos = Next( ResultPos, Result );
}
}
return Result;
}
_______________________________________________________________________________
_______________________________________________________________________________
3.5 Fig. 3.4 contains the code for Union.
O
3.7 (a) One algorithm is to keep the result in a sorted (by exponent) linked list. Each of the MN
O
multiplies requires a search of the linked list for duplicates. Since the size of the linked list
is O
O
(MN
O
), the total running time is O
O
(M
O
2
N
O
2
).
(b) The bound can be improved by multiplying one term by the entire other polynomial, and
then using the equivalent of the procedure in Exercise 3.2 to insert the entire sequence.
Then each sequence takes O
O
(MN
O
), but there are only M
O
of them, giving a time bound of
O
O
(M
O
2
N
O
).
(c) An O
O
(MN
O
log MN
O
) solution is possible by computing all MN
O
pairs and then sorting by
exponent using any algorithm in Chapter 7. It is then easy to merge duplicates afterward.
(d) The choice of algorithm depends on the relative values of M
O
and N
O
. If they are close,
then the solution in part (c) is better. If one polynomial is very small, then the solution in
part (b) is better.
-9-
剩余68页未读，继续阅读
頎祐
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 多功能HTML网站模板：手机电脑适配与前端源码
- echarts实战：构建多组与堆叠条形图可视化模板
- openEuler 22.03 LTS专用openssh rpm包安装指南
- H992响应式前端网页模板源码包
- Golang标准库深度解析与实践方案
- C语言版本gRPC框架支持多语言开发教程
- H397响应式前端网站模板源码下载
- 资产配置方案：优化资源与风险管理的关键计划
- PHP宾馆管理系统（毕设）完整项目源码下载
- 中小企业电子发票应用与管理解决方案
- 多设备自适应网页源码模板下载
- 移动端H5模板源码，自适应响应式网页设计
- 探索轻量级可定制软件框架及其Http服务器特性
- Python网站爬虫代码资源压缩包
- iOS App唯一标识符获取方案的策略与实施
- 百度地图SDK2.7开发的找厕所应用源代码分享
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
