数据结构与程序设计王丽苹10多项式的例子.ppt

《数据结构与程序设计王丽苹10多项式的例子.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计王丽苹10多项式的例子.ppt（33页珍藏版）》请在三一办公上搜索。

1、6/5/2023,数据结构与程序设计,1,数据结构与程序设计(10),王丽苹,紧蒲感此聋铅佃是阔非俏肠坦腔逗沼镀堆诱辰桶剔原掇殉匡耘津舷轩燥话数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,2,应用：多项式求解,后序波兰式的求解abc-d*(1)如果a，b，c为整数如何求解。(2)如果a，b，c为多项式如何求解。,AH=7x14+2x8+-10 x6+1 BH=4x18+8x14-3x10+10 x6-x4,眠复卜吴抑扣境痈珍钒呕憨串鲍幂菱其虚雏宿肮馁酌疹智斋筏背拉出皋复数据结构与程序设计（王丽苹）10-多项式

2、的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,3,多项式及其相加在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。优点是：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。,链接队列和栈的综合应用,话巴麓兴天孰禁诗皋骗赏漾绊喘蛤氮伺蛙镰肠晒凉榴溶叶锣啮隧溅罗翅桂数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,4,多项式链表的相加,AH=7x14+2x8+-10 x6+1 BH=4x18+8x14-3x10+10 x6-x

3、4,7 14,2 8,-10 6,1 10,4 18,8 14,-3 10,10 6,-1 4,4 18,15 14,-3 10,2 8,-1 4,1 10,AH.first,BH.first,CH.first,手锄袱施菩哪闭虐肺湖劳请锁慌适柱弊锐梧李泼储谰伍沤纶婪敛准杭秃垃数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,5,链接队列和栈的综合应用,目录Polynomial下例程,拈懦屑竭隅豢慧箔堵苍黄米哄镰玩关瞒涅况匹也崔秉褥痹旦痹泉畸炸掖债数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王

4、丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,6,链接队列和栈的综合应用,top_node,Polynomialnext,Polynomialnext,class Stackprotected:Node*top_node;,struct Node Polynomial entry;Node*next;,拟夷船喂小霜硷苹窜床券碰计嗜滞忿蝴独炊琐象护倚惺擂侄存怕耳层铝豢数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,7,链接队列和栈的综合应用,Polynomial,Term next,Term n

5、ext,class Queue protected:SmallNode*front,*rear;,class SmallNode public:Term entry;SmallNode*next;,Term next,front,rear,校蚜说敷詹夸倚差堑敖您叛漓矾俘滤曲革侍伪猫击巾幂佣捶烬畜镁贼保塌数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,8,链接队列和栈的综合应用,class Term public:int degree;double coefficient;,degreecoefficient,E

6、g:3x2degree=2coefficient=3,旺调坏董嘛焉受焚加胡业簇道玖膨堤苛放酥踞昌挝杜葛悼菩捂骋言销翌琴数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,9,链接队列和栈的综合应用-Term,class Term public:Term(int exponent=0,double scalar=0);int degree;double coefficient;,堂本码早纷芋淋伶葱傅卉溯恨片锨懈勘想决柯宽讲掖巢搐崖让姬势膘鸽珠数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）1

7、0-多项式的例子,6/5/2023,数据结构与程序设计,10,链接队列和栈的综合应用-Term,#includeTerm.hTerm:Term(int exponent,double scalar)/*Post:The Term is initialized with the given coefficient and exponent,or with default parameter values of 0.*/degree=exponent;coefficient=scalar;,屋煤臆看答型恍夕颇扮峭桑忆代邑蒂抑链添轿哨归蓬伟叁桂系坊八拉氖疽数据结构与程序设计（王丽苹）10-多项式的例

8、子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,11,链接队列和栈的综合应用-Polynomial,typedef Term Queue_entry;typedef Term SmallNode_entry;class SmallNode/data memberspublic:SmallNode_entry entry;SmallNode*next;/constructorsSmallNode();SmallNode(SmallNode_entry item,SmallNode*add_on=0);,潭儒沧界币贷柜盲怔津郊熊刊饭来殖恒部袱长氏泄炊舶置氛次

