




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第二章线性表线性表的概念及抽象数据类型顺序表单链表循环链表双向链表应用与比较本章目标基于空间的考虑顺序表的存储空间是静态分配的,在程序执行之前必须明确规定它的存储规模。动态链表的存储空间是动态分配的,只要内存空间尚有空闲,就不会产生溢出。 当线性表的长度变化较大,难以估计存储规模时,采用动态链表作为存储结构较好顺序表和链表的比较基于时间的考虑顺序表可以随机存取,对表中任一结点都可以在O(1)时间内直接存取;链表中的结点需从头指针起开始顺着链找才能取得。 若线性表的操作主要是进行查找,很少做插入和删除时,宜采用顺序表存储结构顺序表进行插入、删除时,平均要移动表中近一半的元素;而链表只需要修改指针。 需要频繁进行插入、删除操作的线性表,宜采用链表存储结构。顺序表和链表的比较基于语言的考虑顺序表易于操作顺序表和链表的比较线性表链式存储方式的比较操作名链表名称找表头结点找表尾结点找P结点前驱结点带头结点单链表LL->nextO(1)一重循环O(n)顺P结点的next域无法找到P结点的前驱带头结点循环单链表LL->nextO(1)一重循环O(n)顺P结点的next域可以找到P结点的前驱:O(n)带尾指针的循环单链表RR->nextO(1)RO(1)顺P结点的next域可以找到P结点的前驱:O(n)带头结点双向循环链表LL->nextO(1)L->priorO(1)P->priorO(1)一元多项式可按升幂的形式写成:
Pn(x)=p0+p1xe1+p2xe2+…+pnxen,其中ei为第i项的指数(且1≤e1≤e2≤…≤en)pi是指数ei的项的系数一元多项式的表示及相加一元多项式的顺序存储表示(两种方法)一元多项式的链式存储表示一元多项式的存储一元多项式的顺序存储表示—方法1只存储该一元多项式各项的系数,每个系数所对应的指数项则隐含在存储系数的顺序表的下标中。如:B(x)=8x+22x7-9x8一元多项式的存储值080000022-9下标012345678一元多项式的顺序存储表示—方法1采用这种存储方法使得多项式的相加运算的算法定义十分简单,只需将下标相同的单元的内容相加即可。缺点:若多项式的非零项指数很高但非零项很少时,十分浪费存储空间,如:
R(x)=1+5x10000+7x20000一元多项式的存储一元多项式的顺序存储表示—方法2只存储非零项,此时每个非零项需要存储:非零项系数非零项指数如:B(x)=8x+22x7-9x8
一元多项式的存储
值系数822-9指数178下标012一元多项式的链式存储表示只存非零项,每一非零项由两部分构成(指数项和系数项)一元多项式的存储系数coef
指数exp指针next一元多项式的链式存储表示一元多项式的单链表表示示意图一元多项式的存储
A(x)=7+3x+9x8+5x17-17031517∧9881-1227-98∧
B(x)=8x+22x7-9x8
建立一元多项式链式存储的算法算法思想通过键盘输入一组多项式的系数和指数,用尾插法建立一元多项式的链表;以输入系数0为结束标志;并约定建立多项式链表时,总是按指数从小到大的顺序排列。一元多项式的存储两个一元多项式相加运算规则:两个多项式中所有指数相同的项的对应系数相加,若和不为零,则构成“和多项式”中的一项;所有指数不相同的项均复抄到“和多项式”中。一元多项式的存储-17031517∧9881-1227-98∧
polyapolyb-170111517∧227两个一元多项式相加一元多项式的存储-17031517∧9881-1227-98∧
polyapolybpqtail两个一元多项式相加若p->exp<q->exp,则结点p所指的结点应是“和多项式”中的一项,令指针p后移;若p->exp>q->exp,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移;若p->exp==q->exp,则将两个结点中的系数相加,当和不为零时修改结点p的系数域,释放q结点;若和为零,则和多项式中无此项,从A中删去p结点,同时释放p和q结点。一元多项式的存储两个一元多项式相加一元多项式的存储-17031517∧9881-1227-98∧
polyapolybpqtail两个一元多项式相加一元多项式的存储-17031517∧98-1227-98∧
81polyapolybpqtail11temp两个一元多项式相加一元多项式的存储-170111517∧98-1227-98∧
polyapolybpqtailtail两个一元多项式相加一元多项式的存储-170111517∧98-1227-98∧
polyapolybpqtailtemptemp两个一元多项式相加一元多项式的存储-170111517∧-1227polyapolybpqtail多项式深度拷贝及应用比较两个多项式是否相等//比较两个多项式是否相等publicboolean
equals(Object
obj){ returnthis==obj||obj
instanceofPolynomia
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 停课后少先队活动方案
- 健康促进登山活动方案
- 健康夜市活动方案
- 健康扶贫体检活动方案
- 健康步行活动方案
- 健康生活五进活动方案
- 健康跑活动策划方案
- 健康集体活动方案
- 健身会员抽奖活动方案
- 健身大促销活动方案
- 哈尔滨市第九中学校2024-2025学年高二下学期期中地理试卷
- 淮安监理员试题及答案
- 机电工程2025年技术经济学试题及答案
- 2025年粮食仓储行业调研分析报告
- 2025年“巴渝工匠”杯职业技能竞赛(调饮师赛项)备赛试题库(含答案)
- 2025辽宁沈阳副食集团所属企业招聘25人笔试参考题库附带答案详解
- 2024-2025新入员工安全培训考试试题及参考答案(达标题)
- 2025陕西中考:历史必背知识点
- 《电力设施保护》课件
- 《人工智能应用基础》 完整课件(共十个模块-上)
- 国企财务测试题及答案
评论
0/150
提交评论