数据结构课程设计——多项式及猴子吃桃问题.doc

课 程 设 计 任 务 书 理 学院 数学0902 班 学生 邓吉利（07720090227） 课程设计课题：第一题： 在顺序结构、动态链表结构下实现一元多项式的加法、减法、乘法运算。 设有一元多项式和请实现求： 要求：1）首先判定多项式是否稀疏； 2）分别采用顺序和动态存储结构实现； 3）结果中无重复阶项、无零系数项； 4）要求输出结果的升幂和降幂两种排列情况。第二题：猴子吃桃问题： 有一群猴子摘了一堆桃子，它们每天都吃当前桃子的一半再多吃一个，到了第10天就剩下一个桃子，用多种方法实现求出原来这群猴子共摘了多少桃子。要求：1）采用数组数据结构实现上述求解； 2）采用链式数据结构。一、课程设计工作日自 2012 年 2 月 21 日至 2012 年 3 月 2 日二、同组学生： 无 。三、课程设计任务要求（包括课题来源、类型、目的和意义、基本要求、完成时间、主要参考资料等）：课题来源：教师提供课题类型：设计目的和意义：通过数据结构课程设计掌握在c语言中结构体的建立和使用，并能用合适的数据结构设计大型程序完成时间：2012年2月29日主要参考资料：1 严蔚敏数据结构（c语言版）清华大学出版社，20072 严蔚敏数据结构题集（c语言版）清华大学出版社，20073 谭浩强c语言程序设计清华大学出版社，20054 与所用编程环境相配套的c语言或c+相关的资料指导教师签字： 教研室主任签字： 2012年2月29日天津职业技术师范大学课 程 设 计 评 审 表 理 学院 数学0902 班 学生 邓吉利 设计任务完成情况及指导教师评语答辩情况评定成绩成绩： 指导教师签字： 日期： 教研室主任： 院长签字： 日期： 日期： 一、设计分析1 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。2 在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。3 程序执行时的命令：选择创建两个一元多项式输入第一个一元多项式的项数依次输入一元多项式的系数和指数以相同方式输入第二个一元多项式选择操作方式选择降幂或升幂排序输出结果是否退出4.测试数据。输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法结果为；升幂 降幂减法结果为：升幂 降幂乘法结果为：升幂 降幂二、具体设计概要1、数据结构的设计 在该程序中分别分为顺序存储和链式存储结构。2、算法的设计本程序主要分为四大模块主程序模块输入模块：通过getpolyn函数输入输出模块（升幂降幂）：printpolyn函数实现输出数据处理模块（多项式的加减乘）：通过一元多项式的polynomial基本操作实现3、抽象数据类型的设计一元多项式抽象数据类型的定义：抽象数据类型polynomial的定义：三、详细程序设计及运行结果：第一题程序及运行结果：#includeusing namespace std;struct termfloat xishu; /系数int zhishu; /指数;struct lnode term data; /term多项式值struct lnode *next;typedef lnode* polynomail;/*合并同类项*/polynomail hebing(polynomail head)polynomail r,q,p,q;for(q=head-next;q!=null;q=q-next)/合并同类项for(p=q-next,r=q;p!=null;)if(q-data.zhishu=p-data.zhishu) q-data.xishu=q-data.xishu+p-data.xishu;r-next=p-next;q=p;p=p-next;delete q;elser=r-next;p=p-next;return head;/*由小到大排列*/void arrange1(polynomail pa)polynomail h=pa,p,q,r;for(p=pa;p-next!=null;p=p-next);r=p;while(h-next!=r)/大的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishup-next-next-data.zhishu)q=p-next-next;p-next-next=q-next;q-next=p-next;p-next=q;r=p;/r指向参与比较的最后一个，不断向前移动 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r;for(p=pa;p-next!=null;p=p-next); r=p;while(h-next!=r)/小的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishunext-next-data.zhishu) q=p-next-next;p-next-next=q-next;q-next=p-next;p-next=q;r=p;/r指向参与比较的最后一个，不断向前移动 bool judge(polynomail head)arrange2(head);polynomail p;p=head-next;bool xi=false;while(p!=null&p-next!=null&!xi)if(p-data.zhishu-p-next-data.zhishu1)xi=true;p=p-next;return xi;/*打印多项式,求项数*/void printpolyn(polynomail p)int i;polynomail q;if(p=null)coutnext=null)couty=0n;elsecoutnext;i=1;if(q-data.xishu!=0&q-data.zhishu!=0)coutdata.xishuxdata.zhishu;i+; if(q-data.zhishu=0&q-data.xishu!=0)coutdata.xishu;/打印第一项q=q-next;if(q=null)coutdata.xishu!=0&q-data.zhishu!=0)if(q-data.xishu0) cout+;coutdata.xishuxdata.zhishu;i+;if(q-data.zhishu=0&q-data.xishu!=0) if(q-data.xishu0) cout+;coutdata.xishu;q=q-next;if(q=null)coutn;break; /*1、创建并初始化多项式链表*/polynomail creatpolyn(int m)polynomail head,r,s;int i;head=new lnode;r=head;for(i=0;im;i+) s=new lnode;cout请输入第i+1s-data.xishus-data.zhishu;r-next=s; r=s;r-next=null;if(m1)head=hebing(head);return head;/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb)polynomail s,newhead,q,p,r;int j;p=pa-next;q=pb-next;newhead=new lnode;r=newhead;while(p) s=new lnode;s-data.xishu=p-data.xishu;s-data.zhishu=p-data.zhishu;r-next=s; r=s;p=p-next;while(q) s=new lnode;s-data.xishu=q-data.xishu;s-data.zhishu=q-data.zhishu;r-next=s; r=s;q=q-next;r-next=null;if(newhead-next!=null&newhead-next-next!=null)/合并同类项newhead=hebing(newhead);cout升序 1 , 降序 2n;coutj;if(j=1) arrange1(newhead);else arrange2(newhead);return newhead;/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb)polynomail s,newhead,q,p,r; int j;p=pa-next;q=pb-next;newhead=new lnode;r=newhead;while(p)s=new lnode;s-data.xishu=p-data.xishu;s-data.zhishu=p-data.zhishu;r-next=s; r=s;p=p-next;while(q)s=new lnode;s-data.xishu=-q-data.xishu;s-data.zhishu=q-data.zhishu;r-next=s; r=s; q=q-next;r-next=null; if(newhead-next!=null&newhead-next-next!=null)/合并同类项newhead=hebing(newhead);cout升序 1 , 降序 2n;coutj;if(j=1) arrange1(newhead); elsearrange2(newhead);return newhead;/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newhead,q,p,r; int j;newhead=new lnode;r=newhead;for(p=pa-next;p!=null;p=p-next)for(q=pb-next;q!=null;q=q-next)s=new lnode;s-data.xishu=p-data.xishu*q-data.xishu;s-data.zhishu=p-data.zhishu+q-data.zhishu;r-next=s;r=s;r-next=null;cout升序 1 , 降序 2n;coutj;if(j=1) arrange1(newhead);else arrange2(newhead);if(newhead-next!=null&newhead-next-next!=null)/合并同类项newhead=hebing(newhead);return newhead;/*5、销毁已建立的两个多项式*/void delpolyn(polynomail pa,polynomail pb)polynomail p,q;p=pa;while(p!=null) q=p;p=p-next;free(q);p=pb;while(p!=null) q=p;p=p-next;free(q);cout两个多项式已经销毁n;void main() polynomail pa=null,pb=null;polynomail addp=null,subp=null,mulp=null;int n,m;while(1)cout1、创建两个一元多项式n;cout2、两多项式相加得一新多项式n;cout3、两多项式相减得一新多项式n;cout4、两多项式相乘得一新多项式n;cout5、销毁已建立的两个多项式n;cout6、退出n;coutn;switch(n)case 1:if(pa!=null) cout已建立两个一元多项式，请选择其他操作！;break;cout请输入第一个多项式：n;coutm;while(m=0) coutm;pa=creatpolyn(m);printpolyn(pa);if(judge(pa)cout该多项式稀疏n;elsecout该多项式稠密n;cout请输入第二个多项式：n;coutm;pb=creatpolyn(m);printpolyn(pb);if(judge(pb)cout该多项式稀疏n;elsecout该多项式稠密n;break;case 2:if(pa=null) cout请先创建两个一元多项式！n;break;addp=addpolyn(pa,pb);printpolyn(addp);break;case 3:if(pa=null)cout请先创建两个一元多项式！n;break;subp=subpolyn(pa,pb);printpolyn(subp);break;case 4:if(pa=null)cout请先创建两个一元多项式！n;break; mulp=mulpolyn(pa,pb);printpolyn(mulp);break;case 5: if(pa=null)cout请先创建两个一元多项式！n;break;delpolyn(pa,pb);pa=pb=null;break;case 6:delpolyn(pa,pb);exit(0);s第二题程序及运行结果：public class monkey /主函数public static void main(string args) list l = new list();l.array();l.link();/构成链表的结点定义public class node public node next;public object data;public node(object data, node next) this.data = data;this.next = next;public class list private node head = null;private node tail = null;private node pointer = null;private int length = 0;/在当前结点前插入一个结点，并使其成为当前结点public void insert(object d) node e = new node(d, null);if(length = 0) tail = e;head = e; else node temp = cursor();e.next = temp;if(pointer = null)head = e;elsepointer.next = e;length +;/将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点public object remove() object temp;if(length = 0)return 0;else if(length = 1) temp = head.data;deleteall();else node cur = cursor();temp = cur.data;if(cur = head)head = cur.next;else if(cur = tail) pointer.next = null;tail = pointer;reset();elsepointer.next = cur.next;length -;return temp;/返回当前结点的指针private node cursor() if(head = null)return null;else if(pointer = null)return head;elsereturn pointer.next;/返回当前结点的值public object currentnode() node temp = cursor();return temp.data;public void deleteall() head = null;tail = null;pointer = null;length = 0;public void reset() pointer = null;/链表实现public void link() int s = 0;list a=new list ();for(int i=1;i=0; i-) ai = 2 * ai+1 +2;system.out.println(数组实现：);system.out.println(桃子总数: + a0);system.out.println(*);1)package com.zw.tute.list;public class monkey public static void main(string args) list l = new list();l.array();l.link();2)package com.zw.tute.list;/构成链表的结点定义public class node public node next;public object data;public node(object data, node next) this.data = data;this.next = next;/具体方法实现要求3)package com.zw.tute.list;public class list private node head = null;private node tail = null;private node pointer = null;private int length = 0;/在当前结点前插入一个结点，并使其成为当前结点public void insert(object d) node e = new node(d, null);if(length = 0) tail = e;head = e; else node temp = cursor();e.next = temp;if(pointer = null)head = e;elsepointer