一元稀疏多项式简单计算器.doc

浏水浮芸QQ632069015数据结构课程设计报告一元稀疏多项式计算器、迷宫问题、成绩分析问题、图的基本操作与实现以及背包问题的求解 学院（系）： 计算机 班 级： 软件工程 4班 学生姓名： 江志伟 学号 10803080409 指导教师： 时间： 从 2010年 01 月 11日到 2010 年01 月 15 日一、课程设计概述：本次数据结构课程设计共完成五个题：一元稀疏多项式计算器、迷宫问题、成绩分析问题、图的基本操作与实现以及背包问题的求解使用语言：C编译环境：TC3.0二、课程设计题目一实验内容 一元稀疏多项式计算器问题描述设计一个一元稀疏多项式简单计算器。基本要求一元稀疏多项式简单计算器的基本功能是：（1） 输入并建立多项式；（2） 输出多项式，输出形式为整数序列：n,c1,e1, c2,e2, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；（3） 多项式a和b相加，建立多项式a+b；（4） 多项式a和b相减，建立多项式a-b；（5） 计算多项式在x处的值。（6） 计算器的仿真界面。（选做） 概要设计-=ADT=- Test1:主类，程序的启动 Item :项，表示多项式中的某一项 Ploynomial：多项式类 存储结构 Item属性：private double c;/系数private int e;/指数Item方法： public void setC(double c)/设置系数public void setE(int e) /设置指数public double getC()/获取系数public int getE()/获取指数public double resultItem(double x)/在x处 Item的值private double fac(double x,int e)/求x的e次方,当e为整数时Polynomial属性： private LinList list;/单链表Polynomial方法： public Polynomial() public Polynomial(Item item)throws Exception /构造函数 private void initItem(Item item)/初始化Item数组，使其是按降序排序 public int getItemNum()/获取项数 public void print()throws Exception/打印多项式 不空行 public void println()throws Exception/打印多项式 空行 public LinList getLinList()/获取单链表 public void printPolynomial()throws Exception/只打印项数、系数和指数 public Polynomial add(Polynomial other)throws Exception/多项式相加 public Polynomial subtraction(Polynomial other)throws Exception/多项式相减 public double result(double x)throws Exception 详细设计 Item类： public class Item private double c;/系数private int e;/指数public Item()public Item(double c,int e)this.c=c;this.e=e;public void setC(double c)this.c=c;public void setE(int e)this.e=e;public double getC()return c;public int getE()return e;public double resultItem(double x)return getC()*fac(x,getE();private double fac(double x,int e)/求x的e次方,当e为整数时if(e=0) return 1;return x*fac(x,e-1); Polynomial类： import java.util.*;public class Polynomial/多项式类 private LinList list;/单链表 public Polynomial() list=new LinList(0,null); public Polynomial(Item item)throws Exception /构造函数 int n=item.length; list=new LinList(n,null); if(n=0) return; initItem(item); try for(int i=0;in;i+) list.insert(i,itemi); catch(Exception e) private void initItem(Item item)/初始化Item数组，使其是按降序排序 int n=item.length; int max; for(int i=0;in;i+) max=i; for(int j=i+1;jitemmax.getE() max=j; if(max!=i) Item temp=itemi; itemi=itemmax; itemmax=temp; public int getItemNum()/获取项数 Object temp=list.head.getElement(); int n=-1; if(temp instanceof Integer) Integer i=(Integer)temp; n=Value(); return n; public void print()throws Exception/打印多项式 不空行 int n=getItemNum(); / System.out.println(n); if(n=-1) return ; if(n=0) System.out.print(0); return; boolean flag=true;/是不是输出第一项的标志 for(int i=0;i0) System.out.print(+c+x+temp.getE(); else if(c0) System.out.print(c+x+temp.getE(); flag=false; public void println()throws Exception/打印多项式 空行 print(); System.out.println(); public LinList getLinList()/获取单链表 return list; public void printPolynomial()throws Exception/只打印项数、系数和指数 int n=getItemNum(); if(n=0) return ; System.out.print(n+,); for(int i=0;in;i+) Item item=(Item)this.getLinList().getData(i); if(i!=n-1) System.out.print(c+i+=+item.getC()+, +e+i+=+item.getE()+, ); else System.out.print(c+i+=+item.getC()+, +e+i+=+item.getE(); System.out.println(); public Polynomial add(Polynomial other)throws Exception/多项式相加 LinList otherList=other.getLinList(); int n1=getItemNum();/该多项式的项数 int n2=other.getItemNum();/另一个多项式的项数 if(n2=0) return this; if(n1=0) return other; Polynomial temp=new Polynomial(); int i=0,j=0; while (+in1 & jn2) Item item=new Item(); Item item1=(Item)list.getData(i); Item item2=(Item)otherList.getData(j); double c1=item1.getC();/获得系数 double c2=item2.getC(); int e1=item1.getE();/获得指数 int e2=item2.getE(); if(e1=e2)/相等时 double c=c1+c2; item.setC(c); item.setE(e1); i+; j+; else if(e1e2)/不相等时 指数的大的增加 item=item2; j+; else item=item1; i+; try if(item.getC()=0)/当得到项的系数为0时就没有必要加入 continue; temp.getLinList().insert(temp.getLinList().size(),item); catch(Exception e) /将没有参加比较的项加进去，注意比较之后 有且只有一个有多余的项 while(in1) Item item1=(Item)list.getData(i); try temp.getLinList().insert(temp.getLinList().size(),item1); catch(Exception e) i+; while(jn2) Item item1=(Item)otherList.getData(j); try temp.getLinList().insert(temp.getLinList().size(),item1); catch(Exception e) j+; temp.getLinList().head.setElement(temp.getLinList().size();/设置项数 return temp; public Polynomial subtraction(Polynomial other)throws Exception/多项式相减 int n=other.getItemNum(); if(n=0) return this; Polynomial temp=new Polynomial(); LinList l=temp.getLinList(); for(int i=0;in;i+) Item item =(Item)other.getLinList().getData(i); double c=-1*item.getC();/取反 l.insert(i,new Item(c,item.getE(); l.head.setElement(n);/设置项数 return add(temp); public double result(double x)throws Exception double sum=0; int n=getItemNum();/该多项式的项数 if(n=0) return 0; for(int i=0;in;i+) Item item=(Item)list.getData(i); sum+=item.resultItem(x); return sum; Test1类： import java.io.*;import java.util.Scanner;public class Test1 Scanner scanner =new Scanner(System.in);public static void main(String args)throws Exception Test1 test1=new Test1(); Scanner scanner1 =new Scanner(System.in); while(true) System.out.println(请输入你要操作的系号：n+ 1)输出多项式n+ 2)多项式相加n+ 3)多项式相减n+ 4)计算多项式在x处的值n+ 5)退出); String s=scanner1.next(); int t=-1; try t=Integer.parseInt(s); catch(Exception e) switch(t) case 1:test1.printPolynomial();break; case 2:test1.add();break; case 3:test1.subtraction();break; case 4:test1.resultOfPolynomia();break; case 5:System.exit(0);break; default:System.out.println(你输入的操作有误，请重试n);continue; private void printPolynomial()throws Exception/选择1时 System.out.println(请输入要输出的多项式的信息：); Item item=creatItemShuZu(); Polynomial p=new Polynomial(item); p.printPolynomial();private void add()throws Exception/选择2时 System.out.println(请输入第一个多项式的信息：); Item item1=creatItemShuZu(); Polynomial p1=new Polynomial(item1); System.out.println(请输入第二个多项式的信息：); Item item2=creatItemShuZu(); Polynomial p2=new Polynomial(item2); Polynomial p=p1.add(p2); System.out.print(); p1.print(); System.out.print()+(); p2.print(); System.out.print()=); p.print(); System.out.println(); private void subtraction()throws Exception/选择3时 System.out.println(请输入第一个多项式的信息：); Item item1=creatItemShuZu(); Polynomial p1=new Polynomial(item1); System.out.println(请输入第二个多项式的信息：); Item item2=creatItemShuZu(); Polynomial p2=new Polynomial(item2); Polynomial p=p1.subtraction(p2); System.out.print(); p1.print(); System.out.print()-(); p2.print(); System.out.print()=); p.print(); System.out.println(); private void resultOfPolynomia()throws Exception/选择4时 System.out.println(请输入要输出的多项式的信息：); Item item=creatItemShuZu(); Polynomial p=new Polynomial(item); System.out.println(请输入x=); double x=scanner.nextDouble(); System.out.println(p.result(x);private Item creatItemShuZu()throws Exception/构造多项式数组 System.out.print(项数n=);int n=scanner.nextInt();double c=new doublen;int e=new intn;Item item=new Itemn;System.out.print(请输入各项的系数：);for(int i=0;in;i+) ci=scanner.nextDouble();System.out.print(请输入各项的指数：);for(int i=0;in;i+) ei=scanner.nextInt();for(int i=0;in;i+) itemi=new Item(ci,ei); return item; 调试分析本程序主要的操作对象是记录数组，使用的存储结构是结构体数组。另外还有对C语言中关于文件的操作，这是本程序中的一个重点也是难点，是此程序出现问题的主要原因之一：问题一：现象：输出的成绩不是正确的数字，而是一些类似于地址值的数字。原因：程序中对各数组的下标操作不统一。因为程序要分别对三个科目的成绩进行统计，所以程序中就要有一个临时数组来存放成绩值，然而在将学科成绩存放在临时数组的过程中如果出现了下标不统一的情况，即在原记录数组中是1n号元素存放数据,在临时数组中却是0n-1号元素存放数据。就会引起程序的错误。解决的方法是将整个程序中相互有关的数组使用统一的下标存放数据，就可以避免这种问题。问题二：现象：这是一个关于文件操作的问题。在将记录存入文件以后再从文件中读取时就出现错误。原因：在使用fwrite和fread命令的时候函数的参数没有写正确。fwrite和fread 命令的第一个参数是存储数据的首地址，如果没有地址没有正确，那么就不能正常地将数据存到文件中也不能正常地读取。运行结果及分析1. 初始界面：2. 输出多项式测试：输入数据： 输出结果：3、多项式相加测试：输入2后：输入第一个多项式后：输入第二个多项式后：结果：4、多项式相减与相加类似，这里就不举例。5、计算多项式在x处的值测试： 输入4后：输完多项式和x的值后结果：三、课程设计题目二 2 迷宫问题问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求（1） 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2） 编写递归形式的算法，求得迷宫中所有可能的通路；（3） 以方阵形式输出迷宫及其通路。（选做）概要设计public class InterSection/路口类 /行列指定路口的位置int row;/行下标int col;/列下标int w;/0和1分别表示迷宫中的通路和障碍public InterSection(int r,int c,int w1)Maze:public class Mazepublic InterSection getFirstNeighbor(InterSection p)/取路口point的第一个邻结点 若不存在返回null 类似于图的下一个邻结点/只要有一个路口的w值为 那么这两个路口就不相通public InterSection getNext(InterSection p1,InterSection p2)/按顺时针获取的 public boolean depthSearch(InterSection point)throws Exception/递归 public String answer(InterSection p)throws Exception/非递归 通过堆栈来实现public void printMaze()/打印迷宫详细设计public class MazeInterSection point;/路口的二维数组InterSection exit;/出口的那个路口int row;/迷宫的行数int col;/迷宫的列数boolean visited;/构造迷宫public Maze(int p,int r,int c)/r行数 c列数 row=r+1; col=c+1; point=new InterSectionrowcol; /将0列的全部设为阻碍 for(int k=0;kr;k+) pointk0=new InterSection(k,0,1); /将0行的全部设为阻碍 for(int k=0;kr;k+) InterSection temp=new InterSection(0,k,1); point0k=temp; for(int i=0;ir;i+) for(int j=0;jc;j+) pointi+1j+1=new InterSection(i+1,j+1,pij); visited=new booleanrowcol; for(int i=0;irow;i+) for(int j=0;jcol;j+) visitedij=false;public InterSection getFirstNeighbor(InterSection p)/取路口point的第一个邻结点 若不存在返回null 类似于图的下一个邻结点/只要有一个路口的w值为 那么这两个路口就不相通int r=p.row;int c=p.col;int w=p.w;visitedrc=true;if(w=1) return null;/ if( c+1col & pointrc+1.w=0 & !visitedrc+1) return pointrc+1;/向左 即东if(r+1=0 & pointrc-1.w=0 & !visitedrc-1 ) return pointrc-1;/向右 即西if(r-1=0 & pointr-1c.w=0 & !visitedr-1c) return pointr-1c;/向上 即北return null;/连通不到下一个路口public InterSection getNext(InterSection p1,InterSection p2)/按顺时针获取的int r1=p1.row;int c1=p1.col;int r2=p2.row;int c2=p2.col;if(r2r1 & c1=c2)/p2在该点上方时if(c2+1=0 & pointr2-2c2.w=0) return pointr2-2c2;if(r2-1=0 & c2-1=0 & pointr2-1c2-1.w=0) return pointr2-1c2-1;if(r2=r1 & c1c2 )/在该点右方时 if(r2+1=0 & pointr1c2-2.w=0) return pointr1c2-2; if(c2-1=0 & r1-1=0 & pointr1-1c2-1.w=0) return pointr1-1c2-1;if(r2r1 & c1=c2 & c2-1col )/在该点下方时 if(c2-1=0 & pointr1c2-1.w=0 ) return pointr1c2-1;if(r2-2=0 & pointr2-2c2.w=0 ) return pointr2-2c2;if(r2-1=0 & c2+1c2 & r2-1col )/在该点左方时 if( r2-1=0 & pointr2-1c1.w=0) return pointr2-1c1; if( c2+2col & pointr2c2+2.w=0) return pointr2c2+2; if( r2+1row & pointr2+1c1.w=0) return pointr2+1c1; return null; public boolean depthSearch(InterSection point)throws Exception/递归 int r=point.row; int c=point.col; / System.out.print(+point.row+,+point.col+) ); if(r=exit.row & c=exit.col)/出口 System.out.print(+point.row+,+point.col+) ); return true; visitedrc=true; InterSection temp=getFirstNeighbor(point); while(temp!=null) if(!visitedtemp.rowtemp.col) if(depthSearch(temp) System.out.print(+point.row+,+point.col+) ); return true; temp=getNext(point,temp); return false; public String answer(InterSection p)throws Exception/非递归 通过堆栈来实现SeqStack stack=new SeqStack(50);String s1=;String s2=;visitedp.rowp.col=true;stack.push(p);while(stack.notEmpty()InterSection temp=(InterSection)stack.pop(); visitedtemp.rowtemp.col=true; s1+=(+temp.row+,+temp.col+) ; if(temp.row=exit.row & temp.col=exit.col) return s1; s2=s1;InterSection u=getFirstNeighbor(temp);while(u!=null & !visitedu.rowu.col)if(!visitedu.rowu.col)s2+=(+u.row+,+u.col+) ;visitedu.rowu.col=true;if(u.row=exit.row & u.col=exit.col) return s2;stack.push(u);u=getNext(temp,u);return 没有通路;public void printMaze()/打印迷宫 for(int i=1;i10;i+) for(int j=1;j9;j+) System.out.print(pointij.w+ ); System.out.println(); /*/public class InterSection/路口类 /行列指定路口的位置int row;/行下标int col;/列下标int w;/0和1分别表示迷宫中的通路和障碍public InterSection(int r,int c,int w1)row=r;col=c;w=w1;运行结果及分析1. 初始界面及结果：四、课程设计题目三成绩分析问题问题描述录入、保存一个班级学生多门课程的成绩，并对成绩进行分析。基本要求(1)通过键盘输入各学生的多门课程的成绩，建立相应的文件input.dat。(2)对文件input.dat中的数据进行处理，要求具有如下功能：1) 按各门课程成绩排序，并生成相应的文件输出。2) 计算每人的平均成绩，按平均成绩排序，并生成文件。3) 求出各门课程的平均成绩、最高分、最低分、不及格人数、6069分人数、7079分人数、8089分人数、90分以上人数。4) 根据姓名或学号查询某人的各门课成绩，重名情况也能处理。(3)界面美观。概要设计Student类： public class Student String number;String name;int math;int english;int computer;public Student(String num,String n,int m,int e,int c)number=num;name=n;math=m;english=e;computer=c;public Student()name=;number=;math=0;english=0;computer=0;public int getSum()return math+english+computer;public double getAverage()double d=getSum()/3.0;d=(int)(d*10