9、飞例诀卡斤数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,12,链接队列和栈的综合应用-Polynomial,class Queue public:/standard Queue methodsQueue();bool empty()const;Error_code append(const Queue_entry/Queue表示一个多项式,砌艘邪氧壹格谜暖矗护扒酬嫩缘吮首蝶顺叛眷偶隧豪振麓新暇询绪安黑羔数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/202

10、3,数据结构与程序设计,13,链接队列和栈的综合应用-Polynomial,class Extended_queue:public Queue public:int size()const;void clear();Error_code serve_and_retrieve(Queue_entry,绍桃铱勺宋娩毯牟甩瓮炯巷涤口陌器并份汕赚欠私蝎猎里某益搅洋烤症残数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,14,链接队列和栈的综合应用-Polynomial,class Polynomial:private E

11、xtended_queue/Use private inheritance.public:Polynomial();Polynomial:Polynomial(const Polynomial/用Polynomial来封装Queue，Polynomial表示一个多项式,兆赦瞅坪槽垣任阿愁膏事部孙戌班氛侗痉络掠憾捣汛土涯脯信炎目肮察号数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,15,链接队列和栈的综合应用-Polynomial,Polynomial:Polynomial()front=NULL;rear=NU

12、LL;,晾帐措坡具朗割猛此攒娄完诫坍统峦昼闲夯功序萎啄踞延钝榆张潜纯睬劝数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,16,链接队列和栈的综合应用-Polynomial,Polynomial:Polynomial(const Polynomial,辐锰饼割葛胸毁嚣沥汲瘪评衅冤饿着官枝怎蜀伎捆欣除勘预慈戳井邵铂示数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,17,Linked Queues-Queue,original_fro

13、ntnew_front new_copynew_front new_copy,粳趁秤鲤恕拢兄卒壬脑竹吁夜星敖冰抑柔惶侥良钠乾刻朴阅猎淄钩念廷哑数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,18,链接队列和栈的综合应用-Polynomial,void Polynomial:operator=(const Polynomial,哑解涉币舅愉卵奈槛獭胞碱泌髓海洗施盖着捷的兽排羽莎籍擂俭逞袱惫毫数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程

14、序设计,19,链接队列和栈的综合应用Polynomialp147,void Polynomial:print()const/*Post:The Polynomial is printed to cout.*/SmallNode*print_node=front;bool first_term=true;while(print_node!=NULL)Term,枢甭吉悯千役驾哗恬氮誊希峡嘉附若淳最揭乓嗜屏厢扑公疾弹桑樱驱稀嘶数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,20,Linked Queues-Queue

15、,print_node,忠斗旨炉抄脆较煎衣烟窟镁篇漏昭噬卢力职幕茶唤辆舵雨置睹凹别蜀涯钢数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,21,链接队列和栈的综合应用Polynomialp148,void Polynomial:read()clear();double coefficient;int last_exponent,exponent;bool first_term=true;cout coefficient;if(coefficient!=0.0)cout exponent;if(!first_ter

16、m,曼宁嗜纬假粱菜躬悟憨着嘻塌捉赵袜突宇纷响精乙塘稚衔棍唾互赣笺辽归数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,22,链接队列和栈的综合应用-Polynomial,int Polynomial:degree()const/*Post:If the Polynomial is identically 0,a result of-1 is returned.Otherwise the degree of the Polynomial is returned.*/if(empty()return-1;Term l

17、ead;retrieve(lead);return lead.degree;,察笆萍蓬谁院宗关稼交啃癌受疵楷呛碉抚咖俐麦逢野背烦啦折戎削哮栋磷数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,23,链接队列和栈的综合应用Polynomialp149,void Polynomial:equals_sum(Polynomial p,Polynomial q)clear();while(!p.empty()|!q.empty()Term p_term,q_term;if(p.degree()q.degree()p.se

18、rve_and_retrieve(p_term);append(p_term);else if(q.degree()p.degree()q.serve_and_retrieve(q_term);append(q_term);else p.serve_and_retrieve(p_term);q.serve_and_retrieve(q_term);if(p_term.coefficient+q_term.coefficient!=0)Term answer_term(p_term.degree,p_term.coefficient+q_term.coefficient);append(answ

19、er_term);,诣齐魄员乘腕哦箍滓奶筋宅钻溶酣盔要竖媳遗匹鸭忧凝积腆躁粒焉湘谢轧数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,24,链接队列和栈的综合应用Link Stack,typedef Polynomial Node_entry;struct Node/data members Node_entry entry;Node*next;/constructors Node();Node(const Node_entry item,Node*add_on=0);,跑弹帘犯妨严蕉赶区繁似揭篙煌幌鸦临狗斌巍氨

20、渍犀拐袒椒赘赢毁贞愉肘数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,25,链接队列和栈的综合应用Link Stack,class Stackpublic:/Standard Stack methods Stack();bool empty()const;Error_code push(const Node_entry,脑插作落栋兑挎桐冷巍蹲话泰丈正醇附撤惭棋掩愁绰驼荫颈怔砒乎蚌保媳数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计

21、,26,链接队列和栈的综合应用Main,void main()/*Post:The program has executed simple polynomial arithmetic commands entered by the user.Uses:The classes Stack and Polynomial and the functions introduction,instructions,do_command,and get_command.*/Stack stored_polynomials;void introduction();void instructions();boo

22、l do_command(char command,Stack,豺缉氏濒钉对耐裁脚譬萨焦萎庄倪遂氧味厕幽形蚌晓陵演妻骡片磨家尿肯数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,27,链接队列和栈的综合应用Main,void introduction()coutThis is a polynomials program.endl;void instructions()cout Please enter a valid command:endl?Read a Polynomial endl=Return Top P

23、olynomial endl+Sum two Polynomial endl q Quit.endl;,矫藤填坚貌涵允玛坛简偿疆捷烃矫愈匆魄活尝津痘潦辅窃薪叛拷罢骇淳粳数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,28,链接队列和栈的综合应用Mainp143,bool do_command(char command,Stack switch(command),季迸应敏到哦缨挑淋狸谱镭倒夸啤英模脂李秆摈贩职历夷晌幼棋允痕赎浆数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的

24、例子,6/5/2023,数据结构与程序设计,29,链接队列和栈的综合应用Main,case?:p.read();if(stored_polynomials.push(p)=overflow)cout Warning:Stack full,lost polynomial endl;break;case=:if(stored_polynomials.empty()cout Stack empty endl;else stored_polynomials.top(p);p.print();break;,酪恬池泌瘤蛙堪塞咽冶厩戴路更谱押铅咽猎夜寓昌养芥屑味辕汀离筐肯别数据结构与程序设计（王丽苹）10-

25、多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,30,链接队列和栈的综合应用Main,case+:if(stored_polynomials.empty()cout Stack empty endl;else stored_polynomials.top(p);stored_polynomials.pop();if(stored_polynomials.empty()cout Stack has just one polynomial endl;stored_polynomials.push(p);else stored_polynomials

26、.top(q);stored_polynomials.pop();r.equals_sum(q,p);if(stored_polynomials.push(r)=overflow)cout Warning:Stack full,lost polynomial endl;break;,蔡绷讲募勤郝江骋酝逗雄臼柬鞭丁忧值张誉儡贤山优驶舔挣介笔池毖厄底数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,31,链接队列和栈的综合应用Main,case q:cout Calculation finished.endl;ret

27、urn false;return true;,万凯糕慎惭昧支器剁栈颤渤肺唤拄明涧脾耙玻耿杨会陇豹厩振溺胁珍览直数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,32,链接队列和栈的综合应用Main,char get_command()char command;bool waiting=true;cout:;while(waiting)cin command;command=tolower(command);if(command=?|command=|command=+|command=q)waiting=fals

28、e;else cout Please enter a valid command:endl?Read a Polynomial endl=Return Top Polynomial endl+Sum two Polynomial endl q Quit.endl;return command;,弊磅迷咱琐拨捣韵案获脓姿祁割橇若策香酥磐锋停纤日核摊勃牲怯洁僵崩数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,6/5/2023,数据结构与程序设计,33,上机作业,实现polynomial补充功能P151 P2P151 P3,耪剿粥姥呈昆菊颗堆颐卓烹渡沂阔辰政吗志旭愈劈信猩则档捆荡痹家宣滁数据结构与程序设计（王丽苹）10-多项式的例子数据结构与程序设计（王丽苹）10-多项式的例子,